[Bug Bounty] Committee selection can fork leading to multiple concurrent committees

[kladkogex]

High-level description of the bug [1 sentence]

ETH committee selection can fork leading to multiple concurrent committees operating, this needs to be at least addressed and explained in the spec.

Attack scenario

In ETH2 committees are selected based on the current state of the chain, which in turn depends
on the winning branch of the block tree.

The spec seems to not address the fact that since potentially Casper may not finalize for a long time, the LMD GHOST fork rule can lead to long-time reoderings in the chain.

An attacker can potentially reorder the chain, say, one day back in the past, totally changing committee assignments. The committee members that thought they were validating will be invalidated.

It then seems that new true committees will not be able to operate, since no-one can not respond to changes happening back in time, unless there is a time machine invented.

It may be that the spec actually does allow multiple alternative committees operating at the same time, that correspond to alternate branches. If yes, this needs to be explained in the spec. The way the spec currently is written it seems to state that there is a unique committee at each moment in time, which introduces confusion.

As I already mentioned, it may be a documentation issue, but the fact that this is not discussed at all in the spec is not good.

Impact: Describe the effect this may have in a production setting [1 to 2 sentences]

The chain may lose consistency and irreparably stall.

Components: Point to the files, functions, and/or specific line numbers where the bug occurs [1 to 2 sentences]

def get_committee_assignment(state: BeaconState,
epoch: Epoch,
validator_index: ValidatorIndex
) -> Optional[Tuple[Sequence[ValidatorIndex], CommitteeIndex, Slot]]:

Committee assignment depends on the state of the chain, which is not finalized

https://github.com/ethereum/eth2.0-specs/blob/dev/specs/phase0/validator.md#validator-assignments

Reproduction: If used any sort of tools/simulations to find the bug, describe in detail how to reproduce the buggy behavior. Showcasing the bug using the python spec and associated test infrastructure found in the spec repo is preferred!

1. Start the chain.
2. Turn off Casper for a while to simulate LMD Ghost only.
3. Introduce a long-term reorg by voting to for a very old alternative previously non-winning branch.

Details: Very specific details about the bug. What state must the system be in, what types of messages must be included and in which order, etc

I think this is pretty generic, the only condition is a long-term reorg that changes the committees.

It may be that the spec provides some type of defense against this, but I was not able to find it after re-reading the spec several times.

If some type of protection exist, it needs to be documented. So it may be either a documentation bug or a more fundamental spec issue.

Fix: Description of suggested fix if available

Seems that committees need to be selected only based on Casper-finalized state.
This means, that older finalized state needs to be used if newer does not yet exist.

It may be that the spec actually does allow multiple alternative committees operating at the same time, that correspond to alternate branches. If yes, this needs to be explained in the spec.

Note: if there is any bounty, please send it to Cancer Discovery fund

http://med.stanford.edu/cancer/about/help/make-a-gift.html

[protolambda]

This looks more like a misunderstanding than a bug. That said, it's a relevant concern, and has already been raised here: #1523 (Or at least very similar).

[djrtwo]

This is a known feature of the spec.

Within the context of the state transition inclusion of attestations, only those from the most recent and previous epoch wrt the chain in question can be included on chain, and thus from known shufflings.

Within the context of the block tree and LMD GHOST fork choice, all valid attestations from all blocks in the fork choice view are considered.

Within the context of attester slashings, indices (rather than on-chain calculated shufflings) are used to slash committees from unknown (from the view of the current chain) forks.

An attacker can potentially reorder the chain, say, one day back in the past, totally changing committee assignments. The committee members that thought they were validating will be invalidated.

An attacker can attempt to create some chain from the past with different committees, but (1) in most contexts this chain will have very little support (even in the context of non-finality) and be unlikely to be reorged to, and (2) the attacker chain would need to advance to a recent slot for considered at which point, it is indeed viable to look at and a node might swap to it if the LMD GHOST says so

Seems that committees need to be selected only based on Casper-finalized state.
This means, that older finalized state needs to be used if newer does not yet exist.

This would certainly make shufflings cleaner for client implementations, but would lose the benefit of short lookahead when the chain is not operating optimally, breaking some of the assumptions about randomness and committee selection.

The chain may lose consistency and irreparably stall.

Given how the state transition and fork choice handle forks, I do not believe that this is the case. The fork choice can generically handle the block tree, and incoming attestations are validated against the "target" state of the branch they are attesting to. So weight can be added to branches of the chain, a new head can be found, and state transitions up to this new head are self consistent.

It may be that the spec actually does allow multiple alternative committees operating at the same time, that correspond to alternate branches. If yes, this needs to be explained in the spec.

As you may have noted, the spec is particularly... terse. The existence of alternate shufflings in alternate branches is a very well known feature for client teams.

The concern when you open this up is less about pure consensus and fork choice issues (these structures are designed to handle it) and more about potential DoS issues. There is a tough balance between caching/pre-computing shufflings and being able to re-calculate depending on new information (new chains). In long running times of no finality, the potential DoS vector of an attacker exposing some deep reorg and inducing you to calculate epoch's worth of state transitions is a major concern.

[kladkogex]

An attacker can attempt to create some chain from the past with different committees, but (1) in most contexts this chain will have very little support (even in the context of non-finality) and be unlikely to be reorged to, and (2) the attacker chain would need to advance to a recent slot for considered at which point, it is indeed viable to look at and a node might swap to it if the LMD GHOST says so

Lets imagine that 10% of the stake is malicious.

Then, isnt it true that malicious validators, without any help from honest validators, will be able to advance the state of the alternative branch from an old point back in time to the current time? This branch will be much weaker then the winning branch, but then due to an inactivity leak the alternative branch will be able to finalize, so one will end up with two correctly finalized branches, so one will have to apply LDM rule again, after finalization, to decide the fork.

How will the current clients behave if they are faced with two correctly finalized alternative branches?

Will the following realistic attack work?

1. Take control of 1% of stake.
2. Recreate an alternative branch, going back 1 year in time and extending to the current time, where only these 1% nodes participate.
3. Note, that on this branch the good guys are inactive, so they will be leaked out.
4. Finalize this branch using Casper (note that at the current time 1% will turn into 1%).
5. Present the finalized branch to nodes to potentially crash the entire network, since finalization
   is supposed to be final, so presumably nodes are not implemented to deal with two alternative
   Casper-finalized heads, or at they?

To rephrase my question, should one conclude that the inactivity leak in the example breaks the mathematical finality Casper finalization, and nodes need to have additional finality mechanisms on top of Casper such as using the LMD rule again?

[vbuterin]

Right, this attack vector does exist, and it must exist because otherwise if 1-p of nodes go offline there is no way to continue the chain and eventually get back to normal. The response is that this attack is one of the two things (the other being validator rotation) that puts an upper bound on the weak subjectivity period of a chain, so the only solution is that clients need to log on often enough that when they see the attacker's chain they must have already seen a finalized block on the good chain after the attacker split off, and so the client will refuse to switch.

[kladkogex]

From your explanation it seems that the weak subjectivity period should be less or equal to the inactivity leak time.

It is dangerous to accept branches older than inactivity leak time.

So, does one need a check in the source code that specifically reject any new incoming branches older than inactivity leak time?

[JustinDrake]

does one need a check in the source code that specifically reject any new incoming branches older than inactivity leak time?

See #1520

[hwwhww]

@dapplion reminded - all clients have implemented weak subjectivity checks to guard against this attack. I'm closing this issue now.