Cheaper signature verifcation for incoming blocks

[paulhauner]

Problem

I've been thinking about a DoS vector for block processing at sigp/lighthouse#485 (comment).

In summary, a network participant can produce a block which has a parent block more than one epoch ago (e.g., the last finalized block). Before we can verify the signature of this new block, we need to compute the shuffling for the block's epoch where all slots between it and it's parent have been skipped.

Computing the shuffling that results from this large cross-epoch skip is roughly O(V), where V is the validator count. (We might need to recompute the active validator set due to validators exiting or activating).

This means that detecting if some block has been signed by a deposited (not necessarily active) validator is O(V).

To reduce our attack surface, I think it would be desirable to verify that a block has been produced by a deposited validator every time we receive a block from the network (given we're adequately synced). As such, if we're going to call this function a lot, it would be nice if it were faster and more O(1).

Potential Solution

It's difficult to build a cache for this operation because the attacker can modify the shuffling depending upon which parent block they choose. The number of caches required becomes prohibitive.

It seems that adding a proposer field to a BeaconBlock (which holds the block proposer's validator index) would make this operation O(1) at the cost of 8 bytes per block.

I'm interested to hear thoughts or non-spec-changing alternatives :)

[JustinDrake]

Computing the shuffling that results from this large cross-epoch skip is roughly O(V), where V is the validator count. (We might need to recompute the active validator set due to validators exiting or activating).

This may no longer be an issue after merging #1329. Indeed, the shuffling can be point-wise evaluated, so we just need to ensure skipped epochs do not force recomputing the full shuffling. (In hindsight, this is a very sane property to have to mitigate other DoS vectors, e.g. related to evaluating the fork choice rule.) Now compute_shuffled_index is only called by compute_committee which itself is only called by get_crosslink_committee. There are 5 calls to get_crosslink_committee:

1. in get_beacon_proposer_index => only computes the shuffling for the first committee so we benefit from point-wise evaluation (notice that it may suffice to compute the first validators in the first committee, not the full committee).
2. in get_compact_committees_root => this goes away with Remove light client infrastructure from phase 0 #1329
3. in process_crosslinks => not relevant in the context of many skipped epochs
4. in get_crosslink_deltas => computing the shuffling is not necessary since everyone receives a base_reward penalty
5. in get_attesting_indices, which is itself called in 3 places:
   • get_indexed_attestation => only called by process_attestation, itself not relevant for many skipped epochs
   • get_attestation_deltas => for attestation micro-rewards, not relevant for skipped epochs
   • get_unslashed_attesting_indices, itself called in a few places which at first glance don't seem to require recomputing the full shuffle 😂

[vbuterin]

You don't need to compute the entire shuffling to compute the proposer, you can just compute one single shuffled index (or sometimes a couple of extra shuffled indices if the first one doesn't work out).

You can replace candidate_index = first_committee[...] in https://github.com/ethereum/eth2.0-specs/blob/dev/specs/core/0_beacon-chain.md#get_beacon_proposer_index with a direct lazy-evaluated call to compute_shuffled_index.

[paulhauner]

I understand that we don't need to do the entire shuffling, but don't we still need to scan the validator registry to find any validators that have activated/exited during the skipped epochs (in order to get the active validator indices, in order to do the point-wise shuffling)?

This is the O(V) I was referring to.

[JustinDrake]

don't we still need to scan the validator registry to find any validators that have activated/exited during the skipped epochs (in order to get the active validator indices, in order to do the point-wise shuffling)?

A few notes:

1. The activation_queue in process_registry_updates can be implemented as a queue. In the worst case (assuming 2**22 validators) you need to dequeue get_validator_churn_limit(state) == 64 validators per epoch. In other words, there's no need to enumerate(state.validators) and activations are O(1) per epoch in the worst case.
2. Exits can also be implemented as a queue, and a similar analysis to the above can be made for voluntary exits and slashing exits. The harder case to handle is ejection exits which can add to the exit queue during a skipped epoch. The good news is that O(1)-per-epoch ejection exits can be implemented by maintaining the validator registry sorted by balance. Indeed, validators with the lowest balance will be ejected first during skipped epochs.
3. In practice for ejections you may want to only maintain some number (say, 1024) of validators that at most "at risk" of getting ejected. In the worst case these 1024 validators will get ejected in 1024/get_validator_churn_limit(state) >= 16 skipped epochs (and likely many more in the average case) before having to fallback to reading the full registry.

[paulhauner]

Thanks @JustinDrake, I'll come back to these notes if we decide to implement and store such a cache :)

[djrtwo]

I'm pro adding the additional field. It takes ambiguity and complexity out of the equation and allows for a much simpler DoS protection and simpler evaluation when forwarding in the gossip protocol.

This also lowers the overhead and simplifies the calcuation in processing proposer slashing

[mkalinin]

How do we know if proposer with specified index is eligible to propose a block without processing registry updates for empty epochs? For instance, validator could be ejected due to its inactivity and wouldn't be included into a committee.

[djrtwo]

You're right, and eligibility isn't just wrt activations/exits, it is wrt the shuffling in general.

The "cheap" check of checking the proposer signature without knowing the shuffling opens ourselves up to a new DoS vector. Generally, there are only 64 valid proposers per epoch from the view of the canonical chain. If we require validation of the signature wrt the shuffling prior to forwarding a block, we get decent gossip DoS protection. If instead, we forward any block that has a valid proposer signature regardless of checking the shuffling, then we allow for the entirety of the validator set (minus the actual proposers) to get one free DoS block per epoch.

A valid signature but unknown parent might enough to decide to perform the state transition but shouldn't be the min criterion to re-gossip the block. The decision on what to do with a block that is a child of a very old parent or an unknown parent still might need to be subject to heuristics (how old the parent, have we seen any attestations for the block, etc)

[mkalinin]

eligibility isn't just wrt activations/exits, it is wrt the shuffling in general.

Right. Checking a signature with no regard to a shuffling only checks data integrity and proof of possession of the public key.

Also, there is pretty legal case when we have to do an epoch transition in order to validate block's signature:

  -> EMPTY -> B64'
 /
B62 -> B63 -> B64

Signature verification of block B64' requires an additional epoch transition made upon an empty slot. It means that epoch transition should be optimal enough to handle such cases.

The decision on what to do with a block that is a child of a very old parent or an unknown parent still might need to be subject to heuristics (how old the parent, have we seen any attestations for the block, etc)

Is there any cases when we want to continue building a chain upon a block that is behind last justified block?

Proposer index in a block might aid in slashing condition checks. I.e. it should be easier to get proposer's identity and then proceed with that.

[paulhauner]

The "cheap" check of checking the proposer signature without knowing the shuffling opens ourselves up to a new DoS vector.

The ability to do the cheap check reduces the actors that can request you to do an "expensive" check. There's almost no computational overhead to do the cheap check before you do the expensive one.

[mkalinin]

The ability to do the cheap check reduces the actors that can request you to do an "expensive" check.

Agree. That said, validator index is not a 100% reliable thing because it may change due to massive reorg in eth1 chain. And it could make blocks produced by a validator eventually invalid. Do we want to care about that in this particular case?

[JustinDrake]

Do we still want to add a proposer field to beacon blocks? My inclination is "no" for a few reasons:

1. there are ways to mitigate the DoS issue (admittedly, at the cost of implementation complexity)
2. adding a proposer field does not fully resolve the DoS vector anyway
3. this issue has gone stale, indicating a possible lack of interest
4. we need to limit post-freeze substantive changes to ship phase 0 ASAP

Feel free to reopen if you feel otherwise :)