Byzantine quorum safety depends on signer overlap and recovery events
When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT
Distributed, Parallel, and Cluster ComputingCryptography and SecurityData Structures and AlgorithmsNetworking and Internet Architecture
Summary
The paper looks at when distributed computer systems that can tolerate some faulty or malicious parts remain safe after crashes and recovery. The authors study how signed votes from many participants can be combined to prove a decision happened and what happens if some participants lose memory of their previous decisions. They find exact conditions relating the number of faulty and recovered nodes that can cause conflicting decisions. The paper also explains how to prevent these conflicts by recording votes durably before sharing signatures.
What this means in practice
- •For distributed system engineers: Design recovery protocols that prevent conflicting decisions in Byzantine fault tolerant systems by controlling fault and recovery thresholds.
- •For blockchain developers: Ensure safety of consensus certificates when nodes recover from crashes without losing safety guarantees in permissioned blockchains.
A theory result. No direct application yet.
Authors
Arnab Mallick, Indraveni Chebolu
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.