Weaker Assumptions for Asymmetric Trust

Asymmetric trust models, such as those proposed by Damgård et al. [13], Alpos et al. [2], and Losa et al. [22] 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. [20], they are not enough to solve fundamental problems like reliable broadcast and consensus. Therefore, the models introduce additional assumptions on the quorums. The protocols for reliable broadcast and consensus of Alpos et al. [2] require the existence of a guild, a set of processes that contains a quorum for each of its members. Li et al. [20] and Losa et al. [22] 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 start by showing that current assumptions 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 derive an equivalent symmetric trust assumption such that no process will be worse off by adopting it. This result is surprising, considering that Damgård et al. [13] 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 approach to characterize asymmetric problems based on it. We use this concept to provide more general definitions of unauthenticated, asymmetric, asynchronous, Byzantine reliable broadcast and binary consensus. We also propose new algorithms for these problems that forego the guild requirement in favor of weaker assumptions on depth.

The remainder of this document is organized as follows. Section 2 discusses related work in the asymmetric trust setting. Section 3 introduces the model and reviews key concepts that serve as the foundation for our work. We show in Section 4 that the current assumptions are so strong that they invalidate the benefits of asymmetric trust. Section 5 introduces the concept of depth. Sections 6 and 7 present algorithms for reliable broadcast and consensus that forego the guild assumption in favor of weaker depth assumptions. The proofs of all results are deferred to the full version of this article [3].

Threshold and symmetric quorum systems are fundamental tools in distributed computing, commonly used to establish the safety and liveness guarantees of various protocols [25, 23, 6, 11]. They constitute a crucial component of many systems in cloud computing [19, 17] and cryptocurrencies [15, 9, 10]. One drawback is that all participants must use the same quorum system, which restricts their freedom to choose who to trust. The asymmetric model, introduced by Damgård et al. [13] and further developed by Alpos et al. [2], represents a novel approach that generalizes the symmetric paradigm. It allows participants to make trust choices of their own, reflecting social connections or other information available to them outside the protocol. Each participant can specify its own quorum system, giving it the freedom to have its own trust assumptions. Amores-Sesar et al. [5] show that algorithms relying on symmetric quorums cannot be applied directly to the asymmetric model, as certain properties do not hold if the underlying quorums are asymmetric. This drives the need to adapt existing symmetric protocols and redefine protocol properties to fit the new model.

Existing work [2] introduces asymmetric versions of relevant primitives like reliable broadcast, binary consensus, and common coin. Amores-Sesar et al. [5] extend this work by developing a DAG-based consensus protocol that relies on such primitives. Losa et al. [22] present another approach to model asymmetric trust. They forego the notion of fail-prone sets and strengthen the definition of quorums, by requiring each quorum to contain a quorum for each member. Li et al. [20] expand on this model and address the topic of which quorum properties are necessary or sufficient to solve core asymmetric problems such as consensus. Sheff et al. [28] propose a variant of the Paxos protocol that incorporates heterogeneous trust assumptions.

Senn and Cachin [27] explore asymmetric trust in the crash-fault scenario and show that, in this setting, asymmetric trust reduces to symmetric trust.

Asymmetric trust introduces novel challenges to the design of distributed protocols. One significant hurdle is that of processes that have wrong friends, that is, the existence of processes that are correct and behave according to the underlying algorithm, but whose trust assumptions do not capture the actual faulty processes. Damgård et al. [13] and Alpos et al. [2] use the term naive to refer to such participants and point out that their presence can lead to safety and liveness issues in asymmetric protocols. To address this, they introduce the concept of a guild, a set of processes that contains a quorum for each member, and provide algorithms for reliable broadcast and consensus that work correctly only in executions that have this structure. They point out that having a quorum system that only satisfies the consistency and availability properties can lead to liveness issues for some processes. In a slightly different model, Li et al. [20] prove that the traditional properties of quorum consistency and availability are not sufficient to solve reliable broadcast and consensus. They introduce a new property, called strong availability, very similar to the notion of a guild, and prove that this property is sufficient to solve the aforementioned problems. They do not comment on the necessity of such a property.

Asymmetric consensus protocols have also transcended into the blockchain space with XRP Ledger [12] (https://xrpl.org) and Stellar [24, 21] (https://stellar.org) as main representatives. In the XRP Ledger, each participant declares its own assumptions by listing other participating nodes from which it considers votes [12, 4]. Stellar uses a similar approach, in which each participant keeps a list of participants it considers important and waits for a suitable majority of them to agree on a transaction before considering it settled [24, 22, 21].

In the asymmetric trust setting, Li et al. [20] show that a quorum system satisfying the classical properties of consistency and availability alone does not suffice to solve fundamental problems such as reliable broadcast or consensus. The heterogeneous views of the system make it necessary to assume more structure. Different approaches have reached similar conclusions about the assumptions needed to address these problems under asymmetric trust. Alpos et al. [2] require the existence of a guild, while Li et al. [20] propose that the system must satisfy the strong availability property. This is closely related to the idea of a guild, as it also requires the existence of a well-behaved group of processes that includes a quorum for every participant. In this section, we examine the implications of these assumptions, focusing on the model proposed by Alpos et al. [2].

Guilds are a strong assumption, essentially requiring all members to have common beliefs, which goes against the idea of asymmetric trust. We show that for any asymmetric Byzantine fail-prone system $𝔽$, if a guild exists in an execution, then we can build an equally valid symmetric trust assumption $ℱ$ from $𝔽$. This means that, in such cases, asymmetric trust reduces to symmetric trust.

In the crash-fault model, Senn and Cachin [27] already show that given an asymmetric fail-prone system $𝔽$, it is possible to construct a symmetric fail-prone system $ℱ$ from $𝔽$ such that if all processes adopt $ℱ$ 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 fault model for all executions with a guild. This effectively invalidates the advantages of asymmetric trust for the algorithms proposed by Alpos et al. [2] which rely on the existence of a guild.

We now show how to construct a symmetric fail-prone system $ℱ$ from an asymmetric fail-prone system $𝔽$, such that in all executions with a guild, $ℱ$ is as expressive as $𝔽$. We will build it based on the notion of the tolerated system, presented in Section 2 and used by Alpos et al. [2] and Zanolini [29] in their consensus protocols.

From Lemma 5 we know that the tolerated symmetric fail-prone system satisfies the $Q^3$ property and therefore there will be at least one valid symmetric Byzantine quorum system associated to it.

In the symmetric world, processes are classified as correct or faulty. This suffices to express the properties of algorithms and capture all potential states of a process. In the asymmetric world this is not enough, a process might be correct but have incorrect trust assumptions. Damgård et al. [13] and Alpos et al. [2] address this problem by introducing the notions of naive, wise, and guilds.

Existing protocols for reliable broadcast and consensus in the Alpos et al. [2] model require a guild to ensure safety and liveness. The results of Section 4, coupled with the inherent rigidity of having this kind of assumptions, motivate the search for new asymmetric algorithms that forego such assumptions. In order to do this, we introduce a new way to describe the quality of processes, based on how much they can rely on other processes during an execution. We denote this concept as the depth of a process. We then show how it can be used to characterize asymmetric problems in a more fine-grained manner. Definition 10 introduces this notion. This approach allows to generalize the concept of wise process or guild member and introduces more expressivity to the system.

Note that a process with maximal depth $d$ also has depth $d^{\prime }$ for all $0\le d^{\prime }\le d$. We will focus on the maximal depth of a process. In the following sections, any reference to the depth of a process should be understood as its maximal depth. Following the terminology of Damgård et al. [13], naive processes have depth 0, wise processes have depth at least 1, and processes in a guild have infinite depth.

In Sections 6 and 7 we show how the properties of protocols can be adapted to take into account the depth of processes. We modify them to show that some property must hold for all processes with depth at least $d$. For example, the totality property of reliable broadcast is updated to state that all processes with depth $d$ eventually deliver a message.

Section 4 shows that if an execution includes a guild, we can convert asymmetric trust assumptions into symmetric ones. This means that if a problem can only be solved in executions with a guild, the interest in using asymmetric trust to solve it decreases. So far, the only known protocols for reliable broadcast and consensus in the Alpos et al. [2] model require the existence of a guild. This motivates the search for new algorithms that work without relying on guild assumptions for these problems. We start this search with the Byzantine reliable broadcast problem. Our approach weakens the trust assumptions needed and eliminates the need for a guild. Definition 11 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.

The reliable broadcast proposed by Alpos et al. [2] is closely related to RB[$\mathrm{\infty }$], although not as general. RB[$\mathrm{\infty }$] guarantees a solution for all processes with depth $\mathrm{\infty }$, whereas the protocol by Alpos et al. [2] only guarantees a solution for those processes with depth $\mathrm{\infty }$ that also belong to the maximal guild. That is, processes with depth $\mathrm{\infty }$ that are members of a guild, but not of the maximal guild, are not guaranteed to receive a solution.

A natural question arises, which is the minimum depth needed to implement the different primitives. A low depth not only corresponds to weaker asymmetric assumptions, but also reflects, to a certain level, the communication complexity of an algorithm. Lemma 12 shows that it is not possible to solve reliable broadcast for depths 0 or 1.

We adapt the consensus problem to the depth paradigm and propose an algorithm that solves it for all processes with a minimum depth of at least 10. We follow an approach similar to the one proposed by Abraham et al. [1], who use a round-based algorithm composed of a binding crusader agreement and a common coin. However, for reasons that will be discussed in Section 7.3, we replace binding crusader agreement with a binding graded agreement protocol which allows parties to provide multiple input. For this purpose, we introduce depth-characterized versions of these primitives in Sections 7.1 and 7.2, which we use as subprotocols inside the main consensus algorithm.

It is at this point that the need to characterize the depth of starting and finishing processes arises. The consensus protocol first calls the binding graded agreement, and then the common coin. Only processes that finish the former will be able to make the call to the latter. Because of this, we need to take into account that not all correct processes can start executing a protocol. We introduce two parameters to characterize the depth of protocols: $d^{\prime }$ to refer to the depth of processes that start the execution, and $d$ to refer to the depth of processes that finish the execution. We will say that an algorithm works if, in case all processes with depth $d^{\prime }$ start the execution, all processes with depth $d$ satisfy the required properties. In case we assume that all correct processes start (i.e., $d^{\prime }=0$), as is the case for standalone protocols (like consensus and reliable broadcast), we will ignore the $d^{\prime }$ parameter.

Prior to this work, solutions to problems such as reliable broadcast and consensus relied on guild assumptions. Theorem 9 shows that this assumption effectively reduces to the existence of a symmetric system, constructed from the original assumptions, that provides equivalent or stronger guarantees. In other words, existing solutions are not well-suited for genuinely asymmetric settings.

To overcome this limitation, we introduced a more fine-grained way to characterize asymmetry through the notion of depth. We proved that reliable broadcast can be solved for all processes with depth at least 3, and consensus for processes with depth at least 9. This significantly relaxes the requirements compared to prior work by Alpos et al. [2], which established feasibility only for processes with infinite depth (i.e., guild members).

The exact minimum depth required for solving asymmetric reliable broadcast and consensus remains an open problem. For reliable broadcast, the lower bound is either 2 or 3; for consensus, it lies between 1 and 10. Determining these thresholds is crucial, as a lower depth implies less reliance on other processes and more flexible systems.

Finally, an important direction for future research is to explore whether the concepts and techniques introduced here extend to other asymmetric trust models [20, 22].