Brief Announcement: Weaker Assumptions for Asymmetric Trust

Asymmetric trust models, such as those proposed by Damgård et al. [3], Alpos et al. [1], and Li, Chan, and Lesani [4] allow the development of distributed protocols in which each participant can operate under its own trust settings. These algorithms are built on top of asymmetric quorum systems, where each process independently defines its own quorums. The traditional consistency and availability properties must be satisfied by these systems, but as was shown by Li et al. [4], these are not enough to solve fundamental problems like reliable broadcast and consensus. Therefore, the models introduce additional assumptions. The protocols for reliable broadcast and consensus of Alpos et al. [1] require the existence of a guild, a set of processes that contains a quorum for each of its members. Li et al. [4] and Losa, Gafni, and Mazieres [5] identify similar conditions. These assumptions can be very strong and restrictive, and while they are sufficient to provide solutions to the aforementioned problems, we will show that they are not necessary. This leads to asymmetric algorithms that work under weaker assumptions, making such systems more flexible and usable.

We show that assumptions currently identified for algorithms such as reliable broadcast or consensus are so restrictive that it becomes unnecessary to use asymmetric trust models altogether. That is, given an asymmetric trust assumption that satisfies such requirements, we can build an equivalent symmetric trust assumption such that no process will be worse off by adopting it. This result is surprising, considering that Alpos et al. [1] show that asymmetric trust is more expressive than symmetric trust.

To solve this, we introduce the notion of depth of a process and propose a new way to characterize asymmetric problems based on it. We use this concept to provide a more general definition of asymmetric asynchronous reliable broadcast and to propose a new algorithm for this problem that foregoes the guild requirement in favor of a weaker assumption on depth .

For a complete presentation of the asymmetric trust model, we refer the reader to the work of Alpos et al. [1]. In protocols with asymmetric trust, each participant is free to make its own individual trust assumptions about others, captured by an asymmetric quorum system. This contrasts with ordinary, symmetric and threshold quorum systems, where all participants share the same trust assumptions. Given a set of processes $𝒫$, an asymmetric fail-prone system $𝔽=[{ℱ}_1,\mathrm{\dots },{ℱ}_n]$, where ${ℱ}_i$ represents the trust assumptions of process $p_i$, captures the heterogeneous model. Each ${ℱ}_i$ is a collection of subsets of $𝒫$ (the set of processes) such that some $F\in {ℱ}_i$ with $F\subseteq 𝒫$ is called a fail-prone set for $p_i$ and contains all processes that, according to $p_i$, may at most fail together in some execution [3]. We can in turn proceed to define the asymmetric Byzantine quorum systems. Here and from now on, the notation ${𝒜}^{\ast }$ for a system $𝒜\subseteq 2^{𝒫}$ , denotes the collection of all subsets of the sets in $𝒜$, that is, ${𝒜}^{\ast }=\{A^{\prime }|A^{\prime }\subseteq A,A\in 𝒜\}$.

Given an asymmetric quorum system $\mathbb{Q}$ for $𝔽$, an asymmetric kernel system for $\mathbb{Q}$ is defined analogously as the array $𝕂=[{𝒦}_1,\mathrm{\dots },{𝒦}_n]$ that consists of the kernel systems for all processes in $𝒫$. A set $K_i\in {𝒦}_i$ is called a kernel for $p_i$ and for each $K_i$ it holds that $\forall Q_i\in {𝒬}_i,K_i\cap Q_i\ne \mathrm{\varnothing }$, that is, a kernel intersects all quorums of a process.

The existence of a valid $\mathbb{Q}$ is conditioned on $𝔽$ satisfying the $B^3$ condition.

Existing work shows that an asymmetric fail-prone system $𝔽$ satisfies $B^3(𝔽)$ if and only if there exists an asymmetric quorum system for $𝔽$. If $B^3(𝔽)$ holds, then the canonical quorum system, defined as the complement of the asymmetric fail-prone system, is a valid asymmetric quorum system.

During an execution the set of processes that fail is denoted by $F$. The members of $F$ are unknown to the processes and can only be identified by an outside observer and the adversary. A process $p_i$ correctly foresees $F$ if $F\in {ℱ}_i^{\ast }$, that is, $F$ is contained in one of its fail-prone sets. Based on this information, it is possible to classify processes in three categories.

Faulty:

a faulty process, i.e., $p_i\in F$;

Naive:

a correct process $p_i$, i.e. $p_i\notin F$, where $F\notin {ℱ}_i^{\ast }$; or

Wise:

a correct process $p_i$, i.e. $p_i\notin F$, where $F\in {ℱ}_i^{\ast }$

Alpos et al. [1] show that naive processes might affect the safety and liveness guarantees of some protocols. In order to formalize this notion, they introduced the concept of a guild. This concept is central for many of the algorithms they propose (e.g., reliable broadcast, binary consensus), as properties can only be ensured for executions where a guild exists.

Li et al. [4] show that given a Byzantine asymmetric quorum system, the classical properties of consistency and availability alone do not suffice to solve fundamental problems such as reliable broadcast or consensus. The heterogeneous views of the system make it necessary assume more structure. The corresponding algorithms of Alpos et al. [1] require the existence of a guild. In a similar manner, Li et al. [4] propose that the strong availability property should be satisfied to be able to solve such problems. This requirement closely resembles the notion of a guild; in fact, any execution that satisfies the strong availability property is guaranteed to contain at least one guild. We explore here the implications of requiring this kind of assumptions, focusing our attention on the model of Alpos et al. [1].

Guilds are a very strong assumption, essentially requiring all members to have common beliefs, which goes against the spirit of asymmetry. We show that given an asymmetric fail-prone system $𝔽$, in all executions where there is a guild, it is possible to construct an equally valid symmetric trust assumption $ℱ$ from $𝔽$. As a result, asymmetric trust reduces to symmetric trust.

In the crash-fault model, Senn and Cachin [6] already show that given an asymmetric fail-prone system ${𝔽}^{\prime }$, it is possible to construct a symmetric fail-prone system ${ℱ}^{\prime }$ from ${𝔽}^{\prime }$ such that if all processes adopt ${ℱ}^{\prime }$ as their trust assumption, no process will be worse off. This result implies that there is no need for asymmetric trust in that setting. We extend this by showing that a similar scenario occurs in the Byzantine model for all executions with a guild. This effectively invalidates the advantages of asymmetric trust for the algorithms proposed by Alpos et al. [1], which rely on the existence of a guild.

Theorem 4 shows that for executions with a guild, every process is at least as well off using the symmetric quorum system $ℱ$ instead of $𝔽$. For a wise process $p_i$ the situation will remain the same regardless of the quorum system chosen. With the asymmetric system $F\in {ℱ}_i^{\ast }$ will hold, while the symmetric alternative satisfies $F\in {ℱ}^{\ast }$. For naive processes the situation improves, as now the faulty processes will be considered in their trust assumption. Thus, there is no reason for a process not to adopt the derived symmetric fail-prone system $ℱ$. One limitation of this result is that it assumes knowledge of $𝔽$, the trust assumptions for all processes. Although Alpos et al. [1] also make this assumption, it is not required in other asymmetric trust models [5]. We also note that knowing the faulty processes $F$ is not required to derive the symmetric fail-prone system presented in Theorem 4.

If a guild is needed to solve a problem in the asymmetric setting, there exists a way to use existing algorithms in the symmetric model and obtain the same guarantees that an asymmetric algorithm would provide. Therefore, if a problem can only be solved with a guild, the interest in using asymmetric algorithms decreases. This motivates to look for other models and algorithms to implement reliable broadcast, consensus, and other problems, where the asymmetric algorithms known so far require a guild.

The result of Section 3 motivates the search for new guildless algorithms for problems where the only known protocols require a guild. We explore this within the context of the Byzantine reliable broadcast problem. We present a new approach that significantly weakens the assumptions needed to implement the problem and removes the reliance on guilds.

In order to do this, we introduce the notion of the depth of a process. Intuitively, this captures the extent to which a process can depend on others during a multi-round protocol execution. We then show how it can be used to characterize asymmetric problems in a more fine-grained approach.

We will center our attention on the maximal depth of a process. Note that a process with maximal depth $d$ also has depth $d^{\prime }$ for all $0\le d^{\prime }\le d$. Following the terminology of Alpos et al. [1], naive processes have maximal depth 0, wise processes have maximal depth at least 1, and processes in a guild have maximal depth $\mathrm{\infty }$.

Definition 6 presents a way to characterize reliable broadcast based on the depth of processes. Its properties are specific to processes that have at least a certain maximal depth.

RB[$\mathrm{\infty }$] gives a solution for all processes with depth $\mathrm{\infty }$, while the protocol by Alpos et al. only guarantees a solution for processes with depth $\mathrm{\infty }$ that also belong to the maximal guild. Lemma 7 shows that if an algorithm solves RB[$s$] then it also solves RB[$s^{\prime }$] for all $s^{\prime }\ge s$. This simplifies the search for a solution by reducing it to finding an algorithm that works for the minimal value of $s$. Lemma 8 shows that there are no algorithms that can solve RB[1], therefore we must search for a protocol that solves the problem for processes with depth $\ge 2$.

Algorithm 1 presents a solution for RB[3]. Every process in the algorithm waits to receive a quorum of Readyafterecho messages associated to the same message $m$ and round $r$ before delivering $m$. A process with depth 3 will only receive such a quorum if there exists a set of processes $Q$ (which form a quorum for a wise process) that can attest that the sender indeed sent the value $m$. Since there will be an attesting quorum for every process that delivers, and since quorums for wise processes intersect in at least one correct process, we can deduce that all processes with depth 3 that deliver a value $m$ will deliver the same value. In addition, we use a technique similar to Bracha’s kernel amplification [2] to ensure that if a valid process delivers then all valid processes will deliver. The arrays in lines 4, 5, 6, and 7 are hashmaps, so even though they are depicted as having infinite size they are actually sparsely populated. The algorithm has a latency of 3 asynchronous rounds in the best case and 5 in the worst case scenario.

We have shown that if a problem requires a guild assumption to be solved it is of less interest to use asymmetric trust to solve it. This arises from Theorem 4, which shows that for these cases, asymmetric trust reduces to symmetric trust.

To address this we presented a more fine-grained approach to characterize asymmetric problems, using the concept of depth, and showed that reliable broadcast can be solved for all processes with depth at least 3. This weakens the requirements needed to solve the problem in an asymmetric setting compared to the solution proposed by Alpos et al. [1], which only solves reliable broadcast for a fraction of processes with depth $\mathrm{\infty }$. It is an open question if there exists an algorithm that solves RB[2]. These techniques can also be applied to other problems, such as binary consensus and common coin, whose existing solutions in the asymmetric trust setting rely on guilds. This approach could enable the development of new algorithms that operate under significantly weaker assumptions.