pith. sign in

arxiv: 2503.16783 · v4 · pith:LG33OXRRnew · submitted 2025-03-21 · 💻 cs.CR · cs.DC

CoBRA: A Universal Strategyproof Confirmation Protocol for Quorum-based Proof-of-Stake Blockchains

Zeta Avarikioti , Eleftherios Kokoris Kogias , Ray Neiheiser , Christos Stefo This is my paper

Pith reviewed 2026-05-22 23:34 UTC · model grok-4.3

classification 💻 cs.CR cs.DC
keywords proof-of-stakequorum-based consensusrational faultsByzantine faultsstrategyproof protocolsstate machine replicationblockchain securityfinalization rules
0
0 comments X

The pith

Any quorum-based SMR protocol can tolerate up to one-third Byzantine and one-third rational validators by modifying only its finalization rule under a synchrony bound.

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

The paper first proves that no quorum-based protocol can achieve SMR in partially synchronous networks if rational and Byzantine validators together exceed one-third, or in synchronous networks if they exceed two-thirds. It then presents a way to extend any such protocol by adding a bound on the total transaction volume finalized in any time window of length Δ and using the strongest chain rule for finalization. This allows the protocol to remain safe and live against the combined faults while being strategyproof. The design is shown to be practical through data from Ethereum and Cosmos, and includes a recovery mechanism for after violations.

Core claim

Assuming a synchrony bound Δ, any quorum-based SMR protocol can be extended to tolerate up to 1/3 Byzantine and 1/3 rational validators by modifying only its finalization rule to enforce a bound on finalized transaction volume within Δ and to use the strongest chain rule, which finalizes when a supermajority of honest participants supports execution; a recovery mechanism further guarantees safety and liveness after violations with up to 5/9 Byzantine and 1/9 rational stake.

What carries the argument

The strongest chain rule for finalization together with a volume bound on transactions finalized within any synchrony window Δ.

If this is right

  • The extended protocol achieves SMR security under the hybrid fault model with up to 1/3 Byzantine and 1/3 rational.
  • Efficient finalization occurs when a supermajority of honest participants provably supports execution.
  • The protocol remains strategyproof against profit-driven rational validators.
  • A recovery mechanism restores safety and liveness after consistency violations with up to 5/9 Byzantine and 1/9 rational stake.

Where Pith is reading between the lines

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

  • The participation data from existing chains indicates the 5/6 threshold already holds in practice for immediate application.
  • Distinguishing rational from Byzantine faults may permit higher total fault tolerance in other SMR designs.
  • The volume bound could be tested in high-throughput settings to check for unintended throughput limits.

Load-bearing premise

The network satisfies a known synchrony bound Δ on the maximum message delivery delay.

What would settle it

A demonstration that two conflicting transactions are both finalized within the same Δ window despite the volume bound and strongest chain rule being enforced, under the fault model.

Figures

Figures reproduced from arXiv: 2503.16783 by Christos Stefo, Eleftherios Kokoris Kogias, Ray Neiheiser, Zeta Avarikioti.

Figure 1
Figure 1. Figure 1: Design space of 2𝑓 + 1-committable SMR protocols. Thus, 2𝑓 + 1–commitable quorum-based SMR protocols with a quorum of size 𝑞 = 2𝑓 + 1 are not resilient for any 𝑓 ∗ + 𝑘 ≥ 𝑛/3 under the assumptions of Theorem 3.3. Closing the gaps. Corollary 3.4 establishes that, in partial syn￾chrony, reducing the actual number of Byzantine validators does not improve resilience unless we increase the quorum size. Follow￾in… view at source ↗
Figure 2
Figure 2. Figure 2: Forking attack. A subset F𝑅 of 2𝑓 misbehaving validators (Byzantine and rational) fork the system. The adversary partitions all correct validators into 𝑓 + 1 distinct sets and collects their signatures to create conflicting blocks with valid certificates before Δ ∗ elapses. Each correct validator finalizes blocks with transaction volume up to 𝐶 = 𝐷 within Δ ∗ . Assuming Byzantine validators claim no reward… view at source ↗
read the original abstract

The security of many Proof-of-Stake (PoS) payment systems relies on quorum-based State Machine Replication (SMR) protocols. While classical analyses assume purely Byzantine faults, real-world systems must tolerate both arbitrary failures and strategic, profit-driven validators. We therefore study quorum-based SMR under a hybrid model with honest, Byzantine, and rational participants. We first establish the fundamental limitations of traditional consensus mechanisms, proving two impossibility results: (1) in partially synchronous networks, no quorum-based protocol can achieve SMR when rational and Byzantine validators collectively exceed $1/3$ of the participants; and (2) even under synchronous network assumptions, SMR remains unattainable if this coalition comprises more than $2/3$ of the validator set. Assuming a synchrony bound $\Delta$, we show how to extend any quorum-based SMR protocol to tolerate up to $1/3$ Byzantine and $1/3$ rational validators by modifying only its finalization rule. Our approach enforces a necessary bound on the total transaction volume finalized within any time window $\Delta$ and introduces the \emph{strongest chain rule}, which enables efficient finalization of transactions when a supermajority of honest participants provably supports execution. Empirical analysis of Ethereum and Cosmos demonstrates validator participation exceeding the required $5/6$ threshold in over $99%$ of blocks, supporting the practicality of our design. Finally, we present a recovery mechanism that restores safety and liveness after consistency violations, even with up to $5/9$ Byzantine stake and $1/9$ rational stake, guaranteeing full reimbursement of provable client losses.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims two impossibility results for quorum-based SMR protocols in a hybrid fault model (honest, Byzantine, and rational validators): no such protocol works in partial synchrony if rational+Byzantine >1/3, and none works in synchrony if >2/3. It then presents CoBRA, a construction that extends any quorum-based SMR to tolerate 1/3 Byzantine + 1/3 rational (total 2/3) under a synchrony bound Δ solely by changing the finalization rule, via the strongest chain rule and an enforced bound on total transaction volume finalized in any Δ window. The paper supports practicality via empirical analysis of Ethereum and Cosmos (validator participation >5/6 in >99% of blocks) and adds a recovery mechanism that restores safety/liveness after violations even with up to 5/9 Byzantine + 1/9 rational stake while reimbursing provable losses.

Significance. If the construction is correct and truly requires only a finalization-rule change, the result would be significant: it supplies a universal, minimal-modification path to strategyproofness for the large class of existing quorum-based PoS SMR protocols. The empirical participation data and the recovery mechanism with reimbursement are concrete strengths that increase deployability. The impossibility results also usefully delineate the boundary between classical and hybrid models.

major comments (2)
  1. [CoBRA construction] The central universality claim (§ on the CoBRA construction) rests on the assertion that the transaction-volume bound within Δ and the strongest-chain rule can be realized by altering only the finalization predicate. The skeptic concern is load-bearing: imposing an upper bound on finalized volume in any Δ window necessarily constrains which transactions reach the finalization stage, which in standard quorum-based SMR affects proposal validity, quorum formation, or message acceptance rules upstream of finalization. The manuscript must explicitly show (with pseudocode or a formal argument) that these upstream rules remain unchanged; otherwise the “modify only finalization” guarantee fails.
  2. [Impossibility results] The two impossibility results are stated in the abstract and introduction but the hybrid-model definitions, the precise fault thresholds, and the proof sketches are not visible in the provided text. Because these results are used to motivate the construction, the manuscript must supply the model definitions and at least the key steps of the proofs (or a clear reference to an appendix) so that the 1/3 and 2/3 thresholds can be verified.
minor comments (2)
  1. [Empirical analysis] The empirical section should report the exact number of blocks examined and the precise definition of “participation exceeding 5/6” (e.g., whether it counts unique validators or stake-weighted votes).
  2. [Notation] Notation for the synchrony bound Δ and the volume bound should be introduced once and used consistently; currently the abstract introduces Δ but does not define the volume bound formally.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback and positive assessment of the paper's significance. We address each major comment below and will revise the manuscript to improve clarity and accessibility.

read point-by-point responses

  1. Referee: The central universality claim (§ on the CoBRA construction) rests on the assertion that the transaction-volume bound within Δ and the strongest-chain rule can be realized by altering only the finalization predicate. The skeptic concern is load-bearing: imposing an upper bound on finalized volume in any Δ window necessarily constrains which transactions reach the finalization stage, which in standard quorum-based SMR affects proposal validity, quorum formation, or message acceptance rules upstream of finalization. The manuscript must explicitly show (with pseudocode or a formal argument) that these upstream rules remain unchanged; otherwise the “modify only finalization” guarantee fails.

    Authors: We agree that an explicit demonstration strengthens the universality claim. In the revised manuscript we will add pseudocode for the finalization predicate together with a formal argument showing that the volume bound and strongest-chain rule are enforced exclusively inside the finalization decision. Upstream rules (proposal validity, quorum formation, message acceptance) remain identical to the original quorum-based SMR protocol; the new predicate simply filters which blocks produced by that protocol are declared final. This isolates all modifications to the finalization stage. revision: yes

  2. Referee: The two impossibility results are stated in the abstract and introduction but the hybrid-model definitions, the precise fault thresholds, and the proof sketches are not visible in the provided text. Because these results are used to motivate the construction, the manuscript must supply the model definitions and at least the key steps of the proofs (or a clear reference to an appendix) so that the 1/3 and 2/3 thresholds can be verified.

    Authors: The hybrid fault model is defined in Section 2 and the impossibility results (including thresholds and proof sketches) appear in Section 3, with complete proofs in Appendix A. To improve immediate visibility we will insert a concise model summary and the key proof ideas into the introduction, together with explicit forward references to Section 3 and the appendix. This makes the 1/3 (partial synchrony) and 2/3 (synchrony) thresholds directly verifiable from the main text. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's abstract and described claims establish impossibility results under partial synchrony and synchrony, then present a construction extending quorum-based SMR protocols via a modified finalization rule (strongest chain rule plus transaction volume bound in Δ) under a synchrony assumption. No equations, fitted parameters, or self-referential definitions appear that reduce the claimed results to their inputs by construction. Empirical participation data from Ethereum and Cosmos provides external validation rather than a fitted input renamed as prediction. No self-citation chains or ansatzes smuggled via prior work are referenced in the provided text. The derivation chain remains self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Review performed on abstract only; no explicit free parameters, axioms, or invented entities can be extracted beyond standard network synchrony assumptions stated in the text.

axioms (1)
  • domain assumption Network has a known synchrony bound Δ
    Invoked when describing the extension that assumes Δ to enforce transaction volume bounds.
invented entities (1)
  • strongest chain rule no independent evidence
    purpose: Enables efficient finalization when supermajority of honest participants supports execution
    New rule introduced in the finalization modification; no independent evidence provided in abstract.

pith-pipeline@v0.9.0 · 5850 in / 1228 out tokens · 33402 ms · 2026-05-22T23:34:18.516267+00:00 · methodology

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. Wonderboom -- Efficient, and Censorship-Resilient Signature Aggregation for Million Scale Consensus

    cs.CR 2026-02 unverdicted novelty 6.0

    Wonderboom aggregates signatures from over two million validators in one Ethereum slot with stronger security guarantees against stake-shifting attacks than the existing protocol.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · cited by 1 Pith paper · 4 internal anchors

  1. [1]

    Ittai Abraham, Danny Dolev, Rica Gonen, and Joe Halpern. 2006. Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. InProceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing. 53–62

    work page 2006

  2. [2]

    Ittai Abraham, Danny Dolev, and Joseph Y Halpern. 2008. Lower bounds on im- plementing robust and resilient mediators. InTheory of Cryptography Conference. Springer, 302–319

    work page 2008

  3. [4]

    Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. 2020. Sync hotstuff: Simple and practical synchronous state machine replication. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 106–118

    work page 2020

  4. [5]

    Aiyer, Lorenzo Alvisi, Allen Clement, Mike Dahlin, Jean-Philippe Martin, and Carl Porth

    Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Mike Dahlin, Jean-Philippe Martin, and Carl Porth. 2005. BAR fault tolerance for cooperative services.SIGOPS Oper. Syst. Rev.39, 5 (oct 2005), 45–58. doi:10.1145/1095809.1095816

    work page doi:10.1145/1095809.1095816 2005

  5. [6]

    Yackolley Amoussou-Guenou, Bruno Biais, Maria Potop-Butucaru, and Sara Tucci- Piergiovanni. 2019. Rationals vs byzantines in consensus-based blockchains. arXiv preprint arXiv:1902.07895(2019)

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  6. [7]

    Beaconscan. 2024. Network Participation Rate. https://beaconscan.com/stat/ networkparticipation. Accessed on 09.09.2024

    work page 2024

  7. [8]

    Ethan Buchman, Jae Kwon, and Zarko Milosevic. 2018. The latest gossip on BFT consensus.arXiv preprint arXiv:1807.04938(2018)

    work page arXiv 2018

  8. [10]

    Eric Budish, Andrew Lewis-Pye, and Tim Roughgarden. 2024. The Economic Limits of Permissionless Consensus. arXiv:2405.09173 [cs.DC] https://arxiv.org/ abs/2405.09173

    work page arXiv 2024

  9. [11]

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

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  10. [12]

    Miguel Castro and Barbara Liskov. 2002. Practical byzantine fault tolerance and proactive recovery.ACM Trans. Comput. Syst.20, 4 (nov 2002), 398–461. doi:10.1145/571637.571640

    work page doi:10.1145/571637.571640 2002

  11. [13]

    Pierre Civit, Seth Gilbert, and Vincent Gramoli. 2021. Polygraph: Accountable Byzantine Agreement. In2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS). 403–413. doi:10.1109/ICDCS51616.2021.00046

    work page doi:10.1109/icdcs51616.2021.00046 2021

  12. [14]

    Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, and Jovan Koma- tovic. 2023. As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!J. Parallel and Distrib. Comput.181 (2023), 104743. doi:10.1016/j.jpdc.2023. 104743

    work page doi:10.1016/j.jpdc.2023 2023

  13. [15]

    George Danezis, Jovan Komatovic, Lefteris Kokoris-Kogias, Alberto Sonnino, and Igor Zablotchi. 2025. Byzantine Consensus in the Random Asynchronous Model. arXiv preprint arXiv:2502.09116(2025)

    work page arXiv 2025

  14. [16]

    Xavier Défago, André Schiper, and Péter Urbán. 2004. Total order broadcast and multicast algorithms: Taxonomy and survey.ACM Computing Surveys (CSUR) 36, 4 (2004), 372–421

    work page 2004

  15. [17]

    Raymond Strong

    Danny Dolev and H. Raymond Strong. 1983. Authenticated algorithms for Byzantine agreement.SIAM J. Comput.12, 4 (1983), 656–666

    work page 1983

  16. [18]

    Sisi Duan and Haibin Zhang. 2022. Foundations of dynamic BFT. In2022 IEEE Symposium on Security and Privacy (SP). IEEE, 1317–1334

    work page 2022

  17. [19]

    Garay, Aggelos Kiayias, and Nikos Leonardos

    Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. 2024. The Bitcoin Backbone Protocol: Analysis and Applications.J. ACM(apr 2024). doi:10.1145/3653445 Just Accepted

    work page doi:10.1145/3653445 2024

  18. [20]

    Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. 2022. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. InInternational conference on financial cryptography and data security. Springer, 296–315

    work page 2022

  19. [21]

    Tiantian Gong, Gustavo Franco Camilo, Kartik Nayak, Andrew Lewis-Pye, and Aniket Kate. 2025. Recover from Excessive Faults in Partially-Synchronous BFT SMR.Cryptology ePrint Archive(2025)

    work page 2025

  20. [22]

    Yue Guo, Rafael Pass, and Elaine Shi. 2019. Synchronous, with a chance of partition tolerance. InAnnual International Cryptology Conference. Springer, 499– 529

    work page 2019

  21. [23]

    Dimitris Karakostas, Aggelos Kiayias, and Thomas Zacharias. 2022. Blockchain nash dynamics and the pursuit of compliance. InProceedings of the 4th ACM Conference on Advances in Financial Technologies. 281–293

    work page 2022

  22. [24]

    Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford. 2016. Enhancing bitcoin security and performance with strong consistency via collective signing. In25th usenix security symposium (usenix security 16). 279–296

    work page 2016

  23. [25]

    Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. 2019. Fairledger: A fair blockchain protocol for financial institutions.arXiv preprint arXiv:1906.03819(2019)

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  24. [26]

    Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, and Luca Zanolini. 2025. Accountable Liveness. arXiv:2504.12218 [cs.CR] https://arxiv.org/abs/2504.12218

    work page arXiv 2025

  25. [27]

    Andrew Lewis-Pye and Tim Roughgarden. 2025. Beyond Optimal Fault Tolerance. arXiv preprint arXiv:2501.06044(2025)

    work page arXiv 2025

  26. [28]

    Dahlia Malkhi, Kartik Nayak, and Ling Ren. 2019. Flexible byzantine fault toler- ance. InProceedings of the 2019 ACM SIGSAC conference on computer and commu- nications security. 1041–1053

    work page 2019

  27. [29]

    Conor McMenamin, Vanesa Daza, and Matteo Pontecorvi. 2021. Achieving state machine replication without honest players. InProceedings of the 3rd ACM Conference on Advances in Financial Technologies. 1–14

    work page 2021

  28. [30]

    Joachim Neu, Srivatsan Sridhar, Lei Yang, and David Tse. 2024. Optimal flexible consensus and its application to Ethereum. In2024 IEEE Symposium on Security and Privacy (SP). IEEE, 3885–3903

    work page 2024

  29. [31]

    Ethereum Org. 2024. Staking withdrawals. https://ethereum.org/en/staking/ withdrawals/. Accessed on 02.02.2025

    work page 2024

  30. [32]

    Alejandro Ranchal-Pedrosa and Vincent Gramoli. 2022. TRAP: The Bait of Rational Players to Solve Byzantine Consensus. InProceedings of the 2022 ACM on Asia Conference on Computer and Communications Security(Nagasaki, Japan) (ASIA CCS ’22). Association for Computing Machinery, New York, NY, USA, 168–181. doi:10.1145/3488932.3517386

    work page doi:10.1145/3488932.3517386 2022

  31. [33]

    Alejandro Ranchal-Pedrosa and Vincent Gramoli. 2024. ZLB: A Blockchain to Tolerate Colluding Majorities. In2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 209–222. doi:10.1109/ DSN58291.2024.00032

    work page arXiv 2024

  32. [34]

    Alex Shamis, Peter Pietzuch, Burcu Canakci, Miguel Castro, Cédric Fournet, Edward Ashton, Amaury Chamayou, Sylvan Clebsch, Antoine Delignat-Lavaud, Matthew Kerner, et al. 2022. {IA-CCF}: Individual accountability for permis- sioned ledgers. In19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). 467–491

    work page 2022

  33. [35]

    Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, and Pramod Viswanath. 2021. BFT protocol forensics. InProceedings of the 2021 ACM SIGSAC conference on computer and communications security. 1722–1743

    work page 2021

  34. [36]

    Srivatsan Sridhar, Ertem Nusret Tas, Joachim Neu, Dionysis Zindros, and David Tse. 2024. Consensus Under Adversary Majority Done Right. Cryptology ePrint Archive, Paper 2024/1799. https://eprint.iacr.org/2024/1799

    work page 2024

  35. [38]

    Srivatsan Sridhar, Dionysis Zindros, and David Tse. 2023. Better safe than sorry: Recovering after adversarial majority.arXiv preprint arXiv:2310.06338(2023)

    work page arXiv 2023

  36. [39]

    Ertem Nusret Tas, David Tse, Fangyu Gai, Sreeram Kannan, Mohammad Ali Maddah-Ali, and Fisher Yu. 2023. Bitcoin-enhanced proof-of-stake security: Possibilities and impossibilities. In2023 IEEE Symposium on Security and Privacy (SP). IEEE, 126–145

    work page 2023

  37. [40]

    Zhuolun Xiang, Dahlia Malkhi, Kartik Nayak, and Ling Ren. 2021. Strengthened fault tolerance in byzantine fault tolerant replication. In2021 IEEE 41st Interna- tional Conference on Distributed Computing Systems (ICDCS). IEEE, 205–215

    work page 2021

  38. [41]

    Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abra- ham. 2018. HotStuff: BFT consensus in the lens of blockchain.arXiv preprint arXiv:1803.05069(2018). A Rational attacks In this section, we illustrate the challenges of extending (𝑛, 𝑓) – resilient SMR protocols towards(𝑛, 𝑘, 𝑓)–resiliency for𝑘≥1. Safety attacks.Conflicting ledge...

    work page internal anchor Pith review Pith/arXiv arXiv 2018