CS Paper Radar

Revisiting Fast Tendermint: An Agreement Violation and Two Repairs

Alejandro Ranchal-Pedrosa

cs.DC cs.CR ·submitted 2026-10-12 09:08 UTC · v1

Abstract

Fast Tendermint reduces Tendermint's good-case latency to two communication steps for n>=5f+1. We show that its published round-change rule violates Agreement: one Byzantine process suffices for every f>=1, and for f>=2 two Byzantine processes suffice without double signing. The failure occurs when a process advances past a round without recording the value that may have been decided there. The Quint specification that accompanies the protocol does not allow this kind of round skipping and is not affected; the violation lies in the published pseudocode. We present two repairs. Walk requires a process to leave each round on a quorum of that round's precommits and to precommit before leaving. It keeps the recorded valid state and removes the wait after a precommit quorum. Justify carries the evidence needed to accept a proposal in the proposal itself, removing both the recorded valid state and the proposer's synchronization wait. Both satisfy Agreement and Validity under asynchrony and Termination under the partially synchronous gossip model of Tendermint and Fast Tendermint. Both retain proposal timeouts. The main text presents the executions that violate Agreement and explains the two repairs. The appendices provide proofs, a brief comparison with other round-change designs, and an extension to chains.

Closest papers

Nearest neighbours by meaning across the whole index.

Fast Tendermint: Speeding Up a Foundational Consensus Protocol

cs.DC ·2026-08-13 ·Preston Vander Vos, Daniel Cason
similarity 0.82
Abstract

Tendermint is among the most widely studied and deployed Byzantine fault-tolerant (BFT) consensus protocols, owing in part to its native leader-rotation mechanism that subsumes complex view changes. Like most partially-synchronous BFT protocols, Tendermint tolerates $f < n/3$ Byzantine processes and decides in three communication steps. Motivated by the push for lower-latency blockchains, a recent line of work shows that consensus can be solved in two communication steps when $f < n/5$. We present Fast Tendermint, an adaptation of Tendermint to the $n > 5f$ setting that decides in two communication steps in the good case, while preserving Tendermint's leader-rotation structure. Fast Tendermint collapses Tendermint's prevote and precommit steps into a single voting step and merges the $locked$ and $valid$ state. We give proofs of agreement, validity, and termination, and a formal specification in Quint, a modern surface syntax for TLA+, used to model-check the protocol.

0.40

SoK: Design Choices in Tendermint BFT Consensus

cs.DC cs.CR ·2026-11-11 ·Sanaz Taheri-Boshrooyeh, Yahya Hassanzadeh-Nazarabadi
survey similarity 0.64
Abstract

Tendermint is a consensus protocol that tolerates Byzantine faults, implemented first by the Tendermint Core engine and now by CometBFT. Realizing the protocol's separation of agreement from execution, the Application Blockchain Interface (ABCI) of these engines keeps consensus apart from the replicated application, so one engine can serve many independent proof-of-stake chains. A sustained body of research proposes changes that span the protocol's mechanisms, from vote dissemination to block proposal and reward distribution, yet to our knowledge no survey studies the protocol and these works as one family, and broader surveys do not take Tendermint as their subject. We describe the baseline, the protocol as consolidated from its original descriptions, by its design choices. Each is a decision, such as how votes spread or how proposers rotate, through which the baseline provides safety and liveness or another property under its fault and timing model. We classify each work by the design choice it renegotiates, that is, modifies or replaces, by the properties it strengthens or weakens, and by whether its result needs a stronger model. Taking a broader perspective on that classification, we group the surveyed works' solutions into a few threads of concern in the baseline, namely its performance, the accountability of its validators, and the protection of exploitable information. For each thread, we identify the recurring strategies that their approaches follow. Together, these threads and strategies describe the current state of research on the Tendermint family. Where the strategies leave gaps, we pose future directions, each as an open question under an explicit fault and timing model.

0.15

Minimizing Commit Rules for DAG-based Atomic Broadcast

cs.DC ·2026-08-18 ·Petr Kuznetsov, Maxence Perion, Sara Tucci-Piergiovanni
hot direction similarity 0.64
Abstract · We have received external feedback that invalidates the results presented in the paper: a counterexample was found that breaks the safety of…

A popular class of Byzantine fault-tolerant atomic broadcast protocols rely on directed acyclic graphs (DAGs) that represent causal relations between broadcast messages. Each process applies a protocol-specific \emph{commit rule} on its local DAG to determine which vertices can be delivered in a total order. Intuitively, commit rules that impose fewer conditions on the DAG to order its vertices imply more efficient protocols, as the broadcast messages are delivered with lower latency. In this paper, we define commit rules on an uncertified round-based DAG construction, and introduce a sub-rule relation between them: a commit rule $cr_1$ is a sub-rule of a commit rule $cr_2$ if, for any DAG, the set of vertices committed by $cr_1$ contains all vertices committed by $cr_2$. We use the sub-rule relation to determine a minimal commit rule in an eventually synchronous model and a minimal commit rule in an asynchronous model, namely, two commit rules that require the least conditions on the DAG to safely commit any set of vertices in their respective models. To the best of our knowledge, no existing DAG-based atomic broadcast protocol relies on such minimal commit rules: we introduce \emph{Minnow}, a new protocol for DAG-based atomic broadcast, which can be instantiated in both eventually synchronous (S-Minnow) and asynchronous networks (A-Minnow).

0.24

Steelhead: Interleaving Partially Synchronous and Asynchronous Commit Rules on a Shared DAG

cs.DC cs.CR ·2026-09-24 ·Zeno De Angeli, Philipp Jovanovic, Lefteris Kokoris-Kogias, Markus Legner, Alberto Sonnino
theory similarity 0.63
Abstract

Dual-mode consensus protocols are fast when the network is partially synchronous and remain live under asynchrony. We introduce Steelhead, a dual-mode mechanism that composes a partially synchronous and an asynchronous commit rule over one DAG: every k-th round is decided by the asynchronous rule, whose leader a common coin reveals after the votes, and all other rounds by the partially synchronous rule. Every interval, validators replay the committed DAG under each candidate period, adopt the one with the fewest expected message delays, and fall back to k = 1 when the output stalls; the asynchronous rule applied to the coin rounds alone keeps the protocol live. Steelhead sends no message beyond the DAG's blocks, not even to agree on the period, and opens a coin only on the rounds that need a hidden leader. It is generic over pairs of DAG commit rules that share a committee; we instantiate it with Mysticeti and Mahi-Mahi at n >= 3f+1 and with the two variants of BlueBottle at n >= 5f+1. We prove it safe and live, and provide mechanized proofs in Lean 4. In simulation, Steelhead matches the partially synchronous protocol in a healthy network, stays close to the asynchronous one when network conditions stall the partially synchronous one, and adapts quickly in both directions.

0.26

Vantage: Availability-Graded Broadcast for Signature-Free BFT

cs.DC cs.CR ·2026-08-17 ·Nikita Polyanskii
hot direction similarity 0.63
Abstract · 65 pages

Digital signatures make blocks and votes transferable evidence: one party can prove to another what a third party said. Authenticated channels convince only the direct receiver, so a proposer that references another party's block cannot prove to the voters who published it. High-throughput signature-free protocols therefore complete an availability vote or a reliable broadcast for every published data block before a proposer may reference it. We present Vantage, a partially synchronous Byzantine fault-tolerant protocol for $n \ge 3f+1$ parties, at most $f$ Byzantine, that uses only authenticated channels and collision-resistant hashing. Parties publish blocks on hash-linked author lanes; each view's proposer pairs a core manifest of lane prefixes that a quorum has acknowledged to it with an optimistic tip manifest of blocks it has just received. A new primitive, Availability-Graded Broadcast (AGB), makes the core irrevocable on a quorum of directly received acknowledgments while grading, rather than blocking on, the tip. A view that AGB leaves open or silent is decided by an on-demand instance of information-theoretic agreement. A block may thus be referenced in a proposal one message delay after publication, as in signed optimistic designs. Let $δ$ be the message delay after global stabilization (GST). With all parties correct, a proposal commits within $2δ$ of its send if all $n$ parties support it, and within $3δ$ on the quorum path, so a block published in time for the next proposal is sequenced $3δ$ to $4δ$ after publication. Safety holds under asynchrony; liveness holds after GST. On an emulated ten-region WAN with 100 parties, Vantage has the lowest p50 latency among compared signed and signature-free protocols at every offered load up to its peak, and sequences 250k 512-byte transactions per second at median end-to-end latency below 500 ms.

0.48

Simple and Fast Signature-Free Blockchain Consensus

cs.DC ·2026-09-26 ·Giuliano Losa, Xuechao Wang, Zhuolun Xiang, Qianyu Yu
similarity 0.63
Abstract

Signature-free protocols avoid the cost of post-quantum signatures. We present two simple signature-free blockchain consensus protocols for eventual synchrony with optimal good-case commit latency (three message delays for \(f<n/3\) and two for \(f<n/5\)), optimistic responsiveness, a block time of only two message delays without speculation, and \(O(n^2)\) communication per view. They instantiate Generic Simplex, a blockchain consensus construction parameterized by a new abstraction called view agreement. The same construction also captures Simplex, Minimmit, and a new synchronous signature-free protocol with optimal good-case commit latency of two message delays for \(f<n/4\).

0.22

When Is a Reconciliation Break Real? A Temporal Correctness Contract for Streaming Financial Reconciliation

cs.SE ·2026-10-10 ·Abhishek Sharma
code/data similarity 0.62
Abstract · 9 pages, 4 figures, 6 tables, 2 propositions. Code and reproducibility materials: https://github.com/abhisheksharma2411/reconstream (v1.0.2)…

Reconciliation systems decide, continuously, whether money the ledger expected has arrived at the bank. On an asynchronous stream that decision is taken against partial evidence: a credit that has not appeared may be missing, or may simply not have been posted yet. Deployed pipelines settle this with a timeout or a watermark, and the exceptions are treated as findings. We give a temporal correctness contract that says when such a verdict is admissible, relative to a declared per-source lateness bound, and a checker for it that needs no ground truth. The contract separates three things an operator otherwise sees only as a rising break rate: the reconciler decided too early, an input broke the bound it declared, or the money really is gone. On workloads from a published payment simulator, the standard remedy for a stalled streaming join, an idleness timeout, introduces contract violations on 5.42% of obligations (95% CI [3.94, 6.92]) on traffic where the same job without it is exactly sound, and violations vanish once the timeout reaches the slow source's posting period, as predicted. Under a lateness shift, all four identity-based reconcilers we test raise spurious breaks on between 18.3% and 23.0% of the credits the bank did settle, while their contract violation rate stays at or below 1.01%: the checker attributes the loss to 240 bank-side and 413 ledger-side bound violations rather than to the reconcilers. Tracking one horizon per source leaves break latency 12.7% lower on average and halves its tail (p99 224 against 446 ticks) at equal soundness, though it is not cheaper at every cost setting and we report where it loses. An Apache Flink interval join, written the ordinary way, violates the contract on 14.9--20.1% of obligations. The contract is expressible as SQL over the tables a reconciliation system already keeps, agreeing with the reference implementation on all 4,395 verdicts.

0.37

Breaking Fault Lines: Unifying TEE-Assisted BFT Consensus in Partially Trusted Worlds

cs.DC ·2026-09-09 ·Xiaoqing Wen, Tong Liu, Jianyu Niu, Jialin Li, Cong Wang +2 more
published similarity 0.62
Abstract · Accepted to EuroSys 2027

This paper revisits TEE-assisted BFT under a universal partial-TEE model, where an arbitrary subset of replicas execute inside TEEs while the remaining replicas operate without hardware trust guarantees. We show that heterogeneous trust changes the structure of quorum formation and fault tolerance. In particular, we derive a tight resilience bound f < max {n/3, m/2}, where n is the total number of replicas and m is the number of TEE-enabled replicas. The result reveals a sharp threshold phenomenon: TEEs improve fault tolerance only once they exceed two-thirds of the deployment. Guided by this characterization, we introduce two protocol principles: (1) a dual-quorum construction that safely combines TEE-only and mixed quorums, and (2) a TEE-leader fast path that leverages hardware-enforced non-equivocation to reduce both consensus and view-change latency. We realize these ideas in Raftel, which is, to our knowledge, the first HotStuff-style BFT protocol designed explicitly for arbitrary partial-TEE deployments, and in chained-Raftel, a pipelined variant that further accelerates mixed-trust execution. We implement both protocols atop Intel SGX and evaluate them in LAN and WAN environments. Our results show that Raftel achieves up to 625 TPS with sub-670 ms latency in WAN settings, outperforming HotStuff by up to 308 TPS in throughput while approaching the performance of fully TEE-assisted protocols.

0.26