Authored by Dahlia Malkhi, Atsuki Momose, and Ling Ren

Synopsis

Recently, Momose-Ren showed a Byzantine consensus solution under dynamic and unknown participation assuming minority corruption. However, it does not fully support fluctuation. Specifically, the protocol makes progress only when the participation is “stable”. Our previous post removes this assumption but our previous solution tolerates only ⅓ corruption. This post shows how to remove this assumption and achieve the optimal ½ corruption threshold.

Since we already know how to solve full consensus given a solution to Graded Agreement (GA), we focus on GA in this post. We solve GA with minority corruption via a simple modification to the GA solution in Momose-Ren. 

Recap: Problem Model

We solve an abstraction called Graded Agreement (GA) for minority corruption in a setting known as the “sleepy” model of Pass and Shi [2016], which has unknown and fluctuating participation. 

For ease of exposition, we will think of time as divided into discrete “rounds”. In reality, the model can be defined with and our solution can be extended to continuous time.

The set of active participants—also called nodes—is unknown, their count is unknown, and in each round, they may be replaced entirely, subject to the following assumptions:

• PKI. Participating nodes are taken from a finite universe, each can be identified by a public key for which it owns the private key.
• Faulty nodes. The adversary can corrupt up to f nodes, causing them to suffer Byzantine failures.
• Active nodes. Each round r has an unknown set of active nodes, whose (unknown) count, n_r satisfies n_r ≥ 2f + 1.
• Synchronous communication. In round r, honest and active nodes receive all the messages broadcast by honest nodes in round r-1.

Graded Agreement (GA). In the Graded-Agreement problem, a group of active nodes initially holds input values ∈ {0,1} (a bit)¹. At the end of GA, a group of active nodes output (b, g) such that the following properties hold:  

• Graded consistency. If an honest node outputs (b, 1), then all honest nodes output (b, *).
• Integrity. If an honest node outputs (b, *), then at least one honest node inputs b.
  
• Validity. If all honest nodes input b, then all honest nodes output (b, 1).
• Uniqueness. If an honest node outputs (b, 1), then no other honest node outputs (b’, 1) where b’ ≠ b.

In the context of unknown and dynamic participation, the set of active nodes at the beginning of GA may be different from the set of active nodes at the end of the GA.

Note that the GA definition in Momose-Ren does not require the outputs (with either grade) to be unique or have a bounded divergence. We require uniques to simplify embedding GA in Byzantine consensus solutions.

¹_{Extending to non-binary GA is not hard; it is omitted for brevity of exposition.}

Graded Agreement Solution

Throughout the protocol, an awake node at the beginning of round r+1 echoes all the messages it received from round r.

Our GA is constructed in three rounds: 

Round-1. At the start of round 1, an awake node broadcasts its input b in a message “input, b”.

Round-2. At the start of round 2, an awake node broadcasts “tally, b, y” where y is the # of “input, b” messages by unique senders it has received at the end of round 1.

Round-3. At the start of round 3, an awake node broadcasts “vote, b” if the # of “input, b” it has received at the end of round 2 is more than half of unique input senders. 

At the end of round 3, an awake node observes the following parameters:

• E = # of unique senders of “input, *” messages.
• For all b, M(b) = the median of values y in “tally, b, y” by unique senders.
• V = # of unique senders of “vote, *” messages.
  

A node generates the following output, for all b:

• If # of “vote, b” is greater than V/2, then output (b, 0).
• If M(b) > E/2, and did not output (b’, 0) with b’ ≠ b, then output (b, 1).

Intuition

Our solution is built on Momose-Ren’s time-shifted quorum technique but uses a new technique (the highlighted parts) to remove the stable participation requirement. 

More specifically, the Momose-Ren’s time-shifted quorum works as follows. A node in round 2 remembers the # of “input, b” (y in ours), which is then compared with the # of senders of “input, *” at the end of round 3 (E in ours). Since all “input, *” messages are forwarded, if y > E/2 holds (to output (b, 1)), then an awake node at the beginning of round 3 must observe majority “input, b” and vote for b, making everybody output (b, 0). 

The key insight is that a node only needs to know that some honest node had tallied y “input, b” in round 2 to guarantee forwarding y “input, b” messages, it does not need to remember its own tally y in round 2. To get an honest y, we use a median of y’s reported in round 2. This way, we can get a robust estimation of honest node’s y even in the presence of malicious nodes reporting too high/low y, and the time-shifted quorum argument still holds. 

Correctness (Sketch)

Graded consistency: If an honest node outputs (b, 1), then all honest nodes awake at the end of round 3 output (b, 0).

Suppose an honest node p outputs (b, 1). We denote the following:

• E[p], M[p](b) – values of E, M(b) that p has at the end of round 3.

We have that M[p](b) > E[p] / 2.

There exists an honest sender t in T[p] whose “tally b, y[t](b)” has y[t](b) ≥ M[p](b). This is because M[p](b) is the median of all echoed tallies v, each sender has at most one tally counted, and we have an honest majority.

Choose an honest node v awake in round 2. Node v has received at least y[t](b) “input, b” messages in round 2. This is because t is honest, and everything it sends is received by v. Assume to the contrary there is no “vote b” by v. Then v has “input, *” entries from at least 2*y[t](b) senders. Since v echoes all these inputs, they are received by p at the end of round 3. We have E[p] ≥ 2*y[t](b) ≥ 2*M[p](b), in contradiction to y[t](b) ≥ M[p](b) > E[p] / 2. 

Therefore, for all awake nodes v in round 2, v votes b. Hence, each awake node at the end of round 3 must receive majority votes for b and output (b, 0).

Validity: If all honest nodes have the same input b, then all honest nodes awake at the end of round 3 output (b, 1).

Since all honest nodes send “input, b”, the tally y[t](b) of each honest node t is greater than half of the senders of “input, *”. 

Take an honest node p. Using the same notation as above, there exists an honest sender t in T[p] whose tally y[t](b) is not greater than M[p](b). We have M[p](b) ≥ y[t](b) > E[p] / 2, hence p outputs (b,1). 

Integrity: If an honest node outputs (b, *), then at least an honest node awake at the first round inputs b.

At the end of round 3, an output (b,*) by node p requires observing “input, b” messages from more than E[p] / 2 senders in an honest vote or in an honest tally. Since p must receive inputs from all honest senders, at least one sender of “input, b” is honest.