README.md
1 # alphavm-ledger-committee 2 3 [](https://crates.io/crates/alphavm-ledger-committee) 4 [](https://alpha.org) 5 [](./LICENSE.md) 6 7 The `alphavm-ledger-committee` crate provides 8 a data structure and operations for committees. 9 10 A _committee_ is a set of validators, each with attributes like stake. 11 The `Committee` struct in this crate represents a committee. 12 13 At any point in time, 14 a committee is in charge of running the consensus protocol, 15 i.e. generating and endorsing proposals, 16 assembling and exchanging certificates, 17 and so on. 18 Initially, a known _genesis committee_ is in charge. 19 The committee changes dynamically, based on 20 _bonding_ and _unbonding_ transactions: 21 the former add validators to the committee, 22 while the latter remove them. 23 The committee could potentially change at every block, 24 i.e. every two rounds, since there could be a block every two rounds. 25 26 Each validator has its own view of 27 the committee in charge at every round, 28 based on its local copy of the blockchain. 29 Since the protocol guarantees agreement on the blockchain, 30 validators agree on which committee is in charge at which round. 31 32 There are two distinct notions of committee associated to a round: 33 - The _bonded committee_ at round $r$ is 34 the committee resulting from all the bonding and unbonding transactions 35 in all the blocks strictly before round $r$, 36 starting with the genesis committee. 37 - The _active committee_ at round $r$ is 38 the bonded committee at round $r - \ell$ if $r > \ell$, 39 where $\ell$ is the _lookback distance_, 40 or the genesis committee if $r \leq \ell$. 41 This is the committee in charge of running consensus at round $r$, 42 i.e. the committee that is "active" at that round. 43 44 If the latest block in the blockchain has round $R$, 45 the bonded committee 46 is known for all rounds $r$ such that $1 \leq r \leq R+2$, 47 but not yet for rounds $r \geq R+3$, 48 because there could be a new block at round $R+2$ 49 that affects the bonded committee at round $R+3$. 50 The bonded committee at rounds 1 and 2 is always the genesis committee. 51 The bonded committee at rounds 3 and 4 could be different, 52 if there is a block at round 2 53 and that block contains bonding or unbonding transactions; 54 otherwise, it is still the genesis committee. 55 The same pattern applies to subsequent rounds and committees. 56 Each pair of contiguous odd-even rounds always has the same bonded committee, 57 which may only change between an even and the subsequent odd round. 58 59 While it may seem natural for the bonded committee at round $r$ 60 to be in charge of round $r$, 61 a validator is often unable to calculate that committee, 62 when the validator is running consensus for round $r$. 63 For instance, if $r$ is odd, certificates at round $r$ are needed 64 to determine whether a block is generated for even round $r-1$ or not. 65 66 This problem is solved via a _lookback_ approach: 67 the active, not bonded, committee at round $r$ is in charge of round $r$. 68 The rationale is that, with a sufficiently large value of $\ell$, 69 all validators should have enough blocks to calculate that committee. 70 The value $\ell$ is the constant `Committee::LOOKBACK_DISTANCE` in the code. 71 The lookback distance $\ell$ is the delay with which 72 bonding and unbonding validators actually join and leave consensus. 73 74 The following diagram provides an example of bonded and active committees, 75 with a much smaller lookback distance than normal to keep the diagram small: 76  77 78 The _total stake_ $N$ of a committee is 79 the sum of the stakes of all its members. 80 This generalizes the total count of validators in typical BFT systems. 81 82 The _maximum faulty stake_ $f$ of a committee is 83 the maximum sum of the stakes of the faulty members in the committee 84 that the protocol can tolerate 85 and still ensure consensus among correct validators. 86 It is defined as the largest integer $f < N/3$, 87 where $/$ is exact (rational) division. 88 (Alternative equivalent definitions are 89 $f = \lceil N/3 \rceil - 1$ and $f = \lfloor (N-1)/3 \rfloor$.) 90 This generalizes the maximum count of faulty validators in typical BFT systems. 91 92 The _availability stake_ of a committee is defined as $f + 1$. 93 94 The _quorum stake_ of a committee is defined as $N - f$.