#  $\mathsf{JUMBO}$: Fully Asynchronous BFT Consensus Made Truly Scalable

Hao Cheng, Yuan Lu, Zhenliang Lu, Qiang Tang, Yuxuan Zhang, Zhenfeng Zhang
Hao Cheng, Yuan Lu, and Zhenfeng Zhang are with Institute of Software Chinese
Academy of Sciences, Beijing, 100190, China. Email: {chenghao2020, luyuan,
<EMAIL_ADDRESS>Zhenliang Lu and Qiang Tang are with The University of
Sydney, NSW 2006, Australia. Email: {zhenliang.lu<EMAIL_ADDRESS>Yuxuan Zhang is with University of Pittsburgh, Pittsburgh, 15260, PA, US.
Email<EMAIL_ADDRESS>Hao Cheng, Yuan Lu, and Yuxuan Zhang made equal
contribution, and part of the work was done while Yuxuan visited Institute of
Software CAS.

###### Abstract

Recent progresses in asynchronous Byzantine fault-tolerant (BFT) consensus,
e.g. $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ (CCS’ 22) and $\mathsf{Tusk}$
(EuroSys’ 22), show promising performance through decoupling transaction
dissemination and block agreement. However, when executed with a larger number
$n$ of nodes, like several hundreds, they would suffer from significant
degradation in performance. Their dominating scalability bottleneck is the
huge authenticator complexity: each node has to multicast $\mathcal{O}(n)$
quorum certificates (QCs) and subsequently verify them for each block.

This paper systematically investigates and resolves the above scalability
issue. We first propose a signature-free asynchronous BFT consensus FIN-NG
that adapts a recent signature-free asynchronous common subset protocol FIN
(CCS’ 23) into the state-of-the-art framework of concurrent broadcast and
agreement. The liveness of FIN-NG relies on our non-trivial redesign of FIN’s
multi-valued validated Byzantine agreement towards achieving optimal quality.
FIN-NG greatly improves the performance of FIN and already outperforms
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ in most deployment settings. To further
overcome the scalability limit of FIN-NG due to $\mathcal{O}(n^{3})$ messages,
we propose $\mathsf{JUMBO}$, a scalable instantiation of
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$, with only $\mathcal{O}(n^{2})$
complexities for both authenticators and messages. We use various aggregation
and dispersal techniques for QCs to significantly reduce the authenticator
complexity of original $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ implementations
by up to $\mathcal{O}(n^{2})$ orders. We also propose a “fairness” patch for
$\mathsf{JUMBO}$, thus preventing a flooding adversary from controlling an
overwhelming portion of transactions in its output.

Finally, we implement our designs in Golang and experimentally demonstrated
their enhanced scalability with hundreds of Amazon’s AWS instances.
$\mathsf{JUMBO}$ and FIN-NG significantly outperform the state-of-the-art in
(nearly) all deployment settings. Especially, when $n\geq$196,
$\mathsf{JUMBO}$ can attain a throughput that is more than 4x that of FIN and
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$.

###### Index Terms:

Blockchain consensus, Byzantine fault tolerance, asynchronous Byzantine
agreement.

##  I Introduction

Randomized asynchronous Byzantine-fault tolerant (BFT) consensus protocols [1,
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21] can
overcome FLP “impossibility” [22] to ensure both safety (i.e. all honest nodes
agree the same ledger of transactions) and liveness (i.e. a client can expect
her valid transactions eventually output) despite a fully asynchronous network
that can arbitrarily delay message delivery. In contrast, their synchronous or
partial synchronous counterparts, such as PoW [23] and PBFT [24], might suffer
from inherent violation of security (e.g., PoW might output disagreed
decisions [25] and PBFT can completely grind to a halt [12]) if unluckily
encountering an asynchronous adversary [22]. Therefore, the fully asynchronous
BFT consensus protocols become highly desired for their high security
assurance, making them the most robust candidates for critical blockchain
infrastructures deployed over the unstable and occasionally adversarial global
Internet.

###  I-A Scalability Obstacles of the State of the Art

Interests in asynchronous BFT consensus protocols have recently resurged [12,
13, 14, 15, 17, 20, 21, 16, 18, 19] for their higher security assurance
against powerful network adversaries. However, there is limited evidence
supporting their seamless scalability to efficiently handle larger-scale
networks with several hundred nodes. For instance, the state-of-the-art
asynchronous BFT consensus protocols like $\mathsf{Tusk}$
[16]111https://github.com/asonnino/narwhal and
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ [18] were demonstrated with only 50 and
64 nodes, respectively. As Figure 1 depicts, we evaluate these state-of-the-
art designs in a LAN setting, revealing that they suffer from a significant
performance decline as the number of participating nodes increases, despite
their appealing performance at smaller scales like 16 or 64 nodes. 222Note
that a direct comparison between the throughputs of $\mathsf{Tusk}$ and
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ is meaningless due to their difference
on implementing storage, and we shall focus on the trend of throughput and
latency change with scales. Notably, while the number of nodes $n$ increases
from 16 to 256, their peak throughput and latency are worse by 3 and 2 orders
of magnitude, respectively.

Figure 1: $\mathsf{Tusk}$ [16] and $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ [18]
for 16-256 nodes in LAN. Each node is an EC2 c6a.2xlarge instance with 12.5
Gbps bandwidth (upload+download).

The inferior performance in larger-scale networks significantly hampers the
widespread adoption of asynchronous BFT consensus in real-world blockchain
systems. In particular, a larger number of participating nodes is a sine qua
non to diversify trust for mission-critical applications such as
cryptocurrency and decentralized finance, thus necessitating our continued
efforts to boost the performance of asynchronous consensus in larger-scale
networks.

Scalability bottlenecks of signature-involved prior art. We begin with a
succinct examination of $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ and
$\mathsf{Tusk}$ — the most practical asynchronous BFT consensus protocols in
relatively small networks such as several dozens of nodes, in order to unveil
the major obstacles hindering their scalability. Both $\mathsf{Tusk}$ and
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ can execute a process continuously
disseminating transactions concurrently to another process deciding a unitary
order of transactions that have been disseminated, thus maximizing bandwidth
utilization and achieving appealing performance (for several dozens of nodes).

However, both protocols heavily rely on signature based quorum certificates
(QCs) to implement the performance-optimized structure of concurrent broadcast
and agreement: each node has to broadcast $\mathcal{O}(n)$ QCs on different
messages per decision, indicating overall $\mathcal{O}(n^{3})$ QCs per output
block. Worse still, $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ and $\mathsf{Tusk}$,
like many earlier BFT studies [26, 27, 28], implement QCs by concatenating
$2f+1$ non-aggregate signatures (where $f$ is the number of maximal malicious
nodes).333It might be a little bit surprising, but we find that the official
implementations of many popular BFT protocols (like HotStuff, Speeding Dumbo,
Dumbo-NG, Narwhal and Tusk) use ECDSA/EdDSA for implementing QC. Although they
can theoretically use aggregatable signatures like threshold Boneh-Lynn-
Shacham (BLS) signature as alternative, they explicitly avoid the aggregatable
threshold signatures in practice, because threshold signatures might entail
concretely expensive computation costs of cryptographic pairings and Lagrange
interpolation in the exponent (as elaborated by a very recent thorough
benchmarking [29]).

Then if we implement QCs by ECDSA/EdDSA with standard 128-bit security as
suggested by earlier practices [26, 27, 28, 29], when $n$=$200$ nodes, each
node needs to send at least 343 MB signatures per decision;444Each QC contains
$n$-$f$=134 ECDSA/EdDSA signatures, and each signature has 64 bytes (if
compression is turned off for computation efficiency). So sending $n$ QC to
$n$ nodes would cost $(n-f)*64*n*n$=343 MB. even worse, each node receives a
minimum of $n$ distinct QCs that have to verify, indicating a CPU latency of
second(s).555Verifying an ECDSA/EdDSA costs $\sim$40 $\mu$s at EC2 c6a.2xlarge
instance. As Figure 2 depicts, we further test
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ in LAN to experimentally demonstrate the
high cost of QCs in practice. It reveals: (i) when $n$ increases to 196 from
16, the ratio of signature verifications in CPU time increases from
$\sim$16.7% to $\sim$66.6%,666Breakdown of CPU time was measured using
Golang’s profiling tool pprof. (ii) the communication of QCs jumps from
$\sim$0.8% of total communication to $\sim$40%. Apparently, the overhead of
signatures (which can be characterized by a fine-grained metric called
authenticator complexity [26, 30]) now plays a key role in the inferior
performance in the large-scale settings with hundreds of nodes.

Figure 2: Cost breakdown of Dumbo-NG in LAN consisting of 16-196 nodes.

Practical issues of existing (nearly) signature-free designs. Since the major
scalability bottleneck of
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$/$\mathsf{Tusk}$ stems from their
tremendous usage of signature-based QCs, one might wonder whether some
existing “signature-free” asynchronous BFT protocols could better extend to
work in large-scale networks. In particular, some recent studies like PACE
[31] and FIN [20] attempt to reduce authenticators as many as possible,
resulting in some (nearly) signature-free asynchronous BFT protocols 777We
follow the conventional abuse of term “signature-free”, though these protocols
[31, 20] might require public key assumptions to practically generate
distributed common randomness and/or leverage cryptographic hash functions for
efficiency. Both hidden assumptions theoretically imply signatures. that can
get rid of public key operations except for distributed randomness.

In short, PACE and FIN directly execute a special variant of asynchronous
Byzantine agreement called asynchronous common subset (ACS) [32], which can
solicit $n-f$ nodes’ proposals as a block of consensus output. However, these
signature-free approaches have their own efficiency issues that could be even
more serious than $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ and $\mathsf{Tusk}$
[18]: (i) severe transaction censorship— the adversary can constantly prevent
$f$ honest nodes from contributing into consensus results, causing an order of
$\mathcal{O}(n)$ communication blowup because censored transactions have to be
redundantly broadcasted by majority honest nodes;888HoneyBadger BFT (HBBFT)
uses threshold encryption to wrap ACS against censorship threat but this
introduces considerable computational cost. (ii) low bandwidth utilization—
they sequentially execute transaction broadcast and agreement, so during a
long period of agreement phase, bandwidth is “wasted” to contribute nothing
into throughput; (iii) costly erasure-code— they use erasure-code based
reliable broadcasts [33], where every node performs $\mathcal{O}(n)$ erasure-
code decodings, causing high CPU cost (cf. Figure 3).

Figure 3: CPU time breakdown of FIN for 16-196 nodes in LAN (when system load
is close to peak throughput). Here “MT” represents Merkle tree [34]; “RS”
represents Reed-Solomon code [35] (instantiated by a fast implementation [36]
of a systematic Cauchy Reed-Solomon variant [37, 38]).

Bearing the substantial scalability challenge in the state-of-the-art of
asynchronous BFT, the next question remains open:

_Can we extend the appealing performance of the
existing performant asynchronous BFT consensus protocols
to larger networks with several hundreds of nodes?_

TABLE I: Comparison between asynchronous BFT consensus (state-machine
replication) protocols.

| Per-Decision Complexities (summed over all nodes) |  Technique to realize Liveness in the worst case against tx censorship |  Fairness (Quality) |  Concurrent broadcast & agreement
---|---|---|---|---
|  | Amortized
---
Comm.
(worst-case)
Message |  | Authenticator
---
(except dist.
common coin)
Round |  | Number of
---
normal-path
EC decoding
BKR94 [32] | $O(n^{3}|\mathsf{tx}|)$ | $O(n^{3})$ | - | $O(\log n)$ | - | duplicated tx buffers $\ddagger$ | ✓ | ✗
HBBFT [12, 13] | $O(n|\mathsf{tx}|)$ | $O(n^{3})$ | - | $O(\log n)$ |  $O(n^{2})$ ∗ | duplicated tx buffers + TPKE $\diamond$ | ✓ | ✗
PACE [31] | $O(n^{2}|\mathsf{tx}|)$ | $O(n^{3})$ | - | $O(\log n)$ |  $O(n^{2})$ ∗ | duplicated tx buffers $\ddagger$ (hash-only) | ✓ | ✗
DL [21] |  $O(\kappa n|\mathsf{tx}|)$ $\dagger$ | $O(n^{3})$ | - | $O(\log n)$ |  $O(n^{2})$ ∗ | strong validity $\dagger$ | ✓ | ✗
FIN [20] | $O(n^{2}|\mathsf{tx}|)$ | $O(n^{3})$ | - | $O(1)$ |  $O(n^{2})$ ∗ | duplicated tx buffers $\ddagger$ (hash-only) | ✓ | ✗
CKPS01 [11] | $O(n^{3}|\mathsf{tx}|)$ | $O(n^{2})$ | $O(n^{3})$ | $O(1)$ | - | duplicated tx buffers $\ddagger$ | ✓ | ✗
sDumbo [27] |  $O(n|\mathsf{tx}|)$ $\dagger$ | $O(n^{2})$ |  $O(n^{3})$; $O(n^{4})$ impl.§ | $O(1)$ | - | duplicated tx buffers + TPKE $\diamond$ | ✓ | ✗
Tusk [16] | $O(n^{2}|\mathsf{tx}|)$ | $O(n^{2})$ |  $O(n^{3})$; $O(n^{4})$ impl.§ | $O(1)$ | - | duplicated tx buffers $\ddagger$ | ✓ | ✓
Dumbo-NG [18] |  $O(\kappa n|\mathsf{tx}|)$ $\dagger$ | $O(n^{2})$ |  $O(n^{3})$; $O(n^{4})$ impl.§ | $O(1)$ | - | strong validity $\dagger$ | ✗ | ✓
FIN-NG (this work) |  $O(\kappa n|\mathsf{tx}|)$ $\dagger$ | $O(n^{3})$ | - | $O(1)$ | - | strong validity $\dagger$ | ✓ | ✓
$\mathsf{JUMBO}$ (this work) |  $O(\kappa n|\mathsf{tx}|)$ $\dagger$ | $O(n^{2})$ | $O(n^{2})$ | $O(1)$ | - | strong validity $\dagger$ | ✓ | ✓
|  |  |  |  |  |  |  |

  * ‡

“Duplicated tx buffers” mean that a transaction has to be sent to $f+1$ honest
nodes’ transaction buffers, otherwise the transaction might never be agreed
and violate liveness. This is a typical problem causing quadratic (amortized)
communication cost in protocols directly built from asynchronous common subset
(ACS) such as PACE and FIN [20, 31, 32], because the adversary can enforce ACS
to constantly drop $f$ honest nodes’ proposed transactions.

  * $\diamond$

HBBFT, BEAT and sDumbo warp ACS by threshold encryption, amortizedly reducing
communication cost to $O(n)$ despite duplicated tx buffers.

  * †

“Strong validity” guarantees every transaction proposed by any honest node to
be eventually agreed. It allows de-duplication techniques [39, 16] to send
each transaction to only $\kappa$ random nodes (where $\kappa$ is a small
parameter ensuring overwhelming probability to include an honest node in
$\kappa$ random nodes).

  * §

Tusk, sDumbo and Dumbo-NG [18, 16, 27] have $O(n^{3})$ authenticator
complexity if using non-interactive threshold signatures to implement QCs, but
their implementations actually choose ECDSA/EdDSA for concrete performance,
resulting in $O(n^{4})$ authenticator complexity.

  * ∗

Though each node performs $O(n)$ number of erasure-code decoding, this
reflects a computation cost of $\tilde{O}(n^{2})$, as each decoding has
$\tilde{O}(n)$ operations.

###  I-B Our Contribution

We systematically investigate how to overcome the scalability issues of
existing asynchronous BFT consensus and answer the aforementioned question in
affirmative. A couple of more scalable asynchronous consensus protocols
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ and $\mathsf{JUMBO}$ are designed and
experimentally demonstrated. In greater detail, our core contributions can be
summarized as:

  * •

FIN-NG: adapting the existing signature-free approaches into parallel
broadcast and agreement. We initially propose a more scalable signature-free
asynchronous BFT consensus protocol $\mathsf{FIN}\textrm{-}\mathsf{NG}$, by
adapting the signature-free state-of-the-art FIN into the enticing paradigm of
concurrent broadcast and agreement. In comparison to FIN,
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ avoids the unnecessary detour to ACS and
can (i) achieve significantly higher throughput because concurrently running
broadcast and agreement can more efficiently utilize bandwidth resources, (ii)
ensures all honest nodes’ proposals to finally output, thus realizing strong
liveness to mitigate the censorship threat in FIN, (iii) avoid full-fledged
reliable broadcasts as well as computationally costly erasure-coding in normal
path to further reduce latency. FIN-NG not only greatly improves the
performance of FIN, but also already outperforms the signature-involved state-
of-the-art protocols like $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ in most
deployment settings.

  * •

Comprehensive benchmarking and optimizations towards concretely faster QC
implementation. We assess the impact of implementing QCs from various digital
signatures, including concatenated ECDSA/Schnorr signature [40], non-
interactively half-aggregatable Schnorr signature [41, 42], BLS multi-
signature [43, 44] and BLS threshold signature [45]. Neither same to many
previous practitioners [29, 18, 27, 16, 28, 26] suggesting ECDSA/EdDSA for
(concrete) computing efficiency nor similar to many theorists using threshold
signatures for communication efficiency [11, 9, 15, 17], we strictly suggest
to implement QCs by BLS multi-signature in an overlooked “batch-then-verify”
manner [47, 46], with adding a “blocklist” against performance downgrade by
excluding malicious signers while aggregating. This enjoys the short size of
aggregate signatures and avoids their costly verifications or aggregation.
Moreover, regarding the major authenticator bottleneck of sending
$\mathcal{O}(n)$ QCs, we explore the merit of BLS multi-signatures to further
compress $\mathcal{O}(n)$ QCs on different messages, alleviating the
communication of transferring $\mathcal{O}(n)$ QCs by saving more than half in
size.

  * •

$\mathsf{JUMBO}$: even more scalable asynchronous BFT instantiation with
$O(n^{2})$ authenticators and messages. Despite
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ and our various QC optimizations, we still
seek for a more scalable solution to asynchronous BFT that can asymptotically
reduce authenticator complexity and simultaneously attain quadratic message
complexity. As shown in Table I, we achieve the goal by presenting
$\mathsf{JUMBO}$—a non-trivial scalable instantiation of
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$, by introducing the information
dispersal technique [17] to reduce the number of multicasting $\mathcal{O}(n)$
QCs from $n$ to expected constant. $\mathsf{JUMBO}$ asymptotically reduces
authenticator overhead with preserving a balanced $O(n^{2})$ message
complexity, thus significantly outperforming the state-of-the-art protocols
and $\mathsf{FIN}\textrm{-}\mathsf{NG}$ in most settings (particularly in
these settings with larger scales and restricted bandwidth). Moreover, we
propose a patch for $\mathsf{JUMBO}$ to achieve a desired security property of
“fairness”, thus preventing adversaries from controlling arbitrary portion of
transactions in the consensus output.

Figure 4: Our designs v.s. state-of-the-art in a WAN setting (400 ms RTT, 100
Mbps bandwidth) for $n=$128, 196 and 256.

  * •

Open-source implementation and extensive evaluations in varying network
settings with up to 256 nodes. We implemented $\mathsf{JUMBO}$ and FIN-NG in
Golang, and also $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ [18] and FIN [20] in
the same language as by-product for fair comparison. These protocols were
comprehensively evaluated in WAN settings for $n=$ 64, 128, 196, 256 nodes.
Malicious attacks such as $\mathsf{MVBA}$ quality manipulation and sending of
false signatures are also evaluated. Figure 4 highlights part of our results
in a network of 100 Mbps bandwidth and 400 ms RTT. 999Most cloud providers
charge $>$1,000 USD/month for reserving 100 Mbps bandwidth, and 400 ms RTT is
typical for cities between Asia and America. Such condition arguably reflects
a setting of affordable global deployment. Noticeably, $\mathsf{JUMBO}$ is 5X
and 70X faster than FIN and $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$,
respectively, in the setting of 256 nodes. More interestingly,
$\mathsf{JUMBO}$ can realize the least latency and simultaneously achieve the
maximal throughput closer to line rate. For detailed performance comparison
among these protocols, cf. Section VIII.

Our open-source codebase of $\mathsf{JUMBO}$,
$\mathsf{FIN}\textrm{-}\mathsf{NG}$, FIN and
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ is of about 13,000 LOC and available at:

https://github.com/tca-sp/jumbo.

##  II Challenges and Our Techniques

Bearing the major scalability bottleneck of authenticator complexity in
existing signature-involved asynchronous BFT protocols, our first attempt is
to resolve the efficiency issues of signature-free prior art (like FIN),
towards achieving a better scalable signature-free asynchronous BFT protocol
$\mathsf{FIN}\textrm{-}\mathsf{NG}$. Then, we dedicatedly optimize the state-
of-the-art signature-involved protocols (like
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$), leading up to a scalable asynchronous
BFT instantiation $\mathsf{JUMBO}$ that not only asymptotically reduce the
authenticator overhead but also is concretely efficient in large-scale
networks.

Figure 5: The paradigm of parallel broadcasts and agreement (the high-level
rationale behind both $\mathsf{FIN}\textrm{-}\mathsf{NG}$ and
$\mathsf{JUMBO}$).

###  II-A Challenges and Techniques of $\mathsf{FIN}\textrm{-}\mathsf{NG}$

As illustrated in Figure 5, $\mathsf{FIN}\textrm{-}\mathsf{NG}$ has a
straightforward high-level idea similar to [18], i.e., adapt the existing
signature-free asynchronous common subset protocols like FIN into the enticing
paradigm of parallel broadcasts and agreement. The paradigm can deconstruct
asynchronous common subset protocol into two concurrent processes: (i) one
bandwidth-intensive process consists of $n$ multi-shot broadcast instances,
and each broadcast allows a designed node to sequentially disseminate its
transactions to the whole network, and (ii) the other agreement process
executes a sequence of asynchronous multi-valued validated Byzantine agreement
($\mathsf{MVBA}$) protocols, such that every $\mathsf{MVBA}$ can solicit some
latest completed broadcasts and decide a new block to output.

However, when adapting FIN into the enticing paradigm of parallel broadcast
and agreement, we face a couple of new challenges that do not exist in the
signature-involved setting.

Challenge NG-1: erasure-code computation might bring heavy CPU cost in
broadcasts. The first problem of implementing
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ is how to efficiently implement its
broadcast primitives. One might suggest the communication-efficient variants
[48, 33, 49] of Bracha’s reliable broadcast [50, 51]. However, although these
protocols can attain amortized linear communication cost (for sufficiently
large input batch), their price is the necessity of erasure-coding. What is
worse, the efficiency issue of using erasure-code in these broadcast protocols
could be very serious, even if we cherry-pick fairly fast implementation as
suggested by [13] (cf. Figure 3), because these broadcast protocols rely on
sufficiently large input batches to amortize their communication cost, making
encoding over very large fields and thus unsurprisingly slow.

Our approach. We overcome the efficiency issue by introducing a weakened
variant of reliable broadcast that can be efficiently implemented without any
erasure-coding. Similar to the normal path of PBFT [24], the broadcast
primitive no longer ensures all honest nodes to eventually receive the
broadcast value; instead, it only guarantees $f+1$ honest nodes to receive the
original broadcast value, and allows the remaining honest nodes only
eventually receive a hash digest of value. We further provide a pulling
mechanism to compensate the weakening of broadcast. The pulling mechanism
incorporates dispersal technique [33] for communication optimization, such
that for any honest node that only receives the hash digest, it can
efficiently fetch the missing transactions from other honest nodes, at an
amortized linear communication cost.

Challenge NG-2: poor “quality” of existing signature-free MVBA might hinder
liveness of $\mathsf{FIN}\textrm{-}\mathsf{NG}$. It is notable that in
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$, its liveness relies on the so-called
“quality” of $\mathsf{MVBA}$ protocols. Here quality means the output of
$\mathsf{MVBA}$ shall not be fully manipulated by the adversary. Imagine that
the adversary can completely manipulate the $\mathsf{MVBA}$ result, it thus
can rule out a certain honest node’s broadcast from the finalized output
(because the $\mathsf{MVBA}$ result determines which nodes’ broadcasts shall
be solicited by the output block). This clearly violates liveness, because
some honest node’s broadcasted transactions wouldn’t eventually output
anymore. In the signature-based setting, there are several efficient
$\mathsf{MVBA}$ protocols [14, 15, 17] with optimal 1/2 quality, such that
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ can be securely instantiated with
preserving liveness. However, to our knowledge, there is no signature-free
$\mathsf{MVBA}$ protocol with satisfying quality property, which might
potentially cause liveness vulnerability in
$\mathsf{FIN}\textrm{-}\mathsf{NG}$.

Our approach. To deal with the potential liveness issue, we necessarily
redesign the state-of-the-art signature-free $\mathsf{MVBA}$ protocol
FIN-$\mathsf{MVBA}$ [20] to ensures optimal 1/2 quality [52] against adaptive
adversaries, i.e. the output is proposed by some honest node with at least 1/2
probability. In contrast, FIN-$\mathsf{MVBA}$ protocol only ensures 1/3
quality in the same setting.101010Note that although [20] proposed a quality
patch for its $\mathsf{MVBA}$, it still only ensures 1/3 quality against an
adaptive adversary with “after-fact-removal” (i.e., the adversary can
adaptively corrupt some node and remove this node’s undelivered messages), cf.
Appendix B in Supplementary for detailed analysis. The seemingly small
difference in $\mathsf{MVBA}$’s quality can reduce the latency by an entire
$\mathsf{MVBA}$ execution, and can render a considerable improvement of
latency in $\mathsf{FIN}\textrm{-}\mathsf{NG}$ under Byzantine setting (cf.
Section VIII for our experiment evaluation of $\mathsf{MVBA}$ quality’s impact
on latency).

###  II-B Challenges and Techniques of $\mathsf{JUMBO}$

As a concrete instantiation of $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$, the
design of $\mathsf{JUMBO}$ also follows the high-level structure of parallel
broadcast and agreement shown in Figure 5. However, to make $\mathsf{JUMBO}$
practically operate in large-scale networks with enhanced fairness guarantee,
we necessarily overcome the following challenges to reduce the prohibitive
authenticator complexity in $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$, both
concretely and asymptotically.

Challenge J-1: trivial use of aggregatable signatures like BLS could be
computationally slow. Although it is well known that aggregatable signatures
like BLS threshold signature can make great theoretic improvement to BFT
protocols, it is not a popular choice in real-world systems. In particular,
some very recent BFT protocols like HotStuff [26], $\mathsf{Tusk}$ [16] and
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ [18] choose ECDSA/EdDSA signatures
instead of BLS threshold signature to implement QCs in practice. And a recent
benchmarking [29] even suggests ECDSA/EdDSA signature always favorable than
BLS threshold signature for large-scale networks, as it points out that (the
trivial use of) BLS threshold signature might suffer from huge computation
costs like the verification of individual signature and the aggregation
involving interpolation in exponent.

Our approach. To make QC implementation concretely faster, we provide a
resolution to settle the debate regarding QC implementation between theory and
practice, and affirm that QC from BLS multi-signature (with non-trivial
optimizations) could be the best practice for large-scale BFT systems. First,
BLS multi-signature has very simple and efficient aggregation, which is
concretely much faster than its threshold counterpart as it does not perform
the heavy computation of interpolation in exponent. Second, we extend the
optimistic “batch verification” approach for BLS multi-signatures [46, 47] by
adding an easy-to-implement “blocklist” mechanism to rule out malicious nodes
from quorum, thus amortizedly extending its superior efficiency in the
optimistic case into the worst case. Third, BLS multi-signature allows to
aggregate $O(n)$ QCs across various messages (i.e., the primary authenticator
bottleneck in $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ and $\mathsf{Tusk}$), and
we leverage this nice property to further reduce the concrete size of $n$
different QCs by more than half.

Challenge J-2: how to achieve asymptotically lower authenticator complexity?
By extending $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ or $\mathsf{Tusk}$? It is
worth noticing $\mathsf{Tusk}$ has a directed acyclic graph (DAG) structure
where every node has to multicast at least $n-f$ QCs of preceding broadcasts,
These QCs are so-called “edges” pointing to preceding broadcasts to form DAG.
Therefore, all multicasts of $n-f$ QCs are intuitively needed in
$\mathsf{Tusk}$ as part of its DAG structure. In contrast, a key observation
of $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ is that the cubic term of its
authenticator complexity has a unique reason caused by the input multicast
phase of $\mathsf{MVBA}$ protocols. This fact raises a question to us: Can we
reduce the number of input multicasts inside
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$’s $\mathsf{MVBA}$ protocol? This is
probably plausible because $\mathsf{MVBA}$ only decides one node’s input as
output, so the remaining input multicasts are essentially redundant.

Our approach. We leverage the neat structure of
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ to incorporate a simplistic manner to
reduce the authenticator complexity by an $\mathcal{O}(n)$ order. In short, we
apply $\mathsf{MVBA}$ extension protocol [17] to replace the multicasts of $n$
QCs by more efficient dispersals of QCs. More precisely, we let every node use
a provable dispersal protocol [17] to efficiently disperse $n$ QCs (instead of
trivially multicasting), then only a constant number of dispersals (instead of
all $n$ dispersals) are reconstructed for verifications. This dispersal-then-
recast paradigm reflects our observation that only one multicast of $n$ QC is
necessary, and all else are essentially redundant. Clearly, this optimized
execution flow is asymptotically more efficient, because each dispersal has a
much less commutation cost that is only $O(1/n)$ of trivial multicast.

##  III Problem Formulation and Preliminaries

###  III-A System and Threat Models

We adopt a widely-adopted asynchronous message-passing model with initial
setups and Byzantine corruption [9, 11, 15, 17], which can be formally
described in the following:

Known participating nodes. There are $n$ designated nodes in the system. We
denote them by $\\{\mathcal{P}_{i}\\}_{i\in[n]}$, where $[n]$ is short for
$\\{1,\dots,n\\}$. Each $\mathcal{P}_{i}$ is bounded to some public key
$pk_{i}$ known by all other nodes through a bulletin board PKI (though we
might not use the setup in the signature-free construction).

Established threshold cryptosystem. To overcome FLP impossibility, we depend
on a cryptographic coin flipping protocol [9], which can return unpredictable
common randomness upon a threshold of participation nodes invoke it. This
usually requires some threshold cryptosystem [53, 9] that is already setup,
which can be done through either asynchronous distributed key generation [54,
55, 56, 19] or a trusted third party.

Computationally-bounded Byzantine corruption. We focus on optimal resilience
in asynchrony against an adversary $\mathcal{A}$ that can corrupt up to
$f=\lfloor(n-1)/3\rfloor$ nodes. Following standard cryptographic practice,
the adversary is probabilistic polynomial-time bounded, making it infeasible
to break cryptographic primitives. We might consider static or adaptive
adversaries, where static adversaries choose a fixed set of $f$ nodes to
corrupt before the protocol starts, and adaptive ones can gradually corrupt
$f$ nodes during protocol execution.

Reliable authenticated asynchronous network. We consider a reliable
asynchronous message-passing network with fully-meshed point-to-point links
and authentications. Messages sent through the underlying network can be
arbitrarily delayed by the adversary due to asynchrony, but they can be
eventually delivered without being tampered or forged. In addition, while a
node receives a message, it can assert the actual sender of the message due to
authentication.

###  III-B Design Goal: Asynchronous BFT Consensus with Fairness

We aim at secure asynchronous BFT consensus protocols satisfying the next
atomic broadcast abstraction.

######  Definition 1.

Asynchronous BFT atomic broadcast (ABC). In an ABC protocol, each node has an
input buffer of transactions, and continually outputs some blocks of
transactions that form an ever-growing and append-only linearized log of
transactions. The protocol shall satisfy the next properties with all but
negligible probability:

  * •

Agreement. If an honest node outputs a transaction, then all honest nodes
eventually output it.

  * •

Total Order. For any two output logs of honest node(s), one is a prefix of the
other, or they are equal.

  * •

Liveness (Strong Validity). If a transaction is placed in any honest node
input buffer, it can eventually be included by the output log of some honest
node.

  * •

$\alpha$-Fairness. For any block outputted by some honest node, if the block
contains $K$ transactions, then at least $\alpha\cdot K$ transactions in the
block are proposed by honest nodes.

Some remarks on the above definition:

  * •

For liveness (validity), we define it in a strong form: if a transaction stays
in any honest node’s input buffer, it can eventually output, while some weaker
forms only guarantee this if the transaction is input of $f+1$ honest nodes or
all honest nodes. Strong validity is a useful property enabling de-duplication
of input transactions [18, 39, 16], namely, allowing a client forward its
transactions to only a small number of $k$ consensus nodes.

  * •

Fairness bounds the “quality” of consensus [57] and prevents the adversary
controlling an arbitrarily large portion in the output, ensuring that the
consensus output contains sufficiently many transactions proposed by honest
nodes.

###  III-C Complexity Measurements

Besides security, we are also interested in constructing practical
asynchronous BFT protocols. For the purpose, we consider the next complexity
metrics as efficiency indicators:

  * •

Message complexity [11]: the expected number of messages sent by honest nodes
to decide an output. Note that we do not count message complexity amortized
for batched decision in order to reflect the actual overhead of
packet/datagram headers in a real networked systems.

  * •

(Amortized) bit communication complexity [11]: the expected number of bits
sent by honest nodes per output transaction. Note that bit communication
complexity is amortized for a batch of decision to reflect the number of
communicated bits related to each output transaction.

  * •

Round complexity [4]: the expected asynchronous rounds needed to output a
transaction. Here asynchronous round is a “time” unit defined by the longest
delay of messages sent among honest nodes [4, 58].

  * •

Authenticator complexity [26, 30]: the expected communicated bits generated by
honest nodes associated with transferring (or verifying) signatures per output
decision. For protocols that all have the optimal (linear) amortized bit
communication complexity, authenticator communication complexity can provide a
more fine-grained measurement to distinguish their actual communication
overheads, thus guiding us towards more scalable protocol designs.

###  III-D Preliminaries

Byzantine reliable broadcast ($\mathsf{BRBC}$). A $\mathsf{BRBC}$ protocol
[50, 59] among $n$ participating nodes has a designated sender and can
simulate an ideal broadcast channel in an point-to-point network, thus
realizing (i) agreement: any two honest nodes’ outputs are same; (ii)
totality: all honest nodes would eventually output some value conditioned on
some honest node has output, and (ii) validity: an honest sender’s input can
eventually be output by all honest nodes.

Weak Byzantine reliable broadcast (w$\mathsf{BRBC}$). A w$\mathsf{BRBC}$
protocol is a relaxed $\mathsf{BRBC}$, where an honest node either outputs a
value or a hash digest. The protocol satisfies (i) weak agreement: two honest
nodes’ outputs are either the same value, or the same hash digest, or a value
and its hash digest; (ii) weak totality: at least $n-2f$ honest nodes would
eventually output some value and all rest honest nodes would eventually output
some digest conditioned on some honest node has output, (ii) validity: same to
$\mathsf{BRBC}$.

Multi-valued validated Byzantine agreement ($\mathsf{MVBA}$) [15, 11, 17].
This is a variant of Byzantine agreement with external validity, such that all
honest nodes can agree on a value satisfying a publicly known predicate $Q$.
More formally,

######  Definition 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. An $\mathsf{MVBA}$ protocol running among $n$ nodes shall satisfy the
next properties except with negligible probability:

  * •

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

  * •

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

  * •

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

  * •

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

In addition, many studies [60, 61, 62, 20] recently realized that the external
validity property of $\mathsf{MVBA}$ can be extended to support a somewhat
internal predicate, which does not return “false”, but keeps on listening the
change of the node’s local states and returns “true” only if the joint of
predicate input and a node’s local states satisfies a pre-specified validity
condition. This is particularly useful if the higher level protocol can
enforce all nodes’ internal predicates to eventually be true as long as any
honest node’s predicate is true, e.g., all nodes keep on checking whether they
output in a specific $\mathsf{BRBC}$ protocol. Later in Section IV, the
internal predicate allows us to design FIN-NG by adapting the signature-free
ACS protocol FIN into the paradigm of concurrent agreement and broadcast.

Reproposable asynchronous binary agreement ($\mathsf{RABA}$) [31]. This is a
special variant of binary Byzantine agreement, where each node is additionally
allowed to change its input from 0 to 1 (but not vice versa). Here we recall
its definition:

######  Definition 3.

Syntactically, a node in $\mathsf{RABA}$ is allowed to invoke two input
interfaces $raba$-$propose$ and $raba$-$repropose$, and has an output
interface $raba$-$decide$ to receive the output; an honest node is required to
use the interfaces in the following way: (i) must invoke $raba$-$propose$
before $raba$-$repropose$, (ii) cannot use any interface more than once, (iii)
can only take 0 or 1 as input of $raba$-$propose$ and $raba$-$repropose$
interfaces, (iv) cannot $raba$-$propose$ 1 and then $raba$-$repropose$ 0 (but
vice versa is allowed). A $\mathsf{RABA}$ protocol shall satisfy the next
properties except with negligible probability:

  * •

Agreement. If any two honest nodes terminate, then they $raba$-$decide$ the
same value.

  * •

Unanimous termination and Unanimous validity. If all honest nodes
$raba$-$propose$ $v$ and never $raba$-$repropose$, then all honest nodes
terminate and $raba$-$decide$ $v$.

  * •

Biased validity. If $f+1$ honest nodes $raba$-$propose$ 1, no honest node
would $raba$-$decide$ 0.

  * •

Biased termination. If all honest nodes $raba$-$propose$ 1 or eventually
$raba$-$repropose$ 1, then all honest nodes would terminate and
$raba$-$decide$.

Cryptographic notions. $\mathcal{H}$ denotes a collision-resistant one-way
hash function. $\mathsf{Sign}$ and $\mathsf{SigVerify}$ represent the signing
and verifying algorithms of a signature scheme that is existentially
unforgeable under adaptive chosen message attack (i.e., EUF-CMA secure). We
also consider non-interactively aggregatable multi-signature (or threshold
signature) [42, 41, 45, 43, 44], where is another $\mathsf{Agg}$ algorithm
that can input multiple signatures on a message and output a multi-signature
(or threshold signature) on the same message.

Aggregating BLS (multi-)signatures in KOSK model. It is noticeably that we
adopt the standard knowledge-of-secret-key (KOSK) model [45]: every node has
to sign a valid signature to prove its knowledge of secret key when
registering public key. This is the standard process of real-world CA while
issuing certificates [63] and also reflects the public key registration in
proof-of-stake blockchains. The KOSK model brings very convenient aggregation
of BLS signatures. In particular, the simplistic aggregation is in form of
$\mathsf{Agg}(\sigma_{1},\cdots,\sigma_{k})=\prod_{j=1}^{k}\sigma_{j}$, which
simply returns $\sigma_{1}\cdots\sigma_{k}$ as result. Here
$\sigma_{1},\cdots,\sigma_{k}$ can be BLS signatures or even already-
aggregated BLS multi-signatures on either same or different messages. Later in
Section V, we will showcase how asynchronous BFT can leverage this aggregation
technique towards aggregating $\mathcal{O}(n)$ QCs on different messages.

##  IV Initial attempt: $\mathsf{FIN}\textrm{-}\mathsf{NG}$ to scale up
Signature-free Asynchronous BFT

This section attempts to enhance the scalability of signature-free
asynchronous BFT protocols, by adapting the cutting-edge signature-free ACS
protocol FIN into the enticing paradigm of concurrent broadcast and agreement.
The resulting protocol $\mathsf{FIN}\textrm{-}\mathsf{NG}$ already outperforms
existing asynchronous BFT protocols in the bandwidth-sufficient setting.
Finally, we explain why cubic messages of $\mathsf{FIN}\textrm{-}\mathsf{NG}$
might cause unsatisfying performance degradation in the bandwidth-starved
environment.

Figure 6: High-level of $\mathsf{FIN}\textrm{-}\mathsf{NG}$.

Overview of $\mathsf{FIN}\textrm{-}\mathsf{NG}$. As shown in Figure 6,
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ deconstructs FIN ACS [20] to separate
transaction broadcast from consensus. Noticeably, a trivial parallelization of
FIN ACS’s broadcast and agreement wouldn’t bring us well-performing
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ in large-scale networks, and we specially
tailor both modules to alleviate their efficiency bottlenecks as follows:

  * •

Avoid costly $\mathsf{BRBC}$ towards more efficient broadcast: FIN
instantiates its broadcast process by using CT05 $\mathsf{BRBC}$ [59]. The
protocol leverages erasure-code to attain amortized linear communication cost
(for sufficiently large batch of broadcast input). However, CT05
$\mathsf{BRBC}$ involves expensive decoding, which could be very costly in FIN
as each node has to participate in $n$ such $\mathsf{BRBC}$s and perform $n$
times of decoding. We thus suggest to employ a more efficient process of
transaction dissemination with weakened reliability. That means, only $f+1$
honest nodes are ensured to receive consistent transactions and up to $f$
honest nodes might only receive the hash digest (which can be analog to PBFT
[24, 28]). Thanks to such weakening, the broadcast attains amortized linear
communication cost in the absence of erasure coding. To compensate the
weakening in broadcasts, we further propose a couple of communication-
efficient pulling mechanisms, such that any honest node can securely fetch its
missing transactions with amortized linear communication.

  * •

Enhance $\mathsf{MVBA}$ quality for liveness and lower latency: When
separating broadcasts and $\mathsf{MVBA}$ toward realizing
$\mathsf{FIN}\textrm{-}\mathsf{NG}$, the liveness might be hurt if the
underlying $\mathsf{MVBA}$ has sub-optimal quality. This is because if the
adversary can manipulate $\mathsf{MVBA}$’s output due to low quality, it can
make $\mathsf{MVBA}$ result never contain the indices of some nodes’ completed
broadcasts, thus censoring certain nodes and breaking liveness. To guarantee
liveness and fast confirmation in $\mathsf{FIN}\textrm{-}\mathsf{NG}$, we
redesign the signature-free $\mathsf{MVBA}$ protocols proposed in FIN [20].
The resulting FIN-$\mathsf{MVBA}$-Q protocol can ensure optimal 1/2 quality in
the influence of a strong adaptive adversary with “after-the-fact-removal”. In
contrast, $\mathsf{MVBA}$ protocols in FIN [20] only realizes $1/n$ quality
and $1/3$ quality, respectively, in the same setting. Later in Section VIII,
we experimentally test $\mathsf{FIN}\textrm{-}\mathsf{NG}$ using
$\mathsf{MVBA}$s with different quality, revealing that our seemingly small
improvement in $\mathsf{MVBA}$ quality can make a large difference in latency.

###  IV-A $\mathsf{FIN}\textrm{-}\mathsf{NG}$ Protocol

This subsection details $\mathsf{FIN}\textrm{-}\mathsf{NG}$ by elaborating its
transaction dissemination process and block agreement process.

Broadcast process in $\mathsf{FIN}\textrm{-}\mathsf{NG}$. Figure 7 illustrates
the broadcast process that disseminates transactions in
$\mathsf{FIN}\textrm{-}\mathsf{NG}$. There could be $n$ such multi-shot
broadcasts in $\mathsf{FIN}\textrm{-}\mathsf{NG}$, where each node
$\mathcal{P}_{i}$ acts as a leader in one broadcast instance, and all nodes
execute as receivers in all $n$ broadcasts. A multi-shot broadcast instance in
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ is executed as follows.

  * •

Tx dissemination through a sequence of weak $\mathsf{BRBC}$. The designated
sender $\mathcal{P}_{s}$ and all other nodes participate in a sequence of weak
reliable broadcast protocols (w$\mathsf{BRBC}$ defined in Sec. III-D). The
broadcast process resembles a simplistic normal-path of PBFT, so it only
ensures that at least $f+1$ honest nodes might (eventually) receive the
original broadcasted transactions, and up to $f$ else honest nodes might only
receive a consistent hash digest.

To bound the memory of buffering received transactions, all broadcast
participants can dump transactions into persistent storage if some
w$\mathsf{BRBC}$ outputs them, which is because
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ ensures strong validity to guarantee all
broadcasted transactions to be part of consensus output (so we can write these
broadcast results into disk).

  * •

Pulling mechanism in companion with broadcasts. We can enable the $f$ honest
nodes that only hold hash digest to fetch missing transactions from other
honest nodes. Since the node still can obtain the hash digest (despite missing
the original transactions), it can securely fetch the corresponding
transactions, because (i) it knows which w$\mathsf{BRBC}$ to fetch due to the
receival of digest, and (ii) at least $f+1$ honest nodes can output the
corresponding transactions due to the (weaker) totality property of
w$\mathsf{BRBC}$. Given this, we can propose two choices of implementing the
efficient pulling mechanism:

    * –

The first approach resembles Tusk’s pull mechanism against static adversaries
[16]: when $\mathcal{P}_{i}$ receives a hash digest from a certain
w$\mathsf{BRBC}$ instead of the original transactions, it asks $\kappa$ random
nodes for the missing transactions. There shall be an overwhelming probability
such that these selected nodes would contain at least one honest node
receiving the original transactions, implying that $\mathcal{P}_{i}$ can
eventually receive at least one respond carrying the correct transactions
consistent to its hash digest, with except negligible probability in $\kappa$.

    * –

The second way is secure against adaptive adversaries [18]. It lets
$\mathcal{P}_{i}$ ask all nodes when $\mathcal{P}_{i}$ realizes some missing
transactions, with preserving amortizedly linear communication complexity per
decision. The crux of improving communication efficiency is: the responses to
$\mathcal{P}_{i}$ are no longer the original transactions, but incorporate
communication-reducing techniques from asynchronous information dispersal [59,
48]. For each node $\mathcal{P}_{j}$, it chops the transactions requested by
$\mathcal{P}_{i}$ into $f+1$ fragments, and uses erasure code to encode the
$f+1$ fragments into $n$ code fragments, then computes a Merkle tree using $n$
code fragments as leaves, and sends $\mathcal{P}_{i}$ the Merkle tree root,
the $j$-th code fragment, and the corresponding Merkle proof attesting the
$j$-th code fragment’s inclusion in the Merkle tree. At the $\mathcal{P}_{i}$
side, it can finally receive at least $f+1$ responses carrying the same Merkle
tree root with valid Merkle proofs, such that $\mathcal{P}_{i}$ can decode the
$f+1$ code fragments to recover the missing transactions.

Figure 7: Broadcast instance in $\mathsf{FIN}\textrm{-}\mathsf{NG}$.

Agreement process in $\mathsf{FIN}\textrm{-}\mathsf{NG}$.
$\mathsf{FIN}\textrm{-}\mathsf{NG}$’s agreement process is a sequence of
$\mathsf{MVBA}$s proceeding as follows by epoch $e$:

When entering epoch $e=1$, each node $\mathcal{P}_{i}$ initializes a $n$-size
vector $\mathsf{ordered}_{e}=[0,\cdots,0]$. $\mathcal{P}_{i}$ also maintains a
$n$-size vector $0pt_{i}$, where the $j$-th item closely tracks that
$\mathcal{P}_{i}$ has received how many w$\mathsf{BRBC}$s broadcasted by
$\mathcal{P}_{j}$. When $0pt_{i}$ has $n-f$ items larger than
$\mathsf{ordered}_{e}$ and has all items not smaller than
$\mathsf{ordered}_{e}$ in the corresponding positions, the node
$\mathcal{P}_{i}$ takes a snapshot of $0pt_{i}$ as $\mathsf{MVBA}[e]$’s input.
$\mathcal{P}_{i}$ waits for that $\mathsf{MVBA}[e]$ returns a vector
$\mathsf{new\textrm{-}ordered}$ consisting of $n$ indices, and can pack all
w$\mathsf{BRBC}$s with indices between $\mathsf{ordered}_{e}$ and
$\mathsf{new\textrm{-}ordered}$ as a block of consensus result.111111If
$\mathsf{MVBA}[e]$ decides a certain w$\mathsf{BRBC}$ as consensus output but
$\mathcal{P}_{i}$ has not yet received anything from the w$\mathsf{BRBC}$, the
node can also invoke the pulling mechanism of broadcast instance to fetch the
missing transactions. Finally, $\mathcal{P}_{i}$ sets $e=e+1$ and
$\mathsf{ordered}_{e}=\mathsf{new\textrm{-}ordered}$, then enters the next
epoch $e$.

Noticeably, $\mathsf{MVBA}$ used in the above procedures shall be specified by
a predicate function satisfying the next conditions:

  1. 1.

Check that each item in $0pt_{j}$ is not shrink w.r.t. the last output of
$\mathsf{MVBA}$ (i.e. $\mathsf{ordered}_{e}$), return false on check fails,
otherwise go the next step.

  2. 2.

Check that at least $n-f$ items in $0pt_{j}$ increases w.r.t. the last output
of $\mathsf{MVBA}$, return false on check fails, otherwise go the next step.

  3. 3.

Wait for that each item in the local state $0pt_{i}$ is larger than or equal
to the corresponding item in $0pt_{j}$, and then return true.

Similar to [60, 61, 62], the above conditions requires some local states
(i.e., $0pt_{i}$—-each broadcast’s progress from $\mathcal{P}_{i}$’s view) to
verify. One might worry its step 3) might wait forever and hurt termination of
$\mathsf{MVBA}$. However, violation of termination wouldn’t happen because (i)
any honest node $\mathcal{P}_{i}$’s input to $\mathsf{MVBA}$ must be valid
regarding its own local states; (ii) the totality of broadcasts therefore
ensure all honest nodes can eventually update their local states to validate
$\mathcal{P}_{i}$’s input.

Security of $\mathsf{FIN}\textrm{-}\mathsf{NG}$. The security of
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ can be summarized as the following main
theorem:

######  Theorem 1.

$\mathsf{FIN}\textrm{-}\mathsf{NG}$ securely realizes asynchronous BFT atomic
broadcast without fairness except with negligible probability, conditioned on
the underlying w$\mathsf{BRBC}$ and $\mathsf{MVBA}$ protocols are secure
(where $\mathsf{MVBA}$ shall satisfying quality).

Security analysis. The rationale behind Theorem 1 is straight:

  * •

For safety, the broadcast of $\mathsf{FIN}\textrm{-}\mathsf{NG}$ built from
w$\mathsf{BRBC}$ can prevent malicious nodes to broadcast different
transactions to distinct nodes due to its weak agreement; moreover,
$\mathsf{MVBA}$’s validity and agreement can further ensure all honest nodes
would solicit the same finished broadcasts into each output block, thus
ensuring safety.

  * •

For liveness, w$\mathsf{BRBC}$’s validity ensures that all honest nodes can
reliably diffuse their transactions in only constant rounds; moreover,
$\mathsf{MVBA}$’s termination and quality gauntness that once an honest node’s
broadcast is delivered to all other honest nodes, this broadcast (or the same
node’s higher broadcast) would be solicited by some $\mathsf{MVBA}$ output
with an overwhelming probability of $1-(1-q)^{k}$ after $k$ $\mathsf{MVBA}$
executions, where $q$ is the quality of $\mathsf{MVBA}$ protocol, and
$(1-q)^{k}$ represents the probability that the adversary successively
manipulates $k$ $\mathsf{MVBA}$s’ outputs to prevent the certain broadcast
from outputting. Considering that the expectation of $k$ is $1/q$ and
$\mathsf{MVBA}$ also has expected constant round complexity, any transaction
that is broadcasted by some honest node would be decided as consensus output
in expected constant rounds (i.e., the broadcast rounds plus $1/q$ times of
$\mathsf{MVBA}$’s expected rounds), thus realizing liveness.

We defer the full proof to Appendix D in Supplementary.

Complexity analysis. It is fairly simple to count the complexities of
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ for its modular design. In particular, if
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ is instantiated by signature-free
$\mathsf{MVBA}$ with quality and cubic messages (e.g., FIN-$\mathsf{MVBA}$-Q
to be introduced in next subsection), its authenticator complexity is (nearly)
zero, but at a price of cubic messages per decision.

###  IV-B FIN-$\mathsf{MVBA}$-Q: $\mathsf{MVBA}$ with Optimal Quality

If we prefer a signature-free instantiation of
$\mathsf{FIN}\textrm{-}\mathsf{NG}$, it comes to our attention that few
satisfying signature-free $\mathsf{MVBA}$ protocols exist. One candidate is
the recent design of FIN-$\mathsf{MVBA}$ [20], which unfortunately suffers
from quality degradation (cf. Appendix B for detailed analysis) to cause the
adversary hold 2/3 chance to manipulate $\mathsf{MVBA}$ output. Worse still,
quality of $\mathsf{MVBA}$ is critical in $\mathsf{FIN}\textrm{-}\mathsf{NG}$
as it is necessary for liveness: the adversary can lower $\mathsf{MVBA}$
output’s quality to slow down $\mathsf{FIN}\textrm{-}\mathsf{NG}$’s
confirmation or even completely censor certain nodes. In order to guarantee
fast confirmation and liveness of $\mathsf{FIN}\textrm{-}\mathsf{NG}$, we
redesign FIN-$\mathsf{MVBA}$ to improve its quality toward 1/2 against strong
adaptive adversaries. Remarkably, our result attains the optimal quality in
asynchrony [52].

Abandonable validated Byzantine reliable broadcast. We identify the root
reason of quality degradation in FIN-$\mathsf{MVBA}$: an adaptive adversary
can hold a corruption quota until coin flipping is revealed to determine the
elected node, after which it can rushingly corrupt this elected node and
replaces the input value by the manipulating one. To prevent such rushing
adversaries, we set forth a notion of abandonable validated weak Byzantine
reliable broadcast (avw$\mathsf{BRBC}$), such that the honest nodes can reject
a rushing adversary’s value by abandoning the slowest broadcasts as soon as
the elected node is disclosed. Formally, avw$\mathsf{BRBC}$ can be defined as
follows:

######  Definition 4.

An avw$\mathsf{BRBC}$ protocol is a generalized w$\mathsf{BRBC}$ protocol with
a validity predicate $Q()\rightarrow\\{0,1\\}$ for validating input. It also
provides each node a local $abandon()$ interface. An avw$\mathsf{BRBC}$
satisfying the following properties except with negligible probability:

  * •

Agreement and totality. Same to w$\mathsf{BRBC}$.

  * •

Validity. If no honest node invokes $abandon()$, then an honest sender’s input
would eventually be output by all honest nodes.

  * •

External Validity. An honest node outputs $v$ s.t. $Q(v)=1$.

  * •

Abandonability. If a sender inputs a value $v$ to avw$\mathsf{BRBC}$ and
remains so-far honest upon the moment when $n-2f$ forever honest nodes have
invoked their $abandon()$ interface, then for any (strongly) adaptive
adversary $\mathcal{A}$, it cannot make any honest node to output a value
$v^{\prime}\neq v$.

Protocol of avw$\mathsf{BRBC}$ with sender $\mathcal{P}_{s}$ (for each
$\mathcal{P}_{i}$) Input: a value $v_{i}$ s.t. $Q(v_{i})=1$ Initialization:
$ban\leftarrow\textbf{false}$, $val\leftarrow\perp$ 1:if
$\mathcal{P}_{i}=\mathcal{P}_{s}$ then 2: multicast $\mathsf{VAL}(v_{i})$
3:upon receiving $\mathsf{VAL}(v_{s})$ from $P_{s}$ do 4: wait until $Q(v)$
holds or $ban$ = true 5: if $ban$ = false then 6: $val\leftarrow v_{s}$ 7:
multicate $\mathsf{ECHO}(\mathcal{H}(v_{s}))$ 8:upon receiving $n$-$f$
matching $\mathsf{ECHO}(h)$ from distinct nodes do 9: multicast
$\mathsf{READY}(h)$ 10:upon receiving $f+1$ matching $\mathsf{READY}(h)$ from
distinct nodes and hasn’t sent $\mathsf{READY}$ message do 11: multicast
$\mathsf{READY}(h)$ 12:upon receiving $n$-$f$ matching $\mathsf{READY}(h)$
from distinct nodes do 13: $wr\text{-}deliver(h)$ 14:upon
$wr\text{-}deliver(h)$ do 15: wait until $\mathcal{H}(val)=h$ 16:
$r\text{-}deliver(val)$ 17:upon the local interface $abandon()$ is invoked do
18: $ban$ = true Figure 8: Our avw$\mathsf{BRBC}$ protocol. Code is for each
$\mathcal{P}_{i}$.

As shown in Figure 8, we construct avw$\mathsf{BRBC}$ by modifying the
w$\mathsf{BRBC}$ variant of Bracha’s $\mathsf{BRBC}$. External validity is
trivial to realize by applying validation check after each node receives the
broadcasted value as in many studies [19, 20]. However, abandonability has to
be carefully tailored, since we need preserve all other properties of
w$\mathsf{BRBC}$ such as weak totality, which means if some honest node
already outputs, any honest shall still output even if it has invoked
$abandon()$. We identify a unique place in Bracha’s $\mathsf{BRBC}$ to take
$abandon()$ into effect with preserving totality, that is to stop sending echo
messages after invoking $abandon()$ (lines 4-5 in Figure 8).

FIN-$\mathsf{MVBA}$-Q protocol. Given avw$\mathsf{BRBC}$, we now are ready to
construct FIN-$\mathsf{MVBA}$-Q—an adaptively secure $\mathsf{MVBA}$ protocol
with 1/2 quality. Its formal description is in Figure 9. Slightly informally,
it executes in next three phases:

  1. (1)

Broadcast of input (lines 1-6). When receiving the input $v_{i}$,
$\mathcal{P}_{i}$ activates avw$\mathsf{BRBC}_{i}$ to broadcast $v_{i}$. If
avw$\mathsf{BRBC}_{j}$ $wr\text{-}deliver$ $h_{j}$, $\mathcal{P}_{i}$
multicasts a message $\mathsf{FIN}(j,v_{j})$ and records $h_{j}$ in $H_{i}$
(lines 2-4). Once avw$\mathsf{BRBC}_{j}$ $r\text{-}deliver$ $v_{j}$,
$\mathcal{P}_{i}$ records $v_{j}$ in $V_{i}$ (lines 5-6).

  2. (2)

Finish all broadcasts with abandon (lines 7-10). Then, $\mathcal{P}_{i}$ waits
for $n-f$ $\mathsf{FIN}(j,h)$ messages from distinct nodes carrying the same
$h$, $\mathcal{P}_{i}$ then records avw$\mathsf{BRBC}_{j}$ as finished (i.e.,
set $F_{i}\big{[}j\big{]}$ true in line 8) and accepts $v_{j}$ as
avw$\mathsf{BRBC}_{j}$ output (also in line 8). Upon $n-f$ avw$\mathsf{BRBC}$
instances are labeled as finished, $\mathcal{P}_{i}$ would invoke the
$abandon()$ interface of all avw$\mathsf{BRBC}$ instances (line 10).

  3. (3)

Repeating vote until decide an output (lines 11-27). Once $\mathcal{P}_{i}$
abandons in all broadcasts, it loops a voting phase consisting of three steps:
(i) in line 12, invoke coin flipping to randomly $election$ a node
$\mathcal{P}_{k}$; (ii) in line 13-18, invoke $\mathsf{RABA}$ to vote whether
decide $h_{k}$’s pre-image as candidate output or not; (iii) in line 19-28, if
$\mathsf{RABA}$ output 0, $\mathcal{P}_{i}$ will enter the next iteration,
otherwise, $\mathcal{P}_{i}$ will wait for the corresponding $h_{k}$ and
$v_{k}$ (line 20 and 24) to output and terminate.

Protocol of FIN-$\mathsf{MVBA}$-Q (for each $\mathcal{P}_{i}$) Input: a value
$v_{i}$ s.t. $Q(v_{i})=1$ Initialization: $r\leftarrow 0$,
$H_{i}\leftarrow\left[\perp\right]^{n}$,
$V_{i}\leftarrow\left[\perp\right]^{n}$,
$F_{i}\leftarrow\left[\perp\right]^{n}$ 1:start avw$\mathsf{BRBC}_{i}$ with
input $v_{i}$ 2:if $h_{j}$ is $wr\text{-}delivered$ in avw$\mathsf{BRBC}_{j}$
then 3: $H_{i}\big{[}j\big{]}$ $\leftarrow$ $h_{j}$ 4: multicast
$\mathsf{FIN}(j,h_{j})$ 5:if $v_{j}$ is $r\text{-}delivered$ in
avw$\mathsf{BRBC}_{j}$ then 6: $V_{i}\big{[}j\big{]}$ $\leftarrow$ $v_{j}$
7:upon receiving $n$-$f$ same $\mathsf{FIN}(j,h_{j})$ from distinct nodes do
8: $F_{i}\big{[}j\big{]}$ $\leftarrow$ true; $H_{i}\big{[}j\big{]}$
$\leftarrow$ $h_{j}$ 9:wait until $n-f$ values in $F_{i}$ are true 10:
avw$\mathsf{BRBC}_{j}$.$abandon()$ for every $j\in[n]$ 11: repeat //
repeatedly attempt to output a finished broadcast  12:
$k\leftarrow\mathsf{Election}(r)$ // coin flipping to randomly select a node
13: if $H_{i}\big{[}k\big{]}\neq\perp$ then 14: $raba$-$propose$ 1 for
$\mathsf{RABA}_{r}$ 15: else 16: $raba$-$propose$ 0 for $\mathsf{RABA}_{r}$
17: if later $H_{i}\big{[}k\big{]}\neq\perp$ then 18: $raba$-$repropose$ 1 for
$\mathsf{RABA}_{r}$ 19: if $\mathsf{RABA}_{r}$ output $1$ then 20: wait until
$H_{i}\big{[}k\big{]}\neq\perp$ 21: if $V_{i}\big{[}k\big{]}\neq\perp$ then
22: multicast $\mathsf{Value}(V_{i}\big{[}k\big{]})$ 23: else 24: wait
$\mathsf{Value}(v)$ such that $\mathcal{H}(v)=H_{i}\big{[}k\big{]}$ 25:
$mvba\text{-}decide(V_{i}\big{[}k\big{]}$) and $halt$ 26: $r\leftarrow r+1$
27: until $halt$ Figure 9: Our FIN-$\mathsf{MVBA}$-Q protocol. Code is for
each $\mathcal{P}_{i}$.

The above design ensures all broadcasts are “abandoned” while the adversary
learns coin flipping, thus preventing an adaptive rushing adversary to
manipulate $\mathsf{MVBA}$ output. More formally, the security of
FIN-$\mathsf{MVBA}$-Q can be summarized as:

######  Theorem 2.

FIN-$\mathsf{MVBA}$-Q securely realizes $\mathsf{MVBA}$ with $1/2$ quality
except with negligible probability.

Security analysis. Security of FIN-$\mathsf{MVBA}$-Q is also intuitive:

  * •

For agreement, this is because avw$\mathsf{BRBC}$, $\mathsf{RABA}$ and leader
election are all agreed. So any two nodes’ output must be same (as it must be
a value that is broadcasted by the same avw$\mathsf{BRBC}$).

  * •

For termination, the key lemma is: at the moment when the $(f+1)$-th honest
node invokes the leader election (and also abandons all avw$\mathsf{BRBC}$s),
there must be at least $2f+1$ distinct nodes’ avw$\mathsf{BRBC}$s have
delivered to at least $f+1$ honest nodes. Recalling that for these $2f+1$
avw$\mathsf{BRBC}$s, their corresponding $\mathsf{RABA}$s must return 1 (if
were executed), so for in each iteration, there is at least $2/3$ probability
to draw an avw$\mathsf{BRBC}$ whose corresponding $\mathsf{RABA}$ return 1.
Hence after $k$ iterations, the chance of not terminating becomes a negligible
probability $(1/3)^{k}$, which also implies the expected constant round
complexity.

  * •

For quality, we can make a corollary of termination proof: for each iteration,
there is at least $1/3$ probability to decide an honest avw$\mathsf{BRBC}$ as
output, at most $1/3$ probability to draw an malicious node’s
avw$\mathsf{BRBC}$ as output, and at most $1/3$ probability to elect some
unfinished avw$\mathsf{BRBC}$ and thus enter the next iteration. So the lower
bound of quality is $\sum_{r=0}(1/3)(1/3)^{r}=1/2$.

  * •

For external validity, this is true because: (i) the external validity of
avw$\mathsf{BRBC}$ prevents the honest nodes from receiving invalid input (or
digest of invalid input); (ii) if an avw$\mathsf{BRBC}$ does not deliver
output to any honest node, its corresponding $\mathsf{RABA}$ wouldn’t return 1
as no honest node proposes 1, so it is never decided as output.

We defer the full proof to Appendix C in Supplementary.

Complexity analysis. FIN-$\mathsf{MVBA}$-Q has expected constant round
complexity and $\mathcal{O}(n^{3})$ message complexity. Its communication cost
is $\mathcal{O}(|m|n^{2}+\lambda n^{3})$ where $|m|$ represents
$\mathsf{MVBA}$’s input length and $\lambda$ represents the length of hash
digest in avw$\mathsf{BRBC}$. Remark that the communication cost of
FIN-$\mathsf{MVBA}$-Q is as same as FIN-$\mathsf{MVBA}$ [20]. Though such
$\mathcal{O}(|m|n^{2}+\lambda n^{3})$ communication cost is best so far in the
signature-free setting, it is more costly than the state-of-the-art signature-
involved $\mathsf{MVBA}$ protocol [17] that attains expected
$\mathcal{O}(|m|n+\lambda n^{2})$ communication cost.

###  IV-C Whether is $\mathsf{FIN}\textrm{-}\mathsf{NG}$ sufficiently scalable
or NOT?

Careful readers might realize that the design of
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ can be thought of as a signature-free
version of $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$, involving a particular
trade-off to reduce authenticator complexity at a price of other overheads
like cubic message complexity. Observing that, a natural question might raise:
is such stringent signature-free approach the best practice in real-world
global deployment setting with affordable bandwidth (like 100 Mbps or less)
and several hundreds of nodes?

To better understand this natural question, we test two state-of-the-art
$\mathsf{MVBA}$ protocols— FIN-$\mathsf{MVBA}$ (signature-free but cubic
messages) and $\mathsf{Dumbo}$-$\mathsf{MVBA}$ [17] (involving signatures but
only quadratic messages) to estimate the tendency of their latency degradation
in bandwidth-limited settings with $n$=196 nodes. For fair comparison, we take
a vector of $n$ integers as input to FIN-$\mathsf{MVBA}$, and use $n$ QCs
(which is much larger) as input to $\mathsf{Dumbo}$-$\mathsf{MVBA}$. As Figure
10 illustrates, our experimental comparison between FIN-$\mathsf{MVBA}$ and
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ reveals: (i) FIN-$\mathsf{MVBA}$ and
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ have comparable latency only if each node has
more than 100 Mbps bandwidth; (ii) when available bandwidth is less than 50
Mbps, FIN-$\mathsf{MVBA}$’s latency would be dramatically increased.

In short, this evaluation affirms our conjecture that the stringent signature-
free approach of $\mathsf{FIN}\textrm{-}\mathsf{NG}$ might be not the best
practice in the deployment environment with restricted bandwidth, motivating
us further explore even more scalable asynchronous BFT protocols in the
signature-involved setting.

Figure 10: Latency of signature-free $\mathsf{MVBA}$ (i.e.
FIN-$\mathsf{MVBA}$-Q) and signature-involved $\mathsf{MVBA}$ (i.e.
$\mathsf{Dumbo}$-$\mathsf{MVBA}$) for $n=196$ nodes.

##  V Optimize Quorum Certificate to Best Practice

As our initial attempt $\mathsf{FIN}\textrm{-}\mathsf{NG}$ might not scale
very well in the important setting of restricted bandwidth, we continue our
concentration on how to scale up asynchronous BFT consensus using signatures.
To begin with, this section focuses on optimizing QC implementations, as its
prevalent usage has led up to a primary scalability bottleneck in existing
designs.

Batch verification with blocklist: the right way of implementing QCs. We take
consistent broadcast (CBC) [64] as the simplistic context to estimate the CPU
cost of different QC implementations from different signatures.

As Figure 11 (a) plots, CBC has a designated sender that waits for $n-f$ valid
signatures from distinct nodes, such that it can aggregate/concatenate these
$n-f$ valid signatures to form a QC and spread it out. We denote this approach
“individual verification” since the aggregation occurs after validating all
$n-f$ individual signatures. Figure 11 (b) presents a folklore alternative
[46, 65] that directly aggregates (unverified) signatures and then performs
batch verification. Intuitively, the “batch verification” approach is
promising to take the best advantage of aggregate signature, because it avoids
verifying individual signatures in normal case.

We then conduct a comprehensive benchmarking of QCs built from “individual
verification” and “batch verification”, with different types of signatures
(including ECDSA, Schnorr signature, BLS signature, and BLS threshold
signature). Note that ECDSA signature cannot be non-interactively aggregated,
and QC from it simply concatenates $n-f$ valid signatures. Schnorr signature
can be non-interactively half-aggregated [42, 41], so QC from it has a smaller
size that is about half of $n-f$ concatenated signatures, and more
importantly, its batch verification can be faster than trivially verifying
$n-f$ concatenated Schnorr signatures.121212Similar to Schnorr signature,
EdDSA can be half-aggregated and might have very tiny speed-up due to Edward
curve. However, their performances are essentially comparable. Thus we didn’t
do redundant tests of EdDSA. BLS signature can be fully aggregated. In order
to push efficiency, we use a straight way of computing BLS multi-signature by
taking summation of all received signatures (under the standard KOSK model),
so aggregation is much faster than the threshold version of BLS, as the latter
one’s aggregation needs costly interpolation in the exponent [66]. Our
evaluations consider similar security levels for different signatures. ECDSA
and Schnorr are implemented over secp256k1 curve with about 128-bit security
[67]. For BLS signature, we work on a notable and widely-adopted pairing-
friendly elliptic curve BLS12-381 [68, 69], which was designed for 128-bit
security and now is still considered with 117-120 bit security despite recent
cryptanalysis [70].

Figure 11: QC generation in CBC: (a) verify individual signatures then
aggregate; (b) aggregate then verify a batch.

_BLS multi-signature with batch verification would outperform_. The detailed
evaluation of CPU latency in a CBC protocol is plotted in Figure 12.
Evidently, QC implementation from BLS multi-signature with using batch
verification ( the violet line and  the gray line) vastly outperforms all
other instantiations in terms of computation cost. Note the minor difference
between the violet and gray lines reflects the choice of implementing
signatures in $\mathbb{G}_{1}$ or $\mathbb{G}_{2}$ groups over BLS12-381
curve.

_Maintain blocklist to prevent performance degradation attack_. However, the
approach of batch verification might face serous performance downgrade under
attacks, particularly when malicious nodes send false signatures. This issue
can be addressed by maintaining a blocklist containing the identities of those
malicious nodes. As Figure 11 (b) shows, when the aggregated multi-signature
fails in batch verification, one verifies all individual signatures and add
the malicious nodes sending fake signatures to a blocklist. Later, the
blocklist can be used to exclude the faulty nodes from aggregation.

Figure 12: CPU latency (related to digital signatures) in the critical path of
one-shot CBC on varying system scales.

Further aggregation of multiple QCs: efficiently transfer a vector of QCs on
different messages. While implementing QC from BLS multi-signature, one more
benefit largely overlooked by the distributed computing community is that many
such QCs on different messages can be further aggregated. This bonus property
becomes particularly intriguing in asynchronous BFT protocols like
$\mathsf{Tusk}$ and $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ because their
scalability bottleneck stems from multicasting $\mathcal{O}(n)$ QCs. As
illustrated in Fig 13, while multicasting $n$ QCs made from BLS multi-
signature, we can leverage the aggregation property to combine all signature
parts in these QCs and reduce their size to less than half of the original
(cf. Fig 13).

Figure 13: Aggregating many QCs made from BLS multi-sig.

More tips on efficient QC implementation. Besides various aggregation
techniques, we remark a few other tips of implementing QCs from BLS signatures
in real-world BFT systems:

  * •

_BLS signature in $\mathbb{G}_{1}$ group is more favorable than
$\mathbb{G}_{2}$_. BLS12-381 curve is equipped with asymmetric paring
$e:\mathbb{G}_{1}\times\mathbb{G}_{2}\rightarrow\mathbb{G}_{T}$. When
implementing BLS signature over the curve, one can let signature in
$\mathbb{G}_{1}$ and public key in $\mathbb{G}_{2}$, or vice versa. We
recommend signature in $\mathbb{G}_{1}$, because (i) $\mathbb{G}_{1}$ group
element has shorter size, and (ii) there is saving in CPU time for $n\leq 256$
(Figure 12).

  * •

_Encode public keys relating a multi-signature by $n$ bits_. Moreover, in most
realistic proof-of-stake and consortium blockchains, participating nodes’
public keys can be mutually known to each other. So the identities of signing
nodes in a multi-signature can be encoded by $n$ bits instead of transferring
their public keys. Here each bit represents whether a node has signed (1) or
not (0).

##  VI $\mathsf{JUMBO}$: Making signature-involved asynchronous BFT Truely
Scalable

Given concrete optimizations of QCs, it is worth noting that $\mathsf{Tusk}$
and $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ still suffer from cubic
authenticator overhead per decision, because they still let each node to
multicast a vector of $\mathcal{O}(n)$ QCs. Even if using our technique in
Section V, this cost is still a cubic in total, becuase the aggregate
$\mathcal{O}(n)$ BLS-based QCs carry $\lambda n+n^{2}$ bits and need
$\mathcal{O}(n)$ cryptographic pairings to verify. Facing still asymptotically
large authenticator overhead, this section distills a scalable instantiation
of $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$—$\mathsf{JUMBO}$, to asymptotically
reduce the authenticator complexity by introducing information dispersal.
$\mathsf{JUMBO}$ can reduce the number of multicasting $n$ QCs from
$\mathcal{O}(n)$ to $\mathcal{O}(1)$, and in combination with our optimized QC
implementation, it can seamlessly scale up with hundreds of nodes in
bandwidth-starved settings.

Revisiting the core technique of provable dispersal. Before diving into the
details of our scalable construction, we first briefly recall our key
technical component—asynchronous provable dispersal broadcast
($\mathsf{APDB}$) [17, 18]. Informally, $\mathsf{APDB}$ allows a designed
sender to disperse a large input like $n$ QCs to the whole network at an
overall communication cost of merely $O(1)$ QCs. Namely, the communication
cost of dispersing $n$ QCs can be $O(1/n)$ of multicasting them. Moreover, the
sender can generate a proof at the end of dispersal, such that a valid proof
attests that the dispersed $n$ QCs can later be consistently recovered by the
whole network.

More precisely, $\mathsf{APDB}$ can be formally defined as:

######  Definition 5.

Syntactically, an $\mathsf{APDB}$ consists of two subprotocols ($\mathsf{PD}$,
$\mathsf{RC}$) with a validating function $\mathsf{ValidateLock}$:

  * •

$\mathsf{PD}$ subprotocol. In the $\mathsf{PD}$ subprotocol among $n$ parties,
a designated sender $\mathcal{P}_{s}$ inputs a value $v\in\\{0,1\\}^{\ell}$,
and aims to split $v$ into $n$ code fragments and disperses each $j$-th
fragment to the corresponding node $\mathcal{P}_{j}$. If a party terminates in
$\mathsf{PD}$, it shall output a string ${store}$, and if the node is sender,
it shall additionally output a ${lock}$ string.

  * •

$\mathsf{RC}$ subprotocol. In the $\mathsf{RC}$ subprotocol among $n$ parties,
all honest nodes take ${store}$ and ${lock}$ strings outputted by
$\mathsf{PD}$ subprotocol as input, and aim to output a value
$v^{\prime}\in\\{0,1\\}^{\ell}\cup\bot$.

  * •

$\mathsf{ValidateLock}$ function. It takes a ${lock}$ string as input and
returns 0 (reject) or 1 (accept).

An $\mathsf{APDB}$ protocol ($\mathsf{PD}$, $\mathsf{RC}$) shall satisfy the
following properties except with negligible probability:

  * •

Termination. If the sender $\mathcal{P}_{s}$ is honest and all honest nodes
activate the $\mathsf{PD}$ protocol, then each honest node would output
${store}$ in $\mathsf{PD}$; additionally, $\mathcal{P}_{s}$ also outputs valid
${lock}$ in $\mathsf{PD}$ s.t. $\mathsf{ValidateLock}(lock)$=$1$.

  * •

Recast-ability. If all honest parties invoke $\mathsf{RC}$ with inputting the
output of $\mathsf{PD}$ and at least one honest party inputs a valid ${lock}$
s.t. $\mathsf{ValidateLock}(lock)$=$1$, then: (i) all honest parties can
eventually recover a common value $v^{\prime}\in\\{0,1\\}^{\ell}\cup\bot$;
(ii) if the sender is honest and disperses $v$ in $\mathsf{PD}$, then all
honest parties can recover $v$ in $\mathsf{RC}$.

An $\mathsf{APDB}$ protocol satisfying the above definition can be efficiently
implemented as in Figures 15 and 16, through simplifying the design from [17].
$\mathsf{PD}$ subprotocol has a very simple two-round structure: sender
$\xrightarrow[]{\scriptscriptstyle\textsc{Store}}$ parties
$\xrightarrow[]{\scriptscriptstyle\textsc{Stored}}$ sender. In this way, the
communication cost of using $\mathsf{PD}$ to disperse $n$ broadcast QCs can be
brought down to minimum, which asymptotically is only $O(1/n)$ of multicasting
$n$ QCs.

Figure 14: Dispersal-then-recast paradigm of $\mathsf{Dumbo}$-$\mathsf{MVBA}$
[17]. Protocol of Provable Dispersal ($\mathsf{PD}$) with sender
$\mathcal{P}_{s}$ Initialization: $S\leftarrow\\{\ \\}$ 1:/* Protocol for the
sender $\mathcal{P}_{s}$ */  2:upon receiving an input value $v$ do 3: encode
$v$ by erasure code to get the code word $\bf{m}$ of $n$ fragments  4: use $n$
fragments of $\bf{m}$ as leaves to compute Merkle tree root $mt$ 5: for each
$j\in[n]$ do 6: let ${store}:=\langle mr,m_{j},\pi_{j}\rangle$ where $\pi_{j}$
is the Merkle tree path proving that $m_{j}$ is the $j$-th leaf committed to
$mr$ 7: send $(\textsc{Store},\mathsf{ID},{store})$ to $\mathcal{P}_{j}$ 8:
wait until $|S|=2f+1$ // Aggregate threshold signature  9: $\Sigma\leftarrow$
$\mathsf{Agg}(S)$ and let ${lock}:=\langle mr,\Sigma\rangle$ 10: output
${lock}$ and terminate  11:upon receiving valid
$(\textsc{Stored},\mathsf{ID},\sigma_{j})$ from $\mathcal{P}_{j}$ do 12:
$S\leftarrow S\cup(j,\sigma_{j})$ // For a neat description, here is not batch
verification, but we can implement batch verification in practice.  13:/*
Protocol for each party $\mathcal{P}_{i}$ */  14:upon receiving
$(\textsc{Store},\mathsf{ID},{store})$ from sender $\mathcal{P}_{s}$ do 15: if
${store}=\langle mr,m_{i},\pi_{i}\rangle$ carries a valid $\pi_{i}$ proving
that $m_{i}$ is the $i$-th leaf committed to Merkle tree root $mr$ then 16:
$\sigma_{i}\leftarrow\mathsf{Sign}(sk_{i},\langle\mathsf{ID},mr\rangle)$; send
$(\textsc{Stored},\mathsf{ID},\sigma_{i})$ to $\mathcal{P}_{s}$ 17: output
${store}$ and terminate if $\mathcal{P}_{i}\neq\mathcal{P}_{s}$ Figure 15:
Provable dispersal protocol adapted from [17]. Code is for each
$\mathcal{P}_{i}$. Protocol of Reconstruction ($\mathsf{RC}$) (for each
$\mathcal{P}_{i}$) Initialization: $C\leftarrow[\ ]$ (i.e, a dictionary keyed
by Merkle tree root) 1:upon receiving input $({store},{lock})$ do 2: if
${lock}\neq\emptyset$ then 3: multicast $(\textsc{RcLock},\mathsf{ID},{lock})$
to all  4: if ${store}\neq\emptyset$ then 5: multicast
$(\textsc{RcStore},\mathsf{ID},{store})$ to all  6:upon receiving
$(\textsc{RcLock},\mathsf{ID},{lock})$ do 7: if
$\mathsf{ValidateLock}(\mathsf{ID},{lock})=1$ then 8: multicast
$(\textsc{RcLock},\mathsf{ID},{lock})$ to all, if was not sent before  9:
parse ${lock}$ as $\langle mr,\Sigma\rangle$ 10: wait until $|C[mr]|=f+1$ 11:
decode $C[mr]$ by erasure code to obtain $v$ 12: encode $v$ by erasure code to
get code word $\bf{m}$ 13: use $\bf{m}$ as leaves to compute Merkle tree root
$mr^{\prime}$ 14: if $mr=mr^{\prime}$ then return $v$ 15: else return $\bot$
16:upon receiving $(\textsc{RcStore},\mathsf{ID},{store})$ from
$\mathcal{P}_{j}$ do 17: if ${store}=\langle mt,m_{j},\pi_{j}\rangle$ carries
a valid $\pi_{j}$ proving that $m_{j}$ is the $j$-th leaf committed to Merkle
tree root $mr$ then 18: $C[mr]\leftarrow C[mr]\cup(j,m_{j})$ 19:/* Public
$\mathsf{ValidateLock}$ function */ function
$\mathsf{ValidateLock}$$({lock})$:  20: parse ${lock}$ as $\langle
mr,\Sigma\rangle$ 21: verify $\Sigma$ is a valid $(2f+1)$ threshold signature
on $\langle\mathsf{ID},mr\rangle$ 22: return 1 (accept) if verification
passes, otherwise return 0 (reject)  Figure 16: Provable dispersal protocol
adapted from [17]. Code is for each $\mathcal{P}_{i}$.

Inspiration of $\mathsf{JUMBO}$: $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ is
friendly for reducing the authenticator overhead by using $\mathsf{APDB}$! It
comes to our attention that $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ has a very
unique place leading up to its cubic authenticator complexity. That is every
node using a vector of $\mathcal{O}(n)$ QCs as $\mathsf{MVBA}$ input. The neat
structure of $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ hints at introducing
$\mathsf{APDB}$ to extend its $\mathsf{MVBA}$ component, thus asymptotically
reducing overall communication cost for large inputs like $n$ QCs.

The communication-efficient $\mathsf{MVBA}$ protocol extended by
$\mathsf{APDB}$ also has a nickname $\mathsf{Dumbo}$-$\mathsf{MVBA}$ [17]. As
shown in Figure 14, it proceeds as: every node avoids directly multicasting
its large input, but employs the more efficient provable dispersal protocol to
spread much shorter encode fragments instead; then, if some node finishes its
dispersal, it can generate a dispersal QC attesting its successful spread of
$n$ broadcast QCs; every honest node can finish its own dispersal and thus
uses its dispersal QC (which is a single QC instead of $n$ QCs) to invoke the
original $\mathsf{MVBA}$ protocol; finally, all nodes repeat $\mathsf{MVBA}$
protocols, until some $\mathsf{MVBA}$ picks a dispersal QC that allows them
collectively recover a vector of $n$ valid broadcast QCs as their
$\mathsf{MVBA}$ result.

Clearly, after applying the dispersal technique as above, we can reduce the
cubic authenticator bottleneck in $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ to
only quadratic. This is because: (i) $n$ dispersals of $\mathcal{O}(n)$ QCs
have a communication cost similar to a single multicast of $\mathcal{O}(n)$
QCs; (ii) we only have to reconstruct a small constant number of dispersals,
which is also asymptotically same to the communication cost of a single
multicast of $\mathcal{O}(n)$ QCs.

###  VI-A $\mathsf{JUMBO}$ Protocol

As depicted by Figure 17, $\mathsf{JUMBO}$ inherits
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ to have a couple of concurrent
processes—transaction broadcast and block agreement—with using provable
dispersal to resolve the authenticator bottleneck. For completeness of
presentation, we hereunder briefly describe the two processes of
$\mathsf{JUMBO}$, and then introduce its easy-to-implement fairness patch.

Transaction broadcast process. Each node $\mathcal{P}_{i}$ starts $n$
broadcast threads. Each broadcast proceeds in slot $s\in\\{1,2,3\cdots\\}$.
$\mathcal{P}_{i}$ is designated as sender only in the $i$-th broadcast. Each
broadcast proceeds by an increasing-only slot number $s$. Once the sender
$\mathcal{P}_{i}$ enters a slot $s$, it selects a batch of $|B|$ transactions
(denoted $tx_{s}$) from its input buffer, multicasts $tx_{s}$ with the current
slot index $s$ and a quorum certificate $QC_{s-1}$ attesting that a
transaction batch $tx_{s-1}$ was broadcasted in the preceding slot $s-1$, then
it waits for that $n-f$ distinct nodes return valid signatures on
$i||s||\mathcal{H}(tx_{s})$ (where $\mathcal{H}$ is a cryptographic hash
function), and assembles these signatures to form a quorum certificate
$QC_{s}$ and then steps into the next slot $s+1$. On the other side, when any
node $\mathcal{P}_{j}$ (probably non-leader) enters a slot $s$, it waits for
receiving the message carrying $tx_{s}$ and $QC_{s-1}$ from the sender node
$\mathcal{P}_{i}$, checks $QC_{s-1}$ a valid QC and consistent to $tx_{s-1}$
that it received, returns a signature on $i||s||\mathcal{H}(tx_{s})$ to the
sender, and proceeds to the next slot $s+1$.

Note that we refrain from reintroducing the pull mechanism that executes in
companion with broadcast process to help the fetch of missing transactions,
because we have described two instantiations of it in Section IV for
$\mathsf{FIN}\textrm{-}\mathsf{NG}$.

Block agreement process. Concurrent to transaction broadcast, every node
starts an agreement process that executes a sequence of $\mathsf{MVBA}$
protocols in consecutive epochs $e\in\\{1,2,3,\cdots\\}$. Note that all
$\mathsf{MVBA}$s are $\mathsf{Dumbo}$-$\mathsf{MVBA}$ protocols that are
extended by using $\mathsf{APDB}$. To prepare the input of the current epoch’s
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ protocol, each $\mathcal{P}_{i}$ locally
maintains a vector of $[0pt_{1},\cdots,0pt_{n}]$, where each $0pt_{j}$ carries
sender $\mathcal{P}_{j}$’s latest broadcast QC that is indeed received by
$\mathcal{P}_{i}$. Meanwhile, $\mathcal{P}_{i}$ maintains another vector of
$[\mathsf{ordered}_{1},\cdots,\mathsf{ordered}_{n}]$ to track the
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ output of last epoch, where each
$\mathsf{ordered}_{j}$ represents sender $\mathcal{P}_{j}$’s highest broadcast
QC that was already solicited into consensus output. In each epoch, every
$\mathcal{P}_{i}$ waits for that at least $n-f$ QCs in
$[0pt_{1},\cdots,0pt_{n}]$ contain slot numbers higher than their
corresponding items in $[\mathsf{ordered}_{1},\cdots,\mathsf{ordered}_{n}]$,
i.e., $n-f$ broadcasts have indeed progressed since the decision of last
block. Then, $\mathcal{P}_{i}$ takes a snapshot of $[0pt_{1},\cdots,0pt_{n}]$
as input to the current $\mathsf{Dumbo}$-$\mathsf{MVBA}$ protocol. To enforce
the input validity, $\mathsf{Dumbo}$-$\mathsf{MVBA}$’s validity predicate is
set as:

  1. 1.

the input proposal indeed carries $n$ valid QCs associated with $n$ different
broadcasts, if passing the check, go to next clause, otherwise, return false
(0);

  2. 2.

at least $n-f$ QCs have slot numbers that indeed increase in relative to the
last $\mathsf{Dumbo}$-$\mathsf{MVBA}$ output, if passing the check, go to next
clause, otherwise, return false (0);

  3. 3.

other non-increasing QCs shall not carry slot numbers smaller than the last
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ output, if the check passes, return true (1),
otherwise, return false (0);

After invoking the current epoch’s $\mathsf{Dumbo}$-$\mathsf{MVBA}$,
$\mathcal{P}_{i}$ waits for its output, which are $n$ valid broadcast QCs.
According to the $\mathsf{Dumbo}$-$\mathsf{MVBA}$ result, all honest nodes can
decide a common new block that solicits the transactions due to the difference
between the current $\mathsf{Dumbo}$-$\mathsf{MVBA}$ output and the previous
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ output. Finally, every node’s agreement
process updates $[\mathsf{ordered}_{1},\cdots,\mathsf{ordered}_{n}]$ by the
newest $\mathsf{Dumbo}$-$\mathsf{MVBA}$ output and goes to the next epoch.

Enhance fairness by an easy-to-implement patch. Although $\mathsf{JUMBO}$
could scale up after applying $\mathsf{Dumbo}$-$\mathsf{MVBA}$ extension
protocol to asymptotically reduce authenticator overhead, it lacks fairness in
some extremely adversarial cases, because its transaction dissemination
process allows each node $\mathcal{P}_{i}$ to continually participate in all
broadcast threads, thus leaving the adversary a chance to diffuse tremendous
transactions ridiculously fast through the malicious nodes’ broadcast
instances. Nevertheless, the desired fairness could be easily patched by
applying “speed limit” in broadcasts. The high-level idea is very intuitive:
let the honest nodes temporarily halt voting in these broadcasts that are
running too fast in relative to other slower broadcasts, until the slower
broadcast threads catch up.

To implement the “speed limit” idea, a node $\mathcal{P}_{i}$ maintains a
variable $\delta_{j}$ for each broadcast thread. The variable $\delta_{j}$
tracks that the $j$-th broadcast thread has disseminated how many transactions
since the height included by last block (from the local view of node
$\mathcal{P}_{i}$), i.e., $\delta_{j}=0pt_{j}.slot-\mathsf{ordered}_{j}.slot$,
where $0pt_{j}$ tracks the slot number of $\mathcal{P}_{j}$’s latest broadcast
received by $\mathcal{P}_{i}$ with a valid QC, and $\mathsf{ordered}_{j}$
tracks last broadcast slot of $\mathsf{ordered}_{j}$ that has already been
decided as output due to last $\mathsf{MVBA}$ result. Let $\delta$ to be the
$(f+1)$-th smallest one of all $\\{\delta_{j}\\}_{j\in[n]}$; if there is any
$\delta_{j}$ such that $\beta\cdot\delta_{j}\geq\delta$ and $\delta_{j}>0$,
$\mathcal{P}_{i}$ halts voting in the $j$-th broadcast instance until
$\beta\cdot\delta_{j}<\delta$, where $0<\beta<1$ is a fairness parameter (more
“fair” if closer to 1, because of enforcing the fastest $2f+1$ broadcasts to
progress at more similar speeds).

To enforce the above “speed limit”, we also need to add a corresponding
validity rule to the $\mathsf{MVBA}$’s predicate function: per each node
$\mathcal{P}_{i}$’s proposal, the most progressed broadcast since last block
and the $(f+1)$-th least progressed broadcast since last block shall have a
progress ratio bounded by $1/\beta$.

Figure 17: $\mathsf{JUMBO}$ and how does it overcomes authenticator
bottleneck.

###  VI-B Analysis of $\mathsf{JUMBO}$

$\mathsf{JUMBO}$ securely realizes the notion of asynchronous BFT consensus
(atomic broadcast) with fairness. More formally,

######  Theorem 3.

$\mathsf{JUMBO}$ implements asynchronous BFT atomic broadcast with fairness
except with negligible probability.

Security analysis. The security proof of $\mathsf{JUMBO}$ largely coincides
with that of $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ [18], except that (i) the
proof of liveness has to be adapted to consider possible “stuck” caused by
hanging of votes and (ii) fairness requires new analysis. We provide a proof
sketch hereunder and defer the full security proof to Appendix E in
Supplementary.

For proving liveness, we need to consider the pending of votes due to fairness
patch. The roadmap of proofs is as:

  * •

All honest nodes can obtain a valid input to the current $\mathsf{MVBA}$
protocol in constant rounds. All honest nodes won’t halt their voting in the
first round of each broadcast, as they always continue on voting if
$\delta_{j}=0$. So every honest node can at least receives one more broadcast
with valid QC from each honest broadcast sender in constant rounds. Given the
fact that there are at least $n-f$ honest broadcast senders, all honest nodes
can prepare a valid $\mathsf{MVBA}$ input in constant rounds.

  * •

An honest node can broadcast transactions with valid QCs to all honest nodes
in constant rounds. When an honest node broadcasts a batch of transactions,
there are two possible cases: (i) one case is that no honest node halts voting
in the broadcast; (ii) the other case is that some nodes temporarily hang on
voting in the broadcast. In the first case, the sender can generate a valid QC
for the broadcasted transactions in constant rounds. In the second case, it on
average takes a constant number of $\mathsf{MVBA}$s to solicit the highest QC
of the hanging broadcast into some block, after which, the honest nodes would
continue to vote in the broadcast, thus allowing the broadcast sender to
generate a new QC on the broadcast transactions.

  * •

Any honest node’s broadcasted transactions would be solicited by some
$\mathsf{MVBA}$ after expected constant rounds. Putting the above two
assertions together, if a transaction is broadcasted by an honest node, it
first takes expected constant rounds to generate a valid QC on the
transaction, then one round is used to send the valid QC to all honest nodes,
and finally, QC of this transaction (or the same sender’s another QC with
higher slot number) would be solicited by some $\mathsf{MVBA}$ output, with an
overwhelming probability of $1-(1-q)^{k}$ after $k$ $\mathsf{MVBA}$
executions. Thus, it takes an expected constant number of rounds to confirm
transactions broadcasted by any honest node.

For safety, the security intuitions are very straightforward and actually
coincides with the original $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ protocol:

  * •

Guarantee consistency of broadcasts via QCs. A valid broadcast QC associating
with slot number $s$ implies: no malicious sender can broadcast different
transactions to distinct honest nodes associating with a slow number $\leq s$;

  * •

Ensure agreement of each block by soliciting same QCs. The agreement and
external validity of $\mathsf{MVBA}$ further ensures: all honest nodes must
solicit broadcasts with the same slot numbers and valid QCs into each block.
Thus, in combination of broadcasts’ consistency, any two honest nodes’ output
blocks must include same transactions.

For fairness, it can be intuitively seen from “speed limit” placed on fastest
broadcasts. More detailedly, rationales are:

  * •

Bound the number of honest broadcasts solicited in each block. Each block
solicits broadcasts from at least $n$-$f$ distinct senders, out of which at
least $f$+$1$ are honest.

  * •

Bound the difference in progress between malicious and honest broadcasts. Due
to our fairness patch, if malicious broadcasts solicited by a block contribute
$X$ transactions, then honest broadcasts solicited by the block contribute
$\beta\cdot X$ transactions. Thus, in each output block including $K$
transactions, there are at least $K\cdot\beta/(1+\beta)$ transactions proposed
by honest nodes. This gives a fairness lower bound $\alpha=\beta/(1+\beta)$.
Considering $\beta$ can be a parameter close to 1, the fairness $\alpha$ can
arbitrarily approach 1/2.

Complexity analysis. The round, amortized communication, and message
complexities of $\mathsf{JUMBO}$ are same to these of original
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$. For the fined-grained metric of
authenticator complexity, $\mathsf{JUMBO}$ is $\mathcal{O}(n^{2})$, reducing
another $\mathcal{O}(n)$ order when compared to
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ using aggregate BLS signatures. The
authenticator complexity can be divided into two parts. First, in broadcast
process, only the leader generates QCs and multicasts them to receivers. Thus,
for any transaction $tx$, only $\mathcal{O}(1)$ multicasts of a single QC
involve. Second, in block agreement process, every node leverages provable
dispersal protocol to spread out $n$ QCs, and later, each node reconstructs at
most $\mathcal{O}(n)$ QCs, resulting in an authenticator complexity of
$\mathcal{O}(n^{2})$. Moreover, the underlying $\mathsf{MVBA}$ protocol that
we use is sMVBA from Guo et al. [27], which also has an authenticator
complexity of $\mathcal{O}(n^{2})$. In sum, the authenticator complexity of
$\mathsf{JUMBO}$ is $\mathcal{O}(n^{2})$, which is dominated by the block
agreement process.

##  VII Additional Related Work

Sharding is feasible only with more scalable consensus for each shard. One
might wonder whether sharding [71, 72, 73] can overcome our scalability
challenge. But regretfully, this idea still requires each shard to execute
consensus consisting of sufficiently many nodes to bound error probability.
Considering a shard of $k$ nodes randomly elected from an infinite set with
80% honesty, if we expect each shard’s error chance to be $10^{-6}$ (same
parameter in [72, 73]), the shard shall contain $250$ or more nodes. Namely,
sharding becomes feasible only if we have consensus for hundreds of nodes as
basis, which further motivates us to extend the appealing performance of
state-of-the-art asynchronous BFT into larger scales.

Dual-mode asynchronous BFT inherits scalability issues. Recently, a few dual-
mode asynchronous BFT protocols [74, 75, 76] are proposed, such that they can
perform similar to partially-synchronous protocols in synchrony. However,
their pessimistic paths resemble existing single-mode asynchronous BFT
protocols. For example, [74] almost directly inherits $\mathsf{Tusk}$ and [76]
straightforwardly used $\mathsf{Dumbo}$ as their pessimistic paths. That
means, these dual-mode protocols might still suffer from severe scalability
issues in their pessimistic case.

Executing BFT among an elected sub-committee. It is also seemingly
straightforward to sample a sufficiently small sub-committee [77] to solve the
scalability challenge in asynchronous BFT. However, this approach has the same
problem as the sharding paradigm: when we sample a sub-committee, we either
have to assume the candidates have an exaggerated honest portion or need to
sample sufficient many nodes. For example, some reasonable parameters [72, 73]
could be sampling 250 nodes out of 80% honest candidates.

Scalability solutions to partially synchronous BFT. A few recent studies [78,
79, 30] adopt threshold signature towards scaling up partially synchronous BFT
consensus. In HotStuff [26], the paper theoretically realizes linear
communication complexity by implementing QCs from threshold signatures, but
the authors’ implementation chooses ECDSA as concrete instantiation (which now
can be understood by our analysis in Section V, because implementing QCs via
threshold signature in the sub-optimal individual verification manner is
extremely computationally costly). What’s more, even if one uses the optimized
batch verification approach in lieu of individual verification, threshold BLS
signature still places a heavy aggregation cost in the critical path (making
overall computation latency not better than ECDSA), as a result of
interpolation in exponent. In contrast, the aggregation of BLS multi-signature
simply “adds” all receives signatures. The only extra cost of BLS multi-
signature compared to its threshold counterpart is $n$ bits to encode the
identities of signers while embedding into QCs, which is essentially a small
overhead in realistic BFT systems where $n$ is a number like at most a few
hundreds.

Figure 18: Latency v.s. TPS in the regional setting (100 ms RTT and 1 Gbps
bandwidth) for $n=$ 64, 128, 196 and 256 nodes. Figure 19: Latency v.s. TPS in
the continental setting (200 ms RTT and 500 Mbps bandwidth) for $n=$ 64, 128,
196 and 256 nodes. Figure 20: Latency v.s. TPS in the global setting (400 ms
RTT and 100 Mbps bandwidth) for $n=$ 64, 128, 196 and 256 nodes.

##  VIII Implementations and Evaluations

We implement $\mathsf{FIN}\textrm{-}\mathsf{NG}$ and $\mathsf{JUMBO}$ in
Golang. $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ and FIN are also implemented in
the same language with same libraries and network layer. We then extensively
evaluate them in large testnets of up to 256 nodes.131313The performance of
open-sourced $\mathsf{Tusk}$ implementation [16] would be bounded by the I/O
of EC2 c6a.2xlarge instance’s low-profile disk, which is much slower than
bandwidth. Thus, directly comparing $\mathsf{Tusk}$ with our implementations
could be meaningless. Nevertheless, the original
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ and $\mathsf{Tusk}$ have similar trend
of performance degradation in network scales.

Implementations details. We implement four types of processes: a client, a
txpool, a broadcaster, and an orderer. The client process can generate and
submit transactions at a fixed workload rate. The txpool process receives
transactions and batches them into broadcast input. The broadcaster processes
disseminate the batch of transactions. The orderer process decides how to cut
broadcasted transactions into blocks. Each transaction is 250 byte to
approximate the size of a typical Bitcoin transaction with one input and two
outputs.141414The size choice of transactions essentially has little impact on
evaluations, if we count throughput in the unit of “bytes per second” instead.
One can simply think each transaction as an alternative information unit. We
also set a upper limit of broadcast batch at 4000, so a broadcast might
diffuse 1-4000 transactions depending on system load. To realize reliable
fully-meshed asynchronous point-to-point channels, we implement (persistent)
TCP connection between every two nodes. If a TCP connection is dropped, our
implementation would attempt to re-connect.

Regarding signature, $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ [18] chooses ECDSA
library from Bitcoin [67] on secp256k1 curve, and $\mathsf{JUMBO}$ uses BLS
signature library [69] on BLS12-381 curve. For transaction broadcast,
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ and $\mathsf{JUMBO}$ choose the same QC-
based broadcast, $\mathsf{FIN}\textrm{-}\mathsf{NG}$ variant employs
w$\mathsf{BRBC}$ as described in Section IV, and FIN adopts CT05
$\mathsf{BRBC}$ [59]. Regarding $\mathsf{MVBA}$,
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ directly uses s$\mathsf{MVBA}$ [27],
$\mathsf{JUMBO}$ employs s$\mathsf{MVBA}$ extended by
$\mathsf{Dumbo}$-$\mathsf{MVBA}$ [17] to fit large input, and
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ adopts our quality-enhanced version of
FIN-$\mathsf{MVBA}$—FIN-$\mathsf{MVBA}$-Q.

Evaluation setups on Amazon EC2. We used Amazon’s EC2 c6a.2xlarge instances (8
vCPUs and 16 GB main memory) in one region (Virginia) to create testnets. The
performances of BFT protocols were evaluated with varying scales at $n$$=$64,
128, 196, and 256 nodes, where each node corresponds to an EC2 c6a.2xlarge
instance. To simulate WAN environment reproducibly and affordably, we use
Traffic Control (TC) tool of Linux to configure (upload) bandwidth and latency
of all nodes.151515Though simulating WAN in one AWS region using TC can
greatly save the expense as no data transfer fee, our experiments’ cost is
still about $6,000. We consider 3 deployment scenarios: global, continental,
and regional. The global setting reflects a globally distributed environment
with 400 ms round-trip time (RTT) and 100 Mbps bandwidth. The continental
setting is with 200 ms RTT and 500 Mbps bandwidth to depict the network
condition inside a large country or a union of countries. The regional setting
has 100 ms RTT and 1 Gbps bandwidth.

Basic benchmarking. Figures 18, 19 and 20 shows throughput and latency of each
protocol on varying input rates and scales, for the regional, continental and
global settings, respectively. Each data point is averaged over at least a
minute execution after a warm-up period of one block.

_Peak throughput_. $\mathsf{JUMBO}$ always presents the largest peak
throughput. More intriguingly, its peak throughput is close to the line speed,
despite $n$ or network settings. For example, when bandwidth is 500 Mbps, its
throughput can roughly achieve 250,000 tx/s, which approximates 500 Mbps as we
use 2000-bit (256-byte) transaction.161616Note 500 Mbps = $500*1024^{2}$ bit/s
instead of $5*10^{8}$ bit/s in Linux TC.  In addition,
$\mathsf{FIN}\textrm{-}\mathsf{NG}$’s peak throughput is larger than that of
FIN and $\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ in nearly all cases, although it
is less than $\mathsf{JUMBO}$.

The peak throughput of $\mathsf{JUMBO}$ can exceed that of
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ because the QC-based broadcasts in
$\mathsf{JUMBO}$ can better utilize bandwidth resources due to less overheads:
First, the “uncontributive” network packet headers in $\mathsf{JUMBO}$ are an
order-of-$\mathcal{O}(n)$ less, because of its asymptotically better message
complexity; Second, “loadless” message passing rounds are also reduced in
$\mathsf{JUMBO}$, considering that each broadcast in $\mathsf{JUMBO}$ only has
a single loadless round but each w$\mathsf{BRBC}$ in
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ has 2-3 loadless rounds.

_Latency-throughput trade-offs_. It is clear that $\mathsf{JUMBO}$ strictly
surpasses $\mathsf{FIN}\textrm{-}\mathsf{NG}$ in the global and continental
settings when $n$$\geq$$128$ nodes, as $\mathsf{JUMBO}$ can attain the same
throughput at a lower latency. What’s even more intriguing is that
$\mathsf{JUMBO}$’s latency can remain low while its throughput increases from
minimum to maximum. This hints at that $\mathsf{JUMBO}$ is promising to
simultaneously handle throughput-critical and latency-critical applications.
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ cannot match $\mathsf{JUMBO}$ in handling
substantial system loads in large network such as $n$=$256$, but it might
exhibit lower latency when bandwidth is sufficient (e.g., 1 Gbps) and/or
system is relatively small (e.g., 64 nodes), indicating its applications in
scenarios that are extremely latency-sensitive with low system loads and
adequate network resources. Again, FIN and
$\mathsf{Dumbo}\textrm{-}\mathsf{NG}$ perform much worse than
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ and $\mathsf{JUMBO}$ in most cases.

Benchmarking with faulty nodes. We also consider 3 types of faulty nodes: (i)
crash nodes, (ii) Byzantine nodes that send invalid signatures to cause honest
nodes verify all signatures before blocklist comes into effect, and (iii)
Byzantine nodes that can lower the quality of $\mathsf{MVBA}$ to downgrade
performance. These malicious setting experiments are conducted in a network of
1 Gbps bandwidth and 100 ms RTT.

Figure 21: Latency v.s. throughput in case of 100ms RTT and 1Gbps bandwidth
for $n=$256 nodes (with 85 crashed nodes). Figure 22: Execution of
$\mathsf{JUMBO}$ for $n=$256 nodes (where are 85 malicious nodes sending
invalid signatures). Figure 23: Latency of FIN-NG v.s. the quality of MVBA
used in FIN-NG for $n=$256 nodes (with 85 malicious nodes).

_Crash faults_. As illustrated in Fig 21, we evaluated the performance of
$\mathsf{JUMBO}$ and $\mathsf{FIN}\textrm{-}\mathsf{NG}$ with
$\lfloor(n-1)/3\rfloor$ crash nodes for $n=$256 nodes. Crashes cause the
latency of $\mathsf{FIN}\textrm{-}\mathsf{NG}$ and $\mathsf{JUMBO}$ slightly
increased. The peak throughputs of $\mathsf{JUMBO}$ and
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ are almost not impacted by crashes, and
they still can reasonably track available network bandwidth.

_Byzantine faults that send invalid digital signatures_. We evaluated
$\mathsf{JUMBO}$ for $n$=$256$ with 85 malicious nodes that send fake
signatures to downgrade the performance of batch-verification. Figure 22 (a)
and (b) plot the latency and throughput, respectively, during an execution
where the Byzantine nodes launch the attack while running the 11th and later
blocks. Clearly, the attack almost causes negligible impact on these
performance metrics, as the Byzantine nodes were quickly blocklisted and
therefore their attack was prevented.

_Byzantine faults that manipulate $\mathsf{MVBA}$ output quality_. Then we run
tests of $\mathsf{FIN}\textrm{-}\mathsf{NG}$ for $n$=$256$ with 85 Byzantine
nodes that attempt to manipulate $\mathsf{MVBA}$ output. These Byzantine
nodes’ inputs to $\mathsf{MVBA}$ have minimum validity (e.g., only solicit
$n-f$ broadcasts from distinct nodes), and they attempt to let $\mathsf{MVBA}$
decide a malicious output as much as possible. As Figure 23 plots, we compared
the effect of above attack while $\mathsf{MVBA}$’s quality varies from 1/2 to
1/128. It is obvious to see that 1/2-quality is more robust against such
attack and renders a latency closest to the case of no such attack.

Benchmarking in fluctuating network. We also test
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ and $\mathsf{JUMBO}$ with 256 nodes in a
dynamic network controlled by Linux TC to switch between 1 Gbps and 500 Mbps
for each 15 sec. The evaluated results are plotted in Figure 24.
$\mathsf{JUMBO}$ can always closely track the network capacity and achieve
throughput close to the instantaneous line rate.
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ is also can switch smoothly across varying
network conditions, though its concrete throughput is less than
$\mathsf{JUMBO}$.

Figure 24: Executions of $\mathsf{JUMBO}$ and
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ in a fluctuating network that changes
bandwidth and RTT for every 15 sec.

##  IX Conclusion

We present a couple of more scalable asynchronous BFT consensus protocols
$\mathsf{FIN}\textrm{-}\mathsf{NG}$ and $\mathsf{JUMBO}$ with reduced
authenticator overhead. Extensive experiments are conducted, revealing that
these scalable designs can performantly operate in large-scale WAN settings
with up to 256 nodes.

## References

  * [1] M. Ben-Or, “Another advantage of free choice (extended abstract) completely asynchronous agreement protocols,” in _Proc. PODC 1983_ , pp. 27–30.
  * [2] M. O. Rabin, “Randomized byzantine generals,” in _Proc. FOCS 1983_ , pp. 403–409.
  * [3] A. Mostefaoui, H. Moumen, and M. Raynal, “Signature-free asynchronous byzantine consensus with t¡ n/3 and o (n2) messages,” in _Proc. PODC 2014_ , 2014, pp. 2–9.
  * [4] R. Canetti and T. Rabin, “Fast asynchronous byzantine agreement with optimal resilience,” in _Proc. STOC 1993_ , pp. 42–51.
  * [5] C. Cachin and J. A. Poritz, “Secure intrusion-tolerant replication on the internet,” in _Proc. DSN 2002_ , 2002, pp. 167–176.
  * [6] H. Moniz, N. F. Neves, M. Correia, and P. Verissimo, “Ritas: Services for randomized intrusion tolerance,” _IEEE transactions on dependable and secure computing_ , vol. 8, no. 1, pp. 122–136, 2008.
  * [7] A. Patra, A. Choudhary, and C. Pandu Rangan, “Simple and efficient asynchronous byzantine agreement with optimal resilience,” in _Proc. PODC 2009_ , pp. 92–101.
  * [8] I. Abraham, D. Dolev, and J. Y. Halpern, “An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience,” in _Proc. PODC 2008_ , pp. 405–414.
  * [9] C. Cachin, K. Kursawe, and V. Shoup, “Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography,” _Journal of Cryptology_ , vol. 18, no. 3, pp. 219–246, 2005.
  * [10] M. Ben-Or and R. El-Yaniv, “Resilient-optimal interactive consistency in constant time,” _Distributed Computing_ , vol. 16, no. 4, pp. 249–262, 2003\.
  * [11] C. Cachin, K. Kursawe, F. Petzold, and V. Shoup, “Secure and efficient asynchronous broadcast protocols,” in _CRYPTO 2001_ , pp. 524–541.
  * [12] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The honey badger of bft protocols,” in _Proc. CCS 2016_ , 2016, pp. 31–42.
  * [13] S. Duan, M. K. Reiter, and H. Zhang, “Beat: Asynchronous bft made practical,” in _Proc. CCS 2018_ , 2018, pp. 2028–2041.
  * [14] B. Guo, Z. Lu, Q. Tang, J. Xu, and Z. Zhang, “Dumbo: Faster asynchronous bft protocols,” in _Proc. CCS 2020_ , pp. 803–818.
  * [15] I. Abraham, D. Malkhi, and A. Spiegelman, “Asymptotically optimal validated asynchronous byzantine agreement,” in _Proc. PODC 2019_ , pp. 337–346.
  * [16] G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman, “Narwhal and tusk: a dag-based mempool and efficient bft consensus,” in _Proc. EuroSys 2022_ , pp. 34–50.
  * [17] Y. Lu, Z. Lu, Q. Tang, and G. Wang, “Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited,” in _Proc. PODC 2020_ , pp. 129–138.
  * [18] Y. Gao, Y. Lu, Z. Lu, Q. Tang, J. Xu, and Z. Zhang, “Dumbo-ng: Fast asynchronous bft consensus with throughput-oblivious latency,” in _Proc. CCS 2022_ , pp. 1187–1201.
  * [19] I. Abraham, P. Jovanovic, M. Maller, S. Meiklejohn, G. Stern, and A. Tomescu, “Reaching consensus for asynchronous distributed key generation,” in _Proc. PODC 2021_ , pp. 363–373.
  * [20] S. Duan, X. Wang, and H. Zhang, “Practical signature-free asynchronous common subset in constant time,” in _Proc. CCS 2023_.
  * [21] L. Yang, S. J. Park, M. Alizadeh, S. Kannan, and D. Tse, “DispersedLedger: High-Throughput byzantine consensus on variable bandwidth networks,” in _Proc. NSDI 2022_.
  * [22] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” _Journal of the ACM (JACM)_ , vol. 32, no. 2, pp. 374–382, 1985.
  * [23] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” _Decentralized Business Review_ , p. 21260, 2008.
  * [24] M. Castro, B. Liskov _et al._ , “Practical byzantine fault tolerance,” in _Proc. OSDI 1999_ , pp. 173–186.
  * [25] M. Saad, A. Anwar, S. Ravi, and D. Mohaisen, “Revisiting nakamoto consensus in asynchronous networks: A comprehensive analysis of bitcoin safety and chainquality,” in _Proc. CCS 2021_ , pp. 988–1005.
  * [26] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham, “Hotstuff: Bft consensus with linearity and responsiveness,” in _Proc. PODC 2019_ , 2019, pp. 347–356.
  * [27] B. Guo, Y. Lu, Z. Lu, Q. Tang, J. Xu, and Z. Zhang, “Speeding dumbo: Pushing asynchronous bft closer to practice,” in _Proc. NDSS 2022_.
  * [28] A. Bessani, J. Sousa, and E. E. Alchieri, “State machine replication for the masses with bft-smart,” in _Proc. DSN 2014_ , pp. 355–362.
  * [29] Z. Li, A. Sonnino, and P. Jovanovic, “Performance of eddsa and bls signatures in committee-based consensus,” in _Proc. ApPLIED 2023_.
  * [30] Z. Avarikioti, L. Heimbach, R. Schmid, L. Vanbever, R. Wattenhofer, and P. Wintermeyer, “Fnf-bft: Exploring performance limits of bft protocols,” _arXiv preprint arXiv:2009.02235_ , 2020.
  * [31] H. Zhang and S. Duan, “Pace: Fully parallelizable bft from reproposable byzantine agreement,” in _Proc. CCS 2022_ , pp. 3151–3164.
  * [32] M. Ben-Or, B. Kelmer, and T. Rabin, “Asynchronous secure computations with optimal resilience,” in _Proc. PODC 1994_ , pp. 183–192.
  * [33] H. V. Ramasamy and C. Cachin, “Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast,” in _Proc. OPODIS 2005_ , pp. 88–102.
  * [34] R. C. Merkle, “A digital signature based on a conventional encryption function,” in _Conference on the theory and application of cryptographic techniques_ , 1987, pp. 369–378.
  * [35] I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” _Journal of the society for industrial and applied mathematics_ , vol. 8, no. 2, pp. 300–304, 1960.
  * [36] “Reed-solomon erasure coding in go,” accessed: 2024-3-10. [Online]. Available: {https://github.com/klauspost/reedsolomon}
  * [37] J. Blomer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckermank, “An xor-based erasure-resilient coding scheme,” _Tech Report, Tech. Rep._ , 1995\.
  * [38] J. S. Plank, “Optimizing cauchy reed-solomon codes for fault-tolerant storage applications,” _University of Tennessee, Tech. Rep. CS-05-569_ , vol. 38, 2005.
  * [39] C. Stathakopoulou, T. David, M. Pavlovic, and M. Vukolić, “Mir-bft: High-throughput robust bft for decentralized networks,” _arXiv preprint arXiv:1906.05552_ , 2019.
  * [40] C.-P. Schnorr, “Efficient signature generation by smart cards,” _Journal of cryptology_ , vol. 4, pp. 161–174, 1991.
  * [41] K. Chalkias, F. Garillot, Y. Kondi, and V. Nikolaenko, “Non-interactive half-aggregation of eddsa and variants of schnorr signatures,” in _Cryptographers’ Track at the RSA Conference_ , 2021, pp. 577–608.
  * [42] Y. Chen and Y. Zhao, “Half-aggregation of schnorr signatures with tight reductions,” in _ESORICS 2022_ , pp. 385–404.
  * [43] D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the weil pairing,” _Journal of cryptology_ , vol. 17, pp. 297–319, 2004.
  * [44] D. Boneh, M. Drijvers, and G. Neven, “Compact multi-signatures for smaller blockchains,” in _ASIACRYPT 2018_ , pp. 435–464.
  * [45] A. Boldyreva, “Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme,” in _International Workshop on Public Key Cryptography_ , 2003, pp. 31–46.
  * [46] “Use threshold signature as source of randomness,” accessed: 2023-7-20. [Online]. Available: {https://github.com/amiller/HoneyBadgerBFT/commit/ac787c486bc8def0fa0da3cb3287a12926bd437a}
  * [47] K. Jannes, E. H. Beni, B. Lagaisse, and W. Joosen, “Beaufort: Robust byzantine fault tolerance for client-centric mobile web applications,” _IEEE TPDS_ , vol. 34, no. 4, pp. 1241–1252, 2023.
  * [48] S. Das, Z. Xiang, and L. Ren, “Asynchronous data dissemination and its applications,” in _Proc. CCS 2021_ , pp. 2705–2721.
  * [49] N. Alhaddad, S. Das, S. Duan, L. Ren, M. Varia, Z. Xiang, and H. Zhang, “Balanced byzantine reliable broadcast with near-optimal communication and improved computation,” in _Proc. PODC 2022_ , pp. 399–417.
  * [50] G. Bracha, “Asynchronous byzantine agreement protocols,” _Information and Computation_ , vol. 75, no. 2, pp. 130–143, 1987.
  * [51] G. Bracha, “An asynchronous [(n-1)/3]-resilient consensus protocol,” in _Proc. PODC 1984_ , pp. 154–162.
  * [52] G. Goren, Y. Moses, and A. Spiegelman, “Probabilistic indistinguishability and the quality of validity in byzantine agreement,” in _Proc. AFT_ , 2022, pp. 111–125.
  * [53] B. Libert and M. Yung, “Adaptively secure non-interactive threshold cryptosystems,” in _Proc. ICALP 2011_ , 2011, pp. 588–600.
  * [54] E. Kokoris Kogias, D. Malkhi, and A. Spiegelman, “Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures.” in _Proc. CCS 2020_ , pp. 1751–1767.
  * [55] S. Das, T. Yurek, Z. Xiang, A. Miller, L. Kokoris-Kogias, and L. Ren, “Practical asynchronous distributed key generation,” in _IEEE S &P 2022_, pp. 2518–2534.
  * [56] Y. Gao, Y. Lu, Z. Lu, Q. Tang, J. Xu, and Z. Zhang, “Efficient asynchronous byzantine agreement without private setups,” in _Proc. ICDCS 2022_.
  * [57] J. Garay, A. Kiayias, and N. Leonardos, “The bitcoin backbone protocol: Analysis and applications,” in _EUROCRYPT 2015_ , pp. 281–310.
  * [58] I. Keidar, E. Kokoris-Kogias, O. Naor, and A. Spiegelman, “All you need is dag,” in _Proc. PODC 2021_ , pp. 165–175.
  * [59] C. Cachin and S. Tessaro, “Asynchronous verifiable information dispersal,” in _Proc. SRDS 2005_ , pp. 191–201.
  * [60] T. Yurek, Z. Xiang, Y. Xia, and A. Miller, “Long live the honey badger: Robust asynchronous $\\{$DPSS$\\}$ and its applications,” in _USENIX Security 23_ , pp. 5413–5430.
  * [61] S. Das, Z. Xiang, L. Kokoris-Kogias, and L. Ren, “Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling,” in _USENIX Security 23_ , pp. 5359–5376.
  * [62] I. Abraham, G. Asharov, A. Patra, and G. Stern, “Perfectly secure asynchronous agreement on a core set in constant expected time,” _Cryptology ePrint Archive_ , 2023.
  * [63] M. Nystrom and B. Kaliski, “PKCS #10: Certification Request Syntax Specification Version 1.7,” RFC 2986, Nov. 2000. [Online]. Available: https://www.rfc-editor.org/info/rfc2986
  * [64] M. K. Reiter, “Secure agreement protocols: Reliable and atomic group multicast in rampart,” in _Proc. ACM CCS 1994_ , pp. 68–80.
  * [65] “Pragmatic signature aggregation with bls,” accessed: 2023-7-20. [Online]. Available: {https://ethresear.ch/t/pragmatic-signature-aggregation-with-bls/2105}
  * [66] A. Tomescu, R. Chen, Y. Zheng, I. Abraham, B. Pinkas, G. G. Gueta, and S. Devadas, “Towards scalable threshold cryptosystems,” in _Proc. IEEE S &P 2020_, pp. 877–893.
  * [67] libsecp256k1. [Online]. Available: https://github.com/bitcoin-core/secp256k1
  * [68] P. S. Barreto, B. Lynn, and M. Scott, “Constructing elliptic curves with prescribed embedding degrees,” in _SCN 2003_ , pp. 257–267.
  * [69] bls-go-binary. [Online]. Available: https://github.com/herumi/bls-go-binary
  * [70] T. Kim and R. Barbulescu, “Extended tower number field sieve: A new complexity for the medium prime case,” in _Annual international cryptology conference_ , 2016, pp. 543–571.
  * [71] L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena, “A secure sharding protocol for open blockchains,” in _Proc. ACM CCS 2016_ , pp. 17–30.
  * [72] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “Omniledger: A secure, scale-out, decentralized ledger via sharding,” in _Proc. IEEE S &P 2018_, pp. 583–598.
  * [73] M. Zamani, M. Movahedi, and M. Raykova, “Rapidchain: Scaling blockchain via full sharding,” in _Proc. ACM CCS 2018_ , pp. 931–948.
  * [74] N. Giridharan, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman, “Bullshark: Dag bft protocols made practical,” in _Proc. CCS 2022_ , 2022.
  * [75] R. Gelashvili, L. Kokoris-Kogias, A. Sonnino, A. Spiegelman, and Z. Xiang, “Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback,” in _FC 2022_.
  * [76] Y. Lu, Z. Lu, and Q. Tang, “Bolt-dumbo transformer: Asynchronous consensus as fast as pipelined bft,” in _Proc. CCS 2022_ , 2022.
  * [77] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling byzantine agreements for cryptocurrencies,” in _Proceedings of the 26th symposium on operating systems principles_ , 2017, pp. 51–68.
  * [78] G. G. Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. Reiter, D.-A. Seredinschi, O. Tamir, and A. Tomescu, “Sbft: a scalable and decentralized trust infrastructure,” in _Proc. DSN 2019_ , 2019, pp. 568–580.
  * [79] Y. Amir, C. Danilov, D. Dolev, J. Kirsch, J. Lane, C. Nita-Rotaru, J. Olsen, and D. Zage, “Steward: Scaling byzantine fault-tolerant replication to wide area networks,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 7, no. 1, pp. 80–93, 2008.
  * [80] R. Neiheiser, M. Matos, and L. Rodrigues, “Kauri: Scalable bft consensus with pipelined tree-based dissemination and aggregation,” in _Proc. SOSP 2021_ , pp. 35–48.

##  Appendix A CPU Time of Sign, Non-interactive Aggregation and Verification
of Typical Digital Signatures

Table II lists the signing time, verification time, aggregation time, and
batch-verification time of typical digital signatures. From Table II, we have
the next key findings: a) QCs constructed from BLS multi-signature can be
verified much faster than QCs constructed from concatenated ECDSA signatures
and half-aggregated Schnorr signatures, e.g., verifying a QC from BLS multi-
signature is an order of magnitude faster than those from ECDSA and Schnorr
for $n=256$; b) however, verifying a single BLS signature is much slower than
verifying a single ECDSA/Schnorr signature because BLS verification needs
costly pairing operations of elliptic curve, e.g., the verification of a
single BLS signature is an order of magnitude slower than ECDSA and Schnorr
signatures. Given our benchmarking of digital signatures, it becomes easy to
understand why the earlier study [29] concludes that the tempting BLS multi-
signature has inferior performance in their BFT systems with relatively larger
sizes, because the verification of $n-f$ single BLS signatures can quickly
dominate the overall computing cost while $n$ increases.

TABLE II: Time of signing, verifying a single signature, aggregating/concatenating $(n-f)$ signatures, and verifying a $(n-f)$-sized QC, where each data point is averaged over 10 thousand executions at an AWS EC2 c6a.2xlarge server. ECDSA/Schnorr are tested through library [67] over Secp256k1 curve and BLS is tested through library [69] over BLS12-381 curve. |  Sign ($\mu s$) |  Verify ($\mu s$) |  (Half-)aggregate $(n-f)$ signatures to form QC ($\mu s$) |  Verify $(n-f)$-sized QC ($\mu s$)
---|---|---|---|---
|  $n$=4 | 16 | 32 | 64 | 128 | 192 | 256 |  $n$=4 | 16 | 32 | 64 | 128 | 192 | 256
ECDSA | 31 | 43 | 0 as just concatenate |  $n-f$ times of verifying an individual signature
Schnorr | 25 | 44 | 18 | 63 | 120 | 245 | 485 | 731 | 970 | 141 | 430 | 787 | 1587 | 2714 | 3975 | 5005
BLS multi-sig | 187 | 891 | 1 | 6 | 11 | 18 | 49 | 74 | 102 | 904 | 916 | 932 | 951 | 1036 | 1102 | 1184
BLS thld-sig | 187 | 891 | 203 | 769 | 1448 | 3137 | 6294 | 9578 | 12976 | 891 | 891 | 891 | 891 | 891 | 891 | 891

##  Appendix B Quality Downgrade Attack of FIN-MVBA

As aforementioned in Section I and Section IV, the quality of FIN-MVBA [20]
could be only 1/3 under the influence of an adaptive adversary that can
perform “after-fact-removal”, which is lower than the optimal upper bound of
1/2 [52].

Here we illustrate a concrete adversary to perform such quality degradation
attack. Note that the adversary is adaptive such that it can gradually corrupt
up to $f$ nodes during the course of protocol. Besides, we assume the number
of participating nodes $n$ is large enough in order to simplify the
calculation of probability.

Below are the detailed attacking steps:

  1. 1.

Before the start of the FIN-MVBA protocol, the adversary chooses $f-1$ nodes
to corrupt, and let us denote this corrupted set by $A$, such that the input
of any node in $A$ can be replaced and thus controlled by the adversary.

  2. 2.

At the moment when the FIN-MVBA protocol starts, the adversary selects $f$
honest nodes, denoted by set $D$, and delays all messages related to these
nodes in $D$. Note that in addition to $D$, there are still $f+2$ so-far-
honest nodes, and we denote them as set $H$.

  3. 3.

The adversary controls the malicious nodes in $A$ to execute the protocol like
the honest ones until the $election$ protocol. Such that $H$ can proceed to
invoke the random leader $election$ protocol. To minimize the adversary’s
ability, we assume the reconstruction threshold of $election$ is $n-f$, which
equals to the size of $A\cup H$.

  4. 4.

The adversary controls $A$ not send messages in the $election$ protocol, but
it can receive $H$’s messages in the $election$ protocol, which allows $A$ to
get the $election$ protocol’s output $k$.

  5. 5.

Once the adversary gets $k$, there are three possible cases:

    1. (a)

$k$ falls in $A$. In this case, FIN-MVBA will output the input value of
$P_{k}$, which is chosen by the adversary. Note that the probability of this
scenario occurring is about 1/3.

    2. (b)

$k$ falls in $H$. In this case, FIN-MVBA will output the input value of
$P_{k}$, which is an input chosen by the honest node. Note that the
probability of this scenario occurring is also about 1/3.

    3. (c)

$k$ falls in $D$. In this case, the adversary can immediately corrupt node
$P_{k}$ because it still has a quota of corruption. Then the adversary removes
all messages that $P_{k}$ attempted to send because these messages are not
delivered yet, as such the adversary can replace $P_{k}$’s input value, and
rushingly finishes $P_{k}$’s $\mathsf{BRBC}$, after which, the adversary
delivers all messages, then its manipulating value will output in FIN-MVBA. So
in this scenario, the output is always chosen by the adversary. Note that the
probability of this scenario occurring is also about 1/3.

The above steps complete the attack, and result in that with probability 2/3,
the output is manipulated by the adversary.

##  Appendix C Proof of FIN-$\mathsf{MVBA}$-Q

Security of avw$\mathsf{BRBC}$. Note that a few properties of
avw$\mathsf{BRBC}$, such as weak agreement and validity, can immediately
inherited from $w\mathsf{BRBC}$, and we will only focus on the proofs of
totality and external validity properties.

######  Lemma 1.

Totality of avw$\mathsf{BRBC}$. For any avw$\mathsf{BRBC}$ instance, if an