# Efficient O(n^2) Byzantine Fault-Tolerant Asynchronous Approximate Agreement

5 minute read

Published:

In this post, I will describe a new and efficient Asynchronous Approximate Agreement($\epsilon$-agreement) protocol with only $\mathcal{O}(n^2)$ bits of communication per round. Our protocol requires honest nodes to only have binary inputs, where every honest node’s input $V_i \in {v_0,v_1}$, where both $v_0$ and $v_1$ are publicly known and $\Delta = v_1-v_0$.

# Background

The Asynchronous Approximate Agreement or $\epsilon$-agreement primitive allows a set of nodes to approximately agree on a value within the convex-hull of honest nodes’ inputs. This protocol circumvents the prominent Fischer-Lynch-Patterson(FLP)-impossibility result, which states that no deterministic asynchronous protocol can achieve agreement amongst a set of nodes with at least one crashed node. Any $\epsilon$-agreement protocol must satisfy the following three properties.

1. Termination: Every honest node $i$ must eventually decide a value $v_i$.
2. $\epsilon$-agreement: The decided values $v_i,v_j$ of any honest nodes $i,j$ must be within $\epsilon$ distance of each other. $|v_i-v_j| < \epsilon \forall i,j \in \{1,..,n\}$
3. Convex-Hull Validity: The decided value $v_i$ of any honest node must be within the convex-hull of honest nodes’ inputs. $\min(\mathcal{V})\leq v_i \leq \max(\mathcal{V})$

Abraham, Amit and Dolev’s[1] $\epsilon$-agreement protocol achieves all the three properties with an optimal resilience of $1/3$ faults and has a communication complexity of $\mathcal{O}(\kappa n^3)$ bits. The $\kappa$ factor in communication complexity results from the use of Das, Xiang, and Ren’s[2]Reliable Broadcast protocol. If instead Bracha’s RBC was used, the communication complexity of Abraham, Amit, and Dolev’s[1] $\epsilon$-agreement would be $\mathcal{O}(n^4)$ bits.

# Preliminaries

We define the Asynchronous Crusader Agreement primitive, also referred to as 1-slot Proxcensus in Fitzi, Liu-Zhang, and Loss[3].

A crusader agreement protocol $\mathcal{C}$ amongst $n$ nodes must guarantee the following properties.

1. Agreement: If two honest nodes decide values x and y, then either x=y or at least one of the values is $\perp$
2. Liveness: All honest nodes eventually decide and then eventually terminate
3. Validity: If all honest nodes have the same input x, then they must output x

Using this primitive, I build an $\epsilon$-agreement protocol.

# Protocol

I will briefly describe the protocol in Algorithm 1. Each node $i$ broadcasts an ECHO message for its value $V_{i}$. It also broadcasts an ECHO for any other value $V’ \neq V_{i}$ for which it received $f+1$ ECHOs. For a value $v$ to receive $f+1$ ECHOs, at least one non-faulty node must have input $v$ to the protocol. Once a node receives $n-f$ ECHO messages for value $V$, it broadcasts an ECHO2 message for $V$. It waits until it receives $n-f$ ECHOs for two different values $V,V’$ to output $\perp$ or until it receives $n-f$ ECHO2 messages for a single value $V$. In the former case, it updates its state for round $r+1$ as $V_{i} = \frac{V+V’}{2}$, and in the latter case, it updates its state as $V_{i} = V$.

If a node receives $n-f$ ECHO2s for a single value $V$, then no other sensor can receive $n-f$ ECHO2s for any other value $V’ \neq V$. Therefore, after round $1$, non-faulty sensors’ values can be characterized by the following four sets: 1. ${v_{0}}$, 2. ${v_{0},\frac{v_{0}+v_{1}}{2}}$,3. ${\frac{v_{0}+v_{1}}{2},v_{1}}$, 4. ${v_{1}}$, and all four sets have the difference between their states $\Delta_1 \leq \frac{v_{1}-v_{0}}{2}$. After $\log_{2}(\frac{v_{1}-v_{0}}{\epsilon})$ rounds, the nodes achieve $\epsilon$-agreement.

The main intuition behind the reduced communication complexity is that we simplify the node-centric broadcast phase using $n$-parallel reliable broadcasts from Abraham, Amit, and Dolev and replace it with a value-centric broadcast phase derived from Asynchronous crusader agreement. The former phase involves every node participating in the reliable broadcast of every other node, leading to an $\mathcal{O}(n^3)$ factor in communication complexity. However, since our protocol deals with a restricted domain with only two values, the value-centric phase has an $\mathcal{O}(n)$ factor of improvement over the node-centric broadcast phase.

## Proof Sketch

We first prove that if the protocol is in a bivalent state in round $r$, it must move to a bivalent or univalent state in round $r+1$. Assuming nodes start round $r$ of the protocol with values $c_0’$ and $c_1’$. From the properties of Crusader agreement, the protocol moves into state ${c_0’,\perp}$ or ${c_1’,\perp}$. Honest nodes receiving \bottom update their value to $v = \frac{c_0’+c_1’}{2}$, which implies that the range of honest values reduces to $\frac{c_1’-c_0’}{2}$.

In contrast, if the state after round $r$ is univalent, the nodes have already agreed, which implies that the range of honest inputs reduces by at least a factor of $\frac{1}{2}$. Therefore, after at most $\log_2(\frac{\Delta}{\epsilon})$ rounds, the protocol achieves \approxconsensus.

# Complexity Analysis

In each round, every node broadcasts an ECHO message for at most two values, and an ECHO2 message for at most one value. Therefore, each round of $\epsilon$-agreement through this protocol costs only $\mathcal{O}(n^2)$ messages, with each message of size $\mathcal{O}(\log(\frac{\Delta}{\epsilon}))$ bits. Therefore, $\mathcal{O}(\log(\frac{\Delta}{\epsilon}))$ rounds costs $\mathcal{O}(n^2\log^2(\frac{\Delta}{\epsilon}))$ bits overall to achieve $\epsilon$-agreement.

## References

[1] Abraham, Ittai, Yonatan Amit, and Danny Dolev. “Optimal resilience asynchronous approximate agreement.” In Principles of Distributed Systems: 8th International Conference, OPODIS 2004, Grenoble, France, December 15-17, 2004, Revised Selected Papers 8, pp. 229-239. Springer Berlin Heidelberg, 2005.

[2] Das, Sourav, Zhuolun Xiang, and Ling Ren. “Asynchronous data dissemination and its applications.” In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 2705-2721. 2021.

[3] Fitzi, Matthias, Chen-Da Liu-Zhang, and Julian Loss. “A new way to achieve round-efficient Byzantine agreement.” In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 355-362. 2021.

Tags: