# Concurrent Honest Slot Leaders in Proof-of-Stake Blockchains

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.

# Our Paper on Realizing a Graph on Random Points

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:

# 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)]$.

# Random Walk on Integers

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.

# 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.

# 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.

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?

# Vandermonde Submatrices and Arithmetic Progressions

[This post, which is based on an ongoing discussion with Alex Russell and Ravi Sundaram, contains some unpublished results.]

Currently, we are asking whether all submatrices of the order-$p$ Vandermonde matrix over a finite extension of $GF(2)$ are invertible where $p$ is prime. The answer is “no” in general: there are examples of fields where the Vandermonde matrix has a singular submatrix.

We can ask an easier(?) question, though. What happens if we randomly sample a set of columns and look into submatrices formed by a subset of the sampled columns. With a touch of beautiful insight, Professor Russell has connected Szemeredi’s theorem on arithmetic progressions with this question.

Let $AP_k$ denote an arithmetic progression of length $latek k$. Let $[N] := \{1, 2, \cdots, N\}$ for $N \in \mathbb{N}$.

The Szemerédi theorem says, any “sufficiently dense” subset $S \subset [N]$ contains infinitely many $AP_k$ for all $k \in \mathbb{N}$. A finitary version says: Fix your favourite $k \in \mathbb{N}, \delta \in [0, 1]$. Then,  there exists a natural $N := N_{k, \delta}$ such that if you look any subset $S \subset [N]$ of size at least $\delta N$, you will find an $AP_k$. Yet another version says:

Szemerédi’s Theorem. The size of the largest subset $S \subset [N]$ without an $AP_k$ cannot be too large; in particular, it is $o(N)$.

Recall that a function $f(x)$ is $o(g)$ if it grows too slow compared to $g(x)$, so that $\lim_{N\rightarrow \infty}{f(x)/g(x) = 0}$.

# Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code

To this day, no method of finding a generator of $Z_p^*$ is known to be more efficient than essentially trying 2, then 3, and so on. Who cares? Well, the difficulty of breaking a certain public key cryptosystem (due to El Gamal) depends on the difficulty of working with generators of $Z_p^*$.Keith Conrad

An $n$th root of unity in a finite field $F$ is an element $r \in F$ satisfying $r^n=1$, where $n$ is an integer. If $n$ is the smallest positive integer with this property, $r$ is called a primitive $n$th root of unity. If $r$ is a primitive $n$th root of unity, then all elements in the set $\mu_n = \{1, r, r^2, \cdots, r^{n-1}\}$ are also roots of unity. Actually, the set $\mu_n$ form a cyclic group of order $n$ under multiplication, with generator $r$.

Problem: Suppose you are given a finite field $F=GF(2^d)$ of degree $d$, and you are promised that there indeed exists a primitive $p$th root of unity $r\in F$ for $p$ prime. Find $r$, and in particular, produce a C++code that finds it.

In what follows, we talk about how to find such a root and provide my C++ code; the code uses the awesome NTL library.

# Spectral Sparsification by Spielman and Srivastava: How They Connected the Dots

In this post, I will discuss my own understanding of the spectral sparsification paper by Daniel Spielman and Nikhil Srivastava (STOC 2008). I will assume the following:

1. The reader is a beginner, like me, and have already glanced through the Spielman-Srivastava paper (from now on, the SS paper).
2. The reader has, like me, a basic understanding of spectral sparsification and associated concepts of matrix analysis. I will assume that she has read and understood the Section 2 (Preliminaries) of the SS paper.
3. The reader holds a copy of the SS paper while reading my post.

First, I will mention the main theorems (actually, I will mention only what they “roughly” say).