Mitigating attacks on light clients

[vbuterin]

Light clients could theoretically verify the beacon chain with a reasonable degree of security at very low cost by verifying only one crosslink committee per epoch, or even more rarely. However, at present this approach is has a few key weaknesses.

First, it requires the light client to track the entire validator set (up to ~800 MB of state in the worst case), to be able to compute the validator shuffling. Note that alternative shuffling algos do not fix this problem, because the step of filtering out inactive validators still requires a pass through the entire validator set.

Second, it is potentially insecure, because of the following attack. A validator could choose a seed, compute the validator set shuffle assuming a particular validator set size, and then selectively censor validator set changes to make the shuffle match up with their subset. For example, if an attacker has all validator slots with IDs 0 mod 10 (for simplicity, realistically they might have a more chaotic combination with similar spacing), then to make a randomly selected committee of 128 match up with them, then as long as at least 9 validators activated or exited between each selected committee member and the next, they could selectively censor those activations and exits to make the committee match up perfectly with their own validators.

We can solve these issues as follows. First, we can keep track of the last four epoch-boundary validator_registry and validator_balances root hashes in the state, and we can mix the fourth last one (ie. the same one from where the validator set comes) into the shuffling seed. This means that the shuffling will now depend on the exact validator set used, so it will not be possible to manipulate the validator set to target a specific shuffling that the attacker already knows.

Second, in addition to adopting the number-theoretic or other pointwise-evaluable shuffle, we can remove the need for the validator set filtering step as follows. We keep track of another two arrays in the state, one for the historical total length of the validator set, the other for the historical length of the active validator set size. For attack mitigation reasons we can mix both of these values into the shuffling seed as well.

We compute the shuffle over [0...total_length-1] (so it includes all validators, not distinguishing active and inactive). To restrict the shuffle to active validators, we reuse the trick that we used to create number-theoretic shuffles for arbitrary lengths: if p is the permutation function over [0...total_length-1], then to calculate the actual permutation for x we first try p(x), then if p(x) is not a valid result try p(p(x)), if still incorrect try p(p(p(x))), etc (in practice, "not a valid result" means "is not an active validator" if evaluating the shuffle in one direction, and "is less than the active validator count" in the other direction).

Now, a light client can skip ahead by asking for a future block header, use the information in the block header to compute the indices for a committee, ask for Merkle branches to prove the committee, and then ask for those same Merkle branches of the validator set the client already knows about to verify that the validator set has not changed too much.

[JustinDrake]

The p(p(p(x))) idea is definitely clever :) Alternative idea below.

Add active_pubkeys: ['uint384'] to the state where:

• active_pubkeys starts off as []
• when a validator is activated its pubkey is appended to active_pubkeys
• when a validator is deactivated its entry is overwritten by moving the last entry of active_pubkeys to its place

(Notice that updates to active_pubkeys are "in place" to be Merkleisation friendly.) Now shuffles are done on active_pubkeys (rather than validator_registry), avoiding the performance hit of the p(p(p(x))) trick.

[vbuterin]

Workable, but having three validator state arrays is definitely not the best thing.....

[JustinDrake]

Do you mean from an aesthetic point of view? I does save from adding various bits and pieces to the state:

• last four epoch-boundary validator_registry
• last four epoch-boundary validator_balances (BTW, why is that required?)
• historical size of the validator set
• historical size of the active validator set

[vbuterin]

Would the active_pubkeys be updated per-slot, so we would need to do a full pass through the validator registry every slot to determine what gets added and removed? Or would it be a list of the pubkeys that will be active EXIT_ENTRY_DELAY slots from now? (which seems cleaner, but would mean that we need a list of historical roots of the tree).

[vbuterin]

I'm ok with it from an aesthetic point of view, it's more that the state size goes up yet again (we can mitigate this by storing indices and not pubkeys, but still.....).

[JustinDrake]

Would the active_pubkeys be updated per-slot

There are four events that trigger a validator set change 1) activations 2) exits 3) ejections 4) penalizations. All but penalizations happen at epoch boundaries. I'm therefore tempted to make the validator set change also happen at epoch boundaries. (Specifically, in exit_validator replace validator.exit_slot = state.slot + ENTRY_EXIT_DELAY with validator.exit_slot = ((state.slot - 1) // EPOCH_LENGTH + 1) * EPOCH_LENGTH + ENTRY_EXIT_DELAY.) That way active_pubkeys only gets updated per-epoch.

full pass through the validator registry [...] to determine what gets added and removed

A full pass through the validator registry is never required to update active_pubkeys. Indeed, it suffices to make local updates to active_pubkeys whenever validator_registry_delta_chain_tip is updated (in activate_validator and exit_validator).

Or would it be a list of the pubkeys that will be active EXIT_ENTRY_DELAY slots from now?

Having light clients know at least EXIT_ENTRY_DELAY slots ahead of time of validator set changes is definitely valuable for always-online light clients. Indeed, it means that an attacker grinding on the active validator set cannot fool always-online light clients. The good news is that this information is already communicated early with validator_registry_delta_chain_tip.

we can mitigate this by storing indices and not pubkeys

The reason I went with pubkeys as opposed to indices is so that light-clients don't have to bother with validator_registry. Indeed, with indices light clients need one Merkle path per index, and then another Merkle path for the corresponding entry in the registry. It may make sense to add a penalized: bool for every entry in active_pubkeys so that light clients know to ignore votes from penalized validators.

[vbuterin]

A full pass through the validator registry is never required to update active_pubkeys. Indeed, it suffices to make local updates to active_pubkeys whenever validator_registry_delta_chain_tip is updated (in activate_validator and exit_validator).

Right but my point is that if we do it that way, then the active_pubkeys array in the state would represent the active pubkeys ENTRY_EXIT_SLOTS in the future, not in the present. So if we want the current active pubkey set to be accessible, we need to store the set from the last four epochs.

The reason I went with pubkeys as opposed to indices is so that light-clients don't have to bother with validator_registry

True, though for security we would need to add penalized:bool and also balances, as light clients need to take those into account to avoid being hit by a <1/3 attack consisting of low-balance deposit slots. And at that point, it feels much simpler to just store an index and ask validators to also check this other information.

That said, this would lead to light clients needing to download a bunch of Merkle branches, at which point it's not clear that this approach to light clients is even better than the old approach of requiring them to store and update the entire validator set and use that to calculate committees.....

[JustinDrake]

Closing in favour of #459 :)