CS Paper Radar

When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT

Arnab Mallick, Indraveni Chebolu

cs.DC cs.CRcs.DScs.NI ·submitted 2026-10-06 04:55 UTC · v1
published

Abstract

Byzantine quorum safety relies on correct replicas refusing to sign conflicting values. A replica that loses its protocol state during recovery but retains its identity and signing key may forget an earlier vote. We study certificates formed by matching signed votes from at least $q$ of $n$ replicas, assuming that each correct replica avoids conflicting votes between recoveries. If two conflicting certificates form, their overlap has size between $2q-n$ and $b+c$, where $b$ counts Byzantine replicas and $c$ counts correct identities that recovered during the execution considered. Our main result decomposes the slack $b+c-(2q-n)$ into four nonnegative counts: extra signers in the first certificate, extra signers in the second, identities in neither certificate, and Byzantine or recovering identities outside their overlap. Zero slack forces an exact signer partition. With $n=3f+1$ replicas, threshold $q=2f+1$, at most $f$ Byzantine replicas, and exactly one correct recovery event, any conflicting pair forces exactly $f$ Byzantine replicas, all in the overlap together with the recovered replica; each certificate has a disjoint side of $f$ correct replicas. A minimal protocol attains this form. We distinguish certificate formation from acceptance, give a sufficient check using configured fault and recovery caps, and explain why durable vote records written before signature release prevent the conflict.

Comment
To be appeared at ICDCN 2027 as a Short Paper

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Subcubic Byzantine Agreement with Plain PKI

cs.DC ·2026-11-04 ·Marc Dufay, Roger Wattenhofer
theory similarity 0.63
Abstract

We consider Byzantine Agreement (BA), where $n$ parties run a distributed protocol to agree on a common value, despite $t$ parties being byzantine. In the synchronous setting, a choice must be made between the weaker unauthenticated setting, which only allows $t < n/3$ byzantine parties, and the stronger authenticated setting that allows up to $t < n/2$ byzantine parties. For this latter setting, BA can be solved with optimal resiliency and optimal bit complexity. However, so far, all optimal solutions rely on the use of threshold signatures. This shows a gap compared to regular signatures, where only protocols with cubic complexity are known for optimal resiliency $t < n/2$. We wonder whether this cubic complexity is required without the use of threshold signatures and show that this is not the case. More specifically, given $κ$ an upper bound on the size of a hash or signature, we describe a deterministic protocol solving BA with bit complexity $\mathcal{O}(κ^{(\sqrt{13} - 1)/2} n^{(\sqrt{13} + 1)/2}) \approx \mathcal{O}(κ^{1.303}n^{2.303})$ while having optimal resiliency $t<n/2$ and round complexity $\mathcal{O}(n)$.

0.20

Optimal Adaptive Multi-Valued Byzantine Agreement

cs.DC ·2026-08-18 ·Marc Dufay, Anton Paramonov, Roger Wattenhofer
similarity 0.60
Abstract

In Byzantine Agreement (BA), $n$ parties, out of which $t$ can be Byzantine, run a distributed protocol to agree on a common valid input. Traditionally, these protocols have a linear latency and quadratic message complexity, making them impractical at a large scale. In their recent work, Constantinescu, Dufay, Paramonov, and Wattenhofer consider the actual number of byzantine parties $f \leq t$ and work toward decoupling the dependency on $n$ and $t$ in the complexity. They obtain a BA protocol with $\tilde{\mathcal{O}}(n + t\cdot f)$ message complexity and $\tilde{\mathcal{O}}(f)$ round complexity. However, their results are strictly limited to agreement on a binary value. Using the framework given by their work along with novel techniques, we extend these results for BA on an $L$-bit value. With $κ$ being a security parameter, and with optimal resiliency ($t < n/2$ in the synchronous setting or $t < n/3$ otherwise), we obtain: - In synchrony, a deterministic protocol with $\mathcal{O}(n\cdot (L + f \cdot κ))$ bit complexity and $\mathcal{O}(f + \log n)$ round complexity. - In synchrony and partial synchrony, deterministic protocols with $\tilde{\mathcal{O}}(n \cdot κ+ t\cdot (L + f \cdot κ))$ bit complexity and $\mathcal{O}(f)$ round complexity. - In asynchrony, a protocol with $\tilde{\mathcal{O}}(n \cdot κ+ t\cdot(L + t \cdot κ))$ expected bit complexity and expected $\mathcal{O}(1)$ latency.

0.44

Revisiting Fast Tendermint: An Agreement Violation and Two Repairs

cs.DC cs.CR ·2026-10-12 ·Alejandro Ranchal-Pedrosa
similarity 0.60
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.

0.09

Playing the SMR Game with Existential Honesty

cs.CR ·2026-11-18 ·Zeta Avarikioti, Odysseas Sofikitis, Christos Stefo
similarity 0.60
Abstract

State machine replication protocols are usually proven secure in the honest-Byzantine setting, which requires an honest supermajority of validators. Deployed systems offer no such guarantee: validators participate for profit and may deviate from the protocol whenever doing so increases their gains. In our work, every validator is rational or Byzantine, and none is honest. Rational validators may collude with each other and with the Byzantine ones, who may also bribe them to deviate. Known impossibility results show that, without honest validators, clients that decide whether to accept a transaction based on a non-interactive certificate and without further communication cannot be kept safe. To bypass these results, we let clients relay the certificates they receive to full nodes and wait before confirming transactions. We also assume that one full node, whose identity is unknown, is honest and always online. Under this assumption, we build a finalization layer over any certifiable quorum-based protocol in a synchronous network. Clients run an existing freezing gadget and fetch past certificates from the honest full node, which makes the protocol \emph{always-safe}: no two honest clients confirm conflicting ledgers, for any strategy of the validators. We incentivize participation through rewards, which the adversary may use to bribe rational validators into censoring transactions. In this setting, we formalize censorship and characterize it tightly: paying only with his rewards, the adversary censors less than a $\bw$ fraction of the available fees at each height, where $\bw$ is the fraction of the quorum he signs, and every coin of censorship beyond that comes from his own funds.

0.37

Vantage: Availability-Graded Broadcast for Signature-Free BFT

cs.DC cs.CR ·2026-08-17 ·Nikita Polyanskii
hot direction similarity 0.59
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.47

Fast Tendermint: Speeding Up a Foundational Consensus Protocol

cs.DC ·2026-08-13 ·Preston Vander Vos, Daniel Cason
similarity 0.59
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

Quantum Cadence: Post-Quantum Consensus with Multiple Concurrent Proposers

cs.DC cs.CR ·2026-10-23 ·Mohammad Mussadiq Jalalzai, Tobias Klenze, Jovan Komatovic
similarity 0.58
Abstract · 35 pages, 3 figures

The consensus protocols of most high-performance blockchains use quorum certificates, which bundle the signatures of a quorum of validators. Signature schemes such as BLS can aggregate the signatures of a whole quorum into a single short signature, which keeps these certificates small. A large-scale quantum computer would break these schemes, and no post-quantum scheme with comparable aggregate size and aggregation time is known. Without aggregation, a certificate holds one large post-quantum signature per member of the quorum, so it becomes infeasible for each validator to broadcast certificates, as modern consensus protocols often require. We present Quantum Cadence, a post-quantum consensus protocol with multiple concurrent proposers that avoids certificates altogether: every validator counts quorums among the messages it has received itself. Its safety and liveness do not even depend on signatures, although we add signatures to obtain accountability. Quantum Cadence builds on Cadence and replaces its slot consensus, Chorus, with Quantum Chorus, which keeps the optimal fast-path latency of Chorus: dissemination followed by two rounds of votes. When its fast path fails, Quantum Chorus runs Coda, our signature-free Byzantine agreement for multiple proposers. We also outline how the Conductor, which schedules the slots of Cadence, can be adapted to Quantum Cadence. In simulations with 200 validators, Quantum Chorus has a latency comparable to that of Chorus and scales better with the number of proposers.

0.50

Brief Announcement: Fair Binding for Hidden-State Authorization in Byzantine SMR

cs.DC ·2026-08-18 ·Arnab Mallick, Indraveni Chebolu
publishedhot direction similarity 0.57
Abstract · Accepted at DISC 2026

Validated Byzantine SMR assumes that replicas can evaluate the validity of an ordered command. Agent authorization creates a different regime: a command may be valid only relative to a committed policy state that validators cannot reconstruct from the log. A proof that an action was authorized at an old commitment is then only a historical attestation, it does not by itself reserve the hidden resource for later use. We isolate two independent requirements for safe live allocation of a hidden consumable resource under a Byzantine leader. First, arrival order at correct replicas must constrain commit order, the gap addressed by fair-ordering protocols. Second, a committed first request must bind later validity: it must make conflicting later requests invalid, not merely record that the first request was once authorized. The second requirement is non-vacuous precisely because the current policy state is hidden and not prefix-recoverable. Using an explicit authorization-witness interface, we characterize the two distinct obligations in this one-shot reservation model and give a fair reserve/use protocol satisfying both authorization safety and first-arrival liveness. Under trusted FIFO admission the two requirements collapse because admission and execution are atomic, Byzantine SMR separates request commitment from use.

0.43