{"id":"7ef2456c-35be-44ec-8d72-e5317f85150c","arxiv_id":"2501.05377","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A signature-free precomputation of many small honest-majority witness committees enables Byzantine-fault-tolerant broadcast, aggregation, consensus, and common coins with near-constant per-node communication.","lead":"This paper designs distributed algorithms that let many computers agree, broadcast, and aggregate data even when a fraction of them misbehave, with each machine doing only a tiny communication load. It replaces digital signatures with precomputed small witness committees, at the price of a restricted adversary, which could lower the cost of large-scale blockchains and sensor networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Phase A deadline is a factor Θ(log n) too short for honest membership announcements, invalidating Lemma 2.3 and the common-core guarantee underpinning Theorem 6.","rationale":"The reader's weakest assumption was the bandwidth-restricted adversary, but that restriction is arguably implied by the per-node bandwidth cap together with f ≤ n/24: if every node, including Byzantine ones, can send at most σ bits per round, then f Byzantine nodes collectively send at most fσ ≤ nσ/24 bits per round, exactly the F ≤ 1/24 condition. The real soft spot is more concrete: the Phase A announcement deadline does not give honest nodes enough rounds to transmit their membership messages once message size is accounted for, so Lemma 2.3's common-core guarantee is not established. This is load-bearing because the common core is the foundation for agreement in the witness committee system, which all downstream protocols rely on. The threshold overclaim (Theorems 5 and 10 state f < n/2 while Theorem 6 only supports f ≤ n/24) is also a real presentation issue, but it does not undermine the central near-constant-work construction for a constant fraction. The verdict should remain CONDITIONAL: the main idea may be salvageable by extending the deadline by a log n factor and rechecking the bandwidth accounting, but the current text does not support the claimed guarantees.","tokens_in":53231,"tokens_out":27583,"duration_ms":268817,"concrete_test":"Compute the honest per-node bit load in Phase A: η n ⌈log n⌉ bits, versus the Line 5 allowance of β n bits (deadline ⌈β n/B⌉ × B). Verify whether β ≥ η log n; under Lemma 2.5 it is not. Then repair by setting the deadline to ⌈η n⌈log n⌉/B⌉ and re-derive Lemma 2.8's adversary-invalidation bound with the longer window; confirm that Ω(n) nodes still have support ≥ n/2 and that Theorem 6's availability α = 1/6 survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Algorithm 1, every honest node samples η committees and sends ⟨member,u⟩ to all n nodes, i.e., η n messages. Each such message must contain the committee identifier u, so it costs Θ(log n) bits. With per-node bandwidth B = O(poly(log n + λ)) bits per round, the honest sender needs Ω(η n log n / B) rounds to finish. The deadline in Line 5 is ⌈β n / B⌉ rounds, and Lemma 2.5 gives β = Θ(η), so this window is a Θ(log n) factor too short. Lemma 2.3 explicitly asserts that this deadline is sufficient for honest nodes to deliver all membership announcements and concludes that every non-empty preliminary committee A_{u,v} contains exactly the same honest nodes. If the deadline is insufficient, that common-core property does not follow; agreement in Definition 2.1 and all later phases (B and C) that build on the shared core collapse. This is an internal correctness gap in the main construction, not a modeling assumption.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a signature-free, randomized precomputation step that builds a system of Θ(n) small witness committees with honest-majority cores, and then uses this system deterministically to solve reliable broadcast, reliable aggregation, common coins, and consensus with near-constant per-node work. The main claimed contribution is Theorem 6, a Monte Carlo construction of such committees in O(n) rounds with O(poly(log n + λ)) bandwidth per node per round, tolerating a synchronous adversary controlling at most n/24 nodes and n/24 of the total bandwidth. The execution layer (Algorithms 4-9) is modular and, if Theorem 6 is accepted, the proofs of broadcast, aggregation, and consensus are mostly straightforward applications of the witness-committee structure. The paper supplies detailed Chernoff-bound arguments and a clear separation between the randomized precomputation phase and the deterministic execution phase.","tokens_in":53459,"tokens_out":12983,"duration_ms":142061,"significance":"If the construction can be fixed, the paper would make a substantial contribution: it would show that the expensive part of signature-free BFT can be moved into a reusable randomized precomputation step, after which multiple distributed tasks can be solved with near-constant work per node. The modular structure, the use of a bandwidth-restricted adversary to bound committee corruption, and the attempt to avoid cryptographic assumptions are all valuable and worth publishing. However, the main construction currently contains a load-bearing round-complexity error in Phase A that undermines the common-core guarantee and therefore the entire committee system. The paper also advertises consensus for t < n/2 in Theorem 10 while only proving the committee construction for t ≤ n/24; this conditional claim needs to be scoped precisely. Because the Phase A error appears fixable by a logarithmic factor in the deadline, I recommend major revision rather than rejection.","major_comments":[{"comment":"The deadline in Algorithm 1 is too short by a Θ(log n) factor. Each honest node samples η committees and sends ⟨member,u⟩ to all n nodes, so it must transmit η n messages. Each such message contains a committee identifier u, costing Θ(log n) bits. With bandwidth σ bits per round, an honest sender needs Θ(η n log n / σ) rounds to deliver all of its membership announcements. The deadline in Line 5 is τ + ⌈η n / σ⌉, which is a factor Θ(log n) smaller. Consequently, Lemma 2.3's assertion that 'the time bound in Line 5 is sufficient for v to send all its messages' is false as written: honest membership announcements can arrive after the deadline, so honest nodes may build different sets A_{u,v}, and the claimed common core in Definition 2.2 and Lemmas 2.4-2.6 is not established. Since Phases B and C build directly on this common-core agreement, this is a load-bearing error for Theorem 6. The fix is local: multiply the deadline by log n (or equivalently define σ as a per-message bandwidth), and re-check Lemma 2.8 with the longer window; an adversary's extra bit budget over the longer window is offset by the log n bit cost of each membership message, so the bound on invalidated committees should survive.","section":"§2.1, Algorithm 1, Line 5; Lemma 2.3"},{"comment":"The paper's headline theorems claim consensus and reliable broadcast for t < n/2 Byzantine nodes, but the only committee construction given in Theorem 6 is proved only for t, f ≤ n/24. Theorem 10 is conditional on 'a system of witness committees as in Definition 2.1', and the paper does not prove that such a system exists for t up to n/2; the Phase A/B/C lemmas explicitly require t ≤ n/24 (Lemmas 2.8, 2.14, 2.17, 2.18). This is not circular, but it is an unsupported extension of the advertised resilience threshold. The authors should either state clearly that Theorems 7-10 are conditional on an externally supplied system whose existence for t < n/2 is an open assumption, or restrict the consensus theorem to the t ≤ n/24 regime that the construction actually supports.","section":"§3.6, Theorem 10 and §3.4, Theorem 7 versus §2, Theorem 6"},{"comment":"The simulation argument for running Garay-Moses in parallel on many small cores is sketched rather than proved: Lemma 2.12 asserts that differing local views C'_{u,v} can be treated as Byzantine behavior in the original protocol, but it does not specify how a node handles messages from participants that are in one local view but not in another, nor how the interleaving of O(η) parallel consensus instances affects the round count when the set of cores is not known identically to all honest nodes. The conclusion is plausible, but the proof should spell out the simulation at the level of message delivery and round schedules, especially because the final round-complexity claim in Theorem 6 depends on this step.","section":"§2.2, Lemma 2.12"}],"minor_comments":[{"comment":"The proof states 'the existence of a v ∈ H with C_{u,v} = ∅ implies |Supp(u)| ≥ n/3'; the intended statement is clearly 'C_{u,v} ≠ ∅'. Please correct this typo, as it obscures the contrapositive argument.","section":"§2.2, Lemma 2.15, proof"},{"comment":"In the first bullet of the proof, 'C_u ⊆ C_{u,v}^{(?)}' is written with an unclear superscript; it should be 'C_u ⊆ C_{u,v}' for every honest v. Please clarify the notation.","section":"§2.3, Lemma 2.18, proof"},{"comment":"The sentence 'There exists at least one honest node (due to witness committees having honest cores)' is imprecise; the existence of an honest node follows from t < n and n ≥ 1, not from the committee structure. Please rephrase.","section":"§3.6, Theorem 9, proof"},{"comment":"The variables β, η, ω, and σ are introduced in different places and the paper sometimes conflates 'messages' with 'bits' in informal discussions (e.g., Lemma 2.8's proof counts adversary messages as if each cost one bit). A short table or a consistent statement of message bit-lengths in Phase A would help avoid this confusion.","section":"§1.2 and §2.1, notation"}],"recommendation":"major_revision","confidential_remarks":"The Phase A deadline bug is the central technical obstacle and should be the main focus of the revision. I believe it is fixable within the paper's scope by adjusting the deadline by a logarithmic factor and rechecking the adversary budget, but as written the main theorem is not established. The paper should also clearly separate the conditional t < n/2 execution results from the t ≤ n/24 construction, so that readers do not infer an unsupported resilience threshold. There are no citation or novelty concerns from my side."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main idea is genuinely new: instead of relying on one large witness committee or on cryptographic sortition, the paper computes a system of Theta(n) small witness committees by a three-phase randomized sampling procedure, and then uses that system as a reusable precomputation for broadcast, aggregation, consensus, and common coins. If the construction worked, it would be a substantial advance for signature-free BFT with near-constant per-node work. The modular design is also good: the application layer only assumes the existence of the committee system, and the probabilistic analysis in Phases B and C is careful, with explicit Chernoff bounds and w.h.c. guarantees. The paper is also honest about the 1/24 adversary share and says it is not optimized. But there is a serious bug in Phase A. In Algorithm 1, each honest node samples eta committees and sends member messages to all n nodes, so it sends eta n messages, each containing a committee identifier of log n bits. With per-node bandwidth B = poly(log n + lambda) bits per round, an honest sender needs Omega(eta n log n / B) rounds just to transmit its announcements. The deadline in Line 5 is ceil(beta n / B), with beta = Theta(eta), i.e. Theta(eta n / B) rounds, a factor Theta(log n) too short. Lemma 2.3 explicitly asserts that this deadline is sufficient for honest nodes to deliver all membership announcements, and the common-core agreement property follows from that. Without it, the whole Phase A/B/C construction loses its foundation. This is not just a modeling choice; it is an internal correctness gap in the main theorem. The good news is that the bug looks fixable: increase the deadline by a log n factor, which does not change the claimed O-tilde(n) round complexity since the paper suppresses log factors. But as written, the proof of Theorem 6 is incomplete. The other concern the reader raised is also real but less severe: Theorems 5 and 10 advertise consensus with f < n/2 Byzantine nodes, but that is conditional on having a system of witness committees, and the only construction in the paper only supports f <= n/24. The abstract's constant fraction is technically true, but the paper's emphasis on f < n/2 for consensus is misleading without a construction that achieves it. This is an overclaim in presentation, not a logical contradiction. Who is this for? Distributed systems theorists working on scalable BFT, randomized consensus, and committee-based protocols. The paper deserves a serious referee, because the idea is substantive and the central flaw appears to be a correctable constant/log factor mistake rather than a wrong approach. I would not cite it in its current form, but I would want to see a revised version.","headline":"Interesting committee-based BFT scheme with a load-bearing Phase A deadline bug; fixable in principle, but as written the central construction does not go through.","tokens_in":798,"tokens_out":784,"would_cite":false,"duration_ms":51151,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68M15","68W15","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a reusable precomputation of $\\Theta(n)$ small witness committees reduces Byzantine broadcast, aggregation, consensus, and common coins to near-constant work per node, without signatures.","keywords":["Byzantine fault tolerance","witness committees","reliable broadcast","consensus","common coin","randomized protocols","near-constant communication","bandwidth-restricted adversary"],"falsifier":"Run Phase A on a simulated network of $n$ nodes with an adversary that controls exactly $n/24$ nodes and spends its full per-round bandwidth budget on membership announcements for a chosen set of committees. Lemma 2.8 predicts the adversary can invalidate at most about $5n^2/12$ preliminary committee instances across all honest views; if even one run invalidates more than that under the stated budget, Theorem 6's availability guarantee $\\alpha=1/6$ fails. A second check: with the bandwidth cap removed, the same adversary can invalidate all committees, confirming that the cap, not just the node fraction, is load-bearing.","tokens_in":52991,"feed_emoji":"🛡️","tokens_out":11797,"duration_ms":103595,"temperature":0.7,"pith_summary":"Distributed protocols that survive Byzantine faults usually make each node pay communication proportional to the network size, or rely on expensive signatures. This paper tries to break that trade-off: it claims randomized, signature-free protocols for reliable broadcast, reliable aggregation, consensus, and common coins where each node does only near-constant—$\\tilde{O}(1)$, more precisely polylogarithmic—work, while tolerating a constant fraction of Byzantine nodes. The enabler is a reusable precomputation that builds a system of $\\Theta(n)$ small witness committees, each with an honest-majority common core, in $\\tilde{O}(n)$ rounds with $\\tilde{O}(1)$ per-node bandwidth per round. If the construction is right, the hard assumptions about synchrony and adversary strength are confined to that one precomputation, after which many instances of broadcast and consensus can be solved cheaply and without signatures.","feed_headline":"Byzantine tasks cut to near-constant work per node, no signatures","feed_subtitle":"A reusable precomputation of small witness committees shifts the hard parts of BFT into a one-time setup.","key_machinery":"The load-bearing object is the system of witness committees: for each of $\\Theta(n)$ nodes, a near-constant-size set of witnesses with an honest-majority common core, agreed upon by all honest nodes. The paper constructs it in three phases: Phase A uses random sampling so each node joins $O(\\log n+\\lambda)$ committees, Phase B filters out committees with weak support by running a small deterministic consensus inside each candidate core, and Phase C spreads knowledge of the surviving committees by random sampling requests. The bandwidth restriction on the adversary ($n/24$ of honest bandwidth) is what makes Phase A safe: it caps how many preliminary committees the adversary can flood into invalidity, and the paper proves a constant fraction survive.","core_discovery":"On the paper's own terms, the central result is that a Monte Carlo algorithm computes a system of witness committees with availability $\\alpha=1/6$ and near-constant committee size $\\beta=O(\\log n+\\lambda)$ in $O(n)$ rounds with $\\mathrm{poly}(\\log n+\\lambda)$ bits per node per round, succeeding with high confidence against a Byzantine adversary that controls at most $n/24$ nodes and $n/24$ of the total bandwidth. The committees satisfy agreement (all honest nodes' local views of a committee share a common core of honest nodes), membership bounds (no node is overloaded, no committee is large), and availability (at least $n/6$ nodes have valid committees). Given such a system, the paper derives a deterministic reliable broadcast that works asynchronously with $O(\\delta)$ work per node in $O(\\log_\\delta n)$ rounds, and synchronous reliable aggregation, common coins, and multi-value consensus with fewer than $n/2$ Byzantine nodes, all without signatures.","pith_inferences":["A direct next step would be to optimize the deliberately unoptimized $1/24$ adversary bounds and derive the exact trade-off curve between the adversary's node/bandwidth fraction and the availability and committee-size parameters.","Because the execution layer relies only on the existence of the committee system, the same precomputation could plausibly be reused for blockchain sharding, where each shard is a witness committee and cross-shard communication goes through the broadcast tree; the paper mentions this application without specifying a protocol.","In practice the bandwidth-restricted adversary must be enforced at the network layer, for instance by rate limiting or by guaranteed honest send capacity; without such enforcement, a Byzantine node that can send arbitrary volume would invalidate the Phase A committees and nullify the theorems."],"forward_implications":["For any constant degree $\\delta>1$, reliable broadcast runs in $O(\\log n)$ rounds with near-constant work per node, deterministically and asynchronously, after the precomputation supplies the committee system.","Reliable aggregation, common coins (with a 1-late adversary), and deterministic consensus with $t 3t Processors in t + 1 Rounds","cited_arxiv_id":null,"evidence_quote":"Supplies the deterministic synchronous consensus subroutine that Phase B runs inside each small committee core to agree on validity in the critical support range."},{"cited_title":"Algorand: Scaling Byzantine Agreements for C ryptocurrencies","cited_arxiv_id":null,"evidence_quote":"Represents the prior witness-committee approach that relies on cryptographic sortition and a single committee, which this paper's multi-committee system extends and strips of signatures."},{"cited_title":"Dynamic Probabilistic Reliable Broa dcast","cited_arxiv_id":null,"evidence_quote":"Shows the prior art's use of small random samples for probabilistic reliable broadcast, which the precomputation refines into a complete committee system."}],"review_version":1}