Simplex is a partially synchronous Byzantine Fault Tolerant (BFT) protocol designed by Ben Chan and Rafael Pass in 2023. Part of its design is being adopted by Solana. It is a simple and clean protocol, especially for beginners, and Ben did a great job explaining it from scratch. But if you are already familiar with other BFT protocols such as PBFT or Tendermint, you may be wondering how Simplex differs and what its core innovation is. This post is my attempt at understanding Simplex in relation to prior partially synchronous protocols.
In this post, I will start from Tendermint and modify a variant of Tendermint into Simplex. I should clarify that this is most likely not how Ben and Rafael came up with Simplex. But it is a helpful exercise (at least for me) to understand the key idea in Simplex.
For simplicity, I will focus on single-shot consensus. The protocol adopts the standard setting and techniques of partially synchronous BFT:
- n parties, f < n/3 Byzantine,
- increasing views starting from view 1,
- a designated leader per view, who sends a proposal,
- two rounds of all-to-all voting
- quorum certificates (cert for short) for locking
- the lock-decide paradigm
Let Cert(k, x) denote a collection of n-f votes from view k for value x. For convenience, we think of an empty string as Cert(0, x) for any x. Let Δ be the message delay upper bound after GST. All messages are signed and sent to all.
Upon entering view k:
Everyone starts a local timer T
Leader waits for 2Δ time if k > 1
Leader sends (Propose, k, x, Cert(k’, x)) for the highest k’
Upon receiving the first (Propose, k, x, Cert(k’, x)) in view k
Send (Vote, k, x) if having seen no cert from a view higher than k’
Upon receiving n-f (Vote, k, x) in view k // Denote them Cert(k, x)
Send (Finalize, k, x)
Forward Cert(k, x)
Upon receiving n-f (Finalize, k, x)
Decide x
Forward these n-f (Finalize, k, x)
Terminate
Upon T = 6Δ in view k
Send (View-change, k)
Exit view k
Upon receiving n-f (View-change, k)
Forward these n-f (View-change, k)
Enter view k+1
Here are some main takeaways from the above protocol. First, the main idea of Tendermint is that an honest party refuses to vote if it has a higher cert than the one in the leader’s proposal. This ensures safety. Here is a proof sketch. If some honest party decides x in view k, then n-2f honest parties have seen Cert(k, x). They will refuse to vote for any x’ != x in the next view, so Cert(k+1, x’) cannot form. Safety holds by induction.
Second, the above design necessitates a crucial step in Tendermint: the leader needs to wait for 2Δ time before proposing, because we need an honest leader post-GST to receive every honest party’s reported cert. Otherwise, it is possible that some honest party p holds a high cert that the honest leader is unaware of. Then, p will refuse to vote for the honest leader, breaking liveness. The wait is set to 2Δ because post-GST, a party may enter the view up to Δ later than the leader and it takes up to Δ time for its cert to reach the leader. (As a side note, despite the 2Δ wait, Tendermint can achieve optimistic responsiveness.)
That also explains why the view-change timeout is 6Δ: Δ for the leader to enter the view, 2Δ leader wait, and Δ delay for each of the three messages (Propose, Vote, Finalize). If a party does not decide within 6Δ, it requests a view-change. Upon receiving sufficient view-change requests, a party enters a new view.
We are now ready to modify the protocol into Simplex. I have marked the changes in bold with numbered notes.
Upon entering view k:
Everyone starts a local timer T
Leader waits for 2Δ time if k > 1 // Change #3
Leader sends (Propose, k, x, Cert(k’, x)) for the highest k’
Upon receiving the first (Propose, k, x, Cert(k’, x)) in view k
Send (Vote, k, x) if having seen n-f (View-change, l) for all k’ < l < k // Change #2
Upon receiving n-f (Vote, k, x) in view k // Denote them Cert(k, x)
Send (Finalize, k, x)
Forward Cert(k, x)
Enter view k+1 // Change #1
Upon receiving n-f (Finalize, k, x)
Decide x
Forward these n-f (Finalize, k, x)
Terminate
Upon T = 3Δ in view k // Change #4
Send (View-change, k)
Exit view k
Upon receiving n-f (View-change, k)
Forward these n-f (View-change, k)
Enter view k+1
The core innovation of Simplex lies in Changes #1 and #2. First, when an honest party sends Finalize in view k, it moves to the next view right away, so it will never send (View-change, k). Note also that if an honest party sends (View-change, k), it exits view k and will never send Finalize in view k. By the standard quorum intersection argument, this means n-f (View-change, k) and n-f (Finalize, k, *) are mutually exclusive. In other words, n-f (View-change, k) serve as a proof that no decision occurred in view k. This property is a novelty of Simplex to my knowledge and is crucial for Simplex.
In particular, this property enables Change #2. An honest party will vote for the leader’s proposal if it has seen n-f View-change messages for every view higher than the leader’s cert, even if it has seen a higher cert. This behavior would be unsafe in Tendermint. It is safe in Simplex because n-f View-change messages from a view serve as a no-decision proof for that view.
Changes #3 and #4 are natural consequences of the previous two changes. Since an undetected higher cert no longer breaks liveness, the leader no longer needs to wait 2Δ before proposing. With the 2Δ wait removed and Change #1, the view-change timeout can be reduced to 3Δ.
We have now arrived at the single-shot Simplex protocol. (For the multi-shot version, see the Simplex paper, Simplex blog post, or Victor Shoup’s paper.)
What efficiency improvement does Simplex achieve over previous protocols? That turns out to be a tricky question. A comprehensive and accurate answer would be long and complicated. Roughly speaking, Simplex’s advantage over PBFT is that a leader’s proposal is smaller. Simplex’s advantage over Tendermint is the shorter view-change timeout (3Δ instead of 6Δ), so each faulty leader can waste less time.
Acknowledgment. The author thanks Giulia Scaffino and Kartik Nayak for their suggestions on improving the post.