REVIEW 3 major objections 4 minor 30 references
Improved Byzantine Agreement under an Adaptive Adversary
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A randomized Byzantine agreement protocol runs in O(min{t^2 log n/n, t/log n}) rounds under an adaptive adversary, improving the Chor-Coan bound.
desk verdict The committee idea is plausible, but the adaptive-adversary timing breaks the common-coin proof and the round bound contradicts the algorithm itself; as written the main result doesn't hold. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the committee-based common coin (Algorithm 2). In each phase, the $s$ nodes of a designated committee each broadcast a uniform independent bit from $\{-1,1\}$, and every node takes the majority of the received values; the agreement protocol uses this coin only for nodes that failed to lock onto a value. The correctness rests on a single-round anti-concentration bound: by the Paley-Zygmund inequality, the sum of the honest committee members' random choices exceeds $\frac{1}{2}\sqrt{n}$ (or falls below $-\frac{1}{2}\sqrt{n}$) with probability at least $1/12$, and since the adversary controls at most $\frac{1}{2}\sqrt{n}$ nodes it cannot flip the majority. The protocol's round count $c=\min\{\alpha\lceil t^2/n\rceil\log n,\;3\alpha t/\log n\}$ is chosen so that, by a counting argument, many committees have few Byzantine nodes and therefore many phases are independently good with constant probability.
What would settle it
Simulate the one-round coin protocol with an adaptive adversary that, after inspecting every node's private $\pm 1$ coin, corrupts up to $\frac{1}{2}\sqrt{n}$ nodes and replaces their messages with its own value. Measure the empirical probability that all honest nodes output the same bit and check that it is bounded below by a constant. If the probability is not constant, or if the output bit is biased, the common-coin theorem as stated is falsified; the proof in Theorem 3 assumes the honest set $G$ is fixed before the coins are drawn, which is exactly the assumption an adaptive adversary violates.
Extended reading notes
Core claim
Algorithm 3 solves Byzantine agreement with high probability in $O(\min\{t^2\log n/n, t/\log n\})$ rounds under an adaptive rushing adversary in the full-information model, for any $t<n/3$. The protocol is a Rabin-style agreement loop: each phase tries to lock onto a value using an $n-t$ threshold, and nodes that cannot lock use a common coin generated by the phase's committee of designated nodes. The paper proves that committees with fewer than $\frac{1}{2}\sqrt{s}$ Byzantine members (where $s$ is committee size) yield a good phase with constant probability, and that enough such committees exist in the counting of phases. Consequently the runtime strictly improves on Chor and Coan when $t=o(n/\log^2 n)$, matches their runtime for larger $t$, and becomes within logarithmic factors of the lower bound when $t=\Theta(\sqrt{n})$. A Las Vegas variant guarantees termination in the same expected rounds, and the protocol terminates early in $O(\min\{q^2\log n/n, q/\log n\})$ rounds if only $q<t$ nodes are actually corrupted.
Load-bearing premise
The proof of Theorem 3 treats the set $G$ of honest nodes as fixed before the honest random bits are drawn, so the sum $X=\sum_{v\in G} X_v$ has mean $0$; under the paper's own adaptive adversary, which chooses corruptions after seeing all first-round random choices, $G$ is data-dependent and that expectation can be biased, and the constant-probability common-coin guarantee rests on this step.
Editorial extensions
If this is right
- In the regime $t=o(n/\log^2 n)$, the round complexity drops from $O(t/\log n)$ to $O(t^2\log n/n)$, an asymptotic improvement by a factor of about $n/(t\log^2 n)$.
- When $t=\Theta(\sqrt{n})$, the protocol matches the Bar-Joseph and Ben-Or lower bound within logarithmic factors, making it near-optimal in that regime.
- The message complexity $O(\min\{n t^2\log n,\;n^2 t/\log n\})$ also improves on Chor and Coan, so the speedup is not at the cost of more communication.
- The Las Vegas variant ensures agreement is always reached, with only the number of rounds randomized, and early termination gives $O(\min\{q^2\log n/n, q/\log n\})$ rounds when the adversary actually corrupts only $q<t$ nodes.
Reading between the lines
- If the proof of Theorem 3 is repaired, the committee-coin approach likely generalizes to the full range $t<n/3$ by letting committee size grow with $t$, potentially confirming the paper's conjecture that its round complexity is near-optimal.
- The same Paley-Zygmund technique suggests a general design rule for adaptive-adversary protocols: confine all private randomness to a small, publicly known committee and use anti-concentration to show the adversary's lookahead cannot bias the aggregate outcome by more than the committee's honest majority.
- A concrete testable extension would be to apply the committee-coin mechanism to other full-information randomized primitives, such as leader election or verifiable secret sharing, where an adaptive adversary observes random bits before choosing which parties to corrupt.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a synchronous randomized Byzantine agreement protocol for complete networks under an adaptive, rushing, full-information adversary. The protocol combines a committee structure with a majority-based common coin. The main claimed result, Theorem 2, is an O(min{t^2 log n / n, t / log n})-round bound, improving the Chor-Coan bound of O(t / log n) when t is small, and approaching the Bar-Joseph and Ben-Or lower bound when t is near sqrt(n). The core technical ingredient is a one-round common coin protocol, analyzed with the Paley-Zygmund inequality.
Significance. If the claimed result were correct, it would be a substantial improvement over a forty-year-old bound and would nearly match the known lower bound in an important parameter regime. The paper is clearly written and the committee-based design is conceptually attractive. Credit is also due for presenting full algorithms and explicit complexity statements. However, the current version contains two load-bearing problems: the proof of the common coin theorem uses an invalid expectation computation under the paper's own adaptive adversary, and the stated round complexity of Theorem 2 is false as written because of the ceiling in the definition of the number of committees. These issues undermine the central claims as stated, although both appear to be repairable with additional work.
major comments (3)
- [Section 3.1, Theorem 3 proof] The assertion E[X] = E[sum_{v in G} X_v] = 0 is not valid under the paper's stated adversarial model. Section 1.1 says that the adaptive rushing adversary sees the random choices made in the current round before acting, so the honest set G is chosen after, and in response to, the variables X_v. Thus G is a data-dependent set and the X_v in G are not independent Rademacher variables conditional on G. As a concrete witness, if the adversary corrupts the t = 0.5 sqrt(n) nodes with value -1 whenever possible, the expected honest sum E[X] is t + o(1), not 0. The subsequent moment computations and the Paley-Zygmund application, and hence Corollary 1, Lemma 5, and Theorem 2, all rest on this step. A correct proof would need to argue from the unconditional total sum, for example using that the honest sum X satisfies |X| >= ||T| - t| where T is the total sum over all n nodes, and then showing P(|T| > 2t) = Omega(1); no such argument is present in the manuscript.
- [Algorithm 3, line 2 and Theorem 2] The stated round bound is false. Algorithm 3 defines c = min{alpha ceil(t^2/n) log n, 3 alpha t/log n}. For t = n^{0.4}, one has t^2/n = n^{-0.2} < 1, so ceil(t^2/n) = 1 and hence c = min{alpha log n, 3 alpha n^{0.4} / log n} = alpha log n, whereas Theorem 2 claims O(t^2 log n / n) = O(n^{-0.2} log n) = o(1) rounds. The claimed bound is subconstant and unattainable; moreover c itself can be less than 1 for very small t, so the committee construction is not even well-defined in that regime. The theorem and the abstract should be restated with the correct expression, e.g., O(min{alpha ceil(t^2/n) log n, 3 alpha t/log n}) rounds, and the claimed improvement regime for t = o(n/log^2 n) must be revised accordingly.
- [Theorem 2 proof, phase-good independence] The proof says 'Since the event that a phase is good is independent of the other phases', but under an adaptive adversary the set of corrupted nodes, the per-phase assigned values b_i, and the adversary's messages are coupled across phases, so this independence does not follow from the protocol description. The high-probability conclusion can likely be recovered by a conditional-probability argument using the fresh coin tosses of each phase, but that argument is not supplied in the manuscript.
minor comments (4)
- [Section 2.1, Lemma 1] The name 'Paley-Zigmund' should be 'Paley-Zygmund'.
- [Algorithm 1, line 3] The pseudocode sums over N(v), while the preceding text says the sum includes v's own value; the pseudocode should be made consistent with the text.
- [Section 3.1, Theorem 3 proof] The two events X > 0.5 sqrt(n) and X < -0.5 sqrt(n) each have probability at least 1/12, so the phrase 'with probability at least 1/12, all honest nodes will have their sum ... or ...' is ambiguous; the union has probability at least 1/6.
- [Algorithm 3, line 2] The formula for c has mismatched parentheses: it should read c = min{alpha ceil(t^2/n) log n, 3 alpha t/log n}.
Circularity Check
No significant circularity: the common-coin derivation is self-contained and the cited related work is background, not load-bearing.
full rationale
The paper's derivation chain does not reduce to its own inputs. Theorem 3 derives the common-coin property from the Paley-Zygmund inequality (Lemma 1) and direct moment computations on the Rademacher variables X_v; it does not assume the conclusion of Theorem 3, nor does it fit any parameter to the claimed outcome. Algorithm 2 inherits this via Corollary 1, and Lemma 5 uses Corollary 1 only as a probabilistic subroutine, not as an input-equivalent restatement of the phase-goodness claim. The citations to the authors' prior work, notably [3], appear only as related-work context noting a shared anti-concentration technique; they are not used to justify the main theorem or to import a uniqueness or impossibility result. The Bar-Joseph and Ben-Or lower bound [4] is an external mathematical result used only for comparison, not as a premise of the upper-bound proof. The possible concern that the adversary may choose the honest set G after seeing random bits is a correctness or independence issue in the proof, not a circularity: even if the E[X]=0 step is unjustified, that is a gap in an otherwise independent derivation, not a case of the theorem being assumed by construction. No fitted value is renamed as a prediction, no ansatz is smuggled in via citation, and no known result is merely relabeled.
Assumptions & free parameters
free parameters (2)
- alpha =
constant satisfying alpha - 4 sqrt(alpha) >= gamma
- gamma =
arbitrary constant >= 1
assumptions (4)
- standard math Paley-Zygmund inequality
- ad hoc to paper The uncorrupted node set G in the coin-flip round is independent of the honest nodes' random choices X_v
- domain assumption Synchronous, reliable point-to-point complete network with CONGEST bandwidth and authenticated sender identities
- domain assumption Committee sizes are uniform; the last committee being smaller is ignored
Cite this review
Pith. "Pith review of Improved Byzantine Agreement under an Adaptive Adversary." pith.science (2026). https://pith.science/paper/D2ZMOSM5
@misc{pith2026250604919,
author = {Pith},
title = {Pith review of: Improved Byzantine Agreement under an Adaptive Adversary},
year = {2026},
howpublished = {\url{https://pith.science/paper/D2ZMOSM5}},
note = {Machine review of arXiv:2506.04919}
}
abstract
Byzantine agreement is a fundamental problem in fault-tolerant distributed computing that has been studied intensively for the last four decades. Much of the research has focused on a static Byzantine adversary, where the adversary is constrained to choose the Byzantine nodes in advance of the protocol's execution. This work focuses on the harder case of an adaptive Byzantine adversary that can choose the Byzantine nodes \emph{adaptively} based on the protocol's execution. While efficient $O(\log n)$-round protocols ($n$ is the total number of nodes) are known for the static adversary (Goldwasser, Pavlov, and Vaikuntanathan, FOCS 2006) tolerating up to $t < n/(3+\epsilon)$ Byzantine nodes, $\Omega(t/\sqrt{n \log n})$ rounds is a well-known lower bound for adaptive adversary [Bar-Joseph and Ben-Or, PODC 1998]. The best-known protocol for adaptive adversary runs in $O(t/\log n)$ rounds [Chor and Coan, IEEE Trans. Soft. Engg., 1985]. This work presents a synchronous randomized Byzantine agreement protocol under an adaptive adversary that improves over previous results. Our protocol works under the powerful \emph{adaptive rushing adversary in the full information model}. That is, we assume that the Byzantine nodes can behave arbitrarily and maliciously, have knowledge about the entire state of the network at every round, including random choices made by all the nodes up to and including the current round, have unlimited computational power, and may collude among themselves. Furthermore, the adversary can \emph{adaptively} corrupt up to $t < n/3$ nodes based on the protocol's execution. We present a simple randomized Byzantine agreement protocol that runs in $O(\min\{t^2\log n/n, t/\log n\})$ rounds that improves over the long-standing bound of $O(t/\log n)$ rounds due to Chor and Coan [IEEE Trans. Soft. Engg., 1985].
Reference graph
Works this paper leans on
-
[20]
Breaking the𝑂(𝑛 2) bit barrier: Scalable byzantine agreement with an adaptive adversary
Valerie King and Jared Saia. Breaking the𝑂(𝑛 2) bit barrier: Scalable byzantine agreement with an adaptive adversary. Journal of the ACM, 58(4):18:1–18:24, July 2011. URL: http://doi.acm.org/10.1145/1989727.1989732, doi:10.1145/ 1989727.1989732
-
[1]
H. Attiya and J. Welch.Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley Series on Parallel and Distributed Computing. Wiley, 2004. URL: https://books.google.com/books?id=3xfhhRjLUJEC
work page 2004
-
[2]
Scalable and secure computation among strangers: Message-competitive byzantine protocols
John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. Scalable and secure computation among strangers: Message-competitive byzantine protocols. In Hagit Attiya, editor,34th International Symposium on Distributed Computing (DISC 2020), volume 179 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:19,...
work page 2020
-
[4]
A tight lower bound for randomized synchronous consensus
Ziv Bar-Joseph and Michael Ben-Or. A tight lower bound for randomized synchronous consensus. InProceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’98, page 193–199, New York, NY, USA, 1998. Association for Computing Machinery.doi:10.1145/277697.277733
-
[5]
Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols
Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. InProceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC ’83, pages 27–30, New York, NY, USA, 1983. Association for Computing Machinery.doi:10.1145/800221.806707
-
[6]
Byzantine agreement in the full-information model in 𝑂(log𝑛) rounds
Michael Ben-Or, Elan Pavlov, and Vinod Vaikuntanathan. Byzantine agreement in the full-information model in 𝑂(log𝑛) rounds. InProceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC ’06, pages 179–186, New York, NY, USA, 2006. ACM. URL: http://doi.acm.org/10.1145/1132516.1132543, doi:10.1145/ 1132516.1132543
arXiv 2006
-
[7]
Asynchronous byzantine agreement protocols.Inf
Gabriel Bracha. Asynchronous byzantine agreement protocols.Inf. Comput., 75(2):130–143, 1987. doi:10.1016/0890- 5401(87)90054-X. 5 ˜𝑂and ˜Ωnotations hide a logarithmic factor. Improved Byzantine Agreement under an Adaptive Adversary 13
doi:10.1016/0890- 1987
-
[8]
B. Chor and B.A. Coan. A simple and efficient randomized byzantine agreement algorithm.IEEE Transactions on Software Engineering, SE-11(6):531–539, 1985.doi:10.1109/TSE.1985.232245
Show all 30 references
-
[9]
Fischer, Rob Fowler, Nancy A
Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and H. Raymond Strong. An efficient algorithm for byzantine agreement without authentication.Information and Control, 52(3):257–274, 1982. URL: http://www. sciencedirect.com/science/article/pii/S0019995882907768, doi...
1982 doi
-
[10]
An optimal probabilistic protocol for synchronous byzantine agreement.SIAM Journal on Computing, 26(4):873–933, August 1997.doi:10.1137/S0097539790187084
Pesech Feldman and Silvio Micali. An optimal probabilistic protocol for synchronous byzantine agreement.SIAM Journal on Computing, 26(4):873–933, August 1997.doi:10.1137/S0097539790187084
1997 doi
-
[11]
Fischer and Nancy A
Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency.Inf. Process. Lett., 14(4):183–186, 1982.doi:10.1016/0020-0190(82)90033-3
1982 doi
-
[12]
Fischer, Nancy A
Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Comput., 1(1):26–39, 1986.doi:10.1007/BF01843568
1986 doi
-
[13]
Garay and Yoram Moses
Juan A. Garay and Yoram Moses. Fully polynomial byzantine agreement in t+1 rounds. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors,Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 31–41. AC...
1993
-
[14]
Fault-tolerant distributed computing in full-information networks
Shafi Goldwasser, Elan Pavlov, and Vinod Vaikuntanathan. Fault-tolerant distributed computing in full-information networks. In2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 15–26, October 2006.doi:10.1109/FOCS.2006.30
2006 doi
-
[15]
Graham and Andrew Chi-Chih Yao
Ronald L. Graham and Andrew Chi-Chih Yao. On the improbability of reaching byzantine agreements (preliminary version). In David S. Johnson, editor,Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 467–478. ACM...
1989
-
[16]
Vassos Hadzilacos and Joseph Y. Halpern. Message-optimal protocols for byzantine agreement.Math. Syst. Theory, 26(1):41–102, 1993.doi:10.1007/BF01187074
1993 doi
-
[17]
Byzantine agreement in polynomial time with near-optimal resilience
Shang-En Huang, Seth Pettie, and Leqi Zhu. Byzantine agreement in polynomial time with near-optimal resilience. In Stefano Leonardi and Anupam Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 502–514. ACM,...
2022
-
[18]
Byzantine agreement with optimal resilience via statistical fraud detection
Shang-En Huang, Seth Pettie, and Leqi Zhu. Byzantine agreement with optimal resilience via statistical fraud detection. J. ACM, 71(2):12:1–12:37, 2024.doi:10.1145/3639454
2024 doi
-
[19]
Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani
Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani. Fast asynchronous byzantine agreement and leader election with full information.ACM Transactions on Algorithms, 6(4):68:1–68:28, September 2010. URL: http://doi.acm.org/10.1145/1824777.1824788,doi:10...
2010
-
[21]
Byzantine agreement in expected polynomial time.J
Valerie King and Jared Saia. Byzantine agreement in expected polynomial time.J. ACM, 63(2):13:1–13:21, 2016. doi:10.1145/2837019
2016 doi
-
[22]
Scalable leader election
Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable leader election. InProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’06, pages 990–999, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics. URL: htt...
2006
-
[23]
Kowalski and Achour Mostéfaoui
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 Panagiota Fatourou and Gadi Taubenfeld, editors,ACM Symposium on Pr...
2013
-
[24]
Shostak, and Marshall C
Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The byzantine generals problem.ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982.doi:10.1145/357172.357176
1982
-
[25]
Lynch.Distributed Algorithms
N.A. Lynch.Distributed Algorithms. The Morgan Kaufmann Series in Data Management Systems. Morgan Kaufmann,
-
[26]
R. E. A. C. Paley and A. Zygmund. A note on analytic functions in the unit circle.Mathematical Proceedings of the Cambridge Philosophical Society, 28(3):266–272, 1932.doi:10.1017/S0305004100010112
1932 doi
-
[27]
Pease, Robert E
Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults.Journal of the ACM, 27(2):228–234, April 1980.doi:10.1145/322186.322188
1980
-
[28]
Michael O. Rabin. Randomized byzantine generals. InProceedings of the 24th Annual Symposium on Foundations of Computer Science, SFCS ’83, pages 403–409, USA, 1983. IEEE Computer Society.doi:10.1109/SFCS.1983.48
1983 doi
-
[29]
Michael Steele
J. Michael Steele. The Paley-Zygmund argument and three variants. http://www-stat.wharton.upenn.edu/~steele/ Courses/530/Resources/Lower%20Bounds/LowerBounds.pdf
-
[30]
CreateSpace Independent Publishing Platform, North Charleston, SC, USA, 3rd edition, 2019
Roger Wattenhofer.Blockchain Science: Distributed Ledger Technology. CreateSpace Independent Publishing Platform, North Charleston, SC, USA, 3rd edition, 2019
2019
-
[1996]
URL: https://books.google.com/books?id=2wsrLg-xBGgC
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.