Concurrent Honest Slot Leaders in Proof-of-Stake Blockchains

multi-honest-fork
A Proof-of-Stake blockchain execution where honest blocks have double borders and adversarial blocks have single borders. The nodes are labeled with their round numbers. Note that there are multiple adversarial blocks at rounds 2 and 4. Also, there are multiple honest blocks at rounds 6 and 9. These latter rounds were treated sub-optimally in all previous analyses, in part because the adversary could possibly use them to create inconsistent views for honest nodes. Our new paper closes this gap by putting forth a stronger analysis.

Consider the eventual consensus Proof-of-Stake (PoS) blockchains under the longest-chain rule such as Ouroboros, Ouroboros Praos, Sleepy Consensus, Snow White, etc. All existing analyses use a sub-optimal honest majority assumption in that if multiple honest nodes win the block-creation lottery in the same round, the analysis either treats it as a bad event or, at best, a neutral event.

In our paper, we put forth a consistency analysis that takes advantage of these events and thus achieves an asymptotically optimal consistency error under the optimal honest majority assumption; this is a first in the literature. The analysis applies to both synchronous communication and communications with a bounded delay.

This improvement is important since a sub-optimal honest majority assumption leads to weak security parameters for the blockchain system. The paper is going to appear at the prestigious conference IEEE ICDCS 2020. We posted the full version of our paper at https://eprint.iacr.org/2020/041.

 

 

Fractional Moments of the Geometric Distribution

In one of my papers, I needed an upper bound on the fractional moments of the geometric distribution. The integer moments have a nice-looking upper bound involving factorials. In addition, Mathematica showed that the same upper bound holds for fractional moments once we use Gamma function instead of factorials. The problem was, I could not prove it. Worse, I could not find a proof after much looking on the Internet.

This post contains a proof that for any real \lambda > 1, the \lambdath moment of a geometric random variable with success probability \displaystyle p \geq 1/2 is at most \displaystyle \Gamma(\lambda + 1)/p^\lambda.

Continue reading “Fractional Moments of the Geometric Distribution”

Our Paper on Realizing a Graph on Random Points

300px-Minimum_spanning_tree.svg
A minimum spanning tree. (image source)

 

Our paper, titled How to Realize a Graph on Random Points, has been accepted at CCCG (Canadian Conference on Computational Geometry) 2019. I’ll write more about it in future posts.

Abstract:

Continue reading “Our Paper on Realizing a Graph on Random Points”

Random Walk on Integers

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 -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” or “simple” 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. Also, this is an excellent reference.

Edit: the Biased Case. The biased walk follows

\displaystyle p:=\Pr[ \text{down}]\, ,\qquad q:=\Pr[ \text{up} ]\, ,\qquad p + q = 1.

The lazy walk follows

\displaystyle p:=\Pr[ \text{down}]\, ,\qquad q:=\Pr[ \text{up} ]\, , \qquad \Pr[stay] = r\, ,\qquad p + q = 1.

In the exposition, we’ll first state the unbiased case and when appropriate, follow it up with the biased case.

Continue reading “Random Walk on Integers”

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.

randwalk
A random walk starting at z, with absorbing barriers at zero and a. It goes up/down with probability p and q, respectively.

 

The 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 a be constant, a > z. If the walk reaches either a or 0, it stops. Define the two quantities below.

Escape Probability.

\displaystyle p_z := \Pr[ \text{walk reaches } a \text{ before hitting }0].

Ruin Probability.

\displaystyle q_z := \Pr[ \text{walk hits zero before hitting }a] .

It just so happens that given enough time, the walk either ruins or escapes. 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”

A Publicly Verifiable Secret Sharing Scheme

We all know Shamir’s (t,n)-Secret Sharing Scheme: A dealer fixes a group \mathbf{Z}_p and selects a random polynomial P(x) of degree at most t-1 over this group. He sets the constant coefficient equal to your secret \sigma, then distributes n arbitrary evaluations of this polynomial as shares to the n parties. Any subset of t parties can pool their shares and reconstruct the polynomial via Lagrange interpolation.

What if we don’t want to trust the dealer nor the parties? Feldman’s Verifiable Secret Sharing Scheme allows the dealer to publish, in addition to the regular Shamir-shares, a generator g of the group \mathbf{Z}_p^* along with t proofs or commitments c_j for each coefficient of the polynomial P(x). Each party can verify that his share is correct by testing whether

\displaystyle g^{P(i)}\, \overset{?}{=} \, \prod_j{c_j^{i^j}} \bmod p.

However, the shares p(i) are still private. What if we want everyone to be able to verify the correctness of all shares without knowing what the shares are? This is achieved by a Publicly Verifiable Secret Sharing Scheme, such as the one developed by Berry Schoenmaker, assuming the discrete log problem is hard.

Continue reading “A Publicly Verifiable Secret Sharing Scheme”

Two MDS Array Codes for Disk Erasures: the Blaum-Bruck-Vardy Code and the BASIC Code

In this post, I am going to review two erasure codes: the Blaum-Bruck-Vardy code and the BASIC code (also here). These are erasure codes, which means, their purpose is to encode a number of data disks into a number of coding disks so that when one or more data/coding disks fail, the failed disk can be reconstructed using the existing data and coding disks.

A strength of these codes is that although the algebra is described on extension fields/rings over GF(2), the encoding/decoding process uses only Boolean addition/rotation operation and no finite field operation. These codes are also MDS (Maximum Distance Separable), which means they have the largest possible (minimum) distance for a fixed message-length and codeword-length.

(Recall that if a code has d data components and c parity components in its generator matrix in standard form, its distance is at most c + 1 by the Singleton bound. Hence the code is MDS if and only if it can tolerate c arbitrary disk failures.)

The BASIC code does the following things in relations to the BBV code:

  1. Adds a virtual parity bit after each disk, giving each disk an even parity
  2. Does polynomial arithmetic modulo 1+x^p instead of h(x) = 1+x+\cdots + x^{p-1} as in the case of BBV code
  3. Shows equivalence to the BBV code by making a nice observation via Chinese Remainder Theorem
  4. Proves MDS property for any number of coding disks when p is “large enough” and has a certain structure

Open Question: What is the least disk size for which these codes are MDS with arbitrary distance?

Continue reading “Two MDS Array Codes for Disk Erasures: the Blaum-Bruck-Vardy Code and the BASIC Code”