Pith. sign in

REVIEW 4 major objections 7 minor 1 cited by

An Approach to Optimizing the VABA Protocol Using $\kappa$-size Committee

T0 review · 4 major / 7 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read A randomly chosen κ-party committee can carry VABA-style Byzantine agreement while only the committee broadcasts proposals.

desk verdict Coherent committee-based VABA sketch, but the central theorem is an unproved conditional and the claimed saving is not asymptotic. read the letter →

arxiv 2412.03789 v2 pith:GOGBPLYN submitted 2024-12-05 cs.DC

Nasit S Sony This is my paper · ORCID
classification cs.DC MSC 68M1468W15
keywords asynchronousByzantineagreementvalidatedVABAcommitteeselectionprovablebroadcastleaderelectioncommunicationcomplexityblockchain
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 tries to show that asynchronous Byzantine agreement does not need every party to broadcast its proposal. It proposes eVABA, a version of validated asynchronous Byzantine agreement (VABA) in which a randomly chosen committee of κ parties is the only group allowed to promote proposals. The protocol adds a gated broadcast step, prioritized provable-broadcast, so honest parties ignore proposal messages from non-committee members, and it maps the leader election output onto a committee member. The paper claims that under secure committee selection, provable broadcast, and leader election, eVABA keeps VABA's agreement, external validity, and liveness guarantees. If true, the proposal-promotion phase drops from $O(n^2)$ to $O(n\kappa)$ messages per view, with total complexity still $O(n^2)$ because the suggestion, leader-election, and view-change phases remain all-to-all.

What carries the argument

The carrying object is the κ-size committee combined with a gated broadcast primitive called Prioritized Provable-Broadcast (P-PB): a variant of provable broadcast in which honest parties return sign-shares only for senders that are on the view's committee, so only committee members can gather the $n-f$ shares needed to form a threshold-signature proof. On top of this, a distance-based mapping from the elected leader's id to the nearest committee member keeps the single-leader property while forcing the leader into the committee. The view-change phase then moves key/lock/commit proofs to all parties, and a party that cannot decide adopts the value of its latest key and carries it, with its proof, into the next view for external validity.

What would settle it

Take $n=3f+1$ and a uniformly random κ-subset; the probability the committee is entirely Byzantine is $\binom{f}{\kappa}/\binom{n}{\kappa}$ (or the analogous quantity for the paper's unspecified distribution). If for the intended κ this probability is not negligible over the protocol's view count, then the Liveness/Termination half of Theorem 3.2 has no demonstrated precondition, and an adversary could stall every view by ensuring all committee members are corrupt.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is that the expensive all-party broadcast step in VABA can be replaced by a κ-party committee broadcast without changing the protocol's core guarantees. The mechanism is a prioritized provable-broadcast in which honest parties attach sign-shares only to messages from parties selected for the current view, so a Byzantine party that is not on the committee cannot complete a proposal promotion and cannot force honest parties to waste bandwidth. The selected committee members promote proposals, all parties suggest and collect commit proofs, and a deterministic distance-based mapping sends the leader-election outcome to the nearest committee member so that every party agrees on which proposal to deliver. Theorem 3.2 states that eVABA satisfies Agreement, External-Validity, and Liveness/Termination provided the committee-selection, provable-broadcast, and leader-election protocols are secure; the concrete payoff is that proposal promotion costs $n\kappa$ messages instead of $n^2$.

Load-bearing premise

The load-bearing premise is that a randomly selected committee of size κ contains at least one honest party with overwhelming probability; the paper invokes this to guarantee progress but never specifies a selection distribution, a value of κ, or a failure bound.

Editorial extensions

If this is right

  • Only κ parties broadcast proposals in each view, cutting the proposal-promotion message count from $O(n^2)$ to $O(n\kappa)$ while keeping total message complexity of the whole protocol at $O(n^2)$.
  • A non-committee Byzantine party cannot inject a proposal: honest parties' P-PB sign-shares are withheld, so the party cannot complete the threshold-signature proof.
  • The elected leader is always mapped to a committee member, so all parties deliver the same committee-backed proposal even when raw leader election picks an outsider.
  • When a view fails to decide, parties carry the latest key value with its proof into the next view, which preserves external validity across view changes.
  • Expected time complexity stays constant at $O(1)$ views, so the savings do not come at the cost of extra rounds.

Reading between the lines

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

  • Beyond the paper, the trade-off between liveness and cost is governed by the committee-selection distribution: the paper gives no formula for κ, so a natural next step is to derive, for a given adversary threshold f and selection distribution, the minimum κ that makes an all-Byzantine committee unlikely enough to satisfy a target liveness bound.
  • Because the suggestion, leader-election, and view-change phases are still all-to-all, the end-to-end gain concentrates almost entirely in the proposal-promotion step; a further optimization would need to reduce those all-to-all phases, which this paper does not attempt.
  • If a fresh committee is sampled every view rather than once per protocol run, the adversary's ability to target committee members changes, and the protocol's security analysis would need to account for the sampling cost; the paper leaves this variant unexamined.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 7 minor

Summary. This manuscript proposes eVABA, an asynchronous Byzantine agreement protocol based on VABA. Instead of letting all n parties broadcast proposals, the protocol selects a κ-size committee; only committee members run a prioritized provable broadcast (P-PB); a leader is elected and then mapped to a committee member; and a view-change step disseminates the chosen proposal. The paper claims that this preserves the Agreement, External Validity, and Liveness/Termination properties of VABA and reduces the proposal-promotion message cost from O(n^2) to O(nκ) per view, while retaining O(n^2) total message complexity and O(1) expected time.

Significance. The idea of restricting proposal broadcasts to a small committee is a natural and potentially valuable direction for reducing communication in asynchronous Byzantine agreement, and the paper identifies a real inefficiency in all-to-all propose protocols. However, the manuscript does not deliver a verifiable result: the main theorem is a one-sentence assertion that delegates all security to unproved and mostly unspecified sub-protocols; the liveness premise on committee composition is unquantified; and the efficiency analysis contradicts its own reduction claim. There is no machine-checked proof, no simulation, and no formal comparison with VABA's total cost. As it stands, the contribution is an approach description rather than an established protocol with stated guarantees.

major comments (4)
  1. [Theorem 3.2 (Section 3.1)] Theorem 3.2 is the only correctness statement for eVABA, but it is asserted without proof. The preceding text (including Lemma 3.1) only establishes that a selected party can complete a proposal promotion; it does not argue that honest parties decide on a common value, that a decided value satisfies the external-validity predicate, or that a view terminates. A valid proof of the theorem would need invariants or an explicit case analysis for Agreement, Validity, and Termination, as well as a formal reduction to the security properties of the committee-selection, provable-broadcast, and leader-election sub-protocols. None of this is present; the theorem's condition 'given that ... protocols are secure' is not backed by definitions of those security properties or by any argument that eVABA instantiates them. Since the entire claimed contribution rests on this theorem, this is a load-bearing gap.
  2. [Section 2.1 (Committee Selection)] The liveness branch of the protocol depends on the assumption that a randomly selected committee of size κ contains at least one honest party 'with overwhelming probability.' The paper gives no sampling distribution, no concrete value or lower bound for κ, and no failure bound. If κ is too small, a committee can be entirely Byzantine with non-negligible probability; if the adversary can influence the selection, no uniform bound is guaranteed. In either case the claim that at least one honest committee member will complete a promotion and that views will terminate is unquantified and unverifiable. The same issue affects the O(1) expected time claimed in Section 3.2. This is a separate load-bearing premise from the agreement claim and must be resolved before the protocol can be instantiated.
  3. [Section 3.2 (Efficiency Analysis)] The efficiency analysis does not support the stated reduction. The text says the total number of messages for the proposal-promotion sub-protocol is nκ, reducing the cost 'from n^2 to nκ' (the text as printed reads 'from n2 nκ', which is garbled). It then acknowledges that the suggestion, leader-election, and view-change steps are all-to-all and have O(n^2) message complexity. Therefore the overall message complexity is still O(n^2), and the paper's own conclusion of 'optimal message complexity of O(n^2)' does not demonstrate an asymptotic improvement over standard VABA, which also has O(n^2) complexity. To substantiate the claim that eVABA improves efficiency, the paper must either bound the all-to-all phases in terms of κ or compare the total message count, not just the proposal-promotion portion.
  4. [Section 2.4 (Party Selection and Mapping)] The mapping from the elected leader to the nearest committee member introduces an unanalyzed element into the liveness proof. Even if the leader-election protocol selects a common random leader, the paper does not analyze the probability that the mapped committee member is honest or has an available valid proposal. Since a Byzantine committee member can be mapped to even when the elected leader is honest, and liveness requires the view-change step to deliver a valid proposal, the O(1) expected termination time in Section 3.2 is not justified. This is another missing step in the central liveness/termination argument.
minor comments (7)
  1. [Section 3.1, Lemma 3.1] Lemma 3.1 refers to 'Algorithm 2.2', but the promoted protocol is Algorithm 1.
  2. [Throughout] The notation alternates between 'eV ABA', 'eVABA', 'V ABA', and 'V ABA' in ways that make the text hard to read; a consistent notation would improve clarity.
  3. [Section 3.2] The sentence 'The total number of messages are n ∗ κ, which reduces the total number of messages and the related computations from n2 nκ' is typographically garbled; it appears to mean from n^2 to nκ.
  4. [References] References [6]–[9] are the author's own preprints and are used as the basis for the provable-broadcast, leader-election, and committee-selection building blocks; since these are not peer-reviewed or even cited with version/DOI details, the dependency structure of the security claim is not independently verifiable.
  5. [Reference [5]] Reference [5] contains a typo: 'bitcon.org' should be 'bitcoin.org'.
  6. [Figure 1] Figure 1 is mentioned but not described sufficiently in the text; labeling the phases and listing the message flows would improve readability.
  7. [Conclusion] The term 'optimal' is not defined in the conclusion; the paper should state with respect to which class of protocols the O(n^2) complexity is optimal.

Circularity Check

0 steps flagged · score 0.0 of 10

Theorem 3.2 is an unproved conditional reduction, not a circular one; the liveness gap is a proof/quantification gap, not an identity between conclusion and input.

full rationale

The paper's central correctness claim, Theorem 3.2, is phrased as an explicit conditional: eVABA inherits Agreement, External-Validity, and Liveness/Termination 'given that the underlying Committee selection, provable-broadcast, and the leader-election protocols are secure.' A conditional security statement is the normal form of a reduction; it is circular only if the assumptions are definitionally equivalent to the conclusion, and nothing in the text shows that equivalence. The liveness branch is indeed under-specified: Section 2.1 asserts a randomized kappa-committee contains an honest party 'with overwhelming probability' without giving a distribution or a bound on kappa, and Section 3.2 asserts termination without proving the chain from one honest committee member to a decided value. Those are missing proofs and missing quantification, which are correctness risks, not circular reductions. The 'selected property' of Lemma 3.1 follows by inspection of Algorithm 1's sender check, so it is a benign definitional property rather than a smuggled prediction. The self-citations [6-9] appear in the introduction as related work ('followed by [2, 7, 6, 8, 9]') and are not invoked as the evidence for Theorem 3.2; hence they do not form a load-bearing self-citation chain. Section 3.2's admission that suggest, leader-election, and view-change remain all-to-all O(n^2) undercuts the abstract's reduction claim but does not make any stated equation equal to its own input. Overall, no significant circularity is exhibited.

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

The protocol rests on two unquantified assumptions: a committee of size kappa contains an honest party with overwhelming probability, and the security of all sub-protocols is inherited from prior work, mostly the author's own preprints. The only free parameter is kappa, which is never instantiated, and no external validation or lower bound is supplied.

free parameters (1)
  • kappa (committee size)
    Introduced in Section 2.1 as the security parameter controlling the number of broadcasters. No concrete value, no tradeoff with failure probability, yet all efficiency and liveness claims depend on it.
assumptions (5)
  • domain assumption The network is asynchronous and eventually delivers messages; at most f of n=3f+1 parties are Byzantine.
    Stated in the abstract and Section 1; standard ABA model.
  • ad hoc to paper A randomly selected committee of size kappa contains at least one honest party with overwhelming probability.
    Section 2.1 asserts this without proof or parameterization; liveness of eVABA depends on it.
  • domain assumption Honest parties can verify committee membership and will only add sign-shares to messages from selected senders.
    Required by Prioritized Provable Broadcast in Algorithm 1; depends on an authenticated membership mechanism not specified.
  • standard math Threshold signatures and a public-key infrastructure are available.
    Used throughout P-PB and view-change; cryptographic assumption not proved in this paper.
  • ad hoc to paper The leader-election protocol is secure and the distance-based mapping to a committee member preserves the properties needed for agreement.
    Section 2.4 asserts consistency but gives no analysis of how mapping affects the leader distribution or adversarial advantage.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Approach to Optimizing the VABA Protocol Using $\kappa$-size Committee." pith.science (2026). https://pith.science/paper/GOGBPLYN

@misc{pith2026241203789,
  author       = {Pith},
  title        = {Pith review of: An Approach to Optimizing the VABA Protocol Using $\kappa$-size Committee},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GOGBPLYN}},
  note         = {Machine review of arXiv:2412.03789}
}
abstract

Byzantine agreement protocols in asynchronous networks have gained renewed attention due to their independence from network timing assumptions to ensure termination. Traditional asynchronous Byzantine agreement protocols require every party to broadcast its requests (e.g., transactions), leading to high communication costs as parties ultimately agree on one party's request. This inefficiency is particularly significant in multi-valued Byzantine agreement protocols, where parties aim to agree on one party's requests under the assumption $n=3f+1$, where $n$ is the total number of parties, and $f$ is the number of Byzantine parties. To address these inefficiencies, we propose Efficient-VABA (eVABA), an optimized protocol for the asynchronous Byzantine agreement (ABA) problem. By limiting broadcasts to a selected subset of parties, the protocol reduces the number of messages and computation overhead.

Figures

Figures reproduced from arXiv: 2412.03789 by the authors.

Figure 1
Figure 1. eVABA illustration. Parties select a committee, and each committee member promotes its requests using the [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. An efficient validated asynchronous byzantine agreement protocol using committee

    cs.DC 2025-01 reject novelty 2.0 of 10

    A committee-based VABA variant where a stochastically selected subset of f+1 parties broadcasts proposals, claiming a factor (f+1) reduction in proposal-broadcast messages but with incomplete correctness proofs.

Reference graph

Works this paper leans on

10 extracted references · 3 canonical work pages · cited by 1 Pith paper

  1. [7]

    arXivpreprintarXiv: 2406.03739

    Nasit S Sony, Xianzhong Ding, and Mukesh Singhal. Prioritized-MVBA: A New Approach to Design an Optimal Asynchronous Byzantine Agreement Protocol. In arXiv preprint, June 2024. URL: "arXivpreprintarXiv: 2406.03739"

    arXiv 2024

  2. [8]

    A committee based optimal asynchronous byzantine agreement protocol wp 1

    Nasit S Sony, Xianzhong Ding, and Mukesh Singhal. A committee based optimal asynchronous byzantine agreement protocol wp 1. arXiv preprint arXiv:2410.23477, 2024

    arXiv 2024

  3. [9]

    Slim-ABC: An Optimized Atomic Broadcast Protocol

    Nasit S Sony, Xianzhong Ding, and Mukesh Singhal. Slim-ABC: An Optimized Atomic Broadcast Protocol. arXiv preprint arXiv:2410.04268, 2024. 6

    arXiv 2024

  4. [1]

    The honey badger of BFT protocols

    Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of BFT protocols. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communication Security, CCS’16, New York, NY , USA, 2016. ACM Press

    2016

  5. [2]

    Dumbo: Faster asynchronous bft protocols

    Bingyong Guo, Zhenliang Lu, Qiang Tang, Jing Xu and Zhenfeng Zhang. Dumbo: Faster asynchronous bft protocols. In Proceedings of the ACM Conference on Computer and Communications Security, page 803–818,

  6. [3]

    The Byzantine generals problem

    Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. In ACM Transactions on Programming Languages and Systems (TOPLAS), page 382–401. ACM, 1982

    work page 1982

  7. [4]

    Reaching agreement in the presence of faults

    Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. In ACM, page 228–234, 1980

    1980

  8. [5]

    A peer-to-peer electronic cash system, 2008

    Satoshi Nakamoto. A peer-to-peer electronic cash system, 2008. URL: http://bitcon.org/bitcoin.pdf. 5 eV ABA

    work page 2008

Show all 10 references
  1. [6]

    https://easychair.org/publications/preprint/Zs8Mw/ open

    Nasit S Sony, Xianzhong Ding, and Mukesh Singhal. Optimizing Communication in Byzantine Agreement Protocols with Slim-HBBFT. In Euro-Par, 2024. URL: "https://easychair.org/publications/preprint/Zs8Mw/ open"

    2024

  2. [2020]

    https://doi.org/10.1145/3372297.3417262

    URL: "https://doi.org/10.1145/3372297.3417262"

Pith tools

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