To meet the throughput demands of modern blockchain systems, protocols for State Machine Replication increasingly have many processors disseminate transaction blocks in parallel. For these protocols, the certified approach requires availability certificates before blocks enter the ordering process. This is robust, but adds latency. By contrast, BlueBottle’s core protocol, the leading uncertified design under $n\geq5f+1$ (where $n$ is the number of processors, of which at most $f$ are Byzantine), reduces latency in favourable conditions but can put fetching missing data on the critical path. Raptr, the state of the art under $n\geq3f+1$, takes a middle course. It avoids fetching on the voting path, but transactions still wait for a leader’s proposal and two voting rounds. The leader controls the proposed sequence, and one withheld batch can delay everything later in it. We prove that strengthening the resilience assumption alone cannot remove Raptr’s second voting round.
We present Multimmit, a protocol for $n\geq5f+1$ that builds on Raptr’s approach and finalises leader blocks after a single round of voting. Latency improves on Raptr by at least one message delay, and more in the common case. The protocol also guarantees much more than is bought by the change in resilience. Extension votes let voters endorse fresh transaction blocks omitted from the leader’s proposal and give a strong censorship-resistance guarantee: Once a leader block finalises, every fresh, well-circulated block of an honest chain enters the total ordering by the next finalised leader block, even if that block’s leader is Byzantine. Moreover, leader discretion over ordering is constrained: the protocol interleaves producer chains by a prescribed rule, rather than accepting a leader-chosen transaction sequence. For payments, the protocol provides finality within a single round trip. A payment is final once the payment’s producer assembles a certificate of $n-f$ acknowledgments, roughly $2\delta$ after dissemination, for $\delta$ the bound on message delay: the payment will then be ordered and executed, whatever any leader or any other processor does, and across committee changes. The certificate is a transferable receipt, verifiable from committee keys alone.
In experiments on a global deployment of fifty validators across thirteen regions, Multimmit’s median latency to placement in the total ordering moves from 383 to 411\,ms as the offered rate rises from 100,000 to 1,000,000 transactions per second. At 100,000 transactions per second, it is essentially unchanged under $0.1\%$ message loss, which slows BlueBottle by more than an order of magnitude, and rises by a factor of 1.4 with nine validators crashed, which slows Raptr by more than an order of magnitude.
Click here for the pdf. Joint work with Patrick O’Grady and Ben Clabby.