Sorbonne University, France NUS Singapore, SingaporeSupported in part by the
Singapore MOE Tier 2 grant MOE-T2EP20122-0014. Ecole Polytechnique Fédérale de
Lausanne (EPFL), Switzerland Ecole Polytechnique Fédérale de Lausanne (EPFL),
Switzerland Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland Ecole
Polytechnique Fédérale de Lausanne (EPFL), SwitzerlandSupported in part by the
FNS (#200021_215383).

Anon

[500]Theory of computation Distributed algorithms

# Every Bit Counts in Consensus
(Extended Version)

Pierre Civit  Seth Gilbert  Rachid Guerraoui  Jovan Komatovic  Matteo Monti
Manuel Vidigueira

###### Abstract

Consensus enables $n$ processes to agree on a common valid $L$-bit value,
despite $t<n/3$ processes being faulty and acting arbitrarily. A long line of
work has been dedicated to improving the worst-case communication complexity
of consensus in partial synchrony. This has recently culminated in the worst-
case _word_ complexity of $O(n^{2})$. However, the worst-case _bit_ complexity
of the best solution is still $O(n^{2}L+n^{2}\kappa)$ (where $\kappa$ is the
security parameter), far from the $\Omega(nL+n^{2})$ lower bound. The gap is
significant given the practical use of consensus primitives, where values
typically consist of batches of large size ($L>n$).

This paper shows how to narrow the aforementioned gap. Namely, we present a
new algorithm, DARE (Disperse, Agree, REtrieve), that improves upon the
$O(n^{2}L)$ term via a novel dispersal primitive. DARE achieves
$O(n^{1.5}L+n^{2.5}\kappa)$ bit complexity, an effective $\sqrt{n}$-factor
improvement over the state-of-the-art (when $L>n\kappa$). Moreover, we show
that employing heavier cryptographic primitives, namely STARK proofs, allows
us to devise DARE-Stark, a version of DARE which achieves the near-optimal bit
complexity of $O(nL+n^{2}\mathit{poly}(\kappa))$. Both DARE and DARE-Stark
achieve optimal $O(n)$ worst-case latency.

###### keywords:

Byzantine consensus, Bit complexity, Latency

##  1 Introduction

Byzantine consensus [64] is a fundamental primitive in distributed computing.
It has recently risen to prominence due to its use in blockchains [69, 22, 4,
32, 5, 40, 38] and various forms of state machine replication (SMR) [8, 29,
63, 1, 11, 62, 86, 70, 73]. At the same time, the performance of these
applications has become directly tied to the performance of consensus and its
efficient use of network resources. Specifically, the key limitation on
blockchain transaction rates today is network throughput [41, 85, 27]. This
has sparked a large demand for research into Byzantine consensus algorithms
with better communication complexity guarantees.

Consensus operates among $n$ processes: each process proposes its value, and
all processes eventually agree on a common valid $L$-bit decision. A process
can either be correct or faulty: correct processes follow the prescribed
protocol, while faulty processes (up to $t<n/3$) can behave arbitrarily.
Consensus satisfies the following properties:

  * •

_Agreement:_ No two correct processes decide different values.

  * •

_Termination:_ All correct processes eventually decide.

  * •

_(External) Validity:_ If a correct process decides a value $v$, then
$\mathsf{valid}(v)=\mathit{true}$.

Here, $\mathsf{valid}(\cdot)$ is any predefined logical predicate that
indicates whether or not a value is valid.111For traditional notions of
validity, admissible values depend on the proposals of correct processes,
e.g., if all correct processes start with value $v$, then $v$ is the only
admissible decision. In this paper, we focus on external validity [25], with
the observation that any other validity condition can be achieved by reduction
(as shown in [37]).

This paper focuses on improving the worst-case bit complexity of deterministic
Byzantine consensus in standard partial synchrony [51]. The worst-case lower
bound is $\Omega(nL+n^{2})$ exchanged bits. This considers all bits sent by
correct processes from the moment the network becomes synchronous, i.e., GST
(the number of messages sent by correct processes before GST is unbounded due
to asynchrony [84]). The $nL$ term comes from the fact that all $n$ processes
must receive the decided value at least once, while the $n^{2}$ term is
implied by the seminal Dolev-Reischuk lower bound [47, 84] on the number of
messages. Recently, a long line of work has culminated in Byzantine consensus
algorithms which achieve optimal $O(n^{2})$ worst-case _word_ complexity,
where a word is any constant number of values, signatures or hashes [36, 65].
However, to the best of our knowledge, no existing algorithm beats the
$O(n^{2}L+n^{2}\kappa)$ bound on the worst-case bit complexity, where $\kappa$
denotes the security parameter (e.g., the number of bits per hash or
signature). The $n^{2}L$ term presents a linear gap with respect to the lower
bound.

Does this gap matter? In practice, yes. In many cases, consensus protocols are
used to agree on a large batch of inputs [76, 87, 27, 41, 85]. For example, a
block in a blockchain amalgamates many transactions. Alternatively, imagine
that $n$ parties each propose a value, and the protocol agrees on a set of
these values. (This is often known as vector consensus [14, 15, 49, 79, 48,
39].) Typically, the hope is that by batching values/transactions, we can
improve the total throughput of the system. Unfortunately, with current
consensus protocols, larger batches do not necessarily yield better
performance when applied directly [45]. This does not mean that batches are
necessarily ineffective. In fact, a recent line of work has achieved
significant practical improvements to consensus throughput by entirely
focusing on the efficient dissemination of large batches (i.e., large values),
so-called “mempool” protocols [41, 85, 27]. While these solutions work only
optimistically (they perform well in periods of synchrony and without faults),
they show that a holistic focus on _bandwidth_ usage is fundamental (i.e., bit
complexity, and not just word complexity).

###  1.1 Contributions

We introduce DARE (Disperse, Agree, REtrieve), a new Byzantine consensus
algorithm for partial synchrony with worst-case $O(n^{1.5}L+n^{2.5}\kappa)$
bit complexity and optimal worst-case $O(n)$ latency. Moreover, by enriching
DARE with heavier cryptographic primitives, namely STARK proofs, we close the
gap near-optimally using only $O(nL+n^{2}\mathit{poly}(\kappa))$ bits. Notice
that, if you think of $L$ as a batch of $n$ transactions of size $s$, the
average communication cost of agreeing on a single transaction is only
$\tilde{O}(ns)$ bits – the same as a best-effort (unsafe) broadcast [24] of
that transaction!

To the best of our knowledge, DARE is the first partially synchronous
algorithm to achieve $o(n^{2}L)$ bit complexity and $O(n)$ latency. The main
idea behind DARE is to separate the problem of agreeing from the problem of
retrieving an agreed-upon value (see § 1.2 for more details). Figure 1 places
DARE in the context of efficient consensus algorithms.

Protocol |  Model |  Cryptography | Complexity
---|---|---|---
|  |  |  $\mathbb{E}[\text{Bits}]^{\dagger}$ |  $\mathbb{E}[\text{Latency}]^{\dagger}$
ABC [25]‡ |  Async |  PKI, TS [67] |  $O(n^{2}L+n^{2}\kappa+n^{3})$ |  $O(1)$
VABA [6] |  Async |  above |  $O(n^{2}L+n^{2}\kappa)$ |  $O(1)$
Dumbo-MVBA [68] |  Async |  above + ECC [19] |  $O(nL+n^{2}\kappa)$ |  $O(1)$
|  |  |  Bits |  Latency
PBFT [30, 17] |  PSync |  PKI |  $O(n^{2}L+n^{4}\kappa)$ |  $O(n)$
HotStuff [88] |  PSync |  above + TS |  $O(n^{2}L+n^{3}\kappa)$ |  $O(n)$
Quad [36, 65] |  PSync |  above |  $O(n^{2}L+n^{2}\kappa)$ |  $O(n)$
DARE |  PSync |  above + ECC |  $O(n^{1.5}L+n^{2.5}\kappa)$ |  $O(n)$
DARE-Stark |  PSync |  above + STARK |  $O(nL+n^{2}\kappa)$ |  $O(n)$
Figure 1: Performance of various consensus algorithms with $L$-bit values and
$\kappa$-bit security parameter.
† For asynchronous algorithms, we show the complexity in expectation instead
of the worst-case (which is unbounded for deterministic safety guarantees due
to the FLP impossibility result [53]).
‡ Threshold Signatures (TS) are used to directly improve the original
algorithm.

###  1.2 Technical Overview

The “curse” of GST. To understand the problem that DARE solves, we must first
understand why existing algorithms suffer from an $O(n^{2}L)$ term. “Leader-
based” algorithms (such as the state-of-the-art [74, 36, 65]) solve consensus
by organizing processes into a rotating sequence of _views_ , each with a
different leader. A view’s leader broadcasts its value $v$ and drives other
processes to decide it. If all correct processes are timely and the leader is
correct, $v$ is decided.

The main issue is that, if synchrony is only guaranteed _eventually_ (partial
synchrony [51]), a view might fail to reach agreement even if its leader is
correct: the leader could just be slow (i.e., not yet synchronous). The
inability to distinguish the two scenarios forces protocols to change views
even if the current leader is merely “suspected” of being faulty. Since there
can be up to $t$ faulty leaders, there must be at least $t+1$ different views.
However, this comes at the risk of sending unnecessary messages if the
suspicion proves false, which is what happens in the worst case.

Suppose that, before GST (i.e., the point in time the system becomes
synchronous), the first $t$ leaders are correct, but “go to sleep” (slow down)
immediately before broadcasting their values, and receive no more messages
until $\text{GST}+\delta$ due to asynchrony ($\delta$ is the maximum message
delay after GST). Once GST is reached, all $t$ processes wake up and broadcast
their value, for a total of $O(tnL)=O(n^{2}L)$ exchanged bits; this can happen
before they have a chance to receive even a single message! This attack can be
considered a “curse” of GST: the _adversarial shift_ of correct processes in
time creates a (seemingly unavoidable) situation where $\Omega(n^{2})$
messages are sent at GST (which in this case include $L$ bits each, for a
total of $\Omega(n^{2}L)$). Figure 2 illustrates the attack.

Figure 2: The _adversarial shift_ attack on $t+1$ leaders. The first line
shows how leaders are optimistically ordered in time by the protocol to avoid
redundant broadcasts (the blue speaker circle represents an _avoided_
redundant broadcast). The second line shows how leaders can slow down before
GST and overlap at GST, making redundant broadcasts (seem) unavoidable.

DARE: Disperse, Agree, REtrieve. In a nutshell, DARE follows three phases:

  1. 1.

Dispersal: Processes attempt to disperse their values and obtain a _proof of
dispersal_ for any value. This proof guarantees that the value is both (1)
valid, and (2) retrievable.

  2. 2.

Agreement: Processes propose a _hash_ of the value accompanied by its proof of
dispersal to a Byzantine consensus algorithm for small $L$ (e.g.,
$O(\kappa)$).

  3. 3.

Retrieval: Using the decided hash, processes retrieve the corresponding value.
The proof of dispersal ensures Retrieval will succeed and output a valid
value.

This architecture is inspired by randomized asynchronous Byzantine algorithms
[6, 68] which work with _expected_ bit complexity (the worst-case is unbounded
in asynchrony [53]). As these algorithms work in expectation, they can rely on
randomness to retrieve a value ($\neq\bot$) that is valid after an expected
constant number of tries. However, in order to achieve the same effect (i.e.,
a constant number of retrievals) in the worst case in partial synchrony, DARE
must guarantee that the Retrieval protocol _always_ outputs a valid value
($\neq\bot$) _a priori_ , which shifts the difficulty of the problem almost
entirely to the Dispersal phase.

Dispersal. To obtain a proof of dispersal, a natural solution is for the
leader to broadcast the value $v$. Correct processes check the validity of $v$
(i.e., if $\mathsf{valid}(v)=\mathit{true}$), store $v$ for the Retrieval
protocol, and produce a partial signature attesting to these two facts. The
leader combines the partial signatures into a $(2t+1,n)$-threshold signature
(the proof of dispersal), which is sufficient to prove that DARE’s Retrieval
protocol [43] will output a valid value after the Agreement phase.

However, if leaders use best-effort broadcast [24] (i.e., simultaneously send
the value to all other processes), they are still vulnerable to an
_adversarial shift_ causing $O(n^{2}L)$ communication. Instead, we do the
following. First, we use a _view synchronizer_ [77, 20, 21] to group leaders
into _views_ in a rotating sequence. A view has $\sqrt{n}$ leaders and a
sequence has $\sqrt{n}$ views. Leaders of the current view can concurrently
broadcast their values while messages of other views are ignored. Second,
instead of broadcasting the value simultaneously to all processes, a leader
broadcasts the value to different subgroups of $\sqrt{n}$ processes in
intervals of $\delta$ time (i.e., broadcast to the first subgroup, wait
$\delta$ time, broadcast to the second subgroup, …) until all processes have
received the value. Neither idea individually is enough to improve over the
$O(n^{2}L)$ term. However, when they are combined, it becomes possible to
balance the communication cost of the synchronizer ($O(n^{2.5}\kappa)$ bits),
the maximum cost of an _adversarial shift_ attack ($O(n^{1.5}L)$ bits), and
the broadcast rate to achieve the improved $O(n^{1.5}L+n^{2.5}\kappa)$ bit
complexity with asymptotically optimal $O(\delta n)$ latency as shown in
Figure 3.

Figure 3: Overview of DARE (Disperse, Agree, REtrieve).

DARE-Stark. As we explained, the main cost of the Dispersal phase is
associated with obtaining a dispersal proof that a value is valid.
Specifically, it comes from the cost of having to send the entire value ($L$
bits) in a single message.

With Succinct Transparent ARguments of Knowledge (STARKs), we can entirely
avoid sending the value in a single message. STARKs allow a process to compute
a proof ($O(\mathit{poly}(\kappa))$ bits) of a statement on some value without
having to share that value. As an example, a process $P_{i}$ can send $\langle
h,\sigma_{\textsf{STARK}}\rangle$ to a process $P_{j}$, which can use
$\sigma_{\textsf{STARK}}$ to verify the statement “$\exists
v:\mathsf{valid}(v)=\mathit{true}\land\mathsf{hash}(v)=h$”, all without
$P_{j}$ ever receiving $v$. As we detail in § 6, by carefully crafting a more
complex statement, we can modify DARE’s Dispersal and Retrieval phases to
function with at most $O(\mathit{poly}(\kappa))$ bit-sized messages, obtaining
DARE-Stark. This yields the overall near-optimal bit complexity of
$O(nL+n^{2}\mathit{poly}(\kappa))$. Currently, the main drawback of STARKs is
their size and computation time in practice222The associated constants hidden
by the “big O” notation result in computation in the order of seconds, proofs
in the hundreds of KB, and memory usage several times greater [52]., which we
hope will improve in the future.

Roadmap. We discuss related work in § 2. In § 3, we define the system model.
We give an overview of DARE in § 4. In § 5, we detail our Dispersal protocol.
We go over DARE-Stark in § 6. Lastly, we conclude the paper in § 7. Detailed
proofs are relegated to the optional appendix.

##  2 Related Work

We address the communication complexity of deterministic authenticated
Byzantine consensus [64, 25] in partially synchronous distributed systems [51]
for large inputs. Here, we discuss existing results in closely related
contexts, and provide a brief overview of techniques, tools and building
blocks which are often employed to tackle Byzantine consensus.333We use
“consensus” and “agreement” interchangeably.

Asynchrony. In the asynchronous setting, Byzantine agreement is commonly known
as Multi-valued Validated Byzantine Agreement, or MVBA [25]. Due to the FLP
impossibility result [53], deterministic Byzantine agreement is unsolvable in
asynchrony (which implies unbounded worst-case complexity). Hence,
asynchronous MVBA solutions focus on expected complexity. This line of work
was revitalized by HoneyBadgerBFT [72], the first practical fully asynchronous
MVBA implementation. Like most other modern asynchronous MVBA protocols, it
leverages randomization via a common coin [75], and it terminates in expected
$O(\log n)$ time with an expected bit complexity of $O(n^{2}L+n^{3}\kappa\log
n)$. [6] improves this to $O(1)$ expected time and $O(n^{2}L+n^{2}\kappa)$
expected bits, which is asymptotically optimal with $L,\kappa\in O(1)$. Their
result is later extended by [68] to large values, improving the complexity to
$O(nL+n^{2}\kappa)$ expected bits. This matches the best known lower bound
[84, 3, 47], assuming $\kappa\in O(1)$.

Extension protocols [78, 55, 56, 57]. An extension protocol optimizes for long
inputs via a reduction to the same problem with small inputs (considered an
oracle). Using extension protocols, several state-of-the-art results were
achieved in the authenticated and unauthenticated models, both in synchronous
and fully asynchronous settings for Byzantine consensus, Byzantine broadcast
and reliable broadcast [78]. Applying the extension protocol of [78] to [74],
synchronous Byzantine agreement can be implemented with optimal resiliency
($t<n/2$) and a bit complexity of $O(nL+n^{2}\kappa)$. Interestingly, it has
been demonstrated that synchronous Byzantine agreement can be implemented with
a bit complexity of $O(n(L+\mathit{poly}(\kappa)))$ using randomization [18].
The Dolev-Reischuk bound [47] is not violated in this case since the
implementation tolerates a negligible (with $\kappa$) probability of failure,
whereas the bound holds for deterministic protocols. In asynchrony, by
applying the (asynchronous) extension protocol of [78] to [6], the same
asymptotic result as [68] is achieved, solving asynchronous MVBA with an
expected bit complexity of $O(nL+n^{2}\kappa)$.

Unconditionally secure Byzantine agreement with large inputs has been
addressed by [33, 34] under synchrony and [66] under asynchrony, assuming a
common coin (implementable via unconditionally-secure Asynchronous Verifiable
Secret Sharing [35]). Despite [60] utilizing erasure codes to alleviate leader
bottleneck, and the theoretical construction of [37] with exponential latency,
there is, to the best of our knowledge, no viable extension protocol for
Byzantine agreement in partial synchrony achieving results similar to ours
($o(n^{2}L)$).

Error correction. Coding techniques, such as erasure codes [19, 59, 10] or
error-correction codes [81, 14], appear in state-of-the-art implementations of
various distributed tasks: Asynchronous Verifiable Secret Sharing (AVSS)
against a computationally bounded [43, 89, 83] or unbounded [35] adversary,
Random Beacon [42], Atomic Broadcast in both the asynchronous [54, 61] and
partially synchronous [28] settings, Information-Theoretic (IT) Asynchronous
State Machine Replication (SMR) [50], Gradecast in synchrony and Reliable
Broadcast in asynchrony [2], Asynchronous Distributed Key Generation (ADKG)
[43, 44], Asynchronous Verifiable Information Dispersal (AVID) [9], Byzantine
Storage [46, 12, 58], and MVBA [68, 78]. Coding techniques are often used to
reduce the worst-case complexity by allowing a group of processes to balance
and share the cost of sending a value to an individual (potentially faulty)
node and are also used in combination with other techniques, such as
commitment schemes [31, 68].

We now list several problems related to or used in solving Byzantine
agreement.

Asynchronous Common Subset (ACS). The goal in ACS [14, 15, 49] (also known as
Vector Consensus [79, 48, 39]) is to agree on a subset of $n-t$ proposals.
When considering a generalization of the validity property, this problem
represents the strongest variant of consensus [37]. Atomic Broadcast can be
trivially reduced to ACS [48, 25, 72]. There are well-known simple
asynchronous constructions that allow for the reduction of ACS to either (1)
Reliable Broadcast and Binary Byzantine Agreement [15], or (2) MVBA [25] in
the authenticated setting, where the validation predicate requires the output
to be a vector of signed inputs from at least $n-t$ parties. The first
reduction enables the implementation of ACS with a cubic bit complexity, using
the broadcast of [2]. The second reduction could be improved further with a
more efficient underlying MVBA protocol, such as DARE-Stark.

Asynchronous Verifiable Information Dispersal (AVID). AVID [26] is a form of
"retrievable" broadcast that allows the dissemination of a value while
providing a cryptographic proof that it can be retrieved. This primitive can
be implemented with a total dispersal cost of $O(L+n^{2}\kappa)$ bits
exchanged and a retrieval cost of $O(L+n\kappa)$ per node, relying only on the
existence of collision-resistant hash functions [9]. AVID is similar to our
Dispersal and Retrieval phases, but has two key differences. First, AVID’s
retrieval protocol only guarantees that a valid value will be retrieved if the
original process dispersing the information was correct. Second, it is a
broadcast protocol, having stricter delivery guarantees for each process.
Concretely, if a correct process initiates the AVID protocol, it should
eventually disperse its _own_ value. In contrast, we only require that a
correct process obtains a proof of dispersal for _some_ value.

Provable Broadcast (PB) and Asynchronous Provable Dispersal Broadcast (APDB).
PB [7] is a primitive used to acquire a succinct proof of external validity.
It is similar to our Dispersal phase, including the algorithm itself, but
without the provision of a proof of dispersal (i.e., retrievability, only
offering proof of validity). The total bit complexity for $n$ PB-broadcasts
from distinct processes amounts to $O(n^{2}L)$. APDB [68] represents an
advancement of AVID, drawing inspiration from PB. It sacrifices PB’s validity
guarantees to incorporate AVID’s dissemination and retrieval properties. By
leveraging the need to retrieve and validate a value a constant number of
times in expectation, [68] attains optimal $O(nL+n^{2}\kappa)$ expected
complexity in asynchrony. However, this approach falls short in the worst-case
scenario of a partially synchronous solution, where $n$ reconstructions would
cost $\Omega(n^{2}L)$.

Asynchronous Data Dissemination (ADD). In ADD [43], a subset of $t+1$ correct
processes initially share a common $L$-sized value $v$, and the goal is to
disseminate $v$ to all correct processes, despite the presence of up to $t$
Byzantine processes. The approach of [43] is information-theoretically secure,
tolerates up to one-third malicious nodes and has a bit complexity of
$O(nL+n^{2}\log n)$. (In DARE, we rely on ADD in a “closed-box” manner; see §
4.)

##  3 Preliminaries

Processes. We consider a static set
$\mathsf{Process}=\\{P_{1},P_{2},...,P_{n}\\}$ of $n=3t+1$ processes, out of
which (at most) $t>0$ can be Byzantine and deviate arbitrarily from their
prescribed protocol. A Byzantine process is said to be _faulty_ ; a non-faulty
process is said to be _correct_. Processes communicate by exchanging messages
over an authenticated point-to-point network. Furthermore, the communication
network is reliable: if a correct process sends a message to a correct
process, the message is eventually received. Processes have local hardware
clocks. Lastly, we assume that local steps of processes take zero time, as the
time needed for local computation is negligible compared to the message
delays.

Partial synchrony. We consider the standard partially synchronous model [51].
For every execution, there exists an unknown Global Stabilization Time (GST)
and a positive duration $\delta$ such that the message delays are bounded by
$\delta$ after GST. We assume that $\delta$ is known by processes. All correct
processes start executing their prescribed protocol by GST. The hardware
clocks of processes may drift arbitrarily before GST, but do not drift
thereafter. We underline that our algorithms require minimal changes to
preserve their correctness even if $\delta$ is unknown (these modifications
are specified in § C.2), although their complexity might be higher.

Cryptographic primitives. Throughout the paper, $\mathsf{hash}(\cdot)$ denotes
a collision-resistant hash function. The codomain of the aforementioned
$\mathsf{hash}(\cdot)$ function is denoted by $\mathsf{Hash\\_Value}$.

Moreover, we assume a $(k,n)$-threshold signature scheme [82], where
$k=n-t=2t+1$. In this scheme, each process holds a distinct private key, and
there is a single public key. Each process $P_{i}$ can use its private key to
produce a partial signature for a message $m$ by invoking
$\mathsf{share\\_sign}_{i}(m)$. A set of partial signatures $S$ for a message
$m$ from $k$ distinct processes can be combined into a single threshold
signature for $m$ by invoking $\mathsf{combine}(S)$; a threshold signature for
$m$ proves that $k$ processes have (partially) signed $m$. Furthermore,
partial and threshold signatures can be verified: given a message $m$ and a
signature $\Sigma_{m}$, $\mathsf{verify\\_sig}(m,\Sigma_{m})$ returns
$\mathit{true}$ if and only if $\Sigma_{m}$ is a valid signature for $m$.
Where appropriate, the verifications are left implicit. We denote by
$\mathsf{P\\_Signature}$ and $\mathsf{T\\_Signature}$ the set of partial and
threshold signatures, respectively. The size of cryptographic objects (i.e.,
hashes, signatures) is denoted by $\kappa$; we assume that $\kappa>\log
n$.444For $\kappa\leq\log n$, $t\in O(n)$ faulty processes would have
computational power exponential in $\kappa$, breaking cryptographic hardness
assumptions.

Reed-Solomon codes [81]. Our algorithms rely on Reed-Solomon (RS) codes [80].
Concretely, DARE utilizes (in a “closed-box” manner) an algorithm which
internally builds upon error-correcting RS codes. DARE-Stark directly uses RS
erasure codes (no error correction is required).

We use $\mathsf{encode}(\cdot)$ and $\mathsf{decode}(\cdot)$ to denote RS’
encoding and decoding algorithms. In a nutshell, $\mathsf{encode}(\cdot)$
takes a value $v$, chunks it into the coefficients of a polynomial of degree
$t$ (the maximum number of faults), and outputs $n$ (the total number of
processes) evaluations of the polynomial (RS symbols); $\mathsf{Symbol}$
denotes the set of RS symbols. $\mathsf{decode}(\cdot)$ takes a set of $t+1$
RS symbols $S$ and interpolates them into a polynomial of degree $t$, whose
coefficients are concatenated and output.

Complexity of Byzantine consensus. Let $\mathsf{Consensus}$ be a partially
synchronous Byzantine consensus algorithm, and let
$\mathcal{E}(\mathsf{Consensus})$ denote the set of all possible executions.
Let $\alpha\in\mathcal{E}(\mathsf{Consensus})$ be an execution, and
$t_{d}(\alpha)$ be the first time by which all correct processes have decided
in $\alpha$. The bit complexity of $\alpha$ is the total number of bits sent
by correct processes during the time period $[\text{GST},\infty)$. The latency
of $\alpha$ is $\max(0,t_{d}(\alpha)-\text{GST})$.

The _bit complexity_ of $\mathsf{Consensus}$ is defined as

$\max_{\alpha\in\mathcal{E}(\mathsf{Consensus})}\bigg{\\{}\text{bit complexity
of }\alpha\bigg{\\}}.$

Similarly, the _latency_ of $\mathsf{Consensus}$ is defined as

$\max_{\alpha\in\mathcal{E}(\mathsf{Consensus})}\bigg{\\{}\text{latency of
}\alpha\bigg{\\}}.$

##  4 DARE

This section presents DARE (Disperse, Agree, REtrieve), which is composed of
three algorithms:

  1. 1.

Disperser, which disperses the proposals;

  2. 2.

Agreement, which ensures agreement on the hash of a previously dispersed
proposal; and

  3. 3.

Retriever, which rebuilds the proposal corresponding to the agreed-upon hash.

We start by introducing the aforementioned building blocks (§ 4.1). Then, we
show how they are composed into DARE (§ 4.2). Finally, we prove the
correctness and complexity of DARE (§ 4.3).

###  4.1 Building Blocks: Overview

In this subsection, we formally define the three building blocks of DARE.
Concretely, we define their interface and properties, as well as their
complexity.

####  4.1.1 Disperser

Interface & properties. Disperser solves a problem similar to that of AVID
[26]. In a nutshell, each correct process aims to disperse its value to all
correct processes: eventually, all correct processes acquire a proof that a
value with a certain hash has been successfully dispersed.

Concretely, Disperser exposes the following interface:

  * •

request $\mathsf{disperse}(v\in\mathsf{Value})$: a process disperses a value
$v$; each correct process invokes $\mathsf{disperse}(v)$ exactly once and only
if $\mathsf{valid}(v)=\mathit{true}$.

  * •

indication
$\mathsf{acquire}(h\in\mathsf{Hash\\_Value},\Sigma_{h}\in\mathsf{T\\_Signature})$:
a process acquires a pair $(h,\Sigma_{h})$.

We say that a correct process _obtains_ a threshold signature (resp., a value)
if and only if it stores the signature (resp., the value) in its local memory.
(Obtained values can later be retrieved by all correct processes using
Retriever; see § 4.1.3 and Algorithm 1.) Disperser ensures the following:

  * •

_Integrity:_ If a correct process acquires a hash-signature pair
$(h,\Sigma_{h})$, then $\mathsf{verify\\_sig}(h,\Sigma_{h})=\mathit{true}$.

  * •

_Termination:_ Every correct process eventually acquires at least one hash-
signature pair.

  * •

_Redundancy:_ Let a correct process obtain a threshold signature $\Sigma_{h}$
such that $\mathsf{verify\\_sig}(h,\Sigma_{h})=\mathit{true}$, for some hash
value $h$. Then, (at least) $t+1$ correct processes have obtained a value $v$
such that (1) $\mathsf{hash}(v)=h$, and (2) $\mathsf{valid}(v)=\mathit{true}$.

Note that it is not required for all correct processes to acquire the same
hash value (nor the same threshold signature). Moreover, the specification
allows for multiple acquired pairs.

Complexity. Disperser exchanges $O(n^{1.5}L+n^{2.5}\kappa)$ bits after GST.
Moreover, it terminates in $O(n)$ time after GST.

Implementation. The details on Disperser’s implementation are relegated to §
5.

####  4.1.2 Agreement

Interface & properties. Agreement is a Byzantine consensus algorithm.555Recall
that the interface and properties of Byzantine consensus algorithms are
introduced in § 1. In Agreement, processes propose and decide pairs
$(h\in\mathsf{Hash\\_Value},\Sigma_{h}\in\mathsf{T\\_Signature})$; moreover,
$\mathsf{valid}(h,\Sigma_{h})\equiv\mathsf{verify\\_sig}(h,\Sigma_{h})$.

Complexity. Agreement achieves $O(n^{2}\kappa)$ bit complexity and $O(n)$
latency.

Implementation. We “borrow” the implementation from [36]. In brief, Agreement
is a “leader-based” consensus algorithm whose computation unfolds in views.
Each view has a single leader, and it employs a “leader-to-all, all-to-leader”
communication pattern. Agreement’s safety relies on standard techniques [88,
30, 23, 65]: (1) quorum intersection (safety within a view), and (2) “locking”
mechanism (safety across multiple views). As for liveness, Agreement
guarantees termination once all correct processes are in the same view (for
“long enough” time) with a correct leader. (For full details on Agreement, see
[36].)

####  4.1.3 Retriever

Interface & properties. In Retriever, each correct process starts with either
(1) some value, or (2) $\bot$. Eventually, all correct processes output the
same value. Formally, Retriever exposes the following interface:

  * •

request $\mathsf{input}(v\in\mathsf{Value}\cup\\{\bot\\})$: a process inputs a
value or $\bot$; each correct process invokes $\mathsf{input}(\cdot)$ exactly
once. Moreover, the following is assumed:

    * –

No two correct processes invoke $\mathsf{input}(v_{1}\in\mathsf{Value})$ and
$\mathsf{input}(v_{2}\in\mathsf{Value})$ with $v_{1}\neq v_{2}$.

    * –

At least $t+1$ correct processes invoke $\mathsf{input}(v\in\mathsf{Value})$
(i.e., $v\neq\bot)$.

  * •

indication $\mathsf{output}(v^{\prime}\in\mathsf{Value})$: a process outputs a
value $v^{\prime}$.

The following properties are ensured:

  * •

_Agreement:_ No two correct processes output different values.

  * •

_Validity:_ Let a correct process input a value $v$. No correct process
outputs a value $v^{\prime}\neq v$.

  * •

_Termination:_ Every correct process eventually outputs a value.

Complexity. Retriever exchanges $O(nL+n^{2}\log n)$ bits after GST (and before
every correct process outputs a value). Moreover, Retriever terminates in
$O(1)$ time after GST.

Implementation. Retriever’s implementation is “borrowed” from [43]. In
summary, Retriever relies on Reed-Solomon codes [81] to encode the input value
$v\neq\bot$ into $n$ symbols. Each correct process $Q$ which inputs
$v\neq\bot$ to Retriever encodes $v$ into $n$ RS symbols
$s_{1},s_{2},...,s_{n}$. $Q$ sends each RS symbol $s_{i}$ to the process
$P_{i}$. When $P_{i}$ receives $t+1$ identical RS symbols $s_{i}$, $P_{i}$ is
sure that $s_{i}$ is a “correct” symbol (i.e., it can be used to rebuild $v$)
as it was computed by at least one correct process. At this moment, $P_{i}$
broadcasts $s_{i}$. Once each correct process $P$ receives $2t+1$ (or more) RS
symbols, $P$ tries to rebuild $v$ (with some error-correction). (For full
details on Retriever, see [43].)

###  4.2 Pseudocode

Algorithm 1 gives DARE’s pseudocode. We explain it from the perspective of a
correct process $P_{i}$. An execution of DARE consists of three phases (each
of which corresponds to one building block):

  1. 1.

_Dispersal:_ Process $P_{i}$ disperses its proposal $v_{i}$ using Disperser
(line 9). Eventually, $P_{i}$ acquires a hash-signature pair
$(h_{i},\Sigma_{i})$ (line 10) due to the termination property of Disperser.

  2. 2.

_Agreement:_ Process $P_{i}$ proposes the previously acquired hash-signature
pair $(h_{i},\Sigma_{i})$ to Agreement (line 11). As Agreement satisfies
termination and agreement, all correct processes eventually agree on a hash-
signature pair $(h,\Sigma_{h})$ (line 12).

  3. 3.

_Retrieval:_ Once process $P_{i}$ decides $(h,\Sigma_{h})$ from Agreement, it
checks whether it has previously obtained a value $v$ with
$\mathsf{hash}(v)=h$ (line 13). If it has, $P_{i}$ inputs $v$ to Retriever;
otherwise, $P_{i}$ inputs $\bot$ (line 14). The required preconditions for
Retriever are met:

     * •

No two correct processes input different non-$\bot$ values to Retriever as
$\mathsf{hash}(\cdot)$ is collision-resistant.

     * •

At least $(t+1)$ correct processes input a value (and not $\bot$) to
Retriever. Indeed, as $\Sigma_{h}$ is obtained by a correct process, $t+1$
correct processes have obtained a value $v\neq\bot$ with $\mathsf{hash}(v)=h$
(due to redundancy of Disperser), and all of these processes input $v$.

Therefore, all correct processes (including $P_{i}$) eventually output the
same value $v^{\prime}$ from Retriever (due to the termination property of
Retriever; line 15), which represents the decision of DARE (line 16). Note
that $v^{\prime}=v\neq\bot$ due to the validity of Retriever.

Algorithm 1 DARE: Pseudocode (for process $P_{i}$)

1:Uses:

2: $\triangleright$ bits: $O(n^{1.5}L+n^{2.5}\kappa)$, latency: $O(n)$ (see §
5)

3: Disperser, instance $\mathit{disperser}$

4: $\triangleright$ bits: $O(n^{2}\kappa)$, latency: $O(n)$ (see [36])

5: Agreement, instance $\mathit{agreement}$

6: $\triangleright$ bits: $O(nL+n^{2}\log n)$, latency: $O(1)$ (see [43])

7: Retriever, instance $\mathit{retriever}$

8:upon $\mathsf{propose}(v_{i}\in\mathsf{Value})$:

9: invoke $\mathit{disperser}.\mathsf{disperse}(v_{i})$

10:upon
$\mathit{disperser}.\mathsf{acquire}(h_{i}\in\mathsf{Hash\\_Value},\Sigma_{i}\in\mathsf{T\\_Signature})$:

11: invoke $\mathit{agreement}.\mathsf{propose}(h_{i},\Sigma_{i})$

12:upon
$\mathit{agreement}.\mathsf{decide}(h\in\mathsf{Hash\\_Value},\Sigma_{h}\in\mathsf{T\\_Signature})$:
$\triangleright$ $P_{i}$ obtains $\Sigma_{h}$

13: $v\leftarrow$ an obtained value such that $\mathsf{hash}(v)=h$ (if such a
value was not obtained, $v=\bot$)

14: invoke $\mathit{retriever}.\mathsf{input}(v)$

15:upon $\mathit{retriever}.\mathsf{output}(\mathsf{Value}\text{
}v^{\prime})$:

16: trigger $\mathsf{decide}(v^{\prime})$

###  4.3 Proof of Correctness & Complexity

We start by proving the correctness of DARE.

######  Theorem 4.1.

DARE is correct.

######  Proof 4.2.

Every correct process starts the dispersal of its proposal (line 9). Due to
the termination property of Disperser, every correct process eventually
acquires a hash-signature pair (line 10). Hence, every correct process
eventually proposes to Agreement (line 11), which implies that every correct
process eventually decides the same hash-signature pair $(h,\Sigma_{h})$ from
Agreement (line 12) due to the agreement and termination properties of
Agreement.

As $(h,\Sigma_{h})$ is decided by all correct processes, at least $t+1$
correct processes $P_{i}$ have obtained a value $v$ such that (1)
$\mathsf{hash}(v)=h$, and (2) $\mathsf{valid}(v)=\mathit{true}$ (due to the
redundancy property of Disperser). Therefore, all of these correct processes
input $v$ to Retriever (line 14). Moreover, no correct process inputs a
different value (as $\mathsf{hash}(\cdot)$ is collision-resistant). Thus, the
conditions required by Retriever are met, which implies that all correct
processes eventually output the same valid value (namely, $v$) from Retriever
(line 15), and decide it (line 16).

Next, we prove the complexity of DARE.

######  Theorem 4.3.

DARE achieves $O(n^{1.5}L+n^{2.5}\kappa)$ bit complexity and $O(n)$ latency.

######  Proof 4.4.

As DARE is a sequential composition of its building blocks, its complexity is
the sum of the complexities of (1) Disperser, (2) Agreement, and (3)
Retriever. Hence, the bit complexity is

$\underbrace{O(n^{1.5}L+n^{2.5}\kappa)}_{\text{{Disperser}}}+\underbrace{O(n^{2}\kappa)}_{\text{{Agreement}}}+\underbrace{O(nL+n^{2}\log
n)}_{\text{{Retriever}}}=O(n^{1.5}L+n^{2.5}\kappa).$

Similarly, the latency is $O(n)$.

##  5 Disperser: Implementation & Analysis

This section focuses on Disperser. Namely, we present its implementation (§
5.1), and (informally) analyze its correctness and complexity (§ 5.2). Formal
proofs are can be found in Appendix A.

###  5.1 Implementation

Disperser’s pseudocode is given in Algorithm 2. In essence, each execution
unfolds in _views_ , where each view has $X$ _leaders_ ($0<X\leq n$ is a
generic parameter); the set of all views is denoted by $\mathsf{View}$. Given
a view $V$, $\mathsf{leaders}(V)$ denotes the $X$-sized set of leaders of the
view $V$. In each view, a leader disperses its value to $Y$-sized groups of
processes ($0<Y\leq n$ is a generic parameter) at a time (line 14), with a
$\delta$-waiting step in between (line 15). Before we thoroughly explain the
pseudocode, we introduce Sync, Disperser’s view synchronization [36, 88, 65]
algorithm.

Sync. Its responsibility is to bring all correct processes to the same view
with a correct leader for (at least) $\Delta=\delta\frac{n}{Y}+3\delta$ time.
Precisely, Sync exposes the following interface:

  * •

indication $\mathsf{advance}(V\in\mathsf{View})$: a process enters a new view
$V$.

Sync guarantees _eventual synchronization_ : there exists a time
$\tau_{\mathit{sync}}\geq\text{GST}$ (_synchronization time_) such that (1)
all correct processes are in the same view $V_{\mathit{sync}}$
(_synchronization view_) from time $\tau_{\mathit{sync}}$ to (at least) time
$\tau_{\mathit{sync}}+\Delta$, and (2) $V_{\mathit{sync}}$ has a correct
leader. We denote by $V_{\mathit{sync}}^{*}$ the smallest synchronization
view, whereas $\tau_{\mathit{sync}}^{*}$ denotes the first synchronization
time. Similarly, $V_{\mathit{max}}$ denotes the greatest view entered by a
correct process before GST.666When such a view does not exist,
$V_{\mathit{max}}=0$

The implementation of Sync (see § A.1) is highly inspired by RareSync, a view
synchronization algorithm introduced in [36]. In essence, when a process
enters a new view, it stays in the view for $O(\Delta)=O(\frac{n}{Y})$ time.
Once it wishes to proceed to the next view, the process engages in an “all-to-
all” communication step (which exchanges $O(n^{2}\kappa)$ bits); this step
signals the end of the current view, and the beginning of the next one.
Throughout views, leaders are rotated in a round-robin manner: each process is
a leader for exactly one view in any sequence of $\frac{n}{X}$ consecutive
views. As $O(\frac{n}{X})$ views (after GST) are required to reach a correct
leader, Sync exchanges $O(\frac{n}{X})\cdot
O(n^{2}\kappa)=O(\frac{n^{3}\kappa}{X})$ bits (before synchronization, i.e.,
before $\tau_{\mathit{sync}}^{*}+\Delta$); since each view takes
$O(\frac{n}{Y})$ time, synchronization is ensured within $O(\frac{n}{X})\cdot
O(\frac{n}{Y})=O(\frac{n^{2}}{XY})$ time.

Disperser relies on the following properties of Sync (along with eventual
synchronization):

  * •

_Monotonicity:_ Any correct process enters monotonically increasing views.

  * •

_Stabilization:_ Any correct process enters a view $V\geq V_{\mathit{max}}$ by
time $\text{GST}+3\delta$.

  * •

_Limited entrance:_ In the time period $[\text{GST},\text{GST}+3\delta)$, any
correct process enters $O(1)$ views.

  * •

_Overlapping:_ For any view $V>V_{\mathit{max}}$, all correct processes
overlap in $V$ for (at least) $\Delta$ time.

  * •

_Limited synchronization view:_
$V_{\mathit{sync}}^{*}-V_{\mathit{max}}=O(\frac{n}{X})$.

  * •

_Complexity:_ Sync exchanges $O(\frac{n^{3}\kappa}{X})$ bits during the time
period $[\text{GST},\tau_{\mathit{sync}}^{*}+\Delta]$, and it synchronizes all
correct processes within $O(\frac{n^{2}}{XY})$ time after GST
($\tau_{\mathit{sync}}^{*}+\Delta-\text{GST}=O(\frac{n^{2}}{XY})$).

The aforementioned properties of Sync are formally proven in § A.1.

Algorithm description. Correct processes transit through views based on Sync’s
indications (line 10): when a correct process receives $\mathsf{advance}(V)$
from Sync, it stops participating in the previous view and starts
participating in $V$.

Once a correct leader $P_{l}$ enters a view $V$, it disperses its proposal via
dispersal messages. As already mentioned, $P_{l}$ sends its proposal to
$Y$-sized groups of processes (line 14) with a $\delta$-waiting step in
between (line 15). When a correct (non-leader) process $P_{i}$ (which
participates in the view $V$) receives a dispersal message from $P_{l}$,
$P_{i}$ checks whether the dispersed value is valid (line 17). If it is,
$P_{i}$ partially signs the hash of the value, and sends it back to $P_{l}$
(line 20). When $P_{l}$ collects $2t+1$ ack messages, it (1) creates a
threshold signature for the hash of its proposal (line 24), and (2) broadcasts
the signature (along with the hash of its proposal) to all processes via a
confirm message (line 25). Finally, when $P_{l}$ (or any other correct
process) receives a confirm message (line 27), it (1) acquires the received
hash-signature pair (line 28), (2) disseminates the pair to “help” the other
processes (line 29), and (3) stops executing Disperser (line 30).

Algorithm 2 Disperser: Pseudocode (for process $P_{i}$)

1:Uses:

2: Sync, instance $\mathit{sync}$ $\triangleright$ ensures a
$\Delta=\delta\frac{n}{Y}+3\delta$ overlap in a view with a correct leader

3:upon $\mathsf{init}$:

4: $\mathsf{Value}$ $\mathit{proposal}_{i}\leftarrow\bot$

5: $\mathsf{Integer}$ $\mathit{received\\_acks}_{i}\leftarrow 0$

6: $\mathsf{Map}(\mathsf{Hash\\_Value}\to\mathsf{Value})$
$\mathit{obtained\\_values}_{i}\leftarrow\text{empty}$

7:upon $\mathsf{disperse}(\mathsf{Value}\text{ }v_{i})$:

8: $\mathit{proposal}_{i}\leftarrow v_{i}$

9: start $\mathit{sync}$

10:upon $\mathit{sync}.\mathsf{advance}(\mathsf{View}\text{ }V)$:
$\triangleright$ $P_{i}$ stops participating in the previous view

11: $\triangleright$ First part of the view

12: if $P_{i}\in\mathsf{leaders}(V)$:

13: for $\mathsf{Integer}\text{ }k\leftarrow 1\text{ to }\frac{n}{Y}$:

14: send $\langle\textsc{dispersal},\mathit{proposal}_{i}\rangle$ to
$P_{(k-1)Y+1},P_{(k-1)Y+2},...,P_{kY}$

15: wait $\delta$ time

16: every process:

17: upon reception of $\langle\textsc{dispersal},\mathsf{Value}\text{
}v_{j}\rangle$ from process $P_{j}\in\mathsf{leaders}(V)$ and
$\mathsf{valid}(v_{j})=\mathit{true}$:

18: $\mathsf{Hash\\_Value}$ $h\leftarrow\mathsf{hash}(v_{j})$

19: $\mathit{obtained\\_values}_{i}[h]\leftarrow v_{j}$

20: send $\langle\textsc{ack},\mathsf{share\\_sign}_{i}(h)\rangle$ to $P_{j}$

21: $\triangleright$ Second part of the view

22: if $P_{i}\in\mathsf{leaders}(V)$:

23: upon exists $\mathsf{Hash\\_Value}$ $h$ such that
$\langle\textsc{ack},h,\cdot\rangle$ has been received from $2t+1$ processes:

24: $\mathsf{T\\_Signature}$
$\Sigma_{h}\leftarrow\mathsf{combine}\big{(}\\{\mathsf{P\\_Signature}\text{
}\mathit{sig}\,|\,\mathit{sig}\text{ is received in the {ack}
messages}\\}\big{)}$

25: broadcast $\langle\textsc{confirm},h,\Sigma_{h}\rangle$

26: every process:

27: upon reception of $\langle\textsc{confirm},\mathsf{Hash\\_Value}\text{
}h,\mathsf{T\\_Signature}\text{ }\Sigma_{h}\rangle$ and
$\mathsf{verify\\_sig}(h,\Sigma_{h})=\mathit{true}$:

28: trigger $\mathsf{acquire}(h,\Sigma_{h})$

29: broadcast $\langle\textsc{confirm},h,\Sigma_{h}\rangle$

30: stop executing Disperser (and Sync)

###  5.2 Analysis

Correctness. Once all correct processes synchronize in the view
$V_{\mathit{sync}}^{*}$ (the smallest synchronization view), all correct
processes acquire a hash-signature pair. Indeed,
$\Delta=\delta\frac{n}{Y}+3\delta$ time is sufficient for a correct leader
$P_{l}\in\mathsf{leaders}(V_{\mathit{sync}}^{*})$ to (1) disperse its proposal
$\mathit{proposal}_{l}$ to all processes (line 14), (2) collect $2t+1$ partial
signatures for $h=\mathsf{hash}(\mathit{proposal}_{l})$ (line 23), and (3)
disseminate a threshold signature for $h$ (line 25). When a correct process
receives the aforementioned threshold signature (line 27), it acquires the
hash-signature pair (line 28) and stops executing Disperser (line 30).

Complexity. Disperser terminates once all correct processes are synchronized
in a view with a correct leader. The synchronization is ensured in
$O(\frac{n^{2}}{XY})$ time after GST (as
$\tau_{\mathit{sync}}^{*}+\Delta-\text{GST}=O(\frac{n^{2}}{XY})$). Hence,
Disperser terminates in $O(\frac{n^{2}}{XY})$ time after GST.

Let us analyze the number of bits Disperser exchanges. Any execution of
Disperser can be separated into two post-GST periods: (1) _unsynchronized_ ,
from GST until $\text{GST}+3\delta$, and (2) _synchronized_ , from
$\text{GST}+3\delta$ until $\tau_{\mathit{sync}}^{*}+\Delta$. First, we study
the number of bits correct processes send via dispersal, ack and confirm
message in the aforementioned periods:

  * •

Unsynchronized period: Due to the $\delta$-waiting step (line 15), each
correct process sends dispersal messages (line 14) to (at most) $3=O(1)$
$Y$-sized groups. Hence, each correct process sends $O(1)\cdot O(Y)\cdot
L=O(YL)$ bits through dispersal messages.

Due to the limited entrance property of Sync, each correct process enters
$O(1)$ views during the unsynchronized period. In each view, each correct
process sends (at most) $O(X)$ ack messages (one to each leader; line 20) and
$O(n)$ confirm messages (line 25). As each ack and confirm message carries
$\kappa$ bits, all correct processes send

$\begin{split}&n\cdot\big{(}\underbrace{O(YL)}_{\text{{dispersal}}}+\underbrace{O(X\kappa)}_{\text{{ack}}}+\underbrace{O(n\kappa)}_{\text{{confirm}}}\big{)}\\\
&=O(nYL+n^{2}\kappa)\text{ bits via {dispersal}, {ack} and {confirm}
messages.}\end{split}$

  * •

Synchronized period: Recall that all correct processes acquire a hash-
signature pair (and stop executing Disperser) by time
$\tau_{\mathit{sync}}^{*}+\Delta$, and they do so in the view
$V_{\mathit{sync}}^{*}$. As correct processes enter monotonically increasing
views, no correct process enters a view greater than $V_{\mathit{sync}}^{*}$.

By the stabilization property of Sync, each correct process enters a view
$V\geq V_{\mathit{max}}$ by time $\text{GST}+3\delta$. Moreover, until
$\tau_{\mathit{sync}}^{*}+\Delta$, each correct process enters (at most)
$O(\frac{n}{X})$ views (due to the limited synchronization view and
monotonicity properties of Sync). Importantly, no correct leader exists in any
view $V$ with $V_{\mathit{max}}<V<V_{\mathit{sync}}^{*}$; otherwise,
$V=V_{\mathit{sync}}^{*}$ as processes overlap for $\Delta$ time in $V$ (due
to the overlapping property of Sync). Hence, for each view $V$ with
$V_{\mathit{max}}<V<V_{\mathit{sync}}^{*}$, all correct processes send
$O(nX\kappa)$ bits (all through ack messages; line 20). In $V_{\mathit{max}}$
and $V_{\mathit{sync}}^{*}$, all correct processes send (1) $2\cdot O(XnL)$
bits through dispersal messages (line 14), (2) $2\cdot O(nX\kappa)$ bits
through ack messages (line 20), and (3) $2\cdot O(Xn\kappa)$ bits through
confirm messages (line 25). Therefore, all correct processes send

$\begin{split}&\underbrace{O(\frac{n}{X})}_{\text{$V_{\mathit{sync}}^{*}-V_{\mathit{max}}$}}\cdot\underbrace{O(nX\kappa)}_{\text{{ack}}}+\underbrace{O(XnL)}_{\text{{dispersal}
in $V_{\mathit{max}}$ and
$V_{\mathit{sync}}^{*}$}}+\underbrace{O(nX\kappa)}_{\text{{ack} in
$V_{\mathit{max}}$ and
$V_{\mathit{sync}}^{*}$}}+\underbrace{O(Xn\kappa)}_{\text{{confirm} in
$V_{\mathit{max}}$ and $V_{\mathit{sync}}^{*}$}}\\\ &=O(nXL+n^{2}\kappa)\text{
bits via {dispersal}, {ack} and {confirm} messages.}\end{split}$

We cannot neglect the complexity of Sync, which exchanges
$O(\frac{n^{3}\kappa}{X})$ bits during the time period
$[\text{GST},\tau_{\mathit{sync}}^{*}+\Delta]$. Hence, the total number of
bits Disperser exchanges is

$\underbrace{O(nYL+n^{2}\kappa)}_{\text{unsynchronized
period}}+\underbrace{O(nXL+n^{2}\kappa)}_{\text{synchronized
period}}+\underbrace{O(\frac{n^{3}\kappa}{X})}_{\text{{Sync}}}=O(nYL+nXL+\frac{n^{3}\kappa}{X}).$

With $X=Y=\sqrt{n}$, Disperser terminates in optimal $O(n)$ time, and
exchanges $O(n^{1.5}L+n^{2.5}\kappa)$ bits. Our analysis is illustrated in
Figure 4.

Figure 4: Illustration of Disperser’s bit complexity.

##  6 DARE-Stark

In this section, we present DARE-Stark, a variant of DARE which relies on
STARK proofs. Importantly, DARE-Stark achieves
$O(nL+n^{2}\mathit{poly}(\kappa))$ bit complexity, nearly tight to the
$\Omega(nL+n^{2})$ lower bound, while preserving optimal $O(n)$ latency.

First, we revisit Disperser, pinpointing its complexity on proving RS encoding
(§ 6.1). We then provide an overview on STARKs, a cryptographic primitive
providing succinct proofs of knowledge (§ 6.2). We finally present DARE-Stark,
which uses STARKs for provable RS encoding, thus improving on DARE’s
complexity (§ 6.3).

###  6.1 Revisiting DARE: What Causes Disperser’s Complexity?

Recall that Disperser exchanges $O(n^{1.5}L+n^{2.5}\kappa)$ bits. This is due
to a fundamental requirement of Retriever: at least $t+1$ correct processes
must have obtained the value $v$ by the time Agreement decides
$h=\mathsf{hash}(v)$. Retriever leverages this requirement to prove the
correct encoding of RS symbols. In brief (as explained in § 4.1.3): (1) every
correct process $P$ that obtained $v\neq\bot$ encodes it in $n$ RS symbols
$s_{1},\ldots,s_{n}$; (2) $P$ sends each $s_{i}$ to $P_{i}$; (3) upon
receiving $t+1$ identical copies of $s_{i}$, $P_{i}$ can trust $s_{i}$ to be
the $i$-th RS symbol for $v$ (note that $s_{i}$ can be trusted only because it
was produced by at least one correct process - nothing else proves $s_{i}$’s
relationship to $v$!); (4) every correct process $P_{i}$ disseminates $s_{i}$,
enabling the reconstruction of $v$ by means of error-correcting decoding. In
summary, DARE bottlenecks on Disperser, and Disperser’s complexity is owed to
the need to prove the correct encoding of RS symbols in Retriever. Succinct
arguments of knowledge (such as STARKs), however, allow to publicly prove the
relationship between an RS symbol and the value it encodes, eliminating the
need to disperse the entire value to $t+1$ correct processes – a dispersal of
provably correct RS symbols suffices. DARE-Stark builds upon this idea.

###  6.2 STARKs

First introduced in [16], STARKs are succinct, universal, transparent
arguments of knowledge. For any function $f$ (computable in polynomial time)
and any (polynomially-sized) $y$, a STARK can be used to prove the knowledge
of some $x$ such that $f(x)=y$. Remarkably, the size of a STARK proof is
$O(\mathit{poly}(\kappa))$. At a very high level, a STARK proof is produced as
follows: (1) the computation of $f(x)$ is unfolded on an execution trace; (2)
the execution trace is (RS) over-sampled for error amplification; (3) the
correct computation of $f$ is expressed as a set of algebraic constraints over
the trace symbols; (4) the trace symbols are organized in a Merkle tree [71];
(5) the tree’s root is used as a seed to pseudo-randomly sample the trace
symbols. The resulting collection of Merkle proofs proves that, for some known
(but not revealed) $x$, $f(x)\neq y$ only with cryptographically low
probability (negligible in $\kappa$). STARKs are non-interactive, require no
trusted setup (they are transparent), and their security reduces to that of
cryptographic hashes in the Random Oracle Model (ROM) [13].

###  6.3 Implementation

Provably correct encoding. At its core, DARE-Stark uses STARKs to attest the
correct RS encoding of values. For every $i\in[1,n]$, we define
$\mathsf{shard}_{i}(\cdot)$ by

$\mathsf{shard}_{i}(v\in\mathsf{Value})=\begin{cases}\big{(}\mathsf{hash}(v),\mathsf{encode}_{i}(v)\big{)},&\text{if
and only if}\;\mathsf{valid}(v)=\mathit{true}\\\
\bot,&\text{otherwise,}\end{cases}$ (1)

where $\mathsf{encode}_{i}(v)$ represents the $i$-th RS symbol obtained from
$\mathsf{encode}(v)$ (see § 3). We use $\mathsf{proof}_{i}(v)$ to denote the
STARK proving the correct computation of $\mathsf{shard}_{i}(v)$. The design
and security of DARE-Stark rests on the following theorem.

######  Theorem 6.1.

Let $i_{1},\ldots,i_{t+1}$ be distinct indices in $[1,n]$. Let $h$ be a hash,
let $s_{1},\ldots,s_{t+1}$ be RS symbols, let
$\mathit{stark}_{1},\ldots,\mathit{stark}_{t+1}$ be STARK proofs such that,
for every $k\in[1,t+1]$, $\mathit{stark}_{k}$ proves knowledge of some
(undisclosed) $v_{k}$ such that $\mathsf{shard}_{i_{k}}(v_{k})=(h,s_{k})$. We
have that

$v=\mathsf{decode}(\\{s_{1},\ldots,s_{k}\\})$

satisfies $\mathsf{valid}(v)=\mathit{true}$ and $\mathsf{hash}(v)=h$.

######  Proof 6.2.

For all $k$, by the correctness of $\mathit{stark}_{k}$ and Equation 1, we
have that (1) $h=\mathsf{hash}(v_{k})$, (2)
$s_{k}=\mathsf{encode}_{i_{k}}(v_{k})$, and (3)
$\mathsf{valid}(v_{k})=\mathit{true}$. By the collision-resistance of
$\mathsf{hash}(\cdot)$, for all $k,k^{\prime}$, we have
$v_{k}=v_{k}^{\prime}$. By the definition of $\mathsf{encode}(\cdot)$ and
$\mathsf{decode}(\cdot)$, we then have

$v=\mathsf{decode}(\\{s_{1},\ldots,s_{k}\\})=v_{1}=\ldots=v_{t+1},$

which implies that $\mathsf{valid}(v)=\mathit{true}$ and $\mathsf{hash}(v)=h$.

Algorithm 3 DARE-Stark: Pseudocode (for process $P_{i}$)

1:Uses:

2: Agreement, instance $\mathit{agreement}$

3:upon $\mathsf{init}$:

4: $\mathsf{Hash\\_Value}$ $\mathit{proposed\\_hash}_{i}\leftarrow\bot$

5:
$\mathsf{Map}\big{(}\mathsf{Hash\\_Value}\to(\mathsf{Symbol},\mathsf{STARK})\big{)}$
$\mathit{proposal\\_shards}_{i}\leftarrow\text{empty}$

6:
$\mathsf{Map}\big{(}\mathsf{Hash\\_Value}\to\mathsf{Set}(\mathsf{Symbol})\big{)}$
$\mathit{decision\\_symbols}_{i}\leftarrow\text{empty}$

7: $\mathsf{Bool}$ $\mathit{decided}_{i}\leftarrow\mathit{false}$

8:$\triangleright$ Dispersal

9:upon $\mathsf{propose}(\mathsf{Value}\text{ }v_{i})$:

10: $\mathit{proposed\\_hash}_{i}\leftarrow\mathsf{hash}(v_{i})$

11: for $\mathsf{Integer}\text{ }k\leftarrow 1\text{ to }n$:

12: $(\mathsf{Hash}\text{ }h_{k},\mathsf{Symbol}\text{
}s_{k})\leftarrow\mathsf{shard}_{k}(v_{i})$

13: $\mathsf{STARK}$ $\mathit{stark}_{k}\leftarrow\mathsf{proof}_{k}(v_{i})$

14: send $\langle\textsc{dispersal},h_{k},s_{k},\mathit{stark}_{k}\rangle$ to
$P_{k}$

15:upon reception of $\langle\textsc{dispersal},\mathsf{Hash\\_Value}\text{
}h,\mathsf{Symbol}\text{ }s,\mathsf{STARK}\text{ }\mathit{stark}\rangle$ from
process $P_{j}$ and $\mathit{stark}$ proves $\mathsf{shard}_{i}(?)=(h,s)$:

16: $\mathit{proposal\\_shards}_{i}[h]\leftarrow(s,\mathit{stark})$

17: send $\langle\textsc{ack},\mathsf{share\\_sign}_{i}(h)\rangle$ to $P_{j}$

18:$\triangleright$ Agreement

19:upon $\langle\textsc{ack},\mathsf{P\\_Signature}\text{
}\mathit{sig}\rangle$ is received from $2t+1$ processes:

20: $\mathsf{T\\_Signature}$
$\Sigma\leftarrow\mathsf{combine}\big{(}\\{\mathit{sig}\,|\,\mathit{sig}\text{
is received in the {ack} messages}\\}\big{)}$

21: invoke
$\mathit{agreement}.\mathsf{propose}(\mathit{proposed\\_hash}_{i},\Sigma)$

22:upon $\mathit{agreement}.\mathsf{decide}(\mathsf{Hash\\_Value}\text{
}h,\mathsf{T\\_Signature}\text{ }\Sigma)$ with
$\mathit{proposal\\_shards}_{i}[h]\neq\bot$:

23: $(\mathsf{Symbol}\text{ }s,\mathsf{STARK}\text{
}\mathit{stark})\leftarrow\mathit{proposal\\_shards}_{i}[h]$

24: broadcast $\langle\textsc{retrieve},h,s,\mathit{stark}\rangle$

25:$\triangleright$ Retrieval

26:upon reception of $\langle\textsc{retrieve},\mathsf{Hash\\_Value}\text{
}h,\mathsf{Symbol}\text{ }s,\mathsf{STARK}\text{ }\mathit{stark}\rangle$ from
process $P_{j}$ and $\mathit{stark}$ proves $\mathsf{shard}_{j}(?)=(h,s)$:

27:
$\mathit{decision\\_symbols}_{i}[h]\leftarrow\mathit{decision\\_symbols}_{i}[h]\cup\\{s\\}$

28:upon (1) exists $\mathsf{Hash\\_Value}$ $h$ such that
$\mathit{decision\\_symbols}_{i}[h]$ has $t+1$ elements, and (2)
$\mathit{decided}_{i}=\mathit{false}$:

29: $\mathit{decided}_{i}\leftarrow\mathit{true}$

30: trigger
$\mathsf{decide}\big{(}\mathsf{decode}(\mathit{decision\\_symbols}_{i}[h])\big{)}$

Algorithm description. The pseudocode of DARE-Stark is presented in Algorithm
3 from the perspective of a correct process $P_{i}$. Similarly to DARE, DARE-
Stark unfolds in three phases:

  1. 1.

_Dispersal:_ Upon proposing a value $v_{i}$ (line 9), $P_{i}$ sends (line 14)
to each process $P_{k}$ (1) $(h_{k},s_{k})=\mathsf{shard}_{k}(v_{i})$
(computed at line 12), and (2) $\mathit{stark}_{k}=\mathsf{proof}_{k}(v_{i})$
(computed at line 13). In doing so (see Theorem 6.1), $P_{i}$ proves to
$P_{k}$ that $h_{k}=\mathsf{hash}(v_{i})$ is the hash of a valid proposal,
whose $k$-th RS symbol is $\mathsf{encode}_{k}(v_{i})$. $P_{k}$ checks
$\mathit{stark}_{k}$ against $(h_{k},s_{k})$ (line 15), stores
$(s_{k},\mathit{stark}_{k})$ (line 16), and sends a partial signature for
$h_{k}$ back to $P_{i}$ (line 17).

  2. 2.

_Agreement:_ Having collected a threshold signature $\Sigma$ for
$\mathsf{hash}(v_{i})$ (line 20), $P_{i}$ proposes
$(\mathsf{hash}(v_{i}),\Sigma)$ to Agreement (line 21).

  3. 3.

_Retrieval:_ Upon deciding a hash $h$ from Agreement (line 22), $P_{i}$
broadcasts (if available) the $i$-th RS symbol for $h$, along with the
relevant proof (line 24). Upon receiving $t+1$ symbols $S$ for the same hash
(line 28), $P_{i}$ decides $\mathsf{decode}(S)$ (line 30).

Analysis. Upon proposing a value $v_{i}$ (line 9), a correct process $P_{i}$
sends $\mathsf{shard}_{k}(v_{i})$ and $\mathsf{proof}_{k}(v_{i})$ to each
process $P_{k}$ (line 14). Checking $\mathsf{proof}_{k}(v_{i})$ against
$\mathsf{shard}_{k}(v_{i})$ (line 15), $P_{k}$ confirms having received the
$k$-th RS symbol for $v_{i}$ (note that this does not require the transmission
of $v_{i}$, just $\mathsf{hash}(v_{i})$). As $2t+1$ processes are correct,
$P_{i}$ is guaranteed to eventually gather a $(2t+1)$-threshold signature
$\Sigma$ for $\mathsf{hash}(v_{i})$ (line 20). Upon doing so, $P_{i}$ proposes
$(\mathsf{hash}(v_{i}),\Sigma)$ to Agreement (line 21). Since every correct
process eventually proposes a value to Agreement, every correct process
eventually decides some hash $h$ from Agreement (line 22). Because $2t+1$
processes signed $h$, at least $t+1$ correct processes (without loss of
generality, $P_{1},\ldots,P_{t+1}$) received a correctly encoded RS-symbol for
$h$. More precisely, for every $k\in[1,t+1]$, $P_{k}$ received and stored the
$k$-th RS symbol encoded from the pre-image $v$ of $h$. Upon deciding from
Agreement, each process $P_{k}$ broadcasts its RS symbol, along with the
relevant proof (line 24). Because at most $t$ processes are faulty, no correct
process receives $t+1$ RS symbols pertaining to a hash other than $h$. As
$P_{1},\ldots,P_{t+1}$ all broadcast their symbols and proofs, eventually
every correct process collects $t+1$ (provably correct) RS symbols $S$
pertaining to $h$ (line 28), and decides $\mathsf{decode}(S)$ (line 30). By
Theorem 6.1, every correct process eventually decides the same valid value $v$
(with $h=\mathsf{hash}(v)$).

Concerning bit complexity, throughout an execution of DARE-Stark, a correct
process engages once in Agreement (which exchanges $O(n^{2}\kappa)$ bits in
total) and sends: (1) $n$ dispersal messages, each of size
$O(\frac{L}{n}+\mathit{poly}(\kappa))$, (2) $n$ ack messages, each of size
$O(\kappa)$, and (3) $n$ retrieve messages, each of size
$O(\frac{L}{n}+\mathit{poly}(\kappa))$. Therefore, the bit complexity of DARE-
Stark is $O(nL+n^{2}\mathit{poly}(\kappa))$. As for the latency, it is $O(n)$
(due to the linear latency of Agreement).

##  7 Concluding Remarks

This paper introduces DARE (Disperse, Agree, REtrieve), the first partially
synchronous Byzantine agreement algorithm on values of $L$ bits with better
than $O(n^{2}L)$ bit complexity and sub-exponential latency. DARE achieves
$O(n^{1.5}L+n^{2.5}\kappa)$ bit complexity ($\kappa$ is the security
parameter) and optimal $O(n)$ latency, which is an effective $\sqrt{n}$ factor
bit-improvement for $L\geq n\kappa$ (typical in practice). DARE achieves its
complexity in two steps. First, DARE decomposes problem of agreeing on large
values ($L$ bits) into three sub-problems: (1) value dispersal, (2) validated
agreement on small values ($O(\kappa)$), and (3) value retrieval. (DARE
effectively acts as an extension protocol for Byzantine agreement.) Second,
DARE’s novel dispersal algorithm solves the main challenge, value dispersal,
using only $O(n^{1.5}L)$ bits and linear latency.

Moreover, we prove that the lower bound of $\Omega(nL+n^{2})$ is near-tight by
matching it near-optimally with DARE-Stark, a modified version of DARE using
STARK proofs that reaches $O(nL+n^{2}\mathit{poly}(\kappa))$ bits and
maintains optimal $O(n)$ latency. We hope DARE-Stark motivates research into
more efficient STARK schemes in the future, which currently have large hidden
constants affecting their practical use.

## References

  * [1] Michael Abd-El-Malek, Gregory R Ganger, Garth R Goodson, Michael K Reiter, and Jay J Wylie.  Fault-scalable byzantine fault-tolerant services.  ACM SIGOPS Operating Systems Review, 39(5):59–74, 2005.
  * [2] Ittai Abraham and Gilad Asharov.  Gradecast in synchrony and reliable broadcast in asynchrony with optimal resilience, efficiency, and unconditional security.  In Alessia Milani and Philipp Woelfel, editors, PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, pages 392–398. ACM, 2022.  doi:10.1145/3519270.3538451.
  * [3] Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi.  Communication Complexity of Byzantine Agreement, Revisited.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, page 317–326, New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3293611.3331629.
  * [4] Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman.  Solida: A blockchain protocol based on reconfigurable byzantine consensus.  arXiv preprint arXiv:1612.02916, 2016.
  * [5] Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman.  Solidus: An incentive-compatible cryptocurrency based on permissionless byzantine consensus.  CoRR, abs/1612.02916, 2016.
  * [6] Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman.  Asymptotically Optimal Validated Asynchronous Byzantine Agreement.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 337–346, 2019.
  * [7] Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman.  Asymptotically Optimal Validated Asynchronous Byzantine Agreement.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 337–346, 2019.
  * [8] Atul Adya, William J Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R Douceur, Jon Howell, Jacob R Lorch, Marvin Theimer, and Roger P Wattenhofer.  Farsite: Federated, available, and reliable storage for an incompletely trusted environment.  ACM SIGOPS Operating Systems Review, 36(SI):1–14, 2002.
  * [9] Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang.  Brief announcement: Asynchronous verifiable information dispersal with near-optimal communication.  In Alessia Milani and Philipp Woelfel, editors, PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, pages 418–420. ACM, 2022.  doi:10.1145/3519270.3538476.
  * [10] Nicolas Alhaddad, Sisi Duan, Mayank Varia, and Haibin Zhang.  Succinct Erasure Coding Proof Systems.  Cryptology ePrint Archive, 2021.
  * [11] Yair Amir, Claudiu Danilov, Jonathan Kirsch, John Lane, Danny Dolev, Cristina Nita-Rotaru, Josh Olsen, and David Zage.  Scaling byzantine fault-tolerant replication towide area networks.  In International Conference on Dependable Systems and Networks (DSN’06), pages 105–114. IEEE, 2006.
  * [12] Elli Androulaki, Christian Cachin, Dan Dobre, and Marko Vukolic.  Erasure-coded byzantine storage with separate metadata.  In Marcos K. Aguilera, Leonardo Querzoni, and Marc Shapiro, editors, Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Cortina d’Ampezzo, Italy, December 16-19, 2014. Proceedings, volume 8878 of Lecture Notes in Computer Science, pages 76–90. Springer, 2014.  doi:10.1007/978-3-319-14472-6\\_6.
  * [13] Mihir Bellare and Phillip Rogaway.  Random oracles are practical: A paradigm for designing efficient protocols.  In Proceedings of the 1st ACM Conference on Computer and Communications Security, pages 62–73, 1993.
  * [14] Michael Ben-Or, Ran Canetti, and Oded Goldreich.  Asynchronous Secure Computation.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 52–61, 1993.
  * [15] Michael Ben-Or, Boaz Kelmer, and Tal Rabin.  Asynchronous Secure Computations with Optimal Resilience.  In Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, pages 183–192, 1994.
  * [16] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev.  Scalable, transparent, and post-quantum secure computational integrity.  Cryptology ePrint Archive, 2018.
  * [17] Alysson Bessani, João Sousa, and Eduardo EP Alchieri.  State Machine Replication for the Masses with BFT-SMART.  In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 355–362. IEEE, 2014.
  * [18] Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, and Kartik Nayak.  Efficient adaptively-secure byzantine agreement for long messages.  In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part I, volume 13791 of Lecture Notes in Computer Science, pages 504–525. Springer, 2022.  doi:10.1007/978-3-031-22963-3\\_17.
  * [19] Richard E Blahut.  Theory and practice of error control codes, volume 126.  Addison-Wesley Reading, 1983.
  * [20] Manuel Bravo, Gregory Chockler, and Alexey Gotsman.  Making Byzantine Consensus Live.  In 34th International Symposium on Distributed Computing (DISC), volume 179, pages 1–17, 2020.
  * [21] Manuel Bravo, Gregory V. Chockler, and Alexey Gotsman.  Making byzantine consensus live.  Distributed Comput., 35(6):503–532, 2022.  doi:10.1007/s00446-022-00432-y.
  * [22] Ethan Buchman.  Tendermint: Byzantine fault tolerance in the age of blockchains.  PhD thesis, University of Guelph, 2016.
  * [23] Ethan Buchman, Jae Kwon, and Zarko Milosevic.  The latest gossip on BFT consensus.  arXiv preprint arXiv:1807.04938, pages 1–14, 2018.  URL: https://arxiv.org/pdf/1807.04938.pdf, arXiv:1807.04938.
  * [24] Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues.  Introduction to Reliable and Secure Distributed Programming (2. ed.).  Springer, 2011.  doi:10.1007/978-3-642-15260-3.
  * [25] Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup.  Secure and Efficient Asynchronous Broadcast Protocols.  In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, pages 524–541. Springer, 2001.  doi:10.1007/3-540-44647-8\\_31.
  * [26] Christian Cachin and Stefano Tessaro.  Asynchronous Verifiable Information Dispersal.  In 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05), pages 191–201. IEEE, 2005.
  * [27] Martina Camaioni, Rachid Guerraoui, Matteo Monti, Pierre-Louis Roman, Manuel Vidigueira, and Gauthier Voron.  Chop chop: Byzantine atomic broadcast to the network limit.  arXiv preprint arXiv:2304.07081, 2023.
  * [28] Jan Camenisch, Manu Drijvers, Timo Hanke, Yvonne Anne Pignolet, Victor Shoup, and Dominic Williams.  Internet Computer Consensus.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 2021:81–91, 2022.  doi:10.1145/3519270.3538430.
  * [29] Miguel Castro and Barbara Liskov.  Practical byzantine fault tolerance and proactive recovery.  ACM Transactions on Computer Systems (TOCS), 20(4):398–461, 2002\.
  * [30] Miguel Castro and Barbara Liskov.  Practical byzantine fault tolerance and proactive recovery.  ACM Transactions on Computer Systems (TOCS), 20(4):398–461, 2002\.
  * [31] Dario Catalano and Dario Fiore.  Vector Commitments and Their Applications.  In Public-Key Cryptography–PKC 2013: 16th International Conference on Practice and Theory in Public-Key Cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings 16, pages 55–72. Springer, 2013.
  * [32] Jing Chen and Silvio Micali.  Algorand.  arXiv preprint arXiv:1607.01341, 2016.
  * [33] Jinyuan Chen.  Fundamental limits of byzantine agreement.  CoRR, abs/2009.10965, 2020.  URL: https://arxiv.org/abs/2009.10965, arXiv:2009.10965.
  * [34] Jinyuan Chen.  Optimal error-free multi-valued byzantine agreement.  In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 17:1–17:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.DISC.2021.17.
  * [35] Ashish Choudhury and Arpita Patra.  On the communication efficiency of statistically secure asynchronous MPC with optimal resilience.  J. Cryptol., 36(2):13, 2023.  doi:10.1007/s00145-023-09451-9.
  * [36] Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira.  Byzantine Consensus Is $\Theta(n^{2})$: The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!  In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 14:1–14:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.DISC.2022.14.
  * [37] Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira.  On the Validity of Consensus.  To appear in PODC 2023, abs/2301.04920, 2023.  arXiv:2301.04920, doi:10.48550/arXiv.2301.04920.
  * [38] Miguel Correia.  From byzantine consensus to blockchain consensus.  In Essentials of Blockchain Technology, pages 41–80. Chapman and Hall/CRC, 2019.
  * [39] Miguel Correia, Nuno Ferreira Neves, and Paulo Veríssimo.  From Consensus to Atomic Broadcast: Time-Free Byzantine-Resistant Protocols without Signatures.  The Computer Journal, 49(1):82–96, 2006.
  * [40] Tyler Crain, Vincent Gramoli, Mikel Larrea, and Michel Raynal.  Dbft: Efficient leaderless byzantine consensus and its application to blockchains.  In 2018 IEEE 17th International Symposium on Network Computing and Applications (NCA), pages 1–8. IEEE, 2018.
  * [41] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman.  Narwhal and tusk: a dag-based mempool and efficient bft consensus.  In Proceedings of the Seventeenth European Conference on Computer Systems, pages 34–50, 2022.
  * [42] Sourav Das, Vinith Krishnan, Irene Miriam Isaac, and Ling Ren.  Spurt: Scalable distributed randomness beacon with transparent setup.  In 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022, pages 2502–2517. IEEE, 2022.  doi:10.1109/SP46214.2022.9833580.
  * [43] Sourav Das, Zhuolun Xiang, and Ling Ren.  Asynchronous Data Dissemination and its Applications.  In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 2705–2721, 2021.
  * [44] Sourav Das, Thomas Yurek, Zhuolun Xiang, Andrew Miller, Lefteris Kokoris-Kogias, and Ling Ren.  Practical asynchronous distributed key generation.  In 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022, pages 2518–2534. IEEE, 2022.  doi:10.1109/SP46214.2022.9833584.
  * [45] Christian Decker, Jochen Seidel, and Roger Wattenhofer.  Bitcoin Meets Strong Consistency.  In Proceedings of the 17th International Conference on Distributed Computing and Networking, pages 1–10, 2016.
  * [46] Dan Dobre, Ghassan O. Karame, Wenting Li, Matthias Majuntke, Neeraj Suri, and Marko Vukolic.  Proofs of writing for robust storage.  IEEE Trans. Parallel Distributed Syst., 30(11):2547–2566, 2019\.  doi:10.1109/TPDS.2019.2919285.
  * [47] Danny Dolev and Rüdiger Reischuk.  Bounds on information exchange for Byzantine agreement.  Journal of the ACM (JACM), 1985.
  * [48] Assia Doudou and André Schiper.  Muteness Detectors for Consensus with Byzantine Processes.  In Brian A. Coan and Yehuda Afek, editors, Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’98, Puerto Vallarta, Mexico, June 28 - July 2, 1998, page 315. ACM, 1998.  doi:10.1145/277697.277772.
  * [49] Sisi Duan, Xin Wang, and Haibin Zhang.  Practical Signature-Free Asynchronous Common Subset in Constant Time.  Cryptology ePrint Archive, 2023.
  * [50] Sisi Duan, Haibin Zhang, and Boxin Zhao.  Waterbear: Information-theoretic asynchronous BFT made practical.  IACR Cryptol. ePrint Arch., page 21, 2022.  URL: https://eprint.iacr.org/2022/021.
  * [51] Cynthia Dwork, Lynch Nancy, and Larry Stockmeyer.  Consensus in the Presence of Partial Synchrony.  Journal of the ACM (JACM), 35(2):288–323, 1988.
  * [52] Facebook.  Winterfell: A STARK prover and verifier for arbitrary computations.  URL: https://github.com/facebook/winterfell#Performance.
  * [53] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.  Impossibility of Distributed Consensus with One Faulty Process.  Journal of the Association for Computing Machinery,, 32(2):374–382, 1985.
  * [54] Adam Ga̧gol, Damian Leśniak, Damian Straszak, and Michał Świȩtek.  ALEPH: Efficient atomic broadcast in asynchronous networks with Byzantine nodes.  AFT 2019 - Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 214–228, 2019.  arXiv:1908.05156, doi:10.1145/3318041.3355467.
  * [55] Chaya Ganesh and Arpita Patra.  Broadcast extensions with optimal communication and round complexity.  In George Giakkoupis, editor, Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 371–380. ACM, 2016.  doi:10.1145/2933057.2933082.
  * [56] Chaya Ganesh and Arpita Patra.  Optimal extension protocols for byzantine broadcast and agreement.  IACR Cryptol. ePrint Arch., page 63, 2017.  URL: http://eprint.iacr.org/2017/063.
  * [57] Chaya Ganesh and Arpita Patra.  Optimal extension protocols for byzantine broadcast and agreement.  Distributed Comput., 34(1):59–77, 2021.  doi:10.1007/s00446-020-00384-1.
  * [58] James Hendricks, Gregory R. Ganger, and Michael K. Reiter.  Low-overhead byzantine fault-tolerant storage.  In Thomas C. Bressoud and M. Frans Kaashoek, editors, Proceedings of the 21st ACM Symposium on Operating Systems Principles 2007, SOSP 2007, Stevenson, Washington, USA, October 14-17, 2007, pages 73–86. ACM, 2007.  doi:10.1145/1294261.1294269.
  * [59] James Hendricks, Gregory R. Ganger, and Michael K. Reiter.  Verifying distributed erasure-coded data.  In Indranil Gupta and Roger Wattenhofer, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12-15, 2007, pages 139–146. ACM, 2007.  doi:10.1145/1281100.1281122.
  * [60] Ioannis Kaklamanis, Lei Yang, and Mohammad Alizadeh.  Poster: Coded broadcast for scalable leader-based bft consensus.  In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 3375–3377, 2022.
  * [61] Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman.  All you need is DAG.  In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 165–175. ACM, 2021\.  doi:10.1145/3465084.3467905.
  * [62] Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong.  Zyzzyva: speculative byzantine fault tolerance.  In Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, pages 45–58, 2007.
  * [63] Ramakrishna Kotla and Michael Dahlin.  High throughput byzantine fault tolerance.  In International Conference on Dependable Systems and Networks, 2004, pages 575–584. IEEE, 2004.
  * [64] Leslie Lamport, Robert Shostak, and Marshall Pease.  The Byzantine Generals Problem.  ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982.
  * [65] Andrew Lewis-Pye.  Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model, 2022.  URL: https://arxiv.org/abs/2201.01107, doi:10.48550/ARXIV.2201.01107.
  * [66] Fan Li and Jinyuan Chen.  Communication-efficient signature-free asynchronous byzantine agreement.  In IEEE International Symposium on Information Theory, ISIT 2021, Melbourne, Australia, July 12-20, 2021, pages 2864–2869. IEEE, 2021\.  doi:10.1109/ISIT45174.2021.9518010.
  * [67] Benoît Libert, Marc Joye, and Moti Yung.  Born and Raised Distributively: Fully Distributed Non-Interactive Adaptively-Secure Threshold Signatures with Short Shares.  Theoretical Computer Science, 645:1–24, 2016.
  * [68] Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang.  Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 129–138, 2020.
  * [69] Loi Luu, Viswesh Narayanan, Kunal Baweja, Chaodong Zheng, Seth Gilbert, and Prateek Saxena.  Scp: A computationally-scalable byzantine consensus protocol for blockchains.  Cryptology ePrint Archive, 2015.
  * [70] Dahlia Malkhi, Kartik Nayak, and Ling Ren.  Flexible byzantine fault tolerance.  In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pages 1041–1053, 2019.
  * [71] Ralph C. Merkle.  A Digital Signature Based on a Conventional Encryption Function.  In Advances in Cryptology — CRYPTO, 1987.
  * [72] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song.  The honey badger of bft protocols.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 31–42, 2016.
  * [73] Atsuki Momose and Ling Ren.  Multi-threshold byzantine fault tolerance.  In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 1686–1699, 2021.
  * [74] Atsuki Momose and Ling Ren.  Optimal Communication Complexity of Authenticated Byzantine Agreement.  In 35th International Symposium on Distributed Computing (DISC), volume 209, pages 32:1–32:0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2021.
  * [75] Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal.  Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Expected Time.  J. ACM, 62(4):31:1–31:21, 2015.  doi:10.1145/2785953.
  * [76] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  Decentralized business review, page 21260, 2008.
  * [77] Oded Naor and Idit Keidar.  Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR.  34th International Symposium on Distributed Computing (DISC), 179, 2020.
  * [78] Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang.  Improved extension protocols for byzantine broadcast and agreement.  In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 28:1–28:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.DISC.2020.28.
  * [79] Nuno Ferreira Neves, Miguel Correia, and Paulo Verissimo.  Solving Vector Consensus with a Wormhole.  IEEE Transactions on Parallel and Distributed Systems, 16(12):1120–1131, 2005.
  * [80] Irving S Reed and Gustave Solomon.  Polynomial codes over certain finite fields.  Journal of the society for industrial and applied mathematics, 8(2):300–304, 1960.
  * [81] Irving S Reed and Gustave Solomon.  Polynomial odes over certain finite fields.  Journal of the society for industrial and applied mathematics, 8(2):300–304, 1960.
  * [82] Victor Shoup.  Practical Threshold Signatures.  In Bart Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, pages 207–220. Springer, 2000.  doi:10.1007/3-540-45539-6\\_15.
  * [83] Victor Shoup and Nigel P Smart.  Lightweight asynchronous verifiable secret sharing with optimal resilience.  Cryptology ePrint Archive, 2023.
  * [84] Alexander Spiegelman.  In Search for an Optimal Authenticated Byzantine Agreement.  In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:19, Dagstuhl, Germany, 2021\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2021/14840, doi:10.4230/LIPIcs.DISC.2021.38.
  * [85] Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias.  Bullshark: Dag bft protocols made practical.  In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 2705–2718, 2022.
  * [86] Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, Lau Cheuk Lung, and Paulo Verissimo.  Efficient byzantine fault-tolerance.  IEEE Transactions on Computers, 62(1):16–30, 2011.
  * [87] Gavin Wood et al.  Ethereum: A secure decentralised generalised transaction ledger.  Ethereum project yellow paper, 151(2014):1–32, 2014.
  * [88] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham.  HotStuff: BFT Consensus with Linearity and Responsiveness.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 347–356, 2019.
  * [89] Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, and Andrew Miller.  hbacss: How to robustly share many secrets.  In 29th Annual Network and Distributed System Security Symposium, NDSS 2022, San Diego, California, USA, April 24-28, 2022. The Internet Society, 2022.  URL: https://www.ndss-symposium.org/ndss-paper/auto-draft-245/.

##  Appendix A Disperser: Complete Pseudocode & Proof

In this section, we give a complete pseudocode of Disperser, and formally
prove its correctness and complexity. First, we focus on Sync: we present
Sync’s implementation, as well as its proof of correctness and complexity (§
A.1). Then, we prove the correctness and complexity of Disperser (§ A.2).
Throughout the entire section, $X=Y=\sqrt{n}$. For simplicity, we assume that
$\sqrt{n}$ is an integer.

###  A.1 Sync: Implementation & Proof

Algorithm description. The pseudocode of Sync is given in Algorithm 4, and it
highly resembles RareSync [36]. Each process $P_{i}$ has an access to two
timers: (1) $\mathit{view\\_timer}_{i}$, and (2)
$\mathit{dissemination\\_timer}_{i}$. A timer exposes the following interface:

  * •

$\mathsf{measure}(\mathsf{Time}\text{ }x)$: After exactly $x$ time as measured
by the local clock, the timer expires (i.e., an expiration event is received
by the host). As local clocks can drift before GST, timers might not be
precise before GST: $x$ time as measured by the local clock may not amount to
$x$ real time.

  * •

$\mathsf{cancel}()$: All previously invoked $\mathsf{measure}(\cdot)$ methods
(on that timer) are cancelled. Namely, all pending expiration events
(associated with that timer) are removed from the event queue.

We now explain how Sync works, and we do so from the perspective of a correct
process $P_{i}$. When $P_{i}$ starts executing Sync (line 11), it starts
measuring $\mathit{view\\_duration}=\Delta+2\delta$ time using
$\mathit{view\\_timer}_{i}$ (line 12) and enters the first view (line 13).

Once $\mathit{view\\_timer}_{i}$ expires (line 14), which signals that
$P_{i}$’s current view has finished, $P_{i}$ notifies every process of this
via a view-completed message (line 15). When $P_{i}$ learns that $2t+1$
processes have completed some view $V\geq\mathit{view}_{i}$ (line 16) or any
process started some view $V^{\prime}>\mathit{view}_{i}$ (line 22), $P_{i}$
prepares to enter a new view (either $V+1$ or $V^{\prime}$). Namely, $P_{i}$
(1) cancels $\mathit{view\\_timer}_{i}$ (line 19 or line 25), (2) cancels
$\mathit{dissemination\\_timer}_{i}$ (line 20 or line 26), and (3) starts
measuring $\delta$ time using $\mathit{dissemination\\_timer}_{i}$ (line 21 or
line 27). Importantly, $P_{i}$ measures $\delta$ time (using
$\mathit{dissemination\\_timer}_{i}$) before entering a new view in order to
ensure that $P_{i}$ enters only $O(1)$ views during the time period
$[\text{GST},\text{GST}+3\delta)$. Finally, once
$\mathit{dissemination\\_timer}_{i}$ expires (line 28), $P_{i}$ enters a new
view (line 31).

Algorithm 4 Sync: Pseudocode (for process $P_{i}$)

1:Uses:

2: $\mathsf{Timer}$ $\mathit{view\\_timer}_{i}$

3: $\mathsf{Timer}$ $\mathit{dissemination\\_timer}_{i}$

4:Functions:

5: $\mathsf{leaders}(\mathsf{View}\text{
}V)\equiv\\{P_{\big{(}(V\mathsf{mod}\sqrt{n})-1\big{)}\sqrt{n}+1},P_{\big{(}(V\mathsf{mod}\sqrt{n})-1\big{)}\sqrt{n}+2},...,P_{\big{(}(V\mathsf{mod}\sqrt{n})-1\big{)}\sqrt{n}+\sqrt{n}}\\}$

6:Constants:

7: $\mathsf{Time}$
$\mathit{view\\_duration}=\Delta+2\delta=\delta\sqrt{n}+3\delta+2\delta$

8:Variables:

9: $\mathsf{View}$ $\mathit{view}_{i}\leftarrow 1$

10: $\mathsf{T\\_Signature}$ $\mathit{view\\_sig}_{i}\leftarrow\bot$

11:upon $\mathsf{init}$: $\triangleright$ start of the algorithm

12: $\mathit{view\\_timer}_{i}.\mathsf{measure}(\mathit{view\\_duration})$

13: trigger $\mathsf{advance}(1)$

14:upon $\mathit{view\\_timer}_{i}$ expires:

15: broadcast $\langle\textsc{view-
completed},\mathit{view}_{i},\mathsf{share\\_sign}_{i}(\mathit{view}_{i})\rangle$

16:upon exists $\mathsf{View}$ $V\geq\mathit{view}_{i}$ with $2t+1$
$\langle\textsc{view-completed},V,\mathsf{P\\_Signature}\text{
}\mathit{sig}\rangle$ received messages:

17:
$\mathit{view\\_sig}_{i}\leftarrow\mathsf{combine}\big{(}\\{\mathit{sig}\,|\,\mathit{sig}\text{
is received in the }\textsc{view-completed}\text{ messages}\\}\big{)}$

18: $\mathit{view}_{i}\leftarrow V+1$

19: $\mathit{view\\_timer}_{i}.\mathsf{cancel()}$

20: $\mathit{dissemination\\_timer}_{i}.\mathsf{cancel()}$

21: $\mathit{dissemination\\_timer}_{i}.\mathsf{measure}(\delta)$

22:upon reception of $\langle\textsc{enter-view},\mathsf{View}\text{
}V,\mathsf{T\\_Signature}\text{ }\mathit{sig}\rangle$ with
$V>\mathit{view}_{i}$:

23: $\mathit{view\\_sig}_{i}\leftarrow\mathit{sig}$

24: $\mathit{view}_{i}\leftarrow V$

25: $\mathit{view\\_timer}_{i}.\mathsf{cancel()}$

26: $\mathit{dissemination\\_timer}_{i}.\mathsf{cancel()}$

27: $\mathit{dissemination\\_timer}_{i}.\mathsf{measure}(\delta)$

28:upon $\mathit{dissemination\\_timer}_{i}$ expires:

29: broadcast $\langle\textsc{enter-
view},\mathit{view}_{i},\mathit{view\\_sig}_{i}\rangle$

30: $\mathit{view\\_timer}_{i}.\mathsf{measure}(\mathit{view\\_duration})$

31: trigger $\mathsf{advance}(\mathit{view}_{i})$

Proof of correctness & complexity. We prove that Sync satisfies eventual
synchronization and all the properties on which Disperser relies (recall §
5.1).

Given a view $V$, $\tau_{V}$ denotes the first time a correct process enters
$V$. First, we prove that, if any view $V>1$ is entered by a correct process,
then view $V-1$ was previously entered by a correct process.

######  Lemma A.1.

Consider any view $V>1$ which is entered by a correct process (line 31). View
$V-1$ is entered by a correct process by time $\tau_{V}$.

######  Proof A.2.

As $V>1$ is entered by a correct process at time $\tau_{V}$, at least $t+1$
correct processes have broadcast a view-completed message for $V-1$ (line 15)
by time $\tau_{V}$. Therefore, any such correct process $P_{i}$ has previously
invoked the $\mathsf{measure}(\cdot)$ operation on $\mathit{view\\_timer}_{i}$
(line 12 or line 30) at some time $\tau_{i}\leq\tau_{V}$. As this specific
invocation of the $\mathsf{measure}(\cdot)$ operation is not cancelled
(otherwise, $P_{i}$ would not broadcast a view-completed message because of
this invocation), $\mathit{view}_{i}=V-1$ at $\tau_{i}$. Immediately after the
invocation (still at time $\tau_{i}$ as local computation takes zero time),
$P_{i}$ enters $\mathit{view}_{i}=V-1$ (line 13 or line 31), which concludes
the proof.

A direct consequence of Lemma A.1 is that $\tau_{V^{\prime}}\geq\tau_{V}$ for
any two views $V^{\prime}$ and $V$ with $V^{\prime}>V$. Next, we prove that no
correct process updates its $\mathit{view}_{i}$ variable to a view
$V^{\prime}>V$ before time $\tau_{V}+\mathit{view\\_duration}$ if
$\tau_{V}\geq\text{GST}$.

######  Lemma A.3.

Consider any view $V$ such that $\tau_{V}\geq\text{GST}$. No correct process
$P_{i}$ updates its $\mathit{view}_{i}$ variable to a view $V^{\prime}>V$
before time $\tau_{V}+\mathit{view\\_duration}$.

######  Proof A.4.

No correct process sends a view-completed message (line 15) for $V$ (or, by
Lemma A.1, any greater view) before time $\tau_{V}+\mathit{view\\_duration}$
(as local clocks do not drift after GST). Thus, before time
$\tau_{V}+\mathit{view\\_duration}$, no correct process $P_{i}$ receives (1)
$2t+1$ view-completed messages for $V$ or any greater view (line 16), nor (2)
an enter-view message for a view greater than $V$ (line 22), which means that
$\mathit{view}_{i}$ cannot be updated before time
$\tau_{V}+\mathit{view\\_duration}$.

The next lemma proves that every correct process enters $V$ by time
$\tau_{V}+2\delta$, for any view $V>V_{\mathit{max}}$. Recall that
$V_{\mathit{max}}$ is the greatest view entered by a correct process before
GST.

######  Lemma A.5.

For any view $V>V_{\mathit{max}}$, every correct process enters $V$ by time
$\tau_{V}+2\delta$.

######  Proof A.6.

If $V=1$ (which implies that $V_{\mathit{max}}=0$, i.e., no correct process
started executing Sync before GST), every correct process enters $V$ at GST.
Hence, the statement of the lemma holds.

Let $V>1$. Due to the definition of $V_{\mathit{max}}$,
$\tau_{V}\geq\text{GST}$. Every correct process $P_{i}$ receives an enter-view
message for $V$ (line 22) by time $\tau_{V}+\delta$. When $P_{i}$ receives the
aforementioned message, it updates $\mathit{view}_{i}$ to $V$ (line 24).
Moreover, $P_{i}$ does not update its $\mathit{view}_{i}$ variable before time
$\tau_{V}+\mathit{view\\_duration}>\tau_{V}+2\delta$ (by Lemma A.3). Hence,
$\mathit{dissemination\\_timer}_{i}$ expires (line 28), and $P_{i}$ enters $V$
by time $\tau_{V}+2\delta$ (line 31).

The following lemma proves that Sync ensures the overlapping property.

######  Lemma A.7 (Overlapping).

For any view $V>V_{\mathit{max}}$, all correct processes overlap in $V$ for
(at least) $\Delta$ time.

######  Proof A.8.

For any view $V>V_{\mathit{max}}$, $\tau_{V}\geq\text{GST}$ due to the
definition of $V_{\mathit{max}}$. The following holds:

  * •

Every correct process enters $V$ by time $\tau_{V}+2\delta$ (by Lemma A.5).

  * •

No correct process enters another view before time
$\tau_{V}+\mathit{view\\_duration}$ (by Lemma A.3).

Thus, all correct process are in $V$ from $\tau_{V}+2\delta$ until
$\tau_{V}+\mathit{view\\_duration}$, for any view $V>V_{\mathit{max}}$. In
other words, in any view $V>V_{\mathit{max}}$, all correct processes overlap
for (at least) $\mathit{view\\_duration}-2\delta=\Delta$ time.

We are ready to prove that Sync satisfies eventual synchronization.

######  Theorem A.9.

Sync is correct, i.e., it satisfies eventual synchronization.

######  Proof A.10.

By Lemma A.7, all correct processes overlap for (at least)
$\mathit{view\\_duration}-2\delta=\Delta$ time in every view
$V>V_{\mathit{max}}$. Given that the leaders are assigned in the round-robin
manner (line 5), there exists a view $V_{\mathit{sync}}>V_{\mathit{max}}$ with
a correct leader, which concludes the proof.

In the rest of the subsection, we prove that Sync satisfies other properties
specified in § 5.1. We start by proving the monotonicity property of Sync.

######  Lemma A.11 (Monotonicity).

Any correct process enters monotonically increasing views.

######  Proof A.12.

Consider any correct process $P_{i}$. The lemma follows as the value of the
$\mathit{view}_{i}$ variable only increases (line 18 or line 24).

Next, we show a direct consequence of Lemma A.3: no correct process $P_{i}$
updates its $\mathit{view}_{i}$ variable to a view greater than
$V_{\mathit{max}}+1$ by time $\text{GST}+3\delta$.

######  Lemma A.13.

No correct process $P_{i}$ updates its $\mathit{view}_{i}$ variable to any
view greater than $V_{\mathit{max}}+1$ by time $\text{GST}+3\delta$.

######  Proof A.14.

By the definition of $V_{\mathit{max}}$, no correct process enters
$V_{\mathit{max}}+1$ (or a greater view) before GST. Moreover,
$\mathit{view\\_duration}>3\delta$. Thus, the lemma follows from Lemma A.3.

Next, we prove the stabilization property of Sync.

######  Lemma A.15 (Stabilization).

Any correct process enters a view $V\geq V_{\mathit{max}}$ by time
$\text{GST}+3\delta$.

######  Proof A.16.

If $V_{\mathit{max}}=0$ (no correct process started executing Sync before
GST), then all correct processes enter view $V_{\mathit{max}}+1=1$ at GST.
Thus, the lemma holds in this case.

Let $V_{\mathit{max}}>0$. Consider a correct process $P_{i}$. By time
$\text{GST}+\delta$, $P_{i}$ receives an enter-view message for
$V_{\mathit{max}}$ (line 22) as this message was previously broadcast (line
29). Hence, at time $\text{GST}+\delta$, $\mathit{view}_{i}$ is either
$V_{\mathit{max}}$ or $V_{\mathit{max}}+1$; note that it cannot be greater
than $V_{\mathit{max}}+1$ by Lemma A.13. We consider two cases:

  * •

$\mathit{view}_{i}=V_{\mathit{max}}+1$ at time $\text{GST}+\delta$: In this
case, $P_{i}$ does not cancel $\mathit{dissemination\\_timer}_{i}$ (line 20 or
line 26) before it expires (by Lemma A.13). Therefore, $P_{i}$ enters
$V_{\mathit{max}}+1$ (line 31) by time $\text{GST}+2\delta$ (after
$\mathit{dissemination\\_timer}_{i}$ expires at line 28). The claim of the
lemma holds.

  * •

$\mathit{view}_{i}=V_{\mathit{max}}$ at time $\text{GST}+\delta$: If $P_{i}$
does not update its $\mathit{view}_{i}$ variable by time $\text{GST}+2\delta$,
$\mathit{dissemination\\_timer}_{i}$ expires (line 28), and $P_{i}$ enters
$V_{\mathit{max}}$ (line 31) by time $\text{GST}+2\delta$.

Otherwise, $P_{i}$ updates its $\mathit{view}_{i}$ variable to
$V_{\mathit{max}}+1$ (by Lemma A.13), and measures $\delta$ time using
$\mathit{dissemination\\_timer}_{i}$ (line 21 or line 27). Moreover, Lemma
A.13 shows that $P_{i}$ does cancel $\mathit{dissemination\\_timer}_{i}$.
Hence, when $\mathit{dissemination\\_timer}_{i}$ expires (which happens by
time $\text{GST}+3\delta$ at line 28), $P_{i}$ enters $V_{\mathit{max}}+1$
(line 31).

The lemma is true as it holds in both possible cases.

Next, we show that Sync satisfies the limited entrance property.

######  Lemma A.17 (Limited entrance).

In the time period $[\text{GST},\text{GST}+3\delta)$, any correct process
enters $O(1)$ views.

######  Proof A.18.

The lemma holds as any correct process waits $\delta$ time (line 21 or line
27) before entering a new view (local clocks do not drift after GST).

Next, we prove the limited synchronization view property of Sync. Recall that
$V_{\mathit{sync}}^{*}$ is the smallest synchronization view.

######  Lemma A.19 (Limited synchronization view).

$V_{\mathit{sync}}^{*}-V_{\mathit{max}}=O(\sqrt{n})$.

######  Proof A.20.

By Lemma A.7, all correct processes overlap in any view $V>V_{\mathit{max}}$
for (at least) $\Delta$ time. Consider the set of views
$\mathbb{V}=\\{V_{\mathit{max}}+1,V_{\mathit{max}}+2,...,V_{\mathit{max}}+\sqrt{n}\\}$.
Each process is a leader in exactly one view from $\mathbb{V}$ (due to the
round-robin rotation of the leaders). Hence,
$V_{\mathit{sync}}^{*}\in\mathbb{V}$, which concludes the proof.

Finally, we prove the complexity of Sync.

######  Lemma A.21 (Complexity).

Sync exchanges $O(n^{2.5}\kappa)$ bits during the time period
$[\text{GST},\tau_{\mathit{sync}}^{*}+\Delta]$, and it synchronizes all
correct processes within $O(n)$ time after GST
($\tau_{\mathit{sync}}^{*}+\Delta-\text{GST}=O(n)$)

######  Proof A.22.

Due to the definition of $V_{\mathit{sync}}^{*}$, Sync synchronizes all
correct processes in $V_{\mathit{sync}}^{*}$. For each view, each correct
process sends $O(n\kappa)$ bits via the view-completed (line 15) and enter-
view (line 29) messages. By Lemma A.17, each correct process $P_{i}$ enters
$O(1)$ views during the time period $[\text{GST},\text{GST}+3\delta)$.
Moreover, Lemma A.15 shows that all correct processes enter a view $V\geq
V_{\mathit{max}}$ by time $\text{GST}+3\delta$. As
$V_{\mathit{sync}}^{*}-V_{\mathit{max}}=O(\sqrt{n})$, each correct process
sends $O(1)\cdot O(n\kappa)+O(\sqrt{n})\cdot O(n\kappa)=O(n^{1.5}\kappa)$ bits
after GST and before $\tau_{\mathit{sync}}^{*}+\Delta$. Hence, Sync exchanges
$O(n^{2.5}\kappa)$ bits.

As for the latency, each correct process enters $V_{\mathit{max}}+1$ by time
$\tau_{1}=\text{GST}+2\delta+\mathit{view\\_duration}+2\delta$: after
$V_{\mathit{max}}$ is concluded (at time
$\text{GST}+2\delta+\mathit{view\\_duration}$, at the latest), every correct
process receives $2t+1$ view-completed messages (line 16) for
$V_{\mathit{max}}$ by time
$\text{GST}+2\delta+\mathit{view\\_duration}+\delta$, and enters
$V_{\mathit{max}}+1$ (line 31) by time
$\text{GST}+2\delta+\mathit{view\\_duration}+2\delta$. Then, for each view
$V>V_{\mathit{max}}+1$, $V$ is entered by all correct processes by time
$\tau_{1}+(V-V_{\mathit{max}}-1)(\mathit{view\\_duration}+2\delta)$. Hence,
$V_{\mathit{sync}}^{*}$ is entered by time
$\tau_{\mathit{sync}}^{*}=\text{GST}+2\delta+\mathit{view\\_duration}+2\delta+O(\sqrt{n})(\mathit{view\\_duration}+2\delta)$.
Therefore,
$\tau_{\mathit{sync}}^{*}+\Delta-\text{GST}=O(\sqrt{n})+\mathit{view\\_duration}+O(\sqrt{n})\mathit{view\\_duration}=O(n)$.

###  A.2 Proof of Correctness & Complexity

This subsection proves the correctness and complexity of Disperser. We start
by proving that Disperser satisfies integrity.

######  Lemma A.23.

Disperser satisfies integrity.

######  Proof A.24.

Before a correct process acquires a hash-signature pair $(h,\Sigma_{h})$ (line
28), the process checks that
$\mathsf{verify\\_sig}(h,\Sigma_{h})=\mathit{true}$ (line 27). Thus, Disperser
satisfies integrity.

Next, we prove redundancy of Disperser.

######  Lemma A.25.

Disperser satisfies redundancy.

######  Proof A.26.

Let a correct process obtain a threshold signature $\Sigma_{h}$ such that
$\mathsf{verify\\_sig}(h,\Sigma_{h})=\mathit{true}$, for some hash value $h$.
As $\Sigma_{h}$ is a valid threshold signature for $h$, $2t+1$ processes have
partially signed $h$, which implies that at least $t+1$ correct processes have
done so (line 20). These processes have obtained a value $v$ for which
$\mathsf{hash}(v)=h$ (line 19), which concludes the proof.

Next, we prove termination of Disperser. We start by showing that, if a
correct process acquires a hash-signature pair, all correct processes
eventually acquire a hash-signature pair.

######  Lemma A.27.

If a correct process acquires a hash-signature pair at some time $\tau$, then
every correct process acquires a hash-signature pair by time
$\max(\text{{\emph{GST}}},\tau)+\delta$.

######  Proof A.28.

Let $P_{i}$ be a correct process that acquires a hash-signature pair at time
$\tau$ (line 28). Immediately after acquiring the pair, $P_{i}$ disseminates
the pair to all processes (line 29). Hence, every correct process $P_{j}$
receives the disseminated pair (via a confirm message) by time
$\max(\text{GST},\tau)+\delta$. If $P_{j}$ has not previously received a
confirm message and has not stopped participating in Disperser (by executing
line 30), $P_{j}$ acquires the pair (line 28). Otherwise, $P_{j}$ has already
acquired a hash-signature pair (by time $\max(\text{GST},\tau)+\delta$).

The following lemma proves that, if all correct processes overlap for “long
enough” in a view with a correct leader after GST, they all acquire a hash-
signature pair.

######  Lemma A.29.

If (1) all correct processes are in the same view $V$ from some time
$\tau\geq\text{GST}$ until time
$\tau^{\prime}=\tau+\Delta=\tau+\delta\sqrt{n}+3\delta$, and (2) $V$ has a
correct leader, then all correct processes acquire a hash-signature pair by
time $\tau^{\prime}$ (and terminate Disperser).

######  Proof A.30.

By the statement of the lemma, the view $V$ has a correct leader $P_{l}$.
$P_{l}$ sends a dispersal message (line 14) to every correct process by time
$\tau+\delta\sqrt{n}$. Thus, by time $\tau+\delta\sqrt{n}+\delta$, every
correct process has received a dispersal message from $P_{l}$ (line 17), and
sent an ack message back (line 20). Hence, $P_{l}$ receives $2t+1$ ack
messages (line 23) by time $\tau+\delta\sqrt{n}+2\delta$, which implies that
$P_{l}$ sends a confirm message to all processes by this time. Finally, all
correct processes receive the aforementioned confirm message (line 27), and
acquire a hash-signature pair (line 28) by time
$\tau^{\prime}=\tau+\Delta=\tau+\delta\sqrt{n}+3\delta$.

We are now ready to prove termination of Disperser.

######  Lemma A.31.

Disperser satisfies termination.

######  Proof A.32.

If a correct process acquires a hash-signature pair, termination is ensured by
Lemma A.27. Otherwise, Sync ensures that there exists a synchronization time
$\tau\geq\text{GST}$ such that (1) all correct processes are in the same view
$V$ from $\tau$ until $\tau+\Delta=\tau+\delta\sqrt{n}+3\delta$, and (2) $V$
has a correct leader. In this case, termination is guaranteed by Lemma A.29.

As it is proven that Disperser satisfies integrity (Lemma A.23), redundancy
(Lemma A.25) and termination (Lemma A.31), Disperser is correct.

######  Theorem A.33.

Disperser is correct.

Now, we address Disperser’s complexity. We start by proving that (at most)
$O(n^{1.5})$ dispersal messages are sent after GST.

######  Lemma A.34.

At most $O(n^{1.5})$ dispersal messages are sent by correct processes after
GST.

######  Proof A.35.

During the time period $[\text{GST},\text{GST}+3\delta)$, each correct process
can send dispersal messages (line 14) to only $O(1)$ groups of $\sqrt{n}$
processes due to the $\delta$-waiting step (line 15). Moreover, Lemma A.29
claims that all correct processes stop executing Disperser by the end of
$V_{\mathit{sync}}^{*}$ (i.e., by time $\tau_{\mathit{sync}}^{*}+\Delta$).
Furthermore, the stabilization property of Sync guarantees that each correct
process enters a view $V\geq V_{\mathit{max}}$ by time $\text{GST}+3\delta$.
Similarly, the overlapping property of Sync states that, for any view greater
than $V_{\mathit{max}}$, all correct processes overlap in that view for (at
least) $\Delta$ time.

Due to the definition of $V_{\mathit{sync}}^{*}$ and $V_{\mathit{max}}$, no
correct leader exists in any view $V$ with
$V_{\mathit{max}}<V<V_{\mathit{sync}}^{*}$. During the time period
$[\text{GST}+3\delta,\tau_{\mathit{sync}}^{*}+\Delta]$, only the correct
leaders of $V_{\mathit{max}}$ (if any) and $V_{\mathit{sync}}^{*}$ send
dispersal messages. Hence, the number of sent dispersal messages is

$\underbrace{O(n^{1.5})}_{[\text{GST},\text{GST}+3\delta)}+\underbrace{O(n^{1.5})}_{V_{\mathit{max}}}+\underbrace{O(n^{1.5})}_{V_{\mathit{sync}}^{*}}=O(n^{1.5}).$

Thus, the lemma holds.

Finally, we are ready to prove the complexity of Disperser.

######  Theorem A.36.

Disperser exchanges $O(n^{1.5}L+n^{2.5}\kappa)$ bits after GST (and before it
terminates), and terminates in $O(n)$ time after GST.

######  Proof A.37.

All correct processes stop executing Disperser by the end of
$V_{\mathit{sync}}^{*}$ (i.e., by time $\tau_{\mathit{sync}}^{*}+\Delta$) due
to Lemma A.29. Due to the limited entrance property of Sync, each correct
process enters $O(1)$ views during the time period
$[\text{GST},\text{GST}+3\delta)$. Each correct process sends $O(\sqrt{n})$
ack messages (line 20) in each view. Similarly, each correct leader sends
$O(n)$ confirm messages (line 25) in a view. Thus, during the time period
$[\text{GST},\text{GST}+3\delta)$, each correct process sends
$O(1)\cdot\big{(}O(\sqrt{n}\kappa)+O(n\kappa)\big{)}=O(n\kappa)$ bits through
ack and confirm messages.

Due to the stabilization property of Sync, each correct process enters (at
least) $V_{\mathit{max}}$ by time $\text{GST}+3\delta$. For each view $V$ with
$V_{\mathit{max}}<V<V_{\mathit{sync}}^{*}$, no correct leader is associated
with $V$ (due to the overlapping property of Sync and definition of
$V_{\mathit{sync}}^{*}$): each correct process sends $O(\sqrt{n}\kappa)$ bits
(exclusively via ack messages) in any view $V$ with
$V_{\mathit{max}}<V<V_{\mathit{sync}}^{*}$. Hence, during the time period
$[\text{GST}+3\delta,\tau_{\mathit{sync}}^{*}+\Delta]$, each correct process
sends (via ack and confirm messages)

$\underbrace{O(\sqrt{n})}_{\text{$V_{\mathit{sync}}^{*}-V_{\mathit{max}}$}}\cdot\underbrace{O(\sqrt{n}\kappa)}_{\text{{ack}}}+\underbrace{O(\sqrt{n}\kappa)}_{\text{{ack}
in $V_{\mathit{max}}$ and
$V_{\mathit{sync}}^{*}$}}+\underbrace{O(n\kappa)}_{\text{{confirm} in
$V_{\mathit{max}}$ and $V_{\mathit{sync}}^{*}$}}=O(n\kappa)\text{ bits.}$

Furthermore, at most $O(n^{1.5})$ dispersal messages are sent after GST (by
Lemma A.34), which implies that $O(n^{1.5}L)$ bits are sent through dispersal
messages. Next, Sync itself exchanges $O(n^{2.5}\kappa)$ bits. Hence,
Disperser exchanges

$\underbrace{O(n^{2.5}\kappa)}_{\text{{Sync}}}+\underbrace{O(n^{1.5}L)}_{\text{{dispersal}}}+\underbrace{n\cdot
O(n\kappa)}_{\text{{ack} \& {confirm}}}=O(n^{1.5}L+n^{2.5}\kappa)\text{ bits
after GST and before termination}.$

Note that the equation above neglects confirm messages sent by correct
processes at line 29. However, as each correct process broadcasts this message
only once (for a total of $O(n^{2}\kappa)$ sent bits by all correct
processes), the complexity of Disperser is not affected. The latency of
Disperser is $\tau_{\mathit{sync}}^{*}+\Delta-\text{GST}=O(n)$ (due to the
complexity of Sync).

##  Appendix B DARE-Stark: Proof

We start by proving agreement of DARE-Stark.

######  Lemma B.1.

DARE-Stark satisfies agreement.

######  Proof B.2.

By contradiction, suppose that DARE-Stark does not satisfy agreement. Hence,
there exists an execution in which two correct processes $P_{i}$ and $P_{j}$
disagree; let $P_{i}$ decide $v_{i}$ and $P_{j}$ decide $v_{j}\neq v_{i}$.
Process $P_{i}$ (resp., $P_{j}$) has received $t+1$ RS symbols (line 28) which
correspond to some hash value $h_{i}$ (resp., $h_{j}$). Thus, one correct
process has broadcast a retrieve message for $h_{i}$, and one correct process
has broadcast a retrieve message for $h_{j}$ (line 24). As correct processes
broadcast retrieve messages only for hash values decided by Agreement (line
22), $h_{i}=h_{j}=h$. Moreover, $\mathit{decision\\_symbols}_{i}[h]$ and
$\mathit{decision\\_symbols}_{j}[h]$ contain $t+1$ correct RS symbols (due to
the check at line 26). Therefore, Theorem 6.1 shows that
$\mathsf{hash}(v_{i})=\mathsf{hash}(v_{j})=h$, which implies that
$v_{i}=v_{j}$ (as $\mathsf{hash}(\cdot)$ is collision-resistant). We reach a
contradiction, which concludes the proof.

Next, we prove the validity property of DARE-Stark.

######  Lemma B.3.

DARE-Stark satisfies validity.

######  Proof B.4.

Let a correct process $P_{i}$ decide a value $v$ (line 30). The value $v$ is
“constructed” from $\mathit{decision\\_symbols}_{i}$, which contains $t+1$
correct RS symbols (due to the check at line 26). By Theorem 6.1,
$\mathsf{valid}(v)=\mathit{true}$.

The next lemma proves termination.

######  Lemma B.5.

DARE-Stark satisfies termination.

######  Proof B.6.

Each correct process $P_{i}$ successfully disperses its value’s symbols (line
14), each with a valid STARK proof. When a correct process receives its symbol
from $P_{i}$, the process eventually verifies the received proof (line 15),
and partially signs the hash of $P_{i}$’s value (line 17). Therefore, $P_{i}$
eventually receives $2t+1$ partial signatures (line 19), and proposes to
Agreement (line 21). Due to the termination and agreement properties of
Agreement, all correct processes decide the same hash-signature pair
$(h,\Sigma)$ from Agreement (line 22).

At least $t+1$ correct processes have obtained (provably correct) RS symbols
for a value $v$ with $\mathsf{hash}(v)=h$ (as $2t+1$ processes have partially
signed $h$ at line 17). All of these correct processes disseminate their
symbols to all other correct processes (line 24). Hence, all correct processes
eventually obtain $t+1$ correct RS symbols (line 28), and decide (line 30).

As DARE-Stark satisfies agreement (Lemma B.1), validity (Lemma B.3) and
termination (Lemma B.5), DARE-Stark is correct.

######  Theorem B.7.

DARE-Stark is correct.

Finally, we prove DARE-Stark’s complexity.

######  Theorem B.8.

DARE-Stark achieves $O(nL+n^{2}\mathit{poly}(\kappa))$ bit complexity and
$O(n)$ latency.

######  Proof B.9.

Recall that the bit complexity of Agreement is $O(n^{2}\kappa)$. Moreover,
each process sends (1) $O(n)$ dispersal messages (line 14), each with
$O(\frac{L}{n}+\mathit{poly}(\kappa))$ bits, (2) $O(n)$ ack messages (line
17), each with $O(\kappa)$ bits, and (3) $O(n)$ retrieve messages (line 24),
each with $O(\frac{L}{n}+\mathit{poly}(\kappa))$ bits. Hence, through
dispersal, ack and retrieve messages, each correct process sends

$\underbrace{n\cdot
O(\frac{L}{n}+\mathit{poly}(\kappa))}_{\text{{dispersal}}}+\underbrace{n\cdot
O(\kappa)}_{\text{{ack}}}+\underbrace{n\cdot
O(\frac{L}{n}+\mathit{poly}(\kappa))}_{\text{{retrieve}}}=O(L+n\mathit{poly}(\kappa))\text{
bits}.$

Thus, the bit complexity of DARE-Stark is $O(nL+n^{2}\mathit{poly}(\kappa))$.
Moreover, the latency of DARE-Stark is $O(n)$ due to Agreement’s linear
latency.

##  Appendix C Further Analysis of DARE

In this section, we provide a brief good-case analysis of DARE and discuss how
DARE can be adapted to a model with unknown $\delta$.

###  C.1 Good-Case Complexity

For the good-case complexity, we consider only executions where $\text{GST}=0$
and where all processes behave correctly. This is sometimes also regarded as
the common case since, in practice, there are usually no failures and the
network behaves synchronously. Throughout the entire subsection,
$X=Y=\sqrt{n}$.

In such a scenario, the good-case bit complexity of DARE is
$O(n^{1.5}L+n^{2}\kappa)$. As all processes are correct and synchronized at
the starting view, Disperser terminates after only one view. The $n^{1.5}L$
term comes from this view: the first $\sqrt{n}$ correct leaders broadcast
their full $L$-bit proposal to all other processes. The $n^{2.5}\kappa$ term
is reduced to only $n^{2}\kappa$ (only the confirm messages sent by correct
processes at line 29) since Disperser terminates after just one view.

The good-case latency of DARE is essentially the sum of the good-case
latencies of the Dispersal, Agreement, and Retrieval phases:

$\begin{split}&\underbrace{O(\sqrt{n}\cdot\delta)}_{\text{{dispersal}}}+\underbrace{O(\delta)}_{\text{{agreement}}}+\underbrace{O(\delta)}_{\text{{retrieval}}}=O(\sqrt{n}\cdot\delta).\end{split}$

Thus, the good-case latency of DARE is $O(\sqrt{n}\cdot\delta)$.

###  C.2 DARE (and DARE-Stark) with Unknown $\delta$

To accommodate for unknown $\delta$, two modifications to DARE are required:

  * •

Disperser must accommodate for unknown $\delta$. We can achieve this by having
Sync increase the ensured overlap with every new view (by increasing
$\mathit{view\\_duration}$ for every new view).

  * •

Agreement must accommodate for unknown $\delta$. Using the same strategy as
for Sync, Agreement can tolerate unknown $\delta$. (The same modification
makes DARE-Stark resilient to unknown $\delta$.)