@keep-network/sortition-pools

= Sortition Pools

Sortition pool is a logarithmic data structure used to store the pool of eligible operators weighted by their stakes. In the Keep network the stake consists of staked KEEP tokens. It allows to select a group of operators based on the provided pseudo-random seed.

Each privileged application has its own sortition pool and is responsible for maintaining operator weights up-to-date.

A sortition pool provides instant selection results and is less affected by censorship that the ticket selection, although malicious miners can still censor protocol result submissions. Additionally, miners and other actors that can predict the selection seed (due to frontrunning the beacon or a public cached seed being used) may be able to manipulate selection outcomes to some degree by selectively updating the pool. To mitigate this, application using sortition pool should lock sortition pool state before seed used for the new selection is known and should unlock the pool once the selection process is over, keeping in mind potential timeouts and result challenges.

== Optimized higher arity trees

Even though logarithmic data structures are well-known, the particular characteristics of Ethereum smart contracts require specialized optimization to make non-interactive sortition viable.

To enable weighted sortition, each sortition pool would have a weighted tree where each leaf stores an operator and is labeled with the operator's sortition weight, and each branch is labeled with the sum of the weights of its children. To select an operator from the pool, a pseudorandom number in [0, W) (where W is the total sortition weight of the tree) is acquired and used to index into the tree.

A single storage field in the EVM consists of 256 bits/32 bytes. Data structures on the EVM are naturally sparse. An implicit heap can eliminate the need for pointers so the full capacity of each storage field can be used for content data.

KEEP tokens have 18 decimals and the total supply is 1,000,000,000 KEEP. A precise token amount would require roughly 96 bits/12 bytes to store. However, the minimum stake required to participate is expected to be in the region of 1,000~100,000 KEEP.

Instead of using the exact token amount, each operator's sortition weight should use their staker weight as in the Random Beacon group selection. 32 bits is sufficient for all practical purposes.

A storage field can hold 8 values of 32 bits. This gives a theoretical ceiling of 4 billion possible virtual stakers without concern for the exact distribution of weights.

The actual sortition tree has 8 levels, including root and leaves, with the following number of nodes on each level:

• root: 1
• level 2: 8
• level 3: 64
• level 4: 512
• level 5: 4ki
• level 6: 32ki
• level 7: 256ki
• leaves: 2Mi

This means that we can store up to 2 mibioperators (a bit over 2 million) in the sortition tree. If the minimum stake is at least TOKEN_SUPPLY / 2**21, the pool will always be able to accommodate all possible operators.