{"id":"bed8bdee-bc1d-4ee0-adb7-db4b637e15b3","arxiv_id":"2501.11788","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"OciorABA achieves error-free, information-theoretically secure asynchronous Byzantine agreement with O(nℓ+n^3 log q) expected bits and O(1) expected rounds under n ≥ 3t+1.","lead":"This paper claims a new protocol, OciorABA, that lets a network of n computers reach agreement on a message even when up to one third are malicious, without signatures or hashes. The stated payoff is an n-fold improvement in expected communication over prior error-free asynchronous agreement methods, while keeping the expected number of rounds constant.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"APVA's finite for-loop admits positive-probability non-terminating executions, so OciorABA is not error-free as written.","rationale":"I checked the reader's weakest assumption against the full text and find it is the decisive defect. Algorithm 3's for-loop is bounded at n and has no failure branch; the only output statement is conditional on b'=1, which the proof ties to l being in I*. Since I* is only guaranteed to contain n-2t honest nodes, the probability that none of n independent uniform draws hits I* is bounded below by (t/n)^n and is strictly positive for every t>=1. Thus the protocol text does not even terminate with probability 1, let alone in all executions. This is an internal inconsistency between the pseudocode and Theorem 4, not a disagreement with an external consensus. The high-level erasure-code decoding in Algorithm 2 and the ABBBA restatement are plausible, and a corrected unbounded retry loop would likely restore the claimed O(1) expected rounds because each round succeeds with constant probability; however, that correction is not present and Theorem 7's complexity proof is only asserted, not derived. I therefore retain the reader's REJECT verdict.","tokens_in":16590,"tokens_out":10363,"duration_ms":104086,"concrete_test":"Run an exhaustive or Monte-Carlo simulation of Algorithm 3 exactly as written for n=4, t=1, I*={3,4}, with Election[(ID,r)] uniform on {1,2,3,4}. Enumerate all 4^4 coin sequences: the 16 sequences whose four draws are all in {1,2} complete the loop with no output, demonstrating a positive-probability execution that falsifies Theorem 4. A fully analytic check is to compute Pr[intersection_{r=1..n} {l_r not in I*}] >= (t/n)^n > 0 under the protocol's own uniformity assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 3 (APVA) lines 4-15 contain the only termination path of the entire OciorABA construction: `for r in [1:n]`, draw `l <- Election[(ID,r)]`, run ABBBA/ABBA, and `if b' = 1 then output cl`. There is no retry, no `else`, and no return after the loop. Termination therefore requires that at least one of the n coin draws falls in I*, the set of honest nodes that completed ACID* dispersal. The paper's own integrity property gives |I*| >= n-2t, so for n >= 3t+1 and t >= 1, each draw misses I* with probability at least t/n and at most 2t/(3t+1); after n independent draws the probability that every draw misses is at least (t/n)^n > 0. Hence there are positive-probability executions in which Algorithm 3 falls through the loop without output. This contradicts Theorem 4's unconditional termination and the abstract's 'error-free (all executions)' claim. The proof of Lemma 7 assumes 'some round r' with l in I* but never shows one exists inside the loop bound; if the intended design is repeat-until-success, that is not what the pseudocode says, and the expected-rounds/communication analysis would have to be restated for that variant.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two multi-valued asynchronous Byzantine agreement protocols, OciorABA* and OciorABA, together with a new primitive called asynchronous partial vector agreement (APVA). OciorABA* runs n parallel reliable-broadcast and binary-agreement instances and claims expected communication O(nℓ + n^3 log q) bits and O(log n) rounds. OciorABA replaces the per-index binary agreement with one APVA instance and claims expected communication O(nℓ + n^3 log q) bits and O(1) expected rounds under n ≥ 3t + 1. The APVA protocol (Algorithm 3) combines an ACID* dispersal layer, an ABBBA protocol taken from reference [12], a common coin, and a bounded round loop. Theorems 4–7 make unconditional termination, validity, consistency, and complexity claims for the resulting protocol.","tokens_in":16901,"tokens_out":9745,"duration_ms":109531,"significance":"If established, the claimed communication bound O(nℓ + n^3 log q) would improve the best prior error-free ABA result at optimal resilience, O(nℓ + n^4 log n), and the O(1) expected round complexity would be an additional advance. The high-level idea of using APVA to compress the vector-agreement phase is plausible, and the manuscript provides full pseudocode that makes the construction concretely checkable. However, the current version has load-bearing termination and indexing gaps, and the complexity proof is skeletal; the safety properties are mostly compositional. The contribution is potentially publishable after substantial repair, but the central claims are not established as written.","major_comments":[{"comment":"The only termination path in APVA is the finite loop `for r ∈ [1:n]`, with no retry, no else branch, and no return after the loop. The proof of Lemma 7 assumes that at some round r the common coin output l lies in I*, but it never proves that such a round occurs within the n iterations. Since I* satisfies |I*| ≥ n − 2t, for n ≥ 3t+1 and t ≥ 1 each coin draw misses I* with probability at least t/n > 0; after n independent draws, the probability that every draw misses is at least (t/n)^n > 0. In such an execution, Algorithm 3 exits the loop without producing any output, so Lemma 7, Theorem 4, and the abstract's 'error-free in all executions' claim are false as written. Replacing the finite loop by a repeat-until-success loop would repair termination, but that variant is not what is defined or analyzed in the manuscript.","section":"Algorithm 3, lines 4–15; Lemma 7; Theorem 4"},{"comment":"The proof of Theorem 7 does not analyze the expected number of APVA rounds. It states that 'The other communication cost in APVA is expected O(n^3) bits' and that the expected round complexity is O(1), but it gives no success-probability calculation and no bound on the number of iterations. As written, the expectation is not even finite because the finite loop in Algorithm 3 can fail with positive probability. After switching to an unbounded loop, the authors need to prove a constant per-round success probability (for example, using |I*| ≥ n − 2t) and then re-derive both the expected round complexity and the expected communication cost; this analysis is missing.","section":"Theorem 7"},{"comment":"The ELECTION messages in ACID* do not carry the index i of the completed dispersal instance. Line 23 sends (\"ELECTION\", ID) after receiving n − t (\"FINISH\", ID*, i) messages for a particular i, but line 25 triggers on any n − t (\"ELECTION\", ID) messages. Those messages may refer to different dispersal instances, so a node can return from ACID* before there exists an index set I* with the property required by Definition 5 and used in Lemma 7. The pseudocode must either include the index in ELECTION and require n − t completion messages for the same index, or prove that heterogeneous completion messages still imply the required I*; no such proof appears.","section":"Algorithm 4, lines 23–29"}],"minor_comments":[{"comment":"There are typographical issues: 'understating' should be 'understanding', and the table column 'Cryptographic Assumption (Expect for Common Coin)' should read 'Except for Common Coin'; in the same column, 'Non' should be 'None'.","section":"Section I and Table I"},{"comment":"The sentinel notation `ϕ := 2` in the comments is confusing because ϕ is elsewhere described as a special missing-value marker; the paper should state unambiguously that 2 is an internal encoding of ϕ, not a third data value.","section":"Algorithms 2 and 3"},{"comment":"The proof of Lemma 6 concludes that an output vector satisfies ˆv[j] ≠ 0 for honest j, but the output vector may have missing entries; the statement is fine, yet the proof would be clearer if it explicitly separated non-missing entries from missing entries before applying the APVA Validity property.","section":"Section III-B, Lemma 6"}],"recommendation":"major_revision","confidential_remarks":"The protocol relies on two same-author arXiv preprints, OciorRBC [8] and OciorMVBA [12], for its core reliable broadcast and ABBBA primitives. Those dependencies are load-bearing and are not independently verified or included in this manuscript; the editor may wish to check their publication status. I did not make this a main technical comment because the termination, complexity, and indexing gaps already require major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Take this one: the interesting idea is real, but the protocol is not error-free as written. The APVA subroutine in Algorithm 3 loops over r=1..n and outputs only if a coin draw lands in I*. Since I* can be as small as n-2t honest nodes, each draw misses with probability at least t/n, so with probability at least (t/n)^n the loop exits without output. That contradicts Theorem 4's unconditional termination and the abstract's 'all executions' claim. The proof of Lemma 7 assumes a round r with l in I* but never shows one has to occur inside the loop bound. If the intended design was repeat-until-success, the pseudocode doesn't say that, and the complexity analysis would need to be restated.\n\nCredit where due: the claimed improvement over the O(n^4 log n) of Nayak et al. would be a genuine factor-n gain, and APVA is a new primitive not in the cited Patra, Nayak et al., or Li-Chen work. The high-level structure (encode, reliably broadcast, vote on symbols, decode from ABBA outcomes) is sound and follows the familiar OciorCOOL/MVBA pattern. The erasure-code logic and the round/communication arithmetic are plausible.\n\nThe other soft spots are secondary. The APVA complexity proof is asserted rather than derived—the proof of Theorem 7 just states the cost. The core utilities OciorRBC [8] and ABBBA [12] are same-author preprints, not independently verified; that's a real concern in this area, but it's not the reason to reject.\n\nBottom line: the paper as written cannot be accepted. The termination bug is load-bearing, not cosmetic. That said, it's also fixable—make the loop repeat until a good draw, and the expected round/communication bounds likely survive. So this is a candidate for a serious but major-revision review, not a desk reject. I'd send it out, telling the referee to check the revised APVA loop and the complexity proof closely.","headline":"The claimed O(n^3 log q) error-free ABA does not hold as written: APVA's finite loop can fail to terminate with positive probability, so the paper needs a rewrite before it can be taken seriously.","tokens_in":17429,"tokens_out":3583,"would_cite":false,"duration_ms":34982,"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":"OciorABA is an error-free, information-theoretically secure multi-valued ABA protocol that reaches consensus on an $\\ell$-bit message with expected communication $O(n\\ell + n^3 \\log q)$ bits and expected $O(1)$ rounds under $n \\ge 3t+1$.","keywords":["asynchronous Byzantine agreement","error-free consensus","information-theoretic security","partial vector agreement","reliable broadcast","common coin","erasure codes","optimal resilience"],"falsifier":"Run APVA with a fixed $n=4,t=1$ and an adversary that forces the common coin outputs to be the two dishonest indices in every round; with the printed finite for-loop, no honest node ever outputs, which would refute the claim of termination in all executions. If the proof instead intends repeat-until-success, the same test should confirm that the expected number of rounds until a coin output lands in $I^*$ is at most $3$, and observing a substantially larger expected number would refute the $O(1)$-round claim.","tokens_in":16370,"feed_emoji":"⚡","tokens_out":8458,"duration_ms":84536,"temperature":0.7,"pith_summary":"This paper proposes OciorABA, an asynchronous Byzantine agreement protocol that is error-free and information-theoretically secure, meaning it uses no signatures or hashes beyond a common coin, and it works with the optimal resilience $n \\ge 3t+1$: among $n$ nodes, up to $t$ can be dishonest. The protocol aims to let the nodes agree on an $\\ell$-bit message with expected communication $O(n\\ell + n^3 \\log q)$ bits and expected round complexity $O(1)$, where $q$ is the alphabet size of the erasure code used inside. If these claims hold, OciorABA improves the best previous expected communication for this setting from $O(n^4 \\log n)$ to $O(n^3 \\log q)$ bits, and to $O(n\\ell + n^3)$ when a constant-alphabet erasure code is used. The central new object is a primitive the paper calls asynchronous partial vector agreement (APVA), in which nodes agree on a common vector that may have some positions missing; OciorABA uses a single APVA call in place of many binary agreement instances.","feed_headline":"New protocol cuts Byzantine agreement cost to O(n^3)","feed_subtitle":"OciorABA agrees on ℓ-bit messages in expected O(1) rounds under optimal resilience, with no signatures or hashes.","key_machinery":"The load-bearing object is the APVA primitive (Algorithm 3). It takes $n$ input vectors over $\\{0,1,\\phi\\}$, where $\\phi$ marks a missing entry, and outputs a common vector $\\hat{v}$ with at least $n-t$ non-missing entries, each traceable to an honest input. Internally, an ACID-style dispersal phase (Algorithm 4) collects ready and finish flags for each value and leader, and then APVA runs a sequence of rounds; in each round a common coin selects a leader index $l$, a biased binary agreement decides whether leader $l$'s vector $c_l$ should be used, and if so the nodes run another round of biased binary agreements on the non-missing entries of $c_l$. A round succeeds when the coin output lies in $I^*$, the set of honest nodes that completed dispersal; the output is then $c_l$. This single subroutine replaces the $n$ parallel binary Byzantine agreement instances of the simpler protocol and is the reason the expected round count drops to $O(1)$.","core_discovery":"The central claim is that OciorABA achieves termination, consistency, and validity in every execution, with no cryptographic assumptions beyond a common coin, under $n \\ge 3t+1$, while using expected $O(n\\ell + n^3 \\log q)$ bits and $O(1)$ rounds. Each node encodes its message with an erasure code, reliably broadcasts its own symbol, and feeds a binary vote for each received symbol into APVA. APVA returns a common partial vector $\\hat{v}$ with at least $n-t$ non-missing entries; if fewer than $t+1$ entries are $1$, honest nodes output $\\bot$, otherwise they take the first $t+1$ indices marked $1$, recover the corresponding broadcast symbols, decode, and output the same message. The paper also gives a simpler variant, OciorABA$^\\star$, with the same communication bound but $O(\\log n)$ expected rounds, which uses $n$ parallel binary agreements; OciorABA replaces those with one APVA call to reduce the expected round complexity to $O(1)$.","pith_inferences":["The proof of expected $O(1)$ rounds implicitly treats Algorithm 3's finite loop as a repeat-until-success loop; if the pseudocode is read literally as exactly $n$ draws, a run in which the common coin never selects a completed honest leader would not terminate, so the unconditional 'all executions' wording depends on that interpretation.","A concrete way to make the expectation explicit is to replace the loop with an unbounded while-loop and note that each draw hits $I^*$ with probability at least $(n-2t)/n$, so the expected number of draws is $O(1)$ only under the retry reading.","APVA is defined only for binary vectors, but the ACID/ABBBA skeleton suggests it could be adapted to larger alphabets or to weighted partial vectors, which would broaden its use beyond this ABA construction.","The asymptotic gain is largest when the message length $\\ell$ is small relative to $n^3$; in the opposite regime the $n\\ell$ term dominates, so the practical benefit of OciorABA depends on the constant inside $O(n^3 \\log q)$."],"forward_implications":["If OciorABA is correct, error-free multi-valued ABA at optimal resilience improves from expected $O(n^4 \\log n)$ total communication to $O(n\\ell + n^3 \\log q)$, and to $O(n\\ell + n^3)$ for constant alphabet $q$.","The $O(\\log n)$-round variant OciorABA$^\\star$ gives a trade-off: the same communication bound with fewer subroutines, but slower expected termination than OciorABA.","APVA becomes a reusable primitive: any protocol that only needs agreement on a partial vector with at least $n-t$ known entries can call it instead of solving many binary agreement instances.","Because the design is information-theoretic and signature-free apart from the common coin, it avoids public-key costs and remains secure against computationally unbounded adversaries."],"supporting_citations":[{"why":"supplies the OciorRBC reliable broadcast used for each leader's coded symbol, whose per-instance cost enters the communication bound.","marker":"[8]"},{"why":"supplies the ACID definitions and the ABBBA subroutine that APVA invokes, including the algorithm restated as Algorithm 5.","marker":"[12]"},{"why":"the prior best error-free ABA at $n \\ge 3t+1$ with $O(n\\ell + n^4 \\log n)$ expected communication, which OciorABA aims to beat.","marker":"[5]"},{"why":"the earlier $n \\ge 3t+1$ error-free ABA baseline with $O(n\\ell + n^5 \\log n)$ expected communication.","marker":"[10]"},{"why":"an error-free ABA with lower communication but suboptimal resilience $n \\ge 5t+1$, providing the comparison for the resilience-communication trade-off.","marker":"[11]"},{"why":"supplies constant-alphabet error-correcting codes, which make $q$ constant and give the simplified final complexity statement.","marker":"[9]"}],"fun_headline_variants":["OciorABA: error-free Byzantine agreement in O(1) rounds","Asynchronous BFT hits O(1) rounds, O(n^3) communication","OciorABA: optimal-resilience ABA without signatures or hashes","New APVA primitive yields constant-round error-free ABA","Error-free Byzantine agreement: constant rounds, optimal resilience"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the random common coin will eventually pick a completed honest leader; as printed, the subroutine tries only $n$ coin draws with no retry, so the protocol relies on reading that loop as repeating until a success occurs.","fun_headline_variants_meta":{"raw":{"variants":["OciorABA: error-free Byzantine agreement in O(1) rounds","Asynchronous BFT hits O(1) rounds, O(n^3) communication","OciorABA: optimal-resilience ABA without signatures or hashes","New APVA primitive yields constant-round error-free ABA","Error-free Byzantine agreement: constant rounds, optimal resilience"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00098,"raw_usage":{"total_tokens":4181,"prompt_tokens":986,"completion_tokens":3195,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":602,"completion_tokens_details":{"reasoning_tokens":3102}},"tokens_in":602,"tokens_out":3195,"duration_ms":25190,"temperature":1.0,"reasoning_tokens":3102,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:53:30.790598+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run APVA with a fixed $n=4,t=1$ and an adversary that forces the common coin outputs to be the two dishonest indices in every round; with the printed finite for-loop, no honest node ever outputs, which would refute the claim of termination in all executions. If the proof instead intends repeat-until-success, the same test should confirm that the expected number of rounds until a coin output lands in $I^*$ is at most $3$, and observing a substantially larger expected number would refute the $O(1)$-round claim.","supporting_citations":[{"cited_title":"Improved extension protocols for Byzantine broadcast and agreement,","cited_arxiv_id":null,"evidence_quote":"the prior best error-free ABA at $n \\ge 3t+1$ with $O(n\\ell + n^4 \\log n)$ expected communication, which OciorABA aims to beat."},{"cited_title":"Error-free multi-valued broadcast and Byzantine agreement with optimal communication complexity,","cited_arxiv_id":null,"evidence_quote":"the earlier $n \\ge 3t+1$ error-free ABA baseline with $O(n\\ell + n^5 \\log n)$ expected communication."},{"cited_title":"Communication-efficient signature-free asynchronous Byzantine agreement,","cited_arxiv_id":null,"evidence_quote":"an error-free ABA with lower communication but suboptimal resilience $n \\ge 5t+1$, providing the comparison for the resilience-communication trade-off."},{"cited_title":"Expander codes,","cited_arxiv_id":null,"evidence_quote":"supplies constant-alphabet error-correcting codes, which make $q$ constant and give the simplified final complexity statement."}],"review_version":1}