{"id":"e1c04806-d101-46b3-8241-83138fa18412","arxiv_id":"2501.00214","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"OciorMVBA achieves error-free, information-theoretically secure asynchronous MVBA with expected O(n|w| log n + n^2 log q) communication bits under optimal resilience, plus O(1)-round variants.","lead":"The paper presents new asynchronous multi-valued validated Byzantine agreement protocols that let a group of computers agree on a message even when some nodes are dishonest and messages may be delayed, without needing signatures or hashes except for a shared randomness source. The main protocol, OciorMVBA, is error-free and information-theoretically secure, achieving near-linear communication in message size under optimal resilience n >= 3t+1.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"OciorMVBA's agreement and termination rely on Lemma 10, whose key Lemma 9 is imported without proof from the unpublished self-cited OciorCOOL preprint [7]; this is the main unverified load-bearing step.","rationale":"The reader's weakest_assumption identifies exactly the same structural dependency: the correctness of OciorMVBA rests on the imported OciorRBA lemmas from the unpublished OciorCOOL preprint. My stress-test pass found no counterexample to the recursive construction itself, and the paper's high-level structure is plausible: the good-resilience chain, the SHMDM propagation, the ABBBA biased-validity logic, and the recurrence for communication all appear internally coherent. However, the proof of Lemma 10 is not present in this manuscript; Lemma 9 is simply cited. Since these lemmas are necessary for both agreement and termination of the outer MVBA, the central claim is not fully established as written. I considered whether a more specific flaw exists in Algorithm 1's handling of the ordered election/repeat loop, but the for-loop over l in {0,1} combined with the good-child argument in Lemma 4 appears sufficient, so that is not the main issue. I also considered the unspecified black-box ABBA and the error-free/all-executions semantics, but those are secondary to the missing OciorRBA proof. Therefore, the reader's CONDITIONAL verdict is the right disposition: accept only after the imported lemmas are proved or independently verified.","tokens_in":22702,"tokens_out":18359,"duration_ms":188072,"concrete_test":"Independently re-derive Lemma 9 from Algorithm 4 alone: show that if a node reaches |S1_1| >= n-t in Phase 2 and another node reaches |S2_1| >= n-t, then every honest node that sets s^2_i=1 must have encoded the same Phase-1 message, using only the Phase 1/2 code and the ECC properties stated in the paper. If the derivation cannot be completed without invoking [7, Lemma 11], the paper's proof is incomplete, and the claim should remain conditional. As a complementary check, run an exhaustive small-scale search for n=4,t=1 (and n=7,t=2): enumerate all Phase-1 inputs and Byzantine corruption patterns, simulate Algorithm 4 under adversarial message ordering, and test whether any reachable state has two honest nodes with s^2=1 and distinct Phase-1 inputs; finding such a state would disprove Lemma 9, while finding none would increase but not establish confidence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The recursive proof of OciorMVBA depends at every level on OciorRBA's consistency and totality: Lemma 10 is asserted with proof 'similar to [7, Theorem 5]', and its central Lemma 9 is stated as 'directly derived from [7, Lemma 11]'. Both lemmas are about Algorithm 4, but the paper gives no self-contained derivation, no reduction to properties stated in this paper, and no independent argument. If Lemma 9 were false under adaptive corruption—e.g., if two honest nodes could both set s^2_i=1 in Phase 2 while having different Phase-1 input messages—then Lemma 10 fails, and with it both agreement and termination of OciorMVBA break at the first recursive level. The cited OciorCOOL preprint is not a peer-reviewed or independently verified source, so this is not a small presentation gap: it is an unproven necessary condition for the central claim. The protocol's own pseudocode for Phase 3 and the unspecified black-box ABBA add secondary uncertainty, but the missing OciorRBA proof is the load-bearing issue.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes three asynchronous multi-valued validated Byzantine agreement (MVBA) protocols. The main protocol, OciorMVBA, is claimed to be error-free and information-theoretically secure under only a common-coin assumption, achieving optimal resilience n >= 3t+1 with expected O(n|w| log n + n^2 log q) communication bits, O(n^2) messages, O(log n) rounds, and O(log n) common coins. The design is recursive: the network is partitioned into balanced sets S_2p and S_{2p+1}, and the protocol combines SHMDM, an OciorRBA building block, a newly introduced ABBBA primitive, an unspecified ABBA primitive, and common-coin elections. Two further protocols are sketched: OciorMVBArr, which relaxes resilience to n >= 5t+1 and claims O(1) expected rounds/coins, and OciorMVBAh, a hash-based protocol with optimal resilience and O(1) expected rounds/coins. Correctness is argued through a sequence of lemmas leading to Agreement, Termination, and External Validity; complexity is argued via a recurrence for communication bits and rounds.","tokens_in":22947,"tokens_out":10140,"duration_ms":104081,"significance":"If correct, OciorMVBA would be a significant result: it would achieve near-optimal communication and optimal resilience under minimal assumptions, avoiding signatures and hashing while remaining error-free in the common-coin model. The recursive partition idea and the use of a good-resilience network chain are interesting, and Lemmas 1 and 2 are simple and correct. The recurrence in Theorem 3 is consistent for communication bits, modulo minor presentation issues. However, the central correctness argument is not self-contained: the key Consistency and Totality properties of OciorRBA are imported from an unpublished self-cited preprint, and the ABBA primitive used at every recursive level is left unspecified. These gaps are load-bearing for the main claim, and the complexity analysis omits message and common-coin counts that appear in the abstract. The paper would be publishable only after these gaps are closed.","major_comments":[{"comment":"Lemma 9 is asserted to be \"directly derived from [7, Lemma 11]\" and Lemma 10 is said to be \"similar to [7, Theorem 5]\", but [7] is an unpublished arXiv preprint by the same author and no self-contained proof or reduction is given in this manuscript. These lemmas supply the Consistency and Totality properties of OciorRBA, which are used in Lemma 3 and Theorem 1 to establish Agreement and Termination of OciorMVBA. If Phase 2 of Algorithm 4 is inconsistent—for example, if two honest nodes set s_i^2=1 while holding different Phase-1 input messages—then honest nodes can output different values from OciorRBA after ABBA outputs 1, and both Agreement and Termination fail. A citation to an unpublished preprint is not sufficient for a central lemma; please provide a complete proof of Lemmas 9 and 10 within this paper or state OciorRBA's properties as an explicitly justified theorem with all supporting arguments included.","section":"§II-B, Lemmas 9–10; Algorithm 4"},{"comment":"The protocol invokes ABBA in Line 17 as a black box, but the manuscript never defines the properties of ABBA or supplies an implementation. Lemma 5 relies on the \"validity property of Byzantine agreement\" of this ABBA, and the recursive argument in Theorem 1 also relies on ABBA agreement and termination. Please specify the exact required properties (validity, agreement, termination) and either provide an ABBA protocol satisfying them for n ≥ 3t+1 under an adaptive adversary and without cryptographic assumptions, or give a precise reference with a proof. Without this, the correctness and the expected O(log n) round and common-coin claims are not self-contained.","section":"§II, Algorithm 1, Lines 15–17; Lemma 5"},{"comment":"The abstract claims expected O(n^2) messages and expected O(log n) common coins, but Theorem 3 analyzes only communication bits and rounds. No recurrence or argument is given for message complexity or for the total number of common-coin invocations across recursive levels and repeated ABBA/ABBBA uses. These quantities are part of the stated contribution and need a proof.","section":"Theorem 3 and abstract"},{"comment":"The pseudocode for honest nodes with s_i^2=0 is ambiguous: Line 59 says \"wait until receiving t~+1 ... messages, for all j in S[2]_1, for the same y = y*\", which is unclear about whether the wait condition is t~+1 matching symbols or one symbol from every honest node in S[2]_1, and whether this guarantees the OEC decoding condition at Line 66. This ambiguity matters because honest nodes with s_i^2=0 must terminate in Phase 3, and the termination proof for this case is compressed into one sentence in Lemma 10.","section":"Algorithm 4, Phase 3, Lines 59–61"},{"comment":"The two secondary protocols inherit similar gaps. OciorMVBArr in Algorithm 5 calls ABArr, described only by a citation to [17] with asserted O(1) rounds/coins and O(n|w|+n^2 log q) bits, and OciorMVBAh in Algorithm 8 again uses an unspecified ABBA. Moreover, no proof is given for the expected O(1) rounds and O(1) coins claimed for these protocols in the abstract; Theorems 4–6 and 7–9 establish only agreement, termination, and external validity. These complexity and implementation claims should be proved or explicitly deferred.","section":"§III and §IV"}],"minor_comments":[{"comment":"The phrase \"a protocol that that guarantees\" contains a doubled word; similarly, Lemma 3 contains \"hones nodes\" instead of \"honest nodes\".","section":"Section I, error-free protocol definition"},{"comment":"The base case is written as \"if m ≤ M\" with an undefined m; it should be \"if \\tilde n_p ≤ M\". Also, after the expansion, 2^J f_TB(M) is O(n|w|) when f_TB(M) = O(|w|), which is dominated by the O(n|w| log n) term; this should be stated explicitly.","section":"Theorem 3, recurrence base case"},{"comment":"The informal definition of SHMDM says \"all honest nodes are acting as senders\", but Algorithm 3 uses only nodes in S_{2p+θ} as senders for a given θ. This discrepancy should be clarified to avoid confusion about sender sets.","section":"Definition 5 and Algorithm 3"},{"comment":"The proof states that Ifinish[l]=1 implies at least \\tilde n_p - 2\\tilde t_p honest nodes set v_i=1 from OciorRBA; this inference is not immediate and should be expanded, especially because the relationship between receiving \\tilde n_p - \\tilde t_p READY messages and the number of honest v_i=1 holders depends on the as-yet-unspecified behavior of OciorRBA.","section":"Lemma 5, proof"}],"recommendation":"major_revision","confidential_remarks":"The main blocker is the reliance on the author's unpublished [7] for Lemmas 9–10, which are essential for the correctness of the flagship protocol. If the author can supply a self-contained proof of these lemmas and specify the ABBA primitive, the result would be a meaningful contribution. I would also ask the editor to consider whether black-box use of ABBA and of the Li–Chen protocol in the secondary sections is acceptable for the target venue, and whether the expected O(1) round/coin claims for Sections III–IV should be proved in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this is a genuine protocol family with a concrete complexity improvement, but the proof of the main protocol leans on two lemmas that are not proved here. Lemma 10, which gives the consistency and totality of the OciorRBA building block, is asserted with “the proof is similar to [7, Theorem 5],” and its key Lemma 9 is dismissed as “directly derived from [7, Lemma 11].” Reference [7] is an unpublished arXiv preprint by the same author. If those lemmas fail under adaptive corruption, both agreement and termination of OciorMVBA break at the first recursive level. I agree with the stress-test note: this is the load-bearing step and it is unverified.\n\nWhat is genuinely new and good: the recursive MVBA structure, the ABBBA and ACID primitives, and the SHMDM-based propagation are not in the prior MVBA literature, and the asymptotic claim is concrete—expected O(n|w| log n + n^2 log q) bits under n ≥ 3t+1, improving on Duan et al.'s O(n^2|w| + n^3 log n) signature-free MVBA. The recurrence in Theorem 3 is consistent and the ABBBA design is simple and plausible. The OciorMVBArr and OciorMVBAh variants give useful O(1)-round tradeoffs, even if they depend on the same imported OciorRBA/ABBA machinery.\n\nThe soft spots, in proportion: the missing OciorRBA proof is the major one. The paper gives no self-contained derivation of Lemma 9 or 10, no reduction to properties stated in this paper, and no independent verification. This is not a small presentation gap—it is a necessary condition for the central claim. Second, ABBA and ABArr are used as black boxes without concrete instantiations or citations to constructions that satisfy the required properties in this multi-valued, error-free setting. Third, the abstract claims expected O(n^2) messages, but Theorem 3 formally proves only bits and rounds; the message-count recurrence is not given. These are secondary but should be fixed in revision.\n\nWho this is for: protocol designers working on asynchronous Byzantine agreement and MPC building blocks. They will find the recursive approach and the complexity tradeoffs worth studying, provided the OciorRBA gap is closed. The paper is coherent on its own terms and the dependency on [7] is transparently flagged, so I do not read it as sloppy; it is incomplete.\n\nRecommendation: send it to peer review, but the referees should be explicitly instructed that acceptance requires either a self-contained proof of Lemmas 9 and 10 or a formal verification of the imported OciorRBA properties. With that condition, this is a credible contribution.","headline":"A plausible near-optimal MVBA construction whose central recursion is sound on its face, but the load-bearing OciorRBA consistency lemmas are imported unproved from an unpublished self-cited preprint; this is a real gap, not a cosmetic one.","tokens_in":23489,"tokens_out":1938,"would_cite":false,"duration_ms":22522,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that OciorMVBA, an error-free and information-theoretically secure asynchronous MVBA protocol, achieves consensus on a message $\\boldsymbol{w}$ with expected $O(n|\\boldsymbol{w}|\\log n + n^2\\log q)$ communication bits…","keywords":["multi-valued validated Byzantine agreement","asynchronous consensus","information-theoretic security","error-free protocol","common coin","recursive divide-and-conquer","error correction codes","asynchronous binary agreement"],"falsifier":"A concrete check would be a 4-node, 1-fault simulation of OciorMVBA with a common coin against an adaptive adversary that corrupts a node after the OciorRBA phase begins; the claim is false if two honest nodes ever terminate with different messages, if one honest node terminates while another never does, or if the imported OciorRBA property fails on a schedule where two honest Phase-2-confirming nodes hold different inputs.","tokens_in":22485,"feed_emoji":"🤝","tokens_out":12093,"duration_ms":112677,"temperature":0.7,"pith_summary":"This paper proposes three asynchronous multi-valued validated Byzantine agreement (MVBA) protocols, which let $n$ distributed nodes, up to $t$ of them dishonest, agree on one node's proposed message that passes an external predicate. The main protocol, OciorMVBA, claims to do this with expected $O(n|\\boldsymbol{w}|\\log n + n^2\\log q)$ communication bits, expected $O(n^2)$ messages, expected $O(\\log n)$ rounds, and expected $O(\\log n)$ common coins, under the optimal resilience $n \\geq 3t+1$. It is error-free and information-theoretically secure: given a common coin (a public randomness source all honest nodes see), it never violates agreement, termination, or validity in any execution, and it uses no signatures or hashes. If the proof is right, this brings asynchronous agreement on large messages close to the cost of simply sending the message once per node while removing every cryptographic assumption except the coin. Two companion protocols, OciorMVBArr and OciorMVBAh, make the same offer with expected $O(1)$ rounds and coins, the first at the relaxed resilience $n \\geq 5t+1$ and the second at optimal resilience with hash-based commitments.","feed_headline":"Crypto-free async consensus survives n/3 faulty nodes","feed_subtitle":"Claimed cost: O(n|w| log n + n^2 log q) bits, expected O(log n) rounds, no signatures or hashes.","key_machinery":"The load-bearing machinery is the recursive MVBA skeleton $\\mathrm{RMVBA}[(ID,p)]$ running on a binary tree of node subsets. Each level splits a set $S_p$ into two balanced halves, $S_{2p}$ and $S_{2p+1}$, and the recursion relies on the lemma that at least one half of any well-resilient set is itself well-resilient, so a chain from the root to a leaf is always good. Along that chain, SHMDM (strongly-honest-majority distributed multicast, where every honest node acts as a sender and coded symbols are exchanged) carries a value from a half back to the full set; OciorRBA reliably confirms it; a Ready-Finish-Confirm voting stage converts confirmation into readiness flags; ABBBA (a new biased binary primitive whose two inputs are readiness and finish bits) and ABBA then decide whether to stop or retry with the other half. The recurrence above converts the protocol into its communication bound.","core_discovery":"On its own terms, the paper's central discovery is that asynchronous MVBA can be made error-free and information-theoretically secure while keeping communication nearly linear in $n$ and in the message length: expected $O(n|\\boldsymbol{w}|\\log n + n^2\\log q)$ bits at $n \\geq 3t+1$. OciorMVBA reaches this by recursively partitioning the node set into balanced halves, following one chain of halves that retains good resilience down to a constant-size base case, and composing each level from four ingredients: strongly-honest-majority distributed multicast (SHMDM), the reliable Byzantine agreement subroutine OciorRBA, a new asynchronous biased binary agreement (ABBBA), and standard asynchronous binary agreement (ABBA). The paper proves agreement, termination, and external validity for OciorMVBA and shows that the per-level recurrence $f(\\tilde{n}) = O(\\tilde{n}|\\boldsymbol{w}| + \\tilde{n}^2\\log q) + f(\\lfloor \\tilde{n}/2\\rfloor) + f(\\lceil \\tilde{n}/2\\rceil)$ solves to the claimed bound. The relaxed-resilience variant OciorMVBArr and the hash-based variant OciorMVBAh follow the same disperse-and-decide pattern and are analyzed separately.","pith_inferences":["Editorial inference: the recursive skeleton is not obviously limited to MVBA; the same pattern of certifying readiness with SHMDM and ABBBA and then flipping one common coin could be transplanted to asynchronous common subset or atomic broadcast, where the cost of dropping signatures may be worth an extra $\\log n$ factor.","Editorial inference: the recurrence leaves the $\\log n$ factor only on the $n|\\boldsymbol{w}|$ term, which suggests that a protocol that could pick a well-resilient half with a single coin instead of recursing on both halves might reach $O(n|\\boldsymbol{w}| + n^2\\log q)$ at $n \\geq 3t+1$; OciorMVBA itself does not claim that stronger bound.","Editorial inference: because Lemmas 9 and 10 are not proved here, a reader who wants to deploy OciorMVBA should first audit the OciorRBA analysis in [7] against adaptive corruption; that is the one link in the chain not verified in this paper.","Editorial inference: a direct performance test would compare OciorMVBA against hash-based MVBA baselines at the same $n$ and message size; the measured gap would quantify the real-world price of avoiding all cryptographic assumptions."],"forward_implications":["With a constant-alphabet error-correcting code such as an expander code, $q$ is constant and OciorMVBA communicates $O(n|\\boldsymbol{w}|\\log n + n^2)$ bits while remaining signature-free and error-free at $n \\geq 3t+1$.","Because OciorMVBA is error-free, any implementation needs only a functioning common coin; signature verification and hash-based commitments can be dropped from the critical path.","OciorMVBArr gives the same error-free, information-theoretic guarantee with expected $O(1)$ rounds and coins, at the cost of the relaxed resilience $n \\geq 5t+1$.","OciorMVBAh restores optimal resilience $n \\geq 3t+1$ with expected $O(1)$ rounds and coins, paying $O(n^3)$ bits and relying on hash-based vector commitments.","The recursion can stop at any constant-size subnetwork and delegate to an arbitrary inefficient MVBA at the leaves without changing the asymptotic cost."],"supporting_citations":[{"why":"Defines the MVBA problem whose agreement, termination, and external-validity properties the new protocols implement.","marker":"[1]"},{"why":"Proves deterministic asynchronous agreement impossible, which motivates the common-coin assumption shared by all three protocols.","marker":"[3]"},{"why":"Gives constant-alphabet expander codes, the example that makes $q$ constant and the $n^2\\log q$ term $n^2$.","marker":"[4]"},{"why":"Introduces the unique agreement (UA) and honest-majority distributed multicast (HMDM) primitives, along with the COOL protocol, on which the recursive design builds.","marker":"[5]"},{"why":"Extends the COOL line to optimal error-free multi-valued Byzantine agreement in the BA setting, providing the foundation for OciorRBA.","marker":"[6]"},{"why":"Supplies OciorRBA and OciorRBC; Lemmas 9 and 10 of this paper import its consistency and totality results without reproof.","marker":"[7]"},{"why":"Defines online error correction, the decode-as-symbols-arrive procedure used by SHMDM and OciorRBA in the asynchronous schedule.","marker":"[16]"},{"why":"Provides the asynchronous Byzantine agreement subroutine that OciorMVBArr calls as ABArr at $n \\geq 5t+1$.","marker":"[17]"}],"fun_headline_variants":["Error-free async MVBA with near-linear communication","No crypto, no hashes: async consensus at 1/3 faults","Async MVBA: error-free, IT-secure, near-optimal","Fault-tolerant consensus without crypto or hashes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire agreement and termination proof leans on an imported claim, not proved in this paper, that the OciorRBA subroutine always delivers one common message to the honest nodes that confirm a value; if an adaptive adversary can make that subroutine inconsistent or fail to terminate, OciorMVBA's guarantees collapse.","fun_headline_variants_meta":{"raw":{"variants":["Error-free async MVBA with near-linear communication","No crypto, no hashes: async consensus at 1/3 faults","Async MVBA: error-free, IT-secure, near-optimal","Fault-tolerant consensus without crypto or hashes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0007,"raw_usage":{"total_tokens":3292,"prompt_tokens":1207,"completion_tokens":2085,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":823,"completion_tokens_details":{"reasoning_tokens":2014}},"tokens_in":823,"tokens_out":2085,"duration_ms":16003,"temperature":1.0,"reasoning_tokens":2014,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:57:45.521128+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check would be a 4-node, 1-fault simulation of OciorMVBA with a common coin against an adaptive adversary that corrupts a node after the OciorRBA phase begins; the claim is false if two honest nodes ever terminate with different messages, if one honest node terminates while another never does, or if the imported OciorRBA property fails on a schedule where two honest Phase-2-confirming nodes hold different inputs.","supporting_citations":[{"cited_title":"Secure and efficient asynchronous broadcast protocols,","cited_arxiv_id":null,"evidence_quote":"Defines the MVBA problem whose agreement, termination, and external-validity properties the new protocols implement."},{"cited_title":"Impossibility of distributed consensus with one faulty process,","cited_arxiv_id":null,"evidence_quote":"Proves deterministic asynchronous agreement impossible, which motivates the common-coin assumption shared by all three protocols."},{"cited_title":"Asynchronous secure computation,","cited_arxiv_id":null,"evidence_quote":"Defines online error correction, the decode-as-symbols-arrive procedure used by SHMDM and OciorRBA in the asynchronous schedule."}],"review_version":1}