Multimmit: Low-Latency and Robust Transaction Ordering

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.

A Quick Consensus

This is a significant rewrite of “Consensus in 50 pages”, expanded into a short book.

I hope you’ll find it an easy-to-read and self-contained introduction to everything you need to know about distributed computing for blockchain. So far, I’ve completed roughly the first two thirds, which covers most of the basics, including most standard results for the synchronous and partially synchronous settings, and some results for the asychronous setting. You’ll find also find clear explanations of Tendermint, Hotstuff, PBFT, Simplex, accountability, and player reconfiguration.

Still to add: erasure coding in consensus; payment systems; DAG-based protocols; recovery protocols; the Pipes model; 2-round finality protocols.

I’m aiming to finish a first draft by the end of June, and will post updates here.

Here is the pdf.

The Carnot Bound: Limits and Possibilities for Bandwidth-Efficient Consensus 

In leader-based protocols for State Machine Replication (SMR), the leader’s outgoing bandwidth is a natural throughput bottleneck. Erasure coding can alleviate this by allowing the leader to send each processor a single fragment of each block, rather than a full copy. The data expansion rate, the ratio of total data sent to payload size, determines how close throughput can get to the underlying network bandwidth.

We investigate the fundamental limits and possibilities for bandwidth-efficient leader-based consensus. On the negative side, we prove that protocols with 2-round finality (one round of voting) cannot achieve a data expansion rate below approximately 2.5, a bound that is matched by existing protocols. On the positive side, we show that protocols with 3-round finality (two rounds of voting) can push the data expansion rate arbitrarily close to 1. The key insight is that the second voting round provides a recovery mechanism: leaders can attempt aggressive erasure codes and safely fall back to more conservative ones when reconstruction fails, without compromising consistency.

We present two protocols with 3-round finality realising this approach. Carnot~1 assumes $n \geq 4f+1$ processors (of which at most $f$ may be Byzantine) and achieves a clean design requiring no additional fragment dissemination beyond the initial protocol messages. Carnot~2 operates under the optimal resilience assumption $n \geq 3f+1$, at the cost of additional fragment dissemination when Byzantine processors interfere. Both protocols can incorporate stable leaders and optimistic proposals to maximise throughput and minimise latency. Under favourable conditions, with correct leaders and few actual faults, both protocols allow leaders to use  data expansion rates approaching $1$; under adversarial conditions, leaders can revert to safe expansion rates of approximately $1.33$ and $1.5$, respectively — both still well below the 2.5 lower bound for protocols with 2-round finality.

Here is the pdf. Joint work with Patrick O’Grady.

Reaching Univalency with Subquadratic Communication

The Dolev-Reischuk lower bound establishes that any deterministic Byzantine Agreement (BA) protocol for $n$ processors tolerating $f$ faults requires $\Omega(f^2+n)$ messages. But what exactly does this quadratic cost pay for? Even the minimal requirement that every correct processor receive at least one message already necessitates $\Omega(f^2 + n)$ messages. This raises a fundamental question: is the Dolev-Reischuk bound about the difficulty of reaching univalency—the point at which the protocol’s outcome is determined—or merely about disseminating the outcome to all processors afterward?

We resolve this question by showing that reaching univalency does not require quadratic communication. Specifically, we introduce $\epsilon$-BA, a relaxation allowing an $\epsilon$-fraction of correct processors to output incorrectly, and prove it can be solved deterministically with $O(n \log n)$ communication complexity when $f < n(1/3 – \epsilon)$. Crucially, any $\epsilon$-BA protocol can serve as the first phase of a full BA protocol: after $\epsilon$-BA, a single all-to-all exchange and majority vote completes BA. Since the outcome is already determined after $\epsilon$-BA, this demonstrates that the quadratic cost in Dolev-Reischuk stems entirely from dissemination, rather than from reaching univalency. We also define Extractable BA for authenticated settings, capturing when processors collectively hold enough signed messages to determine the agreed value, and show it can be solved with communication complexity $O(f \log f)$.

Here is the pdf, (PODC 2026)

Minimmit: Fast Finality with Even Faster Blocks

Achieving low-latency consensus in geographically distributed systems remains a key challenge for blockchain and distributed database applications. To this end, there has been significant recent interest in State-Machine-Replication (SMR) protocols that achieve 2-round finality under the assumption that $5f+1\leq n$, where $n$ is the number of processors and $f$ bounds the number of processors that may exhibit Byzantine faults. In these protocols, instructions are organised into views, each led by a different designated leader, and 2-round finality means that a leader’s proposal can be finalised after just a single round of voting, meaning two rounds overall (one round for the proposal and one for voting).

In this paper, we introduce Minimmit, a Byzantine-fault-tolerant SMR protocol with lower latency than previous 2-round finality approaches.  Our key insight is that view progression and transaction finality can operate on different quorum thresholds without compromising safety or liveness. Experiments simulating a globally distributed network of 50 processors, uniformly assigned across ten virtual regions, show that the approach leads to a 23.1% reduction in view latency and a 10.7% reduction in transaction latency compared to the state-of-the-art.

Joint work with Brendan Kobayashi Chou and Patrick O’Grady.

Here is the pdf. (FC26)

The Pipes Model for Latency and Throughput Analysis


Abstract: In much of the distributed computing literature, latency is expressed as the number of communication rounds or network delays; such metrics do not directly account for the amount of data sent or the dependencies among parties sending the data. Throughput is also normally evaluated empirically. As a consequence, the standard models used for analysing state machine replication (SMR) protocols do not by themselves provide an end-to-end analytical comparison of practical latency and throughput as functions of per-processor bandwidth and transaction arrival rate.

In this paper, we present Pipes, a model for analysing latency and throughput in SMR protocols. The Pipes model captures the effect of processor bandwidth $S$, transaction arrival rate $D$, and network delays, enabling us to explicitly specify the throughput bottleneck and the latency of a protocol. Using Pipes, we derive good-case latency expressions and throughput bottlenecks for concrete multi-shot protocols implementing Best-effort Broadcast, Consistent Broadcast, Reliable Broadcast, and Reliable Broadcast with erasure coding and pipelining. We consider both single-sender and multi-sender approaches, and extend the analysis to SMR protocols including DispersedSimplex, Sailfish, Tendermint, and HotStuff. Our comparisons reveal the trade-off between the lower latency achievable through pipelining and erasure coding in single-sender protocols and the higher throughput bottlenecks achievable by multi-sender DAG-based protocols. We also quantify when the additional communication phases of HotStuff are preferable to the fixed wait in a Tendermint-style protocol.

Beyond these protocol-specific latency calculations, we establish tight Best-effort Broadcast latency bounds in both the single-sender and multi-sender settings. The analysed protocols are optimal when each recipient receives a full block directly from the transaction’s source, the same blocks are sent to everyone, and outstanding upload work is bounded. We give a second tight bound assuming only direct receipt, attained by a protocol that staggers block boundaries across recipients. For protocols using AVID-style erasure coding, we prove latency lower bounds that combine block formation, reconstruction and fragment forwarding.

Finally, we implement and evaluate variants of DispersedSimplex and Sailfish, comparing measured latency with the predictions of the Pipes model.

Joint work with Kartik Nayak and Nibesh Strestha.

Here is the pdf, (S&P 2026)

Frosty for partial synchrony

Snowman is the consensus protocol used by blockchains on Avalanche. Recent work of ours has shown both how to augment Snowman with a `liveness’ module called `Frosty’ that protects against liveness attacks, and also how to modify Snowman so as to be consistent in partial synchrony. Since Frosty assumes (a strong form of) synchrony, the aim of this note is to show how to modify Frosty to deal with the partially synchronous version of Snowman.

Joint work with Stephen Buttolph and Kevin Sekniqi. Here is the pdf.

From Permissioned to Proof-of-Stake Consensus

This paper presents the first generic compiler that transforms any permissioned consensus protocol into a proof-of-stake permissionless consensus protocol. For each of the following properties, if the initial permissioned protocol satisfies that property in the partially synchronous setting, the consequent proof-of-stake protocol also satisfies that property in the partially synchronous and quasi-permissionless setting (with the same fault-tolerance): consistency; liveness; optimistic responsiveness; every composable log-specific property; and message complexity of a given order. Moreover, our transformation ensures that the output protocol satisfies accountability (identifying culprits in the event of a consistency violation), whether or not the original permissioned protocol satisfied it.

Joint work with Jovan Komatovic, Joachim Neu, Tim Roughgarden, Ertem Nusret Tas

Here is the pdf (AFT 2025).

Constitutional Consensus for Democratic Governance

Grassroots platforms aim to offer an egalitarian alternative to global platforms — centralized/autocratic and decentralized/plutocratic alike. Within the grassroots architecture, consensus is needed to realize platforms that employ digital social contracts, which are like smart contracts except that they are among people not accounts and are executed by these people’s smartphones not by high-performance servers controlled by parties outside to the contract. Key envisioned grassroots platforms include sovereign democratic digital communities and federations, community banks and their grassroots cryptocurrencies, and digital cooperatives.
The grassroots architecture can benefit from a consensus protocol that is (i) quiescent, (ii) efficient during low- and high-throughput, (iii) responsive, (iv) blocklace-based, (v) UDP-ready, and (vi) grassroots. The Grassroots Consensus protocol addresses all these requirements while having competitive performance in both low- and high-throughput scenarios and being one of the most concise and elegant consensus protocols for partial synchrony. It achieves that by building on two cutting-edge consensus protocols — the quiescent high-performance Morpheus and the blocklace-based Cordial Miners, improving the latter’s dissemination protocol and making it UDP-ready, and extending the protocol with a constitution and a constitutional amendment component, making it grassroots.

Joint work with Idit Keidar and Ehud Shapiro. Here is the pdf.

Beyond Optimal Fault-Tolerance

One of the most basic properties of a consensus protocol is its fault-tolerance—the maximum fraction of faulty participants that the protocol can tolerate without losing fundamental guarantees such as safety and liveness. Because of its importance, the optimal fault-tolerance achievable by any protocol has been characterized in a wide range of settings. For example, for state machine replication (SMR) protocols operating in the partially synchronous setting, it is possible to simultaneously guarantee consistency against $\alpha$-bounded adversaries (i.e., adversaries that control less than an $\alpha$ fraction of the participants) and liveness against $\beta$-bounded adversaries if and only if $\alpha + 2\beta \leq 1$.

This paper characterizes to what extent “better-than-optimal” fault-tolerance guarantees are possible for SMR protocols when the standard consistency requirement is relaxed to allow a bounded number $r$ of consistency violations, each potentially leading to the rollback of recently finalized transactions. We prove that bounding rollback  is impossible without additional timing assumptions and investigate protocols that tolerate and recover from consistency violations whenever message delays around the time of an attack are bounded by a parameter $\Delta^*$ (which may be arbitrarily larger than the parameter $\Delta$ that bounds post-GST message delays in the partially synchronous model). Here, a protocol’s fault-tolerance can be a non-constant function of $r$, and we prove, for each $r$, matching upper and lower bounds on the optimal “recoverable fault-tolerance” achievable by any SMR protocol. For example, for protocols that guarantee liveness against 1/3-bounded adversaries in the partially synchronous setting, a 5/9-bounded adversary can always cause one consistency violation but not two, and a 2/3-bounded adversary can always cause two consistency violations but not three.  Our positive results are achieved through a generic “recovery procedure”  that can be grafted on to any accountable SMR protocol and restores consistency following a violation while rolling back only transactions that were finalized in the previous $2\Delta^*$ timesteps.

This is joint work with Tim Roughgarden.

Beyond Optimal Fault-Tolerance, pdf, (AFT 2025).