University of California, Riverside, USA [email protected]://orcid.org/0000-0002-1825-0097 University of California, Riverside, [email protected][orcid] University of California, Riverside, [email protected][orcid] \CopyrightXiao Li, Eric Chan, Mohsen Lesani {CCSXML} <ccs2012> <concept> <concept_id>10010147.10010919.10010172</concept_id> <concept_desc>Computing methodologies Distributed algorithms</concept_desc> <concept_significance>500</concept_significance> </concept> <concept> <concept_id>10010520.10010575.10010578</concept_id> <concept_desc>Computer systems organization Availability</concept_desc> <concept_significance>300</concept_significance> </concept> <concept> <concept_id>10010520.10010575.10010577</concept_id> <concept_desc>Computer systems organization Reliability</concept_desc> <concept_significance>100</concept_significance> </concept> </ccs2012> \ccsdesc[500]Computing methodologies Distributed algorithms \ccsdesc[300]Computer systems organization Availability \ccsdesc[100]Computer systems organization Reliability \EventEditorsRotem Oshman \EventNoEds1 \EventLongTitle37th International Symposium on Distributed Computing (DISC 2023) \EventShortTitleDISC 2023 \EventAcronymDISC \EventYear2023 \EventDateOctober 10-12, 2023 \EventLocationL’Aquila, Italy \EventLogo \SeriesVolume281 \ArticleNo16

Quorum Subsumption for Heterogeneous Quorum Systems

Xiao Li Eric Chan Mohsen Lesani

Abstract

Byzantine quorum systems provide higher throughput than proof-of-work and incur modest energy consumption. Further, their modern incarnations incorporate personalized and heterogeneous trust. Thus, they are emerging as an appealing candidate for global financial infrastructure. However, since their quorums are not uniform across processes anymore, the properties that they should maintain to support abstractions such as reliable broadcast and consensus are not well-understood. It has been shown that the two properties quorum intersection and availability are necessary. In this paper, we prove that they are not sufficient. We then define the notion of quorum subsumption, and show that the three conditions together are sufficient: we present reliable broadcast and consensus protocols, and prove their correctness for quorum systems that provide the three properties.

keywords:

Distributed Systems, Impossibility Results, Byzantine fault tolerance

1 Introduction

Bitcoin [42] had the promise to democratize the global finance. Globally scattered servers validate and process transactions, and maintain a consistent replication of a ledger. However, the nature of the proof-of-work consensus exhibited disadvantages such as high energy consumption, and low throughput. In contrast, Byzantine replication have always had modest energy consumption. Further, since its advent as PBFT [18], many recent extensions [47, 39, 48, 17, 6, 12, 13] have improved its throughput. However, its basic model of quorums is closed and homogeneous: the set of processes are fixed, and the quorums are assumed to be uniform across processes. Thus, projects such as Ripple [44] and Stellar [38, 33] emerged to bring heterogeneity and openness to Byzantine quorum systems. They let every process declare its own set of quorums, or the processes it trusts called slices, from which quorums are calculated.

In this paper, we first consider a basic model of heterogeneous quorum systems where each process has an individual set of quorums. Then, we consider fundamental questions about their properties. Quorum systems are the foundation of common distributed computing abstractions such as reliable broadcast and consensus. We specify the expected safety and liveness properties for these abstractions. What are the necessary and sufficient properties of heterogeneous quorum systems to support these abstractions? Previous work [34] noted that quorum intersection and weak availability properties are necessary for the quorum system to implement the consensus abstraction. Quorum intersection requires that every pair of quorums overlap at a well-behaved process. The safety of consensus relies on the quorum intersection property of the underlying quorum system: intuitively, if an operation communicates with a quorum, and a later operation communicates with another quorum, a single well-behaved process in their intersection can make the second quorum aware of the first. A quorum system is weakly available for a process if it has a quorum for that process whose members are all well-behaved. Intuitively, the quorum system is available to that process through that quorum. Since a process needs to communicate with at least one quorum to terminate, the liveness properties are dependent on the availability of the quorum system.

The quorum intersection and availability properties are necessary. Are they sufficient as well? In this paper, we prove that they are not sufficient conditions to implement reliable broadcast and consensus. For each abstraction, we present execution scenarios, and apply indistinguishability arguments to show that any protocol violates at least one of the safety or liveness properties. What property should be added to make the properties sufficient? A less known property is quorum sharing [34]. Roughly speaking, every quorum should include a quorum for all its members. This is a property that trivially holds for homogeneous quorum systems where every quorum is uniformly a quorum of all its members. However, in general, it does not hold for heterogeneous quorum systems. Previous work showed that it also holds for Stellar quorums if Byzantine processes do not lie about their slices.

Since Byzantine processes’ quorums is arbitrary, in practice, quorum sharing is too strong. In order to require inclusion only for the quorums of a well-behaved subset of processes, we consider a weaker notion, called quorum subsumption. As we will see, this property lets processes in the included quorum make local decisions while preserving the properties of the including quorum. We precisely capture this property, and show that together with the other two properties, it is sufficient to implement reliable broadcast and consensus abstractions. We present protocols for both reliable broadcast and consensus, and prove that if the underlying quorum system has quorum intersection, availability, and subsumption for certain quorums, then the protocols satisfy the required safety and liveness properties.

In summary, this paper makes the following contributions.

•

Properties of quorum-based protocols (§ 3) and specifications of reliable broadcast and consensus on heterogeneous quorum systems (§ 4).
•

Proof of insufficiency of quorum intersection and availability to solve consensus (§ 5.1) and reliable broadcast (§ 5.2).
•

Sufficiency of quorum intersection, quorum availability and quorum subsumption to solve consensus and reliable broadcast. We present protocols for reliable broadcast (§ 6.1) and consensus (§ 6.2), and their proofs of correctness.

2 Heterogeneous Quorum Systems

A quorum is a subset of processes that are collectively trusted to perform an operation. However, this trust may not be uniform: while a process may trust a part of a system, another process may not trust that same part. In this section, we adopt a general model of quorum systems [32, 34] and its properties. These basic definitions adapt common properties of quorum systems to the heterogeneous setting, and serve as the foundation for theorems and protocols in the later sections. Since we want the theorems to be as strong as possible, we introduce the weak notion of quorum subsumption in this paper.

2.1 Processes and Quorums

Processes and Failures. A quorum system is hosted on a set of processes $\mathcal{P}$ . For every execution, we can partition the set $\mathcal{P}$ into Byzantine $\mathcal{B}$ and well-behaved $\mathcal{W}=\mathcal{P}\setminus\mathcal{B}$ processes. Well-behaved processes follow the given protocol, while Byzantine processes can deviate from the protocol arbitrarily.

We assume that the network is partially synchronized, i.e., after an unknown global stabilization time (GST), if both the sender and receiver are well-behaved, the message will eventually be delivered with a known bounded delay [20].

Heterogeneous Quorum Systems (HQS). To represent subjective trust, we let each process specify its own quorums. A quorum $q$ of process $p$ is a non-empty subset $P$ of $\mathcal{P}$ that $p$ trusts to get information from if it obtains the same information from each member of $P$ . (In practice, a quorum of $p$ can contain $p$ itself, although the model does not require it.) Each process $p$ stores its own set of quorums that we call individual quorums of $p$ . Any superset of a quorum of $p$ is also a quorum of $p$ ; thus, there are minimal quorums: a quorum of $p$ is a minimal quorum of $p$ if none of its strict subsets is a quorum of $p$ . Thus, to avoid redundancy, $p$ can ignore its quorums that are proper supersets of its minimal quorums. Thus, each process stores only its individual minimal quorums.

Definition 2.1 (Quorum System).

A heterogeneous quorum system $\mathcal{Q}$ is a mapping from processes to their non-empty set of individual minimal quorums.

Since the trust assumptions of Byzantine processes can be arbitrary, their quorums can be left unspecified. Fig. 1 presents an example quorum system. When obvious from the context, we say quorums of $p$ to refer to the individual minimal quorums of $p$ , and use $\mathcal{Q}$ to refer to the set of all individual minimal quorums of the system, i.e. the co-domain of $\mathcal{Q}$ . Additionally, we say quorum systems to refer to heterogeneous quorum systems. A process $p$ is a follower of a process $p^{\prime}$ iff there is a quorum $q\in\mathcal{Q}(p)$ that includes $p^{\prime}$ .

In dissemination quorum system (DQS) [37] (and the cardinality-based quorum systems as a special case), quorums are uniform for all processes. Processes have the same set of individual minimal quorums. For example, a quorum system that tolerates $f$ Byzantine failures out of $3f+1$ processes considers any set of $2f+1$ processes as a quorum for all processes.

2.2 Properties

A quorum system is expected to maintain certain properties in order to provide distributed abstractions such as Byzantine reliable broadcast and consensus. Quorum intersection and quorum availability are well-established requirements for quorum systems. In the following section, we will see their adaption to HQS. Further, we identify a new property we call quorum subsumption that helps achieve the aforementioned abstractions on HQS. Finally, we briefly present a few related quorum systems, and their properties.

Quorum Intersection. Processes store and retrieve information from the quorum system by communicating with its quorums. To ensure that information is properly passed from a quorum to another, the quorum system is expected to maintain a well-behaved process at the intersection of every pair of quorums. For example, in the running example in Fig. 1, all the quorums of well-behaved processes intersect at at least one of well-behaved processes in $\{1,3,4\}$ .

Definition 2.2 (Quorum Intersection).

A quorum system $\mathcal{Q}$ has quorum intersection iff every pair of quorums of well-behaved processes in $\mathcal{Q}$ intersect at a well-behaved process, i.e., $\forall p,p^{\prime}\in\mathcal{W}.\ q\in\mathcal{Q}(p).\ q^{\prime}\in\mathcal{Q}(p^{\prime}).\ q\cap q^{\prime}\cap\mathcal{W}\neq\emptyset$

Quorum Availability. In order to support progress for a process, the quorum system is expected to have at least one quorum for that process whose members are all well-behaved. We say that the quorum system is weakly available for that process. (In the literature, this notion of availability is often unqualified, but we explicitly contrast the weak notion to the strong notion that we will define.) In classical quorum systems, any quorum is a quorum for all processes. This guarantees that if the quorum system is available for a process, it is available for all processes. However, this is obviously not true in a heterogeneous quorum system where quorums are not uniform. In this setting, we weaken the availability property so that it requires only a subset and not necessarily all well-behaved processes to have a well-behaved quorum. In Fig. 1, $\mathcal{Q}$ is available for the set $\{1,3,4\}$ : the quorum $\{1,4\}$ of process $1$ , and the quorum $\{3,4\}$ of processes $3$ and $4$ make them weakly available. Each process in that subset can always communicate with a quorum independently of Byzantine processes.

Definition 2.3 (Weak Availability).

A quorum system is weakly available for a set of processes $P$ iff every process in $P$ has at least one quorum that is a subset of well-behaved processes $\mathcal{W}$ . A quorum system is available iff it is available for a non-empty set of processes.

If a quorum system is weakly available, there is at least one well-behaved process that can communicate with a quorum independently of Byzantine processes.

With quorum availability introduced, we can consider when a quorum system is unavailable. A quorum system is unavailable for a process when that process has no quorum in $\mathcal{W}$ , i.e., the Byzantine processes $\mathcal{B}$ can block every one of its quorums. We generalize this idea in the notion of blocking.

$\begin{array}[]{l}\mathcal{P}=\mathcal{W}\cup\mathcal{B},\ \ \mathcal{W}=\{1,3,4,5\},\ \ \mathcal{B}=\{2\}\\ \mathcal{Q}=\{1\mapsto\{\{1,2,3\},\{1,4\}\},\\ \phantom{\mathcal{Q}=\{}3\mapsto\{\{3,4\},\{1,3\}\}\\ \phantom{\mathcal{Q}=\{}4\mapsto\{\{3,4\}\}\\ \phantom{\mathcal{Q}=\{}5\mapsto\{\{1,2,3,5\}\}\}\end{array}$

Figure 1: Quorum System Example

Definition 2.4 (Blocking Set).

A set of processes $P$ is a blocking set for a process $p$ (or is $p$ -blocking) if $P$ intersects every quorum of $p$ .

For example, consider cardinality-based quorum systems where the system contains $3f+1$ processes. Any set of size $f+1$ is a blocking set for all well-behaved processes, since a set with $f+1$ processes intersects with any quorum, a set with $2f+1$ processes. In Fig. 1, well-behaved process $5$ is blocked by $\{2\}$ , since its only quorum $\{1,2,3,5\}$ intersect with $\{2\}$

Notice also that the definition does not stipulate that the blocking set is Byzantine, but rather it is more general. The concept of blocking will be useful for designing our protocols in (§ 6). For now, we prove a lemma for blocking sets. In order to state the lemma, we generalize the notion of availability. Given a set of processes $P$ , we generalize availability for $P$ at the complete set of well-behaved processes $\mathcal{W}$ (Definition 2.3) to availability for $P$ at a subset $P^{\prime}$ of well-behaved processes. We say that a quorum system is weakly available for a set of processes $P$ at a subset of well-behaved processes $P^{\prime}$ iff every process in $P$ has at least one quorum that is a subset of $P^{\prime}$ .

Lemma 2.5.

In every quorum system that is weakly available for a set of processes $P$ at $P^{\prime}$ , every blocking set of every process in $P$ intersects $P^{\prime}$ .

Proof 2.6.

Consider a quorum system that is weakly available for $P$ at $P^{\prime}$ , a process $p$ in $P$ , and a set of processes $P^{\prime\prime}$ that blocks $p$ . By the definition of available, there is at least one quorum $q$ of $p$ that is a subset of $P^{\prime}$ . By the definition of blocking set (Definition 2.4), $q$ intersects with $P^{\prime\prime}$ . Hence, $P^{\prime}$ intersects $P^{\prime\prime}$ as well.

Quorum subsumption. We now introduce the notion of quorum subsumption.

Definition 2.7 (Quorum Subsumption).

A quorum system $\mathcal{Q}$ is quorum subsuming for a quorum $q$ iff every process in $q$ has a quorum that is included in $q$ , i.e., $\forall p\in q.\ \exists q^{\prime}\in\mathcal{Q}(p).\ q^{\prime}\subseteq q$ . We say that $\mathcal{Q}$ is quorum subsuming for a set of quorums if it is quorum subsuming for each quorum in the set.

In Fig. 1, $\mathcal{Q}$ is quorum subsuming for $\{3,4\}$ : both members in this quorum have the quorum $\{3,4\}$ that is trivially a subset of itself. However, $\mathcal{Q}$ is not quorum subsuming for process $1$ ’s quorum $\{1,4\}$ : process $4$ ’s only quorum $\{3,4\}$ is not a subset of $\{1,4\}$ .

sender	1	2	3	4
$\mathit{BCast(m_{1})}$
	$\mathit{Echo(m_{1})}$		$\mathit{Echo(m_{1})}$	$\mathit{Echo(m_{1})}$
		$\mathit{Ready(m_{2})}$
	$\mathit{Ready(m_{1})}$		$\mathit{Ready(m_{2})}$	$\mathit{Ready(m_{2})}$
	blocked forever			$\mathit{Deliver(m_{2})}$

Table 1: Non-termination for Bracha protocol with blocking sets

Quorum subsumption is inspired by and weakens the notion of quorum sharing [34]. Quorum sharing requires the above subsumption property for all quorums. Thus, many quorum systems including Ripple and Stellar do not satisfy it (unless Byzantine processes do not lie about their slices [34].) They can maintain the subsumption property only for quorums of a well-behaved subset of processes. In particular, no requirement can be made for quorums of Byzantine processes. Therefore, we define the weaker notion of quorum subsumption for a subset of quorums, and later show that it is sufficient to implement broadcast and consensus.

In order to make progress, protocols (such as Bracha’s Byzantine reliable broadcast [9]) require the members of a quorum to be able to communicate with at least one of their own quorums, or communicate with a subset of processes that contains at least one well-behaved process. Let us see intuitively how quorum subsumption can support liveness properties. Consider a quorum system $\mathcal{Q}$ for processes $\mathcal{P}=\{1,2,3,4\}$ where the Byzantine processes are $\{2\}$ , and $\mathcal{Q}(1)=\{\{1,3,4\}\}$ , $\mathcal{Q}(3)=\{\{1,2,3\}\}$ , and $\mathcal{Q}(4)=\{\{2,3,4\}\}$ . The quorum system $\mathcal{Q}$ has quorum intersection, and is weakly available for the set $\{1\}$ since there is a well-behaved quorum $\{1,3,4\}$ for the process $1$ . In the classic Bracha protocol, the sender broadcasts $\mathit{Echo}(m)$ , a well-behaved broadcasts $\mathit{Echo}(m)$ when it receives it from the sender, it broadcasts $\mathit{Ready}(m)$ after receiving $2f+1$ $\mathit{Echo}(m)$ or $f+1$ $\mathit{Ready}(m)$ messages, and finally, delivers $m$ if it receives $2f+1$ $\mathit{Ready}(m)$ messages. In Stellar [33] and follow-up works [34, 24, 15], the check for receiving $\mathit{Ready}(m)$ messages from $f+1$ processes is replaced with receiving $\mathit{Ready}(m)$ messages from a blocking set of the current process. Let’s consider the example execution presented in Table 1; it gives an intuition of why the quorum system needs stronger conditions than weak availability. Consider a Byzantine sender who sends $\mathit{BCast}(m_{1})$ to process $\{1,3,4\}$ . Well-behaved process $\{1,3,4\}$ sends out $\mathit{Echo}(m_{1})$ to each other. We let process $1$ deliver $\mathit{Echo}(m_{1})$ messages from process $1$ , $3$ , and $4$ first; it then sends out $\mathit{Ready}(m_{1})$ messages. We note that the two processes $3$ , and $4$ cannot broadcast $\mathit{Ready}(m_{1})$ since they have not received $\mathit{Echo}(m_{1})$ from a quorum of their own. Then the Byzantine process $2$ sends $\mathit{Ready}(m_{2})$ messages to process $\{3,4\}$ . Since the set $\{2\}$ is blocking for the quorums of both processes $3$ and $4$ , both send out $\mathit{Ready}(m_{2})$ messages. These broadcast protocols prevent a process that is ready for a value from getting ready for another value. Therefore, although $\{3\}$ and $\{4\}$ are both blocking sets for the process $1$ , it cannot become ready for $m_{2}$ . Process $1$ never receives enough Thus, $\mathit{Ready}$ messages for either $m_{1}$ or $m_{2}$ to deliver a message, and is blocked forever. If the quorum $\{1,3,4\}$ for $1$ had the quorum subsumption property, then $3$ and $4$ could send out $\mathit{Ready}(m_{1})$ messages, and eventually $1$ would make progress.

Complete Quorum. We will later see that quorum availability and quorum subsumption are important together for liveness. We succinctly combine the two properties into the notion of complete quorums.

Definition 2.8 (Complete Quorum).

A quorum $q$ in a quorum system $\mathcal{Q}$ is a complete quorum if all its members are well-behaved, and $\mathcal{Q}$ is quorum subsuming for $q$ .

In our previous running example Fig. 1, quorum $\{3,4\}$ is a complete quorum: both of its members are well-behaved and $\mathcal{Q}$ is quorum subsuming for $\{3,4\}$ .

Definition 2.9 (Strong Availability).

A quorum system $\mathcal{Q}$ has strong availability for a subset of processes $P$ iff every process in $P$ has at least one complete quorum. We call $P$ a strongly available set for $\mathcal{Q}$ , and call a member of $P$ a strongly available process. We say that $\mathcal{Q}$ is strongly available if it is strongly available for a non-empty set.

Intuitively, operations stay available at a strongly available process since its complete quorum can perform operations on his behalf in the face of Byzantine attacks. In Fig. 1, $\mathcal{Q}$ is strongly available for $\{3,4\}$ . In contrast, $\mathcal{Q}$ is only weakly available for process $1$ , since its quorum $\{1,2,3\}$ includes $2$ that is not well-behaved, and its other quorum $\{1,4\}$ is well-behaved but not a complete quorum.

By Lemma 2.5, every blocking set of every strongly available process contains at least one well-behaved process.

3 Protocol Implementation

In the subsequent sections, we will see that it is impossible to construct a protocol for Byzantine reliable broadcast and consensus in an HQS given only quorum intersection and quorum availability. After that, we give a protocol for Byzantine reliable broadcast and consensus for an HQS that has quorum intersection and strong availability. We first need a model of quorum-based protocols, and then the exact specifications of the distributed abstractions we aim to design protocols for. In this section, we consider the former.

We consider a modular design for protocols. A protocol is captured as a component that accepts request events and issues response events. A component uses other components as sub-components: it issues requests to them and accepts responses from them. A component stores a state and defines handlers for incoming requests from the parent component, and incoming responses from children components. Each handler gets the pre-state and the incoming event as input, and outputs the post-state and outgoing events, either as responses to the parent or requests to the children components. The outputs of a handler can be deterministically a function of its inputs, or randomized.

Definition 3.1 (Determinism).

A protocol is deterministic iff the outputs of its handlers are a function of the inputs.

Quorum-based Protocols. A large class of protocols are implemented based on quorum systems. In order to state impossibility results for these protocols, we capture the properties of quorum-based protocols [34, 29] as a few axioms. Our impossibility results concern protocols that adhere to the necessity, sufficiency, and locality axioms.

A process in a quorum-based protocol should process a request only if it can communicate with at least one of its quorums.

Axiom 1 (Necessity of Quorums [34]).

If a well-behaved process $p$ issues a response for a request then there must be a quorum $q$ of $p$ such that $p$ receives at least one message from each member of $q$ .

In a quorum-based protocol, a process only needs the participation of itself and members of one of its quorums to deliver a message.

Axiom 2 (Sufficiency of Quorums).

For every execution where a well-behaved process $p$ issues a response, there exists an execution where only $p$ and a quorum of $p$ take steps, and $p$ eventually issues the same response.

We add a remark for Byzantine reliable broadcast (BRB) which has a designated sender process. We will use a slight variant of the sufficiency axiom for BRB that states that there exists an execution where only the sender, $p$ and a quorum of $p$ take steps.

A process’s local state is only affected by the information that it receives from the members of it’s quorums.

Axiom 3 (Locality).

The state of a well-behaved process changes upon receiving a message only if the sender is a member of one of its quorums.

For BRB, we will use a slight variant of the locality axiom that allows processes change state upon receiving messages from the sender in addition to members of quorums.

4 Protocol Specification

We now define the specification of reliable broadcast and consensus for HQS. The liveness properties are weaker than classical notions since in an HQS, availability might be maintained only for a subset $P$ of well-behaved processes.

Reliable Broadcast. We now define the specification of the reliable broadcast abstraction. The abstraction accepts a single broadcast request from a designated sender (either in the system or a process that is separate from the other processes in system), and issues delivery responses.

Definition 4.1 (Specification of Reliable Broadcast).

•

(Validity for a set of well-behaved processes $P$ ). If a well-behaved process $p$ broadcasts a message $m$ , then every process in $P$ eventually delivers $m$ .
•

(Integrity). If a well-behaved process delivers a message $m$ from a well-behaved sender $p$ , then $m$ was previously broadcast by $p$ .
•

(Totality for a set of well-behaved processes $P$ ). If a message is delivered by a well-behaved process, then every process in $P$ eventually delivers a message.
•

(Consistency). No two well-behaved processes deliver different messages.
•

(No duplication). Every well-behaved process delivers at most one message.

We also consider a variant of reliable broadcast called federated voting. Similar to reliable broadcast, the abstraction accepts a broadcast request from processes, and issues delivery responses. In contrast to reliable broadcast where there is a dedicated sender, in federated voting, every process can broadcast a message. The specification of federated voting is similar to that of reliable broadcast except for validity. The messages that well-behaved processes broadcast may not be the same. Therefore, the validity property provides guarantees only when the messages are the same or there is only one sender. The validity property for a set of well-behaved processes $P$ guarantees that if all well-behaved processes broadcast a message $m$ , or only one well-behaved process broadcasts a message $m$ , then every process in $P$ eventually delivers $m$ .

Consensus. We now consider the specification of the consensus abstraction. It accepts propose requests from processes in the system, and issues decision responses.

Definition 4.2 (Specification of Consensus).

•

(Validity). If all processes are well-behaved, and some process decides a value, then that value was proposed by some process.
•

(Agreement). No two well-behaved processes decide differently.
•

(Termination for a set of well-behaved processes $P$ ). Every process in $P$ eventually decides.

5 Impossibility

We now present the impossibility results for consensus and Byzantine Reliable Broadcast (BRB). It is known that quorum intersection and quorum availability are necessary conditions [34] to implement consensus and BRB protocols. In this section, we show that while these two conditions are necessary, they are not sufficient.

We consider the information-theoretic settings (Fault axiom [21]), where byzantine processes have unlimited computational power, and can show arbitrary behavior. However, processes communicate only over secure channels so that the recipient knows the identity of the sender. A Byzantine process is unable to impersonate a well-behaved process. This is similar to the classic unauthenticated Byzantine general problem [30], and is necessary for open decentralized blockchains and HQS, where the trusted authorities including public key infrastructures may not be available.

The two proofs will take a similar approach. First, we assume there does exist a protocol for our distributed abstraction that satisfies all the desired specifications. We then present a quorum system $\mathcal{Q}$ and consider its executions that have quorum intersection and availability in the face of Byzantine attacks. We then show through a series of indistinguishable executions that the protocol cannot satisfy all the desired specifications, leading to a contradiction. The high-level idea is that in the information-theoretic setting, a well-behaved process is not able to distinguish between an execution where the sender is Byzantine and sends misleading messages, and an execution where the relaying process is Byzantine and forwards misleading messages. For example, let $p_{1},p_{2}$ and $p_{3}$ be three processes in the system. When $p_{3}$ receives conflicting messages from $p_{1}$ through $p_{2}$ , it does not know whether $p_{1}$ or $p_{2}$ is Byzantine. This eventually leads to violation of the agreement or validity property of the abstraction.

We consider binary proposals for consensus, and binary values (from the sender) for reliable broadcast. For the consensus abstraction, we succinctly present the values that processes propose as as a vector of values that we call a configuration. If the initial value of a process is $\bot$ in the configuration, that process is considered Byzantine. Otherwise, the process is well-behaved. For example, a configuration $C=\langle 0,0,\bot\rangle$ denotes the first and second process proposing zero and the third process being Byzantine.

5.1 Consensus

We first consider consensus protocols in HQS.

Theorem 5.1.

Quorum intersection and weak availability are not sufficient for deterministic quorum-based consensus protocols to provide validity, agreement and termination for weakly available processes.

Proof 5.2.

We suppose there is a quorum-based consensus protocol that guarantees validity, agreement, and termination for every quorum system $\mathcal{Q}$ with quorum intersection and weak availability, towards contradiction. Consider a quorum system $\mathcal{Q}$ for processes $\mathcal{P}=\{a,b,c\}$ with the following quorums: $\mathcal{Q}(a)=\{\{a,c\}\}$ , $\mathcal{Q}(b)=\{\{a,b\}\}$ , $\mathcal{Q}(c)=\{\{b,c\}\}$ .

We make the following observations: (1) if all processes are well-behaved, then $\mathcal{Q}$ has quorum intersection and weak availability for $\{a,b,c\}$ , (2) if only process $a$ is Byzantine, then $\mathcal{Q}$ preserves quorum intersection, and weak availability for $\{c\}$ , (3) if only process $c$ is Byzantine, then $\mathcal{Q}$ preserves quorum intersection, and weak availability for $\{b\}$ . Going forward, we implicitly assume termination for weakly available processes.

Now consider the following four configurations as shown in Fig. 2: $C_{0}=\langle{0,0,0}\rangle$ , $C_{1}=\langle{1,1,1}\rangle$ , $C_{2}=\langle{0,1,\bot}\rangle$ , and $C_{3}=\langle{\bot,1,1}\rangle$ . The goal is now to show a series of executions over the configurations so that at least one property of the protocol is violated.

•

We begin with execution $E_{0}$ (shown in red) with the initial configuration $C_{0}$ . All the messages between $a$ and $c$ are delivered. By termination for weakly available processes and validity, process $a$ decides 0. Additionally, by quorum sufficiency, $a$ can reach this decision with only processes $\{a,c\}$ taking steps.
•

Next, we have execution $E_{1}$ (shown in blue) with initial configuration $C_{1}$ . All the messages between $b$ and $c$ are delivered. Again, by termination for weakly available processes and validity, process $c$ decides 1. By quorum sufficiency, $c$ can reach this decision with only processes $\{b,c\}$ taking steps.
•

Next, we have execution $E_{2}$ as a sequence of $E_{1}$ and $E_{0}$ , with initial configuration $C_{2}$ . Suppose messages between well-behaved processes $a$ and $b$ are delayed. Byzantine process $c$ first replays $E_{1}$ with process $b$ , then replays $E_{0}$ with process $a$ . This cause process $a$ to decide $0$ . Now let Byzantine process $c$ stay silent, and messages between processes $a$ and $b$ be delivered. By termination for $b$ , agreement and quorum sufficiency, process $a$ makes $b$ decide $0$ as well (shown in green).
•

Lastly, we have execution $E_{3}$ with initial configuration $C_{3}$ . Suppose messages between $b$ to $c$ are delivered in the beginning. We let processes $\{b,c\}$ replay $E_{1}$ ; thus, $c$ decides 1. Then, Byzantine process $a$ sends messages to $b$ as if it were at the end of $E_{2}$ . In turn, $b$ decides 0. Thus, agreement is violated as two well-behaved processes decided differently.

Figure 2: Indistinguishable Executions

Indistinguishably

We provide some intuition for the proof construction. Ultimately, the problem lies in process $b$ not being able to distinguish whether process $a$ or process $c$ is the Byzantine process. More specifically, both $E_{2}$ and $E_{3}$ begin with execution $E_{1}$ . Since process $b$ cannot distinguish between the two executions, it does not know which value to decide. If process $b$ believes $E_{2}$ is the actual execution, then $b$ should decide 0 to agree with the decision of well-behaved process $a$ . However, if $E_{3}$ is the actual execution, then agreement is violated as process $c$ decided 1. Conversely, if process $b$ believes $E_{3}$ is the actual execution, then $b$ should decide 1 to agree with the decision of well-behaved process $c$ . Then, if $E_{2}$ is the actual execution, agreement is violated as the well-behaved process $a$ decided 0.

We note that this proof could not be constructed if there was quorum subsumption. For example, if the process $b$ adds the quorum $\{a,b,c\}$ , then $\mathcal{Q}$ will have quorum subsumption for the quorum $\{a,b,c\}$ of $b$ . However, then by quorum subsumption, there will be no Byzantine process, and the executions $E_{2}$ and $E_{3}$ cannot be constructed. If the process $a$ adds the quorum $\{a,b\}$ , then it will have quorum subsumption. However, then the process $a$ cannot Byzantine process anymore, and the executions $E_{3}$ cannot be constructed. Similarly, if the process $b$ adds the quorum $\{b,c\}$ , the executions $E_{2}$ cannot be constructed.

5.2 Byzantine Reliable Broadcast

Now, we prove the insufficiency of quorum intersection and quorum availability for Byzantine reliable broadcast.

For the reliable broadcast abstraction, we represent the initial configuration as an array of values received by the processes from the sender. The sender is a fixed and external process in the executions, and is only used to assign input values for processes in the system, which are captured as the initial configurations. The sender does not take steps in the executions, and processes are not able to distinguish executions based on the sender.

Theorem 5.3.

Quorum intersection and weak availability are not sufficient for deterministic quorum-based reliable broadcast protocols to provide validity and totality for weakly available processes, and consistency.

Proof 5.4.

The proof is similar to the proof for consensus. In fact, we will reuse the construction. There are differences between reliable broadcast and consensus specifications in (1) their validity properties, and (2) their totality and termination properties respectively. The proof can be adjusted for these differences. For reliable broadcast, we need a sender process $s$ who broadcasts a message. In executions that we want a well-behaved process to deliver the message $m$ , we either (1) keep the sender $s$ well-behaved and have it send $m$ , and then apply validity, or (2) have a process deliver $m$ , then apply totality and consistency. The initial configuration represents values received by each process from the sender.

Executions follow those in the previous proof. Message delivery and delays mirror the previous executions. In execution $E_{0}$ for configuration $C_{0}$ , the well-behaved sender $s$ broadcasts 0, and messages between processes $a$ and $c$ are delivered. By validity for weakly available processes, process $a$ delivers 0, and by quorum sufficiency, only processes $\{a,c\}$ need to take steps. In execution $E_{1}$ for configuration $C_{1}$ , the well-behaved sender $s$ broadcasts 1, and messages between processes $b$ and $c$ are delivered. By validity for weakly available processes, and quorum sufficiency, process $c$ delivers 1, only with $\{b,c\}$ taking steps. In configurations $C_{2}$ and $C_{3}$ , the sender $s$ is Byzantine. The messages between processes $a$ and $b$ are delayed in the beginning. In execution $E_{2}$ for configuration $C_{2}$ , the Byzantine sender $s$ and Byzantine process $c$ replay $E_{1}$ with process $b$ , then replay $E_{0}$ with process $a$ . Then Byzantine process $c$ stays silent, and messages between processes $a$ and $b$ are delivered. By totality for weakly available processes, since process $a$ delivers 0, then process $b$ will also deliver a value. By consistency, process $b$ delivers 0 as well. In the last execution $E_{3}$ for configuration $C_{3}$ , we let the Byzantine process $a$ stay silent in the beginning, and processes $b$ and $c$ replay $E_{1}$ . Thus, process $c$ delivers 1. Afterwards, messages between process $b$ and $c$ are delayed, and the Byzantine process $a$ replays $E_{2}$ . Again, process $b$ cannot distinguish between the two executions $E_{2}$ and $E_{3}$ . Since process $a$ sends the exact same messages to process $b$ as the end of $E_{2}$ , process $b$ will deliver 0. Thus, consistency between $c$ and $b$ is violated.

6 Protocols

We just showed that quorum intersection and availability are not sufficient to implement our desired distributed abstractions. Now, we show that quorum intersection and strong availability, our newly introduced property are sufficient to implement both Byzantine reliable broadcast and consensus.

Implements:

\mathsf{ReliableBroadcast}

\textbf{request}:\mathit{broadcast}(v)

\textbf{response}:\mathit{deliver}(v)

4Vars:

Q

\triangleright

Minimal quorums of

\mathbf{self}

\mathcal{F}:\mathsf{Set}[\mathcal{P}]

\triangleright

The followers of

\mathbf{self}

\mathit{echoed},\mathit{readied},\mathit{delivered}:\mathsf{Boolean}\leftarrow\mathsf{false}

E,R:V\mapsto\mathsf{Set}[\mathcal{P}]\leftarrow\emptyset

\triangleright

Set of echoed and readied processes

8Uses:

\mathit{ptp}:\mathsf{PointToPointLink}

11upon request

\mathit{broadcast}(v)

from sender

\mathit{ptp}\ \textbf{request}\ \mathit{send}(p,\mathit{BCast}(v))

for each

p\in\mathcal{P}

15upon

\mathit{ptp}\ \textbf{response}\ \mathit{deliver}\mbox{$($}p^{\prime},\mathit{BCast}\mbox{$($}v\mbox{$)$}\mbox{$)$}

16 if $\neg\mathit{echoed}$ then

\mathit{echoed}\leftarrow\mathsf{true}

\mathit{ptp}\ \textbf{request}\ \mathit{send}(p,\mathit{Echo}(v))

for each

p\in\mathcal{F}

22upon

\mathit{ptp}\ \textbf{response}\ \mathit{deliver}\mbox{$($}p^{\prime},\mathit{Echo}\mbox{$($}v\mbox{$)$}\mbox{$)$}

E(v)\leftarrow E(v)\cup\{p^{\prime}\}

25 if $\neg\mathit{readied}$ $\wedge$ $\exists q\in Q.\ q\subseteq E(v)$ then

\mathit{readied}\leftarrow\mathsf{true}

\mathit{ptp}\ \textbf{request}\ \mathit{send}(p,\mathit{Ready}(v))

for

each

p\in\mathcal{F}

31upon

\mathit{ptp}\ \textbf{response}\ \mathit{deliver}\mbox{$($}p^{\prime},\mathit{Ready}\mbox{$($}v\mbox{$)$}\mbox{$)$}

R(v)\leftarrow R(v)\cup\{p^{\prime}\}

33 if $\neg\mathit{readied}$ $\wedge$ $R$ is a blocking set of $\mathbf{self}$ then

\mathit{readied}\leftarrow\mathsf{true}

\mathit{ptp}\ \textbf{request}\ \mathit{send}(p,\mathit{Ready}(v))

for

each

p\in\mathcal{F}

37 if $\neg\mathit{delivered}$ $\wedge$ $\exists q\in Q.\ q\subseteq R(v)$ then

\mathit{delivered}\leftarrow\mathsf{true}

\textbf{response}\ \mathit{deliver}(v)

Algorithm 1 Byzantine Reliable Broadcast (BRB)

6.1 Reliable Broadcast Protocol

In Alg. 1, we adapt the Bracha protocol [9] to show that quorum intersection and strong availability together are sufficient for Byzantine reliable broadcast. The parts that are different from the classical protocol are highlighted in blue.

Each process stores the set of its individual minimal quorums $Q$ , and its set of followers $\mathcal{F}$ . It also stores the boolean flags $\mathit{echoed}$ , $\mathit{readied}$ , and $\mathit{delivered}$ which record actions the process has taken to avoid duplicate actions. It further uses point-to-point links $\mathit{ptp}$ to each of its followers. Upon receiving a request to broadcast a value $v$ (at Alg. 1), the sender broadcasts the value $v$ to all processes (at Alg. 1). Upon receiving the message from the sender (at Alg. 1), a well-behaved process echoes the message among its followers (at Alg. 1) only if it has not already $\mathit{echoed}$ . When a well-behaved process receives a quorum of consistent echo messages (at Alg. 1), it sends ready messages to all its followers (at Alg. 1). A well-behaved process can also send a ready message when it receives consistent ready messages from a blocking set (at Alg. 1). When a well-behaved process receives a quorum of consistent ready messages for $v$ (at Alg. 1), it delivers $v$ (at Alg. 1). The implementation of the federated voting abstraction is similar. The only difference is that there can be multiple senders (at Alg. 1).

We prove that this protocol implements Byzantine reliable broadcast when the quorum system satisfies quorum intersection, and strong availability. We remember that strong availability requires both weak availability and quorum subsumption. More precisely, it requires a well-behaved quorum $q$ for a process $p$ , and quorum subsumption for $q$ .

Theorem 6.1.

Quorum intersection and strong availability are sufficient to implement Byzantine reliable broadcast.

This theorem follows from five lemmas in the appendix [31] that prove the protocol satisfies the specification of Byzantine reliable broadcast that we defined in Definition 4.1. Consider a quorum system with quorum intersection, and strong availability for $P$ . Here, we state and prove only the validity property.

Lemma 6.2.

The BRB protocol guarantees validity for $P$ .

Proof 6.3.

Consider a well-behaved sender that broadcasts a message $m$ . We show that every process in $P$ eventually delivers $m$ . By availability, every process $p\in P$ has a complete quorum $q$ . Consider a process $p^{\prime}\in q$ . By quorum subsumption, $p^{\prime}$ has a quorum $q^{\prime}\subseteq q$ . By availability, all members of $q$ (including $q^{\prime}$ ) are well-behaved. Thus, when they receive $m$ from the sender, they all echo it to their followers. The processes in $q^{\prime}$ have $p^{\prime}$ as a follower. Thus, $p^{\prime}$ receives consistent echo messages for $m$ from one of its quorums $q^{\prime}$ . Thus, $p^{\prime}$ sends out ready messages for $m$ to its followers. Thus, all processes in $q$ send out ready messages for $m$ to their followers. The processes in $q$ have $p$ as a follower. Therefore, $p$ receives a quorum of consistent ready messages for $m$ from one of its quorums $q$ , and delivers $m$ .

6.2 Byzantine Consensus Protocol

In this section, we show that quorum intersection and strong availability are sufficient to implement Byzantine consensus. We first present the consensus protocol for heterogeneous quorum systems, and then prove its correctness.

At a high level, the protocol proceeds in rounds with assigned leaders for each. Ballots that carry proposal values are totally ordered. A leader tries to commit its own candidate ballot only after aborting any lower ballot in the system. Leaders use the federated voting abstraction (that we saw in § 4) to abort or commit ballots. There may be multiple leaders or Byzantine leaders before GST, and they may broadcast contradicting abort and commit messages for the same ballot. However, by the consistency property of federated voting, processes agree on aborting or committing ballots.

A ballot $b$ is a pair $\langle r,v\rangle$ of a round number $r$ and a proposed value $v$ . Ballots are totally ordered by first their round numbers, and then their values: a ballot ${\langle r,v\rangle}$ is below another ${\langle r^{\prime},v^{\prime}\rangle}$ , written as $\langle r,v\rangle<\langle r^{\prime},v^{\prime}\rangle$ , if $r<r^{\prime}$ or $r=r^{\prime}\wedge v<v^{\prime}$ . Two ballots $b=\langle r,v\rangle$ and $b^{\prime}=\langle r^{\prime},v^{\prime}\rangle$ are compatible, $b\sim b^{\prime}$ , if they have the same value, i.e., $v=v^{\prime}$ ; otherwise, they are incompatible, $b\not\sim b^{\prime}$ . We say that a ballot is below and incompatible with another, $b\mathbb{\;\lnsim\;}b^{\prime}$ , if $b<b^{\prime}$ and $b\not\sim b^{\prime}$ . For message passing communication, we assume batched network semantics (BNS), where messages issued in an event are sent as a batch, and the receiving process delivers and processes the batch of messages together. (In particular, as we will see later in the correctness proofs, if prepare messages that are sent together are not processed together the validity property can be violated.)

The protocol is similar to SCP [38, 25] in structure; the important difference is that this protocol uses leaders [34] and guarantees termination. Our protocol guarantees termination regardless of Byzantine processes. On the other hand, the SCP protocol guarantees a liveness property called non-blocking which requires Byzantine processes to stop. (More precisely, if a process $p$ in the intact set [38, 24] has not yet decided in some execution, then for every continuation of that execution in which all the Byzantine processes stop, the process $p$ eventually decides.)

Implements:

\mathsf{Consensus}

\textbf{request}:\mathit{propose}(v)

\textbf{response}:\mathit{decice}(v)

4Vars:

\mathit{round}:\mathbb{N}^{+}\leftarrow 0

\triangleright

Current round number

\mathit{candidate},\mathit{prepared}:\langle\mathbb{N}^{+},V\rangle\leftarrow\langle 0,\bot\rangle

\mathit{leader}:\mathcal{P}\leftarrow p_{0}

\triangleright

current leader

7Uses:

\mathit{fv}:B\mapsto\mathsf{ByzantineReliableBroadcast}

\mathit{le}:\mathsf{EventualLeaderElection}

11upon request

\mathit{propose}(v)

\mathit{candidate}\leftarrow\langle 1,v\rangle

13 if $\mathbf{self}=\mathit{leader}$ then

\mathit{fv}(b^{\prime})

request

\,\mathit{broadcast}(\mathbb{A})

for all

b^{\prime}\mathbb{\;\lnsim\;}\mathit{candidate}

18upon

\mathit{fv}\mbox{$($}\mathit{b^{\prime}}\mbox{$)$}\ \textbf{response}\ \mathit{deliver}\mbox{$($}p,\mathbb{A}\mbox{$)$}

for all

b^{\prime}\mathbb{\;\lnsim\;}b

where

\mathit{prepared}<b

\mathit{prepared}\leftarrow b

20 if $\mathbf{self}=\mathit{leader}\wedge\mathit{prepared}=\mathit{candidate}$ then

\mathit{fv}(\mathit{candidate})

request

\mathit{broadcast}(\mathbb{C})

24upon

\mathit{fv}\mbox{$(b)$}\ \textbf{response}\ \mathit{deliver}\mbox{$($}p,\mathbb{C}\mbox{$)$}

where

b=\mathit{prepared}\land p=\mathit{leader}

\textbf{response}\ \mathit{decice}(b.v)

28upon

\mathit{timeout}

triggered

\mathit{le}\ \textbf{request}\ \mathit{Complain}(\mathit{round})

32upon

\mathit{le}\ \textbf{response}\ \mathit{new\text{-}leader}\mbox{($p$)}

\mathit{leader}\leftarrow p

\mathit{round}\leftarrow\mathit{round}+1

35 if $\mathbf{self}=\mathit{leader}$ then

\mbox{Delay for time }\Delta

38 start-timer(

\mathit{round}

)

39 if $\mathit{prepared}=\langle 0,\bot\rangle$ then

\mathit{candidate}\leftarrow\langle\mathit{round},\mathit{candidate}.v\rangle

42 else

\mathit{candidate}\leftarrow\langle\mathit{round},\mathit{prepared}.v\rangle

45 if $\mathbf{self}=\mathit{leader}$ then

\mathit{fv}(b^{\prime})

request

\,\mathit{broadcast}(\mathbb{A})

for all

b^{\prime}\mathbb{\;\lnsim\;}\mathit{candidate}

Algorithm 2 Byzantine Consensus

Each process stores four local variables: $\mathit{round}$ is the current round number, $\mathit{candidate}$ is the ballot that the process tries to commit, $\mathit{prepared}$ is the ballot that the process is safe to discard any ballots lower and incompatible with, and $\mathit{leader}$ is the current leader. Each process uses an instance of federated voting for each ballot, and an eventual leader election module. The latter issues $\mathit{new\text{-}leader}$ events, and eventually elects a well-behaved process as the leader. (Previous work [34] presented a probabilistic leader election module.)

Upon receiving a proposal request (at Alg. 2), a well-behaved process initializes its candidate ballot to the pair of the first round and its own proposal (at Alg. 2). If the current process $\mathbf{self}$ is the leader, it tries to prepare its $\mathit{candidate}$ by broadcasting abort $\mathbb{A}$ messages for all ballots with $\mathit{candidate}$ (at Alg. 2). When a well-behaved process delivers $\mathbb{A}$ messages from the leader for all ballots below and incompatible with some ballot $b$ , and its current $\mathit{prepared}$ ballot is below $b$ (at Alg. 2), it sets $\mathit{prepared}$ to $b$ (at Alg. 2). If the current process $\mathbf{self}$ is the leader, and the $\mathit{prepared}$ ballot is equal to the $\mathit{candidate}$ ballot, then it broadcasts a commit $\mathbb{C}$ message for its $\mathit{candidate}$ ballot (at Alg. 2). When a well-behaved process delivers a $\mathbb{C}$ message for a ballot $b$ from the leader, and it has already prepared the same ballot (at Alg. 2), it decides the value of that ballot (at Alg. 2).

To ensure liveness, a well-behaved process triggers a timeout if no value is decided after a predefined time elapses in each round. The process then complains to the leader election module (at Alg. 2). When the leader election module issues a new leader (at Alg. 2), a well-behaved process updates its $\mathit{leader}$ variable, and increments the $\mathit{round}$ number (at Alg. 2). The leader itself then waits for a time $\Delta$ (at Alg. 2) which we will further explain below. The process also resets the timer with a doubled timeout for the next round (at Alg. 2). It then updates the $\mathit{candidate}$ ballot: if no value is prepared before, the $\mathit{candidate}$ ballot is updated to the new round number and the value of the current $\mathit{candidate}$ (at Alg. 2); otherwise, it is updated to the new round number and the value of the $\mathit{prepared}$ ballot (at Alg. 2). Then, the leader tries to prepare the $\mathit{candidate}$ by aborting below and incompatible ballots similar to the steps above (at Alg. 2).

Figure 3: Last Minute Attack.

b={\langle 1,4\rangle}

. The

\mathit{candidate}

of well-behaved leader

l_{2}

b^{\prime}={\langle 2,3\rangle}

. The votes

\mathbb{C}

and

\mathbb{A}

are abbreviated as

C

and

A

. The new leader events are triggered at the black dots at each process. Prepared ballots are shown below the time line for each process.

Let us now explain why delay $\Delta$ is needed for termination. Without this delay, a Byzantine leader can perform a last minute attack that we illustrate in Fig. 3. Consider that we have four processes, one of them is Byzantine, and any set of three processes is a quorum. Let the Byzantine process be the leader $l_{1}$ , and let the ballot $b$ be prepared. The leader $l_{1}$ sends a commit for ballot $b$ to one well-behaved process $p_{3}$ . Then, $p_{3}$ echos commit for $b$ . Then, the timeout for $l_{1}$ happens, and the next well-behaved leader $l_{2}$ comes up. Without the delay, $l_{2}$ may have not prepared $b$ yet (although other well-behaved processes $p_{3}$ and $p_{4}$ prepared it). Therefore, the ballot $b^{\prime}$ that $l_{2}$ updates its candidate to (at Alg. 2) is not $b$ , and may not be compatible with $b$ . In order to prepare $b^{\prime}$ , the leader $l_{2}$ tries to abort $b$ (at Alg. 2) but $b$ cannot be aborted: in order to abort $b$ , a quorum of processes should echo it. However, the well-behaved process $p_{3}$ has already echoed commit, and if the Byzantine process $l_{1}$ remains silent, the remaining two well-behaved processes $l_{2}$ and $p_{4}$ are not a quorum, and cannot abort $b$ . Therefore, $l_{2}$ cannot succeed, and the timeout is triggered. Further, if the next leader is the Byzantine process $l_{1}$ again, it can repeat the above scenario: it can abort $b$ to prepare a higher ballot $b_{2}$ , and make a well-behaved process echo commit for $b_{2}$ , before passing the leadership. The attack can continue infinitely, and delay termination. If the delay $\Delta$ is larger than the bounded communication delay after GST, it makes the leader $l_{2}$ observe the highest prepared ballot $b$ , and adopt its value as the value of its candidate $b_{2}^{\prime}$ (at Alg. 2). When it tries to commit $b_{2}^{\prime}$ , since it is compatible with $b$ , it does not need abort it. Therefore, it can prepare and commit $b_{2}^{\prime}$ , and decide. We also note that instead of the delay $\Delta$ , the above attack can be avoided if the leader election can provide two successive well-behaved leaders.

Theorem 6.4.

Quorum intersection and strong availability are sufficient to implement consensus.

This theorem follows from three lemmas in the appendix [31] that prove that the protocol satisfies the specification of Byzantine consensus that we defined in Definition 4.2. An example execution of the protocol is described in the appendix [31].

7 Related Works

Quorum Systems with Heterogeneous Trust. Ripple [44] and Cobalt [35] pioneered decentralized trust. They let each node specify a list, called the unique node list (UNL), of processes that it trusts. However, they do not consider quorum availability or subsumption.

Stellar [38, 33] presents federated Byzantine quorum systems (FBQS) [24, 25] where quorums are iteratively calculated from quorums slices. Stellar also presents a federated voting and consensus protocol. In comparison, the assumptions of the protocols presented in this paper are weaker, and their guarantees are stronger. The stellar consensus protocol (SCP) guarantees termination when Byzantine processes stop. In contrast, the consensus protocol in this paper guarantees termination regardless of Byzantine processes. Further, abstract SCP [24] provides agreement only for intact processes. The intact set for an FBQS is a subset of processes that have strong availability. On the other hand, the consensus protocol in this paper provides agreement for all well-behaved processes. In FBQS, the intersections of quorums should have a process in the intact set; however, in HQS, they only need to have a well-behaved process. The validity and totality properties for the reliable broadcast for FBQS are restricted to the intact set. On the other hand, the reliable broadcast protocol in this paper provides totality for all processes that have weak availability, and validity for all processes that have strong availability.

Personal Byzantine quorum systems (PBQS) [34] capture the quorum systems that FBQSs derive form slices, and propose a responsiveness consensus protocol [48, 1, 43, 3]. They define a notion called quorum sharing which requires quorum subsumption for every quorum. Stellar quorums have quorum sharing if and only if processes do not lie about their slices. (The appendix [31] presents examples.) In this paper, we relax quorum sharing to quorum subsumption, and capture quorums that FBQSs derive even when Byzantine quorums lie about their slices, and show that even if a quorum system does not satisfy quorum sharing, safety can be maintained for all processes, and liveness can be maintained for the set of strongly available processes.

Asymmetric Byzantine quorum systems (ABQS) [15, 16, 4] allow each process to define a subjective dissemination quorum system (DQS), in a globally known system. The followup model [14] lets each process specify a subjective DQS for processes that it knows, transitively relying on the assumptions of other processes. In contrast, HQS lets each process specify its own set of quorums without knowing the quorums of other processes. Further, it does not require the specification of a set of possible Byzantine sets. Further, there are systems where a strongly available set (from HQS) exists but no guild set (from ABQS) exists. (The appendix [31] presents examples.) Therefore, HQS can provide safety and liveness for those executions but ABQS cannot. ABQS presents shared memory and broadcast protocols, and further, rules to compose two ABQSs. On the other hand, this paper proves impossibility results, and presents protocols for reliable broadcast and consensus abstractions. HQS provides strictly stronger guarantees with weaker assumptions. In ABQS, the properties of reliable broadcast are stated for wise processes and the guild. However, this paper states these four properties for well-behaved processes and the strongly available set. Well-behaved processes are a superset of wise processes, and as noted above, in certain executions, the strongly available set is a superset of the guild.

Flexible BFT [36] allows different failure thresholds between learners. Heterogeneous Paxos [45, 46] further generalizes the separation between learners and acceptors with different trust assumptions; it specifies quorums as sets rather than number of processes. These two projects introduce a consensus protocol that guarantees safety or liveness for learners with correct trust assumptions. However, they require the knowledge of all processes in the system. In contrast, HQS only requires partial knowledge of the system, and captures the properties of quorum systems where reliable broadcast and consensus protocols are impossible or possible. Multi-threshold reliable broadcast and consensus [27] and MT-BFT [40] elaborate Bracha [9] to have different fault thresholds for different properties, and different synchrony assumptions. However, they have cardinality-based or uniform quorums across processes. In contrast, HQS supports heterogeneous quorums.

K-consistent reliable broadcast (K-CRB) [7] introduces a relaxed reliable broadcast abstraction where the correct processes can define their own quorum systems. Given a quorum system, it focuses on delivering the smallest number $k$ of different values. In contrast, we propose the weakest condition to solve classical reliable broadcast and consensus. Moreover, K-CRB’s relaxed liveness guarantee (accountability) requires public key infrastructure. In contrast, all the results in this paper are for information-theoretic setting.

Our consensus protocol uses eventual leader election. Several other works present view synchronization and eventual leader election for Byzantine replicated systems [11, 10], and dynamic networks [41, 28]. It is interesting to see if their leader election modules can be generalized to the heterogeneous setting, and support responsiveness [48, 5] for our consensus protocol.

Impossibility Results. There are two categories of assumptions about the computational power of Byzantine processes. In the information-theoretic setting, Byzantine process have unlimited computational resources. While in the computational setting, Byzantine processes can not break a polynomial-time bound [23]. In this work, our impossibility results for reliable broadcast and consensus fall in the information-theoretic category. Whether the same results hold in the computational setting is an interesting open question.

FLP [22] proved that consensus is not solvable in asynchronous networks even with one crash failure. Many following works [26, 19, 2, 21, 30, 8] considered solvability, and necessary and sufficient conditions for consensus and reliable broadcast to tolerate $f$ Byzantine failures in partially synchronous networks. The number of processes should be more than $3f$ and the connectivity of the communication graph should be more than $2f$ . However, these results apply for cardinality-based quorums, which is a special instance of HQS. We generalize the reliable broadcast and consensus abstractions to HQS which supports non-uniform quorums, and prove impossibility results for them.

8 Conclusion

This paper presented a general model of heterogeneous quorum systems where each process defines its own set of quorums, and captured their properties. Through indistinguishably arguments, it proved that no deterministic quorum-based protocol can implement the consensus and Byzantine reliable broadcast abstractions on a heterogeneous quorum system that provides only quorum intersection and availability. It introduced the quorum subsumption property, and showed that the three conditions together are sufficient to implement the two abstractions. It presented Byzantine broadcast and consensus protocols for heterogeneous quorum systems, and proved their correctness when the underlying quorum system maintain the three properties.

Acknowledgments

We would like to thank DISC ’23 reviewers for detailed and constructive reviewers. Further, we would like to specially thank Giuliano Losa for his insightful comments.

References

[1] Ittai Abraham and Gilad Stern. Information theoretic hotstuff. arXiv preprint arXiv:2009.12828, 2020.
[2] Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. Consensus with byzantine failures and little system synchrony. In International Conference on Dependable Systems and Networks (DSN’06), pages 147–155. IEEE, 2006.
[3] Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. Why extension-based proofs fail. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 986–996, 2019.
[4] Orestis Alpos, Christian Cachin, and Luca Zanolini. How to trust strangers: Composition of byzantine quorum systems. In 2021 40th International Symposium on Reliable Distributed Systems (SRDS), pages 120–131. IEEE, 2021.
[5] Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. Journal of the ACM (JACM), 41(1):122–152, 1994.
[6] Mathieu Baudet, Avery Ching, Andrey Chursin, George Danezis, Francois Garillot, Zekun Li, Dahlia Malkhi, Oded Naor, Dmitri Perelman, and Alberto Sonnino. State machine replication in the libra blockchain. The Libra Assn., Tech. Rep, 7, 2019.
[7] João Paulo Bezerra, Petr Kuznetsov, and Alice Koroleva. Relaxed reliable broadcast for decentralized trust. In Networked Systems: 10th International Conference, NETYS 2022, Virtual Event, May 17–19, 2022, Proceedings, pages 104–118. Springer, 2022.
[8] Malte Borcherding. Levels of authentication in distributed agreement. In International Workshop on Distributed Algorithms, pages 40–55. Springer, 1996.
[9] Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM (JACM), 32(4):824–840, 1985.
[10] Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Liveness and latency of byzantine state-machine replication. In 36th International Symposium on Distributed Computing (DISC 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
[11] Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Making byzantine consensus live. Distributed Computing, 35(6):503–532, 2022.
[12] Ethan Buchman. Tendermint: Byzantine fault tolerance in the age of blockchains. PhD thesis, University of Guelph, 2016.
[13] Ethan Buchman, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, Dragos-Adrian Seredinschi, and Josef Widder. Revisiting tendermint: Design tradeoffs, accountability, and practical use. In 2022 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks-Supplemental Volume (DSN-S), pages 11–14. IEEE, 2022.
[14] Christian Cachin, Giuliano Losa, and Luca Zanolini. Quorum systems in permissionless network. arXiv preprint arXiv:2211.05630, 2022.
[15] Christian Cachin and Björn Tackmann. Asymmetric distributed trust. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
[16] Christian Cachin and Luca Zanolini. From symmetric to asymmetric asynchronous byzantine consensus. arXiv preprint arXiv:2005.08795, 2020.
[17] Harold Carr, Christa Jenkins, Mark Moir, Victor Cacciari Miraldo, and Lisandra Silva. Towards formal verification of hotstuff-based byzantine fault tolerant consensus in agda. In NASA Formal Methods: 14th International Symposium, NFM 2022, Pasadena, CA, USA, May 24–27, 2022, Proceedings, pages 616–635. Springer, 2022.
[18] Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99, pages 173–186, 1999.
[19] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Vassos Hadzilacos, Petr Kouznetsov, and Sam Toueg. The weakest failure detectors to solve certain fundamental problems in distributed computing. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 338–346, 2004.
[20] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288–323, 1988.
[21] Michael J Fischer, Nancy A Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26–39, 1986.
[22] Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374–382, 1985.
[23] Juan Garay and Aggelos Kiayias. Sok: A consensus taxonomy in the blockchain era. In Cryptographers’ track at the RSA conference, pages 284–318. Springer, 2020.
[24] Álvaro García-Pérez and Alexey Gotsman. Federated byzantine quorum systems. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[25] Álvaro García-Pérez and Maria A Schett. Deconstructing stellar consensus (extended version). arXiv preprint arXiv:1911.05145, 2019.
[26] Guy Goren, Yoram Moses, and Alexander Spiegelman. Probabilistic indistinguishability and the quality of validity in byzantine agreement. arXiv preprint arXiv:2011.04719, 2020.
[27] Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang. Multi-threshold asynchronous reliable broadcast and consensus. Cryptology ePrint Archive, 2020.
[28] Rebecca Ingram, Patrick Shields, Jennifer E Walter, and Jennifer L Welch. An asynchronous leader election algorithm for dynamic networks. In 2009 IEEE International Symposium on Parallel & Distributed Processing, pages 1–12. IEEE, 2009.
[29] Leslie Lamport. Lower bounds for asynchronous consensus. Distributed Computing, 19:104–125, 2006.
[30] Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, pages 382–401, 1982.
[31] Xiao Li, Eric Chan, and Mohsen Lesani. Quorum subsumption for heterogeneous quorum systems. technical report. In International Symposium on Distributed Computing (DISC 2023), 2023.
[32] Xiao Li and Mohsen Lesani. Open heterogeneous quorum systems, 2023. arXiv:2304.02156.
[33] Marta Lokhava, Giuliano Losa, David Mazières, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafał Malinowsky, and Jed McCaleb. Fast and secure global payments with stellar. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 80–96, 2019.
[34] Giuliano Losa, Eli Gafni, and David Mazières. Stellar consensus by instantiation. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
[35] Ethan MacBrough. Cobalt: Bft governance in open networks. arXiv preprint arXiv:1802.07240, 2018.
[36] Dahlia Malkhi, Kartik Nayak, and Ling Ren. Flexible byzantine fault tolerance. In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pages 1041–1053, 2019.
[37] Dahlia Malkhi and Michael Reiter. Byzantine quorum systems. Distributed computing, 11(4):203–213, 1998.
[38] David Mazieres. The stellar consensus protocol: A federated model for internet-level consensus. Stellar Development Foundation, 32:1–45, 2015.
[39] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft protocols. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 31–42, 2016.
[40] Atsuki Momose and Ling Ren. Multi-threshold byzantine fault tolerance. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 1686–1699, 2021.
[41] Achour Mostefaoui, Michel Raynal, Corentin Travers, Stacy Patterson, Divyakant Agrawal, and Amr EL Abbadi. From static distributed systems to dynamic systems. In 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05), pages 109–118. IEEE, 2005.
[42] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. White paper, 2008.
[43] Rafael Pass and Elaine Shi. Thunderella: Blockchains with optimistic instant confirmation. In Advances in Cryptology–EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part II 37, pages 3–33. Springer, 2018.
[44] David Schwartz, Noah Youngs, and Arthur Britto. The ripple protocol consensus algorithm. Ripple Labs Inc White Paper, 5(8):151, 2014.
[45] Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C Myers. Heterogeneous paxos. In OPODIS: International Conference on Principles of Distributed Systems, number 2020 in OPODIS, 2021.
[46] Isaac C Sheff, Robbert van Renesse, and Andrew C Myers. Distributed protocols and heterogeneous trust: Technical report. arXiv preprint arXiv:1412.3136, 2014.
[47] Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, Lau Cheuk Lung, and Paulo Verissimo. Efficient byzantine fault-tolerance. IEEE Transactions on Computers, 62(1):16–30, 2011.
[48] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: BFT consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347–356, 2019.