-
Each privileged customer has its own sortition pool and eligibility is checked when an operator is selected, rejecting and removing ineligible operators from the pool
-
Non-interactive sortition requires significant optimization even with logarithmic data structures, but once optimized is easily scalable for larger n
-
Requires significant implementation work
-
Provides instant results once the seed is received and is less affected by censorship, although malicious miners can still censor DKG result submissions
A logarithmic data structure could be used to store the pool of eligible operators, weighted by their stakes. Sortition from the pool would be performed without waiting for input from operators.
Each pair of (keep factory, privileged customer) would require its own sortition pool. An operator enters a sortition pool by opting in. The pool checks their eligible tokens (including operator status and authorization to slash stakes), and available bonding currency (including authorization to seize bonds). The operator pays the transaction fees for the pool update.
Keeping these pools up to date cannot be done eagerly as proliferation of privileged customers could be used to perform DOS attacks by increasing the cost of such updates. When a sortition pool prospectively selects an operator, the selected operator’s eligibility status and weight are checked and, if necessary, updated in the sortition pool. If the changes would be detrimental to the operator, the operator selection is performed again with the updated input to ensure correctness.
The number of operator selections required to get n valid members averages n / (1 - e) where e equals the fraction of weight in the pool belonging to operators whose information is detrimentally out of date. If 50% of the pool weight is outdated, the average number of selections is 6, roughly 2% of ECDSA keeps would require 12 or more operator selections, and more than 20 selections would be extremely rare. Sortition pools that are used more often would be less outdated.
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/100,000 of the total KEEP supply.
Instead of using the exact token amount, each operator’s sortition weight should use their staker weight as in the Random Beacon group selection. Because a staker weight exceeding 65,535 would represent catastrophic centralization in the network, 16 bits is sufficient for all practical purposes even if the minimum stake is somewhat less than 10,000 KEEP.
A storage field can hold 16 values of 16 bits. This gives a theoretical ceiling of 1,048,560 possible virtual stakers for a node containing the weights of its 16 children. With a pessimal distribution of child nodes' weights, 524,288 virtual stakers can be accommodated. The maximum permitted staker weight of 65,535 represents approximately 13% of all tokens in the pessimal distribution. Assuming each staker divides their staked tokens equally between two different operators as recommended for smooth upgrades, a single actor following best practices would need to hold 25% of all KEEP to be affected by the staker weight cap of 16 bits. Such an actor would already be a threat to the Keep network and we have no need to accommodate them, so all child nodes can be capped to 16 bits without issues.
If the tree is instead packed optimally using uint16,
we get the following numbers of nodes per level:
-
1
-
16
-
256
-
4,096
-
65,536
-
1,048,576
A 16-ary tree of height 6 is sufficient to hold all possible operators within the limits of the pessimal distribution of 16-bit weights. Updating a path in this tree would only use up to 30,000 gas, and accessing a node would cost at most 4,800 gas.
The minimum stake must be at least 1,910 KEEP.
A branch node consists of {uint16[16] children}
where each field is the weight of its corresponding child.
A weight of 0 means the child node is empty.
A leaf node consists of {uint16 weight; address operator}.
To help insert operators into the tree, there should be lists for levels 2 to 5 (version A) containing the branches with empty children on that level.
Inserting a new operator into the tree is performed in the leftmost empty node of the appropriate level whose level 2 ancestor’s weight would not overflow from the addition of the new operator. The weights of the node’s ancestors are updated, and if the parent node’s children are now full it is removed from the list of branches with empty children.
The total weight of the tree W can either be stored separately or calculated by summing the weights of the root’s children.
An entry V is requested from the Random Beacon,
and an index i in the range [0, W) is derived from V
using a standard algorithm for secure integers in an arbitrary interval.
Using i = V % W is not safe and will lead to biasing the results,
summoning demons from hell,
and embarrassing the entire company on Twitter and Hacker News.
At a branch node, if i is less than the first child’s weight w1 the first child is entered; otherwise i -= w1 and is compared to the second child’s weight w2 and so on until a leaf is reached.
The address P in the leaf is the prospective selected operator, with weight wP.
The staking contract is queried to get the eligible stake of P, and the up-to-date weight W'P is calculated.
If W'P = WP, the weight is up to date and we proceed.
If W'P > WP, something funny is going on because the current spec doesn’t include increasing the staked tokens of an operator after the operator has been created but if this is the future and we’re doing that now we proceed but also queue the weight for updating.
If W'P < WP, we queue the weight for updating and because the update would be in a direction detrimental to the operator, we also queue a new operator selection with the same i once we’re done with the update. If W'P == 0, the operator P is queued for deletion and we don’t bother querying the bond.
Then we query the bonding contract to get the available bond BP and compare it to the minimum bond B:
If BP < B, we queue the operator for deletion and queue a new selection with i after P is deleted from the sortition pool.
If BP >= B and we previously queued a new selection, we perform the queued update and selection.
If B =< BP < 2B and we previously proceeded, the operator P is selected but they don’t have enough bond to stay eligible so P is deleted from the sortition pool.
If BP >= 2B and we previously proceeded, the operator P is selected and they have enough bond to stay in the pool. We then perform queued updates, if any.