# Carnot: A highly Scalable and Responsive BFT Consensus protocol

Mohammad M. Jalalzai<EMAIL_ADDRESS>Status Research & Development GmbH,
Baarerstrasse 10, Zug, Switzerland  Alexander Mozeika  Status Research &
Development GmbH, Baarerstrasse 10, Zug, Switzerland  Marcin P. Pawlowski
Status Research & Development GmbH, Baarerstrasse 10, Zug, Switzerland  Ganesh
Narayanaswamy  Status Research & Development GmbH, Baarerstrasse 10, Zug,
Switzerland

###### Abstract

We present Carnot, a leader-based Byzantine Fault Tolerant (BFT) consensus
protocol that is responsive and operates under the partially synchronous
model. Responsive BFT consensus protocols exhibit wire-speed operation and
deliver instantaneous finality, thereby addressing a fundamental need in
distributed systems. A key challenge in scaling these protocols has been the
computational complexity associated with authenticator verification. We
demonstrate that Carnot effectively addresses this bottleneck by adeptly
streamlining the verification and aggregation of O(log(N)) authenticators per
node. This notable advancement marks a substantial improvement over the
prevailing O(N) state-of-the-art approaches. Leveraging this inherent
property, Carnot demonstrates its capacity to seamlessly scale to networks
comprising tens to hundreds of thousands of nodes. We envision Carnot as a
critical stride towards bridging the gap between classical BFT consensus
mechanisms and blockchain technology.

###### Index Terms:

BFT, Blockchain, Consensus, Latency, Performance, Security.

##  I Introduction

Recently there has been a lot of interest in using BFT-based consensus
protocols in blockchains [1, 2, 3, 4, 5, 6]. The main reason for this
attention is the higher performance of these protocols, i.e. high throughput,
low latency, and the absence of a need for expensive mining to reach a
consensus on a value. The most recent noticeable event related to the latter
was the Ethereum’s merge [7], where Ethereum has merged its main chain, which
used PoW consensus, into the PoS chain that runs a BFT-based consensus thereby
reducing the cost of gas by $99.5\%$.

BFT is the ability of a computer system to tolerate arbitrarily, i.e.
Byzantine[8], faults of its components during the operation. State machine
replication (SMR) refers to the ability of a system to replicate its state
across $N$ nodes in a deterministic manner. Hence, the BFT SMR system will
provide SMR services despite efforts of (at most $M$) Byzantine nodes to break
the system. As is common, we are interested in a partially synchronous
communication model [9] where there is a known maximum bound on message
delivery after some unknown global stabilization time (GST).

BFT-based consensus algorithms can be divided into two categories. The first
category comprises of responsive, but not scalable algorithms[10, 11, 12, 13],
while the second category is comprised of scalable but not responsive
algorithms which also, suffer from chain reorganization, and the lack of
instant finality [14, 5]. Therefore, there is a need for a consensus protocol
that is responsive, has instant finality, is not prone to chain
reorganization, and scales to tens of thousands and potentially hundreds of
thousands of nodes. In the next three paragraphs, we delve into essential
features that are sought after, and highlight all repercussions that arise
from their absence, in a consensus protocol.

Responsiveness. A distinguishing characteristic of partially synchronous BFT
consensus is its _responsiveness_. The latter means that, given a non-
Byzantine leader, the protocol operates at the speed of the network, rather
than being bound by a maximum message delay. In other words, during normal
execution, the protocol is event-driven and does not require waiting for a
round completion. On one hand on a partially synchronous communication model,
optimistic responsiveness holds greater relevance as it is achieved in
optimistic scenarios, typically after the global stabilization time (GST). On
the other hand, protocols that lack responsiveness often introduce a block (or
slot) time parameter, which dictates that the protocol advances to the next
round only at the end of the designated time interval. Unfortunately, this
reliance on time not only slows down the protocol but also creates
vulnerabilities to timing-based attacks. A recent example of such an attack is
the one that affected the Ethereum Gasper, which exploited the protocol’s time
dependency [15], resulting in a loss of approximately $20$ million USD.
Furthermore, responsiveness significantly influences another vital property of
a consensus protocol known as instant-finality.

Finality. In blockchains, _finality_ refers to the confirmation that a
committed block will not be revoked. It is also called safety property in
distributed systems consensus. The time taken from the moment a client submits
a transaction to the network and then receives affirmation of its
finality/safety is called _latency_. Therefore, a low latency protocol
exhibits the instant-finality property. Instant finality improves the client’s
experience and paves the way for many blockchain use cases that weren’t
possible due to the low latency requirements. Moreover, finality prevents
frequent chain reorganization. Chain reorganization also opens attack vectors
when Proof-of-Stake (PoS) is implemented [16]. Changing the algorithm to
address these attacks is very expensive and makes protocol complex [17].

Elastic scalability. Elastic scalability refers to a consensus protocol’s
ability to adapt to changes in the number of nodes in a distributed network.
Carnot BFT is the first protocol to possess this property, making it ideal for
blockchain networks that expand over time. While BFT consensus was originally
designed for small networks, interest in scaling has grown with the
development of blockchain technology. Several scalable BFT consensus protocols
have been proposed, including HotStuff [11], Fast-HotStuff [10], Hermes [18],
and SBFT [13], but they are limited to a few hundred nodes. The Thundrella
[19] and Ethereum Gasper [14] take a different approach, using BFT consensus
within a small committee chosen from a larger pool of nodes. However, the
former relies on proof-of-work as a fallback solution, and the latter has
latency issues and a high risk of chain reorganization. This leads to the
following question.

Is it possible to build a protocol that has elastic scalability, is responsive
and achieves Instant finality?  In this paper, we present Carnot as the first,
to the best of our knowledge, responsive BFT-based consensus protocol with
elastic scalability. Carnot can scale to accommodate a large number of nodes
whereas it can still provide optimistic responsiveness, which helps it to
achieve instant finality. Moreover, it also prevents attacks on PoS due to
chain reorganization.

Authenticator complexity is one of the main bottlenecks in the consensus
protocols [11, 17]. To avoid chain reorganization and achieve responsiveness
and finality, a protocol has to make sure the majority of nodes have attested
the proposal. However, this verification requires at least $O(N)$ signatures
to be aggregated and verified. Although using a peer-to-peer network
significantly reduces the cost of sending authenticators, the verification
cost remains a problem.

To address this issue, responsive pipelined BFT-based protocols [11, 20, 21,
22] have successfully reduced the authenticator verification cost to $O(N)$.
These protocols typically operate by having the leader collect votes from the
previous block and construct a quorum certificate, $QC$, from these votes,
which is then included in the current block. Upon receiving the proposal, each
node needs to verify the $QC$, which serves as proof that more than $2N/3$
nodes in the network have voted. While this approach works effectively for
networks with tens or a few hundred nodes, it becomes inefficient as the
network size grows to thousands or tens of thousands of nodes due to the
aggregation and verification of votes from such a large number of nodes.

Given that the authenticator verification and/or aggregation cost, while
maintaining responsiveness and finality, is the main bottleneck in scaling
consensus protocols, we provide an intuitive solution to this problem. To this
end, we designed a protocol where a node can verify that more than $2N/3$ of
nodes, where $N$ is in thousands ( even tens or hundreds of thousands), have
voted by verifying only a small number of authenticators. Further details of
this protocol will be discussed below.

Assuming that each node in the network is assigned to a committee, with
committees forming binary tree overlay (see Figure 1), and each node has
successfully verified a block, proposed by the leader, the voting process
begins at the leaves of this tree. Members of leaf committees send their votes
to the members of parent committees. Then members of a parent committee
collect votes from at least two-thirds of their child committee and forward
the votes to their parent. This process continues until votes reach the root
committee. Next members of the root committee send their votes, along with
$QC$ representing at least two-thirds of votes from the members of the root
committee’s children, to attest to the proposal 111A member of the root
committee will also forward any additional distinct vote it has received after
casting its vote. More about this will be discussed later.. Finally, the
leader proposes a block and includes proof of votes from the root committee
and its children in the form of $QC$ (from the parent block) appended to the
current block.

The described above process of verifying $QC$, constructed from signatures of
the root committee and its child committees222The count of committees situated
at the upper levels of the binary tree overlay, whose members’ signatures are
encompassed within the $QC$, can be parameterized to offer a customizable
approach., ensures that the majority of nodes in the network have indeed voted
for the block. By collecting and aggregating votes from these committees, the
protocol establishes strong evidence that more than two-thirds of the network
participants have endorsed the proposed block. This low-cost verification step
provides confidence in the validity of the block and strengthens the consensus
achieved by the protocol.

The results of section VII suggest that committee sizes grow logarithmically
with respect to the total number of nodes, $N$, in the network. The latter
allows for a node in a parent committee to verify signatures from its child
committees (see Figure 2) by collecting only $O(\log N)$ signatures. In a
similar manner, the number of signatures that need to be aggregated in the top
three committees is also $O(\log N)$. Hence the protocol is designed to scale
by reducing the cost of the signature verification and aggregation. This
scalability ensures the ability of the protocol to uphold the responsiveness
and finality properties.

##  II Related Work

Currently, there is no other, to the best of our knowledge, consensus protocol
that combines elastic scalability, finality and responsiveness. While there
are consensus protocols that exhibit subsets of these properties, achieving
all three in a single protocol remains a challenge.

On one hand there are protocols which are responsive and provide finality,
such as HotStuff [11], Fast-HotStuff [20], Wendy [21], SBFT [13], [23], Window
based BFT [24], PBFT [12], BFT Smart [25], Aardvark [26], [27] and Zyzzyva
[28], but the complexity of their authenticators varies from $O(N)$ to
$O(N^{2})$. Another group of consensus protocols prioritizes finality over
responsiveness [5, 29, 30]. The latter $O(N)$ authenticator complexity.

On the other hand, there are consensus protocols that offer scalability but
compromise on finality and responsiveness. However, it should be noted that to
the best of our knowledge, there is no known protocol that provides _elastic_
scalability. Nevertheless, there are PoS protocols that can accommodate a
large number of nodes. One such protocol is the Gasper used in Ethereum [14].
The latter achieves scalability by operating on a small subset of nodes
randomly selected from the set of _all_ nodes. However, it relies on the
maximum block generation time interval (or slot time). This time dependency
introduces delays between rounds or views, which hinders the attainment of
finality and increases the likelihood of forks or chain reorganizations.
Consequently, the Gasper protocol provides a suboptimal user experience,
becomes susceptible to timing and PoS attacks, and requires additional
complexity to address these vulnerabilities. The latter makes the protocol
more challenging to maintain and to understand its complexities[17].

To summarise, while there are consensus protocols that excel in certain
aspects, finding a protocol that combines elastic scalability, finality, and
responsiveness in an optimal manner remains a challenge. Here, however, we are
proposing a new consensus protocol, the Carnot, that aims to accommodate all
of these properties within a single protocol. By leveraging innovative design
principles and mechanisms, Carnot seeks to achieve elastic scalability,
providing the ability to adapt to changing network sizes, while maintaining
finality and responsiveness. Through extensive research and analysis, we aim
to address the limitations of existing protocols and pave the way for a more
efficient and robust consensus mechanism in blockchain networks.

##  III System Model and Preliminaries

###  III-A System Model

We consider a system of $N$ nodes where _at most_ $M<\frac{1}{3}N$ nodes may
be Byzantine. $M$ is parameterized to achieve the desired committee size and
failure probability. While honest (or correct) nodes follow the protocol, the
Byzantine nodes may deviate from the latter in an arbitrary manner. We assume
a _partial synchrony_ model [9], i.e. there exists a known bound $\Delta$ on
message transmission delay, applicable after an unknown asynchronous period
called Global Stabilization Time (GST). In practice, the system can only make
progress if the $\Delta$ bound persists for a sufficiently long time, and we
simplify the discussion by assuming that this $\Delta$ bound is _everlasting_.
Furthermore, we assume that _all_ messages exchanged in the system are
_signed_ , and adversaries are computationally bound and cannot forge
signatures (or message digests) with more than negligible probability.
Finally, we assume that Carnot uses _static adversary_ model, i.e. nodes
“decide” if they are correct or corrupted at the beginning of the protocol and
do not change this label during its operation.

###  III-B Preliminaries

View and View Number. A view is identified by a monotonically increasing view
number. During each view, a leader is responsible for submitting a proposal,
and a deterministic (pseudo-random) function is used to select a leader for
that view. This process ensures fairness and randomness in the leader
selection process. The pseudo-random function is based on a random seed
generated by a random Beacon. The deterministic function is used for leader
selection in every view, but during a failure, the random Beacon is also used
to generate a new overlay structure to maintain system availability.

Quorum Certificate (QC), Aggregated QC and high_qc. Quorum Certificate (QC) is
a cryptographic proof that attests agreement (or support) on a specific
proposal (or timeout message) within a group of nodes. It is created by
aggregating signatures of participating nodes. In the Carnot consensus
protocol, there are two types of latest QC, referred to as the local
$high\\_qc$ and the global $high\\_qc$. The local $high\\_qc$ represents the
most recent QC that a node has observed (or received). It serves as a
reference which is used by the node to determine the validity and ranking of
blocks in its local view. In contrast to local $high\\_qc$, the global
$high\\_qc$ represents the most recent QC present in the Aggregated QC
($Aggregated\\_{qc}$). The latter is a compressed representation of the vector
that combines multiple block attestation QCs, providing a collective overview
of the consensus state after unhappy path (failure). In addition to block
attestation QCs, Carnot also utilizes timeout QCs. The latter is a QC
specifically associated with timeout messages and it serves as a proof of the
agreement (or acceptance) of the timeout event within a group of nodes thereby
providing a mechanism to handle failures in the consensus protocol.

Cryptographic scheme selection note. The selection of the signature
aggregation scheme for the implementation of AggQC is a crucial decision. It
will directly impact the execution time of the protocol, due to the overhead
of signatures aggregation and verification. In addition, the decision should
take into account the expected size of a committee. In [31] it was shown that
EdDSA should be favored over BLS for larger deployments (more than 40
validators). The same reasoning is expected for deciding on a source of
randomness for the network. A random beacon construction, in addition to the
security of the scheme, will also impact the execution time of the protocol. A
fully decentralized and multi-party random beacon will increase the security
of the network at the expense of longer randomness generation time, especially
for large-scale deployments. Therefore, we leave these decisions open for
particular instances of the protocol.

Block and Block Tree. The transactions received from clients are batched
together by the leader into a block. The block has a field of the type $QC$.
The leader adds $QC$ of the parent-block, i.e. the preceding block, of the
block being proposed to this field. In this way the block points to its parent
block using the $QC$ of the parent block. We note that every block, except the
genesis block, must specify its parent block and include $QC$ of the parent
block. In this way all blocks are chained together. As there may be forks
during failure, each node maintains a tree, referred to as the $blockTree$ ,
of received blocks. However, blocks that are committed are also linearly
ordered and hence hold a specific position in the blockchain.

Chain and Direct Chain. If block $B$ is stacked atop block $B^{\prime}$ (such
that $B.parent=B^{\prime}$), then these two blocks form the one-chain. If
another block $B^{*}$ is placed atop block $B$, then $B^{\prime}$, $B$, and
$B^{*}$ form the two-chain and so on. Chains grow in two ways. The first is
continuous growth when blocks from consecutive views are directly connected
one after the other. For instance, if $B.curView=B^{\prime}.curView+1$ and
$B.parent=B^{\prime}$, we establish a direct link between $B$ and
$B^{\prime}$, forming a one-direct chain. If $B.curView=B^{\prime}.curView+1$,
$B.parent=B^{\prime}$, and $B^{*}.curView=B.curView+1$ with $B^{*}.parent=B$,
a two-direct link is formed among $B^{\prime}$, $B$, and $B^{*}$.

However, sometimes blocks might not be generated due to leader or network
issues. In these cases, the chain can jump ahead. For example, if
$B.curView=B^{\prime}.curView+k$ ($k>1$) with $B.parent=B^{\prime}$, there’s
no direct link between $B$ and $B^{\prime}$, reflecting a gap in the chain.

##  IV Overlay Tree Formation and Message Dissemination

$C_{0}$$C_{1}$$C_{2}$$C_{3}$$C_{4}$$C_{5}$$C_{6}$$C_{7}$$C_{8}$$C_{9}$ Figure
1: The $N$ nodes in the set $\mathcal{N}$, represented by dots, are assigned
in a _random_ and _unbiased_ way into the _odd_ number, $K$, of committees
$C_{\mu}$, represented by circles, in a such a way that
$\mathcal{N}=\bigcup_{\mu=1}^{K}C_{\mu}$. The _leader_ , represented by the
committee $C_{0}\in\mathcal{N}$, is a special node connected to the root
committee $C_{1}$.

The Carnot presented here is a highly scalable variant of the family of
responsive pipelined consensus protocols [1, 10, 21]. It uses the underlying
peer-to-peer network layer for communication among nodes , but in order to
scale, we use an overlay tree of committees (see Figure 1) for voting (or
$new\\_view$333$new\\_view$ message is used by nodes in the network to enter a
new view when failure is detected. More details are given in subsection V-D
message collection). The tree of committees is defined as follows

######  Definition 1 (Committee Tree).

For the set of nodes $\mathcal{N}=\bigcup_{\mu=1}^{K}C_{\mu}$, where
$N=|\mathcal{N}|$, the committee tree $\mathbb{T}$ is a connected, undirected,
and acyclic graph $\mathbb{T}=(V,E)$, where $V=\\{C_{0},C_{1},\ldots,C_{K}\\}$
is the set of vertices and $E$, with $|E|=K$, is the set of edges. Here the
committee $C_{0}$ contains exactly one node, i.e. $|C_{0}|=1$, and
$C_{0}\in\mathcal{N}$.

In this overlay structure, which is independent of the network layer each
vertex in the tree is a committee of nodes. The latter is used, instead of a
single node, to improve robustness. The novel quorum system of the Carnot
helps the protocol to scale while maintaining responsiveness and instant
finality. However, this design choice results in a probabilistic nature of the
network and of the consensus layer. A more detailed discussion of this will be
presented later, but now we define properties that must be satisfied by the
tree of committees and peer-to-peer network.

######  Definition 2 (Robust Child Committees).

The child committees $C_{\nu}$ and $C_{\mu}$ which share the same parent in
the committee tree $\mathbb{T}$ are robust if at least
$\frac{2(N_{\nu}+N_{\mu})}{3}$ nodes, where $N_{\nu}=|C_{\nu}|$ and
$N_{\mu}=|C_{\mu}|$, are correct in these committees.

######  Definition 3 (Probabilistic Reliable Dissemination).

After the GST, and when the leader is correct and the peer-to-peer network is
robust, all the correct nodes deliver the proposal sent by the leader with
high probability (w.h.p).

For liveness, we assume that peer-to-peer network underlying the Carnot
satisfies properties of the probabilistic reliable dissemination. In practice,
reliability of the peer-to-peer networks will depend on the number of peers a
node is forwarding the received message to. The details of how the data is
received and reshared in the peer-to-peer overlay network are provided in [32,
33].

###  IV-A Overlay Formation

The formation of the overlay structure (see Figure 1) takes a set of nodes
$\mathcal{N}$, size of the committee $n$, that is calculated for a _given_
probability of failure $\delta$ as described in the Algorithm 7, and a random
input $\xi$. We assume that values of these parameters are the same for all
nodes participating in the overlay formation process. The latter is
straightforward, as presented in the Algorithm 1, and can be described as
follows. First, the set of nodes $\mathcal{N}$ is permuted with the random
input $\xi$. This procedure must be deterministic and all permutations must be
equally likely. To this end we are using the Fisher-Yates shuffle as described
in [34].

Next, using parameter $n$, we would like to divide the set $\mathcal{N}$ into
a set of committees of size $n$. In particular
$\mathcal{N}=\bigcup_{\mu=1}^{K}C_{\mu}$, where $C_{\mu}\subseteq\mathcal{N}$
is the committee $\mu$, and $K$ is the number of committees. We note that
$C_{\mu}\bigcap C_{\nu}=\emptyset$ for all $\mu\neq\nu$. The number of
committees $K=\lfloor N/n\rfloor$, but $n$ might not split the set
$\mathcal{N}$ into subsets of equal sizes and a reminder (of nodes) is
expected. To mitigate this we are adding an extra node to the last $r$
committees, where $r$ is the reminder, i.e. each committee indexed by
$\mu\in<K-r,K>$ has $n+1$ nodes, while the rest have $n$ nodes in each
committee. We note that by having (almost) equal committee sizes we are
ensuring that likelihood of one type of failure (see Figure 4), which depends
on committee sizes (see section VII), is not decreased be increasing
likelihoods of other type of failures. Also having uneven committee sizes can
increase the network latency, e.g. a root committee with $n+r$ nodes would
require more resources, depending on the $n$ to $r$ ratio, to move forward the
execution of the consensus.

Finally, the set of committees $\\{C_{1},\ldots,C_{K}\\}$ is mapped onto a
binary tree where the index $\mu$ of the committee $C_{\mu}$ mapped onto one
of its vertices. The latter is implemented via a simple scheme where the
parent vertex, labelled by
$\mu{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1},}$ has
the left and right child vertices labelled, respectively, by $2\mu$ and
$2\mu+1$ Thus, the root committee is $C_{1}$, its left child is $C_{2}$ and
its right child is $C_{3}$. Children of $C_{2}$ are formed with $C_{4}$ and
$C_{5}$, and so on (see Figure 1).

We note that the generation of the overlay tree and node assignment to
committees is deterministic. Therefore, verification and interpretation of the
overlay construction and node membership does not require additional
synchronization and is given by common view of the algorithm inputs.

Algorithm 1 Overlay Tree Formation

1:$\mathcal{N}$ is set of nodes, $n$ is size of the committee, $\xi$ is random
value

2:an overlay tree is formed

3:$K\leftarrow\lfloor N/n\rfloor$ $\triangleright$ $K$ is the number of
committees

4:$r\leftarrow N\mod n$ $\triangleright$ $r$ is a reminder of nodes

5:$nodes\leftarrow\textsc{Shuffle}(\mathcal{N},\xi)$ $\triangleright$ Set of
nodes $\mathcal{N}$ is shuffled with a random seed $\xi$

6:for $K>=\mu>=1$ do

7: if $r>0$ then

8: $C_{\mu}\leftarrow\textsc{Assign}(nodes,n+1)$ $\triangleright$ Assign $n+1$
nodes to $r$ last committees

9: $r\leftarrow r-1$

10: else

11: $C_{\mu}\leftarrow\textsc{Assign}(nodes,n)$ $\triangleright$ Assign $n$
nodes to the rest of the committees

12: end if

13: $V=\\{C_{1},\ldots,C_{K}\\}$

14:end for

15:for $1<=\mu<=K$ do

16: $E\leftarrow\textsc{AddLeftChildEdgeIfExist}(C_{\mu},C_{2\mu})$
$\triangleright$ Add a left child edge from $C_{\mu}$ to $C_{2\mu}$ if
$C_{2\mu}$ exists

17: $E\leftarrow\textsc{AddRightChildEdgeIfExist}(C_{\mu},C_{2\mu+1})$
$\triangleright$ Add a right child edge from $C_{\mu}$ to $C_{2\mu+1}$ if
$C_{2\mu+1}$ exists

18:end for

19:return $\mathbb{T}=(V,E)$ $\triangleright$ Return the overlay tree

Algorithm 2 Propose Block

1:$view$: current view, $quorum$: set of messages from the view

2:broadcast the proposed block to the network

3:assert  is_leader(id)

4:$qc\leftarrow\text{null}$

5:$quorum\leftarrow\text{list}(quorum)$

6:if $quorum[0]$ is of type (Vote) then

7: $\text{assert }\textit{len(quorum) }\geq\textit{
leader\\_super\\_majority\\_threshold()}$

8: $vote\leftarrow quorum[0]$

9:
$qc\leftarrow\textit{build\\_qc}(vote.view,\textit{safe\\_blocks}[vote.block],\text{null})$

10:else if $quorum[0]$ is of type($new\\_view$) then

11: $\text{assert }\textit{len(quorum) }\geq\textit{
leader\\_super\\_majority\\_threshold()}$

12: $new\\_view\leftarrow quorum[0]$

13:
$Aggqc\leftarrow\textit{build\\_Aggqc}(new\\_view.view,\text{null},quorum)$

14:end if

15:$block\leftarrow\text{Block}(view,qc,\textit{[]txs})$

16:$\textsc{broadcast}(block)$

Algorithm 3 Approve Block

1:$block$, $votes$

2:send vote, increment voted view and view number.

3:assert $block.id()\in$ safe_blocks

4:assert $\operatorname{length}(votes)=$ super_majority_threshold( )

5:assert all is_member_of_child_committee( $vote.voter$) for $vote$ in $votes$

6:assert all $vote.block=block.id()$ for $vote$ in $votes$

7:assert $block.view>\text{ highest\\_voted\\_view}$

8:if is_member_of_root_committee( ) then

9: $qc=\text{ $build\\_qc$}(block.view,block,\text{votes})$

10:else

11: $qc=\text{None}$

12:end if

13:$vote:\text{Vote}=\text{Vote}(block=block.id(),voter=\text{self.id},view=block.view,qc=qc)$

14:if is_member_of_root_committee( ) then

15: send($vote$,  leader(block.view + 1))

16:else

17: send($vote$,  parent_committee( ))

18:end if

19:$\text{ increment\\_voted\\_view}(block.view)$ $\triangleright$ to avoid
voting again for this view.

20:$\text{ increment\\_view\\_qc}(block.qc)$

Algorithm 4 Timeout Detected

1:$msgs$: is a set of timeout messages received by the root committee

2:The root committee broadcasts a timeout QC message to all nodes, indicating
that a new view needs to be created

3:$\triangleright$ Root committee detected that supermajority of root + its
children has timed out

4:assert $len(msgs)==leader\\_super\\_majority\\_threshold()$

5:assert $all(msg.view\geq current\\_view\text{ for }msg\text{ in }msgs)$

6:assert $len(set(msg.view\text{ for }msg\text{ in }msgs))==1$

7:assert $is\\_member\\_of\\_root\\_committee(self.id)$

8:$timeout\\_qc\leftarrow\textsc{build\\_timeout\\_qc}(msgs,self.id)$

9:broadcast($timeout\\_qc$) $\triangleright$ we broadcast so all nodes can get
ready for voting on a new view

10:$\triangleright$ Note that $receive\\_timeout\\_qc$ should be called for
root nodes as well

Algorithm 5 Receive Timeout QC

1:$timeout\\_qc$ is a timeout QC message received by a node

2:The node updates its state based on the received timeout QC message and
proceeds to the next step in the protocol

3:assert $timeout\\_qc.view\geq current\\_view$

4:$new\\_high\\_qc\leftarrow timeout\\_qc.high\\_qc$

5:$update\\_high\\_qc$($new\\_high\\_qc$)

6:$update\\_timeout\\_qc$($timeout\\_qc$)

7:$\triangleright$ Update our current view and go ahead with the next step

8:$update\\_current\\_view\\_from\\_timeout\\_qc$($timeout\\_qc$)

9:$rebuild\\_overlay\\_from\\_timeout\\_qc$($timeout\\_qc$)

Algorithm 6 Approve $new\\_view$

1:$timeout\\_qc$ is a timeout QC message and $new\\_views$ is a set of new
view messages received by a node

2:The node approves the new view, updates its state, and broadcasts the new
view message to relevant nodes

3:if $last\\_view\\_timeout\\_qc\neq None$ then

4: assert $\forall new\\_view\in new\\_views$,
$new\\_view.view>last\\_view\\_timeout\\_qc.view$

5:end if

6:assert $\forall$ $new\\_view\in new\\_views$,
$new\\_view.timeout\\_qc.view=timeout\\_qc.view$

7:assert $len(new\\_views)=overlay.super\\_majority\\_threshold()$

8:assert $\forall$ $new\\_view\in new\\_views,$
$is\\_member\\_of\\_child\\_committee(new\\_view.sender)$

9:$\triangleright$ The new view should be for the view successive to the
timeout

10:assert $\forall$ $new\\_view\in
new\\_views,timeout\\_qc.view+1=new\\_view.view$

11:$view\leftarrow timeout\\_qc.view+1$

12:assert $highest\\_voted\\_view<view$

13:$\triangleright$ Get the highest QC from the new views

14:$messages\\_high\\_qc\leftarrow\\{new\\_view.high\\_qc\mid new\\_view\in
new\\_views\\}$

15:$high\\_qc\leftarrow\max([timeout\\_qc.high\\_qc,*messages\\_high\\_qc],key=\lambda
qc:qc.view)$

16:update_high_qc($high\\_qc$)

17:$timeout\\_msg\leftarrow$ $new\\_view$(view=view, high_qc =local_high_qc ,
sender=id, timeout_qc=timeout_qc)

18:if is_member_of_root_committee(self.id) then

19: $AggregatedQC\leftarrow buildAggQC(new\\_views)$

20: $timeout\\_msg.Aggregated\\_qc=AggregatedQC$

21: send($timeout\\_msg$, overlay.leader(current_view + 1))

22:else

23: send($timeout\\_msg$, *overlay.parent_committee(id))

24:end if

25:$\triangleright$ This checks if a node has already incremented its voted
view by local_timeout. If not then it should do it now to avoid voting in this
view.

26:highest_voted_view $\leftarrow\max\\{\text{highest\\_voted\\_view},view\\}$

##  V The Carnot protocol

The protocol is designed to operate in rounds, where each round corresponds to
a view in the system. At the beginning of each round, a leader is chosen for
this round, and the leader proposes a batch of transactions (in the form of a
block) that the nodes will attempt to agree on. First, we will provide an
overview of message types used in Carnot followed by a description of the
protocol.

###  V-A Message Types

When node casts a vote for a proposed block, it creates the _Vote_ object
$\langle view,block.Id(),voter\rangle$ that includes the view number, the hash
value of the proposed block , computed by the $block.Id()$ function, and
identifier of the voting node. The vote is then signed over the $view$ and
$block.Id()$ fields.

The quorum certificate (QC), represented by $\langle
view,block.Id(),voters\rangle$, is a collection of votes for the same view and
block hash ($block.Id()$), along with aggregated signatures of the voters over
the view and $block.Id()$ fields. The set of voters in the QC is represented
as a bit array with a single $1$ bit in the same index as the corresponding
node identifier in the array of node IDs.

The timeout message , given by $\langle view,high\\_qc,sender\rangle$ is used
to inform other nodes of a about the timeout event. The timeout QC
$timeout\\_qc$ is a collection of timeout messages, signed over the view of
the timeout message and $high_{qc}.view$.

The new view message, given by $\langle
view,high\\_qc,sender,timeout\\_qc,{Aggregated\\_qc}\rangle$, is signed over
the current view and the view of the $high\\_qc$. $Aggregated\\_qc$ is only
used by the root committee to forward the $Aggregated\\_qc$ of its children
committees to the next leader, similar to forwarding votes in happy
path444Alternatively, the members of the children committees of the root
committee broadcast their $new\\_view$ messages to the root committee and the
next leader. Each member of the root committee also sends their $new\\_view$
message to the next leader upon receipt of the $super\\_majority\\_threshold$
of the $new\\_view$ messages from its children committee members..

The $Aggregated\\_{qc}$ $\langle view,qc\\_views,senders,high\\_qc\rangle$ is
a collection of $new\\_view$ messages. The next leader builds the aggregated
signature of the aggregated $QC$ by aggregating the signatures of $new\\_view$
messages.

After receiving the proposal the following steps occur:

###  V-B The Happy Path Overview

  * •

Each node in the network independently verifies the validity of a new block.

  * •

If there is a parent committee, nodes in the leaf committee send their votes
to the nodes in the parent committee.

  * •

Each node in the parent committee waits to receive two-thirds of the votes
from both child committees before voting on the block’s validity themselves
(see Figure 2). Once they have reached the required threshold, each node from
the parent committee casts their vote on the block’s validity to their parent
committee(if there is any).

  * •

Nodes at the root committee cast their vote for the leader of the next view.
If the root committee has children committees, then it will also forward the
quorum certificate of children committees in its vote to the next leader.

  * •

Once, a member of the root committee has cast its vote, it forwards any
additional distinct vote to the leader of the next view.

  * •

The leader of the next view builds a QC from more than two-thirds of the votes
(from the root committee and its children combined) it received from the root
committee. It adds the QC to the block and proposes it to the network.

###  V-C The Unhappy Path Overview

The protocol switches to an unhappy path when a failure is detected. The
unhappy and happy paths are very similar. A failure is detected by inspecting
the $timeout\\_qc$ for the current view or a higher view. We note that this
step is analogous to the block proposal in the happy path. Whereas, the
$new\\_view$ message moves through the overlay similar to the votes in the
happy path. This upward movement of $new\\_view$ messages ensures that nodes
agree to begin the next view and also to move the most recent $QC$ (global
$high\\_qc$) upward. The latter will be used by the next leader to propose the
next block pointing to the $high\\_qc.block$ as its parent. More details about
the unhappy path are given in the next subsection , but here we provide a
brief overview.

  * •

Upon timeout, all nodes including the members of root and its children
committees, stop participating in the consensus.

  * •

Member of the root committee and its children send their timeout messages to
the root committee.

  * •

The nodes in the root committee build a $timeout\\_qc$ and broadcast it to the
network.

  * •

Each node recalculates the new overlay.

  * •

The nodes in leaf committees of the new overlay send their $new\\_view$
messages to the nodes of their parent committee.

  * •

Upon receipt of two-thirds of $new\\_view$ messages from child committees,
each node in the parent committee updates its $high\\_qc$ if
$new\\_view.qc.view>high\\_qc.view$. Then each node builds $new\\_view$
message with updated $high\\_qc$ and forwards it to the nodes in its parent
committee. The latter ensures that the latest $high\\_qc$ moves upward in the
overlay.

  * •

The root committee forwards to the leader its $new\\_view$ messages together
with the $Aggregated\\_{qc}$ from two-thirds of $new\\_views$ of its children.

  * •

The next leader builds an aggregated $QC$ from the $new\\_view$ messages it
has received. Then it adds this $Aggregated\\_{qc}$ to the block and proposes
this block.

$C_{0}$$C_{1}$$C_{2}$$i$$C_{3}$$C_{4}$$C_{5}$ Figure 2: The node $i$ in the
committee $C_{2}$ collects votes from its children committees, i.e. the
committees $C_{4}$ and $C_{5}$, then it casts its own vote to nodes in the
parent committee $C_{1}$.

###  V-D Detailed description of the protocol

As a block proposer, the role of the leader is to convince other nodes that
the proposed block carries the latest QC during the happy path. In this
scenario if the view of the proposed block is one more than the view of the
QC, i.e. $block.view==block.qc.view+1$, then this is considered to be the
proof that this QC is the latest.

During an unhappy path, a leader has to make sure that the proposed block is
extending the last committed block, i.e. the latter is not averted by the
proposed block. To satisfy this condition the leader has to provide a proof in
the form of $Aggregated\\_{qc}$. The global $high\\_qc$ in the
$Aggregated\\_{qc}$ is the $QC$ of the last committed block in the network or
a $QC$ of a more recent , i.e. with a higher view number, than the last
committed block. In the safety proof (see section VI) we show how the global
$high\\_qc$ in the $Aggregated\\_{qc}$ is the $QC$ of the last committed block
by the network or a $QC$ formed after the $QC$ of the last committed block.
Let us now consider the happy and unhappy paths.

####  V-D1 The happy path

The Algorithm 2 is executed by the leader who either receives a set of votes
or a set of $new\\_view$ messages. In the context of this algorithm a set of
votes indicates that the view , during which nodes received a proposal (also
called block) and have voted , was successful. If the leader receives a set of
votes then it checks if the number of votes is greater than or equal to the
$leader\\_super\\_majority\\_threshold$ 555More than two-third members of the
root committee and its child committees.. If the latter is true then leader
builds a QC , which is added to the block along with any transactions for the
current view, and proposes the block to the network by broadcasting it.

The Algorithm 3 is called when a node receives a block from the leader and a
set of votes for the same block from the nodes in its children committee. The
vote set is empty if the committee to which the node belongs has no children.
The goal of the algorithm is to send a vote for a given block and to increment
the voted view (to avoid duplicate voting) and view number. The block received
has to be safe, i.e. $block.id()\in safe\\_blocks$. A block is safe if the
$block.view==block.qc.view+1$ or the $block.view==block.AggQC.view+1$ and
$block.qc==AggQC.high\\_qc$. This means that during the happy path a block is
safe if $block.view==block.qc.view+1$. The latter condition shows that
$block.qc$ is the latest $qc$ formed before the block which is known by the
majority of nodes or more recent than the recent $qc$ known by the majority of
nodes.

The Algorithm 3 also performs other checks including one which makes sure that
the votes received by a node are from its children and that the number of
votes received is at least the two-thirds of the total number of its children,
i.e. exceeding the $super\\_majority\\_threshold$. If checks , i.e. the lines
$1-5$ in the algorithm, are successful then the node will send its vote to the
parent committee. If the node is a member of the root committee, then it will
build $QC$ from the votes collected from its children committees add to it its
own vote and forward it to the leader of the next view. The leader of the next
view will build a $QC$ from more than the two thirds of votes from the nodes
in the root and its children committees
($leader\\_super\\_majority\\_threshold$). Then the leader assigns $QC$ to the
$block.qc$ and proposes the block as described in the Algorithm 2.

####  V-D2 The unhappy path

To ensure low authenticator complexity, the Carnot differs from traditional
BFT-based protocols in its approach to the unhappy path. Instead of waiting
for a large number of nodes to fail, the Carnot detects failure when the
_$leader\\_super\\_majority\\_threshold$_ of nodes in the root and its
children committees fail.

In the unhappy path, the nodes that are not in the root and its children
committees stop voting after the timeout. The nodes in the root and its
children committees send timeout messages to each node in the root committee
which indicates that a new view needs to be created. Then nodes in the root
committee build the timeout $QC$, thereby reducing the overall complexity and
ensuring that the protocol can continue even in the face of node failures.

The Algorithm 4 is executed by the root committee when it detects that a
$leader\\_super\\_majority$ of nodes in the current view from the root and its
children committees have timed out. The purpose of this algorithm is to
initiate the creation of timeout $QC$ and to notify all nodes in the network
that a timeout has occurred. The algorithm takes as input the set of timeout
messages received by the root committee. These timeout messages are sent by
nodes, from the root committee and its children committees, when they detect
that the view (round) has failed to be executed in a timely manner. The
algorithm then performs several checks to ensure that the timeout messages are
valid. It checks that they have a view number that is greater than or equal to
the current view and that all messages have the same view number. The
algorithm then builds the timeout QC message. This message is broadcasted to
all nodes in the network. The purpose of the latter is to notify all nodes
that a new view needs to be created and to get them ready for sending their
new view messages upward, i.e. to the parent committee members. The new view
messages are used by a node to update its $high\\_qc$ and to send the
$high\\_qc$ to the nodes in its parent committee. In this way the $high\\_qc$
moves to the top of the committee tree and reaches the next leader without the
broadcasting and verification of $O(N)$ messages. Upon receipt of the
$timeout\\_qc$ message a node updates its $high\\_qc$, increments the view
number, and rebuilds the overlay (see the Algorithm 5).

The Algorithm 6 is executed by a node after the Algorithm 5. This algorithm
uses the set of new view messages $new\\_views$ and the timeout QC message
previously received as an input from the set of $timeout\\_qc$ messages used
in the Algorithm 5. The $new\\_view$ messages received are from the nodes in a
child committees and hence the set of $new\\_view$ messages will be empty for
a node in a leaf committee. The purpose of Algorithm 6 is to approve the new
view and make sure that the next leader receives the global $high\\_qc$. The
latter enables the leader to build a block that points to the block of the
global $high\\_qc$ as its parent. Furthermore, the algorithm ensures that the
view of the $new\\_view.view=timeout\\_qc.view+1$, where $timeout\\_qc$ is the
latest $timeout\\_qc$ of the node. Next it checks that the number of new view
messages is greater than or equal to the supermajority threshold. Also the
algorithm verifies that all senders of the new view messages are the nodes
from children committees and gets the highest QC message from the new views
and updates the local $high\\_qc$ value. Finally, the algorithm creates the
new view message and broadcasts it to the nodes in parent committee. If the
node is a member of the root committee then it sends this message to the
leader of the next view , but otherwise it sends the new view message to all
nodes in parent committees. After broadcasting the new view message, the
algorithm checks if a node has already incremented its voted view by the
$local\\_timeout$. If not, it increments the voted view to avoid voting
(forwarding $new\\_view$ messages) in this view again.

##  VI The Carnot protocol: Proof of Correctness

Any consensus protocol must satisfy two main properties, namely the safety and
liveness. The Carnot protocol offers a _probabilistic_ guarantee of these
properties as follows.

######  Definition 4 (Safety).

If a single (correct) node in a blockchain consensus protocol commits a block
at a specific position in the blockchain (blockchain height) and no other
block will ever be committed at that position, even in the presence of
Byzantine nodes, then this protocol is considered to be safe (w.h.p).

######  Definition 5 (Liveness).

A protocol is alive if even in the presence of Byzantine nodes it guarantees
eventual progress (w.h.p). This means that honest nodes will always reach an
agreement and the protocol will eventually terminate (w.h.p).

The safety and liveness of the Carnot protocol are proved, respectively, in
the Lemmas 1-3 and Lemma 4. In Lemma 1 we show that the existence of a valid
$QC$ (Quorum Certificate) for a given block $b$ guarantees (w.h.p.) that more
than $2/3$ of nodes in the network have voted for $b$. This insight from the
Lemma 1 is essential and is a cornerstone of the safety proof. The Lemma 1 is
then used in the Lemma 2 to establish that the network will not produce $QC$
for two _distinct_ blocks within the same view. The latter implies that at
most one block will be approved within a single view. Next the Lemmas 1 and 2
are used in the proof of Lemma 3. This lemma substantiates that committing two
conflicting blocks is an impossibility. Therefore, once a block is committed
then this block and its lineage of ancestors can not be revoked. Finally, the
Lemma 4 guarantees that the protocol makes progress.

######  Lemma 1.

Suppose that the $QC$ certificate for a proposal was built and the number of
Byzantine nodes is at most $M<\frac{1}{3}N$ then at least $\frac{2N}{3}+1$
nodes in the committee tree $\mathbb{T}$, generated by the Algorithm 1, have
voted for this proposal (w.h.p).

###### Proof.

Let $C_{\mu}$ be a committee in the committee tree $\mathbb{T}$ (see
Definition 1) and assume that all child committees in $\mathbb{T}$ are robust
(see Definition 2). We split the proof of the lemma into two parts. First, we
prove that if a node $j\in C_{\mu}$ has voted for a block $b$ in the view $v$,
then at least ${\frac{2(N_{\mu_{1}}+N_{\mu_{2}})}{3}}$, where
$N_{\mu}=|C_{\mu}|$, nodes in each pair of siblings $C_{\mu_{1}}$ and
$C_{\mu_{1}}$ in a sub-tree of the committee $C_{\mu}$ have voted for the
block $b$ during the view $v$. Second, we prove that at least $\frac{2N}{3}+1$
nodes in the network have voted for the block $b$.

It is clear that in a tree with only one committee, i.e. $\mathbb{T}=C_{1}$,
at least $\frac{2N_{1}}{3}+1$ of nodes in the committee $C_{1}$ has to vote in
order to build a $QC$ for the block $b$. The same is true for a tree with
three committees: the root committee $C_{1}$ forwards the votes from both of
its child committees, i.e. the committees $C_{2}$ and $C_{3}$, to the next
leader (see Figure 1). For any tree $\mathbb{T}$ with more than three
committees the first part can be proven by induction.

The base case: When node $j$ receives the $QC$ of a block proposal $b$ with
the view $v$ this implies that at least
$\frac{2\sum_{\mu=1}^{3}N_{\mu}}{3}+1$, where $N_{\mu}=|C_{\mu}|$, of nodes
from the root committee and its children $\cup_{\mu=1}^{3}C_{\mu}$ have voted
for $b$. Let us define the set $C^{\mathrm{v}}_{\mu}\subseteq C_{\mu}$ of
nodes which voted for proposal $b$ then the set of nodes from both child
committees that have voted is given by $C^{\mathrm{v}}_{2}\cup
C^{\mathrm{v}}_{3}\subseteq C_{2}\cup C_{3}$. We note that
${N^{\mathrm{v}}_{2}+N^{\mathrm{v}}_{3}\geq\frac{2(N_{2}+N_{3})}{3}}$, where
$N^{\mathrm{v}}_{\mu}=|C^{\mathrm{v}}_{\mu}|$. Similarly honest node $i\in
C^{\mathrm{v}}_{2}$ if it has verified the block $b$ and has received at least
$\frac{2(N_{4}+N_{5})}{3}$ votes from its child committees $C_{4}\cup C_{5}$.
The same is true for any honest node in $C^{\mathrm{v}}_{3}$.

The induction step : At any level of the tree $\mathbb{T}$, if honest node
$j\in C_{\mu}$ has voted, it implies that at least
$\frac{2(N_{2\mu}+N_{2\mu+1})}{3}$ of nodes from its child committees
$C_{2\mu}$ and $C_{2\mu+1}$ have voted for the block $b$ in view $v$, or the
$C_{\mu}$ is a leaf committee (see Algorithm 3). Now by recursively applying
this argument to all committees in the sub-tree $\mathbb{T}_{\mu}$ induced by
$C_{\mu}$ until leaf committees are reached, we have proved the first part.

We note that since the committee tree $\mathbb{T}$ was generated by the
Algorithm 1 this implies that the sizes of any two committees may differ by at
most one node. The latter rules out a scenario when some of the child
committees contain _only_ Byzantine nodes, but the tree $\mathbb{T}$ is
robust.

Let us now prove the second part. We know that a node $i\in C_{1}$ only sends
its vote to the leader if it has receive d at least $\frac{2(N_{2}+N_{3})}{3}$
of votes from the committees $C_{2}$ and $C_{3}$. Furthermore, when node $j$
receives the $QC$ for block $b$, then this implies that at least
$\frac{2\sum_{\mu=1}^{3}N_{\mu}}{3}+1$, where $N_{\mu}=|C_{\mu}|$, of nodes in
$\cup_{\mu=1}^{3}C_{\mu}$ have voted. Now by combining the number of nodes
which voted from the base case and induction step of the first proof we have
that the total number of nodes in $\mathbb{T}$ that have voted ,
$N^{\mathrm{v}}$, is given by

$\displaystyle N^{\mathrm{v}}$
$\displaystyle=|\cup_{\mu=1}^{3}C^{\mathrm{v}}_{\mu}|+\sum_{\mu=2}^{\tilde{K}}|C^{\mathrm{v}}_{2\mu}\cup
C^{\mathrm{v}}_{2\mu+1}|$ (1)

from which follows

$\displaystyle N^{\mathrm{v}}$
$\displaystyle\geq\frac{2\sum_{\mu=1}^{3}N_{\mu}}{3}+1+\sum_{\mu=2}^{\tilde{K}}\frac{2(N_{2\mu}+N_{2\mu+1})}{3}$
(2)

and hence

$\displaystyle{N^{\mathrm{v}}}$ $\displaystyle\geq\frac{2N}{3}+1$ (3)

We note that for $N$ nodes with at most $M<\frac{1}{3}N$ Byzantine nodes all
child committees in the tree $\mathbb{T}$ are robust w.h.p. (see section VII)
and hence above is true w.h.p.

∎

######  Lemma 2.

For any two valid $QC$s, the $qc_{1}$ and $qc_{2}$, when the $qc_{1}.block$
conflicts with the $qc_{2}.block$ then $qc_{1}.view\not=qc_{2}.view$.

###### Proof.

We prove this by contradiction. Assume that there are two $QC$s such that
$qc_{1}.view==qc_{2}.view$ and $N^{v_{1}}$ number of nodes have voted for
$qc_{1}$. The latter implies that $N^{v_{2}}=N-N^{v_{1}}$ number of nodes have
voted for $qc_{2}$, but from the Lemma 1 follows that
$N^{v_{1}}\geq\frac{2}{3}N+1$ and hence $N^{v_{2}}\leq\frac{1}{3}N-1$.
However, by the same lemma $N^{v_{2}}\geq\frac{2}{3}N+1$ which can be only
true if at least $\frac{2}{3}N+1-(\frac{1}{3}N-1)=\frac{1}{3}N+2$ number of
nodes have voted for both $QC$s. Comparing this number with the number of
Byzantine nodes $M<\frac{1}{3}N$ we infer that even if all Byzantine nodes
have voted for both $QC$s we will have at least
$\frac{1}{3}N+2-\left(\frac{1}{3}N-1\right)=3$ honest nodes which voted for
both $QC$s. However, an honest node never votes twice in the same view, so our
assumption is incorrect. Hence, this Lemma is correct for any
$M<\frac{1}{3}N$. ∎

$QC\;\;a$$QC\;a^{\prime}$$QC\;a^{\prime\prime}$$QC\;\;b$$QC\;b^{\prime}$$QC\;b^{\prime\prime}$
Figure 3: The blocks $a$ and $b$ in the blockchain are conflicting blocks, but
block $b$ was committed first.

######  Lemma 3.

If the blocks $a$ and $b$ are in conflict, then they cannot be committed by an
honest node.

###### Proof.

This lemma can also be proven by contradiction. We begin by observing that
block $a$ and block $b$ cannot both belong to the same view, as demonstrated
in the argument of Lemma 2. Let us assume that block $a$ is committed by an
honest node during view $v$ through a two-chain (one-direct chain) sequence
$a,a^{\prime},a^{\prime\prime}$. Similarly, let’s assume that block $b$ is
committed through a two-chain sequence $b,b^{\prime},b^{\prime\prime}$ (one-
direct chain). Additionally, both of these two-chain sequences have their
respective Quorum Certificates (QCs). Without loss of generality, we also
assume that block $a$ is added to the chain at a higher view than
$b^{\prime}$, meaning $a^{\prime}.QC.view>b^{\prime\prime}.QC.view$.

Let $v_{s}$ be the lowest view number higher than the view of $b^{\prime}$,
denoted as $v_{b^{\prime}}$, such that
$v_{b^{\prime}}=v_{b^{\prime\prime}}.QC.view$. During this view $v_{s}$, a
Quorum Certificate $qc_{s}$ is formed, and $qc_{s}.block$ is in conflict with
block $b$. The view number of the latter is given by
$v_{b}=v_{b^{\prime}}.QC.view$. We will now define the following predicate:

$E(qc):=(v_{b^{\prime}}<qc.view\leq v_{a})\land(qc.block\textit{ conflicts
with b})$

The Quorum Certificate (QC) representing the first conflicting block with
respect to block $b$ is given by:

$qc_{s}:=\operatornamewithlimits{argmin}\limits\limits_{qc}\\{qc.view|\textit{qc
is valid}\land E(qc)\\}.$

The $qc_{s}$ exist by our assumption and we also assume that
$a^{\prime}.QC=qc_{s}$. Let $i$ be the node that has voted for both the
$qc_{s}$ and $b^{\prime\prime}.QC$. We note that by definition $qc_{s}$ is the
first conflicting block which has the lowest view number among the conflicting
blocks for $b$. Therefore, block $a$ has to be in $safe\\_blocks$. Let us now
check if the conflicting block $qc_{s}.block$ is in $safe\\_blocks$. In
Algorithm 3 the first assertion is False. This is because if a block ($a$)
satisfies the condition $block.view==block.qc.view+1$ then it cannot be in
conflict with the block $b$, because $block.qc$ is the $QC$ for $b$.
Furthermore, let block $t$ be the parent (ancestor) of the $qc_{s}.block$. The
definition of $qc_{s}$ implies that the $t.view\leq b^{\prime}.view$ , but
since the $qc_{s}.block$ is in conflict with the block $b$, and $b$ is
committed, therefore the block $t$ is not the block $b$ or $b^{\prime}$ and
hence $t.QC.view<b^{\prime}.QC.view$. Then by the second part of the second
condition the $block.view==block.AggQC.view+1$ and $block.qc==AggQC.high\\_qc$
is also false. This is because when a two-chain (with one direct-chain) is
formed by the blocks $b$, $b^{\prime}$ and $b^{\prime\prime}$ it implies that
at least $2M+1$ nodes have the $QC$ ($b^{\prime}.QC.block=b$). Therefore the
$high\\_qc$ ,built from $QC$s of $2M+1$ distinct nodes, collected by the new
leader in the unhappy path will have $high\\_qc.view\geq b.view$. Hence, the
fact that the $i$ has voted for the $qc_{s}.block$ is incorrect and
contradicts our assumption.

∎

######  Lemma 4.

If a sufficient amount of time is elapsed after the GST such that a correct
leader is elected and all correct nodes are in the same view then a block $b$
will be committed during this time.

###### Proof.

Given that a time interval after the GST is sufficiently large, it will be a
time when two correct leaders are elected consecutively, all child committees
in the overlay tree are robust, and correct nodes are in the same view, then
the one-direct chain $b,b^{\prime}$ will be formed between the blocks $b$ and
$b^{\prime}$ proposed by leaders. Now the two-chain
$b,b^{\prime},b^{\prime\prime}$ is required for the block $b$ to get
committed. However, the block $b^{\prime\prime}$ will eventually be added by
another correct leader. ∎

##  VII Analysis of failures

###  VII-A Robustness of committee trees

A cornerstone of the correctness proof is the Lemma 1 which ensures that at
least $2/3$ of nodes in the network have voted for a proposal. The latter
relies on a committee tree (see Figures 1 and 2) generated by the Algorithm 1.
This algorithm takes as input the committee size parameter, $n$, and a set of
nodes of size $N$. The committee size $n$ is computed by the Algorithm 7 (see
Appendix C) for a given number of nodes $N$, assumed fraction of Byzantine
nodes, $P$, and probability of failure $\delta(E_{1}(1/3))$. The latter is the
probability that in at least one committee more than $1/3$ of nodes are
Byzantine (see Appendix A-B) and it _dominates_ other failure probabilities in
our model (see Appendix A-A).

###  VII-B Robustness of child committees

The probability of failure $\delta(E_{2}(1/3))$, i.e. in at least one
$C_{\mu_{1}}\cup C_{\mu_{2}}$, where the child committees $C_{\mu_{1}}$ and
$C_{\mu_{2}}$ share the same parent, more that $1/3$ of nodes are Byzantine
(see Appendix A-C), is bounded from above by $\delta(E_{1}(1/3))$ which is a
consequence of the Proposition 2 (see Appendix D). The latter ensures that
given $\delta(E_{1}(1/3))$ all child committees in a committee tree, generated
by the Algorithms 1 and 7, are _robust_ (see Definition 2 ) with the
probability $\delta(E_{2}(1/3))\leq\delta(E_{1}(1/3))$. The probability
$\delta(E_{2}(1/3))$ can be much smaller than $\delta(E_{1}(1/3))$ as can be
seen in the Figure 6.

###  VII-C Logarithmic growth of committee sizes

When $A>P$ the probability of failure $\delta(E_{1}(A))$, i.e. the probability
that in at least one committee more that the fraction of nodes, $A$, are
Byzantine (see Appendix A-B), is bounded above as follows

$\delta(E_{1}(A))\leq\sum_{\mu=1}^{K}\mathrm{e}^{-N_{\mu}\mathrm{D}\left(A(\mu)||P\right)},$
(4)

where $A(\mu)=\frac{\lfloor AN_{\mu}\rfloor+1}{N_{\mu}}$, for both the
hypergeometric (9) and binomial (11) distributions of committee sizes [35]
used in our model (see Appendix A-A). For $N=nK+r$ nodes the Algorithm 1
creates the $K-r$ and $r$ committees with, respectively the sizes $n$ and
$n+1$ then it is easy to show that
$\sum_{\mu=1}^{K}\mathrm{e}^{-N_{\mu}\mathrm{D}\left(A(\mu)||P\right)}\leq
K\mathrm{e}^{-n\,\mathrm{D}\left(A||P\right)}$ and hence $\delta(E_{1}(A))\leq
K\mathrm{e}^{-n\,\mathrm{D}\left(A||P\right)}$ which is equivalent to
$\log(N/\delta(E_{1}(A))\geq n\,\mathrm{D}\left(A||P\right)+\log(n)$. The
latter for $n\geq n_{\min}$, where $n_{\min}$ is the _minimum_ number of nodes
in a committee, leads us to the inequality

$n\leq\frac{1}{\mathrm{D}\left(A||P\right)}\log\left(\frac{N}{n_{\min}\,\delta(E_{1}(A)}\right).$
(5)

Thus the size of a committee grows at most _logarithmically_ with
$N/\delta(E_{1}(A)$ (see Figure 7). Also for $A=1/3$ and $P=A-\epsilon$, where
$\epsilon\in(0,A)$, the upper bound in (5) is given by
$\frac{1}{\mathrm{D}\left(1/3||1/3-\epsilon\right)}\log\left(\frac{N}{n_{\min}\,\delta(E_{1}(A)}\right)=\left[\frac{4(1-\epsilon)}{9\epsilon^{2}}-\frac{19}{18}-\frac{4\epsilon}{9}+O\\!\left(\epsilon^{2}\right)\right]\log\left(\frac{N}{n_{\min}\,\delta(E_{1}(A)}\right)$
when $\epsilon\rightarrow 0$ and hence for the probability of failure
$\delta(E_{1}(A)$ to remain the same the size of a committee $n$ has to grow
(at most) as $O(1/\epsilon^{2})$ when the fraction of Byzantine nodes in the
network approaches $1/3$. Therefore, scalability of the protocol is achieved
through a logarithmic growth of committee sizes with respect to $N$. As a
consequence, nodes need to verify only $O(\log N)$ signatures, whereas each
member of the root committee and the leader aggregate only $O(\log N)$
signatures.

###  VII-D Necessary conditions for QC

The Lemma 1 assumes that a QC certificate was built. The _necessary_
conditions for the latter are the election of an honest leader, all child
committees in committee tree are robust, and more than $2/3$ of nodes in the
top three comm. have to be honest, i.e. we have so-called “leader super-
majority”. The latter is equivalent to the events $E_{0}$ (election of
Byzantine leader), $E_{3}(1/3)$ (failure of leader super-majority), and
$E_{2}(1/3)$ (failure of child committee robustness) not occurring (see
Appendix A for a more precise definition). Now the probability
$\mathrm{P}(E_{0}\cup E_{3}(1/3)\cup E_{2}(1/3))$, i.e. at least one of these
events has occurred, is bounded as follows

$\displaystyle\mathrm{P}(E_{0}\cup E_{2}(1/3)\cup E_{3}(1/3))$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\leq\mathrm{P}(E_{0})+\mathrm{P}(E_{2}(1/3))+\mathrm{P}(E_{3}(1/3))$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\leq
P+\delta(E_{2}(1/3))+\delta(E_{3}(1/3))$ (6)

by the union bound and hence the probability that none of these events has
occurred, i.e. necessary conditions for QC, is bounded from below as follows

$\displaystyle 1-\mathrm{P}(E_{0}\cup E_{2}(1/3)\cup E_{3}(1/3))$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\geq
1-P-\delta(E_{2}(1/3))-\delta(E_{3}(1/3))$ (7)

We note that $\delta(E_{2}(1/3))\leq\delta(E_{1}(1/3))$ and
$\delta(E_{3}(1/3))\leq\delta(E_{1}(1/3))$ by, respectively, the Propositions
2 and 3 (see Appendix D). Hence the lower bound in (7) is greater than
$1-P-2\delta(E_{1}(1/3))$. Now the probability of failure $\delta(E_{1}(1/3))$
can be made as small as possible by choosing $K$ (see Figure 4) and hence the
lower bound in (7) is approximately $1-P$ which is greater than $2/3$ for
$P<1/3$. Thus the necessary conditions for QC are created with high
probability.

###  VII-E Safety failure analysis

The events $E_{3}(2/3)$ and $E_{1}(1/2)$, i.e., respectively, more than $2/3$
of nodes in the top three committees and more than $1/2$ of nodes in at least
one committee are Byzantine, are considered to be safety failures. Having
committees with more than $1/2$ of nodes being Byzantine can jeopardize
safety. Byzantine nodes in such committee might rush to approve blocks,
bypassing votes from other committee members, while all nodes from its sibling
committee have voted. The latter may cause the subtree of the corrupt
committee to lag behind whereas the remaining parts of the overlay tree “move”
faster. During the view change this could result in more than $2/3$ of nodes
lacking QCs for the latest committed block. The probability of this event,
however, is very small (see Figure 6).

The probability $\mathrm{P}(E_{3}(2/3)\cup E_{1}(1/2))$ that at least one of
these events will happen is bounded from above as follows

$\displaystyle\mathrm{P}(E_{3}(2/3)\cup E_{1}(1/2))$ $\displaystyle\leq$
$\displaystyle\mathrm{P}(E_{3}(2/3))+\mathrm{P}(E_{1}(1/2))$ (8)
$\displaystyle=\delta(E_{3}(2/3))+\delta(E_{1}(1/2))$

by the union bound. We note that $\delta(E_{3}(2/3))\leq\delta(E_{3}(1/3))$
and $\delta(E_{1}(1/2))\leq\delta(E_{1}(1/3))$ by the Proposition 1 (see
Appendix D). Also $\delta(E_{3}(1/3))\leq\delta(E_{1}(1/3))$ by the
Proposition 3 and hence the upper bound in (8) is at most
$2\delta(E_{1}(1/3))$. However, the probabilities $\delta(E_{3}(2/3))$ and
$\delta(E_{1}(1/2))$ can be much smaller than $2\delta(E_{1}(1/3))$ as can be
seen in Figure 6.

Figure 4: Failures in a committee tree. The $N$ nodes (blue and red dots) are
assigned _randomly_ into the _odd_ number, $K$, of committees (circles with
solid boundaries). Also, there is a special node representing the _leader_
(blue node connected to the root committee). It is assumed that _at most_ $M$
nodes are adversarial (red dots). The committee tree failure occurs when more
than $1/3$ of nodes in at least _one_ of the committees are Byzantine. The
child committee failure occurs when more than $1/3$ of nodes are Byzantine in
at least _one_ of the committees produced by merging two child committees with
a common parent (ovals with dotted boundaries). The failure in the top three
committees (large circle with dotted boundary) occurs when more than $1/3$ (or
$2/3$) of nodes in these committees are Byzantine. The probability of electing
a Byzantine leader is $M/N$.

##  VIII  Conclusion

In conclusion, we envisage that by combining instantaneous finality and
adaptable scalability the Carnot protocol will emerge as a trailblazing
paradigm in the realm of consensus protocols. The protocol not only achieves
prompt finality but also accommodates organic growth of networks by
effectively mitigating intricate challenges tied to the chain reorganization
and fork vulnerabilities. Our future work includes further increase in fault
tolerance and investigation of eliminating the direct chain prerequisite for a
block commitment. In addition we would like to explore creation of the multi-
leader and multi-overlay Carnot variant which could enhance both performance
and resilience of the protocol. Finally, in future work we will also consider
adding economic (PoS) layer to the Carnot to ensure seamless operation within
some crypto-economic framework.

## Acknowledgement

The authors would like to thank Corey Petty, Daniel Sanchez Quiros, Augustinas
Bacvinka, Giacomo Pasini, Álvaro Castro-Castilla, Daniel Kaiser and Frederico
Teixeira for their invaluable assistance and very enlightening discussions
that greatly enriched this work.

##  Appendix A Details of analysis of failures

###  A-A Model of random partitions

We consider $N$ nodes distributed into $K$ committees in a random and unbiased
way (see Figure 1) for a given committee sizes $\\{N_{1},\ldots,N_{K}\\}$,
where $N_{\mu}=|C_{\mu}|$ is the number of nodes in a committee $C_{\mu}$.
Assuming that the sampling without replacement is used and that $M<N$ nodes
are _Byzantine_ gives us the hypergeometric distribution

$\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)=\frac{\delta_{M;\sum_{\mu=1}^{K}N_{\mu}^{\alpha}}\prod_{\mu=1}^{K}{N_{\mu}\choose
N^{\alpha}_{\mu}}}{{N\choose M}}$ (9)

for the $\\{N_{1}^{\alpha},\ldots,N_{K}^{\alpha}\\}$, where $N_{\mu}^{\alpha}$
is the number of Byzantine nodes in the committee $\mu$. Furthermore, if $M$
is _random_ variable from the binomial distribution

$\mathrm{P}\left(M|N\right)={N\choose M}\,P^{M}\left(1-P\right)^{N-M},$ (10)

where $P\in(0,1)$, then the _average_ of (9) over $M$ is the product of
binomials

$\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K}\right)=\prod_{\mu=1}^{K}\mathrm{P}\left(N^{\alpha}_{\mu}|N_{\mu}\right).$
(11)

We note that in _sharding_ of blockchains the number of Byzantine nodes in a
_single_ committee is usually modeled with the hypergeometric [36, 37, 38] and
binomial [39, 40] probability distributions which are, respectively, the
marginals of the probability distributions (9) and (11). The latter two are
special cases of a more _general_ distribution $\sum_{M\geq
0}\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)\mathrm{P}(M)$.

###  A-B Analysis of committee tree failure

We are interested in the probability of various “failures” that can occur in a
committee tree (see Figure 4). The first failure we consider is the event
$E_{1}(A)=\cup_{\mu=1}^{K}\left\\{N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right\\}$, i.e. more than fraction $A$ of nodes in at least
_one_ of the committees are _Byzantine_. This type of failure concerns
_reliability_ of the whole _structure_ of a committee tree and its probability
is given by

$\delta(E_{1}(A))=\mathrm{P}\left(\cup_{\mu=1}^{K}\left\\{N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right\\}\right),$ (12)

via $\mathrm{P}(E_{1}(A))=1-\mathrm{P}(\neg E_{1}(A))$, is exactly equal to

$\delta(E_{1}(A))=1-\mathrm{P}\left(N_{1}^{\alpha}\leq\lfloor
AN_{1}\rfloor,\ldots,N_{K}^{\alpha}\leq\lfloor AN_{K}\rfloor\right).$ (13)

We note that above was studied in [35] for both the hypergeometric (9) and
binomial (11) distributions. For the latter we obtain

$\delta(E_{1}(A))=1-\prod_{\mu=1}^{K}\left[1-\mathrm{P}(N^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1|N_{\mu})\right],$ (14)

where

$\mathrm{P}(N^{\alpha}\geq\lfloor AN_{\mu}\rfloor+1)=\sum_{N^{\alpha}=\lfloor
AN_{\mu}\rfloor+1}^{N_{\mu}}\mathrm{P}\left(N^{\alpha}|N_{\mu}\right)$ (15)

is the upper tail of the binomial distribution (10), and by the _Theorem_ 3.3
in [35] for $P<A(\mu)<1$, where $A(\mu)=\frac{\lfloor
AN_{\mu}\rfloor+1}{N_{\mu}}$, we have the upper bound

$\displaystyle\delta(E_{1}(A))$ $\displaystyle~{}~{}~{}\leq
1-\prod_{\mu=1}^{K}\left[1-\frac{1}{1-r(\mu)}\frac{\mathrm{e}^{-N_{\mu}\mathrm{D}\left(A(\mu)||P\right)}}{)\sqrt{2\pi
A(\mu)\left(1-A(\mu)\right)N_{\mu}}}\right],$ (16)

where $\mathrm{D}\left(A||P\right)$ with $A,P\in(0,1)$ is the
Kullback$-$Leibler (KL) ‘distance’

$\mathrm{D}\left(A||P\right)=A\log\frac{A}{P}+(1-A)\log\frac{1-A}{1-P}$ (17)

which is $0$ when $A=P$ and is positive semi-definite when $A\neq P$ [41].
Here the term $\frac{1}{1-r(\mu)}$, where
$r(\mu)=\frac{P\left(1-A(\mu)\right)}{A(\mu)\left(1-P\right)}$, is an upper
bound on the sum $\sum_{k=0}^{\left(1-A(\mu)\right)N_{\mu}}r^{k}(\mu)$.

To estimate the probability of failure (12) for the hypergeometric
distribution (9) we will use the Boole’s inequality

$\mathrm{P}\left(\cup_{\mu=1}^{K}\left\\{N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right\\}\right)\leq\sum_{\mu=1}^{K}\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right),$ (18)

also known as the _union bound_ , which gives us

$\delta(E_{1}(A))\leq\sum_{\mu=1}^{K}\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right),$ (19)

where

$\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right)=\sum_{N^{\alpha}_{\mu}=\lfloor
AN_{\mu}\rfloor+1}^{N_{\mu}}\frac{{N_{\mu}\choose
N^{\alpha}_{\mu}}{N-N_{\mu}\choose M-N^{\alpha}_{\mu}}}{{N\choose M}}$ (20)

is the upper tail of the (univariate) hypergeometric distribution, i.e. the
marginal of (9).

$\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor AN_{\mu}\rfloor+1\right)$

$N_{\mu}$ Figure 5: The tail of hypergeometric distribution
$\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor AN_{\mu}\rfloor+1\right)$ as
function of $N_{\mu}$ computed for $N=10^{3}$, $M=N/4$ and $A=1/3$. The upper
bound (21) and exact numerical values (20) are represented, respectively, by
the blue dotted and dashed lines. The red solid line is the Hoeffding bound
$\mathrm{e}^{-N_{\mu}\mathrm{D}\left(A(\mu)||M/N\right)}$, where
$A(\mu)=\frac{\lfloor AN_{\mu}\rfloor+1}{N_{\mu}}$.

The numerical computation of (19) can be very inefficient because of
combinatorial objects in (20). The latter can be estimated by the Hoeffding
bound [42, 43] but this bound is very loose as can be seen in Figure 5. A much
tighter bound (see Figure 5) is given by the

######  Lemma 5.

Suppose that $P+1/N<A$, where $P=M/N$, then

$\displaystyle\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\leq\frac{{N-N_{\mu}\choose M-\left\lfloor
AN_{\mu}\right\rfloor-1}{N_{\mu}\choose\left\lfloor
AN_{\mu}\right\rfloor+1}}{{N\choose M}}\frac{1-r^{N_{\mu}-\left\lfloor
AN_{\mu}\right\rfloor}}{1-r},$ (21)

where $r=\frac{\left[P-\frac{\left\lfloor
AN_{\mu}\right\rfloor+1}{N}\right][1-A(\mu)]}{\left[1-P-\frac{N_{\mu}}{N}+\frac{\left\lfloor
AN_{\mu}\right\rfloor+1}{N}\right]\,A(\mu)}$ and $A(\mu)=\frac{\lfloor
AN_{\mu}\rfloor+1}{N_{\mu}}$.

###### Proof.

See Appendix B. ∎

We note that the RHS in (21) can be further bounded by using [44]

$\displaystyle\sqrt{\frac{1}{8P\left(1-P\right)N}}\mathrm{e}^{NH\left(P\right)}\leq{N\choose
M}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\leq\sqrt{\frac{1}{2\pi
P\left(1-P\right)N}}\mathrm{e}^{NH\left(P\right)},$ (22)

where $H(P)=-P\log(P)-(1-P)\log(1-P)$ is the _entropy_ , in the binomial
coefficients which will reduce numerical complexity of estimating (20).

$\delta(E_{3}(1/3))$

$\delta(E_{1}(1/2))$

$\delta(E_{1}(1/3))$

$\delta(E_{2}(1/3))$

$K$$K$ Figure 6: The probability of failure, $\delta$, as a function of the
number of committees, $K$, computed for the binomial (red solid line) and
hypergeometric (blue dotted line) models of random partitions. The number of
nodes is $N=10^{4}$, where $N=nK+r$, and the number of Byzantine nodes is
_exactly_ (on _average_) $M=N/4$ in hypergeometric (binomial) model. The $n$
and $n+1$ nodes are assigned, respectively, to the $K-r$ and $r$ committees.
Top left: The probability of failure $\delta(E_{1}(1/3))$ estimated by the
upper bounds (16) and (19). The latter uses (21). Top right: The probability
of failure $\delta(E_{2}(1/3))$ estimated by the upper bounds (28) and (30).
Bottom left: The probability of failure $\delta(E_{3}(1/3))$ estimated by the
upper bounds (33) and (35). On the same range the probability of failure
$\delta(E_{3}(2/3))$ is at most $7.31\times 10^{-53}$. Bottom right: The
probability of failure $\delta(E_{1}(1/2))$ estimated by the upper bounds (16)
and (19). The latter uses (21).

The union bound (19) suggest that for $K<\infty$ the probability of failure
$\delta(E_{1}(A))\rightarrow 0$ if we assume that $N_{\mu}/N>0$ for all $\mu$
as $N\rightarrow\infty$. This follows from
$\delta(E_{1}(A))\leq\sum_{\mu=1}^{K}\mathrm{e}^{-N_{\mu}\mathrm{D}\left(A(\mu)||M/N\right)}$
which is obtained by applying the Hoeffding bound [42, 43] to the tail (20).
However, outside of this asymptotic regime one can always find the number of
committees $K$ and committee sizes $N_{\mu}$ for such that the RHS of (19)
exceeds _unity_. The latter can be seen in the Figure 6 where we plot the
bounds (16) and (19) together. The upper bound (16), which assumes the
binomial distribution (11), is bounded from above by unity. Also we expect the
latter, which assumes binomial distribution (11), to be an upper bound on the
$\delta(E_{1}(A))$ when the hypergeometric distribution (9) is assumed [35].

$n$$N$ Figure 7: The committee size, $n$, as a function of the number of
nodes, $N$, plotted for the probability of failure
$\delta(E_{1}(1/3))\in\\{10^{-3},10^{-4},10^{-5},10^{-6}\\}$ (bottom to top)
and the fraction of Byzantine nodes $P=1/4$. The red solid and blue dotted
lines were computed from, respectively, the binomial (16) and hypergeometric
(19) upper bounds. The latter uses the bound (21).

For the number of nodes $N=nK$ we can use the upper bounds (16) and (19) to
find the committee size $n$ for the given failure probability
$\delta(E_{1}(A))$ and fraction of Byzantine nodes $P$. We find that the
committee size $n$ is growing slowly with the number of nodes $N$ and failure
probability $\delta(E_{1}(A))$ (see Figure 7). We note that the $n$ computed
with (16) is an upper bound for the $n$ computed with (19), which reproduces
results of the previous study [35], but the difference between the two is
vanishing as $N$ increases (see Figure 7).

Finally, the upper bounds (16) and (19) can be used to find the _maximum_
number of committees $K$ for a given $N$, $\delta(E_{1}(A))$ and $P$. The
details of an algorithm that implements the latter are provided in the
Appendix C.

###  A-C Analysis of child committees failure

The next type of failure we consider is when in at least one of the committees
produced by merging two child committees with a common parent (see Figure 4)
the fraction of Byzantine nodes is greater than $A$. The latter is the event
$E_{2}(A)=\cup_{\mu=2}^{\tilde{K}}\left\\{S_{\mu}^{\alpha}\geq\lfloor
AS_{\mu}\rfloor+1\right\\}$, where $S_{1}^{\alpha}=N_{1}^{\alpha}$,
$S_{2}^{\alpha}=N_{2}^{\alpha}+N_{3}^{\alpha}$,
$S_{3}^{\alpha}=N_{4}^{\alpha}+N_{5}^{\alpha}$ etc. with
$\tilde{K}=\frac{K+1}{2}$, and hence to compute the failure probability

$\delta(E_{2}(A))=\mathrm{P}\left(\cup_{\mu=2}^{\tilde{K}}\left\\{S_{\mu}^{\alpha}\geq\lfloor
AS_{\mu}\rfloor+1\right\\}\right)$ (23)

we need to know the distribution of
$\\{S_{2}^{\alpha},\ldots,S_{\tilde{K}}^{\alpha}\\}$. The latter for the
hypergeometric distribution (9) is given

$\mathrm{P}\left(S_{1}^{\alpha},\ldots,S_{\tilde{K}}^{\alpha}|S_{1},\ldots,S_{\tilde{K}};M\right)=\frac{\delta_{M;\sum_{\mu=1}^{\tilde{K}}S_{\mu}^{\alpha}}\prod_{\mu=1}^{\tilde{K}}{S_{\mu}\choose
S^{\alpha}_{\mu}}}{{N\choose M}}$ (24)

and for the binomial distribution (11) is given by

$\mathrm{P}\left(S_{1}^{\alpha},\ldots,S_{\tilde{K}}^{\alpha}|S_{1},\ldots,S_{\tilde{K}}\right)=\prod_{\mu=1}^{\tilde{K}}\mathrm{P}\left(S^{\alpha}_{\mu}|S_{\mu}\right).$
(25)

The probability of failure (23) is also equal to

$\delta(E_{2}(A))=1-\mathrm{P}\left(S_{2}^{\alpha}\leq\lfloor
AS_{2}\rfloor,\ldots,S_{\tilde{K}}^{\alpha}\leq\lfloor
AS_{\tilde{K}}\rfloor\right)$ (26)

which gives us

$\delta(E_{2}(A))=1-\prod_{\mu=2}^{\tilde{K}}\sum_{S^{\alpha}_{\mu}=0}^{\lfloor
AS_{\mu}\rfloor}\mathrm{P}\left(S^{\alpha}_{\mu}|S_{\mu}\right)$ (27)

for the binomial distribution (25) and hence by the _Theorem_ 3.3 in [35] for
$P<A(\mu)<1$, where $A(\mu)=\frac{\lfloor AS_{\mu}\rfloor+1}{S_{\mu}}$, we
have the upper bound

$\displaystyle\delta(E_{2}(A))$ $\displaystyle~{}~{}\leq
1-\prod_{\mu=2}^{\tilde{K}}\left[1-\frac{1}{1-r(\mu)}\frac{\mathrm{e}^{-S_{\mu}\mathrm{D}\left(A(\mu)||P\right)}}{)\sqrt{2\pi
A(\mu)\left(1-A(\mu)\right)S_{\mu}}}\right],$ (28)

where $r(\mu)=\frac{P\left(1-A(\mu)\right)}{A(\mu)\left(1-P\right)}$. For the
hypergeometric distribution (24) we can use the Boole’s inequality

$\mathrm{P}\left(\cup_{\mu=2}^{\tilde{K}}\left\\{S_{\mu}^{\alpha}\geq\lfloor
AS_{\mu}\rfloor+1\right\\}\right)\leq\sum_{\mu=2}^{\tilde{K}}\mathrm{P}\left(S_{\mu}^{\alpha}\geq\lfloor
AS_{\mu}\rfloor+1\right)$ (29)

to obtain the upper bound

$\delta(E_{2}(A))\leq\sum_{\mu=2}^{\tilde{K}}\sum_{S_{\mu}^{\alpha}=\left\lfloor
AS_{\mu}\right\rfloor+1}^{S_{\mu}}\frac{{N-S_{\mu}\choose
M-S_{\mu}^{\alpha}}{S_{\mu}\choose S_{\mu}^{\alpha}}}{{N\choose M}}.$ (30)

We note that above bound can be simplified by using the inequality (21) to
bound tails of hypergeometric distributions. The bounds (28) and (30) are
plotted in the Figure 6.

###  A-D Analysis of failures in top three committees

Finally, the last type of failure we consider is when the fraction of
Byzantine nodes in the top three committees is greater than $B$ (see Figure
4). The latter is a special case of the event
$E_{k}(B)=\mathds{1}\left[\sum_{\nu=1}^{k}N_{\nu}^{\alpha}\geq\left\lfloor
B\sum_{\nu=1}^{k}N_{\nu}\right\rfloor+1\right]$, where $k\geq 3$, that the
total number of Byzantine nodes in the _top_ $k$ committees exceeds the
fraction $B$ of the total number of nodes in these committees. Here, we
assumed, without loss of generality, that nodes of the top $k$ committees are
labeled by $[k]$.

Let us define the probability of failure

$\delta(E_{k}(B))=\mathrm{P}\left(\sum_{\nu=1}^{k}N_{\nu}^{\alpha}\geq\left\lfloor
B\sum_{\nu=1}^{k}N_{\nu}\right\rfloor+1\right)$ (31)

and consider above for the hypergeometric (9) and binomial (11) probability
distributions. For the latter we obtain the probability

$\delta(E_{k}(B))=\sum_{S_{k}^{\alpha}=\left\lfloor
BS_{k}\right\rfloor+1}^{S_{k}}{S_{k}\choose
S_{k}^{\alpha}}\,P^{S^{\alpha}_{\mu}}\left[1-P\right]^{S_{k}-S_{k}^{\alpha}},$
(32)

where we have defined the sums
$S_{k}^{\alpha}=\sum_{\nu=1}^{k}N_{\nu}^{\alpha}$ and
$S_{k}=\sum_{\nu=1}^{k}N_{\nu}$. We note that above results is a direct
consequence of that the probability (11) describes _independent_ (binomial)
random variables (r.v.) and hence the sum $S_{k}^{\alpha}$ is also r.v. from a
binomial distribution. Furthermore, for the probability (32) we have the
following bound

$\delta(E_{k}(B))\leq\frac{1}{1-r}\frac{\mathrm{e}^{-S_{k}\mathrm{D}\left(B(k)||P\right)}}{\sqrt{2\pi
B(k)\left(1-B(k)\right)S_{k}}},$ (33)

where $B(k)=\frac{\left\lfloor BS_{k}\right\rfloor+1}{S_{k}}$ and
$r=\frac{P\left(1-B(k)\right)}{B(k)\left(1-P\right)}$, by the _Theorem_ 1 in
[45].

For the hypergeometric probability distribution (9) with a bit of work we
obtain

$\delta(E_{k}(B))=\sum_{S_{k}^{\alpha}=\left\lfloor
BS_{k}\right\rfloor+1}^{S_{k}}\frac{{N-S_{k}\choose
M-S_{k}^{\alpha}}{S_{k}\choose S_{k}^{\alpha}}}{{N\choose M}},$ (34)

i.e. the tail of hypergeometric distribution, which estimated as follows

$\delta(E_{k}(B))\leq\frac{{N-S_{k}\choose M-\left\lfloor
BS_{k}\right\rfloor-1}{S_{k}\choose\left\lfloor
BS_{k}\right\rfloor+1}}{{N\choose M}}\frac{1-r^{S_{k}-\left\lfloor
BS_{k}\right\rfloor}}{1-r},$ (35)

where $r=\frac{\left[P-\frac{\left\lfloor
BS_{k}\right\rfloor+1}{N}\right][1-B(k)]}{\left[1-P-\frac{S_{k}}{N}+\frac{\left\lfloor
BS_{k}\right\rfloor+1}{N}\right]\,B(k)}$, by the _Lemma_ 5. For $k=3$ the
bounds in (33) and (35) are plotted in the Figure 6.

##  Appendix B Analysis of failures: Proof of Lemma 5

###### Proof.

Let us consider the probability (20) as follows

$\displaystyle\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right)=\sum_{N_{\mu}^{\alpha}=\left\lfloor
A\,N_{\mu}\right\rfloor+1}^{N_{\mu}}\mathrm{P}\left(N_{\mu}^{\alpha}|N_{\mu}\right)$
$\displaystyle=\mathrm{P}\left(x_{0}|N_{\mu}\right)\sum_{N_{\mu}^{\alpha}=\left\lfloor
A\,N_{\mu}\right\rfloor+1}^{N_{\mu}}\frac{\mathrm{P}\left(N_{\mu}^{\alpha}|N_{\mu}\right)}{\mathrm{P}\left(x_{0}|N_{\mu}\right)}$
$\displaystyle=\mathrm{P}\left(x_{0}|N_{\mu}\right)\sum_{\ell=0}^{N_{\mu}-\left\lfloor
A\,N_{\mu}\right\rfloor-1}\\!\\!\frac{\mathrm{P}\left(\left\lfloor
A\,N_{\mu}\right\rfloor+1+\ell|N_{\mu}\right)}{\mathrm{P}\left(x_{0}|N_{\mu}\right)},$
(36)

where in above we assumed that the $\sup_{x}\mathrm{P}\left(x|N_{\mu}\right)$
is _unique_ on the interval $\left[\left\lfloor
A\,N_{\mu}\right\rfloor+1,N_{\mu}\right]$ and defined

$\mathrm{P}\left(x_{0}|N_{\mu}\right)=\sup_{x\in\left[\left\lfloor
A\,N_{\mu}\right\rfloor+1,N_{\mu}\right]}\mathrm{P}\left(x|N_{\mu}\right).$
(37)

Now the mode of the probability distribution
$\mathrm{P}\left(N_{\mu}^{\alpha}|N_{\mu}\right)$, for non-integer
$\frac{(N_{\mu}+1)(M+1)}{N+2}$, is located at
$\left\lfloor\frac{(N_{\mu}+1)(M+1)}{N+2}\right\rfloor$. We note that
$\left\lfloor\frac{(N_{\mu}+1)(M+1)}{N+2}\right\rfloor\leq\lfloor(N_{\mu}+1)(P+1/N)\rfloor\leq\lfloor(P+1/N)N_{\mu}\rfloor+1$
and hence for $P+1/N<B$ we have that
$\mathrm{P}\left(x_{0}|N_{\mu}\right)=\mathrm{P}\left(\left\lfloor
A\,N_{\mu}\right\rfloor+1|N_{\mu}\right)$. Thus we obtain

$\displaystyle\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right)=\mathrm{P}\left(\left\lfloor
A\,N_{\mu}\right\rfloor+1|N_{\mu}\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\sum_{\ell=0}^{N_{\mu}-\left\lfloor
A\,N_{\mu}\right\rfloor-1}\frac{\mathrm{P}\left(\left\lfloor
A\,N_{\mu}\right\rfloor+1+\ell|N_{\mu}\right)}{\mathrm{P}\left(\left\lfloor
A\,N_{\mu}\right\rfloor+1|N_{\mu}\right)}.$ (38)

Let us for $\ell>0$ and $n=\left\lfloor A\,N_{\mu}\right\rfloor+1$ consider
the ratio

$\frac{\mathrm{P}\left(n+\ell|N_{\mu}\right)}{\mathrm{P}\left(n|N_{\mu}\right)}=\frac{{N-N_{\mu}\choose
M-n-\ell}{N_{\mu}\choose n+\ell}}{{N-N_{\mu}\choose M-n}{N_{\mu}\choose n}}.$
(39)

We note that

$\frac{{N\choose n}}{{N\choose
n+\ell}}=\frac{(N-n-\ell)!(n+\ell)!}{(N-n)!n!}\geq\frac{n^{\ell}}{(N-n)^{\ell}}$
(40)

and

$\frac{{N\choose n}}{{N\choose
n-\ell}}=\frac{(N-n+\ell)!(n-\ell)!}{(N-n)!n!}\geq\frac{(N-n)^{\ell}}{n^{\ell}},$
(41)

hence using above we obtain the following inequality

$\displaystyle\frac{\mathrm{P}\left(n+\ell|N_{\mu}\right)}{\mathrm{P}\left(n|N_{\mu}\right)}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\leq\left\\{\frac{(M-n)(N_{\mu}-n)}{(N-N_{\mu}-M+n)n}\right\\}^{\ell}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}=\left\\{\frac{\left[P-\frac{\left\lfloor
A\,N_{\mu}\right\rfloor+1}{N}\right][1-A(\mu)]}{\left[1-P-\frac{N_{\mu}}{N}+\frac{\left\lfloor
A\,N_{\mu}\right\rfloor+1}{N}\right]\,A(\mu)}\right\\}^{\ell},$ (42)

where we defined $A(\mu)=\frac{\left\lfloor
A\,N_{\mu}\right\rfloor+1}{N_{\mu}}$ and $P=M/N$. Finally, using above in (38)
we obtain

$\displaystyle\mathrm{P}\left(N_{\mu}^{\alpha}\geq\lfloor
AN_{\mu}\rfloor+1\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}\leq\mathrm{P}\left(\left\lfloor
A\,N_{\mu}\right\rfloor+1|N_{\mu}\right)\sum_{\ell=0}^{N_{\mu}-\left\lfloor
A\,N_{\mu}\right\rfloor-1}r^{\ell}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}=\mathrm{P}\left(\left\lfloor
A\,N_{\mu}\right\rfloor+1|N_{\mu}\right)\frac{1-r^{N_{\mu}-\left\lfloor
A\,N_{\mu}\right\rfloor}}{1-r},$ (43)

where we defined

$r=\frac{\left[P-\frac{\left\lfloor
A\,N_{\mu}\right\rfloor+1}{N}\right][1-A(\mu)]}{\left[1-P-\frac{N_{\mu}}{N}+\frac{\left\lfloor
A\,N_{\mu}\right\rfloor+1}{N}\right]\,A(\mu)}.$ (44)

∎

##  Appendix C Analysis of failures: description of the algorithm

Here we give details of an algorithm which given the number of nodes $N$,
assumed fraction of adversarial nodes parameter $P$, a fraction of committee
parameter $A$ and the probability of failure $\delta$ would give us the
_maximum_ number of committees $K$ and committee sizes. The algorithm computes
the RHS of (14) for the $N=nK+r$ nodes where the $n$ and $n+1$ nodes are
assigned, respectively, to the $K-r$ and $r$ committees. Initially, all $N$
nodes are in one committee, and in subsequent iterations, the number of
committees $K$ is increased by two until the probability (14) is equal to or
less than $\delta$. We note that instead of (14) the upper bound (16) can be
used. The latter has lower numerical complexity but leads to slightly larger
committee sizes. Furthermore, if we assume the hypergeometric distribution (9)
then the upper bound (19) can be used instead of (16) in the algorithm. The
pseudocode of the algorithm is provided in the Algorithm 7.

Algorithm 7 The algorithm to compute minimal sizes of committees resilient to
$\delta$ failure rate.

1:$N$, $\delta$, $A$, $P$

2:$K$, $n$, $r$, $\mathrm{Prob}$

3:$K\leftarrow 1$

4:$n\leftarrow N$

5:$r\leftarrow 0$

6:$m\leftarrow 0$

7:$\mathrm{Prob}\leftarrow 0$

8:repeat

9: //Save values of $K$, $n$, $r$ and $\mathrm{Prob}$.

10: $K_{-1}\leftarrow K$

11: $n_{-1}\leftarrow n$

12: $r_{-1}\leftarrow r$

13: $Prob_{-1}\leftarrow Prob$

14: //Compute next (odd) $K$.

15: $m\leftarrow m+1$

16: $K\leftarrow 2m+1$

17: //Compute remainder, $r$, and quotient, $n$, when $N$ is divided by $K$.

18: $r\leftarrow rem(N,K)$

19: $n\leftarrow quot(N,K)$

20: if $r>0$ then

21: //Compute CDF of the Binomial(n,P) and Binomial(n+1,P).

22: $\mathrm{Prob}_{0}\leftarrow\mathrm{P}(X\leq\lfloor An\rfloor\,|\,n,P)$

23: $\mathrm{Prob}_{1}\leftarrow\mathrm{P}(X\leq\lfloor
A(n+1)\rfloor\,|\,n+1,P)$

24: //Compute probability of failure.

25: $\mathrm{P}\leftarrow 1-\mathrm{Prob}_{0}^{K-r}\mathrm{Prob}_{1}^{r}$

26: else

27: $\mathrm{Prob}_{0}\leftarrow\mathrm{P}(X\leq\lfloor An\rfloor\,|\,n,P)$

28: $Prob\leftarrow 1-\mathrm{Prob}_{0}^{K}$

29: end if

30:until $\mathrm{Prob}>\delta$

31:$K\leftarrow K_{-1}$

32:$n\leftarrow n_{-1}$

33:$r\leftarrow r_{-1}$

34:$\mathrm{Prob}\leftarrow\mathrm{Prob}_{-1}$

##  Appendix D Analysis of failures: properties of $\delta(E_{k}(A))$

In this section we consider properties of the failure probability
$\delta(E_{k}(A))$ which hold for _any_ probability distribution
$\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K}\right)$.
First, we show that the probability $\delta(E_{k}(A))$, which is defined for
$k=1$ in (12), for $k=2$ in (23) and for $k\geq 3$ in (31), is a monotonic
non-increasing function of $A$.

######  Proposition 1.

For the $A,B\in[0,1]$ such that $A\leq B$ and $k\geq 1$ the probability of
failure $\delta(E_{k}(B)\leq\delta(E_{k}(A)$.

###### Proof.

Let us consider the $k=1$ case as follows

$\displaystyle 1-\delta(E_{1}(A))$
$\displaystyle~{}~{}~{}=\mathrm{P}\left(N_{1}^{\alpha}\leq\lfloor
AN_{1}\rfloor,\ldots,N_{K}^{\alpha}\leq\lfloor AN_{K}\rfloor\right)$
$\displaystyle~{}~{}~{}=\sum_{N_{1}^{\alpha}=0}^{\lfloor
AN_{1}\rfloor}\cdots\sum_{N_{K}^{\alpha}=0}^{\lfloor
AN_{K}\rfloor}\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)$
$\displaystyle~{}~{}~{}~{}~{}\leq\sum_{N_{1}^{\alpha}=0}^{\lfloor
BN_{1}\rfloor}\cdots\sum_{N_{K}^{\alpha}=0}^{\lfloor
BN_{K}\rfloor}\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}=1-\delta(E_{1}(B))$ (45)

and hence $\delta(E_{1}(B))\leq\delta(E_{1}(A))$. We note that the same
argument can be used to show that $\delta(E_{k}(B))\leq\delta(E_{k}(A))$ for
$k\geq 2$. ∎

Second, for a fixed $A$ we establish how the $\delta(E_{k}(A))$ of different
$k$ are related to which other in the following two propositions.

######  Proposition 2.

For $A\in[0,1]$ the probability of failure
$\delta(E_{2}(A)\leq\delta(E_{1}(A)$.

###### Proof.

First, we consider

$\displaystyle 1-\delta(E_{2}(A))$
$\displaystyle~{}~{}~{}~{}~{}=\mathrm{P}\left(S_{2}^{\alpha}\leq\lfloor
AS_{2}\rfloor,\ldots,S_{\tilde{K}}^{\alpha}\leq\lfloor
AS_{\tilde{K}}\rfloor\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\geq\mathrm{P}\left(S_{1}^{\alpha}\leq\lfloor
AS_{1}\rfloor,\ldots,S_{\tilde{K}}^{\alpha}\leq\lfloor
AS_{\tilde{K}}\rfloor\right)$
$\displaystyle~{}~{}~{}~{}~{}=\sum_{N_{1}^{\alpha}}\cdots\sum_{N_{K}^{\alpha}}\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)$
$\displaystyle~{}~{}~{}~{}~{}\times\mathds{1}\left[N^{\alpha}_{1}\leq\lfloor
AN_{1}\rfloor\right]$
$\displaystyle~{}~{}~{}~{}~{}\times\prod_{\mu=2}^{\tilde{K}}\mathds{1}\left[N^{\alpha}_{2\mu}+N^{\alpha}_{2\mu+1}\leq\lfloor
A(N_{2\mu}+N_{2\mu+1})\rfloor\right],$ (46)

where in above we used the definition (26). Second, we show that

$\displaystyle\mathds{1}\left[N^{\alpha}_{2\mu}+N^{\alpha}_{2\mu+1}\leq\lfloor
A(N_{2\mu}+N_{2\mu+1})\rfloor\right]$
$\displaystyle~{}~{}~{}~{}~{}\geq\mathds{1}\left[N^{\alpha}_{2\mu}\leq\lfloor
AN_{2\mu}\rfloor\right]\mathds{1}\left[N^{\alpha}_{2\mu+1}\leq\lfloor
AN_{2\mu+1}\rfloor\right]$ (47)

Here we only need to prove that when the LHS in above is $0$ then the RHS can
not be $1$. Let us assume that the latter is not true then
$N^{\alpha}_{2\mu}+N^{\alpha}_{2\mu+1}>\lfloor A(N_{2\mu}+N_{2\mu+1})\rfloor$,
$N^{\alpha}_{2\mu}\leq\lfloor AN_{2\mu}\rfloor$ and
$N^{\alpha}_{2\mu+1}\leq\lfloor AN_{2\mu+1}\rfloor$. However, the last two
inequalities imply that $N^{\alpha}_{2\mu}+N^{\alpha}_{2\mu+1}\leq\lfloor
AN_{2\mu}\rfloor+\lfloor AN_{2\mu+1}\rfloor$, but $\lfloor
AN_{2\mu}\rfloor+\lfloor AN_{2\mu+1}\rfloor\leq\lfloor
A(N_{2\mu}+N_{2\mu+1})\rfloor$ and hence

$N^{\alpha}_{2\mu}+N^{\alpha}_{2\mu+1}\leq\lfloor
A(N_{2\mu}+N_{2\mu+1})\rfloor<N^{\alpha}_{2\mu}+N^{\alpha}_{2\mu+1}$

which is not possible. Thus the inequality (47) is true. Now using the latter
in (46) gives us

$\displaystyle 1-\delta(E_{2}(A))$
$\displaystyle~{}~{}~{}~{}~{}\geq\sum_{N_{1}^{\alpha}}\cdots\sum_{N_{K}^{\alpha}}\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\times\mathds{1}\left[N^{\alpha}_{1}\leq\lfloor
AN_{1}\rfloor\right]\prod_{\mu=2}^{\tilde{K}}\mathds{1}\left[N^{\alpha}_{2\mu}\leq\lfloor
AN_{2\mu}\rfloor\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\times\mathds{1}\left[N^{\alpha}_{2\mu+1}\leq\lfloor
AN_{2\mu+1}\rfloor\right]$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}=\mathrm{P}\left(N_{1}^{\alpha}\leq\lfloor
AN_{1}\rfloor,\ldots,N_{K}^{\alpha}\leq\lfloor AN_{K}\rfloor\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}=1-\delta(E_{1}(A))$ (48)

and hence $\delta(E_{2}(A))\leq\delta(E_{1}(A))$. ∎

######  Proposition 3.

For $A\in[0,1]$ and $k\geq 3$ the probability of failure
$\delta(E_{k}(A)\leq\delta(E_{1}(A)$.

###### Proof.

First, from the definition (31) follows the equality

$\displaystyle 1-\delta(E_{k}(A))$ $\displaystyle=$
$\displaystyle\mathrm{P}\left(\sum_{\nu=1}^{k}N_{\nu}^{\alpha}\leq\lfloor
A\sum_{\nu=1}^{k}N_{\nu}\rfloor\right)$ (49) $\displaystyle=$
$\displaystyle\sum_{N_{1}^{\alpha}}\cdots\sum_{N_{K}^{\alpha}}\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)$
$\displaystyle~{}~{}~{}~{}~{}\times\mathds{1}\left[\sum_{\nu=1}^{k}N_{\nu}^{\alpha}\leq\lfloor
A\sum_{\nu=1}^{k}N_{\nu}\rfloor\right].$

Second, in order to show that

$\displaystyle\mathds{1}\left[\sum_{\nu=1}^{k}N_{\nu}^{\alpha}\leq\lfloor
A\sum_{\nu=1}^{k}N_{\nu}\rfloor\right]$ $\displaystyle\geq$
$\displaystyle\prod_{\nu=1}^{k}\mathds{1}\left[N^{\alpha}_{\nu}\leq\lfloor
AN_{\nu}\rfloor\right]$ (50)

we assume that $\sum_{\nu=1}^{k}N_{\nu}^{\alpha}>\lfloor
A\sum_{\nu=1}^{k}N_{\nu}\rfloor$ and $N^{\alpha}_{\nu}\leq\lfloor
AN_{\nu}\rfloor$ for all $\nu\in[k]$. This implies that
$\sum_{\nu=1}^{k}N^{\alpha}_{\nu}\leq\sum_{\nu=1}^{k}\lfloor AN_{\nu}\rfloor$,
but $\sum_{\nu=1}^{k}\lfloor AN_{\nu}\rfloor\leq\lfloor
A\sum_{\nu=1}^{k}N_{\nu}\rfloor$ and

$\sum_{\nu=1}^{k}N^{\alpha}_{\nu}\leq\lfloor
A\sum_{\nu=1}^{k}N_{\nu}\rfloor<\sum_{\nu=1}^{k}N_{\nu}^{\alpha}$

which can not be true. Hence (50) is correct and using this inequality in (49)
gives us

$\displaystyle 1-\delta(E_{k}(A))$ $\displaystyle\geq$
$\displaystyle\sum_{N_{1}^{\alpha}}\cdots\sum_{N_{K}^{\alpha}}\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)$
(51)
$\displaystyle~{}~{}~{}~{}~{}\times\prod_{\nu=1}^{k}\mathds{1}\left[N^{\alpha}_{\nu}\leq\lfloor
AN_{\nu}\rfloor\right]$
$\displaystyle\geq\sum_{N_{1}^{\alpha}}\cdots\sum_{N_{K}^{\alpha}}\mathrm{P}\left(N_{1}^{\alpha},\ldots,N_{K}^{\alpha}|N_{1},\ldots,N_{K};M\right)$
$\displaystyle~{}~{}~{}~{}~{}\times\prod_{\mu=1}^{K}\mathds{1}\left[N^{\alpha}_{\mu}\leq\lfloor
AN_{\mu}\rfloor\right]$ $\displaystyle~{}~{}~{}=1-\delta(E_{1}(A))$

from which follows $\delta(E_{k}(A)\leq\delta(E_{1}(A)$. ∎

## References

  * [1] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham, “Hotstuff: Bft consensus with linearity and responsiveness,” in _Proceedings of the 2019 ACM PODC_ , ser. PODC ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 347–356.
  * [2] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling Byzantine agreements for cryptocurrencies,” in _Proceedings of the 26th Symposium on Operating Systems Principles_ , ser. SOSP ’17. New York, NY, USA: ACM, 2017, pp. 51–68.
  * [3] A. Hentschel, Y. Hassanzadeh-Nazarabadi, R. M. Seraj, D. Shirley, and L. Lafrance, “Flow: Separating consensus and compute - block formation and execution,” _ArXiv_ , vol. abs/2002.07403, 2020.
  * [4] M. Baudet, A. Ching, A. Chursin, G. Danezis, F. Garillot, Z. Li, D. Malkhi, O. Naor, D. Perelman, and A. Sonnino, “State machine replication in the libra blockchain,” 2019.
  * [5] V. Buterin and V. Griffith, “Casper the friendly finality gadget,” _arXiv preprint arXiv:1710.09437_ , 2017.
  * [6] Ethereum. [Online]. Available: https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md
  * [7] ——. [Online]. Available: https://ethereum.org/en/upgrades/merge/
  * [8] L. Lamport, R. Shostak, and M. Pease, “The Byzantine generals problem,” _ACM Trans. Program. Lang. Syst._ , vol. 4, no. 3, pp. 382–401, Jul. 1982\.
  * [9] C. Dwork, N. Lynch, and L. Stockmeyer, “Consensus in the presence of partial synchrony,” _J. ACM_ , vol. 35, no. 2, pp. 288–323, Apr. 1988.
  * [10] M. M. Jalalzai, J. Niu, C. Feng, and F. Gai, “Fast-hotstuff: A fast and resilient hotstuff protocol,” 2020. [Online]. Available: https://arxiv.org/abs/2010.11454
  * [11] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham, “Hotstuff: Bft consensus in the lens of blockchain,” _arXiv preprint arXiv:1803.05069_ , 2018.
  * [12] M. Castro and B. Liskov, “Practical Byzantine fault tolerance,” in _Proceedings of the Third Symposium on Operating Systems Design and Implementation_ , ser. OSDI ’99. Berkeley, CA, USA: USENIX Association, 1999, pp. 173–186.
  * [13] G. Golan-Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. K. Reiter, D. Seredinschi, O. Tamir, and A. Tomescu, “SBFT: a scalable decentralized trust infrastructure for blockchains,” _CoRR_ , vol. abs/1804.01626, 2018\.
  * [14] V. Buterin, D. Hernandez, T. Kamphefner, K. Pham, Z. Qiao, D. Ryan, J. Sin, Y. Wang, and Y. X. Zhang, “Combining ghost and casper,” 2020. [Online]. Available: https://arxiv.org/abs/2003.03052
  * [15] M. N. Georgios Konstantopoulos, “Time, slots, and the ordering of events in ethereum proof-of-stake,” 2023. [Online]. Available: https://www.paradigm.xyz/2023/04/mev-boost-ethereum-consensus
  * [16] J. Neu, E. N. Tas, and D. Tse, “Two more attacks on proof-of-stake ghost/ethereum,” in _Proceedings of the 2022 ACM Workshop on Developments in Consensus_ , ser. ConsensusDay ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 43–52. [Online]. Available: https://doi.org/10.1145/3560829.3563560
  * [17] E. Team. Paths toward single-slot finality. [Online]. Available: https://notes.ethereum.org/@vbuterin/single_slot_finality
  * [18] M. Jalalzai, C. Feng, C. Busch, G. R. III, and J. Niu, “The hermes bft for blockchains,” _IEEE Transactions on Dependable and Secure Computing_ , no. 01, pp. 1–1, sep 5555.
  * [19] R. Pass and E. Shi, “Thunderella: Blockchains with optimistic instant confirmation,” in _Advances in Cryptology – EUROCRYPT 2018_ , J. B. Nielsen and V. Rijmen, Eds. Cham: Springer International Publishing, 2018, pp. 3–33.
  * [20] M. M. Jalalzai, J. Niu, C. Feng, and F. Gai, “Fast-hotstuff: A fast and robust bft protocol for blockchains,” _IEEE Transactions on Dependable and Secure Computing_ , no. 01, pp. 1–17, aug 5555.
  * [21] N. Giridharan, H. Howard, I. Abraham, N. Crooks, and A. Tomescu, “No-commit proofs: Defeating livelock in bft,” Cryptology ePrint Archive, Paper 2021/1308, 2021, https://eprint.iacr.org/2021/1308. [Online]. Available: https://eprint.iacr.org/2021/1308
  * [22] M. Rambaud, A. Tonkikh, and M. Abspoel, “Linear view change in optimistically fast bft,” in _Proceedings of the 2022 ACM Workshop on Developments in Consensus_ , ser. ConsensusDay ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 67–78. [Online]. Available: https://doi.org/10.1145/3560829.3563562
  * [23] M. M. Jalalzai, C. Busch, and G. G. Richard, “Proteus: A scalable bft consensus protocol for blockchains,” in _2019 IEEE International Conference on Blockchain (Blockchain)_ , 2019, pp. 308–313.
  * [24] M. M. Jalalzai and C. Busch, “Window based BFT blockchain consensus,” in _iThings, IEEE GreenCom, IEEE (CPSCom) and IEEE SSmartData 2018_ , July 2018, pp. 971–979.
  * [25] A. Bessani, J. Sousa, and E. E. P. Alchieri, “State machine replication for the masses with bft-smart,” in _2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks_ , 2014, pp. 355–362.
  * [26] A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti, “Making byzantine fault tolerant systems tolerate byzantine faults,” in _Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation_ , ser. NSDI’09. USA: USENIX Association, 2009, p. 153–168.
  * [27] Y. Amir, B. Coan, J. Kirsch, and J. Lane, “Byzantine replication under attack,” in _2008 IEEE International Conference on Dependable Systems and Networks With FTCS and DCC (DSN)_ , vol. 00, June 2008, pp. 197–206. [Online]. Available: doi.ieeecomputersociety.org/10.1109/DSN.2008.4630088
  * [28] R. Kotla, A. Clement, E. Wong, L. Alvisi, and M. Dahlin, “Zyzzyva: Speculative Byzantine fault tolerance,” _Commun. ACM_ , vol. 51, no. 11, pp. 86–95, Nov. 2008.
  * [29] E. Buchman, “Tendermint: Byzantine fault tolerance in the age of blockchains,” Jun 2016.
  * [30] M. Rambaud, A. Tonkikh, and M. Abspoel, “Linear view change in optimistically fast bft,” in _Proceedings of the 2022 ACM Workshop on Developments in Consensus_ , ser. ConsensusDay ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 67–78. [Online]. Available: https://doi.org/10.1145/3560829.3563562
  * [31] Z. Li, A. Sonnino, and P. Jovanovic, “Performance of eddsa and bls signatures in committee-based consensus,” _arXiv preprint arXiv:2302.00418_ , 2023.
  * [32] kaiserd. (2022) Waku v2 ambient peer discovery. [Online]. Available: https://vac.dev/wakuv2-apd
  * [33] O. Thorén, S. Taheri-Boshrooyeh, and H. Cornelius, “Waku: A family of modular p2p protocols for secure and censorship resistant communication,” in _2022 IEEE 42nd International Conference on Distributed Computing Systems Workshops (ICDCSW)_ , 2022, pp. 86–87.
  * [34] D. E. Knuth, _The art of computer programming_. Pearson Education, 1997, vol. 3.
  * [35] A. Mozeika, M. M. Jalalzai, and M. P. Pawlowski, “How to generate a fault-resilient network at a lower cost,” _arXiv preprint arXiv:2303.14276_ , 2023.
  * [36] M. Zamani, M. Movahedi, and M. Raykova, “Rapidchain: Scaling blockchain via full sharding,” in _Proceedings of the 2018 ACM SIGSAC conference on computer and communications security_ , 2018, pp. 931–948.
  * [37] H. Dang, T. T. A. Dinh, D. Loghin, E.-C. Chang, Q. Lin, and B. C. Ooi, “Towards scaling blockchain systems via sharding,” in _Proceedings of the 2019 international conference on management of data_. New York: Association for Computing Machinery, 2019, pp. 123–140.
  * [38] M. Zhang, J. Li, Z. Chen, H. Chen, and X. Deng, “An efficient and robust committee structure for sharding blockchain,” _IEEE Transactions on Cloud Computing_ , 2022.
  * [39] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “Omniledger: A secure, scale-out, decentralized ledger via sharding,” in _2018 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2018, pp. 583–598.
  * [40] D. Tennakoon and V. Gramoli, “Dynamic blockchain sharding,” in _5th International Symposium on Foundations and Applications of Blockchain 2022 (FAB 2022)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [41] T. M. Cover and J. A. Thomas, _Elements of information theory_. New York: John Wiley & Sons, 2012.
  * [42] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” _Journal of the American Statistical Association_ , vol. 58, no. 301, pp. 13–30, 1963.
  * [43] V. Chvátal, “The tail of the hypergeometric distribution,” _Discrete Mathematics_ , vol. 25, no. 3, pp. 285–287, 1979. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0012365X79900840
  * [44] F. J. MacWilliams and N. J. A. Sloane, _The theory of error-correcting codes_. Elsevier, 1977, vol. 16.
  * [45] G. C. Ferrante, “Bounds on binomial tails with applications,” _IEEE Transactions on Information Theory_ , vol. 67, no. 12, pp. 8273–8279, 2021.