Things I Want to Remember


Number Theory Coding Theory Probability/Combinatorics
Algebraic Graph Theory Linear Algebra Randomized Algorithms
Deviation Inequalities Complexity Theory Cryptography
Distributed Computing Optimization Series
Inequalities/Identities Papers



Notes on the PCP Theorem and the Hardness of Approximation: Part 1

In this note, we are going to state the PCP theorem and its relation to the hardness of approximating some NP-hard problem.

PCP Theorem: the Interactive Proof View

Intuitively, a PCP (Probabilistically Checkable Proof) system is an interactive proof system where the verifier is given r(n) random bits and he is allowed to look into the proof \pi in q(n) many locations. If the string x \in \{0,1\}^n is indeed in the language, then there exists a proof so that the verifier always accepts. However, if x is not in the language, no prover can convince this verier with probability more than 1/2. The proof has to be short i.e., of size at most q(n) 2^{r(n)}. This class of language is designated as PCP[r(n), q(n)].

Theorem A (PCP theorem). Every NP language has a highly efficient PCP verifier. In particular,

NP = PCP[O(\log n), O(1)].

Continue reading “Notes on the PCP Theorem and the Hardness of Approximation: Part 1”

Ouroboros Proof-of-Stake Blockchain Protocol: Assumptions and Main Theorems

Image Source: http://maxpixel.freegreatpicture.com/Coin-Money-Currency-Bitcoin-Electronic-Money-2729807
Bitcoin and blockchain protocols

A blockchain protocol is essentially a distributed consensus protocol. A Proof-of-Work protocol such as Bitcoin requires a user to show a proof  — such as making a large number of computations — before he can add a block to an existing chain. Proof-of-Stake protocols, on the other hand, would not require “burning electricity” since the ability to “mine” a coin would depend only on the user’s current stake at the system.

The growing computing power of the bitcoin miners is already consuming a significant amount of electricity. One can easily see the necessity of a provably secure and efficient cryptocurrency without the heavy energy requirement. However, it is easier said than done. So far, I am aware of only three Proof-of-Stake protocols which give provable security guarantees. These are Ouroboros, led by Aggelos Kiayias, Alex Russell, and others; Snow White, led by Rafael Pass and Elaine Shi; Ouroboros Praos from the Ouroboros team; and Algorand, led by Silvio Micali. There is also an open-source initiative to implement Ourorboros, named Cardano.

In this post, I am going to present the main theorems of Ouroboros.

Continue reading “Ouroboros Proof-of-Stake Blockchain Protocol: Assumptions and Main Theorems”

Notes On Unbiased Random Walks

Unbiased Random Walks (source:Wikipedia)
Unbiased Random Walks

Imagine that a particle is walking in a two-dimensional space, starting at the origin (0, 0). At every time-step (or “epoch”) n = 0, 1, 2, 3, \cdots it takes a \pm 1 vertical step. At every step, the particle either moves up by +1, or down by $altex -1$. This walk is “unbiased” in the sense that the up/down steps are equiprobable.

In this post, we will discuss some natural questions about this “unbiased random walk.” For example, how long will it take for the particle to return to zero? What is the probability that it will ever reach +1? When will it touch a for the first time? Contents of this post are a summary of the Chapter “Random Walks” from the awesome “Introduction to Probability” (Volume I) by William Feller.

Continue reading “Notes On Unbiased Random Walks”

Characterizing the Adversarial Grinding Power in a Proof-of-Stake Blockchain Protocol

[Contents of this post are based on an ongoing discussion with Alex Russell and Aggelos Kiayias. It contains potentially unpublished material.]

In a proof-of-stake blockchain protocol such as Ouroboros, at most half of the users are dishonest. While an honest user always extends the longest available blockchain, the dishonest users try to fool him into extending a manipulated blockchain. Here, the user who is allowed to issue a block at any time-slot is called the “slot leader.” As it happens, a number of future slot leaders are computed in advance using the random values present in the blocks. Although counterintuitive, such a scheme ensures that if the adversary does not control more than half the users now, it is very unlikely that he cannot control more than half the slot leaders. The time-slots are divided into “epochs” of length R.

Continue reading “Characterizing the Adversarial Grinding Power in a Proof-of-Stake Blockchain Protocol”

Forkable Strings are Rare

In a blockchain protocol such as Bitcoin, the users see the world as a sequence of states. A simple yet functional view of this world, for the purpose of analysis, is a Boolean string w = w_1, w_2, \cdots of zeros and ones, where each bit is independently biased towards 1 favoring the “bad guys.”

A bad guy is activated when w_t = 1 for some t. He may try to present the good guys with a conflicting view of the world, such as presenting multiple candidate blockchains of equal length. This view is called a “fork”. A string w that allows the bad guy to fork (with nonnegligible probability) is called a “forkable string”. Naturally, we would like to show that forkable strings are rare: that the manipulative power of the bad guys over the good guys is negligible.

Claim ([1], Bound 2). Suppose w =w_1, \cdots, w_n is a Boolean string, with every bit independently set to 1 with probability (1-\epsilon)/2 for some \epsilon < 1. The probability that w is forkable is at most \exp(-\epsilon^3n/2).

In this post, we present a commentary on the proof that forkable strings are rare. I like the proof because it uses simple facts about random walks, generating functions, and stochastic domination to bound an apparently difficult random process.

Continue reading “Forkable Strings are Rare”

Some Facts about the Gambler’s Ruin Problem

Consider a random walk in the two-dimensional discrete space, where the horizontal direction is indexed by nonnegative time steps and the vertical direction is indexed by integers.

A particle is at its initial position z > 0 at time 0. At every time step, it independently takes a step up or down: up with probability p and down with probability q = 1-p. If p = q the walk is called symmetric. Let p_z and q_z be the probabilities that the particle ever reaches some level a >z or 0, respectively. When it does, the walk stops. The quantity q_z is the ruin probability. We set the initial conditions as q_0 = 1, q_a = 0.

The Gambler’s Ruin Problem: What is the probability that a walk, starting at some z > 0, eventually reaches the origin?

Continue reading “Some Facts about the Gambler’s Ruin Problem”