pith. sign in

arxiv: 2405.02615 · v2 · submitted 2024-05-04 · 💻 cs.CR

TetraBFT: Reducing Latency of Unauthenticated, Responsive BFT Consensus

Qianyu Yu , Giuliano Losa , Xuechao Wang This is my paper

Pith reviewed 2026-05-24 01:09 UTC · model grok-4.3

classification 💻 cs.CR
keywords Byzantine fault toleranceconsensuspartial synchronyunauthenticated protocolsoptimistic responsivenessblockchain
0
0 comments X

The pith

TetraBFT achieves unauthenticated BFT consensus in five message delays while using constant storage and optimal communication.

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

The paper introduces TetraBFT, an unauthenticated Byzantine fault tolerant consensus protocol for partially synchronous networks that avoids public key cryptography entirely. It seeks to establish that a single protocol can meet four properties together: constant local storage, optimal communication complexity, optimistic responsiveness that tracks real network speeds when faults are absent, and completion after only five message delays. A sympathetic reader would care because prior unauthenticated protocols could not combine all these traits at once, limiting their use in systems that need both security against unbounded adversaries and low overhead. The work supplies a security proof, formal verification, and an extension that applies pipelining to produce a chained multi-shot version.

Core claim

TetraBFT solves consensus in partial synchrony without authentication by using a protocol structure that meets constant storage, optimal communication, optimistic responsiveness, and five message delay latency, outperforming prior unauthenticated protocols with these properties. It further applies pipelining to create a chained multi-shot version.

What carries the argument

The protocol's specific sequence of message exchanges and decision rules that permit agreement after five delays without signatures or growing storage.

Load-bearing premise

It is possible to design one unauthenticated protocol that simultaneously satisfies constant storage, optimal communication, optimistic responsiveness, and five-message-delay consensus in partial synchrony.

What would settle it

An execution trace or formal counter-example showing that TetraBFT either exceeds five message delays or violates constant storage or optimal communication under the stated network model.

Figures

Figures reproduced from arXiv: 2405.02615 by Giuliano Losa, Qianyu Yu, Xuechao Wang.

Figure 1
Figure 1. Figure 1: Liveness lemmas logical framework. for smaller value of 𝑣 ′ , thus also reducing the computational complexity. The algorithm maintains an overall complexity of 𝑂(𝑣 × 𝑚 × 𝑛), the same as Algorithm 4. 4 SECURITY ANALYSIS In this section, we prove that Basic TetraBFT solves the problem of consensus as defined in Definition 1. We first prove some useful lemmas on liveness and safety. The proof for liveness is … view at source ↗
Figure 2
Figure 2. Figure 2: Example of Multi-shot TetraBFT in the good case. [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example of Multi-shot TetraBFT with failed blocks. [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
read the original abstract

This paper presents TetraBFT, a novel unauthenticated Byzantine fault tolerant protocol for solving consensus in partial synchrony, eliminating the need for public key cryptography and ensuring resilience against computationally unbounded adversaries. TetraBFT has several compelling features: it necessitates only constant local storage, has optimal communication complexity, satisfies optimistic responsiveness -- allowing the protocol to operate at actual network speeds under ideal conditions -- and can achieve consensus in just 5 message delays, which outperforms all known unauthenticated protocols achieving the other properties listed. We validate the correctness of TetraBFT through rigorous security analysis and formal verification. Furthermore, we extend TetraBFT into a multi-shot, chained consensus protocol, making a pioneering effort in applying pipelining techniques to unauthenticated protocols. This positions TetraBFT as a practical and deployable solution for blockchain systems aiming for high efficiency.

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 presents TetraBFT, an unauthenticated BFT consensus protocol for partial synchrony that requires no public-key cryptography and resists unbounded adversaries. It claims constant local storage, optimal communication complexity, optimistic responsiveness, and consensus in 5 message delays (outperforming prior unauthenticated protocols with the other listed properties). Correctness is supported by security analysis and formal verification; the protocol is extended to a chained multi-shot version via pipelining for blockchain use.

Significance. If the central claims hold, the result would be significant: it would demonstrate a novel combination of constant storage, optimal communication, optimistic responsiveness, and 5-delay latency in the unauthenticated partial-synchrony model, with the first application of pipelining to such protocols. The formal verification and security analysis strengthen the contribution for practical deployment.

major comments (2)
  1. [§4, §5] §4 (Protocol Description) and §5 (Latency Analysis): the 5-message-delay claim is load-bearing for the main contribution; the section must explicitly map each of the five delays to the protocol steps (including view-change and leader election under partial synchrony) and show why no additional delays arise from the unauthenticated setting.
  2. [§6] §6 (Security Analysis): the proof that constant storage is maintained while achieving optimistic responsiveness must be checked against the storage data structures; any hidden linear growth in the number of pending proposals would contradict the constant-storage claim.
minor comments (2)
  1. Notation for message types and views is introduced without a consolidated table; a single table listing all message formats would improve readability.
  2. The formal verification section references a tool but does not state the exact properties verified (safety, liveness, responsiveness) or the model used; add this explicitly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful review and for identifying areas where additional clarity would strengthen the presentation. We address each major comment below and will incorporate revisions to improve explicitness in the relevant sections.

read point-by-point responses

  1. Referee: [§4, §5] §4 (Protocol Description) and §5 (Latency Analysis): the 5-message-delay claim is load-bearing for the main contribution; the section must explicitly map each of the five delays to the protocol steps (including view-change and leader election under partial synchrony) and show why no additional delays arise from the unauthenticated setting.

    Authors: We agree that an explicit mapping will improve readability. The current §4 describes the message flows and §5 counts the delays under optimistic responsiveness, but we will revise §5 to include a numbered breakdown that directly associates each of the five delays with specific protocol steps (proposal dissemination, voting, certificate collection, view-change initiation, and leader election). The argument that the unauthenticated setting adds no extra delays will be expanded by referencing the hash-chain and flooding mechanisms already present in the protocol, which are folded into the existing delay count rather than requiring additional rounds. This change will be made in the next version. revision: yes

  2. Referee: [§6] §6 (Security Analysis): the proof that constant storage is maintained while achieving optimistic responsiveness must be checked against the storage data structures; any hidden linear growth in the number of pending proposals would contradict the constant-storage claim.

    Authors: We re-verified the data structures and proof in §6 against the protocol description. Storage remains constant because the protocol bounds the number of retained proposals to a fixed window (current view plus a constant number of prior views) via the locking rule and view-synchronization primitive; proposals outside this window are discarded upon view change. Optimistic responsiveness does not create unbounded pending proposals because a new leader only advances after collecting a quorum from the prior view, preventing accumulation. The formal verification model encodes these bounds. We will add a short clarifying paragraph in the revised §6 that cross-references the exact data-structure fields to make the constant bound fully explicit. revision: partial

Circularity Check

0 steps flagged

No significant circularity; protocol construction is self-contained

full rationale

The paper presents TetraBFT as a new protocol construction achieving listed properties (constant storage, optimal communication, optimistic responsiveness, 5-message-delay consensus) in an unauthenticated partial-synchrony model. Claims rest on explicit protocol description plus separate rigorous security analysis and formal verification, with no equations, fitted parameters, or predictions that reduce by construction to inputs. No self-citation chains, ansatzes, or renamings appear as load-bearing steps in the provided abstract or central claims. The derivation is therefore independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no identifiable free parameters, axioms, or invented entities; the protocol is presented as a new construction without explicit modeling details.

pith-pipeline@v0.9.0 · 5671 in / 1212 out tokens · 28454 ms · 2026-05-24T01:09:51.544019+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. 2021. Good-case Latency of Byzantine Broadcast: a Complete Categorization. InProceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC’21). Association for Computing Machinery, New York, NY, USA, 331–341. https://doi.org/10.1145/3465084.3467899 22 Qianyu Yu, Giuliano Losa a...

    work page doi:10.1145/3465084.3467899 2021

  2. [2]

    Ittai Abraham, Ling Ren, and Zhuolun Xiang. 2022. Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization. InDROPS-IDN/v2/document/10.4230/LIPIcs.OPODIS.2021.5. Schloss-Dagstuhl - Leibniz Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.5

    work page doi:10.4230/lipics.opodis.2021.5 2022

  3. [3]

    Ittai Abraham and Gilad Stern. 2020. Information theoretic hotstuff.arXiv preprint arXiv:2009.12828(2020)

    work page arXiv 2020

  4. [4]

    Ittai Abraham and Gilad Stern. 2021. Information Theoretic HotStuff (IT-HS): Part One. https://decentralizedthoughts. github.io/2021-09-20-information-theoretic-hotstuff-it-hs-part-one/

    work page 2021

  5. [5]

    Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić. 2020. Security analysis of ripple consensus.arXiv preprint arXiv:2011.14816(2020)

    work page arXiv 2020

  6. [6]

    Hagit Attiya and Jennifer L Welch. 2023. Multi-valued connected consensus: A new perspective on crusader agreement and adopt-commit.arXiv preprint arXiv:2308.04646(2023)

    work page arXiv 2023

  7. [7]

    Hagit Attiya and Jennifer L. Welch. 2023. Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit. https://doi.org/10.48550/arXiv.2308.04646 arXiv:2308.04646 [cs]

    work page doi:10.48550/arxiv.2308.04646 2023

  8. [8]

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

    Ethan Buchman. 2016.Tendermint: Byzantine fault tolerance in the age of blockchains. Ph. D. Dissertation. University of Guelph

    work page 2016

  9. [9]

    Christian Cachin. 2021. Asymmetric distributed trust. InInternational Conference on Distributed Computing and Networking 2021. 3–3

    work page 2021

  10. [10]

    Christian Cachin, Giuliano Losa, and Luca Zanolini. 2023. Quorum Systems in Permissionless Networks. In26th International Conference on Principles of Distributed Systems (OPODIS 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 253), Eshcar Hillel, Roberto Palmieri, and Etienne Rivière (Eds.). Schloss Dagstuhl – Leibniz- Zentrum für I...

    work page doi:10.4230/lipics.opodis.2022.17 2023

  11. [11]

    2001.Practical Byzantine Fault Tolerance

    Miguel Castro. 2001.Practical Byzantine Fault Tolerance. Ph.D. MIT

    work page 2001

  12. [12]

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

    work page 2002

  13. [13]

    Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. InOsDI, Vol. 99. 173–186

    work page 1999

  14. [14]

    Benjamin Y Chan and Elaine Shi. 2020. Streamlet: Textbook streamlined blockchains. InProceedings of the 2nd ACM Conference on Advances in Financial Technologies. 1–11

    work page 2020

  15. [15]

    Danny Dolev and Rüdiger Reischuk. 1985. Bounds on Information Exchange for Byzantine Agreement.J. ACM32, 1 (Jan. 1985), 191–204. https://doi.org/10.1145/2455.214112

    work page doi:10.1145/2455.214112 1985

  16. [16]

    Dolev and H

    D. Dolev and H. R. Strong. [n. d.]. Authenticated Algorithms for Byzantine Agreement. 12, 4 ([n. d.]), 656–666. https://doi.org/10.1137/0212045 Publisher: Society for Industrial and Applied Mathematics

    work page doi:10.1137/0212045

  17. [17]

    Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the presence of partial synchrony.Journal of the ACM (JACM)35, 2 (1988), 288–323

    work page 1988

  18. [18]

    Álvaro García-Pérez and Alexey Gotsman. 2018. Federated Byzantine Quorum Systems. In22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

    work page 2018

  19. [19]

    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

  20. [20]

    Mohammad M Jalalzai, Jianyu Niu, Chen Feng, and Fangyu Gai. 2023. Fast-hotstuff: A fast and robust bft protocol for blockchains.IEEE Transactions on Dependable and Secure Computing(2023)

    work page 2023

  21. [21]

    Igor Konnov, Jure Kukovec, and Thanh-Hai Tran. 2019. TLA+ model checking made symbolic.Proceedings of the ACM on Programming Languages3, OOPSLA (Oct. 2019), 123:1–123:30. https://doi.org/10.1145/3360549

    work page doi:10.1145/3360549 2019

  22. [22]

    2002.Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers

    Leslie Lamport. 2002.Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers. Addison- Wesley Longman Publishing Co., Inc., USA

    work page 2002

  23. [23]

    Andrew Lewis-Pye and Tim Roughgarden. 2023. Permissionless Consensus. https://doi.org/10.48550/arXiv.2304.14701 arXiv:2304.14701 [cs]

    work page doi:10.48550/arxiv.2304.14701 2023

  24. [24]

    Xiao Li, Eric Chan, and Mohsen Lesani. 2023. Quorum subsumption for heterogeneous quorum systems. In37th International Symposium on Distributed Computing (DISC 2023). Schloss-Dagstuhl-Leibniz Zentrum für Informatik

    work page 2023

  25. [25]

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

    work page 2019

  26. [26]

    Giuliano Losa, Eli Gafni, and David Mazières. 2019. Stellar Consensus by Instantiation. In33rd International Symposium on Distributed Computing (DISC 2019) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 146), Jukka Suomela (Ed.). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 27:1–27:15. https://doi.org/10.4230/ LIP...

    work page 2019

  27. [27]

    Dahlia Malkhi and Kartik Nayak. 2023. HotStuff-2: Optimal Two-Phase Responsive BFT.Cryptology ePrint Archive (2023). TetraBFT: Reducing Latency of Unauthenticated, Responsive BFT Consensus 23

    work page 2023

  28. [28]

    Rafael Pass and Elaine Shi. 2018. Thunderella: Blockchains with Optimistic Instant Confirmation. InAdvances in Cryptology – EUROCRYPT 2018 (Lecture Notes in Computer Science), Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer International Publishing, Cham, 3–33. https://doi.org/10.1007/978-3-319-78375-8_1

    work page doi:10.1007/978-3-319-78375-8_1 2018

  29. [29]

    Pease, R

    M. Pease, R. Shostak, and L. Lamport. [n. d.]. Reaching Agreement in the Presence of Faults. 27, 2 ([n. d.]), 228–234. https://doi.org/10.1145/322186.322188

    work page doi:10.1145/322186.322188

  30. [30]

    Peiyao Sheng, Xuechao Wang, Sreeram Kannan, Kartik Nayak, and Pramod Viswanath. 2023. TrustBoost: Boosting Trust among Interoperable Blockchains. InProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. 1571–1584

    work page 2023

  31. [31]

    Ertem Nusret Tas, Runchao Han, David Tse, and Mingchao Yu. 2023. Interchain timestamping for mesh security. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. 1585–1599

    work page 2023

  32. [32]

    long enough

    Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT consensus with linearity and responsiveness. InProceedings of the 2019 ACM Symposium on Principles of Distributed Computing. 347–356. 24 Qianyu Yu, Giuliano Losa and Xuechao Wang APPENDIX A HELPER ALGORITHMS Algorithm 4A leader determines value𝑣𝑎𝑙safe in v...

    work page 2019