A very useful tool in Asynchronus distributed computing is Reliable Broadcast, or simply called Broadcast. It allows a leader to send a message, knowing that all parties will eventually receive the same message, even if a malicious adversary control $f$ parties and $f<n/3$. Broadcast is deterministic and takes just a constant number of rounds.
A natural extension of broadcast is a Multi-Broadcast, where each party has an input. Ideally, you may want all parties to agree on the same set of outputs. We discuss this primitive, called Agreement on a Core Set (ACS) in a separate post (also see Canetti page 15). ACS requires to solve Consensus in asynchrony, which we know must have infinite executions. Running ACS typically also incurs high costs, traditionally using $n$ binary agreements.
In this post, we explore a surprising alternative, called Gather which runs in a constant number of rounds. To the best of our knowledge, this primitive first appeared as the main building block in Canetti and Rabin’s Asynchronous Byzantine Agreement protocol. Variations of this primitive have many uses, for example in Asynchronous Approximate Agreement, Asynchronous Distributed Key Generation and recently for multi-valued oblivious common coin and ACS in constant expected time.
In a Gather protocol, each party has an input, and each party outputs a set of received values and the parties who sent them (i.e. of pairs $(j,x)$ where $j$ is the index of a party, and $x$ is the value it sent). The properties are:
-
Common core: There exists a core set $S^{*}$ of size at least $n-f$ such that all nonfaulty parties include $S^{*}$ in their output set.
-
Validity: If a nonfaulty party includes $(j,x_j)$ in its output set, and $j$ is a nonfaulty party, then $x_j$ must be $j$’s input.
-
Agreement: All parties that include some pair for a party $j$ agree on the value it sent. More precisely, if two nonfaulty parties include the pairs $(j,x)$ and $(j,x’)$ in their outputs, then $x=x’$.
At first glance, it may seem as if Gather is solving agreement, but that is not the case! The crucial observation is that all parties output a set that includes the core $S^{*}$ but they don’t necessarily know what $S^{*}$ is.
The basic Gather protocol
We will define $x_i$ to be party $i$’s input. Since this protocol uses broadcast, we will assume that $f<\frac{n}{3}$. The protocol proceeds in $4$ conceptual rounds that look very similar to each other:
- Broadcast $x_i$ (using Bracha’s Reliable Broadcast protocol).
- Define the set $S_i$ of pairs $(j,x_j)$, where $x_j$ was received from $j$. Once $S_i$ contains $n-f$ pairs send $S_i$ to every party.
- When receiving a message $S_j$ from party $j$, accept the message after receiving the broadcast $x_k$ from $k$ for every $(k,x_k)\in S_j$. After accepting $n-f$ sets $S_j$, send $T_i=\cup S_j$ to all parties.
- When receiving a message $T_j$ from party $j$, accept the message after receiving the broadcast $x_k$ from $k$ for every $(k,x_k)\in T_j$. After accepting $n-f$ sets $T_j$, output $U_i=\cup T_j$.
See the similarity in rounds 3 and 4? it may seem like adding another identical round doesn’t do much, but we will see that is not the case at all. Let’s try to understand the protocol gradually and see what each round adds to the process.
Round breakdown
Rounds 1-2
We start off by Broadcasting values (via Reliable Broadcast), then collect $n-f$ broadcasted values and send them as a set. So if an honest party accepts some set then eventually all honest parties will accept that set. Hence the Agreement and Validity properties of Gather follow from the Agreement and Validity properties of Reliable Broadcast.
Round 3
The first non-trivial property we achieve happens after nonfaulty parties accept $n-f$ $S$ sets:
- Weak core: Let $G$ be the $n-f$ first nonfaulty parties that complete round 3. There exists a round 2 set $S^{*}$ sent by a nonfaulty party such that $f+1$ nonfaulty parties include $S^{*}$ in their $T$ sets. More formally: there exists a set $W \subset G$ of size $|W|=f+1$, such that for any $i\in W$, $S^{*}\subseteq T_i$.
Lets count how many sets are received by $G$ that are sent from nonfaulty parties in round 2. Since each party in $G$ gathers $n-f$ sets in round 3, then at least $n-2f$ of those set were sent from nonfaulty parties. By assumption $f<\frac{n}{3}$, so $n-2f\geq f+1$. Hence, each nonfaulty party in $G$ receives round 2 sets from at least $f+1$ nonfaulty parties. In total, parties in $G$ receive at least $(f+1)(n-f)$ round 2 sets.
Assume the property above is false, so every round 2 set from a nonfaulty party is received by at most $f$ nonfaulty parties in $G$. This means that the total number of rounds 2 sets from nonfaulty parties that are received by nonfaulty parties is at most $f(n-f)$. This is a contradiction (clearly $f(n-f)<(f+1)(n-f)$).
Round 4
We use the weak core property to achieve a common core in one more round.
- Common core: There exists a round 2 set $S^{*}$ sent by a nonfaulty party that all nonfaulty parties include in their $U$ sets.
By the weak core property, there is a set $S^{*}$ such that at least $|W|=f+1$ nonfaulty parties include $S^{*}$ in their round 3 sets. Every nonfaulty party computes their round 4 sets as a union of $n-f$ round 3 sets. By quorum intersection of $n-f$ and $f+1$, at least one such set must have come from $W$, hence $U$ must include $S^{*}$. Note that $S^{*}$ is of size $n-f$ or greater because nonfaulty parties wait for their round 2 sets to be of that size before sending them. This means that our common core also fulfills our size requirement.
Gather protocol complexity
Each party sends a single broadcast (which requires $O(n^2)$ words), requiring $O(n^3)$ words to be sent overall. In addition, we have a constant number of all-to-all communication rounds in which parties send sets of $O(n)$ elements to each other. This also totals in $O(n^3)$ words sent overall. This brings our sum-total to $O(n^3)$ words sent overall.
In future posts, we will talk about how to enhance the Gather protocol even further: add binding properties, add verification properties and see how cryptography can help… stay tuned!
Please answer/discuss/comment/ask on Twitter.