Source-linked AI summary
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary
Valerie King, Jared Saia
TL;DR
Byzantine agreement for large networks has faced a practical communication barrier, including quadratic message costs. This paper presents a protocol using ˜O(√n) bits per processor against an adaptive adversary, and reports high-probability agreement in polylogarithmic time. Its conclusion is bounded by assumptions including a sufficiently large knowledgeable good-processor set in one protocol stage.
Problem
Quadratic communication costs have been cited as making Byzantine agreement infeasible for synchronizing large numbers of replicas.
Source: §1 · p. 2Method
The paper uses secret sharing of message sequences across processors, with threshold shares required to reconstruct each secret.
Source: §3.1 · p. 5Results
˜O(n^1/2) bits of communication suffice for Byzantine agreement in polylogarithmic time with high probability against an adaptive, rushing adversary controlling fewer than 1/3 − ϵ of processors.
Source: §1.2 · p. 3Takeaways & Limitations
The authors present Byzantine agreement with subquadratic total communication against an adaptive adversary, using private channels but no other cryptographic assumptions.
Source: §6 · p. 13The almost-everywhere-to-everywhere protocol assumes that at least (1/2 + ϵ)n processors are knowledgeable and can agree on a random number.
Source: §4 · p. 12
Abstract
from arXiv · showhide
We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only $\tilde{O}(\sqrt{n})$ bits, where $n$ is the total number of processors. Our algorithm succeeds with high probability against an \emph{adaptive adversary}, which can take over processors at any time during the protocol, up to the point of taking over arbitrarily close to a 1/3 fraction. We assume synchronous communication but a \emph{rushing} adversary. Moreover, our algorithm works in the presence of flooding: processors controlled by the adversary can send out any number of messages. We assume the existence of private channels between all pairs of processors but make no other cryptographic assumptions. Finally, our algorithm has latency that is polylogarithmic in $n$. To the best of our knowledge, ours is the first algorithm to solve Byzantine agreement against an adaptive adversary, while requiring $o(n^{2})$ total bits of communication.
1 Introduction
The paper targets Byzantine agreement’s communication barrier for large networks, presenting polylogarithmic-time protocols with subquadratic communication against an adaptive, rushing adversary. Its approach combines secret-shared random arrays and revised election procedures to extend agreement from almost all processors to all good processors.
1 Introduction
- The paper addresses the practical difficulty of Byzantine agreement in large networks, where quadratic message costs have been cited as infeasible and batching cannot offset them.The introduction also frames agreement as necessary for reliable computation despite malicious components.Source: §1 · p. 2
1.2 Results
- ˜O(n^1/2) bits of communication and polylogarithmic time suffice for Byzantine agreement with high probability against an adaptive, rushing adversary controlling fewer than 1/3 − ϵ of processors.The model is synchronous; channels are private, and the adversary may flood the network.Source: §1.1 · p. 2, §1.2 · p. 3
- Almost-everywhere agreement runs in O((log^(4+ϵ) n)/log log n) time with ˜O(n^(4/ϵ)) bits per processor, and supports an almost-everywhere global coin subsequence at additional cost.The added coin-subsequence cost is O(log n / log log n) time and ˜O(n^(4/ϵ)) bits per bit of s.Source: §1.2 · p. 3
- With a partly known sequence containing t independent uniform coinflips, a protocol running in O(s) time and O(log n) bit complexity makes all but C2n/log n good processors commit to one good-input vote with probability at least 1 − e^(−C1n) + 1/2^t.The sequence has length s, and its coinflip subsequence is known to 1 − O(1/log n) good processors.Source: §1.2 · p. 3
- Given agreement by n/2 + ϵn good processors and an oracle generating each global coin bit in O(1) time, the protocol makes all good processors output M with probability 1 − 1/n^c.It runs in O(s log n) time and uses ˜O(sn^1/2) bits per processor, assuming t > c log n.Source: §1.2 · p. 3
1.3 Techniques
- To resist adaptive takeovers, the protocol elects arrays of random numbers rather than processors and repeatedly secret-shares them among larger groups, delaying reconstruction until the appropriate time.The method splits arrays as they advance through a tournament.Source: §1.3 · p. 4
- The election adapts Feige’s bin selection by using Rabin’s algorithm [21] on a sparse network, with almost-everywhere global coins generated from the arrays.The earlier participant-election approach is unsuitable against an adaptive adversary because it requires agreement within a small group.Source: §1.3 · p. 4
- The paper also gives a distinct protocol that combines almost-everywhere agreement and the global coin subsequence problem to reach everywhere agreement against an adaptive adversary.The authors distinguish this technique from the earlier non-adaptive approach.Source: §1.3 · p. 4
2 Related work
Prior work established bandwidth-efficient almost-everywhere agreement for a non-adaptive adversary, while later work studied sparse-network implementations and constraints on low-message protocols. This paper’s related-work discussion distinguishes its everywhere-agreement step from those settings.
2 Related work
- The cited prior result gives polylogarithmic-time, polylogarithmic-communication almost-everywhere agreement, leader election, and universe reduction against a non-adaptive rushing adversary.Its model is synchronous and full-information.Source: §2 · p. 4
- In sparse networks, everywhere agreement is impossible when faulty processors can surround a good processor; another result requires some processor to send Ω(n^1/3) messages under a specified listening constraint.That constraint requires processors to pre-specify whom they will listen to at the start of each round.Source: §2 · p. 4
- The paper places its almost-everywhere protocol within that restrictive listening model, but not its almost-everywhere-to-everywhere protocol, whose listening decisions depend on received-message counts.The sparse-network implementation and earlier partially connected secure multiparty agreement results are also noted; the latter has Ω(n^2) message cost.Source: §2 · pp. 4–5
3 Almost everywhere protocol
The protocol organizes processors in a sampler-based tree and uses iterated secret sharing and local elections to move candidate arrays upward. Its communication and correctness mechanisms aim to keep secrets hidden along good paths and deliver them to almost all good processors.
3 Almost everywhere protocol
- Each processor creates a random-bit array and shares it with its level-1 node; local election winners advance through the tree to a small root set.At the root, the remaining arrays support almost-everywhere Byzantine agreement with a global coin.Source: §3 · p. 5
3.1 Secret sharing
- Iterated threshold sharing lets processors reshare shares while deleting originals; the paper assumes t = n/2 and says any t in [1/3, 2/3] also works.The lemma states that an adversary holding t_i shares of each i-share learns no information about the secret.Source: §3.1 · pp. 5–6
3.2.1 Samplers
- Averaging samplers define sparse connections whose subsets usually contain a bad-element fraction close to that of the full set.The paper uses (1/log n, 1/log n) samplers with degree O((s/r + 1) log^3 n).Source: §3.2.1 · p. 6
3.2.2 Network structure
- The network is a q-ary tree whose nodes and uplinks, descendant links, and within-node links are determined using samplers.Fewer than a 1/log n fraction of nodes on any level are bad, and the stated uplink and descendant-link properties bound poorly connected processors.Source: §3.2.2 · pp. 6–7
3.2.3 Communication protocols
- Communication uses sendSecretUp to share secrets toward parents, sendDown to reconstruct shares toward leaves, and sendOpen to aggregate values from linked level-1 nodes.sendSecretUp erases the sender's original secret after sharing it.Source: §3.2.3 · p. 7
3.2.4 Correctness of communications
- If a secret sent upward is learned by the adversary, its path must contain a bad node.On a good path, the adversary remains below the sharing threshold until release; afterward, at least 1 − 1/log n of good processors in the node learn the secret under the stated descendant conditions.Source: §3.2.4 · p. 8
- When enough level-1 descendants and paths are good, reconstruction returns shares down good paths so that at least 1 − 1/log n of the node's good processors learn the secret.A secret is considered released when it is first sent down from a node.Source: §3.2.4 · p. 8
3.3 Election
The election groups candidate blocks by bin choice and selects a set of indices associated with the lightest bin. Feige’s result bounds how many randomly generated candidates survive even when the adversary sets other bits after seeing their bin choices.
3.3 Election
- Each candidate block begins with a bin-choice word followed by r words used as coins for Byzantine agreement on candidates' bin choices.The election output is a set of indices, with w = 5c log^3 n.Source: §3.3 · p. 8
- The election selects r/numBins indices, padding the set if needed, after Byzantine agreement determines candidates' bin choices and the lightest bin is identified.The procedure runs agreement on bin choices in parallel and forms the selected set from candidates choosing the minimum bin.Source: §3.3 · p. 8
- With probability at least 1 − 2^−(ϵ²|S|/(3numBins)), at least (1/numBins − ϵ)|S| winners come from independently random bin choices, even if the adversary sets remaining bits afterward.The passage gives a 1 − 1/n^c probability when |S| > 2r/3 and r/numBins > 5c log^3 n.Source: §3.3 · p. 8
3.4 Main protocol for Almost Everywhere Byzantine Agreement
The main protocol runs elections across the tree, exposing bin choices and agreement coins as needed while forwarding winner shares upward. The construction also yields a mostly random global-coin subsequence, and its stated almost-everywhere protocol has polylogarithmic time and near-square-root-per-processor bit complexity.
3.4 Main protocol for Almost Everywhere Byzantine Agreement
- At each level, processors expose bin choices through sendDown and sendOpen, run agreement with coins exposed as needed, and send shares of winning blocks to the parent.The tree illustration describes bin-choice revelation, level-ℓ agreement, and upward transmission of winner shares.Source: §3.4 · p. 9, §3.6 · p. 10
3.5 Modification to output a sequence of mostly random bits
- Adding a block for the desired sequence and recovering words from the contestants at the root modifies the protocol to solve the global coin subsequence problem.The stated task is to produce a sequence of length s with 2s/3 global coinflips.Source: §3.5 · p. 9
3.6 Bit complexity and running time analysis
- The almost-everywhere Byzantine agreement protocol runs in O((log n)^(4+δ)/log log n) time and uses Õ(n^(4/δ)) bits per processor.This is the bound stated for any δ > 0.Source: §3.6 · p. 9
3.7 Proof of correctness
The correctness analysis bounds the fraction of good arrays that survive successive elections and accounts for arrays lost through bad nodes. It concludes that the root retains a mostly random sequence known to almost all good processors.
3.7 Proof of correctness
- The root sequence contains a 2/3 + ϵ − 5/log log n fraction of random words known to 1 − 1/log n of good processors.The lemma also bounds the fraction of good winning arrays at level ℓ by at least 2/3 − 7ℓ/log n.Source: §3.7 · p. 11
- Bad nodes can make elections bad by breaking paths, eliminating good arrays that pass through those elections; a bad election does not itself make additional paths bad.The passage gives level-dependent bounds on the fractions of elections affected by bad nodes.Source: §3.7 · p. 11
- The analysis bounds the total fraction of root-level elections made bad by bad nodes by less than 5ℓ*/log n = 5/log log n.This bound yields the stated root fraction of good arrays.Source: §3.7 · pp. 11–12
4 Almost Everywhere to Everywhere
The protocol extends agreement from almost all good processors to every processor using private channels, random request labels, and a shared random label. Its correctness analysis bounds overload and shows that repetition yields agreement with high probability.
4 Almost Everywhere to Everywhere
- The protocol assumes at least (1/2 + ϵ)n good processors agree on a message and can generate a random number in [1, √n].The construction also assumes private channels.Source: §4 · p. 12
- Each processor sends requests with random labels; processors respond only to requests matching the shared random label, subject to an overload limit.A processor decides the message returned most often for its most frequently returned label if it passes the stated threshold.Source: §4 · p. 12
4.1 Proof of correctness
- With probability at least 1 − 1/n^c, every processor either agrees on M or remains undecided after one loop.The proof establishes this using bounds on knowledgeable and corrupt or confused processors among each processor’s requests.Source: §4.1 · p. 12
- The shared random label limits overload: the probability that more than ϵn/4 knowledgeable processors are overloaded is below 4/(ϵ log n).Each processor has at most a 1/log n chance of being overloaded when the label is chosen randomly.Source: §4.1 · pp. 12–13
- Repeating the loop (c/3)ϵ ln n times gives probability 1 − 1/n^c that all processors agree on M and none outputs a different message.A single loop succeeds with probability 4/(ϵ log n) − 1/n^c, according to the proof.Source: §4.1 · pp. 12–13
5 Everywhere Byzantine Agreement
The protocol first reaches almost-everywhere agreement, then uses generated secret numbers to extend agreement across processors. This yields polylogarithmic latency while keeping per-processor communication at ˜O(√n) bits.
5 Everywhere Byzantine Agreement
- The protocol first reaches almost-everywhere consensus on a bit, then runs AlmostEverywhereToEverywhere using generated secret numbers.The sequence contains a subsequence of c log n uniformly and independently random numbers known to 1 − 1/log n processors.Source: §5 · p. 13
- The complete protocol uses ˜O(√n) bits per processor and has polylogarithmic time complexity.The communication cost is dominated by each execution of AlmostEverywhereToEverywhere.Source: §5 · p. 13
6 Conclusion
The paper concludes that Byzantine agreement can be solved with ˜O(√n) bits per processor. It identifies lower communication, asynchronous operation, and practical deployment as open questions.
6 Conclusion
- The algorithm solves Byzantine agreement using only ˜O(√n) bits per processor.The conclusion asks whether o(√n) bits are possible or whether Ω(√n) bits are necessary against an adaptive adversary.Source: §6 · p. 13
- Whether the approach extends to asynchronous communication or yields a practical algorithm for large real-world networks remains open.The paper also asks whether its techniques can support scalable secure multiparty computation for other functions.Source: §6 · p. 13
A.1 Proof of Lemma 5
The proof bounds running time and per-processor communication by accounting for work across protocol levels and node appearances. With a polylogarithmic parameter choice, it obtains polylogarithmic time and ˜O(n^(4/δ)) bits per processor.
A.1 Proof of Lemma 5
- The running-time bound is O(ℓ*(q(w + 1))), with each round taking O(ℓ*) time.The analysis counts q rounds in the first execution and q*w rounds in later executions.Source: §A.1 · p. 15
- In the first execution of Step 2(a) and (b), level-2 processors send down O(q^2 d_m) words, while each level-1 processor sends q^2 words.Level-1 processors reconstruct 1-shares from 2-shares and share them within the level-1 node.Source: §A.1 · p. 15
- Per-processor communication is bounded by summing costs across protocol steps, with processor appearances and levels absorbed by the ˜ notation.The proof identifies Step 2 as dominating Step 3.Source: §A.1 · p. 16
- The proof gives O(log^(4+δ) n) running time and ˜O(n^(4/δ)) bit complexity per processor for δ > 4.It sets q = (log n)^δ and uses w = O(log^3 n).Source: §A.1 · p. 16
A.2 Almost Everywhere Byzantine Agreement (AEBA) with Unreliable Global Coins
Algorithm 5 updates each processor’s vote using neighbor votes and a global coin, repeating this process for each round.
A.2 Almost Everywhere Byzantine Agreement (AEBA) with Unreliable Global Coins
- Each round, processors send their current vote to neighbors in G, collect neighbor votes, and compute the majority bit and its vote fraction.The algorithm initializes vote to the processor’s input bit.Source: §A.2 · p. 16
- When the majority fraction reaches (1 −ϵ0)(2/3 + ϵ/2), a processor sets its vote to that majority bit.Source: §A.2 · p. 16
- Otherwise, the processor sets its vote to 1 for heads or 0 for tails from GetGlobalCoin; after the rounds, it commits to its vote.Source: §A.2 · p. 16
A.3 Analysis
Under the stated bad-processor bound, the analysis establishes that a sparse random graph yields informed processors in each round, then uses global coins to drive and preserve agreement.
A.3 Analysis
- The analysis assumes at most 1/3 + ϵ bad processors for fixed ϵ > 0 and defines success of GetGlobalCoin as an independent uniform bit learned by all but O(n/log n) processors.Source: §A.3 · p. 16
- With at least r successful GetGlobalCoin rounds on a random k log n-regular graph, all but C2n/log n good processors commit to the same good input bit with probability at least 1 −e−C1n + 1/2r.The constants C1 and C2 are positive, and k depends on them.Source: §A.3 · p. 17
- With high probability, each round has at most Cn/log n processors outside the informed set, for sufficiently large graph-degree constant k.The proof bounds both processors receiving too little support for the majority among good processors and those receiving too much support when bad processors are included.Source: §A.3 · pp. 17–18
- For the informing argument, the good processors’ majority set S′ has size at least 1/3(n + ϵ), and the analysis bounds deviations in neighbor-vote fractions on a random regular graph.It compares edge counts under sampling without replacement and with replacement, then uses a Chernoff bound and union bounds.Source: §A.3 · p. 17
- If all but Cn/log n good processors vote for b′ in a round, all but Cn/log n continue voting for b′ in every remaining round, regardless of GetGlobalCoin’s outcome.This persistence follows because informed processors meet the vote-fraction threshold and retain b′.Source: §A.3 · p. 18
- A successful GetGlobalCoin call makes all but O(n/log n) good processors share a vote at round end with probability at least 1/2.A successful call returns the same unbiased coin toss to all but O(n/log n) good processors.Source: §A.3 · pp. 16, 18
- Across r successful coin rounds, the analysis bounds the chance of failing to reach agreement that persists by 2r, then applies a union bound to establish Theorem 3.The theorem proof also uses the persistence result to preserve the agreed vote.Source: §A.3 · pp. 18–19
- If all processors start with the same input bit, all but C2n/log n eventually commit to it with probability at least 1−e−C1n.Source: §A.3 · p. 19