{"id":"b648b8fc-c4e0-42fb-a194-982e8fe393b5","arxiv_id":"2501.00717","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A committee-based VABA variant where a stochastically selected subset of f+1 parties broadcasts proposals, claiming a factor (f+1) reduction in proposal-broadcast messages but with incomplete correctness proofs.","lead":"This paper designs a variant of validated asynchronous Byzantine agreement in which only a randomly chosen committee of f+1 parties broadcasts proposals, aiming to cut message overhead. The proof of correctness is largely deferred to earlier work, and the total asymptotic communication cost remains quadratic.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The agreement-preservation bridge is missing: Algorithm 9 never stores the mapped leader in `Party[view]`, and Lemma 5.9, the only invariant carrying a decided value into later views, is stated without proof.","rationale":"The reader's weakest assumption points to Lemma 5.9 and the possibility that the mapped committee member is unprepared or Byzantine. I agree that this is the most load-bearing gap, and I refine it by showing where the protocol text fails even to instantiate the needed invariant: the leader identity is never written into `Party[view]`, and the view-change message sends the sender's own proposal state rather than the selected leader's state. Because of these unbound variables and the missing assignment, the literal Algorithm 9/10 cannot execute the view-change validation that Lemma 5.9 presupposes. The paper's other problems, such as Lemma 3.1's impossible condition `f+1 <= f` and the efficiency claim being a constant-factor reduction within an overall O(n^2) protocol, also undermine the paper, but they are not the single most load-bearing point: even if committee selection were fixed and the efficiency claim were stated accurately, the agreement proof would still fail without a supported invariant carrying decided values across views. I therefore recommend keeping the reader's REJECT verdict. I mark partial rather than full agreement because the reader frames the issue as a missing lemma about a Byzantine or unprepared leader, whereas I emphasize that the protocol as written lacks the data flow needed even to state that lemma; the two readings are complementary, not identical.","tokens_in":15690,"tokens_out":18643,"duration_ms":190591,"concrete_test":"Check by hand or by a small state-space search (n=4, f=1) the execution in which view 1 decides v through a mapped leader, and view 2's mapped leader is a Byzantine committee member absent from all completed P-PB steps. Trace Algorithms 9-10 literally: record whether any line assigns `Party[2]`, and whether line 35 for a non-selected honest party evaluates `getPrepare(ID)` with a bound `ID`. If `Party[view]` remains `_|_` (so no view-change validates), or if the only way to make the trace progress requires adding an assignment and sending the leader's state rather than the sender's own state, Lemma 5.9 is unsupported and the manuscript's proof does not establish agreement or termination.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that a value decided in view j is the only value that can receive a valid step-1 proof in any later view. That is exactly Lemma 5.9, and the paper neither proves it nor gives the protocol a way to support it. In the literal pseudocode, Algorithm 8 initializes `Party[view] <- _|_` for every view; Algorithm 9 elects and maps a leader at lines 32-34 but never assigns `Party[view]`. Algorithm 10 then reads `Party[view]` at line 21 to validate view-change proofs. So the validation path used by the view-change step is dead: `party` is `_|_`, and the threshold-validate checks at lines 22-31 cannot pass. Even if one repairs this by assigning `Party[view]`, line 35 multicasts `getPrepare(ID)/getLock(ID)/getCommit(ID)` where `ID` is the sender's own proposal ID (set only at line 6 for selected parties) and is undefined for non-selected parties; it therefore does not send the mapped leader's delivery, as Section 4.6 claims. The premise of Lemma 5.9, that the leader's second/third step proofs exist and are distributed, is not established. A Byzantine or merely inactive committee member can be the nearest mapped party; the protocol has no mechanism guaranteeing that member completed a P-PB step, and the later-view prepare invariant is exactly what would be needed to rule out promoting a different value. Without Lemma 5.9, the agreement and liveness proofs in Theorem 5.15 have no bridge from a decision in view j to prepared values in view j+1. This is load-bearing because it is the step at which the committee modification interacts with VABA-style view changes.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Efficient-VABA, a validated asynchronous Byzantine agreement protocol that restricts the set of proposal broadcasters to a randomly selected committee of size f+1, maps an elected leader to a member of that committee, and otherwise follows the structure of Abraham et al.'s VABA protocol [14]. The central claim is that this reduces proposal-broadcast message complexity from O(n^2) to n(f+1) while preserving agreement, termination, external validity, and integrity with O(1) expected running time. The manuscript gives protocol pseudocode, a set of lemmas intended to establish the security properties, and an efficiency analysis.","tokens_in":16119,"tokens_out":6258,"duration_ms":61824,"significance":"If the protocol were correct, the message-complexity improvement in the proposal phase would be a meaningful practical contribution, because VABA-style multi-valued validated Byzantine agreement is a building block for asynchronous atomic broadcast and state-machine replication. The paper also identifies a genuinely important design question: how to reduce the number of proposal broadcasts without sacrificing the security guarantees of the underlying view-based protocol. However, the claimed result is currently not supported: several load-bearing lemmas are unproved, the main theorem is a sketch, and the pseudocode appears not to implement the described view-change mechanism. The paper does not include machine-checked proofs, executable code, or independent experimental validation, so the evaluation rests entirely on the correctness of the mathematical claims.","major_comments":[{"comment":"The statement 'If n = 3f + 1, f + 1 ≤ f' is contradictory: f + 1 ≤ f is false for every integer f, so the lemma has no meaningful hypothesis. Moreover, for the committee size κ = f + 1 used in the protocol and n = 3f + 1, the probability expression (f choose κ)/(n choose κ) evaluates to 0 because κ > f. The claim should be re-derived with the correct committee-size parameter; as written, the validity property of the committee-selection primitive is not established.","section":"Section 3, Lemma 3.1"},{"comment":"The view-change validation path is dead in the pseudocode. Algorithm 9 maps the elected leader to a committee member at lines 32–34 but never assigns the result to Party[view], while Algorithm 8 initializes Party[view] ← ⊥ for every view; Algorithm 10 then reads Party[view] at line 21 and threshold-validates messages that mention 'party'. Furthermore, line 35 multicasts getPrepare(ID)/getLock(ID)/getCommit(ID) with ID bound at line 6 only for selected parties, so a non-selected party's ID is undefined, and the message does not carry the mapped leader's delivery as Section 4.6 claims. The view-change step therefore cannot perform the proof-carrying promotion on which all later lemmas depend.","section":"Section 4.6, Algorithms 9 and 10"},{"comment":"Lemma 5.9 is the key agreement invariant: once a party decides v in view j, every valid step-1 proof produced in any later view must also carry v. It is stated without proof, and it is used directly in Theorem 5.15 for agreement. No argument in the paper shows that the committee member chosen by Algorithm 7 has completed a second- or third-step P-PB instance, so valid prepare/lock proofs for that member may not exist. If the nearest committee member is Byzantine or inactive, the premise of the lemma fails, and the theorem's bridge from view j to view j + 1 is missing.","section":"Section 5.1, Lemma 5.9"},{"comment":"Several supporting lemmas are asserted without proof or with only a sketch: Lemma 5.6 (propagation of view-change proofs), Lemma 5.10 (lock implies prepare in the next view), and Lemma 5.11 (external validity of all broadcast messages) are all used in the proof of Theorem 5.15. The proof of Theorem 5.15 itself is a high-level sketch, and its External-Validity part repeats the proof of Lemma 5.11 rather than establishing the property for the modified protocol; since the committee mapping changes the view-change format, a direct appeal to VABA [14] is not sufficient.","section":"Section 5.1, Lemmas 5.6, 5.10, and Theorem 5.15"}],"minor_comments":[{"comment":"The condition 'threshold-validate(⟨id, v′⟩, v′) = true' should presumably read 'threshold-validate(⟨id, v′⟩, σ′) = true'; as written, the argument is a value rather than a signature.","section":"Section 2.1.1, PB-Provability definition"},{"comment":"The heading says 'Gocal variables initialization'; this should be 'Global variables initialization'.","section":"Algorithm 8"},{"comment":"The line numbering in Algorithm 5 is out of order (lines 09-08), and several threshold-validate expressions in Algorithms 5 and 10 have unbalanced parentheses, making it difficult to determine the exact message ID being validated.","section":"Algorithms 5 and 10"},{"comment":"The text states that each party multicasts the selected party's delivery via VIEW-CHANGE, but Algorithm 9 uses getPrepare(ID), getLock(ID), and getCommit(ID) where ID is the sender's own identifier; this discrepancy should be resolved even apart from the substantive issue raised in the major comments.","section":"Section 4.6"}],"recommendation":"reject","confidential_remarks":"The manuscript is not ready for publication: the central security proof has multiple unproved lemmas, and the pseudocode does not implement the described view-change. I recommend rejection rather than major revision because the missing invariant (Lemma 5.9) is not a local gap: the protocol's leader-mapping rule does not guarantee that the mapped committee member has the required proofs. The paper also relies heavily on the author's own unpublished works for committee selection and provable-broadcast definitions, which complicates independent verification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The paper identifies a real inefficiency in VABA — letting every party broadcast when only one value will be agreed on — and proposes to restrict proposal broadcasts to a random f+1 committee, with the elected leader mapped to the nearest committee member. That's a legitimate direction, and the suggestion step (wait for n-f suggestions to ensure enough honest parties saw a proposal) is a sensible patch. But the protocol as written does not work. In Algorithm 9, a party never assigns Party[view]; Algorithm 8 initializes it to ⊥ and Algorithm 10 line 21 reads it to validate view-change messages. So the validation path is dead. For non-selected parties, ID is undefined when getPrepare(ID) is called at line 35. These are not typos; they break the protocol's operation. The load-bearing invariant, Lemma 5.9, is stated without proof, and it's exactly the claim needed to carry a decided value into later views. The stress-test note is right: without Lemma 5.9, Theorem 5.15 has no bridge. The external-validity proof restates Lemma 5.11, and Lemma 3.1 has an impossible condition 'f+1 ≤ f' with a factorial over a negative integer in the proof. The efficiency gain is modest: overall complexity stays O(n^2); only the proposal-broadcast phase drops by a factor of f+1. And the novelty is limited because the committee idea is explicitly from the author's own prior work. Still, the paper is not a random pile of claims; the architecture is coherent enough that a careful rewrite might produce a valid protocol. But as it stands, the central proof is missing and the pseudocode contradicts itself. Who should read this? Someone working on MVBA variants, or the author's other papers, might skim it for ideas. But it is not ready for peer review. A serious editor should desk reject this version and invite a revision that fixes the pseudocode, proves Lemma 5.9, and corrects Lemma 3.1.","headline":"A plausible efficiency idea, but the protocol's own pseudocode cannot run and the key agreement-preservation lemma is unproved.","tokens_in":16583,"tokens_out":4043,"would_cite":false,"duration_ms":37415,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68M15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Efficient-VABA reduces the proposal-broadcast set from all n parties to a randomly chosen committee of f+1, claiming the same validated asynchronous Byzantine agreement guarantees as VABA while cutting proposal-broadcast messages from…","keywords":["asynchronous Byzantine agreement","validated Byzantine agreement","committee selection","provable broadcast","threshold signatures","leader election","communication complexity","view-change protocol"],"falsifier":"Construct a view where the elected leader is not on the committee and the mapped nearest committee member is Byzantine, and check whether any honest party holds a valid threshold-signature prepare proof for that member at the start of the next view. A small n=4, f=1 simulation with adversarially delayed messages can test whether a value decided in view j fails to be promoted, which would contradict Lemma 5.9.","tokens_in":15501,"feed_emoji":"📡","tokens_out":9856,"duration_ms":92075,"temperature":0.7,"pith_summary":"The paper is trying to establish that a validated asynchronous Byzantine agreement protocol can get by with far fewer proposal broadcasts than the VABA baseline. It proposes Efficient-VABA, in which only a randomly selected committee of f+1 parties, rather than all n parties, broadcast their requests, with a suggestion step so parties can move forward after the first completed proposal. The paper claims this preserves VABA's agreement, liveness, external validity, and integrity properties while reducing proposal-broadcast messages from O($n^{2}$) to n(f+1). A sympathetic reader would care because, when parties are agreeing on a single value, having every party broadcast its proposal is wasteful; the paper points to a way to spend the communication budget only on a small committee.","feed_headline":"Committee of f+1 broadcasters cuts VABA messages to n(f+1)","feed_subtitle":"Only f+1 randomly chosen parties propose; the protocol claims same safety, liveness and validity as VABA.","key_machinery":"The load-bearing object is the prioritized provable-broadcast sub-protocol, a four-step sequential broadcast in which each step's threshold-signature proof becomes the input of the next, ending in a commit proof. Honest parties return sign-shares only for senders listed in the current view's prioritized committee, so only the f+1 selected parties can ever obtain a completed promotion. The supporting mechanisms are committee selection by threshold coin-tossing, a suggestion phase that lets a party act on the first valid proposal, and a leader-election-to-committee mapping that picks the nearest committee member to the elected leader. Together these are supposed to ensure that one honest committee member's proposal is disseminated, locked, and carried into the next view.","core_discovery":"The paper's central claim is that the VABA leader-based structure survives a reduction in the number of broadcasters. In Efficient-VABA, committee selection picks f+1 prioritized parties for each view; only those parties can initiate the four-step prioritized provable-broadcast chain that produces prepare, lock, and commit threshold-signature proofs. Leader election is then forced onto the committee by mapping the randomly elected leader to the nearest committee member. The paper asserts that at least one selected honest party completes promotion, that only selected parties can complete promotion, and that these changes reduce the proposal-broadcast message count to n(f+1) while preserving agreement, termination, external validity, and integrity under f