Pith. sign in

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 →

arxiv 2506.04919 v1 pith:D2ZMOSM5 submitted 2025-06-05 cs.DC cs.DS

classification cs.DCcs.DS
keywords ByzantineagreementadaptiveadversaryfullinformationmodelcommoncoincommitteePaley-Zygmundinequalityroundcomplexityrandomizeddistributedalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that Byzantine agreement in a synchronous complete network can be solved faster than the long-standing Chor-Coan bound even against an adaptive, rushing, full-information adversary. Its protocol runs in $O(\min\{t^2\log n/n, t/\log n\})$ rounds with high probability while tolerating up to $t

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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)
  1. [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.
  2. [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.
  3. [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)
  1. [Section 2.1, Lemma 1] The name 'Paley-Zigmund' should be 'Paley-Zygmund'.
  2. [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.
  3. [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.
  4. [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

0 steps flagged · score 0.0 of 10

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 2 free parameters · 4 assumptions · 0 invented entities

The protocol depends on the hand-chosen constants alpha and gamma, on the standard Paley-Zygmund inequality, and on a false independence assumption about the adversary's adaptive corruption set. The independence assumption is the key unproved premise; if it is removed, the common-coin theorem needs a different proof.

free parameters (2)
  • alpha = constant satisfying alpha - 4 sqrt(alpha) >= gamma
    Appears in the definition of the number of committees c and in the high-probability failure exponent; hand-chosen in the analysis, not derived from data.
  • gamma = arbitrary constant >= 1
    Sets the polynomial failure probability in the high-probability argument; hand-chosen, not fitted to data.
assumptions (4)
  • standard math Paley-Zygmund inequality
    Invoked in Lemma 1 and used in the proof of Theorem 3 to derive constant-probability tails for the honest coin sum.
  • ad hoc to paper The uncorrupted node set G in the coin-flip round is independent of the honest nodes' random choices X_v
    Used implicitly in the moment computation E[X] = 0 and E[X^2] = g in Theorem 3. The paper's own timing statement, that the adversary corrupts after seeing random choices, makes this false; this is a load-bearing invalid assumption.
  • domain assumption Synchronous, reliable point-to-point complete network with CONGEST bandwidth and authenticated sender identities
    Standard model assumptions stated in Section 1.1; the protocol and lower bound comparison rely on them.
  • domain assumption Committee sizes are uniform; the last committee being smaller is ignored
    Section 3.2 says the last committee may be smaller and is ignored with minimal impact; this is assumed rather than proved.

how reviews work

0 comments
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].

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 22 canonical work pages

  1. [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

  2. [1]

    Attiya and J

    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

  3. [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,...

  4. [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. [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. [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

  7. [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

  8. [8]

    Chor and B.A

    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
  1. [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...

  2. [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

  3. [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

  4. [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

  5. [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...

  6. [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

  7. [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...

  8. [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

  9. [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,...

  10. [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

  11. [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...

  12. [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

  13. [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...

  14. [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...

  15. [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

  16. [25]

    Lynch.Distributed Algorithms

    N.A. Lynch.Distributed Algorithms. The Morgan Kaufmann Series in Data Management Systems. Morgan Kaufmann,

  17. [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

  18. [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

  19. [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

  20. [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

  21. [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

  22. [1996]

    URL: https://books.google.com/books?id=2wsrLg-xBGgC

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.