pith. sign in

arxiv: 1907.11445 · v1 · pith:ID456PAInew · submitted 2019-07-26 · 💻 cs.CR · cs.DC

Protocol for Asynchronous, Reliable, Secure and Efficient Consensus (PARSEC) Version 2.0

Pierre Chevalier , Bartlomiej Kaminski , Fraser Hutchison , Qi Ma , Spandan Sharma , Andreas Fackler , William J Buchanan This is my paper

Pith reviewed 2026-05-24 16:01 UTC · model grok-4.3

classification 💻 cs.CR cs.DC
keywords asynchronous consensusByzantine fault toleranceBFT protocolcommon coinleaderless algorithmdynamic membership
0
0 comments X

The pith

The PARSEC protocol achieves fully asynchronous Byzantine consensus with agreement probability one under one-third faults using a common coin.

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

The paper presents PARSEC as an open source leaderless algorithm for consensus in asynchronous networks subject to Byzantine faults. It establishes correctness when fewer than one third of nodes are faulty and extends the model to dynamic membership where nodes join and leave freely. By employing a common coin for randomization the protocol reaches agreement with probability one while respecting the FLP impossibility result for deterministic asynchronous consensus. This matters because it offers a way to build reliable systems in networks without timing guarantees or designated leaders.

Core claim

PARSEC defines an optimal asynchronous BFT protocol resilient to one third Byzantine nodes that uses a common coin to achieve agreement with probability one.

What carries the argument

The common coin, which provides the shared randomness necessary to overcome symmetry in an asynchronous setting and ensure progress toward agreement.

If this is right

  • Correctness is guaranteed below the one third fault threshold.
  • The protocol operates without a leader.
  • It supports dynamic changes in network membership.
  • The model is optimal in its resilience for asynchronous conditions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This approach may allow consensus in highly variable network conditions such as the internet.
  • The dynamic membership handling suggests applications in evolving peer-to-peer systems.
  • Integration with existing common coin implementations could be tested for practical performance.

Load-bearing premise

A reliable common coin primitive exists that delivers shared randomness in a fully asynchronous network without introducing timing assumptions.

What would settle it

Finding a counterexample execution with less than one third faulty nodes where agreement is not reached with probability one or where the common coin cannot be realized asynchronously.

Figures

Figures reproduced from arXiv: 1907.11445 by Andreas Fackler, Bartlomiej Kaminski, Fraser Hutchison, Pierre Chevalier, Qi Ma, Spandan Sharma, William J Buchanan.

Figure 1
Figure 1. Figure 1: d_4 sees b_0: b_0 is its ancestor and there are no forks [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: An example gossip graph, along with estimates and bin_values associated with [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
read the original abstract

In this paper we present an open source, fully asynchronous, leaderless algorithm for reaching consensus in the presence of Byzantine faults in an asynchronous network. We prove the algorithm's correctness provided that less than a third of participating nodes are faulty. We also present a way of applying the algorithm to a network with dynamic membership, i.e. a network in which nodes can join and leave at will. The core contribution of this paper is an optimal model in the definition of an asynchronous BFT protocol, and which is resilient to 1/3 byzantine nodes. This model matches an agreement with probability one (unlike some probabilistic methods), and where a common coin is used as a source of randomization so that it respects the FLP impossibility result.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 1 minor

Summary. The manuscript presents PARSEC v2.0, an open-source leaderless consensus algorithm for fully asynchronous networks with Byzantine faults. It claims a proof of correctness achieving agreement with probability 1 under less than 1/3 faulty nodes by using a common coin for randomization (respecting FLP impossibility), and describes an extension to dynamic membership networks.

Significance. If the correctness proof is rigorous and the common coin is formally realized without hidden timing assumptions, the work would be significant as an optimal-resilience asynchronous BFT protocol with probability-1 agreement. The dynamic-membership extension would further broaden applicability, but these claims cannot be assessed without the missing model and proof details.

major comments (3)
  1. [Abstract] Abstract: the assertion of a correctness proof under the 1/3 fault threshold supplies no proof sketch, formal model, or verification steps, preventing evaluation of the claimed 'optimal model' for asynchronous BFT.
  2. [Common coin / randomization] Common-coin section: the protocol's ability to evade FLP while achieving probability-1 agreement rests on a reliable common-coin primitive supplying unbiased shared randomness in a fully asynchronous network; the manuscript treats this as an oracle without a construction, reduction, or proof that it introduces no timing assumptions or trusted setup.
  3. [Dynamic membership] Dynamic-membership section: the extension to nodes joining/leaving at will is presented as part of the contribution, yet it is unclear how the static-case correctness argument carries over without additional assumptions on membership changes or re-initialization of the common coin.
minor comments (1)
  1. Notation for the common coin and fault threshold should be defined consistently between the abstract and the protocol description.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight areas where additional detail would strengthen the manuscript, and we address each point below with plans for revision.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the assertion of a correctness proof under the 1/3 fault threshold supplies no proof sketch, formal model, or verification steps, preventing evaluation of the claimed 'optimal model' for asynchronous BFT.

    Authors: We agree that the abstract would benefit from a high-level sketch to support evaluation of the claims. The full formal model and proof appear in the body and appendix, but the revised version will incorporate a concise proof outline (key steps for agreement, validity, and probabilistic termination under <1/3 faults) directly into the abstract or introduction. revision: yes

  2. Referee: [Common coin / randomization] Common-coin section: the protocol's ability to evade FLP while achieving probability-1 agreement rests on a reliable common-coin primitive supplying unbiased shared randomness in a fully asynchronous network; the manuscript treats this as an oracle without a construction, reduction, or proof that it introduces no timing assumptions or trusted setup.

    Authors: The common coin is modeled as a standard primitive (as in prior randomized asynchronous BFT work) whose properties enable probability-1 agreement while respecting FLP. We will revise the section to include references to concrete realizations (e.g., via threshold cryptography or VRF-based constructions that require no timing assumptions or extra trusted setup) and explicitly state the reduction from protocol security to the primitive's properties. revision: yes

  3. Referee: [Dynamic membership] Dynamic-membership section: the extension to nodes joining/leaving at will is presented as part of the contribution, yet it is unclear how the static-case correctness argument carries over without additional assumptions on membership changes or re-initialization of the common coin.

    Authors: We will expand the dynamic-membership section with additional explanation and lemmas showing how the static-case arguments extend. This will cover epoch-based reconfiguration, handling of joins/leaves, and maintenance of the common-coin primitive across membership changes without introducing new timing assumptions. revision: yes

Circularity Check

0 steps flagged

No circularity; protocol and proof presented as independent construction

full rationale

The paper introduces PARSEC as a new leaderless asynchronous BFT algorithm and states that its correctness is proved under the standard <1/3 Byzantine fault bound, using a common coin primitive for randomization to evade FLP. No equations, definitions, or steps in the provided abstract reduce a claimed result to its own inputs by construction. The common coin is treated as an external modeling assumption rather than derived from the protocol itself. No self-citations, fitted parameters renamed as predictions, or uniqueness theorems imported from prior author work are referenced. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claim rests on standard distributed-computing assumptions about network asynchrony, fault thresholds, and the availability of a common coin; no free parameters or new invented entities are mentioned.

axioms (3)
  • domain assumption The communication network is fully asynchronous (arbitrary message delays, no timing bounds)
    Invoked to place the protocol in the FLP-impossible setting while still claiming probabilistic agreement.
  • domain assumption Fewer than one third of nodes are Byzantine faulty
    Standard threshold required for the claimed correctness proof in asynchronous BFT.
  • domain assumption A common coin primitive is available that supplies unbiased shared randomness
    Used explicitly to break symmetry and achieve agreement with probability one.

pith-pipeline@v0.9.0 · 5675 in / 1469 out tokens · 31270 ms · 2026-05-24T16:01:58.360351+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Distributed Key Generation

    Fackler A. Distributed Key Generation . https://github.com/poanetwork/hbbft/issues/47#issuecomment- 394422248

    work page

  2. [2]

    Optimistic Randomness for ABA

    Miller A. Optimistic Randomness for ABA . https://github.com/amiller/HoneyBadgerBFT/issues/63

    work page

  3. [3]

    Defining liveness

    Bowen Alpern and Fred B Schneider. Defining liveness. 21(4):181–185

    work page

  4. [4]

    On the computational complexity of gossip protocols

    Krzysztof R Apt, Eryk Kopczynski, and Dominik Wojtczak. On the computational complexity of gossip protocols. InIJCAI, pages 765–771

    work page

  5. [5]

    The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance

    Leemon Baird. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance

    work page

  6. [6]

    The promise, and limitations, of gossip protocols

    Ken Birman. The promise, and limitations, of gossip protocols. 41(5):8– 13. 24

    work page

  7. [7]

    Short signatures from the weil pairing

    Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. 17(4):297–319

    work page

  8. [8]

    Generalized flp impossibility result for t-resilient asynchronous computations

    Elizabeth Borowsky and Eli Gafni. Generalized flp impossibility result for t-resilient asynchronous computations. InProceedings of the twenty- fifth annual ACM symposium on Theory of computing, pages 91–100. ACM

    work page

  9. [9]

    Efficient gossip protocols for verifying the consistency of certificate logs

    Laurent Chuat, Pawel Szalachowski, Adrian Perrig, Ben Laurie, and Eran Messeri. Efficient gossip protocols for verifying the consistency of certificate logs. In 2015 IEEE Conference on Communications and Network Security (CNS), pages 415–423. IEEE

    work page 2015

  10. [10]

    Impossi- bility of distributed consensus with one faulty process

    Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossi- bility of distributed consensus with one faulty process

    work page

  11. [11]

    Lifting: lightweight freerider-tracking in gossip

    Rachid Guerraoui, Kévin Huguenin, Anne-Marie Kermarrec, Maxime Monod, and Swagatika Prusty. Lifting: lightweight freerider-tracking in gossip. In Proceedings of the ACM/IFIP/USENIX 11th International Conference on Middleware, pages 313–333. Springer-Verlag

    work page

  12. [12]

    Aleph: A leaderless, asynchronous, byzantine fault tolerant consensus protocol

    Adam Gągol and Michał Świętek. Aleph: A leaderless, asynchronous, byzantine fault tolerant consensus protocol

    work page

  13. [13]

    PARSEC reference implementation (WIP)

    MaidSafe. PARSEC reference implementation (WIP) . https://github.com/maidsafe/parsec

    work page

  14. [14]

    The honey badger of bft protocols

    Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft protocols. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 31–42. ACM

    work page 2016

  15. [15]

    Signature- freeasynchronousbyzantineconsensuswitht<n/3ando(n2)messages

    Achour Mostefaoui, Hamouma Moumen, and Michel Raynal. Signature- freeasynchronousbyzantineconsensuswitht<n/3ando(n2)messages. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 2–9. ACM

    work page 2014

  16. [16]

    To- wards an internet of trusted data: A new framework for identity and data sharing

    A Penland, David Shrier, T Hardjono, and I Wladawsky-Berger. To- wards an internet of trusted data: A new framework for identity and data sharing. 25

    work page

  17. [17]

    Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies

    Team Rocket. Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies

    work page

  18. [18]

    Byzantine Agreement, Made Trivial

    Micali S. Byzantine Agreement, Made Trivial. 26

    work page