[Instant Finality in Byzantine Generals With Unknown and Dynamic Participation](https://blog.chain.link/instant-finality-in-byzantine-generals-with-unknown-and-dynamic-participation/) Simple solution for Byzantine Generals problem with unknown and dynamic participation - Unconditional safety guarantees [[sleepy model]] borrows 2 core pillars from permissionless setting: 1. Continuity - require synchronous message propagation among currently active participants 2. At any moment, there is an *unknown and dynamic* set of active and synchronously connected parties with honest majority Sleepy consensus solves Byzantine agreement, but inherits the probabilistic safety and high latency from longest-chain protocols By bringing participation up from 51% to 2/3 honest, a solution for Byzantine agreement in unknown and dynamic participation becomes evident Deterministic and unconditional safety guarantees, a small constant expected latency #### Unknown and Dynamic Participation Model Time divided into rounds Strong synchrony assumption: known upper bound on channel propagation delays among every pair of honest participants *Synchronous communication:* if an honest node p sends a message in round r, then every honest node q that's active in round r+1 receives the message *Honest participation:* In each round, unknown number of active participants with 2/3+ being honest **Byzantine Agreement Problem:** In binary variant, a group of participants initially hold a value of 0 or 1 and come to an agreement on the output satisfying: - Safety: output of two honest parties is the same - Validity: If all honest parties start with the same input value, the output is that value - Liveness: Eventually all honest parties output a value #### Binary Agreement **Unknown and Dynamic Quorum property (UDQ):** Each node receives in round (r+1) a set of messages sent during round r. We observe the following key facts: - Denote the unknown number of messages received by an honest node in round (r+1) by R. We have R <= $n_r$ (total active nodes in round) - Due to synchrony, among the R messages, at least 2/3 $n_r$ >= 2/3 R messages are received from honest round-r nodes (at least 2/3 of the messages are from honest nodes) - An unknown number $t_r$ <= 1/3 R messages out of R are from faulty round-r nodes (less than 1/3 of total messages) Assume protocol messages carry a single value each. The following guarantees hold: **UDQ-unique:** If node p receives a supermajority of messages carrying value b, and q receives supermajority carrying value b', then b=b'. **UDQ-valid:** If an honest node receives in round (r+1) more than one-third of round-r messages carrying b, then some honest node has sent a message carrying B. **UDQ-graded-agreement:** If an honest node p receives in round r+1 a supermajority of round r messages containing a value b, then more than a third of round-r messages received by another honest node in round (r+1) contain b. Now we can construct in two broadcast steps a single-shot binary agreement protocol. - Starts with round where nodes advertise inputs - Then alternates between collection-GA rounds and decision-GA rounds - In a round, active nodes listen to incoming messages broadcast in the previous round, process them, then broadcast a message **Round 0 - initialization** A node broadcasts to all nodes (0, collect, input) **Collection-GA r+1** (GA = graded agreement) Let S-collect be the set of received messages (r, collect,\*) A node broadcasts to all nodes: - (r+1, propose, b) if more than two-third of S-collect are (r,collect,b) - (r+1,propose,"empty") otherwise Simultaneously, a node broadcasts to all nodes: - (r+1, VRF,c) where c is a random bit **Decision-GA r+2** - Let S-propose be the set of received messages (r+1, propose, \*) - A node p processes S-propose as follows: - Decide b: If more than two-thirds of S-propose are (r+1,propose, b) - Adopt vp <- b: If more than one-third of S-propose are (r+1, propose, b) - Adopt vp <- value v in (r+1, VRF,v) with the highest VRF: otherwise - A node p broadcasts to all nodes (r+2, collect, vp) In collection-GA rounds, nodes collect messages containing other nodes' adopted values. At the end of these rounds, if a node receives more than two-thirds (collect, b) for some value b, then it broadcasts (propose, b). Otherwise, it broadcasts (propose, "empty") Simultaneously, a node broadcasts (VRF,c) where VRF is a unique pseudo-random value and is verifiably using the node's public key and the round number, and c is a local coin toss. Note: at the very first round of execution, nodes send collect-messages with their own input In decision-GA rounds, nodes collect (propose, \*). Every node that receives more than two-thirds (propose, b) messages **decides** b Every node that receives more than one-third (propose, b) adopts v as its current value. Other nodes adopt the random value b' in a message (VRF, b') whose VRG value is the highest among all VRFs they receive. At the end of this round, every node p broadcasts (collect, vp) carrying its adopted value. ##### Correctness Claims Claim-1 (Unique-adopt): In decision-GAs, at most one value b may be forced to be adopted. In order to be adopted, a value has to be received by more than one-third of a preceding collection-GA's messages. By UDQ-valid, it is sent by one honest sender. However, by UDQ-unique, at most one value b may be broadcast by honest nodes in a collection-GA. Claim-2 (Safety): If an honest node decides b in a decision, then by UDQ-GA, every other honest node receives more than one-third of a preceding collection-GA's messages carrying (propose, b). By unique-adopt, only b may be forced to be adopted. Hence, every honest party adopts b in decision-GA. Claim-3 (Termination): If no decision is made, then by UDQ-adopt at most one value b may be forced to be adopted. b will have a 1/2 probability of being adopted because of a winning VRF value.