Proposal for persistent committees

[vbuterin]

One recent desideratum of the spec has been to remove the explicit shufflings (both crosslink and persistent committees) from the state, allowing it to instead be calculated directly from the validator set (see #374 which makes it easy to determine historical validator sets from present state) and a historical RANDAO value. Here is a specific proposal for doing the same for persistent committees.

Preliminaries:

• Let RESHUFFLE_PERIOD = 1024 epochs (~4.5 days). Let get_randao_mix_at_epoch(e) = latest_randao_mixes[e % LATEST_RANDAO_MIXES_LENGTH]
• Change the latest_randao_mixes array so it stores the last 8192 epoch boundary RANDAOs, not the last 8192 slot RANDAOs.
• Let reassign_position(validator_index) = validator_index % RESHUFFLE_PERIOD

Proposal 1

For every validator, we calculate a "relevant randao hash" that changes every RESHUFFLE_PERIOD epochs, but where different validators' hashes change at different times. These hashes are then used to determine what shard a validator is in.

• Let epoch(slot) = slot // EPOCH_LENGTH. Let relevant_randao_epoch(validator_index, current_slot) = max(0, epoch(current_slot) - (epoch(current_slot) % RESHUFFLE_PERIOD) - RESHUFFLE_PERIOD + reassign_position(validator_index))
• Let relevant_randao_hash(validator_index, current_slot) = get_randao_mix_at_epoch(relevant_randao_epoch(validator_index, current_slot))

To determine what shard a validator with some validator_index is on, calculate hash(relevant_randao_hash(validator_index, state.slot) + bytes8(validator_index)) % SHARD_COUNT.

Proposal 2

Let current_epoch = epoch(current_slot), reshuffle_epoch = current_epoch - current_epoch % RESHUFFLE_PERIOD - RESHUFFLE_PERIOD. Use split(shuffle(get_active_validator_set(reshuffle_slot), get_randao_mix_at_epoch(current_epoch)) to calculate the "current shard committees".

However, for any individual validator with some index, when the shard committee switches, they continue using the old committee for an additional hash(get_randao_mix_at_epoch(current_epoch) + bytes8(index)) % RESHUFFLE_PERIOD epochs.

Properties

Benefits of both proposals:

• The validators are always roughly evenly distributed between the shards
• Reassignment is predictable at least RESHUFFLE_PERIOD in advance
• No extra storage in the state is required

Differences between the two proposals:

• In proposal 1, every validator's shard is predictable exactly RESHUFFLE_PERIOD in advance, in proposal 2 it's predictable between RESHUFFLE_PERIOD and 2 * RESHUFFLE_PERIOD in advance.
• In proposal 1, validators can target a specific reassignment epoch by targeting a specific time when they deposit. However, the worst case scenario here is simply that a large pool of attackers all get reassigned at roughly the same time, which doesn't directly break anything.
• Proposal 2 puts more pressure on one specific RANDAO value than proposal 1 (though especially with VDFs the effect of this will be limited)
• Proposal 2 allows easy calculation of the entire persistent committee for a specific shard (which is needed eg. to calculate the proposer at any given slot) without going through the entire validator set; proposal 1 does not.

At present I lean toward proposal 2 or something similar because of the last item especially, though either seems fundamentally workable.

Roadmap strategy notes:

• If we agree that something like this is fundamentally a good idea, we can remove persistent committees from the protocol entirely for phase 0, and move this logic into phase 1.

[djrtwo]

For proposal 2, is the following how we would calculate the actual persistent committees at any time?

• get prev_persistent_committees from the prev_reshuffle_epoch (reshuffle_epoch - RESHUFFLE_PERIOD)
• get presistent_committees from reshuffle_epoch
• gather the indices swapped_indices that should be swapped up to current_epoch
• remove swapped_indices from prev_persistent_committees
• remove all indices that are not in swapped_indices from persistent_committees
• construct actual_persistent_committees as:

actual_persistent_committees = [
    prev_persistent_committees[shard] + persistent_committees[shard]
    for shard in range(SHARD_COUNT)
]

And if we use one of the shufflings that allows us to directly calculate positions, then we can easily reduce the above routine to a single shard.

[djrtwo]

I think I remember @JustinDrake was keen to have slot granular randao mixes for more optionality to expose to use layer. It should be noted that this proposal removes that granularity.

I think it's fine. I'm not sure there is much benefit to expose so many mixes. In the event that we have VDFs only the epoch boundaries will be hardened anyway.

[djrtwo]

I lean in favor [2] as well. It seems a little less clean due to the varied range of lookahead for each validator, but reducing the overhead required to get the shuffling of a particular shard by 1000x seems like a solid win for resource constrained defines. We need to switch the shuffling alg to something like in #323 to get this benefit, correct?

[JustinDrake]

I think I remember @JustinDrake was keen to have slot granular randao mixes for more optionality to expose to use layer.

I don't care too much about that :) The application layer can use maximally-granular RANDAO mixes extremely simply: just pass in the intermediate values and verify they match the boundary RANDAO mixes.

[vbuterin]

For proposal 2, is the following how we would calculate the actual persistent committees at any time?

That looks right.

We need to switch the shuffling alg to something like in #323 to get this benefit, correct?

Yes.

[djrtwo]

This is implemented here https://github.com/ethereum/eth2.0-specs/blob/dev/specs/core/1_shard-data-chains.md#get_persistent_committee