Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback

Paper: [1]

Summary

  • It is an SMR Protocol.
  • This paper has two SMR protocols:
    1. Jolteon: 2-chain variant of DiemBFT/HotStuff [2] with a quadratic view-change.
    2. Ditto: Jolteon + asynchronous fallback via VABA [3].
  • It uses the standard SMR definition (safety + liveness + external validity).
  • Jolteon is partially synchronous (eventually synchronous). Ditto is network-adaptive: partially synchronous happy path, asynchronous fallback.
  • It is adaptively secure.
  • \(n = 3f + 1\).

Motivation

  • Important: this paper builds on DiemBFT (LibraBFT), not the original HotStuff paper. DiemBFT is a production instantiation of HotStuff with a concrete TC-based pacemaker. The paper uses "HotStuff" and "DiemBFT" interchangeably throughout (stated explicitly in Section 2). The original HotStuff paper [2] never specified a pacemaker.
  • Existing linear protocols (DiemBFT) sacrifice liveness under asynchrony. Robust protocols (VABA) pay \(O(n^2)\) even in the happy path.
  • Key observation: DiemBFT's view synchronization (forming a TC via all-to-all timeout message exchange) is already \(O(n^2)\). So the linear view-change communication (leader proposal after a bad round carries only \(qc_{high}\)) is a theoretical milestone but practically irrelevant — the system already pays quadratic for synchronization.
  • Since view synchronization is already quadratic, making view-change communication quadratic (leader sends the full TC with \(2f+1\) \(qc_{high}\) values) does not change the asymptotic worst case, but enables a 2-chain commit rule, reducing block-commit latency by ~30%.

Jolteon

Core Insight

  • DiemBFT's 3-chain commit rule is forced by its linear view-change communication. After a bad round, the new leader's proposal carries only its own \(qc_{high}\), which is insufficient to prove safety with just 2 chains.
  • With a quadratic view-change communication (proposal includes the TC containing \(2f+1\) validators' \(qc_{high}\) values), the new leader can prove that no higher QC exists among honest replicas. This makes 2 chains sufficient for safety.
  • This is a co-design of the view-change mechanism with the commit rule.

Protocol (Figure 2)

  • Derived from DiemBFT (Figure 1) with changes in blue.
  • Block format: \(B = [id, qc, tc, r, v_{cur}, txn]\). The leader sets \(tc = tc_{r-1}\) if it entered round \(r\) via a TC, otherwise \(tc = \bot\).
  • Propose: Leader \(L_r\) multicasts \(B = [id, qc_{high}, tc, r, v_{cur}, txn]\).
  • Vote: Replica votes for the first valid proposal \(B\) in round \(r\) if \(r = r_{cur}\), \(v = v_{cur}\), \(r > r_{vote}\), and at least one of:
    1. \(B.r = B.qc.r + 1\) (direct extension: block extends parent from previous round), or
    2. \(B.r = B.tc.r + 1\) and \(B.qc.r \geq \max\{qc_{high}.r \mid qc_{high} \in B.tc\}\) (view-change: block is in the round after a TC, and the QC it extends is at least as high as the highest QC in the TC).
  • Lock (1-chain): On seeing a valid \(qc\), update \(qc_{high} \leftarrow \max(qc_{high}, qc)\).
  • Commit (2-chain): Whenever two adjacent certified blocks \(B, B'\) exist in the chain with consecutive round numbers (\(B'.r = B.r + 1\)), commit \(B\) and all ancestors.
  • Pacemaker: Identical to DiemBFT. TC-based: on timeout, multicast \(\langle \{r_{cur}\}_i, qc_{high} \rangle_i\). Upon \(2f+1\) timeouts, form a TC. Quadratic cost.

Why 2-chain is safe with quadratic view-change

  • Safety after view change relies on the leader proving that the QC it extends is the highest among honest replicas.
  • In HotStuff's linear view-change, the leader only sends its own \(qc_{high}\)—insufficient proof, requiring a 3rd chain so that \(f+1\) honest replicas lock before any commit.
  • In Jolteon's TC, the \(2f+1\) \(qc_{high}\) values collectively prove no higher QC exists (by quorum intersection with any certified QC's voters). The second vote condition enforces this: \(B.qc.r \geq \max\{qc_{high}.r \mid qc_{high} \in B.tc\}\).

Complexity comparison with DiemBFT

Metric DiemBFT (3-chain) Jolteon (2-chain)
Steady-state comm. \(O(n)\) (linear) \(O(n)\) (linear)
View-change comm. \(O(n)\) (linear) \(O(n^2)\) (quadratic)
View synchronization \(O(n^2)\) (quadratic) \(O(n^2)\) (quadratic)
Block-commit latency \(7\Delta\) \(5\Delta\)
Rounds to commit 7 messages 5 messages
  • The view-change cost increases from linear to quadratic because the proposal now includes the TC (\(2f+1\) \(qc_{high}\) values). But view synchronization (timeout message exchange) is already quadratic in both protocols, so this does not change the asymptotic worst case.

Limitations

  • No liveness under asynchrony or DDoS on leaders—same as HotStuff/DiemBFT. Throughput drops to 0.

Ditto

Design

  • Combines Jolteon's synchronous fast path with an asynchronous fallback protocol at no extra asymptotic cost.
  • Instead of synchronizing views that will fail anyway (timeout due to asynchrony or bad leader), fall back to an asynchronous protocol that robustly guarantees progress.
  • Ditto switches between sync and async paths seamlessly in the pipelined chaining fashion.

Steady State (Figure 4)

  • Identical to Jolteon except: the first block in a new view includes the \(qc_{coin}\) of the previous view (the coin-QC from the fallback leader election).
  • Replica keeps a boolean fallback-mode (initialized false). Does not vote for regular blocks when in fallback.
  • 2-chain commit applies to both regular blocks and endorsed fallback-blocks.

Asynchronous Fallback (Figure 5)

  • Triggered on timeout: enter fallback, set fallback-mode = true.
  • Each replica acts as a leader and builds a fallback-chain (f-chain) of 2 f-blocks:
    1. Height-1 f-block: extends \(qc_{high}\), contains transactions.
    2. Height-2 f-block: extends the f-QC of the height-1 block.
  • When \(2f+1\) height-2 f-QCs are collected, random leader election via threshold signatures: each replica signs the hash of the view number. \(f+1\) valid coin shares form a \(qc_{coin}\) that elects a leader with probability \(1/n\).
  • All replicas continue steady state from the elected leader's f-chain.
  • Safety: 1-chain lock and 2-chain commit apply uniformly across regular blocks and endorsed f-blocks. Endorsed f-QCs are handled as regular QCs for lock/commit.

Complexity (Theorem 1)

  • Synchronous path (honest leaders): amortized \(O(n)\) per block decision, \(5\) rounds block-commit latency.
  • Asynchronous fallback: expected \(O(n^2)\) per block decision, expected \(10.5\) rounds block-commit latency.
  • Async latency breakdown: 1 round timeout exchange + \(2 \times 2 = 4\) rounds for height-1 and height-2 f-blocks + 1 round for f-QC exchange + 1 round for randomness shares. Total = 7 rounds per fallback, commit with probability 2/3, so expected \(7 \times 1.5 = 10.5\) rounds.

2-chain VABA (by-product)

  • Disabling the synchronous path (setting timeout \(\tau = 0\)) yields an improved VABA with expected \(10.5\) rounds (down from \(16.5\) in [3]).
  • Correctness follows from Ditto's safety and liveness proofs.

Exponential Backoff

  • Under prolonged asynchrony, replicas use exponential backoff for the fallback timer: execute \(x\) consecutive async fallbacks, then multiply \(x\) by a constant factor (5 in experiments).
  • Under synchrony and honest leaders, \(x = 1\) always (single fallback then back to steady state).

Evaluation

  • Deployed on AWS (m5.8xlarge) across 5 regions: Virginia, California, Sydney, Stockholm, Tokyo. WAN experiments with 10, 20, 50 replicas.
  • Jolteon consistently outperforms 3-chain DiemBFT by 200–300ms latency (one round-trip across WAN). Both scale similarly.
  • Under crash faults: Ditto performs better than Jolteon (which drops to 0 throughput), close to 2-chain VABA. 2-chain VABA is most robust.
  • Under DDoS on leaders: DiemBFT and Jolteon drop to 0 throughput. Ditto and 2-chain VABA maintain liveness. Ditto's performance is close to 2-chain VABA.
  • Under combined crash faults + DDoS: Ditto slightly outperforms crash-only case due to exponential backoff skipping timer waits.

Concurrent work

  • Two concurrent 2-chain HotStuff variants: [4] and Rambaud (ePrint 2020:1480).
  • Rambaud relies on impractical cryptographic primitives to preserve linear view-change (still quadratic pacemaker). Fast-HotStuff does not provide implementation or evaluation.
  • Neither protocol provides comprehensive evaluation to showcase that quadratic view-change costs are negligible in practice.
  • "Most importantly, both protocols fail to realize the full power of 2-chain protocols missing the fact that the view-change can become robust and DDoS resilient" — this is what Ditto achieves.

Notes

  • The key conceptual contribution is the co-design of view-change mechanism and commit rule: once you accept that view synchronization is already quadratic (in DiemBFT's TC-based pacemaker), making view-change communication quadratic too costs nothing asymptotically but enables 2-chain commit.
  • This paper gives the clearest explanation of why DiemBFT (and by extension HotStuff) uses 3 chains: it is the price of a linear view-change communication. The 3rd chain ensures \(f+1\) honest replicas lock, compensating for the leader's inability to prove safety from collected evidence alone.
  • Notation difference from HotStuff: rounds and views are separated. In DiemBFT and Jolteon, the view number is always 0 (no async fallback). In Ditto, the view number increments after each async fallback.
  • The Ditto liveness proof (Appendix B, Theorem 5) is by induction on view numbers: in each view, honest replicas either commit in steady state or enter fallback and commit a new block with probability 2/3.

References

[1] Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. 2021. “Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback.” http://arxiv.org/abs/2106.10362.
[2] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. “HotStuff: BFT Consensus with Linearity and Responsiveness.” https://doi.org/10.1145/3293611.3331591.
[3] Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. 2019. “Asymptotically optimal validated asynchronous byzantine agreement.”
[4] Mohammad M. Jalalzai, Jianyu Niu, Chen Feng, and Fangyu Gai. 2021. “Fast-HotStuff: A Fast and Resilient HotStuff Protocol.” http://arxiv.org/abs/2010.11454.