How Much Public Randomness Do Modern Consensus Protocols Need?

By Abraham et al. [1], any protocol that is secure against a strongly adaptive adversary must use $\mathrm{\Omega }(n^2)$ bits of communication. This bound is known to be tight in the setting of a computationally bounded adversary by the work of Abraham et al. [2]. The protocol of this work also achieves optimal $O(1)$ round complexity, in expectation.

On the road to circumventing the lower bounds of [1, 6], various relaxations to the strongly rushing adversary have been considered.

• $\mathrm{■}$

  A typical relaxation is that if the adversary chooses to corrupt a player $p$ at round $r$, player $p$ still performs the honest behaviour of round $r$ prior to the adversary taking control of $p$ (at which point the adversary can send additional messages, still in round $r$). Protocols achieving $o(n^2)$ communication complexity under this assumption include the work of King and Saia [26], and the follow up work by King, Lonargan, Saia and Trehan [25] in which they show protocols with $O(n^{1.5})$ communication complexity. Additional cryptographic assumptions allow the design of protocols with nearly linear communication complexity [8, 11, 2, 9]. Another class of protocol circumventing the communication lower bound of [1] are motivated by blockchain applications, and make use of proof-of-work or proof-of-stake assumptions [16, 32].

• $\mathrm{■}$

  Another line of work considers a late adaptive adversary. Roughly, this is an adaptive adversary with an outdated view of the state of the protocol. At each round the adversary may choose players to corrupt based on all information available so far, however the actual corruption occurs several rounds later. Most of these works consider relaxed variants of the consensus problem, e.g., almost-everywhere consensus [36, 4, 3, 27].

• $\mathrm{■}$

  A mobile blocking adversary has been considered previously in [36], and is generally related to the well studied model of omission failures [30, 23].

As mentioned, the idealized randomness beacon assumption, also known as a common coin, is extensively used in consensus protocol design in asynchronous networks (See [31] and references within). A recent work [23] studies a similar question to ours. Specifically, they consider protocols secure against an adaptive omission failure adversary, and characterize the trade-off between the required number of oracle calls to a random beacon and the round complexity.

We let $\lambda$ denote the security parameter. If a function $f(\lambda )$ is $O(1/\mathrm{𝗉𝗈𝗅𝗒}\left(\lambda \right))$ for every polynomial in $\lambda$, we say $f$ is negligible in $\lambda$. We write $f=\mathrm{𝗇𝖾𝗀𝗅}\left(\lambda \right)$. We let $\log (x)$ denote the logarithm base 2 of $x$. If $X$ is a random variable over domain $\mathrm{\Omega }$, and $\mathrm{Supp}\left(X\right)=\{x\in \mathrm{\Omega }\mid \mathrm{Pr}[X=x]>0\}$, we denote the min-entropy of $X$ by $H_{\mathrm{\infty }}(X)={\min }_{x\in \mathrm{Supp}\left(X\right)}\frac{1}{\mathrm{Pr}[X=x]}$.

We consider a network of $n$ players (eq. nodes or participants). We focus here on the permissioned setting, in which the set of $n$ players is fixed and known to all players in advance. At most $f$ players can be corrupt. We further assume that communication takes place over a synchronous network with maximum message delay of $\mathrm{\Delta }$, i.e. a player $p$ at round $t$ has received all messages sent to it up to round $t-\mathrm{\Delta }$. For simplicity of exposition, we assume that $\mathrm{\Delta }=1$, but all our results extend naturally to the general case of delay parameter $\mathrm{\Delta }$. Throughout the paper we consider two models for a communication network. In the peer-to-peer model, players may send different messages to different players during each round. In the broadcast model, players (including corrupted players) may only broadcast a message, which is received by all other players.

Specifically, the latter model does not allow corrupt players to equivocate. Our lower bound holds even in the more generous broadcast model, and our upper bounds hold even in the more general peer-to-peer model of communication.

All of the adversaries considered in the paper are computationally unbounded, and in particular we assume no PKI (though we do assume authenticated channels between participants). Specifically, we consider three types of adversaries, static, adaptive, and mobile blocking. Let $f$ be the adversary’s corruption budget. It is useful for us to consider an adversary as a pair of algorithms $𝒜=({𝒜}_0,{𝒜}_1)$, where ${𝒜}_0$ is responsible for choosing the identities of up to $f$ corrupted players at every round $t$, and ${𝒜}_1$ is the adversary participating in the protocol. A bit more formally, at each round $t$, ${𝒜}_0$ may observe $(\mathrm{\Pi },t,{\mathrm{Tr}}_t)$ and output a set ${ℱ}_t$ of at most $f$ players. Here, $\mathrm{\Pi }$ is a description a protocol and ${\mathrm{Tr}}_t$ refers to the transcript of a protocol up to round $t$ (see Definition 2). Each adversary type we consider imposes different restrictions on either ${𝒜}_0$ or ${𝒜}_1$.²²2One might ask about the possibility of a mobile adversary capable of corruption, but this is tricky to reason about as it requires a notion of “un-corrupting” players.

• $\mathrm{■}$

  Static. The static adversary chooses the identities of $f$ corrupt players at round $t=0$, and this choice is fixed throughout the execution of the protocol. The adversary has complete control over the behaviour of the corrupted players. In other words ${ℱ}_t={ℱ}_0$ for all $t$. There are no restrictions on ${𝒜}_1$.

• $\mathrm{■}$

  Adaptive. At the beginning of each round $t$, the adversary chooses the identities of players to corrupt in that round, based on its observations of the transcript of the protocol and the players it has corrupted thus far. These players stay corrupted for the rest of the execution. In other words, ${ℱ}_t\subseteq {ℱ}_{t+1}$ for all $t$. There are no restrictions on ${𝒜}_1$.

• $\mathrm{■}$

  Mobile blocking. A mobile blocking adversary can, at every round, observe $(\mathrm{\Pi },t,{\mathrm{Tr}}_t)$, where $t$ is a round, and ${\mathrm{Tr}}_t$ is the transcript of $\mathrm{\Pi }$ up to round $t$, and output a set ${ℱ}_t$ of at most $f$ players that are prohibited from sending messages at round $t$. We emphasize that unlike the adaptive adversary which is constrained by the total number of corruptions, the mobile adversary may corrupt up to $f$ players in each round regardless of how many players it has corrupted in the past. A mobile blocking adversary is also captured by the $({𝒜}_0,{𝒜}_1)$ notation via ${𝒜}_0(\mathrm{\Pi },t,{\mathrm{Tr}}_t)=S$, and ${𝒜}_1$ be an adversary behaviour in which corrupted players send no messages.

In any adversary variant, we say that an adversary corrupting at most $f=\rho n$ players is $\rho$-bounded.

The protocols we consider in this work have two main sources of randomness. For both of them, we assume an ideal functionality as our goal is to reason about the nature and amount of randomness required to design consensus protocols.

1. 1.

   Common Random String (CRS). We assume that at round $t=0$, an arbitrarily long (as per the protocol’s specification) uniformly random string $\mathrm{𝖢𝖱𝖲}$ is revealed to all players. A static adversary must choose the identities of corrupt players prior to the CRS being revealed. An adaptive or mobile adversary can choose the identities of corrupt players after $\mathrm{𝖢𝖱𝖲}$ is revealed.

2. 2.

   Randomness Beacon. A randomness beacon is an oracle that at every round $t$, produces a fresh uniformly random string ${\mathrm{𝗌𝖾𝖾𝖽}}_t$ of an arbitrary length (as per the protocol’s specification). In particular, for each round $t$, an adaptive or a mobile adversary must choose the identities of corrupted players prior to the revelation of ${\mathrm{𝗌𝖾𝖾𝖽}}_t$.

Clearly, in the presence of an adaptive adversary the latter source of randomness is significantly more powerful than the former. It is precisely the latter source of randomness that is the main focus of this paper.

Similarly to prior work [26, 8], we assume that communication channels in our network are authenticated. Intuitively, this means that each player knows the identity of the sender for any message received. This can be formalized by instantiating communication channels with a map that maps a message $m$ to the tuple $(m,p)$, where $p$ is the sender of $m$. This mapping is fixed and can not be tampered with by the adversary.

An execution is a tuple $E=(\mathrm{\Pi },𝒜,r)$ where $\mathrm{\Pi }$ is the protocol run by honest players. $𝒜$ is a particular adversary, i.e. $𝒜$ is an algorithm that chooses corrupt players (only at $t=0$ if static, otherwise ${𝒜}_0$ chooses at every round $t$) based on the transcript of the protocol and internal state of corrupt players, and instructions for the behaviour of the environment. $r$ denotes the random coins of all players. Given a protocol $\mathrm{\Pi }$ we say that $E$ is an execution of $\mathrm{\Pi }$ if the first component of $E$ is $\mathrm{\Pi }$.

We say that an execution is admissible in the adaptive model if for all rounds $t\ge 0$ it holds that . In the static model we further demand that the identities of corrupt players remain fixed throughout the execution of the protocol. At times we abuse notation and refer to an execution also as the random variable $(\mathrm{\Pi },𝒜)$ which is a distribution over executions in which $\mathrm{\Pi }$ is the protocol run by honest players, and $𝒜$ is the adversary (corrupt players in each round, and actions taken by them). We denote this random variable by $E_{𝒜}$.

The specification of the consensus problem we consider takes the form of the well known Byzantine Agreement problem [33, 28].

In the $\mathrm{𝖡𝖠}$ task, $n$ players must come to an agreement on a bit under some constraints. Each player $P_i$ has an input $b_i\in \{0,1\}$, and produces an output $o_i\in \{0,1\}$. We say that a protocol $\mathrm{\Pi }$ solves the $\mathrm{𝖡𝖠}$ task if the following three properties are guaranteed by $\mathrm{\Pi }$, except for with $\mathrm{𝗇𝖾𝗀𝗅}\left(\lambda \right)$ probability.

1. 1.

   Termination. There exists $t$ such that all honest players have produced an output by round $t$.

2. 2.

   Agreement. For any pair of honest players $P_i,P_j$, the probability (over the randomness of the adversary and the protocol) that these players output different values is at most $\mathrm{𝗇𝖾𝗀𝗅}\left(\lambda \right)$.

3. 3.

   Validity. If all honest players have the same input bit $b$, then all honest players always output $b$.

An additional critical notion relating to a $\mathrm{𝖡𝖠}$ protocol is latency, which is defined as follows. Intuitively, latency captures the expected number of rounds it takes for $\mathrm{\Pi }$ to terminate.

In this paper, we consider an $\mathrm{\ell }$-bit randomness beacon to be an $n$-party protocol ${\mathrm{\Pi }}^{𝒪}$ with access to a random oracle $𝒪$ that satisfies termination and agreement and, on input $1^{\lambda }$, outputs a string $s$ of length $\mathrm{\ell }(\lambda )$. Furthermore, the value output by the honest parties must be computationally indistinguishable from random, in the random oracle model. In other words, the adversary responsible with distinguishing between the uniform distribution and the output of the beacon is only bounded in its number of queries to the random oracle, but not in any other manner. In particular, it can perform arbitrary computation. More precisely, let $𝒜$ be any (computationally unbounded) adversary corrupting $f$ out of $n$ players. Let ${ℬ}^{𝒪}$ by any computationally bounded distinguisher, making $poly(\lambda )$ queries to the random oracle $𝒪$. Denote by $v\leftarrow {\mathrm{\Pi }}_{𝒜}^{𝒪}$ the output of the honest parties from an execution of $\mathrm{\Pi }$ with the adversary $𝒜$. For any such $𝒜,{ℬ}^{𝒪}$ it must hold that:

We say that ${\mathrm{\Pi }}^{𝒪}$ is secure against a static/adaptive/mobile blocking adversary if the above holds and $𝒜$ is a static/adaptive/mobile blocking adversary respectively. We note that the definition of a randomness beacon varies throughout the literature; here, we consider a weak notion where the adversary corrupting parties during the protocol execution is different from the adversary attempting to distinguish the beacon output from random. This notion is still nontrivial.

Assume towards a contradiction that there exist a constant $c>0$ and an adversary $𝒜=({𝒜}_0,{𝒜}_1)$ such that

Now for each $t\in \mathbb{N}$, denote by $k_t$ the value . Applying $f(x)=\frac{1}{2^x}$ to both sides of the inequality above, we get that

Thus, by definition of min-entropy, we have that there exist strings $S_t,t\in \mathbb{N}$ s.t.

We thus have that

where the first transition is by definition of the probability of event intersection. Since $I_{E_{𝒜}}^t$ is a part of ${\mathrm{Tr}}_{E_{𝒜}}^t$, we thus get that there exists set ${\widehat{I}}_t,t\in \mathbb{N}$ s.t.

Now note that an adversary ${𝒜}_2$ that predicts at round $t$ the set ${\widehat{I}}_t$ can realize this success probability, thus violating the global leader unpredictability condition, as required. Such an adversary is realizable both in the adaptive and mobile blocking models since the adversary at round $t$ has definitive knowledge of the transcript up to and including round $t-1$, including $\mathrm{𝖢𝖱𝖲}$. $◀$

We would now like to prove that the lack of the global unpredictability condition, combined with low communication, implies susceptibility to attacks by adaptive adversaries. With the notion of a transcript in hand, we can also now formally define the relevant notion for this paper of low communication.

The goal of defining uniform communication, as opposed to just considering the general number of bits exchanged between players in the protocol, is to speak rigorously about protocols in which only a few players speak in each round. We now aim to prove the following theorem, which says that any $\mathrm{𝖡𝖠}$ protocol in which few players speak in every round, uses low beacon entropy, and is adaptively secure, requires many rounds. In other words, no $\mathrm{𝖡𝖠}$ protocol can simultaneously be efficient, adaptively secure, and use low beacon entropy.

By the assumption that $\mathrm{\Pi }$ does not satisfy global leader unpredictability, we deduce that there exist a polynomial $p(n)$ and adversaries $𝒜=({𝒜}_0,{𝒜}_1)$ and ${𝒜}_2$ such that

Now consider the following adversary $ℬ=({ℬ}_0,{ℬ}_1)$, acting as follows. Let $r=O(1)$ be the number of initial rounds which may have high communication complexity. In the following, we employ a well-known result [13], which states that any $\mathrm{𝖡𝖠}$ protocol with $r$ rounds has error probability of at least $\mathrm{\Omega }(\frac{1}{n^r})$, with the adversary needing to corrupt at most $r$ players [13]. In our case, $\mathrm{\Omega }(\frac{1}{n^r})=1/n^{O(1)}$.

1. 1.

   For the first $r$ rounds, employ the adversary strategy [13], corrupting at most $r$ players in the process.

2. 2.

   ${ℬ}_0$ acts as follows: At the beginning of any round $t>r$, use to obtain ${\widehat{I}}_{𝒜,{𝒜}_2}^t$. In the case of the adaptive adversary, corrupt all the players in ${\widehat{I}}_{𝒜,{𝒜}_2}^t$ until the total number of corrupted parties has reached the corruption budget $\rho n$. In the case of a mobile blocking adversary, corrupt them for round $t$.

3. 3.

   ${ℬ}_1$ sends no messages by the corrupted players; that is, the players in ${\widehat{I}}_{𝒜,{𝒜}_2}^t$. Note that this is compatible behaviour with the mobile blocking adversary, in addition to the adaptive adversary.

From here on in, the analysis is conditioned on the event that ${𝒜}_2$ has guessed correctly the identity of speakers at all rounds, which occurs w.p. at least $\frac{1}{p(n)}$, by assumption. Due to the strategy of [13], we have that with at least inverse polynomial probability, $\mathrm{\Pi }$ does not solve $\mathrm{𝖡𝖠}$ up to round $r$ of the execution. For the following $\mathrm{\Omega }(\frac{\rho n}{k})$ rounds, no progress is made since the adversary corrupts all parties participating in the protocol for those rounds. Thus at least with inverse polynomial probability, $\mathrm{\Pi }$ requires $\mathrm{\Omega }(\frac{\rho n}{k})$ rounds, as required. In the case of a mobile blocking adversary, no progress is made at all, indefinitely, and so in particular the protocol either has no termination, or has error probability at least $\mathrm{\Omega }(\frac{1}{n^r\cdot p(n)})$, which is a contradiction. $◀$

We now show that global leader unpredictability implies a randomness beacon. This randomness beacon simply runs $\mathrm{\Pi }$ and computes the hash(i.e. queries the random oracle) of the identities that spoke in each round. Since these identities are unpredictable, given enough parties there is sufficient randomness to construct a beacon.

Let $𝒪:{\{0,1\}}^{\ast }\to {\{0,1\}}^{\lambda }$ be a hash function which we model as a random oracle. Let ${\mathrm{\Pi }}^{\prime 𝒪}$ be the protocol obtained by running $\mathrm{\Pi }$ and outputting the hash(i.e. querying the oracle $𝒪$) of the identities of the parties that speak in each round of $\mathrm{\Pi }$. Observe now that ${\mathrm{\Pi }}^{\prime 𝒪}$ trivially satisfies the first bullet point, since it involves only running $\mathrm{\Pi }$ and applying a function to its transcript. Since we operate in the broadcast setting with authenticated channels, all parties know these identities of speaking parties. Recall that global leader unpredictability states that this tuple of speaking parties has at least $c\log n$ min-entropy for any constant $c$. Therefore, for any fixed string $s$, the probability that this tuple of identities equals $s$ is at most $1/{\lambda }^c$ for any constant $c$. Let ${ℬ}^{𝒪}$ be a computationally bounded adversary making a polynomial number of queries to the random oracle $𝒪$. The probability that $ℬ$ queried the tuple of speaking parties to $𝒪$ is smaller than the inverse of any polynomial, which is negligible. Therefore, except with negligible probability the hash of the tuple of speaking parties is a freshly random value from the perspective of ${ℬ}^{𝒪}$. $◀$

All the proofs relating to security against an adaptive adversary in this section can easily be modified to work for a mobile blocking adversary, with the same protocols. The main observation is that against an adversary that can only silence players, none of our proofs use the property that the same parties are corrupted between rounds, and also that in our protocols, the actions of an honest player depend only on the messages received from the previous round, and not any other round in the past.

In modern blockchains, adaptive security is especially desirable to prevent bribery attacks or other attacks where nodes are temporarily compromised. In practice, modern blockchains often use randomness beacons to unpredictably elect leaders or committees. However, these randomness beacons come at a cost and add design and implementation complexity. Our work shows that efficient and adaptively secure protocols require beacons; this cost is in some sense unavoidable.

A natural next question is exactly how much randomness is needed from the beacon. Our possibility results show that the amount of entropy required is relatively low, growing only logarithmically in the number of parties. Therefore, using a beacon is unavoidable, yet this beacon can be relatively lightweight.

In this work, we have considered a computationally unbounded adversary and an information-theoretic setting. This choice mainly served to maintain the simplicity and clarity of the exposition. A natural alternative model is the PKI setting, with computationally bounded adversaries. Our positive results trivially extend to this setting, as information-theoretic security implies security against a computationally bounded adversary. Extending our lower bound is slightly more subtle, though we expect it to hold for a notion of pseudorandomness rather than statistical beacon entropy. We leave formalizing this analogous bound as an interesting direction for future work.

In this work, we restricted our attention to a special variety of low-communication protocols, specifically ones where the set of parties speaking in each round is small. This notion of communication efficiency is desirable in practice, and several protocols use a committee subsampling approach to this end (e.g., Algorand, Ethereum). However, one might also be interested in other notions of communication efficiency, for example the setting where communication is simply measured by the total number of bits exchanged by honest parties. An open question is whether our results stand in this alternate setting.