Consensus protocols often need to balance simplicity with performance. Simplex is a beautiful example of minimalistic design. In this post, we explore two variations of Simplex, one that improves view latency in silent views and another that improves view latency in the worst-case when the actual network delay $\delta$ is smaller than $\Delta$, the maximal delay after GST.

Recall that Simplex has a view latency of $3\Delta+\delta$ in the worst-case, including when the leader is silent.

It is commonly believed that many real world failures are just crashes, so getting better latency when the leader is silent seems to be a good practical addition.

The Simplex variant implemented by commonware’s Module simplex has such a simple addition. Here we extract that addition to a protocol we call C-Simplex. C-Simplex has a view latency of $3\Delta+\delta$ in the worst-case, and a view latency of $2\Delta+\delta$ when the leader is silent.

Another Simplex variant is Kudzu BFT which focuses on having a 2-round fast path in optimistic conditions. Here we extract its properties for the $3f+1$ case (no fast path) to a protocol we call Kuplex. Kuplex has a view latency of $2\Delta+\delta$ when the leader is silent and a view latency of $2\Delta+2\delta$ in the worst-case. This is better in executions where $\delta \ll \Delta$ but is not useful if $\delta=\Delta$.

Protocol Worst-case view latency Silent view latency
Simplex $3\Delta+\delta$ $3\Delta+\delta$
C-Simplex $3\Delta+\delta$ $2\Delta+\delta$
Kuplex $2\Delta+2\delta$ $2\Delta+\delta$

C-Simplex

C-Simplex adds a new rule (Upon 3) that sends a (Final, k, ⊥) if a party does not vote in the first $2\Delta$ time.

// Notation:
// Denote n-f (Vote, k, x) as Cert(k, x)  
// Denote n-f (Final, k, ⊥) as Cert(k, ⊥) 

C-Simplex

1. Upon entering view k: 
    Start a local timer T_k 
    Leader sends (Propose, k, x, Cert(k', x)) for the highest k’ 
    
2. Upon received (Propose, k, x, Cert(k’, x)) 
            and Cert(l, ⊥) for all k' < l < k
            and has not sent Vote
            and T_k < 2Δ
    Send (Vote, k, x)   // Denote n-f (Vote, k, x) as Cert(k, x)  

3. Upon T_k = 2Δ and has not sent Vote
    Send (Final, k, ⊥)    // Denote n-f (Final, k, ⊥) as Cert(k, ⊥)

4. Upon T_k = 3Δ and has not sent Final
    Send (Final, k, ⊥)    

5. Upon receiving Cert(k, x) 
    if has not sent Final
        Send (Final, k, x) 
    Forward Cert(k, x)
    Enter view k+1

6. Upon receiving n-f (Final, k, x) 
    Decide x 
    Forward the n-f (Final, k, x) 
    Terminate 

7. Upon receiving Cert(k, ⊥)
    Forward Cert(k, ⊥)
    Enter view k+1

The change to the protocol is minimal and the proof changes are also minimal.

Liveness:

Latency for silent views: If the leader of the view is silent then all honest parties will trigger Upon 3 and send Final for $\bot$ after at most $2\Delta$ time from when the last honest enters the view. Hence by $2\Delta+\delta$ all honest will trigger Upon 7 and move to the next view.

Safety:

Upon 3 adds an additional condition for sending a Final for $\bot$. The key property of Simplex is preserved: an honest party will send at most one Final message per view. Hence n-f (Final, k, x) implies no Cert(k, ⊥). In this case, all honest will complete view $k$ with Cert(k, x), which implies univalency.

Kuplex

In Kuplex, a party similarly sends a Vote for a value or $\bot$ if it does not vote by $2\Delta$ time. Two additional rules are added. First, a party votes a Final for $\bot$ if it sees $f+1$ Votes for $\bot$ or two equivocating proposals from the leader (Upon 4). Second, a party may later send a SecondVote for a different value (if it sees $f+1$ Votes for that value, see Upon 5). A certificate for a mix of $n-f$ Votes and SecondVotes is used to move to the next view.

Importantly, sending a Final for a value (Upon 6) happens only if the party did not send a Final for $\bot$, did vote for the same value as the certificate, and did not send a SecondVote.

Kuplex

// Notation: 
// * can be a value or ⊥, x is value that is not ⊥
// Denote a mix of n-f (Vote, k, *) and (SecondVote, k, *) as Cert(k, *)
// Denote n-f (Final, k, *) as FinalCert(k, *)

1. Upon entering view k: 
    Start a local timer T_k 
    Leader sends (Propose, k, x, Cert(k', x)) for the highest k’ 
    
2. Upon received (Propose, k, x, Cert(k’, x)) 
            and FinalCert(l, ⊥) or Cert(l, ⊥) for all k' < l < k
            and has not sent Vote
            and T_k < 2Δ
    Send (Vote, k, x)   // also include proposal for validity

3. Upon T_k = 2Δ and has not sent Vote
    Send (Vote, k, ⊥)    
    
4. Upon two valid votes on equivocating valid proposals
        or f+1 (Vote, k, ⊥) 
    Send (Final, k, ⊥) 
                       
5. Upon receiving f+1 (Vote, k, x)    
    If has not sent Vote 
        Send (Vote, k, x)  
    Else if sent (Vote, k, x') where x' != x
        Send (SecondVote, k, x)

6. Upon receiving Cert(k, x) and has sent Vote
    If sent (Vote, k, x)
            and has not sent SecondVote or Final
        Send (Final, k, x)
    Forward Cert(k, x)        
    Enter view k+1 if in view k 

7. Upon receiving n-f (Final, k, x) 
    Decide x 
    Forward FinalCert(k, x) 
    Terminate 

8. Upon receiving Cert(k, ⊥) or FinalCert(k, ⊥)
    Forward it 
    Enter view k+1 if in view k

Note that a party sends one vote, one final and at most 2 SecondVotes per view.

Liveness:

Honest leader view: after GST, all honest will vote after $\delta$ from the last honest to enter the view. No honest will trigger Upon 3 so there can be at most $f$ votes for ⊥. Hence all honest votes will be from Upon 2 or Upon 5 and no honest will SecondVote.

So by $2\delta$ all honest will have Voted and seen a Cert for that value and no honest will send a Final for $\bot$ or a SecondVote. Hence all honest will send a Final for that value and so all honest will decide by $3\delta$.

Worst-case view latency: after GST, all honest parties will see all honest votes by $T=2\Delta+\delta$ from the time the last honest joins the view. There are three cases:

  • If two honest parties vote on different values, then all will send (Final, k, ⊥) by $T$ (Upon 4), so all will see FinalCert(k, $\bot$) by $T+\delta$.
  • If $t+1$ honest parties vote $\bot$, then again all will send (Final, k, ⊥) by $T$, so all will see FinalCert(k, $\bot$) by $T+\delta$.
  • Otherwise, by $T$, every honest party will see at least $t+1$ honest votes for the same $x \neq \bot$, so all honest will send either (Vote, k, x) or (SecondVote, k, x) so all will see a Cert(k ,x) by $T+\delta$.

In all three cases, all honest enter the next view by $T+\delta = 2\Delta+2\delta$.

Silent view latency: all honest will see Cert(k, $\bot$) by $2\Delta+\delta$ and move to next view.

Safety:

  • Each honest party sends just one Vote. If there is a Cert(k, ⊥), then no Cert(k, x) can exist and no honest sends (Final, k, x).

Each honest party sends just one Final and just one Vote. If there are $f+1$ honest that sent (Final, k, x) then they also sent (Vote, k, x) and did not send any SecondVote. This means:

  • no FinalCert(k, ⊥) can exist.
  • no Cert(k, ⊥) can exist.
  • no Cert(k, x') can exist for $x’ \neq x$.

Hence a FinalCert(k, x) implies all honest will complete view $k$ with Cert(k, x) which implies univalency.

Observe that in views with less than $f+1$ honest parties sending (Final, k, x), there may be three certificates with different values.

Conclusion

C-Simplex and Kuplex show that one can improve the performance of Simplex in the practical case of silent leaders with a minimal change, and in the case of actually small network delays with somewhat involved changes. These variants remain true to the Simplex design spirit while highlighting the design space between simplicity and performance.