20

#  $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$: Asynchronous
Consensus As Fast As Pipelined BFT

Yuan Lu
Institute of Software
Chinese Academy of Sciences
<EMAIL_ADDRESS>Zhenliang Lu

<EMAIL_ADDRESS>Qiang Tang
School of Computer Science
The University of Sydney
<EMAIL_ADDRESS>
###### Abstract

The emergence of decentralized applications puts unprecedented demand of
deploying Byzantine agreement protocols in the open Internet. The simpler
deterministic protocols have to rely on timing assumptions that all messages
to be delivered within some (known or unknown) time bound, which may not
always hold in the open network. On the other hand, asynchronous protocols are
robust, but still substantially more complicated and slower due to inherent
usage of randomizations.

Optimistic asynchronous atomic broadcast (Kursawe and Shoup, 2002; Ramasamy
and Cachin, 2005) has been proposed to leverage the “hybridization” art to
improve the performance of asynchronous protocols while remaining their robust
liveness against unstable network. The basic idea is to run faster
deterministic protocols in the optimistic case when network condition is good,
while safely fallback to a pessimistic path running asynchronous protocols
when the protocol fails to proceed.

Unfortunately, the existing fallback mechanisms directly use a heavy tool of
multivalued asynchronous validated Byzantine agreement (MVBA). The resulting
fallback mechanisms would become even less efficient than the underlying
asynchronous protocol. When network is fluctuating, the benefit of adding the
deterministic protocol for the optimistic case will be directly eliminated
since the inefficient fallback may happen frequently.

We present a new generic framework for practical optimistic asynchronous
atomic broadcast. In particular, we give a new abstraction of the optimistic
case protocol, which prepared us to design a highly efficient fallback
mechanism, and can be instantiated easily. The latter not only reduces the
communication complexity by a factor of $\mathcal{O}(n)$, but also replace the
cumbersome MVBA protocol with a type of binary agreement only. We give a
detailed security analysis.

Moreover, we give concrete instantiations of our framework, and implemented
the protocol. Our extensive experimental results show that our new fallback
mechanism add minimal overhead, thus the overall protocol would be as fast as
the pipelined protocols in the good case, and similar to the asynchronous
protocol in the extremes case (when network never becomes stable). As long as
there are some fraction of stable period, our protocol can enjoy the best of
both deterministic (partially) synchronous and asynchronous protocols.

##  I Introduction

The explosive popularity of blockchain and decentralized applications [1, 2,
3] create an unprecedented demand of deploying robust yet still highly
efficient Byzantine fault-tolerant (BFT) protocols over the open Internet [4,
5], the dynamic nature (e.g., unreliable network links, large network delays
due to attacks) of which raises new fundamental challenges for BFT protocols.
In case messages might be arbitrarily delayed due to network asynchrony, the
classical FLP “impossibility” [6] stated that no deterministic protocol can
ensure both safety and liveness in such an asynchronous network.

Timing assumption? Dilemma between responsiveness and robust liveness! Given
the FLP “impossibility”, one common method to salvage the deterministic
protocols is to introduce timing assumptions, as in many state-of-the-art
(partial) synchronous BFT protocols [7, 8, 9, 10, 11, 12, 13, 4]. For example,
partially synchrony assumes that the adversary can fully control the
communication network for at most an unknown bounded period $GST$, so the
network always can stabilize to be eventually synchronous and then deliver
messages to any destination party in a known delay upper bound $\Delta$.

Though many of these (partially) synchronous protocols have demonstrated high
performance when the network can luckily stay in synchronous periods [8, 9,
10, 11, 12, 13, 4], they lack assurance on the critical liveness property
during $GST$. That means, when the network is hard to stabilize and are rarely
synchronous, these protocols might grind to a “halt” (as formally shown in
[14]) and generate a large number of messages without any throughput.

What’s worse, the fragile liveness of synchronous (and partially synchronous)
protocols caused by timing assumptions is not merely a theoretic possibility.
The engineers have to carefully tweak their timeout policy for liveness, e.g.,
using some not-so-small time-out parameter $\tau$ for the estimated network
delay (or adaptively increasing $\tau$) to make the synchronous assumption to
hold (i.e., ensuring $\tau\geq\Delta$) with a larger probability for the
underlying network.

Unfortunately, this gives up a responsiveness property that the performance of
the protocol is only depending on the actual network delay. It might even lead
up to serious worries of performance degradation. Indeed, as shown in the
classical result of Dolev-Strong [15], all deterministic protocols, inherently
have an average confirmation delay bounded by $\mathcal{O}(\Delta)$, even if
the network may actually be synchronous [15, 16]. To see simple examples, in
the leader-based protocols such as PBFT and HotStuff, malicious leaders can
always withhold their outgoing messages up to $\Delta$, causing that the
adversary-influencing average latency is related to $\Delta$ and the
throughput is directly deteriorated.

That said, for the deterministic (partially) synchronous protocols, although
tuning time-out parameters larger can make eventual synchrony possible and
promise more robust liveness, it unfortunately makes them not responsive and
even causes potential performance deterioration, resulting in an inherent
liveness-responsiveness dilemma.

Randomized asynchronous BFT? Robustness with a high price! In contrast to
partially-synchronous or synchronous BFT, asynchronous protocols can ensure
responsiveness without any form of timing assumptions. In particular, the
transactions at top of each party’s backlog (a.k.a. tx pool or tx buffer)
would always be output in some time bounded by a polynomial number of
asynchronous rounds, which is only related to the actual network delay
$\delta$ instead of the time-out parameter $\tau$ (or the delay upper bound
$\Delta$), thus realizing robustness and responsiveness simultaneously. Also
it removes the necessity of complicated manual timeout policies and save the
practitioners’ life. Following that, asynchronous BFT protocols become
arguably the most robust candidates for mission-critical replicated services
deployed in the unstable global network.

However, those benefits of asynchronous BFT protocols do not come for free, as
they must run randomized subroutines to bypass the FLP “impossibility”. The
cost of randomization could be large or even prohibitive: essentially none of
the asynchronous protocols has been deployed in practice during the past
decades, until the recent progress of of HoneyBadgerBFT [14] and Dumbo
protocols [17, 18] which provide novel paths to practical asynchronous BFT.

Despite those recent progress on practical asynchronous BFT, they are still
far slower (particularly latency) than the state-of-the-art synchronous
protocols in terms of concrete efficiency. Especially, when the communication
network is mostly stable (e.g., all parties are closed to the Internet
backbone), the state-of-the-art, e.g., pipelined protocols can agree on a
block per several rounds at best, but even the currently most efficient
asynchronous protocol Dumbo has to spend dozens of asynchronous rounds on
average to output a block at best. Those inferior performance of these
randomized asynchronous protocols is (inherently) due to the costly “common
coin” subroutine in which all the peers jointly generate randomness on the
fly, and essential multi-round repetitions to ensure termination with an
overwhelming probability, facing potential arbitrary delays.

Achieving the best of both? The above issues correspond to a fundamental
“dilemma” lying in the design space of BFT protocols suitable to be deployed
in the open Internet: the cutting-edge deterministic (e.g., pipelined)
partially synchronous protocols might optimistically work very fast but lack
assurances of liveness or promised performance in unstable networks; while
asynchronous protocols, on the contrary, are very robust in arbitrarily bad
networks but unfortunately suffer from sub-optimal concrete performance.

To resolve the “dilemma”, it becomes natural to combine the deterministic
approach and the randomized approach to enhance the performance of
asynchronous protocols on a good day without having the risk of getting
“stuck” (losing liveness) in bad times. The pioneering work of Kursawe-Shoup
[19] back to 2002, and a later improved version Ramasamy-Cachin [20] in 2005,
indeed attempted to “graft” a deterministic “fastlane” 111Sometimes, it is
called optimistic path, or Bolt in the paper to a randomized pessimistic path
through a fallback mechanism (we call pace synchronization, which is similar
to “view changes” in many of the partially synchronous protocols such as PBFT,
but with a slightly more general purpose) 222Many other works consider how to
get a higher tolerance in optimistic (synchronous) case, while we focus on
harvesting the best efficiency without worrying about liveness. See Related
Work for more careful comparisons..

The rationale behind the idea is straightforward: the real wide-area Internet
might optimistically remain in a good condition to deliver messages
synchronously for a while, though it can also suddenly become unstable or even
adversarial.

From a high-level, such a “hybrid” structure proceeds as follows: (i) when the
network is in a good condition (say, with some constant probabilities), and
the leader is honest, the deterministic optimistic path can succeed to offer
high performance similar to the cutting-edge (partially) synchronous
protocols, and (ii) when the optimistic path fails to progress, it can
smoothly fall back into the robust pessimistic path with randomized
executions, so it can tolerate arbitrarily delayed networks to restore
critical liveness and recover to the optimistic case as soon as possible.

More interestingly, such a “hybrid” paradigm for asynchronous BFT might bring
more practical merits. Recall that when deploying (partially) synchronous
protocols in the open Internet, the engineers have to conservatively choose
the timeout parameter (or to adaptively increase it) during the deterministic
executions trying to ensure the synchrony assumption. This in turn degrades
the performance. Now, the fallback mechanisms ensures that liveness can be
safeguarded by the asynchronous protocols in the pessimistic path, so
engineers can aggressively set the timeout parameter according to her
optimistic estimation about benign network conditions for good days only,
making the optimistic path to be unchained and run in full horse-power to be
even responsive.

However, challenges remain to be conquered to make above promising paradigm
actually work in practice.

Limitations of existing asynchronous fallback. Intuitively, when the
optimistic path fails to make progress, a fallback mechanism must be activated
to ensure all honest nodes to: (i) make an agreement on the need of fallback
(common fastlane failure in many nodes); (ii) then reach a consensus on the
current progress (or from which state to continue); (iii) and run asynchronous
protocol (or pessimistic path) to make progress and re-enter the fastlane.
Clearly, the fallback mechanism must be functioning in fully asynchronous
network to ensure robust liveness without relying on any timing assumptions.

Earlier studies [19, 20] demonstrated the theoretic feasibility to implement
the fully asynchronous fallback simply via the asynchronous BFT. More
specifically, from an advanced building block of multi-valued validated
asynchronous Byzantine agreement (MVBA), which can be used to directly
construct an asynchronous BFT [21]. Those MVBA protocols are suffering from
overall at least $\mathcal{O}(n^{3})$ communications (including the recent
[22] when input size depends on $n$, where $n$ is the number of peer nodes)
and dozens of asynchronous rounds. 333Remark that the $\mathcal{O}(n^{3})$
communication may be reduced to $\mathcal{O}(n^{2})$ using the very recent
improvement of asymptotically optimal MVBA construction [18], but the
construction remains costly due to the large number of running rounds. In
contrast, we present a much simpler construction for the fallback that does
not need the heavy MVBA components.

A more severe issue is the following: in real world wide-area network, the
network condition might fluctuate, thus the fallback mechanism could
potentially be triggered frequently. Suppose the fallback procedure is 3 times
slower than the asynchronous protocol (which is indeed the case in existing
work [19]), and the blocks with an even index are output by the asynchronous
protocol, while the blocks with the odd index are generated during the
optimistic case via the synchronous protocol. The latter is simply because
fallback is taken place half of the time. Now the overall protocol actually
has no performance improvement than the asynchronous protocol even sometimes
the deterministic protocol is executted. An easier extreme case example is
when the network is completely asynchronous, adding the fastlane with a safe
fallback mechanism actually at least triples the cost of the asynchronous
protocol than running the latter alone.

It follows that an inefficient fallback would likely eliminate the potential
benefits of introducing faster synchronous protocols in the fastlane, and the
following fundamental practical challenge remains open:

Can we construct an asynchronous consensus protocol with an optimistic
fastlane that can almost always be faster than the underlying asynchronous
protocol? and ideally, such an asynchronous protocol an be as fast as the
(partially) synchronous ones in real-world network environment?

Figure 1: The overview of $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\
}Transformer}$ framework.

###  I-A Our contributions

We give an affirmative answer to the aforementioned question and we propose a
new practical generic framework we call
$\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ (BDT) to attain
randomized asynchronous BFT protocols with optimistic deterministic
executions. In particular, the optimistic case is taken place if the network
is benign (message delivered within a guessed network delay $\tau$ and leader
is honest), and Bolt will be run. If there is no progress can be made using
Bolt, in the pessimistic case, an asynchronous BFT protocol we call Dumbo will
be run. While there is a pace synchronization phase, we call Transformer, will
be executed if enough honest peers do not make progress and would agree on how
to restart. See Fig. 1. More concretely,

  * •

A new abstraction of the fastlane. We formulate a new simple property of
notarizability for the fastlane protocol: in the optimistic case, it performs
as a full-fledged BFT protocol; but if the synchrony assumption sometimes
fails to hold, the notarizability still requires that whenever an honest party
outputs a block $\mathsf{log}[j]$ at position $j$, then at least $f+1$ honest
ones already output a block at the position $j-1$.

This property is critical for preparing Bolt to be paired with a very
efficient Transformer as we will demonstrate below. On the other hand, this
new property is very easy to obtain from the deterministic BFT protocols. We
present two exemplary optimistic path implementations.

The first one is a stable leader version of HotStuff [11] and is appropriate
for the scenarios that favor latency over throughput. The second one is by
sequentially executing (provable) reliable broadcasts (with using erasure code
to reduce the leader’s bandwdith usage) and is more friendly for batching,
thus achieving higher throughput in global Internet.

  * •

Highly efficient pace synchronization. At the core of our BDT framework, it is
a more efficient “pace” synchronization mechanism to enable secure and
practical fallback when the fastlane fails to progress within the guessed
network delay $\tau$. Our technique not only achieves an $\mathcal{O}(n)$
factor improvement to prior results [19, 20], but more importantly, removes
the need of cumbersome MVBA module by reducing the “pace” synchronization
problem to a much simpler specific-purpose asynchronous binary Byzantine
agreement, we call it two-consecutive-valued binary agreement
($\mathsf{tcv\textnormal{-}BA}$ for short). The new agreement of
$\mathsf{tcv\textnormal{-}BA}$ ensures a special validity that: if the honest
parties input one integer or two consecutive integers, the common output shall
be one of the honest input values. We give a very simple construction for this
concrete module by only replacing three lines of the pseudocode of the binary
agreement in [17]. It is essentially optimal, since pace synchronization can
be viewed as a version of BFT protocols itself. This is possible because of
the simple property of notarizability of the fastlane.

On the other hand, the high efficiency of the new pace synchronization allows
the engineers now to aggressively guess the network delay to be a very small
$\tau$, since now the liveness will be based on the pace synchronization and
the pessimistic paths. More importantly, once a node stopped making progress
at some block $i$, and finally recovers at block $i+k$ (for some $k$), he can
obtain all the intermediate blocks. Careful readers may wonder, in some
drastically changing network, the pace synchronization may be executed by some
nodes for multiple times before the network gets stable again. This indeed
will potentially deteriorate the overall improvement of introducing the
fastlane, if the pace synchronization is inefficient (e.g., as slow as the
pessimistic path asynchronous protocol). Luckily, our highly efficient pace
synchronization frees us from this worry.

Indeed, at the end of the pace synchronization, we add a simple check. Except
when all honest peers made no progress at all in the fastlane, thus have to
execute the pessimistic asynchronous protocol to move forward, we let them
switch back to the fastlane immediately. This again is in contrast with
previous works of [19, 20] that the pessimistic protocol will always be run at
the end of fallback, which is often unnecessarily costly.

After all, we give a detailed security analysis for the
$\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ protocol.

  * •

Implementation and extensive tests in real-world environments. We give
instantiations of the BDT framework (with using $\mathsf{Dumbo}$ BFT [17]
444Remark that [17] presents two asynchronous common subset constructions and
hence gives two asynchronous BFT, i.e., Dumbo-1 and Dumbo-2. Since Dumbo-2
employs a better reduction to MVBA and always outperforms the former, we let
Dumbo BFT (or Dumbo) refer to Dumbo-2 through the paper. as the pessimistic
backup), and implement the whole protocol.

We conduct extensive experiments to demonstrate its real-world
applicabilities. Two optimistic paths are implemented, one of which is based
on stable leader HotStuff and the other of which is based on causal broadcast
by sequentially executing provable RBC. We compare these two BDT
implementations to Dumbo BFT and HotStuff BFT. For fair comparison, we
implement them in the same language with same cryptographic libraries and
deploy them in the same test environment consisting of 100 EC2 c5.large
servers evenly distributed across sixteen AWS regions in five different
continents.

TABLE I: Highlights of performance comparison of BDT, HotStuff, and Dumbo
across 100 EC2 c5.large servers in five continents

|  | Best case
---
Fastlanes always complete
| Worst case
---
Fastlanes always fail
|  | BDT-HS∗
---
| BDT-RBC†
---
HotStuff§ |  | BDT-Timtout‡
---
Dumbo
| Basic latency
---
(sec)
0.44 | 0.67 | 0.42 | 21.95 | 16.36
| Peak throughput
---
(tps)
9253 | 18234 | 10805 | 18806 | 21242

∗ BDT-HS runs stable-leader HS for 50 blocks and then run pace sync.
† BDT-RBC runs RBC for 50 blocks and then invokes pace sync.
‡ BDT-Timeout waits 2.5 sec before pace sync and finally runs Dumbo.
§ We remark following reasons why HotStuff’s performance is different from
[11]: (i) we test in global Internet among 16 AWS regions across five
continents which has significantly larger message latency; (ii) we let all BFT
including HotStuff to make agreement on 250-byte transaction instead of
32-byte transaction hash; (iii) for fair comparison, we use a single-core non-
blocking network layer written in Python for all BFT with using gevent for
concurrent tasks, differing from optimized communication layer in [11].

Some highlight results are: (i) when the optimistic path always fails to
progress, the throughput of BDT remains 90% of Dumbo BFT’s and is close to
20,000 transaction per second (where each transaction is 250-byte), even
conditioned on that we do let BDT wait as long as 2.5 seconds in the
optimistic path before falling back to amplify the extra cost; (ii) when the
optimistic path can always keep on delivering blocks in time, the BDT
implementation based on stable leader HotStuff attains a basic latency about
only 0.3 second (i.e., less than 3% of Dumbo’s and nearly same to HotStuff’s),
even if we do intentionally raise frequent pace synchronizations after every
50 optimistic blocks to amplify the average latency. Those at least
demonstrate BDT can maintain robust performance in bad cases and achieve much
lower latency in good cases. More evaluations to understand the scenarios in-
between are presented and carefully discussed in Section VII.

Technical overview. We briefly overview the ideas of designing an asynchronous
fallback and new observations for our new designs.

Prior technique. In the optimistic case, when messages are delivered within a
guessed time parameter $\tau$ and the leader is honest, it is intuitive that
we may consider directly deploying a stable leader version of a (partially)
synchronous broadcast protocol. When sufficient nodes feel the optimistic path
is not making fast enough progress (or no progress at all), they could start
the pace synchronization to jointly determine how many blocks are deed
optimistically outputted so they can sync up to here, and more importantly,
this vote shall not rollback too many optimistic blocks; otherwise, the
confirmation of optimistic paths would be slowed down. For example, if $k$
optimistic blocks could be rolled back at worst, then an optimistic block can
be confirmed for sure only after $k$ more blocks output.

To bound the rollback of optimistic blocks, prior studies let the honest
parties sign and broadcast their optimistic paces to the whole network, then
each party can wait $n-f$ such pace-signature pairs and take them as input to
invoke a MVBA instance, as such all parties would invoke the MVBA instance and
a set of $n-f$ valid pace-signature pairs would eventually return to all
honest parties. Since each signed pace is also attached with a small proof
attesting that at least $n-2f$ honest parties deed output its immediately
precedent block, so the parties can choose the maximum pace out of the output
set of MVBA minus one as the final common pace of optimistic path to sync up,
which would simply bound the rollback of optimistic path because the MVBA
result contains at least one honestly signed pace that is at most one block
later than the tail block of the optimistic path.

Our methodology. We realize that the above “pace” synchronization of using a
whole set of $n-f$ pace-signature pairs as MVBA input is unnecessary. At the
core of the $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$
framework, we provide a highly efficient alternative “pace” synchronization
mechanism as fast as binary agreement.

Our main observation lies in the fact that: there are at least $n-2f$ honest
parties that stay in the latest two optimistic blocks, so once all parties
receive $n-f$ valid pace-signature pairs, they can simply compute the maximum
among these paces. Thanks to the “notorizability”, they would get either the
same value or two consecutive integers, and our task of “pace” synchronization
is therefore reduced to make the honest parties choose one common integer out
of those two unknown consecutive values. To this end, we propose and construct
a novel asynchronous Byzantine agreement primitive to solve the specific issue
of agreeing between two uncertain consecutive values. The construction has
message patterns and execution flows exactly same to the state-of-the-art
binary agreement protocol in [17] and only has three different lines in
pseudocode for checking slightly updated “if-else” conditions.

Moreover, thanks to the novel efficient pace synchronization mechanism, we now
can adopt some more aggressive optimistic tactics as follows. First, different
from [19] that keeps on running optimistic path until it becomes problematic,
we can proactively and even frequently raise “pace” synchronizations once the
optimistic path has made enough progresses, which is important when the
optimistic path is leader-based. Second, different from [19, 20] where the
pessimistic path is always executed after “pace” synchronization, we now can
invoke the pessimistic path only if the optimistic path is completely failed
to output anything, i.e., even if the optimistic path seemingly goes
problematic during the course of executing, we would keep on trying the
optimistic path again after “pace” synchronization as long as it remains to
return some minimal output (e.g., one single block).

###  I-B Related Work

In the past decades, most of asynchronous BFT protocols are theoretical in
nature, and no practical feasibility was shown until recent works (i.e.,
HoneyBadger [14], Dumbo [17], VABA [22], BEAT [23], Dumbo-MVBA [18]). They
don’t rely on time assumptions and enjoy responsiveness; however, in order to
obtain these benefits, they often have large latency (much larger than the
partially synchronous protocols) due to dozens of rounds incurred by
randomization.

The previous mentioned KS02 [19] and RC05 [20] demonstrated theoretical
feasibility for the asynchronous fallback, however, as discussed above, their
framework and instantiations are both inefficient that may not bring the
promised benefits of introducing the deterministic optimistic path.

Several prior works [24, 16, 25, 10, 26] consider (partial) synchronous
protocols that achieve optimistic responsiveness that the protocols are
responsive when some special conditions were satisfied. Our protocol will be
responsive all the time.

Except that, there also some literature [27, 28, 29, 30] focuses on using
hybrid mechanism of synchronous and asynchronous protocols for stronger
security guarantees and particularly higher fault tolerance. These line of
works mainly focuses on designing asynchronous protocols that can tolerate up
to $n/2$ corruptions in the optimistic synchronous case, and tolerate $n/3$
corruptions as usual in asynchronous cases. Our work instead aims for gaining
efficiency improvements.

##  II Preliminaries

Collision-resistance hash function. A hash function
$\mathcal{H}:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{\lambda}$ is said to be
collision-resistant, if no probabilistic polynomial algorithm adversary can
generate a couple of distinct values $x_{1}$ and $x_{2}$ subject to
$\mathcal{H}(x_{1})=\mathcal{H}(x_{2})$ except with negligible probability.

Non-interactive threshold signature. A non-interactive $(t,n)$-threshold
signature scheme $\mathsf{TSIG}$ is a tuple of algorithms/protocols involving
$n$ parties $\\{\mathcal{P}_{i}\\}_{i\in[n]}$ hereunder:

  * •

$\mathsf{TSIG}.\mathsf{Setup}(1^{\lambda},t,n)\rightarrow(pk,{vk},{sk})$. Once
this algorithm/protocol is completed, there generates a public key $pk$, a
vector of public verification keys ${vk}:=(vk_{1},\cdots,vk_{n})$, along with
a vector of private secret keys ${sk}:=(sk_{1},\cdots,sk_{n})$ where
$\mathcal{P}_{i}$ gets $sk_{i}$ only.

  * •

$\mathsf{TSIG}.\mathsf{SignShare}_{t}(sk_{i},m)\rightarrow\sigma_{i}$. It
takes a message $m$ and a private key share $sk_{i}$ as input, and outputs a
signature share $\sigma_{i}$. We also use
$\mathsf{TSIG}.\mathsf{SignShare}_{t}(m)$ for short.

  * •

$\mathsf{TSIG}.\mathsf{VrfyShare}_{t}(pk,{vk},m,(i,\sigma_{i}))\rightarrow\\{0,1\\}$.
This is a deterministic algorithm taking a message $m$, the public key $pk$,
the verification keys ${vk}$, a “partial” signature $\sigma_{i}$ and an index
$i$ as input. It outputs 1 or 0 depending on whether $\sigma_{i}$ is deemed as
a valid “partial” signature share produced by party $\mathcal{P}_{i}$ or not.
We also use $\mathsf{TSIG}.\mathsf{VrfyShare}_{t}(m,(i,\sigma_{i}))$ for
short.

  * •

$\mathsf{TSIG}.\mathsf{Combine}_{t}(pk,{vk},m,\\{(i,\sigma_{i})\\}_{i\in[n]})\rightarrow\sigma$.
The algorithm takes the public key $pk$, the verification keys ${pk}$, a
message $m$, along with $t$ partial signature-index pairs $(i,\sigma_{i})$ as
input. This algorithm either outputs a full signature $\sigma$ for message
$m$, or $\bot$ when $\\{(i,\sigma_{i})\\}_{i\in[n]}$ contains ill-formed
$(i,\sigma_{i})$. We might use
$\mathsf{TSIG}.\mathsf{Combine}_{t}(m,\\{(i,\sigma_{i})\\}_{i\in[n]})$ for
short.

  * •

$\mathsf{TSIG}.\mathsf{Vrfy}_{t}(pk,m,\sigma)\rightarrow\\{0,1\\}$. This is a
deterministic algorithm that takes as input a message $m$, the public key $pk$
and an “combined” signature $\sigma$. It outputs 1 or 0 depending on whether
$\sigma$ is the valid signature for message $m$ or not. Remark that the
notation $\mathsf{TSIG}.\mathsf{Vrfy}_{t}(m,\sigma)$ could be used for short.

Besides the trivial correctness of enforcing all honestly produced signature
shares and signatures to pass verification, we require robustness and
unforgeability for $\mathsf{TSIG}$:

  * •

Robustness. No P.P.T. adversary can produce $t$ valid “partial” signature
shares, s.t. running $\mathsf{Combine}$ over these “partial” signatures does
not produce a valid “full” signature, except with negligible probability.
Intuitively, robustness ensures any $t$ valid “partial” signatures for a
message must induce a valid “full” signature [31].

  * •

Unforgeability (for static adversary). This can be defined by a threshold
version Existential UnForgeability under Chosen Message Attack game.
Intuitively, the property ensures that no P.P.T. adversary $\mathcal{A}$ that
corrupts $t-1$ parties can produce a valid “full” signature except with
negligible probability, unless $\mathcal{A}$ receives a “partial” signature
produced by an honest party.

Threshold public key encryption ($\mathsf{TPKE}$). A $(t,n)$-threshold public
key encryption scheme $\mathsf{TPKE}$ is a tuple of algorithms/protocols
involving $n$ parties $\\{\mathcal{P}_{i}\\}_{i\in[n]}$:

  * •

$\mathsf{TPKE}.\mathsf{Setup}(1^{\lambda},t,n)\rightarrow(epk,{esk})$. It
generates a public encryption key $epk$, along with a vector of private keys
${esk}:=(esk_{1},\cdots,esk_{n})$, each item of which $esk_{i}$ is the secret
key held by the corresponding party $\mathcal{P}_{i}$.

  * •

$\mathsf{TPKE}.\mathsf{Enc}(epk,m)\rightarrow c$. It encrypts a message $m$ to
a ciphertext $c$ with using the public encryption key $epk$.

  * •

$\mathsf{TPKE}.\mathsf{DecShare}(esk_{i},c)\rightarrow c_{i}$. It allows a
party $\mathcal{P}_{i}$ to use its secret key $esk_{i}$ to produce a
decryption share $c_{i}$ for $c$ (or a special symbol $\bot$ in case $c$ is
ill-formed).

  * •

$\mathsf{TPKE}.\mathsf{Dec}(epk,\\{(i,c_{i})\\}_{i\in[n]})\rightarrow m$. It
combines a set of valid decryption shares $(i,c_{i})$ from at least $t$
distinct parties to reconstruct the plaintext $m$.

The correction requirement of $\mathsf{TPKE}$ is obvious, which is any $t$
honest parties can cooperate to decrypt a ciphertext $c$ to get the
corresponding plaintext $m$, as long as $c$ is produced by an honest party
through encrypting $m$. Informally speaking, we expect an established
$(t,n)$-$\mathsf{TPKE}$ scheme to be robust and IND-CCA secure (see [32, 33]
for rigor definitions).

Threshold common-coin scheme ($\mathsf{Coin}$). A $(t,n)$-threshold common-
coin scheme $\mathsf{Coin}[\mathsf{id}]$ [34] is a protocol joined by $n$
parties and satisfies the following properties :

  * •

Agreement. If $t$ parties invoke
$\mathsf{Coin}[\mathsf{id}].\mathsf{GetCoin}()$, then all honest parties that
active $\mathsf{Coin}[\mathsf{id}].\mathsf{GetCoin}()$ eventually receive a
common value $r\in\\{0,1\\}$.

  * •

Unpredictability. The value
$r\leftarrow\mathsf{Coin}[\mathsf{id}].\mathsf{GetCoin}()$ cannot be
predicated by P.P.T. adversary (who can statically corrupt up to $t-1$
parties) except with negligible advantage, until one honest party calls
$\mathsf{Coin}[\mathsf{id}].\mathsf{GetCoin}()$.

Provable reliable broadcast ($\mathsf{PRBC}$). A protocol among a set of $n$
parties with a designated sender, a boolean function
$\mathsf{PRBC}.\mathsf{Verify}$, and identification $\mathsf{id}$ is said to
be $\mathsf{PRBC}$, if it satisfies the hereafter properties (in presence of
$f$ static corrupted Byzantine parties) except with negligible probability:

  * •

Validity. If all honest parties invoke $\mathsf{PRBC}[\mathsf{id}]$ and the
sender is honest with taking a message $m$ as input, all honest parties
eventually output $m$ with some string $\sigma$ s.t.
$\mathsf{PRBC}.\mathsf{Verify}(\mathsf{id},\sigma)=1$.

  * •

Agreement. If two honest parties output $m$ and $m^{\prime}$ in
$\mathsf{PRBC}[\mathsf{id}]$ respectively, then $m=m^{\prime}$.

  * •

Totality. If any (probably malicious) party outputs $m$ and $\sigma$ in
$\mathsf{PRBC}[\mathsf{id}]$ s.t.
$\mathsf{PRBC}.\mathsf{Verify}(\mathsf{id},\sigma)=1$, then all honest parties
eventually output some value attached with a proof $\sigma$ s.t.
$\mathsf{PRBC}.\mathsf{Verify}(\mathsf{id},\sigma)=1$ in
$\mathsf{PRBC}[\mathsf{id}]$.

  * •

Unforgeability. If $f+1$ or more honest parties do not activate
$\mathsf{PRBC}[\mathsf{id}]$, it computationally infeasible for any party to
produce a string $\sigma$ s.t.
$\mathsf{PRBC}.\mathsf{Verify}(\mathsf{id},\sigma)=1$.

Asynchronous binary agreement ($\mathsf{ABA}$). In an asynchronous binary
agreement [35, 36], each party has a single-bit input, and their goal is to
output a common bit. In particular, a protocol $\mathsf{ABA}$ running among
$n$ parties with identification $\mathsf{id}$ is said to be asynchronous
binary agreement, if it guarantees the following properties except with
negligible probability:

  * •

Termination. If all honest parties pass inputs to $\mathsf{ABA}[\mathsf{id}]$,
then all honest parties output associated to $\mathsf{id}$.

  * •

Agreement. If any honest party outputs a bit $b$ associated to $\mathsf{id}$,
all honest parties output the same $b$ on $\mathsf{id}$.

  * •

Validity. If any honest party outputs $b$ (associated to $\mathsf{id}$), then
at least one honest party takes $b$ as input to $\mathsf{ABA}[\mathsf{id}]$.

Asynchronous common subset ($\mathsf{ACS}$). In the $\mathsf{ACS}$ protocol
among $n$ parties (where are up to $f$ Byzantine faulty parties) with
identification $\mathsf{id}$, each party takes as input a value and outputs a
set of values. It satisfies the following properties except with negligible
probability:

  * •

Validity. If an honest party outputs a set of values $\bf v$, then $|{\bf
v}|\geq n-f$ and ${\bf v}$ contains the inputs from at least $n-2f$ honest
parties.

  * •

Agreement. If an honest party outputs a set of values $\bf v$, then every
party outputs the same set $\bf v$.

  * •

Termination. If $n-f$ honest parties receive an input, then every honest party
delivers an output.

##  III Notations & Problem Formulation

###  III-A Data structures & notations

Transaction. Without loss of generality, we let a transaction denoted by
$\mathsf{tx}$ to be a bit string of $|m|$ bits. Through the paper, we will
omit the detailed syntax of the transactions.

Block structure. The block is a tuple in form of $\mathsf{block}:=\langle
epoch,slot,\mathsf{TXs},\mathsf{Proof}\rangle$, where $epoch$ and $slot$ are
natural numbers, $\mathsf{TXs}$ is a sequence of transactions also known as
the payload. Through the paper, we assume $|\mathsf{TXs}|=B$, where $B$ be the
batch size parameter. The batch size can be chosen to saturate the network’s
available bandwidth in practice. $\mathsf{Proof}$ is a proof string (a.k.a.
quorum certificate) attesting that at least $f+1$ honest parties participate
in generating the $\mathsf{block}$.

Blocks as $\mathsf{log}$. Through the paper, a $\mathsf{log}$ (or
interchangeably called as $\mathsf{blocks}$) refers to an indexed sequence of
blocks. For a $\mathsf{log}$ with length $L:=|\mathsf{log}|$, we might use
hereunder conventional notations:

  * •

$\mathsf{log}[i]$ denotes the $i$-th block in $\mathsf{log}$, and $i\in[1,L]$.
Notation-wise, $\mathsf{log}[1]$ is the first block of $\mathsf{log}$, and
$\mathsf{log}[0]$ cannot be addressed;

  * •

$\mathsf{log}[-i]$ is the alias of the block $\mathsf{log}[L-i+1]$. In
particular, $\mathsf{log}[-1]$ represents the last block in $\mathsf{log}$,
$\mathsf{log}[-2]$ represents the second-to-last block in $\mathsf{log}$, and
so forth.

  * •

$\mathsf{log}[i:j]$ denotes to all blocks from $\mathsf{log}[i]$ till
$\mathsf{log}[j]$. Both $\mathsf{log}[i]$ and $\mathsf{log}[j]$ are inclusive
for pretension simplicity.

  * •

$\mathsf{log}.append(\cdot)$ represents to append a suffix of
$\mathsf{block}$(s) to the tip of $\mathsf{log}$. For example, when
$\mathsf{log}.append(\cdot)$ takes a $\mathsf{block}\neq\emptyset$ as input,
the length of $\mathsf{log}$ increased by one, and $\mathsf{log}[-1]$ becomes
this $\mathsf{block}$ after this operation.

###  III-B System and adversary modeling

We consider the standard asynchronous message-passing model with trusted setup
for granted. The system consists of $n$ parties
$\\{\mathcal{P}_{i}\\}_{i\in[n]}$ interconnected via asynchronous point-to-
point (p2p) channels, where $n\in\mathbb{N}$ represents the number of parties
and $[n]$ is short for $\\{1,\cdots,n\\}$. The adversary can fully control all
p2p channels and statically corrupt up to $f$ parties. The detailed system
model can be described as follows:

  * •

Trusted setup. There are $n$ designated parties, each of which has a unique
identity (i.e. $\mathcal{P}_{1}$ through $\mathcal{P}_{n}$) that is known by
everyone else. Moreover, through existing PKI, each party $\mathcal{P}_{i}$ is
bounded to a unique secret-public key pair of digital signature scheme
$\mathsf{SIG}$. Besides PKI, we assume all involved threshold cryptosystems
such as $\mathsf{TSIG}$ and $\mathsf{TPKE}$ have been properly set up, such
that all participating parties can get and only get their own secret keys in
addition to all relevant public keys. The above setups can be done either via
a trusted dealer or through some distrusted key generation protocols.

  * •

Static Byzantine corruptions. The adversary can fully control $f$ out of $n$
parties where $f=\lfloor(n-1)/3\rfloor$. In addition, we restrict to static
corruptions, namely, the adversary chooses up to $f$ parties to corrupt before
the execution. No asynchronous BFT can tolerate more than
$\lfloor(n-1)/3\rfloor$ static corruptions. Through the paper, we stick with
this optimal resilience. Therefore, $f+1$ and $n-2f$ are interchangeable, so
are $2f+1$ and $n-f$.

  * •

Fully-meshed asynchronous p2p channels. We consider assume that there exists
an established reliable authenticated p2p channel between any two parties. The
adversary can arbitrarily reorder/delay messages, but cannot drop/modify
messages sent among honest parties.

  * •

Computationally-bounded adversary. We also consider computationally bounded
adversary. In the asynchronous network, it means the adversary can perform
some probabilistic computing steps bounded by polynomials in the number of
message bits generated by honest parties.

  * •

Adversary-controlling local “time”. Remark that there is no notion of time in
the asynchronous model. Nevertheless, we do not require any common wall-clock
for liveness, so it is feasible [37, 19] to let each party keep an adversary-
controlling local “clock” that elapses at the speed of actual network delay
$\delta$: after initializing, each party sends a “tick” message to itself via
the adversary-controlling network, then whenever it receives a “tick” message,
it increases its local “time” by one and resends a new “tick” to itself via
the adversary. Using the adversary-controlling “clock”, each party can
maintain a timeout mechanism. We let $timer(\tau).start()$ denote to
initialize a local timer that raises a timeout signal after counting $\tau$
clock “ticks” and $timer(\tau).restart()$ denote to reset the timer’s internal
“tick” counting to zero.

This “timeout” notion illustrates that the timeout parameter $\tau$ in our
optimistic path is essentially a function of the actual network delay $\delta$
instead of the upper bound $\Delta$.

###  III-C Goal: asynchronous atomic broadcast

Our goal is to develop atomic broadcast protocols that attains high robustness
in the unstable or even hostile network environment and hopefully remains high
performance if the network is luckily benign. The proposed BFT protocols shall
satisfy the following definition of atomic broadcast in the asynchronous model
to keep all honest parties reach an agreement on an ever-growing linearly
ordered log of blocks:

###### Definition 1

Atomic broadcast. In an atomic broadcast protocol with identification
$\mathsf{id}$, each party inputs a queue $\mathsf{buf}$ of transactions (the
size of which is bounded by an unfixed polynomial) and outputs a
$\mathsf{log}$ of blocks. It satisfies the following properties except with
negligible probability:

  * •

Total-order. If an honest party outputs a sequence of $\mathsf{blocks}$ called
$\mathsf{log}$, and another honest party outputs a sequence of blocks called
$\mathsf{log}^{\prime}$, then $\mathsf{log}[i]=\mathsf{log}^{\prime}[i]$ for
every $i$ that $1\leq i\leq\min\\{|\mathsf{log}|,|\mathsf{log}^{\prime}|\\}$.

  * •

Agreement. If an honest party appends a $\mathsf{block}$ to its
$\mathsf{log}$, then all correct parties would (eventually) append the same
$\mathsf{block}$ to their $\mathsf{log}$s.

  * •

Censorship-resilience. If $n-f$ honest parties take a transaction
$\mathsf{tx}$ as input, $\mathsf{tx}$ would eventually included by an honest
party’s $\mathsf{log}$. Remark that the censorship-resilience can also be
translated to a couple of mutually complement notions called validity and
fairness in [21, 19], which essentially corresponds to liveness.

Remark. Through the paper, we insist a stronger version of censorship-
resilience/liveness: if $n-f$ honest parties take $\mathsf{tx}$ as input,
$\mathsf{tx}$ would eventually included by an honest party’s $\mathsf{log}$,
after the protocol executes at most some polynomial number of asynchronous
rounds. This is quintessential because: (i) the protocol must have polynomial-
bounded execution rounds to bound the computing power of adversary in our
model, otherwise underlying cryptographic primitives are broken [21]; (ii) it
highlights our goal of achieving asynchronous BFT with fast confirmation (even
in worst cases) and separates this aim from some studies having exponentially
large confirmation latency [38].

###  III-D Performance metrics

We are particularly interested in constructing efficient asynchronous atomic
broadcasts, and therefore, it becomes meaningful to consider various (on-
average) costs of generating each block. So we consider the following
performance metrics:

  * •

Communication complexity. We primarily focus on the (average) bits of all
messages associated to output each block. Because the communicated bits per
block essentially reflects the amortized communication complexity per
delivered transaction (a.k.a., efficiency defined in [14]), if the protocol
can ensure each block to include at least $\mathcal{O}(B)$ size transactions.

  * •

Each party’s bandwidth usage. This is similar to per-block communication
complexity, but it does not count the overall network’s communicated bits
averaged for each block. However, this metric counts a certain party’s
bandwidth usage (including both incoming and outgoing messages) amortized for
each output block.

  * •

Message complexity. We are also interested in the (average) number of messages
associated to a block. This key indicator characterizes the expense of the
total number of messages exchanged between the honest parties to produce a
block.

  * •

Round complexity (or running time). The eventual delivery of the asynchronous
network notion might cause that the protocol execution is somehow independent
to “real time”, but it is nevertheless needed to characterize the running time
of asynchronous protocols. A well-accepted notion [39] is for the adversary to
assign each message a virtual round number $r$, subject to the condition that
any $(r-1)$-th round messages between any two correct nodes must be delivered
before any $(r+1)$-th round message is sent. Following this rationale, it
becomes straightforward to measure the upper bound of any transaction’s
confirmation latency by counting such “rounds”. For the sake of highly
responsive liveness, we might also require the “time” of generating each block
to be on average $\mathcal{O}(1)$ asynchronous rounds.

##  IV Notarizable Weak Atomic Broadcast: Abstraction and Implementations of
Bolt

###  IV-A Defining $\mathsf{Bolt}$: the optimistic path abstraction

The first ingredient is a fast optimistic path called Bolt. We begin with the
security abstraction of this key component, a.k.a., notarizable weak atomic
broadcast ($\mathsf{nw\textnormal{-}ABC}$).

###### Definition 2

Notarizable weak atomic broadcast $\mathsf{nw\textnormal{-}ABC}$ (a.k.a.
$\mathsf{Bolt}$). In a $\mathsf{Bolt}$ protocol with identification
$\mathsf{id}$ and a boolean function $\mathsf{Bolt.Verify}$, each party takes
a transactions’ buffer as input and outputs a $\mathsf{log}$ of blocks. It
shall satisfy the following properties except with negligible probability:

  * •

Total-order. Same to asynchronous atomic broadcast.

  * •

Notarizability. If any (probably malicious) party outputs at the $j$-th
position of its $\mathsf{log}$ a block
$\mathsf{log}[j]:=\langle\mathsf{id},j,\mathsf{TXs}_{j},\mathsf{Proof}_{j}\rangle$
s.t. $\mathsf{Bolt.Verify}(\mathsf{id},j,\mathsf{Proof}_{j})=1$, then at least
$f+1$ honest parties already output some block
$\mathsf{log}[j-1]:=\langle\mathsf{id},{j-1},\mathsf{TXs}_{j-1},\mathsf{Proof}_{j-1}\rangle$
in their $\mathsf{log}$ s.t.
$\mathsf{Bolt.Verify}(\mathsf{id},j-1,\mathsf{Proof}_{j-1})=1$.

  * •

Abandonability. An honest node is allowed to invoke
$\mathsf{abandon}(\mathsf{id})$. After the invocation of
$\mathsf{abandon}(\mathsf{id})$, the honest node will not deliver any message
associated to $\mathsf{Bolt}[\mathsf{id}]$. If $f+1$ honest nodes invoke
$\mathsf{abandon}(\mathsf{id})$, then no node would deliver valid
$\mathsf{block}$.

Remarks. Comparing to atomic broadcast, $\mathsf{Bolt}$ do not have the
agreement and liveness properties: (i) to compensate the lack of agreement,
the notarizability is introduced to guarantee that whenever an honest party
outputs a block $\mathsf{log}[j]$ at position $j$, then at least $f+1$ honest
ones already output a block at the position $j-1$; (ii) liveness does not
exist to any extent, as a trivial implementation actually can be: “each party
remains idle to do nothing, until the abandon interface is invoked and it
aborts”; nevertheless, this weakening allows the optimistic path to be easily
implementable in the asynchronous setting by simple deterministic protocols.
Here down below we present two exemplary concise constructions.

###  IV-B $\mathsf{Bolt}$-$\mathsf{HS}$ from pipelined multicasts

$\mathsf{Bolt}$ can be easily constructed as a stable leader version of
HotStuff from pipelined multicasts with using threshold signature, called
$\mathsf{Bolt}$-$\mathsf{HS}$ and shown in Figure 2. The basic idea is as
simple as: the leader proposes a batch of transactions through
multicast,555Remark that our optimistic path abstraction is quite general. As
an example, we also can let every party send a signed $tx$ to the leader, and
the leader can combine at least $n-f$ tx-signature pairs as a set
$\mathsf{TXs}$ and then multicasts $\mathsf{TXs}$ as proposal, and other
parties vote only if $\mathsf{TXs}$ contains $n-f$ tx-signature pairs. This
can guarantee a block-quality property, i.e., at least half $tx$ of each block
would be from honest parties, though latency could be sacrificed. Moreover,
the optimistic path implementation in [20] also fits our abstraction. then all
parties send their votes for the proposal to the leader, once the leader
collects enough votes from distinct parties (i.e., $2f+1$), it repeats to
multicast proposal (along with those votes for its previous proposal) and the
parties repeat to return their votes; this simple execution is repeated until
the abandon interface is invoked.

let $e$ be the sesssion identification of $\mathsf{Bolt}[e]$, $\mathsf{buf}$
be a FIFO queue of input transactions, $B$ be the batch parameter, and
$\mathcal{P}_{l}$ be the leader $\mathcal{P}_{i}$ initializes $s=1$ and runs
the protocol in consecutive slot number $s$ as follows: • Broadcast . if
$\mathcal{P}_{i}$ is the leader $\mathcal{P}_{l}$ – if $s=1$ then: multicast
$(\mathsf{proposal},e,s,\mathsf{TXs}_{s},\sigma_{s-1})$, where
$\mathsf{TXs}_{s}\leftarrow\mathsf{buf}[:B]$ – if $s>1$ then: waiting for
$2f+1$ valid $\mathsf{vote}$ messages $(\mathsf{vote},e,s-1,\sigma_{i})$ from
distinct nodes $\mathcal{P}_{i}$, then multicast
$(\mathsf{proposal},e,s,\mathsf{TXs}_{s},\sigma_{s-1})$, where
$\mathsf{TSIG}.\mathsf{VrfyShare}_{2f+1}(\langle
e,s-1,\mathcal{H}(\mathsf{TXs}_{s-1})\rangle,(i,\sigma_{i}))=1$,
$\sigma_{s-1}\leftarrow\mathsf{TSIG}.\mathsf{Combine}_{2f+1}(\langle
e,s-1,\mathcal{H}(\mathsf{TXs}_{s-1})\rangle,\\{(i,\sigma_{i})\\}_{2f+1})$ •
Vote and Commit. upon receiving a $\mathsf{proposal}$ message
$(\mathsf{proposal},e,s,\mathsf{TXs}_{s},\sigma_{s-1})$ from leader
$\mathcal{P}_{l}$ – if $s=1$ then: send $(\mathsf{vote},e,s,\sigma_{i})$ to
the leader $\mathcal{P}_{l}$, where
$\sigma_{i}\leftarrow\mathsf{TSIG}.\mathsf{SignShare}_{2f+1}(sk_{i},\langle
e,s,\mathcal{H}(\mathsf{TXs}_{s})\rangle)$, and $s\leftarrow s+1$ – if $s>1$
and $\mathsf{TSIG}.\mathsf{Vrfy}_{2f+1}(\langle
e,s-1,\mathcal{H}(\mathsf{TXs}_{s-1})\rangle,\sigma_{s-1})=1$ then: @itemiii
then send $(\mathsf{vote},e,s,\sigma_{i})$ to the leader $\mathcal{P}_{l}$,
where
$\sigma_{i}\leftarrow\mathsf{TSIG}.\mathsf{SignShare}_{2f+1}(sk_{i},\langle
e,s,\mathcal{H}(\mathsf{TXs}_{s})\rangle)$ @itemiii return
$\mathsf{block}$:=$(e,s-1,\mathsf{TXs}_{s-1},\mathsf{Proof}_{s-1})$ where
$\mathsf{Proof}_{s-1}:=\langle\mathcal{H}(\mathsf{TXs}_{s-1}),\sigma_{s-1}\rangle$,
and let $s\leftarrow s+1$ • Abandon. upon $\mathsf{abandon}(e)$ is invoked
then: abort the above execution function
$\mathsf{Bolt.Verify}(\mathsf{id},s,\langle h,\sigma\rangle)$: return
$\mathsf{TSIG}.\mathsf{Vrfy}_{2f+1}(\langle\mathsf{id},s,h\rangle,\sigma)$

Figure 2: $\mathsf{Bolt}$ from pipelined multicasts

let $e$ be the sesssion identification of $\mathsf{Bolt}[e]$, $\mathsf{buf}$
be a FIFO queue of input transactions, $B$ be the batch parameter, and
$\mathcal{P}_{l}$ be the leader $\mathcal{P}_{i}$ initializes $s=1$ and runs
the protocol in consecutive slot number $s$ as follows: • Broadcast. if
$\mathcal{P}_{i}$ is the leader $\mathcal{P}_{l}$, activates
$\mathsf{PRBC}[\left\langle e,s\right\rangle]$ with taking as input
$\mathsf{TXs}_{s}\leftarrow\mathsf{buf}[:B]$; else activates
$\mathsf{PRBC}[\left\langle e,s\right\rangle]$ as non-leader party; • Commit.
upon $\mathsf{PRBC}[\left\langle e,s\right\rangle]$ returns
$(\mathsf{TXs}_{s},\mathsf{Proof}_{s})$: – return
$\mathsf{block}$:=$(e,s,\mathsf{TXs}_{s},\mathsf{Proof}_{s})$, and let
$s\leftarrow s+1$ • Abandon. upon $\mathsf{abandon}(e)$ is invoked then: abort
the above execution function
$\mathsf{Bolt.Verify}(\mathsf{id},s,\mathsf{Proof})$: return
$\mathsf{PRBC}.\mathsf{Verify}(\langle\mathsf{id},s\rangle,\mathsf{Proof})$

Figure 3: $\mathsf{Bolt}$ from sequential $\mathsf{PRBC}$s

###### Lemma 1

The algorithm in Figure 2 satisfies the total-order, notarizability and
abandonability properties of $\mathsf{Bolt}$ except with negligible
probability.

Proof: Here we prove the three properties one by one:

For total-order: First, we prove at same position, for any two honest parties
$\mathcal{P}_{i}$ and $\mathcal{P}_{j}$ return $\mathsf{block}_{i}$ and
$\mathsf{block}_{j}$, respectively, then
$\mathsf{block}_{i}=\mathsf{block}_{j}$. It is clear that if the honest party
$\mathcal{P}_{i}$ outputs $\mathsf{block}_{i}$, then at least $f+1$ honest
parties did vote for $\mathsf{block}_{i}$ because
$\mathsf{TSIG}.\mathsf{Vrfy}_{2f+1}$ passes verification. So did $f+1$ honest
parties vote for $\mathsf{block}_{j}$. That means at least one honest party
votes for both blocks, so $\mathsf{block}_{i}=\mathsf{block}_{j}$.

For notarizability: Suppose an honest party $\mathcal{P}_{i}$ outputs
$\mathsf{blocks}[j]$, it means at least $f+1$ honest parties vote for
$\mathsf{block}[j]$, and hence, according to the pseudocode, at least those
same $f+1$ honest nodes already output $\mathsf{blocks}[j-1]$.

For abandonability: it is immediate to the pseudocode. $\hfill\square$

Performance metrics. Given that each $\mathsf{Bolt}$-$\mathsf{HS}$ block
contains a batch of $B$ size transactions, the per-block message complexity is
$\mathcal{O}(n)$, the overall per-block communication complexity is
$\mathcal{O}(Bn+\lambda n)$, the per-block bandwidth usage of the leader is
$\mathcal{O}(Bn+\lambda n)$, the per-block bandwidth usage of other nodes is
$\mathcal{O}(B+\lambda)$.

###  IV-C $\mathsf{Bolt}$-$\mathsf{RBC}$ from provable reliable broadcast

In $\mathsf{Bolt}$-$\mathsf{HS}$, the bandwidth usage of leader is always $n$
times more than the other nodes’. This essentially restricts each block’s
transaction batch size and becomes the throughput bottleneck, unless the
leader has significant physical resources. We therefore present an alternative
$\mathsf{Bolt}$ implementation in order to reduce the bandwidth bottleneck at
the leader. The idea of $\mathsf{RBC}$ with using erasue code and Merkle tree
is borrowed from [14] to balance the communications over the whole network.
For $\mathsf{Bolt}$’s notarizability property, we can follow [17] to augment
$\mathsf{RBC}$ by threshold signature, resulting in provable reliable
broadcast ($\mathsf{PRBC}$) that can output publicly verifiable proof
attesting $\mathsf{RBC}$’s termination besides output.

As shown in Figure 3, $\mathsf{PRBC}$ modules with increasing identifiers are
sequentially executed, through which a designated optimistic path leader can
broadcast its proposed transaction batch to all parties. Moreover, when a
$\mathsf{PRBC}$ module delivers some transaction batch to some honest party,
it also attaches a succinct proof along with the output, which attests at
least $f+1$ honest parties did participate into this $\mathsf{PRBC}$ and
further proves that at least those same parties already output in the
immediately precedent $\mathsf{PRBC}$ module, thus making another simple
$\mathsf{Bolt}$ construction that we call $\mathsf{Bolt}$-$\mathsf{RBC}$.

###### Lemma 2

The algorithm in Figure 3 satisfies the total-order, notarizability and
abandonability properties of $\mathsf{Bolt}$ except with negligible
probability.

Proof: It is clear that the total-order, notarizability and abandonability
follow immediately from the properties of $\mathsf{PRBC}$ and the pseudocode
of $\mathsf{Bolt}$-$\mathsf{RBC}$, since the agreement and totality of
$\mathsf{PRBC}$ guarantees that all parties can agree on the same
$\mathsf{block}$ with valid proof, and the unforgeability property along with
the sequentially executing nature of all $\mathsf{PRBC}$ instances would
ensure notarizability. $\hfill\square$

Performance metrics. Here we analyze the per-block complexities of
$\mathsf{Bolt}$-$\mathsf{RBC}$, conditioned on that each
$\mathsf{Bolt}$-$\mathsf{RBC}$ block contains a batch of $B$ size
transactions, In $\mathsf{PRBC}$, the message complxity is
$\mathcal{O}(n^{2})$, the overall communication complxity is
$\mathcal{O}(nB+\lambda n^{2}\log n)$, the bandwidth usage of every party are
of $\mathcal{O}(B+\lambda n\log n)$ bits. It is easy to see from the algorithm
that these $\mathsf{PRBC}$ complexities are also the per-block complexities of
$\mathsf{Bolt}$-$\mathsf{RBC}$.

##  V Build the AllSpark for our $\mathsf{Transformer}$: Two-Consecutive-Value
Byzantine Agreement

The most critical ingredient of our paper is an efficient pace synchronization
subprotocol (a.k.a. $\mathsf{Transformer}$) that enables efficient fallback
from the optimistic path to the pessimistic path. As briefly mentioned in
Introduction, our novel pace synchronization is created from a key component
two-consecutive-value Byzantine agreement ($\mathsf{tcv\textnormal{-}BA}$). It
can help the honest parties to choose one common integer out of two unknown
but consecutive integers, thus making them reach an agreement on how many
blocks are indeed finalized in the optimistic path. Essentially, that is a
generalized notion to extend the conventional binary-value agreement, and can
be formalized due to the following definition.

###### Definition 3

Two-consecutive value Byzantine agreement with identification $\mathsf{id}$ is
denoted by $\mathsf{tcv\textnormal{-}BA}[\mathsf{id}]$, and satisfies the
following properties except with negligible probability:

  * •

Strong Validity. If an honest party outputs a value $v\in\mathbb{N}\cup 0$,
then at least one honest party inputs the value $v$.

  * •

Termination. Conditioned on all honest parties input a value in $\\{v,v+1\\}$
where $v\in\mathbb{N}\cup 0$, then every honest party outputs a value.

  * •

Agreement. The output of any two honest parties is same.

Though $\mathsf{tcv\textnormal{-}BA}$ can be approached through “black-box”
construction from an instance of asynchronous binary Byzantine agreement
($\mathsf{ABA}$), c.f. Figure 5. Nevertheless, any such “black-box”
construction might correspond to several extra “broadcasts/amplifications” to
disperse inputs besides calling the $\mathsf{ABA}$ instance. Hence, to squeeze
extreme performance of the critical pace synchronization subprotocol, we
figure out a non-black-box construction $\mathsf{tcv\textnormal{-}BA}$ that
only has to revise three lines of code of the practical $\mathsf{ABA}$
construction due to [17]. Though we cannot quantitatively measure the
“simplicity” of our revision, the construction essentially remains as same as
the pseudocode of Algorithm 7 in [17] except few slightly different if-else
checking (see Figure 4) and hence straightforwardly inherits the asymptotic
performance metrics as well as the concrete applicability.

Modify $\mathsf{ABA}$ Protocol (Algorithm 7) in [17] for node
$\mathcal{P}_{i}$ as follows: • Replace line 13-23 of Algorithm 7 in [17] with
the next instructions: – $s\leftarrow\mathsf{Coin}_{r}.\mathsf{GetCoin}()$
@itemiii if $S_{r}=\\{v\\}$ then: $\cdot$ if $v\%2=s\%2$ $\cdot$ if $decided$
= false then: decide$(v)$; $decided$ = true $\cdot$ else (i.e, $decided$ =
true) then: halt $\cdot$ $\mathsf{est}_{r+1}\leftarrow v$ @itemiii if
$S_{r}=\\{v_{1},v_{2}\\}$ then: $\cdot$ if $v_{1}\%2=s\%2$, then
$\mathsf{est}_{r+1}\leftarrow v_{1}$ $\cdot$ else (i.e, $v_{2}\%2=s\%2$), then
$\mathsf{est}_{r+1}\leftarrow v_{2}$

Figure 4:  $\mathsf{tcv\textnormal{-}BA}$ protocol. Lines different to Alg. 7
in [17] are in  orange texts

Let $\mathsf{ABA}$ Protocol is Algorithm 7 in [17], then for node
$\mathcal{P}_{i}$ as follows: Upon receiving input R then: • multicast
$\textsc{Value}(e,R)$ • wait until receiving $f+1$ $\textsc{Value}(e,v)$
messages from distinct parties that agree on $v$ then: – input $v\%2$ into
$\mathsf{ABA}[e]$ – wait for $\mathsf{ABA}[e]$ return s @itemiii wait until
receiving $f+1$ $\textsc{Value}(e,v^{\prime})$ messages from distinct parties
that $v^{\prime}\%2=s$ $\cdot$ return $v^{\prime}$

Figure 5:  $\mathsf{tcv\textnormal{-}BA}$ protocol with using $\mathsf{ABA}$
as “black-box”

##  VI $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ Framework:
Optimistic Asynchronous Atomic Broadcast

Here we are ready to present our optimistic asynchronous atomic broadcast
protocol $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$, which
is constructed by grafting the optimistic $\mathsf{Bolt}$ to a pessimistic
path, which can be instantiated by some randomized asynchronous BFT such as
$\mathsf{Dumbo}$ BFT. Note that the pessimistic path can be replaced with any
other asynchronous BFT atomic broadcast protocols. Through the paper, we
choose $\mathsf{Dumbo}$ as the concrete instantiation of the pessimistic path
because of its start-of-the-art status.

Figure 6: The execution flow of $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\
}Transformer}$.

As illustrated by Figure 6, $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\
}Transformer}$ consists of three components, i.e., $\mathsf{Bolt}$,
$\mathsf{Dumbo}$, and $\mathsf{PaceSync}$, each of which deals with each of
following critical challenges:

  * •

Optimistic path $\mathsf{Bolt}$. In the beginning of each epoch, all nodes are
initially “optimistic” and begin with trying an optimistic path
$\mathsf{Bolt}$ that is extremely simple and efficient. $\mathsf{Bolt}$ might
luckily return some optimistic blocks, but it encounters two issues: the first
is about when to finalize and output the optimistic blocks, because confirming
an optimistic block immediately might not safe enough as $\mathsf{Bolt}$ does
not have agreement assurance; the second is because the optimistic path cannot
ensure the critical liveness all the time, so it is also necessary to handle
the possible grinding to halt. These issues bring us the following critical
question to answer:

When to finalize $\mathsf{Bolt}$ blocks and when to give up $\mathsf{Bolt}$?

  * •

Pace synchronization $\mathsf{PaceSync}$. To cope with the failure of
optimistic path, a $\mathsf{PaceSync}$ subprotocol can be activated.
Functionality-wise, we not only expect it to enable the participating parties
to eventually agree on dropping the “optimistic” epoch, but also hope it to
allow the parties to reach the consensus on how many blocks have been
optimistically delivered during the optimistic path. This is important to
overcome the lack of agreement in $\mathsf{Bolt}$ to enforce the parties
finalize a common “pace” before falling back into the next fully asynchronous
pessimistic path. To realize these essential functionalities, we answer the
hereunder critical problem in our concrete $\mathsf{PaceSync}$ instantiation
i.e., $\mathsf{Transformer}$:

How to efficiently resolve disagreement caused by $\mathsf{Bolt}$?

  * •

Pessimistic path $\mathsf{Dumbo}$. Once the $\mathsf{PaceSync}$ subprotocol is
completed, it might reveal that the optimistic path delivers too few blocks,
which can raise a worry that the protocol might completely lose the critical
liveness. One earlier idea of always running the pessimistic path after pace
synchronization might invoke too many randomized executions and thus
sacrifices the benefits of trying optimistic paths on good days. While too
aggressive strategies such as never run randomized pessimistic paths might
raise completely failed liveness. It becomes critical for us to identify an
aggressive way that attempts less randomized asynchronous protocols yet still
attains provable liveness in harsh networks. This calls us for addressing the
following question in our pessimistic design:

How to try less $\mathsf{Dumbo}$ runs yet still ensure liveness?

###  VI-A Details of $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\
}Transformer}$

Our $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ protocol is
formally illustrated in Figure 7. It employs a reduction to
$\mathsf{nw\textnormal{-}ABC}$, $\mathsf{tcv\textnormal{-}BA}$ and
$\mathsf{ACS}$. In details, it proceeds by epoch, and each epoch might invoke
three phases including $\mathsf{Bolt}$, $\mathsf{Transformer}$ and
$\mathsf{Dumbo}$, which can be briefly described as follows:

  * •

$\mathsf{Bolt}$ phase. When an honest party enters an epoch $e$, it
optimistically activates a $\mathsf{Bolt}[e]$ instance, and locally starts an
adversary-controlling “timer” that expires after $\tau$ clock “ticks”666Remark
that we do not have a common clock in the system. To our terminology, each
clock “tick” means that the party receives a special “tick” message that it
sends to itself via the adversary. So $\tau$ essentially is a function in the
actual network delay $\delta$ instead of relating to the delay upper bound
$\Delta$. and resets once hearing the “heartbeat” of $\mathsf{Bolt}[e]$ (e.g.,
$\mathsf{Bolt}[e]$ returns a new block). With the “timeout” mechanism, every
party can check whether an unexpectedly large amount of “time” has passed
since last $\mathsf{Bolt}[e]$ progress; if it receives a new
$\mathsf{Bolt}[e]$ block in time, it temporarily records the block as
$1$-$\mathsf{notarized}$, the previous (non-empty) $1$-$\mathsf{notarized}$
becomes $2$-$\mathsf{notarized}$, and more importantly, the previous (non-
empty) $2$-$\mathsf{notarized}$ is finalized as the atomic broadcast output.
Namely, every $\mathsf{Bolt}[e]$ block is confirmed once two more consecutive
optimistic blocks appended to it.

Beside the above “timeout” mechanism that interrupts when $\mathsf{Bolt}[e]$
does not progress in time, we also consider the case that some transactions
are probably censored: if the oldest input transaction (i.e., the top
transaction at the input buffer) is not output for a long duration $T$, an
interruption is also raised to abandon $\mathsf{Bolt}[e]$. Finally, a party
might also raise an interruption when $\mathsf{Bolt}[e]$ returns enough
blocks, so it is the time to shift into the next epoch. Once a party is
interrupted for any reason out of the three, it immediately abandons
$\mathsf{Bolt}[e]$ and multicasts its lasest “pace” in $\mathsf{Bolt}[e]$
(e.g., the non-empty $1$-$\mathsf{notarized}$ block’s slot number) along with
the corresponding proof via the PaceSync message.

For concrete instantiations of $\mathsf{Bolt}$, there are various choices to
carter varying demands as earlier discussed in Section IV. For example,
$\mathsf{Bolt}$-$\mathsf{HS}$ is through the lens of HotStuff (see Figure 2),
which is driven by a designated leader in an extremely simple “pipelined”
fashion and could be low latency in practice for its simplest communication
pattern. $\mathsf{Bolt}$ could also be built from broadcast protocols, like
$\mathsf{Bolt}$-$\mathsf{RBC}$ using $\mathsf{RBC}$ (see Figure 3), which can
better shift the communication load from the leader to all parties so it might
subject to better performance if larger batch sizes are used for throughput.

  * •

$\mathsf{Transformer}$ phase. If an honest party receives ($2f+1$) valid
PaceSync messages from distinct parties regarding to $\mathsf{Bolt}[e]$, it
enters this $\mathsf{Transformer}$ phase. It is easy to see that once an
honest party switches to the $\mathsf{Transformer}$ phase of the epoch $e$,
then all honest parties will do so, because when an honest party starts
$\mathsf{Transformer}$, then it must be receive at least $2f+1$ PaceSync
messages from distinct nodes for epoch $e$, then at least those $f+1$ honest
parties abandon $\mathsf{Bolt}[e]$, resulting in that the $\mathsf{Bolt}[e]$
instance cannot output any valid block to any honest parties, so all honest
parties’ timer must raise interruptions and then abandon $\mathsf{Bolt}[e]$ in
at most $\mathcal{O}(\tau)$ asynchronous rounds. Clearly, this induces that
all honest parties will mulitcast PaceSync messages and therefore switch to
the $\mathsf{Transformer}$ phase for epoch $e$.

Once entering the $\mathsf{Transformer}$ phase, the party simply computes the
maximum “pace” $\mathsf{maxpace}$ out of the $2f+1$ slot numbers including by
the $2f+1$ PaceSync messages that it received, and it would use
$\mathsf{maxpace}$ as input to invoke the $\mathsf{tcv\textnormal{-}BA}[e]$
instance. Once $\mathsf{tcv\textnormal{-}BA}[e]$ returns a value $p$, each
party would reach an agreement that the $\mathsf{Bolt}[e]$ instance did
finalize the common pace as $p-1$, and it would sync up to here if it did not
yet output $p-1$ blocks during executing $\mathsf{Bolt}[e]$.

  * •

$\mathsf{Dumbo}$ phase. This phase may not be executed unless the optimistic
path of current epoch $e$ makes no progress at all, i.e, the finally reached
common pace during the $\mathsf{Transformer}$ phase is zero. In this case,
$\mathsf{Bolt}[e]$ essentially contributes nothing to the final output, so
$\mathsf{Dumbo}$ BFT is invoked to produce some blocks (e.g., 1) despite how
bad the underlying network is, which becomes the key for us to ensure
liveness.

Remarks. First, we briefly introduce the $\mathsf{Help}$ service and the
$\mathsf{CallHelp}$ functionality shown in Figure 8. The $\mathsf{Help}$
service is activated once every party is initialized and takes care of
CallHelp messages from other parties. In each CallHelp message, a party
specifies some $\mathsf{Bolt}$ blocks that are agreed to output (i.e., lower
than the common pace output in $\mathsf{Transformer}$) but it unluckily did
not receive yet. Nevertheless, since the common pace output in
$\mathsf{Transformer}$ is at most the highest pace minuses one, there must be
$f+1$ honest parties do output all finalized $\mathsf{Bolt}$ blocks. So the
unlucky party can broadcast CallHelp, and at least the $f+1$ honest parties
would respond it and return an erasure-code fragment of those blocks, thus
allowing the unlucky party eventually recover the missed Bolt. Second, no
block finalized in some honest party’s $\mathsf{log}$ can be revoked, besides,
the last two block of each $\mathsf{Bolt}[e]$ instance may has no chance to be
agreed to output in the log, c.f. Lemma 6 in the next subsection. We therefore
advocate a strategy in each $\mathsf{Bolt}[e]$ instance: the last two blocks,
i.e., the ($Esize$-$1$)-th and the $Esize$-th blocks can include zero payload.
Third, though in our formal description of the protocol we let the
$\mathsf{Dumbo}$ phase to agree only one block once it is invoked, we remark
that there could be some global heuristic algorithms that can estimate how
many pessimistic blocks (at least one block for sure) to output during the
$\mathsf{Dumbo}$ phase according to the known public information in the log
(e.g., how many times Bolt completely fails in a stream). Designing such a
heuristic to better fit the real-world Internet environments could be an
interesting engineering question to explore in the future but does not impact
any security analysis in this paper.

Let $e$ be the epoch number, $Esize$ be the epoch size parameter, $\tau$ be
the timeout parameter of optimistic paths, $T$ be a time parameter to check
suspicious transaction censorship, and $\mathsf{buf}$ be a FIFO queue of input
transactions with a known maximum size $X$ (namely, once $\mathsf{buf}$ is
full, it becomes blocking) initialize $e=1$, a local $timer(\tau)$, and all
parties $\mathcal{P}_{i}$ runs the protocol in consecutive epoch numbered $e$
as follows: • activate $\mathsf{Bolt}[e]$ instance, $S\leftarrow\\{\\}$,
$2$-$\mathsf{notarized}=\emptyset$ and $1$-$\mathsf{notarized}=\emptyset$ •
while $s\leq Esize$ then:  // optimistic path – $timer(\tau).start()$ – upon
$\mathsf{Bolt}[e]$ delivers a $\mathsf{block}$: parse
$\mathsf{block}$:=$(e,r_{i},\mathsf{TXs}_{r_{i}},\mathsf{Proof}_{r_{i}})$
@itemiii if for any $\mathsf{tx}\in\mathsf{TXs}_{r_{i}}$,
$\mathsf{tx}\notin\mathsf{log}$ and $\mathsf{tx}\notin 2$-$\mathsf{notarized}$
and $\mathsf{tx}\notin 1$-$\mathsf{notarized}$ then: $timer(\tau).restart$
$\cdot$ if $2$-$\mathsf{notarized}=\emptyset$ then:
$2$-$\mathsf{notarized}\leftarrow$ $1$-$\mathsf{notarized}$,
$1$-$\mathsf{notarized}\leftarrow\mathsf{block}$ $\cdot$ if
$2$-$\mathsf{notarized}\neq\emptyset$ then:
$\mathsf{log}.append(2$-$\mathsf{notarized})$,
$2$-$\mathsf{notarized}\leftarrow$ $1$-$\mathsf{notarized}$,
$1$-$\mathsf{notarized}\leftarrow\mathsf{block}$,
$~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mathsf{buf}=\mathsf{buf}\setminus\\{\mathsf{TXs}\textrm{
in }2\textrm{-}\mathsf{notarized}\\}$ • upon $timer(\tau)$ timeout or
$s>Esize$ or the top (oldest) tx in $\mathsf{buf}$ stays for $T$ clock
“ticks”: // the optimistic path seemingly fails or completes – invoke
$\mathsf{abandon}(e)$, parse
$1$-$\mathsf{notarized}$:=$(e,{p}_{i},\mathsf{TXs}_{{p}_{i}},\mathsf{Proof}_{{p}_{i}})$,
then multicast $\textsc{PaceSync}(e,{p}_{i},\mathsf{Proof}_{{p}_{i}})$ //
broadcast the pace and its proof • upon receiving message
$\textsc{PaceSync}(e,{p}_{j},\mathsf{Proof}_{{p}_{j}})$ from $P_{j}$ for the
first time: – if $\mathsf{Bolt.Verify}(e,{p}_{j},\mathsf{Proof}_{{p}_{j}})=1$
then: $S=S\cup{p}_{j}$ – upon $|S|=2f+1$ // into pace sync @itemiii call
$\mathsf{Transformer}$($e$, $S$, $2$-$\mathsf{notarized}$,
$1$-$\mathsf{notarized}$, ${p}_{i}$) and wait for it returns @itemiii proceed
to next epoch $e\leftarrow e+1$ // return to the next optimistic epoch
function $\mathsf{Transformer}$($e$, $S$, $2$-$\mathsf{notarized}$,
$1$-$\mathsf{notarized}$, ${p}_{i}$): • let
$\mathsf{maxpace}_{e}\leftarrow\max(S)$, then pass $\mathsf{maxpace}_{e}$ to
$\mathsf{tcv\textnormal{-}BA}[e]$ as input • wait for that
$\mathsf{tcv\textnormal{-}BA}[e]$ returns $p$ then:
$\mathsf{pace}_{e}\leftarrow\max(p-1,0)$ // sync to slot $\mathsf{pace}_{e}$ •
if $\mathsf{pace}_{e}=0$ then: invoke $\mathsf{Dumbo}(e)$ and wait for its
return  // pessimistic path (adapted from [17]) • if $\mathsf{pace}_{e}>0$
then: – if $2$-$\mathsf{notarized}\neq\emptyset$ and
$\mathsf{pace}={p}_{i}-1$: $\mathsf{log}.append(2$-$\mathsf{notarized})$,
$\mathsf{buf}=\mathsf{buf}\setminus\\{\mathsf{TXs}\textrm{ in
}2\textrm{-}\mathsf{notarized}\\}$ – if $2$-$\mathsf{notarized}\neq\emptyset$
and $\mathsf{pace}\geq{p}_{i}$:
$\mathsf{log}.append(2$-$\mathsf{notarized}).append(1$-$\mathsf{notarized})$,
$\mathsf{buf}=\mathsf{buf}\setminus\\{\mathsf{TXs}\textrm{ in
}1\textrm{-}\mathsf{notarized}\textrm{ and }2\textrm{-}\mathsf{notarized}\\}$
@itemiii let $\mathsf{gap}\leftarrow\mathsf{pace}_{e}-2-{p}_{i}$, if
$\mathsf{gap}>0$ then: invoke $\mathsf{CallHelp}(|\mathsf{log}|,\mathsf{gap})$
// see Fig. 8 function $\mathsf{Dumbo}$($e$):  // the reduction to ACS from
[14]; the underlying ACS from [17] • let $\mathsf{TXs}\leftarrow[{\ }]$,
$\mathsf{TX}_{i}$ be a random selection of $\left\lfloor B/n|m|\right\rfloor$
transactions from the first $B$ elements of $\mathsf{buf}$ • encrypt
$x_{i}\leftarrow\mathsf{TPKE}.\mathsf{Enc}(epk,\mathsf{TX}_{i})$ // threshold
encryption • pass $x_{i}$ as input to $\mathsf{ACS}[e]$, then wait to receive
$\\{x_{j}\\}_{j\in S}$ from $\mathsf{ACS}[e]$, where $S\subset[n]$ //
Dumbo2-ACS • for each $j\in S$ do: // threshold decryption – let
$e_{j}\leftarrow\mathsf{TPKE}.\mathsf{DecShare}(esk_{i},x_{j})$, then
multicast $\textsc{Dec}(e,i,j,e_{i,j})$ to all – waiting for $f+1$ Dec
messages $\textsc{Dec}(e,k,j,e_{k,j})$, then
$\mathsf{TX}_{j}\leftarrow\mathsf{TPKE}.\mathsf{Dec}(epk,\\{k,e_{k,j}\\})$,
$\mathsf{TXs}\leftarrow\mathsf{TXs}\cup\mathsf{TX}_{j}$ • let
$\mathsf{block}:=(e,1,\mathsf{TXs},\bot)$, then
$\mathsf{log}.append(\mathsf{block})$,
$\mathsf{buf}=\mathsf{buf}\setminus\\{\mathsf{TXs}\textrm{ in
}\mathsf{block}\\}$ and return // Note that there might exist some common
heuristics to compute an integer $y$ based on the public states (e.g., how
many times Bolt have completely failed in a stream), and then repeat the above
code for $y$ times instead of only executing once. Nevertheless, this would
not impact our security proof.

Figure 7: $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$
protocol

upon receiving message $\textsc{CallHelp}(e,\mathsf{tip},\mathsf{gap})$ from
party $\mathcal{P}_{j}$: • assert $1\leq\mathsf{gap}\leq Esize$ • retrieve all
blocks in $\mathsf{log}$ with epcoh field $e$ to form $\mathsf{log}_{e}$ • if
$\mathsf{tip}+\mathsf{gap}\leq|\mathsf{log}_{e}|$ then – let
$M\leftarrow\mathsf{log}_{e}[\mathsf{tip}+1:\mathsf{tip}+\mathsf{gap}]$ – let
$\\{m_{k}\\}_{k\in[n]}$ to be the blocks of an $(n-2f,n)$-erasure coding
scheme applied to $M$, and $h$ to be a Merkle tree root computed over
$\\{m_{k}\\}_{k\in[n]}$ – send
$\textsc{Help}(e,\mathsf{tip},\mathsf{gap},h,m_{i},b_{i})$ to
$\mathcal{P}_{j}$, where $m_{i}$ is the $i$-th erasure coding block of $M$,
and $b_{i}$ is the $i$-th branch of Merkle tree rooted from $h$ function
$\mathsf{CallHelp}(\mathsf{tip},\mathsf{gap})$: • multicast message
$\textsc{CallHelp}(e,\mathsf{tip},\mathsf{gap})$ • upon receiving the message
$\textsc{Help}(e,\mathsf{tip},\mathsf{gap},h,m_{j},b_{j})$ from node
$\mathcal{P}_{j}$ – check that $b_{j}$ is a valid Merkle branch for root $h$
and leaf $m_{j}$, otherwise discard • upon receiving $n-2f$ valid
$\textsc{Help}(e,\mathsf{tip},\mathsf{gap},h,\cdot,\cdot)$ messages from
distinct nodes $\\{\mathcal{P}_{j}\\}$ – interpolate the $n-2f$ leaves
$\\{m_{i}\\}$ to reconstruct $M$ – parse $M$ as a sequence of
$\mathsf{block}s$, then $\mathsf{log}.append(\mathsf{blocks})$,
$\mathsf{buf}=\mathsf{buf}\setminus\\{\mathsf{TXs}\textrm{ in
}\mathsf{blocks}\\}$ and return

Figure 8: $\mathsf{Help}$ and $\mathsf{CallHelp}$

###  VI-B Analyzing the $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\
}Transformer}$ construction

Here we prove that the $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\
}Transformer}$ protocol satisfies all properties of atomic broadcast in the
asynchronous authenticated message-passing network against the computationally
bounded adversary. For presentation brevity, all events/messages/subprotocols
mentioned down below are associated to the same epoch and all statements
hereafter are true with all but negligible probabilities in our asynchronous
system model.

Safety Proof. Here is proof for total-order and agreement.

###### Lemma 3

If an honest party activates $\mathsf{tcv\textnormal{-}BA}[e]$, at least
$n-2f$ honest parties have already invoked $\mathsf{abandon}(e)$ to quit
$\mathsf{tcv\textnormal{-}BA}[e]$, and from now on: any party (including the
faulty ones) cannot receive (or forge) a valid $\mathsf{Bolt}[e]$ block that
has a slot number larger than all existing $\mathsf{Bolt}[e]$ blocks, and all
honest parties would activate $\mathsf{tcv\textnormal{-}BA}[e]$, ensuring the
termination of $\mathsf{tcv\textnormal{-}BA}[e]$.

Proof: When an honest party $\mathcal{P}_{i}$ activates
$\mathsf{tcv\textnormal{-}BA}[e]$, it must have received $n-f$ valid PaceSync
messages from distinct parties, so there would be at least $n-2f$ honest nodes
multicast PaceSync messages. It also means that at least $n-2f$ honest parties
have invoked $\mathsf{abandon}(e)$, so from now on, no party would deliver any
valid optimistic $\mathsf{block}$ in this epoch’s $\mathsf{Bolt}$ phase due to
the abandonability property of $\mathsf{Bolt}$. Therefore, all honest parties
will eventually interrupted by the “timeout” mechanism after $\tau$
asynchronous rounds and then multicast PaceSync messages. This would ensure
that all honest parties eventually receive $n-f$ valid PaceSync messages from
distinct nodes. $\hfill\square$

###### Lemma 4

Suppose that some party receives a valid $\mathsf{block}$:=$\langle
e,R,\cdot,\cdot\rangle$ from $\mathsf{Bolt}[e]$ when an honest party invokes
$\mathsf{tcv\textnormal{-}BA}[e]$ s.t. this $\mathsf{block}$ is the one with
largest slot number among all parties’ valid $1$-$\mathsf{notarized}$ blocks
(which means the union of the honest parties’ actual $1$-$\mathsf{notarized}$
blocks and the malicious parties’ arbitrary valid $\mathsf{Bolt}[e]$ block),
then all honest parties’ $\mathsf{maxpace}_{e}$ must be same and be either $R$
or $R-1$.

Proof: Following Lemma 3, since one honest party invokes
$\mathsf{tcv\textnormal{-}BA}[e]$, then it means the $\mathsf{Bolt}[e]$ block
with the largest slot number $R_{max}$ would not change anymore. Let us call
this already fixed $\mathsf{Bolt}[e]$ block with highest slot
$\mathsf{block}_{max}$. Since there is someone that receives
$\mathsf{block}_{max}$:=$\langle e,R,\cdot,\cdot\rangle$, at least $f+1$
honest parties have already received the block $\langle
e,R-1,\cdot,\cdot\rangle$ from $\mathsf{Bolt}[e]$, which is because the
notarizability property of $\mathsf{Bolt}$. So these honest parties would
broadcast a valid $\textsc{PaceSync}(e,R-1,\cdot)$ message or a valid
$\textsc{PaceSync}(e,R,\cdot)$ message. According to the pseudocode in Figure
7, $\mathsf{maxpace}_{e}$ is the maximum number of the set of $S$. Note $S$
contains the slot numbers encapsulated by $2f+1$ valid PaceSync messages, so
$S$ must contain one PaceSync message’s slot number from these same $f+1$
honest nodes that broadcast $\textsc{PaceSync}(e,R-1,\cdot)$ or
$\textsc{PaceSync}(e,R,\cdot)$. Hence, all honest parties’ $S$ must contain
$R-1$ and/or $R$. Moreover, there is no valid PaceSync message containing any
slot larger than $R$, that means $R$ is the largest possible value in all
honest parties’ $S$. Therefore, all honest parties’ $\mathsf{maxpace}_{e}$
must be either $R$ or $R-1$. $\hfill\square$

###### Lemma 5

If $\mathsf{tcv\textnormal{-}BA}[e]$ returns $h$, then at least $f+1$ honest
parties have already received the $\mathsf{Bolt}$ phase $\mathsf{block}$s with
slot numbers from $1$ to $h-1$ from the $\mathsf{Bolt}[e]$ instance.

Proof: Suppose $\mathsf{tcv\textnormal{-}BA}[e]$ returns $h$, according to the
validity of $\mathsf{tcv\textnormal{-}BA}$, then at least one honest party
inputs the number $h$. The same honest party must receive a valid message
$\textsc{PaceSync}(e,h,\cdot)$, which means there must exists a valid
$\mathsf{Bolt}$ block $\langle e,h,\cdot,\mathsf{Proof}_{h}\rangle$. Following
the notarizability and total-order properties of $\mathsf{Bolt}$, at least
$f+1$ honest parties already deliver $\mathsf{Bolt}$ blocks from $\langle
e,h-1,\cdot,\cdot\rangle$ till $\langle e,1,\cdot,\cdot\rangle$.
$\hfill\square$

###### Lemma 6

No honest party would get a $\mathsf{pace}_{e}$ smaller than the slot number
of it latest finalized block $\mathsf{log}[-1]$ (i.e., no block finalized in
some honest party’s $\mathsf{log}$ can be revoked).

Proof: Suppose the $\mathsf{Bolt}$ phase block $\langle
e,R,\cdot,\cdot\rangle$ is the one with largest slot number among the union of
the honest parties’ actual $1$-$\mathsf{notarized}$ blocks and the malicious
parties’ arbitrary valid $\mathsf{Bolt}[e]$ block, when $f+1$ honest parties
invoke $\mathsf{abandon}(e)$ (i.e., $\mathsf{Bolt}[e]$ has completely stopped
in the sense that it will not return any block having a slot number larger
than $R$). Then we consider the next two cases:

  1. 1.

Only malicious parties have this block $\langle e,R,\cdot,\cdot\rangle$ block;

  2. 2.

Some honest party $\mathcal{P}_{i}$ also has the $\langle
e,R,\cdot,\cdot\rangle$ block.

For Case 1) Due to the notarizability property of $\mathsf{Bolt}$ and this
case’s baseline, there exist $f+1$ honest parties (denoted by a set $Q$) have
the block $\langle e,R-1,\cdot,\cdot\rangle$ as their local
$1$-$\mathsf{notarized}$ and have the block $\langle e,R-2,\cdot,\cdot\rangle$
as their local $2$-$\mathsf{notarized}$. Note that remaining honest parties
(denoted by a set $\bar{Q}$) would have local $1$-$\mathsf{notarized}$ block
not higher than $R-1$ and local $2$-$\mathsf{notarized}$ block not higher than
$R-2$. Because of Lemma 4, all honest parties will activate
$\mathsf{tcv\textnormal{-}BA}[e]$ with taking either $R$ or $R-1$ as input.
According to the validity of $\mathsf{tcv\textnormal{-}BA}$, the output must
be either $R$ or $R-1$. Finally, according to the algorithm in Figure 7, we
can state that: (i) if the output is $R$, then all honest parties will sync
their $\mathsf{log}$ up to the block $\langle e,R-1,\cdot,\cdot\rangle$ (which
include all honest parties’ local $2$-$\mathsf{notarized}$ and
$1$-$\mathsf{notarized}$), and their $\mathsf{log}$ would be common because of
the notarizability and total-order properties of $\mathsf{Bolt}$; (ii)
similarly, if the output is $R-1$, all honest parties will sync up till
$\langle e,R-2,\cdot,\cdot\rangle$ (which include all honest parties’ local
$2$-$\mathsf{notarized}$). So in this case, all honest parties (i.e.,
$\bar{Q}\cup Q$) will not discard their $2$-$\mathsf{notarized}$, let alone
discard some $\mathsf{Bolt}$ that are already finalized to output into
$\mathsf{log}$.

For Case 2) Let $Q$ denote the set of honest parties that have the block
$\langle e,R,\cdot,\cdot\rangle$ as their local $1$-$\mathsf{notarized}$ and
have the block $\langle e,R-1,\cdot,\cdot\rangle$ as their local
$2$-$\mathsf{notarized}$. Note the remaining honest parties $\bar{Q}$ would
have the $1$-$\mathsf{notarized}$ block not higher than $R-1$ and the
$2$-$\mathsf{notarized}$ block not higher than $R-2$. Because of Lemma 4, all
honest parties will activate $\mathsf{tcv\textnormal{-}BA}[e]$ with taking
either $R$ or $R-1$ as input. According to the validity of
$\mathsf{tcv\textnormal{-}BA}$, the output must be either $R$ or $R-1$.

Due to the algorithm in Figure 7, we can see that: (i) if the output is $R$,
then all honest parties will sync their $\mathsf{log}$ up to the block
$\langle e,R-1,\cdot,\cdot\rangle$ (which include $\bar{Q}$ parties’ local
$2$-$\mathsf{notarized}$ and $1$-$\mathsf{notarized}$ and ${Q}$ parties’ local
$2$-$\mathsf{notarized}$), and their $\mathsf{log}$ would be common; (ii)
similarly, if the output is $R-1$, all honest parties will sync up till
$\langle e,R-2,\cdot,\cdot\rangle$ (which include $\bar{Q}$ parties’ local
$1$-$\mathsf{notarized}$ and ${Q}$ parties’ finalized output $\mathsf{log}$).
So in this case, all honest parties (i.e., $\bar{Q}\cup Q$) will not discard
any block in their finalized $\mathsf{log}$. $\hfill\square$

###### Lemma 7

If an honest party invokes $\mathsf{CallHelp}$ function to retrieve a block
$\mathsf{log}[i]$, it eventually can get it; if another honest party retrieves
a block $\mathsf{log}[i]^{\prime}$ at the same log position $i$ from
$\mathsf{CallHelp}$, then $\mathsf{log}[i]=\mathsf{log}[i]^{\prime}$.

Proof: Due to Lemma 5, any block $\mathsf{log}[i]$ that an honest party is
retrieving through $\mathsf{CallHelp}$ function shall have been in the output
$\log$ of at least $f+1$ honest parties, so it eventually can get $f+1$
correct Help messages with the same Merkle tree root $h$ from distinct
parties, then it can interpolate the $f+1$ leaves to reconstruct
$\mathsf{log}[i]$ which is same to other honest parties’ local
$\mathsf{log}[i]$. We can argue the agreement by contradiction, in case the
interpolation of honest party fails or it recovers a block
$\mathsf{log}^{\prime}[i]$ different from the the honest party’s local
$\mathsf{log}[i]$, that means the Merkle tree with root $h$ commits some
leaves that are not coded fragments of $\mathsf{log}[i]$; nevertheless, there
is at least one honest party encode $\mathsf{log}[i]$ and commits the block’s
erasure code to have a Merkle tree root $h$; so the adversary deed breaks the
collision resistance of Merkle tree, which implies the break of the collision-
resistance of hash function, that is impossible. So the party must retrieve a
block $\mathsf{log}[i]$ consistent to other honest parties’ $\mathsf{log}[i]$.
$\hfill\square$

###### Lemma 8

If any two honest parties are during the $\mathsf{Bolt}$ phase or the
$\mathsf{Transformer}$ phase, there exists one party, such that its
$\mathsf{log}$ is a prefix of the other’s.

Proof: This is true, because the total-order property of $\mathsf{Bolt}$ as
well as Lemma 6 and Lemma 7. $\hfill\square$

###### Lemma 9

If all honest parties enter the $\mathsf{Bolt}$ phase with the same
$\mathsf{log}$, then they will always finish the $\mathsf{Transformer}$ phase
with still having the same $\mathsf{log}^{\prime}$.

Proof: When all honest parties enter the epoch, it is easy to see that they
all will raise the interruption to abandon the $\mathsf{Bolt}$ phase. Due to
Lemma 3, all parties would finish $\mathsf{tcv\textnormal{-}BA}[e]$ to get a
common $h$, and they can sync up to the same $\mathsf{log}$ with the highest
slot number $h-1$ (due to Lemma 7), and hence all parties would finish the
$\mathsf{Transformer}$ phase with having the same output $\mathsf{log}$.
$\hfill\square$

###### Lemma 10

If any honest party enters the $\mathsf{Dumbo}$ phase, then all honest parties
will enters the phase and always leave the phase with having the same
$\mathsf{log}$, and for any two honest parties during the phase, there exists
one party, such that its $\mathsf{log}$ is a prefix of the other’s.

Proof: If any honest party enter the $\mathsf{Dumbo}$ phase, all honest
parties would enter this phase, which is due to Lemma 3 and the agreement
property of $\mathsf{tcv\textnormal{-}BA}$. Let us assume that all honest
parties enter the $\mathsf{Dumbo}$ phase with the same $\mathsf{log}$, it
would be trivial too see the statement for the agreement and termination
properties of $\mathsf{ACS}$ and the correct and robustness properties of
threshold public key encryption. Then considering Lemma 9 and the simple fact
that all honest parties activate with the common empty $\mathsf{log}$, we can
inductively reason that all honest parties must enter any $\mathsf{Dumbo}$
phase with the same $\mathsf{log}$. So the Lemma holds. $\hfill\square$

###### Theorem 1

The $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ protocol
satisfies the agreement and total order properties.

Proof: This can be induced by Lemma 8, 9 and 10 along with the fact that all
honest parties initialize with the same empty $\mathsf{log}$ to enter the
first epoch’s $\mathsf{Bolt}$ phase. $\hfill\square$

Liveness Proof. Then let us prove the liveness property.

###### Lemma 11

Once all honest parties enter the $\mathsf{Bolt}$ phase, they must leave the
phase in at most constant asynchronous rounds and then all enter the
$\mathsf{Transformer}$ phase.

Proof: At worst case, all honest parties’ timeout will interrupt, causing them
abandon the $\mathsf{Bolt}$ phase in $\mathcal{O}(\tau+\kappa Esize)$
asynchronous rounds, where $\kappa$ could be a constant that depends on the
underlying $\mathsf{Bolt}$ instantiation. Upon timeout, the broadcast of
$\mathsf{PaceSync}$ will take one more asynchronous round. So all honest
parties would receive enough $\mathsf{PaceSync}$ messages to enter the
$\mathsf{Transformer}$ phase. $\hfill\square$

###### Lemma 12

If all honest parties enter the $\mathsf{Transformer}$ phase, they all leave
the phase in on-average constant asynchronous rounds and then enter the
$\mathsf{Dumbo}$ phase or the next epoch’s $\mathsf{Bolt}$ phase.

Proof: If all honest parties enter the $\mathsf{Transformer}$ phase is trivial
to see since the underlying $\mathsf{tcv\textnormal{-}BA}$ terminates in on-
average constant asynchronous rounds. $\hfill\square$

###### Lemma 13

all honest parties enter the $\mathsf{Bolt}$ phase, all honest parties will
leave this $\mathsf{Bolt}$ phase with outputting on-average
$\mathcal{O}(B)$-sized transactions.

Proof: Similar to [14]’s analysis, $\mathsf{Dumbo}$ at least outputs
$\mathcal{O}(B)$-sized transactions (without worrying that the adversary can
learn any bit about the transactions to be outputted before they are actually
finalized as output) for each execution (where $B$ is the batch size). Here we
remark that the original analysis in [14] only requires IND-CPA security of
threshold public key encryption might be not enough, since we need to simulate
that the adversary can query decryption oracle by inserting her ciphertext
into the ACS output. Moreover, the underlying $\mathsf{Dumbo}$ construction
would ensure all parties to leave the phase in on-average constant
asynchronous rounds. $\hfill\square$

###### Theorem 2

The $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ protocol
satisfies the censorship-resilience/liveness property .

Proof: Due to Lemma 11 and 12, the adversary would not be able to stuck the
honest parties during the $\mathsf{Bolt}$ and $\mathsf{Transformer}$ phases.
Even if in the worst cases, the two phases do not deliver any useful output
and the adversary intends to prevent the parties from running the
$\mathsf{Dumbo}$ phase (thus not eliminating any transactions from the honest
parties’ input buffer), we still have a timeout mechanism against censorship,
which can ensure to execute the $\mathsf{Dumbo}$ phase for every
$\mathcal{O}(T)$ asynchronous rounds if there is a suspiciously censored
$\mathsf{tx}$ in all honest parties’ buffers due to some timeout parameter
$T$. Recall Lemma 13, for each $\mathsf{tx}$ in all honest parties’ buffers,
it would take $\mathcal{O}(XT/B)$ asynchronous rounds at worst (i.e., we
always rely on the timeout $T$ to invoke the $\mathsf{Dumbo}$ phase) to make
$\mathsf{tx}$ be one of the top $B$ transactions in all parties’ buffers,
where $X$ is the bound of buffer size (e.g., an unfixed polynomial in
$\lambda$). After that, any luckily finalized optimistic phase block would
output $\mathsf{tx}$ (in few more $\delta$), or still relying on the timeout
to invoke the $\mathsf{Dumbo}$ phase, causing the worst case latency
$\mathcal{O}((X/B+\lambda)\delta T)$, which is a function in the actual
network delay $\delta$ factored by polynomials of security parameters. We
remark that the above analysis relies heavily on timeout parameters, and
proving a tighter bound of the liveness could an interesting further
extension. $\hfill\square$

Complexities. Here we analyze the
$\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ protocol
regarding its complexities, we always measure the performance of protocol for
per block. For each block, it at best can contain a batch of $B$-sized
transactions. Through the paper, we assume $B$ large enough, e.g.,
$\Omega(\lambda n^{2}\log n)$. Following the algorithm, the messages are
communicated in three phase. First, all parties participate in the optimistic
path $\mathsf{Bolt}$; second, all parties switches into the pace
synchronization phase $\mathsf{Transformer}$; third, all parties probably
participate in the pessimistic path $\mathsf{Dumbo}$.

For the optimistic path $\mathsf{Bolt}$, we have two instantiations, namely
$\mathsf{Bolt}$-$\mathsf{HS}$ and $\mathsf{Bolt}$-$\mathsf{RBC}$. As shown in
Table II, $\mathsf{Bolt}$-$\mathsf{HS}$ is with linear per-block message
complexity as $\mathcal{O}(B)$, but the leader’s per-block bandwidth usage is
linear in $n$ as $\mathcal{O}(nB)$; $\mathsf{Bolt}$-$\mathsf{RBC}$ is with
quadratic per-block message complexity as $\mathcal{O}(n^{2})$, while no
party’s per-block bandwidth usage is more than the batch size
$\mathcal{O}(B)$; for both “fastlane” instantiations, the generation of each
$\mathsf{Bolt}$ block will cost exact $\mathcal{O}(1)$ rounds. Remark that
their differences in performance metrics cause their quite different favoring,
namely, $\mathsf{Bolt}$-$\mathsf{HS}$ favors latency and
$\mathsf{Bolt}$-$\mathsf{HS}$ favors throughput (which can be verified in our
experiments conducted across the globe in various settings, c.f., Figure 10
and 9).

TABLE II: Per-block performance of $\mathsf{Bolt}$ instantiations | Msg. | Comm. | Round | Bandwidth Cost
---|---|---|---|---
| Leader | Others
$\mathsf{Bolt}$-$\mathsf{HS}$ | $\mathcal{O}(n)$ | $\mathcal{O}(nB)$ | $\mathcal{O}(1)$ | $\mathcal{O}(nB)$ | $\mathcal{O}(B)$
$\mathsf{Bolt}$-$\mathsf{RBC}$ | $\mathcal{O}(n^{2})$ | $\mathcal{O}(nB)$ | $\mathcal{O}(1)$ | $\mathcal{O}(B)$ | $\mathcal{O}(B)$

During the $\mathsf{Transformer}$ phase, all parties would multicast a
PaceSync message and then participate in $\mathsf{tcv\textnormal{-}BA}$. The
message complexity is $\mathcal{O}(n^{2})$, the communication complexity is
$\mathcal{O}(\lambda n^{2})$ and the bandwidth cost for each nodes is
$\mathcal{O}(\lambda n)$. Besides, if the output value of
$\mathsf{tcv\textnormal{-}BA}$ large than 1, then the $\mathsf{CallHelp}()$
could probably be invoked, this process will incur $\mathcal{O}(n^{2})$
message complexity, $\mathcal{O}(nB)$ communication complexity, and
$\mathcal{O}(B)$ bandwidth cost for each party. The latency of generating each
block in this phase itself is on average $\mathcal{O}(1)$, if any block is
deed finalized. In addition, there is a worst-case overhead of
$\mathcal{O}(\tau)$ asynchronous rounds to leave this phase without generating
any meaningful blocks. In pessimistic phase, all nodes participate in
$\mathsf{Dumbo}$ subprotocol, then the message complexity is
$\mathcal{O}(n^{3})$, the communication complexity is $\mathcal{O}(nB)$ and
the bandwidth usage for each nodes is $\mathcal{O}(B)$.

To summarize these, we can have the worst-case per-block performance
illustrated in Table III, in which $\mathsf{BDT}$-$\mathsf{HS}$ means
$\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ with using
$\mathsf{Bolt}$-$\mathsf{HS}$ as “fastlane” and $\mathsf{BDT}$-$\mathsf{RBC}$
is the instantiation using $\mathsf{Bolt}$-$\mathsf{RBC}$ as “fastlane”. Note
that their major difference is the bandwidth usage at the fastlane’s leader
side.

TABLE III: Per-block performance of
$\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$ (worst case)

| Msg. | Comm. | Round | Bandwidth Cost
---|---|---|---|---
| Leader | Others
$\mathsf{BDT}$-$\mathsf{HS}$ | $\mathcal{O}(n^{3})$ | $\mathcal{O}(nB)$ |  $\mathcal{O}(\tau)$∗ | $\mathcal{O}(nB)$ | $\mathcal{O}(B)$
$\mathsf{BDT}$-$\mathsf{RBC}$ | $\mathcal{O}(n^{3})$ | $\mathcal{O}(nB)$ |  $\mathcal{O}(\tau)$∗ | $\mathcal{O}(B)$ | $\mathcal{O}(B)$

∗ Note $\mathcal{O}(\tau)$ can be closed to $\mathcal{O}(1)$, since we
essentially let $\tau$ “clock ticks” to approximate the new block “heartbeats”
in $\mathsf{Bolt}$ paths with $\mathcal{O}(1)$-period.

##  VII Performance Evaluation

To showcase the applicability of $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\
}Transformer}$, we perform intensive experiments and evaluate the performance
of its prototype implementation across the global Internet among AWS servers
evenly distributed in five continents, respectively. Along the way, we also
comprehensively compare it to $\mathsf{HotStuff}$ and $\mathsf{Dumbo}$, i.e.,
the state-of-the-art pipelined partially synchronous BFT and the state-of-the-
art asynchronous BFT, in the same global Internet setting.

Our experiments across 64 and 100 global AWS servers support an affirmative
proposition that $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$
(BDT) can hopefully achieve the best of its both paths deployed in the wide-
area network environments:

  * •

In the benign test cases (when each epoch’s $\mathsf{Bolt}$ path always
succeeds and then smoothly moves to the next epoch’s $\mathsf{Bolt}$ path
after doing the pace synchronization via $\mathsf{Transformer}$), we verify
that $\mathsf{BDT}$ can enjoy quick confirmation as fast as
$\mathsf{HotStuff}$ despite the $\mathsf{Transformer}$ overhead (i.e., 36
times faster than $\mathsf{Dumbo}$), demonstrating how cheap the critical
$\mathsf{Transformer}$ subprotocol is to make $\mathsf{BDT}$ applicable on
good days.

  * •

In the somewhat worse scenarios when $1/3$ optimistic paths are timed out due
to $n/3$ crash faults, our results demonstrate how efficient the
$\mathsf{BDT}$ framework can still be, as it achieves a throughput nearly as
high as the robust $\mathsf{Dumbo}$’s (i.e., twice of $\mathsf{HotStuff}$’s )
while remaining an average latency one order of magnitude smaller than
$\mathsf{Dumbo}$’s , indicating how applicable $\mathsf{BDT}$ is for its cheap
$\mathsf{Transformer}$.

  * •

Even if in the arguable worst cases when all optimistic $\mathsf{Bolt}$
executions halt to progress, we realize $\mathsf{BDT}$ only has slightly
increased latency when comparing to $\mathsf{Dumbo}$, e.g., only few more
seconds than $\mathsf{Dumbo}$’s (when their throughputs are same).

Implementation tips. The prototype implementations of BDT, $\mathsf{Dumbo}$
and $\mathsf{HotStuff}$ are written in Python 3. For fair comparison, we
implement $\mathsf{Dumbo}$ and $\mathsf{HotStuff}$ in the same language, with
using the same libraries and security parameters for all underlying
cryptographic implementations.

All the BFT protocols are implemented as a single-core Python process with
using gevent library to handle concurrent tasks. Besides, the exactly same
network layer is programmed by using unauthenticated TCP sockets. The network
layer is implemented as a separate Python process to provide non-blocking
communication interfaces to all BDT, $\mathsf{Dumbo}$ and $\mathsf{HotStuff}$
implementations. Inter-process communications between the BFT process and the
network process are optimized for broadcasting, thus a message broadcast
incurs only constant communication between the two processes.

For common coin, it is realized by hashing the Boldyreva’s pairing-based
threshold signature, and we borrow the same implementation used in HBBFT over
MNT224 curve [14]. For threshold signature (except the one used for common
coin), we use ECDSA over secp256k1 curve with using coincurve library, i.e.,
Python bindings for libsecp256k1 library, which helps us achieve a
$\mathsf{Dumbo}$ implementation that can perform better than the original
result [17] where Boldyreva’s threshold signature [40] is used. For threshold
public key encryption, the hybrid encryption approach implemented in HBBFT is
used [14]. For erasure coding, the Reed-Solomon implementation in the zfec
library is used as same as [14] and [17].

Experiment setup on Amazon EC2. To demonstrate the applicability of our scheme
in the real-world environment, we run $\mathsf{BDT}$ (as well as
$\mathsf{Dumbo}$ and $\mathsf{HotStuff}$ for benchmarking) on Amazon EC2
c5.large instances (which are equipped with 2 vCPUs and 4 GB memory). We
perform comprehensive evaluations for varying protocol parameters on 64
c5.large instances and 100 c5.large instances, respectively. All EC2 instances
in our tests are evenly distributed in 16 AWS regions across five continents,
i.e., Virgina, Ohio, California, Oregon, Central Canada, San Paulo, Frankfurt,
Ireland, London, Paris, Stockholm, Mubai, Seoul, Singapore, Tokyo, Sydney.

In the AWS tests, we might fix some parameters of $\mathsf{BDT}$ to
intentionally amplify the overhead of the $\mathsf{Transformer}$ phase. For
example, we let each optimistic path interrupted after outputting at most
merely 50 blocks, so the $\mathsf{Transformer}$ phase is always frequently
invoked. We also set the optimistic path’s timeout $\tau$ be as large as 2.5
seconds (which is about a magnitude larger than the worst network delay among
AWS’s global regions), so all timeout-triggered fallbacks include this
conservative 2.5 seconds overhead in addition to the execution delay of
$\mathsf{Transformer}$.

Optimistic path choices. We implement two $\mathsf{Bolt}$ protocols presented
in Section IV. $\mathsf{Bolt\textnormal{-}Dumbo\textnormal{\ }Transformer}$
with using the HotStuff-style $\mathsf{Bolt}$-$\mathsf{HS}$ is denoted by
$\mathsf{BDT}$-$\mathsf{HS}$, while the other instantiation with using
$\mathsf{PRBC}$ based $\mathsf{Bolt}$-$\mathsf{RBC}$ is denoted by
$\mathsf{BDT}$-$\mathsf{RBC}$. In addition, a simple idle procedure that does
nothing and just waits for timeout is also a theoretic “implementation” of
$\mathsf{Bolt}$, which is denoted as $\mathsf{BDT}$-$\mathsf{timeout}$ and
might be used as benchmark to “mimic” the worst cases that $\mathsf{Bolt}$
always fails to output anything.

Basic latency. In our experiments, we measure the latency of a transaction as
the time elapsed between the moment when it appears at the top of a party’s
input transaction buffer and the moment when it is outputted to the finalized
log of blocks. It worth to noticing that we cannot assume a transaction is
confirmed if a $\mathsf{Bolt}$ block including it is just received, since this
block is just $1$-$\mathsf{notarized}$ block, and we have to wait two more
$\mathsf{Bolt}$ blocks for its finalization to safely count the transaction’s
latency.

Figure 9: Minimum latency in experiments over wide-area network for
$\mathsf{HotStuff}$, $\mathsf{BDT}$-$\mathsf{HS}$,
$\mathsf{BDT}$-$\mathsf{RBC}$ and $\mathsf{Dumbo}$ (if no fault).

The first latency metric for us to measure is the basic latency shown in
Figure 9 to reflect how fast the protocol is in the zero-payload case. Though
this case is somewhat extreme, it provides us the baseline understanding about
how fast BDT, $\mathsf{HotStuff}$ and $\mathsf{Dumbo}$ can be to handle the
scenarios favoring low-latency. Figure 9 reveals that: in terms of basic
latency, $\mathsf{BDT}$-$\mathsf{HS}$ is 36x faster than $\mathsf{Dumbo}$ and
$\mathsf{BDT}$-$\mathsf{RBC}$ is 23x faster than $\mathsf{Dumbo}$ when
$n=100$, $\mathsf{BDT}$-$\mathsf{HS}$ is 18x faster than $\mathsf{Dumbo}$ and
$\mathsf{BDT}$-$\mathsf{RBC}$ is 10x faster than $\mathsf{Dumbo}$ when $n=64$;
moreover, the execution speed of both $\mathsf{BDT}$-$\mathsf{HS}$ and
$\mathsf{BDT}$-$\mathsf{RBC}$ are at the same magnitude of
$\mathsf{HotStuff}$, in particular, the basic latency of
$\mathsf{BDT}$-$\mathsf{HS}$ is almost as same as $\mathsf{Hotstuff}$.

Peak throughput. We measure throughput in unit of transactions per second
(where each transaction is a 250 bytes string to approximate the size of a
typical Bitcoin transaction). In each test run, throughput therefore can be
computed as the number of transactions that are finalized to output over the
time of the protocol execution.

Figure 10: Highest throughput in experiments over wide-area network for
$\mathsf{HotStuff}$, $\mathsf{BDT}$-$\mathsf{HS}$,
$\mathsf{BDT}$-$\mathsf{RBC}$ and $\mathsf{Dumbo}$ (if no fault).

The first measurement performed from the throughput aspect is the peak
throughput shown in Figure 10 to reflect the upper limit of processing
transactions of each BFT protocol. This gives us an insight how well BDT,
$\mathsf{HotStuff}$ and $\mathsf{Dumbo}$ can handle the application scenarios
favoring throughput. The results shows that: $\mathsf{BDT}$-$\mathsf{HS}$
realizes a peak throughput that remains about 85% of $\mathsf{HotStuff}$’s
when either $n$ is 100 or 64, $\mathsf{BDT}$-$\mathsf{RBC}$ achieves a maximum
throughput that is as high as around 90% of $\mathsf{Dumbo}$’s for $n=64$ case
and about 85% of $\mathsf{Dumbo}$’s for $n=100$ case. All these throughput
peaks are achieved despite frequent $\mathsf{Transformer}$ executions since we
intend to let each fastlane to switch after 50 blocks.

$\mathsf{Transformer}$ overhead (in worst cases). It is critical for us to
understand the extra cost incurred by $\mathsf{Transformer}$, since lower cost
of the $\mathsf{Transformer}$ phase will free us from worrying too much on the
overhead caused by failures of the optimistic paths, and therefore more
aggressive design spaces (e.g., a tighter $\tau$ chosen to more closed to each
block’s generation latency in the $\mathsf{Bolt}$ path) such as smaller
timeout parameter $\tau$ can be attempted to squeeze performance out of any
periods that are good days. To this end, we estimate such overhead from two
different perspectives as shown in Figure 11 and 12.

Figure 11: Latency of voting on optimistic progress in
$\mathsf{BDT}$-$\mathsf{HS}$ and $\mathsf{BDT}$-$\mathsf{RBC}$, when there is
no fault and 1/3 crash, respectively.

First, as shown in Figure 11, we measure the execution time of the
$\mathsf{Transformer}$ component in various settings by taking combinations of
the following setups: (i) to execute $\mathsf{BDT}$-$\mathsf{HS}$ or
$\mathsf{BDT}$-$\mathsf{RBC}$; (ii) to enable or disable $1/3$ crashes; (iii)
to deploy across 64 EC2 instances or 100 EC2 instances. The result indicates
that: in case of executing $\mathsf{BDT}$-$\mathsf{RBC}$, the
$\mathsf{Transformer}$ phase is always smaller than 1 second, no matter $n$
and the (dis)able of crashes, which is really cheap relative to the high cost
of running $\mathsf{Dumbo}$; in all cases, $\mathsf{BDT}$-$\mathsf{HS}$ has a
$\mathsf{Transformer}$ phase taking longer time to run than
$\mathsf{BDT}$-$\mathsf{RBC}$, which is because in
$\mathsf{BDT}$-$\mathsf{RBC}$, all parties would more likely take the same
input to $\mathsf{tcv\textnormal{-}BA}$, causing this randomized module easier
to terminate and thus saving considerable overhead in $\mathsf{Transformer}$.

Figure 12: Latency v.s. throughput for experiments of $\mathsf{BDT}$ with a
timeout-only optimistic path (i.e., just wait 2.5 seconds to fallback).

Second, as illustrated in Figure 12, we measure the latency-throughput
tradeoffs for $\mathsf{BDT}$-$\mathsf{timeout}$, namely, to see how much
$\mathsf{BDT}$ is worse than $\mathsf{Dumbo}$ when $\mathsf{BDT}$’s fastlane
never works. This is arguably the worst test vector for $\mathsf{BDT}$, since
relative to $\mathsf{Dumbo}$, it always costs extra 2.5 seconds to timeout and
then executes the extra $\mathsf{Transformer}$ subprotocol. Nevertheless, the
result shows that even if having so much extra cost, the performance
degradation in terms of comparing to $\mathsf{Dumbo}$ is still acceptable,
since for the same throughput, $\mathsf{BDT}$ always only spends few more
seconds to output (much of which is resulted from the conservation 2.5 seconds
timeout waiting).

Figure 13: Latency v.s. batch size for experiments over wide-area network
(when there is no fault).

Varying batch size. Though the concrete meaning of batch might be different
for different BFT protocols, it in general captures the number of transactions
in each block. To understanding how this parameter matters in the BFT
protocols, we measure and report how throughput and latency depend on varying
batch sizes in Figure 13 and 14, respectively.

Figure 13 illustrates how latency increases with larger batch size in
$\mathsf{BDT}$-$\mathsf{RBC}$, $\mathsf{BDT}$-$\mathsf{HS}$,
$\mathsf{HotStuff}$ and $\mathsf{Dumbo}$ when $n=100$ and $n=64$,
respectively. It clearly states that: Dumbo always takes a latency much larger
than $\mathsf{BDT}$-$\mathsf{RBC}$, $\mathsf{BDT}$-$\mathsf{HS}$ and
$\mathsf{HotStuff}$; for $\mathsf{BDT}$-$\mathsf{RBC}$, its latency increases
very slowly relative to $\mathsf{BDT}$-$\mathsf{HS}$ and $\mathsf{HotStuff}$,
in particular when $B=10000$, the latency of $\mathsf{BDT}$-$\mathsf{RBC}$ is
around one second only, while these of $\mathsf{BDT}$-$\mathsf{HS}$ and
$\mathsf{HotStuff}$ have been more than 2 seconds. The slow increasing of
$\mathsf{BDT}$-$\mathsf{RBC}$’s latency is mainly because its better balanced
network load pattern.

Figure 14 illustrates how latency increases with larger batch size in
$\mathsf{BDT}$-$\mathsf{RBC}$, $\mathsf{BDT}$-$\mathsf{HS}$,
$\mathsf{HotStuff}$ and $\mathsf{Dumbo}$ when $n=100$ and $n=64$,
respectively. It is clear to see that: $\mathsf{Dumbo}$ really needs very
large batch size to make its throughput start to increase;
$\mathsf{BDT}$-$\mathsf{HS}$ and $\mathsf{HotStuff}$ again have a similar
trend; the throughput of $\mathsf{BDT}$-$\mathsf{RBC}$ is increasing faster
than those of $\mathsf{BDT}$-$\mathsf{HS}$ and $\mathsf{HotStuff}$, because
larger batch size would not place much worse bandwidth load on the leader and
therefore triggers less latency increase than $\mathsf{BDT}$-$\mathsf{HS}$ and
$\mathsf{Hotstuff}$.

Figure 14: Throughput v.s. batch size for experiments over wide-area network
(when there is no fault).

Latency-throughput trade-offs (no-faulty). It is shown in Figure 15 that
either $\mathsf{BDT}$-$\mathsf{HS}$ or $\mathsf{BDT}$-$\mathsf{RBC}$ is much
faster than $\mathsf{Dumbo}$ by several orders of magnitude in all cases,
while those two $\mathsf{BDT}$ instantiations have different favors leaning
towards distinct scenarios.

$\mathsf{BDT}$-$\mathsf{HS}$ has a latency-throughput trade-off similar to
$\mathsf{HotStuff}$’s, in particular when $n=100$, their latency-throughput
curves are nearly closed. Comparing to $\mathsf{Dumbo}$’s,
$\mathsf{BDT}$-$\mathsf{HS}$ has a clear trend favoring latency. For example,
when fixing throughput around 5000 tps, $\mathsf{BDT}$-$\mathsf{HS}$ has only
a latency of around $0.5$ second when $n=64$ and a latency of about $0.9$
second when $n=100$, in contrast $\mathsf{Dumbo}$ needs about 10 seconds or 20
seconds to realize the same throughput for $n=64$ and $n=100$, respectively.
This results in the difference of latency in several magnitudes when requiring
only moderate throughput, say 5000 tps.

$\mathsf{BDT}$-$\mathsf{RBC}$ has a latency-throughput trend quite different
from $\mathsf{HotStuff}$ and $\mathsf{BDT}$-$\mathsf{HS}$. Namely, when fixing
larger throughput, $\mathsf{BDT}$-$\mathsf{RBC}$ has a latency less than
$\mathsf{BDT}$-$\mathsf{HS}$’s, while fixing some small throughput,
$\mathsf{BDT}$-$\mathsf{RBC}$ is slower than $\mathsf{BDT}$-$\mathsf{HS}$.
This separates them clearly in terms of their suitable application scenarios,
since $\mathsf{BDT}$-$\mathsf{RBC}$ is always the better choice for large
throughput cases and $\mathsf{BDT}$-$\mathsf{HS}$ is more suitable for small
throughput scenarios. The rationale behind the different latency-throughput
favoring is that the $\mathsf{RBC}$ based optimistic path can leverage the
erasure coding technique to balance the network load, which causes eventual
better performance when leaning towards higher throughput.

Figure 15: Throughput v.s. latency for experiments over wide-area network
(when there is no fault).

Latency-throughput trade-offs (1/3 crashes). We also report the latency-
throughput trade-offs of $\mathsf{BDT}$-$\mathsf{HS}$,
$\mathsf{BDT}$-$\mathsf{RBC}$, $\mathsf{HotStuff}$ and $\mathsf{Dumbo}$ for
$n=100$ and $n=64$ case when there are $1/3$ crashed parties in the system.
Those crashes would not only lag the execution of all protocols, but also
simulate the worse cases when a portion of $\mathsf{Bolt}$ paths fail (since
our exemplary $\mathsf{Bolt}$ instantiations employ stable leader). To
simulate a crash fault, we let the network layer process keeps on receiving
messages (which do not allow the honest parties to save bandwidth due to these
crashes) but drops all incoming message as well as all outgoing messages.
Remark that we might fix the batch size of the pessimistic path of
$\mathsf{BDT}$-$\mathsf{HS}$ and $\mathsf{BDT}$-$\mathsf{RBC}$ to be $10^{6}$
transactions in these tests with $1/3$ crashed faults.

Shown in Figure 16, both $\mathsf{BDT}$-$\mathsf{HS}$ and
$\mathsf{BDT}$-$\mathsf{RBC}$ have some design spaces that show a latency
better than $\mathsf{Dumbo}$’s and presents a throughput always better than
$\mathsf{HotStuff}$’s, despite that on avergae the $\mathsf{Bolt}$ paths in
$1/3$ epochs would unluckily wait for 2.5 seconds to timeout without making
any optimistic output. That means the “hybrid” art of combining the
deterministic path and the randomized path does create new design space for
us, where we can achieve reasonable throughput and latency simultaneously.

Figure 16: Throughput v.s. latency for experiments over wide-area network
(when there is 1/3 crash fault). We fix the fallback batch size of
$\mathsf{BDT}$ instances to $10^{6}$ transactions in both of the 64-node and
100-node tests.

## References

  * [1] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2008.
  * [2] V. Buterin, “A next-generation smart contract and decentralized application platform.”
  * [3] G. Wood, “Ethereum: A secure decentralised generalised transaction ledger,” _Ethereum project yellow paper_ , 2014.
  * [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] E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. De Caro, D. Enyeart, C. Ferris, G. Laventman, Y. Manevich _et al._ , “Hyperledger fabric: a distributed operating system for permissioned blockchains,” in _Proceedings of the Thirteenth EuroSys Conference_. ACM, 2018, p. 30.
  * [6] M. J. FISCHER, N. A. LYNCH, and M. S. PATERSON, “Impossibility of distributed consensus with one faulty process,” _Journal of the Assccktion for Computing Machinery_ , vol. 32, no. 2, pp. 374–382, 1985.
  * [7] M. Castro, B. Liskov _et al._ , “Practical byzantine fault tolerance,” in _OSDI_ , vol. 99, no. 1999, 1999, pp. 173–186.
  * [8] A. Bessani, J. Sousa, and E. E. Alchieri, “State machine replication for the masses with bft-smart,” in _2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks_. IEEE, 2014, pp. 355–362.
  * [9] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong, “Zyzzyva: speculative byzantine fault tolerance,” in _ACM SIGOPS Operating Systems Review_ , vol. 41, no. 6. ACM, 2007, pp. 45–58.
  * [10] G. G. Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. Reiter, D.-A. Seredinschi, O. Tamir, and A. Tomescu, “Sbft: a scalable and decentralized trust infrastructure,” in _2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_. IEEE, 2019, pp. 568–580.
  * [11] 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_. ACM, 2019, pp. 347–356.
  * [12] Y. Amoussou-Guenou, A. Del Pozzo, M. Potop-Butucaru, and S. Tucci-Piergiovanni, “Correctness of tendermint-core blockchains,” in _22nd International Conference on Principles of Distributed Systems (OPODIS 2018)_ , 2018.
  * [13] T.-H. H. Chan, R. Pass, and E. Shi, “Pala: A simple partially synchronous blockchain.” _IACR Cryptology ePrint Archive_ , vol. 2018, p. 981, 2018.
  * [14] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The honey badger of bft protocols,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2016, pp. 31–42.
  * [15] D. Dolev and H. R. Strong, “Authenticated algorithms for byzantine agreement,” _SIAM Journal on Computing_ , vol. 12, no. 4, pp. 656–666, 1983\.
  * [16] R. Pass and E. Shi, “Thunderella: Blockchains with optimistic instant confirmation,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2018, pp. 3–33.
  * [17] B. Guo, Z. Lu, Q. Tang, J. Xu, and Z. Zhang, “Dumbo: Faster asynchronous bft protocols,” in _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 803–818.
  * [18] Y. Lu, Z. Lu, Q. Tang, and G. Wang, “Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited,” in _Proceedings of the 39th Symposium on Principles of Distributed Computing_ , 2020, pp. 129–138.
  * [19] K. Kursawe and V. Shoup, “Optimistic asynchronous atomic broadcast,” in _International Colloquium on Automata, Languages, and Programming_. Springer, [2002] 2005, pp. 204–215.
  * [20] H. V. Ramasamy and C. Cachin, “Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast,” in _International Conference On Principles Of Distributed Systems_. Springer, 2005, pp. 88–102.
  * [21] C. Cachin, K. Kursawe, F. Petzold, and V. Shoup, “Secure and efficient asynchronous broadcast protocols,” in _Annual International Cryptology Conference_. Springer, 2001, pp. 524–541.
  * [22] I. Abraham, D. Malkhi, and A. Spiegelman, “Asymptotically optimal validated asynchronous byzantine agreement,” in _Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing_. ACM, 2019, pp. 337–346.
  * [23] S. Duan, M. K. Reiter, and H. Zhang, “Beat: Asynchronous bft made practical,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2018, pp. 2028–2041.
  * [24] I. Abraham, D. Malkhi, K. Nayak, L. Ren, and M. Yin, “Sync hotstuff: Simple and practical synchronous state machine replication,” in _Proceedings of the 41th IEEE Symposium on Security and Privacy_. IEEE, 2020.
  * [25] N. Shrestha, I. Abraham, L. Ren, and K. Nayak, “On the optimality of optimistic responsiveness,” in _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ , 2020, pp. 839–857.
  * [26] A. Momose, J. P. Cruz, and Y. Kaji, “Hybrid-bft: Optimistically responsive synchronous consensus with optimal latency or resilience.” _IACR Cryptol. ePrint Arch._ , vol. 2020, p. 406, 2020.
  * [27] E. Blum, J. Katz, and J. Loss, “Synchronous consensus with optimal asynchronous fallback guarantees,” in _Theory of Cryptography Conference_. Springer, 2019, pp. 131–150.
  * [28] E. Blum, C.-D. Liu-Zhang, and J. Loss, “Always have a backup plan: fully secure synchronous mpc with asynchronous fallback,” in _Annual International Cryptology Conference_. Springer, 2020, pp. 707–731.
  * [29] E. Blum, J. Katz, and J. Loss, “Network-agnostic state machine replication,” _arXiv preprint arXiv:2002.03437_ , 2020.
  * [30] J. Loss and T. Moran, “Combining asynchronous and synchronous byzantine agreement: The best of both worlds.” _IACR Cryptol. ePrint Arch._ , vol. 2018, p. 235, 2018.
  * [31] V. Shoup, “Practical threshold signatures,” in _International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2000, pp. 207–220.
  * [32] V. Shoup and R. Gennaro, “Securing threshold cryptosystems against chosen ciphertext attack,” in _International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 1998, pp. 1–16.
  * [33] D. Boneh, X. Boyen, and S. Halevi, “Chosen ciphertext secure public key threshold encryption without random oracles,” in _Cryptographers’ Track at the RSA Conference_. Springer, 2006, pp. 226–243.
  * [34] 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_. ACM, 2000, pp. 123–132.
  * [35] A. Mostefaoui, H. Moumen, and M. Raynal, “Signature-free asynchronous byzantine consensus with $t<n/3$ and $\mathcal{O}(n^{2})$ messages,” in _Proceedings of the 2014 ACM symposium on Principles of distributed computing_. ACM, 2014, pp. 2–9.
  * [36] L. Lamport, R. Shostak, and M. Pease, “The byzantine generals problem,” _ACM Transactions on Programming Languages and Systems (TOPLAS)_ , vol. 4, no. 3, pp. 382–401, 1982.
  * [37] C. Cachin, K. Kursawe, A. Lysyanskaya, and R. Strobl, “Asynchronous verifiable secret sharing and proactive cryptosystems,” in _Proceedings of the 9th ACM Conference on Computer and Communications Security_ , 2002, pp. 88–97.
  * [38] M. Ben-Or, “Another advantage of free choice (extended abstract) completely asynchronous agreement protocols,” in _Proceedings of the second annual ACM symposium on Principles of distributed computing_ , 1983, pp. 27–30.
  * [39] R. Canetti and T. Rabin, “Fast asynchronous byzantine agreement with optimal resilience,” in _Proceedings of the twenty-fifth annual ACM symposium on Theory of computing_. ACM, 1993, pp. 42–51.
  * [40] A. Boldyreva, “Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme,” in _International Workshop on Public Key Cryptography_. Springer, 2003, pp. 31–46.