Pith. sign in

REVIEW 1 major objections 4 minor 5 cited by

Raptr: Prefix Consensus for Robust High-Performance BFT

T0 review · 1 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Raptr claims that voting on block prefixes lets Byzantine-tolerant replication hit optimal latency and high throughput at the same time.

desk verdict Raptr's prefix-consensus mechanism is a genuine advance, but the safety proof has a load-bearing gap: the protocol allows two QC-votes per replica per round while certificate verification does not enforce distinct voters, so a Byzantine aggregator can form a QC with fewer than 2f+1 distinct replicas and break quorum intersection. read the letter →

arxiv 2504.18649 v2 pith:EH6QUWM7 submitted 2025-04-25 cs.DC

Andrei Tonkikh , Balaji Arun , Zhuolun Xiang , Zekun Li , Alexander Spiegelman This is my paper · ORCID
classification cs.DC MSC 68M1468M15
keywords Byzantinefaulttolerancestatemachinereplicationprefixconsensusblockvotingdatadisseminationpartialsynchronyquorumcertificatesatomicbroadcast
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Raptr is a protocol for Byzantine fault-tolerant state machine replication, letting a group of replicas maintain one ordered transaction log even when some are malicious or the network misbehaves, and it aims to show that the usual trade-off between speed and resilience is not necessary. The key idea is prefix consensus: rather than voting for or against a whole proposed block, each replica votes for the longest prefix of that block whose data it already has locally. Because a quorum of such votes certifies only a prefix, and later proposals are required to extend already-committed prefixes, different replicas can commit different prefixes of the same block without ever ordering them differently. If the proof is right, a leader-based BFT system can have the optimal 3-message-delay consensus latency, 5-message-delay ordering latency, and throughput comparable to DAG-based systems. The paper's experiments with 100 geo-distributed replicas report 260,000 transactions per second at sub-second latency, and only mild degradation when 1% of messages are dropped.

What carries the argument

The load-bearing mechanism is the pair (block hash, prefix) as the unit of voting, together with the rule 'certify the $S$-th largest prefix, commit the minimum prefix, extend the maximum prefix.' A quorum certificate certifies a prefix only when at least $S \ge f+1$ replicas voted for that prefix or larger, guaranteeing that a committed prefix's data is retrievable from at least one honest replica. A commit certificate commits the minimum prefix among a quorum of CC-votes, and the next round's entry rule forces the leader to extend the maximum certified prefix from a full-prefix QC, a CC, or a TC. This mechanism makes the availability quorum ($S$) independent of the safety quorum ($\lceil(n+f+1)/2\rceil$ votes), which is why full blocks can commit while only a minority of replicas have all the data. The implementation uses a no-commit-proof aggregate signature scheme and groups batch digests into $K$ sub-blocks so that verifying heterogeneous prefix votes costs constant-size pairing work.

What would settle it

Instrument a Raptr deployment, inject network partitions or Byzantine leaders that send different blocks in the same round, and search the logs for two valid quorum certificates with the same round number but different block hashes; Lemma C.2 proves such a pair cannot exist, so finding one would settle that the safety argument is wrong.

Watch

Extended reading notes

Core claim

The central claim is that non-binary voting on block prefixes preserves atomic broadcast safety while removing the latency cost of certifying data before consensus. Replicas sign votes of the form (block hash, prefix), and a quorum certificate is valid if it contains a quorum of votes for the same block; it certifies the prefix that is the $S$-th largest among the votes, with $S \ge f+1$, so at least one honest replica holds all batches in that prefix. A commit certificate is built from a quorum of votes on a QC and commits the minimum certified prefix among them. Quorum intersection then forces every later proposal to extend the maximum certified prefix, yielding the prefix-containment property that underlies safety. Raptr therefore commits full blocks in the common case, degrades to partial-prefix commits when batches are slow, and reaches the optimal 3-message-delay consensus latency with a 5-message-delay ordering latency.

Load-bearing premise

The design assumes that a malicious party cannot forge the aggregated digital signatures behind any certificate, and that an honest participant never signs two different statements in the same round; if either fails, the ordering guarantee collapses.

Editorial extensions

If this is right

  • The optimal-latency bound need not be purchased with fragile optimistic data dissemination: Raptr shows a leader-based BFT protocol can commit in 3 message delays and order in 5 while sustaining 260k TPS at sub-second latency in a 100-replica deployment.
  • Data certification can run in the background rather than on the critical path: the paper reports that Raptr eliminates the two message delays of quorum store proof creation, giving up to 25% lower end-to-end latency than the baseline at low to moderate load.
  • Full blocks can be committed even when only $f+1$ replicas have all the data, because the remaining votes in the safety quorum may be partial; this is what keeps throughput high under load and steady under 1% message loss.
  • In the full network glitch experiment, Raptr keeps a flat transaction rate with no failed rounds and roughly 15% higher latency, while the compared certified DAG protocol loses its smooth block rate and the uncertified DAG protocol spikes sharply.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because prefix votes are agnostic to whether the underlying proposal is a leader's block or a DAG anchor, a similar partial-vote rule could be layered onto uncertified DAG protocols, targeting exactly the missing-node stall the paper identifies as their weakness.
  • The decoupling of the availability quorum from the safety quorum is a general resource: any BFT protocol that separates data availability from ordering might use a smaller availability threshold without weakening safety, as long as committed prefixes remain nested.
  • Optimistic proposal techniques or K parallel instances of Raptr, which the paper notes are orthogonal, should cut the one-message-delay block-inclusion time further; a direct test would be rerunning the 100-replica evaluation with eight parallel instances and comparing the reported 610 ms latency.
  • A testable tuning question the paper leaves open is the QC-vote timer: too long makes replicas wait unnecessarily, too short makes them vote on low prefixes that the next leader must extend, so the optimal setting likely depends on network jitter and batch size distribution.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper introduces Raptr, a leader-based BFT state machine replication protocol that augments the Jolteon*/Quorum Store baseline with prefix consensus. Instead of voting only on complete blocks, replicas vote on the longest available prefix of a proposed block; quorum certificates certify the S-th largest prefix among votes, commit certificates commit the minimum certified prefix in a quorum, and the next leader extends the maximum certified prefix. The paper claims a common-case ordering latency of five message delays, high throughput under favorable conditions, and graceful degradation under message loss. It provides full pseudocode, formal safety and liveness proofs in Appendices B and C, and an implementation evaluated on a 100-replica geo-distributed testbed against Shoal++, Mysticeti, Aptos+, and Baby Raptr.

Significance. If the protocol is correct, Raptr would be a significant practical contribution: it aims to eliminate the latency-versus-robustness tradeoff between pessimistic and optimistic data dissemination in BFT SMR while keeping throughput comparable to certified DAG protocols. The paper is commendably concrete: it ships detailed pseudocode, self-contained formal proofs, an open-source implementation, and a large-scale evaluation against externally developed baselines (Mysticeti, Shoal++). The latency breakdown and fault-injection experiments are informative. However, I find a load-bearing gap in the safety argument: the QC verification does not enforce that the votes in a quorum come from distinct replicas, while the protocol explicitly permits two QC-votes per replica per round. A Byzantine aggregator can exploit this to build quorums whose honest intersection is empty, invalidating the formal safety proof. The central idea is likely repairable with a distinct-voter check, but the manuscript as submitted does not establish the claimed Byzantine safety guarantee.

major comments (1)
  1. [Appendix C, Lemmas C.1-C.5; Algorithms 2 and 5] VerifyQC (Algorithm 2, lines 46-47) checks only that |qc.votePrefixes| >= ceil((n+f+1)/2) and that the aggregate signature verifies over the listed (replicaId, prefix) tuples; it does not require the replica identifiers to be distinct. Meanwhile, Algorithm 5 (lines 131-143) explicitly lets an honest replica issue two QC-votes for the same block: one on timer expiry with some prefix p < K and another when the full block is available with prefix K, and both votes are multicast. With the no-commit-proof instantiation of Section 6.2, these two votes are signed with different key shares corresponding to different prefix tags, so an aggregate signature over both tuples (q, p) and (q, K) verifies. A Byzantine aggregator can therefore include two votes from the same honest replica q in one QC, and the quorum-size check counts one physical replica twice. Formally, with n = 3f+1, a QC needs 2f+1 tuples; a Byzantine aggregator can assemble this from f Byzantine votes plus as few as ceil((f+1)/2) honest replicas each contributing two votes, i.e., from fewer than 2f+1 distinct replicas. Lemma C.1's supermajority quorum intersection applies to sets of replicas, not to multisets of votes, so two such QCs can intersect only in Byzantine replicas. This invalidates Lemma C.2 (no two different-block QCs in the same round), and with it the prefix-containment induction in Lemmas C.3-C.5 and Theorem C.7. It also breaks the assumption in Algorithm 6, line 158, that all same-round QCs have the same block hash. The statement in Section 5.2 that issuing more than two QC-votes would not violate safety is therefore not supported by the proof as written. The fix is to require qc.votePrefixes to contain distinct replica identifiers in VerifyQC, to aggregate at most one vote per replica when forming a QC, and to re-verify all quorum-intersection arguments under that requirement.
minor comments (4)
  1. [Appendix A] The sentence 'the ⪯ relation is commutative' is mathematically imprecise for a binary relation; the intended statement is presumably that the relation is transitive and that qc1 ⪯ qc2 implies messages(chain(qc1)) is a prefix of messages(chain(qc2)).
  2. [Section 5.2, Algorithm 5] The QCVote function updates lastQCVote to the newly issued (round, prefix), so a timer-based vote followed by a full-prefix vote is intentionally allowed; this design choice should be revisited explicitly after enforcing distinct-voter checks, since it is the source of the duplicate-counting ambiguity in QC formation.
  3. [Section 6.2] The description of the simplified no-commit-proofs scheme should state whether the same replica identity may appear with multiple prefix tags in one aggregate, and how verification enforces the intended quorum semantics; the current prose says only that 'signature verification will be evaluated based on the claimed prefix numbers and corresponding public key shares.'
  4. [Appendix C, Lemma C.8] The phrase 'after correcting for any possible clock speed differences' is vague; the proof should state the clock-drift assumption explicitly or cite a standard bounded-drift model, since the liveness argument depends on timer lower bounds.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Raptr's latency and safety claims are derived from protocol structure and quorum arguments, with self-citations used only as component baselines or external benchmarks.

full rationale

The paper's central latency claim, 3-message-delay consensus latency and 5-message-delay ordering latency, is obtained by counting message hops in the protocol pseudocode (proposal, QC-vote, CC-vote) and from the statement that blocks are proposed every two message delays (Section 5.4). This is a structural derivation, not a fit to measured data and not an equation defined in terms of the target result. The claimed optimality is referenced to external lower-bound results [1, 25]; although one lower-bound paper shares a co-author, the lower bound itself is not derived or replaced inside this paper, so the citation is independent evidence rather than a self-imported theorem. Safety is argued in Appendix C through quorum intersection (Lemma C.1), the single-CC-vote-per-round rule (line 110), and the induction on ranks in Lemmas C.3-C.5; these are self-contained protocol arguments that do not assume prefix containment as an input. Self-citations to Jolteon* [41] and Quorum Store [35] describe the baseline components on which Raptr builds, but the novel prefix-voting and partial-commit mechanism is analyzed independently, and the evaluation also includes the external Mysticeti [7] baseline. The reviewer's concern about two QC-votes per round is a potential correctness or safety gap in the proof, not a circular reduction: no fitted parameter is renamed as a prediction and no definition presupposes the theorem being proved. Therefore the derivation chain is self-contained and the circularity score is low.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the partially synchronous BFT model, quorum intersection, and the security of the aggregate signature scheme. The protocol has a few hand-set parameters (availability threshold S, sub-block count K, minimum batch age, QC-vote timer) that affect empirical performance but not the correctness proof. The paper invents no new physical entities.

free parameters (4)
  • Availability quorum S
    Protocol parameter in Section 5.1; determines how many votes certify a prefix. It is chosen by hand and must satisfy S >= f+1 for retrievability; the paper does not disclose the value used in evaluation.
  • Number of sub-blocks K = 8
    Section 6.2 and Section 7: K limits prefix granularity and signature verification cost. The value 8 is chosen for evaluation and affects measured latency and throughput.
  • Minimum batch age = 30ms
    Section 6.4 and Section 7: heuristic to let batches disseminate before proposal. Hand-tuned in evaluation; affects Raptr's latency under fault-free conditions.
  • QC-vote timer delay (epsilon * Delta) = epsilon * Delta, exact value unspecified
    Algorithm 1 line 28 and line 130: timer that decides when replicas vote on partial prefixes if full data is missing. It is configurable and influences latency under glitches.
assumptions (4)
  • domain assumption Partially synchronous network: a known Delta and unknown GST exist, and all messages sent after GST are delivered within Delta.
    Section 2.1 system model; used in liveness arguments (Lemma C.8) and protocol timers.
  • domain assumption At most f Byzantine replicas and n = 3f + 1; adversary is computationally bounded.
    Section 2.1; quorum intersection Lemma C.1 relies on it.
  • standard math Hash function is collision resistant and aggregate signatures are unforgeable.
    Appendix A and Section 2.3; used to argue a QC references at most one block and to rule out forged certificates.
  • ad hoc to paper The simplified no-commit proofs scheme used in the implementation preserves the security properties of the full scheme.
    Section 6.2 states a simplified version is used without a security analysis of the simplification. If false, the implementation may not realize the proved protocol.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Raptr: Prefix Consensus for Robust High-Performance BFT." pith.science (2026). https://pith.science/paper/EH6QUWM7

@misc{pith2026250418649,
  author       = {Pith},
  title        = {Pith review of: Raptr: Prefix Consensus for Robust High-Performance BFT},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EH6QUWM7}},
  note         = {Machine review of arXiv:2504.18649}
}
read the original abstract

In this paper, we present Raptr--a Byzantine fault-tolerant state machine replication (BFT SMR) protocol that combines strong robustness with high throughput, while attaining near-optimal theoretical latency. Raptr delivers exceptionally low latency and high throughput under favorable conditions, and it degrades gracefully in the presence of Byzantine faults and network attacks. Existing high-throughput BFT SMR protocols typically take either pessimistic or optimistic approaches to data dissemination: the former suffers from suboptimal latency in favorable conditions, while the latter deteriorates sharply under minimal attacks or network instability. Raptr bridges this gap, combining the strengths of both approaches through a novel Prefix Consensus mechanism. We implement Raptr and evaluate it against several state-of-the-art protocols in a geo-distributed environment with 100 replicas. Raptr achieves 260,000 transactions per second (TPS) with sub-second latency under favorable conditions, sustaining 610ms at 10,000 TPS and 755ms at 250,000 TPS. It remains robust under network glitches, showing minimal performance degradation even with a 1% message drop rate.

Figures

Figures reproduced from arXiv: 2504.18649 by the authors.

Figure 1
Figure 1. Illustration of the non-binary voting on prefixes in Raptr, as described in Section 5.1 and 5.2. Four replicas (𝑅1, . . . , 𝑅4) receive different subsets of batches (green) of the same block, and vote on the longest available prefix. A quorum of QC-votes form a quorum certificate (QC), certifying a block’s prefix. In this example, suppose 𝑆 = 2, QC-votes from 𝑅1, 𝑅2, 𝑅3 certify prefix 3, while QC-votes from 𝑅2, 𝑅3, … view at source ↗
Figure 2
Figure 2. Common case performance of Raptr versus other protocols. The points represent the 50th percentile latency and the error bars show the 25th and 75th percentile latencies respectively. Experimental Setup. We deployed a geo-distributed testbed using Google Cloud Platform (GCP) to emu￾late a decentralized network at global scale. Our setup consists of 100 replicas evenly distributed across 10 GCP regions worldwide: 3 in… view at source ↗
Figure 3
Figure 3. Latency breakdown for Raptr and Aptos+ under fault-free conditions. to Raptr but begins to saturate around 250K TPS. Quorum store-based protocols send batches more frequently and inde￾pendently of round progression, thereby utilizing bandwidth more effectively and achieving higher performance. In contrast, Shoal++ and Mysticeti exhibit sharp latency spikes beyond 130k TPS and 110k TPS, respectively, indicat￾ing earl… view at source ↗
Figures from the paper (3 more)
Figure 2
Figure 2. Figure 2: At low to moderate loads (up to 100K TPS), [PITH_FULL_IMAGE:figures/full_fig_p011_2.png]
Figure 5
Figure 5. Figure 5: Impact of a full network glitch on performance. Note the latency y-axis is in log-scale. Partial network glitch. We simulate a transient network fault by dropping 1% of egress messages at 5% of the replicas, resulting in a total drop rate of 0.05% across the network. S…
Figure 4
Figure 4. Figure 4: Impact of a partial network glitch on performance. Note the latency y-axis is in log-scale. As mentioned in Section 6.4, leader reputation system can rotate out failed replicas, making experiments with per￾manently failed leaders less informative for demonstrating robu…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Prefix Consensus For Censorship Resistant BFT

    cs.DC 2026-02 conditional novelty 8.0 of 10

    Prefix Consensus, a new primitive where parties output consistent low/high prefixes, is solvable asynchronously in exactly three rounds, and yields leaderless BFT consensus with at most f censored slots after GST.

  2. Multimmit: Extending Blocks for Faster Finality

    cs.DC 2026-07 conditional novelty 7.0 of 10

    Multimmit finalises transaction blocks in one voting round with roughly 3δ average latency from dissemination, confining a faulty producer's damage to its own chain.

  3. Cassandra: Consensus with Partial Progress via Robust Partitionable View Synchronization

    cs.DC 2026-07 accept novelty 6.5 of 10

    Cassandra enables safety-preserving partial progress under network partitions via two-tier (PoA/PoR) certification, multi-proposer priority, and a weak-quorum decoupled pacemaker, while matching SOTA throughput when t...

  4. CATs: Secure Blockchain Interoperability with Cross-chain Atomic Transactions

    cs.DC 2026-07 conditional novelty 6.0 of 10

    A shared-coordination protocol for cross-chain atomic transactions that guarantees safety, liveness via timeouts, and minimal blocking of independent transactions through explicit dependency tracking.

  5. Diagnosing High-Performance BFT Consensus via Mixture Modeling of Block Time Distributions

    cs.DC 2026-08 conditional novelty 5.0 of 10

    Block time distributions in HotStuff-based blockchains can be decomposed via quorum-completion time mixture models, with mainnet fits distinguishing homogeneous (Hyperliquid) from heterogeneous (Aptos) validator deployments.

Reference graph

Works this paper leans on

56 extracted references · 47 canonical work pages · cited by 5 Pith papers

  1. [1]

    Good- case latency of byzantine broadcast: A complete categorization

    Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Good- case latency of byzantine broadcast: A complete categorization. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 331–341, 2021

    work page 2021

  2. [2]

    Malicious security comes for free in consensus with leaders

    Mark Abspoel, Thomas Attema, and Matthieu Rambaud. Malicious security comes for free in consensus with leaders. Cryptology ePrint Archive, 2020

    work page 2020

  3. [3]

    Official implementation in rust., 2024

    Aptos. Official implementation in rust., 2024

    work page 2024

  4. [4]

    Shoal++: High throughput dag bft can be fast! arXiv preprint arXiv:2405.20488, 2024

    Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman. Shoal++: High throughput dag bft can be fast! arXiv preprint arXiv:2405.20488, 2024

    arXiv 2024

  5. [5]

    DuoBFT: Resilience vs. Performance Trade-off in Byzantine Fault Tolerance

    Balaji Arun and Binoy Ravindran. Duobft: Resilience vs. efficiency trade-off in byzantine fault tolerance. CoRR, abs/2010.01387, 2020

    work page Pith review arXiv 2010

  6. [6]

    Scalable byzantine fault tolerance via partial decentralization

    Balaji Arun and Binoy Ravindran. Scalable byzantine fault tolerance via partial decentralization. Proc. VLDB Endow., 15(9):1739–1752, may 2022

    work page 2022

  7. [7]

    Mysticeti: Low-latency dag consensus with fast commit path

    Kushal Babel, Andrey Chursin, George Danezis, Lefteris Kokoris- Kogias, and Alberto Sonnino. Mysticeti: Low-latency dag consensus with fast commit path. arXiv preprint arXiv:2310.14821, 2023

    arXiv 2023

  8. [8]

    The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance

    Leemon Baird. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance. Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep, 2016

    work page 2016

Show all 56 references
  1. [9]

    Aggregate and verifiably encrypted signatures from bilinear maps

    Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. InAdvances in Cryptology—EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003 P...

    2003

  2. [10]

    Asynchronous byzantine agreement protocols

    Gabriel Bracha. Asynchronous byzantine agreement protocols. Infor- mation and Computation, 75(2):130–143, 1987

    1987

  3. [11]

    Tendermint: Byzantine fault tolerance in the age of blockchains, 2016

    Ethan Buchman. Tendermint: Byzantine fault tolerance in the age of blockchains, 2016

    2016

  4. [12]

    Casper the friendly finality gadget

    Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437, 2017

    2017 arXiv

  5. [13]

    Practical byzantine fault toler- ance and proactive recovery

    Miguel Castro and Barbara Liskov. Practical byzantine fault toler- ance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398–461, 2002

    2002

  6. [14]

    Be aware of your leaders

    Shir Cohen, Rati Gelashvili, Lefteris Kokoris Kogias, Zekun Li, Dahlia Malkhi, Alberto Sonnino, and Alexander Spiegelman. Be aware of your leaders. In Financial Cryptography and Data Security: 26th International Conference, FC 2022, Grenada, May 2–6, 2022, Revised Selected Pap...

    2022

  7. [15]

    Narwhal and tusk: a dag-based mempool and efficient bft consensus

    George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexan- der Spiegelman. Narwhal and tusk: a dag-based mempool and efficient bft consensus. In Proceedings of the Seventeenth European Conference on Computer Systems, pages 34–50, 2022

    2022

  8. [16]

    Moonshot: Optimizing chain-based rotating leader bft via opti- mistic proposals

    Isaac Doidge, Raghavendra Ramesh, Nibesh Shrestha, and Joshua To- bkin. Moonshot: Optimizing chain-based rotating leader bft via opti- mistic proposals. In International Conference on Dependable Systems and Networks, 2024

    2024

  9. [17]

    Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes

    Adam Gągol, Damian Leśniak, Damian Straszak, and Michał Świętek. Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 214–228, 2019

    2019

  10. [18]

    Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback

    Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. InFinancial Cryptogra- phy and Data Security: 26th International Conference, FC 2022, Grenada...

    2022

  11. [19]

    No-commit proofs: Defeating livelock in bft.Cryptology ePrint Archive, 2021

    Neil Giridharan, Heidi Howard, Ittai Abraham, Natacha Crooks, and Alin Tomescu. No-commit proofs: Defeating livelock in bft.Cryptology ePrint Archive, 2021

    2021

  12. [20]

    Autobahn: Seamless high speed bft

    Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. Autobahn: Seamless high speed bft. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles , pages 1–23, 2024

    2024

  13. [21]

    Fast- hotstuff: A fast and robust bft protocol for blockchains

    Mohammad M Jalalzai, Jianyu Niu, Chen Feng, and Fangyu Gai. Fast- hotstuff: A fast and robust bft protocol for blockchains. IEEE Transac- tions on Dependable and Secure Computing , 21(4):2478–2493, 2023

    2023

  14. [22]

    Hotstuff-1: Linear consensus with one-phase speculation.International Conference on Management of Data (SIGMOD) , 2025

    Dakai Kang, Suyash Gupta, Dahlia Malkhi, and Mohammad Sadoghi. Hotstuff-1: Linear consensus with one-phase speculation.International Conference on Management of Data (SIGMOD) , 2025

    2025

  15. [23]

    All you need is DAG

    Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All you need is DAG. InProceedings of the 40th Symposium on Principles of Distributed Computing , PODC ’21, 2021

    2021

  16. [24]

    Cordial miners: A family of simple, efficient and self-contained consensus protocols for every eventuality

    Idit Keidar, Oded Naor, and Ehud Shapiro. Cordial miners: A family of simple, efficient and self-contained consensus protocols for every eventuality. arXiv preprint arXiv:2205.09174, 2022

    2022 arXiv

  17. [25]

    Revisiting optimal resilience of fast byzantine consensus

    Petr Kuznetsov, Andrei Tonkikh, and Yan X Zhang. Revisiting optimal resilience of fast byzantine consensus. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing , pages 343–353, 2021

    2021

  18. [26]

    Fast and secure global payments with stellar

    Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nico- las Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, and Jed McCaleb. Fast and secure global payments with stellar. In Proceedings of the 27th ACM Symposium on Operating Systems Principles , pages 80–96, 2019

    2019

  19. [27]

    Triangle inequality variations in the internet

    Cristian Lumezanu, Randy Baden, Neil Spring, and Bobby Bhattachar- jee. Triangle inequality variations in the internet. In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement , pages 177–183, 2009

    2009

  20. [28]

    Flexible byzantine fault tol- erance

    Dahlia Malkhi, Kartik Nayak, and Ling Ren. Flexible byzantine fault tol- erance. In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pages 1041–1053, 2019

    2019

  21. [29]

    Bbca- chain: One-message, low latency bft consensus on a dag.arXiv preprint arXiv:2310.06335, 2023

    Dahlia Malkhi, Chrysoula Stathakopoulou, and Maofan Yin. Bbca- chain: One-message, low latency bft consensus on a dag.arXiv preprint arXiv:2310.06335, 2023

    2023 arXiv

  22. [30]

    Multi-threshold byzantine fault toler- ance

    Atsuki Momose and Ling Ren. Multi-threshold byzantine fault toler- ance. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 1686–1699, 2021

    2021

  23. [31]

    Kauri: Scalable bft consensus with pipelined tree-based dissemination and aggregation

    Ray Neiheiser, Miguel Matos, and Luís Rodrigues. Kauri: Scalable bft consensus with pipelined tree-based dissemination and aggregation. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, pages 35–48, 2021

    2021

  24. [32]

    Ebb-and-flow proto- cols: A resolution of the availability-finality dilemma

    Joachim Neu, Ertem Nusret Tas, and David Tse. Ebb-and-flow proto- cols: A resolution of the availability-finality dilemma. In 2021 IEEE Symposium on Security and Privacy (SP) , pages 446–465. IEEE, 2021. 13

    2021

  25. [33]

    Sailfish: Towards improving latency of dag-based bft

    Nibesh Shrestha, Aniket Kate, and Kartik Nayak. Sailfish: Towards improving latency of dag-based bft. Cryptology ePrint Archive, Paper 2024/472, 2024. https://eprint.iacr.org/2024/472

    2024

  26. [34]

    Shoal: Improving dag-bft latency and robustness

    Alexander Spiegelman, Balaji Arun, Rati Gelashvili, and Zekun Li. Shoal: Improving dag-bft latency and robustness. In International Conference on Financial Cryptography and Data Security , pages 92–109. Springer, 2024

    2024

  27. [35]

    Quorum store: How consensus horizontally scales on the aptos blockchain

    Alexander Spiegelman and Brian Cho. Quorum store: How consensus horizontally scales on the aptos blockchain. https://medium.com/aptoslabs/quorum-store-how-consensus- horizontally-scales-on-the-aptos-blockchain-988866f6d5b0 , 2023. Accessed: January 2025

    2023

  28. [36]

    Bullshark: Dag bft protocols made practical

    Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lef- teris Kokoris-Kogias. Bullshark: Dag bft protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 2705–2718, 2022

    2022

  29. [37]

    Bullshark: The partially synchronous version

    Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: The partially synchronous version. arXiv preprint arXiv:2209.05633, 2022

    2022 arXiv

  30. [38]

    Mir-bft: High-throughput BFT for blockchains

    Chrysoula Stathakopoulou, Tudor David, and Marko Vukolic. Mir-bft: High-throughput BFT for blockchains. CoRR, abs/1906.05552, 2019

    1906 arXiv

  31. [39]

    Marlin: Two-phase bft with linearity

    Xiao Sui, Sisi Duan, and Haibin Zhang. Marlin: Two-phase bft with linearity. In 2022 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) , pages 54–66. IEEE, 2022

    2022

  32. [40]

    Sui networks, 2023

    The Sui Team. Sui networks, 2023. Accessed: May 2023

    2023

  33. [41]

    AIP-89 Consensus Latency Reduction using Order Votes

    Satya Vusirikala, Daniel Xiang, and Zekun Li. AIP-89 Consensus Latency Reduction using Order Votes. https://github.com/aptos- foundation/AIPs/blob/main/aips/aip-89.md, 2025. Accessed: January 2025

    2025

  34. [42]

    Strength- ened fault tolerance in byzantine fault tolerant replication

    Zhuolun Xiang, Dahlia Malkhi, Kartik Nayak, and Ling Ren. Strength- ened fault tolerance in byzantine fault tolerant replication. In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pages 205–215. IEEE, 2021

    2021

  35. [43]

    Fides: Scalable censorship-resistant dag consensus via trusted components

    Shaokang Xie, Dakai Kang, Hanzheng Lyu, Jianyu Niu, and Moham- mad Sadoghi. Fides: Scalable censorship-resistant dag consensus via trusted components. arXiv preprint arXiv:2501.01062, 2025

    2025 arXiv

  36. [44]

    In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22) , 2022

    Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse.{DispersedLedger}:{High-Throughput} byzantine con- sensus on variable bandwidth networks. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22) , 2022

    2022

  37. [45]

    advance round

    Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. Hotstuff: BFT consensus with linearity and responsive- ness. In Peter Robinson and Faith Ellen, editors,Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, To...

    2019

  38. [46]

    block(qc2).entryReason = FullQC(qc∗) (line 53): By line 54, qc∗.round = qc2.round− 1≥ qc1.round and qc∗.prefix =𝐾≥ qc1.prefix⇒ rank(qc∗)≥ rank(qc1) (QED)

  39. [47]

    Since cc2.round = qc2.round− 1≥ qc1.round, the only case left to con- sider is when cc2.round = qc1.round

    block(qc2).entryReason = CC(cc2, qc∗) (line 55): If cc2.round > qc1.round, then, by line 55, qc∗.round = cc2.round > qc1.round (QED). Since cc2.round = qc2.round− 1≥ qc1.round, the only case left to con- sider is when cc2.round = qc1.round. In this case, qc∗.round = cc2.round ...

  40. [48]

    By the un- forgeability property of aggregate signatures, for each honest replica in𝑄2, it must be that each honest replica in𝑄2 issues “tc-vote” message (line 164)

    block(qc2, qc∗).entryReason = TC(tc) (line 57): Let𝑄2 be the quorum of replicas that TC-voted for tc (i.e., whose votes are recorded in tc.voteData). By the un- forgeability property of aggregate signatures, for each honest replica in𝑄2, it must be that each honest replica in𝑄...

  41. [49]

    By line 54, qc∗.round = qc2.round − 1 ≥ qc1.round and qc∗.prefix =𝐾≥ qc1.prefix⇒ rank(qc∗)≥ rank(qc1) (QED)

    block(qc2).entryReason = FullQC(qc∗) (line 53): Iden- tical to the case (1) in Lemma C.4. By line 54, qc∗.round = qc2.round − 1 ≥ qc1.round and qc∗.prefix =𝐾≥ qc1.prefix⇒ rank(qc∗)≥ rank(qc1) (QED)

  42. [50]

    Otherwise ( qc2.round > qc1.round+ 1), by line 56, qc∗.round = qc2.round− 1 > qc1.round (QED)

    block(qc2).entryReason = CC(cc, qc∗) (line 55): If qc2.round = qc1.round+ 1, then, by Lemma C.2, qc∗ = block(qc2).qcparent = block( eqc).qcparent = qc1 (QED). Otherwise ( qc2.round > qc1.round+ 1), by line 56, qc∗.round = qc2.round− 1 > qc1.round (QED)

  43. [51]

    Hence, let us consider the case when qc2.round > qc1.round+ 1

    block(qc2).entryReason = TC(tc, qc∗) (line 57): Analo- gously to the previous case, ifqc2.round = qc1.round+ 1, then qc∗ = qc1 (QED). Hence, let us consider the case when qc2.round > qc1.round+ 1. let 𝑄1 be the set of replicas that QC-voted for eqc, and let 𝑄2 the set of repli...

  44. [52]

    Assuming that the Round Timeout timer is set to at least(4+𝜖)Δ (after correcting for any possible clock speed differences), no correct replica will time out (line 162) round𝑟 (or higher) before time𝑡0+( 4+𝜖)Δ

  45. [53]

    Hence, no TC for round𝑟 (or higher) will be formed before time𝑡0+( 4+𝜖)Δ

  46. [54]

    Hence, no valid entry reason for round 𝑟+ 1 can be formed before the time min{𝑡𝑄𝐶,𝑡 0+( 4+𝜖)Δ}

  47. [55]

    No correct replica will QC-vote in round 𝑟 for any block other than the one proposed by𝐿𝑟

  48. [56]

    advance round

    Hence, no QC for any block other than the one pro- posed by𝐿𝑟 will be formed in round𝑟 (line 146), and no correct replica will CC-vote for any other block (line 112). Suppose𝑡𝑄𝐶≤𝑡0+( 3+𝜖)Δ. Then, by the time𝑡𝑄𝐶+ Δ≤ 𝑡0+( 4+𝜖)Δ, every correct replica will have received the CC-vo...

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.