{"id":"89f924d3-08a1-4c93-a9f0-3987c52d1197","arxiv_id":"2502.02320","paper_version":3,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new reduction plus two new crusader agreement protocols aims to give asynchronous byzantine agreement on long messages quadratic-in-n communication with information-theoretic security.","lead":"This paper shows how to build multivalued byzantine agreement, where parties agree on long messages, from a binary agreement subroutine plus a weaker primitive called crusader agreement. It also designs two new crusader agreement protocols with information-theoretic security, claiming asynchronous agreement with quadratic communication overhead.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"EXT's liveness proof fails: a party that outputs ⊥ from ΠCA and then sees ΠBA output 1 never terminates, so the central reduction is unsound.","rationale":"The reader's rationale already identifies the same EXT liveness failure, but the designated weakest_assumption field points at CA2's collision bound rather than this issue. The EXT failure is the more load-bearing defect: it breaks the central reduction that connects both CA1 and CA2 to multivalued BA, so even a perfectly secure CA would not yield a working extension. The counterexample is protocol-level and independent of the error-correcting code details: it uses only the stated guarantees of CA (weak consistency permits honest ⊥ outputs alongside a non-⊥ value) and the explicit code of EXT and REC. While the CA2 pseudocode inversion noted by the reader is also a serious independent blocker, the EXT liveness gap alone is sufficient to invalidate the paper's main theorem. The verdict REJECT remains appropriate, with high confidence.","tokens_in":26083,"tokens_out":8101,"duration_ms":79155,"concrete_test":"Check the following execution of EXT with n=4, t=1. Let P1 and P2 be honest parties that output v* from ΠCA and input v* to REC; let P3 be a third honest party that outputs ⊥ from ΠCA, multicasts ⊥, and inputs 0 to ΠBA; let the byzantine party P4 send ⊥ to P3 so that P3 also receives t+1 ⊥ messages. Suppose P1 and P2 terminate REC and input 1 to ΠBA, and ΠBA outputs 1 (allowed because the honest inputs to ΠBA are not all equal). Trace P3: it never inputs to REC, so y_3 stays ⊥, and line 18 never fires. This directly falsifies the liveness claim of Theorem 3.3 and shows that the proof's reliance on REC totality for non-input parties is unfounded.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.3 asserts that when ΠBA outputs 1, 'the honest parties all terminate REC with the output v*' because some honest party terminated REC and REC has totality. This use of totality is invalid for EXT. In REC (Appendix A), a party that never acquires an input never executes lines 4-6, never sets y_i on line 16 (line 9 is guarded by y_i ≠ ⊥), and therefore can never satisfy the termination condition on lines 19-20. Thus REC's totality does not cover parties without a REC input. In EXT, any honest party that outputs ⊥ from ΠCA (lines 7-9) never inputs to REC, so its y_i remains ⊥. If ΠBA outputs 1 in the same execution, that party reaches lines 17-18 and is blocked forever because y_i = ⊥. This is not a degenerate case: crusader agreement explicitly permits some honest parties to output ⊥ while others output v*, and binary BA is allowed to output 1 in such a scenario. The liveness property of EXT, and therefore the claimed reduction from multivalued BA to binary BA plus CA, fails for both proposed instantiations.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an asynchronous Byzantine agreement extension, EXT, that reduces multivalued BA on ℓ-bit inputs to one instance of binary BA, one instance of multivalued crusader agreement, a constant number of extra rounds, and Θ(ℓn+n²) extra bits of communication. It then presents two new information-theoretic crusader agreement protocols: CA1, statistically secure for t<n/3 using almost-universal hashing, and CA2, perfectly secure for t≤n/(3+ε) using error-correcting codes and a COOL-inspired preprocessing step. The claimed outcome is the first information-theoretic asynchronous BA extension with quadratic-in-n overhead at resilience t≥n/5, with communication complexity competitive with or better than existing extensions.","tokens_in":26175,"tokens_out":13176,"duration_ms":125323,"significance":"If the central claims were correct, this would be a useful contribution: the EXT reduction is conceptually clean, the complexity accounting is explicit, and the two CA protocols are presented as independently interesting primitives. The comparison table and discussion of prior work are informative. However, the main liveness theorem is not established as written because of a concrete flaw in the REC subprotocol, and the CA2 collision bound relies on an unproved property of the cited codes. These are load-bearing issues for the main theorems, though both appear potentially repairable. The paper does not provide machine-checked proofs or code; the assessment is based on the written proof structure.","major_comments":[{"comment":"Theorem 3.3 fails as written because REC totality does not cover parties that never input to REC. In EXT, an honest party that outputs ⊥ from ΠCA (lines 7-9) never inputs to REC. In REC, line 9 stores an incoming MINE symbol only 'if y_i ≠ ⊥'; a party that never acquired an input keeps y_i=⊥, so it never stores any symbol, never reaches line 16, and can never satisfy the termination condition on lines 19-20. Thus, in an execution where CA returns v* to some honest parties and ⊥ to others, and ΠBA outputs 1, the ⊥ parties reach EXT line 17 with y_i=⊥ and never terminate. Such an execution is permitted: CA weak consistency allows mixed v*/⊥ outputs, and binary BA consistency permits output 1 when some honest parties input 0 and some input 1. The proof of Theorem A.2 likewise overclaims that every honest party terminates after t+1 honest parties send YOURS messages; the line-9 guard blocks exactly the parties without REC inputs. Changing the guard to store a symbol when z_j=⊥ would be a natural repair, but as written the liveness proof is unsound.","section":"§3, Appendix A"},{"comment":"Lemma 5.6 depends on the assertion that distinct messages share at most δ−1 encoded symbols, i.e. any δ symbols uniquely determine the message. This property is not established for the (n,δ)-codes from [25,30,38]; near-MDS codes in the standard sense have minimum distance n−δ rather than n−δ+1, in which case two codewords can agree in δ positions. Under that weaker property the collision bound becomes ⌊(n−3t)/2⌋ instead of ⌊(n−3t−1)/2⌋, and the strict inequalities in Lemma 5.8 (first bullet) and Lemma 5.9 fail; for n=3t+2, |H|−|E_i| evaluates to t rather than t+1, so the parties outside the core need not multicast ⊥. The parenthetical justification in footnote 3 assumes the decoding guarantee is well-defined for every δ-subset, but that is precisely the MDS-like property that needs proof. The paper should either prove that the cited codes have this property or state it as an explicit assumption and adjust the corresponding claims.","section":"§5.3, Lemma 5.6; §2"}],"minor_comments":[{"comment":"The sentence introducing CA2 says 'The protocol CA1 uses the same design as CA1' but should refer to CA2.","section":"§5.3"},{"comment":"In line 4 of REC, the encoding is written as Enc_{n−2t}(v*) but should be Enc_{n−2t}(v_i), since a party encodes its own input.","section":"Appendix A, REC pseudocode"},{"comment":"The liveness clause contains a typo: 'they they all output' should be 'they all output'.","section":"§2, Reliable Agreement"},{"comment":"The word 'csumming' should be 'summing'.","section":"§5.3, Complexity of CA2"},{"comment":"Theorem 4.1 states only validity and consistency for SRA, but the CA1 liveness proof also relies on SRA liveness when all honest parties input the same value to SRA; the liveness argument should be stated explicitly.","section":"§4.1, Theorem 4.1"}],"recommendation":"major_revision","confidential_remarks":"The liveness flaw in EXT via REC is central and must be fixed before the paper can be accepted, but it looks like a localized pseudocode/guard error rather than an unfixable defect in the reduction idea. The CA2 code-property issue is more serious because it concerns whether the cited near-MDS codes actually support the claimed quadratic complexity; the authors need to verify this carefully. I therefore recommend major revision rather than outright rejection, but the next version must address both points head-on."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The core idea is better than the execution. The EXT reduction from multivalued BA to binary BA plus crusader agreement is genuinely new, and the two CA protocols are original. But as written, both central claims fail on close reading.\n\nFirst, EXT's liveness proof is wrong. When an honest party outputs ⊥ from ΠCA, it does not input to REC; it only multicasts ⊥ and inputs 0 to ΠBA. REC, as defined in Appendix A, only lets parties with inputs participate and output. So if ΠBA outputs 1, those ⊥-outputters reach line 18 with y_i = ⊥ and wait forever. Theorem 3.3 invokes REC totality for all honest parties, but totality only covers parties that actually run REC with an input. The proof of Lemma 3.2 anticipates the case where t+1 honest parties output v*, but it does not account for other honest parties simultaneously outputting ⊥, which crusader agreement explicitly allows. This is a real liveness hole, not a corner case.\n\nSecond, the CA2 pseudocode inverts the matching test. Lines 8-10 put non-matching symbol pairs into A_i, while the proofs of Lemmas 5.8 and 5.9 treat A_i as the set of matching parties. With the pseudocode as written, an execution with a common honest input makes every honest party add everyone else to B_i, multicast ⊥, and then output ⊥, violating validity. This is likely a typo -- CA1's version is correct -- but it is load-bearing because the proofs rely on the opposite convention.\n\nWhat the paper does well: the reduction framework, if repaired, would be a useful contribution; the use of almost-universal hashing and ECC symbols with a COOL-style preprocessing step is creative; the complexity accounting is careful and the related-work table is informative. The CA2 collision bound in Lemma 5.6 depends on a near-MDS code property cited from [30] rather than proved, but that is a minor concern next to the two bugs above.\n\nBottom line: this is not publishable as is. The errors are fixable in principle, but they are not cosmetic. I would still send it to review rather than desk-reject, because the core ideas deserve referee time and a major revision might bring them into working shape. For your reading group, it is a good example of how subtle liveness assumptions about subprotocols can break an extension proof.","headline":"Nice reduction idea, but two load-bearing bugs--EXT liveness and CA2 validity--break the central claims as written.","tokens_in":26818,"tokens_out":4717,"would_cite":false,"duration_ms":42435,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Multivalued asynchronous Byzantine agreement reduces to one binary agreement instance plus one crusader-agreement instance, at only $\\Theta(\\ell n+n^2)$ extra bits.","keywords":["Byzantine agreement","crusader agreement","asynchronous distributed algorithms","information-theoretic security","multivalued agreement","extension protocols","error-correcting codes","almost-universal hashing"],"falsifier":"Give CA2 an $(n,\\delta)$-code whose minimum distance is exactly $n-\\delta$, so two distinct messages can share $\\delta$ encoded symbols, while keeping the advertised symbol size $\\Theta(\\ell/\\delta+\\log(n/\\delta))$; Lemma 5.6's collision bound then becomes $(n-3t)/2$ instead of $(n-3t-1)/2$, and one can arrange KCA outputs so that honest parties pass the $n-t$ matching test for two different values, violating weak consistency.","tokens_in":25771,"feed_emoji":"🤝","tokens_out":13505,"duration_ms":117302,"temperature":0.7,"pith_summary":"Multivalued Byzantine agreement asks $n$ parties, up to $t<n/3$ of them byzantine, to agree on an $\\ell$-bit input. The paper tries to close the gap between binary and multivalued agreement in asynchronous networks: it gives a reduction EXT that turns any terminating binary Byzantine agreement protocol into an $\\ell$-bit Byzantine agreement protocol using one binary agreement call, one $\\ell$-bit crusader agreement call, a constant number of rounds, $\\Theta(n^2)$ extra messages, and $\\Theta(\\ell n+n^2)$ extra bits. Because the reduction needs multivalued crusader agreement, the paper also builds two information-theoretic crusader agreement protocols, CA1 and CA2, of independent interest. CA1 is statistically secure against $t<n/3$ faults using almost-universal hashing, and CA2 is perfectly secure against $t\\le n/(3+\\varepsilon)$ faults using error-correcting codes with a COOL-style preprocessing step. If correct, these give the first information-theoretic asynchronous Byzantine agreement extensions the authors are aware of that tolerate $t\\ge n/5$ with quadratic-in-$n$ communication overhead.","feed_headline":"Crusader agreement extends binary Byzantine agreement to ℓ-bit inputs","feed_subtitle":"Two information-theoretic protocols reach Θ(ℓn+n²) bits against up to n/3 Byzantine faults.","key_machinery":"The load-bearing machinery is the EXT reduction plus two equality-check layers. EXT uses REC, a terminating reconstruction protocol based on asynchronous data dissemination, so that a single binary Byzantine agreement vote chooses between one reconstructed value $v^*$ and $\\bot$; REC's totality converts a 1 vote into universal knowledge of $v^*$. CA1 uses an $\\varepsilon$-almost-universal keyed hash so pairs of parties can test input equality by comparing one hash per pair. CA2 replaces hashes with $(n,\\delta)$-error-correcting code symbols and adds KCA, a perfectly secure $(8/\\sigma)$-crusader agreement protocol; KCA limits the number of distinct non-$\\bot$ values that any honest party can see, and Lemma 5.6's collision bound keeps symbol coincidences below the threshold that would break weak consistency. The named complexity targets come from choosing $\\delta$ so that each encoded symbol has size $\\Theta(\\ell/n\\cdot\\min(1,\\varepsilon^2)+\\max(1,\\log(1/\\varepsilon)))$.","core_discovery":"The central claim is that crusader agreement is the right intermediate primitive for asynchronous Byzantine agreement extension. EXT runs an $\\ell$-bit crusader agreement, feeds any non-$\\bot$ output through a terminating reconstruction protocol REC (an asynchronous data dissemination variant with totality), and uses a single binary Byzantine agreement vote to decide whether everyone outputs that reconstructed value or the safe fallback $\\bot$. The binary input is 1 only after a party terminates REC, so REC's totality guarantees that a 1 vote makes every honest party learn the same value, while a 0 vote makes everyone output $\\bot$. Instantiating EXT with CA1 gives a statistically secure extension with $\\Theta(\\ell n+n^2(\\lambda+\\log n))$ bits of communication against $t<n/3$; instantiating with CA2 gives a perfectly secure extension with $O(\\ell n/\\min(1,\\varepsilon^2)+n^2\\max(1,\\log(1/\\varepsilon)))$ bits against $t\\le n/(3+\\varepsilon)$. The perfect protocol achieves this by replacing hash comparisons with error-correcting-code symbol comparisons and adding KCA, a $(8/\\sigma)$-crusader agreement preprocessing step adapted from COOL, to bound how many distinct non-$\\bot$ values survive.","pith_inferences":["An implicit design lesson of EXT is that weak consistency plus a totality-giving dissemination layer is enough to lift binary agreement to multivalued agreement; graded consensus, 2-crusader agreement, or vector agreement might replace crusader agreement and yield different complexity trade-offs.","If the near-MDS code family used by CA2 is validated, the collision-bounding pattern behind CA2 could be transplanted to perfectly secure reliable broadcast and multivalued broadcast extensions, since those primitives keep the more forgiving $n-t$ thresholds in the COOL-style preprocessing step.","CA1's communication carries a $\\lambda+\\log n$ factor from the hash length; explicit hash families with tighter collision bounds, or derandomized keys, might shave that factor without changing the protocol skeleton.","A natural stress test is to instantiate CA2 with Reed-Solomon codes (large symbols, standard proofs) versus the cited near-MDS codes; the claimed communication advantage collapses precisely in the symbol-size regime where the near-MDS property is doing the work."],"forward_implications":["Any terminating binary asynchronous Byzantine agreement protocol can be lifted to $\\ell$-bit inputs with one extra crusader agreement call, constant round overhead, $\\Theta(n^2)$ extra messages, and $\\Theta(\\ell n+n^2)$ extra bits.","The statistically secure instantiation EXT+CA1 achieves information-theoretic security against $t<n/3$ with $\\Theta(\\ell n+n^2(\\lambda+\\log n))$ bits of communication, matching the asymptotic cost of the best cryptographic extension in that regime.","The perfectly secure instantiation EXT+CA2 tolerates $t\\le n/(3+\\varepsilon)$ for any constant $\\varepsilon>0$ with $O(\\ell n+C_A+n^2)$ bits when $\\varepsilon$ is constant, where $C_A$ is the underlying binary BA communication cost; this matches A-COOL's asymptotic overhead while tolerating more faults.","Both extensions run the underlying binary Byzantine agreement only once, avoiding the $n$-fold runs or expected leader elections used by earlier perfect extensions.","The CA1 and CA2 protocols are themselves new multivalued crusader agreement protocols with constant rounds and $\\Theta(n^2)$ messages, so they can be reused as building blocks beyond BA extension."],"supporting_citations":[{"why":"Supplies the COOL protocol whose first two phases become the KCA preprocessing step, and defines the k-crusader agreement notion used in CA2.","marker":"[10]"},{"why":"Supplies the asynchronous data dissemination protocol that REC adapts, adding totality and termination.","marker":"[18]"},{"why":"Supplies the almost-universal hashing technique and the first O(ℓn+...) BA extension whose statistical equality checks CA1 follows.","marker":"[22]"},{"why":"Provides the perfectly secure asynchronous BA extension A-COOL that EXT+CA2 matches asymptotically while tolerating more faults.","marker":"[29]"},{"why":"Provides the near-MDS code family with symbol size Θ(ℓ/k+log(n/k)) and the recovery property CA2's collision bound assumes.","marker":"[30]"},{"why":"Provides the cryptographic extension baseline whose Θ(ℓn+n·CA+n²λ) complexity EXT+CA1 matches asymptotically and whose symbol-accumulation design EXT adapts.","marker":"[34]"},{"why":"Provides the universal classes of hash functions used to construct CA1's ε-almost-universal keyed hash.","marker":"[8]"},{"why":"Provides concurrent perfectly secure asynchronous BA extensions with n binary BA instances or expected leader elections, the overhead comparison for EXT+CA2.","marker":"[13]"},{"why":"Provides the terminating reliable agreement protocol used to give the underlying binary BA the totality and termination guarantee EXT requires.","marker":"[17]"}],"fun_headline_variants":["Crusader agreement: the bridge to multivalued Byzantine agreement","Reducing multivalued BA to binary BA with crusader agreement","Two new crusader protocols power info-theoretic Byzantine agreement","From binary to multivalued: crusader agreement does it efficiently"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"CA2's perfect security rests on the existence of near-MDS error-correcting codes in which any $\\delta$ of the $n$ encoded symbols already determine the message; the paper cites this family but does not prove its existence, and if the true minimum distance is $n-\\delta$ rather than $n-\\delta+1$, the collision bound that makes the protocol work degrades by one and the strict inequality $t\\le n/(3+\\varepsilon)$ can fail.","fun_headline_variants_meta":{"raw":{"variants":["Crusader agreement: the bridge to multivalued Byzantine agreement","Reducing multivalued BA to binary BA with crusader agreement","Two new crusader protocols power info-theoretic Byzantine agreement","From binary to multivalued: crusader agreement does it efficiently"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000333,"raw_usage":{"total_tokens":1941,"prompt_tokens":1129,"completion_tokens":812,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":745,"completion_tokens_details":{"reasoning_tokens":739}},"tokens_in":745,"tokens_out":812,"duration_ms":7547,"temperature":1.0,"reasoning_tokens":739,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T12:34:31.505917+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Give CA2 an $(n,\\delta)$-code whose minimum distance is exactly $n-\\delta$, so two distinct messages can share $\\delta$ encoded symbols, while keeping the advertised symbol size $\\Theta(\\ell/\\delta+\\log(n/\\delta))$; Lemma 5.6's collision bound then becomes $(n-3t)/2$ instead of $(n-3t-1)/2$, and one can arrange KCA outputs so that honest parties pass the $n-t$ matching test for two different values, violating weak consistency.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the COOL protocol whose first two phases become the KCA preprocessing step, and defines the k-crusader agreement notion used in CA2."},{"cited_title":"2025.Improved Explicit Near-Optimal Codes in the High-Noise Regimes","cited_arxiv_id":null,"evidence_quote":"Provides the near-MDS code family with symbol size Θ(ℓ/k+log(n/k)) and the recovery property CA2's collision bound assumes."}],"review_version":1}