Fully-Fluctuating Participation in Sleepy Consensus

Our first result establishes the utility of the external adversary model by showcasing a separation from the standard adversary model. Namely, consider the case where participation of both honest and corrupt nodes decreases over time. In particular, for any point in time, future honest participation may be eclipsed by current corrupt participation. Recent work [21] showed that in this setting, no protocol can be secure in the presence of an adversary that can carry out key transfer.

Our first result shows that against an external adversary, a consensus protocol resilient to decaying participation is not only feasible, but can be made highly efficient and requires only standard cryptographic assumptions.

Thm.˜6 establishes the strength of the external adversary model from the lens of protocol design, allowing us to obtain provable security guarantees known to be impossible under the standard notion of an adversary, that is able to carry out the key transfer attack. We now turn our attention to the more general setting of fully-fluctuating participation, in which participation of honest and corrupt nodes can both increase and decrease over time, to the discretion of the adversary. Designing a protocol secure in the fully-fluctuating setting in a relaxed adversary model was explicitly stated as an open problem in [21]. We show that with the help of VDFs, one can design an efficient consensus protocol for the fully-fluctuating participation setting, secure against an external adversary.

Tab.˜1 summarizes our contributions and gives full context of previous work using the formal notation we introduce in Sec.˜2. See Sec.˜6 for an in-depth overview of related work.

Even in non-sleepy synchrony settings [27], any consensus protocol must assume that the adversary is limited in corrupting only a minority of the participants. The sleepy model, being a generalization of the traditional setting, clearly must also abide by an assumption of similar flavour. Note further that in the sleepy model, the awake/asleep status of every node at every point in time is also dictated by the adversary. Thus the changing nature of node participation in the sleepy model makes such an assumption non-trivial to state. Arguably the minimal assumption one could make, is that at each point in time, honest participation exceeds corrupt participation. E.g., this is the assumption for which Nakamoto consensus [23] is proven secure in the proof-of-work setting. In the translation to proof-of-stake, however, such a minimal assumption forces any purported protocol to be resilient against the following two attack vectors. We emphasize that these attacks remain a concern in the external adversary model, and are described to go through within the confines of the model. To envisage the attack vectors in a tangible manner, we consider here as a running example the proof-of-stake version of Nakamoto consensus.

• $\mathrm{■}$

  Backward simulation. (Fig.˜2(a)) Consider the following. The adversary commences the protocol at time $0$ with low participation of both corrupt and honest nodes. As time goes on, the adversary increases participation of corrupt (and respectively, honest) nodes until at some point in time $t$, corrupt participation at time $t$ exceeds honest participation at timeslot $0$ by a sufficiently large amount. At this point, the corrupt nodes, via a costless simulation attack, can construct a private chain whose length exceeds the length of the honest chain constructed thus far. From the point of view of a newly woken up honest node at time $t$, the longest chain rule will cause it to build on top of the corrupt chain, violating safety. Such an attack is a concern in periods of increasing participation.

• $\mathrm{■}$

  Forward simulation. (Fig.˜2(b)) Alternatively, consider the following scenario. Participation starts out high, and as time goes on, the adversary puts corrupt (and honest, respectively) nodes to sleep until at some time $t$, the number of awake corrupt nodes at time $0$ exceeds honest participation at time $t$ by a sufficiently large amount. Assume further that the leader order is predictable from time $0$. The corrupt nodes awake at time $0$ can simulate an execution from time $0$ to time $t$ with a consistent participation rate equal to the number of corrupt nodes awake at time $0$. From the point of view of a newly woken up honest node at time $t$, the longest chain rule will cause it to build on top of the corrupt chain, violating safety. Such an attack is a concern in periods of decreasing participation.

In this work, we devise several tools to deal with such attack vectors.

We define a new primitive in the context of the sleepy model, which might be of independent interest, which we call wakeness vectors. Intuitively, wakeness vectors allow nodes to have an estimate on the timeslots in which other nodes were awake throughout the execution a protocol. A similar idea was explored by Bar-Joseph, Keidar, and Lynch [4] in the context of crash failures. Both of our protocols (for the decaying setting, and the fully-fluctuating setting) begin with establishing that the respective models we consider allow the nodes to implement wakeness vectors of sufficient quality. The construction of these vectors employs different techniques in each of the settings. See Sec.˜4 and Sec.˜5 for an in-depth overview of the main ideas behind the construction of wakeness vectors for the decaying and fully-fluctuating settings, respectively, along with the formal proofs. Armed with this primitive, we then show how can be used to to secure protocol against forward/backward simulation attacks, and enhance protocols in the sleepy model to remain secure amidst decaying/fully-fluctuating participation.

For our protocols (Thms.˜6 and 8) we actually prove a more general statement than discussed above. We identify key properties, which most existing protocols in the literature satisfy, that are necessary for a protocol to be compatible with our techniques, and then prove that any such protocol can be augmented to be secure amidst fully-fluctuating or decaying participation, in the presence of an external adversary. In the next section (Sec.˜2), we pour rigor into above discussion by formally defining the models and problems we consider in this work.

Intuitively, a protocol is said to be stateless if an honest nodes action depends on messages it received from nodes it has deemed to be awake in recent timeslots. We assume w.l.o.g. that in any protocol $\mathrm{\Pi }$, honest node keep a local view of wakeness vectors. Note that these vectors are not necessarily $d$-valid for any $d$. Such a property depends on the model and protocol in question. We further assume w.l.o.g. that honest nodes always attach the current timeslot to their messages.

Intuitively, this property captures the adversary’s ability to predict the contents of the log of honest nodes at some future timeslot.

Let $\mathrm{\Pi }$ be the protocol given in the premise of Lem.˜5. The protocol we construct is described in Alg.˜1. The protocol is divided into epochs, each of length $\alpha$. Each node that wakes up, reconstructs the contents of the log inductively starting from the first epoch. The inductive step is then implemented by each honest node ignoring all messages regarding blocks of epoch $e$ that do not extend a block of epoch $e-1$ confirmed by the node. This is formalized as described in Alg.˜1. In Alg.˜1, the notation $v_p^i[e]$ corresponds to all coordinates of $v_p^i$ corresponding to epoch $e$. First we prove the following property of Alg.˜1.

We prove this by induction over the epochs. Denote by $t$ the current timeslot. For $e=0$, the wakeness vector statement is trivial, i.e., whenever $v_q^i[e=0]=1^{\alpha }$ for an honest node $q$ for some $i$, then node $i$ was awake at timeslot at least $0$. For ${ℒ}_q^{\ast }$, Let $B$ be a block in ${ℒ}^{\ast }$ that extends the genesis block, this implies that $q$ observed a majority of decide messages for $B$ amongst all decide messages it received for blocks extending the genesis block. This includes all the honest nodes awake during epoch $0$, by line 16 of Alg.˜1. By the $(10\alpha ,\mathrm{\infty },\rho )$-sleepy model, the honest nodes awake during epoch $0$ exceed the total number of corrupt nodes that are ever going to be awake during the execution. This implies that $p$ received a decide message for $B$ from at least one honest node $p$, i.e., $B\in ℒ({𝐄}_p^{t^{\prime }})$ for some timeslot , as required. The log ${ℒ}_q\ast$ contains the genesis block, and thus contains a block of $ℒ({𝐄}_p^t)$ of epoch $0$. For the induction step, consider the claim to be true for all epochs at most $\le e$, we prove the claim for epoch $e+1$. Let $q$ be an honest node awake at timeslot $t$ of epoch $\ge e+1$ and let $i$ be a node such that $v_q^i[e]=1^{\alpha }$. This implies that $q$ received a decide message from $i$ extending a block in ${ℒ}_q^{\ast }$ of epoch $e-1$. Consider the event $E$ in which $p_i$ was last awake during epoch $e^{\prime }\le e-5$. By the induction hypothesis, up to epoch $e-1$, all wakeness vectors stored by all honest nodes are $3\alpha$ valid. In particular, due to the $(T_{\mathrm{f}}=10\alpha ,\mathrm{\infty },\rho )$-sleepy assumption, and due to the $\alpha$-stateless property of $\mathrm{\Pi }$, we get that at least up to the end of epoch $e-1$, $\mathrm{\Pi }$ correctly solves the atomic broadcast problem, as by line 11 of Alg.˜1, all honest nodes consider messages from a set that has an honest majority. This allows us to invoke the $\alpha$-unpredictability of $\mathrm{\Pi }$, together with the second induction assumption, that assures us that ${ℒ}_q^{\ast }$ contains a block in $ℒ({𝐄}_q^t)$ of epoch $e-1$ to claim that the probability that $i$ could send to $q$ a block extending a block of epoch $e+1$ in ${ℒ}_q^{\ast }$ is $\mathrm{𝗇𝖾𝗀𝗅}(\lambda ,n)$. This invokes the external adversary assumption, meaning that a message observed to be from $i$ can be sent only by $i$ (or other corrupt node) at a timeslot in which $i$ is awake. Thus $E$ occurs with at most negligible probability. Applying a union bound over all corrupt nodes and over all timeslots during the execution horizon (both polynomial in $n,\lambda$) maintains this negligible probability, and proves the claim for the wakeness vectors. This guarantees the correctness of $\mathrm{\Pi }$ for epoch $e+1$ by its $\alpha$-stateless property. This implies that $ℒ$ is consistent between all honest nodes at timeslot $t$. Now we must prove that at iteration $e$, a block of epoch $e$ in $ℒ({𝐄}_q^t)$ is added to ${ℒ}_q^{\ast }$, and no blocks that are not decided by some honest node are added.

Assume that for an honest node $q$ no block of epoch $e$ is added to ${ℒ}_q^{\ast }$ by the end of iteration $e$. This implies that there exists an honest node $p$, awake at timeslot $t-1$, that doesn’t have any blocks of epoch $e$ in $ℒ({𝐄}_p^{t-1})$. This again holds by the induction assumption of ${ℒ}^{\ast }$ for iteration $e-1$, the $3\alpha$-validity of the wakeness vectors, the $\alpha$-unpredictability of $\mathrm{\Pi }$, and the $(10\alpha ,\mathrm{\infty },\rho )$-sleepy execution. All these imply that $q$ is hearing from an honest majority, even when restricted to honest nodes awake at timeslot $t-1$. So if all honest nodes awake at timeslot $t-1$ had a block of epoch $e$ decided, consistency of $\mathrm{\Pi }$ would imply that it is added to ${ℒ}^{\ast }$ for $q$ at line 9 of Alg.˜1.

This event can only happen with negligible probability, as otherwise we contradict the $\alpha$-unpredictability of $\mathrm{\Pi }$, as the adversary at round $t-\alpha -1$ had already seen all blocks of epoch at most $e-1$ communicated between honest nodes, including the transcript of the protocol, and all messages received by $p$, and could thus compute $ℒ({𝐄}_p^{t-1})$ with non negligible confidence. Thus except for with negligible probability, all honest nodes awake at timeslot $t-1$ have a block of epoch $e$ decided, and thus this block is added to ${ℒ}^{\ast }$ by $q$ at timeslot $t$ by the behaviour of the protocol and the induction assumption. Lastly, again since $q$ hears from an honest majority, we get that every block $B$ added to ${ℒ}_q^{\ast }$ was decided by at least one honest node, i.e., added to $ℒ({𝐄}_p^{t^{\prime }})$ for some honest node $p$ at a timeslot . $◀$ The $3\alpha$-validity of the wakeness vectors given by Lem.˜7, combined with the $(10\alpha ,\mathrm{\infty },\rho )$-sleepy executions, and the $\alpha$-statelessness of $\mathrm{\Pi }$, allow us to deduce that ${\mathrm{\Pi }}^{\prime }$ (Alg.˜1) solves the atomic broadcast correctly as required. Notice that block confirmation in ${\mathrm{\Pi }}^{\prime }$ coincides with block confirmation in $\mathrm{\Pi }$, and thus they have the same latency properties. The only added communication occurs in decision messages part of the protocol, and each message is of length $O(\lambda )$, thus the total communication blowup per timeslot is $O(\lambda n^2)$, as required. $◀$

All that is left to obtain Thm.˜6, is to observe that the protocol (specifically, Algorithm 3) of [21] (henceforth [21, Alg. 3]) is $O(\mathrm{\Delta })$-stateless, works in the $(\mathrm{\infty },\mathrm{\infty },\frac{1}{2})$-sleepy model (see Thm.˜11). It can be augmented to be $O({\log }^2\lambda )$-unpredictable with an incredibly simple change to the GPE invocation part of the protocol, which we describe in Alg.˜2. In words, each honest node, when inputting a block $B$ to ${\mathrm{𝖦𝖯𝖤}}_{𝗏}$, simply includes in its $\mathrm{𝗌𝖾𝖾𝖽}$ a VRF computation on the current timeslot and the parent block of $B$. This ensures that the contents of each block contain a component with high entropy, thus making the logs of honest nodes unpredictable.

More formally, the augmented algorithm is described in Alg.˜2, with the red lines indicating changes from the original pseudo-code. Due to the simplicity of the change, and not to burden the write up with the technical details of [21, Alg. 3], we provide below a sketch of the proof argument. [21, Alg. 3] is divided into views, each consisting of $O(\mathrm{\Delta })$ timeslots, during which an attempt to agree on this next block in the log is executed. This attempt is captured by the GPE procedure, which is executed once every view. By the properties (in particular, validity) of the GPE subroutine (see Def.˜4) and the behaviour of [21, Alg. 3], w.p. at least $\frac{1}{2}$, at the end of the GPE subroutine, all honest nodes decide a block proposed by an honest node into their log. Conditioned on this event, the contents of $O_{\mathrm{V}}(\mathrm{𝖼𝖺𝗇𝖽𝗂𝖽𝖺𝗍𝖾},t)$ are uniformly random and unpredictable to any adversary not awake before the beginning of the current view. In particular, the adversary $𝒜$ attempting at timeslot $t$ to guess the contents of the log of any honest node, succeeds w.p. at most $\frac{1}{2^{\lambda }}$. As different GPE executions are independent, we get that after $O(\lambda )$ views, condition 3 in Def.˜4 is invoked except w.p. $\frac{1}{2^{\lambda }}$. Thus in total, the probability that an adversary at timeslot $t$ can correctly guess the contents of the log of any honest node at timeslot $t+O(\lambda \mathrm{\Delta })$ is at most $\frac{1}{2^{\lambda }}$, as required. $◀$

We prove this by induction on $t$. For $t=0$, the claim is trivial since a node that wasn’t awake at any time $\ge 0$ can not send any messages. Assume that node $p$ received a valid depth-$t$ value $\mathrm{𝗏𝖺𝗅}$ from $q$, for $q$ that was not awake at any timeslot $\ge t$. Denote the corresponding nodes and values by $p_1,\mathrm{\dots },p_{t-1}=q$, ${\mathrm{𝗏𝖺𝗅}}_0,\mathrm{\dots },{\mathrm{𝗏𝖺𝗅}}_{t-1}$. Note that in particular, ${\mathrm{𝗏𝖺𝗅}}_{t-1}$ is a valid depth-$(t-1)$ value w.r.t. $p$, sent by $p_{t-2}$, and thus by the induction assumption, it was sent by $p_{t-2}$ at timeslot $t^{\prime \prime }\ge t-1$.

Now assume that $\mathrm{𝗏𝖺𝗅}$ was sent by $p_{t-1}$ at a timeslot , this means that $p_{t-1}$ had not yet received ${\mathrm{𝗏𝖺𝗅}}_{t-1}$ from $p_{t-2}$. Denote by $Q$ the total number of queries to the VDF oracle made by any node by timeslot $r$, that number is bounded by $r\cdot n\cdot p(n,\mathrm{\Pi })$, in particular, the probability that ${\mathrm{𝗏𝖺𝗅}}_{t-1}$ appeared as the valid output of a VDF oracle at timeslot $\le r$ is at most $\frac{r\cdot n\cdot p(n,\mathrm{\Pi })}{2^n}$, and thus as long as $r=o(2^n)$, w.h.p. $p_{t-1}$ could not have computed $O_{\mathrm{D}}(p_{t-1},{\mathrm{𝗏𝖺𝗅}}_{t-1},\cdot )$ before timeslot $r$, for any . Thus w.h.p. $p_{t-1}$ could have computed $O_{\mathrm{D}}(p_{t-1},{\mathrm{𝗏𝖺𝗅}}_{t-1},\cdot )=\mathrm{𝗏𝖺𝗅}$ only after $p_{t-2}$ sent ${\mathrm{𝗏𝖺𝗅}}_{t-1}$, which occurred at timestep at least $t-1$, i.e., $p_{t-1}$ could have only queried $O_{\mathrm{D}}(p_{t-1},{\mathrm{𝗏𝖺𝗅}}_{t-1},\cdot )$ at timestep at least $t-1$, and received a response at timestep at least $t$ due to the behavior of $O_{\mathrm{D}}$, thus $p_{t-1}$ sent $\mathrm{𝗏𝖺𝗅}$ at timestep at least $t$, and was thus awake at timestep at least $t-1$, as required. $\mathrm{⊲}$

The full algorithm is depicted in Alg.˜3, specifically in the wakeness vector updates and VDF chain extension parts.

With Clm.˜13 in mind, the main observation is that to prove the lemma, it suffices to prove that at every timeslot, every honest node extends a valid VDF chain of at least one other honest node. Notice that this is necessary as well, as otherwise, consider the following case involving 3 nodes $p_1,p_2,p_3$.

1. 1.

   Node $p_3$ is corrupt and awake at timeslot $1$, node $p_1$ is honest and awake at timeslot $2$, node $p_2$ is honest and awake at timeslot $3$.

2. 2.

   Node $p_3$ computes ${\mathrm{𝗏𝖺𝗅}}_1=O_{\mathrm{D}}(p_3,{\mathrm{𝗏𝖺𝗅}}_0,1)$, and sends it to $p_1$, but not to $p_2$.

3. 3.

   By instructions of some protocol $\mathrm{\Pi }$, $p_1$ computes ${\mathrm{𝗏𝖺𝗅}}_2=O_{\mathrm{D}}(p_1,{\mathrm{𝗏𝖺𝗅}}_1,2)$ and broadcasts it.

Note now that $p_2$ by timeslot $3$ did not receive ${\mathrm{𝗏𝖺𝗅}}_1=O_{\mathrm{D}}(p_3,{\mathrm{𝗏𝖺𝗅}}_0,1)$, and thus in particular, w.h.p. ${\mathrm{𝗏𝖺𝗅}}_2$ is not considered a valid depth-$2$ value w.r.t. to $p$, even though $p_1$ was indeed awake at timeslot $2$.

The trivial solution to this would be to instruct each honest node $p$ to extend the VDF chains it received from all nodes, thus extending all honest node’s chains. However, this incurs a multiplicative $n$ cost in communication. A better approach, and the one we implement in Alg.˜3, is to let each honest node $p$ sample $O({\log }^2(n\cdot t))$ of the nodes it received valid depth-$t$ VDF computations from, and extend those chains, thus guaranteeing that except with negligible probability, at least one of the chosen nodes is honest (due to the honest majority assumption in any admissible execution) and that for all $t$, except with negligible probability all honest nodes at all timeslots $t$ observe valid chains from all honest nodes for the appropriate timeslots they were awake.

We prove this by induction on the timeslot. The base case of $t=0$ clearly holds as all honest nodes have valid wakeness vectors. Assume correctness for $t$ and consider time $t+1$, let $p$ be an honest node awake at time $t$. By the induction assumption, $p$ had valid wakeness vectors, and so $p$ set $v_p^i[t-1]=1$ for all honest nodes $i$ awake at time $t-1$. In particular, by the behavior of the protocol, this implies that $p$ observed valid depth-$(t-1)$ w.r.t. all honest nodes $i$ awake at time $t-1$. Furthermore, the validness of the wakeness vectors of $p$ at timeslot $t$, the set of nodes $i$ for which $v_p^i[t-1]=1$ has an honest majority. As such, by lines 11, 12 of Alg.˜3, when $p$ chooses $O({\log }^{2}n)$ random nodes amongst these, the probability of an honest node not being chosen is at most $2^{{\log }^{2}n}=\mathrm{𝗇𝖾𝗀𝗅}(n)$. Thus w.h.p. $p$ extends in round $t$ a valid depth-$(t-1)$ chain sent by an honest node, which implies that at round $t+1$, all honest nodes see a valid depth-$t$ honest chain from $p$, and thus set $p$ as being awake in their wakeness vectors, as required. This proves the completeness of the wakeness vectors at time $t+1$, i.e., that for all honest $q$ awake at time $t+1$, and all and all honest $p$ awake at time $t^{\prime }$, we have that $v_q^p[t^{\prime }]=1$. The soundness of the wakeness vectors at time $t+1$ is implied by Clm.˜13. This completes the induction argument and concludes the proof. $◀$

Denote the given protocol in the premise of Lem.˜10 by $\mathrm{\Pi }$. Lem.˜9 proves that wakeness vector updates and VDF chain extension correctly implement valid wakeness vectors. Which in turns implies, due to the $(T_{\mathrm{b}},T_{\mathrm{b}},\rho )$-sleepy model, that $\mathrm{\Pi }$ is executed by every honest node by only considering messages from an honest majority at every timeslot. By the $T$-stateless property of $\mathrm{\Pi }$, we thus have that $\mathrm{\Pi }$ solves the atomic broadcast problem correctly. Thus ${\mathrm{\Pi }}^{\prime }$ inherits $ϵ$-Safety, and $(ϵ,\mathrm{\ell })$-Liveness from $\mathrm{\Pi }$. Protocol ${\mathrm{\Pi }}^{\prime }$ decides blocks when $\mathrm{\Pi }$ decides them, thus the expected latency of ${\mathrm{\Pi }}^{\prime }$ can not be worse than that of $\mathrm{\Pi }$, and implementing wakeness vector updates and VDF chain extension requires an additive $O(\lambda n^2{\log }^{2}n)$ overhead in communication at every timeslot, as required. $◀$