# Proof-of-Eligibility and Ephemeral participation to Solve Consensus in a Permissionless Environment

Emmanuelle Anceaume, Robin Frédérique, Bruno Sericola

► To cite this version:

Emmanuelle Anceaume, Robin Frédérique, Bruno Sericola. Proof-of-Eligibility and Ephemeral participation to Solve Consensus in a Permissionless Environment. 2025. hal-05423728

HAL Id: hal-05423728

https://cnrs.hal.science/hal-05423728v1

Preprint submitted on 18 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Proof-of-Eligibility and Ephemeral participation to Solve Consensus in a Permissionless Environment

## ANONYMOUS AUTHOR(S)

We consider a large scale and permissionless system, that is a system in which users can join and leave at any time without any preliminary indication to their application. We also consider that a percentage of these users are malicious, that is exhibit an arbitrary behavior. These users can collide together. This is modeled by an oblivious adversary. In such a system, we propose a probabilistic consensus algorithm that allows all the correct users to decide on the same set of values. Specifically, with any probability larger than $1 - \epsilon$, if any two correct users decide a set of values, then those sets are exactly the same. This holds even if the adversary tries to prevent convergence to the same set of values. Handling the adversarial nature of the system is achieved through proof-of-eligibility, ephemeral participation and the introduction of a broadcast factor $\lambda$. Altogether, they guarantee with probability larger than $1 - 2\epsilon$ that any transaction initially broadcast by any correct user will belong to the decision value, and that any two decision values contain exactly the same set of transactions, whatever the adversarial nature of the execution. Finally, any consensus execution terminates in six asynchronous rounds. A straightforward application of our consensus algorithm is the design of permissionless distributed ledgers.

CCS Concepts: • **Theory of computation** → **Distributed algorithms**.

Additional Key Words and Phrases: consensus algorithm, proof of eligibility, aggregation, asynchronous and permissionless environment, adaptive adversary.

## ACM Reference Format:

Anonymous Author(s). 2018. Proof-of-Eligibility and Ephemeral participation to Solve Consensus in a Permissionless Environment. 1, 1 (August 2018), 23 pages. https://doi.org/XXXXXXX.XXXXXXX

## 1 Introduction

Permissionless blockchains aim to achieve the impressive result of being a persistent, distributed, consistent, and continuously growing log of transactions, publicly auditable and writable by anyone without demanding the presence of a trusted third party [18]. Designing algorithms in a permissionless system must deal with the challenge of unknown players (the set of distinct entities that might run the algorithm is unknown as well as its cardinality), the challenge of inactivity of players (involved entities can stop and resume their execution at any time), and the Sybil challenge (the adversary can masquerade as many) [15]. The general approach to handle those challenges is to implement a pseudo-random lottery, weighted according to a particular resource, which selects a collection of distinguished parties (specifically addresses or identifiers). The source of randomness must not be biased by any adversarial strategy, and the outcome of the lottery must be unpredictable and Sybil-proof. For example, in the case of Bitcoin [18] the underlying resource is the hashing power that allows Proofs of Work (PoW); in the case of Ouroboros [4] and Algorand [12], it is the virtual stake in the resource, which allows Proofs of Stake (PoS). In Proof-of-Work, pseudorandomness is in some sense external to the cryptocurrency: the first miner to successfully find a good nonce produces the next block, and

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

© 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM.

Manuscript submitted to ACM
this miner is selected completely independently of the current state of the cryptocurrency. Unfortunately, resilience of PoW-based solutions fundamentally relies on the massive use of computational resources, which is a real issue today.

¹ In contrast, in solutions based on proof-of-stake (PoS) the pseudorandomness comes from within the cryptocurrency itself. All the information needed to verify the legitimacy of a stakeholder to create a block (i.e., crypto-currency possession) is already stored in the blockchain. PoS-based solutions split into two main approaches: longest-chain paradigm (also called Nakamoto-style approach) and iterated Byzantine fault-tolerant consensus.

In the former one followed by some large proof-of-stake cryptocurrencies such as Snow White and Cardano (e.g. [4, 8, 9, 14]), a snapshot of current participants' status is taken periodically (i.e., at each synchronous epoch), from which zero, one or several lottery leaders are charged with proposing the next block. Most PoS protocols implement their lottery by relying on an internal random beacon, which is based on the state of the chain. These random beacons are vulnerable, to some extent, to grinding attacks where an adversary grinds through the block space in order to bias the randomness and find a value for which an unfair advantage can be extracted [5]. The grinding works as follows: whenever the adversary is elected leader, it can decide to publish its block or skip the round, thus biasing the randomness. Bagaria et al. [5] studied the security of PoS protocols where the randomness is updated every c blocks and the trade-offs between updating the randomness more frequently (and being more vulnerable to grinding) or less frequently (and being more predictable) [5]. In the second approach, PoS protocols iterate BFT consensus executions to create one block at a time. Most BFT-based protocols have the concept of a leader in each round, and the consensus goal of each round is for everyone to agree on the leader's proposed block. Leader selection is challenging, though: it should be done proportional to stake, but in a way that neither relies on a trusted external source of randomness nor is manipulable by participants. Each round of the consensus is run among the winners of a lottery, i.e., block leaders and block verifiers. Block verifiers are in charge of voting for one of the block leader, leader whose block will be the next block of the blockchain. For instance, Algorand [12] is based on verifiable random functions (VRFs). The VRF is used to identify a few potential leaders that must manifest and then proceed to choose a winner among them by using some tie-breaker method (e.g., smallest VRF output). The weakness of the proposed approach is that the final leader does not know that she is the leader until all the potential leaders publish their values. In addition, the users that do not receive the winner's output might incorrectly believe that a different leader was elected, which can lead to a fork in the chain.

The objective of this work is to propose an iterated Byzantine fault tolerant consensus-based solution, dedicated to a permissionless and asynchronous setting. Our solution, called merge consensus, deeply relies on ephemeral but provable user identities, and repeatedly combines a verifiable random function and a cryptographic sortition scheme to sub-sample users as a function of their current stake and the consensus round number. Elected users form the consensus committee for the specified round and propagate the set of values received from the previous round. To defend against an adaptive and rushing adversary whose aim is to delay arbitrarily long convergence to a unique set of values, the merge consensus algorithm prunes at a certain point any value that has not been sufficiently propagated. We prove that six rounds are necessary and sufficient to guarantee that any two correct users decide on the same set of values at the end of the 6-th round, and that all values proposed by each correct user belong to the decision set.

To fit the context of blockchains, users propose a set of transactions as their input values, and the decision value is a set of transactions. By introducing the notion of diffusion factor $\lambda$, our solution prevents the adversary from continuously revealing transactions with parsimony to arbitrarily delay convergence to a unique set of transactions.

<footnote n="1">¹Numerous investigations have been devoted to find a secure alternative to PoW, but most of them either rely on the intensive use of a large quantity of physical resources (e.g. proof-of-space [3], proof-of-space/time [17]) or make compromises in their trust assumptions (e.g. proof-of-elapsed-time [13], delegated proof-of-stake [11]).</footnote>
The remainder of the paper is organised as follows. Section 2 presents the model of system in terms of synchrony, communication, security, and user transactions. Section 3 specifies the problem addressed in this paper. Section 4 positions the contribution of this work with respect to the state of the art. Section 5 describes the main tenets of our consensus algorithm. Section 6 presents an in-depth analysis of our algorithm. Section 7 concludes.

## 2 System assumptions

*Asynchronous and permissionless system.* By permissionless we mean a distributed system in which (i) the number of participants for carrying out the protocol is not known before hand, is not even known during the course of the execution, and may change over time, (ii) the right to contribute and to participate is not controlled by a (trustworthy) third authority, i.e. we do not assume the presence of any public key infrastructure (PKI), and (iii) participants communicate over a reliable connected communication topology. We assume an asynchronous environment, that is our algorithm does not make any synchrony assumptions, i.e. does not assume any bounds on the time needed for a message to be received by its recipients, nor on the computation time of the processes, nor on the individual drifts of clocks.

*Cryptographic functions.* Users have access to basic cryptographic functions, including a cryptographic hash function $h$ and an asymmetric signature scheme that allows a user to generate a public and secret key pairs $(sk, pk)$, and compute a signature $\sigma_{sk,h}(d)$ of any message $d$. Function $h$ is modeled as a random oracle. Our algorithm relies on verifiable random functions (VRFs). A Verifiable Random Function (VRF) [16] is the public-key version of a keyed cryptographic hash. It is a pseudorandom function that provides a proof of its correct computation. Only the holder of the private key $sk$ can compute the hash, but anyone with corresponding public key $pk$ can verify the correctness of the hash. A VRF hashes an input $m$ using the private key $sk$ to obtain a VRF hash output $\beta = \text{VRF}(sk, m)$, commonly denoted as $\beta = \text{VRF}_{sk}(m)$, such that $\beta$ will always be unique for a given input message and a public key. Function VRF is also modeled as a random oracle, and is deterministic, in the sense that it always produces the same output $\beta$ given a pair of inputs $(sk, m)$. The private key $sk$ is also used to construct a proof $\pi$ showing that $\beta$ is the correct hash output, i.e. $\pi = \text{VRF\_prove}_{sk}(m)$. We adopt the following notation $\langle \beta, \pi \rangle = \text{VRF}_{sk}(m)$.

*Public Keys as Identities principle [7].* Users own some minimal amount of stake (i.e., money), which gives them the right to participate to the algorithm. We adopt (a simplified version of) what is commonly known as the Bitcoin Unspent Transaction Output (UTXO) model. An UTXO can be roughly seen as a user's account credited by some stake. An UTXO is uniquely characterised by a key pair $(pk, sk)$ and its associated amount of stake. Each public key is related to the digital signature schema with the uniqueness property, which allows stakeholders to use the public keys (or a hash thereof) of their UTXOs as a reference to them, as demonstrated in the "Public Keys as Identities principle" of Chaum [7]. Hence user $u$ is publicly known as $pk_u$ if $u$ owns the UTXO whose key pair is $(pk_u, sk_u)$. An UTXO is created when it appears for the first time in the output set of a transaction, and once it is referenced in the input set of another transaction, it cannot be used anymore. Hence, by using UTXOs as user identities, a user owns as many verifiable identities as he wants. Since UTXOs are ephemeral, the number of users continuously varies with the activity of the system.

**REMARK 1.** In the following, when we say that UTXO $(pk_u, sk_u)$ is selected to perform some action we mean the user that owns this UTXO is selected to perform some action. Symmetrically, when we say that some user $u$ executes some action we mean the owner of UTXO $\langle pk_u, sk_u \rangle$ executes some action.
**Threat model: An adaptive adversary.** We assume the presence of Byzantine (i.e. malicious) users which controls up to $p^{\mathcal{A}} < 1/3$ of the total amount of stake currently available in the system. This model, named the "stake threshold adversary" by Abraham and Malkhi [2], is an alternative to the common threshold adversary model, which bounds the total number of parties the adversary controls relative to the total population of the system, and an extension of the computational threshold adversary introduced by Bitcoin, which bounds the proportion of the computational power owned by parties. Byzantine users can deviate from the protocol. They are modeled by an adversary that perfectly coordinates their actions. Any (syntactically correct) message sent by the adversary is immediately received by all correct users. On the other hand, the adversary cannot prevent a correct user from sending a message et cannot prevent the recipient of this message from receiving it. This is known as "after-the-fact message removal" attack: if the adversary corrupts a party $p$ after $p$ sends a message, the adversary cannot prevent that message from being delivered. This avoids the lower bound of Abraham et al [1]. Further the adversary is adaptive: it can select at any time which users to corrupt in replacement of corrupted ones as long as it does not control more than $p^{\mathcal{A}}$ of the total amount of stake currently available in the system (i.e. corruptions are "moving"). The adversary is computationally bounded so that it can neither forge correct users' signatures nor break the hash function and the signature scheme. Finally, we assume that all users (correct and malicious) share an initial knowledge that we call *genesis block* which contains an initial arbitrary UTXO set. We assume this block also shares the same properties as regular blocks. How to setup the genesis block is out of the scope of this paper.

### 3 The addressed problem: the merge consensus

While the overall goal of this work is to build a permissionless blockchain in a Proof-of-Eligibility (PoE) setting, this article is devoted to the design of a consensus algorithm that solves the merge consensus problem. Specifically, a solution to the merge consensus problem should satisfy Validity, Agreement and Termination with any probability greater than $1 - \varepsilon$. Specifically, let $\mathcal{T}_u$ be the set of transactions decided by some correct user $u$ in the system. $\mathcal{T}_u$ is called the decision value of user $u$.

* **Validity:** For any correct user $u$, any decision value $\mathcal{T}_u$ contains at least all the transactions initially broadcast by correct users, with probability larger than $1 - 2\varepsilon$;

* **Agreement:** For any two correct users $u$ and $v$, $u \neq v$, that respectively decide $\mathcal{T}_u$ and $\mathcal{T}_v$ then $\mathcal{T}_u = \mathcal{T}_v$ with probability larger than $1 - 2\varepsilon$;

* **Termination:** Each correct user $u$ eventually outputs its decision value $\mathcal{T}_u$.

### 4 State of the art

The cryptocurrency community is at the origin of blockchains whose consensus mechanism relies on proof-of-stake consensus. We can cite Algorand [12], Snow White [8], Ouroboros [14], Ouroboros Praos [9] and Ouroboros Genesis [4] as example of such systems. All these solutions are accompanied by a formal security proof that they achieve a well defined set of desirable properties. This may rely on a strong restriction of the dynamic availability of participants. For example, Snow White [8], Ouroboros [14], Ouroboros Praos [9] require an honest blockchain to be delivered as trusted 'advice' to any joining party, a form of 'checkpointing'. This solves the problem of joining parties getting up to speed with the correct chain. This is indeed a challenge that needs to be faced, but arguably a strong assumption. The PoS protocol Algorand [12] does not require such checkpointing or parties being regularly online, however, it requires a good estimate on participation to be fixed in the protocol, thus forfeiting dynamic availability as well. This requirement
stems from the fact that the cryptographic lottery samples committee members based on the full stake of the system. Specifically, at each round a user computes a VRF, and if the result is smaller than a threshold, he is chosen as a block proposer. Multiple users can become a block proposer. However, the algorithm does not wait until users converge to one chain. Algorand uses Fast Byzantine Algorithm, which runs in rounds, where elected committee (users who are block proposers) diffuses a message. The Algorand protocol is slow to terminate in the worst case (due to its exponential backoff), but when the network is good for long periods of time, it can terminate executions of consensus executions in reasonable time. Algorand [12] needs less than 1/3 of the stake of the system to be held by malicious parties.

Execution in Ouroboros [14], Ouroboros Praos [9], Ouroboros Genesis [4] and Ethereum with proof-of-stake [10] is organised in synchronous slots during which the current leader proposes its set of pending transactions to be decided. To ensure that slot leaders are chosen from the appropriate stake distribution, multiple slots are collected into epochs, each of which contains a given number of slots. During an epoch *e*, the stake distribution that is used for the slot-leader election corresponds to the distribution recorded in the ledger up to the last block of epoch (*e* − 2). Ouroboros [14] achieves only “semi-adaptive” security (corruptions with delay). On the other hand, Ouroboros Genesis [4] can tolerate fully adaptive adversaries assuming that all parties have access to a global clock. Snow White [8] and Ouroboros Praos [9] achieve the optimal 1/2 bound, at the cost of needing a checkpointing functionality to accommodate joining parties. The main design goal of Ethereum’s proof-of-stake is to keep using a Nakamoto-style consensus. The consensus protocol relies on validators. A validator is any user that “stake” an amount of 32 ETH, the native cryptocurrency of Ethereum. Validators have synchronised clocks, and time is measured by periods of 12 seconds exactly, called slots. Blocks are created by randomly chosen validators. A seed of randomness is constructed by applying the xor operation on a specific field of each block of an epoch (an epoch is made of 32 slots). The seed created during epoch *e* is used to draw which validators will be in charge of creating their block during epoch (*e* + 2). Note that slots might be empty.

Finally, we have published a preliminary and short version (four pages) of this paper in the proceedings of an peer-reviewed international conference [BLINDED].

## 5 The merge consensus algorithm

The algorithm we propose to implement the merge consensus specification is made up of a sequence of asynchronous rounds during which successive committees try to converge to a unique set of transactions, each of these transactions having been proposed by committee members of round 0.

By adopting the nice idea of user replacement [12], each asynchronous round $r$, $r \ge 0$, is run by a dynamically created committee whose members are selected among all the users (i.e. UTXO owners) of the system at round $r$. Selection is achieved in a random, unpredictable, and non-interactive way. To prevent an adaptive adversary from manipulating committee members during round $r$, $r \ge 0$, the action of each committee member is limited to a unique step of computation followed by a unique step of communication. Hence, if the adversary eavesdrops a message from a committee member $u$, it is too late for the adversary to manipulate $u$ since $u$ will not execute any more steps in round $r$, and possibly in any other rounds of the algorithm. Recall that users are "short-lived" (a user is alive as long as its UTXO has not been spent).

To prevent the adversary from postponing arbitrarily long the round at which all correct committee members will be able to converge to a unique set of transactions, we introduce the notion of diffusion factor $\lambda$. This factor is only used at round 3 of the algorithm. Although very simple, such a construction prevents the adversary from revealing transactions with parsimony beyond round 1.
## 5.1 Participation via a Proof-of-Eligibility (PoE)

Selection of committee members relies on a Proof-of-Eligibility (PoE). Since Algorand [12], PoEs have become essential in the design of permissionless distributed ledgers. PoEs allow us to decide who is in charge of executing an action. When the eligibility is found out by each one individually, it is called a cryptographic sortition scheme, i.e. the opportunity to determine if you are the winner of a “lottery” depends on you alone. Cryptographic sortition needs to fulfil three main properties. First, entities should be able to determine by themselves whether they are eligible to perform a certain action. Second, the eligibility should be verifiable by other entities. Third, a cryptographic sortition is associated with a single identity, i.e. entities need to be sure that the proof was generated by the entity claiming it. Additionally, one would also like that the proof is indistinguishable from random. Note that in contrast to cryptographic sortition, PoW cannot be attributed to a single user which explains the development of mining pools. Concretely, cryptographic sortition relies on the properties of verifiable random functions (VRFs) [16] and random sampling. The idea of our algorithm is to select, at each round of the algorithm, a random subset of users proportionally to the amount of stake credited on user UTXOs. Correctness of our cryptographic sortition is ensured by guaranteeing that no obvious Byzantine strategy such as a concentration of the stake on a single manipulated UTXO or a massive sub-division of stake on a multitude of compromised UTXOs (Sybil attack), can bias user random selection.

Cryptographic sortition exports two functions: the `DRAW` and `VERIFYDRAW` functions. Function `DRAW` is a private function which allows users (i) to determine by themselves whether they are selected as a committee member of a given round $r$ of the consensus algorithm, and (ii) to provide later and if necessary a proof of soundness of this selection. The `DRAW` function, whose pseudo-code is given in Algorithm 1, when invoked by UTXO $< sk_u, pk_u >$, has six arguments: the current round $r$, the secret key $sk_u$ of the UTXO, a seed `seed` from which comes the randomness of the sortition, the expected positive quantity of stake $\tau$ selected by the current sortition, the quantity of stake $w_u$ credited on UTXO $< sk_u, pk_u >$, and the total current positive quantity of stake $W$ owned by all the users of the system. Computation of the seed is based on the most recent pieces of information known by every user. In our case, this is the hash of the last created block, that is the hash of the decision value decided by the preceding instance of the merge-consensus. In the following we omit to include the instance number as parameter of the merge-consensus algorithm not to overload the pseudo-codes. The knowledge of $W$ is obtained by successively reading all the blocks of the blockchain. Function `DRAW` is made of two steps, first a call to a VRF function which calculates a random and verifiable number $h_u$, and a weighted random sampling seeded with $h_u$. This weighted random sampling computes the voting weight $vote_u$ of UTXO $< sk_u, pk_u >$ during round $r$ according to the quantity of stake credited on this UTXO. This voting weight is used by UTXO $< sk_u, pk_u >$ during round $r$ of the consensus algorithm. If at round $r$ $vote_u$ is equal to 0, user $u$ cannot participate to the $r$-th round of the consensus algorithm. Otherwise, $vote_u$ gives $u$ the right to belong to the committee of round $r$, and represents the weight of $u$'s vote during round $r$.

Specifically, let $vote_u$ be the random variable representing the voting weight of UTXO $< sk_u, pk_u >$ as computed by function `DRAW`. Random variable $vote_u$ has a binomial distribution $\mathcal{B}(w_u, p)$ where probability $p$ is equal to $\tau/W$. By definition of $\tau$, we have $p > 0$. The probability that UTXO $< sk_u, pk_u >$ is selected is thus $1 - (1 - \frac{\tau}{W})^{w_u}$. By independence, whatever the sub-division $w_1 + w_2 = w$ of $w$, the distribution of the weight associated with $w$ is the same as the sum of the weight associated with $w_1$ and $w_2$: $\mathcal{B}(w, p) = \mathcal{B}(w_1, p) + \mathcal{B}(w_2, p)$. This guarantees that an adversary has no advantage in launching a Sybil attack: an adversary can create as many UTXOs as it wants, what will influence the probability of winning is the total amount of stake the adversary owns on all its UTXOs, not the number of UTXOs. Notation $\mathcal{B}(k, w_u, p)$ in Algorithm 1 represents the probability mass function of the Binomial distribution,
<figure><img src="image_2.png" /><figcaption>Fig. 1. Probabilities $P_{w_u}$ (Relation (1)) as a function of the stake $w_u$. The total quantity of stake $W$ is set to $10^5$.</figcaption></figure>

UTXO $u$ with stake $w_u$ is chosen more than once during the $r+1$ rounds of Algorithm 3 is denoted $P_{w_u}$ and given by

$$ 
\begin{aligned}
P_{w_u} &= 1 - ((1-p)^{w_u})^{r+1} - (r+1)((1-p)^{w_u})^r \binom{w_u}{1} p(1-p)^{w_u-1} \\
&= 1 - (1-p)^{r+1}w_u \left(1 + (r+1)w_u \frac{p}{1-p}\right).
\end{aligned} 
\quad (1) $$

Probability $P_{w_u}$ is increasing with $w_u$ (as illustrated by Figure 1). This confirms the interest of spreading user stake over multiple UTXOs: it allows us to dimension $w_u$ to limit the adversary probability of guessing which UTXO is going to be chosen at least twice during a merge-consensus execution. Note that in Algorand [12], the selection of users is done proportionally to the total amount of stake they own. This increases the likelihood that users will be chosen at least twice during a merge-consensus execution. If the adversary has the capability to observe and detect the wealthiest users along the rounds of the algorithm (those with high voting weight), it might make a DoS attack on them. By doing this, the adversary will prevent round progress by making the number of votes within any given round insufficient.

## 5.3 Aggregating sets of transactions

Any correct user of the system invokes the merge-consensus algorithm (invocation of Propose()). From above, in expectation, for each round $r$, a quantity $\tau$ of stake is randomly selected among the total quantity $W$ currently present in the system. In the following we assume that the following parameters are public knowledge (see Section 5.1): the seed of the current instance of the consensus, the expected number of stake $\tau$ selected by the lottery, the total quantity of stake $W$ in the system, and the broadcast factor $\lambda$. The objective of the merge-consensus algorithm is to aggregate valid transactions that are initially pending at users. A transaction is valid if none of its referenced UTXOs have already been spent in some transactions belonging to a previous decision value (i.e., in a block belonging to the blockchain). In
<caption>**Algorithm 3:** Merge consensus run by UTXO <pk<sub>u</sub>, sk<sub>u</sub>> with stake w<sub>u</sub></caption>

1 **Propose** ():
2 &nbsp;&nbsp;&nbsp;&nbsp;`r` &harr; 0
3 &nbsp;&nbsp;&nbsp;&nbsp;`T<sub>u</sub>` &harr; set of pending transactions
4 &nbsp;&nbsp;&nbsp;&nbsp;`T&#773;<sub>u</sub>` &harr; Ø
5 &nbsp;&nbsp;&nbsp;&nbsp;`(vote<sub>u</sub>, h<sub>u</sub>, π<sub>u</sub>)` &harr; `DRAW` (`r`, `sk<sub>u</sub>`, `seed`, τ, w<sub>u</sub>, W)
6 &nbsp;&nbsp;&nbsp;&nbsp;**if** `vote<sub>u</sub>` &gt; 0 **then**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`m<sub>u</sub>` &harr; `(r, pk<sub>u</sub>, h<sub>u</sub>, π<sub>u</sub>, T<sub>u</sub>, T&#773;<sub>u</sub>, Ø, vote<sub>u</sub>)`
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`BROADCAST`(`m<sub>u</sub>`) to all users of the system
9 &nbsp;&nbsp;&nbsp;&nbsp;`r` &harr; `r` + 1
10 &nbsp;&nbsp;&nbsp;&nbsp;**while** `r` ≤ 5 **do**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`M<sub>u</sub>` &harr; `COLLECTMESSAGES`(`r`)
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`T<sub>u</sub>`, `T&#773;<sub>u</sub>` &harr; `TRANSACMERGE`(`M<sub>u</sub>`)
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** `r` = 3 **then**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`T<sub>u</sub>`, `T&#773;<sub>u</sub>` &harr; `TRANSACFREQUENCY`(`M<sub>u</sub>`)
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** `r` = 5 **then**
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`decision` = `T<sub>u</sub> \ T&#773;<sub>u</sub>`
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** `decision`
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`(vote<sub>u</sub>, h<sub>u</sub>, π<sub>k</sub>)` &harr; `DRAW`(`r`, `sk<sub>u</sub>`, `seed`, τ, w<sub>u</sub>, W)
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** `vote<sub>u</sub>` &gt; 0 **then**
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`m<sub>u</sub>` &harr; `(r, pk<sub>u</sub>, h<sub>u</sub>, π<sub>u</sub>, T<sub>u</sub>, T&#773;<sub>u</sub>, M<sub>u</sub>, vote<sub>u</sub>)`
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`BROADCAST`(`m<sub>u</sub>`) to all users of the system
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`r` &harr; `r` + 1

the following we assume that only valid transactions are proposed. An execution of the merge-consensus algorithm
(see Algorithm 3) by any correct user *u* proceeds as follows.

Round $r=0$.

Let *u* be any correct user, and let $\mathcal{T}_u$ be its initial set of pending transactions. In round 0, user *u* proposes its set of pending transactions $\mathcal{T}_u$ by transmitting the message $m_u = \langle 0, pk_u, \pi_u, \mathcal{T}_u, \bar{T}_u, vote_u \rangle$ with $\mathcal{T}_u = \bar{T}_u = \emptyset$ to all users (line 8 of Algorithm 3). As will be clarified in the next paragraph, we denote by $\mathfrak{M}_u$ a proof that evaluates the right for a transaction to appear either in the aggregated set of transactions $\mathcal{T}$ or $\bar{\mathcal{T}}$, which will be built along the subsequent rounds of the algorithm.

Round $r > 0$.

Subsequent rounds of the merge consensus algorithm aim at collecting transactions until all correct users have converged to exactly the same set of transactions.

Each round $r > 0$ is made of the following two steps: (1) collect of messages broadcast at the previous round $r - 1$, and (2) construction of the estimation of the final set of transactions, based on the proof that all those transactions have been initially broadcast in round $r = 0$.

Step 1: *Collecting messages (Line 11 of Algorithm 3).* Pseudo-code of Function `COLLECTMESSAGE` is given Algorithm 4).
This function allows any correct user to collect enough messages broadcast during round $r-1$. By enough, we mean a
Byzantine tolerant quorum equal to $\mu\tau$ messages, each message containing a set of transactions. Properties of Byzantine
<caption>**Algorithm 4: Collect Messages function invoked by < pk<sub>u</sub>, sk<sub>u</sub> >**</caption>

1 **Function** COLLECTMESSAGES(*r*):
2 &nbsp;&nbsp;&nbsp;&nbsp;*M*<sub>*u*</sub>, SeenUsers[ ], BadUsers[ ] ← 0, 0, 0
3 &nbsp;&nbsp;&nbsp;&nbsp;WeightCnt ← 0
4 &nbsp;&nbsp;&nbsp;&nbsp;**while** WeightCnt < ⌊*μτ*⌋ **do**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** each message *m*<sub>*j*</sub> received **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*v* ← VERIFYDRAW(*r* − 1, *m*<sub>*j*</sub>.pk<sub>*j*</sub>, *m*<sub>*j*</sub>.π<sub>*j*</sub>, *m*<sub>*j*</sub>.h<sub>*j*</sub>, seed, *T*, *T*<sub>U</sub>, *w*<sub>*j*</sub>, *W*)
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** *v* = *m*<sub>*j*</sub>.vote **and** VALID(*m*<sub>*j*</sub>.M) = true **then**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** *pk*<sub>*j*</sub> ∉ (SeenUsers ∪ BadUsers) **then**
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;WeightCnt ← WeightCnt + *m*<sub>*j*</sub>.vote
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SeenUsers ← SeenUsers ∪ {pk<sub>*j*</sub>}
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;M*<sub>*u*</sub>[pk<sub>*j*</sub>] ← *m*<sub>*j*</sub>
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** *pk*<sub>*j*</sub> ∈ SeenUsers **and** M*<sub>*u*</sub>[pk<sub>*j*</sub>] ≠ *m*<sub>*j*</sub> **then**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;WeightCnt ← WeightCnt − *m*<sub>*j*</sub>.vote
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;SeenUsers ← SeenUsers \ {pk<sub>*j*</sub>}
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BadUsers ← BadUsers ∪ {pk<sub>*j*</sub>}
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;delete(M*<sub>*u*</sub>[pk<sub>*j*</sub>])
18 &nbsp;&nbsp;&nbsp;&nbsp;**return** M*<sub>*u*</sub>
proof contains $\lfloor \mu\tau \rfloor$ messages, each one containing one set of transactions broadcast at round $r = 0$. Function VALID (see Line 7 of Algorithm 4) takes care of such a verification, as well as of all verifications that concern the construction of the final sets $\mathcal{T}$ and $\overline{\mathcal{T}}$ of transactions. If message $m_j$ is valid then user $u$ updates its own proof $\mathfrak{M}_u$ with $m_j$, and updates the number of votes it has received so far during the collect (see Line 9 of Algorithm 4). Lines (14-18) of Algorithm 4 penalize a sender from broadcasting several sets of transactions during the same round.

**Step 2: Construction of the final set of transactions (Lines 11–17 of Algorithm 3).** Pseudo-code of Function TRANSACTMERGE is given in Algorithm 5). The construction of the final set of transactions goes along three main phases, which respectively consists in giving time enough to correct users to aggregate valid transactions broadcast at round 0, then in pruning valid but unfrequent transactions, and finally in building the final set of transactions.

Specifically, in the first phase (i.e., rounds $r = 1$ and $r = 2$), $u$ collects valid transactions, cumulates them in $\mathcal{T}_u$. If $u$ successfully passes the function DRAW (i.e., $u$ is a committee member of round $r$), then $u$ transmits a message $m_u$ reflecting all the knowledge $u$ has learned during round $r$. Recall that at each round, the committee is renewed, so each message must be broadcast to all users of the system (see Line 21 of Algorithm 3). As will be shown in Section 6 all the transactions initially broadcast by correct committee members of round $r = 0$ are received by all correct users by the end of the first phase.

The second phase is made of uniquely round $r = 3$, and aims at guaranteeing with high probability fast convergence to a unique set of transactions. Indeed, only keeping transactions that have been initially sent in round $r = 0$ is necessary but not sufficient to prevent the adversary from devising parsimony attacks.

**Definition 5.1 (Parsimony attack).** A parsimony attack consists for Byzantine committee members in broadcasting their pending transactions among themselves to get the proof that their transactions were present in round 0, and then in keeping secret these transactions during subsequent rounds, until correct users are close to converge to a final set of transactions. When such a round occurs, the adversary reveals some of their transactions. By repeating this strategy with all their secret pending transactions, the adversary may expect to delay convergence to a unique set of transactions.

Hence at round $r = 3$, Function TRANSACFREQUENCY (see Line 14 of Algorithm 3) prunes from $\mathcal{T}_u$ any (valid) transaction that $u$ has received less than $\lambda$ times and inserts them in $\overline{\mathcal{T}}$ (see Lines 12–16 of Algorithm 5). Parameter $\lambda$ is called the broadcast factor of the merge consensus algorithm. As will be shown in Section 6, $\overline{\mathcal{T}}$ is essential to defend correct users from adversarial strategies, in particular if the adversary pretends that some transaction should belong to the final decision set or should be definitively pruned.

Finally, the third phase consists of rounds $r = 4$ and $r = 5$. By the end of this phase, all correct users deliver the set of transactions in $\mathcal{T} \setminus \overline{\mathcal{T}}$. Section 6 shows that by the end of the third phase, all correct users deliver exactly the same set of transactions.

To summarise, for any transaction $t$ broadcast by a correct committee member at round 0, $t$ will belong to the final decision set of all correct users at round 5. We say that $t$ is decided. For any transaction $t'$ broadcast by a malicious committee member at round 0, if $t'$ does not belong to the final decision of a correct user $u$ then $t'$ will not belong to the final decision of any correct user $v$, and this occurs only if some correct user has received $t'$ less than $\lambda$ times at round 3 of the merge consensus algorithm.
# 6 Analysis of the merge consensus algorithm

Correctness of the merge consensus algorithm imposes conditions on $\mu\tau$, $\alpha$ and $\lambda$. In the following, we assume without loss of generality that $U$, the quantity of stake of an UTXO, is set to 1. Hence, any elected user has a voting weight equal to 1 and each user waits for $\lfloor \mu\tau \rfloor$ messages. Furthermore parameter $\lambda$ is set to $2\mu\tau/3$.

Specifically, the number of users selected to be committee members of round $r$ is such that their stake at round $r$ follows the binomial distribution with parameter $W$ and $p$, with $p = \tau/W$ (see Section 5). We denote by $X_r$ this random variable. Let $X_r^H$ be the random variable that represents the number of correct users selected at round $r$ to form a committee of size $X_r$, given the overall correct stake $W^H$, with $W^H = (1-p^A)W$ (see Section 2). Random variable $X_r^A$ follows the binomial distribution with parameter $W^A$ and $p$. Similarly, let $X_r^A$ be the random variable that represents the number of Byzantine users selected at round $r$ to form a committee of size $X_r$, given the overall Byzantine stake $W^A$, with $W^A = p^A W$. Random variable $X_r^A$ follows the binomial distribution with parameter $W^A$ and $p$. We have $X_r = X_r^H + X_r^A$ for any $r \ge 0$.

## 6.1 Byzantine tolerant quorums

Recall that any correct committee member, selected to execute round $r \ge 1$ of the merge consensus, waits for a subset of the votes, sent during round $r-1$ by the committee members of round $r-1$, to make a decision. This subset of votes is called a Byzantine tolerant quorum of votes, and is equal to $\lfloor \mu\tau \rfloor$, where $\tau$ is the expected cumulative stake owned by the committee members, and $\mu \in (0, 1)$. A Byzantine tolerant quorum of votes is a number of votes that must be small enough so that all the votes of the quorum can be votes from exclusively correct committee members (see Property (P$_1$)), and must be large enough so that (i) malicious votes cannot have the majority even if the adversary combines all its votes (see Property (P$_2$)) and (ii) the intersection of any two Byzantine tolerant quorums intersect at, at least, one correct vote (see Property (P$_3$)).

**Property (P$_1$).** For any $r \ge 0$, for any $\varepsilon \in (0, 1)$,

$$ \mathbb{P}\{X_r^H < \lfloor \mu\tau \rfloor\} \le \varepsilon. \qquad (P_1) $$

Property P$_1$ states that there exists a Byzantine quorum composed of solely correct users with probability larger than $1 - \varepsilon$.

**Property (P$_2$).** For any $r \ge 0$, for any $\varepsilon \in (0, 1)$,

$$ \mathbb{P}\{X_r^A \ge \lfloor \mu\tau \rfloor/3\} \le \varepsilon. \qquad (P_2) $$

Property P$_2$ states that even if the adversary combines all their votes, they will not be greater than or equal to $1/3$ of the Byzantine quorum with probability larger than $1 - \varepsilon$.

**Property (P$_3$).** For any $r \ge 0$, for any $\varepsilon \in (0, 1)$,

$$ \mathbb{P}\{X_r^H + 2X_r^A \ge 2\lfloor \mu\tau \rfloor\} \le \varepsilon. \qquad (P_3) $$

Property P$_3$ states that any two Byzantine quorums in the same round necessarily intersect at a correct user with probability larger than $1 - \varepsilon$.

Properties (P$_1$), (P$_2$) and (P$_3$) hold by carefully dimensioning the proportion of votes the committee members are waiting for as a function of $\tau$. The parameters $W$ (that is, the total number of stakes in the system) and $\tau$ (that is, the
expected number of stakes selected in each round) are tightly linked through the binomial sampling procedure, where the proportion of stakes p selected among the stakes W of the system verifies $\tau = pW$. Thus, we only need to dimension parameters $\mu$ as a function of $\tau$.

Let us analyse in detail properties ($P_1$), ($P_2$) and ($P_3$) when parameters $W$, $p^{\mathcal{A}} \in (0, 1/3)$ and $\varepsilon$ are fixed. It is well-known that a binomial distribution $\mathcal{B}(n, p)$ can be quite accurately approximated by a normal distribution $\mathcal{N}(m, \sigma)$, with $m = np$ and $\sigma^2 = np(1-p)$ if we have $n \ge 30$, $np \ge 5$ and $n(1-p) \ge 5$.

Consider first property ($P_1$). Random variable $X_r^H$ has a binomial distribution with parameters $n = W^H$ and $p = \tau/W$. We then have $np = \tau W^H/W = (1-p^\mathcal{A})\tau$ and $n(1-p) = W^H - (1-p^\mathcal{A})\tau = (1-p^\mathcal{A})(W-\tau)$. It follows that the approximation can be used if

$$W^H \ge 30 \text{ and } 15/2 \le \tau \le W - 15/2. \qquad (2)$$

With these conditions, if $\mathcal{N}(m, \sigma)$ denotes a random variable normally distributed with parameters $m$ and $\sigma$, property ($P_1$) can be written as

$$\mathbb{P}\{\mathcal{N}(m, \sigma) \le \mu\tau\} \le \varepsilon.$$

Centering and reducing the variable $\mathcal{N}(m, \sigma)$, property ($P_1$) reads

$$\mathbb{P}\left\{\mathcal{N}(0, 1) \le \frac{\mu\tau - (1 - p^{\mathcal{A}})\tau}{\sqrt{(1 - p^{\mathcal{A}})\tau(1 - \tau/W)}}\right\} \le \varepsilon.$$

If $F$ denotes the cumulative distribution function of a Gaussian random variable $\mathcal{N}(0, 1)$, we have

$$F\left(\frac{\mu\tau - (1 - p^{\mathcal{A}})\tau}{\sqrt{(1 - p^{\mathcal{A}})\tau(1 - \tau/W)}}\right) \le \varepsilon.$$

Observe that, for small $\varepsilon$ ($\varepsilon < 1/2$) this condition necessarily implies that we must have $\mu < (1 - p^\mathcal{A})$. We then have

$$F\left(\frac{(1 - p^{\mathcal{A}})\tau - \mu\tau}{\sqrt{(1 - p^{\mathcal{A}})\tau(1 - \tau/W)}}\right) \ge 1 - \varepsilon$$

which is equivalent to

$$\frac{(1 - p^{\mathcal{A}})\tau - \mu\tau}{\sqrt{(1 - p^{\mathcal{A}})\tau(1 - \tau/W)}} \ge F^{-1}(1 - \varepsilon).$$

This leads to

$$\mu \le 1 - p^{\mathcal{A}} - F^{-1}(1 - \varepsilon)\sqrt{(1 - p^{\mathcal{A}})(1/\tau - 1/W)}.$$

For instance, when $\varepsilon = 10^{-4}$ we have $F^{-1}(1 - \varepsilon) = 3.7190165$ which gives

$$\mu \le 1 - p^{\mathcal{A}} - 3.7190165\sqrt{(1 - p^{\mathcal{A}})(1/\tau - 1/W)}.$$

Consider now property ($P_2$). Random variable $X_r^\mathcal{A}$ has a binomial distribution with parameters $n = W^\mathcal{A}$ and $p = \tau/W$. We then have $np = \tau W^\mathcal{A}/W = p^\mathcal{A}\tau$ and $n(1-p) = W^\mathcal{A} - p^\mathcal{A}\tau = p^\mathcal{A}(W-\tau)$. It follows that the approximation can be used if

$$W^\mathcal{A} \ge 30 \text{ and } 5/p^\mathcal{A} \le \tau \le W - 5/p^\mathcal{A}. \qquad (3)$$

With these conditions, if $\mathcal{N}(m, \sigma)$ denotes a random variable normally distributed with parameters $m$ and $\sigma$, property ($P_2$) can be written as

$$\mathbb{P}\{\mathcal{N}(m, \sigma) \ge \mu\tau/3\} \le \varepsilon.$$
Centering and reducing the variable $\mathcal{N}(m, \sigma)$, property $(P_2)$ reads

$$ \mathbb{P} \left\{ \mathcal{N}(0, 1) \geq \frac{\mu\tau/3 - p^{\mathcal{A}}\tau}{\sqrt{p^{\mathcal{A}}\tau(1 - \tau/W)}} \right\} \leq \varepsilon, $$

that is

$$ F\left(\frac{\mu\tau/3 - p^{\mathcal{A}}\tau}{\sqrt{p^{\mathcal{A}}\tau(1 - \tau/W)}}\right) \geq 1 - \varepsilon. $$

Observe that, for small $\varepsilon$ ($\varepsilon < 1/2$) this condition necessarily implies that we must have $\mu > 3p^{\mathcal{A}}$. This is equivalent to

$$ \frac{\mu\tau/3 - p^{\mathcal{A}}\tau}{\sqrt{p^{\mathcal{A}}\tau(1 - \tau/W)}} \geq F^{-1}(1 - \varepsilon) $$

which leads to

$$ \mu \geq 3p^{\mathcal{A}} + 3F^{-1}(1 - \varepsilon)\sqrt{p^{\mathcal{A}}(1/\tau - 1/W)}. $$

For instance, when $\varepsilon = 10^{-4}$ we have $F^{-1}(1 - \varepsilon) = 3.7190165$ which gives

$$ \mu \geq 3p^{\mathcal{A}} + 11.1570495\sqrt{p^{\mathcal{A}}(1/\tau - 1/W)}. $$

Consider now Property $(P_3)$. Random variable $X_r^{\mathcal{H}}$ is approximated by a normal distribution with parameters $m_1 = (1 - p^{\mathcal{A}})\tau$ and $\sigma_1^2 = (1 - p^{\mathcal{A}})\tau(1 - \tau/W)$, and random variable $X_r^{\mathcal{A}}$ is approximated by a normal distribution with parameters $m_2 = p^{\mathcal{A}}\tau$ and $\sigma_2^2 = p^{\mathcal{A}}\tau(1 - \tau/W)$. By the independence of $X_r^{\mathcal{H}}$ and $X_r^{\mathcal{A}}$, the linear combination $X_r^{\mathcal{H}} + 2X_r^{\mathcal{A}}$ can be approximated by a normal distribution with parameters $m = m_1 + 2m_2 = (1 + p^{\mathcal{A}})\tau$ and $\sigma^2 = \sigma_1^2 + 4\sigma_2^2 = \tau(1 - \tau/W)(1 + 3p^{\mathcal{A}})$ if both conditions (2) and (3) are satisfied, that is if

$$ W^{\mathcal{H}} \geq 30, W^{\mathcal{A}} \geq 30, \max\{5/p^{\mathcal{A}}, 15/2\} \leq \tau \leq \min\{W - 5/p^{\mathcal{A}}, W - 15/2\}. $$

With these conditions, if $\mathcal{N}(m, \sigma)$ denotes a random variable normally distributed with parameters $m$ and $\sigma$, property $(P_3)$ can be written as

$$ \mathbb{P}\{\mathcal{N}(m, \sigma) \geq 2\mu\tau\} \leq \varepsilon. $$

Centering and reducing the variable $\mathcal{N}(m, \sigma)$, property $(P_3)$ reads

$$ F\left(\frac{2\mu\tau - (1 + p^{\mathcal{A}})\tau}{\sqrt{(1 + 3p^{\mathcal{A}})\tau(1 - \tau/W)}}\right) \geq 1 - \varepsilon. $$

Observe that, for small $\varepsilon$ ($\varepsilon < 1/2$) this condition necessarily implies that we must have $\mu > (1 + p^{\mathcal{A}})/2$. This is equivalent to

$$ \frac{2\mu\tau - (1 + p^{\mathcal{A}})\tau}{\sqrt{(1 + 3p^{\mathcal{A}})\tau(1 - \tau/W)}} \geq F^{-1}(1 - \varepsilon) $$

which leads to

$$ \mu \geq \frac{1 + p^{\mathcal{A}}}{2} + \frac{F^{-1}(1 - \varepsilon)}{2} \sqrt{(1 + 3p^{\mathcal{A}})(1/\tau - 1/W)}. $$

For instance, when $\varepsilon = 10^{-4}$ we have $F^{-1}(1 - \varepsilon) = 3.7190165$ which gives

$$ \mu \geq \frac{1 + p^{\mathcal{A}}}{2} + 1.85950825\sqrt{(1 + 3p^{\mathcal{A}})(1/\tau - 1/W)}. $$
Finally, putting together these three results, the conditions that must be satisfied by $\mu$ and $\tau$ when parameters $W$, $p^{\mathcal{A}}$ and $\varepsilon$ are fixed, are the following.

$$0 \le \mu \le 1 - p^{\mathcal{A}} - F^{-1}(1 - \varepsilon)\sqrt{(1 - p^{\mathcal{A}})(1/\tau - 1/W)} \quad (4)$$

$$3p^{\mathcal{A}} + 3F^{-1}(1 - \varepsilon)\sqrt{p^{\mathcal{A}}(1/\tau - 1/W)} \le \mu \le 1. \quad (5)$$

$$\frac{1 + p^{\mathcal{A}}}{2} + \frac{F^{-1}(1 - \varepsilon)}{2} \sqrt{(1 + 3p^{\mathcal{A}})(1/\tau - 1/W)} \le \mu \le 1. \quad (6)$$

Figure 2 represents the evolution of $\mu$ as a function of $\tau$, for different proportions $p^{\mathcal{A}}$ of adversarial users, for $\varepsilon = 10^{-4}$, and $W = 10^5$. Any value of the pair $(\tau, \mu)$ belonging to the hatched area satisfies the three properties simultaneously. We observe, for instance, that to tolerate a proportion $p^{\mathcal{A}} = 5\%$ of malicious users, Properties $(P_1)$, $(P_2)$ and $(P_3)$ are simultaneously satisfied with probability $1 - 10^{-4}$ once the Byzantine tolerant quorum is set to $[0.68 \times 174.5] = 118$ votes, while for $p^{\mathcal{A}} = 20\%$, the size of the Byzantine tolerant quorum must be equal to $0.72 \times 1699.6 = 1223$ votes.

**REMARK 2.** Our tight analysis allows us to accurately dimension the size of Byzantine tolerant quorums. The constraints imposed by Property $(P_2)$ on $\mu\tau$ become predominant over the one imposed by Property $(P_3)$ for increasing values of $p^{\mathcal{A}}$. For instance, beyond Property $(P_1)$ that upper bounds the quorum sizes, the lower bound is imposed by either Property $(P_2)$ or $(P_3)$. We observe that for $p^{\mathcal{A}} = 5\%$, Property $(P_3)$ is predominant, for $p^{\mathcal{A}} = 18\%$, both Properties $P_2$ and $(P_3)$ are involved, and for $p^{\mathcal{A}} = 20\%$, Property $(P_2)$ is predominant. In contrast and for instance in Algorand [12], the authors dimension the Byzantine tolerant quorums by (i) guaranteeing that there exists at least one quorum that contains only correct users (i.e., Property $eqP_1$) and by (ii) ensuring that any two quorum intersect at least one correct user (i.e., Property $(P_3)$). They do not constraint the proportion of malicious users in any single quorum which turns out to be crucial for large values of $p^{\mathcal{A}}$ as illustrated in Figure 2d. The size of Algorand’s quorums (i.e., equal to $[800 \times 0.68] = 544$) is too small to cope with 20% of malicious users.

## 6.2 Analysis of the merge consensus algorithm

In the following we consider values of $\mu$ and $\tau$ so that Properties $(P_1)$, $(P_2)$ and $(P_3)$ hold.

We model the broadcast primitive as an urn and ball problem. Each user maintains two urns: Urn $H$ and urn $A$. When a correct user broadcasts a message, its message is thrown into Urn $H_v$ of each user $v$ of the system. When the adversary broadcasts a message, its message is thrown into Urn $A_v$ of each user $v$ of the system. When the adversary broadcasts a message with parsimony, then for each correct user $u$, the message is thrown in Urn $H_u$ with probability $q$. When a correct user $u$ waits for $\mu\tau$ messages at the beginning of each round, then $u$ first draws all the balls of Urn $A_u$ and randomly picks balls from Urn $H_u$ until it draws a total of $\mu\tau$ balls.

**LEMMA 6.1.** Let $t$ be a transaction broadcast by one single correct committee member in round 0 of the merge consensus algorithm. Then at the end of any round $r \ge 2$ and for any correct user $u$, we have, for any $\varepsilon \in (0, 1/2)$,

$$\mathbb{P}\{t \in \mathcal{T}_u\} \ge 1 - 2\varepsilon.$$

**PROOF.** Let $t$ be a transaction broadcast at round 0 by solely one correct committee member $v \in X_0^H$. Note that the adversary may know $t$, but it does not broadcast $t$ to any correct users to reduce their chances of receiving $t$. At round $r = 1$, any correct user $u$ waits for $\mu\tau$ votes, i.e., $\mu\tau$ messages (recall that we assume that any committee member has a voting power equal to 1). Let $N_{1,t}^H$ be the random variable that counts the number of messages containing $t$, which have
<figure><img src="image_3.png" /><figcaption>Fig. 2. Curves $f_1(\tau)$, $f_2(\tau)$ et $f_3(\tau)$, respectively associated to properties ($P_1$), ($P_2$) and ($P_3$) for $W = 10^5$ and $\varepsilon = 10^{-4}$.</figcaption></figure>

been received by *u* during round 1. The variable $N_{1,t}^H$ follows an hypergeometric distribution $\mathcal{H}(Y_0^H, 1, \lfloor \mu\tau \rfloor - X_0^\mathcal{A})$, where $Y_0^H$ follows a binomial distribution with parameters $W^H - 1$ and $p$, and represents the number of correct users
833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

<figure><img src="image_4.png" /><figcaption>(c) $p^{\mathcal{A}} = 0.18$</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(d) $p^{\mathcal{A}} = 0.20$</figcaption></figure>

<caption>Fig. 2. Curves $f_1(\tau)$, $f_2(\tau)$ et $f_3(\tau)$, respectively associated to properties ($P_1$), ($P_2$) and ($P_3$) for $W = 10^5$ and $\varepsilon = 10^{-4}$.</caption>
selected at round 0 among all the correct users except user $u$. Observe that at round 1, $N_{1,t}^H \in \{0, 1\}$. We have, using the independence of $X_0^\mathcal{A}$ and $Y_0^H$,

$$ 
\begin{align}
\mathbb{P}\{N_{1,t}^H = 1\} & = \sum_{a=0}^{\lfloor \mu\tau \rfloor - 1} \sum_{h=\lfloor \mu\tau \rfloor - a - 1}^{W^H - 1} \mathbb{P}\{N_{1,t}^H = 1 \mid X_0^\mathcal{A} = a, Y_0^H = h\} \mathbb{P}\{X_0^\mathcal{A} = a, Y_0^H = h\} \nonumber \\
& = \sum_{a=0}^{\lfloor \mu\tau \rfloor - 1} \sum_{h=\lfloor \mu\tau \rfloor - a - 1}^{W^H - 1} \frac{\lfloor \mu\tau \rfloor - a}{h+1} \binom{W^\mathcal{A}}{a} p^a (1-p)^{W^\mathcal{A}-a} \binom{W^H-1}{h} p^h (1-p)^{W^H-1-h} \nonumber \\
& = \frac{1}{W^H} \sum_{a=0}^{\lfloor \mu\tau \rfloor - 1} (\lfloor \mu\tau \rfloor - a) \binom{W^\mathcal{A}}{a} p^a (1-p)^{W^\mathcal{A}-a} \sum_{h=\lfloor \mu\tau \rfloor - a - 1}^{W^H - 1} \binom{W^H}{h} p^h (1-p)^{W^H-1-h} \nonumber \\
& = \frac{1}{pW^H} \sum_{a=0}^{\lfloor \mu\tau \rfloor - 1} (\lfloor \mu\tau \rfloor - a) \binom{W^\mathcal{A}}{a} p^a (1-p)^{W^\mathcal{A}-a} \left( 1 - \sum_{h=0}^{\lfloor \mu\tau \rfloor - a - 1} \binom{W^H}{h} p^h (1-p)^{W^H-h} \right). \tag{7}
\end{align}
$$

We have $1 - \sum_{h=0}^{\lfloor \mu\tau \rfloor - a - 1} \binom{W^H}{h} p^h (1-p)^{W^H-h} = 1 - \mathbb{P}\{X_0^H < \lfloor \mu\tau \rfloor - a\}$. Since $a < \lfloor \mu\tau \rfloor$, by property (P$_1$), the last term of Relation (7) is larger than or equal to $1 - \epsilon$. Now, $\sum_{a=0}^{\lfloor \mu\tau \rfloor - 1} \lfloor \mu\tau \rfloor \binom{W^\mathcal{A}}{a} p^a (1-p)^{W^\mathcal{A}-a} = \lfloor \mu\tau \rfloor (1 - \sum_{a=\lfloor \mu\tau \rfloor}^{W^\mathcal{A}} \binom{W^\mathcal{A}}{a} p^a (1-p)^{W^\mathcal{A}-a}) = \lfloor \mu\tau \rfloor (1 - \sum_{a=\lfloor \mu\tau \rfloor}^{W^\mathcal{A}} \binom{W^\mathcal{A}}{a} p^a (1-p)^{W^\mathcal{A}-a}) = \lfloor \mu\tau \rfloor (1 - \epsilon)$ by property (P$_2$). Finally, we have $\sum_{a=0}^{\lfloor \mu\tau \rfloor - 1} a \binom{W^\mathcal{A}}{a} p^a (1-p)^{W^\mathcal{A}-a} \le pW^\mathcal{A}$. Thus altogether we get

$$ \mathbb{P}\{N_{1,t}^H = 1\} \ge \frac{1}{pW^H} (1-\epsilon)(\lfloor \mu\tau \rfloor(1-\epsilon) - pW^\mathcal{A}). $$

Since $p^\mathcal{A} = W^\mathcal{A}/W$ and $\tau = pW$, we obtain by multiplying and dividing by $\tau$

$$ \mathbb{P}\{N_{1,t}^H = 1\} \ge \frac{1-\epsilon}{1-p^\mathcal{A}} (\mu(1-\epsilon) - p^\mathcal{A}). \tag{8} $$

At round $r=2$, any correct user $u$ waits for $\lfloor \mu\tau \rfloor$ messages. Let $N_{2,t}^H$ be the random variable that counts the number of messages containing $t$ that have been received by $u$ during round 2. The variable $N_{2,t}^H$ follows an hypergeometric distribution $H(X_1^H, Z_{1,t}^H, \lfloor \mu\tau \rfloor - X_1^\mathcal{A})$, where $Z_{1,t}^H$ is the random variable that represents the number of correct committee members in $X_1^H$ that broadcast $t$ at the end of round 1. $Z_{1,t}^H$ follows a binomial distribution with parameters $X_1^H$ and $p_{1,t}$, where $p_{1,t} = \mathbb{P}\{N_{1,t}^H = 1\}$.
We have, using the independence of $X_1^{\mathcal{A}}$, $X_1^{\mathcal{H}}$ and $Z_{1,t}^{\mathcal{H}}$,

$$ 
\begin{aligned}
\mathbb{P}\{N_{2,t}^{\mathcal{H}} = i\} &= \sum_{a=0}^{\lfloor\mu\tau\rfloor-i} \sum_{h=\lfloor\mu\tau\rfloor-a}^{W^{\mathcal{H}}} \sum_{j=i}^{h-\lfloor\mu\tau\rfloor+a+i} \mathbb{P}\{N_{2,t}^{\mathcal{H}} = i \mid X_1^{\mathcal{A}} = a, X_1^{\mathcal{H}} = h, Z_{1,t}^{\mathcal{H}} = j\} \\
&\quad \times \mathbb{P}\{X_1^{\mathcal{A}} = a, X_1^{\mathcal{H}} = h, Z_{1,t}^{\mathcal{H}} = j\} \\
&= \sum_{a=0}^{\lfloor\mu\tau\rfloor-i} \sum_{h=\lfloor\mu\tau\rfloor-a}^{W^{\mathcal{H}}} \sum_{j=i}^{h-\lfloor\mu\tau\rfloor+a+i} \frac{\binom{j}{i} \binom{h-j}{\lfloor\mu\tau\rfloor-a-i}}{\binom{h}{\lfloor\mu\tau\rfloor-a}} \binom{h}{j} (p_{1,t})^j (1-p_{1,t})^{h-j} \\
&\quad \times \binom{W^{\mathcal{H}}}{a} p^a (1-p)^{W^{\mathcal{A}}-a} \binom{W^{\mathcal{H}}}{h} p^h (1-p)^{W^{\mathcal{H}}-h}.
\end{aligned}
$$

The probability that some correct user $u$ does not receive transaction $t$ at round 2 of Algorithm 3 is given by $\mathbb{P}\{N_{2,t}^{\mathcal{H}} = 0\}$. After some algebra, we get

$$ \mathbb{P}\{N_{2,t}^{\mathcal{H}} = 0\} = \sum_{a=0}^{\lfloor\mu\tau\rfloor} (1-p_{1,t})^{\lfloor\mu\tau\rfloor-a} \binom{W^{\mathcal{A}}}{a} p^a (1-p)^{W^{\mathcal{A}}-a} \left(1 - \sum_{h=0}^{\lfloor\mu\tau\rfloor-a-1} \binom{W^{\mathcal{H}}}{h} p^h (1-p)^{W^{\mathcal{H}}-h}\right). \quad (9) $$

The second term of Relation (9) is less than or equal to 1. Thus,

$$ \mathbb{P}\{N_{2,t}^{\mathcal{H}} = 0\} \le (1-p_{1,t})^{\lfloor\mu\tau\rfloor} - (\lfloor\mu\tau\rfloor/3) - 1 \sum_{a=0}^{\lfloor\mu\tau\rfloor/3-1} \binom{W^{\mathcal{A}}}{a} p^a (1-p)^{W^{\mathcal{A}}-a} + \sum_{a=\lfloor\mu\tau\rfloor/3\rfloor}^{\lfloor\mu\tau\rfloor} \binom{W^{\mathcal{A}}}{a} p^a (1-p)^{W^{\mathcal{A}}-a}. \quad (10) $$

The first term on the right hand side is less than $(1 - p_{1,t})^{2\lfloor\mu\tau\rfloor/3+1}$ and by property ($P_2$), the second term is less than $\epsilon$. It has been shown in relation (8) that

$$ p_{1,t} \ge \frac{1-\epsilon}{1-p^{\mathcal{A}}} (\mu(1-\epsilon) - p^{\mathcal{A}}). $$

Condition (5) implies that $\mu \ge 3p^{\mathcal{A}}$ and Condition (6) implies that $\mu \ge 1/2$. It follows that

$$ p_{1,t} \ge \begin{cases} \frac{1-\epsilon}{1-p^{\mathcal{A}}} \left( \frac{1-\epsilon}{2} - p^{\mathcal{A}} \right) & \text{if } p^{\mathcal{A}} \in (0, 1/6] \\ \frac{(1-\epsilon)p^{\mathcal{A}}(2-3\epsilon)}{1-p^{\mathcal{A}}} & \text{if } p^{\mathcal{A}} \in [1/6, 1/3). \end{cases} $$

We then have

$$ (1-p_{1,t})^{2\mu\tau/3+1} \le \begin{cases} \left[1 - \frac{1-\epsilon}{1-p^{\mathcal{A}}} \left(\frac{1-\epsilon}{2} - p^{\mathcal{A}}\right)\right]^{2\mu\tau/3+1} & \text{if } p^{\mathcal{A}} \in (0, 1/6] \\ \left[1 - \frac{(1-\epsilon)p^{\mathcal{A}}(2-3\epsilon)}{1-p^{\mathcal{A}}}\right]^{2\mu\tau/3+1} & \text{if } p^{\mathcal{A}} \in [1/6, 1/3). \end{cases} $$

Consider now the function $g_2(\tau) = \tau f_2(\tau)$. The second derivative $g_2''(\tau)$ is negative. This means that the first derivative $g_2'(\tau)$ is decreasing and it is easily checked that when $\tau$ is maximal, i.e., when $W - 5/p^{\mathcal{A}}$, we have $g_2'(W - 5/p^{\mathcal{A}}) \ge 0$ for sufficiently small $\epsilon$. We then have $g_2'(\tau) \ge g_2'(W - 5/p^{\mathcal{A}}) \ge 0$, which means that the function $g_2(\tau)$ is increasing. It
follows from condition (5) that,

$$\mu\tau \geq g_2(\tau) \geq g_2(5/p^{\mathcal{A}}) = 15 + 3F^{-1}(1-\epsilon)\sqrt{5(1-5/(p^{\mathcal{A}}W))},$$

that is

$$2\mu\tau/3 + 1 \geq 11 + 2F^{-1}(1-\epsilon)\sqrt{5(1-5/(p^{\mathcal{A}}W))}.$$

Since $p^{\mathcal{A}}W = W^{\mathcal{A}} \geq 30$, we obtain

$$2\mu\tau/3 + 1 \geq 11 + 10F^{-1}(1-\epsilon)/\sqrt{6}. \qquad (11)$$

Denoting by $U(\epsilon)$ this upper bound, we obtain

$$(1 - p_{1,t})^{2\mu\tau/3+1} \leq \begin{cases} \left[ 1 - \frac{1-\epsilon}{1-p^{\mathcal{A}}} \left( \frac{1-\epsilon}{2} - p^{\mathcal{A}} \right) \right]^{U(\epsilon)} & \text{if } p^{\mathcal{A}} \in (0, 1/6] \\ \left[ 1 - \frac{(1-\epsilon)p^{\mathcal{A}}(2-3\epsilon)}{1-p^{\mathcal{A}}} \right]^{U(\epsilon)} & \text{if } p^{\mathcal{A}} \in [1/6, 1/3). \end{cases}$$

Using the variations of $p^{\mathcal{A}}$, it is easily checked that

$$(1 - p_{1,t})^{2\mu\tau/3+1} \leq \left( \frac{3 + 5\epsilon - 3\epsilon^2}{5} \right)^{11+10F^{-1}(1-\epsilon)/\sqrt{6}}.$$

This bound is less than $\epsilon$ for all $\epsilon \leq 0.1$. We thus get

$$\mathbb{P}\{N_{2,t}^{\mathcal{H}} = 0\} < 2\epsilon. \qquad (12)$$

Thus, at the beginning of round $r=2$, any correct user $u$ will receive transaction $t$ with probability greater than $1-2\epsilon$. At round $r=3$, any correct user $u$ waits for $\lfloor \mu\tau \rfloor$ messages, such that among them $X_2^{\mathcal{A}}$ messages have been sent by the adversary. By Property $(P_2)$, we have $\mathbb{P}\{X_2^{\mathcal{A}} < \lfloor \mu\tau \rfloor/3\} > 1-\epsilon$ and by Property $(P_1)$, we have $\mathbb{P}\{X_2^{\mathcal{H}} > \lfloor \mu\tau \rfloor\} > 1-\epsilon$. Thus with probability $1-\epsilon$, $u$ will receive $t$ in more than $\lambda$ messages. Thus by Function TRANSACFREQUENCY (see Algorithm 5), $t \in \mathcal{T}_u$ at the end of round 3. In all the subsequent rounds $r > 3$ of Algorithm 5, all the correct users $v$ update $\mathcal{T}_v$ with the union of all the correctly built $\mathcal{T}$ at the beginning of round $r$. This completes the proof of the lemma. $\square$

**COROLLARY 6.2.** Let $t \in \overline{\mathcal{T}}_u$ be a transaction broadcast by some correct committee member $u$ at the end of round 3. Then at the end of round 5, and for any correct user $v$, we have, for any $\epsilon \in (0, 1/2)$,

$$\mathbb{P}\{t \in \overline{\mathcal{T}}_v\} \geq 1 - 2\epsilon.$$

**PROOF.** In all the subsequent rounds $r > 3$ of Algorithm 5, all the correct users $v$ update $\overline{\mathcal{T}}_v$ with the union of all the correctly built $\overline{\mathcal{T}}$ at the beginning of round $r$. This completes the proof of the corollary. $\square$

**COROLLARY 6.3.** Let $t \in \mathcal{T}_u$ be a transaction broadcast by some correct committee member $u$ at the end of round 3. Then at the end of round 5, and for any correct user $v$, we have, for any $\epsilon \in (0, 1/2)$,

$$\mathbb{P}\{t \in \mathcal{T}_v\} \geq 1 - 2\epsilon.$$

**LEMMA 6.4.** Let $\mathcal{V}_0^{\mathcal{A}}$ be a set of valid transactions initially known by solely the adversary. If the adversary keeps them hidden from any correct users during both rounds 0 and 1 of Algorithm 3, then for any round $r \geq 3$, for any $t \in \mathcal{V}_0^{\mathcal{A}}$, and
Manuscript submitted to ACM
for any correct user $u$, we have for any $\epsilon \in (0, 1/2)$,

$$ \mathbb{P}\{t \in \bar{T}_u\} \geq 1 - \epsilon. $$

PROOF. Let $V_0^A$ be a set of valid transactions initially known by solely the adversary. At round 0, the set $V_0^A$ is broadcast only to corrupted users, so that the adversary will be able to prove that $V_0^A$ has been broadcast at round 0. During round 1, the adversary still keeps $V_0^A$ hidden from correct users. At round 2 the adversary makes them public: all the corrupted users elected at round 2 (i.e., all committee members $w \in X_2^A$) broadcast all transactions $t \in V_0^A$ to all the users of the system. By assumption (see Section 2), these transactions are received by all correct users instantaneously. Let $N_{3,t}^H$ be the random variable that counts the number of messages containing transaction $t \in V_0^A$ that have been received by any correct user $u$ at round 3. For each $t \in V_0^A$, we have

$$ N_{3,t}^H = j \iff X_2^A = j $$

By Property (P₂), $\mathbb{P}\{X_r^A \geq [\mu\tau]/3\} \leq \epsilon$ for any $r \geq 0$. Thus with any probability larger than $1 - \epsilon$, for any $t \in V_0^A$, correct user $u$ will receive transaction $t$ in less than $[\mu\tau]/3$ messages. By assumption $\lambda = 2\mu\tau/3$. So none of the transactions of $V_0^A$ will pass the test of Function TRANSACFREQUENCY and thus any correct user $u$ will insert all $t \in V_0^A$ in $\bar{T}_u$ at the end of round 3. For the subsequent rounds, $\bar{T}_u$ can only increase, thus all the transactions $t \in V_0^A$ will remain in $\bar{T}_u$ until the end of round 5, and thus will not appear in $u$'s decision set (see Line 16 of Algorithm 3). $\square$

LEMMA 6.5. Let $V_0^A$ be a set of valid transactions initially known by solely the adversary. If the adversary broadcasts them to correct users at round 0 and with probability $q \in [1 - e^{V(\epsilon)}$, 1), with $V(\epsilon) = \ln(\epsilon)\sqrt{6}/(11\sqrt{6} + 10F^{-1}(1 - \epsilon))$, then for any round $r \geq 2$, for any $t \in V_0^A$ and for any correct user $u$, we have for any $\epsilon \in (0, 1/2)$,

$$ \mathbb{P}\{t \in \bar{T}_u\} \geq 1 - 2\epsilon. $$

PROOF. By assumption, at round 0, the adversary broadcasts its transactions in $t \in V_0^A$ with parsimony. This means that at round 1, each correct user $u$ receives $t$ with probability $q$, where $q$ is chosen by the adversary. Recall that by assumption, any message sent by the adversary is received instantaneously by any correct user. By Algorithm 3, only $u \in X_1^H$ broadcasts all the information $u$ has accumulated in round 1 to the system. At round $r = 2$, any correct $u$ waits for $[\mu\tau]$ messages. Let $N_{2,t}^H$ be the random variable that counts the number of messages containing $t \in V_0^A$ that have been received by $u$. $N_{2,t}^H \in \{0, \dots, [\mu\tau]\}$ and follows the hypergeometric distribution $\mathcal{H}(X_1^H, Z_{1,t}^H, [\mu\tau] - X_1^A)$, where $Z_{1,t}^H$ is the random variable that represents the number of correct committee members in $X_1^H$ that broadcast $t \in V_0^A$. $Z_{1,t}^H \in \{0, X_1^H\}$ and follows a Binomial distribution with parameters $X_1^H$ and $q$. We have, using the independence of $X_1^H$, $Z_{1,t}^H$ and $X_1^A$,

$$ \mathbb{P}\{N_{2,t}^H = 0\} = \sum_{a=0}^{\lfloor \mu\tau \rfloor} (1-q)^{\lfloor \mu\tau \rfloor - a} \binom{W^A}{a} p^a (1-p)^{W^A-a} \left(1 - \sum_{h=0}^{\lfloor \mu\tau \rfloor - a - 1} \binom{W^H}{h} p^h (1-p)^{W^H-h}\right). \quad (13) $$

This relation is similar to relation (10), so we have

$$ \mathbb{P}\{N_{2,t}^H = 0\} \leq (1-q)^{2\mu\tau/3+1} + \epsilon. $$

Now, using relation (11) we get

$$ (1-q)^{2\mu\tau/3+1} \leq (1-q)^{11+10F^{-1}(1-\epsilon)/\sqrt{6}} $$
and

$$ (1-q)^{11+10F^{-1}(1-\epsilon)/\sqrt{6}} \le \epsilon \iff q \ge 1 - \exp\left(\frac{\ln(\epsilon)\sqrt{6}}{11\sqrt{6} + 10F^{-1}(1-\epsilon)}\right). $$

For example, when $\epsilon = 10^{-4}$ we have $q \in [0.296558, 1)$. It follows that for $q \in [1-e^{V(\epsilon)}, 1)$, with $V(\epsilon) = \ln(\epsilon)\sqrt{6}/(11\sqrt{6}+10F^{-1}(1-\epsilon))$, we have $\mathbb{P}\{N_{2,t}^H = 0\} \le 2\epsilon$.

Relation (13) applies for any transactions $t \in \mathcal{V}_0^A$. Thus, any correct $u$ receives each transaction of $t \in \mathcal{V}_0^A$ with probability $1-\epsilon$. At round 3, any correct $u$ waits for $\lfloor \mu\tau \rfloor$ messages, such that among them $X_2^A$ messages have been sent by the adversary. By Property (P$_2$), we have $\mathbb{P}\{X_2^A < \lfloor \mu\tau/3 \rfloor\} > 1-\epsilon$ and by Property (P$_1$), we have $\mathbb{P}\{X_2^H > \lfloor \mu\tau \rfloor\} > 1-\epsilon$. Thus with probability $1-\epsilon$, $u$ will receive $t$ in more than $2\lfloor \mu\tau/3 \rfloor$ messages, i.e., in more than $\lambda$ messages. Thus by Function TRANSACFREQUENCY (see Line 20 of Algorithm 3), $t \in \mathcal{T}_u$ at the end of round 3. In all the subsequent rounds $r \ge 3$ of the algorithm, $t \in \mathcal{V}_0^A$ will remain in the decision set $\mathcal{T}_u$ of all correct users $u$. This completes the proof of the lemma. $\square$

LEMMA 6.6. Let $\mathcal{V}_0^A$ be a set of valid transactions initially known by solely the adversary. If the adversary broadcasts them to correct users with probability $q \in [1-e^{V(\epsilon)}, 1)$, with $V(\epsilon) = \ln(\epsilon)\sqrt{6}/(11\sqrt{6}+10F^{-1}(1-\epsilon))$, then at round $r = 5$, for any correct users $u$ and $v$, $u \ne v$, and for any $t \in \mathcal{V}_0^A$,

$$ \mathbb{P}\{t \in \mathcal{T}_u \Rightarrow t \in \mathcal{T}_v\} \ge 1 - 2\epsilon. $$

PROOF. There are several cases to consider.

(1) The adversary broadcast its transactions in $\mathcal{V}_0^A$ at round 0. By Lemma 6.5, for any $\epsilon \in (0, 1/2)$ and for any correct user $u$, we have $\mathbb{P}\{t \in \mathcal{T}_u\} \ge 1 - 2\epsilon$. This proves this sub-case.

(2) The adversary broadcast its transactions in $\mathcal{V}_0^A$ at round 2. By Lemma 6.4, for any correct user $u$, we have for any $\epsilon \in (0, 1/2)$, $\mathbb{P}\{t \in \mathcal{T}_u\} \ge 1 - \epsilon$. By contraposition, this sub-case is proven.

(3) At the end of round $r = 3$, there exist some correct users $u$ such that, for $t \in \mathcal{V}_0^A$, $t$ belongs to $\mathcal{T}_u$. By Corollary 6.3, for all correct users $w$, at the end of round 5, $\mathbb{P}\{t \in \mathcal{T}_w\} \ge 1 - 2\epsilon$.

(4) At the end of round $r = 3$, there exist some correct users $u$ such that, for $t \in \mathcal{V}_0^A$, $t$ belongs to $\overline{\mathcal{T}}_u$. By Corollary 6.2, for all correct users $w$, at the end of round 5, $\mathbb{P}\{t \in \overline{\mathcal{T}}_w\} \ge 1 - 2\epsilon$, which by contraposition proves this sub-case.

(5) At the end of round $r = 3$, for any $t \in \mathcal{V}_0^A$, for any correct user $u$, $t$ belongs to $\mathcal{T}_u$, while some adversarial user $v$ pretends that $t \in \overline{\mathcal{T}}_v$. This sub-case is impossible as the adversary cannot exhibit, at the end of round 3, $\lambda$ messages that do not contain $t$.

(6) At the end of round $r = 3$, for any $t \in \mathcal{V}_0^A$, for any correct user $u$, $t$ belongs to $\overline{\mathcal{T}}_u$, while some adversarial user $v$ pretends that $t \in \overline{\mathcal{T}}_v$. This sub-case is also impossible as the adversary cannot exhibit, at the end of round 3, $\lambda$ messages that contain $t$.

This completes the proof. $\square$

THEOREM 6.7 (AGREEMENT). For any two correct users $u$ and $v$, $u \ne v$, that respectively decide $\mathcal{T}_u$ and $\mathcal{T}_v$ then $\mathcal{T}_u = \mathcal{T}_v$ with probability larger than $1 - 2\epsilon$.

PROOF. By Property P$_3$, any two Byzantine tolerant quorums in the same round intersect at a correct user. Applying Lemmas 6.1 and 6.6 complete the proof. $\square$
**THEOREM 6.8 (VALIDITY).** For any correct user *u*, any decision value $T_u$ contains at least all the transactions initially broadcast by correct users, with probability larger than $1 - 2\epsilon$.

**PROOF.** Straightforward from Lemma 6.1. □

**THEOREM 6.9 (TERMINATION).** Each honest user *u* eventually outputs its decision value $T_u$.

**PROOF.** By construction of Algorithm 3, any correct user returns the decision value at round 5 and terminate (see Line 17). □

# 7 Conclusion

In this paper we have presented the design of a Byzantine tolerant consensus algorithm, which in presence of a rushing adversary, guarantees that all correct users of a permissionless system decide on the same set of values in no more than six rounds with any high probability. This algorithm deeply relies on ephemeral and numerous user identities to implement cryptographic sortition and short live committees. As future work, we plan to reduce the quantity of information contained in the messages by relying on commitments. An intriguing idea would be to organize transactions at each round in Merkle Mountain Ranges [6].

# References

[1] I. Abraham, T.-H. Chan, D. Dolev, K. Nayak, R. Pass, L. g Ren, and E. Shi. 2023. Communication complexity of byzantine agreement, revisited. *Distributed Computing* 36, 1 (2023), 3–28.

[2] Ittai Abraham and Dahlia Malkhi. 2017. The blockchain consensus layer and BFT. *Bulletin of the European Association for Theoretical Computer Science* 123 (2017).

[3] G. Ateniese, I. Bonacina, A. Faonio, and N. Galesi. 2014. Proofs of Space: When Space Is of the Essence. In *International Conference on Security and Cryptography for Networks (SCN)*.

[4] C. Badertscher, P. Gaži, A. Kiayias, A. Russell, and V. Zikas. 2018. Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability. In *Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS)*.

[5] V. K. Bagaria, A. Dembo, S. Kannan, S. Oh, D. Tse, P. Viswanath, X. Wang, and O. Zeitouni. 2022. Proof-of-Stake Longest Chain Protocols: Security vs Predictability. In *Proceedings of the 2022 ACM Workshop on Developments in Consensus*.

[6] Joseph Bonneau, Jessica Chen, Miranda Christ, and Ioanna Karantaidou. 2025. Merkle Mountain Ranges are Optimal: On witness update frequency for cryptographic accumulators. (2025). https://eprint.iacr.org/2025/234

[7] David Chaum. 1988. Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms. *Commun. ACM* 24, 2 (1988), 84–90.

[8] P. Daian, R. Pass, and E. Shi. 2016. Snow white: Provably secure proofs of stake. (2016). https://eprint.iacr.org/2016/919 Cryptology ePrint Archive, Report 2016/919.

[9] B. David, P. Gazi, A. Kiayias, and A. Russel. 2018. Ouroboros praos: An adaptively-secure semi-synchronous proof-of-stake blockchain. In *Advances in Cryptology – EUROCRYPT*.

[10] B. Edgington. 2023. *Upgrading Ethereum, a technical handbook on Ethereu's move to proof of stake and beyond*. https://eth2book.info/capella/

[11] EOS.IO. 2019. Technical White Paper v2. https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md Accessed: 2019-03-10.

[12] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In *Proceedings of the 26th Symposium on Operating Systems Principles (SOSP)* (Shanghai, China) (SOSP '17). Association for Computing Machinery, New York, NY, USA, 51–68. https://doi.org/10.1145/3132747.3132757

[13] Intel. 2019. Hyperledger Sawtooth Description. https://sawtooth.hyperledger.org/docs/core/releases/latest/architecture/poet.html Accessed: 2019-03-10.

[14] A. Kiayias, A. Russell, B. David, and R. Oliynykov. 2017. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In *Advances in Cryptology – CRYPTO*.

[15] A. Lewis-Pye and T. Roughgarden. 2023. Byzantine generals in the permissionless setting. In *27th International Conference on Financial Cryptography and Data Security (FC)*.

[16] S. Micali, M. Rabin, and S. Vadhan. 1999. Verifiable random functions. In *40th Annual Symposium on Foundations of Computer Science*.

[17] Tal Moran and Ilan Orlov. 2016. Proofs of space-time and rational proofs of storage. http://eprint.iacr.org/2016/035. In *Cryptology ePrint Archive*, Report 2016/035.

[18] S.Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. www.bitcoin.org (2008).