[Instant Finality Under Unknown/Dynamic Participation](https://blog.chain.link/instant-finality-in-byzantine-atomic-broadcast-under-unknown-dynamic-participation/) Sequel to [[Instant Finality in Byzantine Generals Under Unknown or Dynamic Participation]] Extends this approach to multi-valued consensus on a sequence of values - the Byzantine atomic broadcast (BAB) problem This solution has 3-round latency, deterministic and unconditional safety, does not require eventual stable participation, and allows fluctuating participation of faulty nodes. ### Protocol Block B' extends a block B if the sequencing ending in B is a prefix of the sequence ending in B'. If two blocks don't extend one another, they are *conflicting* **Graded Agreement:** An abstraction implemented in each communication step. In the context of unknown and dynamic participation, the set of active nodes at the beginning of this one-round (GA) may be different from the set of active nodes at the end of the GA (active nodes in next round). Every active node at the beginning of the GA has an input block B. Every (newly) active node at the end of the GA determines a set { (B,g) } of pairs of block B and grade bit g as an output of GA. ##### GA Protocol At the beginning of the GA, every active node p sends (vote, B) for its input B. (the set of active nodes may not be replaced, a different set of nodes could receive and tally votes) At the end of the GA, every active node tallies votes. If B' extends B, then a vote for B' also counts as a vote for B. Votes for conflicting blocks from the same voter are ignored. - Outputs (B,1) if over 2/3 of the received votes vote for B - Outputs (B,0) if over 1/3 of the received votes vote for B **Properties of Graded Agreement** (from UDQ) - 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' that extends B. - Validity: Let B be the highest common ancestor of honest nodes' inputs. Then, all honest nodes output (B,1) - Uniqueness: If an honest node outputs (B,1) and another honest node outputs (B',1), then B and B' don't conflict with each other - Bounded divergence: Each node outputs (with grade 0) at most two conflicting blocks **Atomic Broadcast Protocol** C = candidate, L = lock, and they're initialized to genesis A view is a time when nodes propose and vote on blocks and consists of a complete cycle of two rounds of communication Each view has two rounds. There is an extra round before the first view v=1 starts. There are two graded commitments per view *Initial round 0:* Send (propose, B, VRF) where B is a block that extends the genesis *Round 1 of view v:* If v > 1: Decide any block B such that GA2 of view v-1 outputs (B, 1) Meaning B has received more than two-thirds of votes in previous round Set **L** to the highest block such that GA2 of view v-1 outputs (L,\*) Block commitment Input to GA1 a block with the highest VRF among "propose" messages from the previous round that extend L In other words, input to the first Graded Agreement a block with the highest VRF value from the proposals in the previous round that extend L. If there is no such block, input L to GA1. *Round 2 of view v:* Set B to the highest block such that GA1 outputs (B,1) Block received over two-thirds of votes Set C to a highest block such that GA1 outputs (C,\*) Candidate is a potential block to add to the chain. If there are two, node picks one at random Input B to GA2 Send (propose, B', VRF) where B' extends C. B' extends their current candidate C The process repeats for each subsequent view, with the nodes updating their locks and candidates and voting on new blocks. ##### Proof Sketch **Safety:** Supposed an honest active node decides on B in round 1 of view v, meaning it outputs (B,1) from GA2 that was started in view v-1. Due to graded consistency, any honest node p active in round 1 of view v must output (B,\*). Also, observe that GA2 of view v-1 could not have outputted any conflicting block, because not honest node could have input any conflicting block to GA2 of view v-1, because of uniqueness of GA1, and GA2 could not have output any conflicting block without some honest node's input (due to integrity). So p must have set L to a block extending B in round 1 of view v. Both GAs in view v, and inductively in all views after v, output only blocks extending B (due to validity). So no honest node decides any conflicting block. **Liveness:** Call the node who sent the highest VRF (highest output value from a random function) in view v-1 the leader of view V. If all honest active nodes input an honest leader's proposal to GA1 of view v, the proposed block must be decided. The only reason an honest node wouldn't input the leader's proposal to GA1 is it conflicts with its lock L. Node p must have output (L, \*) from the GA2 that started in the previous view v-1. Then, some honest node q must have input L (or a block extending L) to GA2 after outputting (L, 1) in GA1 of view v-1. Thus, the leader of view v outputs (L,0) in GA1 of view v-1 (due to graded consistency). Due to bounded divergence, the leader outputs at most one other conflicting block from GA1 of view v-1. Therefore, with probability at least 1/2, the leader proposes a block extending L and all honest nodes accept the leader's proposal. Another way to put it is that the only reason an honest node does not input the leader's proposal to GA1 is that it conflicts with its lock L. In this case, with a probability of at least 1/2, the leader proposes a block extending L and all honest nodes accept the leader's proposal.