Pith. sign in

REVIEW 55 references

Accountable Liveness

T0 review · 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 Accountable liveness is achievable in x-partially-synchronous networks if and only if x < 1/2 and the adversary controls fewer than n/2 nodes.

arxiv 2504.12218 v2 pith:FD7KJC4H submitted 2025-04-16 cs.CR

Andrew Lewis-Pye , Joachim Neu , Tim Roughgarden , Luca Zanolini This is my paper · ORCID
classification cs.CR
keywords livenessnodesnumberpartially-synchronoussafetytimeaccountabilityaccountable
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

Blockchain and database systems that let many computers agree on an ordered list of transactions must guarantee two things: safety (no two computers ever disagree) and liveness (every transaction eventually gets included). Recent systems add accountability: if safety is broken, the honest computers can produce a mathematical proof that at least a third of the misbehaving computers are guilty, which allows the system to punish them financially. This paper asks whether a similar guarantee is possible for liveness, that is, when the network is so slow that transactions never get confirmed.

The authors introduce a new way to model the network: a network is mostly good if, over every sufficiently long window, at most a fraction x of the time is unresponsive, and after an unknown time it becomes fully reliable. They prove that accountable liveness is achievable exactly when x is less than one half and fewer than half of the computers are adversarial. Their protocol, based on the Tendermint consensus algorithm, adds an extra voting round in which computers say whether all pending transactions were confirmed, and it keeps records so that when a liveness violation happens, a large set of misbehaving computers can be proved guilty. They also prove that no protocol can do this if adversarial computers are a majority or if the network is unresponsive half of the time or more. For the intermediate cases, they give near-matching bounds on how many guilty computers can be identified, and they show their guarantees are tight for a particular parameter value.

Extended reading notes

Core claim

The central characterization: for optimally-resilient atomic broadcast protocols that are safe and live under partial synchrony, non-trivial accountable liveness is achievable in (Delta,g,x)-partial-synchrony with f <= tau_AL_max if and only if x < 1/2 and tau_AL_max < n/2. Theorem 1 shows sufficiency by constructing a Tendermint variant that identifies tau_AL_max - floor(((1+x+delta_x)(tau_AL_max - n/3))/(1 - x - delta_x)) adversary nodes after a liveness violation; Theorems 2 and 3 show necessity, including impossibility under synchrony when tau_AL_max >= n/2.

Load-bearing premise

The (Delta,g,x)-partial-synchrony network model (Sec. 2.1) assumes that for every partition into periods of length Delta' and every interval of g(Delta') periods, at most an x fraction of periods are asynchronous, with all rounds after an unknown GST synchronous. If real networks can have correlated, long-lasting outages that violate this sliding-window bound, then the protocol may produce incorrect certificates of guilt or none at all, and the x < 1/2 frontier would not describe reality. This is a new, unvalidated timing assumption; the paper's plausibility argument (Sec. 2.5) is anecdotal.

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.

Assumptions & free parameters 2 free parameters · 8 assumptions · 0 invented entities

The central claim rests on a new network model, random leader election, and standard cryptographic assumptions. The only ad hoc addition is the unproven now-or-never property for classical PBFT-style protocols, which supports the near-optimality discussion but not the main theorems. No invented physical or mathematical entities are introduced.

free parameters (2)
  • delta_x = arbitrary in (0, 1/2 - x)
    Design parameter governing the probability that a super-view lacks an honest leader and the number of identifiable adversary nodes; appears in Thm 1's tau_AL_ident and the failure probability exp(-delta_x g(Delta')/6).
  • phase delays in Alg. 1 (2D,2D,3D,3D,2D) = multiples of Delta
    Chosen by hand to make Lemmas 3 and 4 hold: the 2D and 3D delays ensure that honest transcript messages bound what other honest nodes could have seen or sent, which the blame accounting relies on.
assumptions (8)
  • domain assumption PKI with ideal digital signatures; adversary cannot forge signatures (Sec. 2, opening paragraph)
    Used throughout for certificate validity and unique transcript attribution.
  • domain assumption Computationally bounded adversary and static corruption before protocol randomness (Sec. 2)
    Static corruption ensures the random leader election argument in Lemma 7; computational bound justifies ideal signatures.
  • domain assumption Synchronized clocks and discrete rounds (Sec. 2)
    Needed for view timing and for defining x-partial-synchrony periods.
  • domain assumption (Delta,g,x)-partial-synchrony network assumption (Sec. 2.1)
    Central model: every window of g(Delta') periods has at most x fraction asynchronous, with GST after which all rounds are synchronous. This is the main external assumption on which the characterization is built.
  • domain assumption Uniform random independent leader election per view (Alg. 1, Sec. 3; Lemma 7)
    Ensures with high probability that most super-views contain at least one honest leader, which is required for the adjudication rule's completeness.
  • domain assumption Optimal resilience n = 2 tau_L + tau_S + 1 for Thm 3 and related (Def. 5)
    The impossibility for x >= 1/2 is shown for optimally-resilient protocols; non-optimal protocols could in principle behave differently, as the paper notes.
  • ad hoc to paper Now-or-never property (Def. 6) holds for classical PBFT-style protocols (Sec. 6.3)
    Asserted without proof; used to state Thm 5 and the near-optimality claim. The general case is only conjectured (Conj. 1), but the specific claim about PBFT, Tendermint, HotStuff, CasperFFG, Streamlet is presented as fact.
  • standard math Chernoff bound (Prop. 1)
    Used in Lemma 7 to bound the number of super-views lacking an honest leader.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Accountable Liveness." pith.science (2026). https://pith.science/paper/FD7KJC4H

@misc{pith2026250412218,
  author       = {Pith},
  title        = {Pith review of: Accountable Liveness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FD7KJC4H}},
  note         = {Machine review of arXiv:2504.12218}
}
abstract

Safety and liveness are the two classical security properties of consensus protocols. Recent works have strengthened safety with accountability: should any safety violation occur, a sizable fraction of adversary nodes can be proven to be protocol violators. This paper studies to what extent analogous accountability guarantees are achievable for liveness. To reveal the full complexity of this question, we introduce an interpolation between the classical synchronous and partially-synchronous models that we call the $x$-partially-synchronous network model in which, intuitively, at most an $x$ fraction of the time steps in any sufficiently long interval are asynchronous (and, as with a partially-synchronous network, all time steps are synchronous following the passage of an unknown "global stablization time"). We prove a precise characterization of the parameter regime in which accountable liveness is achievable: if and only if $x < 1/2$ and $f < n/2$, where $n$ denotes the number of nodes and $f$ the number of nodes controlled by an adversary. We further refine the problem statement and our analysis by parameterizing by the number of violating nodes identified following a liveness violation, and provide evidence that the guarantees achieved by our protocol are near-optimal (as a function of $x$ and $f$). Our results provide rigorous foundations for liveness-accountability heuristics such as the "inactivity leaks" employed in Ethereum.

Figures

Figures reproduced from arXiv: 2504.12218 by the authors.

Figure 1
Figure 1. Illustration of key results: Impossibility of accountable liveness for [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Overview of how certificates of guilt for Alg. 1 are produced, from the perspective of a node [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Illustration of indistinguishable executions [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Illustration of indistinguishable executions used in Thm. 4, for [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 45 canonical work pages

  1. [1]

    Ethereum.org: The complete guide to Ethereum

    2024. Ethereum.org: The complete guide to Ethereum. https://ethereum.org/

    work page 2024

  2. [2]

    pod – how it works

    2025. pod – how it works. https://pod.network/how-it-works

    work page 2025

  3. [3]

    Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. 2020. Sync HotStuff: Simple and Practical Synchronous State Machine Replication. In SP. IEEE, 106–118

    work page 2020

  4. [4]

    Schneider

    Bowen Alpern and Fred B. Schneider. 1985. Defining Liveness.Inf. Process. Lett. 21, 4 (1985), 181–185

    work page 1985

  5. [5]

    Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros. 2025. Pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer. arXiv:2501.14931v3 [cs.DC]

    arXiv 2025

  6. [6]

    Sarah Azouvi and Marko Vukolic. 2022. Pikachu: Securing PoS Blockchains from Long-Range Attacks by Checkpointing into Bitcoin PoW using Taproot. In ConsensusDay@CCS. ACM, 53–65

    work page 2022

  7. [7]

    Erica Blum, Jonathan Katz, and Julian Loss. 2019. Synchronous Consensus with Optimal Asynchronous Fallback Guarantees. InTCC (1) (Lecture Notes in Computer Science, Vol. 11891). Springer, 131–150

    work page 2019

  8. [8]

    Erica Blum, Jonathan Katz, and Julian Loss. 2020. Network-Agnostic State Ma- chine Replication. arXiv:2002.03437v3 [cs.CR]

    work page Pith review arXiv 2020

Show all 55 references
  1. [9]

    Erica Blum, Chen-Da Liu Zhang, and Julian Loss. 2020. Always Have a Backup Plan: Fully Secure Synchronous MPC with Asynchronous Fallback. InCRYPTO (2) (Lecture Notes in Computer Science, Vol. 12171). Springer, 707–731

    2020

  2. [10]

    Ethan Buchman, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, Dragos- Adrian Seredinschi, and Josef Widder. 2022. Revisiting Tendermint: Design Tradeoffs, Accountability, and Practical Use. InDSN (Supplements). IEEE, 11–14

    2022

  3. [11]

    Ethan Buchman, Jae Kwon, and Zarko Milosevic. 2018. The latest gossip on BFT consensus. arXiv:1807.04938v3 [cs.DC]

    2018 arXiv

  4. [12]

    Eric Budish, Andrew Lewis-Pye, and Tim Roughgarden. 2024. The Economic Limits of Permissionless Consensus. InEC. ACM, 704–731

    2024

  5. [13]

    2018.A Guide to 99% Fault Tolerant Consensus

    Vitalik Buterin. 2018.A Guide to 99% Fault Tolerant Consensus. https://vitalik. eth.limo/general/2018/08/07/99_fault_tolerant.html

    2018

  6. [14]

    Vitalik Buterin and Virgil Griffith. 2017. Casper the Friendly Finality Gadget. arXiv:1710.09437v4 [cs.CR]

    2017 arXiv

  7. [15]

    Vitalik Buterin, Diego Hernandez, Thor Kamphefner, Khiem Pham, Zhi Qiao, Danny Ryan, Juhyeok Sin, Ying Wang, and Yan X Zhang. 2020. Combining GHOST and Casper. arXiv:2003.03052v3 [cs.CR] 14 Accountable Liveness

    2020 arXiv

  8. [16]

    Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. 2011.Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer

    2011

  9. [17]

    Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In OSDI. USENIX Association, 173–186

    1999

  10. [18]

    Chan and Elaine Shi

    Benjamin Y. Chan and Elaine Shi. 2020. Streamlet: Textbook Streamlined Blockchains. InAFT. ACM, 1–11

    2020

  11. [19]

    Pierre Civit, Seth Gilbert, and Vincent Gramoli. 2021. Polygraph: Accountable Byzantine Agreement. InICDCS. IEEE, 403–413

    2021

  12. [20]

    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 Distributed Comput.181 (2023), 104743

    2023

  13. [21]

    2022.Casper FFG as a full protocol and its relationship with Streamlet

    Francesco D’Amato. 2022.Casper FFG as a full protocol and its relationship with Streamlet. https://ethresear.ch/t/casper-ffg-as-a-full-protocol-and-its- relationship-with-streamlet/13803

    2022

  14. [22]

    Evangelos Deirmentzoglou, Georgios Papakyriakopoulos, and Constantinos Pat- sakis. 2019. A Survey on Long-Range Attacks for Proof of Stake Protocols.IEEE Access7 (2019), 28712–28725

    2019

  15. [23]

    Raymond Strong

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

    1983

  16. [24]

    Lynch, and Larry J

    Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. 1988. Consensus in the presence of partial synchrony.J. ACM35, 2 (1988), 288–323

    1988

  17. [25]

    Fischer, Nancy A

    Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process.J. ACM32, 2 (1985), 374–382

    1985

  18. [26]

    Neil Giridharan, Ittai Abraham, Natacha Crooks, Kartik Nayak, and Ling Ren

  19. [27]

    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, Paper 2025/083. https://eprint.iacr.org/2025/083

    2025

  20. [28]

    Yue Guo, Rafael Pass, and Elaine Shi. 2019. Synchronous, with a Chance of Partition Tolerance. InCRYPTO (1) (Lecture Notes in Computer Science, Vol. 11692). Springer, 499–529

    2019

  21. [29]

    Andreas Haeberlen, Petr Kouznetsov, and Peter Druschel. 2007. PeerReview: practical accountability for distributed systems. InSOSP. ACM, 175–188

    2007

  22. [30]

    Andreas Haeberlen and Petr Kuznetsov. 2009. The Fault Detection Problem. In OPODIS (Lecture Notes in Computer Science, Vol. 5923). Springer, 99–114

    2009

  23. [31]

    Ruomu Hou and Haifeng Yu. 2023. Optimistic Fast Confirmation While Tolerating Malicious Majority in Blockchains. InSP. IEEE, 2481–2498

    2023

  24. [32]

    Ruomu Hou, Haifeng Yu, and Prateek Saxena. 2022. Using Throughput-Centric Byzantine Broadcast to Tolerate Malicious Majority in Blockchains. InSP. IEEE, 1263–1280

    2022

  25. [33]

    Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. 2017. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. InCRYPTO (1) (Lecture Notes in Computer Science, Vol. 10401). Springer, 357–388

    2017

  26. [34]

    Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, and Luca Zanolini. 2025. Accountable Liveness. Cryptology ePrint Archive, Paper 2025/693. https://eprint. iacr.org/2025/693

    2025

  27. [35]

    Andrew Lewis-Pye and Tim Roughgarden. 2023. Permissionless Consensus. arXiv:2304.14701v5 [cs.DC]

    2023 arXiv

  28. [36]

    Andrew Lewis-Pye and Tim Roughgarden. 2025. Beyond Optimal Fault Tolerance. arXiv:2501.06044v7 [cs.DC]

    2025 arXiv

  29. [37]

    Atsuki Momose and Ling Ren. 2021. Multi-Threshold Byzantine Fault Tolerance. InCCS. ACM, 1686–1699

    2021

  30. [38]

    Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. https: //bitcoin.org/bitcoin.pdf

    2008

  31. [39]

    Joachim Neu, Ertem Nusret Tas, and David Tse. 2020. Snap-and-Chat Protocols: System Aspects. arXiv:2010.10447v1 [cs.CR]

    2020 arXiv

  32. [40]

    Joachim Neu, Ertem Nusret Tas, and David Tse. 2022. The Availability- Accountability Dilemma and Its Resolution via Accountability Gadgets. InFi- nancial Cryptography (Lecture Notes in Computer Science, Vol. 13411). Springer, 541–559

    2022

  33. [41]

    Joachim Neu, Ertem Nusret Tas, and David Tse. 2024. Short Paper: Accountable Safety Implies Finality. InFC (1) (Lecture Notes in Computer Science, Vol. 14744). Springer, 41–50

    2024

  34. [42]

    Rafael Pass and Elaine Shi. 2017. The Sleepy Model of Consensus. InASIACRYPT (2) (Lecture Notes in Computer Science, Vol. 10625). Springer, 380–409

    2017

  35. [43]

    Rafael Pass and Elaine Shi. 2018. Thunderella: Blockchains with Optimistic Instant Confirmation. InEUROCRYPT (2) (Lecture Notes in Computer Science, Vol. 10821). Springer, 3–33

    2018

  36. [44]

    Ulysse Pavloff, Yackolley Amoussou-Guenou, and Sara Tucci Piergiovanni. 2024. Byzantine Attacks Exploiting Penalties in Ethereum PoS. InDSN. IEEE, 53–65

    2024

  37. [45]

    Pease, Robert E

    Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. 1980. Reaching Agree- ment in the Presence of Faults.J. ACM27, 2 (1980), 228–234

    1980

  38. [46]

    Alejandro Ranchal-Pedrosa and Vincent Gramoli. 2024. ZLB: A Blockchain to Tolerate Colluding Majorities. InDSN. IEEE, 209–222

    2024

  39. [47]

    Alex Shamis, Peter R. Pietzuch, Burcu Canakci, Miguel Castro, Cédric Fournet, Edward Ashton, Amaury Chamayou, Sylvan Clebsch, Antoine Delignat-Lavaud, Matthew Kerner, Julien Maffre, Olga Vrousgou, Christoph M. Wintersteiger, Manuel Costa, and Mark Russinovich. 2022. IA-CCF: In...

    2022

  40. [48]

    Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, and Pramod Viswanath. 2021. BFT Protocol Forensics. InCCS. ACM, 1722–1743

    2021

  41. [49]

    Elaine Shi. 2020. Foundations of Distributed Consensus and Blockchains. https: //www.distributedconsensus.net Book manuscript

    2020

  42. [50]

    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

    2024

  43. [51]

    Srivatsan Sridhar, Dionysis Zindros, and David Tse. 2023. Better Safe than Sorry: Recovering after Adversarial Majority. arXiv:2310.06338v2 [cs.CR]

    2023 arXiv

  44. [52]

    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. InSP. IEEE, 126–145

    2023

  45. [53]

    Ertem Nusret Tas, David Tse, Fisher Yu, and Sreeram Kannan. 2022. Babylon: Reusing Bitcoin Mining to Enhance Proof-of-Stake Security. arXiv:2201.07946v1 [cs.CR]

    2022 arXiv

  46. [54]

    reasonable

    Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abra- ham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In PODC. ACM, 347–356. A Additional Related Work We survey additional related works beyond those discussed in Sec. 7. Achieving ...

    2019

  47. [2024]

    InDISC (LIPIcs, Vol

    Granular Synchrony. InDISC (LIPIcs, Vol. 319). Schloss Dagstuhl - Leibniz- Zentrum für Informatik, 30:1–30:22

Pith tools

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