Paper 2026/1214

Faster Leader-Based Consensus via Certificates of Exclusivity and Overlapping Iterations

Abstract

Blockchain consensus protocols, also known as BFT state-machine replication, enable a system of $n$ players to decide an ever-growing chain of blocks. We consider partial synchrony: after an unknown time GST, messages sent by honest players are delivered within an unknown actual delay $\delta$, and a known bound $\Delta$ satisfies $\delta \leq \Delta$. This setting imposes $t<n/3$ corruptions. We study leader-based consensus, a class with the smallest known latency metrics when sufficiently many designated leaders behave honestly. We consider the mainstream metric of {expected latency in the view-based sense:} for a transaction known to all honest players having entered a post-GST iteration, this is the expected time until that transaction appears in a decided block, under independent random leaders. We introduce Hamster, a rotating-leader consensus protocol, which reduces this expected latency to $\Delta+4\delta$, down from the previous $1.5\Delta+3.5\delta$ bound achieved by Simplex (Chan-Pass, TCC'23) for the same view-based metric. Hamster also brings this latency further down to $\Delta+3.5\delta$ for adversaries that do not get publicly caught equivocating. The main technical novelty is a certificate of exclusivity for a block $B$. It is shown by the next leader as evidence that players can safely vote for a child of $B$. A certificate of exclusivity is an interpolation between a quorum certificate and a timeout certificate, in that it is formed from a mix of votes for a unique block $B$ and complaint votes, proving that $B$ is the only non-dummy block that can still obtain a decision certificate for that iteration. The other novelty of Hamster is the use of {overlapping iterations: after a process has supported a newer proposal, the protocol may still allow it to support a safe proposal of an earlier iteration}. This overlap is what allows old honest proposals to be decided in time despite players advancing iterations faster. We also analyze another metric, called the {pessimistic block proposal time}, which is the time during which a bad leader can delay the proposal of a transaction in a block which will be decided. Hamster achieves a pessimistic block proposal time of $2\Delta+2\delta$, refined to $2\Delta+\delta$ for leaders not caught equivocating, down from $3\Delta+\delta$ for Simplex.

Note: 10 June 2026: updated Fig. 1