Kudzu: Fast and Simple High-Throughput BFT

A long line of work proposes consensus protocols with a fast path, typically called “fast”, “early-stopping” or “one-step” consensus [9, 27, 18, 36, 32, 21]. FaB Paxos [32] introduces a parametrized model with $3f+2p+1$ replicas, where $p\ge 0$. The parameter $p$ describes the number of replicas that are not needed for the fast path. These protocols can terminate optimally fast in theory ($2\delta$, or 2 network delays) under optimistic conditions. The papers [18, 28, 2] point out that the lower bound of $3f+2p+1$ actually only applies to a restricted type of protocol. The papers present single-shot consensus protocols that use only $3f+2p^{\ast }-1$ replicas, with $p^{\ast }\ge 1$, and prove the corresponding lower bound.

Interestingly, in practice, these fast path protocols might increase the finalization latency, as the fast path requires a round of voting between $n-p$ replicas, which could be slower than two rounds of voting between $n-f-p$ replicas that are concentrated in a geographic area. Banyan [38] performs the fast path in parallel with the $3\delta$ mechanism, which is optimally fast if more than $p$ replicas are faulty or exhibit higher network latency. However, Banyan can exhibit unbounded message complexity when there is a corrupt leader. Kudzu addresses this drawback, shares the same optimistic latency properties, improves throughput through balanced dispersal, benefits from a simpler design, and better properties during leader rotation (see Section 2.4).

Leader-based protocols such as PBFT [14], HotStuff [41] and Tendermint [10] suffer from a bandwidth bottleneck, as in these protocols the leader is responsible for disseminating transactions to all replicas. As mentioned above, this bottleneck has been well known for quite a while [37, 33, 16]. One way to alleviate this bottleneck is to move away from leader-based protocols to a more symmetric, leaderless protocol design where all replicas disseminate transactions. Such an approach was already taken in [37, 33, 24, 16]. These protocols typically have worse latency than leader-based protocols, and moreover, since many replicas may end up broadcasting the same transactions, the supposed improvement in throughput can end up being illusory (note that [37] actually tackles this duplication problem head on).

Kudzu follows a different approach to address the leader bottleneck, which makes use of erasure coding [39, 20]. By splitting blocks into smaller, erasure-coded shares, the leader can transmit less data, leading to a balanced utilization of resources. This line of work shines by providing high throughput and low latency [34, 30]. Alpenglow [25] is a recent proof-of-stake protocol being deployed for the Solana blockchain that showcases the appeal of this line of work in practice. Alpenglow and Kudzu are intimately related in their voting logic.

Some atomic broadcast protocols are notorious for having complex view changes, especially in the presence of a fast path [4]. In the case of Zzyzzva [26] and UpRight [15], safety errors were later pointed out [1]. Arguably SBFT [22] was the first to correct these mistakes. SBFT [22] avoids the all-to-all broadcast that occurs in Kudzu, but this results in higher finalization latency. Moreover, SBFT does not address the above-mentioned leader bottleneck.

We will not generally assume network synchrony. However, we say the network is $\delta$-synchronous at time $T$ if every message sent from an honest replica $P$ at or before time $T$ to an honest replica $Q$ is received by $Q$ before time $T+\delta$. We also say the the network is $\delta$-synchronous over an interval $[a,b+\delta ]$ if it is $\delta$-synchronous at time $T$ for all $T\in [a,b]$.

While our protocols always guarantee safety, even in periods of asynchrony, liveness will only be guaranteed in periods of $\delta$-synchrony, for appropriately bounded $\delta$ (and this synchrony bound may be explicitly used by the protocol). Thus, we are essentially working in the partial synchrony model of [19]. However, instead of assuming a single point in time (GST) after which the network is assumed to be synchronous, we take a somewhat more general point of view that models a network that may alternate between periods of asychrony and synchrony.

Replicas have local clocks that can measure the passage of local time. We do not assume that clocks are synchronized in any way. However, we do assume that there is no clock skew, that is, all clocks tick at the same rate (but we could also just assume the skew is bounded and incorporate that bound into the protocol’s synchrony bound).

The purpose of state machine replication is to totally order blocks containing transactions, so that all replicas output transactions in the same order. Our protocol orders blocks by associating them with natural numbered slots. Some leader replica is assigned to every slot. For every slot, either some block produced by the leader might be finalized, or the protocol can yield an empty block. The guarantees of our protocol can be stated as follows:

• $\mathrm{■}$

  Safety: If some honest replica finalizes block $B$ in slot $v$, and another honest replica finalizes block $B^{\prime }$ in slot $v$, then $B=B^{\prime }$.

• $\mathrm{■}$

  Liveness: If the network is in a period of synchrony, each honest replica continues to finalize blocks for slots $v=1,2,\mathrm{\dots }$

In addition to liveness and safety, we support a fast path:

• $\mathrm{■}$

  Fast Termination: If the network is in a period of synchrony, $n-p$ replicas behave momentarily honestly, and an honest leader proposes a block $B$ at time $t$, then every honest replica finalizes $B$ at time $t+2\delta$.

Each replica maintains a pool with votes and certificates. For every slot, the pool stores votes and certificates associated with the slot.

As we will see, by design, for any one slot, a honest replica can send only 1 first vote, 1 timeout vote, and 1 finalization vote. As we will also see later (in Section 5.3), for one slot a honest replica can only send at most 3 (non-timeout) notarization votes. Any votes exceeding this bound can only result from misbehavior and are not added to the pool. For example, if a replica receives more than three notarization votes for a given slot from some replica $P$, the replica can ignore these votes and conclude that $P$ is corrupt. In particular, only one first vote per replica can be observed by the protocol loop in Protocol 1. When a first vote is added to the pool, also the contained notarization vote is added to the pool.

Whenever a replica receives enough votes, and it does not already have a corresponding certificate, it will generate the certificate, add it to the pool, and broadcast the certificate to all replicas. Similarly, whenever a replica receives a certificate, and it does not already have a corresponding certificate, it will add it to the pool, and broadcast the certificate to all replicas. For one slot it is impossible that the pool would receive or create more than: 1 timeout certificate, 1 fast finalization certificate, 1 finalization certificate, and 5 notarization certificates. The first bound is immediate, since there can be only one timeout certificate per slot. The second and third bounds follow from the safety analysis below. The fourth bound follows from the analysis in Section 5.3.

Each replica also maintains a complete block tree, which is a tree of blocks rooted at a notional genesis block at slot 0. We will show that the number of blocks for a given slot is bounded by 5. A block $B=\text{Block}(v,\tau ,h_p)$ is added to the tree if each of the following holds:

• $\mathrm{■}$

  the certificate pool contains a notarization certificate for $B$ and $B\ne B_v^{\text{timeout}}$;

• $\mathrm{■}$

  $h_p=\perp$ or the complete block tree contains a parent block with the hash $h_p$;

• $\mathrm{■}$

  the replica has received enough (i.e. $f+p+1$) notarization votes to reconstruct the effective payload $M$ of $B$ as

  $$M\leftarrow \text{Decode}(\tau ,{\{(f_i,{\pi }_i)\}}_{i\in ℐ}),$$

  where ${\{(f_i,{\pi }_i)\}}_{i\in ℐ}$ is the corresponding collection of certified fragments for $\tau$;

• $\mathrm{■}$

  $M\ne \perp$ and satisfies some correctness predicate that may depend on the path of blocks (and their payloads) from genesis to block $B$.

A replica does not broadcast anything in addition to adding a block to the block tree.

We say that a block $B$ for slot $v$ is explicitly finalized by replica $P$ if the complete block tree of $P$ contains $B$ and the certificate pool of $P$ contains either a fast finalization certificate for $B$ or finalization certificate for $B$. In this case, we say that all of the predecessors of block $B$ in the complete block tree are implicitly finalized by $P$. The payloads of finalized blocks may be then transmitted in order to the execution layer of the protocol stack of a replicated state machine.

The logic for generating block proposal material $B$, $(f_1,{\pi }_1),\mathrm{\dots },(f_n,{\pi }_n)$ in slot $v$ in line 16 of Protocol 1 is as follows:

• $\mathrm{■}$

  build a payload $M$ that validly extends the path in the complete block tree ending at a block $B_{\text{p}}$ with hash $h_p$;

• $\mathrm{■}$

  compute

  $$(\tau ,{\{(f_i,{\pi }_i)\}}_{i\in [n]})\leftarrow \text{Encode}(M);$$

• $\mathrm{■}$

  set $B≔\text{Block}(v,\tau ,h_p)$.

To check if $\text{BlockProp}(B,f_j,{\pi }_j)$ is a valid block proposal in slot $v$ in line 18 of Protocol 1, replica $P_j$ checks that the following conditions holds:

• $\mathrm{■}$

  the proposal is signed or otherwise authenticated by the leader,

• $\mathrm{■}$

  $B$ is of the form $\text{Block}(v,\tau ,h_p)$,

• $\mathrm{■}$

  $(f_j,{\pi }_j)$ is a certified fragment for $\tau$ at position $j$,

• $\mathrm{■}$

  the complete block tree contains a block with the hash $h_p$ in a slot ;

• $\mathrm{■}$

  the pool contains timeout certificates for slots $v^{\prime }+1,\mathrm{\dots },v-1$;

These last two conditions might not hold at a given point in time, but may hold at a later point in time, and so might need to be checked again when blocks or certificates are added.

The main protocol for $P_j$ is described in Protocol 1. In the description, $\text{leader}(v)$ denotes the leader for slot $v$ – as mentioned, leaders may be rotated in each slot, either in a round-robin fashion or using some pseudo-random sequence.

As mentioned in Section 4.2, each replica only considers only one first vote that it receives from any other replica. To make this explicit in the protocol, we use a map $\mathrm{𝑓𝑖𝑟𝑠𝑡𝑉𝑜𝑡𝑒}$ from replicas to blocks to record these votes for the current slot. The protocol also uses simple helper functions on this map.

• $\mathrm{■}$

  $\text{allVotes}(\text{firstVote})$: the total number of first votes for slot $v$ contained in the pool,

• $\mathrm{■}$

  $\text{maxVotes}(\text{firstVote})$: the maximal number of first votes on some non-timeout block $B$ for slot $v$ contained in the pool,

• $\mathrm{■}$

  $\text{manyVotes}(\text{firstVote})$: returns the set of non-timeout blocks in slot $v$ on which the pool contains at least $f+p+1$ first votes.

For example, if the pool contains 1, 2, 3, 4 first votes on blocks $B_1$, $B_2$, $B_3$, $B_v^{\text{timeout}}$ respectively (and $f+p+1=2$), then $\text{allVotes}=10$, $\text{maxVotes}=3$, and $\text{manyVotes}=\{B_2,B_3\}$.

The protocol also uses a subprotocol ReconstructAndNotarize$(v,B)$, defined in Protocol 2.

Each replica $P_j$ moves through slots $v=1,2,\mathrm{\dots }.$ In each slot, it will enter a loop in which it waits for one of several conditions to trigger an action. These conditions are based on the objects in its pool and its complete block tree, as well as local variables.

• $\mathrm{■}$

  Lines 9–11 present the logic for the replica successfully exiting the slot by finding a block $B$ for that slot in its complete block tree. In addition, if the replica did not broadcast a notarization vote for any other block (including the timeout block) for that slot, it will also broadcast a finalization block for $B$.

• $\mathrm{■}$

  Lines 12–13 present the logic for the replica unsuccessfully exiting the slot by obtaining a timeout certificate for that slot.

• $\mathrm{■}$

  Lines 14–17 present the logic for the replica proposing a block for that slot if it is the leader for that slot. It generates the block proposal as in Section 4.5, extending the path in the complete block tree ending at $B_{\text{p}}$. Here, $B_{\text{p}}$ is either the genesis block or the block that it found in its complete block tree the last time it successfully exited a slot (other choices of $B_{\text{p}}$ are possible).

• $\mathrm{■}$

  Lines 18–21 present the logic for the replica broadcasting a first vote for a non-timeout block $B$. It will do so only if $B$ is a valid block proposed by the leader (as in Section 4.6) and has not already first voted. Recall that a first vote for $B$ also includes a notarization vote for $B$.

• $\mathrm{■}$

  Lines 22–25 present the logic for the replica broadcasting a first vote for the timeout block for this slot. It will do so only if a sufficient amount of time has passed since it entered the slot and has not already first voted.

• $\mathrm{■}$

  Lines 26–27 present the logic for updating the map $\mathrm{𝑓𝑖𝑟𝑠𝑡𝑉𝑜𝑡𝑒𝑠}$. No other actions are taken.

• $\mathrm{■}$

  Lines 28–31 present the logic for the replica taking a “second look” at a block $B$, if it has received sufficiently many first votes for $B$. It will do so only if it has already first voted (and has not already taken a second look at $B$). If it can reconstruct a valid payload for $B$, it will broadcast a notarization vote for $B$ (if it has not already done so); otherwise, it will broadcast a notarization vote for the timeout block.

• $\mathrm{■}$

  Lines 32–35 present the logic for the replica broadcasting a timeout vote under special circumstances. It will do so only if it has already first voted and

  $$\text{allVotes}(\text{firstVote})-\text{maxVotes}(\text{firstVote})\ge f+p+1.$$

  We note that the quantity

  $$\text{allVotes}(\text{firstVote})-\text{maxVotes}(\text{firstVote})$$

  cannot decrease as we add entries to firstVote. That is because, when we add an entry, the first term increases by 1 and the second either decreases by 1 or remains unchanged.

Liveness follows from the following lemmas. The first lemma analyzes the optimistic case where the network is synchronous and the leader of a given slot is honest, showing that the leader’s block will be committed.

We prove some simple results that allow us to bound message and storage complexity. Here, we are assuming both (1) and (2).

Let us consider notarization votes on non-timeout blocks. An honest replica sends a first vote for at most one such block. Any notarization vote for some other non-timeout block $B$ requires that the replica found $B\in \text{manyVotes}(\mathrm{𝑓𝑖𝑟𝑠𝑡𝑉𝑜𝑡𝑒𝑠})$. In other words, the replica has seen at least $f+p+1$ other replica’s first votes for $B$. At most one first vote per replica is considered when computing $\text{manyVotes}(\mathrm{𝑓𝑖𝑟𝑠𝑡𝑉𝑜𝑡𝑒𝑠})$. Therefore, an honest replica can cast at most $\lfloor n/(f+p+1)\rfloor$ notarization votes beyond the first vote, and by (2), $\lfloor n/(f+p+1)\rfloor \le 2$, for a total of 3 notarization votes for non-timeout blocks.

Suppose there are $f^{\prime }\le f$ corrupt replicas, and so $n-f^{\prime }$ honest replicas. The honest replicas therefore issue at most $3(n-f^{\prime })$ notarization votes for non-timeout blocks per slot.

Now, to construct a notarization certificate for a non-timeout block $B$, we require that $(n-f-p-f^{\prime })$ honest replicas cast a notarization vote for $B$. Therefore, by the result in the previous paragraph, there can be at most

distinct blocks for which a notarization certificate can be constructed.

We claim that $N\le 5$. To see this, first note that the derivative of $(3(n-f^{\prime }))/(n-f-p-f^{\prime })$ with respect to $f^{\prime }$ is positive, and therefore the right-hand side of (3) is maximized when $f=f^{\prime }$, and so

So it suffices to show that . This is easily seen to follow by a simple calculation using (1).

So to summarize, we have shown that in any slot,

1. 1.

   each replica casts a notarization vote for at most $2$ non-timeout blocks besides its first vote, and

2. 2.

   there are at most $5$ distinct blocks for which a notarization certificate can be constructed.

This immediately gives us bounds on the message and storage complexity of the protocol per slot.

Based on the concrete bounds in Section 5.3 (and the preliminary discussion in Section 4.2), it is easily seen that the message complexity per slot is $O(n^2)$. Based on the properties of erasure codes and Merkle trees discussed in Section 3.3.2, the communication complexity per slot is $O(\beta n+n^2\log (n)\kappa +n^2\lambda )$, where $\beta$ is a bound on the payload size, $\kappa$ is the output length of the collision-resistant hash, and $\lambda$ is a bound on the length of any signature share or certificate. Moreover, the communication is balanced, in that every replica, including the leader, transmits the same amount of data, up to a constant factor. It is also easily seen that each replica needs to store $O(\beta +n\log (n)\kappa +n\lambda )$ bits of data.