Pith. sign in

REVIEW 4 major objections 4 minor 1 cited by

This paper introduces Prefix Consensus, a relaxation of Byzantine consensus in which parties output a low and a high vector, and proves it is solvable deterministically in a fully asynchronous network with optimal resilience, with three com

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 05:13 UTC pith:DIHBNKXL

load-bearing objection Solid core result on Prefix Consensus with a tight 3-round bound, but the f-censorship theorem for the multi-slot protocol has a genuine gap around honest suspensions and timeouts. the 4 major comments →

arxiv 2602.02892 v2 pith:DIHBNKXL submitted 2026-02-02 cs.DC

Prefix Consensus For Censorship Resistant BFT

Zhuolun Xiang , Andrei Tonkikh , Alexander Spiegelman This is my paper
classification cs.DC
keywords Prefix ConsensusCensorship ResistanceByzantine Fault ToleranceAsynchronous ConsensusLeaderless ConsensusGraded ConsensusRound ComplexityPartial Synchrony
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper introduces a new consensus primitive, Prefix Consensus, in which parties submit vectors and output two related vectors (v_low, v_high) rather than one agreed value. The primitive relaxes agreement just enough that it becomes solvable deterministically in a fully asynchronous network with optimal resilience n=3f+1, and the paper proves that three communication rounds are necessary and sufficient. Building on this, it defines Strong Prefix Consensus, which adds agreement on the high output, and uses it to build a leaderless multi-proposer BFT state machine replication protocol. The multi-slot protocol commits in four rounds under a synchronized start and guarantees that after the network becomes synchronous at most f slots can censor honest proposals. It also yields a 3-round graded consensus protocol and leaderless binary and validated consensus with improved worst-case complexity.

Core claim

On its own terms, the paper's central claim is that inclusion—not total agreement—is the hard core of censorship resistance, and once formulated as Prefix Consensus it can be guaranteed even under full asynchrony. In Prefix Consensus each honest party outputs v_low (safe to commit) and v_high (safe to extend), with the upper-bound property that every honest low is a prefix of every honest high, and validity that the maximum common prefix of all honest inputs is a prefix of every low output. The paper proves a tight three-round asynchronous protocol, a matching lower bound for n<=4f, a leaderless partially synchronous Strong Prefix Consensus protocol, and a multi-slot protocol with f-censorsh

What carries the argument

The load-bearing object is the output pair (v_low, v_high) connected by the prefix relation v_low ⪯ v_high for all honest parties; the protocol computes v_low as a maximum common prefix and v_high as a minimum common extension of certified prefixes collected in three rounds of quorum certificates. In the multi-slot construction, the second key mechanism is a deterministic ranking over proposers that is updated by demoting the first party whose proposal was excluded from the committed prefix, so each Byzantine party can censor at most one slot before moving to the end of the order. Strong Prefix Consensus layers on a cyclic shift of this outer ranking and parent-pointer certificates to force

Load-bearing premise

The bound that at most f slots are censored assumes that after GST every honest proposal reaches every honest party within the 2∆ timeout, so the first party excluded from the committed prefix must be Byzantine; if an honest party's proposal can be delayed past that timeout or the party is suspended, the demotion step could penalize an honest proposer and the bound no longer follows.

What would settle it

Run the multi-slot protocol with n=4, f=1 after GST, and slow down every honest proposal of one honest party so it arrives after the 2∆ timeout in a given slot while another honest party's proposal is omitted from the committed prefix. If that slot is counted as uncensored or the honest slow party is demoted rather than the Byzantine one, the 'first excluded party is Byzantine' step of the f-censorship proof is violated.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Prefix Consensus is a new building block: deterministic asynchronous inclusion with optimal resilience, which classic consensus cannot provide.
  • Graded consensus can be solved in three message delays, matching a new lower bound, improving on the previous seven-round protocol.
  • Leaderless binary and validated consensus inherit O(n^3) worst-case message complexity from Strong Prefix Consensus, improving the prior O(n^4) leaderless bound.
  • A BFT SMR built on Strong Prefix Consensus commits slots in four rounds under synchronized start (three in the optimistic failure-free case) and, after GST, at most f slots censor an honest proposal.
  • In long-lived blockchains the bounded f censored slots become a negligible fraction, giving a practical inclusion guarantee without a designated leader.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The paper proves Leaderless Termination and f-Censorship Resistance under separate adversary models; a single composition theorem covering both adversaries simultaneously is not provided.
  • The f-censorship proof relies on the first-excluded-party being Byzantine, which requires every honest post-GST proposal to arrive within the 2∆ timeout; if an honest proposal is delayed beyond that window, the demotion mechanism could in principle penalize an honest party.
  • If slot times can be made small relative to transaction rates, f-censorship resistance implies a weak order-fairness guarantee: after the bounded censor period, any transaction delivered to an honest party is ordered in the next slot.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The paper introduces Prefix Consensus, a consensus-like primitive in which parties input vectors and output two consistent vectors (low, high) that extend the maximum common prefix of honest inputs and satisfy that every honest low is a prefix of every honest high. The main theoretical claim is that, under optimal resilience n = 3f + 1, Prefix Consensus can be solved deterministically in an asynchronous Byzantine setting in exactly three communication rounds, with a matching lower bound for n ≤ 4f (Theorems 1.1, 3.4, 4.1). The paper then defines Strong Prefix Consensus (agreement on the high value), gives a leaderless partially synchronous construction, and lifts it to a multi-slot, multi-proposer BFT SMR protocol claimed to provide four-round commit latency, leaderless termination, and after GST at most f censored slots. It also connects Prefix Consensus to graded consensus, yielding a three-round graded consensus protocol and a matching lower bound, and derives leaderless binary/validated consensus with improved complexity. Proofs for the Strong Prefix Consensus and multi-slot parts are in the appendices.

Significance. If the results hold, the paper makes a valuable conceptual contribution: Prefix Consensus is a clean, asynchronous-solvable relaxation of consensus that directly targets inclusion and censorship, and the tight three-round bound is a solid theoretical result. The connection to graded consensus is also significant, improving the known optimal latency from seven to three message delays and transferring the lower bound. The multi-slot protocol with bounded post-GST censorship and leaderless progress is practically motivated and could be important for blockchain deployment. The paper is generally careful, contains detailed proofs and several optimized variants, and is transparent about which parts are in the appendices. However, the multi-slot censorship-resistance proof currently relies on unsupported assumptions about slot-entry synchronization and about the adversary model, so the advertised 'at most f slots can be censored' guarantee is not yet fully established.

major comments (4)
  1. [Appendix B, Theorem B.2] The proof's central step states that because a slot starts after GST, every honest proposal is received by every honest party within the 2Δ timeout. This is not established. In Algorithm 4, NewSlot(s+1) is triggered independently by each party upon obtaining the previous slot's high output (lines 22–24); no lemma bounds the skew between honest parties' start times for the same slot. Under the Leaderless Termination adversary of Definition 2.1, an honest party can be suspended for a round, so its proposal may be absent from other honest parties' buffers and filled with H(⊥) after the timeout (lines 8–15). Then an honest party can become the first excluded party p_{l+1}; the claim 'p_{l+1} must be Byzantine' fails, and the counting argument 'each censored slot consumes one Byzantine party' no longer yields the at-most-f bound. The authors need either a slot-entry skew lemma or an explicit
  2. [Appendix B, Theorem B.2] The assertion 'if p_{l+1} were honest, then all honest inputs agree on entries 1..l+1' is not a consequence of the protocol as written. A Byzantine party at an earlier rank can equivocate or withhold its proposal, causing honest input vectors to disagree at that earlier position. Thus agreement on entries 1..l+1 does not follow from p_{l+1} being honest. The proof needs a lemma showing that the first position at which honest input vectors differ is necessarily the position of a Byzantine party, or an alternative argument based on the quorum-certificate structure. Without this, the contradiction at the heart of the proof is not established.
  3. [Definitions 2.7–2.8 and Section 7.2.1] The notion 'a slot that starts after GST' is ambiguous in a sequential protocol without a global slot start. Does it mean every honest party's NewSlot(s) occurs after GST? If so, slots that begin for some honest parties before GST and for others after GST are not covered. The abstract's unqualified claim 'after GST at most f slots can be censored' is stronger than what the current proof establishes. The formal statements should specify the intended interpretation and the theorems should be restricted accordingly.
  4. [Section 7 and Appendix B] The protocol is advertised as simultaneously leaderless and censorship-resistant. However, Theorem B.2 proves f-censorship under up to f Byzantine parties with no suspensions, while Theorem B.3 proves Leaderless Termination under an adversary that suspends one party per round with up to f−1 Byzantine parties. No theorem proves both properties under a common adversary. If the two guarantees are meant to hold simultaneously, that composition must be stated and proved; if they are meant to hold under separate adversary models, the text should be reworded to avoid implying a combined guarantee.
minor comments (4)
  1. [Appendix C, Claim 4] The equivalence argument refers to 'Theorem D.10' for the basic Prefix Consensus properties; the basic protocol's theorem is Theorem 3.4. This looks like a cross-reference typo.
  2. [Theorem D.11] The proof derives communication complexity O((cL+κ_s)n^5), but the theorem states O((cL+κ_s)n^4). The warm-up optimistic protocol's complexity should be reconciled.
  3. [Algorithm 4, line 17] The update rule uses v_high_{i,s-1}, but the protocol only invokes RunSPC after NewSlot, which is after a high output for the previous slot is obtained. This should be stated explicitly to avoid confusion.
  4. [Section 4] The lower bound proof is presented for deterministic algorithms; the authors note the usual coin-fixing argument for randomized protocols. That is sufficient, but the definition of 'latency 2δ' should be made explicit in the theorem statement.

Circularity Check

0 steps flagged

No significant circularity: all central bounds are derived in-text from quorum intersection and standard indistinguishability arguments; the sole self-citation is acknowledged inspiration and is not load-bearing.

full rationale

The derivation chain is self-contained. Algorithm 1 defines outputs as quorum-certificate-derived prefixes and all supporting lemmas (3.1, 3.2, 3.3, 4.3, 4.4, 4.5) are proved in the paper from quorum intersection and the formal properties of Definition 2.2; no output quantity is defined in terms of a target result, and no fitted parameter is relabeled as a prediction. The round lower bound (Theorem 4.1) is an indistinguishability argument built in-text, not imported from prior work. Strong Prefix Consensus is a black-box composition of Verifiable Prefix Consensus, and Multi-slot Consensus is a black-box composition of Strong Prefix Consensus, so the higher-level claims reduce to the proved base protocol rather than to their own assumptions. The only self-citation, to Raptr [64], explicitly states that Raptr 'inspiring our Prefix Consensus definition' but 'does not formalize it or explore its applications,' so it is not load-bearing for any theorem. The appendix proof of f-Censorship Resistance (Theorem B.2) contains a potential liveness gap: it asserts that after GST every honest proposal is received within the 2Δ timeout, which may fail if honest parties enter slots asynchronously; however, a proof gap is a correctness concern, not a circular reduction of the claimed guarantee to an input assumption. No equation in the paper is shown to equal a previous result by construction, and no uniqueness theorem from the authors is invoked to force a choice.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No post-hoc entities or fitted constants. The new 'Prefix Consensus' abstraction is the paper's contribution and is supported by proofs, not by an unexplained falsifiable handle. The axioms listed are the standard model, cryptographic, and availability assumptions the constructions rely on.

axioms (5)
  • domain assumption Standard BFT model: n >= 3f+1, at most f Byzantine parties, reliable authenticated channels; asynchronous or partially synchronous communication with GST and known bound ∆.
    Section 2.1 states this model; all protocols and bounds are formulated inside it.
  • domain assumption Digital signatures are existentially unforgeable and used with domain separation; the hash function H is collision-resistant.
    Signatures and hashes are used in all protocols (Sections 2.1, 6.1.2) to certify votes and proposals; the security proofs assume they cannot be forged.
  • domain assumption Availability (Definition A.1): every output element of (Verifiable) Prefix Consensus is supported by some honest input.
    Required by Strong Prefix Consensus and Multi-slot Consensus to fetch preimages of committed hashes; proven for Algorithm 1 but assumed for the abstraction and the optimized variants.
  • domain assumption Leaderless Termination definition of Antoniadis et al. [6] is adopted as the liveness criterion.
    Definition 2.1; the paper builds on prior work rather than redefining the property.
  • standard math Maximum common prefix and minimum common extension are well-defined on finite sets of pairwise consistent vectors.
    Used in QC1Certify/QC2Certify/QC3Certify (Algorithm 1) and Lemma 3.1 to justify mce termination.

pith-pipeline@v1.3.0-alltime-deepseek · 49714 in / 31160 out tokens · 319824 ms · 2026-08-03T05:13:38.749878+00:00 · methodology

0 comments
read the original abstract

Despite broad adoption of BFT consensus in blockchains, censorship resistance remains weak: existing designs offer limited inclusion guarantees and allow leaders to exclude transactions. We address this with a new abstraction and protocol stack. We define \emph{Prefix Consensus}, where parties input vectors and output two consistent vectors $(v^{\sf low},v^{\sf high})$ that extend the maximum common prefix of honest inputs and satisfy $v_i^{\sf low}\preceq v_j^{\sf high}$ for all honest parties $i,j$. We show that Prefix Consensus is solvable asynchronously and establish tight round-complexity bounds. We then define \emph{Strong Prefix Consensus}, which additionally requires agreement on the high output, and give a leaderless partially synchronous protocol. Using its accountable variant, we build a leaderless, multi-proposer, censorship-resistant BFT SMR protocol with amortized four-round commit latency under synchronized starts, while guaranteeing that after GST at most $f$ slots can be censored. Finally, we connect Prefix Consensus to graded consensus, obtaining a matching lower bound and a 3-round protocol, and derive leaderless Binary Consensus with improved worst-case complexity.

Figures

Figures reproduced from arXiv: 2602.02892 by Alexander Spiegelman, Andrei Tonkikh, Zhuolun Xiang.

Figure 1
Figure 1. Figure 1: Executions 𝜌0, 𝜌1, and 𝜌 ∗ used in the lower-bound proof. For clarity, messages to Byzantine parties and messages sent at or after 2 ˆ𝛿 are omitted from the picture. A(𝑣1) B(𝑣0) C(𝑣1) D(𝑣0) time ˆ𝛿 2 ˆ𝛿 same as 𝜌 ′′ 1 diff. from 𝜌 ′′ 1 𝑣 high 𝐶 = 𝑣1 (a) Execution 𝜌1: 𝐴(𝑣1),𝐶(𝑣1), 𝐷(𝑣0) are honest; 𝐵 is Byzantine and only sends messages to 𝐷; messages𝐶 → 𝐷 are slowed down. 𝑣 high 𝐶 (𝜌1) = 𝑣1 because 𝜌1 𝐶 ∼ … view at source ↗
Figure 2
Figure 2. Figure 2: Executions 𝜌1, 𝜌 ′ 1 , and 𝜌 ′′ 1 from the proof of Lemma 4.5. For clarity, messages to Byzantine parties and messages sent at or after 2 ˆ𝛿 are omitted from the picture. parties start at the same time, and all messages take exactly ˆ𝛿 time to be delivered, with ties in the delivery order broken deterministically (e.g., messages from 𝐴 first, then 𝐵, 𝐶, and 𝐷). Moreover, groups 𝐴 and 𝐶 will always have inp… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. AMP: Arc Multi-Proposer Protocol with Bounded Inclusion Guarantees

    cs.DC 2026-05 unverdicted novelty 4.0

    AMP is a multi-proposer extension to Tendermint that separates dissemination from agreement and provides bounded inclusion guarantees plus deterministic ordering over payloads from multiple sources.

Reference graph

Works this paper leans on

74 extracted references · 7 linked inside Pith · cited by 1 Pith paper

  1. [1]

    In: 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

    Abraham, I., Ben-David, N., Stern, G., Yandamuri, S.: On the round complex- ity of asynchronous crusader agreement. In: 27th International Conference on Principles of Distributed Systems (OPODIS 2023). pp. 29–1. Schloss Dagstuhl– Leibniz-Zentrum für Informatik (2024)

    2023

  2. [2]

    In: Pro- ceedings of the 2022 ACM Symposium on Principles of Distributed Comput- ing (PODC ’22)

    Abraham, I., Ben-David, N., Yandamuri, S.: Efficient and adaptively secure asynchronous binary agreement via binding crusader agreement. In: Pro- ceedings of the 2022 ACM Symposium on Principles of Distributed Comput- ing (PODC ’22). pp. 381–391. Association for Computing Machinery (2022). https://doi.org/10.1145/3519270.3538426

    arXiv 2022

  3. [3]

    Cryptol- ogy ePrint Archive (2025)

    Abraham, I., Efron, Y., Ren, L.: The latency cost of censorship resistance. Cryptol- ogy ePrint Archive (2025)

    2025

  4. [4]

    In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

    Abraham, I., Malkhi, D., Spiegelman, A.: Asymptotically optimal validated asyn- chronous byzantine agreement. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. pp. 337–346 (2019)

    2019

  5. [5]

    Cryptology ePrint Archive (2020)

    Abspoel, M., Attema, T., Rambaud, M.: Malicious security comes for free in consensus with leaders. Cryptology ePrint Archive (2020)

    2020

  6. [6]

    In: 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS)

    Antoniadis, K., Desjardins, A., Gramoli, V., Guerraoui, R., Zablotchi, I.: Leaderless consensus. In: 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS). pp. 392–402. IEEE Computer Society (2021)

    2021

  7. [7]

    (2024), https://github.com/aptos-labs/ aptos-core

    Aptos: Official implementation in rust. (2024), https://github.com/aptos-labs/ aptos-core

    2024

  8. [8]

    In: 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

    Arteaga Vázquez, A.E.: On time-optimal, fault-tolerant algorithms for connected consensus beyond grade two. In: 29th International Conference on Principles of Distributed Systems (OPODIS 2025). pp. 24–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2026)

    2025

  9. [9]

    Arun, B., Li, Z., Suri-Payer, F., Das, S., Spiegelman, A.: Shoal++: High throughput dag bft can be fast! arXiv preprint arXiv:2405.20488 (2024)

    Pith/arXiv arXiv 2024

  10. [10]

    In: 27th International Conference on Principles of Distributed Systems (2024)

    Attiya, H., Welch, J.L.: Multi-valued connected consensus: A new perspective on crusader agreement and adopt-commit. In: 27th International Conference on Principles of Distributed Systems (2024)

    2024

  11. [11]

    arXiv preprint arXiv:2310.14821 (2023)

    Babel, K., Chursin, A., Danezis, G., Kokoris-Kogias, L., Sonnino, A.: Mysticeti: Low- latency dag consensus with fast commit path. arXiv preprint arXiv:2310.14821 (2023)

    arXiv 2023

  12. [12]

    Baird, L.: The swirlds hashgraph consensus algorithm: Fair, fast, byzan- tine fault tolerance. Tech. Rep. TR-2016-01, Swirlds Tech Report (2016), https://www.swirlds.com/wp-content/uploads/2016/06/2016-05-31-Swirlds- Consensus-Algorithm-TR-2016-01.pdf

    2016

  13. [13]

    In: DSN (2014)

    Bessani, A., Sousa, J., Alchieri, E.E.P.: BFT-SMaRt: High-performance byzantine fault tolerant state machine replication. In: DSN (2014)

    2014

  14. [14]

    (2025), https://www.bitget.com/news/detail/12560605124672

    BlockchainReporter: Aptos hits sub-50ms block times as new blockchain speed standard. (2025), https://www.bitget.com/news/detail/12560605124672

    arXiv 2025

  15. [15]

    In: Theory of Cryptography Conference

    Blum, E., Katz, J., Liu-Zhang, C.D., Loss, J.: Asynchronous byzantine agreement with subquadratic communication. In: Theory of Cryptography Conference. pp. 353–380. Springer (2020)

    2020

  16. [16]

    In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

    Bouzid, Z., Mostfaoui, A., Raynal, M.: Minimal synchrony for byzantine consen- sus. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. pp. 461–470 (2015)

    2015

  17. [17]

    In: Annual International Cryptology Conference

    Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: Annual International Cryptology Conference. pp. 524–

  18. [18]

    In: Inter- national Conference on Financial Cryptography and Data Security

    Cachin, C., Mićić, J., Steinhauer, N., Zanolini, L.: Quick order fairness. In: Inter- national Conference on Financial Cryptography and Data Security. pp. 316–333. Springer (2022)

    2022

  19. [19]

    In: DISC (2017)

    Cachin, C., Vukolić, M.: Blockchain consensus protocols in the wild. In: DISC (2017)

    2017

  20. [20]

    In: OSDI

    Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: OSDI. pp. 173–186 (1999)

    1999

  21. [21]

    ACM Transactions on Computer Systems (TOCS)20(4), 398–461 (2002)

    Castro, M., Liskov, B.: Practical byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS)20(4), 398–461 (2002)

    2002

  22. [22]

    In: International Conference on Financial Cryptography and Data Security

    Cohen, S., Gelashvili, R., Kogias, L.K., Li, Z., Malkhi, D., Sonnino, A., Spiegel- man, A.: Be aware of your leaders. In: International Conference on Financial Cryptography and Data Security. pp. 279–295. Springer (2022)

    2022

  23. [23]

    In: International Conference on Financial Cryptography and Data Security

    Cohen, S., Goren, G., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A.: Proof of availability and retrieval in a modular blockchain architecture. In: International Conference on Financial Cryptography and Data Security. pp. 36–53. Springer (2023)

    2023

  24. [24]

    In: 2018 IEEE 17th International Symposium on Network Computing and Applications (NCA)

    Crain, T., Gramoli, V., Larrea, M., Raynal, M.: Dbft: Efficient leaderless byzantine consensus and its application to blockchains. In: 2018 IEEE 17th International Symposium on Network Computing and Applications (NCA). pp. 1–8. IEEE (2018)

    2018

  25. [25]

    In: Proceedings of the Seven- teenth European Conference on Computer Systems

    Danezis, G., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A.: Narwhal and tusk: a dag-based mempool and efficient bft consensus. In: Proceedings of the Seven- teenth European Conference on Computer Systems. pp. 34–50 (2022)

    2022

  26. [26]

    In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC)

    Danielsson, A., Gaéba, P., Malewicz, G., Mularczyk, M.: Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). pp. 345–354 (2018). https://doi.org/10.1145/3212734.3212763

    arXiv 2018

  27. [27]

    In: Theory of Cryptography Conference

    Deligios, G., Hirt, M., Liu-Zhang, C.D.: Round-efficient byzantine agreement and multi-party computation with asynchronous fallback. In: Theory of Cryptography Conference. pp. 623–653. Springer (2021)

    2021

  28. [28]

    arXiv preprint arXiv:2401.01791 (2024)

    Doidge, I., Ramesh, R., Shrestha, N., Tobkin, J.: Moonshot: Optimizing chain-based rotating leader bft via optimistic proposals. arXiv preprint arXiv:2401.01791 (2024)

    Pith/arXiv arXiv 2024

  29. [29]

    Journal of Algorithms3(1), 14–30 (1982)

    Dolev, D.: The byzantine generals strike again. Journal of Algorithms3(1), 14–30 (1982)

    1982

  30. [30]

    Journal of the ACM (JACM)32(1), 191–204 (1985)

    Dolev, D., Reischuk, R.: Bounds on information exchange for byzantine agreement. Journal of the ACM (JACM)32(1), 191–204 (1985)

    1985

  31. [31]

    Journal of the ACM35(2), 288–323 (1988)

    Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. Journal of the ACM35(2), 288–323 (1988)

    1988

  32. [32]

    Cryptology ePrint Archive (2025)

    Fernando, R., Policharla, G.V., Tonkikh, A., Xiang, Z.: Trx: Encrypted mempools in high performance bft protocols. Cryptology ePrint Archive (2025)

    2025

  33. [33]

    Journal of the ACM (JACM)32(2), 374–382 (1985)

    Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM)32(2), 374–382 (1985)

    1985

  34. [34]

    arXiv preprint arXiv:2509.23984 (2025)

    Garimidi, P., Neu, J., Resnick, M.: Multiple concurrent proposers: Why and how. arXiv preprint arXiv:2509.23984 (2025)

    arXiv 2025

  35. [35]

    In: International conference on financial cryptography and data security

    Gelashvili, R., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A., Xiang, Z.: Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. In: International conference on financial cryptography and data security. pp. 296–315. Springer (2022)

    2022

  36. [36]

    In: Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles

    Giridharan, N., Suri-Payer, F., Abraham, I., Alvisi, L., Crooks, N.: Autobahn: Seamless high speed bft. In: Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles. pp. 1–23 (2024)

    2024

  37. [37]

    In: 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)

    Gueta, G.G., Abraham, I., Grossman, S., Malkhi, D., Pinkas, B., Reiter, M., Seredin- schi, D.A., Tamir, O., Tomescu, A.: Sbft: a scalable and decentralized trust infras- tructure. In: 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). pp. 568–580. IEEE (2019)

    2019

  38. [38]

    In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

    Guo, B., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Dumbo: Faster asynchronous bft protocols. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. pp. 803–818 (2020)

    2020

  39. [39]

    In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

    Keidar, I., Kokoris-Kogias, E., Naor, O., Spiegelman, A.: All you need is dag. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. pp. 165–175 (2021)

    2021

  40. [40]

    In: Proceedings of the 2021 ACM Sympo- sium on Principles of Distributed Computing (PODC)

    Keidar, I., Kokoris-Kogias, E., Naor, O., Spiegelman, A.: Dag-rider: Fast byzantine consensus with a dag. In: Proceedings of the 2021 ACM Sympo- sium on Principles of Distributed Computing (PODC). pp. 471–480 (2021). https://doi.org/10.1145/3465084.3467928

    arXiv 2021

  41. [41]

    In: 37th International Symposium on Distributed Computing (DISC)

    Keidar, I., Naor, O., Poupko, O., Shapiro, E.: Cordial miners: Fast and efficient consensus for every eventuality. In: 37th International Symposium on Distributed Computing (DISC). Leibniz International Proceedings in Informatics (LIPIcs), vol. 281, pp. 26:1–26:22 (2023). https://doi.org/10.4230/LIPIcs.DISC.2023.26

    doi:10.4230/lipics.disc.2023.26 2023

  42. [42]

    In: Proceedings of the 2023 acm sigsac conference on computer and communications security

    Kelkar, M., Deb, S., Long, S., Juels, A., Kannan, S.: Themis: Fast, strong order- fairness in byzantine consensus. In: Proceedings of the 2023 acm sigsac conference on computer and communications security. pp. 475–489 (2023)

    2023

  43. [43]

    In: Annual International Cryptology Conference

    Kelkar, M., Zhang, F., Goldfeder, S., Juels, A.: Order-fairness for byzantine con- sensus. In: Annual International Cryptology Conference. pp. 451–480. Springer (2020)

    2020

  44. [44]

    In: SOSP (2007)

    Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.: Zyzzyva: Speculative byzantine fault tolerance. In: SOSP (2007)

    2007

  45. [45]

    In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

    Kuznetsov, P., Tonkikh, A., Zhang, Y.X.: Revisiting optimal resilience of fast byzantine consensus. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. pp. 343–353 (2021)

    2021

  46. [46]

    ACM Trans- actions on Programming Languages and Systems4(3), 382–401 (1982)

    Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans- actions on Programming Languages and Systems4(3), 382–401 (1982)

    1982

  47. [47]

    In: Proceedings of the 39th Sym- posium on Principles of Distributed Computing

    Lu, Y., Lu, Z., Tang, Q., Wang, G.: Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited. In: Proceedings of the 39th Sym- posium on Principles of Distributed Computing. pp. 129–138 (2020)

    2020

  48. [48]

    arXiv preprint (2024), available at https://arxiv.org/abs/2501.14732

    Lyu, H., Xie, S., Niu, J., Beschastnikh, I., Zhang, Y., Sadoghi, M., Feng, C.: Or- thrus: Accelerating multi-bft consensus through concurrent partial ordering of transactions. arXiv preprint (2024), available at https://arxiv.org/abs/2501.14732

    Pith/arXiv arXiv 2024

  49. [49]

    arXiv preprint (2024), available at https://arxiv.org/abs/2409.10954

    Lyu, H., Xie, S., Niu, J., Feng, C., Zhang, Y., Beschastnikh, I.: Ladon: High- performance multi-bft consensus via dynamic global ordering. arXiv preprint (2024), available at https://arxiv.org/abs/2409.10954

    Pith/arXiv arXiv 2024

  50. [50]

    arXiv preprint (2025), available at https://arxiv.org/abs/2511.05843

    Lyu, H., Xie, S., Niu, J., Sadoghi, M., Zhang, Y., Wang, C., Beschastnikh, I., Feng, C.: Hydra: Breaking the global ordering barrier in multi-bft consensus. arXiv preprint (2025), available at https://arxiv.org/abs/2511.05843

    arXiv 2025

  51. [51]

    In: CCS (2016)

    Miller, A., Xia, Y., Croman, K., Shi, E., Song, D.: The honey badger of bft protocols. In: CCS (2016)

    2016

  52. [52]

    In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

    Momose, A., Ren, L.: Constant latency in sleepy consensus. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. pp. 2295–2308 (2022)

    2022

  53. [53]

    Acm Computing Surveys (CSUR)22(4), 299–319 (1990)

    Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: A tutorial. Acm Computing Surveys (CSUR)22(4), 299–319 (1990)

    1990

  54. [54]

    In: IEEE Symposium on Security and Privacy (SP)

    Shrestha, N., Shrothrium, R., Kate, A., Nayak, K.: Sailfish: Towards improving the latency of dag-based bft. In: IEEE Symposium on Security and Privacy (SP). pp. 1928–1946 (2025). https://doi.org/10.1109/SP61157.2025.00021

    arXiv 1928

  55. [55]

    arXiv15 preprint (2025), available at https://arxiv.org/abs/2505.02761

    Shrestha, N., Yu, Q., Kate, A., Losa, G., Nayak, K., Wang, X.: Sailfish++: Post- quantum secure, signature-free dag-based bft with optimistic low latency. arXiv15 preprint (2025), available at https://arxiv.org/abs/2505.02761

    Pith/arXiv arXiv 2025

  56. [56]

    (2024), https://solana.com/solana-whitepaper.pdf

    Solana: Whitepaper. (2024), https://solana.com/solana-whitepaper.pdf

    2024

  57. [57]

    In: International Conference on Financial Cryptography and Data Security

    Spiegelman, A., Aurn, B., Gelashvili, R., Li, Z.: Shoal: Improving dag-bft latency and robustness. In: International Conference on Financial Cryptography and Data Security. Springer (2023)

    2023

  58. [58]

    https://medium.com/aptoslabs/quorum-store-how-consensus- horizontally-scales-on-the-aptos-blockchain-988866f6d5b0 (2023), accessed: Jan- uary 2025

    Spiegelman, A., Cho, B.: 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: Jan- uary 2025

    2023

  59. [59]

    In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

    Spiegelman, A., Giridharan, N., Sonnino, A., Kokoris-Kogias, L.: Bullshark: Dag bft protocols made practical. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. pp. 2705–2718 (2022)

    2022

  60. [60]

    arXiv preprint arXiv:1906.0555292(2019)

    Stathakopoulou, C., David, T., Vukolic, M.: Mir-bft: High-throughput bft for blockchains. arXiv preprint arXiv:1906.0555292(2019)

    Pith/arXiv arXiv 1906

  61. [61]

    In: Proceedings of the Seventeenth European Conference on Computer Systems

    Stathakopoulou, C., Pavlovic, M., Vukolić, M.: State machine replication scalabil- ity made simple. In: Proceedings of the Seventeenth European Conference on Computer Systems. pp. 17–33 (2022)

    2022

  62. [62]

    In: Proceedings of the 2019 USENIX An- nual Technical Conference (USENIX ATC)

    Stathakopoulou, C.G., Pavlovic, M., Vukolić, M.: Mir-BFT: High-throughput byzantine fault tolerant replication. In: Proceedings of the 2019 USENIX An- nual Technical Conference (USENIX ATC). pp. 677–691 (2019), https://www. usenix.org/conference/atc19/presentation/stathakopoulou

    2019

  63. [63]

    (2024), https://github.com/MystenLabs/sui

    Sui: Official implementation in rust. (2024), https://github.com/MystenLabs/sui

    2024

  64. [64]

    arXiv preprint arXiv:2504.18649 (2025)

    Tonkikh, A., Arun, B., Xiang, Z., Li, Z., Spiegelman, A.: Raptr: Prefix consensus for robust high-performance bft. arXiv preprint arXiv:2504.18649 (2025)

    Pith/arXiv arXiv 2025

  65. [65]

    In: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing

    Yang, J., Neiger, G., Gafni, E.: Structured derivations of consensus algorithms for failure detectors. In: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing. pp. 297–306 (1998) 16 A Analysis of Strong Prefix Consensus Protocol In this section, we analyze the properties of our Strong Prefix Con- sensus protocol (Alg...

    1998

  66. [66]

    first excluded

    high value. The total high latency is3 + 4 = 7rounds, i.e.,7𝛿. Message and communication complexity.Per view, each party broadcasts at most onenew-view, onenew-commit, and oneempty-view message, for a total of𝑂(𝑛2)messages. Message payloads consist of hash vectors, Verifiable Prefix Consensus proofs, and (possibly ag- gregate) signatures. When𝐿 =𝑛, a Veri...

  67. [67]

    Similarly, any𝑄𝐶3,𝑄𝐶′ 3 intersect in at least one honest party’s vote-3 = (𝑧,∗,∗,∗ )

    Since𝑄𝐶1.𝑦 = mcp({𝑣∈𝑄𝐶 1}) ⪯𝑣 and 𝑄𝐶′ 1.𝑦 = mcp({𝑣∈𝑄𝐶 ′ 1}) ⪯𝑣 , we conclude that𝑄𝐶 1.𝑦∼𝑄𝐶 ′ 1.𝑦. Similarly, any𝑄𝐶3,𝑄𝐶′ 3 intersect in at least one honest party’s vote-3 = (𝑧,∗,∗,∗ ). Since 𝑄𝐶3.𝑧p = mcp({𝑧∈𝑄𝐶 3}) ⪯𝑧 and 𝑄𝐶′ 3.𝑧p =mcp({𝑧∈𝑄𝐶 ′ 3})⪯𝑧, we conclude that𝑄𝐶 3.𝑧p∼𝑄𝐶′ 3.𝑧p. □ Lemma D.3.All functions in Algorithm 5 always terminate. Proof. Function...

  68. [68]

    □ Lemma D.4.𝑣 H⪯𝑄𝐶 1.𝑥for any𝑄𝐶 1

    Thereforemce(·)operations inQC2Certify andQC4Certifyare well-defined. □ Lemma D.4.𝑣 H⪯𝑄𝐶 1.𝑥for any𝑄𝐶 1. Proof.Identical to the proof of Lemma 3.3.□ Lemma D.5.𝑣 H∼𝑄𝐶 1.𝑦for any𝑄𝐶 1. Proof. Any𝑄𝐶1 contains at least one honest partyℎ∈H with some input𝑣 in ℎ . By definition,𝑦 := mcp({𝑣∈𝑄𝐶 1})⪯𝑣 in ℎ , and𝑣H := mcp({𝑣 in 𝑖}𝑖∈H )⪯𝑣 in ℎ . Thus we can conclude ...

  69. [69]

    Therefore we conclude that𝑄𝐶1&2.𝑧⪰𝑄𝐶 ′ 2.𝑦p, for any𝑄𝐶1&2 ={𝑄𝐶1,𝑄𝐶 2} and any𝑄𝐶′ 2.□ Lemma D.8.𝑣 H⪯𝑄𝐶 1&2.𝑧, for any𝑄𝐶 1&2 ={𝑄𝐶 1,𝑄𝐶 2}

    By definition (line 12),𝑄𝐶1&2.𝑧⪰𝑄𝐶 2.𝑦e. Therefore we conclude that𝑄𝐶1&2.𝑧⪰𝑄𝐶 ′ 2.𝑦p, for any𝑄𝐶1&2 ={𝑄𝐶1,𝑄𝐶 2} and any𝑄𝐶′ 2.□ Lemma D.8.𝑣 H⪯𝑄𝐶 1&2.𝑧, for any𝑄𝐶 1&2 ={𝑄𝐶 1,𝑄𝐶 2}. Proof.There are three cases to consider: • If𝑄𝐶2.𝑦e⪯𝑄𝐶 1.𝑥, by line 12,𝑄𝐶1&2.𝑧 :=𝑄𝐶1.𝑥. By Lemma D.4, 𝑄𝐶1.𝑥⪰𝑣 H. Thus𝑄𝐶 1&2.𝑧⪰𝑣 H. • If𝑄𝐶1.𝑥⪯𝑄𝐶 2.𝑦e, by line 12,𝑄𝐶1&2.𝑧 :=𝑄𝐶2.𝑦e⪰𝑄...

  70. [70]

    By quorum intersection, at least one honest party’s vote-4 = (𝑧p,∗,∗ )is in both𝑄𝐶4 and𝑄𝐶′

  71. [71]

    Let 𝑄𝐶3.𝑧e denote 𝑧e := mce({𝑧∈𝑄𝐶 3})as in line 39

    Since𝑄𝐶4.𝑧pp := mcp({𝑧p∈𝑄𝐶 4})⪯𝑧 p and 𝑄𝐶′ 4.𝑧pe := mce({𝑧p∈𝑄𝐶 4})⪰𝑧 p, we conclude that 𝑄𝐶4.𝑧pp⪯ 𝑄𝐶′ 4.𝑧pe. Let 𝑄𝐶3.𝑧e denote 𝑧e := mce({𝑧∈𝑄𝐶 3})as in line 39. We then prove 𝑄𝐶4.𝑧pp ⪯𝑄𝐶 3.𝑧e for any 𝑄𝐶4 and 𝑄𝐶3 such that 𝑧∼𝑧 ′ for∀𝑧,𝑧′ ∈𝑄𝐶 3. For any such 𝑄𝐶3 and any 𝑄𝐶′ 3, they intersect in at least one honest party’s vote-3 = (𝑧,∗,∗,∗ ). Since 𝑄𝐶′ 3.𝑧p...

  72. [72]

    By Lemma D.9, we have𝑄𝐶4.𝑧pp⪰ 𝑄𝐶′ 2.𝑦p for any𝑄𝐶′

  73. [73]

    Therefore,𝑣 opt 𝑖 ⪯ 𝑣 low 𝑖 for any𝑖∈H

    By line 30 and 46, for any𝑖∈H ,𝑣 opt 𝑖 =𝑄𝐶2.𝑦p for some𝑄𝐶2, and𝑣 low 𝑖 =𝑄𝐶4.𝑧pp for some𝑄𝐶4. Therefore,𝑣 opt 𝑖 ⪯ 𝑣 low 𝑖 for any𝑖∈H. Optimistic Validity.When|H| =𝑛, for any𝑄𝐶1,𝑄𝐶1.𝑦 := mcp({𝑣∈ 𝑄𝐶1})⪰𝑣 H := mcp({𝑣 in ℎ}ℎ∈H ). This implies that mcp({𝑄𝐶1.𝑦 : ∀𝑄𝐶1})⪰𝑣H. By definition,𝑄𝐶2.𝑦p := mcp({𝑦∈𝑄𝐶 2})⪰mcp ({𝑄𝐶1.𝑦 : ∀𝑄𝐶1}). Therefore𝑄𝐶 2.𝑦p⪰𝑣H for any𝑄𝐶 ...

  74. [74]

    Termination.FunctionsQC1Certifyalways terminates because mcp(·)is well-defined and terminates on any finite set of vectors

    Therefore𝑣 low 𝑖 ⪯𝑣 high 𝑗 for any 𝑖,𝑗∈H. Termination.FunctionsQC1Certifyalways terminates because mcp(·)is well-defined and terminates on any finite set of vectors. FunctionQC2Certifyalso terminates: the operation mce(·)is well- defined since, by Lemma E.1, we have 𝑄𝐶1.𝑥∼𝑄𝐶 ′ 1.𝑥 for any 𝑄𝐶1,𝑄𝐶′ 1, ensuring that a common extension always exists. All hone...