Multimmit: Extending Blocks for Faster Finality

summary

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.

In short

Multimmit is a protocol for State Machine Replication that combines multi-chain data dissemination with a consensus skeleton based on Minimmit. It uses proposal-relative voting and extension voting to achieve low latency and high fault tolerance. The system guarantees strong censorship resistance and ensures blocks are ordered correctly even when placement waits for future leader proposals.

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 used across episodes

This episode discusses

The paper

Multimmit: Extending Blocks for Faster Finality · Read on arXiv

London School of Economics · Commonware

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.

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.

More episodes

← Home