get_changed_validators processes validators out-of-order

[arnetheduck]

validator_records in BeaconState is updated by replacing the validator min_empty_validator_index, but get_changed_validators iterates in list order - thus, sometimes a validator that was added at a later time to the list will be activated early.

bfe0e9f

[hwwhww]

I think you're right. /cc @JustinDrake @djrtwo
It seems related to the MAX_BALANCE_CHURN_QUOTIENT threshold checking you've mentioned.

[djrtwo]

This is true but not a very game-able imo.

A simple solution would be to sort the validator list in get_changed_validators by latest_status_change_slot to ensure that validators that changed status longer ago get priority in processing.

I'm in favor of this change. What say you @hwwhww, @JustinDrake, @vbuterin

[JustinDrake]

A simple solution would be to sort the validator list in get_changed_validators by latest_status_change_slot

Right, sort validators in this for loop (taking care to not sort anything else)

for i in range(len(validators)):
    if validators[i].status == PENDING_ACTIVATION and validators[i].balance >= MAX_DEPOSIT:

[thadguidry]

What happens if there's a cloned validator ? For example, I somehow manage to clone a validators laptop nefariously or steal it, and original owner has backup and comes online (I have BLS pubkey & withdrawal_credentials, etc.) and attempt to validate the beacon chain as an imposter for my own nefarious purposes ? Possible ? Anything else needed within a ValidatorRecord or elsewhere to mitigate this hypothetical scenario ? isDuplicateValidator() ?

I guess one path taken would be the else for the condition if pubkey not in validator_pubkeys: ? What else ?

[djrtwo]

There can only be one instance of a ValidatorRecord in state per pubkey. The else on that statement is to just increase the balance of the existing validator with the new deposit (a "top-up").

If you steal a validator key, you are (from the perspective of the protocol) the validator. You can sign messages however you see fit. You are likely to sign a set of slashable messages or just submit an exit call. Other than that, you can't do much harm. The slashing (if not correlated with a high number of other slashings) will be relatively small. The withdrawal address is distinct from the signing key so as long as you kept your signing key offline/safe/secure, you will still control the ejected funds.

[djrtwo]

@JustinDrake Because the index is not a field on ValidatorRecord, the indices first need to be gathered and then sorted alongside the ValidatorRecords

Something like

indices_and_validators = sorted(
    [(i, validator) for i, validator in enumerate(state.validator_registry)],
    key=lambda index_and_validator: index_and_validator[1].latest_status_change_slot
)

# Activate validators within the allowable balance churn
balance_churn = 0
for index, validator in indices_and_validators:
    ...

Not the prettiest, but works.
Do you think we should go ahead with this?
(cc: @vbuterin, @JustinDrake, @hwwhww)

[zah]

Here is one more idea that might be interesting:

What if instead of using min_empty_validator_index to find an unused slot for a new validator, we use a free list? This will allow us to find an unused validator slot in O(0) at the expense of adding a new field to the ValidatorRecord (e.g. next_slot*). The additional twist here is that the same field can be utilized in the active slots to form a chronological list of the inserted validators that can be used for activation in the right order.

* In practice, next_slot can fit in the unused bits of some of the other fields (e.g. status).

[JustinDrake]

min_empty_validator_index is gone now so this is a non-issue, at least for phase 0 👍

See #374

[zah]

Hmm, I can see that in #374, the process_deposit function now looks like this:

    if pubkey not in validator_pubkeys:
        # Add new validator
        validator = ValidatorRecord(...)

        # Note: In phase 2 registry indices that has been withdrawn for a long time will be recycled.
        index = len(state.validator_registry)
        state.validator_registry.append(validator)
        state.validator_balances.append(amount)

In other words, it always appends to the end of the validator list. What is the long term plan regarding this? Is the final solution postponed to phase 2? If there is interest, I can try to flesh out a bit more how the free-list solution might work. All the validator lifecycle operations will be able to run in O(0).

[JustinDrake]

I'm tempted to punt this until phase 2. Feel free to reopen @zah if you end up working on a solution :)