Byzantine Reliable Broadcast (BRB) is a fundamental distributed computing primitive, with applications ranging from notifications to asynchronous payment systems.
Motivated by practical consideration, we study (), a multi-shot variant of BRB whose interface is split between broadcasting clients and delivering servers.
We present , an optimally resilient implementation of .
Like most implementations of BRB, guarantees both liveness and safety in an asynchronous environment.
Under good conditions, however, achieves unparalleled efficiency.
In a moment of synchrony, free from Byzantine misbehaviour, and at the limit of infinitely many broadcasting clients, a server delivers a $b$-bits payload at an asymptotic amortized cost of $0$ signature verifications, and $\rp{log_2\rp{\clientcount} + b}$ bits exchanged, where $\clientcount$ is the number of clients in the system.
This is the information-theoretical minimum number of bits required to convey the payload ($b$ bits, assuming it is compressed), along with an identifier for its sender ($\log_2\rp{\clientcount}$ bits, necessary to enumerate any set of $\clientcount$ elements, and optimal if broadcasting frequencies are uniform or unknown).
These two achievements have profound practical implications.
Real-world BRB implementations are often bottlenecked either by expensive signature verifications, or by communication overhead.
For , instead, the network is the limit: a server can deliver payloads as quickly as it would receive them from an infallible oracle.

§ INTRODUCTION

Byzantine reliable broadcast (BRB) is one of the most fundamental and versatile building blocks in distributed computing, powering a variety of Byzantine fault-tolerant (BFT) systems <cit.>.
The BRB abstraction has recently been shown to be strong enough to process payments, enabling cryptocurrency deployments in an asynchronous environment <cit.>.
Originally introduced by Bracha <cit.> to allow a set of processes to agree on a single message from a designated sender, BRB naturally generalizes to the multi-shot case, enabling higher-level abstractions such as Byzantine FIFO <cit.> and causal <cit.> broadcast.
We study a practical, multi-shot variant of BRB whose interface is split between broadcasting clients and delivering servers.
We call this abstraction ().

in brief
Clients broadcast, and servers deliver, payloads composed by a context and a message.
This interface allows, for example, Alice to announce her wedding as well as will her fortune by respectively broadcasting

\begin{align*}
\rp{\underbrace{\texttt{"My wife is"}}_{\text{context} \; c_w}, \underbrace{\texttt{"Carla"}}_{\text{message} \; m_w}} \;\;\;
\rp{\underbrace{\texttt{"All my riches go to"}}_{\text{context} \; c_r}, \underbrace{\texttt{"Bob"}}_{\text{message} \; m_r}}
\end{align*}

guarantees that: (Consistency) no two correct servers deliver different messages for the same client and context; (Totality) either all correct servers deliver a message for a given client and context, or no correct server does; (Integrity) if a correct server delivers a payload from a correct client, then the client has broadcast that payload; and (Validity) a payload broadcast by a correct client is delivered by at least one correct server.
Following from the above example, Carla being Alice's wife does not conflict with Bob being her sole heir (indeed, $c_w \neq c_r$), but Alice would not be able to convince two correct servers that she married Carla and Diana, respectively.
Higher-level broadcast abstractions can be easily built on top of .
For example, using integer sequence numbers as contexts and adding a reordering layer yields Client-Server Byzantine FIFO Broadcast.
For the sake of , however, it is not important for contexts to be integers, or satisfy any property other than comparability.
Throughout the remainder of this paper, the reader can picture contexts as opaque binary blobs.
Lastly, while the set of servers is known, as presented does not assume any client to be known a priori.
The set of clients can be permissionless, with servers discovering new clients throughout the execution.

A utopian model
Real-world BRB implementations are often bottlenecked either by expensive signature verifications <cit.> or by communication overhead <cit.>.
With the goal of broadening those bottlenecks, simplified, more trustful models are useful to establish a (sometimes grossly unreachable) bound on the efficiency that an algorithm can attain in the Byzantine setting.
For example, in a utopian model where any agreed-upon process can be trusted to never fail (let us call it an oracle), can easily be implemented with great efficiency.
Upon initialization, the oracle organizes all clients in a list, which it disseminates to all servers.
For simplicity, let us call id a client's position in the list.
To broadcast a payload $p$, a client with id $i$ simply sends $p$ to the oracle: the oracle checks $p$ for equivocation (thus ensuring consistency), then forwards $\rp{i, p}$ to all servers (thus ensuring validity and totality).
Upon receiving $\rp{i, p}$, a server blindly trusts the oracle to uphold all properties, and delivers $\rp{i, p}$.  is clearly very efficient.
On the one hand, because the oracle can be trusted not to attribute spurious payloads to correct clients, integrity can be guaranteed without any server-side signature verification.
On the other, in order to deliver $\rp{i, p}$, a server needs to receive just $\rp{\ceil{\log_2\rp{\clientcount}} + \abs{p}}$ bits, where $\clientcount$ denotes the total number of clients, and $\abs{p}$ measures $p$'s length in bits.
This is optimal assuming the rate at which clients broadcast is unknown[
Lacking an assumption on broadcasting rates, an adversarial scheduler could have all messages broadcast by the client with the longest id, which we cannot guarantee to be shorter than $\ceil{\log_2\rp{\clientcount}}$ bits.
] or uniform[
Should some clients be expected to broadcast more frequently than others, we could further optimize  by assigning smaller ids to more active clients, possibly at the cost of having less active clients have ids whose length exceeds $\ceil{\log_2\rp{\clientcount}}$. Doing so, however, is beyond the scope of this paper.
] <cit.>.

Matching the oracle
Due to its reliance on a single infallible process,  is not a fault-tolerant distributed algorithm: shifting back to the Byzantine setting, a single failure would be sufficient to compromise all properties.
Common sense suggests that Byzantine resilience will necessarily come at some cost: protocol messages must be exchanged to preserve consistency and totality, signatures must be produced and verified to uphold integrity and, lacking the totally-ordering power that only consensus can provide, ids cannot be assigned in an optimally dense way.
However, this paper proves the counter-intuitive result that an asynchronous, optimally-resilient, Byzantine implementation of can asymptotically match the efficiency of .
This is not just up to a constant, but identically.
In a synchronous execution, free from Byzantine misbehaviour, and as the number of concurrently broadcasting clients goes to infinity (we call these conditions the batching limit[
The batching limit includes other easily achievable, more technical conditions that we omit in this section for the sake of brevity.
We formally define the batching limit in Section <ref>
), our implementation delivers a payload $p$ at an asymptotic[The asymptotic costs are reached quite fast, at rates comparable to $C^{-1}$ or $log(C)\cdot C^{-1}$.], amortized cost of $0$ signature verifications[This does not mean that batches are processed in constant time: hashes and signature aggregations, for example, still scale linearly in the size of a batch. The real-world computational cost of such simple operations, however, is several orders of magnitude lower than that of signature verification.] and $\rp{\ceil{\log_2\rp{\clientcount}} + \abs{p}}$ bits exchanged per server, the same as in  (we say that achieves oracular efficiency).
At the batching limit a server is dispensed from nearly all signature verifications, as well as nearly all traffic that would be normally required to convey protocol messages, signatures, or client public keys.
Network is the limit: payloads are delivered as quickly as they can be received.

's common bottlenecks
To achieve oracular efficiency, we focus on three types of server overhead that commonly affect a real-world implementation of :

* Protocol overhead.
Safekeeping consistency and totality typically requires some form of communication among servers.
This communication can be direct (as in Bracha's original, all-to-all BRB implementation) or happen through an intermediary (as in Bracha's signed, one-to-all-to-one BRB variant), usually employing signatures to establish authenticated, intra-server communication channels through a (potentially Byzantine) relay.

* Signature overhead.
Upholding integrity usually requires clients to authenticate their messages using signatures.
For servers, this entails both a computation and a communication overhead.
On the one hand, even using well-optimized schemes, signature verification is often CPU-heavy enough to dominate a server's computational budget, dwarfing in particular the CPU footprint of much lighter, symmetric cryptographic primitives such as hashes and ciphers.
On the other hand, transmitting signatures results in a fixed communication overhead per payload delivered.
While the size of a signature usually ranges from a few tens to a few hundreds of bytes, this overhead is non-negligible in a context where many clients broadcast small messages.
This is especially true in the case of payments, where a message reduces to the identifier of a target account and an integer to denote the amount of money to transfer.

* Identifier overhead.
's multi-shot nature calls for a sender identifier to be attached to each broadcast payload.
Classically, the client's public key is used as identifier.
This is convenient for two reasons.
First, knowing a client's identifier is sufficient to authenticate its payloads.
Second, asymmetric keypairs have very low probability of collision.
As such, clients can create identities in the system without any need for coordination: locally generating a keypair is sufficient to begin broadcasting messages.
By cryptographic design, however, public keys are sparse, and their size does not change with the number of clients.
This translates to tens to hundreds of bytes being invested to identify a client from a set that can realistically be enumerated by a few tens of bits.
Again, this communication overhead is heavier on systems where broadcasts are frequent and brief.

On the way to matching 's performance, we develop techniques to negate all three types of overhead: at the batching limit, a server delivers a payload wasting $0$ bits to protocol overhead, performing $0$ signature verifications, and exchanging $\ceil{\log_2\rp{\clientcount}}$ bits of identifier, the minimum required to enumerate the set of clients.
We outline our contributions below, organized in three (plus one) take-home messages (T-HMs).

T-HM1: The effectiveness of batching goes beyond total order
In the totally ordered setting, batching is famously effective at amortizing protocol overhead <cit.>.
Instead of disseminating its message to all servers, a client hands it over to (one or more)[In most real-world implementations, a client optimistically entrusts its payload to a single process, extending its request to larger portions of the system upon expiration of a suitable timeout.] batching processes.
Upon collecting a large enough set of messages, a batching process organizes all messages in a batch, which it then disseminates to the servers.
Having done so, the batching process submits the batch's hash to the system's totally-ordering primitive.
Because hashes are constant in length, the cost of totally ordering a batch does not depend on its size.
Once batches are totally ordered, so too are messages (messages within a batch can be ordered by any deterministic function), and equivocations can be handled at the application layer (for example, in the context of a cryptocurrency, the second request to transfer the same asset can be ignored by all correct servers, with no need for additional coordination).
At the limit of infinitely large batches, the relative overhead of the ordering protocol becomes vanishingly small, and a server can allocate virtually all of its bandwidth to receiving batches.
This strategy, however, does not naturally generalize to , where batches lack total order.
As payloads from multiple clients are bundled in the same batch, a correct server might detect equivocation for only a subset of the payloads in the batch.
Entirely accepting or entirely rejecting a partially equivocated batch is not an option.
In the first case, consistency could be violated.
In the second case, a single Byzantine client could single-handedly “poison” the batches assembled by every correct batching process with equivocated payloads, thus violating validity.
In , a server can partially reject a batch, acknowledging all but some of its payloads.
Along with its partial acknowledgement, a server provides a proof of equivocation to justify each exception.
Having collected a quorum of appropriately justified partial acknowledgements, a batching process has servers deliver only those payloads that were not excepted by any server.
Because proofs of equivocations cannot be forged for correct clients, a correct client handing over its payload to a correct batching process is guaranteed to have that payload delivered.
In the common case where batches have little to no equivocations, servers exchange either empty or small lists of exceptions, whose size does not scale with that of the batch.
This extends the protocol-amortizing power of batching to and, we conjecture, other non-totally ordered abstractions.

T-HM2: Interactive multi-signing can slash signature overhead
Traditionally, batching protocols are non-interactive on the side of clients.
Having offloaded its message to a correct batching process, a correct client does not need to interact further for its message to be delivered: the batching process collects an arbitrary set of independently signed messages and turns to the servers to get each signature verified, and the batch delivered.
This approach is versatile (messages are not tied to the batch they belong to) and reliable (a client crashing does not affect a batch's progress) but expensive (the cost of verifying each signature is high and independent of the batch's size).
In , batching processes engage in an interactive protocol with clients to replace, in the good case, all individual signatures in a batch with a single, batch-wide multi-signature.
In brief, multi-signature schemes extend traditional signatures with a mechanism to aggregate signatures and public keys: an arbitrarily large set of signatures for the same message[Some multi-signature schemes also allow the aggregation of signatures on heterogeneous messages.
In that case, however, aggregation is usually as expensive as signature verification.
Given our goal to reduce CPU complexity for servers, this paper entirely disregards heterogeneous aggregation schemes.] can be aggregated into a single, constant-sized signature; similarly, a set of public keys can be aggregated into a single, constant-sized public key.
The aggregation of a set of signatures can be verified in constant time against the aggregation of all corresponding public keys.
Unlike verification, aggregation is a cheap operation, reducing in some schemes to a single multiplication on a suitable field.
Multi-signature schemes open a possibility to turn expensive signature verification into a once-per-batch operation.
Intuitively, if each client contributing to a batch could multi-sign the entire batch instead of its individual payload, all multi-signatures could be aggregated, allowing servers to authenticate all payloads at once.
However, as clients cannot predict how their payloads will be batched, this must be achieved by means of an interactive protocol.
Having collected a set of individually-signed payloads in a batch, a batching process shows to each contributing client that its payload was included in the batch.
In response, clients produce their multi-signatures for the batch's hash, which the batching process aggregates.
Clients that fail to engage in this interactive protocol (e.g., because they are faulty or slow) do not lose liveness, as their original signature can still be attached to the batch to authenticate their individual payload.
In the good case, all clients reply in a timely fashion, and each server has to verify a single multi-signature per batch.
At the limit of infinitely large batches, this results in each payload being delivered at an amortized cost of $0$ signature verifications.
The usefulness of this interactive protocol naturally extends beyond to all multi-shot broadcast abstractions whose properties include integrity.

T-HM3: Dense id assignment can be achieved without consensus
In order to efficiently convey payload senders, 's oracle organizes all clients in a list, attaching to each client a successive integral identifier.
Once the list is disseminated to all servers, the oracle can identify each client by its identifier, sparing servers the cost of receiving larger, more sparse, client-generated public keys.
Id-assignment strategies similar to that of  can be developed, in the distributed setting, building on top of classical algorithms that identify clients by their full public keys (we call such algorithms id-free, as opposed to algorithms such as , which are id-optimized).
In a setting where consensus can be achieved, the identifier density of  is easily matched.
Upon initialization, each client submits its public key to an id-free implementation of Total-Order Broadcast (TOB).
Upon delivery of a public key, every correct process agrees on its position within the common, totally-ordered log.
As in , each client can then use its position in the list as identifier within some faster, id-optimized broadcast implementation.
In a consensus-less setting, achieving a totally-ordered list of public keys is famously impossible <cit.>.
This paper, however, proves the counter-intuitive result that, when batching is used, the density of ids assigned by a consensus-less abstraction can asymptotically match that of those produced by  or consensus.
In , our consensus-less id-assigning algorithm, a client requests an id from every server.
Each server uses an id-free implementation of FIFO Broadcast to order the client's public key within its own log.
Having observed its public key appear in at least one log, the client publicly elects the server in charge of that log to be its assigner.
Having done so, the client obtains an id composed of the assigner's public key and the client's position within the assigner's log.
We call the two components of an id domain and index, respectively.
Because the set of servers is known to (and can be enumerated by) all processes, an id's domain can be represented in $\ceil{\log_2\rp{\servercount}}$ bits, where $\servercount$ denotes the total number of servers.
Because at most $\clientcount$ distinct clients can appear in the FIFO log of any server, indices are at most $\ceil{\log_2\rp{\clientcount}}$ bits long.
In summary, assigns ids to clients without consensus, at an additional cost of $\ceil{\log_2\rp{\servercount}}$ bits per id.
Interestingly, even this additional complexity can be amortized by batching.
Having assembled a batch, a batching process represents senders not as a list of ids, but as a map, associating to each of the $\servercount$ domains the indices of all ids in the batch under that domain.
At the limit of infinitely large batches ($C \gg N$), the bits required to represent the map's keys are entirely amortized by those required to represent its values.
This means that, while $\rp{\ceil{\log_2\rp{\servercount}} + \ceil{\log_2\rp{\clientcount}}}$ bits are required to identify a client in isolation, $\ceil{\log_2\rp{\clientcount}}$ bits are sufficient if the client is batched: even without consensus, asymptotically matches the id efficiency of .

Bonus T-HM: Untrusted processes can carry the system
In THM1, we outlined how batching can be generalized to the consensus-less case, and discussed its role in removing protocol overhead.
In THM2, we sketched how an interactive protocol between clients and batching processes can eliminate signature overhead.
In employing these techniques, we shifted most of the communication and computation complexity of our algorithms from servers to batching processes.
Batching processes verify all client signatures, create batches, verify and aggregate all client multi-signatures, then communicate with servers in an expensive one-to-all pattern, engaging server resources (at the batching limit) as little as an oracle would.
Our last contribution is to observe that a batching process plays no role in upholding 's safety.
As we discuss in detail throughout the remainder of this paper, a malicious batching process cannot compromise consistency (it would need to collect two conflicting quorums of acknowledgements), totality (any server delivering a batch has enough information to convince all others to do the same) or integrity (batches are still signed, and forged or improperly aggregated multi-signatures are guaranteed to be detected).
Intuitively, the only damage a batching process can do to the system is to refuse to process client payloads[Or cause servers to waste resources, e.g., by transmitting improperly signed batches. Simple accountability measures, we conjecture, would be sufficient to mitigate these attacks in .
A full discussion of Denial of Service, however, is beyond the scope of this paper.].
This means that a batching process does not need to satisfy the same security properties as a server.
's properties cannot be upheld if a third of the servers are faulty.
Conversely, has both liveness and safety as long as a single batching process is correct.
This observation has profound practical implications.
In the real world, scaling the resources of a permissioned, security-critical set of servers can be hard.
On the one hand, reputable, dependable institutions partaking in the system might not have the resources to keep up with its demands.
On the other, more trusted hardware translates to a larger security cross-section.
Trustless processes, however, are plentiful to the point that permissionless cryptocurrencies traditionally waste their resources, making them compete against each other in expensive proofs of Sybil-resistance <cit.>.
In this paper, we extend the classical client-server model with brokers, a permissionless, scalable set of processes whose only purpose is to alleviate server complexity.
Unlike servers, more than two-thirds of which we assume to be correct, all brokers but one can be faulty.
In , brokers act as an intermediary between clients and servers, taking upon themselves the batching of payloads, verification and aggregation of signatures, the dissemination of batches, and the transmission of protocol messages.

We discuss related work in Section <ref>. We state our model and recall useful cryptographic background in Section <ref>. In Section <ref>, we introduce our implementation : we overview 's protocol in Section <ref>, and provide high-level arguments for 's efficiency in Section <ref>. We draw our conclusions and propose future work in Section <ref>. We leave a fully formal analysis of our algorithms to Appendices <ref> and <ref>: Appendix <ref> fully defines the abstraction (<ref>), proves 's correctness (<ref>), and analyzes 's complexity at the batching limit (<ref>); Appendix <ref> introduces the abstraction (<ref>) and proves the correctness of our implementation (<ref>). For the sake of tidiness, we gather all pseudocode in Appendix <ref> (<ref>, <ref> and <ref> for , <ref> and <ref> for ).

§ RELATED WORK

Byzantine Reliable Broadcast (BRB) is a classical primitive of distributed computing, with widespread practical applications such as in State Machine Replication (SMR) <cit.>, Byzantine agreement <cit.>, blockchains <cit.>, and online payments <cit.>.
In classical BRB, a system of $n$ processes agree on a single message from a single source (one of the $n$ processes), while tolerating up to $f$ Byzantine failures ($f$ of the $n$ processes can behave arbitrarily).
A well known solution to asynchronous BRB with provably optimal resilience ($f < n/3$) was first proposed by Bracha <cit.> who introduced the problem.
Bracha's broadcast reaches $O(n^2)$ message complexity, and $O(n^2L)$ communication complexity (total number of transmitted bits between correct processes <cit.>), where $L$ is the length of the message.
Since $O(n^2)$ message complexity is provably optimal <cit.>, the main focus of BRB-related research has been on reducing its communication complexity.
The best lower bound for communication complexity is $\Omega(nL + n^2)$, although it is unknown whether it is tight.
The $nL$ term comes from all processes having to receive the message (length $L$), while the $n^2$ term comes from each of the $n$ processes having to receive $\Omega(n)$ protocol messages to ensure agreement in the presence of $f = \Theta(n)$ failures <cit.>.
One line of research focuses on worst-case complexity, predominantly using error correcting codes <cit.> or erasure codes <cit.>, and has produced various BRB protocols with improved complexity <cit.>, many of them quite recently.
The work of Das, Xiang and Ren <cit.> achieves $O(nL + kn^2)$ communication complexity (specifically, $7nL + 2kn^2$), where $k$ is the security parameter (e.g., the length of a hash, typically $256$ bits).
As the authors note, the value of hidden constants (and $k$, which is sometimes considered as a constant in literature) is particularly important when considering practical implementations of these protocols.
Another line of research focuses on optimizing the good case performance of BRB, i.e., when the network behaves synchronously and no process misbehaves <cit.>.
As the good case is usually the common case, in practice, the real-world communication complexity of these optimistic protocols matches that of the good case.
A simple and widely-used hash-based BRB protocol is given by Cachin et al. <cit.>.
It replaces the echo and ready phase messages in Bracha's protocol with hashes, achieving $O(nL + kn^2)$ in the good case (specifically, $nL + 2kn^2$), and $O(n^2L)$ in the worst-case.
Considering practical throughput, some protocols also focus on the amortized complexity per source message <cit.>.
Combining techniques such as batching <cit.> and threshold signatures <cit.>, at the limit (of batch size), BRB protocols reach $O(nL)$ amortized communication complexity in the good case <cit.>.
At this point, the remaining problem lies in the hidden constants.
In the authenticated setting, batching-based protocols rely on digital signatures to validate (source) messages before agreeing to deliver them <cit.>.
In reality, each source message in a batch includes its content, an identifier of the source (e.g., a $k$-sized public key), a sequence id (identifying the message), and a $k$-sized signature.
When considering systems where $L$ is small (e.g., online payments), these can take up a large fraction of the communication.
To be precise, the good-case amortized communication complexity would be $O(nL + kn)$.
In fact, message signatures (the $kn$ factor) are by far the main bottleneck in practical applications of BRB today <cit.>, both in terms of communication and computation (signature verification), leading to various attempts at reducing or amortizing their cost <cit.>.
For example, Crain et al. <cit.> propose verification sharding, in which only $f + 1$ processes have to receive and verify all message signatures in the good case, which is a $3$-fold improvement over previous systems (on the $kn$ factor) where all $n$ processes verify all signatures.
However, by itself, this does not improve on the amortized cost of $O(nL + kn)$ per message.
When contrasting theoretical research with practical systems, it is interesting to note the gap that can surge between the theoretical model and reality.
The recent work of Abraham et al. <cit.>, focused on the good-case latency of Byzantine broadcast, expands on some of these mismatches and argues about the practical limitations of focusing on the worst-case.
Another apparent mismatch lies in the classical model of Byzantine broadcast.
In many of the applications of BRB mentioned previously (e.g., SMR, permissioned blockchains, online payments), there is usually a set of servers ($n$, up to $f$ of which are faulty), and a set of external clients ($\clients$) which are the true sources of messages.
The usual transformation from BRB's classical model into these practical settings maps the set of $n$ servers as the $n$ processes and simply excludes clients as system entities, e.g., assuming their messages are relayed through one of the servers.
Since the number of clients can be very large ($|\clients| \gg n$), clients are untrusted (which can limit their usefulness), and the focus is on the communication complexity of the servers, this transformation seems reasonable and simplifies the problem.
However, it can also limit the search for more practical solutions.
In this paper, in contrast with the classical model of BRB, we explicitly include the set of clients $\clients$ in our system while focusing on the communication complexity surrounding the servers (i.e., the bottleneck).
Furthermore, we introduce brokers, an untrusted set $\brokers$ of processes, only one of which is assumed to be correct, whose goal is to assist servers in their operation. By doing this, we can leverage brokers to achieve a good-case, amortized communication complexity (for servers, information received or sent) of $nL + o(nL)$.

§ MODEL & BACKGROUND

§.§ Model

System and adversary We assume an asynchronous message-passing system where the set $\processes$ of processes is the distinct union of three sets: servers ($\servers$), brokers ($\brokers$), and clients ($\clients$). We use $\servercount = \abs{\servers}$, $\brokercount = \abs{\brokers}$ and $\clientcount = \abs{\clients}$.
Any two processes can communicate via reliable, FIFO, point-to-point links (messages are delivered in the order they are sent).
Faulty processes are Byzantine, i.e., they may fail arbitrarily. Byzantine processes know each other, and may collude and coordinate their actions.
At most $\faultcount$ servers are Byzantine, with $\servercount = 3 \faultcount + 1$. At least one broker is correct.
All clients may be faulty.
We use $\correctprocesses$ and $\faultyprocesses$ to respectively identify the set of correct and faulty processes.
The adversary cannot subvert cryptographic primitives (e.g., forge signatures).
Servers and brokers[The assumption that brokers are permissioned is made for simplicity, and can be easily relaxed to the requirement that every correct process knows at least one correct broker.] are permissioned (every process knows $\servers$ and $\brokers$), clients are permissionless (no correct process knows $\clients$ a priori).
We call certificate a statement signed by either a plurality ($f+1$) or a quorum ($2f+1$) of servers.
Since every process knows $\servers$, any process can verify a certificate.

Good case The algorithms presented in this paper are designed to uphold all their properties in the model above.
, however, achieves oracular efficiency only in the good case.
In the good case, links are synchronous (messages are delivered at most one time unit after they are sent), all processes are correct, and the set of brokers contains only one element.
To take advantage of the good case, makes use of timers (which is uncommon for purely asynchronous algorithms).
A timer with timeout $\delta$ set at time $t$ rings: after time $\rp{t + \delta}$, if the system is synchronous; after time $t$, otherwise.
Intuitively, in the non-synchronous case, timers disregard their timeout entirely, and are guaranteed to ring only eventually.

§.§ Background

Besides commonly used hashes and signatures, the algorithms presented in this paper make use of two less often used cryptographic primitives, namely, multi-signatures and Merkle trees. We briefly outline their use below.
An in-depth discussion of their inner workings, however is beyond the scope of this paper.

Like traditional signatures, multi-signatures <cit.> are used to publicly authenticate messages: a public / secret keypair $\rp{p, r}$ is generated locally; $r$ is used to produce a signature $s$ for a message $m$; $s$ is publicly verified against $p$ and $m$. Unlike traditional signatures, however, multi-signatures for the same message can be aggregated.
Let $\rp{p_1, r_1}, \ldots, \rp{p_n, r_n}$ be a set of keypairs, let $m$ be a message, and let $s_i$ be $r_i$'s signature for $m$.
$\rp{p_1, \ldots, p_n}$ and $\rp{s_1, \ldots, s_n}$ can be respectively aggregated into a constant-sized public key $\hat p$ and a constant-sized signature $\hat s$.
As with individually-generated multi-signatures, $\hat s$ can be verified in constant time against $\hat p$ and $m$.
Aggregation is cheap and non-interactive: provided with $\rp{p_1, \ldots, p_n}$ (resp., $\rp{s_1, \ldots, s_n}$) any process can compute $\hat p$ (resp., $\hat s$).

Merkle trees
Merkle trees <cit.> extend traditional hashes with compact proofs of inclusion.
As with hashes, a sequence $\rp{x_1, \ldots, x_n}$ of values can be hashed into a preimage and collision-resistant digest (or root) $r$.
Unlike hashes, however, a proof $p_i$ can be produced from $\rp{x_1, \ldots, x_n}$ to attest that the $i$-th element of the sequence whose root is $r$ is indeed $x_i$.
In other words, provided with $r$, $p_i$ and $x_i$, any process can verify that the $i$-th element of $\rp{x_1, \ldots, x_n}$ is indeed $x_i$, without having to learn $\rp{x_1, \ldots, x_{i - 1}, x_{i + 1}, \ldots, x_n}$.
The size of a proof of inclusion for a sequence of $n$ elements is logarithmic in $n$.

§ : OVERVIEW

In this section, we provide an intuitive overview of our implementation, , as well as high-level arguments for its efficiency.
A full analysis of can be found in Appendix <ref>, where we introduce 's full pseudocode, formally prove its correctness, and thoroughly study its good-case signature and communication complexity.

§.§ Protocol

's protocol.
Having collected a batch of client payloads, a broker engages in an interactive protocol with clients to reduce the batch, replacing (most of) its individual payload signatures with a single, batch-wide multi-signature.
The broker then disseminates the batch to all servers, successively gathering a witness for its correctness and a certificate to commit (some of) its payloads.
Having had a plurality of servers deliver the batch, the broker notifies all clients with a suitable certificate.
In the bad case, servers can ensure totality without any help from the broker, propagating batches and commit certificates in an all-to-all fashion.

Dramatis personae
The goal of this section is to provide an intuitive understanding of 's protocol.
In order to do this, we focus on four processes: a correct client $\client$, a correct broker $\broker$, a correct and fast server $\server$, and a correct but slow server $\tilde \server$.
We follow the messages exchanged between $\client$, $\broker$, $\server$ and $\tilde \server$ as the protocol unfolds, as captured by Figure <ref>.

The setting
$\client$'s goal is to broadcast a payload $p$.
$\client$ has already used 's underlying abstraction () to obtain an id $i$.
In brief, guarantees that $i$ is assigned to $\client$ only, and provides $\client$ with an assignment certificate $a$, which $\client$ can use to prove that its id is indeed $i$.
As we discussed in Section <ref>, uses -assigned ids to identify payload senders.
This is essential to 's performance, as guarantees density: as we outline in Section <ref>, $\ceil{\log_2\rp{\clientcount}}$ bits are asymptotically sufficient to represent each id in an infinitely large batch.
We discuss the details of the abstraction in Appendix <ref>, along with our implementation, .
Throughout the remainder of this paper, we say that a process $\process$ knows an id $\hat i$ iff $\process$ knows the public keys to which $\hat i$ is assigned.

Building a batch
In order to broadcast its payload $p$, $\client$ produces a signature $s$ for $p$, and then sends a  message to $\broker$ (fig. <ref>, step 1).
The  message contains $p$, $s$, and $\client$'s assignment certificate $a$.
Upon receiving the  message, $\broker$ learns $\client$'s id $i$ from $a$, then verifies $s$ against $p$.
Having done so, $\broker$ stores $\rp{i, p, s}$ in its submission pool.
For a configurable amount of time, $\broker$ fills its pool with submissions from other clients, before flushing it into a batch.
Let us use $\rp{i_1, p_1, s_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow, s_\csbalbatchingwindow}$ to enumerate the elements $\broker$ flushes from the submission pool (for some $n$, we clearly have $\rp{i, p, s} = \rp{i_n, p_n, s_n}$).
For convenience, we will also use $\client_j$ to identify the sender of $p_j$ (owner of $i_j$).
Importantly, $\broker$ flushes the pool in such a way that $i_j \neq i_k$ for all $j \neq k$: for safety reasons that will soon be clear, 's protocol prevents a client from having more than one payload in any specific batch.
Because of this constraint, some payloads might linger in $\broker$'s pool.
This is not an issue: $\broker$ will simply flush those payloads to a different batch at a later time.
When building the batch, $\broker$ splits submissions and signatures, storing $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$ separately from $s_1, \ldots, s_\csbalbatchingwindow$.

Reducing the batch
Having flushed submissions $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$ and signatures $s_1, \ldots, s_\csbalbatchingwindow$, $\broker$ moves on to reduce the batch, as exemplified in Figure <ref>. In an attempt to minimize signature overhead for servers, $\broker$ engages in an interactive protocol with clients $\client_1, \ldots, \client_\csbalbatchingwindow$ to replace as many signatures as possible with a single, batch-wide multi-signature.
In order to do so, $\broker$ organizes $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$ in a Merkle tree with root $r$ (for brevity, we call $r$ the batch's root). $\broker$ then sends an  message to each $\client_j$ (fig. <ref>, step 2).
Each  message contains $r$, along with a proof of inclusion $q_j$ for $\rp{i_j, p_j}$.
Upon receiving its  message, $\client$ checks $q_n$ against $r$.
In doing so, $\client$ comes to two conclusions. First, $\client$'s submission $\rp{i, p} = \rp{i_n, p_n}$ is part of a batch whose root is $r$.
Second, because no batch can contain multiple payloads from the same client, that batch does not attribute $\client$ any payload other than $p$.
In other words, $\client$ can be certain that $\broker$ will not broadcast some spurious payload $p' \neq p$ in $\client$'s name: should $\broker$ attempt to do that, the batch would be verifiably malformed, and immediately discarded.
This means $\client$ can safely produce a multi-signature $m$ for $r$: as far as $\client$ is concerned, the batch with root $r$ upholds integrity.
Having signed $r$, $\client$ sends $m$ to $\broker$ by means of a  message (fig. <ref>, step 3).
Upon receiving $\client_j$'s  message, $\broker$ checks $\client_j$'s multi-signature $m_j$ against $r$.
Having done so, $\broker$ discards $\client_j$'s original signature $s_j$.
Intuitively, with $m_j$, $\client_j$ attested its agreement with whatever payload the batch attributes to $\client_j$.
Because this is equivalent to individually authenticating $p_j$, $s_j$ is redundant and can be dropped.
Upon expiration of a suitable timeout, $\broker$ stops collecting  messages: clearly, if $\broker$ waited for every $\client_j$ to produce $m_j$, a single Byzantine client could prevent the protocol from moving forward by refusing to send its  message.
$\broker$ aggregates all the multi-signatures it collected for $r$ into a single, batch-wide multi-signature $m$.
In the good case, every $\client_j$ is correct and timely.
If so, $\broker$ drops all individual signatures, and the entire batch is authenticated by $m$ alone.

An example of partially reduced batch.
$B = 8$ submissions are organized on the leaves of a Merkle tree with root $r$.
Each submission $\rp{i_j, p_j}$ is originally authenticated by an individual signature $s_j$.
Upon collecting a multi-signature $m_j$ for $r$, the broker drops $s_j$.
Here the broker collected multi-signatures $m_2$, $m_5$, $m_6$ and $m_8$, leaving a straggler set $S = \cp{\rp{i_1, s_1}, \rp{i_3, s_3}, \rp{i_4, s_4}, \rp{i_7, s_7}}$.
Upon expiration of a suitable timeout, the broker aggregates $m_2$, $m_5$, $m_6$ and $m_8$ into a single multi-signature $m$.
As such, every payload in the batch is authenticated either by $m$ or by $S$.

The perks of a reduced batch
Having reduced the batch, $\broker$ is left with a sequence of submissions $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$, a multisignature $m$ on the Merkle root $r$ of $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$, and a straggler set $S$ holding the individual signatures that $\broker$ failed to reduce.
More precisely, $S$ contains $\rp{i_j, s_j}$ iff $\broker$ did not receive a valid  message from $\client_j$ before the reduction timeout expired.
We recall that $m$'s size is constant, and $S$ is empty in the good case.
Once reduced, the batch is cheap to authenticate: it is sufficient to verify the batch's multi-signature against the batch's root, and each straggler signature against its individual payload.
More precisely, let $T$ denote the set of timely clients ($\client_j$ is in $T$ iff $(i_j, \tail)$ is not in $S$).
Let $t$ denote the aggregation of $T$'s public keys.
Provided with $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$, $m$ and $S$, any process that knows $i_1, \ldots, i_\csbalbatchingwindow$ can verify that the batch upholds integrity by: (1) computing $r$ and $t$ from $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$ and $S$; (2) using $t$ to verify $m$ against $r$; and (3) verifying each $s_j$ in $S$ against $p_j$.
In the good case, authenticating the batch reduces to verifying a single multi-signature.
This is regardless of the batch's size.

The pitfalls of a reduced batch
As we discussed in the previous paragraph, reducing a batch makes it cheaper to verify its integrity.
Reduction, however, hides a subtle trade-off: once reduced, a batch gets easier to authenticate as whole.
Its individual payloads, however, become harder to authenticate.
For the sake of simplicity, let us imagine that $\broker$ successfully dropped all the individual signatures it originally gathered from $\client_1, \ldots, \client_\csbalbatchingwindow$.
In order to prove that $\rp{\client = \client_n}$ broadcast $\rp{p = p_n}$, $\broker$ could naively produce the batch's root $r$, $\rp{i_n, p_n}$'s proof of inclusion $q_n$, and the batch's multi-signature $m$ for $r$.
This, however, would not be sufficient to authenticate $p$: because the multi-signature $m_n$ that $\client$ produced for $r$ was aggregated with all others, $m$ can only be verified by the aggregation of all $\client_1, \ldots, \client_\csbalbatchingwindow$'s public keys.
This makes authenticating $p$ as expensive as authenticating the entire batch: in order to verify $m$, all $\rp{i_j, p_j}$ must be produced and checked against $r$, so that all corresponding public keys can be safely aggregated.

Witnessing the batch
As we discuss next, proving the integrity of individual payloads is fundamental to ensure 's validity.
In brief, to prove that some $\client_k$ equivocated its payload $p_k = \rp{c_k, l_k}$, a server must prove to $\broker$ that $\client_k$ also issued some payload $p'_k = \rp{c_k, l'_k \neq l_k}$.
Lacking this proof, a single Byzantine server could, for example, claim without basis that $\client$ equivocated $p$.
This could trick $\broker$ into excluding $p$, thus compromising 's validity.
As we discussed in the previous paragraph, however, proving the integrity of an individual payload in a reduced batch is difficult.
While we conjecture that purely cryptographic solutions to this impasse might be achievable in some schemes[For example, using BLS, $\broker$ could aggregate the public keys of $\client_1, \ldots, \client_{n - 1}, \client_{n + 1}, \ldots, \client_\csbalbatchingwindow$ into a public key $\tilde t_n$, then show that the aggregation of $\tilde t_n$ with $\client$'s public key correctly verifies $m$ against $r$.
Doing so, however, would additionally require $\broker$ to exhibit a proof that $\tilde t_n$ is not a rogue public key, i.e., that $\tilde t_n$ indeed results from the aggregation of client public keys.
This could be achieved by additionally having $\client_1, \ldots, \client_\csbalbatchingwindow$ multi-sign some hard-coded statement to prove that they are not rogues.
$\broker$ could aggregate such signatures on the fly, producing a rogue-resistance proof for $\tilde t_n$ that can be transmitted and verified in constant time.
This, however, is expensive (and, frankly, at the limit of our cryptographic expertise).], has $\broker$ engage in a simple protocol to further simplify the batch's authentication, replacing all client-issued (multi-)signatures with a single, server-issued certificate.
Having collected and reduced the batch, $\broker$ sends a  message to all servers (fig. <ref>, step 4).
The  message only contains $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$.
Upon receiving the  message, $\server$ collects in a set $U_\server$ all the ids it does not know ($i_j$ is in $U_\server$ iff $\server$ does not know $i_j$), and sends $U_\server$ back to $\broker$ by means of a  message (fig. <ref>, step 5).
Upon receiving $\server$'s  message, $\broker$ builds a set $A_\server$ containing all id assignments that $\server$ is missing ($a_j$ is in $A_\server$ iff $i_j$ is in $U_\server$).
Having done so, $\broker$ sends a  message to $\server$ (fig. <ref>, step 6).
The  message contains the batch's multi-signature $m$, the straggler set $S$, and $A_\server$.
We underline the importance of sending id assignments upon request only.
Thinking to shave one round-trip off the protocol, $\broker$ could naively package in a single message all submissions, all (multi-)signatures, and all assignments relevant to the batch.
In doing so, however, $\broker$ would force each server to receive one assignment per submission, immediately forfeiting 's oracular efficiency.
As we discuss in Section <ref>, at the batching limit we assume that all servers already know all broadcasting clients.
In that case, both $U_\server$ and $A_\server$ are constant-sized, empty sets, adding only a vanishing amount of communication complexity to the protocol.
Upon receiving the  message, $\server$ verifies and learns all assignments in $A_\server$.
Having done so, $\server$ knows $i_1, \ldots, i_\csbalbatchingwindow$.
As we outlined above, $\server$ can now efficiently authenticate the whole batch, verifying $m$ against the batch's root $r$, and each $i_j$ in $S$ against $p_j$.
Having established the integrity of the whole batch, $\server$ produces a witness shard for the batch, i.e., a multi-signature $w_\server$ for $\qp{\texttt{Witness}, r}$, effectively affirming to have successfully authenticated the batch.
$\server$ sends $w_\server$ back to $\broker$ by means of a  message (fig. <ref>, step 7).
Having received a valid  message from $f + 1$ servers, $\broker$ aggregates all witness shards into a witness $w$.
Because $w$ is a plurality ($f+1$) certificate, at least one correct server necessarily produced a witness shard for the batch.
This means that at least one correct server has successfully authenticated the batch by means of client (multi-)signatures.
Because $w$ could not have been gathered if the batch was not properly authenticated, $w$ itself is sufficient to authenticate the batch, and $\broker$ can drop all (now redundant) client-generated (multi-)signatures for the batch.
Unlike $m$, $w$ is easy to verify, as it is signed by only $f + 1$, globally known servers.
Like $m$, $w$ authenticates $r$.
As such, any $p_j$ can now be authenticated just by producing $w$, and $\rp{i_j, p_j}$'s proof of inclusion $q_j$.

Gathering a commit certificate
Having successfully gathered a witness $w$ for the batch, $\broker$ sends $w$ to all servers by means of a  message (fig. <ref>, step 8).
Upon receiving the  message, $\server$ moves on to check $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$ for equivocations.
More precisely, $\server$ builds a set of exceptions $E_\server$ containing the ids of all equivocating submissions in the batch ($i_j$ is in $E_\server$ iff $\server$ previously observed $\client_j$ submit a payload $p'_j$ that conflicts with $p_j$; we recall that $p_j$ and $p'_j$ conflict if their contexts are the same, but their messages are different).
$\server$ then produces a commit shard for the batch, i.e., a multi-signature $c_\server$ for $\qp{\texttt{Commit}, r, E_\server}$, effectively affirming that $\server$ has found all submissions in the batch to be non-equivocated, except for those in $E_\server$.
In the good case, every client is correct and $E_\server$ is empty.
Having produced $c_\server$, $\server$ moves on to build a set $Q_\server$ containing a proof of equivocation for every element in $E_\server$.
Let us assume that $\server$ previously received from some $\client_k$ a payload $p'_k$ that conflicts with $p_k$.
$\server$ must have received $p'_k$ as part of some witnessed batch.
Let $r'_k$ identify the root of $p'_k$'s batch, let $w'_k$ identify $r'_k$'s witness, let $q'_k$ be $\rp{i_k, p'_k}$'s proof of inclusion in $r'_k$.
By exhibiting $\rp{r'_k, w'_k, p'_k}$, $\server$ can prove to $\broker$ that $\client_k$ equivocated: $p_k$ conflicts with $p'_k$, and $\rp{i_k, p'_k}$ is provably part of a batch whose integrity was witnessed by at least one correct server.
Furthermore, because correct clients never equivocate, $\rp{r'_k, w'_k, p'_k}$ is sufficient to convince $\broker$ that $\client_k$ is Byzantine.
For each $i_j$ in $E_\server$, $\server$ collects in $Q_\server$ a proof of equivocation $\rp{r'_j, w'_j, p'_j}$.
Finally, $\server$ sends a  message back to $\broker$ (fig. <ref>, step 9).
The  message contains $c_\server$, $E_\server$ and $Q_\server$.
Upon receiving $\server$'s  message, $\server$ verifies $c_\server$ against $r$ and $E_\server$, then checks all proofs in $Q_\server$.
Having collected valid  messages from a quorum of servers $\server_1, \ldots, \server_{2f + 1}$, $\broker$ aggregates all commit shards into a commit certificate $c$.
We underline that each $\server_j$ signed the same root $r$, but a potentially different set of exceptions $E_{\server_j}$.
Let $E$ denote the union of $E_{\server_1}, \ldots, E_{\server_{2f + 1}}$.
We call $E$ the batch's exclusion set.
Because a proof of equivocation cannot be produced against a correct client, $\broker$ knows that all clients identified by $E$ are necessarily Byzantine.
In particular, because $\client$ is correct, $\rp{i = i_n}$ is guaranteed to not be in $E$.

Committing the batch
Having collected a commit certificate $c$ for the batch, $\broker$ sends $c$ to all servers by means of a  message (fig. <ref>, step 10).
Upon receiving the  message, $\server$ verifies $c$, computes the exclusion set $E$, then delivers every payload $p_j$ whose id $i_j$ is not in $E$.
Recalling that $c$ is assembled from a quorum of commit shards, at least $f + 1$ correct servers contributed to $c$.
This means that, if some $i_k$ is not in $E$, then at least $f + 1$ correct servers found $p_k$ not to be equivocated.
As in most BRB implementations <cit.>, this guarantees that no two commit certificates can be gathered for equivocating payloads: 's consistency is upheld.

The role of equivocation proofs
As the reader might have noticed, $\broker$ does not attach any proof of equivocation to its  message.
Having received $\broker$'s commit certificate $c$, $\server$ trusts $\broker$'s exclusion set $E$, ignoring every payload whose id is in $E$.
This is not because $\server$ can trust $\broker$ to uphold validity.
On the contrary, $\server$ has no way to determine that $\broker$ is not maliciously excluding the payload of a correct client.
Indeed, even if $\server$ were to verify a proof of exclusion for every element in $E$, a malicious $\beta$ could still censor a correct client simply by ignoring its  message in the first place.
Equivocation proofs are fundamental to 's validity not because they force malicious brokers to uphold validity, but because they enable correct brokers to do the same.
Thanks to equivocation proofs, a malicious server cannot trick a correct broker into excluding the payload of a correct client.
This is enough to guarantee validity.
As we discuss below, $\client$ successively submits $p$ to all brokers until it receives a certificate attesting that $p$ was delivered by at least one correct server.
Because we assume at least one broker to be correct, $\client$ is eventually guaranteed to succeed.

Notifying the clients
Having delivered every payload whose id is not in the exclusion set $E$, $\server$ produces a completion shard for the batch, i.e., a multi-signature $z_\server$ for $\qp{\texttt{Completion}, r, E}$, effectively affirming that $\server$ has delivered all submissions in the batch whose id is not in $E$.
$\server$ sends $z_\server$ to $\broker$ by means of a  message (fig. <ref>, step 11).
Upon receiving $f + 1$ valid  messages, $\broker$ assembles all completion shards into a completion certificate $z$.
Finally, $\broker$ sends a  message to $\client_1, \ldots, \client_\csbalbatchingwindow$ (fig. <ref>, step 12).
The  message contains $z$ and $E$.
Upon receiving the  message, $\client$ verifies $z$ against $E$, then checks that $i$ is not in $E$.
Because at least one correct server contributed a completion shard to $z$, at least one correct process delivered all payloads that $E$ did not exclude, including $p$.
Having succeeded in broadcasting $p$, $\client$ does not need to engage further, and can stop successively submitting $p$ to all brokers.

No one is left behind
As we discussed above, upon receiving the commit certificate $c$, $\server$ delivers every payload in the batch whose id is not in the exclusion set $E$.
Having gotten at least one correct server to deliver the batch, $\broker$ is free to disengage, and moves on to assembling and brokering its next batch.
In a moment of asynchrony, however, all communications between $\broker$ and $\tilde \server$ might be arbitrarily delayed.
This means that $\tilde \server$ has no way of telling whether or not it will eventually receive batch and commit certificate: a malicious $\broker$ might have deliberately left $\tilde \server$ out of the protocol.
Server-to-server communication is thus required to guarantee totality.
Having delivered the batch, $\server$ waits for an interval of time long enough for all correct servers to deliver batch and commit certificate, should the network be synchronous and $\broker$ correct.
$\server$ then sends to all servers an  message (fig. <ref>, step 13).
The  message contains the batch's root $r$, and the exclusion set $E$.
In the good case, upon receiving $\server$'s  message, every server has delivered the batch and ignores the offer.
This, however, is not the case for slow $\hat \server$, which replies to $\server$ with an  message (fig. <ref>, step 14).
Upon receiving $\tilde \server$'s  message, $\server$ sends back to $\tilde \server$ a  message (fig. <ref>, step 15).
The  message contains all submissions $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$, id assignments for $i_1, \ldots, i_\csbalbatchingwindow$, and the commit certificate $c$.
Upon delivering $\server$'s  message, $\tilde \server$ computes $r$ from $\rp{i_1, p_1}, \ldots, \rp{i_\csbalbatchingwindow, p_\csbalbatchingwindow}$, checks $c$ against $r$, computes $E$ from $c$, and delivers every payload $p_j$ whose id $i_j$ is not in $E$.
This guarantees totality and concludes the protocol.

§.§ Complexity

As we introduced in Section <ref>, uses ids assigned by its underlying () abstraction to identify payload senders.
A -assigned id is composed of two parts: a domain and an index.
Domains form a finite set $\domains$ whose size does not increase with the number of clients, indices are natural numbers.
Along with safety (e.g., no two processes have the same id) and liveness (e.g., every correct client that requests an id eventually obtains an id), guarantees density: the index part of any id is always smaller than the total number of clients $\clientcount$ (i.e., each id index is between $0$ and $\rp{\clientcount - 1}$).
Intuitively, this echoes the (stronger) density guarantee provided by , the oracle-based implementation of we introduced in Section <ref> to bound 's performance.
In , the oracle organizes all clients in a list, effectively labeling each client with an integer between $0$ and $\rp{\clientcount - 1}$.
In a setting where consensus cannot be achieved, agreeing on a totally-ordered list of clients is famously impossible: a consensus-less implementation cannot assign ids if $\abs{\domains} = 1$.
As we show in Appendix <ref>, however, can be implemented without consensus if servers are used as domains ($\domains = \servers$).
In our implementation , each server maintains an independent list of public keys.
In order to obtain an id, a client $\client$ has each server add its public key to its list, then selects a server $\server$ to be its assigner.
In doing so, $\client$ obtains an id $\rp{\server, n}$, where $n \in 0..\rp{\clientcount - 1}$ is $\client$'s position in $\server$'s log.
In summary, a consensus-less implementation of still guarantees that indices will be smaller than $\clientcount$, at the cost of a non-trivial domain component for each id.
This inflates the size of each individual id by $\ceil{\log_2\rp{\abs{\domains}}}$ bits.

Batching ids
While -assigned ids come with a non-trivial domain component, the size overhead due to domains vanishes when infinitely many ids are organized into a batch.
This is because domains are constant in the number of clients.
Intuitively, as infinitely many ids are batched together, repeated domains become compressible.
When building a batch, a broker represents the set $I$ of sender ids not as a list, but as a map $\tilde i$.
To each domain, $\tilde i$ associates all ids in $I$ under that domain ($n$ is in $\tilde i\qp{d}$ iff $\rp{d, n}$ is in $I$).
Because $\tilde i$'s keys are fixed, as the size of $I$ goes to infinity, the bits required to represent $\tilde i$'s keys are completely amortized by those required to represent $\tilde i$'s values.
At the batching limit, the cost of representing each id in $\tilde i$ converges to that of representing its index only, $\ceil{\log_2\rp{\clientcount}}$.

Protocol cost
As we discuss in Section <ref>, at the batching limit we assume a good-case execution: links are synchronous, all processes are correct, and the set of brokers contains only one element. We additionally assume that infinitely many clients broadcast concurrently. Finally, we assume all servers to already know all broadcasting clients. Let $\broker$ denote the only broker. As all broadcasting clients submit their payloads to $\broker$ within a suitably narrow time window, $\broker$ organizes all submissions into a single batch with root $r$. Because links are synchronous and all clients are correct, every broadcasting client submits its multi-signature for $r$ in time. Having removed all individual signatures from the batch, $\broker$ is left with a single, aggregated multi-signature $m$ and an empty straggler set $S$. $\broker$ compresses the sender ids and disseminates the batch to all servers. As $m$ and $S$ are constant-sized, the amortized cost for a server to receive each payload $p$ is $\rp{\ceil{\log_2\rp{\clientcount}} + \abs{p}}$ bits. As $m$ authenticates the entire batch, a server authenticates each payload at an amortized cost of $0$ signature verifications. The remainder of the protocol unfolds as a sequence of constant-sized messages: because all broadcasting clients are known to all servers, no server requests any id assignment; witnesses are always constant-sized; and because all processes are correct, no client equivocates and all exception sets are empty. Finally, again by the synchrony of links, all offers of totality are ignored. In summary, at the batching limit a server delivers a payload at an amortized cost of $0$ signature verifications and $\rp{\ceil{\log_2\rp{\clientcount}} + \abs{p}}$ bits exchanged.

As depicted in Figure <ref>, the latency of is 10 message delays in the synchronous case (fast servers deliver upon receiving the broker’s Commit message), and at most 13 message delays in the asynchronous case (slow servers deliver upon receiving other servers’ Totality messages).
By comparison, the latency of the optimistic reliable broadcast algorithm by Cachin et al. <cit.> is respectively 4 message delays (synchronous case) and 6 message delays (asynchronous case).
Effectively, trades oracular efficiency for a constant latency overhead.

Worst-case complexity
In the worst case, a server delivers a $b$-bits payload by exchanging $O\rp{\rp{\log\rp{\clientcount} + b} \brokercount \servercount}$ bits, where $\clientcount$, $\brokercount$ and $\servercount$ respectively denote the number of clients, brokers and servers. In brief, the same id, payload and signature is included by each broker in a different batch (hence the $\brokercount$ term) and propagated in an all-to-all fashion (carried by  messages) across correct servers (hence the $\servercount$ term). By comparison, the worst-case communication complexity of Cachin et al.'s optimistic reliable broadcast is $O\rp{l \servercount}$ per server, where $l$ is the length of the broadcast payload. A direct batched generalization of the same algorithm, however, would raise the worst-case communication to $O\rp{l \servercount^2}$ per server, similar to that of when $\servercount \sim \brokercount$. Both batched Bracha and can be optimized by polynomial encoding, reducing their per-server worst-case complexity to $O(l \servercount)$ and $O(\rp{\log\rp{\clientcount} + b} \brokercount)$ respectively. Doing so for , however, is beyond the scope of this paper.

§ CONCLUSIONS

Our contributions
In this paper we study (), a multi-shot variant of Byzantine Reliable Broadcast (BRB) whose interface is split between broadcasting clients and delivering servers. We introduce , a toy implementation of that relies on a single, infallible oracle to uphold all properties. Unless clients can be assumed to broadcast at a non-uniform rate, 's signature and communication complexities are optimal: in , a server delivers a payload $p$ by performing $0$ signature verifications, and exchanging $\rp{\ceil{\log_2\rp{\clientcount}} + \abs{p}}$ bits, where $\clientcount$ is the number of clients. We present , our implementation of . upholds all properties under classical BRB assumptions (notably asynchronous links and less than a third of faulty servers). When links are synchronous and all processes are correct, however, and at the limit of infinite concurrently broadcasting clients, 's signature and communication complexities match those of .

Future work
We hope to extend to allow multiple messages by the same client in the same batch.
We envision that this could be achieved by using other types of cryptographic accumulators or variants of Merkle trees, such as Merkle-Patricia trees <cit.>.
It would also be interesting to see if the worst-case performance of could be improved, e.g. by using error correction codes (ECC) or erasure codes, without significantly affecting its good-case performance.
Lastly, we hope to use 's keys ideas to implement a total-order broadcast primitive, improving the scalability of existing SMR implementations.

§ : FULL ANALYSIS

§ : FULL ANALYSIS

§ PSEUDOCODE

§.§ Client

§.§ Broker

§.§ Server

§.§ Server