Hierarchical Consensus: Scalability Through Optimism and Weak Liveness

A reliable broadcast protocol is an agreement protocol where a special participant, called the leader, disseminates a value amongst the participating agents. Formally, a protocol $𝒫$ with participating agents $𝒜$, a known set of valid decision values $𝒱$, a leader agent $a_L\in 𝒜$, and a leader input value $v_L\in 𝒱$ is a reliable broadcast protocol if and only if the following properties hold:

• $\mathrm{■}$

  Safety:

  • –

    Consistency: If two honest agents $a$ and $a^{\prime }$ output values $v$ and $v^{\prime }$, respectively, then $v=v^{\prime }$.

  • –

    Integrity: If the leader is honest, an honest agent cannot output $v$ such that $v\ne v_L$.

• $\mathrm{■}$

  Liveness:

  • –

    Validity: If the leader is honest, an honest agent eventually outputs a value.

  • –

    Totality: If an honest agent outputs a value, all honest agents eventually output a value.

Note that this protocol is consistent, as any agreement protocol must be.

We will use consensus as a sub-protocol in our constructions. A consensus protocol is an agreement protocol where agents must eventually output a single agreed-upon value. Formally, a protocol $𝒫$ with participating agents $𝒜$, a chosen set of valid decision values $𝒱$, and where each agent $a_i\in 𝒜$ has an input value $v_i\in 𝒱$ is a consensus protocol if and only if the following properties hold:

• $\mathrm{■}$

  Safety:

  • –

    Consistency: If two honest agents $a$ and $a^{\prime }$ output values $v$ and $v^{\prime }$, respectively, then $v=v^{\prime }$.

  • –

    Weak Validity: If all agents are honest and have the same input value $v$, then they can only output $v$.

• $\mathrm{■}$

  Liveness:

  • –

    Termination: All honest agents eventually output a value.

In this work, we demonstrate how to use a hierarchical architecture to efficiently achieve consensus. Our techniques should be easily generalisable to a wide range of agreement protocols, but for simplicity and presentation purposes, we chose to focus on this weak version of consensus, as it is a versatile building block for other distributed applications and particularly state-machine replication.

A protocol $𝒫$ is said to be $t$-resilient if it can tolerate up to $t$ Byzantine faults, that is, in the presence of up to $t$ Byzantine agents, the protocol can still satisfy its prescribed properties; $t$ can also be seen as a fault threshold for the protocol. In this paper, we make use of the notion of multi-threshold protocols to take advantage of our hierarchical consensus architecture. Multi-threshold protocols have been first investigated by Blum et al. [2, 3, 4] and more comprehensively studied by Momose and Ren [22]. A multi-threshold protocol $𝒫$ has two fault thresholds $t_{\text{safe}}$ and $t_{\text{live}}$ such that, given a categorisation of its properties into Safety and Liveness, it must be the case that:

• $\mathrm{■}$

  $𝒫$ satisfies at least its Safety properties in the presence of at most $t_{\text{safe}}$ faults;

• $\mathrm{■}$

  $𝒫$ satisfies both its Safety and Liveness properties in the presence of at most $t_{\text{live}}$ faults.

Note that this definition implies that $t_{\text{safe}}\ge t_{\text{live}}$.

Momose and Ren [22] consider the resilience of the same protocol when executed in a synchronous network (with thresholds $t_{\text{safe}}^s$ and $t_{\text{live}}^s$) or a partially synchronous network (with thresholds $t_{\text{safe}}^a$ and $t_{\text{live}}^a$). They try to establish relations involving these four thresholds. In this paper, however, we only analyse (and use thresholds related to) partially synchronous protocols.

The usual theorems for Byzantine fault tolerance can be extended to multi-threshold protocols, with the main result being that partially synchronous multi-threshold agreement protocols require [22], even when assuming the existence of digital signatures and a PKI.

The outputs of publicly verifiable protocols are endowed with verifiability, namely, outputs are intrinsically supported by a publicly verifiable proof. Given a predefined and protocol-specific publicly verifiable predicate $\text{Verify}(\pi ,v)$ that checks whether $\pi$ is a valid proof for output value $v$, output verifiability means that an honest agent outputs $v$ if and only if it has a proof $\pi$ such that $\text{Verify}(\pi ,v)$ holds. A consequence of this definition is that the reception of a proof by an honest agent is equivalent to outputting the associated supported value. So, verifiability can be used to achieve a sort of totality by relying on the propagation of a proof.

For instance, a publicly verifiable reliable broadcast protocol is defined as being an RBC protocol which has a publicly verifiable function $\text{Verify}(\pi ,v)$, and, in addition to its Safety and Liveness properties, the following Verifiability property:

• $\mathrm{■}$

  Verifiability: An honest agent $a\in 𝒜$ outputs $v\in 𝒱$ if and only if it has a proof $\pi$ such that $\text{Verify}(\pi ,v)$.

The equivalence of outputting and obtaining a proof for a value arising from output verifiability in combination with the consistency property prevents honest agents from obtaining proofs supporting two different values for the same execution. These proofs allow third parties who do not take part in the protocol to validate its output: inconsistent proofs cannot be produced even by Byzantine agents. Verifiability is more of a structural property of the protocol as opposed to a safety property, but we place it in the Safety category for convenience as we expect it to be required for both failure thresholds $t_{\text{safe}}$ and $t_{\text{live}}$. A publicly verifiable reliable broadcast protocol must respect the following inequality [22], which also implies in our case.

We present two impossibility results that together show that Justifiability is a fundamental concept for handover protocols. First, we present a claim (that is more formally stated as Theorem 9 in Appendix A) that states that for any protocol $P$ that can be used as a primary in a handover, $P$ must satisfy some form of Justifiability.

Furthermore, Justifiability adds a weak liveness requirement even when there are up to $t_{\text{safe}}$ faults if compared to RBC protocols. Thus, an argument similar to the one demonstrating that a RBC protocol must satisfy [22] can be applied to show that a JRBC protocol must satisfy . As $t_{\text{safe}}\ge t_{\text{live}}$, the latter relation is strictly more restrictive than the former.

The proof is essentially the same as in [22], except that one of the executions that is required to be live with $t_{\text{live}}$ faults is replaced with an execution that is weakly live with $t_{\text{safe}}$ faults.

We proceed by contradiction. Let us assume that there is a partially synchronous multi-threshold Justifiable RBC protocol $𝒫$ such that $2t_{\text{safe}}+t_{\text{live}}=n$; the following proof can be trivially extended to the case $2t_{\text{safe}}+t_{\text{live}}>n$.

Let $S$, $L_0$ and $L_1$ be sets partitioning the set of agents $𝒜$, such that $|S|=|L_0|=t_{\text{safe}}$, $|L_1|=t_{\text{live}}$ and the sender $a_L$ is in $S$. Let $E$, $E_0$ and $E_1$ be three executions as follows.

In $E_0$, agents in $L_0$ crashed and do not send any message, the remaining agents behave honestly, and $a_L$ has input $v_0$. By weak liveness and $t_{\text{safe}}$ faults, honest agents in $E_0$, including agents in $L_1$, eventually output either an indecision, a pre-decision on $v_0$, or a decision on $v_0$; let $T_0$ be the time when the last honest agent outputs in $E_0$. $E_1$ is the same as $E_0$ but with $L_1$ crashed instead of $L_0$ and $a_L$ input being $v_1$ such that $v_1\ne v_0$. By liveness and $t_{\text{live}}$ faults, honest agents in $E_1$, including agents in $L_0$, eventually output a decision for $v_1$; let $T_1$ be the time when the last honest agent outputs in $E_1$.

In $E$, agents in $S$ are Byzantine while the remaining agents behave correctly. Messages between $L_0$ and $L_1$ are not delivered until $GST=max(T_0,T_1)$, and agents in $S$ behave towards each $L_i$ for $i\in \{0,1\}$ as in $E_{1-i}$, with the same respective network delays. Thus, agents in $L_i$ cannot distinguish between $E_{1-i}$ and $S$ until $GST$, and so they must output as per $E_{1-i}$. So, agents in $L_0$ must output a decision on $v_1$ as per $E_1$, whereas agents in $L_1$ must output either an indecision, a pre-decision on $v_0$, or a decision on $v_0$ as per $E_0$. If an agent in $L_1$ outputs an indecision, we have a violation of Indecision consistency. Similarly, the output of a pre-decision (decision) on $v_0$ by an agent in $L_1$, would violate Pre-decision (Decision, respectively) consistency. Hence, $𝒫$ cannot be a JRBC protocol. $◀$

Our proposed implementation for a partially synchronous JRBC, presented later, shows that this bound is tight. Given this bound, we have that when $t_{\text{safe}}$ goes from $\frac{n}{3}$ to $\frac{n}{2}$, our JRBC protocol is limited to $t_{\text{live}}$ going from $\frac{n}{3}$ to $0$ whereas non-justifiable ones may have $t_{\text{live}}$ going from $\frac{n}{3}$ to $\frac{n}{2}$ (and $t_{\text{safe}}$ go above $\frac{n}{2}$ as well).

The notion of justifiability can also be applied to consensus protocols. Similarly to JRBC, Justifiable consensus protocols would have the three types of outputs (decisions, pre-decision, and indecision), the associated consistency, validity, verifiability, and weak termination notions. Unlike JRBC, it does not have an agent with the role of a leader and the properties associated with this role (e.g., integrity, totality, and termination based on leader honesty).

A Justifiable reliable broadcast can be constructed from a Justifiable consensus protocol in the typical way: the leader value is used to set up the initial values of the agents in the Justifiable consensus, and their consensus outputs become outputs for the Justifiable broadcast protocol construction. So, any impossibility for Justifiable reliable protocols must apply to Justifiable consensus protocols too.

The messages sent between ${𝒜}_o$ and ${𝒜}_l$ flow only from the former to the latter. So, we only need to demonstrate that ${𝒫}^H({𝒫}_l,{𝒫}_o)$ satisfies all the properties of a hierarchical consensus protocol.

• $\mathrm{■}$

  Consistency: ${𝒫}_o$ and ${𝒫}_l$ enforce local consistency, namely, no two agents within these protocols can decide on different values. The definition of ${𝒱}_l$ predicated on the outputs of ${𝒫}_o$ ensures inter-protocol consistency. Let us assume that an agent $a_o\in {𝒜}_o$ outputs a decision on $v^{\prime }$. By the consistency properties of ${𝒫}_o$, it must be that all agents in ${𝒜}_o$ output either a pre-decision or a decision on that value. Hence, the decision set ${𝒱}_l$ for agents in ${𝒜}_l$ can contain only the value $v^{\prime }$. Therefore, ${𝒫}_l$ can only output $v^{\prime }$.

• $\mathrm{■}$

  Weak Validity: If all the agents in ${𝒜}_o$ are honest and have the same input value $v^{\prime }$, if they output a pre-decision or decision, it must be on $v^{\prime }$, by their integrity properties. So, the agents in ${𝒜}_l$ receive from agents in ${𝒜}_l$ enough messages to support $v^{\prime }$ as their initial value or enough indecision so they use their own initial value, which is also $v^{\prime }$. By ${𝒫}_l$ own notion of validity, we have that agents in ${𝒜}_l$ can only output $v^{\prime }$ too.

• $\mathrm{■}$

  Verifiability: Decisions of ${𝒫}^H$ are verifiable by relying on the publicly verifiable functions of the underlying protocols ${𝒫}_o$ and ${𝒫}_l$.

• $\mathrm{■}$

  Termination: If an agent in ${𝒜}_o$ outputs a decision, it will eventually be propagated to all agents in $𝒜$. Otherwise, by weak termination of ${𝒫}_o$, each honest agent in ${𝒜}_l$ is guaranteed to eventually receive either a pre-decision or an indecision (with accompanying proof) from agents in ${𝒜}_o$. Therefore, all honest agents in ${𝒜}_l$ will eventually run ${𝒫}_l$ with some input value. By termination of ${𝒫}_l$, they all eventually output the value from ${𝒫}_l$.

$◀$

Note that we do not use the (strong) liveness property of JRBC to show Termination for ${𝒫}^H$. This property is proven using only JRBC’s weak liveness. On the other hand, JRBC’s Liveness guarantees that when $t_{\text{live}}$ is met, the optimistic protocol will succeed, provided that the timeout is large enough.

To complete the construction of a handover protocol, we propose a partially synchronous JRBC protocol implementation; many well-known consensus protocol implementations exist, of course.

We show that psync-JRBC satisfies all Safety properties of a JRBC protocol for $t_{\text{safe}}\in [0,\lfloor \frac{n-1}{2}\rfloor ]$ and both Safety and Liveness properties for $t_{\text{live}}=\min (\{n-T_p,n-T_d,t_{\text{safe}}\})$.

• $\mathrm{■}$

  Consistency: We prove this by contradiction. So, let us assume that two honest agents output decisions on $v$ and $v^{\prime }$ such that $v\ne v^{\prime }$. For each of these decisions, at least one honest agent must have Commit for each of these values. Let us call them $a$ and $a^{\prime }$ for values $v$ and $v^{\prime }$, respectively. Thus, $a$ and $a^{\prime }$ must have obtained pre-decisions for $v$ and $v^{\prime }$, respectively. However, a pre-decision requires a quorum of $T_p=\lceil \frac{t_{\text{safe}}+n+1}{2}\rceil$ agents, namely, it requires the participation of more than half of the honest agents. Hence, by a quorum intersection argument, it must be that an honest agent has sent a Prepare message for both values $v$ and $v^{\prime }$, which contradicts our algorithm.

• $\mathrm{■}$

  Pre-decision consistency: We can use the pre-decision quorum intersection argument again to show here that two pre-decisions cannot be obtained for two distinct values. We can prove the other case, i.e., that a decision and a pre-decision output by honest agents cannot support different values, using a similar argument. Let us assume that agent $a$ has obtained a pre-decision for $v$ and that agent $a^{\prime }$ has obtained a decision for $v^{\prime }$. The quorum required for a decision must include at least one honest agent; let us call this agent $a^{\ast }$. This agent must have, then, obtained a pre-decision for $v^{\prime }$. That contradicts the fact that two pre-decisions for distinct values cannot be obtained for the same run of the protocol.

• $\mathrm{■}$

  Indecision consistency: We prove this by contradiction. Let us assume that agent $a$ outputs $\perp$ and agent $a^{\prime }$ outputs a decision on $v$. By our algorithm, for $a$ to output $\perp$, it must be that $n-2t_{\text{safe}}$ distinct honest agents have aborted. For the decision on $v$, by our algorithm, there must have been $t_{\text{safe}}+1$ distinct honest agents who have obtained a pre-decision for $v$. There are $T_d+T_a=(n-t_{\text{safe}}+2t_{\text{safe}}+1-n)=t_{\text{safe}}+1$ overlapping agents in the intersection of these two quorums, but an honest agent cannot both abort and possess a pre-decision, a contradiction.

• $\mathrm{■}$

  Decision, Pre-decision, and indecision verifiability: A proof of a decision is a collection of $T_d=2t_{\text{safe}}+1$ Commit messages from distinct agents; a proof of a pre-decision is a set of $T_p=\lceil \frac{t_{\text{safe}}+n+1}{2}\rceil$ Prepare messages from distinct agents; and a proof of indecision is a set of $T_a=n-t_{\text{safe}}$ Abort messages from distinct agents. Given that $t_{\text{live}}\le t_{\text{safe}}$, to satisfy the public verifiability requirement of , it must be that $t_{\text{safe}}\in [0,\lfloor \frac{n-1}{2}\rfloor ]$.

• $\mathrm{■}$

  Integrity: If the leader $a_L$ is honest, honest agents can only send Prepare messages for $v_L$. Given that a pre-decision quorum requires the participation of honest agents, a pre-decision can only be for $v_L$ and, as a consequence, a decision can only be for $v_L$.

• $\mathrm{■}$

  Pre-decision integrity: As per the previous property.

• $\mathrm{■}$

  Weak termination: The timer of honest agents will eventually expire. When that happens, two cases can arise. If an honest agent has obtained a pre-decision, it will propagate this pre-decision, eventually compelling all honest agents to output this pre-decision. If no honest agent has obtained a pre-decision, they will all send abort messages. Given that there are $n-t_{\text{safe}}$ honest agents, they can eventually obtain an abort proof and output $\perp$.

• $\mathrm{■}$

  Termination: Our requirement $t_{\text{live}}=\min (\{n-T_p,n-T_d,t_{\text{safe}}\})$ means that we have enough honest agents to meet the quorum for a pre-decision and a decision. Hence, if the leader is honest and the timer lasts for enough time, the algorithm will converge after $GST$ to a decision on the leader’s input value.

$◀$

The higher fault tolerance for JRBC (i.e. primary) protocols allows them to rely on small committees if compared to typical consensus protocols. In this section, we dive into a probabilistic approach to choose committees to implement (i.e. run) our deterministic protocols. That does not make our protocols stochastic, but that means that our correctness guarantees become probabilistic. We rely on a notion of stochastic reasoning to bound the probability with which correctness may be violated. We use the error parameter $ϵ$ as the upper bound on correctness violation, which should be negligible in the security parameter. In our context, a violation arises if we select a committee with the wrong proportion of honest agents. This error parameter can be understood as the probability with which we will select a committee with the wrong proportion of honest agents.

We select agents for our committees from a population of agents with a probability $p$ of being honest. We rely on a process that selects randomly and independently (with repetition) $n$ agents from this population. The probability that this set has $k$ honest agents is governed by a binomial distribution with parameters $(n,p)$. The probability that this collection has up to $k$ honest agents is equal to the cumulative distribution $F(k;n,p)={\sum }_{i=0}^k\left(\genfrac{}{}{0pt}{}{n}{i}\right)p^i{(1-p)}^{n-i}$. This probability is equivalent to the probability of the collection having at least $n-k$ Byzantine agents, and so the probability that it has at most $n-k-1$ Byzantine agents is $1-F(k;n,p)$. So, by minimising $F(k;n,p)$, we increase the probability that $n-k-1$ bounds the number of Byzantine agents in this collection, and $F(k;n,p)$ can be seen as the probability that $n-k-1$ is not a correct bound. We use $K(n,p,ϵ)=max(\{k\in \{0\mathrm{\dots }n\}\mid F(k;n,p)\le ϵ\})$ to find the $k$, if it exists, that represents the tightest $k+1$ lower bound to the number of honest agents in the committee, respecting the error probability $ϵ$. For a given probability $p$ of agents to be honest, a target maximum number of Byzantine fault $t$ and error threshold $ϵ$, we compute the committee size $n^{ϵ}(p,t)$ as the smallest number, if it exists, that guarantees less than $t$ faults, i.e., $n^{ϵ}(p,t)=\min (\{n\in \mathbb{N}\mid k=K(n,p,ϵ)\wedge n-k-1\le t\})$.

In Table 1, we illustrate how the ability to tolerate more Byzantine agents can lead to smaller committee sizes. We present the values of $n^{ϵ}(p,t)$ for some values of $p$ and $ϵ$ and for failure thresholds $t=\lfloor \frac{n-1}{2}\rfloor$ and $t=\lfloor \frac{n-1}{3}\rfloor$; we choose $0.68$ as a starting value for $p$ because of the need for a $2/3$ ratio of honest agents to implement consensus. These values demonstrate the substantial impact that tolerating more failures can have in the size of the committees being randomly selected. For instance, for $p=0.68$ and $ϵ={10}^{-14}$, a primary protocol would require a committee of size $411$, whereas the secondary protocol would require the participation of $72061$ agents; the secondary committee size would be about $17500\%$ that of the primary. As expected, the discrepancy between committee sizes reduces as the probability of an agent being honest increases.

We examine the communication complexity of handover protocols, i.e. the number of bits sent by honest agents. We note ${𝒞}^P(n)$ the communication cost of protocol $P$ as a function of the number of participating agents. It is straightforward to see that ${𝒞}^{{𝒫}^H}(|𝒜|)={𝒞}^{{𝒫}_o}(|{𝒜}_o|)+{𝒞}^{{𝒫}_l}(|{𝒜}_l|)+O(|{𝒜}_o||{𝒜}_l|)$ in general, and for optimistic executions ${𝒞}^{{𝒫}^H}(|𝒜|)={𝒞}^{{𝒫}_o}(|{𝒜}_o|)+O(|{𝒜}_o||{𝒜}_l|)$. This shows that there are gains to be expected from the optimistic executions, although the handover can, in some situations, incur a cost higher than just running the fallback. More generally, since our technique yields a constant factor improvement in the committee size, we cannot analyse them using asymptotic notation. Depending on the protocols at hand, tail bounds on the binomial distribution (e.g., the Chernoff bound) may be used instead. Increasing $t_{\text{safe}}$ for ${𝒫}_o$ makes $|{𝒜}_o|$ smaller, at the expense of decreasing $t_{\text{live}}$ and therefore the probability of making ${𝒫}_o$ (strongly) live.

We intended to use our hierarchical protocol as a consensus engine for blockchains. In this context, we could set up incentive structures that can be naturally implemented in these distributed systems to encourage optimistic executions. For instance, they could financially reward more favourably these executions against fallback ones. These incentive structures can be used to optimise another aspect of our construction. Note that when $t_{\text{safe}}>t_{\text{live}}$ for ${𝒫}_o$, it only takes a small number of Byzantine agents ($n-2t_{\text{safe}}$) to prevent the primary from reaching a decision. For instance, for $n=2t_{\text{safe}}+1$, it only takes one Byzantine agent (being silent, for example) to prevent ${𝒫}_o$ from being live. Of course, weak liveness still holds for the primary, so the Byzantine agents in ${𝒫}_o$ can delay a ${𝒫}^H$ decision, but they cannot prevent it. Thus, once more, incentive structures can be set up to ensure that delaying a decision is not worthwhile, encouraging, then, the Byzantine agents in ${𝒜}_o$ to cooperate in reaching a ${𝒫}_o$ decision.