Eth2.0-specs: `get_shards_and_committees_for_slot` for future slots

[djrtwo]

Issue

get_shards_and_committees_for_slot only provides a shuffling for the previous cycle and the next cycle (since the last state recalc). If a cycle's worth of proposers don't show up, and the next block proposed is in the following cycle, then this function cannot be used to get the committees and proposers.

This function needs to provide valid committee/proposer for slots of arbitrary distance into the future.

Proposed solution

def get_shards_and_committees_for_slot(crystallized_state: CrystallizedState,
                                       slot: int) -> List[ShardAndCommittee]:
    earliest_slot_in_array = crystallized_state.last_state_recalculation - CYCLE_LENGTH
    assert earliest_slot_in_array <= slot
    if slot < crystallized_state.last_state_recalculation:
        index = slot - earliest_slot_in_array
    else:
        index = CYCL_LENGTH + (slot % CYCLE_LENGTH)
    return crystallized_state.shard_and_committee_for_slots[index]

The else statement index allows for slots arbitrarily in the future to be mapped to the second half of the crystallized_state.shard_and_committee_for_slots array.

[djrtwo]

cc: @vbuterin @hwwhww

[vbuterin]

Seems reasonable to me. Typo CYCL_LENGTH -> CYCLE_LENGTH

[rawfalafel]

Would this cause weird timing issues? Two nodes could have different proposers for the same slot depending on whether or not state recalculations had happened for that cycle.

[hwwhww]

So the slot >= earliest_slot_in_array + CYCLE_LENGTH * 2 case only happens when there's a large slot gap between blocks, so we need to determine the proposer of the in-coming block?

This sentence in the spec might need to be modified because we can set any future slot, but the consistency is not guaranteed now:

get_shards_and_committees_for_slot(_, s) should not change unless the validator set changes.

[rawfalafel]

This is an issue for the first block of every new cycle, not just when there's a large gap. It's a bit of a chicken-and-egg problem where the proposers for a new cycle are determined _after_ the first block gets processed, so the proposer for that first block isn't known when it's time to propose.

@hwwhww brings up a good point, and I think there's two issues with the proposed solution:

• get_shards_and_committees_for_slot(_, s) is no longer consistent, but is now dependent on whether or not s is the first block in the cycle.
• get_shards_and_committes_for_slot(_, s) no longer works when s is the first block in a cycle and s < last_state_recalculation.

The proposed solution will require an additional bool in each block to specify whether or not its the first block in the cycle, and some additional logic to hold onto that one [ShardAndCommittee] object for one extra cycle.

Here's another solution. Have shard_and_committee_for_slots contain 3 cycles worth of committees, and the following change:

def get_shards_and_committees_for_slot(crystallized_state: CrystallizedState,
                                       slot: int) -> List[ShardAndCommittee]:
    earliest_slot_in_array = crystallized_state.last_state_recalculation - CYCLE_LENGTH
    assert earliest_slot_in_array <= slot
    if slot < crystallized_state.last_state_recalculation + CYCLE_LENGTH:
        index = slot - earliest_slot_in_array
    else:
        index = CYCLE_LENGTH * 2 + (slot % CYCLE_LENGTH)
    return crystallized_state.shard_and_committee_for_slots[index]

Assuming 2^18 or 262144 validators, my quick math says that one cycle worth of committees takes up 770kb of space, and the ValidatorRecord array takes up 28MB of space. Therefore, adding an additional cycle worth of committees will increase the size of crystallized_state by about 2.5%. That's not trivial, so maybe not worth it.

[djrtwo]

3 cycles just kicks the can down the road! You could have a block that skipped an entire cycle and was at the next boundary.

This is a bug that runs deeper than we previously acknowledged. We should really only be using the randao_mix from the last_finalized_block rather than with the most recent blocks processed. Essentially, when we do a re-shuffling, no one should disagree on this new shuffling.

[rawfalafel]

In my alternate solution, the third cycle represents the next non-empty cycle, so it can handle the scenario where one or more cycles are skipped. Now that I think about it, the alternate solution would also need one more modification to make sure that the first cycle of shard_and_committees_for_slots is correct when an entire cycle's skipped.

[djrtwo]

Ah, I see. I didn't read through it fully. It is a more clever solution than I initially realized :)

I _think_ that grabbing the randao mix from the last last_finalized_block from the previous _previous_ cycle will give us what we want and ensure the consistent shuffling. I'll get a firmed solution propose shortly.

[djrtwo]

I'll pick this up now that we finally handled the big changes

[JustinDrake]

Can this be closed @djrtwo?