REVIEW 5 major objections 4 minor 2 cited by
OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA
T0 review · 5 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (5)
- [§II-B, Lemmas 9–10; Algorithm 4] 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.
- [§II, Algorithm 1, Lines 15–17; Lemma 5] 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.
- [Theorem 3 and abstract] 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.
- [Algorithm 4, Phase 3, Lines 59–61] 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.
- [§III and §IV] 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.
minor comments (4)
- [Section I, error-free protocol definition] The phrase "a protocol that that guarantees" contains a doubled word; similarly, Lemma 3 contains "hones nodes" instead of "honest nodes".
- [Theorem 3, recurrence base case] 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.
- [Definition 5 and Algorithm 3] 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.
- [Lemma 5, proof] 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.
Circularity Check
OciorMVBA's agreement and termination ultimately rest on Lemma 10, whose key Lemma 9 is imported without proof from the same author's unpublished OciorCOOL preprint [7]; this is load-bearing self-citation rather than construction-level circularity.
-
self citation load bearing
[Section II-B, Lemma 9 (used by Lemma 10 and Theorem 1)]
"Lemma 9. [7, Lemma 11] Assume that Sp has good resilience. If ABBA[(ID, p, l,˜np, ˜tp)] outputs 1, then all of the honest nodes who set s[2] i = 1 in Phase 2 of OciorRBA [(ID, p, l)] should have the same input message w⋆ at the beginning of Phase 1 of OciorRBA[(ID, p, l)], for some w⋆, for l ∈ {0, 1}. Proof. The result is directly derived from [7, Lemma 11]."
The proof of Lemma 10, the only argument for OciorRBA's Consistency and Totality, depends on Lemma 9, which is asserted to be 'directly derived from [7, Lemma 11]', and on '[7, Theorem 5]'. Reference [7] is the same author's unpublished OciorCOOL preprint (arXiv:2409.06008). The paper supplies no proof of Lemma 9 or Theorem 5 here, and no independent verification, implementation, or external reproduction is cited. Theorem 1 then builds the recursive agreement and termination argument on Lemma 10 via Lemmas 3 and 4. Thus the central correctness claim of OciorMVBA reduces to an unverified self-citation: if Lemma 9 fails, both agreement and termination break at the first recursive level. This is load-bearing self-citation, though not a definitional or fit-based equivalence.
full rationale
The main positive contribution, the recursive OciorMVBA construction with expected O(n|w| log n + n^2 log q) communication, is not circular by construction: the complexity proof solves a recurrence, external validity is checked by the predicate test, and no fitted parameter is renamed as a prediction. However, the agreement and termination proof is not self-contained. Theorem 1 depends on Lemmas 3 and 4, both of which invoke Lemma 10, the Consistency and Totality properties of OciorRBA. Lemma 10's proof is 'similar to [7, Theorem 5]' and its central Fact 2 is Lemma 9, which is stated as 'directly derived from [7, Lemma 11]', where [7] is the same author's unpublished OciorCOOL preprint. The paper does not prove or independently reproduce the needed OciorRBA Phase-1/Phase-2 property; if that imported lemma fails, agreement and termination break at the first recursive level. The OciorMVBArr protocol also cites the author-coauthored Li-Chen ABA [17], but [17] is a peer-reviewed ISIT publication and is less concerning than the unpublished [7]. Overall, this is load-bearing self-citation without independent support, but it is not a definitional or fit-based reduction, so the appropriate score is 4.
Assumptions & free parameters
free parameters (1)
- M (recursion cutoff)
assumptions (6)
- domain assumption Common coin Election[id] with termination, consistency, uniform distribution, and unpredictability exists.
- domain assumption There exists an error-free, IT-secure asynchronous binary Byzantine agreement (ABBA) with O(1) expected rounds and O(1) coins under n >= 3t+1.
- ad hoc to paper OciorRBA from [7] satisfies the consistency and totality properties stated in Lemmas 9 and 10.
- domain assumption An inefficient error-free, IT-secure MVBA (IneMVBA) exists for any constant-size network.
- domain assumption The Li-Chen [17] asynchronous Byzantine agreement protocol can be used in multi-valued form as ABArr under n >= 5t+1.
- standard math Reed-Solomon and Expander codes satisfy the stated online error correction conditions.
Cite this review
Pith. "Pith review of OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA." pith.science (2026). https://pith.science/paper/OERXNRG2
@misc{pith2026250100214,
author = {Pith},
title = {Pith review of: OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA},
year = {2026},
howpublished = {\url{https://pith.science/paper/OERXNRG2}},
note = {Machine review of arXiv:2501.00214}
}
abstract
In this work, we propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA. This protocol achieves MVBA consensus on a message $\boldsymbol{w}$ 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 optimal resilience $n \geq 3t + 1$ in an $n$-node network, where up to $t$ nodes may be dishonest. Here, $q$ denotes the alphabet size of the error correction code used in the protocol. When error correction codes with a constant alphabet size (e.g., Expander Codes) are used, $q$ becomes a constant. An MVBA protocol that guarantees all required properties without relying on any cryptographic assumptions, such as signatures or hashing, except for the common coin assumption, is said to be information-theoretically secure (IT secure). Under the common coin assumption, an MVBA protocol that guarantees all required properties in all executions is said to be error-free. We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^2 \log n)$ communication bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under a relaxed resilience (RR) of $n \geq 5t + 1$. Additionally, we propose a hash-based asynchronous MVBA protocol, called OciorMVBAh. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^3)$ bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under optimal resilience $n \geq 3t + 1$.
Figures
Forward citations
Cited by 2 Pith papers
-
Extending Asynchronous Byzantine Agreement with Crusader Agreement
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.
-
OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement
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.
Reference graph
Works this paper leans on
-
[7]
OciorCOOL: Faster Byzantine agreement and reliable broadcast,
——, “OciorCOOL: Faster Byzantine agreement and reliable broadcast,” Sep. 2024, available on ArXiv: https://arxiv.org/abs/2409.06008
arXiv 2024
-
[2]
Reaching agreement in the presence of faults,
M. Pease, R. Shostak, and L. Lamport, “Reaching agreement in the presence of faults,” Journal of the ACM, vol. 27, no. 2, pp. 228–234, Apr. 1980
1980
-
[17]
Communication-efficient signature-free asynchronous Byzantine agreement,
F. Li and J. Chen, “Communication-efficient signature-free asynchronous Byzantine agreement,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2021
2021
-
[1]
Secure and efficient asynchronous broadcast protocols,
C. Cachin, K. Kursawe, F. Petzold, and V . Shoup, “Secure and efficient asynchronous broadcast protocols,” in Advances in Cryptology– CRYPTO 2001. Lecture Notes in Computer Science , vol. 2139, Aug. 2001
work page 2001
-
[3]
Impossibility of distributed consensus with one faulty process,
M. Fischer, N. Lynch, and M. Paterson, “Impossibility of distributed consensus with one faulty process,” Journal of the ACM , vol. 32, no. 2, pp. 374–382, Apr. 1985
work page 1985
-
[4]
Expander codes,
M. Sipser and D. Spielman, “Expander codes,” IEEE Trans. Inf. Theory , vol. 42, no. 6, pp. 1710–1722, Nov. 1996
1996
-
[5]
Fundamental limits of Byzantine agreement,
J. Chen, “Fundamental limits of Byzantine agreement,” 2020, available on ArXiv: https://arxiv.org/pdf/2009.10965.pdf
arXiv 2020
-
[6]
Optimal error-free multi-valued Byzantine agreement,
——, “Optimal error-free multi-valued Byzantine agreement,” in International Symposium on Distributed Computing (DISC) , Oct. 2021
2021
Show all 17 references
-
[8]
Asymptotically optimal validated asynchronous Byzantine agreement,
I. Abraham, D. Malkhi, and A. Spiegelman, “Asymptotically optimal validated asynchronous Byzantine agreement,” in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) , Jul. 2019, pp. 337–346
2019
-
[9]
Dumbo-MVBA: Optimal multi-valued validated asynchronous Byzantine agreement, revisited,
Y . Lu, Z. Lu, Q. Tang, and G. Wang, “Dumbo-MVBA: Optimal multi-valued validated asynchronous Byzantine agreement, revisited,” in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) , Jul. 2020, pp. 129–138
2020
-
[10]
FIN: Practical signature-free asynchronous common subset in constant time,
S. Duan, X. Wang, and H. Zhang, “FIN: Practical signature-free asynchronous common subset in constant time,” in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security , 2023, pp. 815–829
2023
-
[11]
Making hash-based MVBA great again,
H. Feng, Z. Lu, T. Mai, and Q. Tang, “Making hash-based MVBA great again,” Mar. 2024, available on: https://eprint.iacr.org/2024/479
2024
-
[12]
Toward optimal-complexity hash-based asynchronous MVBA with optimal resilience,
J. Komatovic, J. Neu, and T. Roughgarden, “Toward optimal-complexity hash-based asynchronous MVBA with optimal resilience,” Oct. 2024, available on ArXiv: https://arxiv.org/abs/2410.12755
2024 arXiv
-
[13]
Polynomial codes over certain finite fields,
I. Reed and G. Solomon, “Polynomial codes over certain finite fields,” Journal of the Society for Industrial and Applied Mathematics , vol. 8, no. 2, pp. 300–304, Jun. 1960
1960
-
[14]
Roth, Introduction to coding theory
R. Roth, Introduction to coding theory . Cambridge University Press, 2006
2006
-
[15]
Nonbinary BCH decoding (abstr.),
E. Berlekamp, “Nonbinary BCH decoding (abstr.),” IEEE Trans. Inf. Theory , vol. 14, no. 2, pp. 242–242, Mar. 1968
1968
-
[16]
Asynchronous secure computation,
M. Ben-Or, R. Canetti, and O. Goldreich, “Asynchronous secure computation,” in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing , 1993, pp. 52–61
1993
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.