Settling The Round Complexity of Byzantine Agreement Against a Full-Information, Adaptive Adversary Yuval Efron1 1
IAS
July 17, 2026
arXiv:2607.14413v1 [cs.DC] 15 Jul 2026
Abstract We prove that every randomized synchronous Byzantine Agreement protocol in the fullinformation, strongly adaptive adversary model, secure against t corrupt parties, has worst-case expected round complexity t2 . Ω n log(n + 1) This improves upon the seminal Ω( √ t ) bound of [Bar-Joseph, Ben-Or 98]. Our result n log nn 2 o n matches the recent upper bound of O min t log , logt n of [Dufoulon, Pandurangan 25], up n to a log2 n factor in the t ≪ n regime. Our proof takes inspiration from the recent works of [Etesami, Mahloujifar, Mahmoody 20] and [Haitner, Karidi-Heller 26]. Specifically, we prove a multi-round concentration lemma showing that q any transcript event of probability p can be forced with probability one by corrupting O( n log( p1 )) parties in expectation. From there, tools from [Chor, Merritt, Shmoys 89] allow us to lower-bound the probability of the protocol 1 not concluding in R rounds by nO(R) , using a crash schedule involving at most R parties. The combination of these techniques yields the desired bound.
1
Introduction
Byzantine agreement (BA), the problem in which n parties, of which at most t are corrupt and controlled by an adversary, must reach agreement on a value, is a cornerstone problem of distributed computing. Since its inception in the seminal work of [LSP82], it has been studied intensively over the last 45 years, along many axes [Rab83; DR85; FLP85; BG93; CKS05; KK06; Gar+07; Nak08; KS11; Abr+19; MR21; CP23; BCG24]. In this work, we focus on synchronous point-to-point networks, in which a message sent in round r arrives at its recipient by round r + 1. Of the many efficiency metrics that have been studied for the BA task, we focus on round complexity, which measures the number of rounds a protocol takes to converge to a decision: in the worst case for a deterministic protocol, or in expectation (over the protocol randomness) for a randomized protocol. Round complexity. For deterministic protocols, the landscape of round complexity of BA protocols has been well studied and is by now well understood. Specifically, [DS83] proved that any 1
deterministic BA protocol secure against t faults must have round complexity of at least t + 1. A plethora of protocols in the literature achieve this bound, some concretely and some asymptotically, trading off various other efficiency metrics and settings [Dol+82; DS83; KM13; MR21]. In this work, we focus on randomized protocols, for which the round-complexity landscape, while studied, is far from understood. Before proceeding, we discuss an important facet of the problem whenever randomness is brought up: the adaptivity and knowledge of the adversary. Adaptivity. In the context of randomized protocols, a gross partition separates adversaries into two categories: static and adaptive. A static adversary chooses the set of corrupt parties before the beginning of the protocol, i.e., before viewing any random outcomes throughout the protocol. An adaptive adversary, on the other hand, may corrupt parties during the protocol execution, based on the parties’ internal private states, coin flips, and other information available to it. We note that the distinction between static and adaptive adversaries is irrelevant for deterministic protocols. Knowledge & computational power. In the private channels setting, it is assumed that parties, along with having private states, communicate over secure channels, the content of which the adversary cannot see. In the full-information setting, on the other hand, the adversary has a complete view of every communication channel and the internal states of all parties at any point in time. Importantly, however, the full-information adversary cannot know the future states of parties (e.g., their coin-flip outcomes in future rounds); it has access only to information up to the current round. We say that the adversary is rushing if, in round r, the adversary can also view the randomness of all parties in round r and, based on this information, can corrupt parties before round-r messages are delivered. Moreover, the adversary can either be computationally bounded, in which case cryptographic primitives can be employed, or computationally unbounded. In this paper, we consider the full-information, rushing, adaptive, computationally unbounded adversary. Interest in the full-information setting has recently been rekindled in several works [AS20; YLW24; CEK25; Abr+26; Yu+26], due to the looming threats posed to modern cryptographic tools by quantum computers and side-channel attacks. We note that in this model, the BA task is feasible iff t < n3 , irrespective of the synchrony assumption of the network [LSP82; FLM86]. Round complexity of randomized protocols. The round complexity of BA protocols is well understood in the context of a static adversary. A long line of work (see [BPV06; GPV06] and references therein) has explored the problem, culminating in the work of Goldwasser, Pavlov, and n n Vaikuntanathan [GPV06], which designs a BA protocol tolerating t < 3+ϵ faults with O( log ) rounds ϵ2 in expectation against a full-information, rushing, computationally unbounded adversary. A lower bound is also known from the influential work of Chor, Merritt, and Shmoys [CMS89], which shows −r that any BA protocol terminating in r rounds must have failure probability at least Ω(( rn t ) ), even against a crash-fault adversary. The round complexity of BA is also well understood when the adversary is adaptive but channels are private, or when the adversary is computationally bounded and has no access to internal states. Vast amounts of work have been carried out in these settings, e and by now many works in these settings boast BA protocols with O(1) or O(1) expected round complexity [KK06; KS11; Abr+19]. Previous work. As mentioned, we consider a full-information, adaptive, rushing adversary. In our considered setting, the pioneering work of Chor and Coan [CC85] designed a BA protocol with 2
expected round complexity O( logt n )1 , beating the Ω(t) lower bound for deterministic protocols. t Later, the seminal work of Bar-Joseph and Ben-Or [BB98] established a lower bound Ω( √n log ) on n the expected round complexity of BA protocols in our setting, even against crash failures. They also showed their bound to be tight in the crash-failure setting by exhibiting a corresponding protocol. Progress on the problem then stalled until a recent breakthrough last year by Dufoulon t2 log n and Pandurangan [DP25], who designed a protocol with expected round complexity O( n o). n Combined with the result of Chor and Coan, the state of the art then has an O(min protocol for the problem.
t2 log n t n , log n
)
Main Result. In this work, we nearly settle the round complexity of the BA task in the fullinformation, rushing, adaptive-adversary model by exhibiting an adversary that establishes an t2 Ω n log(n + 1)
!
lower bound on the expected round complexity of any BA protocol that tolerates t corruptions. Additional related work. A full review of the wealth of literature on BA is beyond the scope of this work. Directly relevant lines of work include work on full-information adaptive adversaries in asynchrony and work on late adversaries. The early works of Ben-Or [Ben83] and Bracha [Bra87] presented asynchronous BA protocols in the full-information, adaptive setting, albeit with exponential round complexity. The first such protocol with polynomial expected round complexity was given by King and Saia [KS16; KS18]. Their resilience, however, is far from optimal. More recent work by Huang, Pettie, and Zhu [HPZ22; HPZ24] improved on the state of the art by an impressive margin, obtaining protocols with near-optimal resilience and O(n4 ) expected round complexity. The optimality question, however, remains far from resolved, with the state-of-the-art lower bound being Ω(n) by the work of Attiya and Censor-Hillel [AC08], building on [Asp98]. Another angle that has been considered in the literature is that of a late adversary. A late adversary, in round r, has a complete view of the protocol transcript and local coin flips up to some previous round r − d. This cleanly interpolates between static and adaptive adversaries. The work of [RSS18] explored the almost-everywhere BA task in this setting.
2
Preliminaries
We consider a setting with n parties connected by synchronous authenticated point-to-point channels. Furthermore, parties may utilize randomness by locally tossing coins. In particular, we assume no setup for a common coin or any other setup. In other words, we consider the plain model. The adversary. We consider a full-information, strongly adaptive, rushing adversary. Specifically, for every r, at the beginning of round r, the adversary sees the internal states, local coin flips, and protocol transcript up to round r. It then also sees the local coin tosses and resulting internal states of all parties in round r, after which it can choose parties to corrupt in round r, prior to any 1 The original paper designs a Monte Carlo protocol that solves BA w.h.p. The recent work of [DP25] shows that it can be easily modified to a Las Vegas version.
3
round-r message being delivered. A party, once corrupted, stays corrupted for the entire execution. A corrupt party is completely controlled by the adversary in all of its actions. We say that the adversary is t-bounded in a given execution if |Cr | ≤ t for all rounds r of the execution, where Cr denotes the set of corrupt parties at the end of round r. In a given execution, a party p is correct in round r if p ∈ / Cr . A party is forever correct in a given execution if p ∈ / Cr for all rounds r. All protocol randomness consists of mutually independent local coin flips that are private from the other correct parties. Byzantine Agreement (BA). In the BA task, each party i ∈ [n] has an input xi ∈ {0, 1}. Given a protocol Π and an adversary A, we consider the following properties. 1. Agreement. For every input vector and every realization of the parties’ and adversary’s randomness, no two forever-correct parties decide different values. 2. Validity. For every input vector and every realization of the parties’ and adversary’s randomness, if all forever-correct parties have input b, then every forever-correct party that decides outputs b. 3. Termination. For an input vector x, let TΠ,A,x := inf {r : every forever-correct party has decided and halted by the end of round r} , with inf ∅ = ∞. Protocol Π satisfies termination against A if, for every input vector x, P[TΠ,A,x < ∞] = 1, where the probability is over the parties’ private randomness and any randomness used by A. We say that Π is secure against A if it satisfies agreement, validity, and termination against A. We say that Π is t-secure if it is secure against every t-bounded adversary.
Synchronous rounds vs. turns A synchronous communication round r has the following semantics. (i) Each party i that is still correct first processes all messages from round r − 1. Then, depending only on its local state and round-r local coin flips, it prepares its outgoing message vector Mi,r = (Mi,r→1 , . . . , Mi,r→n ). Here, Mi,r→j denotes the message that party i sends to party j in round r. Any explicit public action, such as OUT(v) or DECIDE(v), is included as a tagged component of this message vector. All honest round-r message vectors are prepared before any round-r message is delivered or processed. (ii) The full-information rushing adversary observes the prepared message vectors. It may also observe the parties’ current local states and coin flips, up to and including round r. It may then corrupt additional parties and, for every corrupt party, completely control and determine its outgoing message vector for round r. The resulting vector is called that party’s outgoing message vector for round r. 4
(iii) At the end of the round, all message vectors prepared by both correct and corrupt parties are delivered simultaneously. They are received by their respective recipients only at the beginning of round r + 1. At times, for the analysis only, we reveal the already-prepared round-r message vectors sequentially, in a fixed public order ≺s , as turns. Processing the vector of sender iℓ is the analytical turn (r, ℓ). At this turn, the adversary examines Miℓ ,r and decides whether to corrupt iℓ . No party receives a message or changes state between analytical turns; all message vectors are delivered simultaneously after the final turn of the round. More formally, write the sender order as i1 ≺s · · · ≺s in , and let Gr−1 be the transcript at the boundary preceding round r. Put Hr,0 = Gr−1 . Turn (r, ℓ) fixes the message vector of party iℓ for round r, following the turn description above, and appends it to Hr,ℓ−1 , thereby producing Hr,ℓ . Only after Hr,n has been fixed are its recipient components delivered and the next round-boundary transcript Gr formed. For 0 < ℓ < n, Hr,ℓ is an adversarial bookkeeping prefix, not a reachable distributed configuration. Accordingly, round complexity always counts synchronous communication rounds, never turns. Through round R, the labeled process below has nR turns, but the slow event it forces is still the event that some correct party has not decided by the end of round R. Theorem 2.1 (Main theorem). Let 1 ≤ t < n/3. Let Π be a randomized binary BA protocol secure against any t-bounded full-information, strongly adaptive, rushing adversary A. Then there exist an input vector x ∈ {0, 1}n , a t-bounded adversary A, and universal constants c1 , c2 , c3 > 0 such that "
#
t2 P TΠ,A,x ≥ c1 − c2 ≥ c3 . n log(n + 1) Consequently, t2 sup E[TΠ,A,x ] = Ω n log(n + 1) A,x
! e 2 /n). = Ω(t
Remark 2.2. For simplicity and clarity of exposition, we prove the lower bound for Las Vegas protocols, i.e., protocols that always achieve validity and agreement and terminate with probability one. Our proof can easily be generalized to protocols achieving agreement with probability 1 − ϵ by incorporating the non-agreement event into the event constructed in Section 7. In the theorem above, this would translate to the probability of not terminating by the required bound being lower-bounded by c3 − ϵ.
3
Proof overview
Ben-Or & Bar-Joseph. The lower bound of Bar-Joseph and Ben-Or [BB98] follows a round-byround valency argument. Every configuration is classified as either 0-valent, 1-valent, bivalent, or null-valent, depending on the probability of the crash adversary being able to force the outcome to 0, 1, both, or neither. Bivalent configurations can be handled with standard tools to create a bivalent configuration for the next round with at most a single crash fault. The main difficulty lies with nullvalent configurations, from which the adversary cannot make either decision value overwhelmingly likely. After the parties generate their randomness for the next round, Bar-Joseph and Ben-Or encode the resulting valency of the next configuration as the outcome of a one-round coin-flipping 5
game. Their concentration argument biases this game in the required √ direction to maintain the null-valency of the configuration with high probability by crashing O( n log n) additional parties. In this round-by-round treatment, a given configuration in some round is treated as falling into one of the four valency classes in a black-box manner, disregarding the adversary’s behavior in previous rounds. Consequently, the one-round concentration argument must be invoked afresh in √ every round, and the adversary pays O( n log n) new crashes per round. As they show, this loss is essentially tight for crash adversaries. The global approach. Nevertheless, the crash-schedule argument underlying the error-probability lower bound of Chor, Merritt, and Shmoys [CMS89] hints at additional global structure. For every fixed realization of the parties’ randomness, which induces a deterministic protocol, the standard valency approach shows that an R-round execution can be forced not to terminate by crashing at most R parties, at most one in each round. It is here that Chor, Merritt, and Shmoys make a simple yet powerful observation: The number of distinct adversaries crashing at most one party in each round is not too large. Namely, it is bounded by nO(R) . Averaging over these adversaries and the protocol randomness produces one specific such adversary under which the randomized protocol remains unfinished through round R with probability p ≥ n−O(R) . This event may be rare and hence does not by itself yield an expected-round lower bound, but its rarity is controlled: log(1/p) = O(R log n). We have therefore reduced the problem to forcing a single event of probability p ≥ n−O(R) over the product probability space of the parties’ private randomness. This is precisely where the concentration-of-measure approach of Etesami, Mahloujifar, and Mahmoody [EMM20] and its many-turn generalization by Haitner and Karidi-Heller [HK26] become relevant. Their perspective suggests that Byzantine corruptions can replace the round-by-round valency attack with a single global attack that gradually steers the execution toward the desired slow event. In their paper, Haitner and Karidi-Heller employed this approach to prove that no coin-flipping protocol can remain √ unbiasable amidst more than O( n) Byzantine corruptions against a full-information, adaptive adversary. We adapt these tools to randomized BA protocols. Let E be any event whose membership is determined by the transcript through some globally known finite round, and suppose that E has probability p > 0 over the local randomness of the parties. We prove that a full-information, adaptive, rushing adversary can make E occur with probability one while corrupting O
q
n log(1/p)
distinct parties in expectation. Truncating this attack gives a worst-case corruption budget at the cost of reducing its success probability to a constant. With these ideas in mind, the proof of our main theorem proceeds in three steps. Step 1: Normalization. We first run a constant-round termination synchronizer alongside the given protocol Π. A party that outputs v in Π explicitly announces READY(v), and the synchronizer 6
uses this announcement and COMMIT messages before performing a public DECIDE(v) action. Let b denote the resulting protocol. For a universal constant d, the synchronizer has two properties. Π First, if every forever-correct party decides in Π by round r, then every forever-correct party decides b by round r + d. Second, in an execution containing only the crashes of a fixed schedule S, once in Π b every forever-correct party decides in Π b within d rounds. The one forever-correct party decides in Π, b first property allows us to project a round lower bound for Π back to Π, with only a constant loss. The second property makes the slow event constructed in the next step robust to the additional corruptions introduced in Step 3. See Section 6 for more details. Step 2: A rare robust slow event. Fix a horizon R and sample one complete realization of each b into a deterministic consensus party’s private randomness. Fixing all of this randomness turns Π protocol under every counterfactual input and crash schedule. For every fixed randomness vector ρ, the crash-schedule valency argument of [DS83] supplies an input Ik = (1k , 0n−k ) and a crash schedule S involving at most R parties under which not all correct parties decide by b allows us to deduce that no party round R. Applying the valency argument to the normalized Π b by round R − d. has decided in Π There are at most R
(n + 1)|ΣR | ≤ (n + 1) 1 + n(n + 1)
= exp(O((R + 1) log n))
possible pairs (k, S). Averaging over the protocol randomness therefore gives one fixed pair (k ⋆ , S ⋆ ), chosen independently of the realized randomness, for which the robust slow event E=
n
no non-crashed party has decided by the end of round R − d
has probability p = P[E] ≥
o
1 = n−O(R) . (n + 1)|ΣR |
See Section 7 for more details. Step 3: Forcing the slow event. We construct a forcing attack for finite transcript processes: an event of probability p > 0 can be forced with probability one using an expected O
q
n log(1/p)
distinct party corruptions. All turns of one party carry the same label, so corrupting that label once permits the adversary to control the party in every later round without paying again. The precise budgeted lemma says that, for universal constants a0 , A > 0, if √ L := log(1/p) ≤ a20 n and 4A nL ≤ B, then an attack using at most B additional corruptions on every execution forces the event with probability at least 3/4. 7
For the event from Step 2, L = O((R + 1) log n). We choose t2 R=Θ n log(n + 1)
!
with a sufficiently small hidden constant and invoke the lemma with additional budget B = t − R. Its two hypotheses then hold, while the base crash schedule uses at most R faults. Hence, the total fault set has size at most t on every execution, and the robust slow event occurs with probability at b through round R − d. least 3/4. On that event, some forever-correct party remains undecided in Π The projection from Step 1 implies that some forever-correct party remains undecided in Π through round R − O(1), proving the claimed expected-round lower bound. The remaining bounded-R regime follows from the elementary fact that, on a suitable mixed input, some correct party cannot decide before communication. See Section 5 for more details.
4
Labelled full-information processes
This section serves two purposes: First, it formally defines the notion of a labeled transcript process, the mathematical structure on top of which we then prove our forcing lemma. It then shows how any adversary in that setting can be implemented by a full-information, adaptive, rushing adversary in a synchronous protocol.
4.1
Baseline transcript processes
Definition 4.1 (Finite-horizon labelled transcript process). A finite-horizon labelled transcript process consists of a rooted prefix space H of finite depth, a set of terminal prefixes Hterm , and, for every nonterminal prefix h ∈ H: (i) a persistent label λ(h) ∈ [n] identifying the party whose turn occurs at h; (ii) a countable outcome space Xh ; and (iii) a conditional probability kernel Ph on Xh . If M ∼ Ph , the next transcript prefix is hM . The kernels induce a baseline probability distribution P on terminal transcripts. A transcript event is a subset E ⊆ Hterm . A transcript prefix records only the protocol actions and message vectors that are released in the simulated execution. It does not record a pending message vector that the adversary suppresses, the adversary’s private coins or marks, or the physical fact that a label has already been corrupted. These variables may be present in the adversary’s private view but are not part of the filtration defining Ph . The label map may depend on the prefix, although the synchronous application uses the fixed public sender order ≺s within every physical round. The number of turns may be much larger than n. What persists is the label: turns (r, ℓ) and (r′ , ℓ) both carry the persistent label iℓ . These turns serialize the adversary’s treatment of already-prepared message vectors; they do not serialize the honest parties’ local computation. For a horizon of R physical rounds, deterministic all-⊥ turns are included for parties that have already crashed, so the process has exactly nR analytical turns. The deterministic delivery and state transition after turn (r, n) are part of the closure that forms Gr and incur no additional turn or corruption charge. 8
Definition 4.2 (Strong label-tampering attack). A strong label-tampering attack maintains a permanent corrupted-label set C ⊆ [n], initially empty. At a prefix h with current label i = λ(h): f ∼ Ph is sampled and revealed to the attack. The attack either / C, a pending outcome M (i) If i ∈ f, or adds i to C and replaces it by an outcome sampled from an arbitrary attack releases M kernel supported on Supp(Ph ).
(ii) If i ∈ C, the attack directly samples the outcome from an arbitrary attack kernel supported on Supp(Ph ). The cost of the attack is |C|, the number of distinct corrupted labels, not the number of modified turns. Restricting replacement outcomes to Supp(Ph ) only weakens the adversary. It is analytically crucial(!) because every attacked prefix remains in the support of the baseline distribution and every conditional probability below remains well-defined. The forcing attack will use only such outcomes.
4.2
From a distributed execution to a labelled process
Fix a public recipient order j1 ≺r · · · ≺r jn . A crash schedule S assigns each party i a crash round τi ∈ N ∪ {∞} and, if τi < ∞, a cutoff ci ∈ {0, . . . , n}. Its finite crash rounds are distinct. Let F (S) = {i : τi < ∞} and define ( ΓSi,r (m) j = k
mjk , ⊥,
r < τi , or r = τi and k ≤ ci , otherwise.
(1)
Thus, in its crash round, i prepares its honest message vector before the cutoff is applied, and is silent thereafter. Fix a protocol Π, an input vector x, a horizon R, and a deterministic crash schedule S whose crashes occur by round R. Let ρi ∼ µi be the mutually independent private randomness of party i. For a supported round-boundary transcript g, the honest round-r message vector of a party with r ≤ τi is a deterministic function Mi,r (g|i , ρi ) of its local history and private randomness. Put (
Yi,r =
ΓSi,r Mi,r (Gr−1 |i , ρi ) , r ≤ τi , (⊥, . . . , ⊥), r > τi .
Using the analytical prefixes defined above, for h = Hr,ℓ−1 set λ(h) = iℓ ,
Ph (m) = P[Yiℓ ,r = m | Hr,ℓ−1 = h].
(2)
The label is the physical party identity: it recurs in every round with a kernel determined by the current prefix, and is charged only once if corrupted. Lemma 4.3 (Exact protocol–process correspondence). The kernels in (2), followed after every n turns by the deterministic round closure, generate exactly the execution of Π on (x, S) through round R. Moreover, every support-preserving strong label-tampering attack T on this process is implementable by a full-information, strongly adaptive, rushing Byzantine adversary AT . Under a coupling, their released transcripts agree after every analytical turn, and the final faulty-party set is F (S) ∪ C, where C is the final corrupted-label set of T . 9
Proof. Fix a supported analytical prefix h = (g, yi1 ,r , . . . , yiℓ−1 ,r ). For each party i, let Ai (h) be the set of realizations of ρi consistent with the actions of i recorded in h. Since h fixes every delivered local history, {Hr,ℓ−1 = h} =
n \
{ρi ∈ Ai (h)}.
i=1
Taking ℓ = 1, independence of the parties’ private randomness shows that their randomness remains independent conditional on Gr−1 = g. Since all round-r vectors are prepared from g before the first analytical turn and each sender occurs only once in the round, these vectors are conditionally independent. Hence Ph (m) = P[Yiℓ ,r = m | Gr−1 = g]. (3) Sequentially exposing these vectors and then delivering them simultaneously therefore reproduces the execution round by round. We now implement T . In every physical round, AT lets every party that has not previously been corrupted prepare its honest message vector. It then simulates the n turns of T in sender order, before any vector is delivered, maintaining the same released prefix h. Although it sees all pending vectors, it gives T only the vector of the sender currently being processed. Consider the turn of sender i, and let Cu be the current corrupted-label set. If i ∈ / Cu and e = ΓS e e r ≤ τi , form the candidate m (M ); if r > τ , let m be the all-⊥ vector. Give m to T . If it is i,r i i,r released, use it as i’s physical message vector. Otherwise T adds i to its corrupted set; corrupt i e and use the supported replacement sampled by T . physically unless it is already faulty, discard m, If i ∈ Cu before the turn, use directly the outcome sampled from T ’s attack kernel. If r = τi and i is not already faulty, the scheduled physical corruption is made after the honest vector is prepared and before the chosen vector is released. Support preservation ensures that every vector used in round τi obeys the scheduled cutoff and that every later vector is all-⊥. e has distribution Ph . Inductively, conditional on the It remains to verify that each candidate m common prefix and the private history of T , the private randomness of parties that are neither in Cu nor previously crashed remains independent with its baseline conditional distribution. A released candidate is recorded in the common prefix; a suppressed candidate belongs to a sender immediately added to Cu ; and the simulation does not use an unprocessed sender’s pending vector. e ∼ Ph at the next turn. Thus the invariant is preserved, and (3) gives m After all n turns, the same vectors are delivered simultaneously in both executions, so the induction continues to the next round. The transcripts therefore agree turn by turn. The only physical corruptions are those in F (S) ∪ C, with overlap counted once, and every replacement occurs after preparation and before delivery. Hence AT is a legal full-information, adaptive, rushing adversary.
5
Label forcing lemma
We now prove the probabilistic ingredient for the process of Definition 4.1. Lemma 5.1 (Budgeted label-aware forcing). There exist absolute constants a0 ∈ (0, 1) and A ≥ 1 such that the following holds. Let P be the distribution over labeled finite transcripts, possibly in the presence of a fixed base adversary with fault set F ⊆ [n], and let E be a transcript event with p = P (E) > 0,
L = log(1/p). 10
Let B be an integer satisfying 1 ≤ B ≤ n − |F |. Assume that
and
L ≤ a20 n
(4)
√ 4A nL ≤ B.
(5)
Then there is a label-tampering attack with an internally selected label set Cb whose additional corrupted-label set C := Cb \ F ⊆ [n] \ F has size at most B on every execution and satisfies 3 P[E] ≥ . 4 In particular, the total faulty set is F ∪ C and satisfies |F ∪ C| ≤ |F | + B. Proof. We commence the proof by defining useful terms and setting up several constants. For a supported transcript prefix h, define q(h) = P (E | h). For the next baseline conditional kernel Ph , put rh (m) = As long as q(h) > 0,
q(hm) . q(h)
Em∼Ph rh (m) = 1.
(6)
Discarded pending samples, corruption status, and the attack’s private marks are not included in h. If p = 1, the lemma follows from the passive attack, which adds no corrupted label and follows the baseline kernel at every turn. Hence assume p < 1, and set q a = L/n > 0. Sanitizing choice. For every supported prefix h with q(h) > 0, averaging in (6) and countability of Supp(Ph ) give an outcome m0 (h) ∈ Supp(Ph ) such that rh (m0 (h)) ≥ 1. We call m0 (h) the sanitizing choice at h. Large turn choice. For every supported prefix h with q(h) > 0 satisfying sup
rh (m) ≥ e2a ,
m∈Supp(Ph )
choose a supported m+ (h) with rh (m+ (h)) ≥ ea . These choices exist by the definition of the supremum. We refer to m+ (h) as the large turn choice of h. Fix absolute constants η ∈ (0, 1/2] sufficiently small and K0 > 0 sufficiently large; their precise choices will be specified in the analysis. Having fixed η and K0 , choose 0 < a0 ≤ min
11
1 η , 3 4K0
.
Consequently, whenever a ≤ a0 (which holds due to (4)), K0 a 1 ≤ , η 4
1 − e−a ≥
a . 2
(7)
Whenever a ≤ a0 , for every b ∈ [0, 1] we also have a a log 1 + b ≥ b. 2 4
(8)
This follows from log(1 + x) ≥ x/2 for 0 ≤ x ≤ 1. Moreover, whenever a ≤ a0 , every random variable X supported on [−a, 2a] satisfies log EeX − EX ≤ 2 Var(X).
(9)
Indeed, for Y = X − EX we have |Y | ≤ 3a ≤ 1, and hence eY ≤ 1 + Y + 2e Y 2 . Taking expectations and using log(1 + x) ≤ x proves (9). By (4), a ≤ a0 . Set K0 a . c0 = η By (7), c0 ≤ 1/4. Definition of the forcing attack.
Let U := max{|h| : h ∈ H}
be the depth of the finite prefix space. The attack uses chunks. A chunk is a consecutive block in one label’s subsequence of ordinary turns; turns of other labels may be interleaved globally. Each label may have many chunks, and each chunk has a binary mark. We now specify how chunks are opened, closed, and marked. For every label i and k ∈ [U ], privately sample independent marks Zi,k ∼ Bernoulli(c0 ). The attack does not inspect Zi,k before the k-th chunk of label i is opened. Chunks are created online and contain only non-large turns of their label. In the beginning of the attack, i.e., in the first turn when h = ∅, all labels have no active chunks. Given a turn with supported prefix h and label i, the attack proceeds according to one of the following two cases. 1. If the displayed supremum at this turn is at least e2a , i.e. supm∈Supp(Ph ) rh (m) ≥ e2a , we refer to the turn as large. If i is not yet corrupt, the attack observes the pending Ph -sample required by Definition 4.2, corrupts i, and discards that sample. It then outputs m+ (h). Note that since m+ (h) ∈ Supp(Ph ), this is a valid and well-defined adversary. A large turn does not create, advance, or close a chunk. 2. Otherwise, the turn isn’t large. We call such a turn ordinary. Before defining the attack in this case, we introduce two important distributions. Consider the following sanitization map m0 (h), m,
(
ϕh (m) =
12
rh (m) ≤ e−a , rh (m) > e−a ,
and now let Sh be the distribution of ϕh (M ) for M ∼ Ph . For m ∈ Supp(Sh ) put Xh (m) = log rh (m), Observe that
wh = VarSh (Xh ).
µh = ESh Xh , −a ≤ Xh ≤ 2a.
(10)
Set α = η/(3a) and define Sh (m) 1 + α(Xh (m) − µh ) , 0,
(
Sh1 (m) =
m ∈ Supp(Sh ), m∈ / Supp(Sh ).
(11)
Since ESh (Xh − µh ) = 0 and |α(Xh − µh )| ≤ η < 1, Sh1 is a probability distribution with the same support as Sh . We now describe the attack for ordinary turns. If i has no active chunk, its next chunk is opened with accumulated variance W = 0 and the next unused mark is Zi,k . The current ordinary turn belongs to that chunk. Thus Zi,k is the mark of the current active chunk of label i. The behavior of the adversary depends on whether Zi,k = 1 (the chunk is marked) or Zi,k = 0 (the chunk is unmarked): f ∼ Ph (a) If the chunk is marked, wh > 0, and i is uncorrupted, the pending outcome M f, and outputs an is first sampled and revealed; the attack then corrupts i, discards M 1 independent sample from Sh . If the chunk is marked, wh > 0, and i is already corrupt, the attack samples directly from Sh1 . (b) Otherwise, i.e., if either Zi,k = 0, or wh = 0, the adversary uses Sh : if i is uncorrupted, it applies ϕh to the pending Ph -sample, corrupting i only if the sample lies in the lower tail and ϕ has it replaced with the sanitized choice; if i is already corrupt, it samples directly from Sh .
After an ordinary turn, the adversary adds wh to W , the accumulated variance of the current chunk of i. A chunk closes the first time that W ≥ a2 . The next ordinary turn of i then opens the next chunk, with mark Zi,k+1 . Corruption never resets the chunk bookkeeping. In particular, a lower-tail turn contributes wh and may close its chunk normally. Suppressed pending samples are never used later. Once a label is corrupt, later turns still follow the same large/Sh /Sh1 case distinction. Every released outcome lies in Supp(Ph ) and has positive rh : on a large turn this follows from the choice of m+ ; under Sh from the definition of ϕh ; under Sh1 from Supp(Sh1 ) = Supp(Sh ). Hence, inductively, q remains positive and every later kernel is defined. This completes the definition of the attack. Analysis and accounting. Let Cb ⋆ be the final internally selected-label set of the untruncated attack. Let CG , CO , and CM count its new label corruptions, respectively, on large turns, by lower-tail replacement on ordinary turns using Sh , and on ordinary turns using Sh1 . These cases are disjoint and exhaust all new corruptions, so pathwise |Cb ⋆ | = CG + CO + CM . We bound the expectation of this quantity before truncating the attack. 13
(12)
Large turns and the potential.
Use the potential Φ(h) := log q(h).
Releasing m changes Φ by log rh (m); its conditional expected change under some distribution is the drift of the distribution at h. The invariant q(h) > 0 and the terminal identity q = 1E imply that the attack forces E. The potential starts at −L and ends at 0, so its net increment is Φ(hfinal ) − Φ(∅) = 0 − log p = L. Every new corruption counted by CG releases an outcome with rh (m) ≥ ea , and hence Φ(hm) − Φ(h) = log rh (m) ≥ a. Large turns therefore contribute at least aCG to the total increment. This does not yet bound CG , because ordinary turns may decrease Φ. Marked-chunk corruptions reduce to total variance. Let O be the random set of ordinary turns. Let X V := wHs , s∈O
be the total variance, and let Nch be the number of chunks created. By (10),
wh = VarSh (Xh ) ≤ ESh Xh −
a 2
2
≤
9a2 . 4
A completed chunk therefore has total variance 9 a2 ≤ W < a2 + a2 < 4a2 , 4
(13)
while an unfinished chunk has W < a2 . Consequently, pathwise, Nch ≤ n +
V . a2
(14)
The mark Zi,k is sampled independently, and the attack neither inspects nor uses it before the kth chunk of label i is created. Thus chunk creation is independent of its mark. A marked chunk causes at most one new corruption counted by CM . Hence K0 a EV ECM ≤ c0 ENch ≤ n+ 2 η a
It remains to control CO and V together.
14
.
(15)
Ordinary lower-tail corruptions and variance. Let Hs be the released prefix before turn s. Put bh := Ph [rh (M ) ≤ e−a ]. At a turn using Sh with an uncorrupted label, bh is the conditional probability of a new corruption counted by CO . Hence " # X
ECO ≤ E
(16)
bHs .
s∈O
Replacing the lower tail by an outcome of ratio at least one gives a ESh eXh ≥ 1 + (1 − e−a )bh ≥ 1 + bh . 2 Combining (17), (8), and (9) yields µh ≥ Moreover, by (11),
a bh − 2wh . 4
(17)
(18)
ES 1 Xh = µh + αwh .
(19)
h
Fix s ∈ O, and let c be its chunk. Condition on the creation prefix of c and on all other chunk marks; denote this information by Gc , and put πs := P[Zc = 1 | Gc , Hs ]. 1 . Therefore its drift δ satisfies The conditional next-outcome distribution is (1 − πs )SHs + πs SH s s
δs = µHs + πs αwHs ≥
a bH + (πs α − 2)wHs . 4 s
(20)
Let DO be the total change in Φ over ordinary turns. By (16), (20), and the tower property, "
#
X a (πs α − 2)wHs . EDO ≥ ECO + E 4 s∈O
(21)
it remains to prove that for some absolute constants c2 , C3 > 0: #
"
E
X
(πs α − 2)wHs ≥ c2 EV − C3 na2 .
(22)
s∈O
Finishing the proof assuming (22). Let DG be the signed change in Φ over large turns. Every large turn that creates a new corruption increases Φ by at least a, so DG ≥ aCG . Although Φ need not be monotone, its signed increments telescope: DO + DG = Φ(Hfinal ) − Φ(H0 ) = L. Consequently, once (22) is proved, (21) gives L = EDO + EDG ≥
a ECO + aECG + c2 EV − C3 na2 . 4 15
Since na2 = L, Therefore Using (15),
a ECO + aECG + c2 EV ≤ (1 + C3 )L. 4 E(CO + CG ) = O(L/a), EV K0 a n+ 2 ECM ≤ η a
EV = O(L).
(23)
= O(an + L/a) = O(L/a),
where the last equality uses na2 = L. Hence ECG = O(L/a), and therefore
ECO = O(L/a),
ECM = O(L/a),
√ E|Cb ⋆ | = E(CG + CO + CM ) = O(L/a) = O( nL).
Claim 5.2. Inequality (22) holds for some absolute constants c2 , C3 > 0. Proof. Fix a potential chunk c = (i, k) and condition on a creation prefix of c and every mark except Zc ; denote this information by Gc . The mark Zc remains Bernoulli(c0 ) under this conditioning. Let P0 and P1 be the distributions of the released continuation transcript conditional on Zc = 0 and Zc = 1, stopped when c closes or the transcript horizon is reached and absorbed thereafter. At turns of other labels and at large turns, the two conditional kernels coincide. At an ordinary turn of c, they are Sh and Sh1 . For m ∈ Supp(Sh ), let uh (m) := α(Xh (m) − µh ). Then |uh | ≤ η, ESh uh = 0, and ESh u2h = α2 wh . Since Sh1 (m) = Sh (m)(1 + uh (m)), the elementary bounds for log(1 + u) give D(Sh1 ∥Sh ) ≤ Cα2 wh . By the chain rule for relative entropy and (13), D(P1 ∥P0 ) ≤ Cα2 (4a2 ) ≤ Cη 2 . Let Λs :=
(24)
dP1≤s dP0≤s
be the likelihood ratio of the released prefix before turn s. Let Ac be the event that Λs < 1/2 at some such prefix while c is active. Let σc be the time at which c closes or the transcript horizon D is reached. Let τc be the first such prefix s ≤ σc , setting τc = σc if no such prefix exists. Then 1 P1 (Ac ) = EP0 [Λτc 1Ac ] ≤ P0 (Ac ). 2 Consequently, by Pinsker’s inequality and (24), 1 P0 (Ac ) ≤ P0 (Ac ) − P1 (Ac ) ≤ ∥P0 − P1 ∥TV ≤ Cη. 2 16
Since the actual conditional distribution is (1 − c0 )P0 + c0 P1 , it follows that P[Ac | Gc ] = (1 − c0 )P0 (Ac ) + c0 P1 (Ac ) ≤ P0 (Ac ) ≤ Cη.
(25)
Before Ac occurs, Bayes’ rule gives πs =
c0 Λs c0 ≥ . 1 − c0 + c0 Λs 3
(26)
Call a created chunk bad when Ac occurs, and let Vbad be the total variance of all bad chunks. The estimate (25) is uniform over every value of Gc for which c is created. Averaging over Gc , using that every chunk has variance at most 4a2 , and summing over potential chunks gives EVbad ≤ Cηa2 ENch ≤ Cη(na2 + EV ),
(27)
where the last inequality uses (14). Treating the entire variance of every bad chunk pessimistically, (26) and αc0 /3 = K0 /9 imply pathwise X K0 K0 −2 V − Vbad . (πs α − 2)wHs ≥ 9 9 s∈O Taking expectations and using (27) yields "
E
# X
(πs α − 2)wHs ≥
s∈O
K0 − 2 − CηK0 EV − CηK0 na2 . 9
Choose η so that Cη ≤ 1/18, and then choose K0 so that K0 /18 − 2 > 0. Setting c2 :=
K0 − 2, 18
C3 := CηK0
proves (22). Truncating the attack. Claim 5.2 proves the only estimate assumed in the preceding accounting. Hence √ E|Cb ⋆ | = O( nL). Fix an absolute constant A ≥ 1, accounting for all constant choices in the analysis, such that √ (28) E|Cb ⋆ | ≤ A nL. Put C ⋆ = Cb ⋆ \ F . By (5),
√ E|C ⋆ | ≤ A nL ≤ B/4.
Couple the forcing attack to an attack that follows it until it would select the (B + 1)st distinct label outside F . From that turn on, it corrupts no new labels. On all labels from that point, both corrupted and uncorrupted, it allows the sample Ph to be released without issue. Thus it is a valid online strong label-tampering attack and selects an additional set C ⊆ [n] \ F with |C| ≤ B on every execution; it introduces no faulty label outside F ∪ C. Note that the truncated and untruncated attacks agree whenever |C ⋆ | ≤ B. Since the untruncated attack forces E surely, Markov’s inequality gives E|C ⋆ | 3 ≥ . B 4 The total faulty set is F ∪ C and has size at most |F | + B. P[E] ≥ P[|C ⋆ | ≤ B] ≥ 1 −
17
6
Termination synchronizer
An arbitrary protocol Π can have significant gaps between the rounds in which forever-correct parties decide and halt. For our proof, it is important that these gaps be small. Specifically, we show that, with a simple constant-round deterministic wrapper, any protocol Π can be turned into b in which correct parties decide and halt at most O(1) rounds apart. a protocol Π The wrapper. Normalize Π so that a local halt in Π is followed by an explicit READY(v) notification for the decided value v to every party in the halting party’s next outgoing message vector. This adds one round. Run the following tagged deterministic wrapper alongside Π even before a party produces a READY message and halts in Π; wrapper messages are ignored by the state-transition function of Π. In each round, a party’s genuine Π messages and its wrapper messages form one combined outgoing message vector. Conditional on the transcript history and the genuine Π component, the b as follows: wrapper component is deterministic. Construct Π (i) After receiving n − t READY(v) messages from distinct parties, send COMMIT(v). (ii) After receiving t + 1 COMMIT(v) messages from distinct parties, relay COMMIT(v) if it has not already been sent. (iii) After receiving n − t COMMIT(v) messages from distinct parties, decide v and halt. Claim 6.1. Let Π be a t-secure BA protocol. Then there exists a constant d > 0 such that the b following properties hold for Π. b is a t-secure BA protocol. 1. Π
2. If every forever-correct party decides in Π by round r, then every forever-correct party decides b by round r + d. and halts in Π b by round r, then every forever-correct party 3. If any forever-correct party decides and halts in Π b by round r + d. decides and halts in Π b inherits the security of Π against t-bounded Proof. As the wrapper is entirely deterministic, Π full-information adaptive adversaries. Termination and validity are clear. For agreement, first note that if any forever-correct party sends a COMMIT(v) message for a value v, then there exists a forever-correct party that received n − t READY(v) messages, e.g., the first forever-correct party to send a COMMIT(v) message. Thus, since each forever correct party sends READY for at most one value, forever-correct parties as a whole send COMMIT for at most one value by quorum intersection, as t < n3 . Note that a party deciding a value v implies that at least n − 2t ≥ t + 1 forever-correct parties sent a COMMIT(v) message. This means that all forever-correct parties receive t + 1 COMMIT messages for v by the next round, relay them, and decide v in the following round.
It will be useful for a later part of the proof to fix the following constant: R0 = 4d + 4.
18
(29)
7
A heavy crash schedule
In this section, we prove a simplified variant of the result of [CMS89]. Namely, for every R and every randomized BA protocol Π, there exist an R-round crash schedule S and an input vector I 1 such that, with probability at least nO(R) over the randomness of Π, not all correct parties decide by round R under (S, I). We achieve this result in two steps. • First, we show that every deterministic protocol has round complexity at least R under some R-round crash schedule. • We bound the total number of R-round crash schedules by nO(R) . From there, averaging over all fixings of the randomness of Π concludes the proof. Throughout this section, we fix some order of the [n] parties, e.g., the natural order on [n]. Let ΣR be the crash schedules defined in Section 4 for which every finite crash round lies in {1, . . . , R}. In each round, the schedule chooses either no crash or a pair (j, c) consisting of the newly crashed party and its recipient cutoff. Each schedule is fixed offline and does not react to the random message vectors. Therefore, R |ΣR | ≤ 1 + n(n + 1) . (30) Definition 7.1 (Configuration). For a deterministic protocol Π, a crash schedule S, an input vector I, and a round r, we define the configuration at round r to be the tuple of internal states of all non-crashed parties at the beginning of round r in the execution induced by (Π, S, I). When the schedule and input vector are clear from context, we denote the configuration at round r by Cr . Definition 7.2 (Decision value). For a deterministic BA protocol Π secure against t crashes, an input vector I, and an R-round crash schedule S with R < t, we denote by valS,I (Π) the eventual decision value of Π under (S, I). Definition 7.3 (Valency). Let Π be a deterministic BA protocol secure against t crash faults, and let C be a round-r configuration reachable by an (r − 1)-round schedule S ′ and input vector I. We say that C is b-univalent if there exists b ∈ {0, 1} such that every t-round schedule S that extends (S ′ , I) has valS,I (Π) = b. Otherwise, we say that C is bivalent. Observation. If there exists a bivalent round-r configuration, then there exists an r-round crash schedule such that not all correct parties decide by the end of round r − 1. Lemma 7.4 (Crash-schedule consensus). Let Π be a deterministic binary BA protocol secure against R + 1 < n crashes. Then there exist an input vector Ik = (1k , 0n−k ) for some k ∈ {0, . . . , n} and a schedule S ∈ ΣR under which not all correct parties decide by the end of round R. Proof. We prove the lemma by induction on R, showing that there exists a bivalent round-R configuration. Assume that, for every input Ik and every schedule in ΣR , all correct parties decide by the end of round R. We start with R = 1, which requires us to show that there exists a bivalent round-1 configuration reachable with 0 crashes. Fix some order on the parties, e.g., the natural order on [n]. Consider the following n + 1 input vectors: Ik = (1, . . . , 1, 0, . . . , 0), | {z } | {z } k
n−k
19
k = 0, . . . , n.
Validity of Π implies that, under the empty crash schedule, val∅,In (Π) = 1 ̸= 0 = val∅,I0 (Π). If there exists 0 ≤ k ≤ n such that the round-1 configuration induced by Ik is bivalent, we are done. Otherwise, assume that the induced configurations are univalent for all such k. We derive a contradiction as follows. Since the configurations at the two ends disagree, there must exist 0 ≤ i ≤ n − 1 such that Ii is 0-valent and Ii+1 is 1-valent. Consider the schedule in which party i + 1 is crashed in the first round and sends no messages to any party. Since i + 1 is the only party with different inputs in Ii and Ii+1 , the resulting round-2 configurations are indistinguishable to all correct parties and thus lead to the same decision value, contradicting either the 1-valency of Ii+1 or the 0-valency of Ii . For the induction step, suppose that a bivalent configuration Ck has been reached at round k ≤ R, with a schedule crashing at most k − 1 parties. Suppose, for the sake of contradiction, that all k-crash schedules extending Ck are univalent. Let N denote the round-(k + 1) configuration in which no party crashes in round k. For every non-crashed party j in Ck and cutoff c ∈ {0, . . . , n}, let Sj,c denote the round-(k + 1) configuration in which j crashes after sending to the first c recipients. For each fixed j, consider the configurations Sj,0 , Sj,1 , . . . , Sj,n . Adjacent configurations Sj,c and Sj,c+1 differ only in the state of the unique recipient c + 1 that receives the additional message. Crashing c + 1 in round k + 1 without that party sending a message to any party renders the resulting round-(k + 2) configurations indistinguishable to all correct parties, and thus they lead to the same decision value. As such, for all c, Sj,c and Sj,c+1 have the same univalence. Moreover, Sj,n and N have an identical round-(k + 1) configuration, and so that configuration has the same valency in both executions. Thus, for every j and every c, the univalent configurations Sj,c have the same valency as N . Hence, all round-(k + 1) configurations extending Ck have the same valency, contradicting the bivalence of the current configuration Ck . Therefore, there exist a party j and a cutoff c such that Sj,c is a bivalent round-(k + 1) configuration. Note that all considered executions use at most k + 1 ≤ R + 1 crashes and are thus valid. Iterating gives a bivalent round-R + 1 configuration after crashing at most R parties. This concludes the proof. Lemma 7.5 (Heavy input–schedule pair). Let Π be a randomized binary BA protocol secure against every t-bounded adversary. Fix 1 ≤ R < t with n > R + 1. Then there exist k ∈ {0, . . . , n} and S ∈ ΣR such that "
not all parties outside F (S) decide by round R P in the execution of Π on input Ik under S
#
≥
1 . (n + 1)|ΣR |
(31)
Denote this probability by pD , where D = (k, S). Then log(1/pD ) ≤ C1 (R + 1) log(n + 1)
(32)
for an absolute constant C1 > 0. Proof. Let ρ = (ρ1 , . . . , ρn ) be the vector of the parties’ independent private randomness. For fixed ρ, the protocol Πρ is deterministic. Under our pointwise definition of perfect safety, Πρ satisfies agreement and unanimous validity for every ρ. 20
For each k ∈ {0, . . . , n} and S ∈ ΣR , let (
not all parties outside F (S) decide by round R ρ: in Πρ on input Ik under schedule S
Ek,S :=
)
.
Applying Lemma 7.4 to Πρ shows that n [
Ω⊆
[
Ek,S .
k=0 S∈ΣR
Hence, some pair D = (k, S) satisfies pD := P[Ek,S ] ≥
1 1 ≥ R . (n + 1)|ΣR | (n + 1) 1 + n(n + 1)
Taking logarithms proves the final assertion.
8
Applying the forcing lemma
b and an In this section, we complete the proof of our main theorem by applying Lemma 5.1 on Π event ED derived from the event given by Lemma 7.5, and then projecting back to the original protocol Π.
Proof of Theorem 2.1. Let a0 , A be the constants from Lemma 5.1, and let C1 be the constant in (32). Choose a universal constant c > 0 small enough that 2C1 c ≤ a20 , 9 Set
p 1 4A 2C1 c ≤ , 2 $
t2 R= c n log(n + 1)
c 1 ≤ . 3 log 2 4
(33)
%
(34)
and first consider the regime R ≥ R0 . Since t < n/3, the third condition in (33) gives R≤c
t2 c t < t≤ . n log(n + 1) 3 log 2 4
(35)
In particular, R ≤ t and n > R + 1, so the preceding section, in Lemma 7.5, supplies a pair D = (k, S) with |F (S)| ≤ R, and the following event. n
o
n
o
b by round R . GD := not all parties outside F (S) decide in Π
Consider the event b by round R − d . ED := no party outside F (S) decides in Π b (Specifically, property (3) in Claim 6.1), we have that GD ⊆ ED . Note that by the properties of Π And so Pr[ED ] ≥ Pr[GD ]. We thus proceed with Pr[ED ], and in particular denote pD := Pr[ED ]. Put L = log(1/pD ), B = t − R.
21
Because R ≥ 1, equations (32) and (34) give L ≤ 2C1 R log(n + 1) ≤ 2C1 c
t2 . n
(36)
The first condition in (33) and t < n/3 therefore imply L≤
2C1 c n ≤ a20 n. 9
Moreover, the second condition in (33), (36), and (35) imply √ p t 4A nL ≤ 4A 2C1 c t ≤ ≤ B. 2 Finally, 1 ≤ B and, since |F (S)| ≤ R and t < n, B = t − R ≤ n − |F (S)|. Thus all hypotheses of Lemma 5.1 hold for the finite labelled transcript process through round b on input I , with base crash schedule S, event ED viewed as a terminal R of the execution of Π k transcript event, and additional budget B. The lemma supplies a label-tampering attack T , and Lemma 4.3 realizes T as a full-information, strongly adaptive, rushing adversary Ab in the original synchronous execution, such that 3 PAb[ED ] ≥ , 4
|F (S) ∪ C| ≤ |F (S)| + B ≤ t
(37)
on every execution, where C ⊆ [n] \ F (S) is its additional corruption set. On ED , the fault bound in (37) and t < n ensure that there exists q∈ / F (S) ∪ C. This party is forever correct. The event ED says that no DECIDE notification from any party outside F (S), including q, is recorded by round R − d. Therefore P[TΠ b ,A,I b ≥ R − d] ≥ 3/4. k
(38)
If adversaries are formally required to be deterministic, fix the attack’s private randomness. Averaging guarantees a seed attaining at least the probability in (38), and the hard corruption bound holds for every seed. Projection to the original protocol. The wrapper messages in every outgoing message are a deterministic function of the Π transcript and are ignored by Π itself. Hence the adversary Ab b induces an adversary A against Π: It makes the same corruptions and the constructed against Π same replacements to the genuine Π components, while simulating the wrapper internally. The two coupled executions have the same genuine Π transcript and the same corrupted-party set. By property (2) given by Claim 6.1, TΠ b ,A,I b ≤ TΠ,A,Ik + d. k
22
b by round R − d. Therefore On ED , no forever correct party has finished Π
ED ⊆ {TΠ,A,Ik ≥ R − 2d} , and consequently
3 P[TΠ,A,Ik ≥ R − 2d] ≥ P[ED ] ≥ . 4 Since R ≥ R0 , we have R − 2d ≥ R/2, which gives the desired Ω(R) lower bound. The case of R < R0 is degenerate, and its proof can be found in Section A. This completes the proof of our main theorem, Theorem 2.1.
9
AI usage disclosure
The first draft of the statement and proof of the forcing lemma, Lemma 5.1, was obtained in collaboration with ChatGPT 5.6 Sol Ultra. Initially, the author fed the model the works of Ben-Or & Bar-Joseph [BB98], Haitner & Karidi-Heller [HK26], and Etesami, Mahloujifar, Mahmoody [EMM20]. The author described his wish to stray from the round-by-round valency approach of Ben-Or & Bar-Joseph, described the Chor, Merritt, Shmoys [CMS89] crash argument, and asked whether the multi-round forcing tools of Haitner & Karidi-Heller could be adapted to our setting. After thinking for about 2 hours, the model responded with a candidate proof. Significant rounds of interaction for editing, simplification and typesetting followed. The author takes full and complete responsibility for the veracity of the contents of the paper.
References [Dol+82]
Danny Dolev et al. “An Efficient Algorithm for Byzantine Agreement without Authentication”. In: Inf. Control. 52.3 (1982), pp. 257–274.
[LSP82]
Leslie Lamport, Robert Shostak, and Marshall Pease. “The Byzantine Generals Problem”. In: ACM Transactions on Programming Languages and Systems 4.3 (1982), pp. 382–401.
[Ben83]
Michael Ben-Or. “Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols (Extended Abstract)”. In: Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, 1983, pp. 27–30.
[DS83]
Danny Dolev and H. Raymond Strong. “Authenticated Algorithms for Byzantine Agreement”. In: SIAM Journal on Computing 12.4 (1983), pp. 656–666.
[Rab83]
Michael O. Rabin. “Randomized Byzantine Generals”. In: FOCS. IEEE Computer Society, 1983, pp. 403–409.
[CC85]
Benny Chor and Brian A. Coan. “A Simple and Efficient Randomized Byzantine Agreement Algorithm”. In: IEEE Transactions on Software Engineering SE-11.6 (1985), pp. 531–539.
[DR85]
Danny Dolev and Rüdiger Reischuk. “Bounds on Information Exchange for Byzantine Agreement”. In: Journal of the ACM 32.1 (1985), pp. 191–204.
[FLP85]
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. “Impossibility of Distributed Consensus with One Faulty Process”. In: Journal of the ACM 32.2 (1985), pp. 374–382. 23
[FLM86]
Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. “Easy Impossibility Proofs for Distributed Consensus Problems”. In: Distributed Computing 1.1 (1986), pp. 26–39.
[Bra87]
Gabriel Bracha. “Asynchronous Byzantine Agreement Protocols”. In: Information and Computation 75.2 (1987), pp. 130–143.
[CMS89]
Benny Chor, Michael Merritt, and David B. Shmoys. “Simple Constant-Time Consensus Protocols in Realistic Failure Models”. In: Journal of the ACM 36.3 (1989), pp. 591–614.
[BG93]
Piotr Berman and Juan A. Garay. “Randomized Distributed Agreement Revisited”. In: 23rd International Symposium on Fault-Tolerant Computing (FTCS). IEEE, 1993, pp. 412–419.
[Asp98]
James Aspnes. “Lower Bounds for Distributed Coin-Flipping and Randomized Consensus”. In: J. ACM 45.3 (1998), pp. 415–450.
[BB98]
Ziv Bar-Joseph and Michael Ben-Or. “A Tight Lower Bound for Randomized Synchronous Consensus”. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, 1998, pp. 193–199.
[CKS05]
Christian Cachin, Klaus Kursawe, and Victor Shoup. “Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography”. In: Journal of Cryptology 18.3 (2005), pp. 219–246.
[BPV06]
Michael Ben-Or, Elan Pavlov, and Vinod Vaikuntanathan. “Byzantine agreement in the full-information model in O(log n) rounds”. In: STOC. ACM, 2006, pp. 179–186.
[GPV06]
Shafi Goldwasser, Elan Pavlov, and Vinod Vaikuntanathan. “Fault-Tolerant Distributed Computing in Full-Information Networks”. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 2006, pp. 15–26.
[KK06]
Jonathan Katz and Chiu-Yuen Koo. “On Expected Constant-Round Protocols for Byzantine Agreement”. In: Advances in Cryptology — CRYPTO 2006. Vol. 4117. Lecture Notes in Computer Science. Springer, 2006, pp. 445–462.
[Gar+07]
Juan A. Garay et al. “Round Complexity of Authenticated Broadcast with a Dishonest Majority”. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2007, pp. 658–668.
[AC08]
Hagit Attiya and Keren Censor. “Tight bounds for asynchronous randomized consensus”. In: J. ACM 55.5 (2008), 20:1–20:26.
[Nak08]
Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin. org/bitcoin.pdf. 2008.
[KS11]
Valerie King and Jared Saia. “Breaking the O(n2 ) Bit Barrier: Scalable Byzantine Agreement with an Adaptive Adversary”. In: Journal of the ACM 58.4 (2011), 18:1– 18:24.
[KM13]
Dariusz R. Kowalski and Achour Mostéfaoui. “Synchronous byzantine agreement with nearly a cubic number of communication bits: synchronous byzantine agreement with nearly a cubic number of communication bits”. In: PODC. ACM, 2013, pp. 84–91.
[KS16]
Valerie King and Jared Saia. “Byzantine Agreement in Expected Polynomial Time”. In: Journal of the ACM 63.2 (2016), 13:1–13:21. 24
[KS18] [RSS18]
Valerie King and Jared Saia. Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016. 2018. e √n) Peter Robinson, Christian Scheideler, and Alexander Setzer. “Breaking the Ω( Barrier: Fast Consensus under a Late Adversary”. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 2018, pp. 173– 182.
[Abr+19]
Ittai Abraham et al. “Communication Complexity of Byzantine Agreement, Revisited”. In: PODC. ACM, 2019, pp. 317–326.
[AS20]
Ittai Abraham and Gilad Stern. “Information Theoretic HotStuff”. In: OPODIS. Vol. 184. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 11:1–11:16.
[EMM20] Omid Etesami, Saeed Mahloujifar, and Mohammad Mahmoody. “Computational Concentration of Measure: Optimal Bounds, Reductions, and More”. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2020, pp. 345–363. [MR21]
Atsuki Momose and Ling Ren. “Optimal Communication Complexity of Authenticated Byzantine Agreement”. In: 35th International Symposium on Distributed Computing (DISC). Vol. 209. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 32:1–32:16.
[HPZ22]
Shang-En Huang, Seth Pettie, and Leqi Zhu. “Byzantine Agreement in Polynomial Time with Near-Optimal Resilience”. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM, 2022, pp. 502–514.
[CP23]
Benjamin Y. Chan and Rafael Pass. “Simplex Consensus: A Simple and Fast Consensus Protocol”. In: Theory of Cryptography Conference (TCC). Vol. 14372. Lecture Notes in Computer Science. Cryptology ePrint Archive, Paper 2023/463. Springer, 2023, pp. 452– 479. √ Elette Boyle, Ran Cohen, and Aarushi Goel. “Breaking the O( n)-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party”. In: J. Cryptol. 37.1 (2024), p. 2.
[BCG24] [HPZ24]
Shang-En Huang, Seth Pettie, and Leqi Zhu. “Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection”. In: Journal of the ACM 71.2 (2024), 12:1– 12:37.
[YLW24]
Qianyu Yu, Giuliano Losa, and Xuechao Wang. “TetraBFT: Reducing Latency of Unauthenticated, Responsive BFT Consensus”. In: PODC. ACM, 2024, pp. 257–267.
[CEK25]
Daniel Collins, Yuval Efron, and Jovan Komatovic. “Juggernaut: Efficient CryptoAgnostic Byzantine Agreement”. In: Advances in Cryptology — EUROCRYPT 2025. Lecture Notes in Computer Science. Cryptology ePrint Archive, Paper 2024/1601. Springer, 2025.
[DP25]
Fabien Dufoulon and Gopal Pandurangan. “Improved Byzantine Agreement under an Adaptive Adversary”. In: Proceedings of the 2025 ACM Symposium on Principles of Distributed Computing (PODC). ACM, 2025, pp. 173–180.
[Abr+26]
Ittai Abraham et al. “Forget-IT: Optimal Good-Case Latency For Information-Theoretic BFT”. In: PODC. ACM, 2026, pp. 478–488.
25
[HK26]
Iftach Haitner and Yonatan Karidi-Heller. “A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip”. In: Journal of the ACM 73.3 (2026), 21:1–21:32.
[Yu+26]
Qianyu Yu et al. “Simple-IT: Practical Low-Latency Signature-Free BFT Consensus”. In: CoRR abs/2606.14404 (2026).
A
Main theorem Addendum
It remains to consider R < R0 . Put Q :=
t2 . n log(n + 1)
Since R = ⌊cQ⌋ < R0 , we have
R0 + 1 , c which is bounded by a universal constant. A one-round lower bound therefore suffices for the expectation. Consider a failure-free execution with two parties i ̸= j having inputs xi = 0 and xj = 1. Before receiving any message, their behavior depends only on their respective inputs and independent local randomness. Validity implies that any decision made by i at this point is 0, while any such decision made by j is 1. Perfect agreement and independence therefore imply that at least one of these parties does not decide and halt before communication, with probability one. Hence Q<
ETΠ,A,x ≥ 1 = Ω(Q). Finally, take c3 = 3/4 and c1 = c/4. In the regime R ≥ R0 , the preceding argument gives TΠ,A,x ≥ c1 Q with probability at least c3 . In the regime R < R0 , choose c2 ≥
c1 (R0 + 1) . c
Then c1 Q − c2 ≤ 0, so the claimed tail inequality is automatic.
26