pith. sign in

arxiv: 1907.03437 · v1 · pith:RZFJB64Wnew · submitted 2019-07-08 · 💻 cs.DC · cs.CR· cs.DS

Fair Byzantine Agreements for Blockchains

Tzu-Wei Chao , Hao Chung , Po-Chun Kuo This is my paper

Pith reviewed 2026-05-25 01:12 UTC · model grok-4.3

classification 💻 cs.DC cs.CRcs.DS
keywords Byzantine agreementfair validitysynchronous networkspartition resilienceresponsive protocolsblockchain consensusfault tolerance
0
0 comments X

The pith

A Byzantine agreement protocol achieves fair validity in synchronous networks while tolerating up to one-third corruptions.

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

The paper defines fair validity as a property that lower-bounds the expected number of times honest nodes' proposed values are selected when a Byzantine agreement protocol runs repeatedly. It proves no protocol can achieve this property in asynchronous networks. The authors then construct a protocol for synchronous networks that meets fair validity, terminates according to actual message delays rather than fixed bounds, and preserves safety even if the network partitions. This matters for blockchains because consensus outcomes often determine rewards, so unequal selection of honest values can skew incentives and participation.

Core claim

We propose a novel notion called fair validity for Byzantine agreement. Intuitively, fair validity lower-bounds the expected numbers that honest nodes' values being decided if the protocol is executed many times. However, we also show that any Byzantine agreement could not achieve fair validity in an asynchronous network, so we focus on synchronous protocols. This leads to our second contribution: we propose a fair, responsive and partition-resilient Byzantine agreement protocol tolerating up to 1/3 corruptions. Fairness means that our protocol achieves fair validity. Responsiveness means that the termination time only depends on the actual network delay instead of depending on any pre-orded

What carries the argument

The fair validity property, which lower-bounds the expected selection frequency of honest values, realized through a synchronous protocol that is also responsive and partition-resilient.

If this is right

  • Repeated executions of the protocol will select honest nodes' values at a guaranteed minimum expected rate.
  • The protocol terminates in time that depends only on the actual network delay.
  • Safety holds even when the network is partitioned, with termination resuming once the partition ends.
  • The guarantees hold while tolerating up to one-third corrupt nodes.

Where Pith is reading between the lines

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

  • Blockchains adopting this protocol could see more balanced reward distributions tied to consensus outcomes.
  • The fairness definition might extend to related primitives such as leader election in distributed systems.
  • Approximate versions of fair validity could be studied under partial synchrony if exact fairness remains impossible.

Load-bearing premise

The network must be synchronous with bounded message delays, because the paper proves fair validity is impossible without that assumption.

What would settle it

A concrete execution of the protocol in a synchronous network with one-third corruptions where the measured frequency of honest value selections falls below the claimed lower bound would falsify the achievement of fair validity.

Figures

Figures reproduced from arXiv: 1907.03437 by Hao Chung, Po-Chun Kuo, Tzu-Wei Chao.

Figure 1
Figure 1. Figure 1: The histogram of latency of RBA. For HBA , the experiment repeats 715 times and the histogram is shown in [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The histogram of latency of HBA. VII. SIMULATION To demonstrate the performance, responsiveness, and partition-resilience of HBA, we implement three other Byzan￾tine agreements and compare the simulation results. The three protocols are PBFT [7], the synchronous BA proposed by Abraham et al. (ADD+19) [10] (the version against static adversary), and Algorand agreement [5]. Let n be the number of nodes, f be… view at source ↗
Figure 3
Figure 3. Figure 3: Confirmation time of each Byzantine Agreement: [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Bandwidth cost and confirmation time of each Byzan [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
read the original abstract

Byzantine general problem is the core problem of the consensus algorithm, and many protocols are proposed recently to improve the decentralization level, the performance and the security of the blockchain. There are two challenging issues when the blockchain is operating in practice. First, the outcomes of the consensus algorithm are usually related to the incentive model, so whether each participant's value has an equal probability of being chosen becomes essential. However, the issues of fairness are not captured in the traditional security definition of Byzantine agreement. Second, the blockchain should be resistant to network failures, such as cloud services shut down or malicious attack, while remains the high performance most of the time. This paper has two main contributions. First, we propose a novel notion called fair validity for Byzantine agreement. Intuitively, fair validity lower-bounds the expected numbers that honest nodes' values being decided if the protocol is executed many times. However, we also show that any Byzantine agreement could not achieve fair validity in an asynchronous network, so we focus on synchronous protocols. This leads to our second contribution: we propose a fair, responsive and partition-resilient Byzantine agreement protocol tolerating up to 1/3 corruptions. Fairness means that our protocol achieves fair validity. Responsiveness means that the termination time only depends on the actual network delay instead of depending on any pre-determined time bound. Partition-resilience means that the safety still holds even if the network is partitioned, and the termination will hold if the partition is resolved.

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

2 major / 1 minor

Summary. The paper introduces a new notion called fair validity for Byzantine agreement, which lower-bounds the expected frequency with which honest nodes' proposed values are decided across repeated executions. It claims to prove that no Byzantine agreement protocol can achieve fair validity in asynchronous networks and therefore restricts attention to the synchronous case, where it constructs a protocol that simultaneously achieves fair validity, responsiveness (termination time depends only on actual delay), and partition resilience while tolerating up to one-third corruptions.

Significance. If the impossibility result and the synchronous construction are correct, the work would be significant for blockchain consensus because it augments the traditional safety/liveness definitions with an explicit fairness property relevant to incentive-driven settings. The combination of responsiveness and partition resilience under a standard corruption threshold would also be practically useful. The impossibility result would usefully delineate the model assumptions required for fairness.

major comments (2)
  1. [Abstract] Abstract: the statement that 'any Byzantine agreement could not achieve fair validity in an asynchronous network' is presented without a formal definition of fair validity, without a precise network model or adversary, and without even a proof sketch. This claim is load-bearing for the subsequent decision to restrict the construction to synchronous protocols.
  2. [Abstract] Abstract: the synchronous protocol is announced only at the level of properties ('we propose a fair, responsive and partition-resilient Byzantine agreement protocol tolerating up to 1/3 corruptions') with no pseudocode, no security argument, and no indication of how the protocol simultaneously satisfies fair validity, responsiveness, and partition resilience. The absence of any construction detail prevents verification of the central positive result.
minor comments (1)
  1. [Abstract] The abstract contains minor grammatical and phrasing issues (e.g., 'the outcomes of the consensus algorithm are usually related to the incentive model, so whether each participant's value has an equal probability of being chosen becomes essential') that should be cleaned up in a revision.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major comment below by clarifying the location of formal details in the manuscript and indicating any planned revisions to the abstract.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the statement that 'any Byzantine agreement could not achieve fair validity in an asynchronous network' is presented without a formal definition of fair validity, without a precise network model or adversary, and without even a proof sketch. This claim is load-bearing for the subsequent decision to restrict the construction to synchronous protocols.

    Authors: The abstract provides a high-level overview consistent with standard practice for such summaries. The formal definition of fair validity is given in Section 2, the precise network model and adversary appear in Section 3, and the impossibility result with its full proof is developed in Section 4. We will revise the abstract to include a brief parenthetical reference to these sections for improved readability. revision: partial

  2. Referee: [Abstract] Abstract: the synchronous protocol is announced only at the level of properties ('we propose a fair, responsive and partition-resilient Byzantine agreement protocol tolerating up to 1/3 corruptions') with no pseudocode, no security argument, and no indication of how the protocol simultaneously satisfies fair validity, responsiveness, and partition resilience. The absence of any construction detail prevents verification of the central positive result.

    Authors: The abstract is a concise summary and does not contain pseudocode or proofs, as is conventional. The protocol construction with pseudocode is presented in Section 5. The security arguments establishing each property (fair validity, responsiveness, and partition resilience) and demonstrating that they hold simultaneously under the stated corruption threshold are provided in Section 6. The body of the paper therefore supplies the necessary details for verification. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines fair validity as a new property, proves its impossibility under asynchrony (justifying the synchronous focus), and constructs a protocol achieving it plus responsiveness and partition resilience under 1/3 faults. This chain relies on external network-model assumptions and standard BA techniques rather than any self-definition, fitted input renamed as prediction, or load-bearing self-citation. No equations or parameters reduce by construction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; full definitions, proofs, and any hidden parameters or modeling assumptions are unavailable. No free parameters, axioms, or invented entities can be extracted.

pith-pipeline@v0.9.0 · 5796 in / 1168 out tokens · 18157 ms · 2026-05-25T01:12:55.288008+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

  1. [1]

    The byzantine generals prob- lem,

    L. Lamport, R. Shostak, and M. Pease, “The byzantine generals prob- lem,” ACM Transactions on Programming Languages and Systems , vol. 4, pp. 382–401, jul 1982

    work page 1982

  2. [2]

    The consensus problem in unreliable distributed systems (a brief survey),

    M. J. Fischer, “The consensus problem in unreliable distributed systems (a brief survey),” in Foundations of Computation Theory , pp. 127–140, Springer Berlin Heidelberg, 1983

    work page 1983

  3. [3]

    Algorand

    J. Chen and S. Micali, “Algorand,” CoRR, vol. abs/1607.01341v9, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  4. [4]

    Hybrid consensus: Efficient consensus in the permissionless model,

    R. Pass and E. Shi, “Hybrid consensus: Efficient consensus in the permissionless model,” in 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria (A. W. Richa, ed.), vol. 91 of LIPIcs, pp. 39:1–39:16, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017

    work page 2017

  5. [5]

    Algorand agreement: Super fast and partition resilient byzantine agreement,

    J. Chen, S. Gorbunov, S. Micali, and G. Vlachos, “Algorand agreement: Super fast and partition resilient byzantine agreement,” IACR Cryptology ePrint Archive, vol. 2018, p. 377, 2018. 6When the messages are delayed maliciously, the agreement of ADD+19 may be broken. However, such a network condition is beyond their assump- tion

    work page 2018

  6. [6]

    Validated asynchronous byzantine agreement with optimal resilience and asymptotically optimal time and word communication,

    I. Abraham, D. Malkhi, and A. Spiegelman, “Validated asynchronous byzantine agreement with optimal resilience and asymptotically optimal time and word communication,” 2018

    work page 2018

  7. [7]

    Practical byzantine fault tolerance,

    M. Castro and B. Liskov, “Practical byzantine fault tolerance,” in Proceedings of the Third Symposium on Operating Systems Design and Implementation , OSDI ’99, (Berkeley, CA, USA), pp. 173–186, USENIX Association, 1999

    work page 1999

  8. [8]

    Consensus in the presence of partial synchrony (preliminary version),

    C. Dwork, N. A. Lynch, and L. J. Stockmeyer, “Consensus in the presence of partial synchrony (preliminary version),” in Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, Vancouver, B. C., Canada, August 27-29, 1984 , pp. 103– 118, 1984

    work page 1984

  9. [9]

    Verifiable random functions,

    S. Micali, M. Rabin, and S. Vadhan, “Verifiable random functions,” in Proceedings of the 40th Annual Symposium on the Foundations of Computer Science, (New York, NY), pp. 120–130, IEEE, October 1999

    work page 1999

  10. [10]

    Synchronous byzantine agreement with expected O(1) rounds, expected O(n2) com- munication, and optimal resilience,

    I. Abraham, S. Devadas, D. Dolev, K. Nayak, and L. Ren, “Synchronous byzantine agreement with expected O(1) rounds, expected O(n2) com- munication, and optimal resilience,” in 23rd International Conference on Financial Cryptography and Data Security , FC’19, pp. 429–445, 2019. APPENDIX A DEFINITION OF VRF The definition is paraphrased from [9]. Definition 2...

    work page 2019

  11. [11]

    KeyGen takes as input a security parameter κ and outputs a pair of key (pk,sk )

    work page

  12. [12]

    Prove takes as input a seed x and a secret key sk; it outputs a value Fsk(x) and a proof πsk(x)

    work page

  13. [13]

    Let a : N → N ∪ {∗} and a : N → N be any functions such that a(κ) and b(κ) are computable in time poly(κ)

    Veri takes as input (pk,x,y,π ); it verifies whether y = Fsk(x) by using the proof π and key pk. Let a : N → N ∪ {∗} and a : N → N be any functions such that a(κ) and b(κ) are computable in time poly(κ). We say (KeyGen, Prove, Veri) is a verifiable random function with input length a(κ) and output length b(κ) if the following properties hold:

    work page

  14. [14]

    If (y,π ) = Prove(sk,x ), then Pr[Veri(pk,x,y,π ) = yes] ≥ 1 − negl(κ)

    Correctness. If (y,π ) = Prove(sk,x ), then Pr[Veri(pk,x,y,π ) = yes] ≥ 1 − negl(κ)

    work page

  15. [15]

    For every (pk,x,y 1,y 2,π 1,π 2) such that y1 ̸=y2, the following holds for either i = 1 or i = 2: Pr[Veri(pk,x,y i,π i) = yes] ≤ negl(κ)

    Uniqueness. For every (pk,x,y 1,y 2,π 1,π 2) such that y1 ̸=y2, the following holds for either i = 1 or i = 2: Pr[Veri(pk,x,y i,π i) = yes] ≤ negl(κ)

    work page

  16. [16]

    (Sketched) Any probabilistic poly- nomial time adversary cannot distinguish the output of a VRF from a uniform random variable

    Pseudorandomness. (Sketched) Any probabilistic poly- nomial time adversary cannot distinguish the output of a VRF from a uniform random variable. Intuitively, pseudorandomness requires that the output of a VRF should be indistinguishable from a string sampled from a uniform distribution. APPENDIX B PROOF IN RBA A. Agreement Lemma. Assumet ≤tmax. Suppose a...

    work page

  17. [17]

    Take as input a seed x and a secret key sk

    work page

  18. [18]

    Overi is defined as:

    Return Prove(x,sk ). Overi is defined as:

    work page

  19. [19]

    Take as input a public key pk, a seed x, a value y and a proof π

    work page

  20. [20]

    We also define the ideal functionality of VRF, consisting of two algorithm: Iprove and Iveri

    Return Veri(pk,x,y,π ). We also define the ideal functionality of VRF, consisting of two algorithm: Iprove and Iveri. Iprove is defined as:

    work page

  21. [21]

    Takes as input a seed x and a secret key sk

    work page

  22. [22]

    If not, choose y ← {0, 1}ℓ andπ ← {0, 1}ℓ uniformly at random

    Check whether Q(x,sk ) is defined. If not, choose y ← {0, 1}ℓ andπ ← {0, 1}ℓ uniformly at random. Then, set Q(x,sk ) = (y,π ). If Q(x,sk ) is defined, Iprove(x,sk ) return Q(x,sk ). Iveri is defined as:

    work page

  23. [23]

    Takes as input a public key pk, a seed x, a value y and a proof π

    work page

  24. [24]

    If not, return false; otherwise, return true

    Check whether Q(x,sk ) is defined. If not, return false; otherwise, return true. In the ideal world, all the nodes does not compute and verify the value of VRF locally. Instead, they query the oracle Iprove and Iveri. All the else operations are the same as RBA. Lemma 21 (fairness in the ideal world) . Suppose the network is synchronous. Then, in the ideal...

    work page