Minority Corruption Resilience in Byzantine Generals With Unknown and Fluctuating Participation
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”. 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, nr satisfies nr ≥ 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)1. 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.
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.