Can Simplex Keep A Secret?

In 2023, Simplex defined a new state of the art in responsive BFT consensus, and this is the core protocol upon which Commonware's Simplex module is designed. Commonware implements a variant of Simplex (C-Simplex) which includes some nuanced changes that turn out to be critical for embedding unpredictable onchain per-iteration randomness into the consensus protocol.

Simplex has been discussed in many contexts using different terminology, so in the interest of clarity we unify all terminology in this post to be as consistent as possible with the original paper. 3f+1 players, of whom up to f are byzantine, execute the Simplex protocol to reach consensus over a blockchain. Simplex advances through iterations (each uniquely identified by a positive integer h). Each iteration outputs a notarization (agreement between at least 2f + 1 players) over a blockchain of height h ending in dummy block ⊥_h and/or a notarization over blockchain of height h ending in non-dummy block b_h. The protocol also produces a finalization (agreement between at least 2f + 1 players) over a single notarized blockchain for each h.

Commonware's implementation differs in two key aspects from the original Simplex protocol without reducing security or responsiveness. First, it adds a new rule that after 2Δ time has elapsed without voting since entering an iteration, an honest player will send (Final, k, ⊥). As discussed in the blog post on C-Simplex (Commonware's implementation of Simplex), this reduces the silent view latency (i.e., the duration of an iteration when the leader does not broadcast any proposal) from 3Δ+δ to 2Δ+δ, where Δ is the upper bound of message delivery time and δ is the actual message delivery time (Δ > δ).

One additional change in C-Simplex that has not yet previously been discussed is a modification of the voting rule. We reproduce Step 3 of the original Simplex paper with this modification in bold red text below:

In the unmodified protocol, players vote for a proposal b_h if all of the following conditions hold: (1) it is the first non-dummy proposal received from the correct leader of the iteration, (2) the proposal includes a valid blockchain, and (3) the prefix (excluding b_h) is notarized. C-Simplex adds one additional check (4) the local timer T_h has not yet fired.

This modification in C-Simplex is not formally proven secure in the academic paper: honest players in C-Simplex do not vote on non-dummy proposals after voting for a dummy proposal within the same iteration, whereas honest players in Simplex do vote for such proposals. This change is intuitively safe because it can only reduce the number of votes in the protocol i.e., under certain conditions, an honest player will not vote on a proposal in C-Simplex that it would have voted for in Simplex. All voting patterns in C-Simplex are proven safe by the consistency proofs of Simplex.

The liveness of C-Simplex is less obvious, but it is still guaranteed as the local timer of any honest player will never fire in an iteration with an honest leader after GST.

This change is deceivingly simple, but actually has important implications regarding embedded VRFs and other binding commit/reveal schemes which rely on the unpredictability of a per-iteration random beacon. Commonware uses one such VRF in multiple contexts including leader election of Alto.

Interestingly, in Simplex, players may still vote for the leader's proposal after the timeout. This fact may be exploited by a malicious leader if the leader is incentivized to hold the proposal until after observing the notarization of the dummy block. For example, if the VRF entropy is revealed in the notarization of ⊥_h, it may be used by the malicious proposer to build block b_h! In C-Simplex, this behavior is disallowed, as no honest player would vote to notarize this malicious proposal after they have already voted to nullify the iteration.

Proving C-Simplex’s Liveness

Simplex uses a nonstandard network model that enables a "delightfully simple" proof of liveness, and to understand how C-Simplex is live it is important to first understand the formal network model.

Assuming an honest player p has sent a message at time t_p, that message will be delivered on or before time max(GST, t_p + δ). Put simply, an old message may not be delivered until exactly time = GST, and a message sent sufficiently close to or after GST will arrive within a delay of δ. Note that this definition of partial synchrony differs from the usual definition that messages are delivered on or before time max(GST, t_P) + δ; this distinction is very important in understanding the proof of liveness in Simplex.

For brevity, we discuss the proof of safety and liveness in the context of the corresponding proofs in the Simplex paper. The proofs for each lemma and theorem remain valid for C-Simplex with the exception of Lemma 3.5 Subclaim 3.1. We reproduce Lemma 3.5 Subclaim 3.1 below as it appears in the original paper, up to the point that the proof is invalid with respect to C-Simplex.

Lemma 3.5 (The Effect of Honest Leaders). Let h be any iteration with an honest leader L_h. Suppose that L_h entered iteration h by some time t > GST. Then, with all but negligible probability, every honest player will have entered iteration h+1 by time t + 2δ. Moreover, every honest player will see a finalized block at height h, proposed by L_h, by time t + 3δ.

Subclaim 3.1. Every honest player will see a notarized blockchain of height h, and thus enter iteration h + 1, by time t + 2δ (except with negligible probability)

Proof. Recall that L_h enters iteration h by time t. Thus, L_h must multicast a proposal for a new non-dummy block b_h by time t. Thus, by time t + δ (observing that t > GST), every honest player must have seen a valid proposal from the leader for b_h. There are now two cases:

• Case 1. Every honest player p casts a vote ⟨vote, h, b_h⟩_p by time t + δ. Subsequently, every honest player will see a notarization for b_h and thus a notarized blockchain of height h by time t + 2δ, if not earlier, and enter iteration h + 1, as required.

The proof of case 2 is not correct with respect to C-Simplex, so we modify the argument as follows:

• Case 2. There is some honest player p that did not multicast a vote ⟨vote, h, b_h⟩_p by time t + δ. However, by Lemma 3.4, every honest player should have entered iteration h by time t + δ, so the only ways that the honest player p did not multicast a vote ⟨vote, h, b_h⟩_p by time t + δ are:
  • Case (a) p entered iteration h + 1 before time t + δ. Lemma 3.4 states that every honest player will also enter iteration h + 1 by time t + 2δ which is consistent with Subclaim 3.1.
  • Case (b) p's local timer T_h has been fired before time t + δ. We will show that if L_h entered iteration h by time t > GST, then any honest player p's local timer can never fire before time t + δ in iteration h. To see this, we first show that p must enter iteration h after time t - δ. Otherwise, if p enters iteration h at a time before t - δ, then by Lemma 3.4, L_h must also enter iteration h exactly at time GST, which contradicts the assumption that t > GST. Consequently, because p enters iteration h after time t - δ, and because the p's local timer is set to 2∆ > 2δ, p's local timer cannot fire before time t + δ. (Notice that C-Simplex adds an additional timer at 2∆). 

The proof of case (b) is elegantly captured by the below diagram (adapted from the Simplex paper to include the C-Simplex 2∆ timer), showing that our additional constraint on voting does not affect the claim of Lemma 3.5.

 * Note that the original Simplex protocol uses a timeout of T_h = 3∆, whereas C-Simplex adds an additional timeout of T_h = 2∆. The proof of Lemma 3.5 is applicable in both cases.

Authors: Thomas Kim (LayerZero), Brendan Kobayashi Chou (Commonware), Patrick O'Grady (Commonware), Hao Chung (LayerZero), Saeid Yazdinejad (LayerZero), Ryan Zarick (LayerZero)

This post was co-written by LayerZero Labs and Commonware, with review and input from Joachim Neu (a16z) and Andrew Lewis-Pye (Commonware + London School of Economics and Political Science).