11institutetext: Chainlink Labs

#  BBCA-Chain: One-Message, Low Latency BFT Consensus on a DAG

Dahlia Malkhi  Chrysoula Stathakopoulou  Maofan Yin

###### Abstract

This paper presents a partially synchronous BFT consensus protocol powered by
BBCA, a lightly modified Byzantine Consistent Broadcast (CBC) primitive. BBCA
provides a Complete-Adopt semantic through an added probing interface to allow
either aborting the broadcast by correct nodes or exclusively, adopting the
message consistently in case of a potential delivery. It does not introduce
any extra type of messages or communication cost to CBC.

BBCA is harnessed into BBCA-CHAIN to make direct commits on a chained backbone
of a causally ordered graph of blocks, without any additional voting blocks or
artificial layering. With the help of Complete-Adopt, the additional knowledge
gained from the underlying CBC completely removes the voting latency in
popular DAG-based protocols. At the same time, causal ordering allows nodes to
propose blocks in parallel and achieve high throughput. BBCA-CHAIN thus closes
up the gap between protocols built by consistent broadcasts (e.g., Bullshark)
to those without such an abstraction (e.g., PBFT/HotStuff), emphasizing their
shared fundamental principles.

Using a Bracha-style CBC as an example, we fully specify BBCA-CHAIN with
simplicity, serving as a solid basis for high-performance replication systems
(and blockchains).

##  1 Introduction

A consensus protocol allows a network of nodes to consistently commit a
sequence of values (referred to as _blocks_). Usually, practical solutions
assume a _partially synchronous_ network that may suffer from temporary
outages or periods of congestion, where protocols can tolerate Byzantine
faulty nodes exhibiting arbitrary behavior so long has a _quorum_ of two-
thirds are correct.

After decades, this line of research has reached the known communication
complexity lower bound that is linear [43, 29] for steady operations and upon
reconfiguration. However, these solutions operate in a sequential manner,
extending the committed prefix one proposed block at a time. Hence, throughput
is limited by the (underutilized) proposer’s computational power, as it has to
wait for a round-trip to collect a quorum to move on.

To fully utilize the idle time in which a proposer waits for the next
sequential progress, recent works [19, 25, 14, 37, 30] harness Lamport’s
causal communication to allow blocks to be injected to the network in parallel
to finalize their commit ordering. Each block references one or more previous
blocks and the protocol relies on causal ordering, so that when nodes deliver
the block, they have already delivered the blocks in its entire ancestry on a
Direct Acyclic Graph (DAG). Then, the consensus logic “rides” on the DAG, so
that nodes interpret it locally for a sequentially committed _backbone_ (the
chain made from blocks with crowns in Figure 1). Each backbone block also
commits other non-backbone blocks it transitively references. Systems based on
such a design have demonstrated significant throughput gains.

Figure 1: A sequenced backbone on a DAG (thick arrows and solid blocks) and
referenced blocks that commit with it (thin arrows and hollow blocks).

However, existing DAG-riding solutions come with a relatively complicated
logic and suffer from several times higher latency. For example, a solution
like Bullshark [37] takes a minimum of 4 chained blocks to commit one block,
as illustrated on the left of Figure 2: a regular block at the head of the
chain needs to first be delivered into the DAG; secondly it must be followed
and referenced by a leader block which is restricted to odd layers of the DAG,
hence may take two more blocks; third, the proposal must be referenced by a
quorum of vote blocks that need to be on a subsequent, even layer dedicated to
voting. Each block in this procedure has to be delivered by a Byzantine
Consistent Broadcast (CBC) instance to guarantee a consistent view at all
nodes. Internally, CBC already consists of multiple rounds of messages,

This paper introduces BBCA-Chain, a new DAG-based consensus solution that
enables the same high throughput with much lower latency. BBCA-Chain
substantially simplifies the overall consensus logic: it commits a backbone
block via a single BBCA broadcast, a variant of CBC, without requiring vote
blocks or waiting to broadcast into the artificial layers. Apart from using
fewer steps than existing protocols, it also places fewer constraints on how
the DAG could be grown.

Figure 2: Reducing Bullshark commit latency (left) via three mechanisms.

BBCA-Chain achieves these improvements via three mechanisms depicted in Figure
2 from left to right:

Instead of encoding the voting process by the DAG layers, it removes vote
blocks altogether, because BBCA addresses voting internally. More
specifically, by peeking inside CBC, we observe that it is already a multi-
phase process similar to what other consensus protocols (such as PBFT [8]) do
in their main logic. We add a shim on top of CBC to create BBCA (Byzantine
Broadcast with Complete-Adopt), a new primitive that supports _probing_ the
local state of the broadcast protocol. The key new feature is a Complete-Adopt
interface: if a broadcast is completed by any non-faulty node running the BBCA
protocol, then a quorum probing via BBCA-probe will _adopt_ it. Said
differently, if a quorum probes and gets a BBCA-noadopt response, then it is
guaranteed that no completion of the BBCA broadcast will ever occur to any
(non-faulty) node. Through the Complete-Adopt interface from BBCA, one can
extract this useful invariant to directly drive the committed backbone. As
probing is done locally with a simple check of some protocol state variable,
it does not incur any additional communication.

As no vote blocks are needed, BBCA-Chain does not need special layering, which
further reduces the latency. As depicted in the middle of Figure 2, a block
can be immediately referenced by a leader block and become committed when the
leader block is completed by BBCA-broadcast. Finally, only leader blocks need
to use BBCA. All other blocks can be broadcast with a “Best-Effort Broadcast”
that simply sends the same message to all nodes via the inter-node channels
(denoted as “BEB” block on the right of Figure 2).

The table below summarizes the latency in terms of consecutive network-trips
of BBCA-Chain compared with state-of-art DAG solutions like Bullshark. The
implementation of the BBCA broadcast is assumed to use an all-all protocol,
since there is only a single BBCA invocation per view (see more details on
broadcasts in the body of the paper).

Latency | BBCA-Chain | Bullshark
---|---|---
Broadcast primitives |  BEB, 1 trip BBCA, 3 trips | CBC, 3 trips
leader blocks |  $1\times$ BBCA |  $2\times$ CBC
non-leader blocks |  $1\times$ BEB $\ +\ 1\times$ BBCA |  $4\times$ CBC
Table 1: Latency to commit a block on a DAG.

#### The Benefits of Causal Ordering.

BBCA-Chain is an interesting mid-point between non-DAG and DAG-based consensus
solutions, that enjoys the best of both worlds: the same latency as in those
non-DAG protocols, the high throughput from a better utilization of processing
power while waiting for backbone’s progress, and the simplicity of checking a
DAG to know the commitment progress.

In steady state, the way the sequenced backbone is formed in BBCA-Chain
resembles traditional non-DAG consensus protocols. The difference is that in
the latter, the network is underutilized as the protocol only disseminates
blocks on the linear backbone, whose rate of progress is bounded by a quorum
round-trip time, whereas DAG-based protocols can keep injecting non-backbone
blocks without waiting. Furthermore, the leader has to broadcast a
(potentially large) block combining all the requests. Previous studies [38]
have demonstrated that a single leader becomes a throughput bottleneck, even
if it broadcasts blocks which only include references to transactions. BBCA-
Chain leverages causal communication to allow nodes to inject blocks in
parallel. Then the leader sends a (smaller) block that simply references other
blocks. In addition, BBCA-Chain benefits from being able to parallelize the
validation of blocks, offloading the computational burden from the backbone.

At the same time, the way BBCA-Chain handles failures borrows the simplified
logic of DAG-based consensus. When leaders fail, the causal history allows
nodes to accept leader proposals without reasoning about (un)locking. Compared
to existing DAG-based protocols, BBCA-Chain further simplifies the solution by
requiring nodes only to inject new-view blocks into the DAG, foregoing vote
blocks.

Foregoing block-votes on the DAG has two additional far reaching benefits.

  1. 1.

It avoids the extra latency introduced in previous DAG-based solutions.
Rather, BBCA-Chain makes use of acknowledgment messages which are in any case
sent inside the BBCA broadcast protocol as votes.

  2. 2.

Whereas votes must be non-equivocating, blocks do not need to. Because we got
rid of vote blocks, there is no need to use CBC for non-leader blocks. Rather,
regular blocks can be uniquely ordered via the backbone utilizing only
causality. This change allows further reduction in latency.

##  2 Technical Overview

#### Consensus.

In the celebrated State-Machine-Replication (SMR) approach, a network of
validator nodes form consensus on a growing totally ordered log (or ”chain”)
of transactions. The focus in this paper is on practical settings in which
during periods of stability, transmission delays on the network are upper
bounded, but occasionally the system may suffer unstable periods. This is
known as the _partial synchrony_ model [17]. The strongest resilience against
Byzantine faults which is possible in this setting is $f$-tolerance, where
$f<n/3$ for a network of $n$ validators.

#### Separating Data Availability.

Borrowing from various prevailing systems, we assume that a separate data-
availability layer is used for disseminating data blobs. First, parallel
workers disseminate transactions and generate certificates of availability.
Then bundles of certificates are assembled into blocks in the consensus layer.
This way, when a leader proposes a block containing a bundle of certificates,
validators trust that their data can be retrieved. The information
dissemination and data-availability work is left out of scope in this paper
and we note that it can be highly parallelized, and is not considered in the
critical path of consensus or counted in latency analysis.

#### Causal Broadcast.

Direct Acyclic Graph (DAG) captures a transport substrate that guarantees
causal ordering of block delivery. Whenever a node is ready to broadcast a
block, the block contains references to some locally delivered blocks. The
consensus logic operates above the transport level, such that blocks are
handled (received and generated) in causal order.

#### The Backbone.

The general approach we take for DAG-based consensus is forming a sequenced
_backbone_ of leader blocks which we therefore call backbone blocks (Figure
1). When a backbone block becomes committed, every leader block in its causal
ancestry becomes committed as well. By walking from the earliest uncommitted
leader block in the backbone towards the latest committed leader block, one
can also commit those blocks outside the backbone but causally referenced by
the backbone blocks, according to any predefined, deterministic DAG traversal
order.

Forming consensus on the backbone itself “rides” on the DAG: any viewer can
detect a _commit-structure_ to determine when a block becomes committed to the
sequenced backbone by viewing the DAG, without additional communication or
historical states outside the DAG. In previous solutions, the detectable
commit-structure is somewhat complex, consisting of specialized layers. As we
shall see below, the commit-structure in BBCA-Chain is very simple: backbone
blocks become committed by themselves, utilizing the invariants from Complete-
Adopt of BBCA.

We first describe the BBCA broadcast primitive, and then we explain how BBCA
is used in BBCA-Chain to solve consensus on a DAG.

###  2.1 BBCA

The BBCA primitive is an abortable variation of CBC. Similar to CBC, BBCA has
a dedicated sender which BBCA-broadcasts messages and no two correct nodes
BBCA-complete different messages for the same BBCA instance.

Informally, inside BBCA, $f+1$ correct nodes must become locked on a unique
message $m$ before BBCA-complete is possible at any node. BBCA adds an
interactive Complete-Adopt interface allowing nodes to actively probe at any
time regardless of their progress in CBC. Probing stops a node from completing
the delivery, with one of two possible return values; BBCA-adopt for some
locked message $m$ or BBCA-noadopt, with the following guarantee:

#### The Complete-Adopt Invariant.

If any correct node $\textsc{BBCA-
complete}(\mathit{bid},m,\mathit{cert}_{m})$, then at least $f+1$ correct
nodes return $\langle\textsc{BBCA-
adopt},\mathit{bid},m,\mathit{cert}_{m}\rangle$ upon probing. In other words,
if $f+1$ probes by correct nodes return $\langle\textsc{BBCA-
noadopt},\mathit{bid}\rangle$, $\textsc{BBCA-
complete}(\mathit{bid},m,\mathit{cert}_{m})$ never occurs at any correct node.

We implement BBCA via an all-all regime a la Bracha broadcast [3]. In this
form, BBCA takes $3$ network trips. To further improve scalability, all-to-all
communication may take place over a peer-to-peer gossip transport.
Furthermore, acknowledgements may be batched and aggregated.

The table below summarizes the number of network trips in BBCA compared with
other forms of broadcast. In all forms, the underlying communication may be
carried either over all-all authenticated channels, or in a linear regime
relayed through a sender who aggregates signatures.

Broadcast scheme | all-all | linear
---|---|---
Best Effort Broadcast (BEB) | 1 | 1
Byzantine Consistent Broadcast (CBC) | 2 | 3
BBCA | 3 | 5
Table 2: Network trips in various broadcast schemes.

###  2.2 BBCA-Chain

Figure 3: Decision making latency in BBCA-Chain (left) compared with Bullshark
(right). Figure 4: When a view timer expires, each node needs to include a
BBCA-probe result inside its new-view block. The left DAG depicted an adopted
block, and some correct node may have just BBCA-completed it. The right DAG
shows $2f+1$ noadopt responses, proving that no block can be completed in that
view.

BBCA-Chain is a view-by-view protocol. Each view reaches a consensus decision
in a single BBCA step. BBCA-Chain forms a DAG of two types of blocks: backbone
blocks and new-view blocks. Although there is no artificial layering, they can
be logically grouped by views (as depicted on the left of Figure 3). Both
types of blocks may carry transaction payload.

A transition to view $v$ occurs either upon BBCA-complete of the backbone
block of view $v-1$, or when the new-view timer of view $v-1$ expires. In the
second case, a node invokes BBCA-probe locally, and then embeds the return
value in its new-view block. A new-view block must include one of the
following three items: a BBCA-completed backbone block from view $v-1$, an
adopted backbone block from probing, or a signed BBCA-noadopt result together
with the highest completed block locally known. Before entering view $v$, each
node broadcasts a new-view block under one of the three mentioned cases, and
also starts a new-view timer. The leader of view $v$ BBCA-broadcasts a
backbone block. The block refers to the completed or adopted backbone block of
view $v-1$, if available111As a technical matter, note that the code in Figure
94 encapsulates these references in a new-view block which the leader can
embed inside a backbone block., otherwise it references $2f+1$ blocks with
signed BBCA-noadopt.

The left graph of Figure 3 shows the fast, _commit path_ , when the leader has
BBCA-completed the backbone block of the previous view. Figure 4 illustrates
the _adopt path_ , with two different outcomes from nodes’ probing results.
The key observation is that the BBCA Complete-Adopt scheme guarantees that the
fast and adopt paths are consistent

BBCA allows backbone blocks to become committed by themselves, without any
additional votes or DAG layering. This single-broadcast commit decision
accomplishes a substantive reduction in latency to reach consensus, and also
significantly simplifies the logic.

Non-backbone blocks are broadcast in parallel using a Best-Effort Broadcast
where a node just directly sends a block to all nodes. These blocks become
committed by being causally referenced by some blocks on the backbone, similar
to “uncle blocks” in Ethereum. Since the local DAG of different nodes may
evolve at different pace, the Complete-Adopt feature of BBCA preserves the
safety of committed backbone blocks. BBCA-completed backbone blocks suffice to
uniquely determine which non-backbone blocks to include in the total ordering.

It is worth noting that previous solutions like Bullshark need non-backbone
blocks to vote in the consensus protocol, hence to prevent equivocation, these
blocks are broadcast using CBC. Because BBCA-Chain gets rid of voting blocks
altogether, there is no need to use CBC for non-backbone blocks, and this
change allows further reduction in latency. While CBC is not required for
correctness, it may be used for other reasons (e.g., to avoid keeping
equivocating blocks in the DAG). Even if CBC is used for non-backbone blocks,
BBCA-Chain exhibits an overall substantially lower latency than existing DAG-
based protocols.

Overall, BBCA-Chain accomplishes a substantial reduction in latency over
state-of-art DAG protocols. Figure 3 illustrates side-by-side the time to
commit backbone blocks in BBCA-Chain (left) compared with a DAG-based solution
like Bullshark (right). Hourglasses on the right side denote additional
constraints posed on advancing layers by Bullshark.

##  3 The BBCA Primitive

BBCA-Chain invokes BBCA broadcast primitive, an abortable variant of CBC
222Pronounced ‘Bab-Ka’, and loosely stands for Byzantine Abortable Broadcast
with Complete-Adopt. for multiple times. Each BBCA instance has a unique
identifier $\mathit{bid}$ to be totally isolated in its progress. Similar to
CBC, each instance of BBCA broadcast has a dedicated node as the _sender_ who
can invoke $\textsc{BBCA-broadcast}(\mathit{bid},m)$, to broadcast message $m$
for instance $\mathit{bid}$. Eventually, the node may $\textsc{BBCA-
complete}(bid,m,\mathit{cert}_{m})$. We say for short that the node BBCA-
completes $m$ and $\mathit{cert}_{m}$ is a certificate to convince any node
that $m$ has been completed. A node may also abort a BBCA instance and probe
its state at any time by invoking $\textsc{BBCA-probe}(\mathit{bid})$. This
invocation returns in two possible ways. The BBCA instance returns
$\langle\textsc{BBCA-adopt},\mathit{bid},m,\mathit{cert}_{m}\rangle$ for some
message $m$ with a certificate $\mathit{cert}_{m}$, to certify that some
correct node might complete $m$ and no correct node could complete a message
$m^{\prime}\neq m$. Otherwise, BBCA returns $\langle\textsc{BBCA-
noadopt},\mathit{bid}\rangle$. In the former case, we say in short that the
node BBCA-adopts $m$, otherwise, we say that it does not BBCA-adopt any
message. BBCA maintains the following properties:

Validity.

If a correct sender BBCA-broadcasts a message $m$ for instance $\mathit{bid}$,
and no correct node probes $\mathit{bid}$, eventually every correct node BBCA-
completes $m$.

Consistency.

If a correct node either BBCA-adopts or BBCA-completes a message $m$ for
instance $\mathit{bid}$, and some other correct node BBCA-completes message
$m^{\prime}$ for $\mathit{bid}$, then $m=m^{\prime}$.

Complete-Adopt.

If a message $m$ is ever BBCA-completed by some correct node for instance
$\mathit{bid}$, then at least $f+1$ correct nodes get $\langle\textsc{BBCA-
adopt},\mathit{bid},m,\mathit{cert}_{m}\rangle$ for $\mathit{bid}$, if they
invoke $\textsc{BBCA-probe}(\mathit{bid})$. That is, if $f+1$ correct nodes
get $\langle\textsc{BBCA-noadopt},\mathit{bid}\rangle$, then no correct node
ever BBCA-completes any message for instance $\mathit{bid}$.

Integrity.

If a correct node BBCA-adopts or BBCA-completes a message $m$ for instance
$\mathit{bid}$ and the sender $p$ is correct, then $p$ has previously invoked
$\textsc{BBCA-broadcast}(\mathit{bid},m)$.

BBCA is intialized with an external validity predicate $\mathcal{P}$, such
that a correct node only BBCA-completes $m$ if $\mathcal{P}(m)$ is true.

The pseudocode in Figure 67 implements BBCA by slightly modifying the Bracha
broadcast protocol [3]. Upon sender’s invocation of BBCA-broadcast, it
broadcasts $\langle\textsc{Init},\mathit{bid},m\rangle$. For a node $p$, upon
receiving $\langle\textsc{Init},\mathit{bid},m\rangle$ from the sender of
instance $\mathit{bid}$, it checks that validity condition $\mathcal{P}(m)$
holds. If $m$ is valid, $p$ broadcasts
$\langle\textsc{Echo},\mathit{bid},m\rangle_{\sigma_{p}}$, where $\sigma_{p}$
is the signature of $p$ on $\langle\textsc{Echo},\mathit{bid},m\rangle$, and
becomes _initialized_ , such that it will no longer be initialized again.

Upon receiving an Echo message from $2f+1$ distinct nodes for $\mathit{bid}$
and $m$ with valid signatures, $p$ becomes _ready_ , _unless_ $p$ has already
probed instance $\mathit{bid}$. Then it broadcasts a signed message
$\langle\textsc{Ready},\mathit{bid},m\rangle_{\sigma_{p}}$. The $2f+1$
signatures on $\langle\textsc{Echo},\mathit{bid},m\rangle$ certify a node has
sent a ready message for $m$.

Upon receiving a valid Ready message from $2f+1$ distinct nodes for
$\mathit{bid}$ and $m$, and, BBCA-completes $m$ in instance $\mathit{bid}$.
The $2f+1$ signatures on $\langle\textsc{Ready},\mathit{bid},m\rangle$ certify
a node has completed $m$.

When probed in instance $\mathit{bid}$, if $p$ has already become ready for
$m$, it returns $\langle\textsc{BBCA-
adopt},\mathit{bid},m,\mathit{cert}_{m}\rangle$ where $\mathit{cert}_{m}$ is a
collection of $2f+1$ signed echo messages. Otherwise, it returns
$\langle\textsc{BBCA-noadopt},\mathit{bid}\rangle$.

1:Init:

2: // $\mathit{bid}$ is a unique identifier for a BBCA-broadcast instance, it
contains $\mathit{bid}.\mathit{sender}$ indicating the designated sender of
the instance

3: $\mathit{bbcaState}[\mathit{bid}].\mathit{pendingMsgs}\leftarrow\\{\\}$

4: // $\mathit{pendingMsgs}[m].\mathit{nEcho}\leftarrow\\{\\}$ and

5: // $\mathit{pendingMsgs}[m].\mathit{nReady}\leftarrow\\{\\}$

6: // when message $m$ is first seen.

7: $\forall p\in
N,\mathit{bbcaState}[\mathit{bid}].\mathit{receivedEcho}[p]\leftarrow\textsc{false}$

8: $\forall p\in
N,\mathit{bbcaState}[\mathit{bid}].\mathit{receivedReady}[p]\leftarrow\textsc{false}$

9: $\mathit{bbcaState}[\mathit{bid}].\mathit{ready}\leftarrow\textsc{false}$

10: $\mathit{bbcaState}[\mathit{bid}].\mathit{echo}\leftarrow\textsc{false}$

11: $\mathit{bbcaState}[\mathit{bid}].\mathit{abort}\leftarrow\textsc{false}$

12:

13:interface _BBCA-broadcast_($\mathit{bid},m$) :

14: $\textsc{becomesInitialized}(\mathit{bid},m)$

15: $\textsc{broadcast}(\langle\textsc{Init},\mathit{bid},m\rangle)$

16:

17:interface _BBCA-probe_($\mathit{bid}$) :

18: $\textbf{let}\,\,{\mathit{bstate}}={\mathit{bbcaState}[\mathit{bid}]}$

19:
$\textbf{let}\,\,{\mathit{mstates}}={\mathit{bstate}.\mathit{pendingMsgs}}$

20: if $\exists m:|\mathit{mstates}[m].\mathit{nEcho}|\geq 2f+1$ then

21: return $\langle\textsc{BBCA-
adopt},\mathit{bid},m,\mathit{mstates}[m].\mathit{nEcho}\rangle$

22: else

23: $\mathit{bstate}.\mathit{abort}\leftarrow\textsc{true}$

24: return $\langle\textsc{BBCA-noadopt},\mathit{bid}\rangle$

25: end if

26:

27:procedure _becomesInitialized_($\mathit{bid},m$) is

28: $\mathit{bbcaState}[\mathit{bid}].\mathit{echo}\leftarrow\textsc{true}$

29:
$\textsc{broadcast}(\langle\textsc{Echo},\mathit{bid},m\rangle_{\sigma_{p}})$

30:

31:procedure _becomesReady_($\mathit{bid},m$) is

32: if
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}!\mathit{bbcaState}[\mathit{bid}].\mathit{abort}}$
then

33: $\mathit{bbcaState}[\mathit{bid}].\mathit{ready}\leftarrow\textsc{true}$

34: $\textsc{broadcast}(\langle\textsc{Ready},\mathit{bid},m\rangle)$

35: end if

36:

37:upon receiving $\langle\textsc{Init},\mathit{bid},m\neq\bot\rangle$ from
$q$ do

38: $\textbf{let}\,\,{\mathit{bstate}}={\mathit{bbcaState}[\mathit{bid}]}$

39: if
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{P}(m)}\land
q=\mathit{bid}.\mathit{sender}\land(!\mathit{bstate}.\mathit{echo})$ then

40: becomesInitialized($\mathit{bid},m$)

41: end if

42:

43:upon receiving
$\langle\textsc{Echo},\mathit{bid},m\neq\bot\rangle_{\sigma_{q}}$ from $q$ do

44: $\textbf{let}\,\,{\mathit{bstate}}={\mathit{bbcaState}[\mathit{bid}]}$

45: if
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{P}(m)}\land(!\mathit{bstate}.\mathit{receivedEcho}[q])$
then

46: $\mathit{bstate}.\mathit{receivedEcho}[q]\leftarrow\textsc{true}$

47:
$\textbf{let}\,\,{\mathit{mstate}}={\mathit{bstate}.\mathit{pendingMsgs}[m]}$

48:
$\mathit{mstate}.\mathit{nEcho}\leftarrow\mathit{mstate}.\mathit{nEcho}\cup\\{\sigma_{q}\\}$

49: if
$!\mathit{bstate}.\mathit{ready}\land|\mathit{mstate}.\mathit{nEcho}|=2f+1$
then

50: becomesReady($\mathit{bid},m$)

51: end if

52: end if

53:

54:upon receiving
$\langle\textsc{Ready},\mathit{bid},m\neq\bot\rangle_{\sigma_{q}}$ from $q$ do

55: $\textbf{let}\,\,{\mathit{bstate}}={\mathit{bbcaState}[\mathit{bid}]}$

56: if
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{P}(m)}\land(!\mathit{bstate}.\mathit{receivedReady}[q])$
then

57: $\mathit{bstate}.\mathit{receivedReady}[q]\leftarrow\textsc{true}$

58:
$\textbf{let}\,\,{\mathit{mstate}}={\mathit{bstate}.\mathit{pendingMsgs}[m]}$

59:
$\mathit{mstate}.\mathit{nReady}\leftarrow\mathit{mstate}.\mathit{nReady}\cup\\{\sigma_{q}\\}$

60: if
$!\mathit{bstate}.\mathit{ready}\land|\mathit{mstate}.\mathit{nReady}|=f+1$
then

61: becomesReady($\mathit{bid},m$)

62: end if

63: if $|\mathit{mstate}.\mathit{nReady}|=2f+1$ then

64: BBCA-complete($\mathit{bid},m,\mathit{mstate}.\mathit{nReady}$)

65: end if

66: end if

67: Figure 5: BBCA-broadcast primitive with a validity predicate $\mathcal{P}$
based on a all-to-all Bracha broadcast protocol. The blue text shows the
simple tweak that is added to the vanilla Bracha to enable the Complete-or-
Adopt scheme, whereas red text shows the part that is removed.

For completeness, we mention that another approach for implementation is a
linear regime a la Cachin et al. [7]. In a linear form, BBCA takes $5$ network
trips, while the probing logic is similar (return the adopted $m$ or promise
not to sign the second acknowledgement):

  1. 1.

The designated sender broadcasts the block to all nodes.

  2. 2.

After the validation of the block, nodes respond with a signed acknowledgement
over the block’s digest.

  3. 3.

The sender broadcasts an aggregated/concatenated proof of $2f+1$ signatures.

  4. 4.

Nodes respond to the proof from the sender with a signed acknowledgement over
the proof.

  5. 5.

The sender broadcasts an aggregate/concatenated proof of signatures, and nodes
BBCA-complete it upon receipt.

#### Relationship to Other Broadcasts

Bracha’s “all-to-all” broadcast protocol is not only a CBC but also a
Byzantine Reliable Broadcast (RBC), because it additionally guarantees
reliable delivery of the broadcast message. Since BBCA is abortable,
reliability is not guaranteed in presence of a faulty sender or network
delays. However, when used in the construction of BBCA-Chain as we show later,
reliability is gained for committed blocks through chaining: after seeing a
BBCA-complete certificate for a block, later commits will causally reference
the block itself or BBCA-Adopt of it.

Since we forego reliability for BBCA, we remove the extra trip shown in red
text from the original Bracha protocol (Figure 67). Requiring a weaker
broadcast primitive also allows the alternative linear form to preserve
linearity, otherwise all-to-all broadcast would be required on top “linear”
CBC in order to guarantee reliability. Therefore, BBCA makes a weaker, more
basic primitive than RBC and reduces latency/message-complexity.

##  4 The BBCA-Chain Protocol

###  4.1 Model

We assume a set of $n$ nodes which communicate via point-to-point
authenticated channels such that up to $f<\frac{n}{3}$ of them may fail
arbitrarily. We assume partially synchronous communication such that network
delays are unbounded until some unknown Global Stabilization Time (GST). After
GST, network delays are bounded by constant $\Delta$. But because GST is
unknown, the safety of the protocol cannot rely on $\Delta$.

###  4.2 Consensus

In a consensus protocol, each correct node may take some payload (e.g.,
transactions), seal it in a block, and send it to the network. A commit
statement is triggered to sequence blocks in their final order, with the
following properties:

Consistency.

For the sequences of committed blocks by any two nodes, one has to be the
prefix of another.

Chain growth.

The sequence of committed blocks keeps growing for all correct nodes.

Censorship resistance.

After GST, if a correct node sends a block $b$ to the network, then $b$ is
eventually committed.

BBCA-Chain commits blocks in _views_ and in each view $v$, one node acts as
_leader_ , evaluated by each node via a $\textsc{getProposer}(v)$ function.
For simplicity, throughout the paper we assume a round-robin rotation, though
more elaborate and/or adaptive schemes may be used. Nodes enter a new view
with a _view synchronization_ protocol, which we discuss in more detail in
Section 5. Each node, upon entering a new view, starts a view timer and starts
participating in a new BBCA instance (identified as
$\mathit{bid}=\langle\textsc{getProposer}(v),v\rangle$). Nodes other than the
leader broadcast a _new-view_ block. The leader, however, proposes a _backbone
block_ $B_{v}$ by invoking $\textsc{BBCA-broadcast}(\mathit{bid},B_{v})$.

In the common case, a node completes view $v$ and is ready to enter view $v+1$
upon it BBCA-completes the backbone block of view $v$. The block that has
completed gets marked as the final block for $v$ and the protocol guarantees
that every correct node eventually also commits this block. In this case, the
new-view block for view $v+1$ includes (1) a causal reference to the completed
backbone block $B_{v}$, (2) the BBCA-complete certificate
$\mathit{cert}_{B_{v}}$ proving that $p$ completed $B_{v}$, (3) the view
number $v$, and (optionally) a payload of pending transactions and causal
references to help commit some additional previous blocks. For a node that is
the leader of $v+1$, instead of broadcasting this new-view block, it just
embeds (or causally references to) it when it propose in view $v+1$.

If at some node $p$ the timer for a view $v$ expires before a BBCA-complete of
backbone block for view $v$, then $p$ _probes_ the BBCA instance of view $v$
and completes view $v$. This forces the BBCA instance to stop sending ready
messages internally. If there exists a node that could BBCA-complete a
backbone block $B_{v}$, then BBCA returns $\langle\textsc{BBCA-
adopt},B_{v},\mathit{cert}_{B_{v}}\rangle$, for at least $f+1$ correct nodes
where $\mathit{cert}_{B_{v}}$ is the corresponding adopt certificate. In this
case, similarly, the new-view block for view $v+1$ includes (1) a causal
reference to the adopted backbone block $B_{v}$, (2) the adopt certificate
$\mathit{cert}_{B_{v}}$ proving that $p$ adopted $B_{v}$ (i.e., no correct
node could complete any other block), (3) the view number $v$, and like the
previous case, some optional payload and causal references.

For the rest of the nodes, BBCA may return $\langle\textsc{BBCA-
noadopt}\rangle$. In this case the new-view block which $p$ broadcasts
includes (1) a causal reference to the backbone block
$B=\mathit{lastCompleted}$ of the highest view which $p$ has completed, (2)
the corresponding complete certificate $\mathit{cert}_{B}$, proving that $p$
completed $B$, (3) a signed tuple
$\langle\textsc{noadopt},v\rangle_{\sigma_{p}}$, together with the additional
information as mentioned.

The backbone block for view $v+1$ includes (1) a causal reference to $1$ or
$2f+1$ new-view blocks, depending on how the leader enters the view, (2) the
new view number $v+1$, and like new-view blocks, possibly some additional
payload. In the common case, the leader includes a causal reference to a new-
view block which references the backbone block of view $v$ which the leader of
view $v$ has committed. Notice that in this case the leader can _embed_ its
own new-view block, and, hence, does not have to wait for other new-view
blocks to arrive. Otherwise, the leader waits for new-view blocks of other
nodes to justify what happened in view $v$. If the leader receives a new-view
block $B_{n}$ with a valid adopt certificate $\mathit{cert}_{B_{v}}$ for the
backbone block $B_{v}$ of view $v$, the leader includes a causal reference to
$B_{n}$. Otherwise, the leader waits for and causally references $2f+1$ new-
view blocks from distinct nodes with a valid signature on the tuple
$\langle\textsc{noadopt},v\rangle$. These constitute a justification that no
node could commit a backbone block in view $v$ and thus it is safe to skip.

Each node maintains local state for _finalized_ views, i.e., each view $v$ for
which the node has a valid complete certificate for a backbone block, a valid
adopt certificate for a backbone block causally followed by a completed
backbone block, or $2f+1$ distinct valid signatures on
$\langle\textsc{noadopt},v\rangle$. Upon receiving a new-view block, including
their own, with a causal reference to a backbone block $B_{v}$ for view $v$
and a valid complete certificate for $B_{v}$, a node $p$ finalizes view $v$
with $B_{v}$. Moreover, $p$ recursively finalizes the non-finalized views in
$B_{v}$’s causal history as follows: a view $v^{\prime}$ is finalized with
$B_{v^{\prime}}$ if there exists a complete or adopt certificate for
$B_{v^{\prime}}$, otherwise $v^{\prime}$ is finalized with a special no-op
value to indicate that view $v^{\prime}$ should simply be skipped.

Additionally, the node maintains a pointer for the highest committed view
$\mathit{lastCommitted}$. Upon finalizing some view $v$, $p$ commits backbone
blocks for all contiguous finalized views, starting from
$\mathit{lastCommitted}$, while skipping views finalized with no-op. This
ensures that nodes commit backbone blocks in increasing view numbers with
consistent committed prefixes. Along each backbone block, $p$ commits to the
total order all remaining causally referenced blocks including new-view blocks
according to some deterministic rule. Note that by the causality of broadcast,
a node that commits the backbone block already has all the blocks referenced
by the backbone block available.

The BBCA-Chain protocol is presented as pseudocode in Figure 94.

1:Init:

2: $\forall v\in\mathbb{N},\mathit{newViewBlocks}[v]\leftarrow\bot$

3: // $\mathit{newViewBlocks}[v]$ holds the set of received new-view blocks in
view $v$, $\mathit{newViewBlocks}[v][q]$ is the block from $q$

4: $\forall v\in\mathbb{N},\mathit{finalized}[v]\leftarrow\bot$

5: // $\mathit{finalized}[v]$ holds the finalized block for view $v$, a
continuously committed prefix is the committed chain.

6: $\mathit{lastCommitted}\leftarrow 0$

7: $\mathit{lastCompleted}\leftarrow\langle
B_{\mathit{genesis}},\mathit{cert}_{0}\rangle$

8: $\mathit{newViewBlocks}[0]\leftarrow\mathit{newViewBlock}($

9:
$\mathit{ref}=B_{\mathit{genesis}},\mathit{completeCert}=\mathit{cert}_{0})$

10: $\mathit{view}\leftarrow 0$

11: $\mathit{viewTimer}.\mathit{init}()$

12: $\textsc{enterView}(1)$

13:

14:procedure _enterView_($v$) is

15: $\mathit{view}\leftarrow v$

16: $\mathit{viewTimer}.\mathit{restart}()$

17:
$\textbf{let}\,\,{\mathit{proposer}}={\textsc{getProposer}(\mathit{view})}$

18: initialize BBCA instance with
$\mathit{bid}=\langle\mathit{proposer},\mathit{view}\rangle$

19: // Nothing for non-leader to do until some event received

20: if $\mathit{proposer}\neq p$ then return

21: $\textbf{let}\,\,{C}={\mathit{newViewBlocks}[\mathit{view}-1]}$

22: $\textbf{let}\,\,{\mathit{complete}}={\exists
q:C[q].\mathit{completeCert}\neq\bot\,\,\land}$

23: $C[q].\mathit{ref}.\mathit{view}=\mathit{view}-1$

24: $\textbf{let}\,\,{\mathit{adopt}}={\exists
q:C[q].\mathit{adoptCert}\neq\bot}$

25: $\textbf{let}\,\,{\mathit{noadopt}}={\exists Q:|Q|=2f+1\,\,\land}$

26: $(\forall r\in
Q:C[r].\mathit{sig}=\langle\textsc{noadopt},\mathit{view}-1\rangle_{\sigma_{r}})$

27: wait until
$\mathit{complete}\lor\mathit{adopt}\lor\mathit{noadopt}=\textsc{true}$

28: if $\mathit{complete}$ then

29: $\mathit{prevView}\leftarrow\langle\mathit{completed}=C[q]\rangle$

30: else if $\mathit{adopt}$ then

31: $\mathit{prevView}\leftarrow\langle\mathit{adopted}=C[q]\rangle$

32: else

33: $\mathit{prevView}\leftarrow\langle\mathit{noadopted}=\\{C[r]:\forall r\in
Q\\}\rangle$

34: end if

35:
$B\leftarrow\mathit{backboneBlock}(\mathit{ref}=\mathit{prevView},\mathit{view}=\mathit{view})$

36: $\textsc{BBCA-
broadcast}(\langle\mathit{sender}=p,\mathit{view}=\mathit{view}\rangle,B)$

37:

38:upon $\textsc{BBCA-complete}(\mathit{bid},B,\mathit{cert}_{B})$ do

39: $\textsc{tryCommit}(B)$

40: if $B.\mathit{view}<\mathit{view}$ then return

41:
$\mathit{lastCompleted}\leftarrow\langle\mathit{ref}=B,\mathit{cert}=\mathit{cert}_{B}\rangle$

42: $\textbf{let}\,\,{B_{n}}={\mathit{newViewBlock}(}$

43: $\mathit{ref}=B,\mathit{completeCert}=\mathit{cert}_{B},B.\mathit{view})$

44: if $\textsc{getProposer}(B.\mathit{view}+1)=p$ then

45: // $p$ is the proposer for the next view, thus

46: // enterView will embed $B_{n}$ in the proposal.

47: $\mathit{newViewBlocks}[B_{n}.\mathit{view}][p]\leftarrow B_{n}$

48: else

49: $\textsc{broadcast}(B_{n})$

50: end if

51: $\textsc{enterView}(B.\mathit{view}+1)$

52:

53:upon $\mathit{viewTimer}.\mathit{elapsed}>\mathit{T_{max}}$ do

54: if $\langle\textsc{BBCA-
adopt},\mathit{bid},B,\mathit{cert}_{B}\rangle=\textsc{BBCA-
probe}(\mathit{bid})$ then

55: $\textsc{broadcast}(\mathit{newViewBlock}($

56: $\mathit{ref}=B,\mathit{adoptCert}=\mathit{cert}_{B},\mathit{view}))$

57: else

58: $\langle B,\mathit{cert}_{B}\rangle\leftarrow\mathit{lastCompleted}$

59: $\textsc{broadcast}(\mathit{newViewBlock}($

60: $\mathit{ref}=B,\mathit{completeCert}=\mathit{cert}_{B},$

61: $\mathit{sig}=\langle\textsc{noadopt},\mathit{view}\rangle_{\sigma_{p}}))$

62: end if

63: $\textsc{enterView}(\mathit{view}+1)$

64:

65:upon receiving newViewBlock $B_{n}$ from $q$ do

66: if $\mathit{newViewBlocks}[B_{n}.\mathit{view}][q]=\bot$ then

67: $\mathit{newViewBlocks}[B_{n}.\mathit{view}][q]\leftarrow B_{n}$

68: if $B_{n}.\mathit{completeCert}\neq\bot$ then
$\textsc{tryCommit}(B_{n}.\mathit{ref})$

69: end if

70:

71:procedure _tryCommit_($B$) is

72: $\textsc{finalize}(B)$

73: while $\mathit{finalized}[\mathit{lastCommitted}+1]\neq\bot$ do

74: $\mathit{lastCommitted}\leftarrow\mathit{lastCommitted}+1$

75: if $\mathit{finalized}[\mathit{lastCommitted}]\neq\textsc{no-op}$ then

76: $\textbf{commit}\,\mathit{finalized}[\mathit{lastCommitted}]$

77: end if

78: end while

79:

80:procedure _finalize_($B$) is

81: if $\mathit{finalized}[B.\mathit{view}]\neq\bot$ then return

82: $\mathit{finalized}[B.\mathit{view}]\leftarrow{B}$

83: if $B.\mathit{ref}.\mathit{completed}\neq\bot$ then

84: $\textsc{finalize}(B.\mathit{ref}.\mathit{completed}.\mathit{ref})$

85: else if $B.\mathit{ref}.\mathit{adopted}\neq\bot$ then

86: $\textsc{finalize}(B.\mathit{ref}.\mathit{adopted}.\mathit{ref})$

87: else

88: $B_{\max}\leftarrow\operatorname*{arg\,max}_{B_{n}\in
B.\mathit{ref}.\mathit{noadopted}}(B_{n}.\mathit{ref}.\mathit{view})$

89: for $i\in[B_{\max}.\mathit{ref}.\mathit{view}+1,{}B.\mathit{view})$ do

90: $\mathit{finalized}[i]\leftarrow\textsc{no-op}$

91: end for

92: $\textsc{finalize}(B_{\max}.\mathit{ref})$

93: end if

94: Figure 6: BBCA-Chain operational logic for node $p$. Block validation is
omitted in the code for clarity. $\mathit{backboneBlock}()$ and
$\mathit{newViewBlock}()$ construct backbone and new-view blocks respectively.
During the block construction, actual payload (e.g., transactions from the
mempool) and causal references to the uncommitted frontier can be added to
causally commit useful transactions according to the consistent ordering on
the view-by-view backbone determined by commit.

##  5 Further Discussion

#### Simplifying further.

We can change the protocol to avoid requiring nodes to broadcast new-view
blocks. Adopting the principles of HotStuff-2 [29], nodes will send new-view
messages directly to the leader of the next view. The view-synchronization
would be handled using some protocol outside the DAG (see the related works in
Section 8).

Briefly, this modification works as follows. The leader of view $v$ waits for
the earliest of the following conditions in order to form a proposal:

  * •

a commit certificate of $B_{v-1}$ is received.

  * •

an adopt certificate has been received.

  * •

new-view messages on view $v-1$ have been received from all nodes.

  * •

the view $v-1$ timer has expired, potentially with an additional time to allow
one network trip.

Other nodes guard the safety of backbone proposals by comparing with their own
highest certified backbone block, instead of by looking at the proposal causal
history. That is, the predicate $\mathcal{P}(B_{v})$ nodes use before they
accept a backbone block is that the block references a backbone block (either
as commit or an adopt certificate) at least as high as the node’s highest
adopt/commit certificate.

Briefly, after GST, in case the leader of view $v$ does not obtain a
certificate for a backbone block of view $v-1$, then it is guaranteed that no
correct node holds a commit or adopt certificate for view $v-1$. Before GST,
the leader proposal might not receive in time the highest backbone block
certificate in the system. In case there is any node with a higher backbone
block certificate than proposed, then this node may indeed reject the leader
proposal because it will not pass the $\mathcal{P}(B_{v})$ predicate. This is
ok, because safety is ensured, while liveness can only be guaranteed after
GST.

#### Network utilization.

As discussed in Section 4 backbone blocks and new-view blocks may include a
payload, i.e., transactions or a bundle of certificates for available
transactions, assuming a separate data dissemination and availability layer.
However, BBCA-Chain design allows nodes to broadcast data blocks, i.e., blocks
with payload, independently in parallel, at any time, and orthogonally to view
progression. Therefore, unlike in layered DAGs, nodes with high load and high
bandwidth capacity can broadcast data blocks more frequently. Moreover, nodes
can continue broadcasting data blocks, even when view progression is slow, in
presence of a network partition or a slow/Byzantine leader. This allows nodes
to stay busy continuously and truly saturate the network capacity.

#### View synchronization.

In BFT protocols, view synchronization ensures that all correct nodes enter a
new view within bounded time. There exist several recent advancements in
literature which could be used by BBCA-Chain [9, 28]. However, we can enhance
BBCA-Chain itself to implement view synchonization with few simple rules. In
the common case, a node completes view $v$ and enters view $v+1$ upon it BBCA-
completes the backbone block of view $v$. Moreover, a correct node, upon
receiving a new-view block $B_{n}$ for view $v+1$, which references a
completed backbone block completes view $v$ and enters view $v+1$. Similarly,
a correct node upon receiving a new-view block $B_{n}$ references an adopted
backbone block, adopts the backbone block, and enters view $v+1$. A correct
node, if upon a timeout probes BBCA and gets BBCA-noadopt, does not enter view
$v+1$ unless it receives $2f+1$ new-view messages. Finally, a correct node,
upon receiving $f+1$ new-view blocks for view $v+1$ with a valid
$\langle\textsc{noadopt},v+1\rangle$ signature, probes its BBCA instance for
view $v$, completes view $v$ and enters view $v+1$. In the last case, $f+1$
messages are necessary to ensure that $f$ parties cannot force a correct node
to complete a view.

##  6 BBCA Implementation Correctness

In this section we prove that the specification of BBCA in Algorithm 67
satisfies BBCA properties described in Section 3.

######  Lemma 1 (Validty)

If a correct sender BBCA-broadcasts a message $m$ for instance $\mathit{bid}$,
and no correct node probes $\mathit{bid}$, eventually every correct node BBCA-
completes $m$.

###### Proof

Because the sender is correct, all correct nodes broadcast an Echo message for
$m$. All correct nodes then receives at least $n-f=2f+1$ Echo messages. As no
correct node invokes BBCA-probe, all correct nodes will broadcast a Ready
message for $m$. Therefore, all correct nodes receive at least $2f+1$ Ready
messages and BBCA-complete $m$.

######  Lemma 2 (Consistency)

If a correct node either BBCA-adopts or BBCA-completes a message $m$ for
instance $\mathit{bid}$, and some other correct node BBCA-completes message
$m^{\prime}$ for $\mathit{bid}$, then $m=m^{\prime}$.

###### Proof

For either BBCA-adopt or BBCA-complete case, a correct node $p$ needs to
receive at least $2f+1$ Echo messages. Let’s assume that some other node $q$
BBCA-completes some message $m^{\prime}\neq m$ in the instance of
$\mathit{bid}$. Then $q$ has also received at least $2f+1$ Echo messages.
Since $n=3f+1$, among $2(2f+1)=4f+2$ messages, there are $f+1$ sent by the
same set of nodes to both $p$ and $q$. Thus at least one correct node has sent
to both $p$ and $q$, leading to a contradiction that a correct node can only
echo the same $m$.

######  Lemma 3 (Complete-Adopt)

If a message $m$ is ever BBCA-completed by some correct node for instance
$\mathit{bid}$, then at least $f+1$ correct nodes get $\langle\textsc{BBCA-
adopt},\mathit{bid},m,\mathit{cert}_{m}\rangle$ for $\mathit{bid}$, if they
invoke $\textsc{BBCA-probe}(\mathit{bid})$. That is, if $f+1$ correct nodes
return $\langle\textsc{BBCA-noadopt},\mathit{bid}\rangle$, then no correct
node ever BBCA-completes any message for instance $\mathit{bid}$.

###### Proof

If some correct node BBCA-completes a message $m$, then it has received a
Ready message from at least $2f+1$ nodes. Among them, at least $f+1$ are
correct nodes, who have an adopt certificate (consists of $2f+1$ signed Echo
messages) for $m$. Therefore they will return BBCA-adopt upon probing.

For the second part of the lemma, assume that some correct node $p$ BBCA-
completes a message $m$. $p$ has received $2f+1$ Ready messages, of which
$f+1$ are from the correct nodes. For the group of $f+1$ nodes which return
BBCA-noadopt, there is at least one node that also has sent the aforementioned
Ready message, which is contradictory because a node cannot both send a ready
message and returns BBCA-noadopt, in any order (in the pseudocode, probing
will mark $\mathit{abort}\leftarrow\textsc{true}$, preventing the node from
sending Ready; and after sending Ready, probing will always return the adopted
message).

######  Lemma 4 (Integrity)

If a correct node BBCA-adopts or BBCA-completes a message $m$ for instance
$\mathit{bid}$ and the sender $p$ is correct, then $p$ has previously invoked
$\textsc{BBCA-broadcast}(\mathit{bid},m)$.

###### Proof

Correct nodes only broadcast Echo messages for an Init message from the
instance sender, so a completed message must have been initially sent in Init
message, sent by $p$ upon the invocation of BBCA-broadcast.

##  7 BBCA-Chain Correctness

###  7.1 Safety

To prove consistency, we need to show that nodes commit the same blocks in the
same order, or equivalently, if two correct nodes commit backbone blocks
$B_{1}$ and $B_{2}$ respectively at the same height, then $B_{1}=B_{2}$.

###### Lemma 5

There can be at most one unique $B$ per view obtaining a complete certificate
and/or an adopt certificate (for all correct nodes).

###### Proof

The lemma follows directly from BBCA consistency, as in each view correct
nodes initialize a single BBCA instance.

###### Lemma 6

Suppose a node $p$ commits a backbone block $B_{v}$ for view $v$. Then there
exists a view $v^{\prime}$ where $v^{\prime}\geq v$, such that $p$ has BBCA-
completed a block $B_{v^{\prime}}$ at view $v^{\prime}$ and such that there is
a causal chain of complete certificates or adopt certificates of backbone
blocks from $B_{v^{\prime}}$ back to $B_{v}$.

###### Proof

Nodes process commit blocks in strictly increasing views, iterating back to
their last committed view. The lemma follows immediately from the code:
procedure tryCommit is invoked only upon BBCA-complete, and iterates backward
through blocks in the $\mathit{finalized}$ array, each of which has a complete
or an adopt certificate.

###### Lemma 7

If two correct nodes commit backbone blocks $B_{v}$, $B_{v}^{\prime}$
respectively for view $v$, then $B_{v}=B_{v}^{\prime}$.

###### Proof

The lemma follows immediately by putting Lemmata 6 and 5 together.

######  Lemma 8 (Consistency)

If a correct node $p$ commits $B_{v}$ for some view $v$, and another correct
node $q$ commits any $C_{w}$ for view $w\geq v$, then $q$ commits $B_{v}$ for
view $v$.

###### Proof

Let $v^{\prime}$ be the lowest view where $v^{\prime}\geq v$ for which $p$
BBCA-completes some block $B_{v^{\prime}}$ ($v^{\prime}$ exists by Lemma 6).
Likewise, let $w^{\prime}$ be the lowest view where $w^{\prime}\geq v$ for
which $q$ BBCA-completes some block $C_{w^{\prime}}$ (likewise, $w^{\prime}$
exists). Without loss of generality, assume $w^{\prime}\geq v^{\prime}$.

If $w^{\prime}=v^{\prime}$, then and by Lemma 7,
$C_{w^{\prime}}=B_{v^{\prime}}$. Otherwise, $w^{\prime}>v^{\prime}$.

When $q$ iterates from view $w^{\prime}$ back to view $v$, it goes through
view $v^{\prime}$. By assumption, $p$ BBCA-completed $B_{v^{\prime}}$ and $q$
did not obtain a complete certificate for view $v^{\prime}$. Therefore, $q$
either adopts $B_{v^{\prime}}$ or skips view $v^{\prime}$. However, by the
Complete-Adopt property of BBCA, $q$ cannot skip with $2f+1$
$\langle\textsc{BBCA-noadopt}\rangle$ for view $v^{\prime}$, since $p$ has
BBCA-completed a block in view $v^{\prime}$ (by BBCA’s Commit-Adopt
property).Therefore, $q$ commits some backbone block in view $v^{\prime}$ via
an adopt certificate, and By Lemma 5 this block must be $B_{v^{\prime}}$.

In both scenarios, by Lemma 7, both $p$ and $q$ iterate from $B_{v^{\prime}}$
back to $B_{v}$ through an identical sequences of committed backbone blocks.

###  7.2 Liveness

We assume a view synchronization protocol which guarantees that, after GST,
all correct nodes enter view $v$ within bounded time $\Delta_{sync}$. Section
7.3 shows BBCA-Chain can satisfy this property without incurring extra
communication, using the DAG causal ordering of blocks by all nodes.

A view-timer $\Gamma$ with duration $\Delta_{\Gamma}$ is picked such that
after GST, if $2f+1$ correct nodes enter view $v$ at time $t$ then $\Gamma$
suffices for the leader of view $v$ to

(i) Enter view $v$,

(ii) Broadcast a backbone block via BBCA, and reach BBCA-complete at all
$2f+1$ correct nodes.

I.e. $\Gamma\geq\Delta_{sync}+3\Delta$, where $\Delta$ the maximum network
delay after GST.

###### Lemma 9

After GST, if the leader of view $v$ is correct, BBCA-complete is reached in
view $v$ by all correct nodes.

###### Proof

Let as assume that we are after GST and the first correct node $p$ to ender
view $v$ does so at time $t$. By Lemma 14, all correct nodes, including the
leader, enter view $v$ the latest at time $t+\Delta_{sync}$. Therefore the
leader broadcasts a block $B_{v}$ the latest at time $t+\Delta_{sync}$, that
will get accepted inside BBCA (we assume the leader is correct), the latest at
$t+\Delta_{sync}+\Delta$ by all correct nodes. The latest at
$t+\Delta_{sync}+2\Delta$ all correct nodes will have received $2f+1$ Echo
messages and the latest at $t+\Delta_{sync}+3\Delta$ all correct nodes will
have BBCA-completed $B_{v}$, i.e, before $\Gamma$ expires for $p$.

###### Lemma 10

For every view $v$, a correct node eventually enters the view. Furthermore,
upon entering view $v$, the node has received one of the following from view
$v-1$: (i) a commit certificate of the backbone block of view $v-1$, (ii) an
adopt certificate of the backbone block of view $v-1$, (iii) $2f+1$ signed
noadopt of the backbone block of view $v-1$.

###### Proof

We prove this by induction. After entering view $v$, each node broadcasts a
new-view block for view $v-1$ either upon receiving messages from others
(including possibly the backbone block for view $v-1$), or its own view $v-1$
timer expires. Since eventually all correct nodes send new-view blocks, a node
$p$ enters view $v$ when one of the following conditions holds:

  * •

$p$ received $2f+1$ new-view messages for view $v-1$ carrying (signed) BBCA-
noadopt (for view $v-1$).

  * •

$p$ received a commit-certificate for view $v-1$.

  * •

$p$ received a new-view message carrying an adopt-certificate for view $v-1$.

###### Lemma 11

For every view $v$ a correct node either commits a block, or skips the view.

###### Proof

By Lemma 10, eventually every correct node enters $v$ having received a “skip”
certificate ($2f+1$ noadopt’s), a commit certificate, or an adopt certificate.
By Lemma 9, after GST eventually there is a view $v^{\prime}\geq v$ whose
leader is correct and all nodes BBCA-complete the backbone block of
$v^{\prime}$. A node then invokes tryCommit which iterates backward starting
at the committed block of view $v^{\prime}$. Starting with the block that
becomes committed in view $v^{\prime}$, each committed block $B$ encountered
in the loop determines a block $B_{prev}$ that immediately precedes $B$ in the
sequenced $\mathit{backbone}$:

  * •

If $B.\mathit{ref}$ references a commit or an adopt certificate, then
$B_{prev}$ is the certified block.

  * •

Otherwise, $B_{prev}$ is the block whose view is maximal among the commit and
adopt certificates which are referenced by blocks in
$B.\mathit{ref}.\mathit{noadopted}$.

Then, all the views between $B_{prev}$ and $B$ becomes finalized as skipped;
$B_{prev}$ becomes committed and the next loop continues iterating backward
from it.

The loop completes when all non-finalized views $\leq v^{\prime}$ become
finalized. Therefore, if view $v$ hasn’t been finalized already, it will
become finalized either as skipped or committed.

######  Lemma 12 (Chain growth)

The chain of blocks grows infinitely, i.e., eventually, all correct nodes
commit a backbone block for some view $v$.

###### Proof

By Lemma 9 and the assumption that $\textsc{GetProposer}(v)$ returns a correct
leader for some view $v$ after GST, all correct nodes BBCA-complete some
backbone block $B_{v}$ for view $v$. We therefore need to show that eventually
$B_{v}$ will also be committed. By Lemma 11, for every view $v^{\prime}<v$
either some block is committed, or the view is skipped. Therefore, $v$ will be
recursively committed.

######  Lemma 13 (Censorship resistance)

After GST, if a correct node broadcasts a block $b$, then the block will be
eventually committed.

###### Proof

If the block is a backbone block, then by Lemma 9, $b$ gets BBCA-completed for
some view $v$. By Lemma 11, for all views $v^{\prime}<v$ eventually, either
some block gets committed or the view is skipped and, therefore, eventually
$b$ gets committed. Otherwise the block will be committed as a causal
reference of a backbone block.

###  7.3 View Synchronization

######  Lemma 14 (View Synchronization)

Let $p$ be the first correct node enters view $v+1$ at time $t$ after GST.
Then all correct nodes view $v+1$ the latest at time $t+\Delta$, where
$\Delta$ is the maximum network delay.

###### Proof

We examine exhaustively all ways in which $p$ may enter view $v+1$.

  1. 1.

$p$ BBCA-completes the backbone block of view $v$. In this case $p$ broadcasts
a new-view block for $v+1$, which all correct nodes receive the latest after
$\Delta$. This allows them to enter view $v+1$ themselves.

  2. 2.

$p$ receives a new-view block for view $v+1$ which references a completed
backbone block for view $v$. As in the previous case, $p$ broadcasts a new-
view block for $v+1$, and all correct nodes enter view $v+1$ the latest after
$\Delta$.

  3. 3.

$p$ receives a new-view block for view $v+1$ which references an adopted
backbone block for view $v$. Again, $p$ broadcasts a new-view block for $v+1$,
and all correct nodes enter view $v+1$ the latest after $\Delta$.

  4. 4.

$p$ probes BBCA (either due to a timeout, or after receiving $f+1$ new-view
messages with noadopt) which returns BBCA-adopt. In this case $p$ broadcasts a
new-view block for $v+1$ with an adopt certificate, which all correct nodes
receive the latest after $\Delta$ and enter view $v+1$ themselves.

  5. 5.

$p$ probes BBCA (either due to a timeout, or after receiving $f+1$ new-view
messages with noadopt) which returns BBCA-noadopt. By the assumption that $p$
is the first correct node who enters view $v+1$, $p$ has received $2f+1$ new-
view messages with a $\langle\textsc{noadopt},v+1\rangle$ signature. At least
$f+1$ of them are from correct nodes. Let’s assume that the $f+1^{th}$ correct
node who sent a new-view message with $\langle\textsc{noadopt},v+1\rangle$ did
so at time $\tau$. Therefore, all corrects nodes receive $f+1$ new-view
messages by time at most $\tau+\Delta$ and send a new-view message themselves.
Therefore, all correct nodes receive in total $2f+1$ messages by time
$\tau+2\Delta$ and enter view $v+1$, that is at most $\Delta$ after $p$.

##  8 Related Work

The focus of our work is solving consensus and state-machine-replication (SMR)
while allowing underlying parallel communication for high throughput.

We therefore review SMR solutions along a spectrum: on one extreme are
traditional leader-based SMR protocols, in the middle are solutions that
leverage causality to parallelize certain aspects, and at the far extreme are
leaderless/multi-leader solutions that commit proposals at bulk.

PBFT [8], a landmark in BFT solutions introduced two decades ago, emphasizes
optimistically low latency. It established the view-by-view “recipe” where the
leader of a new-view submits a proposal with a _justification proof_. This
approach for justifying a new leader proposal after a view-change is the
foundation of all protocols in the PBFT family, including FaB [31], Zyzzyva
[26], Aardvark [10], and SBFT [22]. Notably, the last builds on the pioneering
works of Cachin et. al [6] and Reiter [34], to linearize the common case
message complexity by employing signature aggregation. Still, the view-change
justification proof is complex to code and incurs quadratic communication
complexity. Tendermint [4] introduced a simpler view-change sub-protocol than
PBFT, later adopted in Casper [5]. HotStuff [43] harnesses and enhances the
simple Tendermint view-change via an extra phase; several advances to HotStuff
[24, 41, 20, 1, 21] eventually led to HotStuff-2 [29] which successfully
removes the requirement of an extra phase.

Follow-up research works [11, 42, 23, 38, 39, 27] focused on improving
throughput by enabling multiple nodes to act as leaders in parallel, and
therefore, alleviate the computational and communication single-leader
bottleneck of previously mentioned works. Still, those protocols require
similar view-change mechanisms with their single-leader counterparts,
resulting in periods with underutilized network resources. This issue was
addressed by DAG-based solutions which employ causal ordering and pipelining
to decouple consistent block dissemination from ordering.

One class of DAG-based algorithms are asynchronous and leaderless and include
DAG-based solutions that date back to the 1990’s as well as recent protocols
for blockchains [15, 32, 2, 25, 14]. Recently, a class of DAG-based algorithms
emerged that borrow the leader-based approach of algorithms like PBFT/HotStuff
and optimize performance for partial synchrony settings. These DAG-based
consensus protocols [19, 13, 25, 14, 37, 30] form a backbone sequence of
backbone blocks on the DAG. However, as discussed previously, the current
generation of DAG-riding solutions incurs increased latency and a complicated
logic. Very recently there has been an effort to reduce latency by
interleaving two instances of Bullshark on the same DAG [33, 36], resulting in
one CBC latency reduction. Cordial Miners is an alternative approach to
reducing latency in DAG protocols by using only causal Best-Effort Broadcast
(BEB).

BBCA-Chain borrows the key ideas that deal with partial synchrony from the
above works, modifying it to substantially reduce latency and simplify the
logic. Importantly, BBCA-Chain gets rid of specialized layers altogether,
leading to an arguably simpler implementation. It further reduces latency by
integrating voting in the BBCA broadcast of a backbone block and by allowing
non-backbone blocks to use BEB.

A key ingredient in DAG-based solutions is the notion of the secure, causal,
and reliable broadcast, introduced by Reiter and Birman [35], and later
refined by Cachin [6] and Duan et al. [16]. This primitive was utilized in a
variety of BFT replicated systems, but not necessarily in the form of “zero
message overhead” protocols riding on a DAG. Several of these pre-blockchain-
era BFT protocols are DAG based, notably Total [32] and ToTo [15], both of
which are BFT solutions for the asynchronous model.

GradedDAG [12] is a randomized consensus protocol that inspired us to abstract
a core primitive whose strong guarantees simplify the DAG-level consensus
logic. GradedDAG uses GRBC, an RBC variant that yields graded output, to
facilitate consensus, whereas BBCA-Chain uses BBCA with Complete-Adopt exposed
from a CBC primitive whose weaker properties suffice for consensus. BBCA-Chain
operates under the partial synchrony model whereas GradedDAG is asynchronous.

The intuition behind Complete-Adopt is a notion at the heart of consensus
solutions, familiar to “Commit-Adopt” by Gafni et al. in [18]. In the context
of BBCA, it stipulates that a broadcast can complete only after a quorum has
locked it. Although many forms of broadcasts have been formulated, including
gradecast with multiple grades of output, to our knowledge no previous
broadcast primitive has been formulated with a Complete-Adopt guarantee.

Finally, we remark that data availability is an orthogonal problem which
already in PBFT [8] was addressed by batching transactions hashes into blocks
and form consensus on blocks. Recently, Narwhal [14] decoupled data
availability from total ordering for DAG-based protocols. In parallel,
DispersedLeder [42] and HotShot [40] proposed a data-availability component
which pre-disseminates transactions and obtains a certificate of uniqueness
and availability.

## References

  * [1] M. Abspoel, T. Attema, and M. Rambaud.  Malicious security comes for free in consensus with leaders.  Cryptology ePrint Archive, 2020.
  * [2] L. Baird.  The swirlds hashgraph consensus algorithm: Fair, fast, Byzantine fault tolerance.  Swirlds Tech Reports SWIRLDS-TR-2016-01, Tech. Rep, 34:9–11, 2016\.
  * [3] G. Bracha and S. Toueg.  Asynchronous consensus and broadcast protocols.  J. ACM, 32(4):824–840, 1985.
  * [4] E. Buchman.  Tendermint: Byzantine fault tolerance in the age of blockchains.  PhD thesis, University of Guelph, 2016.
  * [5] V. Buterin and V. Griffith.  Casper the friendly finality gadget.  arXiv preprint arXiv:1710.09437, 2017.
  * [6] C. Cachin, K. Kursawe, F. Petzold, and V. Shoup.  Secure and efficient asynchronous broadcast protocols.  In Annual International Cryptology Conference, pages 524–541. Springer, 2001.
  * [7] C. Cachin, K. Kursawe, and V. Shoup.  Random oracles in constantipole: practical asynchronous byzantine agreement using cryptography.  In Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, pages 123–132, 2000.
  * [8] M. Castro and B. Liskov.  Practical Byzantine fault tolerance.  In M. I. Seltzer and P. J. Leach, editors, Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22-25, 1999, pages 173–186. USENIX Association, 1999.
  * [9] P. Civit, M. A. Dzulfikar, S. Gilbert, V. Gramoli, R. Guerraoui, J. Komatovic, and M. Vidigueira.  Byzantine consensus is $\theta$(n²): The Dolev-Reischuk bound is tight even in partial synchrony!  In International Symposium on Distributed Computing, 2022.
  * [10] 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, NSDI’09, page 153–168. USENIX Association, 2009\.
  * [11] T. Crain, C. Natoli, and V. Gramoli.  Red belly: A secure, fair and scalable open blockchain.  In 2021 IEEE Symposium on Security and Privacy (SP), pages 466–483. IEEE, 2021.
  * [12] X. Dai, Z. Zhang, J. Xiao, J. Yue, X. Xie, and H. Jin.  GradedDAG: An asynchronous DAG-based BFT consensus with lower latency.  In 42nd International Symposium on Reliable Distributed Systems, SRDS 2023, Marrakech, Morocco, September 27-29, 2023. IEEE, 2023.
  * [13] G. Danezis and D. Hrycyszyn.  Blockmania: from block dags to consensus.  arXiv preprint arXiv:1809.01620, 2018.
  * [14] G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman.  Narwhal and tusk: a dag-based mempool and efficient BFT consensus.  In Y. Bromberg, A. Kermarrec, and C. Kozyrakis, editors, EuroSys ’22: Seventeenth European Conference on Computer Systems, Rennes, France, April 5 - 8, 2022, pages 34–50. ACM, 2022.
  * [15] D. Dolev, S. Kramer, and D. Malki.  Early delivery totally ordered multicast in asynchronous environments.  In FTCS-23 The Twenty-Third International Symposium on Fault-Tolerant Computing, pages 544–553. IEEE, 1993.
  * [16] S. Duan, M. K. Reiter, and H. Zhang.  Secure causal atomic broadcast, revisited.  In 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 61–72. IEEE, 2017.
  * [17] C. Dwork, N. A. Lynch, and L. J. Stockmeyer.  Consensus in the presence of partial synchrony.  J. ACM, 35(2):288–323, 1988.
  * [18] E. Gafni.  Round-by-round fault detectors (extended abstract) unifying synchrony and asynchrony.  In Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pages 143–152, 1998.
  * [19] A. Gagol, D. Lesniak, D. Straszak, and M. Swietek.  Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes.  In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Switzerland, October 21-23, 2019, pages 214–228. ACM, 2019.
  * [20] R. Gelashvili, L. Kokoris-Kogias, A. Sonnino, A. Spiegelman, and Z. Xiang.  Jolteon and Ditto: Network-adaptive efficient consensus with asynchronous fallback.  In Financial Cryptography and Data Security: 26th International Conference, FC 2022, pages 296–315. Springer, 2022.
  * [21] N. Giridharan, H. Howard, I. Abraham, N. Crooks, and A. Tomescu.  No-commit proofs: Defeating livelock in BFT.  Cryptology ePrint Archive, 2021.
  * [22] G. Golan Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. Reiter, D. Seredinschi, O. Tamir, and A. Tomescu.  SBFT: A scalable and decentralized trust infrastructure.  In Proceedings - 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2019, Proceedings - 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2019, pages 568–580, 2019.
  * [23] S. Gupta, J. Hellings, and M. Sadoghi.  RCC: resilient concurrent consensus for high-throughput secure transaction processing.  In 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19-22, 2021, pages 1392–1403. IEEE, 2021\.
  * [24] M. M. Jalalzai, J. Niu, C. Feng, and F. Gai.  Fast-HotStuff: A fast and resilient HotStuff protocol.  arXiv preprint arXiv:2010.11454, 2020.
  * [25] I. Keidar, E. Kokoris-Kogias, O. Naor, and A. Spiegelman.  All you need is DAG.  In A. Miller, K. Censor-Hillel, and J. H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 165–175. ACM, 2021.
  * [26] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong.  Zyzzyva: Speculative Byzantine fault tolerance.  In Proceedings of Twenty-First ACM SIGOPS Symposium on Operating Systems Principles, SOSP ’07, page 45–58. Association for Computing Machinery, 2007.
  * [27] K. Lev-Ari, A. Spiegelman, I. Keidar, and D. Malkhi.  Fairledger: A fair blockchain protocol for financial institutions.  In International Conference on Principles of Distributed Systems, 2019.
  * [28] A. Lewis-Pye.  Quadratic worst-case message complexity for state machine replication in the partial synchrony model.  ArXiv, abs/2201.01107, 2022.
  * [29] D. Malkhi and K. Nayak.  Hotstuff-2: Optimal two-phase responsive bft.  Cryptology ePrint Archive, 2023.
  * [30] D. Malkhi and P. Szalachowski.  Maximal extractable value (MEV) protection on a DAG.  CoRR, abs/2208.00940, 2022.
  * [31] J.-P. Martin and L. Alvisi.  Fast Byzantine consensus.  Dependable and Secure Computing, IEEE Transactions on, 3:202– 215, 08 2006.
  * [32] L. E. Moser and P. M. Melliar-Smith.  Byzantine-resistant total ordering algorithms.  Information and Computation, 150(1):75–111, 1999.
  * [33] Mysten Labs.  Private communication, 2023.
  * [34] M. K. Reiter.  Secure agreement protocols: Reliable and atomic group multicast in Rampart.  In Proceedings of the 2nd ACM Conference on Computer and Communications Security, CCS ’94, page 68–80. Association for Computing Machinery, 1994.
  * [35] M. K. Reiter and K. P. Birman.  How to securely replicate services.  ACM Transactions on Programming Languages and Systems (TOPLAS), 16(3):986–1009, 1994.
  * [36] A. Spiegelman, B. Aurn, R. Gelashvili, and Z. Li.  Shoal: Improving dag-bft latency and robustness.  arXiv preprint arXiv:2306.03058, 2023.
  * [37] A. Spiegelman, N. Giridharan, A. Sonnino, and L. Kokoris-Kogias.  Bullshark: DAG BFT protocols made practical.  In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 2705–2718, 2022.
  * [38] C. Stathakopoulou, T. David, M. Pavlovic, and M. Vukolic.  [solution] Mir-BFT: Scalable and robust BFT for decentralized networks.  J. Syst. Res., 2(1), 2022.
  * [39] C. Stathakopoulou, M. Pavlovic, and M. Vukolic.  State machine replication scalability made simple.  In Y. Bromberg, A. Kermarrec, and C. Kozyrakis, editors, EuroSys ’22: Seventeenth European Conference on Computer Systems, Rennes, France, April 5 - 8, 2022, pages 17–33. ACM, 2022.
  * [40] E. Systems.  The espresso sequencer: HotShot consensus and tiramisu data availability.  arXiv preprint arXiv:2306.03058, 2023.
  * [41] T. D. Team.  DiemBFT v4: State machine replication in the Diem blockchain.  https://developers.diem.com/docs/technical-papers/state-machine-replication-paper, 2021\.
  * [42] L. Yang, S. J. Park, M. Alizadeh, S. Kannan, and D. Tse.  DispersedLedger: High-Throughput Byzantine consensus on variable bandwidth networks.  In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), pages 493–512, 2022.
  * [43] 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 Symposium on Principles of Distributed Computing, PODC ’19, page 347–356. Association for Computing Machinery, 2019.