Pith. sign in

REVIEW 3 major objections 3 minor 2 cited by

OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement

T0 review · 3 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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$.

desk verdict 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. read the letter →

arxiv 2501.11788 v2 pith:NHABW6SS submitted 2025-01-20 cs.DC cs.CRcs.ITmath.IT

Jinyuan Chen This is my paper · ORCID
classification cs.DCcs.CRcs.ITmath.IT
keywords asynchronousByzantineagreementerror-freeconsensusinformation-theoreticsecuritypartialvectorreliablebroadcastcommoncoinerasurecodesoptimalresilience
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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)$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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)$.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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)$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

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.

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 (3)
  1. [Algorithm 3, lines 4–15; Lemma 7; Theorem 4] 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.
  2. [Theorem 7] 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.
  3. [Algorithm 4, lines 23–29] 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.
minor comments (3)
  1. [Section I and Table I] 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'.
  2. [Algorithms 2 and 3] 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.
  3. [Section III-B, Lemma 6] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No construction-level circularity: OciorABA's APVA/ACID* composition is a substantive derivation; self-citations and the finite-loop termination gap are support/correctness concerns, not circular reductions.

full rationale

Walking the derivation chain, the claimed ABA result is not equivalent to its inputs by construction. OciorABA (Algorithm 2) reduces consensus to APVA plus erasure-code decoding, and the proofs of Theorem 5 and Lemma 10 trace each 1 entry of the APVA output to an honest node's coded symbol; this is a composition argument, not a self-definition. APVA (Algorithm 3) is specified as ACID* dispersal, a common-coin-elected candidate vector, ABBBA/ABBA validation, and RBC retrieval; Lemma 9 establishes validity from the local vote/ready/finish fields of Algorithm 4, and Lemma 8 establishes consistency from the agreement of Election, ABBA, and RBC. These do not assume the ABA theorem being proved. The communication bound in Theorem 7 combines the stated OciorRBC cost from [8] with an APVA cost analysis; that is a dependency on same-author prior work, and because [8] and [12] are not reproduced or machine-checked here, the result inherits verification risk, but rule 4 treats such parameter-free protocol citations as independent evidence. The notable flaw in the paper is that Algorithm 3's for-loop (Lines 4-15) has no retry when the n common-coin draws all miss I*, creating positive-probability non-termination and contradicting the 'all executions' error-free claim; that is a correctness/termination gap, not a circular derivation. I therefore set the circularity score to 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 1 invented entities

The protocol is built on several assumed primitives: common coin, OciorRBC [8], ABBBA [12], an abstract ABBA, an erasure code, and the asynchronous model. No free parameters are fitted to data. The only invented object is the APVA primitive, which has no independent evidence outside the paper.

assumptions (6)
  • domain assumption Common coin Election[id] exists, is uniform over [1:n], is unpredictable, and all honest activations output the same l.
    Definition 7; used in APVA Line 5 and throughout the termination analysis.
  • ad hoc to paper OciorRBC [8] is a correct reliable broadcast with Validity, Consistency, Totality, and communication cost O(nc + nt log q).
    Assumed by citation; no proof here. Algorithm 1, 2, and 3 call it for every RBC instance.
  • ad hoc to paper ABBBA from [12] satisfies Conditional Termination, Biased Validity, and Biased Integrity.
    Lemma 11 restates the claim but gives only a sketch; APVA validity and termination use these properties throughout.
  • standard math An (n, k=t+1) erasure code exists from which any k symbols decode the original message.
    Definition of erasure code in Section I-A; used in Lines 3 and 18 of Algorithm 2 and in decoding.
  • domain assumption Asynchronous network with eventual delivery and an adaptive Byzantine adversary of size at most t.
    Section I-A describes the model; this underlies all liveness arguments.
  • domain assumption The ABBA primitive used in OciorABA⋆ and APVA satisfies Termination and Consistency.
    Assumed for the n ABBA instances in Algorithm 1 and for ABBA[(ID*,l)]/ABBA[(ID,l)] in APVA; no concrete protocol is specified.
invented entities (1)
  • Asynchronous partial vector agreement (APVA)
    purpose: New common-vector primitive used as the consensus layer in OciorABA; it accepts partial input vectors and outputs one common vector with at least n-t non-missing entries.
    Defined in Definition 1 and implemented by Algorithm 3; no external implementation or independent verification is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement." pith.science (2026). https://pith.science/paper/NHABW6SS

@misc{pith2026250111788,
  author       = {Pith},
  title        = {Pith review of: OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NHABW6SS}},
  note         = {Machine review of arXiv:2501.11788}
}
abstract

In this work, we propose an error-free, information-theoretically secure multi-valued asynchronous Byzantine agreement (ABA) protocol, called OciorABA. This protocol achieves ABA consensus on an $\ell$-bit message with an expected communication complexity of $O(n\ell + n^3 \log q )$ bits and an expected round complexity of $O(1)$ rounds, under the optimal resilience condition $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. In our protocol design, we introduce a new primitive: asynchronous partial vector agreement (APVA). In APVA, the distributed nodes input their vectors and aim to output a common vector, where some of the elements of those vectors may be missing or unknown. We propose an APVA protocol with an expected communication complexity of $O( n^3 \log q )$ bits and an expected round complexity of $O(1)$ rounds. This APVA protocol serves as a key building block for our OciorABA protocol.

Figures

Figures reproduced from arXiv: 2501.11788 by the authors.

Figure 1
Figure 1. A block diagram of the proposed OciorABA⋆ protocol with an identifier ID. Here Aones ⊆ [1 : n] denotes the indices of all ABBA instances that delivered 1, while Bones ⊆ Aones denotes the first t + 1 smallest values in Aones. The description focuses on the example with n = 4 and t = 1. II. OciorABA⋆ This proposed OciorABA⋆ is an error-free, information-theoretically secure asynchronous BA protocol. OciorABA⋆ does not… view at source ↗
Figure 2
Figure 2. A block diagram of the proposed OciorABA protocol with an identifier ID. Here vˆ denotes the output vector of APVA. Aones ⊆ [1 : n] denotes the indices of all elements in vˆ that are equal to 1, i.e., Aones = {j : vˆ[j] = 1, j ∈ [1 : n]}, while Bones ⊆ Aones denotes the first t + 1 smallest values in Aones. The description focuses on the example with n = 4 and t = 1 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. A block diagram of the proposed APVA protocol with an identifier ID. Details of the ACID⋆ protocol are presented in [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: A block diagram of the proposed ACID⋆ protocol with an identifier ID [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Extending Asynchronous Byzantine Agreement with Crusader Agreement

    cs.DC 2025-02 reject novelty 7.0 of 10

    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.

  2. Ocior: Ultra-Fast Asynchronous Leaderless Consensus with Two-Round Finality, Linear Overhead, and Adaptive Security

    cs.DC 2025-09 reject novelty 6.0 of 10

    Ocior is a leaderless asynchronous BFT protocol advertising two-round finality and O(n) overhead via a layered threshold signature, but its adaptive-security proofs are deferred and its O(n) computation good case is v...

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages · cited by 2 Pith papers

  1. [8]

    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. [12]

    OciorMVBA: Near-optimal error-free asynchronous MVBA,

    J. Chen, “OciorMVBA: Near-optimal error-free asynchronous MVBA,” Dec. 2024, available on ArXiv: https://arxiv.org/abs/2501.00214

    arXiv 2024

  3. [1]

    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

    work page 1980

  4. [2]

    Error-free multi-valued consensus with Byzantine failures,

    G. Liang and N. Vaidya, “Error-free multi-valued consensus with Byzantine failures,” in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) , Jun. 2011, pp. 11–20

    work page 2011

  5. [3]

    Optimal extension protocols for Byzantine broadcast and agreement,

    C. Ganesh and A. Patra, “Optimal extension protocols for Byzantine broadcast and agreement,” in Distributed Computing, Jul. 2020

    work page 2020

  6. [4]

    Optimal and error-free multi-valued Byzantine consensus through parallel execution,

    A. Loveless, R. Dreslinski, and B. Kasikci, “Optimal and error-free multi-valued Byzantine consensus through parallel execution,” 2020, available on: https://eprint.iacr.org/2020/322

    work page 2020

  7. [5]

    Improved extension protocols for Byzantine broadcast and agreement,

    K. Nayak, L. Ren, E. Shi, N. Vaidya, and Z. Xiang, “Improved extension protocols for Byzantine broadcast and agreement,” in International Symposium on Distributed Computing (DISC) , Oct. 2020

    work page 2020

  8. [6]

    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

Show all 12 references
  1. [7]

    Optimal error-free multi-valued Byzantine agreement,

    ——, “Optimal error-free multi-valued Byzantine agreement,” in International Symposium on Distributed Computing (DISC) , Oct. 2021

    2021

  2. [9]

    Expander codes,

    M. Sipser and D. Spielman, “Expander codes,” IEEE Trans. Inf. Theory , vol. 42, no. 6, pp. 1710–1722, Nov. 1996

    1996

  3. [10]

    Error-free multi-valued broadcast and Byzantine agreement with optimal communication complexity,

    A. Patra, “Error-free multi-valued broadcast and Byzantine agreement with optimal communication complexity,” in International Conference on Principles of Distributed Systems (OPODIS) , 2011, pp. 34–49

    2011

  4. [11]

    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

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.