# Unrealized Justification Reorgs Thanks to Paul, Potuz, Danny [toc] ## Background ### `Store` updates The fork choice tracks the states of the beacon chain using the [`Store`](https://github.com/ethereum/consensus-specs/blob/9f643d8dbf678430bc6707f0e5b914d0bf62545c/specs/phase0/fork-choice.md#store). The Store is updated on every clock tick, block, & attestation: - [`on_block`](https://github.com/ethereum/consensus-specs/blob/9f643d8dbf678430bc6707f0e5b914d0bf62545c/specs/phase0/fork-choice.md#on_block) processes the new block and saves the corresponding post-state & just./fin. updates in the `Store`. - [`on_tick`](https://github.com/ethereum/consensus-specs/blob/9f643d8dbf678430bc6707f0e5b914d0bf62545c/specs/phase0/fork-choice.md#on_tick) makes time- and cache-related updates to the `Store`, but does not process or save state updates. ### Block tree filtering The fork choice filters the block tree to [include only those leaves that satisfy](https://github.com/ethereum/consensus-specs/blame/9f643d8dbf678430bc6707f0e5b914d0bf62545c/specs/phase0/fork-choice.md#L223-L226): ```python correct_justified = ( store.justified_checkpoint.epoch == GENESIS_EPOCH or head_state.current_justified_checkpoint == store.justified_checkpoint ) ``` ### Unrealized justification An unrealized jutification is found when a block includes enough attestations in its chain to justify a newer checkpoint as compared to the one in its post-state, because we haven't yet processed FFG votes. FFG votes are processed only at the epoch boundary. ### Validator attestation behavior Validators are assigned attestation duties for specific slots. When making an attestation for a skipped epoch boundary slot, the validator is expected to use the [following `head_block` and `head_state`](https://github.com/ethereum/consensus-specs/blob/9f643d8dbf678430bc6707f0e5b914d0bf62545c/specs/phase0/validator.md#attestation-data): > - Let `head_block` be the result of running the fork choice during the assigned slot. > - Let `head_state` be the state of `head_block` processed through any empty slots up to the assigned slot using `process_slots(state, slot)`. For a skipped epoch boundary slot, such a `head_state` will not be found in any actual block's post state. **Note**: The processed `head_state` for skipped slots is not saved in the `Store`. The current spec defines the general behavior in the validator guide but expects clients to process & save these states using out-of-spec objects. --- ## Problem ### Reorg Attack  #### Chronology - Epoch 9 progresses normally: - $C_9$ is the checkpoint block at Epoch 9. - Enough attestations are included in the chain to justify $C_9$ by the end of the epoch. - $C_{10}$ is the first block in Epoch 10. - Since $C_{10}$ is an epoch boundary block, the FFG votes from Epoch 9 are processed, so $J_{C_{10}} = {C_9}$ - $X$ is the first block in Epoch 10 that includes enough attestations to justify $C_{10}$, so $U_X = C_{10}$. - $Y$ is the last block in Epoch 10. There are no forks in Epoch 10, so $Y$ is clearly the fork choice winner at the end of Epoch 10. - The attacker controls the first slot of Epoch 11 and proposes $Z$. - $Z$ is a descendant of $X$ that competes with $Y$. - Since $Z$ is the first block of Epoch 11, FFG votes from Epoch 10 are counted to update justified & finalized information in the post-state. $J_Z = C_{10}$. #### Reorg After block $Z$ is received, `store.justified_checkpoint` is set to $C_{10}$. Now, the fork choice filters out all the leaves that do not see $C_{10}$ as justified in their post-state, which forks out $Y$ as a viable head. Even though $Y$ was the fork choice winner at the end of Epoch 10, and $Z$ does not have *any* LMD support, $Z$ is the fork choice winner after its slot. Note that $Z$ could just as easily reorg a chain of length 9 instead of only block $Y$ ($X$ has to be the 23rd block for the unrealized justification). ### Deadlock  #### Chronology - Epoch 8 progresses as usual. $C_8$ is the checkpoint block at Epoch 8. - $C_9$ is the checkpoint block at Epoch 9. - $J_{C_9} = C_8$ - During Epoch 9, enough attestations to justify $C_9$ are not included on chain. - $C_{10}$ is the checkpoint block at Epoch 10. - $C_{10}$ is the first block to include enough attestations to justify $C_9$, so $U_{C_{10}} = C_9$. - $X$ is the last block at Epoch 10, and includes enough attestations to justify $C_{10}$, so $U_X = C_{10}$ - The attacker controls the first slot in Epoch 11 - The attacker proposes $Z$ late in the slot, so attesters in that committee vote for "pulled-up" block $X$ - After $Z$ is received by nodes, a reorg similar to the [previous example](https://notes.ethereum.org/SX_8wRoUQkuyrw8Ye4RtPw#Reorg-Attack) is executed - In Epoch 11, enough attestations to justify anything newer than $C_9$ are not included on chain. So, the justified block in $Z$'s chain remains $C_9$. #### Deadlock The first committee in Epoch 11 makes FFG vote $A$. When those attesters vote again in Epoch 12, their fork choice instructs them to make FFG vote $B$, which is clearly a surround vote. --- ## Solutions Proposed solutions are: - **Unrealized Justification Filtering (UJF)**: Filtering based on unrealized justification in the chain, instead of post-state based filtering - Early UJF: Apply UJF as soon as a new unrealized justification is found - On-time UJF: Apply UJF for the epoch only at the end - **Non-highest Justified Filtering (NJF)**: Instead of checking that a leaf's post-state equals the store's highest justified checkpoint, use a different operator than equality - Justified epoch or previous: Justified in leaf's post-state should be either in same or previous epoch as store's justified - Compatible: Justified in leaf's post-state should be in the chain of store's justified ### Unrealized Justification Filtering (UJF) Change the [filteration condition](https://github.com/ethereum/consensus-specs/blame/9f643d8dbf678430bc6707f0e5b914d0bf62545c/specs/phase0/fork-hoice.md#L223-L226) as follows: - `store` keeps track of best unrealized justified checkpoint known yet - Allow the block tree leaves whose unrealized justified checkpoint is the same as the store's unrealized justified checkpoint With this fix in the [reorg example](https://notes.ethereum.org/SX_8wRoUQkuyrw8Ye4RtPw#Reorg-Attack): - `store`'s unrealized justified checkpoint is $C_{10}$ - $U_Y = U_Z = C_{10}$ - $Y$ is not filtered out, and LMD competition between $Y$ & $Z$ is allowed #### Early UJF Update the `store`'s unrealized justified checkpoint upon each block. The following reorg is possible:  - Epoch 9 progresses as usual - $C_{10}$ is the checkpoint block of Epoch 10 - $J_{C_{10}} = C_9$ - $X$ contains *almost* enough attestations in its chain to justify $C_{10}$. - $Y$ is a descendant of $X$ that does not include enough attestations to justify $C_{10}$. - $Z$ is a descendant of $X$ competing with $Y$ that includes enough attestations to justify $C_{10}$, i.e., $U_Z = C_{10}$. $Y$ will be filtered out irrespective of LMD support because it does not have the best possible unrealized justification according to the `store`. #### On-time UJF Update the `store`'s unrealized justified checkpoint only at epoch boundary clock ticks. This prevents the reorg in the [previous example](https://notes.ethereum.org/SX_8wRoUQkuyrw8Ye4RtPw#Early-UJF), but still allows for the following similar reorg (block tree structure & attestations exactly as before): - $Y$'s chain is not filtered out in Epoch 10, and competition is allowed between $Y$ & $Z$ - At the epoch boundary, $Y$'s chain is filtered out if it does not include enough attestations to justify $C_{10}$. This makes such reorg attacks harder, because the honest chain ($Y$'s chain) is given time till the end of the epoch to include new attestations. ### Non-highest Justified Filtering (NJF) Potuz write-up: https://hackmd.io/uDF5kmzQQZmono9PtTaSig?view #### Justified epoch or previous NJF Change the [filteration condition](https://github.com/ethereum/consensus-specs/blame/9f643d8dbf678430bc6707f0e5b914d0bf62545c/specs/phase0/fork-choice.md#L223-L226) to: ```python correct_justified = ( store.justified_checkpoint.epoch == GENESIS_EPOCH or head_state.current_justified_checkpoint.epoch >= store.justified_checkpoint.epoch - 1 ) ``` #### Compatible NJF Change the [filteration condition](https://github.com/ethereum/consensus-specs/blame/9f643d8dbf678430bc6707f0e5b914d0bf62545c/specs/phase0/fork-choice.md#L223-L226) to allow leaves whose `head_state.current_justified_checkpoint` is in the same chain as `store.justified_checkpoint` #### Opinion: (solely) NJF is dangerous Implementing solely NJF allows for a deadlock scenario if a reorg from a chain with a higher justified checkpoint to one with a lower justified checkpoint is executed. This is dangerous because the source epoch of FFG votes will move backwards, while the target epoch can move forward - which is the surround vote condition. Open question: Is it possible to have NJF + additional conditions to prevent source moving backward?