{"id":"f6ecabe9-4345-49ba-9c2e-d460133da40b","arxiv_id":"2412.03789","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"A committee-based variant of VABA that restricts proposal broadcasts to kappa selected parties, claimed to reduce messages while preserving agreement, liveness, and external validity.","lead":"This paper proposes eVABA, a Byzantine agreement protocol in which only a small committee of kappa parties broadcasts proposals instead of all n parties. The claimed benefit is fewer messages per view, but the security proof is missing and the total complexity remains O(n^2).","discovery_kind":"incremental","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Liveness is asserted, not proved: Theorem 3.2 is stated without proof, and the committee-honesty premise in Section 2.1 is unquantified, so the central claim cannot be instantiated or verified.","rationale":"I read the paper's contribution as reducing VABA's proposal-promotion cost from O(n^2) to O(n*kappa) by restricting broadcasts to a kappa-size committee, while preserving VABA's guarantees. The liveness half of Theorem 3.2 is the most load-bearing condition because it is the only place where the committee assumption does real work, and it is left uninstantiated. The reader's weakest_assumption identifies exactly this: no distribution or kappa value makes the 'overwhelming probability' premise testable. I agree with that identification. In addition, the theorem has no proof, so even conditional on a secure committee selection, the agreement and liveness claims are unsupported. The efficiency claim is also questionable because the paper itself concedes all-to-all O(n^2) steps remain, but the liveness gap is sufficient to reject. No machine-checked proof or reproducible implementation is supplied. The reader's verdict of REJECT therefore remains appropriate.","tokens_in":5016,"tokens_out":10337,"duration_ms":112769,"concrete_test":"Independently re-derive Theorem 3.2's liveness proof for a concrete instantiation: uniform random kappa-subset with n=3f+1 and f=n/3. Compute the explicit bound P(no honest committee member) <= (f/n)^kappa, and prove that even when the mapped leader is Byzantine, the view-change terminates in expected constant rounds. If the proof cannot be completed without additional assumptions about the committee distribution, the leader-election protocol, or the value of kappa, the liveness claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 3.2: eVABA preserves VABA's agreement, external-validity, and liveness/termination while reducing proposal-promotion cost. The theorem is stated without proof; the preceding Lemma 3.1 only shows that a selected party can complete a promotion, not that honest parties decide on a common value or that views terminate. The liveness branch depends on Section 2.1's assumption that a randomized kappa-size committee contains at least one honest party 'with overwhelming probability,' but the paper gives no sampling distribution, no lower bound on kappa, and no failure bound. Without these, 'overwhelming' is vacuous: if kappa is too small, an all-Byzantine committee is likely and no honest proposal is promoted; if the adversary can influence selection, no uniform bound follows. Moreover, liveness requires the leader-election/mapping in Section 2.4 to yield a leader with an available valid proposal; the paper does not analyze the probability that the mapped leader is honest, so the O(1) expected termination time in Section 3.2 is unsupported. Section 3.2 also contradicts its own reduction claim by admitting that suggest, leader-election, and view-change are all-to-all O(n^2), but the liveness gap is logically prior.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript proposes eVABA, an asynchronous Byzantine agreement protocol based on VABA. Instead of letting all n parties broadcast proposals, the protocol selects a κ-size committee; only committee members run a prioritized provable broadcast (P-PB); a leader is elected and then mapped to a committee member; and a view-change step disseminates the chosen proposal. The paper claims that this preserves the Agreement, External Validity, and Liveness/Termination properties of VABA and reduces the proposal-promotion message cost from O(n^2) to O(nκ) per view, while retaining O(n^2) total message complexity and O(1) expected time.","tokens_in":5287,"tokens_out":6314,"duration_ms":56735,"significance":"The idea of restricting proposal broadcasts to a small committee is a natural and potentially valuable direction for reducing communication in asynchronous Byzantine agreement, and the paper identifies a real inefficiency in all-to-all propose protocols. However, the manuscript does not deliver a verifiable result: the main theorem is a one-sentence assertion that delegates all security to unproved and mostly unspecified sub-protocols; the liveness premise on committee composition is unquantified; and the efficiency analysis contradicts its own reduction claim. There is no machine-checked proof, no simulation, and no formal comparison with VABA's total cost. As it stands, the contribution is an approach description rather than an established protocol with stated guarantees.","major_comments":[{"comment":"Theorem 3.2 is the only correctness statement for eVABA, but it is asserted without proof. The preceding text (including Lemma 3.1) only establishes that a selected party can complete a proposal promotion; it does not argue that honest parties decide on a common value, that a decided value satisfies the external-validity predicate, or that a view terminates. A valid proof of the theorem would need invariants or an explicit case analysis for Agreement, Validity, and Termination, as well as a formal reduction to the security properties of the committee-selection, provable-broadcast, and leader-election sub-protocols. None of this is present; the theorem's condition 'given that ... protocols are secure' is not backed by definitions of those security properties or by any argument that eVABA instantiates them. Since the entire claimed contribution rests on this theorem, this is a load-bearing gap.","section":"Theorem 3.2 (Section 3.1)"},{"comment":"The liveness branch of the protocol depends on the assumption that a randomly selected committee of size κ contains at least one honest party 'with overwhelming probability.' The paper gives no sampling distribution, no concrete value or lower bound for κ, and no failure bound. If κ is too small, a committee can be entirely Byzantine with non-negligible probability; if the adversary can influence the selection, no uniform bound is guaranteed. In either case the claim that at least one honest committee member will complete a promotion and that views will terminate is unquantified and unverifiable. The same issue affects the O(1) expected time claimed in Section 3.2. This is a separate load-bearing premise from the agreement claim and must be resolved before the protocol can be instantiated.","section":"Section 2.1 (Committee Selection)"},{"comment":"The efficiency analysis does not support the stated reduction. The text says the total number of messages for the proposal-promotion sub-protocol is nκ, reducing the cost 'from n^2 to nκ' (the text as printed reads 'from n2 nκ', which is garbled). It then acknowledges that the suggestion, leader-election, and view-change steps are all-to-all and have O(n^2) message complexity. Therefore the overall message complexity is still O(n^2), and the paper's own conclusion of 'optimal message complexity of O(n^2)' does not demonstrate an asymptotic improvement over standard VABA, which also has O(n^2) complexity. To substantiate the claim that eVABA improves efficiency, the paper must either bound the all-to-all phases in terms of κ or compare the total message count, not just the proposal-promotion portion.","section":"Section 3.2 (Efficiency Analysis)"},{"comment":"The mapping from the elected leader to the nearest committee member introduces an unanalyzed element into the liveness proof. Even if the leader-election protocol selects a common random leader, the paper does not analyze the probability that the mapped committee member is honest or has an available valid proposal. Since a Byzantine committee member can be mapped to even when the elected leader is honest, and liveness requires the view-change step to deliver a valid proposal, the O(1) expected termination time in Section 3.2 is not justified. This is another missing step in the central liveness/termination argument.","section":"Section 2.4 (Party Selection and Mapping)"}],"minor_comments":[{"comment":"Lemma 3.1 refers to 'Algorithm 2.2', but the promoted protocol is Algorithm 1.","section":"Section 3.1, Lemma 3.1"},{"comment":"The notation alternates between 'eV ABA', 'eVABA', 'V ABA', and 'V ABA' in ways that make the text hard to read; a consistent notation would improve clarity.","section":"Throughout"},{"comment":"The sentence 'The total number of messages are n ∗ κ, which reduces the total number of messages and the related computations from n2 nκ' is typographically garbled; it appears to mean from n^2 to nκ.","section":"Section 3.2"},{"comment":"References [6]–[9] are the author's own preprints and are used as the basis for the provable-broadcast, leader-election, and committee-selection building blocks; since these are not peer-reviewed or even cited with version/DOI details, the dependency structure of the security claim is not independently verifiable.","section":"References"},{"comment":"Reference [5] contains a typo: 'bitcon.org' should be 'bitcoin.org'.","section":"Reference [5]"},{"comment":"Figure 1 is mentioned but not described sufficiently in the text; labeling the phases and listing the message flows would improve readability.","section":"Figure 1"},{"comment":"The term 'optimal' is not defined in the conclusion; the paper should state with respect to which class of protocols the O(n^2) complexity is optimal.","section":"Conclusion"}],"recommendation":"reject","confidential_remarks":"The self-citation pattern is notable: the security of eVABA depends on sub-protocols that the author has only described in related preprints [6–9]. For a journal submission, the editor may wish to verify the status of these preprints and whether they have been independently reviewed. The manuscript also appears to be a short 'approach' paper; if the intended venue is a workshop, the expectations may differ, but for a journal the lack of a full proof is disqualifying."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a clear sketch of a committee-based VABA variant, but the central theorem is a conditional assertion with no proof, and the efficiency win is modest because most phases stay O(n^2). The one genuinely useful idea is prioritized provable broadcast: restrict sign-share replies to committee members so non-selected Byzantine parties cannot promote proposals. The leader-to-committee mapping is also a clean trick. And to the paper's credit, its own efficiency section honestly admits that suggest, leader-election, and view-change remain all-to-all O(n^2); it does not oversell the asymptotic complexity as a total improvement.\n\nThe soft spots are where the reader put them. Theorem 3.2 is the entire security argument: one sentence saying agreement, external validity, and liveness hold given that committee selection, provable broadcast, and leader election are secure. There is no invariant, no case analysis, no termination argument. Lemma 3.1 only shows that a selected party can complete a promotion, not that honest parties decide on a common value or that views terminate. The liveness half is especially under-specified: Section 2.1 says a random committee of size kappa contains an honest party 'with overwhelming probability,' but gives no sampling distribution, no lower bound on kappa, and no failure probability. Without that, 'overwhelming' is vacuous; a too-small committee can be all Byzantine and the protocol never terminates. The O(1) expected termination claim in Section 3.2 is similarly unsupported because the probability that the mapped leader is honest is never analyzed.\n\nThe novelty concern is real. The paper's own references [7], [8], [9] are the author's prior committee-based ABA preprints, and the kappa-size committee reduction plus prioritized reply appear to be recombinations of those ideas. The new piece here is the mapping trick and a slightly cleaner presentation, but the paper does not compare against those earlier protocols or explain what this version adds. That is not a fatal flaw by itself—self-citation is fine when the cited work is real—but here it makes the contribution hard to pin down.\n\nWho is this for? A reader working on asynchronous BFT might find the P-PB and mapping ideas worth a look, but as a paper it is not ready for serious peer review. It needs a real proof, a concrete committee-sampling instantiation, and a comparison with the author's own prior work. I would not bring it to a reading group, and I would not cite it. If the author develops the missing pieces, it could become a useful note; today it is a sketch.","headline":"Coherent committee-based VABA sketch, but the central theorem is an unproved conditional and the claimed saving is not asymptotic.","tokens_in":5799,"tokens_out":3346,"would_cite":false,"duration_ms":33261,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A randomly chosen κ-party committee can carry VABA-style Byzantine agreement while only the committee broadcasts proposals.","keywords":["asynchronous Byzantine agreement","validated asynchronous Byzantine agreement","VABA","committee selection","provable broadcast","leader election","communication complexity","blockchain"],"falsifier":"Take $n=3f+1$ and a uniformly random κ-subset; the probability the committee is entirely Byzantine is $\\binom{f}{\\kappa}/\\binom{n}{\\kappa}$ (or the analogous quantity for the paper's unspecified distribution). If for the intended κ this probability is not negligible over the protocol's view count, then the Liveness/Termination half of Theorem 3.2 has no demonstrated precondition, and an adversary could stall every view by ensuring all committee members are corrupt.","tokens_in":4780,"feed_emoji":"🗳️","tokens_out":8577,"duration_ms":83800,"temperature":0.7,"pith_summary":"This paper tries to show that asynchronous Byzantine agreement does not need every party to broadcast its proposal. It proposes eVABA, a version of validated asynchronous Byzantine agreement (VABA) in which a randomly chosen committee of κ parties is the only group allowed to promote proposals. The protocol adds a gated broadcast step, prioritized provable-broadcast, so honest parties ignore proposal messages from non-committee members, and it maps the leader election output onto a committee member. The paper claims that under secure committee selection, provable broadcast, and leader election, eVABA keeps VABA's agreement, external validity, and liveness guarantees. If true, the proposal-promotion phase drops from $O(n^2)$ to $O(n\\kappa)$ messages per view, with total complexity still $O(n^2)$ because the suggestion, leader-election, and view-change phases remain all-to-all.","feed_headline":"Committee voting cuts Byzantine agreement broadcast cost to O(nκ)","feed_subtitle":"A small randomly chosen committee broadcasts proposals while agreement, validity, and termination are preserved.","key_machinery":"The carrying object is the κ-size committee combined with a gated broadcast primitive called Prioritized Provable-Broadcast (P-PB): a variant of provable broadcast in which honest parties return sign-shares only for senders that are on the view's committee, so only committee members can gather the $n-f$ shares needed to form a threshold-signature proof. On top of this, a distance-based mapping from the elected leader's id to the nearest committee member keeps the single-leader property while forcing the leader into the committee. The view-change phase then moves key/lock/commit proofs to all parties, and a party that cannot decide adopts the value of its latest key and carries it, with its proof, into the next view for external validity.","core_discovery":"On its own terms, the paper's discovery is that the expensive all-party broadcast step in VABA can be replaced by a κ-party committee broadcast without changing the protocol's core guarantees. The mechanism is a prioritized provable-broadcast in which honest parties attach sign-shares only to messages from parties selected for the current view, so a Byzantine party that is not on the committee cannot complete a proposal promotion and cannot force honest parties to waste bandwidth. The selected committee members promote proposals, all parties suggest and collect commit proofs, and a deterministic distance-based mapping sends the leader-election outcome to the nearest committee member so that every party agrees on which proposal to deliver. Theorem 3.2 states that eVABA satisfies Agreement, External-Validity, and Liveness/Termination provided the committee-selection, provable-broadcast, and leader-election protocols are secure; the concrete payoff is that proposal promotion costs $n\\kappa$ messages instead of $n^2$.","pith_inferences":["Beyond the paper, the trade-off between liveness and cost is governed by the committee-selection distribution: the paper gives no formula for κ, so a natural next step is to derive, for a given adversary threshold f and selection distribution, the minimum κ that makes an all-Byzantine committee unlikely enough to satisfy a target liveness bound.","Because the suggestion, leader-election, and view-change phases are still all-to-all, the end-to-end gain concentrates almost entirely in the proposal-promotion step; a further optimization would need to reduce those all-to-all phases, which this paper does not attempt.","If a fresh committee is sampled every view rather than once per protocol run, the adversary's ability to target committee members changes, and the protocol's security analysis would need to account for the sampling cost; the paper leaves this variant unexamined."],"forward_implications":["Only κ parties broadcast proposals in each view, cutting the proposal-promotion message count from $O(n^2)$ to $O(n\\kappa)$ while keeping total message complexity of the whole protocol at $O(n^2)$.","A non-committee Byzantine party cannot inject a proposal: honest parties' P-PB sign-shares are withheld, so the party cannot complete the threshold-signature proof.","The elected leader is always mapped to a committee member, so all parties deliver the same committee-backed proposal even when raw leader election picks an outsider.","When a view fails to decide, parties carry the latest key value with its proof into the next view, which preserves external validity across view changes.","Expected time complexity stays constant at $O(1)$ views, so the savings do not come at the cost of extra rounds."],"supporting_citations":[{"why":"Supplies the Honey Badger asynchronous atomic-broadcast protocol whose all-party broadcast cost eVABA aims to remove.","marker":"[1]"},{"why":"Provides Dumbo, a faster asynchronous BFT protocol, which the proposed protocol positions itself against and extends.","marker":"[2]"},{"why":"Defines the Byzantine agreement problem and the resilience bound n=3f+1 that the analysis assumes.","marker":"[4]"},{"why":"Prior work on optimizing communication in Byzantine agreement protocols, part of the line this paper continues.","marker":"[6]"},{"why":"Prior protocol introducing prioritized proposal promotion, the technique that P-PB adapts to committee members.","marker":"[7]"},{"why":"Prior committee-based optimal asynchronous Byzantine agreement protocol, direct predecessor of eVABA.","marker":"[8]"}],"fun_headline_variants":["eVABA: Small committee broadcast slashes Byzantine agreement costs","Cutting ABA broadcast from n² to nκ with a small committee","Random committee keeps VABA guarantees while slashing messages","Byzantine agreement gets leaner: eVABA broadcasts via κ-party set"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a randomly selected committee of size κ contains at least one honest party with overwhelming probability; the paper invokes this to guarantee progress but never specifies a selection distribution, a value of κ, or a failure bound.","fun_headline_variants_meta":{"raw":{"variants":["eVABA: Small committee broadcast slashes Byzantine agreement costs","Cutting ABA broadcast from n² to nκ with a small committee","Random committee keeps VABA guarantees while slashing messages","Byzantine agreement gets leaner: eVABA broadcasts via κ-party set"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000665,"raw_usage":{"total_tokens":2995,"prompt_tokens":865,"completion_tokens":2130,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":481,"completion_tokens_details":{"reasoning_tokens":2057}},"tokens_in":481,"tokens_out":2130,"duration_ms":17036,"temperature":1.0,"reasoning_tokens":2057,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:06:17.868387+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $n=3f+1$ and a uniformly random κ-subset; the probability the committee is entirely Byzantine is $\\binom{f}{\\kappa}/\\binom{n}{\\kappa}$ (or the analogous quantity for the paper's unspecified distribution). If for the intended κ this probability is not negligible over the protocol's view count, then the Liveness/Termination half of Theorem 3.2 has no demonstrated precondition, and an adversary could stall every view by ensuring all committee members are corrupt.","supporting_citations":[{"cited_title":"https://easychair.org/publications/preprint/Zs8Mw/ open","cited_arxiv_id":null,"evidence_quote":"Prior work on optimizing communication in Byzantine agreement protocols, part of the line this paper continues."}],"review_version":1}