Tendermint and Simplex are both leader-based BFT protocols for partial synchrony with optimal resilience and $3\delta$ good-case latency. There is a subtle tradeoff between them:
- In the optimistic responsive model, Simplex obtains a worst-case view latency of $3\Delta+\delta$ while Tendermint obtains a worst-case view latency of $4\Delta+\delta$.
- On the other hand, Tendermint requires only a bounded number of certificates to make progress in each view, while in Simplex the number of certificates may grow with the number of skipped views.
It is natural to ask:
Is there a protocol that obtains the best of both Simplex and Tendermint?
We show a modification of Simplex that makes it more like Tendermint. We call this protocol Complex.
Complex obtains worst-case view latency of $3\Delta+\delta$ (as good as Simplex) and requires just a constant number of certificates (as good as Tendermint).
We use the framework of our previous post on deconstructing Simplex to similarly deconstruct Complex into an outer shell and an inner shell. This allows us to derive Complex with relatively few changes.
The inner shell of Complex is similar to Simplex; in particular, it uses the same Graded-Broadcast. The outer shell of Complex is similar to Tendermint (and key-based HotStuff) with a small Simplex-like modification. Finally, the external-validity rule of Graded-Broadcast is similar to Tendermint: vote only if the proposed lock is at least as large as yours.
Complex outer shell
Each party maintains three sets: lockSet (lock certificates it directly delivered), keySet (all lock certificates it has seen, including forwarded ones), and skipSet (skip certificates it has delivered). Initially all three are empty.
For view v, the primary of view v with input (val, val-proof):
if keySet is not empty,
let p in keySet be the lock certificate of highest view w
if w = v-1
Graded-Broadcast (v, p.val, (p, ⊥))
otherwise (w < v-1)
let s in skipSet be the skip certificate for view v-1
Graded-Broadcast (v, p.val, (p, s))
otherwise
if v > 1
let s in skipSet be the skip certificate for view v-1
Graded-Broadcast (v, val, (val-proof, s))
otherwise (v = 1)
Graded-Broadcast (1, val, (val-proof, ⊥))
Note that checking that the certificate in the proposal is at least as large as the party’s lock is the essence of Tendermint’s safety rule. The small modification is also requiring a skip certificate for view v-1 when the lock is from a lower view.
Complex uses the following event handlers (certificates can arrive from Graded-Broadcast or be forwarded):
On first skip certificate for view v, add it to skipSet, and move to view v+1
On first lock certificate for view v, add it to lockSet, forward it to all parties, and move to view v+1
On first strong certificate, decide and forward it
On receiving a forwarded lock certificate for the first time, add it to keySet
The Complex voting rule is the external-validity function passed to Graded-Broadcast:
For view v:
if receive (v, p.val, (p,s)) check that p is a valid lock certificate
and that (p.view = v-1 or s is a valid skip certificate for view v-1)
and that does not exist lock in my lockSet with view r where
r > p.view and r ≠ v-1
if receive (v, val, (val-proof, s)) check that val-proof is a proof that val is valid
and that my lockSet is empty
and that s is a valid skip certificate for view v-1 (or that v=1)
In words, the proposal must be justified by a lock certificate that is either from the previous view or from an earlier view with a skip certificate, and the proposed lock must be at least as recent as any lock in the party’s lockSet that is not from the previous view.
Checking that the proposed lock is at least as recent as the party’s own lock (the maximality condition) is the essence of Tendermint’s safety rule. The small Simplex-like modification additionally requires a skip certificate for view $v-1$ when the proposed lock is from an earlier view, proving that no commit occurred in view $v-1$.
Recall that the main reason for the additional $\Delta$ wait in Tendermint is the hidden lock problem. Complex overcomes this in a novel way:
- If a hidden lock is from view $v-2$ or older, then it will be forwarded and seen, hence will not be hidden.
- A lock in view $v-1$ may be hidden from the leader of view $v$, but that means the leader of view $v$ will hold a skip certificate for view $v-1$. The leader can use this skip certificate to unlock the holders of certificates from view $v-1$.
Proving Complex
We now prove that Complex implements single-shot provable consensus with external validity. The proof uses the six properties of Graded-Broadcast together with the Complex voting rule and the outer-shell view-transition rule.
In fact, we will prove the stronger accountable-safety property for Complex.
Claim 1 (accountable safety)
Complex satisfies Provable Agreement via the stronger accountable safety property: any safety violation implicates at least $f+1$ identifiable faulty parties, and since at most $f$ parties are Byzantine, no violation can occur.
Let $k$ be the first view with a valid commit certificate for value $x$, and let $S_2$ be the $n-f$ parties that sent Final. If a valid lock certificate for value $x’ \neq x$ exists in any view $v \geq k$, then at least $f+1$ parties in $S_2$ demonstrably violated the Complex voting rule.
Grade Safety implies no skip certificate for view $k$ exists, and Uniqueness implies every valid lock certificate in view $k$ has value $x$. No lock for $x’ \neq x$ can form in view $k+1$ either: the only admissible proposal there uses a view-$k$ lock (no skip for view $k$ is available), which has value $x$ by Uniqueness.
| For the first view $v^- \geq k+2$ with a lock for $x’ \neq x$, let $L$ be its $n-f$ voters. Quorum intersection gives $ | S_2 \cap L | \geq n-2f > f$. Every $i \in S_2 \cap L$ holds a view-$k$ lock (value $x$) in its lockSet (a non-$(v^–1)$ lock since $v^- \geq k+2$) yet voted for a proposal with lock $q$ where $q.\text{view} < k$ (every lock in views $[k, v^-)$ has value $x$ by the above). This violates the maximality condition of the Complex voting rule and is detectable from the commit certificate, the lock for $v^-$, and the proposal. Since $ |
S_2 \cap L | > f$, at least $f+1$ violators are identified, and Provable Agreement follows. |
External Validity
Any valid commit certificate is a valid strong certificate of some Graded-Broadcast instance. By the External Validity property of Graded-Broadcast, its value must be externally valid.
Claim 2 (liveness)
All honest parties eventually hold a valid commit certificate.
If any honest party delivers a strong certificate, Totality propagates it to all. Otherwise, consider the first post-GST view $v^+$ with an honest leader that starts after all earlier certificates have propagated. By Liveness, every earlier view delivered a lock or skip certificate; by the $\Delta$-gap part of Liveness, all honest parties enter $v^+$ within $\Delta$ of each other, satisfying Strong Validity’s premise.
If keySet is non-empty, the primary proposes its highest lock $p$ (view $w$) paired with $\bot$ if $w = v^+-1$, or the skip for view $v^+-1$ otherwise. If keySet is empty, it proposes its own externally valid input with the skip for view $v^+-1$ (or vacuously for $v^+ = 1$). In both cases the proposal satisfies the Complex voting rule: the skip condition holds by the above, and the maximality condition holds because all delivered lock certificates have propagated, so the primary’s highest lock in keySet dominates every non-$(v^+-1)$ lock in any honest party’s lockSet (or both are empty). By Strong Validity, all honest parties deliver a strong certificate in view $v^+$.
Notes
Note that a party needs to store at most the two most recent lock certificates and the most recent skip certificate, so the number of certificates stored is constant. In contrast, in Simplex a party may need to store a lock certificate for every skipped view, which can grow with the number of skipped views.
Just like Kuplex improves Simplex from $3\Delta+\delta$ to $2\Delta+2\delta$, one can devise Komplex, which also obtains worst-case view latency $2\Delta+2\delta$ and, like Complex, still requires only a constant number of certificates per view. We leave the details to a future post.
Similarly, there is a Fast Simplex protocol with a two-round good case. This can be transformed to a Fast Complex variant for $5f+1$, and will be explored in later posts.
Acknowledgments
Many thanks to Jovan for insightful feedback on this post.
Your thoughts on X (link coming soon).