Re-use beacon chain indexes

Assign new deposits to existing validator records that have withdrawn long ago

Motivation

Withdrawn indexes are dead weight that adds cost to the protocol:

• Beacon state size is roughly proportional to validator count
• Some epoch transition steps require a full sweep over all validators
• Higher tree-hashing cost / complexity

Safe to reuse epochs constant

From @djrtwo : Tentatively ~3x WS period, so 1 year

Refer to ethereum/EIPs#6914 for security considerations and attacks.

Strategy A: Full-sweep

def assign_index_to_deposit(state: BeaconState) -> uint64:
    for index, validator in enumerate(state.validators):
        if is_reusable_validator(...):
            return index
    return len(state.validators)

• Most efficient, always allocate re-usable indexes to validators
• Requires a cache to be efficient, see full sweep cache

Strategy B: Bounded sweep

def compute_reuse_index(state: BeaconState) -> uint64:
    index = state.next_reuse_sweep_index
    bound = min(len(state.validators), MAX_VALIDATORS_PER_REUSE_SWEEP)
    for _ in range(bound):
        if is_reusable_validator(...):
            state.next_reuse_sweep_index = index + 1
            return index
        index = ValidatorIndex((index + 1) % len(state.validators))
    state.next_reuse_sweep_index = index
    return len(state.validators)

• Similar to withdrawals sweep, boundness should prevent the need a cache.
• Will not allocate all potentially re-usable indexes to validators, see bounded sweep reuse efficiency

Full sweep cache

Define reusable_indexes(state) as the set of all validator indexes in state that satisfy predicate is_reusable_validator.

Reusable indexes must satisfy conditions:

1. validator.withdrawable_epoch < epoch - REUSE_VALIDATOR_INDEX_DELAY: epoch is constant through an epoch (duh) and validator.withdrawable_epoch can only change if this validator is reused. Re-using is an irreversible action during an epoch. So the set reusable_indexes(state_0) includes all possible sets reusable_indexes(state_child) where state_child is a descendant of state_0 in the same epoch.
2. balance == 0. Balance may not be zero if there's remaining balance from active duties (in extreme configurations). Balance can only be increased with a deposit topup. Balance can only be decreased to zero with a full withdrawal (if EPOCHS_PER_SLASHINGS_VECTOR < REUSE_VALIDATOR_INDEX_DELAY)

Cache strategy

• Once per dependent root after applying an epoch transition, compute a list potential_reusable_indexes of all validator indexes with validator.withdrawable_epoch < epoch. That set includes all possible reusable indexes on that epoch. Store that list as immutable referenced by all child states in epoch. Instantiate an empty set reused_indexes
• On each fork share the immutable reference to potential_reusable_indexes and clone reused_indexes
• On apply_deposit, iterate sequentially over potential_reusable_indexes and check index not in reused_indexes and balance == 0. If so, add the index to reused_indexes
• (extra) If last finalized < MIN_VALIDATOR_WITHDRAWABILITY_DELAY the cached list is guaranteed to be the same for all states at epoch N.

def on_epoch_process(state: BeaconState, cache):
    # Immutable shared cache for all child states in same epoch
    cache.potential_reusable_indexes = []
    # Per state set of indexes reused
    cache.reused_indexes = set()
    for index, validator in enumerate(state.validators):
        if validator.withdrawable_epoch < get_current_epoch(state) - REUSE_VALIDATOR_INDEX_DELAY:
            cache.potential_reusable_indexes.push(index)

def compute_reuse_index(state: BeaconState, cache) -> int:
    for index in cache.potential_reusable_indexes:
        if state.balances[index] == 0:
            cache.reused_indexes.add(index)
            return index
    return len(state.validators)

Bounded sweep reuse efficiency

Define efficiency as the ratio of re-used indexes with partial sweep by re-used indexes with full sweep (theoretical maximum). We want to maximize efficiency.

We also want to bound computational cost on block processing, such that avg deposits per block * MAX_VALIDATORS_PER_REUSE_SWEEP << len(state.validators). Note that after EIP6110, deposits per block is bounded only by gas, and could be much higher than current MAX_DEPOSITS = 16.

Note that this two goals oppose each other. Also note that missing the opportunity to re-use an index results on a significant long term cost (until new index withdraws) of an extra validator record.

Toy examples

Consider the following patterns of validator records:

• Pattern ------YY means 6 non-reusable indexes, 2 reusable indexes
• Assume MAX_VALIDATORS_PER_REUSE_SWEEP = 2