Pith. sign in

REVIEW 4 major objections 4 minor 35 references

An efficient validated asynchronous byzantine agreement protocol using committee

T0 review · 4 major / 4 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 Efficient-VABA reduces the proposal-broadcast set from all n parties to a randomly chosen committee of f+1, claiming the same validated asynchronous Byzantine agreement guarantees as VABA while cutting proposal-broadcast messages from…

desk verdict A plausible efficiency idea, but the protocol's own pseudocode cannot run and the key agreement-preservation lemma is unproved. read the letter →

arxiv 2501.00717 v1 pith:IQ6JKBQW submitted 2025-01-01 cs.DC

Nasit S Sony This is my paper · ORCID
classification cs.DC MSC 68M1468M15
keywords asynchronousByzantineagreementvalidatedcommitteeselectionprovablebroadcastthresholdsignaturesleaderelectioncommunicationcomplexityview-changeprotocol
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

The paper is trying to establish that a validated asynchronous Byzantine agreement protocol can get by with far fewer proposal broadcasts than the VABA baseline. It proposes Efficient-VABA, in which only a randomly selected committee of f+1 parties, rather than all n parties, broadcast their requests, with a suggestion step so parties can move forward after the first completed proposal. The paper claims this preserves VABA's agreement, liveness, external validity, and integrity properties while reducing proposal-broadcast messages from O($n^{2}$) to n(f+1). A sympathetic reader would care because, when parties are agreeing on a single value, having every party broadcast its proposal is wasteful; the paper points to a way to spend the communication budget only on a small committee.

What carries the argument

The load-bearing object is the prioritized provable-broadcast sub-protocol, a four-step sequential broadcast in which each step's threshold-signature proof becomes the input of the next, ending in a commit proof. Honest parties return sign-shares only for senders listed in the current view's prioritized committee, so only the f+1 selected parties can ever obtain a completed promotion. The supporting mechanisms are committee selection by threshold coin-tossing, a suggestion phase that lets a party act on the first valid proposal, and a leader-election-to-committee mapping that picks the nearest committee member to the elected leader. Together these are supposed to ensure that one honest committee member's proposal is disseminated, locked, and carried into the next view.

What would settle it

Construct a view where the elected leader is not on the committee and the mapped nearest committee member is Byzantine, and check whether any honest party holds a valid threshold-signature prepare proof for that member at the start of the next view. A small n=4, f=1 simulation with adversarially delayed messages can test whether a value decided in view j fails to be promoted, which would contradict Lemma 5.9.

Watch

Extended reading notes

Core claim

The paper's central claim is that the VABA leader-based structure survives a reduction in the number of broadcasters. In Efficient-VABA, committee selection picks f+1 prioritized parties for each view; only those parties can initiate the four-step prioritized provable-broadcast chain that produces prepare, lock, and commit threshold-signature proofs. Leader election is then forced onto the committee by mapping the randomly elected leader to the nearest committee member. The paper asserts that at least one selected honest party completes promotion, that only selected parties can complete promotion, and that these changes reduce the proposal-broadcast message count to n(f+1) while preserving agreement, termination, external validity, and integrity under f<n/3.

Load-bearing premise

The protocol's safety across views rests on Lemma 5.9, stated without proof in Section 4.5 after Algorithm 7, which assumes that the committee member nearest the elected leader has already completed enough of the broadcast rounds to hold a valid signed proof of the decided value; if that member is Byzantine or has not finished broadcasting, the value decided in the previous view may not be carried forward.

Editorial extensions

If this is right

  • Proposal-broadcast messages drop from O(n^2) to n(f+1), saving roughly a factor of f+1 in that subsystem.
  • Honest parties can advance a view after one completed promotion plus suggestions, rather than waiting for n-f completed proposals.
  • Only selected committee members can get their proposals accepted, because honest parties issue sign-shares exclusively to selected senders.
  • The protocol claims to keep optimal resilience f<n/3 and expected O(1) views.
  • The all-to-all suggestion, leader-election, and view-change phases still contribute O(n^2) messages, so the gain is localized to the proposal-promotion subsystem.

Reading between the lines

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

  • The same 'suggest after the first valid proposal' rule could be applied to other multi-valued agreement protocols that currently wait for n-f proposals, potentially shortening per-view latency; the paper does not develop this transfer.
  • Composing the committee-broadcast reduction with erasure coding, as some asynchronous BFT protocols do, could shrink the remaining n(f+1) proposal cost further; this is not explored here.
  • A profiling experiment that measures the four provable-broadcast rounds separately from the all-to-all suggestion, leader-election, and view-change phases would show how much of the claimed saving appears in wall-clock time; the abstract itself notes the protocol is time-consuming.
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 / 4 minor

Summary. The paper proposes Efficient-VABA, a validated asynchronous Byzantine agreement protocol that restricts the set of proposal broadcasters to a randomly selected committee of size f+1, maps an elected leader to a member of that committee, and otherwise follows the structure of Abraham et al.'s VABA protocol [14]. The central claim is that this reduces proposal-broadcast message complexity from O(n^2) to n(f+1) while preserving agreement, termination, external validity, and integrity with O(1) expected running time. The manuscript gives protocol pseudocode, a set of lemmas intended to establish the security properties, and an efficiency analysis.

Significance. If the protocol were correct, the message-complexity improvement in the proposal phase would be a meaningful practical contribution, because VABA-style multi-valued validated Byzantine agreement is a building block for asynchronous atomic broadcast and state-machine replication. The paper also identifies a genuinely important design question: how to reduce the number of proposal broadcasts without sacrificing the security guarantees of the underlying view-based protocol. However, the claimed result is currently not supported: several load-bearing lemmas are unproved, the main theorem is a sketch, and the pseudocode appears not to implement the described view-change mechanism. The paper does not include machine-checked proofs, executable code, or independent experimental validation, so the evaluation rests entirely on the correctness of the mathematical claims.

major comments (4)
  1. [Section 3, Lemma 3.1] The statement 'If n = 3f + 1, f + 1 ≤ f' is contradictory: f + 1 ≤ f is false for every integer f, so the lemma has no meaningful hypothesis. Moreover, for the committee size κ = f + 1 used in the protocol and n = 3f + 1, the probability expression (f choose κ)/(n choose κ) evaluates to 0 because κ > f. The claim should be re-derived with the correct committee-size parameter; as written, the validity property of the committee-selection primitive is not established.
  2. [Section 4.6, Algorithms 9 and 10] The view-change validation path is dead in the pseudocode. Algorithm 9 maps the elected leader to a committee member at lines 32–34 but never assigns the result to Party[view], while Algorithm 8 initializes Party[view] ← ⊥ for every view; Algorithm 10 then reads Party[view] at line 21 and threshold-validates messages that mention 'party'. Furthermore, line 35 multicasts getPrepare(ID)/getLock(ID)/getCommit(ID) with ID bound at line 6 only for selected parties, so a non-selected party's ID is undefined, and the message does not carry the mapped leader's delivery as Section 4.6 claims. The view-change step therefore cannot perform the proof-carrying promotion on which all later lemmas depend.
  3. [Section 5.1, Lemma 5.9] Lemma 5.9 is the key agreement invariant: once a party decides v in view j, every valid step-1 proof produced in any later view must also carry v. It is stated without proof, and it is used directly in Theorem 5.15 for agreement. No argument in the paper shows that the committee member chosen by Algorithm 7 has completed a second- or third-step P-PB instance, so valid prepare/lock proofs for that member may not exist. If the nearest committee member is Byzantine or inactive, the premise of the lemma fails, and the theorem's bridge from view j to view j + 1 is missing.
  4. [Section 5.1, Lemmas 5.6, 5.10, and Theorem 5.15] Several supporting lemmas are asserted without proof or with only a sketch: Lemma 5.6 (propagation of view-change proofs), Lemma 5.10 (lock implies prepare in the next view), and Lemma 5.11 (external validity of all broadcast messages) are all used in the proof of Theorem 5.15. The proof of Theorem 5.15 itself is a high-level sketch, and its External-Validity part repeats the proof of Lemma 5.11 rather than establishing the property for the modified protocol; since the committee mapping changes the view-change format, a direct appeal to VABA [14] is not sufficient.
minor comments (4)
  1. [Section 2.1.1, PB-Provability definition] The condition 'threshold-validate(⟨id, v′⟩, v′) = true' should presumably read 'threshold-validate(⟨id, v′⟩, σ′) = true'; as written, the argument is a value rather than a signature.
  2. [Algorithm 8] The heading says 'Gocal variables initialization'; this should be 'Global variables initialization'.
  3. [Algorithms 5 and 10] The line numbering in Algorithm 5 is out of order (lines 09-08), and several threshold-validate expressions in Algorithms 5 and 10 have unbalanced parentheses, making it difficult to determine the exact message ID being validated.
  4. [Section 4.6] The text states that each party multicasts the selected party's delivery via VIEW-CHANGE, but Algorithm 9 uses getPrepare(ID), getLock(ID), and getCommit(ID) where ID is the sender's own identifier; this discrepancy should be resolved even apart from the substantive issue raised in the major comments.

Circularity Check

0 steps flagged · score 1.0 of 10

No construction-level circularity; the main weakness is an unproven cross-view invariant, not a self-referential derivation.

full rationale

I found no step in which a claimed result is identical to its input by construction. The efficiency reduction is a direct message-count comparison within the proposed protocol (Section 5.2), not a fitted prediction. The committee-selection primitive is attributed to the author's own pMVBA [25], but the paper gives Algorithm 1 and proves the needed validity property in Lemma 3.1, so the self-citation is not the load-bearing justification. The real gap is in the security derivation: Section 5.1 says 'We only state and change the lemma definitions to match the proposed protocol requirements and skip the proofs if it follows the V ABA,' and then Lemma 5.9, the invariant needed to carry a decided value from view j into all later views, is stated without proof even though the protocol changes leader selection via Algorithm 7 and the view-change path reads `Party[view]` (Algorithm 8 line 5 and Algorithm 10 line 21) without ever assigning it in Algorithm 9. Theorem 5.15 then derives Agreement directly from Lemma 5.9. This is an omitted-proof/correctness defect in the modified protocol, not a circular reduction: no equation or fitted parameter is reused as its own conclusion. I therefore keep the circularity score at the non-significant level.

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

The protocol's correctness rests on several unproved or internally inconsistent foundations. The committee selection, the security of the modified provable broadcast, and the mapped leader election are all assumed to behave as claimed. No new entities are postulated.

free parameters (2)
  • committee size κ = f+1
    Set to f+1 in Algorithm 1 and §4.1 to guarantee an honest committee member with certainty. The security proof in Lemma 3.1 uses a bound valid only for κ ≤ f, creating an inconsistency.
  • signature threshold t = n - f = 2f+1
    The P-PB sender waits for n-f sign-shares (Algorithm 4, line 5). This is a design choice, standard in asynchronous quorum protocols, not fitted to data.
assumptions (6)
  • domain assumption Asynchronous network with reliable, authenticated point-to-point links
    Stated in §2; deliverability of messages between honest parties is assumed for liveness.
  • domain assumption Trusted dealer for threshold coin-tossing provides a PRG and private shares
    Assumed in §3, Preliminaries; used by committee selection and leader election.
  • standard math Threshold signature scheme is unforgeable and robust
    Adopted from [7,32,11] in §3; no new proof is given.
  • ad hoc to paper Committee selection protocol satisfies Termination, Agreement, Validity and Unpredictability
    Algorithm 1 is claimed to satisfy these properties; the Validity proof in Lemma 3.1 is internally inconsistent.
  • standard math The VABA protocol [14] satisfies validated Byzantine agreement
    The paper builds on VABA and defers correctness of unmodified parts to it.
  • ad hoc to paper View-change and leader mapping preserve decided values (Lemmas 5.6, 5.9, 5.10)
    These lemmas are stated without proof and are essential for agreement; they are not inherited from VABA because the leader is mapped to a committee member.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An efficient validated asynchronous byzantine agreement protocol using committee." pith.science (2026). https://pith.science/paper/IQ6JKBQW

@misc{pith2026250100717,
  author       = {Pith},
  title        = {Pith review of: An efficient validated asynchronous byzantine agreement protocol using committee},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IQ6JKBQW}},
  note         = {Machine review of arXiv:2501.00717}
}
read the original abstract

We present a Byzantine agreement protocol to address the inefficiencies inherent in multi-valued Byzantine agreement protocols, i.e., a version of the Byzantine agreement protocol where every party broadcasts its request, and at the end of the protocol, every party agrees on one of the party's requests. The protocol we present is a validated asynchronous Byzantine agreement protocol, i.e., a party's request must be validated by some external validity property before it is proposed for agreement. Differently from most of the MVBA protocols, we allow only a subset of total parties to broadcast their requests instead of all, and we make the subset selection stochastic each time the parties choose to broadcast a new set of requests. Then, at the time of the agreement, we choose a party from the selected subset, and the parties reach an agreement on the selected party's broadcast. Extensive theoretical analysis shows that this approach can produce efficient output regarding messages and computation overhead, but the protocol is time-consuming.

Figures

Figures reproduced from arXiv: 2501.00717 by the authors.

Figure 1
Figure 1. An overview of the proposed protocol. In this section, we present the proposed protocol. We first provide the task of each step of the protocol and finally, the integration of the steps. Since we propose an algorithm that improves the VABA protocol, we adopted the definitions and the protocols from VABA [14]. The visual description of the Efficient-VABA protocol’s steps is given in [PITH_FULL_IMAGE:figures/full_fig… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 31 canonical work pages

  1. [14]

    Asymptotically optimal validated asynchronous byzantine agreement

    Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically optimal validated asynchronous byzantine agreement. In PODC, 2019

    work page 2019

  2. [1]

    Signature-free asynchronous byzantine consensus with t <n 3 and O(n2) messages

    Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. Signature-free asynchronous byzantine consensus with t <n 3 and O(n2) messages. In In Proc. ACM PODC, pages 2–9, 2014

    work page 2014

  3. [2]

    Upright cluster services

    Allen Clement, Manos Kapritsos, Sangmin Lee, Yang Wang, Lorenzo Alvisi, Michael Dahlin, and Taylor Riche. Upright cluster services. In In Proceedings of the 22nd ACM Symposium on Operating Systems Principles, page 277–290, Big Sky, Montana, USA, October 11-14 2009

    work page 2009

  4. [3]

    State Machine Replication for the Masses with BFT-SMART

    Alysson Neves Bessani, João Sousa, and Eduardo Adílio Pelinson Alchieri. State Machine Replication for the Masses with BFT-SMART. In In 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, 2014

    work page 2014

  5. [4]

    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

    work page 2016

  6. [5]

    Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares

    Benoît Libert, Marc Joye, and Moti Yung. Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares. . In Theory of Computer Science, volume 645, pages 1–24, 2016

    work page 2016

  7. [6]

    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,

    work page

  8. [7]

    Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography

    Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. In Journal of Cryptology, 2000

    work page 2000

Show all 35 references
  1. [8]

    Asynchronous verifiable secret sharing and proactive cryptosystems

    Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, and Reto Strobl. Asynchronous verifiable secret sharing and proactive cryptosystems. In In Proc. ACM CCS, page 88–97, 2002

    2002

  2. [9]

    Secure and efficient asynchronous broadcast protocols

    Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Advances in Cryptology, 2001. 15 eV ABA

    2001

  3. [10]

    Consensus in the presence of partial synchrony

    Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. In Journal of the ACM (JACM), volume 35(2), page 288–323. ACM, 1988

    1988

  4. [11]

    https://doi.org/10.1007/s00145-004-0314-9

    Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. In Journal of Cryptology, page 297–319, 2004. URL: "https://doi.org/10.1007/s00145-004-0314-9"

    2004 doi

  5. [12]

    Reiter, Dragos- Adrian Seredinschi, Orr Tamir, and Alin Tomescu

    Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos- Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: a Scalable Decentralized Trust Infrastructure for Blockchains. In arXiv:1804.01626, 2018

    2018 arXiv

  6. [13]

    Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast

    HariGovind V Ramasamy and Christian Cachin. Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast. In International Conference On Principles Of Distributed Systems., page 88–102, 2005

    2005

  7. [15]

    Optimistic asynchronous atomic broadcast

    Klaus Kursawe and Victor Shoup. Optimistic asynchronous atomic broadcast. In In International Colloquium on Automata, Languages, and Programming., page 204–215, 2005

    2005

  8. [16]

    The weak Byzantine generals problem

    Leslie Lamport. The weak Byzantine generals problem. In JACM 30, 3, page 668–676, 1983

    1983

  9. [17]

    Ben-Or, B

    M. Ben-Or, B. Kelmer, and T. Rabin. Asynchronous secure computations with optimal resilience. InIn Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, page 183–192, 1994

    1994

  10. [18]

    M. Naor, B. Pinkas, and O. Reingold. Distributed pseudo-random functions and KDCs. InAdvances in Cryptology: EUROCRYPT, volume 1592, page 82–96. Springer, 1999

    1999

  11. [19]

    Reiter, Guy Golan Gueta, and Ittai Abraham

    Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: Bft consensus in the lens of blockchain. In PODC, 2019

    2019

  12. [20]

    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

  13. [21]

    Fischer, Nancy A

    Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process.32(2):. In ACM, page 374–382. ACM, April 1985

    1985

  14. [22]

    Practical byzantine fault tolerance

    Miguel Castro, Barbara Liskov. Practical byzantine fault tolerance. In OSDI, volume 99, page 656–666, 1999

    1999

  15. [23]

    A peer-to-peer electronic cash system, 2008

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

    2008

  16. [24]

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

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

    2024

  17. [25]

    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"

    2024

  18. [26]

    The Next 700 BFT Protocols

    Pierre-Louis Aublin, Rachid Guerraoui, Nikola Knezevic, Vivien Quéma, and Marko Vukolic. The Next 700 BFT Protocols. In ACM Trans. Comput. Syst. 32, 4, page 12:1–12:45, 2015

    2015

  19. [27]

    Zyzzyva: Speculative Byzantine Fault Tolerance

    Ramakrishna Kotla, Lorenzo Alvisi, Michael Dahlin, Allen Clement, and Ed- mund L.Wong. Zyzzyva: Speculative Byzantine Fault Tolerance. In ACMTrans. Comput. Syst. 27, page 7:1–7:39, 2009

    2009

  20. [28]

    An Approach to Optimizing the V ABA Protocol Using κ-size Committee

    Nasit S Sony. An Approach to Optimizing the V ABA Protocol Using κ-size Committee. arXiv preprint arXiv:2412.03789, 2024

    2024 arXiv

  21. [29]

    Agreement protocol wp

    Nasit S Sony and Xianzhong Ding. Agreement protocol wp. easychair, 2024

    2024

  22. [30]

    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

    2024 arXiv

  23. [31]

    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

    2024 arXiv

  24. [32]

    Practical threshold signatures

    Victor Shoup. Practical threshold signatures. In International Conference on the Theory and Applications of Cryptographic Techniques.Springer, 2000

    2000

  25. [33]

    Coan, Jonathan Kirsch, and John Lane

    Yair Amir, Brian A. Coan, Jonathan Kirsch, and John Lane. Prime: Byzantine Replication under Attack. In IEEE Trans. Dependable Sec. Comput. 8, page 564– 577, https://doi.org/10.1109/TDSC.2010.70, 2011

    2010 doi

  26. [34]

    Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited

    Yuan Lu, Zhenliang Lu, Qiang Tang and Guiling Wang. Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited. InProceedings of the 39th Symposium on Principles of Distributed Computing, July 2020. 16 eV ABA A Related work A Byzantine agreement pro...

    2020

  27. [2020]

    https://doi.org/10.1145/3372297.3417262

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

Pith tools

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