Shard persistent committee selection

[vbuterin]

Setup

• There is a function get_period_committee(shard, period) -> List[ValidatorIndex] which returns the period persistent committee for a shard (1 period = PERIOD_LENGTH slots ~= 9 days)
• Every validator has a private "switchover block", 0 <= x_i < PERIOD_LENGTH. A validator switches over from their period-n responsibility to their period-(n+1) responsibility at slot n * PERIOD_LENGTH + x_i. This staggered transition mechanism facilitates smooth transitions between committees, so only a few validators enter or leave at a time.
• Hence, the validators active at any given slot s in any given shard are a combination of some members of some committees prev_committee and post_committee.

Question: how to choose (i) the proposer and (ii) the attester committee for slot s?

A quick note on light clients and committee sizes

A crosslink committee has size ~4096 in the worst case, ~915 in the 30 million ETH case, ~305 in the 10 million ETH case. A validator record is ~56 bytes, and a period is 2048 384-second epochs or ~9 days. A light client can just download the record for the entire persistent committee every period, achieving a worst-case data overhead of 56 * 4096 / (308 * 2048) ~= 0.2917 bytes per second, plus extra overhead for verifying specific blocks (by comparison, Bitcoin block headers are about 80 / 565 = 0.142 bytes per second).

But we don't want the entire committee validating every block because that would be inefficient, and we can tolerate occasional faults because the crosslink committee would reject them anyway. Instead, we can try to target ~64 persistent committee validators validating any given block.

But if we do this, then we have smaller signatures, and we can try to enable the possibility of light clients that are even lighter, downloading only the first ~64 members of a persistent committee and in exchange only being able to verify shard blocks once in a while. This could be an optimal arrangement for light clients inside highly constrained environments. Such a light client would have a data overhead of 56 * 64 / (308 * 2048) = 0.00568 bytes per second or 490 bytes per day. This is what we mean by "ultra-light client".

Choosing the attester committee

Option 1: status quo

Let N = max(len(prev_committee), len(post_committee)) // 64. Split prev_committee and post_committee both into N pieces. Combine the (s % N)'th piece of the active portions of each committee, to get the attesters.

Pros:

• Is status quo
• Not too complex
• Light clients can download 1/N of each committee and still keep up with the shard chain, but with N-slot latency (this is optimal)

Cons:

• Attester set size not exactly fixed
• Attester sets fully predictable
• Validation responsibility evenly spread across slots; higher efficiency would be assigning longer contiguous slices (that is, a validator validates .....*.....*.....*.....*.....)

Option 2: status quo but attester sets are per-epoch, not per-slot

Pros: validation responsibility compressed into contiguous ranges of slots (that is, a validator validates ..........***...............***.........)

Cons:

• The entire attester sub-committee changes at the same time
• Attester sets fully predictable
• Ultra-light-client latency goes up to N epochs

Option 3: fractional staggering

Let ROTATION_PERIOD = 1024 slots. A validator with index i in either committee (with L being the total length of that committee) is an active attester for slot s if (i + L - x) % L <= 64 where x = ((s * L) // ROTATION_PERIOD) % L.

Pros: same as option 2, but smoother transition

Cons: same as option 2 (but validation contiguousness vs ultra-light-client latency can be easily parametrized via ROTATION_PERIOD)

Option 4: use randomness

Let x be the root of the previous period committee. Let the seed for epoch i be seed = h(x, r, shard) where shard is the shard ID and r is the randao mix in the state at the start of epoch i. Use seed to randomly select a size-64 committee for each slot.

Pros: unpredictable
Cons:

• Much worst ultra-light-client capacity as there's no specific size-64 committee you can download to guarantee verifying a particular block
• Light clients have to trust attackers to give them a seed, and attackers could manipulate the seed (though VDFs may mitigate this)

Option 5: use randomness plus fractional staggering

Choose the epoch committees as above, but make the attesters for slot s be prev_epoch_committee[((s // 2) % 64):] + cur_epoch_committee[:(s // 2) % 64].

Pros: gradual replacement
Cons: a bit more complexity

Proposers vs attesters

It seems likely that we care more about unpredictability of proposers versus unpredictability of attesters. So one could favor using options 1-3 to choose attester committees, and randomly choose proposers, as light clients don't particularly need to securely verify who the proposer is.

Implementation alternative

The spirit of options 2 and 3 above can also be implemented by:

• Reducing the max persistent committee size to 64 (so often most validators will just formally not be part of any persistent committee)
• Reducing the max persistent committee period to ~12 hours
• Making the period committee function repeat its outputs often (ie. make outputs in the pattern ABCABCABCABCDEFDEFDEFDEFGHIGHIGHIGHI...)

This will reduce the complexity of these options by ~2x as we get to reuse a lot of logic

[djrtwo]

Generally in favor of the alternative described at the bottom knowing that even with smaller persistent committees, we have the (larger) crosslink committees as gatekeepers on bad/unavailable data. Components of options 3-5 seem too complex and the tradeoffs not in the right direction.

And agreed on the persistent committee repeating itself for longer usage of a single persistent committee in light clients.

Do we see any potential downside in having a small known set that can act highly performant in block production/attestation in the ~1 day time period? Smaller set is easier to bribe but the crosslink committees act as gatekeepers. I suppose one concern would be a smaller set that can be the target of DoS attacks.

[vbuterin]

I'm not especially worried about DoS attacks; if you knock down 2/3 of a committee then the other 1/3 are still standing and can form a chain. Light clients having trouble with a committee of one shard could even seamlessly switch to another shard.