Validity in Network-Agnostic Byzantine Agreement

The foundational investigation into general validity properties was initiated by Civit et al. [8] for the partially synchronous model. Subsequently, Civit et al. [7] embarked on a follow-up study, extending their analysis to the synchronous model. Both works provide a complete characterization, identifying the necessary and sufficient conditions for solving a validity property deterministically. We also note that the contributions of [8, 7] extend beyond this characterization, an important side of these works lying in the exploration of lower bounds on message complexity. This generalizes the well-established Dolev-Reischuk bound on message complexity for BA with strong unanimity [15] to encompass the broader landscape of non-trivial validity properties. Considerations of message complexity are outside our scope. We also note that probabilistic validity properties are outside the scope of the analysis of Civit et al, and also outside our scope. A notable example is qualitative validity, introduced by Goren et al [25].

Designing protocols that achieve security guarantees in both synchronous and asynchronous networks has been the subject of an extensive line of work. The network-agnostic paradigm was introduced by Blum, Katz and Loss [4]. The work of [4] shows that, if a public key infrastructure is provided, BA with strong unanimity can be achieved if and only if $n>2\cdot t_s+t_a$. Further works on network-agnostic BA with strong unanimity have focused on improving the efficiency guarantees [12, 13].

Due to its broad applicability, convex validity within the network-agnostic communication paradigm has attracted increased attention. Ghinea, Liu-Zhang and Wattenhofer [20, 21] have investigated the feasibility of achieving convex validity for a weaker variant of BA, known as Approximate Agreement [14, 1]. In particular, [20] shows that Approximate Agreement on real numbers is solvable under the same necessary and sufficient condition $n>2\cdot t_s+t_a$ assuming a public key infrastructure. Building on the previous, [21] gives sufficient conditions for the multidimensional variant of the problem that match the known requirements in the pure synchronous and asynchronous models [32, 28]. Returning to the non-approximate version, Constantinescu et al. [11] have provided the tight conditions for network-agnostic BA with convex validity for abstract convex spaces. In this case, the conditions include $n>2\cdot t_s+t_a$ or, if no cryptographic setup is available, $n>3\cdot t_s$, along with a few additional conditions that depend on the Helly number of the convexity space.

Other takes on network-agnostic BA have been considered, such as scaling the validity guarantees with the network conditions: for real-valued inputs, [10] proposes a protocol for BA with median validity guaranteeing that the output is closer to the honest inputs’ median when the network is synchronous than when it is asynchronous. This protocol simultaneously matches the optimal closeness guarantees for purely synchronous [31, 27] and purely asynchronous [10] networks. Such validity properties that scale with the network conditions are outside our scope.

As outlined above, the conditions $n>2\cdot t_s+t_a$ and, if no cryptographic setup is available, $n>3\cdot t_s$, have been proven to be necessary for strong unanimity properties, i.e., stronger than strong unanimity [4]. Our work shows that this is a requirement for weaker validity properties as well, i.e., for any non-trivial property. We find this result surprising especially for weak validity: if all parties are honest and hold input $v$, then the output agreed upon must be $v$. Assuming a public key infrastructure, this property is solvable in the synchronous model for , as a straightforward application of the Dolev-Strong broadcast protocol [16]. On the other hand, our result implies that if we expect a BA protocol with weak validity to remain secure in the asynchronous model even for no corruptions (i.e., $t_a=0$), then the synchronous resilience threshold steps down from to .

In contrast to the work of [11] regarding network-agnostic BA with convex validity, our results move the difficulty of proving such feasibility results as a whole to only verifying whether a validity condition satisfies our similarity condition. That is, one can show that convex validity satisfies this similarity condition if and only if the necessary Helly number-based conditions of [11] hold. Our impossibility arguments diverge: we investigate these under any validity property, while the work of [11] considers a fixed validity property but also shows impossibility under weaker agreement requirements. On the other hand, our protocol matching our lower bounds is a more general variant of the protocol of [11].

Our paper provides a characterization similar to those of [8, 7] for the synchronous and partially synchronous settings, respectively. The key difference is that these two models allow for deterministic protocols, while the network-agnostic model inherently requires randomization for achieving BA when $t_a>0$ [19]. Consequently, the focus shifts towards randomized protocols, requiring our proofs to employ different techniques. While the arguments behind the containment condition of [7] can be easily adapted for randomized protocols, this is not immediate for their proof that $n>3\cdot t_s$ is necessary when no cryptographic setup is available. Our proof for this lower bound, in fact, assumes the synchronous setting and, therefore, strengthens the characterization of [7]. Summing up, their necessary conditions now hold even for randomized protocols, and, as shown in their paper, they can be matched by deterministic protocols.

Denote the two parties by $P_1$ and $P_2$. Let $\omega \in \mathrm{\Omega }$. For every input configuration, we will define a finite number of executions using randomness $\omega$, including the required canonical executions. Under the assumption that all executions defined for $\omega$ decide, we show that all canonical executions using randomness $\omega$ decide the same value $v$. From here, our proof proceeds as follows: individually, each defined execution decides almost surely (by construction). The number of executions defined for each input configuration is finite, and the set of input configurations is countable (since $V_{\text{in}}$ is countable). A countable intersection of events holding almost surely holds almost surely. Then, almost surely, all defined executions for $\omega$ decide, i.e., our additional assumption holds almost surely, completing the proof. $◀$

Hence, from now on, we fix $\omega \in \mathrm{\Omega }$ and only consider executions running with this randomness $\omega$. We assume that all executions we consider decide, and we want to show that all canonical executions decide the same value $v$.

We first consider canonical executions where one of the parties crashes. Let $v_1,v_2\in V_{\text{in}}$ be two arbitrary values. First, we consider the canonical execution ${\epsilon }_1(\omega )$ of $A$ (in a synchronous network) where $P_1$ is honest and has input $v_1$. $P_2$ is corrupted and crashes at the beginning of the execution. We have assumed that ${\epsilon }_1(\omega )$ is deciding, hence $P_1$ outputs some value $v_1^{\prime }$ within a finite amount of time $T_1(\omega )$ (note: without receiving any messages from $P_2$). Second, consider the canonical execution ${\epsilon }_2(\omega )$ of $A$ (again, in a synchronous network) where $P_2$ is honest and has input $v_2$. $P_1$ is corrupted and crashes at the beginning of the execution. We have assumed that ${\epsilon }_2(\omega )$ is deciding, hence $P_2$ outputs some value $v_2^{\prime }$ within a finite amount of time $T_2(\omega )$. We prove that $v_1^{\prime }=v_2^{\prime }$ by defining a third execution ${\epsilon }_{1,2}(\omega )$, but, this time, in the asynchronous model. Here, both $P_1$ and $P_2$ are honest with inputs $v_1$ and $v_2$ respectively. The scheduler delays any message between them until time $\max (T_1(\omega ),T_2(\omega ))$. This way, $P_1$ cannot distinguish execution ${\epsilon }_{1,2}(\omega )$ from execution ${\epsilon }_1(\omega )$, and therefore it outputs $v_1^{\prime }$ in ${\epsilon }_{1,2}(\omega )$ as well. Similarly, $P_2$ outputs $v_2^{\prime }$ in ${\epsilon }_{1,2}(\omega )$. Recall that $A$ achieves agreement, hence $v_1^{\prime }=v_2^{\prime }$. Note that the argument holds for arbitrary $v_1,v_2\in V_{\text{in}}$, so we get that all canonical executions where one of the parties crashes decide the same value, which we denote by $v$.

We now consider canonical executions where none of the parties crashes and show that all such executions also decide $v$. Consider any $v_1,v_2\in V_{\text{in}}$ and the canonical execution ${\epsilon }_M(\omega )$ of $A$ where both parties are honest and have inputs $v_1$ and $v_2$. We also define ${\epsilon }_{1,2}(\omega )$ as before. From the previous part, it follows that ${\epsilon }_{1,2}(\omega )$ decides $v$. We will now show that ${\epsilon }_M(\omega )$ decides $v$ as well. Based on our assumption, we already know that ${\epsilon }_M(\omega )$ decides, so it does so after a finite number of messages $\mathrm{\ell }$. For the next part of the proof, we first give an intuitive outline. Roughly, we will build a chain of $\mathrm{\ell }+1$ scenarios between execution ${\epsilon }_{1,2}(\omega )$ and execution ${\epsilon }_M(\omega )$: in each scenario , the network is asynchronous, and the scheduler ensures that the first $m$ messages are received synchronously, while all subsequent messages are delayed sufficiently long. Scenarios $0$ and $\mathrm{\ell }$ correspond to executions ${\epsilon }_{1,2}(\omega )$ and ${\epsilon }_M(\omega )$ respectively, and any two consecutive scenarios will be indistinguishable to the party that sent the last message: this will imply that ${\epsilon }_M(\omega )$ also decides $v$. In the following, we write this idea formally.

For $0\le m\le \mathrm{\ell }$, we consider an execution ${\epsilon }_{M,m}(\omega )$ of $A$ in the asynchronous model: both $P_1$ and $P_2$ are honest, and they have inputs $v_1$ and $v_2$ respectively. In execution ${\epsilon }_{M,0}(\omega )$, the scheduler uses the same strategy as that of execution ${\epsilon }_{1,2}(\omega )$: the scheduler delays any message in execution ${\epsilon }_{M,0}(\omega )$ until time $T=\max (T_1(\omega ),T_2(\omega ))$. Hence, $P_1$ and $P_2$ cannot distinguish between executions ${\epsilon }_{M,0}(\omega )$ and ${\epsilon }_{1,2}(\omega )$, implying that ${\epsilon }_{M,0}(\omega )$ decides $v$ by some time $T_0$. In execution ${\epsilon }_{M,1}(\omega )$, the scheduler allows the first message to be delivered after exactly $\mathrm{\Delta }$ time. Assume without loss of generality that this message is sent by $P_1$. All further messages are delayed until time $T_1>T_0$ (we define the exact time later): hence, $P_1$ cannot distinguish from this execution and execution ${\epsilon }_{M,0}(\omega )$, therefore it outputs $v$ by time $T_0$, as in execution ${\epsilon }_{M,0}(\omega )$. $P_2$, on the other hand, can distinguish between ${\epsilon }_1(\omega )$ and ${\epsilon }_{M,0}(\omega )$: however, it cannot distinguish between ${\epsilon }_{M,1}(\omega )$ and an execution where the network is, in fact, synchronous, and $P_1$ has crashed. If $P_1$ has crashed, $P_2$ has to output eventually, hence by time $T_1^{\prime }$. Hence, the scheduler makes sure to delay all messages until time $T_1>\max (T_0,T_1^{\prime })$. Consequently, $P_2$ has to output $v$ in ${\epsilon }_{M,1}(\omega )$ by time $T_1$. The next executions are defined similarly: in execution ${\epsilon }_{M,m}(\omega )$ with $m>0$, the scheduler allows the first $m$ messages to be delivered after exactly $\mathrm{\Delta }$ units of time. The remaining messages are delivered sufficiently late to ensure that the last message’s sender is unable to distinguish between ${\epsilon }_{M,m}(\omega )$ and execution ${\epsilon }_{M,m-1}(\omega )$. Thus, the last message’s sender outputs $v$ in execution ${\epsilon }_{M,m}(\omega )$, which forces the other honest party to also output $v$.

We remark that executions ${\epsilon }_{M,\mathrm{\ell }}(\omega )$ and ${\epsilon }_M(\omega )$ are indistinguishable, so ${\epsilon }_M(\omega )$ will decide $v$. Since this holds for arbitrary values $v_1,v_2$, we have obtained that all canonical executions where no party crashes also output $v$, hence completing the proof. ∎

Consider a (possibly randomized) $(t_s,0)$-secure BA protocol $\mathrm{\Pi }$ that solves val when $n=2\cdot t_s$. Let $I_1$ and $I_2$ be two arbitrary maximal input configurations. We show that the canonical executions of $I_1$ and $I_2$ almost surely decide on the same output when run using the same randomness. Then, Lemma 5 ensures that val is trivial.

We use $\mathrm{\Pi }$ to build a $2$-party protocol $A$ that matches the setting described in Lemma 6. For protocol $A$, we consider the input set $\{0,1\}$ and output set $V_{\text{out}}$, and we denote the two parties running $A$ by $P_1$ and $P_2$. Since $n=2\cdot t_s$, we may partition the set of $n$ parties $𝒫$ into two sets ${𝒫}_L$ and ${𝒫}_R$ of $t_s$ parties each.

Then, as shown in Figure 2, $P_1$ will simulate the parties in ${𝒫}_L$, while $P_2$ will simulate the parties in ${𝒫}_R$. Concretely, in protocol $A$, $P_1$ proceeds as follows:

• $\mathrm{■}$

  $P_1$ simulates all $t_s$ parties of ${𝒫}_L$ running $\mathrm{\Pi }$.

• $\mathrm{■}$

  If $P_1$ has input $0$, then the simulated parties in ${𝒫}_L$ use their inputs from $I_1$. Otherwise, they use their inputs from $I_2$.

• $\mathrm{■}$

  Messages between the simulated parties in ${𝒫}_L$ are received after exactly $\mathrm{\Delta }$ units of time, and $P_1$ forwards to $P_2$ every message sent by a simulated party in ${𝒫}_L$ to a party in ${𝒫}_R$. Once $P_2$ receives this message, it immediately forwards it to the simulated receiver in ${𝒫}_R$.

• $\mathrm{■}$

  As soon as a party in ${𝒫}_L$ decides a value, $P_1$ decides this value. $P_1$ continues forwarding messages as described above.

$P_2$ proceeds identically to $P_1$, switching ${𝒫}_L$ and ${𝒫}_R$.

Note that running $A$ in an asynchronous network where both $P_1$ and $P_2$ are honest corresponds to running $\mathrm{\Pi }$ in an asynchronous network where all $n$ parties are honest. In addition, running $A$ in a synchronous network where at most one party may crash corresponds to running $\mathrm{\Pi }$ in a synchronous network where at most $t_s$ parties may crash. Then, since $\mathrm{\Pi }$ is a $(t_s,0)$-secure BA protocol, $A$ achieves probabilistic termination and agreement in the setting described in Lemma 6. Then, applying Lemma 6, we obtain that: almost surely, there is a value $v$ such that all canonical executions of $A$ decide on the same value $v$. Moreover, the canonical execution of $A$ with input values $(0,0)$ matches the canonical execution of $I_1$ for $\mathrm{\Pi }$. Similarly, the canonical execution of $A$ with input $(1,1)$ matches the canonical execution of $I_2$. As a consequence, canonical executions of $I_1$ and $I_2$ decide the same value almost surely. Using Lemma 5, we can therefore conclude that val is trivial. $◀$

Assume $n=2\cdot t_s+t_a$ and that there is a $(t_s,t_a)$-secure BA protocol $\mathrm{\Pi }$ solving val. We consider two input configurations $I_1$ and $I_2$ such that $\text{parties}(I_1)=\text{parties}(I_2)=𝒫$ (i.e., all parties are honest). We show that, almost surely, the canonical executions of $I_1$ and $I_2$ decide on the same output. Then, Lemma 5 ensures that val is trivial. Similarly to the proof of Theorem 7, we use $\mathrm{\Pi }$ to build a two-party protocol $A$ that matches the setting of Lemma 6. For $A$, we consider the input space $\{0,1\}$ and the output space $V_{\text{out}}$.

This time, we partition $𝒫$ into three sets ${𝒫}_L$, ${𝒫}_M$ and ${𝒫}_R$ such that $|{𝒫}_L|=|{𝒫}_R|=t_s$ and $|{𝒫}_M|=t_a$. A crucial difference from the proof of Theorem 7 is that, as shown in Figure 3, each party in $𝒫$ simulates its own copy of the parties in ${𝒫}_M$. Our construction will ensure that, when $A$ runs in the synchronous setting, the two simulated copies of each party in ${𝒫}_M$ will be in the exact same state at any point, maintaining the guarantees of $\mathrm{\Pi }$ when at most $t_s$ of the parties are corrupted. Meanwhile, in the asynchronous setting, the copies of the $t_a$ parties in ${𝒫}_M$ may be in different states, but $\mathrm{\Pi }$ is able to tolerate $t_a$ byzantine parties in this case. Concretely, in protocol $A$, party $P_1$ proceeds as follows:

• $\mathrm{■}$

  $P_1$ simulates all $t_s+t_a$ parties of ${𝒫}_L\cup {𝒫}_M$ running $\mathrm{\Pi }$.

• $\mathrm{■}$

  If $P_1$ has input $0$, then parties in ${𝒫}_L\cup {𝒫}_M$ take their input from $I_1$. Otherwise, they take their input from $I_2$.

• $\mathrm{■}$

  As depicted in Figure 4, the messages sent between the parties simulated by $P_1$ are exchanged as if all $t_s+t_a$ parties are running independently: each such message is delivered after exactly $\mathrm{\Delta }$ units of time. Additionally, once a simulated party in ${𝒫}_L$ sends a message to a simulated party in ${𝒫}_M$, $P_1$ immediately forwards this message to $P_2$ as well. Once $P_2$ receives this message, it immediately forwards it to its own simulated receiver in ${𝒫}_M$. The message delay here depends on the type of network that $A$ is running in.

• $\mathrm{■}$

  Messages from a party in ${𝒫}_L$ to ${𝒫}_R$ are sent from $P_1$ to $P_2$. $P_2$ then forwards each such message to its simulated receiver in ${𝒫}_R$.

• $\mathrm{■}$

  $P_1$ discards any messages sent by the simulated parties in ${𝒫}_M$ to parties in ${𝒫}_R$.

• $\mathrm{■}$

  As soon as a party in ${𝒫}_L$ (but not ${𝒫}_M$) decides a value, $P_1$ decides this value. $P_1$ continues forwarding messages as described above until all its simulated parties terminate.

The behavior of $P_2$ is the same as the behavior of $P_1$, switching ${𝒫}_L$ and ${𝒫}_R$.

We now need to analyze $A$ in the setting described by Lemma 6. Running $A$ in an asynchronous network where both parties are honest corresponds to running $\mathrm{\Pi }$ in a network where the communication between parties in ${𝒫}_L$ and ${𝒫}_R$ is asynchronous. While the simulated copies in ${𝒫}_M$ are not necessarily consistent, $\mathrm{\Pi }$ is resilient against $t_a=\left|{𝒫}_M\right|$ byzantine corruptions, and therefore maintains its guarantees. Hence, $A$ achieves agreement and probabilistic termination in this setting. It remains to show that $A$ also achieves these guarantees in a synchronous network where one of the two parties may crash. Settings where both $P_1$ and $P_2$ are honest correspond to running $\mathrm{\Pi }$ in a synchronous network where all $n$ parties are honest. We note that, in this case, for each party in ${𝒫}_M$, the copy simulated by $P_1$ and the copy simulated by $P_2$ maintain the same state at all times. Settings where at most one of $P_1$ and $P_2$ may crash correspond to running $\mathrm{\Pi }$ in a synchronous setting where the $t_s$ parties meant to be simulated only by the party crashing in $A$ are corrupted. As $\mathrm{\Pi }$ tolerates $t_s$ corruptions, it maintains its guarantees. Hence, $A$ achieves agreement and probabilistic termination in this setting as well.

We conclude the proof in an identical manner to the proof of Theorem 7. Applying Lemma 6, we obtain that, almost surely, all canonical executions of $A$ decide on the same value. Moreover, the canonical execution of $A$ with input values $(0,0)$ matches the canonical execution of $I_1$ for $\mathrm{\Pi }$. Similarly, the canonical execution of $A$ with input $(1,1)$ matches the canonical execution of $I_2$. As a consequence, canonical executions of $I_1$ and $I_2$ decide the same value almost surely. Using Lemma 5, we can therefore conclude that val is trivial. $◀$