9

# Dumbo-NG: Fast Asynchronous BFT Consensus with Throughput-Oblivious Latency

Yingzi Gao  ISCAS & UCAS<EMAIL_ADDRESS>,  Yuan Lu  ISCAS
<EMAIL_ADDRESS>,  Zhenliang Lu  USYD<EMAIL_ADDRESS>,  Qiang
Tang  USYD<EMAIL_ADDRESS>,  Jing Xu  ISCAS<EMAIL_ADDRESS>and
Zhenfeng Zhang  ISCAS<EMAIL_ADDRESS>
(2022)

###### Abstract.

Despite recent progresses of practical asynchronous Byzantine-fault tolerant
(BFT) consensus, the state-of-the-art designs still suffer from suboptimal
performance. Particularly, to obtain maximum throughput, most existing
protocols  with guaranteed linear amortized communication complexity require
each participating node to broadcast a huge batch of transactions, which
dramatically sacrifices latency. Worse still, the $f$ slowest nodes’
broadcasts might never be agreed to output and thus can be censored (where $f$
is the number of faults). Implementable mitigation to the threat either uses
computationally costly threshold encryption or incurs communication blow-up by
letting the honest nodes to broadcast redundant transactions, thus causing
further efficiency issues.

We present $\mathsf{Dumbo\textrm{-}NG}$, a novel asynchronous BFT consensus
(atomic broadcast) to solve the remaining practical issues. Its technical core
is a non-trivial direct reduction from asynchronous atomic broadcast to multi-
valued validated Byzantine agreement ($\mathsf{MVBA}$) with quality property
(which ensures the $\mathsf{MVBA}$ output is from honest nodes with 1/2
probability). Most interestingly, the new protocol structure empowers
completely concurrent execution of transaction dissemination and asynchronous
agreement. This brings about two benefits: (i) the throughput-latency tension
is resolved to approach peak throughput with minimal increase in latency; (ii)
the transactions broadcasted by any honest node can be agreed to output, thus
conquering the censorship threat with no extra cost.

We implement $\mathsf{Dumbo\textrm{-}NG}$ with using the current fastest
GLL+22 $\mathsf{MVBA}$ with quality (NDSS’22) and compare it to the state-of-
the-art asynchronous BFT with guaranteed censorship resilience including
$\mathsf{Dumbo}$ (CCS’20) and Speeding-$\mathsf{Dumbo}$ (NDSS’22). Along the
way, we apply the techniques from Speeding-$\mathsf{Dumbo}$ to
$\mathsf{DispersedLedger}$ (NSDI’22) and obtain an improved variant of
$\mathsf{DispersedLedger}$ called $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ for
comprehensive comparison. Extensive experiments (over up to 64 AWS EC2 nodes
across 16 AWS regions) reveal: $\mathsf{Dumbo\textrm{-}NG}$ realizes a peak
throughput 4-8x over $\mathsf{Dumbo}$, 2-4x over Speeding-$\mathsf{Dumbo}$,
and 2-3x over $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ (for varying scales);
More importantly, $\mathsf{Dumbo\textrm{-}NG}$’s latency, which is lowest
among all tested protocols, can almost remain stable when throughput grows.

Asynchronous consensus, Byzantine-fault tolerance, blockchain

††journalyear: 2022††copyright: acmcopyright††conference: ACM SIGSAC
Conference on Computer and Communications Security (CCS’22); November 7-11,
2022; Los Angeles, USA††booktitle: ACM Conference on Computer and
Communications Security (CCS’22), November 7-11, 2022, Los Angeles,
USA††price: 15.00††isbn: 978-1-4503-9450-5/22/11††doi:
XX.XXXX/XXXXXX.XXXXX††ccs: Security and privacy Systems security; Distributed
systems security††ccs: Computer systems organization Reliability

##  1\. Introduction

The huge success of Bitcoin (Nakamoto, 2008) and blockchain (Buterin, 2014;
Cachin and Vukolić, 2017) leads to an increasing tendency to lay down the
infrastructure of distributed ledger for mission-critical applications. Such
decentralized business is envisioned as critical global infrastructure
maintained by a set of mutually distrustful and geologically distributed nodes
(Baudet et al., 2019), and thus calls for consensus protocols that are both
secure and efficient for deployment over the Internet.

Asynchronous BFT for indispensable robustness. The consensus of decentralized
infrastructure has to thrive in a highly adversarial environment. In
particular, when the applications atop it are critical financial and banking
services, some nodes can be well motivated to collude and launch malicious
attacks. Even worse, the unstable Internet might become part of the attack
surface due to network fluctuations, misconfigurations and even network
attacks. To cope with the adversarial deployment environment, asynchronous
Byzantine-fault tolerant (BFT) consensuses (Cachin et al., 2001; Miller et
al., 2016; Duan et al., 2018; Guo et al., 2020; Abraham et al., 2019; Lu et
al., 2020) are arguably the most suitable candidates. They can realize high
security-assurance to ensure liveness (as well as safety) despite an
asynchronous adversary that can arbitrarily delay messages. In contrast, many
(partial) synchronous consensus protocols (Amoussou-Guenou et al., 2018; Chan
and Shi, 2020; Gueta et al., 2019; Bessani et al., 2014; Pass and Shi, 2018;
Amir et al., 2010; Guerraoui et al., 2010; Veronese et al., 2009; Aublin et
al., 2013) such as PBFT (Castro et al., 1999) and HotStuff (Yin et al., 2019)
might sustain the inherent loss of liveness (i.e., generate unbounded
communications without making any progress) (Miller et al., 2016; Fischer et
al., 1985) when unluckily encountering an asynchronous network adversary.

###  1.1. Practical obstacles of adopting
asynchronous BFT consensus

Unfortunately, it is fundamentally challenging to realize practical
asynchronous BFT consensus, and none of such protocols was widely adopted due
to serious efficiency concerns. The seminal FLP “impossibility” (Fischer et
al., 1985) proves that no deterministic consensus exists in the asynchronous
network. Since the 1980s, many attempts (Ben-Or, 1983; Rabin, 1983; Canetti
and Rabin, ; Patra et al., 2009; Abraham et al., 2008; Cachin et al., 2005;
Ben-Or and El-Yaniv, 2003) aimed at to circumventing the “impossibility” by
randomized protocols, but most of them focused on theoretical feasibility, and
unsurprisingly, several attempts of implementations (Cachin and Poritz, 2002;
Moniz et al., 2008) had inferior performance.

Until recently, the work of $\mathsf{HoneyBadger}$ BFT ($\mathsf{HBBFT}$)
demonstrated the first asynchronous BFT consensuses that is performant in the
wide-area network (Miller et al., 2016). As shown in Figure 1,
$\mathsf{HBBFT}$ was instantiated by adapting the classic asynchronous common
subset ($\mathsf{ACS}$) protocol of Ben-Or et al. (Ben-Or et al., 1994). It
firstly starts $n$ parallel reliable broadcasts ($\mathsf{RBC}$s) with
distinct senders. Here $n$ is the total number of nodes, and $\mathsf{RBC}$
(Bracha, 1987) emulates a broadcast channel via point-to-point links to allow
a designated sender to disseminate a batch of input transactions. However, we
cannot ensure that every honest node completes a certain $\mathsf{RBC}$ after
a certain time due to asynchrony. So an agreement phase is invoked to select
$n-f$ completed and common $\mathsf{RBC}$s (where $f$ is the number of allowed
faulty nodes). In $\mathsf{HBBFT}$, the agreement phase consists of $n$
concurrent asynchronous binary Byzantine agreement ($\mathsf{ABBA}$). Each
$\mathsf{ABBA}$ corresponds to a $\mathsf{RBC}$, and would output 1 (resp. 0)
to solicit (resp. omit) the corresponding $\mathsf{RBC}$ in the final
$\mathsf{ACS}$ output.

Figure 1. Execution flow of an epoch in $\mathsf{HBBFT}$, $\mathsf{Dumbo}$ and
their variants. The protocols proceed by consecutive epochs.

The above $\mathsf{ACS}$ design separates the protocol into bandwidth-
intensive broadcast phase and bandwidth-oblivious agreement phase. Here the
broadcast is bandwidth-intensive (i.e., latency heavily relies on available
bandwidth), because of disseminating a large volume of transactions; and the
agreement is bandwidth-oblivious (i.e., latency depends on network prorogation
delay more than bandwidth), as it only exchanges a few rounds of short
messages. $\mathsf{HBBFT}$ then focused on optimizing the bandwidth-intensive
part—transaction broadcasts. It adapted the techniques of using erasure code
and Merkle tree from verifiable information dispersal (Cachin and Tessaro,
2005) to reduce the communication cost of Bracha’s $\mathsf{RBC}$ (Bracha,
1987), and realized amortized $\mathcal{O}(n)$ communication complexity for
sufficiently large input batch. As such, $\mathsf{HBBFT}$ can significantly
increase throughput via batching more transactions, but its $n$ concurrent
$\mathsf{ABBA}$s incurred suboptimal expected $\mathcal{O}(\log n)$ rounds. A
recent work $\mathsf{Dumbo}$ (Guo et al., 2020) concentrated on the latency-
critical part consisting of $n$ $\mathsf{ABBA}$s, and used a single
asynchronous multi-valued validated Byzantine agreement ($\mathsf{MVBA}$) to
replace the slow $n$ $\mathsf{ABBA}$s. Here $\mathsf{MVBA}$ is another variant
of asynchronous $\mathsf{BA}$ whose output satisfies a certain global
predicate, and can be constructed from 2-3 $\mathsf{ABBA}$s (e.g., CKPS01
(Cachin et al., 2001)) or from more compact structures (e.g., AMS19 (Abraham
et al., 2019) and GLL+22 (Guo et al., 2022)). Thanks to more efficient
agreement phase based on $\mathsf{MVBA}$, $\mathsf{Dumbo}$ reduced the
execution rounds from expected $\mathcal{O}(\log n)$ to $\mathcal{O}(1)$, and
achieved an order-of-magnitude of improvement on practical performance.

Actually, since $\mathsf{HBBFT}$ (Miller et al., 2016), a lot of renewed
interests in addition to $\mathsf{Dumbo}$ are quickly gathered to seriously
explore whether asynchronous protocols can ever be practical (Duan et al.,
2018; Gagol et al., 2019; Abraham et al., 2019; Keidar et al., 2021; Yang et
al., 2022).

Notwithstanding, few existing “performant” asynchronous BFT consensuses can
realize high security assurance, low latency, and high throughput,
simultaneously. Here down below we briefly reason two main practical obstacles
in the cutting-edge designs.

Throughput that is severely hurting latency. A serious practicality hurdle of
many existing asynchronous protocols (e.g. $\mathsf{HBBFT}$ and
$\mathsf{Dumbo}$) is that their maximum throughput is only achievable when
their latency is sacrificed. As early as 2016, $\mathsf{HBBFT}$ (Miller et
al., 2016) even explicitly argued that latency is dispensable for throughput
and robustness, if aiming at the decentralized version of payment networks
like VISA/SWIFT. The argument might be correct at the time of 2016, but after
all these years, diverse decentralized applications have been proposed from
quick inter-continental transactions (Chase and MacBrough, 2018) to instant
retail payments (Baudet et al., 2019). Hence it becomes unprecedentedly urgent
to implement robust BFT consensus realizing high throughput while preserving
low latency.

To see the reason behind the throughput-latency tension in the existing
performant asynchronous BFT protocols (with linear amortized communication
complexity) such as $\mathsf{HBBFT}$/$\mathsf{Dumbo}$, recall that these
protocols consist of two main phases—the bandwidth-intensive transaction
dissemination phase and the bandwidth-oblivious agreement phase. Different
from the dissemination phase that contributes into throughput, the agreement
phase just hinders throughput, as it “wastes” available bandwidth in the sense
of incurring large latency to block successive epochs’ broadcasts. Thus, to
sustain high throughput, each node has to broadcast a huge batch of
transactions to “contend” with the agreement phase to seize most available
bandwidth resources.

However, larger batches unavoidably cause inferior latency, although they can
saturate the network capacity to obtain the maximum throughput. For example,
Figure 2 clarifies: (i) when each node broadcasts a small batch of 1k tx in
$\mathsf{Dumbo}$ ($n$=16), the latency is not that bad (2.39 sec), but the
throughput is only 4,594 tx/sec, as the transaction dissemination only takes
16.5% of all running time; (ii) when the batch size increases to 30k tx, the
broadcast of transactions possesses more than 50% of the running time, and the
throughput becomes 37,620 tx/sec for better utilized bandwidth, but the
latency dramatically grows to nearly 9 sec.

Figure 2. Latency breakdown of $\mathsf{Dumbo}$ (on 16 Amazon EC2 c5.large
instances across different regions). $|B|$ is batch size, i.e., the number of
tx to broadcast by each node (where each tx is 250-byte to approximate the
size of Bitcoin’s basic tx). TPKE is a technique from $\mathsf{HBBFT}$ for
preventing censorship.

Liveness111Remark that liveness in the asynchronous setting cannot be
guaranteed by merely ensuring protocols to progress without stuck. It needs to
consider the liveness notion (e.g. validity from (Cachin et al., 2001)) to
ensure that any tx input by sufficient number of honest nodes must eventually
output, which was widely adopted in (Miller et al., 2016; Duan et al., 2018;
Guo et al., 2020, 2022; Keidar et al., 2021; Yang et al., 2022; Gagol et al.,
2019). relies on heavy cryptography or degraded efficiency. Besides the
unpleasant throughput-latency tension, the asynchronous protocols might also
face serious censorship threat. This is because during the transaction
dissemination phase, the adversarial network can delay the broadcasts
containing its disliked transactions and prevent the certain transactions from
being output.

To mitigate the censorship threat and ensure liveness, existing designs rely
on asymptotically larger communications, costly cryptographic operations, or
probably unbounded memory. Specifically,

  * $\bullet$

One somewhat trivial “solution” to censorship-resilience is to diffuse
transactions across all nodes and let every node work redundantly. Therefore,
even if the adversary can slow down up to $f$ honest nodes’ broadcasts, it
cannot censor a certain transaction $tx$, because other $n-2f$ honest nodes
still process $tx$. This is the exact idea in Cachin et al.’s asynchronous
atomic broadcast protocol (Cachin et al., 2001), but clearly incurs another
$\mathcal{O}(n)$ factor in the communication complexity. Recently,
$\mathsf{Tusk}$ (Danezis et al., 2022) leveraged de-duplication technique to
let a small number of $k$ nodes process each transaction according to
transaction hash (Stathakopoulou et al., 2019) or due to the choice of
clients. Here $k$ is expected a small security parameter to luckily draw a
fast and honest node. Nevertheless, an asynchronous adversary (even without
actual faults) can prevent up to $f$ honest nodes from eventually output in
$\mathsf{Tusk}$, and therefore the transactions duplicated to $k$ nodes can
still be censored unless $k\geq f+1$, i.e., $\mathcal{O}(n)$ redundant
communication still occurs in the worst case. That means, though de-
duplication techniques are enticing, we still need underlying consensus
stronger (e.g., any honest node’s input must eventually output) to reduce
redundant communication by these techniques without hurting liveness.

  * $\bullet$

As an alternative, $\mathsf{HBBFT}$ introduces threshold public key encryption
(TPKE) to encrypt the broadcast input.222 Remark that one also can use
asynchronous verifiable secret sharing (AVSS) to replace TPKE, since both can
implement a stronger consensus variant called casual broadcast (Cachin et al.,
2001), i.e., it first outputs transactions in a confidential manner, and then
reveals. We do not realize any practical censorship-resilience implementation
based on AVSS. Now, transactions are confidential against the adversary before
they are solicited into the final output, so that the adversary cannot learn
which broadcasts are necessary to delay for censoring a certain transaction.
But TPKE decryption could be costly. Figure 2 shows that in some very small
scales $n=16$, TPKE decryption already takes about 20% of the overall latency
in $\mathsf{Dumbo}$ (using the TPKE instantiation (Baek and Zheng, 2003) same
to $\mathsf{HBBFT}$). For larger scales, the situation can be worse, because
each node computes overall $\mathcal{O}(n^{2})$ operations for TPKE
decryptions.

  * $\bullet$

Recently, DAG-Rider (Keidar et al., 2021) presented a (potentially
unimplementable) defense against censorship: the honest nodes do not kill the
instances of the slowest $f$ broadcasts but forever listen to their delivery.
So if the slow broadcasts indeed have honest senders, the honest nodes can
eventually receive them and then attempt to put them into the final consensus
output. This intuitively can ensure all delayed broadcasts to finally output,
but also incurs probably unbounded memory because of listening an unbounded
number of broadcast instances that might never output due to corrupted senders
(as pointed out by (Danezis et al., 2022)).333 In DAG-Rider (Keidar et al.,
2021), every node has to keep on listening unfinished broadcasts. So if there
are some nodes get crashed or delayed for a long time, the honest nodes need
to listen more and more unfinished broadcasts with the protocol execution. The
trivial idea of killing unfinished broadcasts after some timeout would re-
introduce censorship threat, because this might kill some unfinished
broadcasts of slow but honest nodes.

Given the state-of-the-art of existing “performant” asynchronous BFT
consensuses, the following fundamental challenge remains:

Can we push asynchronous BFT consensus further to
realize minimum latency, maximum throughput, and
guaranteed censorship-resilience, simultaneously?

###  1.2. Our contribution

In short, we answer the above question affirmatively by presenting
$\mathsf{Dumbo\textrm{-}NG}$—a direct, concise and efficient reduction from
asynchronous BFT atomic broadcast to multi-valued validated Byzantine
agreement ($\mathsf{MVBA}$). In greater detail, the core contributions of
$\mathsf{Dumbo\textrm{-}NG}$ can be summarized as follows:

  * $\bullet$

Resolve the latency-throughput tension. $\mathsf{Dumbo\textrm{-}NG}$ resolves
the severe tension between throughput and latency in
$\mathsf{HBBFT}$/$\mathsf{Dumbo}$. Recall the issue stems from: for higher
throughput, the broadcasts in $\mathsf{HBBFT}$/$\mathsf{Dumbo}$ have to
sacrifice latency to disseminate a huge batch of transactions, and this is
needed to “contend” with the agreement modules to seize more bandwidth
resources.

$\mathsf{Dumbo\textrm{-}NG}$ solves the issue and can approach the maximum
throughput without trading latency, i.e., realize throughput-oblivious
latency. This is because it supports to run the bandwidth-intensive
transaction broadcasts completely concurrently to the bandwidth-oblivious
agreement modules. Remark that the concurrent execution of broadcasts and
agreement is non-trivial in the asynchronous setting, as we need carefully
propose and implement a few properties of broadcast and agreement to bound
communication complexity and ensure censorship resilience, cf. Section 2 for
detailed discussions about the challenges and why existing techniques to
parallelize agreement and broadcast (e.g., (Danezis et al., 2022)) cannot help
us simultaneously realize guaranteed censorship resilience in the hostile
asynchronous setting.

Table 1. Validity (liveness) of asynchronous atomic broadcast if stressing on
nearly linear amortized communication

|  Strong validity (Definition 4.1) ? |  Memory-bounded implementation?
---|---|---
|  DAG-Rider (Keidar et al., 2021),
---
$\mathsf{DispersedLedger}$ (Yang et al., 2022),
and $\mathsf{Aleph}$ (Gagol et al., 2019)
|  ✓ $*$
---
$\dagger$
|  $\mathsf{Tusk}$ (Danezis et al., 2022)
---
| ✗ suboptimal comm.;
---
or after GST $\ddagger$
✓
|  $\mathsf{HBBFT}$ (Miller et al., 2016),
---
$\mathsf{Dumbo}$ (Guo et al., 2020)
and variants (Duan et al., 2018; Guo et al., 2022)
| ✓ diffuse TX +
---
TPKE for de-duplication
✓
$\mathsf{Dumbo\textrm{-}NG}$ (this paper) |  |  ✓ $*$
---
✓

    * $*$

Here we assume de-duplicated input buffers in DAG-Rider,
$\mathsf{DispersedLedger}$ and $\mathsf{Dumbo\textrm{-}NG}$, which can be
realized (i) in a permissioned setting where a client only has permission to
contact several nodes or (ii) by de-duplication techniques (Crain et al., ;
Danezis et al., 2022; Stathakopoulou et al., 2019), cf. Footnote 4.

    * $\dagger$

The memory-bounded implementation of (Keidar et al., 2021; Yang et al., 2022;
Gagol et al., 2019) is unclear, cf. Footnote 3.

    * $\ddagger$

Though $\mathsf{Tusk}$ employs transaction de-duplication techniques to send
transactions to only $k$ nodes, it doesn’t realize strong validity, so still
needs $k=f+1$ to ensure all transactions to output in the worst-case
asynchronous network, cf. Footnote 4; and a recent improvement of
$\mathsf{Tusk}$— Bullshark (Giridharan et al., 2022) presents an
implementation that explicitly stresses on strong validity only after global
stabilization time (GST).

  * $\bullet$

Prevent censorship with minimal cost. As shown in Table 1, similar to DAG-
Rider (Keidar et al., 2021) and $\mathsf{DispersedLedger}$ (Yang et al.,
2022), $\mathsf{Dumbo\textrm{-}NG}$ ensures that any transaction input by an
honest node can eventually output (a.k.a. strong validity in (Cachin et al.,
2001)), and thus when building a state-machine replication (SMR) service
(Schneider, 1990) from such atomic broadcasts, one can expect to overcome
potential censorship with minimized extra cost (e.g., by directly using de-
duplication techniques (Danezis et al., 2022; Stathakopoulou et al.,
2019)).444 Remark that when implementing SMR API from atomic broadcast (i.e.,
adding clients), strong validity allows multiple simple de-duplication
techniques (Crain et al., ; Danezis et al., 2022; Stathakopoulou et al., 2019)
to preserve nearly optimal amortized communication cost, for example, a client
only has to send transactions to $k$ random consensus nodes (where $k$ can be
a small security parameter) instead of $\mathcal{O}(n)$ nodes. Also, strong
validity can realize best-possible liveness in a permissioned setting where a
client can only contact certain nodes. In contrast, if there is only weaker
validity and tx is diffused to less than $f+1$ honest nodes, tx can probably
be censored in a hostile asynchronous network, because the adversary can
constantly drop $f$ honest nodes’ inputs from output (even if there is
“quality” ensuring the other $f+1$ honest nodes’ inputs to output). See
Appendix A for details. So we call strong validity and censorship resilience
interchangeably, and can safely assume the honest parties have de-duplicated
input buffers containing mostly different transactions throughout the paper.
Such resilience of censorship is born with our new protocol structure, because
no matter how slow a broadcast can be, the concurrently running agreement
modules can eventually pick it into the final output through a quorum
certificate pointing to it. As such, $\mathsf{Dumbo\textrm{-}NG}$ does not
rely on additional heavy cryptographic operations (e.g, (Duan et al., 2018;
Guo et al., 2020, 2022)) or sub-optimal redundant communication (e.g., the
worst case of $\mathsf{Tusk}$ (Danezis et al., 2022)) to realize guaranteed
resistance against an asynchronous censorship adversary. This further
demonstrates the strength of our result w.r.t its security aspect in addition
to its practicality.

  * $\bullet$

By-product of adapting $\mathsf{DispersedLedger}$ to the state-of-the-art.
Along the way, we note that the recent work $\mathsf{DispersedLedger}$ was
explained by adapting the suboptimal $\mathsf{ACS}$ design from
$\mathsf{HBBFT}$, and it used an unnecessarily strong asynchronous verifiable
information dispersal (AVID) notion (Cachin and Tessaro, 2005) to facilitate
transaction dissemination. As a by-product and also sine qua non for fair
comparison, we adapt $\mathsf{DispersedLedger}$ to Speeding-$\mathsf{Dumbo}$
($\mathsf{sDumbo}$) (Guo et al., 2022) to enjoy the fast termination of the
state-of-the-art $\mathsf{ACS}$ design. A weaker thus cheaper information
dispersal notion—provable dispersal from $\mathsf{Dumbo}$-$\mathsf{MVBA}$ (Lu
et al., 2020) is also adopted to replace AVID. The resulting protocol (called
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$) realizes asymptotic improvement in
message and round complexities, and significantly outperforms
$\mathsf{sDumbo}$/$\mathsf{Dumbo}$ in terms of hurting latency less while
realizing maximum throughput.

Table 2. In comparison with existing performant asynchronous consensuses in
the WAN setting at $n$=4, 16, 64 nodes.

Protocol |  Peak throughput (tps)† |  Latency@peak-tps(sec)
---|---|---
$n$=4 |  $n$=16 |  $n$=64 |  $n$=4 |  $n$=16 |  $n$=64
$\mathsf{Dumbo}$ (Guo et al., 2020) | 22,038 | 40,943 | 28,747 | 11.85 | 13.43 | 29.91
Speeding $\mathsf{Dumbo}$ (Guo et al., 2022) | 38,545 | 74,601 | 43,284 | 4.86 | 7.37 | 15.45
$\mathsf{DispersedLedger}$‡(Yang et al., 2022) | 54,868 | 92,402 | 33,049 | 3.09 | 5.05 | 7.03
$\mathsf{Dumbo\textrm{-}NG}$ | 166,907 | 165,081 | 97,173 | 1.89 | 1.97 | 6.99

    * $\dagger$

Throughput of the protocols is evaluated in WAN settings consisting of Amazon
EC2 c5.large instances evenly distributed among up to 16 regions, and each
transaction is of 250 bytes.

    * $\ddagger$

We actually evaluate an improved $\mathsf{DispersedLedger}$ (called
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ by us) using cutting-edge techniques
from Speeding-$\mathsf{Dumbo}$ (Guo et al., 2022) and
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ (Lu et al., 2020), cf. Section 5 for details.

  * $\bullet$

Implementation and extensive experiments over the Internet. We implement
$\mathsf{Dumbo\textrm{-}NG}$ and extensively test it among $n=4$, 16 or 64
nodes over the global Internet, with making detailed comparison to the state-
of-the-art asynchronous protocols including $\mathsf{Dumbo}$ and two very
recent results—$\mathsf{DispersedLedger}$ (Yang et al., 2022) and
Speeding-$\mathsf{Dumbo}$ ($\mathsf{sDumbo}$) (Guo et al., 2022). At all
system scales, the peak throughput of $\mathsf{Dumbo\textrm{-}NG}$ is multiple
times better than any of the other tested asynchronous BFT ABC protocols,
e.g., 4-8x over $\mathsf{Dumbo}$, 2-4x over $\mathsf{sDumbo}$, and 2-3x over
the $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ version of
$\mathsf{DispersedLedger}$.

More importantly, the latency of $\mathsf{Dumbo\textrm{-}NG}$ is significantly
less than others (e.g., 4-7x faster than $\mathsf{Dumbo}$ when both protocols
realizes the maximum throughput). Actually, the latency of
$\mathsf{Dumbo\textrm{-}NG}$ is nearly independent to its throughput,
indicating how effective it is to resolve the throughput-latency tension lying
in the prior designs. As shown in Figure 3, we can quantitatively estimate
throughput-obliviousness by the increment ratio of latency from minimum to
(nearly) maximum throughputs. In particular, a protocol is said more
throughput-oblivious than another protocol, if such the ratio is much closer
to zero, so throughput obliviousness is an easily measurable metric that can
also be used in many other studies. For $n$=64, when the throughput increases
from minimum to maximum (around 100k tx/sec), the latency increment ratio of
$\mathsf{Dumbo\textrm{-}NG}$ is only 11% (increased by 0.72 sec); in contrast,
$\mathsf{Dumbo}$, $\mathsf{sDumbo}$ and $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$
suffer from 347% (28 sec), 141% (12 sec), 94% (3.4 sec) increment ratio (or
increment) in latency, respectively, when pumping up throughput from minimum
to maximum.

Figure 3. Latency increment of async. BFT when throughput increases from
minimum to maximum in the WAN setting for $n$=64 nodes (cf. Section 7 for
detailed experiment setup).

##  2\. Path to our solution

Here we take a brief tour to our solution, with explaining the main technical
challenges and how we overcome the barriers.

An initial attempt. A recent work $\mathsf{DispersedLedger}$ ($\mathsf{DL}$)
(Yang et al., 2022) also dissects $\mathsf{HBBFT}$ and recognizes the
efficiency hurdles lying in the bandwidth wasted during running the agreement
phase. Although $\mathsf{DispersedLedger}$ originally aimed at throughput
(more precisely, throughput in a variable network condition), it actually
presents a promising idea of separating the bandwidth-intensive transaction
dissemination and the bandwidth-oblivious agreement.

As Figure 4 illustrates, $\mathsf{DispersedLedger}$ splits $\mathsf{ACS}$ into
two concurrent paths: one path first disperses transactions (instead of direct
broadcast) and then agrees on which dispersed transactions to appear into the
final output; and the other path can concurrently retrieve the transactions
supposed to output. Here dispersal and retrieval can be implemented by
asynchronous verifiable information dispersal (Cachin and Tessaro, 2005).
Remarkably, the communication cost of dispersal can be asymptotically cheaper
than that of broadcast in $\mathsf{HBBFT}$/$\mathsf{Dumbo}$: the per node
commutation cost in the dispersal phase is $\mathcal{O}(|B|)$ bits, and per
node commutation cost in the retrieval phase is $\mathcal{O}(n|B|)$ bits, if
each node takes a sufficiently large $|B|$-sized input to $\mathsf{ACS}$.
Clearly, the retrieval phase becomes the most bandwidth-starving component,
and fortunately, it can be executed concurrently to the dispersal and
agreement phases of succeeding $\mathsf{ACS}$. This becomes the crux to help
$\mathsf{DispersedLedger}$ (DL) to outperform $\mathsf{HBBFT}$. To go one step
further (and test the limit of DL framework), we use the orthogonal techniques
from the $\mathsf{Dumbo}$ protocols (Guo et al., 2020; Lu et al., 2020; Guo et
al., 2022), particularly the very recent Speeding-$\mathsf{Dumbo}$ (Guo et
al., 2022), and get a protocol called $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$
that further reduces DL’s complexities and improves its practical metrics
significantly.

Figure 4. Execution flow of $\mathsf{DispersedLedger}$. Transaction retrieval
is executed concurrently to dispersal and agreement. Modules in the light-
orange region represents one $\mathsf{ACS}$.

However, the DL framework implements the idea of separating bandwidth-
intensive and bandwidth-oblivious modules in a sub-optimal way, in particular:
(i) dispersal is still blocked by the agreement phase of preceding
$\mathsf{ACS}$, so considerable batch sizes are still needed to fully utilize
the bandwidth; (ii) when large batch sizes are adopted for higher throughput,
the dispersal phase is no longer bandwidth-oblivious, and it also incurs a lot
of network workload, which significantly enlarges the latency.

Even if the improvements of $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ greatly
alleviates the above issues because of a much faster agreement phase, these
issues still take considerable effects to lag the confirmation. For example,
in our WAN experiment setting, to fully utilize the bandwidth while
GLL+22-$\mathsf{MVBA}$ is running, the needed batch size remains larger than
6MB (which even becomes about 20MB after applying erasure-code for fault-
tolerant retrieval).

In short, though $\mathsf{DispersedLedger}$ can realize considerable
improvement in throughput, it cannot preserve a stable latency while
approaching the maximum throughput (even after adapting it to the cutting-edge
$\mathsf{ACS}$ framework (Guo et al., 2022)), cf. Section 5 for more detailed
discussions on $\mathsf{DispersedLedger}$’s merits and bottlenecks.

Path to our final solution: barriers and techniques. Taking the merits and
issues of $\mathsf{DispersedLedger}$ constructively, we aim to make broadcast
and agreement to execute completely concurrently.

As Figure 5 illustrates, we let each node act as a sender in an ever-running
multi-shot broadcast to disseminate its input transactions, and concurrently,
run the agreement phase to pack the broadcasted transactions into the final
consensus output. Now, the bandwidth-intensive transaction dissemination is
continuously running to closely track the network capacity over all running
time, and no longer needs to use large batch sizes to contend with the
bandwidth-oblivious agreement modules for seizing network resources (as prior
art does). As such, it becomes promising to obtain the peak throughput without
hurting latency.

However, the seemingly simple idea of running broadcasts concurrent to
Byzantine agreement ($\mathsf{BA}$) is facing fundamental challenges in the
asynchronous setting. Here we briefly overview the barriers and shed a light
on our solution to tackle them.

Figure 5. High-level of $\mathsf{Dumbo\textrm{-}NG}$. Each node leads an ever-
running multi-shot broadcast to disseminate its input transactions. Aside from
broadcasts, a sequence of asynchronous multi-valued validated Byzantine
agreements ($\mathsf{MVBA}$s) are executed to totally order all broadcasted
transactions.

Challenge I: allow $\mathsf{BA}$ to pack broadcasts, concurrently & validly.
In an asynchronous network, the adversary can arbitrarily delay broadcasts,
and thus some multi-shot broadcast might progress very fast while some might
move forward much slower. So the concurrent Byzantine agreement modules have
to agree on the “valid” progress of each multi-shot broadcast instance, where
“valid” progress means the broadcast has indeed progressed up to here. The
above task, intuitively, is much more challenging than the agreement problem
in $\mathsf{HBBFT}$/$\mathsf{Dumbo}$/$\mathsf{DispersedLedger}$ (which only
decides 1/0 for each single-shot broadcast to mark whether the broadcast is
completed or not). At first glance, we seemingly need asynchronous
$\mathsf{BA}$ with strong validity, because the agreed broadcast progress
needs to be from some honest node to ensure it was indeed completed
(otherwise, the adversary can manipulate the agreement result to let honest
nodes agree on some broadcast progresses that were not completed). But,
unfortunately, strong validity is unimplementable for multi-valued agreement
in the asynchronous setting, as it needs huge communication cost exponential
in input length (Fitzi and Garay, 2003).

To circumvent the challenge, we carefully add quorum certificates to the
multi-shot broadcasts by threshold signature, such that the adversary cannot
forge a certificate for some uncompleted broadcast progress. In particular,
our multi-shot broadcast can be thought of a compact variant of running a
sequence of verifiable consistent broadcasts (Ramasamy and Cachin, 2005), in
which a quorum certificate can prove that the honest nodes either have
delivered (or can retrieve) the same sequence of all broadcasted transactions
(Danezis et al., 2022; Cachin et al., 2001). This allows us to design the
needed agreement module by (implementable) asynchronous $\mathsf{MVBA}$ with
fine-tuned external validity. We let $\mathsf{MVBA}$’s input/output to be a
vector of $n$ broadcasts’ certificates, and the external validity checks: (i)
all $n$ certificates are valid, (ii) at least $n-f$ certificates attest that
their corresponding $n-f$ broadcasts have progressed. As such, we can run a
sequence of $\mathsf{MVBA}$s completely concurrent to the $n$ ever-running
broadcasts, and each $\mathsf{MVBA}$ can pack $n-f$ progressed broadcasts to
form a final consensus output.

Challenge II: output all completed broadcasts to prevent censorship.

Nevertheless, external validity of $\mathsf{MVBA}$ is not enough to ensure
liveness, as it cannot guarantee that all progressed broadcasts can be
solicited by some $\mathsf{MVBA}$ to output, and the censorship threat is
still a valid concern. The reason behind the problem is: the conventional
$\mathsf{MVBA}$ notion (Cachin et al., 2001) allows the adversary to fully
decide the agreed result (as long as satisfying the external validity
condition), so in our context, the adversary can exclude up to $f$ honest
nodes’ broadcasts from the final consensus output.

To overcome this subtle issue, we realize that some recent $\mathsf{MVBA}$
protocols (Abraham et al., 2019; Lu et al., 2020; Guo et al., 2022) actually
have an additional quality property (at no extra cost). Here quality means
that with at least 1/2 probability (or other constant probability), the
$\mathsf{MVBA}$’s output is proposed by some honest node. Hence, if we
carefully choose an $\mathsf{MVBA}$ protocol with quality, liveness (aka
censorship-resilience) can be guaranteed because: once a broadcast’s quorum
certificate is received by all honest nodes, it will be decided to output
after expected 2 $\mathsf{MVBA}$s.

Our techniques v.s. $\mathsf{Tusk}$’s transaction diffuse. Recently,
$\mathsf{Tusk}$ (Danezis et al., 2022) adapted Prism’s (Bagaria et al., 2019)
core idea to separate transaction diffuse and agreement into the asynchronous
setting, and presented how to diffuse transactions concurrently to a compact
DAG-based asynchronous consensus: each node multicasts transaction batches to
the whole network and waits $n-f$ naive receipt acknowledgements, such that
the digests of transaction batches (instead of the actual transactions) can be
agreed inside $\mathsf{Tusk}$’s DAG. Nevertheless, the above transaction
diffuse does not generate quorum certificates for transaction retrievability
by itself, but relies on consistent broadcasts inside $\mathsf{Tusk}$’s DAG to
generate such certificates.

That means, diffused transactions of $f$ honest nodes might have no quorum
certificates generated for retrievability in $\mathsf{Tusk}$ because their
corresponding consistent broadcasts are never completed (and they will finally
be garbage collected). In contrast, we require every node (even the slowest)
can generate certificates for retrievability of its own input transactions
through a multi-shot broadcast instance. This is critical for preventing
censorship, because any honest node, no matter how slow it is, can generate
these certificates and use them to convince the whole network to solicit its
disseminated input into the final consensus output. This corresponds to the
reason why $\mathsf{Tusk}$’s transaction diffuse cannot directly replace our
transaction dissemination path without hurting censorship resilience.

##  3\. Other related work

Besides closely related studies (Danezis et al., 2022; Miller et al., 2016;
Guo et al., 2020, 2022; Keidar et al., 2021; Yang et al., 2022) discussed in
Introduction, there also exist a few works (Kursawe and Shoup, 2005; Ramasamy
and Cachin, 2005) including some very recent ones (Lu et al., 2022; Gelashvili
et al., ) that consider adding an optimistic “fastlane” to the slow
asynchronous atomic broadcast. The fastlane could simply be a fast leader-
based deterministic protocol. This line of work is certainly interesting,
however in the adversarial settings, the “fastlane” never succeeds, and the
overall performance would be even worse than running the asynchronous atomic
broadcast itself. This paper, on the contrary, aims to directly improve
asynchronous BFT atomic broadcast, and can be used together with the
optimistic technique to provide a better underlying pessimistic path. In
addition, BEAT (Duan et al., 2018) cherry-picked constructions for each
component in $\mathsf{HBBFT}$ (e.g., coin flipping and TPKE without pairing)
to demonstrate better performance in various settings, and many of its
findings can benefit us to choose concrete instantiations for the future
production-level implementation. There are also interesting works on
asynchronous distributed key generation (Gao et al., 2022; Das et al., 2021;
Kokoris Kogias et al., 2020; Abraham et al., 2021), which could be helpful to
remove the private setup phase in all recent asynchronous BFT protocols.

In addition to fully asynchronous protocols, a seemingly feasible solution to
robust BFT consensus is choosing a conservative upper bound of network delay
in (partially) synchronous protocols. But this might bring serious performance
degradation in latency, e.g., the exaggeratedly slow Bitcoin. Following the
issue, a large number of “robust” (partially) synchronous protocols such as
Prime (Amir et al., 2010), Spinning (Veronese et al., 2009), RBFT (Aublin et
al., 2013) and many others (Clement et al., 2009a, b) are also subject to this
robustness-latency trade-off. Let alone, none of them can have guaranteed
liveness in a pure asynchronous network, inherently (Fischer et al., 1985). In
addition, a few recent results (Shrestha et al., 2020; Pass and Shi, 2018;
Abraham et al., 2020) make synchronous protocols to attain fast (responsive)
confirmation in certain good cases, but still suffer from slow confirmation in
more general cases.

##  4\. Problem Definition & Preliminaries

###  4.1. System/threat models and design goals

System and adversary models. We adopt a widely-adopted asynchronous message-
passing model (Attiya and Welch, 2004; Cachin et al., 2001; Duan et al., 2018;
Abraham et al., 2019; Miller et al., 2016; Guo et al., 2020; Lu et al., 2020;
Cachin et al., 2005) with setup assumptions. In greater detail, we consider:

  * $\bullet$

Known identities & setup for threshold signature. There are $n$ designated
nodes in the system, each of which has a unique identity. W.o.l.g, their
identities are denoted from $\mathcal{P}_{1}$ to $\mathcal{P}_{n}$. In
addition, non-interactive threshold signature ($\mathsf{TSIG}$) is properly
set up, so all nodes can get and only get their own secret keys in addition to
the public keys. The setup can be done through distributed key generation
(Pedersen, 1991; Gennaro et al., 1999; Kate and Goldberg, 2009; Gao et al.,
2022; Das et al., 2021; Kokoris Kogias et al., 2020; Abraham et al., 2021; Das
et al., 2022) or a trusted dealer.

  * $\bullet$

$n/3$ Byzantine corruptions. We consider that up to $f=\lfloor(n-1)/3\rfloor$
nodes might be fully controlled by the adversary. Remark that our
implementation might choose statically secure threshold signature as a
building block for efficiency as same as other practical asynchronous
protocols (Guo et al., 2020; Miller et al., 2016; Duan et al., 2018), noticing
that a recent adaptively secure attempt (Liu et al., ) has dramatically
degraded throughput less than half of its static counterpart for moderate
scales $\sim$50 nodes. Nevertheless, same to (Cachin et al., 2001; Lu et al.,
2020; Abraham et al., 2019), our protocol can be adaptively secure to defend
against an adversary that might corrupt nodes during the course of protocol
execution, if given adaptively secure threshold signature (Libert et al.,
2016; Libert and Yung, 2011) and $\mathsf{MVBA}$ (Lu et al., 2020; Abraham et
al., 2019). Besides adaptively secure building blocks, the other cost of
adaptive security is just an $\mathcal{O}(n)$-factor communication blow-up in
some extreme cases.

  * $\bullet$

Asynchronous fully-meshed point-to-point network. We consider an asynchronous
message-passing network made of fully meshed authenticated point-to-point
(p2p) channels (Attiya and Welch, 2004). The adversary can arbitrarily delay
and reorder messages, but any message sent between honest nodes will
eventually be delivered to the destination without tampering, i.e., the
adversary cannot drop or modify the messages sent between the honest nodes. As
(Miller et al., 2016) explained, the eventual delivery of messages can be
realized by letting the sender repeat transmission until receiving an
acknowledge from the receiver. However, when some receiver is faulty, this
might cause an increasing buffer of outgoing messages, so we can let the
sender only repeat transmissions of a limited number of outgoing messages. To
preserve liveness in the handicapped network where each link only eventually
delivers some messages (not all messages), we let each message carry a quorum
certificate allowing its receiver sync up the latest progress, cf. Appendix B
for details.

Security goal. We aim at a secure asynchronous BFT consensus satisfying the
following atomic broadcast ($\mathsf{ABC}$) abstraction:

###### Definition 4.1.

In an atomic broadcast protocol among $n$ nodes against $f$ Byzantine
corruptions, each node has an implicit input transaction $\mathsf{buffer}$,
continuously selects some transactions from $\mathsf{buffer}$ as actual input,
and outputs a sequence of totally ordered transactions. In particular, it
satisfies the following properties with all but negligible probability:

  * $\bullet$

Agreement. If one honest node outputs a transaction $tx$, then every honest
node outputs $tx$;

  * $\bullet$

Total-order. If any two honest nodes output sequences of transactions $\langle
tx_{0},tx_{1},\dots,tx_{j}\rangle$ and $\langle
tx_{0}^{\prime},tx_{1}^{\prime},\dots,tx_{j^{\prime}}^{\prime}\rangle$,
respectively, then $tx_{i}=tx_{i}^{\prime}$ for $i\leq$ min$(j,j^{\prime})$;

  * $\bullet$

Liveness (strong validity (Cachin et al., 2001) or censorship resilience). If
a transaction $tx$ is input by any honest node, it will eventually output.

In (Cachin et al., 2001), Cachin et al. called the above liveness “strong
validity”, which recently was realized in DAG-rider (Keidar et al., 2021) and
$\mathsf{DispersedLedger}$ (Yang et al., 2022). As we explained in Footnote 4,
strong validity is particularly useful for implementing state-machine
replication API because it prevents censorship even if applying de-duplication
techniques. Nevertheless, there are some weaker validity notions (Cachin et
al., 2001) ensuring a transaction to output only if all honest nodes (or $f+1$
honest nodes) input it, cf. Appendix A for more detailed separations between
strong validity and weaker notions.

Note that there are also other complementary liveness notions orthogonal to
validity, for example, (Cachin et al., 2001) proposed “fairness” that means
the relative confirmation latency of any two transactions is bounded (at least
$f+1$ honest nodes input them), and Kelkar et al. (Kelkar et al., 2020) and
Zhang et al. (Zhang et al., 2020) recently introduced “order-fairness”.
Nevertheless, following most studies about practical asynchronous BFT
consensus, we only consider liveness in form of strong validity without
fairness throughout the paper.

Performance metrics. We are particularly interested in constructing practical
asynchronous BFT protocols. So it becomes meaningful to consider the following
key efficiency metrics:

  * $\bullet$

Message complexity (Cachin et al., 2001): the expected number of messages
generated by honest nodes to decide an output;

  * $\bullet$

(Amortized) communication complexity (Cachin et al., 2001): the expected
number of bits sent among honest nodes per output transaction;

  * $\bullet$

Round complexity (Canetti and Rabin, ): the expected asynchronous rounds
needed to output a transaction $tx$ (after an honest node invokes the protocol
to totally order $tx$). Here asynchronous round is the “time” measurement in
an asynchronous network, and can be viewed as a “time” unit defined by the
longest delay of messages sent among honest nodes (Canetti and Rabin, ; Keidar
et al., 2021).

###  4.2. Preliminaries

Multi-valued validated Byzantine agreement ($\mathsf{MVBA}$). $\mathsf{MVBA}$
(Abraham et al., 2019; Cachin et al., 2001; Lu et al., 2020) is a variant of
Byzantine agreement with external validity, such that the participating nodes
can agree on a value satisfying a publicly known predicate $Q$. Here we recall
its formal definition:

###### Definition 4.2.

Syntax-wise, each node in the $\mathsf{MVBA}$ protocol takes a (probably
different) value validated by a global predicate $Q$ (whose description is
known by the public) as input, and decides a value satisfying $Q$ as the
output. The protocol shall satisfy the next properties except with negligible
probability:

  * $\bullet$

Termination. If all honest nodes input some values satisfying $Q$, then each
honest node would output;

  * $\bullet$

Agreement. If two honest nodes output $v$ and $v^{\prime}$, respectively, then
$v=v^{\prime}$.

  * $\bullet$

External-Validity. If an honest node outputs a value $v$, then $v$ is valid
w.r.t. $Q$, i.e., $Q(v)=1$;

  * $\bullet$

Quality. If an honest node outputs $v$, the probability that $v$ was input by
the adversary is at most 1/2.

Note that not all $\mathsf{MVBA}$ protocols have the last quality property.
For example, a very recent design mentioned in (Gelashvili et al., ) might
leave the adversary a chance to always propose the output if without further
careful adaption .555To add quality in $\mathsf{MVBA}$ mentioned in Appendix C
of Ditto (Gelashvili et al., ), it is needed to enforce each node to propose
its height-2 f-block chained to its own height-1 f-block in the first view
(iteration). Without the adaption, the honest nodes would propose its height-2
f-block chained to any earliest height-1 f-block that it receives, and
unfortunately the adversary can always propose the fastest height-1 f-block to
manipulate the output. Through the paper, we choose GLL+22-MVBA (Guo et al.,
2022) as $\mathsf{MVBA}$ instantiation, as it is the state-of-the-art quality-
featured $\mathsf{MVBA}$ protocol.

Cryptographic abstractions and notations. We consider a $(2f+1,n)$ threshold
signature scheme $\mathsf{TSIG}$ consisting of a tuple of algorithms
$(\mathsf{Share\textrm{-}Sign},\mathsf{Share\textrm{-}Verify},\mathsf{Combine},\mathsf{Sig\textrm{-}Verify})$
that is unforgeable under chosen message attacks. $\mathcal{H}$ denotes a
collision-resistant hash function. The cryptographic security parameter is
denoted by $\lambda$ and captures the size of (threshold) signature and the
length of hash value. We let $|B|$ to denote the batch size parameter, i.e.,
each node always chooses $|B|$ transactions from its buffer to disseminate.
$[n]$ is short for $\\{1,2,\dots,n\\}$.

##  5\. Initial attempt:
$\mathsf{DispersedLedger}$ married to $\mathsf{Dumbo}$

Here we take a brief tour to the enticing $\mathsf{DispersedLedger}$
($\mathsf{DL}$) protocol, then alleviate its performance bottlenecks by
adapting it into the cutting-edge $\mathsf{ACS}$
framework—Speeding-$\mathsf{Dumbo}$, the resulting
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ already outperforms all existing
asynchronous consensus with linear worst-case amortized communication
complexity. Finally, we also explain why
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ still cannot achieve throughput-
oblivious latency and effective censorship-resilience.

Overview of $\mathsf{DL}$. At a very high-level, $\mathsf{DL}$ proceeds as
follows.

Splitting broadcast into dispersal and retrieval. First, $\mathsf{DL}$
separates the bandwidth-intensive transaction dissemination phase into two
parts: dispersal and retrieval. The dispersal phase alone is much cheaper than
the whole transaction dissemination, because it only disperses encoded
fragments of transactions instead of broadcasting transactions themselves. The
retrieval phase remains bandwidth-bound, but it can execute concurrently to
the bandwidth-oblivious agreement modules, thus better utilizing the
previously wasted bandwidth while running agreement.

To implement dispersal and retrieval, the authors of $\mathsf{DL}$ adopted the
classic notion of asynchronous verifiable information dispersal
($\mathsf{AVID}$) (Cachin and Tessaro, 2005; Hendricks et al., 2007) that can
be defined as follows:

###### Definition 5.1.

$\mathsf{AVID}$ with a designated sender $\mathcal{P}_{s}$ consists of two
sub-protocols $(\mathsf{Disperse},\mathsf{Retrieve})$. In $\mathsf{Disperse}$,
the sender $\mathcal{P}_{s}$ takes a value $v$ as input, and every node
outputs a fragment of $v$ (probably together with some auxiliary metadata); in
$\mathsf{Retrieve}$, a node can interact with the participating nodes of
$\mathsf{Disperse}$ sub-protocol to recover a value. The $\mathsf{AVID}$
protocol shall satisfy the following properties with all but negligible
probability:

  * $\bullet$

Totality. A.k.a. agreement, if any honest node outputs in $\mathsf{Disperse}$,
all honest nodes would output in $\mathsf{Disperse}$;

  * $\bullet$

Recoverability. If $f+1$ honest nodes output in $\mathsf{Disperse}$, any node
can invoke $\mathsf{Retrieve}$ to recover some value $v^{\prime}$;

  * $\bullet$

Commitment. If some honest nodes outputs in $\mathsf{Disperse}$, there exists
a fixed value $v^{*}$, such that if any node recovers a value $v^{\prime}$ in
$\mathsf{Retrieve}$, then $v^{\prime}=v^{*}$;

  * $\bullet$

Correctness. If the sender is honest and has input $v$, then all honest nodes
can eventually output in $\mathsf{Disperse}$, and the value $v^{*}$ (fixed due
to commitment) equals to $v$.

$\mathsf{DL}$ also gave an $\mathsf{AVID}$ construction
$\mathsf{AVID\textrm{-}M}$, which slightly weakens Cachin et al.’s
$\mathsf{AVID}$ construction (Cachin and Tessaro, 2005):
$\mathsf{AVID\textrm{-}M}$ might have $f$ honest nodes do not receive the
correct fragments of input value, though they did output in
$\mathsf{Disperse}$. Thanks to such weakening, the $\mathsf{Disperse}$ sub-
protocol of $\mathsf{AVID\textrm{-}M}$ costs only $O(|B|+\lambda n^{2})$ bits
in total, where $|B|$ represents the size of input (i.e., batch size) and
$\lambda$ is security parameter. For $\mathsf{Retrieve}$, each node can spend
$O(|B|+\lambda n\log n)$ bits to recover each dispersed $|B|$-sized input.

So given $\mathsf{AVID}$ at hand, $\mathsf{DL}$ can tweak $\mathsf{HBBFT}$’s
$\mathsf{ACS}$ execution flow as follows to avoid sequentially running all
consecutive $\mathsf{ACS}$: each node uses a $\mathsf{Disperse}$ protocol to
disperse the encoded fragments of its input (instead of directly reliably
broadcasting the whole input), thus realizing a dispersal phase that costs
only $O(|B|n+\lambda n^{2}\log n)$ bits and saves an $\mathcal{O}(n)$ order in
relative to transaction dissemination for sufficiently large batch size. Then,
similar to $\mathsf{HBBFT}$, $\mathsf{DL}$ invokes an agreement phase made of
$n$ $\mathsf{ABBA}$s to agree on which senders’ $\mathsf{Disperse}$ protocols
have indeed completed. Once the agreement phase is finished, $\mathsf{DL}$
starts two concurrent tasks that can execute independently: (i) it starts a
new $\mathsf{ACS}$ to run new $\mathsf{Disperse}$ protocols followed by new
$\mathsf{ABBA}$ protocols; (ii) it concurrently run $\mathsf{Retrieve}$
protocols to recover the dispersed transactions.

The most bandwidth-consuming path in $\mathsf{DL}$ is retrieval. It costs
$O(|B|n^{2}+\lambda n^{3}\log n)$ bits in total to enable all $n$ nodes to
recover all necessary transactions, and now it can simultaneously execute
aside the succeeding $\mathsf{ACS}$es’ dispersal and agreement phases.

Listen forever for slow dispersals. To prevent censorship without using
threshold cryptosystems, $\mathsf{DispersedLedger}$ is conceptually similar to
DAG-rider (Keidar et al., 2021), that is: forever listening unfinished
$\mathsf{Disperse}$ protocols, and once a delayed $\mathsf{Disperse}$
belonging to previous $\mathsf{ACS}$ delivers, try to decide it as part of the
output of the current $\mathsf{ACS}$.

$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$: apply $\mathsf{DL}$ to
$\mathsf{sDumbo}$. Nevertheless, the protocol structure of $\mathsf{DL}$
heavily bases on $\mathsf{HBBFT}$, which uses a sub-optimal design of $n$
$\mathsf{ABBA}$s. This can incur $\mathcal{O}(n^{3})$ messages and
$\mathcal{O}(\log n)$ rounds per $\mathsf{ACS}$. Moreover,
$\mathsf{AVID\textrm{-}M}$ is unnecessarily strong, and $\mathcal{O}(n^{2})$
messages are expected to implement every $\mathsf{Disperse}$ due to totality.
Hence, we present an improved version of $\mathsf{DL}$ using techniques from
$\mathsf{Dumbo}$ protocols (Lu et al., 2020; Guo et al., 2020, 2022) to
alleviate its efficiency bottlenecks. We nickname the improved $\mathsf{DL}$
by $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$, as it can be thought of applying
$\mathsf{DL}$’s idea to Speeding $\mathsf{Dumbo}$. The improvement involves
the next two main aspects:

  * $\bullet$

We replace the agreement phase of $n$ concurrent $\mathsf{ABBA}$ instances by
one single $\mathsf{MVBA}$ (instantiated by the state-of-the-art
GLL+22-$\mathsf{MVBA}$ (Guo et al., 2022)). This reduces the expected rounds
of protocol to asymptotically optimal $\mathcal{O}(1)$, and also reduces the
expected message complexity to $\mathcal{O}(n^{2})$.

  * $\bullet$

Thanks to the external validity of $\mathsf{MVBA}$, the totality property of
$\mathsf{AVID\textrm{-}M}$ becomes unnecessary, and thus we replace
$\mathsf{AVID\textrm{-}M}$ by a weakened information dispersal primitive
without totality (provable dispersal, $\mathsf{PD}$) (Lu et al., 2020).
$\mathsf{PD}$ has a provability property to compensate the removal of
totality, as it allows the sender to generate a proof to attest: at least
$f+1$ honest nodes have received consistent encoded fragments, and thus a
unique value can be recovered later (with using a valid proof).
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ (Lu et al., 2020) constructed $\mathsf{PD}$
with using only $\mathcal{O}(n)$ messages, $O(|B|+\lambda n\log n)$ bits and
two rounds for dispersal.

Due to lack of space, we defer the formal description and security analysis of
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ to Appendix C.

We compare the complexities of the original $\mathsf{DL}$ and
$\mathsf{sDumbo\textrm{-}DL}$ in Table 3. $\mathsf{sDumbo\textrm{-}DL}$
strictly outperforms $\mathsf{DL}$: they have same communication complexity,
while $\mathsf{sDumbo\textrm{-}DL}$ is asymptotically better than
$\mathsf{DL}$ w.r.t. round complexity and message complexity. Also, in
experimental evaluations, $\mathsf{sDumbo\textrm{-}DL}$ outperforms
$\mathsf{sDumbo}$ in concrete performance. See details in Section 7, e.g.,
Figure 9.

Table 3. Complexities per $\mathsf{ACS}$ in $\mathsf{DL}$ and
$\mathsf{sDumbo\textrm{-}DL}$; $|B|$ is the size of each node’ input, and
$\lambda$ is security parameter.

Protocol | Complexities of each $\mathsf{ACS}$
---|---
Round |  Communication † | Message
$\mathsf{DispersedLedger}$ | $\mathcal{O}(\log n)$ | $\mathcal{O}(|B|n^{2}+\lambda n^{3}\log n)$ | $\mathcal{O}(n^{3})$
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ | $\mathcal{O}(1)$ | $\mathcal{O}(|B|n^{2}+\lambda n^{3}\log n)$ |  $\mathcal{O}(n^{2})$ ‡

  * $\dagger$

For $\mathsf{ACS}$ where each node takes a $|B|$-sized input, the lower bound
of communication is $\mathcal{O}(|B|n^{2})$, so $\mathcal{O}(|B|n^{2}+\lambda
n^{3}\log n)$ is optimal for sufficiently large $|B|\geq\lambda n\log n$.

  * $\ddagger$

To exchange quadratic messages in $\mathsf{sDumbo\textrm{-}DL}$, each node can
multicast only one retrieval message by concatenating the fragments (and
metadata) associated to different $\mathsf{PD}$ instances.

Why $\mathsf{DL}$ cannot realize a throughput-oblivious latency? After
improving $\mathsf{DL}$ with $\mathsf{PD}$ and GLL+22-$\mathsf{MVBA}$ as
described above, we obtain $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$, which
seemingly can make full use of bandwidth resources, if the input batch size is
sufficiently large, such that the bandwidth-intensive dispersal phase is
running all the time.

Unfortunately, while increasing the batch size $|B|$ to saturate the network
capacity, two undesired factors might take effect in
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$: (i) the communication cost of provable
dispersal $\mathsf{PD}$ quickly grows up, because each node sends
$O(|B|+\lambda{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}n^{2}})$
bits to disperse its input, causing the overall latency to increase; (ii) the
cost of retrieval might soar even more dynamically, because each node needs to
send/receive $O(|B|n+\lambda n^{2}\log n)$ bits.

We quantitatively measure the unpleasant tendency in a WAN experiment setting
among $n$=16 nodes from distinct AWS regions (cf. Section 7 for detailed
experiment setup). We gradually increase the input batch size, and plot in
Figure 6 to illustrate the latency of dispersal and retrieval phases (at some
random node) under varying batch sizes. The latency of dispersal experiences a
continuing growth that finally triples, and the latency of retrieval even
becomes 5X slower, when the batch size increases from 100 $tx$ to 25,000 $tx$,
where 25,000 $tx$ (6.25MB) is the batch size saturating bandwidth.

Figure 6. Latency of dispersal/retrieval as batch size grows.

In short, even if we use more efficient components to improve
$\mathsf{DispersedLedger}$, its latency remains to be dramatically sacrificed
while approaching larger throughput. Let alone its censorship prevention
technique might be “unimplementable” due to the same unbounded memory issue
lying in DAG-rider (as earlier mentioned in Footnote 3) in adversarial
situations, e.g., some nodes crashed (or simply got delayed) for a long time.

##  6\. $\mathsf{Dumbo\textrm{-}NG}$: Realizing Throughput-oblivious Latency

Given our multiple improvements, $\mathsf{DispersedLedger}$ still does not
completely achieve our ambitious goal of asynchronous BFT consensus with high-
throughput, low-latency, and guaranteed censorship-resilience. The major issue
of it and also $\mathsf{HBBFT}$/$\mathsf{Dumbo}$ is: the agreement modules
block the succeeding transaction dissemination, so huge batches are necessary
there to utilize most bandwidth for maximum throughput, which unavoidably
hurts the latency.

To get rid of the issue, we aim to support concurrent processes for bandwidth-
intensive transaction dissemination and bandwidth-oblivious $\mathsf{BA}$
modules, so we can use much smaller batches to seize most bandwidth for
realizing peak throughput. Here we elaborate our solution
$\mathsf{Dumbo\textrm{-}NG}$ that implements the promising idea.

Overview of $\mathsf{Dumbo\textrm{-}NG}$. At a very high level,
$\mathsf{Dumbo\textrm{-}NG}$ consists of (i) $n$ ever-running broadcasts and
(ii) a sequence of $\mathsf{BA}$s.

Figure 7. Ever-growing multi-shot broadcast.

Each node uses an ever-running multi-shot broadcast to continuously
disseminate its input transactions to the whole network. As Figure 7
illustrates, the broadcast is never blocked to wait for any agreement modules
or other nodes’ broadcasts, and just proceeds by consecutive slots at its own
speed. In each slot, the broadcast delivers a batch of transactions along with
a quorum certificate (containing a threshold signature or concatenating enough
digital signatures from distinct nodes). A valid certificate delivered in some
slot can prove: at least $f+1$ honest nodes have received the same
transactions in all previous slots of the broadcast. The multi-shot broadcast
is implementable, since each node only maintains several local variables
(related to the current slot and immediate previous slot), and all earlier
delivered transactions can be thrown into persistent storage to wait for the
final output.

Because we carefully add certificates to the ever-running broadcasts, it
becomes possible to concurrently execute $\mathsf{MVBA}$ with fine-tuned
external validity condition to totally order the disseminated transactions. In
particular, a node invokes an $\mathsf{MVBA}$ protocol, if $n-f$ distinct
broadcasts deliver new transactions to it (so also deliver $n-f$ new
certificates), and the node can take the $n-f$ certificates as $\mathsf{MVBA}$
input. The $\mathsf{MVBA}$’s external validity is specified to first check all
certificates’ validity and then check that these $n-f$ indeed correspond to
some newly delivered transactions that were not agreed to output before. Once
$\mathsf{MVBA}$ returns, all honest nodes receive a list of $n-f$ valid
certificates, and pack the transactions certified by these certificates as a
block of consensus output.

One might wonder that $\mathsf{MVBA}$’s external validity alone cannot ensures
all broadcasted transactions are eventually output, because the adversary can
let $\mathsf{MVBA}$ always return her input of $n-f$ certificates, which can
always exclude the certificates of $f$ honest nodes’ broadcasts. As such, the
adversary censors these $f$ honest nodes. Nevertheless, the quality property
of some recent $\mathsf{MVBA}$ protocols (Guo et al., 2022; Lu et al., 2020;
Abraham et al., 2019) can fortunately resolve the issue without incurring
extra cost. Recall that quality ensures that with at least $1/2$ probability,
the output of $\mathsf{MVBA}$ is from some honest node. So the probability of
censorship decreases exponentially with the protocol execution.

Figure 8. Illustration on how to totally order the received broadcasts through
executing a sequence of $\mathsf{MVBA}$s.

Details of the $\mathsf{Dumbo\textrm{-}NG}$ protocol. Here we elaborate how we
construct $\mathsf{Dumbo\textrm{-}NG}$ in the spirit of aforementioned high-
level ideas (cf. Figure 14 for formal pseudo-code description). As Figure 8
illustrates, $\mathsf{Dumbo\textrm{-}NG}$ is composed of two concurrent
components, $n$ ever-running multi-shot broadcasts and a sequence of
$\mathsf{MVBA}$s, which separately proceed as follows in a concurrent manner:

Broadcasts: There are $n$ concurrent broadcasts with distinct senders. The
sender part and receiver part of each broadcast proceed by slot $s$ as
follows, respectively:

  * $\bullet$

Sender Part. At the sender $\mathcal{P}_{i}$’s side, once it enters a slot
$s$, it selects a $|B|$-sized batch $\mathsf{TX}_{i,s}$ of transactions from
$\mathsf{buffer}$, then multicasts it with the current slot index $s$ (and
probably a threshold signature $\Sigma_{s-1}$ if $s>1$) via Proposal message,
where $\Sigma_{s-1}$ can be thought as a quorum certificate for the
transaction batch $\mathsf{TX}_{i,s-1}$ that was broadcasted in the preceding
slot $s-1$. After that, the node $\mathcal{P}_{i}$ waits for $2f+1$ valid Vote
messages from distinct nodes. Since each Vote message carries a threshold
signature share for $\mathsf{TX}_{j,s}$, $\mathcal{P}_{i}$ can compute a
threshold signature $\Sigma_{s}$ for $\mathsf{TX}_{j,s}$. Then, move into slot
$s+1$ and repeat.

  * $\bullet$

Receiver Part. At the receivers’ side of a sender $\mathcal{P}_{j}$’s
broadcast, if a receiving node $\mathcal{P}_{i}$ stays in slot $s$, it waits
for a valid Proposal message that carries
$(s,\mathsf{TX}_{j,s},\Sigma_{j,s-1})$ from the designated sender
$\mathcal{P}_{j}$. Then, $\mathcal{P}_{i}$ records $\mathsf{TX}_{j,s}$, and
also marks the transaction batch $\mathsf{TX}_{j,s-1}$ received in the
preceding slot $s-1$ as the “fixed” (denoted by
$\mathsf{fixed\textrm{-}TX}_{j}[s-1]$ and can be thrown into persistent
storage). This is because $\Sigma_{j,s-1}$ attests that $\mathsf{TX}_{j,s-1}$
was received and signed by enough honest nodes, so it can be fixed (as no
other honest node can fix a different $\mathsf{TX}_{j,s-1}^{\prime}$).
Meanwhile, $\mathcal{P}_{i}$ updates its local
$\mathsf{current\textrm{-}cert}$ vector, by replacing the $j$-th element by
$(s-1,\mathsf{digest}_{j,s-1},\Sigma_{j,s-1})$, because $\mathcal{P}_{i}$
realizes the growth of $\mathcal{P}_{j}$’s broadcast. Next, $\mathcal{P}_{i}$
computes a partial signature $\sigma_{s}$ on received proposal
$\mathsf{TX}_{j,s}$, and sends a Vote message carrying $\sigma_{s}$ to
$\mathcal{P}_{j}$. Then $\mathcal{P}_{i}$ moves into the next slot $s+1$ and
repeats the above. In case $\mathcal{P}_{j}$ (staying at slot $s$) receives a
Proposal message
$(s^{\prime},\mathsf{TX}_{j,s^{\prime}},\Sigma_{j,s^{\prime}-1})$ with some
$s^{\prime}>s$, it shall first retrieve missing transaction batches till slot
$s^{\prime}-1$ and then proceed in slot $s^{\prime}$ as above to vote on the
latest received transaction $\mathsf{TX}_{j,s^{\prime}}$ and then move to slot
$s^{\prime}+1$. The details about how to pull transactions from other nodes
will be soon explained in a later subsection. 666There is a subtle reason to
first retrieve the missing transactions and then increase the local slot
number in each broadcast instance, if a node is allowed to jump into a much
higher slot without completing the pull of missing transactions, the
asynchronous adversary might cause less than $f+1$ honest nodes have the
broadcasted transactions in its persistent storage. Our design ensures that a
quorum certificate can certainly prove that $f+1$ honest nodes indeed have
thrown all previously broadcasted transactions (except the latest slot’s) into
their persistent storage (otherwise they wouldn’t vote).

Agreements: Aside the transaction broadcasts, a separate asynchronous
agreement module is concurrently executing and totally order the broadcasted
transaction batches. The agreement module is a sequence of $\mathsf{MVBA}$s
and proceeds as follows by epoch $e$.

Each node initializes a vector (denoted by
$\mathsf{ordered\textrm{-}indices}$) as $[0,\dots,0]$ when $e=1$. The $j$-th
element in $\mathsf{ordered\textrm{-}indices}$ is denoted by
$\mathsf{ordered}_{j}$ and represents how many transaction batches from the
sender $\mathcal{P}_{j}$ have been totally ordered as output. Also, every node
locally maintains a $n$-size vector denoted by
$\mathsf{current\textrm{-}cert}$ to track the current progresses of all
broadcasts. In particular, the $j$-th element
$({0pt}_{j},\mathsf{digest}_{j},\Sigma_{j})$ in
$\mathsf{current\textrm{-}cert}$ tracks the progress of $\mathcal{P}_{j}$’s
broadcast, and ${0pt}_{j}$, $\mathsf{digest}_{j}$ and $\Sigma_{j}$ presents
the slot index, the hash digest, and the threshold signature associated to the
last transaction batch received from the sender $\mathcal{P}_{j}$,
respectively.

Then, a node waits for that at least $n-f$ broadcasts deliver new transactions
(along with new certificates), i.e., ${0pt}_{j}>\mathsf{ordered}_{j}$ for at
least $n-f$ distinct $j$. Then, it invokes an $\mathsf{MVBA}[e]$ instance
associated to the current epoch $e$ with taking
$\mathsf{current\textrm{-}cert}$ as input. The global predicate $Q_{e}$ of
$\mathsf{MVBA}[e]$ is fine-tuned to return a vector
$\mathsf{current\textrm{-}cert}^{\prime}$ =
$[({0pt}_{1}^{\prime},\mathsf{digest}_{1}^{\prime},\Sigma_{1}^{\prime}),\dots,$
$({0pt}_{n}^{\prime},\mathsf{digest}_{n}^{\prime},\Sigma_{n}^{\prime})]$, such
that: (i) all $\Sigma_{j}^{\prime}$ is a valid threshold signature for the
${0pt}_{j}^{\prime}$-th slot of $\mathcal{P}_{j}$’s broadcast, and (ii)
${0pt}_{j}^{\prime}>\mathsf{ordered}_{j}$ for at least $n-f$ different
$j\in[n]$. Finally, all nodes decide this epoch’s output due to
$\mathsf{current\textrm{-}cert}^{\prime}$. Specifically, they firstly check if
$\mathsf{TX}_{j,{0pt}_{j}^{\prime}}$ was received and
$\mathsf{fixed\textrm{-}TX}_{j}[{0pt}_{j}^{\prime}]$ was not recorded, if that
is the case and
$\mathsf{digest}_{j}^{\prime}=\mathcal{H}(\mathsf{TX}_{j,{0pt}_{j}^{\prime}})$,
they mark $\mathsf{TX}_{j,{0pt}_{j}^{\prime}}$ as fixed and record it as
$\mathsf{fixed\textrm{-}TX}_{j}[{0pt}_{j}^{\prime}]$. Then, the honest nodes
pack the output of the epoch: for each $j\in[n]$, find the fixed transaction
batches $\mathsf{fixed\textrm{-}TX}_{j}[{\mathsf{ordered}_{j}}+1]$,
$\mathsf{fixed\textrm{-}TX}_{j}[{\mathsf{ordered}_{j}}+2]$, $\cdots$,
$\mathsf{fixed\textrm{-}TX}_{j}[{0pt}_{j}^{\prime}]$, and put these batches
into the epoch’s output. After output in the epoch $e$, each node updates
$\mathsf{ordered\textrm{-}indices}$ by the latest indices in
$\mathsf{current\textrm{-}cert}^{\prime}$, and enters the epoch $e+1$.

Handle missing transaction batches: Note that is possible that some node might
not store $\mathsf{fixed\textrm{-}TX}_{j}[k]$, when (i) it has to put
$\mathsf{fixed\textrm{-}TX}_{j}[k]$ into its output after some $\mathsf{MVBA}$
returns in epoch $e$ or (ii) has to sync up to the $k$-th slot in the sender
$\mathcal{P}_{j}$’s broadcast instance because of receiving a Proposal message
containing a slot number higher than its local slot. In both cases, each node
can notify a $\mathsf{CallHelp}$ process (cf. Figure 15 in Appendix D for
formal description) to ask the missing transaction batches from other nodes,
because at least $f+1$ honest nodes must record or receive it because of the
simple property of quorum certificate (otherwise they would not vote to form
such certificates). We can adopt the techniques of erasure-code and Merkle
tree used in verifiable information dispersal (Cachin and Tessaro, 2005;
Miller et al., 2016) to prevent communication blow-up while pulling
transactions. In particular, the $\mathsf{CallHelp}$ function is invoked to
broadcast a CallHelp message to announce that
$\mathsf{fixed\textrm{-}TX}_{j}[k]$ is needed. Once a node receives the
$\mathsf{CallHelp}$ message, a daemon process $\mathsf{Help}$ (also cf. Figure
15) would be activated to proceed as: if the asked transaction batch
$\mathsf{fixed\textrm{-}TX}_{j}[k]$ was stored, then encode
$\mathsf{fixed\textrm{-}TX}_{j}[k]$ using an erasure code scheme, compute a
Merkle tree committing the code fragments and $i$-th Merkle branch from the
root to each $i$-th fragment. Along the way, the $\mathsf{Help}$ daemon sends
the Merkle root, the $i$-th fragment, and the $i$-th Merkle branch to who is
requesting $\mathsf{fixed\textrm{-}TX}_{j}[k]$. Every honest node requesting
$\mathsf{fixed\textrm{-}TX}_{j}[k]$ can receive $f+1$ valid responses from
honest nodes with the same Merkle root, so it can recover the correct
$\mathsf{fixed\textrm{-}TX}_{j}[k]$. As such, each $\mathsf{Help}$ daemon only
has to return a code fragment of the missing transactions under request, and
the fragment’s size is only $\mathcal{O}(1/n)$ of the transactions, thus not
blowing up the overall communication complexity.

Security intuitions. $\mathsf{Dumbo\textrm{-}NG}$ realizes all requirements of
$\mathsf{ABC}$ (cf. Appendix E for detailed proofs). The security intuitions
are:

Safety intuitively stems from the following observations:

  * $\bullet$

Safety of broadcasts. For any sender $\mathcal{P}_{j}$’s broadcast, if a valid
quorum certificate $\Sigma_{j,s}$ can be produced, at least $f+1$ honest nodes
have received the same sequence of transaction batches $\mathsf{TX}_{j,s}$,
$\mathsf{TX}_{j,s-1}$, $\cdots$ $\mathsf{TX}_{j,1}$. In addition, if two
honest nodes locally store $\mathsf{fixed\textrm{-}TX}_{j}[s]$ and
$\mathsf{fixed\textrm{-}TX}_{j}^{\prime}[s]$ after seeing $\Sigma_{j,s}$ and
$\Sigma^{\prime}_{j,s}$, respectively, then
$\mathsf{fixed\textrm{-}TX}_{j}[s]=\mathsf{fixed\textrm{-}TX}_{j}^{\prime}[s]$.
The above properties stem from the simple fact that quorum certificates are
$2f+1$ threshold signatures on the hash digest of received transaction
batches, so the violation of this property would either break the security of
threshold signatures or the collision-resistance of cryptographic hash
function.

  * $\bullet$

External validity and agreement of $\mathsf{MVBA}$. The global predicate of
every $\mathsf{MVBA}$ instance is set to check the validity of all broadcast
certificates (i.e., verify threshold signatures). So $\mathsf{MVBA}$ must
return a vector
$\mathsf{current\textrm{-}cert}^{\prime}=[({0pt}_{1}^{\prime},\mathsf{digest}_{1}^{\prime},\Sigma_{1}^{\prime}),$
$\dots,({0pt}_{n}^{\prime},\mathsf{digest}_{n}^{\prime},\Sigma_{n}^{\prime})]$,
such that each $({0pt}_{j}^{\prime},\mathsf{digest}_{j}^{\prime},$
$\Sigma_{j}^{\prime})\in\mathsf{current\textrm{-}cert}^{\prime}$ is valid
broadcast certificate. In addition, any two honest nodes would receive the
same $\mathsf{current\textrm{-}cert}^{\prime}$ from every $\mathsf{MVBA}$
instance, so any two honest nodes would output the same transactions in every
epoch, because each epoch’s output is simply packing some fixed transaction
batches according to $\mathsf{current\textrm{-}cert}^{\prime}$ returned from
$\mathsf{MVBA}$.

Liveness (censorship-resilience) is induced as the following facts:

  * $\bullet$

Optimistic liveness of broadcasts. If a broadcast’s sender is honest, it can
broadcast all input transactions to the whole network, such that all nodes can
receive an ever-growing sequence of the sender’s transactions with
corresponding quorum certificates.

  * $\bullet$

Quality of $\mathsf{MVBA}$. Considering that an honest sender broadcasts a
transaction batch $\mathsf{TX}_{j,s}$ at slot $s$, all nodes must receive some
quorum certificate containing an index equal or higher than $s$ eventually
after a constant number of asynchronous rounds. After some moment, all honest
nodes would input such certificate to some $\mathsf{MVBA}$ instance. Recall
the quality of $\mathsf{MVBA}$, which states that with 1/2 probability, some
honest node’s input must become $\mathsf{MVBA}$’s output. So after expected 2
epochs, some honest node’s input to $\mathsf{MVBA}$ would be returned,
indicating that the broadcast’s certificate with index $s$ (or some larger
index) would be used to pack $\mathsf{TX}_{j,s}$ into the final output.

  * $\bullet$

Termination of $\mathsf{MVBA}$. Moreover, $\mathsf{MVBA}$ can terminate in
expected constant asynchronous rounds. So every epoch only costs expected
constant running time.

Complexity and performance analysis. The round and communication complexities
of $\mathsf{Dumbo\textrm{-}NG}$ can be analyzed as follows:

  * $\bullet$

The round complexity is expected constant. After a transaction is broadcasted
by an honest node, every honest node would receive a valid quorum certificate
on this transaction after 3 asynchronous rounds. Then, the transaction would
output after expected two $\mathsf{MVBA}$ instances (due to the quality of
$\mathsf{MVBA}$). In case of facing faults and/or adversarial network, there
could be more concrete rounds, for example, some nodes might need two rounds
to retrieve missing transaction batches and $\mathsf{MVBA}$ could also become
slower by a factor of 3/2.

  * $\bullet$

The amortized communication complexity is linear for sufficiently large batch
size parameter. Due to our broadcast construction, it costs
$\mathcal{O}(|B|n+\lambda n)$ bits to broadcast a batch of $|B|$ transactions
to all nodes. The expected communication complexity of an $\mathsf{MVBA}$
instance is $\mathcal{O}(\lambda n^{3})$. Recall that every $\mathsf{MVBA}$
causes to output a block containing at least $\mathcal{O}(n|B|)$ transactions,
and probably $\mathcal{O}(n|B|)$ transactions need to bother $\mathsf{Help}$
and CallHelp subroutines, costing at most $\mathcal{O}(n^{2}|B|+\lambda
n^{3}\log n)$ bits. In sum, each epoch would output $\mathcal{O}(n|B|)$
transactions with expected $\mathcal{O}(n^{2}|B|+\lambda n^{3}\log n)$ bits
despite the adversary, which corresponds to linear amortized communication
complexity if $|B|\geq\lambda n\log n$.

(a) Peak throughput

(b) Latency-throughput trade-off ($n=4$)

(c) Latency-throughput trade-off ($n=16$)

(d) Latency-throughput trade-off ($n=64$)

Figure 9. Performance of $\mathsf{Dumbo\textrm{-}NG}$ in comparison with the
state-of-the-art asynchronous protocols (in the WAN setting).

##  7\. Implementation and Evaluations

We implement $\mathsf{Dumbo\textrm{-}NG}$ and deploy it over 16 different AWS
regions across the globe. A series of experiments is conducted in the WAN
settings with different system scales and input batch sizes. The experimental
results demonstrate the superiority of $\mathsf{Dumbo\textrm{-}NG}$ over the
existing performant asynchronous BFT consensus protocols including two very
recent results $\mathsf{DispersedLedger}$ ($\mathsf{DL}$) (Yang et al., 2022)
and Speeding-$\mathsf{Dumbo}$ ($\mathsf{sDumbo}$) (Guo et al., 2022). In
particular, $\mathsf{Dumbo\textrm{-}NG}$ can preserve low latency (only
several seconds) while realizing high throughput (100k tx/sec) at all system
scales (from 4 to 64 nodes).

###  7.1. Implementation & WAN experiment setup

Implementations details. We implement $\mathsf{Dumbo\textrm{-}NG}$,
$\mathsf{sDumbo}$, $\mathsf{Dumbo}$, and $\mathsf{DispersedLedger}$ (more
precisely, the improved version $\mathsf{sDumbo\textrm{-}DL}$, cf. Section 5)
in Python3.777Proof-of-concept implementation is available at
https://github.com/fascy/Dumbo_NG. Though our proof-of-concept implementation
didn’t implement the processes for pulling missing transactions in
$\mathsf{Dumbo\textrm{-}NG}$, it cautiously counts the number of such
retrievals and found that there were less than 1% missing transaction batches
to retrieve in all WAN evaluations. The same cryptographic libraries and
security parameters are used throughout all implementations. Both
$\mathsf{Dumbo\textrm{-}NG}$ and $\mathsf{sDumbo\textrm{-}DL}$ are implemented
as two-process Python programs. Specifically, $\mathsf{sDumbo\textrm{-}DL}$
uses one process to deal with dispersal and $\mathsf{MVBA}$ and uses another
process for retrieval; $\mathsf{Dumbo\textrm{-}NG}$ uses one process for
broadcasting transactions and uses the other to execute $\mathsf{MVBA}$. We
use gevent library for concurrent tasks in one process. Coin flipping is
implemented with using Boldyreva’s pairing-based threshold signature
(Boldyreva, 2003). Regarding quorum certificates, we implement them by
concatenating ECDSA signatures. Same to $\mathsf{HBBFT}$ (Miller et al.,
2016), $\mathsf{Dumbo}$ (Guo et al., 2020) and BEAT (Duan et al., 2018), our
experiments focus on evaluating the performance of stand-alone asynchronous
consensus, and all results are measured in a fair way without actual clients.

Implementation of asynchronous network. To realize reliable fully meshed
asynchronous point-to-point channels, we implement a (persistent)
unauthenticated TCP connection between every two nodes. The network layer runs
on two separate processes: one handles message receiving, and the other
handles message sending. If a TCP connection is dropped (and fails to deliver
messages), our implementation would attempt to re-connect.

Setup on Amazon EC2. We run $\mathsf{Dumbo\textrm{-}NG}$, $\mathsf{Dumbo}$,
Speeding-$\mathsf{Dumbo}$ ($\mathsf{sDumbo}$), and $\mathsf{DispersedLedger}$
(the $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ variant) among EC2 c5.large
instances which are equipped with 2 vCPUs and 4 GB main memory. Their
performances are evaluated with varying scales at $n=4,16,$ and $64$ nodes.
Each transaction is 250-byte to approximate the size of a typical Bitcoin
transaction with one input and two outputs. For $n=16$ and 64, all instances
are evenly distributed in 16 regions across five continents: Virginia, Ohio,
California, Oregon, Canada, Mumbai, Seoul, Singapore, Sydney, Tokyo,
Frankfurt, London, Ireland, Paris, Stockholm and São Paulo; for $n=4$, we use
the regions in Virginia, Sydney, Tokyo and Ireland.

###  7.2. Evaluation results in the WAN setting

$\mathsf{Dumbo\textrm{-}NG}$ v.s. prior art. To demonstrate the superior
performance of $\mathsf{Dumbo\textrm{-}NG}$, we first comprehensively compare
it to the improved $\mathsf{DispersedLedger}$ ($\mathsf{sDumbo\textrm{-}DL}$)
as well as other performant asynchronous protocols ($\mathsf{sDumbo}$ and
$\mathsf{Dumbo}$). Specifically,

  * $\bullet$

Peak throughput. For each asynchronous consensus, we measure its throughput,
i.e., the number of transactions output per second. The peaks of the
throughputs of $\mathsf{Dumbo\textrm{-}NG}$, $\mathsf{sDumbo\textrm{-}DL}$
$\mathsf{sDumbo}$ and $\mathsf{Dumbo}$ (in varying scales) are presented in
Figure 9(a). This reflects how well each protocol can handle the application
scenarios favoring throughput. Overall, the peak throughput of
$\mathsf{Dumbo\textrm{-}NG}$ has a several-times improvement than any other
protocol. Specifically, the peak throughput of $\mathsf{Dumbo\textrm{-}NG}$ is
more than 7x of $\mathsf{Dumbo}$ when $n=4$, about 4x of $\mathsf{Dumbo}$ when
$n=16$, and roughly 3x of $\mathsf{Dumbo}$ when $n=64$. As for
$\mathsf{sDumbo}$, it is around 4x of $\mathsf{sDumbo}$ when $n=4$, over 2x of
$\mathsf{sDumbo}$ when $n=16$, and almost 3x of $\mathsf{sDumbo}$ when $n=64$.
Even if comparing with $\mathsf{sDumbo\textrm{-}DL}$,
$\mathsf{Dumbo\textrm{-}NG}$ still achieves over 3x improvement in peak
throughput when $n=4$, and about 2x when $n=16$ or $n=64$.

  * $\bullet$

Latency-throughput trade-off. Figure 9(b), 9(c) and 9(d) illustrate the
latency-throughput trade-off of $\mathsf{Dumbo\textrm{-}NG}$,
$\mathsf{sDumbo\textrm{-}DL}$, $\mathsf{sDumbo}$ and $\mathsf{Dumbo}$ when
$n=4$, 16 and 64, respectively. Here latency is the time elapsed between the
moment when a transaction appears in the front of a node’s input buffer and
the moment when it outputs, so it means the “consensus latency” excluding the
time of queuing in mempool. The trade-off between latency and throughput
determines whether a BFT protocol can simultaneously handle throughput-
critical and latency-critical applications. To measure
$\mathsf{Dumbo\textrm{-}NG}$’s (average) latency, we attach timestamp to every
broadcasted transaction batch, so all nodes can track the broadcasting time of
all transactions to calculate latency. The experimental results show: although
$\mathsf{Dumbo\textrm{-}NG}$ uses a Byzantine agreement module same to that in
$\mathsf{sDumbo}$ and $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ (i.e., the
GLL+22-$\mathsf{MVBA}$), its trade-off surpasses $\mathsf{sDumbo}$ in all
cases. The more significant result is that at all system scales,
$\mathsf{Dumbo\textrm{-}NG}$ preserves a low and relatively stable latency
(only a few seconds), while realizing high throughput at the magnitude of 100k
tx/sec. In contrast, other protocols suffer from dramatic latency increment
while approaching their peak throughput. This demonstrates that
$\mathsf{Dumbo\textrm{-}NG}$ enjoys a much broader array of application
scenarios than the prior art, disregarding throughput-favoring or latency-
favoring.

Figure 10. Throughput/latency of $\mathsf{Dumbo\textrm{-}NG}$,
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$, $\mathsf{sDumbo}$ and $\mathsf{Dumbo}$
in varying batch size for WAN setting ($n=16$).

Latency/throughput while varying batch sizes. The tested asynchronous
protocols do have a parameter of batch size to specify that each node can
broadcast up to how many transactions each time. As aforementioned, the
latency-throughput tension in many earlier practical asynchronous BFT
consensuses like $\mathsf{HBBFT}$ and $\mathsf{Dumbo}$ is actually related to
the choice of batch size: their batch size parameter has to be tuned up for
higher throughput, while this might cause a dramatic increment in latency.

Here, we gradually increase the batch size and record the latency and
throughput to see how batch size takes effect in the tested protocols. Figure
10 plots a sample when $n=16$ for $\mathsf{Dumbo\textrm{-}NG}$,
$\mathsf{sDumbo\textrm{-}DL}$, $\mathsf{sDumbo}$ and $\mathsf{Dumbo}$. It is
observed that with the increment of batch size, the throughput of all
protocols starts to grow rapidly but soon tends to grow slowly. The latency of
$\mathsf{Dumbo}$ and $\mathsf{sDumbo}$ grows at a steady rate as the batch
size increases. The latency of $\mathsf{sDumbo\textrm{-}DL}$ tends to increase
slowly in the beginning but then increase significantly (once the batch size
reaches 20k-30k tx). However, the latency of $\mathsf{Dumbo\textrm{-}NG}$
remains constantly small. When the batch size increases from 1k to 5k,
$\mathsf{Dumbo\textrm{-}NG}$ reaches its peak throughput (about 160k tx/sec),
and its latency only increases by less than 0.5 sec; in contrast,
$\mathsf{sDumbo\textrm{-}DL}$, $\mathsf{sDumbo}$ and $\mathsf{Dumbo}$ have to
trade a few seconds in their latency for reaching peak throughput. Clearly,
$\mathsf{Dumbo\textrm{-}NG}$ needs a much smaller batch size (only about 1/10
of others) to realize the highest throughput, which allows it to maintain a
pretty low latency under high throughput.

###  7.3. More tests with controlled delay/bandwidth

The above experiments in the WAN setting raises an interesting question about
$\mathsf{Dumbo\textrm{-}NG}$: why it preserves a nearly constant latency
despite throughput? We infer the following two conjectures based on the
earlier WAN setting results:

  1. (1)

The $\mathsf{MVBA}$ protocols are actually insensitive to the amount of
available bandwidth, so no matter how much bandwidth is seized by transaction
broadcasts, their latency would not change as only rely on round-trip time of
network.

  2. (2)

The nodes in $\mathsf{Dumbo\textrm{-}NG}$ only need to broadcast a small batch
of transactions (e.g., a few thousands that is 1/10 of $\mathsf{Dumbo}$ and
$\mathsf{DispersedLedger}$) to closely track bandwidth.

Clearly, if the above conjectures are true, the latency of
$\mathsf{Dumbo\textrm{-}NG}$ would just be 1-2x of $\mathsf{MVBA}$’s running
time. Hence, we further conduct extensive experiments in a LAN setting
(consisting of servers in a single AWS region) with manually controlled
network propagation delay and bandwidth to verify the two conjectures,
respectively.

Figure 11. Latency of GLL+22-$\mathsf{MVBA}$ (Guo et al., 2022) with $n$=16
nodes in varying bandwidth for (a) 50ms and (b) 200ms one-way network delay,
respectively.

Evaluate $\mathsf{MVBA}$ with controlled network bandwidth/delay. We measure
$\mathsf{MVBA}$, in particular, its latency, in the controlled experiment
environment (for $n$=16 nodes). Here the input-size of $\mathsf{MVBA}$ is set
to capture the length of $n$ quorum certificates. Figure 11 (a) and (b) show
the results in the setting of 50 and 100 ms network propagation delays,
respectively, with varying the bandwidth of each peer-to-peer tcp link (5, 10,
20, 50, 75, or 100 Mbps). Clearly, our first conjecture is true, as
$\mathsf{MVBA}$ is definitely bandwidth-oblivious, as its latency relies on
propagation delay other than available bandwidth.

Figure 12. The dependency of throughput on varying batch size in controlled
deployment environment with 50 ms one-way delay and (a) 75Mbps and (b) 150Mbps
bandwidth.

Test $\mathsf{Dumbo\textrm{-}NG}$ with controlled network bandwidth/delay.
Then we verify whether $\mathsf{Dumbo\textrm{-}NG}$ can closely track
available bandwidth resources with only small batch sizes. We examine how
$\mathsf{Dumbo\textrm{-}NG}$ gradually saturates bandwidth resources whiling
batch size increases, in a controlled environment (for $n$=16 nodes). The one-
way network delay is set to 50ms, and per-node’s bandwidth is set for (a)
75Mbps (5Mbps per tcp socket) or (b) 150Mbps (10Mbps per tcp socket). The
controlled network parameters well reflect an inter-continental communication
network. Clearly, the results verify our second conjecture that
$\mathsf{Dumbo\textrm{-}NG}$ can fully utilize bandwidth while using small
batch sizes (less than 1MB).

###  7.4. Behind the throughput-oblivious latency

Given the extensive experiment results, we now can understand why the latency
of $\mathsf{Dumbo\textrm{-}NG}$ is almost independent to its throughput: (i)
some small batch sizes can already fully utilize network bandwidth, and
therefore the latency of broadcasting a batch transactions is much smaller
than that of $\mathsf{MVBA}$; (ii) when the broadcast instances seize most
bandwidth, the latency of $\mathsf{MVBA}$ would not be impacted as its latency
is bandwidth-insensitive. So if a broadcast makes a progress when the
$\mathsf{MVBA}$ of epoch $e$ is running, this progress would be solicited to
output by the $\mathsf{MVBA}$ of next epoch $e+1$ (if no fault), and even if
there are $n/3$ faulty nodes, it is still expected to output by the
$\mathsf{MVBA}$ of epoch $e+2$ (due to $\mathsf{MVBA}$’s quality), which
results in throughput-oblivious latency. For sake of completeness, we also
interpret the above intuition into analytic formula and perform numerical
analysis in Appendix F.

##  8\. Discussions

Flooding launched by malicious nodes. In the $\mathsf{HBBFT}$ and DAG type of
protocols (Miller et al., 2016; Guo et al., 2020, 2022; Duan et al., 2018;
Keidar et al., 2021; Danezis et al., 2022), the malicious nodes cannot
broadcast transactions too much faster than the honest nodes, because all
nodes explicitly block themselves to wait for the completeness of $n-f$
broadcasts to move forward. While one might wonder that in
$\mathsf{Dumbo\textrm{-}NG}$, the malicious nodes probably can broadcast a
huge amount of transactions in a short term, which might exhaust the resources
of the honest nodes and prevent them from processing other transactions.

Nevertheless, this is actually a general flooding attack in many distributed
systems, and it is not a particularly serious worry in
$\mathsf{Dumbo\textrm{-}NG}$, because a multitude of techniques already exist
to deter it. For example, the nodes can allocate an limited amount of
resources to handle each sender’s broadcast, so they always have sufficient
resources to process the transactions from the other honest senders, or an
alternative mitigation can also be charging fees for transactions as in
Avalanche (Rocket et al., 2019).

Input tx buffer assumptions related to censorship-resilience. Censorship-
resilience (liveness) in many work (Miller et al., 2016; Guo et al., 2020;
Duan et al., 2018; Guo et al., 2022) explicitly admits an assumption about
input buffer (a.k.a. backlog or transaction pool): a transaction is guaranteed
to eventually output, only if it has been placed in all honest nodes’ input
buffer. Our censorship resilience allows us to adopt a different and weaker
assumption about the input buffer (that is same to $\mathsf{DispersedLedger}$
(Yang et al., 2022), Aleph (Gagol et al., 2019) and DAG-rider (Keidar et al.,
2021)): if a transaction appears in any honest node’s input buffer (resp. $k$
random nodes’ input buffers), the transaction would output eventually (resp.
output with all but negligible probability in $k$).

Our input buffer assumption is appropriate or even arguably quintessential in
practice. First, in many consortium blockchain settings, a user might be
allowed to contact only several consensus nodes. For example, a Chase bank
user likely cannot submit her transactions to a consensus node of Citi bank.
Moreover, even if in a more open setting where a client is allowed to contact
all nodes, it still prefers to fully leverage the strength of our censorship
resilience property to let only $k$ consensus nodes (instead of all) to
process each transaction for saving communication cost.

Challenges and tips to production-level implementation. For production-level
implementation of $\mathsf{Dumbo\textrm{-}NG}$ with bounded memory, a few
attentions (some of which are even subtle) need to be paid. First, the
$\mathsf{MVBA}$ instantiation shall allow nodes to halt after they decide
output (without hurting other nodes’ termination), such that a node can quit
old $\mathsf{MVBA}$ instances and then completely clean them from memory.
Also, similar to $\mathsf{Tusk}$ (Danezis et al., 2022), messages shall carry
latest quorum certificates to attest that $f+1$ honest nodes have stored data
in their persistent storage, such that when a slow node receives some “future”
messages, it does not have to buffer the future messages and can directly
notify a daemon process to pull the missing outputs accordingly. In addition,
$\mathsf{Dumbo\textrm{-}NG}$ has a few concurrent tasks (e.g., broadcasts and
$\mathsf{MVBA}$s) that rely on shared global variables. This is not an issue
when implementing these tasks by multiple threads in one process.
Nevertheless, when separating these tasks into multiple processes, inter-
process communication (IPC) implementation has to correctly clean IPC buffers
to avoid their memory leak due to long network delay. Last but not least, if a
node constantly fails to send a message to some slow/crashed node, it might
keeps on re-sending, and thus its out-going message buffer might dramatically
increase because more and more out-going messages are queued to wait for
sending. It can adopt the practical alternative introduced by $\mathsf{Tusk}$,
namely, stop (re-)sending too old out-going messages and clean them from
memory, because messages in $\mathsf{Dumbo\textrm{-}NG}$ can also embed latest
quorum certificates (to help slow nodes sync up without waiting for all
protocol messages).

For more detailed tips that extend the above discussions and elaborate how to
implement $\mathsf{Dumbo\textrm{-}NG}$ towards a production-level system with
bounded memory, cf. Appendix B.

##  9\. Conclusion

We present $\mathsf{Dumbo\textrm{-}NG}$, an efficient asynchronous BFT atomic
broadcast protocol favoring censorship resilience. It can realize high
throughput, low latency and guaranteed censorship resilience at the same time.
Nevertheless, despite the recent progress of practical asynchronous BFT
consensus, a few interesting problems remain open: practical asynchronous BFT
consensuses with enhanced fairness guarantees (e.g., order fairness) are
largely unexplored; most existing asynchronous BFT protocols cannot smoothly
scale up, e.g., to support several hundreds of nodes with preserving a
reasonable latency, and a solution to the scalability issue could be very
interesting.

###### Acknowledgements.

We would like to thank the anonymous reviewers for their valuable comments
that helped us considerably improve the paper. Yuan and Zhenfeng are supported
in part by National Key R&D Project. Yuan is also partially supported by NSFC
under Grant 62102404 and the Youth Innovation Promotion Association CAS.
Yingzi and Jing were supported in part by NSFC under Grant 62172396. Qiang and
Zhenliang are supported in part by research gifts from Ethereum Foundation,
Stellar Foundation, Protocol Labs, Algorand Foundation and The University of
Sydney.

## References

  * (1)
  * Abraham et al. (2008) Ittai Abraham, Danny Dolev, and Joseph Y Halpern. 2008\.  An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience. In Proc. PODC 2008. 405–414.
  * Abraham et al. (2021) Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu. 2021.  Reaching consensus for asynchronous distributed key generation. In Proc. PODC 2021. 363–373.
  * Abraham et al. (2020) Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. 2020.  Sync hotstuff: Simple and practical synchronous state machine replication. In IEEE S&P 2020. 106–118.
  * Abraham et al. (2019) Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. 2019\.  Asymptotically optimal validated asynchronous byzantine agreement. In Proc. PODC 2019. 337–346.
  * Amir et al. (2010) Yair Amir, Brian Coan, Jonathan Kirsch, and John Lane. 2010\.  Prime: Byzantine replication under attack.  IEEE transactions on dependable and secure computing 8, 4 (2010), 564–577.
  * Amoussou-Guenou et al. (2018) Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni. 2018\.  Correctness of tendermint-core blockchains. In Proc. OPODIS 2018.
  * Attiya and Welch (2004) Hagit Attiya and Jennifer Welch. 2004.  Distributed computing: fundamentals, simulations, and advanced topics. Vol. 19.  John Wiley & Sons.
  * Aublin et al. (2013) Pierre-Louis Aublin, Sonia Ben Mokhtar, and Vivien Quéma. 2013.  Rbft: Redundant byzantine fault tolerance. In Proc. ICDCS 2013. 297–306.
  * Baek and Zheng (2003) Joonsang Baek and Yuliang Zheng. 2003.  Simple and efficient threshold cryptosystem from the gap diffie-hellman group. In GLOBECOM’03. 1491–1495.
  * Bagaria et al. (2019) Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. 2019.  Prism: Deconstructing the blockchain to approach physical limits. In Proc. CCS 2019. 585–602.
  * Baudet et al. (2019) Mathieu Baudet, Avery Ching, Andrey Chursin, George Danezis, François Garillot, Zekun Li, Dahlia Malkhi, Oded Naor, Dmitri Perelman, and Alberto Sonnino. 2019\.  State machine replication in the Libra Blockchain.  (2019).
  * Ben-Or (1983) Michael Ben-Or. 1983\.  Another advantage of free choice (Extended Abstract) Completely asynchronous agreement protocols. In Proc. PODC 1983. 27–30.
  * Ben-Or and El-Yaniv (2003) Michael Ben-Or and Ran El-Yaniv. 2003.  Resilient-optimal interactive consistency in constant time.  Distributed Computing 16, 4 (2003), 249–262.
  * Ben-Or et al. (1994) Michael Ben-Or, Boaz Kelmer, and Tal Rabin. 1994.  Asynchronous secure computations with optimal resilience. In Proc. PODC 1994. 183–192.
  * Bessani et al. (2014) Alysson Bessani, Joao Sousa, and Eduardo EP Alchieri. 2014\.  State machine replication for the masses with BFT-SMART. In Proc. DSN 2014. 355–362.
  * Blum et al. (2019) Erica Blum, Jonathan Katz, and Julian Loss. 2019.  Synchronous consensus with optimal asynchronous fallback guarantees. In Theory of Cryptography Conference. 131–150.
  * Boldyreva (2003) Alexandra Boldyreva. 2003\.  Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. In International Workshop on Public Key Cryptography. Springer, 31–46.
  * Bracha (1987) Gabriel Bracha. 1987\.  Asynchronous Byzantine agreement protocols.  Information and Computation 75, 2 (1987), 130–143.
  * Buterin (2014) Vitalik Buterin. 2014\.  A next-generation smart contract and decentralized application platform.  white paper 3, 37 (2014).
  * Cachin et al. (2001) Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. 2001.  Secure and efficient asynchronous broadcast protocols. In Advances in Cryptology – CRYPTO 2001. 524–541.
  * Cachin et al. (2005) Christian Cachin, Klaus Kursawe, and Victor Shoup. 2005\.  Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography.  Journal of Cryptology 18, 3 (2005), 219–246.
  * Cachin and Poritz (2002) Christian Cachin and Jonathan A Poritz. 2002.  Secure intrusion-tolerant replication on the Internet. In Proc. DSN 2002. 167–176.
  * Cachin and Tessaro (2005) Christian Cachin and Stefano Tessaro. 2005.  Asynchronous verifiable information dispersal. In Proc. SRDS 2005. 191–201.
  * Cachin and Vukolić (2017) Christian Cachin and Marko Vukolić. 2017.  Blockchain consensus protocols in the wild.  arXiv preprint arXiv:1707.01873 (2017).
  * (26) Ran Canetti and Tal Rabin.  Fast asynchronous Byzantine agreement with optimal resilience. In Proc. STOC 1993. 42–51.
  * Castro et al. (1999) Miguel Castro, Barbara Liskov, et al. 1999\.  Practical byzantine fault tolerance. In Proc. OSDI 1999. 173–186.
  * Chan and Shi (2020) Benjamin Y Chan and Elaine Shi. 2020.  Streamlet: Textbook streamlined blockchains. In Proc. AFT 2020.
  * Chase and MacBrough (2018) Brad Chase and Ethan MacBrough. 2018.  Analysis of the XRP ledger consensus protocol.  arXiv preprint arXiv:1802.07242 (2018).
  * Clement et al. (2009a) Allen Clement, Manos Kapritsos, Sangmin Lee, Yang Wang, Lorenzo Alvisi, Mike Dahlin, and Taylor Riche. 2009a.  Upright cluster services. In Proc. SOSP 2009. 277–290.
  * Clement et al. (2009b) Allen Clement, Edmund L Wong, Lorenzo Alvisi, Michael Dahlin, and Mirco Marchetti. 2009b.  Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults.. In Proc. NSDI 2009. 153–168.
  * (32) Tyler Crain, Christopher Natoli, and Vincent Gramoli.  Red belly: A secure, fair and scalable open blockchain. In IEEE S&P 2021. 466–483.
  * Danezis et al. (2022) George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022.  Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. In Proc. EuroSys 2022. 34–50.
  * Das et al. (2021) Sourav Das, Zhuolun Xiang, and Ling Ren. 2021.  Asynchronous data dissemination and its applications. In Proc. CCS 2021. 2705–2721.
  * Das et al. (2022) Sourav Das, Thomas Yurek, Zhuolun Xiang, Andrew Miller, Lefteris Kokoris-Kogias, and Ling Ren. 2022\.  Practical Asynchronous Distributed Key Generation. In IEEE S&P 2022. 2518–2534.
  * Duan et al. (2018) Sisi Duan, Michael K Reiter, and Haibin Zhang. 2018\.  BEAT: Asynchronous BFT made practical. In Proc. CCS 2018. 2028–2041.
  * Fischer et al. (1985) Michael J Fischer, Nancy A Lynch, and Michael S Paterson. 1985\.  Impossibility of distributed consensus with one faulty process.  Journal of the ACM (JACM) 32, 2 (1985), 374–382.
  * Fitzi and Garay (2003) Matthias Fitzi and Juan A Garay. 2003.  Efficient player-optimal protocols for strong and differential consensus. In Proc. PODC 2003. 211–220.
  * Gagol et al. (2019) Adam Gagol, Damian Leśniak, Damian Straszak, and Michał Świetek. 2019\.  Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In Proc. AFT 2019. 214–228.
  * Gao et al. (2022) Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2022\.  Efficient Asynchronous Byzantine Agreement without Private Setups. In Proc. ICDCS 2022.
  * Garay et al. (2015) Juan Garay, Aggelos Kiayias, and Nikos Leonardos. 2015\.  The bitcoin backbone protocol: Analysis and applications. In Advances in Cryptology – EUROCRYPT 2015. 281–310.
  * (42) Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang.  Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback. In FC 2022.
  * Gennaro et al. (1999) Rosario Gennaro, Stanisław Jarecki, Hugo Krawczyk, and Tal Rabin. 1999.  Secure distributed key generation for discrete-log based cryptosystems. In Advances in Cryptology – EUROCRYPT 1999. 295–310.
  * Giridharan et al. (2022) Neil Giridharan, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022.  Bullshark: DAG BFT Protocols Made Practical. In Proc. CCS 2022.
  * Guerraoui et al. (2010) Rachid Guerraoui, Nikola Knežević, Vivien Quéma, and Marko Vukolić. 2010.  The next 700 BFT protocols. In Proc. EuroSys 2010. 363–376.
  * Gueta et al. (2019) Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019.  Sbft: a scalable and decentralized trust infrastructure. In Proc. DSN 2019. 568–580.
  * Guo et al. (2022) Bingyong Guo, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2022\.  Speeding Dumbo: Pushing Asynchronous BFT Closer to Practice. In Proc. NDSS 2022.
  * Guo et al. (2020) Bingyong Guo, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2020.  Dumbo: Faster asynchronous bft protocols. In Proc. CCS 2020. 803–818.
  * Hendricks et al. (2007) James Hendricks, Gregory R Ganger, and Michael K Reiter. 2007\.  Verifying distributed erasure-coded data. In Proc. PODC 2007. 139–146.
  * Kate and Goldberg (2009) Aniket Kate and Ian Goldberg. 2009.  Distributed key generation for the internet. In Proc. ICDCS 2009. 119–128.
  * Keidar et al. (2021) Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021.  All You Need is DAG. In Proc. PODC 2021. 165–175.
  * Kelkar et al. (2020) Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. 2020.  Order-Fairness for Byzantine Consensus. In Advances in Cryptology – CRYPTO 2020. 451–480.
  * Kokoris Kogias et al. (2020) Eleftherios Kokoris Kogias, Dahlia Malkhi, and Alexander Spiegelman. 2020.  Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.. In Proc. CCS 2020. 1751–1767.
  * Kursawe and Shoup (2005) Klaus Kursawe and Victor Shoup. 2005.  Optimistic asynchronous atomic broadcast. In Proc. ICALP 2005. 204–215.
  * Libert et al. (2016) Benoît Libert, Marc Joye, and Moti Yung. 2016.  Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares.  Theoretical Computer Science 645 (2016), 1–24.
  * Libert and Yung (2011) Benoît Libert and Moti Yung. 2011.  Adaptively secure non-interactive threshold cryptosystems. In Proc. ICALP 2011. 588–600.
  * (57) Chao Liu, Sisi Duan, and Haibin Zhang.  EPIC: efficient asynchronous BFT with adaptive security. In Proc. DSN 2020. 437–451.
  * Lu et al. (2022) Yuan Lu, Zhenliang Lu, and Qiang Tang. 2022.  Bolt-Dumbo Transformer: Asynchronous Consensus As Fast As Pipelined BFT. In Proc. CCS 2022.
  * Lu et al. (2020) Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang. 2020\.  Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited. In Proc. PODC 2020. 129–138.
  * MacBrough (2018) Ethan MacBrough. 2018\.  Cobalt: BFT governance in open networks.  arXiv preprint arXiv:1802.07240 (2018).
  * Miller et al. (2016) Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016.  The honey badger of BFT protocols. In Proc. CCS 2016. 31–42.
  * Moniz et al. (2008) Henrique Moniz, Nuno Ferreria Neves, Miguel Correia, and Paulo Verissimo. 2008.  RITAS: Services for randomized intrusion tolerance.  IEEE transactions on dependable and secure computing 8, 1 (2008), 122–136.
  * Mostefaoui et al. (2014) Achour Mostefaoui, Hamouma Moumen, and Michel Raynal. 2014\.  Signature-free asynchronous Byzantine consensus with t¡ n/3 and O (n2) messages. In Proc. PODC 2014. 2–9.
  * Nakamoto (2008) Satoshi Nakamoto. 2008\.  Bitcoin: A peer-to-peer electronic cash system.  Decentralized Business Review (2008), 21260.
  * Pass and Shi (2018) Rafael Pass and Elaine Shi. 2018.  Thunderella: Blockchains with optimistic instant confirmation. In Advances in Cryptology – EUROCRYPT 2018. 3–33.
  * Patra et al. (2009) Arpita Patra, Ashish Choudhary, and Chandrasekharan Pandu Rangan. 2009\.  Simple and efficient asynchronous byzantine agreement with optimal resilience. In Proc. PODC 2009. 92–101.
  * Pedersen (1991) Torben Pryds Pedersen. 1991\.  A threshold cryptosystem without a trusted party. In Advances in Cryptology – EUROCRYPT 1991. 522–526.
  * Rabin (1983) Michael O Rabin. 1983\.  Randomized byzantine generals. In 24th Annual Symposium on Foundations of Computer Science. 403–409.
  * Ramasamy and Cachin (2005) HariGovind V Ramasamy and Christian Cachin. 2005.  Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast. In Proc. OPODIS 2005. 88–102.
  * Rocket et al. (2019) Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, and Emin Gün Sirer. 2019.  Scalable and probabilistic leaderless BFT consensus through metastability.  arXiv preprint arXiv:1906.08936 (2019).
  * Schneider (1990) Fred Schneider. 1990\.  Implementing Fault-tolerant Services using the State Machine Approach: A Tutorial.  Comput. Surveys (1990).
  * Shrestha et al. (2020) Nibesh Shrestha, Ittai Abraham, Ling Ren, and Kartik Nayak. 2020\.  On the optimality of optimistic responsiveness. In Proc. CCS 2020. 839–857.
  * Stathakopoulou et al. (2019) Chrysoula Stathakopoulou, Tudor David, Matej Pavlovic, and Marko Vukolić. 2019.  Mir-bft: High-throughput robust bft for decentralized networks.  arXiv preprint arXiv:1906.05552 (2019).
  * Veronese et al. (2009) Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, and Lau Cheuk Lung. 2009.  Spin one’s wheels? Byzantine fault tolerance with a spinning primary. In Proc. SRDS 2009. 135–144.
  * Yang et al. (2022) Lei Yang, Seo Jin Park, Mohammad Alizadeh, Sreeram Kannan, and David Tse. 2022.  DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks. In Proc. NSDI 2022.
  * Yin et al. (2019) Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. 2019\.  HotStuff: BFT consensus with linearity and responsiveness. In Proc. PODC 2019. 347–356.
  * Zhang et al. (2020) Yunhao Zhang, Srinath Setty, Qi Chen, Lidong Zhou, and Lorenzo Alvisi. 2020.  Byzantine Ordered Consensus without Byzantine Oligarchy. In Proc. OSDI 2020.

##  Appendix A Asynchronous liveness notions

The validity of asynchronous atomic broadcast captures that a certain input
transaction would eventually output. It has a few fine-grained flavors (Cachin
et al., 2001):

  * $\bullet$

Strong validity (called censorship resilience through the paper): $tx$ can
eventually output, if any honest node takes it as input;

  * $\bullet$

Validity: if $f+1$ honest nodes input $tx$, it can eventually output;

  * $\bullet$

Weak validity: if all honest nodes input $tx$, it eventually outputs.

From strong validity to censorship resilience: The next examples can
demonstrate why strong validity can easily prevent censorship of transactions
when building SMR from atomic broadcast, but weaker flavors of validity
cannot:

  * $\bullet$

In permissioned settings: Strong validity has practical meaning in real-world
consortium blockchain systems, because a client might not be allowed to
contact all consensus nodes, and can only rely on several designated nodes to
process its transactions (Yang et al., 2022). In this setting, strong validity
is critical because only it ensures that every client can have the input
transactions to eventually output as long as the client has permission to
contact an honest consensus node.

  * $\bullet$

Enable de-duplication: In more open settings where a client has the permission
to contact all nodes to duplicate its transactions, strong validity is still
important as it empowers de-duplication techniques (Danezis et al., 2022;
Stathakopoulou et al., 2019) to reduce redundant communication. For example,
each transaction can be sent to only $k$ nodes (where $k$ is a security
parameter), because the $k$ random nodes would contain at least one honest
node with a probability exponentially large in $k$ (in case of static
corruptions); in contrast, a client has to contact $f+1$ honest nodes (resp.
$2f+1$ honest nodes) if there is only validity (resp. weak validity).

Relation/separation to quality: GKL15 (Garay et al., 2015) defines quality as:
for any sufficiently long substring of consensus output, the ratio of blocks
proposed by the adversary is bounded by a non-zero constant. By definition,
quality does not prevent the adversary constantly dropping certain honest
nodes’ input, and in many asynchronous protocols with quality but without
strong validity (e.g., asynchronous common subset (Cachin et al., 2001; Ben-Or
et al., 1994) and $\mathsf{Tusk}$ (Danezis et al., 2022)), the adversary can
indeed drop $f$ honest nodes. Thus, quality only implies liveness conditioned
on that all honest nodes propose/input all transactions redundantly (as
explicitly stated in GKL15 (Garay et al., 2015)). In other words, if aiming at
liveness from quality directly, it needs to duplicate transactions over all
honest nodes as redundant input. This “approach”, unfortunately, might incur
$\mathcal{O}(n)$ communication blow-up in leaderless asynchronous protocols as
discussed in Section 1. Alternatively, quality together with threshold
encryption can also ensure liveness (Miller et al., 2016) but might incur
heavy computation.

##  Appendix B Detailed tips towards production-level implementation

In Section 8 we brief the challenges and tips towards production-level
implementation of $\mathsf{Dumbo\textrm{-}NG}$. Here we extend the discussions
to give more detailed suggestions for practitioners.

  1. (1)

Halt in asynchronous $\mathsf{BA}$ without hurting termination. In many
asynchronous $\mathsf{BA}$ protocols (Cachin et al., 2005; Abraham et al.,
2019), the honest nodes cannot simultaneously decide their output in the same
iteration. So even if a node has decided its output, it might need to continue
the execution to help other nodes also output (otherwise, there might exist a
few nodes fail to output). Fortunately, a few studies (Mostefaoui et al.,
2014; MacBrough, 2018; Blum et al., 2019; Guo et al., 2020) demonstrated how
to securely halt in asynchronous $\mathsf{BA}$s without hurting termination.
Our $\mathsf{MVBA}$ instantiation (Guo et al., 2022) also has the feature of
immediate halt after output, as the honest nodes would always multicast a
quorum certificate proving the decided output and then quit.

  2. (2)

Share variables across concurrent processes. Some global variables are shared
among the concurrent tasks in $\mathsf{Dumbo\textrm{-}NG}$, for example, the
task of $\mathsf{MVBA}$s $n$ shall have access to read the latest broadcast
certificates generated in the tasks of $n$ running broadcasts. When
practitioners implement these tasks with different processes, inter-process
communication (IPC) for sharing these global variables shall be cautiously
handled. For example, if IPC socket is used to pass the latest broadcast
certificates to the $\mathsf{MVBA}$s’ process, it is important to implement a
thread that executes concurrent to $\mathsf{MVBA}$s to continuously take
certificates out of the IPC sockets and only track the latest certificates
(otherwise, a huge number of certificates could be accumulated in the
receiving buffer of IPC socket if a single $\mathsf{MVBA}$ is delayed).

  3. (3)

Use quorum certificates for retrievability to help slow nodes. Up to $f$ slow
honest nodes might receive a burst of “future” messages in an asynchronous
network. There are three such cases: (i) a broadcast sender receives Vote
messages higher than its local slot; (ii) a broadcast receiver gets Proposal
messages higher than its local slot; or (iii) any nodes receivers some
$\mathsf{MVBA}$ messages with epoch number higher than its local epoch. For
case (i), it is trivial that the broadcast sender can just omit such “future”
Vote messages, because these messages must be sent by corrupted nodes. For
case (ii), we have elaborated the solution in Section 6: when a slow node
staying at slot $s$ receives a Proposal message with valid quorum certificate
but slot $s^{\prime}>s$, it needs to first pull the missing transactions till
slot $s^{\prime}-1$ and then increase its local slot number to continue voting
in slot $s^{\prime}$ and later slots. For case (iii), it can also be trivially
solved by letting the $e$-th epoch’s $\mathsf{MVBA}$ messages carry the
unforgeable quorum certificate for $\mathsf{MVBA}[e-1]$’s output, such that
upon a slow node receives some $\mathsf{MVBA}$ message belong to a “future”
epoch $e^{\prime}$ larger than its local epoch $e$, it can pull all missing
$\mathsf{MVBA}$ outputs till epoch $e^{\prime}-1$ (similar to pull broadcasted
transactions) and then move into epoch $e^{\prime}$.

  4. (4)

Avoid infinite buffer of out-going messages. To correctly implement
asynchronous communication channels, a message sending node might continuously
re-send each protocol message until the message receiving node returns an
acknowledgment receipt (e.g., through TCP connection). As such, the message
sending node might have more and more out-going messages accumulated while
stucking in re-sending some very old messages. At first glance, it seemingly
requires infinite memory to buffer these out-going messages. However, recall
that $\mathsf{Tusk}$ (Danezis et al., 2022) can stop re-sending old out-going
messages and then securely clean them. The implementation of
$\mathsf{Dumbo\textrm{-}NG}$ can also adapt the idea to bound the size of out-
going buffer by cleaning the “old” out-going messages belong to slot/epoch
smaller than the current local slot/epoch, as long as practitioners follow the
guidance in (3) to embed previous slot/epoch’s quorum certificate in the
current slot/epoch’s out-going messages to help slow nodes to pull missing
outputs by a quorum certificate (instead of actually receiving all sent
protocol messages).

The $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ protocol (for each node
$\mathcal{P}_{i}$)Äpgjy let $\mathsf{buffer}$ to be a FIFO queue of input
transactions, $B$ to be the batch size parameter, the algorithm proceed in
consecutive epochs numbered $e$: Process 1: Dispersal and agreement let
$\\{\mathsf{APDB}[e,j]\\}_{j\in[n]}$ refer to $n$ instances of Asynchronous
Provable Dispersal Broadcast protocol, and $\mathcal{P}_{j}$ is the sender of
$\mathsf{PD}[e,j]$ The $Q_{e}$ of $\mathsf{sMVBA}$ be the following predicate:
$Q_{e}(\\{(h_{1},\sigma_{1}),\cdots,(h_{n},\sigma_{n})\\})\equiv$ (exist at
least $n-f$ distinct $i\in[n]$, such that $h_{i}\neq\perp$ and
$\mathsf{Sig\textrm{-}Verify}_{(2f+1)}(\langle\langle\textsc{Stored},e,i\rangle,h_{i}\rangle,\sigma_{i})=1$)
Initial: $W_{e}=\\{(h_{1},\sigma_{1}),\cdots,(h_{n},\sigma_{n})\\}$, where
$(h_{j},\sigma_{j})\leftarrow(\perp,\perp)$ for all $1\leq j\leq n$;
$FS_{e}=0$; $S_{e}=\\{\\}$ $\bullet$ upon receiving input value $v_{i}$ –
input $v_{i}$ to $\mathsf{PD}[{\left\langle e,i\right\rangle}]$ $\circ$ upon
receiving $lock:=\langle{vc}_{i},\sigma\rangle$ from
$\mathsf{PD}[{\left\langle e,i\right\rangle}]$ $\circ$ multicast
$(\mathsf{Final},e,{vc}_{i},\sigma)$ $\bullet$ upon receiving
$(\mathsf{Final},e,{vc}_{j},\sigma)$from $\mathcal{P}_{j}$ for the first time
– if
$\mathsf{Sig\textrm{-}Verify}_{(2f+1)}(\langle\langle\textsc{Stored},e,j\rangle,{vc}_{j}\rangle,\sigma)=1$
$\triangleright$ c.f. Algorithm 1 in (Lu et al., 2020) $\circ$
$(h_{j},\sigma_{j})\leftarrow({vc}_{j},\sigma)$, where $(h_{j},\sigma_{j})\in
W_{e}$ $\circ$ $FS_{e}=FS_{e}+1$ $\circ$ if $FS_{e}=n-f$ @itemiv invoke
$\mathsf{sMVBA}[e]$ with $W_{e}$ as input $\bullet$ upon the
$\mathsf{sMVBA}[e]$ return
$\overline{W}=\\{(\overline{h}_{1},\overline{\sigma}_{1}),\cdots,(\overline{h}_{n},\overline{\sigma}_{n})\\}$
– for all $1\leq j\leq n$: $\circ$ if $\overline{h}_{j}\neq\bot$, then
$S_{e}\leftarrow S_{e}\cup{j}$ – $e\leftarrow e+1$ $\triangleright$ enter next
epoch Process 2: Retrieval $\bullet$ upon $S_{e^{\prime}}\neq\\{\\}$ – For all
$j\in S_{e^{\prime}}$, invoke $\mathsf{RC}[e^{\prime},j]$ subprotocol of
$\mathsf{APDB}[e^{\prime},j]$ to download the value $v_{e^{\prime},j}$
$\bullet$
$\mathsf{block}_{e^{\prime}}\leftarrow\mathsf{sort}(\\{v_{e^{\prime},j}|j\in
S_{e^{\prime}}\\}\\})$, i.e. sort $\mathsf{block}_{e^{\prime}}$ canonically
(e.g., lexicographically) $\bullet$
$\mathsf{buffer}\leftarrow\mathsf{buffer}\setminus\mathsf{block}_{e^{\prime}}$
and output $\mathsf{block}_{e^{\prime}}$ Figure 13. The
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ protocol.

##  Appendix C Formal description for $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$

Here we present the deferred formal description of
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ for sake of completeness.

###  C.1. APDB-W: a week variant of asynchronous provable dispersal broadcast

$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ relies on the variant of the
Asynchronous Provable Dispersal Broadcast protocol (APDB) (Lu et al., 2020)
for implementing the dispersal phase and the retrieval phase in the
$\mathsf{DispersedLedger}$ framework. More precisely,
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ only needs a subset of APDB’s
properties.

Recall that APDB consists of the following two subprotocols:

  * $\bullet$

$\mathsf{PD}$ subprotocol. In the $\mathsf{PD}$ subprotocol among $n$ nodes, a
designated sender $\mathcal{P}_{s}$ inputs a value $v\in\\{0,1\\}^{\ell}$, and
aims to split $v$ into $n$ encoded fragments and disperses each fragment to
the corresponding node. During the $\mathsf{PD}$ subprotocol, each node is
allowed to invoke an $abandon$ function. After $\mathsf{PD}$ terminates, each
node shall output two strings ${store}$ and ${lock}$, and the sender shall
output an additional string $\mathsf{proof}$.

  * $\bullet$

$\mathsf{RC}$ subprotocol. In the $\mathsf{RC}$ subprotocol, all honest nodes
take the output of the $\mathsf{PD}$ subprotocol as input, and aim to output
the value $v$ that was dispersed in the $\mathsf{RC}$ subprotocol. Once
$\mathsf{RC}$ is completed, the nodes output a common value in
$\\{0,1\\}^{\ell}\cup\bot$.

A full-fledged APDB protocol ($\mathsf{PD}$, $\mathsf{RC}$) with identifier ID
satisfies the following properties except with negligible probability:

  * $\bullet$

Termination. If the sender $\mathcal{P}_{s}$ is honest and all honest nodes
activate $\mathsf{PD}[\mathsf{ID}]$ without invoking $abandon(\mathsf{ID})$,
then each honest node would output ${store}$ and valid ${lock}$ for
$\mathsf{ID}$; additionally, the sender $\mathcal{P}_{s}$ outputs valid
$\mathsf{proof}$ for $\mathsf{ID}$.

  * $\bullet$

Recast-ability. If all honest nodes invoke $\mathsf{RC}[\mathsf{ID}]$ with
inputting the output of $\mathsf{PD}[\mathsf{ID}]$ and at least one honest
node inputs a valid ${lock}$, then: (i) all honest nodes recover a common
value; (ii) if the sender dispersed $v$ in $\mathsf{PD}[\mathsf{ID}]$ and has
not been corrupted before at least one node delivers valid ${lock}$, then all
honest nodes recover $v$ in $\mathsf{RC}[\mathsf{ID}]$.

  * $\bullet$

Provability. If the sender of $\mathsf{PD}[\mathsf{ID}]$ produces valid
$\mathsf{proof}$, then at least $f+1$ honest nodes output valid ${lock}$.

  * $\bullet$

Abandon-ability. If every node (and the adversary) cannot produce valid
${lock}$ for $\mathsf{ID}$ and $f+1$ honest nodes invoke
$abandon(\mathsf{ID})$, no node would deliver valid ${lock}$ for
$\mathsf{ID}$.

Nevertheless, in context of implementing the dispersal phase and the retrieval
phase in the $\mathsf{DispersedLedger}$, Abandon-ability and Provability are
not necessary. Thus, we can set forth to the following weaker variant (that we
call it APDB-W).

Formally, APDB-W consists of the following two subprotocols:

  * $\bullet$

$\mathsf{PD}$ subprotocol. The syntax is same to that of APDB, except that (i)
non-sender node only outputs the ${store}$ string, (ii) sender only outputs
${lock}$ and ${store}$ strings, and (iii) no invocable $abandon$ function.

  * $\bullet$

$\mathsf{RC}$ subprotocol. The syntax is same to that of APDB.

An APDB-W protocol ($\mathsf{PD}$, $\mathsf{RC}$) with identifier
$\mathsf{ID}$ satisfies the following properties except with negligible
probability:

  * $\bullet$

Termination. If the sender $\mathcal{P}_{s}$ is honest and all honest nodes
activate $\mathsf{PD}[\mathsf{ID}]$, then each honest node would output
${store}$ for $\mathsf{ID}$; additionally, the sender $\mathcal{P}_{s}$
outputs valid ${lock}$ for $\mathsf{ID}$.

  * $\bullet$

Recast-ability. Same to that of APDB.

For brevity, we consider all $\mathsf{PD}$ and $\mathsf{RC}$ from APDB-W in
the paper since then on. Also, note that the properties of APDB-W is a subset
of APDB, so any construction of APDB would naturally implement APDB-W, for
example, (Lu et al., 2020) presented a simple 4-round construction of APDB,
and actually (Lu et al., 2020) also pointed out that APDB without provability
(i.e., still an APDB-W) can be realized by only two rounds. We refer the
interested readers to (Lu et al., 2020) for details.

###  C.2. Formal description for $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$

Given APDB-W (and also $\mathsf{sMVBA}$) at hand, we can then construct
$\mathsf{sDumbo}\textrm{-}\mathsf{DL}$ as described in Figure 13, which
essentially implements asynchronous common subset ($\mathsf{ACS}$), i.e., an
epoch in the $\mathsf{DispersedLedger}$ framework. When running a sequence of
$\mathsf{ACS}$es together with the inter-node linking technique in
$\mathsf{DispersedLedger}$ (that we refrain from reintroducing here),
asynchronous atomic broadcast can be realized.

###  C.3. Security for $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$

Here we (informally) prove that the $\mathsf{sDumbo}\textrm{-}\mathsf{DL}$
algorithm presented in Figure 13 securely realizes $\mathsf{ACS}$.

Let us first recall the formal definition of $\mathsf{ACS}$. In the
$\mathsf{ACS}$ protocol among $n$ nodes (including up to $f$ Byzantine faulty
nodes) with identification $\mathsf{ID}$, each node takes as input a value and
outputs a set of values. It satisfies the following properties except with
negligible probability:

  * $\bullet$

Validity. If an honest node 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
nodes.

  * $\bullet$

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

  * $\bullet$

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

Security intuition. The Algorithm 13 satisfies all properties of ACS. Its
securities can be intuitively understood as follows:

  * $\bullet$