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

We consider a variant of Ouroboros where the random bits necessary for selecting the slot leaders for the next epoch come from a per-epoch random value, plus the random values from a certain prefix of the blocks issued in the current epoch. Because the random values do not depend on the contents of the block, the adversary cannot maliciously choose a block-content that affects the leader selection. He, however, has one of three options:

1. Issuing a block and attaching it to the longest available chain
2. Not issuing a block
3. Issuing a block but linking it to a shorter, possibly malicious chain. If an honest block is bypassed by this maneuver, we say the adversary has skipped an honest player

We are interested in giving an upper bound to the expected number of competing chains that the adversary can possibly present to the leader selection process. This number would limit the choices for even a computationally-unbounded adversary. Not surprisingly, we call this number the grinding power of the adversary.

Competitive Chains. If the adversary has to “sell” a manipulated chain to an honest player $h$ at the end of an epoch, the chain has to satisfy the following:

1. It has to be competitive. That is, it has to be at least as large as the number of honest users preceding $h$ because these honest players will always add a new block to the longest available chain. Otherwise, there is no chance that $h$ will select this chain.
2. Moreover, every prefix of this chain, ending in an honest block, must be competitive for the same reason.

Towards a Formal Definition.  A characteristic string $w$ is a Boolean string where a zero denotes an honest player and a one denotes an adversarial player. Suppose $w \in \{0,1\}^n$ contains $m$ zeros located at increasing positions $z_1, \cdots, z_m \in [n]$. Set $z_{m+1} := 0$ because we assume that an honest player is going to be presented with the outcomes dictated by $w$. A substring of $w$ can only be obtained by deleting bits from $w$. For any string $s$, let $s\vert_k$ be the first $k$ bits of $s$. Let $\text{suffix}(w, k)$ be the suffix of $w$ starting at position $k$. Let $s_i$ denote the $i$th bit in a string $s$.

Let $Z(s)$ and $W(s)$ denote the number of zeros and ones in a string $s$, respectively. Define $D(s) := W(s) - Z(s)$ as the discrepancy of $s$. Fix $w, n = \vert w \vert$ and $m := Z(w)$. Let $[a,b]$ denote a closed interval. We write $w[a,b]$ to refer to the substring $w_a w{a+1} \cdots w_b$. Let $W(a,b)$ and $Z(a,b)$ denote the number of ones and zeros, respectively, in the interval $w[a,b]$. Let $\overset{\leftarrow}{s}$ denote the reverse string of any string $s$.

Definition (Admissible strings and grinding power). Let $w$ be an $n$-bit Boolean string containing $m$ zeros. Let $z_k$ be the $k$th zero-bit in $w$. Let $s = w(S)$ be the substring of $w$ supported on a characteristic vector $S \in \{0,1\}^n$. $s$ is “‘admissible” if the following hold:

1. $\vert s \vert \geq m$, and
2. If $s$ contains $z_k$ but not $z_{k-t}$, then $s$ must contain at least $t$ one-bits from the interval $[z_{k-t}, z_k]$.

The number $g(w) := \vert \{ S \subset [m] \mid w(S) \text{ is admissible } \} \vert$ is called the “grinding power” of $w$.

The second constraint says that $\text{suffix}(s, i+1)$ must include at least one one-bit from $\text{suffix}(w, i+1)$ for every $i$ such that $w_i = 0$ but $s_i = 0$ i.e., an honest player is skipped. The first constraint takes care of the case that the last zero-bit is skipped.

Let us make one more definition before we proceed.

Definition (ZPDC strings). Given Boolean string $s$, consider a string $s^\prime$, with $\vert s^\prime \vert = \vert s \vert$, which obeys the following rule: if $s_i = 0$ then

1. $s^\prime_i = 0$, hence we say $s^\prime$ is pinned on the zeros of $s$; and
2. The discrepancy of the suffix of $s^\prime$ beginning at $i$ is nonnegative.

We call $s^\prime$ a zero-pinned discrepancy-constrained string, or a ZPDC string for $s$ in short. Let $h(s)$ denote the number of possible ZPDC strings for $s$.

Towards an Expression for $g(w)$

For an index set $x \subset [m]$, let $g_x$ be the number of admissible substrings that contain the zero-bits from the positions indexed by $x$. That is, if $x = x_1x_2\cdots x_k$, $g_x$ considers the substrings which contain zero-bits from $w$-positions $\{z_k\}$ where $k \in x$.

Boundary values. For completeness, set $x_0 := 0, x_{\vert x \vert+1} := n$ and z_0 := 0, z_{m+1} := n+1\$.

Claim. The grinding power  is

$\displaystyle g(w) \,:=\, \sum_{x \subseteq [m]}g_x$, where

$\displaystyle g_x \,: =\, \prod_{\ell \geq 1}^{\vert x \vert + 1} h( w[I_\ell ] )\,$ and

$I_{\ell} := [x_{\ell-1}, x_{\ell}]\, .$

Explanation. Every subset $x \subseteq [m]$ of the $m$ zero-bits of $w$ gives rise to a family of substrings, each containing the zero-bits indexed by $x$. A fixed subset $x$ partitions $w$ into $\vert x \vert 1$ intervals. The admissible substrings pertaining to $x$ exclude the zero-bits that are interior to these intervals.

All zero-bits of $w$ are turned off inside the interval $I$. However, if we look at any suffix of $w[I]$, at least one one-bit must be “on” in the admissible string to render a zero-bit “off.” Consider the characteristic vector of the one-bits of an admissible string restricted to the interval $I$, and let us call it $a[I]$. It will certainly have zeros where $w[I]$ has zeros. Since these zeros are “off” in the admissible string, every suffix of $a[I]$ rooted at these zeros must have a nonnegative discrepancy. That is, suppose $\text{suffix}(w[I], i)$, rooted at a zero-bit, has $k$ zeros in it. Then $\text{suffix}(a[I], i)$ will contain at least $k$ ones. This condition can be stated as the discrepancy of every suffix of $a[I]$, rooted at zeros of $w[I]$, is nonnegative. $h(w[I])$ is the number of such ZPDC strings (see the definition above).

The boundary values above ensure that the expression works for all intervals, especially the first and the last. This leads to the following.

The number of admissible strings for a characteristic string $w$, which we call $g(w)$, is the same as the number of ways we can partition $w$ into intervals $\{I\}$ using subsets of the zero-bits of $w$, times the number of ZPDC strings for each interval $w[I]$ in each partition.

What is Next?

Naturally, we would like to give an upper bound to this number. Moreover, we want to bound the expectation of this number when $w$ is drawn from the Binomial distribution with a biased probability $\Pr[w_i = 1] = (1-\epsilon)/2$.

While I don’t know how to do that at this moment, I’ll tackle that in a future post.

References