Source-linked AI summary
Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback
Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, Zhuolun Xiang
TL;DR
Existing BFT SMR systems trade linear happy-path communication for robustness under asynchrony. The paper develops Jolteon and Ditto, using a 2-chain design and asynchronous fallback, and reports that Ditto adapts across optimistic and faulty conditions while preserving linear and quadratic costs on the respective paths.
Problem
Existing systems either provide linear happy-path communication without liveness under asynchrony or robust progress with quadratic communication.
Method
Ditto replaces partially synchronous view synchronization with an asynchronous fallback, while Jolteon uses a quadratic view-change and 2-chain commits to reduce HotStuff latency.
Results
Ditto performs like Jolteon under optimistic conditions and like VABA during attacks, with 50% better optimistic-path throughput than VABA.
Takeaways & Limitations
Ditto provides linear communication during synchrony, quadratic communication during asynchrony, and robust progress under asynchronous conditions and DDoS attacks.
Takeaways & Limitations
During asynchrony or DDoS attacks on leaders, DiemBFT and Jolteon have no liveness guarantees.
Abstract
from arXiv · showhide
Existing committee-based Byzantine state machine replication (SMR) protocols, typically deployed in production blockchains, face a clear trade-off: (1) they either achieve linear communication cost in the happy path, but sacrifice liveness during periods of asynchrony, or (2) they are robust (progress with probability one) but pay quadratic communication cost. We believe this trade-off is unwarranted since existing linear protocols still have asymptotic quadratic cost in the worst case. We design Ditto, a Byzantine SMR protocol that enjoys the best of both worlds: optimal communication on and off the happy path (linear and quadratic, respectively) and progress guarantee under asynchrony and DDoS attacks. We achieve this by replacing the view-synchronization of partially synchronous protocols with an asynchronous fallback mechanism at no extra asymptotic cost. Specifically, we start from HotStuff, a state-of-the-art linear protocol, and gradually build Ditto. As a separate contribution and an intermediate step, we design a 2-chain version of HotStuff, Jolteon, which leverages a quadratic view-change mechanism to reduce the latency of the standard 3-chain HotStuff. We implement and experimentally evaluate all our systems. Notably, Jolteon's commit latency outperforms HotStuff by 200-300ms with varying system size. Additionally, Ditto adapts to the network and provides better performance than Jolteon under faulty conditions and better performance than VABA (a state-of-the-art asynchronous protocol) under faultless conditions. This proves our case that breaking the robustness-efficiency trade-off is in the realm of practicality.
1 Introduction
Existing BFT protocols trade linear communication in favorable conditions for robustness under asynchrony. The paper introduces Jolteon and Ditto to combine efficient operation with stronger fault and network-delay handling.
- Motivation: Linear protocols reduce happy-path communication but lose liveness under asynchrony, while robust leaderless protocols require quadratic communication even in good conditions.This trade-off matters for production blockchains exposed to unpredictable delays and targeted DDoS attacks.
- Ditto: Ditto replaces HotStuff/DiemBFT view synchronization with an asynchronous fallback that guarantees progress without extra asymptotic communication cost.It switches between the happy path and fallback without additional rounds and retains pipelined operation.
- Jolteon: Jolteon preserves HotStuff’s linear good-network structure while using a 2-chain commit rule to reduce steady-state block-commit latency by 30%.The latency reduction costs a quadratic view-change, which does not affect experiments because the pacemaker is already quadratic.
- Evaluation: Ditto matches Jolteon under optimistic conditions and VABA during attacks, while achieving 50% higher optimistic-path throughput than VABA.Under faulty leaders, Ditto is 30-50% better than HotStuff and Jolteon; under network instability, those protocols drop to 0.
- Evaluation: The paper theoretically compares its implementations with HotStuff and VABA and evaluates their performance experimentally.The comparison covers communication complexity and block-commit latency.
2 Preliminaries
The paper models permissioned BFT replication with authenticated communication, adaptive Byzantine faults, and synchronous, asynchronous, or partially synchronous executions. It defines chained blocks, quorum certificates, rounds, views, and the protocol state used by HotStuff-derived systems.
- System Model: The system has n=3f+1 replicas, with an adaptive adversary controlling message delivery and corrupting up to f replicas.Messages among honest replicas are assumed eventually delivered.
- System Model: Synchronous executions bound honest-replica delays, asynchronous executions leave them unbounded, and partial synchrony bounds them only after GST.The n=3f+1 setting is the optimal worst-case resilience bound for the considered models.
- Cryptography and Certificates: The protocols use digital signatures, PKI, threshold signatures, and quorum certificates formed from 2f+1 signature shares.Quorum certificates authenticate blocks and connect them into a chain or block-tree.
- BFT SMR: BFT SMR provides safety and liveness, while validated BFT SMR additionally requires every committed transaction to satisfy an application-dependent validity predicate.The paper focuses on the core BFT SMR formulation and omits validity-check details.
- Terminology: HotStuff and DiemBFT order transactions by chaining proposals, with each commit covering the entire preceding chain prefix.Blocks contain a parent QC, round, view, transaction batch, and hash-derived identifier.
- Jolteon State: Jolteon’s steady-state protocol uses rotating round leaders, quorum certificates, a 2-chain lock rule, and a 3-chain commit rule.Replicas track voted and locked rounds, the current round, the highest QC, and the last-round timeout certificate.
3 Jolteon Design
Jolteon converts DiemBFT into a 2-chain protocol, retaining linear steady-state communication while accepting quadratic view-change cost to reduce commit latency. Its view-change handles bad rounds, but the protocol itself has no liveness guarantee during asynchrony or leader-targeted DDoS.
- Jolteon Design: Jolteon uses quadratic view-change to support safe proposals after asynchronous or faulty rounds, while keeping the steady-state protocol linear.The leader attaches a timeout certificate and extends the highest QC represented in it.
- Jolteon Design: A proposal is safe when it either directly extends the previous round’s block or extends at least the highest QC reported by the timeout certificate.The latter condition uses quorum intersection and nondecreasing qchigh values to prevent voting for proposals that conflict with committed blocks.
- Efficiency: Both DiemBFT and Jolteon have linear communication per round and decision under synchrony with honest leaders, but quadratic view synchronization under asynchrony or failures.Threshold signatures keep leader proposals and votes constant-sized, while all-to-all timeout messages create the quadratic synchronization cost.
- Limitations: During asynchrony or leader-targeted DDoS, Jolteon and DiemBFT have no liveness guarantee because replicas continue timing out without certifying or committing blocks.The paper characterizes this limitation as unavoidable for deterministic partially synchronous Byzantine agreement before GST.
- Transition to Ditto: Ditto addresses this limitation by replacing view synchronization with an asynchronous fallback whose quadratic cost matches the synchronization cost already paid by these protocols.The fallback is presented as a way to guarantee progress under asynchrony without adding asymptotic communication cost.
4 Ditto Design
Ditto combines Jolteon’s synchronous fast path with an MVBA-based asynchronous fallback. It retains linear communication during synchrony and provides expected quadratic communication and progress under asynchronous conditions.
- Ditto Design: Ditto has linear communication on the synchronous path, quadratic communication on the asynchronous path, and robust liveness under asynchronous network conditions.It is designed to strengthen the liveness guarantees of DiemBFT and Jolteon.
- Fallback: Ditto uses MVBA as a black-box fallback protocol to agree on and commit a new block after replicas enter fallback.MVBA provides agreement, external validity, and termination except with negligible probability under its stated guarantees.
- Path Transition: The synchronous path follows Jolteon’s 1-chain lock and 2-chain commit rule, while MVBA agreement supports safe transfer between synchronous and fallback paths.The protocol is structured so either the synchronous path progresses or enough replicas time out to invoke fallback.
- Steady State: In steady state, leaders propose blocks carrying the current high QC, and replicas vote only for first proposals that extend the QC from the immediately preceding round.The protocol advances rounds and updates locks when new QCs arrive.
- Fallback: Replicas initiate fallback by broadcasting timeout messages with their highest QC; after 2f + 1 matching timeouts, they enter fallback and exchange proof messages.Each replica records fallback state separately, and the fallback replaces Jolteon’s pacemaker.
- Fallback: When MVBA decides a block, replicas commit it and its ancestors, certify the block, and exit fallback before resuming other protocol steps.Certification follows commitment so the decided block becomes integrated into the chained protocol state.
- Efficiency: Ditto’s expected communication complexity is O(n) per decision during synchrony and O(n2) during asynchrony, with block-commit latency of 5 rounds and R+4 rounds, respectively.The asynchronous fallback commits a new block with probability 2/3 per instance; fallback latency can be reduced to R+3 rounds when MVBA already certifies its output.
5 Implementation and Evaluation
The evaluation compares Jolteon, Ditto, HotStuff, and 2-chain VABA across fault-free, crash-fault, and leader-attack settings. Jolteon improves block-commit latency, while Ditto preserves near-Jolteon performance in optimistic conditions and remains productive under faults and leader attacks.
- Implementation and methodology: The implementations and evaluations of 2-chain VABA and Ditto’s asynchronous fallback are outdated, while Jolteon and Ditto’s synchronous path are up to date.The systems are built on a high-performance open-source HotStuff implementation and evaluated using AWS deployments and reproducible benchmarking infrastructure.
- Jolteon evaluation: 200–300ms: Jolteon reduces block-commit latency versus 3-chain DiemBFT across 10, 20, and 50 nodes, with similar scaling.These measurements use WAN experiments without replica faults, with 500KB mempool batches and 512B transactions.
- Jolteon evaluation: Under crashes of 0, 1, or 3 nodes, Jolteon outperforms 3-chain DiemBFT in most settings because its 2-chain rule enables more frequent commits.The authors conclude that the extra round-trip of 3-chain DiemBFT provides little practical benefit relative to its theoretically linear view-change.
- Ditto evaluation: Under synchronous, fault-free conditions, Ditto performs almost identically to Jolteon, while 2-chain VABA performs worse because every replica synchronizes with O(n) leaders per round.Ditto’s asynchronous fallback and Jolteon’s quadratic pacemaker are not triggered in this setting.
- Ditto evaluation: Under leader attacks, HotStuff and Jolteon have zero throughput, whereas Ditto performs close to 2-chain VABA through its asynchronous fallback.Ditto’s exponential backoff lets it skip most view timers during prolonged leader attacks and enter fallback directly.
- Ditto evaluation: Ditto adapts to network behavior and achieves almost optimal performance, although 2-chain VABA can outperform it during intermittent asynchrony by avoiding Ditto’s timeout cost.That advantage comes with a significant cost when the network is good.
6 Related Work
The paper situates Ditto among BFT protocols that trade efficient happy-path communication for robustness, and presents it as a practical protocol combining synchronous and asynchronous operation without switching overhead.
- The evaluation compares 3-chain DiemBFT, Jolteon, Ditto, and 2-chain VABA under WAN conditions with 20 replicas, varying faults, and fixed batch and transaction sizes.
- HotStuff achieves O(n) decision cost but uses O(n^2) view synchronization, while asynchronous SMR protocols generally incur quadratic or amortized quadratic communication.
- Ditto combines synchronous and asynchronous paths without the overhead of composing separate consensus protocols as black boxes.
- Ditto offers asymptotically optimal communication in both happy and fallback paths while retaining pipelining and latency better than 3-chain HotStuff/DiemBFT and VABA.
- A separate limitation is that incorporating an optimistic 1-chain commit path is left for future work.
7 Conclusion and Future Work
The paper concludes that Ditto combines efficient communication with progress under asynchrony and DDoS attacks, while Jolteon reduces latency through a 2-chain design. Future work targets an optimistic 1-chain commit path.
- Ditto provides linear happy-path and quadratic fallback communication with progress guarantees under worst-case asynchrony and DDoS attacks.
- Jolteon uses quadratic view change to reduce the latency of standard 3-chain HotStuff.
- An optimistic 1-chain commit path remains future work for Jolteon and Ditto to improve fault-free latency.
A.1 Safety
The safety argument establishes that certified blocks form a consistent extension relation, implying that honest replicas commit the same transactions at each log position.
- A certified block has a quorum certificate, and QC-linked blocks define the extension relation used throughout the safety proof.
- A globally direct-committed block is supported by f +1 honest votes in the following round and updates replicas’ high QC state.
- If an honest replica commits a block, that block is globally direct-committed.
- At most one block can be certified in each round because a certified block prevents another block from gathering f +1 honest votes there.
- Every certified block at or after a globally direct-committed block extends that block, yielding comparability between any two globally direct-committed blocks.
- Because committed blocks share a unique prefix, all honest replicas commit the same block and transaction order at each blockchain position.
A.2 Liveness
The liveness proof shows that honest replicas continue entering higher rounds and eventually commit after stabilization, using honest-leader proposals and quorum progress.
- Rounds advance through proposals, quorum certificates, timeout certificates, and voting predicates that preserve increasing round progress.
- If message delays and round timeouts among honest replicas are finite, all honest replicas continue entering increasing rounds.
- When no QC exists and no honest replica has timed out, honest replicas vote for a proposal from the honest leader.
- After GST, an honest leader’s proposal reaches all honest replicas within 2∆ of the first honest replica entering the round.
- After GST, every honest replica eventually locally commits a block from a round higher than any specified round.
- The proof selects three consecutive honest-leader rounds, whose proposals and votes establish global direct commitment and then local direct commitment.
- Repeatedly proposing each client transaction by honest replicas ensures eventual commitment by all honest replicas.
B.1 Safety
The safety argument establishes that committed blocks remain mutually consistent across synchronous and asynchronous commit paths. Consequently, honest replicas commit the same block and transaction order at every blockchain position.
- B.1 Safety: A sync-committed block is directly committed through a 2-chain, while an async-committed block is the output of MVBA during fallback.
- B.1 Safety: Global direct-commit guarantees that f + 1 honest replicas vote for a proposal whose quorum certificate certifies the committed block.
- B.1 Safety: Certified blocks with equal rank are identical, and certified descendants of committed blocks must extend those blocks.
- B.1 Safety: Lemma 13 and Lemma 14 propagate the extension property across later views for async-committed and globally direct-committed blocks.
- B.1 Safety: Theorem 4 states that any two committed blocks are ordered by extension, so they cannot conflict.This follows by relating sync-committed and async-committed blocks through the extension lemmas.
- B.1 Safety: All honest replicas therefore commit the same block and do not commit different transactions at the same log position.
B.2 Liveness
The liveness results show that Ditto continues committing blocks under both synchronous faultless operation and asynchronous execution. Under the stated transaction-proposal assumption, every client transaction is eventually committed by all honest replicas.
- B.2 Liveness: If the network is synchronous and all replicas are honest, honest replicas keep committing new blocks with increasing round numbers.
- B.2 Liveness: MVBA invocations preserve external validity across honest replicas through the high-QC predicate.
- B.2 Liveness: If the network is asynchronous, all honest replicas keep committing new blocks with increasing ranks.MVBA agreement and termination allow replicas to converge on fallback decisions when ordinary commits stop.
- B.2 Liveness: Each client transaction is eventually committed by all honest replicas when honest replicas repeatedly propose it until commitment.