Lighthouse: DoS vector when processing blocks with big skips

[paulhauner]

Description

As mentioned in #482, when we receive a block for processing we load its previous state from disk and advance the state to the slot of the to-be-processed block.

Advancing the state requires significant computation (hashing, per-epoch processing, etc) which scales linearly with the slot-wise distance between the block and it's parent. With an unbounded distance, it's not unreasonable to expect minutes/hours of computation. This is a severe DoS vector.

Potential Solutions

I propose that we add a MAX_DISTANCE value (not necessarily constant) which defines the maximum slot-wise distance between a block and it's parent, and that we impose that upon all block processing. Any block that exceeds this distance will be deemed invalid.

The trade-off here is that we fail to support some valid consensus messages (e.g., producing a block at slot 1,000,000 which references genesis is indeed valid). My conjecture is that if MAX_DISTANCE is set to to something in the order of 10's of epochs there would be no negative impact on a real-world system.

[terencechain]

@prestonvanloon was just talking about this today, we saw big timeout when beacon node has to process a bunch of skip slots to compute the assignments. We are researching a proper way to cache for long skip slots and redundant advancements

[paulhauner]

Great minds! :D

We have a cached BeaconState that we use for faster block production and committee retrieval. It's a bit naive at the moment, but I'm looking to improve it with #482. I'll be interested to hear what you come up with!

I think this issue is similar to that, but a solution to the block _production_ and committee retrieval problem doesn't necessarily address this problem about block _processing_. When doing production and committee retrieval, we can optimize under the assumption that we're operating operating +/- 1 epoch from the current slot and that we want to work off the head. When it comes to block _processing_ we're potentially dealing with actors who can arbitrarily pick the parent.

[paulhauner]

@protolambda just pointed out that there's a safe MAX_DISTANCE that doesn't restrict the set of processable blocks because at some point all validators will be slashed out.

[paulhauner]

I'm working on this now

[prestonvanloon]

Why would a block at slot 1,000,000 have a parent block that is genesis and still be valid? (Assuming there is at least one finalized epoch since genesis.) We already know that this block can never be the head of the chain since we already have a finalized fork height that is greater than the parent of this block.

I'm thinking that we can reject any block from the future and any block that references a parent older than the most recent finalized epoch. What do you think?

[paulhauner]

I'm thinking that we can reject any block from the future and any block that references a parent older than the most recent finalized epoch. What do you think?

Agreed, we're taking this approach too.

However, if the last finalized epoch is 4 epochs ago, there's still this problem where a malicious actor can force us to replay 4 epochs worth of skipping when it's very unlikely that 4 * 64 blocks have been skipped.

The real concern is that we can't even verify the signature of the block before we do this skipping as we can't map block.slot -> validator_index until we know the shuffling in that final state, meaning this attack is not restricted to proposers (anyone can do it).

Thinking about this some more, the MAX_DISTANCE solution is a bit heavy handed. Here are some alternatives:

Add a proposer field to BeaconBlock

This field would contain the index of the proposer that signed the block.

With this field, we could run the following checks using only the parent block's state (i.e., without any skipping):

• Is the validator obviously not active in the slot of the proposed block? (i.e., inactive, slashed, etc)
• Did the validator actually sign the block?

This would reduce the scope of the attack to validators who are _probably_ slashable.

• Pros
  
  
  
  • Signature verification becomes much easier, becomes cheaper to reject blocks that aren't signed by validators.
  
  
  • Simpler than other solutions.
  
  
• Cons
  
  
  
  • Spec change.
  
  
  • 8 more bytes to send over the wire.
  
  

Create a light-weight skip method

In order to learn the validator_index of the proposer and reduce the scope of this attack to deposited validators, all you need to know is the shuffling for that epoch.

You don't need to do the whole per_slot_processing to learn that -- I think all you need is active_validator_indices for each intermediate epoch and the seed of the last epoch (easily computed).

• Pros
  
  
  
  • Doesn't change spec.
  
  
• Cons
  
  
  
  • Light-weight skip method is additional complexity.
  
  
  • Calculating active validator indices is still a bit of work.
  
  

Use an attestation-based heuristic for rejecting such blocks

You could make a reasonable judgement that if some block skips 4 epochs, but there's some block 1 epoch ago with significant amount of attestations than the received block is invalid.

• Pros:
  
  
  
  • Doesn't change the spec.
  
  
• Cons:
  
  
  
  • Rejects valid consensus messages (even if those messages might be eventually useless).
  
  
  • Maintaining and calculating this heuristic is potentially more effort than the previous suggestions.
  
  

[arnetheduck]

Create a light-weight skip method

We've been contemplating this one mostly - it applies to most of the spec that it would be nice to be able to apply only relevant parts. We have yet to make the data dependency analysis to find out which parts of the spec code touch which parts of the state and therefore can be made independent. Has anyone conducted a study like this? I imagine with a control flow graph one could generate it from the code.

[paulhauner]

Has anyone conducted a study like this? I imagine with a control flow graph one could generate it from the code.

I haven't done anything like this, but as I just mentioned here https://github.com/ethereum/eth2.0-specs/issues/1339, you probably need to scan the validator registry at least once during this process.

Validator exit or activation epochs might occur during the skips and you need to keep track of that in order to know the active validator indices (and therefore the shuffling) for the to-be-verified block's epoch.

[paulhauner]

Here's a fairly detailed analysis from Vitalik: https://github.com/ethereum/eth2.0-specs/issues/1340

[adaszko]

Closed it accidentally (GitHub UI deceived me). Please ignore.

[paulhauner]

Closing this since we now have proposer_index on blocks and we have a fairly light-weight method for skipping slots to compute committees.