Description
Description
While debugging a test failure on this PR, we found that shuffling_is_compatible is subject to false negatives, i.e. it can return false for inputs that are compatible:
The reason for this is that shuffling_is_compatible acts on the assumption that the shufflings of two states are equal at a given epoch if and only if they have equal block roots at the decision slot for that epoch, i.e.
get_block_root(state_a, decision_slot(epoch)) == get_block_root(state_b, decision_slot(epoch)) <->
committee_cache(state_a, epoch) == committee_cache(state_b, epoch)As the example linked above shows, this implication is actually one directional (-> holds but <- does not). I.e. equal block roots are a sufficient but not necessary condition for the shufflings to be equal.
Impact
In practice, on large networks we are unlikely to see this case arise because there are so many validators. To trigger it requires at minimum two consecutive proposals by the same validator at the end of an epoch, e.g. RANDAO mix is A for both slot offsets 30 and 31, leading to slot 29 and slot 31 having identical RANDAO values in the state (X and X ^ A ^ A = X).
Even if it does occur, the only impact is that some attestations from a forked chain will be deemed incompatible and prevented from being packed in blocks. In our example above, a validator who votes for slot 29 two epochs later will have their attestation discarded because the decision block root will be the block root from slot 29 rather than the block from the canonical chain (slot 31). This is totally harmless and fine (TM). That's a pretty low quality attestation anyway, and we don't care if it gets trashed.
Version
Lighthouse v5.3.0
Steps to resolve
Unclear. Re-working shuffling_is_compatible to remove these sorts of false negatives is likely to be hard, because the only information that it has access to is information about block roots (from fork choice). We would need access to the RANDAO to do better.
Alternatively, we could rename the function to something like shuffling_is_definitely_compatible, and improve its docs to highlight the possibility of false negatives.