Brief Announcement: Carry the Tail in Consensus Protocols

The Carry-the-Tail protocol operates in a view-by-view manner. Each view $v$ has a known designated leader $L_v$ performing a single quorum-exchange with replicas. The leader broadcasts a proposal $B_v$ to the replicas; replicas respond (subject to safety rules) with a NEW-VIEW message carrying a signature-share on $B_v$. The signature-share is referred to as a vote on $B_v$.

A Quorum-Certificate (QC) consists of a threshold-signature by a quorum of $2F+1$ replicas. We say that the proposal is certified when $\mathrm{𝖰𝖢}(B_v)$ is formed. To form QCs, leaders collect signature-shares for previous proposals and aggregate them. Broadcasting a QC incurs only linear word-communication complexity.

Each proposal $B_v$ includes an opaque payload and meta-information. The meta-information references a history known to the leader. It includes $B_v.QC$ prior to view $v$, the highest known certified tail. Chaining proposals to one another using cryptographic certificates is utilized along with protocol voting and commit rules to ensure safety.

Figure 1 depicts a failure-free flow of the protocol with leader proposals chained to one another via QCs. Upon receiving a proposal $B_v$, a replica becomes locked on $B_v.QC$. Locking is key to ensuring safety: in the future, the replica pledges that it will only accept proposals that extend $B_v.QC$ or a QC from a higher view. The figure shows a failure-free execution snippet with four consecutive leaders chaining proposals one after another.

A commit necessitates two consecutive successful views. If a leader $L_v$ forms $\mathrm{𝖰𝖢}(v-1)$ for the proposal $B_{v-1}$ immediately preceding it, then the proposal becomes committed once there are $2F+1$ signature-shares on $B_v$, forming $\mathrm{𝖰𝖢}(v)$. Anyone can learn this commit decision by obtaining these votes. In particular, anyone observing a chain $B_{\ast }.QC=\mathrm{𝖰𝖢}(v)$, $B_v.QC=\mathrm{𝖰𝖢}(v-1)$ learns that $B_{v-1}$ has been committed. In Figure 1, $B_1$ and $B_2$ have been committed, and anyone observing this chain can learn these decisions.

To guarantee liveness, a leader proposes if it received a QC from the immediately-preceding view or a timeout. The timeout is implemented by a separate view-synchronization (Pacemaker) module [3, 11, 12]. Any (linear) Pacemaker can be plugged here. The Pacemaker guarantees that sufficient time has elapsed for all honest replicas to have entered view $v$ and for their NEW-VIEW messages to have arrived at the leader.

We first explain the tail-forking attack which was exposed in BeeGees [5], and later describe how Carry prevents it.

Figure 2(a) depicts a scenario with failed view $B_2$, zooming in on the transition from $B_2$ to $B_3$. In view 2, no replica succeeds to vote for $B_2$. $L_3$, the leader of view 3, times out without having formed a QC for $B_2$ and must skip $B_2$.

The problem is that a malicious $L_3$ could exploit this and omit votes for $B_2$ to wrongfully skip it. Figure 2(b) shows that $B_3$ could ignore the $2F+1$ honest votes (the dashed arrows) for $B_2$ and wrongfully skip it. More generally, a view $v$ suffers a tail-forking attack if $2F+1$ signature shares are sent by honest replicas on $B_v$, but the next leader $L_{v+1}$ intentionally ignores and skips it. The attack can be caused by either a malicious or a sluggish leader.

Regardless of the cause for tail-forking, it causes significant performance degradation. First, a proposal (e.g., $B_2$) is unnecessarily dropped. Second, the latency to a commit decision on pending earlier proposals increases. Moreover, tail-forking might occur frequently if there are many malicious/sluggish leaders. In the worst case, $F$ bad leaders perfectly interspersed among honest views as depicted in Figure 4(perf1), where leaders $L_3,L_5,\mathrm{\dots },$ are bad. This might cause $O(N)$ throughput degradation and $O(N)$ latency increase.

As explained below, the Carry method prevents the tail-foring attacks from happening.

Because replicas send NEW-VIEW messages to the next leader, in lieu of a vote, they can send a signature-share on an empty vote (“$\perp$”). In Carry, a justified skip over a tail $B_v$ is allowed if it is accompanied by an Empty Certificate (EC) consisting of a threshold signature by $2F+1$ replicas on $\perp$. An Empty Certificate cannot possibly be formed if $F+1$ honest replicas voted for $B_v$; but if only $F$ or fewer honest replicas voted for $B_v$, it could form, which affects neither safety nor liveness. Figure 3(c) depicts shows how ECs justifies a skipped tail, where $L_3$ collects $2F+1$ empty votes (the yellow arrows) for view $2$ and forms an $\mathrm{𝖤𝖢}(2)$.

If there is neither a QC nor an EC, previous solutions (e.g., [5]) required leaders to justify skipping the tail by using all the votes, resulting in cubic word-communication complexity in the worst case with $F$ consecutive malicious leaders.

Instead, the main idea in Carry is to force the next leader to reinstate the last (possibly uncertified) voted block. To implement this, Carry introduces an optional field $B_v.reinstate$. This field references an uncertified earlier proposal $B_x$ that becomes an integral part of $B_v$. As illustrated in Figure 3(d), $L_3$ receives $F+1=2$ votes for $B_2$ and two empty votes, preventing the formation of either $\mathrm{𝖰𝖢}(2)$ or $\mathrm{𝖤𝖢}(2)$. Consequently, $B_2$ is reinstated in $B_3$.

With this new mechanism, as shown in Figure 4(perf2), a leader must justify skipping a tail via an EC or else reinstate the tail. Notably, reinstating also helps if insufficient votes arrive for $B_v$ due to mere sluggishness.

Reinstating protects the tail in case an EC cannot be formed on an immediately preceding view. Unfortunately, tail-forking of $B_v$ remains possible by having two consecutive malicious leaders following $B_v$. Attacks by two consecutive malicious leaders, $L_{v+1}$ and $L_{v+2}$, are depicted in Figure 4(perf3), e.g., $L_3$ and $L_4$. First, $L_{v+1}$ “fails” in view $v+1$, not forming $\mathrm{𝖰𝖢}(v)$. Next, $B_{v+2}$ uses $\mathrm{𝖤𝖢}(v+1)$ to justify skipping $B_{v+1}$. Furthermore, $B_{v+2}$ skips $B_v$ because no justification is required to skip $B_v$ and no replica is locked on it.

To protect against tail-forking by two or more consecutive bad leaders, we apply the Carry method to the last $\rho$ views. The NEW-VIEW messages from replicas should carry their votes, possibly empty, for the last $\rho$ views. This protects a tail unless it is followed by $\rho$ consecutive bad views. Hence, in each view rotation, all but $(F_{actual}/\rho )$ proposals are protected from tail-forking. This property is referred to as $\rho -Tail-Resilience$. $2-Tail-Resilience$ is depicted in Figure 4(perf4). Importantly, for modest values of $\rho$, the chance of incurring $\rho$ consecutive bad views in practice is very small, especially if leader rotation is randomized.

The overhead incurred is $O(\rho N)$ word communication.

BeeGees formulated a property called “Any-Honest-Leader commit” (AHL): after GST, once an honest leader proposes in a view, that block will be committed after at most $k$ subsequent honest-leader views¹¹1$k$ is a protocol parameter indicating the number of phases to reach a commit; typically, $k=2$ or $k=3$.. BeeGees employs a complex leader handover in order to satisfy AHL (in one variant, it incurs quadratic word-communication per view, and in a second variant, it relies on computationally-prohibitive SNARK proofs for compressing communication).

The property $\rho$-tail-resilience guarantees, under a reasonably small choice of $\rho$ (e.g. $\rho =6$), that a large constant fraction of honest leader proposals become committed even against the worst-case tail-forking attacks. It is worth noting that by setting $\rho =f$, we get the same AHL property in Carry as in BeeGees, while incurring the same communication burden. However, arguably Carry has simpler logic and also allows $\rho$ to be a tunable parameter in production.