Multimmit: Extending Blocks for Faster Finality

arXiv:2607.21021 · cs.DC · Submitted 2026-07-23 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Multimmit: Extending Blocks for Faster Finality".

Jane: Here's the gist of the paper. Multimmit is a protocol designed for State Machine Replication (SMR) that integrates multi-chain data dissemination with a consensus skeleton derived from Minimmit.

Tom: It operates under a partially synchronous model where messages may experience arbitrary delays before being delivered within a known bound delta.

Jane: The system requires n at least 5f + 1 processors to achieve finality in one round of voting per view.

Tom: The core mechanism involves proposal-relative voting, where the leader proposes tips for every chain, and each voter reports the extent to which it can endorse that proposal on each chain.

Paper summary: Tom: So we're looking at this paper by Andrew Lewis-Pye and Patrick O’Grady and Ben Clabby called Multimmit: Extending Blocks for Faster Finality. What they're tackling here is how to handle the throughput demands of modern blockchain systems where you have a lot of processors all trying to build blocks in parallel and then figuring out a total order on those blocks.

Jane: That sounds really complex, Tom. The big question is when does a block get put into the ordering process? Does it wait for everyone to confirm they have the data, or can we start ordering right away using what we have?

Tom: Exactly. They’re looking at the trade-off between waiting until a block is fully attested by a quorum, which keeps things robust but adds delays to every transaction, and an optimistic approach where proposals can reference existing blocks immediately for low latency.

Lu: The paper introduces something they call Raptr as the current state of the art, and Multimmit takes a middle course. It lets leaders propose sequences of batches without requiring every voter to hold all that data, and each voter supports the longest initial segment of the sequence whose data it actually has available.

Meng: That sounds promising for speed, but what happens when that initial segment isn't long enough? If a faulty producer with only one batch withheld can spoil the whole optimistic path, how does this new approach handle that kind of attack?

Lalam: The paper says Raptr has a weakness they call easy spoiling. If data behind an early batch is missing, most voters can only support a short prefix, and the proposal finalizes little or nothing, even if it references a lot of available data <ref:2607.21021#pg3>.

Jane: So Multimmit tries to fix that by finalizing a prefix supported by a quorum right away, which means no processor ever has to wait or fetch data on the critical path for every transaction. That sounds like it keeps things moving, even if the initial segment is short.

Tom: Right, and they focus on strong censorship resistance here too. The paper claims that no single leader can finalize its leader block while simultaneously excluding a fresh, well-circulated block from an honest chain.

Lu: They establish total ordering through something called Quorum Certificates, which are split into safe-to-extend tips and finalized tips <ref:2607.21021#pg1>. These certificates have specific extraction rules that dictate the final sequence of blocks, ensuring faulty producers can't mess up the optimistic path.

Paper summary: Meng: If you need those certificates to define the order, how much data does that require? Because if we're talking about scaling to a lot of transactions, we need to know if these consensus objects grow with volume or not.

Tom: The good news is they maintain small consensus objects whose size is independent of transaction volume <ref:2607.21021#pg3>. That keeps the overhead low even when things get busy.

Jane: And to guarantee liveness, meaning that correct processors eventually get into every view, they use mechanisms involving nullifications and those V-QCs and L-QCs to ensure every correct processor eventually enters every view <ref:2607.21021#pg3>. That sounds like a solid safety net against getting stuck.

Lalam: They also focus on data availability, making sure that if a correct processor is missing some data, they can request it from all other processors and get a response within two delta time <ref:2607.21021#pg3>. Plus, possession of reference chain V-QCs is guaranteed because leader blocks on the reference chain are received with at least five votes <ref:2607.21021#pg3>.

Tom: The performance analysis shows they're doing better than some other protocols. In the good case, when everything is perfect, Multimmit orders a transaction block at t plus three delta time in expectation, or even at best two delta time <ref:2607.21021#pg1>. That’s significantly faster than Raptr’s expectation of t plus five delta <ref:2607.21021#pg3>.

Lu: In the common case, when we have up to f faulty processors, an honest chain's block gets finalized by t plus three delta time on average <ref:2607.21021#pg3>. This suggests good performance even when things aren't perfect.

Meng: If I were deploying this at scale, what about the actual cost of running all these voting rounds and proposal checks? Is it feasible for production workloads?

Tom: The analysis confirms that correct processors follow the proposal validity conditions within t plus two delta time <ref:2607.21021#pg3>. And nullification attempts by faulty producers fail because correct processors can demonstrate the necessary evidence, which requires twenty-one messages, is never accumulated by just the faulty messages alone.

Jane: That level of certainty in the voting process sounds reassuring for building reliable systems. So they’re saying that even with Byzantine faults, correct processors can reliably reach a decision quickly <ref:2607.21021#pg3>?

Paper summary: Lalam: They guarantee membership finality through Lemma thirteen which states that if a block is membership-finalized by an L-notarization, no incompatible block can be certifiable <ref:2607.21021#pg3>. The threshold for this guarantee is exactly thirty plus one, because the proof shows twenty plus the number of faulty producers plus one endorsing votes suffice against those faulty ones <ref:2607.21021#pg3>.

Tom: That means for membership finality, we need a threshold of thirty plus one endorsements <ref:2607.21021#pg3>. It’s a concrete number that tells us the required security level for that guarantee.

Lu: Block inclusion is covered by Theorem three, which ensures that if a block lies above the base of an L-notarization for view v, it's either membership-finalized by every correct processor or it extends the proposed tip on chain i <ref:2607.21021#pg3>. This guarantees blocks are ordered correctly according to the next finalized leader block even if placement waits for a later view.

Meng: So, what is the main thing this means for us when we're thinking about deploying AI models that need to agree on a sequence of actions? Does it simplify the complexity or just move it somewhere else?

Jane: It seems like Multimmit provides a middle ground between pessimistic and optimistic approaches. You get certified ordering by finalizing a prefix supported by a quorum, but you don't have to wait for every single piece of data before starting the process <ref:2607.21021#pg1>.

Tom: It keeps no processor blocked or fetching on the critical path, which is huge for keeping things responsive. It’s about getting a prefix finalized quickly and then ordering the rest later <ref:2607.21021#pg3>.

Lu: The core idea is proposing sequences of batches without needing all voters to hold the corresponding data, which supports the longest initial segment they possess <ref:2607.21021#pg3>. That’s ambitious for a consensus protocol.

Meng: I worry about that sensitivity to order if we are dealing with very fast updates, you know? If one batch is missing early on, it can really hurt the whole proposal <ref:2607.21021#pg3>.

Jane: That’s a valid concern. The authors do admit that this sensitivity to order is the remaining weakness they refer to as easy spoiling, and they mention that Raptr mitigates this with a reputation mechanism, but that mitigation is reactive <ref:2607.21021#pg3>.

Tom: So it’s not a perfect solution for every scenario, but it’s designed to be much faster than what we used before, like Raptr which took five delta time in the good case <ref:2607.21021#pg3>. It's about improving the practical performance under realistic network conditions <ref:2607.21021#pg3>.

Paper summary: Lu: The implication is that we can achieve strong censorship resistance while still aiming for low latency in favourable conditions, provided we have enough processors to meet the n greater than five f plus one requirement <ref:2607.21021#pg1>.

Jane: So, ultimately, Multimmit seems to be a way to balance the need for guaranteed ordering with the need for speed in a system where data availability isn't always immediate <ref:2607.21021#pg3>. What we’re seeing here is how they try to keep the consensus objects small even when transaction volume grows <ref:2607.21021#pg3>.

Tom: It's about keeping the size of these consensus objects independent of how many transactions you have, which is a key win for scalability <ref:2607.21021#pg3>.

Meng: For deployment, I’d need to see some real traffic data on this to know if that constant time performance holds up when it's actually under load and we're dealing with unpredictable network delays <ref:2607.21021#pg2>.

Jane: It sounds like they’ve done the heavy lifting on the theoretical side, showing that even with these complex ordering rules, correctness is achievable in a partially synchronous model where messages might be delayed by a bound delta <ref:2607.21021#pg2>.

Tom: So to wrap up this look at Multimmit: Extending Blocks for Faster Finality, the authors are proposing a middle ground protocol for State Machine Replication. They use proposal-relative voting and an extension voting mechanism to allow voters to endorse blocks beyond the proposed tips <ref:2607.21021#pg1>.

Jane: The key claim is that this design prioritizes low latency while maintaining strong censorship resistance, even when dealing with Byzantine faults, by finalizing a prefix supported by a quorum quickly <ref:2607.21021#pg3>. It’s about not blocking processors or fetching on the critical path for every single transaction.

Lu: The implication for the field is that we can achieve strong guarantees on total ordering and membership finality with consensus objects whose size does not grow with transaction volume <ref:2607.21021#pg3>. This keeps things efficient at scale.

Meng: From a deployment standpoint, it suggests a path toward more responsive systems that still have the necessary safety guarantees for distributed applications.

Tom: It’s about finding that sweet spot between certified and uncertified approaches, offering better performance in the common case than previous state-of-the-art methods like Raptr <ref:2607.21021#pg3>.

Jane: The paper shows that even with delays bounded by delta, correct processors can adhere to proposal validity conditions quickly and lead to L-notarization within t plus three delta time <ref:2607.21021#pg3>. That’s

Conclusion: Tom: So we're wrapping up our look at Multimmit, which is this protocol for state machine replication that tries to find a middle ground between slow, super-safe systems and fast, less certain ones.

Jane: It’s about taking this idea of ordering blocks across many chains and making the actual finalization happen much quicker by using proposal relative voting.

Lu: The authors are aiming for low latency while keeping strong censorship resistance, even when you have a bunch of bad actors trying to mess with the data flow.

Meng: From my side, what this means is that we might be able to get better performance under realistic network conditions without totally sacrificing the safety guarantees we need for production systems.

Lalam: It’s about keeping those consensus objects small, meaning the size of the data needed to reach a decision doesn't grow with how many transactions you have happening on the blockchain.

Tom: Exactly. It’s not just about making things faster; it’s about making them scalable in a way that respects what we need from a reliable system.

Jane: So, in short, Multimmit is trying to show us how to get fast finality by letting voters support what they have available right now without waiting for everything else.

Tom: It’s the trade off between waiting for full data versus finalizing a prefix that a quorum already agrees on.

Lu: The core idea is proposing sequences of batches where voters only need to hold the longest initial segment they actually possess, which supports that optimistic path really well.

Meng: That sensitivity to order is still something they flag as "easy spoiling" if you have very fast updates and some early data gets missed.

Jane: So, the big question we leave with is how robust this optimistic approach truly is when things get under heavy load and network delays become unpredictable.

London School of Economics · Commonware

cs.DC

Submitted: 2026-07-23

Updated: 2026-11-12

Code: https://github.com/commonwarexyz/monorepo

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: Multimmit is a protocol designed for State Machine Replication (SMR) that integrates multi-chain data dissemination with a consensus skeleton derived from Minimmit.

Key concepts

Proposal-relative voting
Voters report how much they can endorse a leader's proposal on each chain. This allows the system to quickly determine the extent of agreement across multiple chains without waiting for every single transaction to be finalized by a new leader.
Extension voting mechanism
This feature lets votes endorse fresh blocks beyond the initially proposed tips. This removes the need to wait for a new leader's proposal for every transaction, significantly reducing latency on the critical path.
Quorum Certificates (QCs)
These are small consensus objects used to establish total ordering. They are categorized into safe-to-extend tips and finalized tips, which dictate the sequence of blocks. This structure ensures that faulty producers cannot disrupt the ordering of transactions.
Membership finality threshold
The minimum number of votes required to guarantee that a block is membership-finalized (meaning no incompatible block can be certified). The paper proves this threshold is exactly 3f + 1, ensuring strong guarantees against faulty processors.

Terminology

Summary

Multimmit is a protocol designed for State Machine Replication (SMR) that integrates multi-chain data dissemination with a consensus skeleton derived from Minimmit. p. 2

Where the paper says it

Raptr mitigates the attack with a reputation mechanism, but the mitigation is reactive, in that each faulty processor spoils before it is blamed, and reputations must be forgiving enough to readmit processors after periods of asynchrony, so that any reset re-arms the same attack. 1 Our contributions We present Multimmit, a protocol that combines multi-chain data dissemination with the consensus skeleton of Minimmit [24], in which a single round of voting suffices for finality under the assumption that n ≥ 5f + 1, for n the number of processors and f the number that may be faulty.

It operates under a partially synchronous model where messages may experience arbitrary delays before being delivered within a known bound delta. p. 1
Where the paper says it

The core challenge is to ensure that all correct processors agree on the same sequence of transactions (Consistency), while also guaranteeing that new transactions are eventually included (Liveness), even in the presence of Byzantine faults, where corrupted processors may behave arbitrarily. Protocols for SMR typically operate in the partially synchronous model [28], in which messages may be delayed arbitrarily before an unknown time GST (the Global Stabilisation Time), but are delivered within a known bound ∆ thereafter.

The system requires n at least 5f + 1 processors to achieve finality in one round of voting per view. p. 0
Where the paper says it

If the data behind a single batch early in the sequence is withheld, most voters can support only a short prefix, and the proposal finalises little or nothing, however much available data it references: individual faulty producers can therefore still deny the system its optimistic path. We present Multimmit, a protocol for n ≥ 5f + 1 processors that combines a consensus layer requiring one round of voting per view with multi-chain data dissemination.

The core mechanism involves proposal-relative voting, where the leader proposes tips for every chain, and each voter reports the extent to which it can endorse that proposal on each chain. p. 2

Where the paper says it

• Proposal-relative voting. The leader proposes tips for every chain, certified or not, and each voter responds with a single vote, reporting per chain how far up the chain it can endorse the proposal.

An extension voting mechanism further allows votes to endorse fresh blocks beyond the proposed tips, effectively removing the need to wait for a new leader's proposal for every transaction's critical path.

The design prioritizes low latency and fault tolerance. p. 2

Where the paper says it

The design has three principal benefits, which we quantify and compare with the state of the art in Section 3. Low latency.

A faulty producer can only delay its own chain’s blocks, imposing at most a one-view wait on other chains for total ordering placement. p. 0
Where the paper says it

A transaction block disseminated at time t is then ordered by t + 3δ in expectation and t + 2δ at best, where δ bounds message delay, these figures being measured from the dissemination of the transaction block itself rather than from the leader’s proposal. Performance degrades gracefully in the presence of faults: a faulty producer can delay only its own chain’s blocks, costing other chains at most a one-view wait for placement in the total ordering.

Multimmit guarantees strong censorship resistance: no single leader can simultaneously finalize its leader block while excluding a fresh, well-circulated block from an honest chain. p. 0
Where the paper says it

Performance degrades gracefully in the presence of faults: a faulty producer can delay only its own chain’s blocks, costing other chains at most a one-view wait for placement in the total ordering. The protocol also provides a strong censorship-resistance guarantee, by which no leader can both finalise its leader block and exclude a fresh, well-circulated block of an honest chain.

Performance analysis shows that in the good case (synchrony, all processors correct), Multimmit orders a transaction block at t + 3 delta in expectation and t + 2 delta at best, compared to Raptr's t + 5 delta expectation. In the common case (synchrony, correct leader, up to f faulty processors), an honest chain’s block is finalized by t + 3 delta on average. p. 3

Where the paper says it

In the common case, an honest chain’s block disseminated at time t is still finalised by t + 3δ in expectation, and finalisation means more than the eventual inclusion that certification alone already provides: the block’s inclusion and the content of its chain’s contribution to the ordering are fixed, and any leader block subsequently finalised, by whichever leader and however that leader behaves, must place the block in the total ordering. Placement in the total ordering therefore accompanies finalisation at t + 3δ unless the block is queued behind a lagging faulty chain, and completes by t + 5δ in expectation in any case.

The protocol maintains small consensus objects whose size is independent of transaction volume. p. 0

Where the paper says it

The protocol also provides a strong censorship-resistance guarantee, by which no leader can both finalise its leader block and exclude a fresh, well-circulated block of an honest chain. Consensus objects total tens of kilobytes per view, independent of transaction volume.

Total ordering is established through Quorum Certificates (QCs), which are categorized into safe-to-extend tips (V-QCs) and finalized tips (L-QCs). p. 7
Where the paper says it

First, leader blocks contain no transactions; their role is to coordinate the chains of transaction blocks (described next). Second, the objects playing the role of M-notarisations, which we call V-QCs, certify somewhat more (and are correspondingly larger).

The extraction rules for these QCs dictate the total ordering, ensuring that faulty producers cannot spoil the optimistic path. p. 3
Where the paper says it

5δ in expectation, and by easy spoiling that finalisation may in any case order little or nothing. In short, Multimmit establishes a total ordering that faulty producers cannot spoil before Raptr establishes the ordering that they can.

Liveness is guaranteed via view progression mechanisms utilizing nullifications and V-QCs/L-QCs to ensure every correct processor eventually enters every view. p. 6

Where the paper says it

To this end, a processor that sees no progress in view v will eventually time out and send a nullify(v) message, indicating that it wishes to abandon the view. While no protocol can ensure that every view produces an Lnotarisation, Minimmit ensures that every view produces at least one of the following, either of which suffices: • An M-notarisation (‘M’ for ‘mini’) for a view v block b: a set of 2f + 1 votes for b.

Finalization from the vote pool ensures that a processor with n - f or more votes for a leader block can finalize it, and this process is monotone. p. 6
Where the paper says it

While no protocol can ensure that every view produces an Lnotarisation, Minimmit ensures that every view produces at least one of the following, either of which suffices: • An M-notarisation (‘M’ for ‘mini’) for a view v block b: a set of 2f + 1 votes for b. This proves that no other view v block can receive an L-notarisation, since the two vote sets would share (2f + 1) + (n − f) − n ≥ f + 1 processors, hence a correct one, and correct processors vote at most once per view.

The total ordering extracted from an L-QC specifies the sequence of blocks, and the extraction apparatus (Tips, Tips*) determines whether blocks are safe to extend or finalized. p. 9
Where the paper says it

Finalisation and ordering. It will help throughout to keep the following picture in mind, distinguishing the transaction blocks a quorum certificate finalises from the portion of the total ordering that can be extracted from it.

This ordering ensures that faulty producers cannot influence other chains' blocks prior to Raptr achieving its ordering.

The protocol's summary highlights a middle ground between certified (pessimistic) and uncertified (optimistic) approaches: it proposes sequences of batches without requiring voters to hold all data, supporting the longest initial segment they possess, and finalizes a prefix supported by a quorum, thus keeping no processor blocked or fetching on the critical path.

Detailed analysis confirms that correct processors adhere to proposal validity conditions within t + 2 delta. p. 7

Where the paper says it

By the time the proposal arrives (strictly, within δ of this time), every correct processor holds the parent’s M-notarisation and the interim nullifications. All correct processors therefore vote, and there are at least n − f of them, so the proposal receives an L-notarisation and is finalised.

Nullification attempts by faulty processors fail because correct processors can demonstrate the necessary evidence (requiring 2f+1 messages) is never accumulated by faulty messages alone. p. 2
Where the paper says it

1 Our contributions We present Multimmit, a protocol that combines multi-chain data dissemination with the consensus skeleton of Minimmit [24], in which a single round of voting suffices for finality under the assumption that n ≥ 5f + 1, for n the number of processors and f the number that may be faulty. 1 We work in the standard partially synchronous model: messages may be delayed arbitrarily before an unknown time GST (the global stabilisation time), and are delivered within a known bound ∆ thereafter.

Every correct processor votes for the unique candidate block by t + 2 delta, leading to an L-notarization of within t + 3 delta. p. 7
Where the paper says it

During synchrony, a correct leader selects the greatest v ′ for which it holds an Mnotarisation and proposes. By the time the proposal arrives (strictly, within δ of this time), every correct processor holds the parent’s M-notarisation and the interim nullifications.

Data availability is guaranteed: a correct processor missing data requests it from all processors, and after GST, a correct holder responds within 2 delta. p. 5

Where the paper says it

If pi and pj are correct and if pi receives the transaction tr then, for some t, tr ∈ logj (t). As is common for protocols that separate data dissemination from ordering, what the protocol explicitly guarantees for the transaction blocks entering the log is data availability (sufficiently many correct processors hold the data of each such block for it to be retrievable); how processors retrieve the data of blocks they are missing is left as an implementation detail.

Possession of reference chain V-QCs is also guaranteed because leader blocks on the reference chain are received with 2f+1 votes. p. 1
Where the paper says it

They also couple dissemination to consensus structurally, since a block enters the ordering only once later blocks reference it, so that placement depends on the continued growth of the graph. Multi-chain designs such as Autobahn [34] retain the leader-based structure, decouple the two concerns, and are the starting point for this paper.

Membership finality is established by Lemma 13: if a block b is membership-finalized by an L-notarization, no incompatible block can be certifiable. p. 3

Where the paper says it

The protocol provides a guarantee of block inclusion that does not depend on the leader. If a fresh transaction block produced by a correct processor reaches all correct processors before they vote in a view, then either the view finalises nothing at all, or the block’s membership of the eventual ledger is settled in that view and it enters the total ordering by the next finalised leader block, at the latest.

The threshold for this guarantee is exactly 3f + 1, as the proof shows that 2f + f a + 1 endorsing votes suffice against f a faulty processors, forcing the optimal threshold of 3f+1. p. 7
Where the paper says it

Upon receiving a block b on pi ’s chain, each processor sends a DA-vote (‘data availability vote’, a threshold signature share) for b back to pi , who forms and disseminates the resulting DA-certificate from n − 2f shares. 2 A DA-certificate ensures data availability (at least n − 3f ≥ 2f + 1 correct processors hold the block, so it can always be recovered) and uniqueness, since two certified blocks at the same height of the same chain would give two sets of n − 2f DA-voters intersecting in n − 4f ≥ f + 1 processors, and correct processors DA-vote at most once per (chain, height).

Block inclusion (Theorem 3) ensures that if a block b lies above the base of an L-notarization for view v, it is either membership-finalized by every correct processor or extends the proposed tip on chain i. p. 3

Where the paper says it

The protocol provides a guarantee of block inclusion that does not depend on the leader. If a fresh transaction block produced by a correct processor reaches all correct processors before they vote in a view, then either the view finalises nothing at all, or the block’s membership of the eventual ledger is settled in that view and it enters the total ordering by the next finalised leader block, at the latest.

This guarantees that blocks are ordered correctly according to the next finalized leader block, even when placement awaits a later view. p. 0
Where the paper says it

A transaction block disseminated at time t is then ordered by t + 3δ in expectation and t + 2δ at best, where δ bounds message delay, these figures being measured from the dissemination of the transaction block itself rather than from the leader’s proposal. Performance degrades gracefully in the presence of faults: a faulty producer can delay only its own chain’s blocks, costing other chains at most a one-view wait for placement in the total ordering.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Low latency improvement: The system achieves transaction block ordering in expectation at t + 3δ and at best at t + 2δ in synchronous, correct cases, which is roughly two message delays better than Raptr's expected t + 5δ. This reduction is achieved by removing the wait for the leader’s next proposal from every transaction’s critical path through proposal-relative voting and extension voting.

  2. Robustness improvement: A faulty producer can delay only its own chain’s blocks, costing other chains at most a one-view wait for placement in the total ordering, and easy spoiling has no analogue, as faulty producers can deny it its optimistic path for k consecutive proposals is mitigated by Multimmit's mechanism.

  3. Censorship resistance improvement: The protocol provides a guarantee of block inclusion that does not depend on the leader; if an honest producer’s block reaches all correct processors before they vote in a view, either the view finalises nothing at all, or the block’s membership of the eventual ledger is settled in that view and it enters the total ordering by the next finalised leader block, at latest.

  4. Throughput improvement: The consensus layer objects total tens of kilobytes per view, independent of transaction volume, allowing transaction data to travel only once from each producer to all, enabling finalisation rates that are roughly at the rate at which validators can receive data.

  5. Latency reduction via extension votes: Extension votes remove a message delay from the critical path because a transaction block need only reach the voters before they vote, rather than the leader before it proposes, reducing latency by a further δ on average.

  6. Handling of Byzantine leaders: Against a greedy Byzantine leader seeking finalisation, "the block inclusion theorem applies: either the view finalises nothing, or every fresh honest block that reached the voters is membership-finalised in the view (no competing block ever certifiable) and ordered at latest by the next finalised leader block."

  7. Formal specification for implementation: The paper provides a complete formal specification with proofs of consistency and liveness, along with concrete sizes for all objects, allowing for direct implementation guidance via pseudocode.

Abstract

To meet the throughput demands of blockchain systems, protocols for State Machine Replication increasingly have many processors disseminate transaction blocks in parallel. Certified designs require availability certificates before blocks enter the ordering process, which is robust but adds latency. BlueBottle, the leading uncertified design under n at least 5f+1 (n processors, at most f Byzantine), reduces latency in favourable conditions but can put fetching missing data on the critical path. Raptr, the state of the art under n at least 3f+1, avoids fetching on the voting path, but transactions wait for a leader's proposal and two voting rounds, and the leader controls the proposed sequence. We prove that strengthening the resilience assumption alone cannot remove Raptr's second voting round. We present Multimmit, a protocol for n at least 5f+1 that builds on Raptr's approach and finalises leader blocks after a single round of voting, improving latency by at least one message delay. Extension votes let voters endorse fresh transaction blocks omitted from the leader's proposal: 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. Producer chains are interleaved by a prescribed rule, not in a leader-chosen sequence. Payments are final within a single round trip, once the producer assembles n-f acknowledgments into a transferable receipt. With 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 100k to 1M transactions per second. At 100k, it is essentially unchanged under 0.1% message loss and rises by a factor of 1.4 with nine validators crashed; these conditions slow BlueBottle and Raptr, respectively, by more than an order of magnitude.

Sources

Related papers