# Fork Choice Store Justified-Finalized Inconsistency ## Desired Invariant (D): `store.justified_checkpoint` must always be a descendant of `store.finalized_checkpoint` ## Claim: **D** does not hold for [on_tick](https://github.com/ethereum/eth2.0-specs/blame/8107d0d58244ab2b61a6fdbdfb71f64147b9ce12/specs/phase0/fork-choice.md#L332) ### Counter-Examples: [`on_tick`](https://github.com/ethereum/eth2.0-specs/blame/8107d0d58244ab2b61a6fdbdfb71f64147b9ce12/specs/phase0/fork-choice.md#L320-L332) ```python def on_tick(store: Store, time: uint64) -> None: ... # Update store.justified_checkpoint if a better checkpoint is known if store.best_justified_checkpoint.epoch > store.justified_checkpoint.epoch: store.justified_checkpoint = store.best_justified_checkpoint # ---------------------------------------- # >>>>>>>> D does not hold here! <<<<<<<< # ---------------------------------------- ``` [`on_block`](https://github.com/ethereum/eth2.0-specs/blame/8107d0d58244ab2b61a6fdbdfb71f64147b9ce12/specs/phase0/fork-choice.md#L338-L383) ```python def on_block(store: Store, signed_block: SignedBeaconBlock) -> None: ... # Update justified checkpoint if state.current_justified_checkpoint.epoch > store.justified_checkpoint.epoch: if state.current_justified_checkpoint.epoch > store.best_justified_checkpoint.epoch: store.best_justified_checkpoint = state.current_justified_checkpoint if should_update_justified_checkpoint(store, state.current_justified_checkpoint): store.justified_checkpoint = state.current_justified_checkpoint # Update finalized checkpoint if state.finalized_checkpoint.epoch > store.finalized_checkpoint.epoch: store.finalized_checkpoint = state.finalized_checkpoint # Potentially update justified if different from store if store.justified_checkpoint != state.current_justified_checkpoint: # Update justified if new justified is later than store justified if state.current_justified_checkpoint.epoch > store.justified_checkpoint.epoch: # ------------------------ # >>>>>>>> CASE 1 <<<<<<<< # ------------------------ store.justified_checkpoint = state.current_justified_checkpoint return # Update justified if store justified is not in chain with finalized checkpoint finalized_slot = compute_start_slot_at_epoch(store.finalized_checkpoint.epoch) ancestor_at_finalized_slot = get_ancestor(store, store.justified_checkpoint.root, finalized_slot) if ancestor_at_finalized_slot != store.finalized_checkpoint.root: # ------------------------ # >>>>>>>> CASE 2 <<<<<<<< # ------------------------ store.justified_checkpoint = state.current_justified_checkpoint ``` #### Case 1: "Update justified if new justified is later than store justified" section In fork choice rule `on_block`: https://github.com/ethereum/eth2.0-specs/blob/dev/specs/phase0/fork-choice.md#on_block It updates `store.justified_checkpoint` if conditions match. (ref: PR #1580) ```python # Update justified if new justified is later than store justified if state.current_justified_checkpoint.epoch > store.justified_checkpoint.epoch: # ------------------------ # >>>>>>>> CASE 1 <<<<<<<< # ------------------------ store.justified_checkpoint = state.current_justified_checkpoint return ``` ##### Illustration ![](https://storage.googleapis.com/ethereum-hackmd/upload_e413a9d65594e1b1a6b6c82294fda849.png) ![](https://storage.googleapis.com/ethereum-hackmd/upload_2009bb7df2572a35508e5636d778bf2f.png) ![](https://storage.googleapis.com/ethereum-hackmd/upload_2abbbb0a87a178a7927af1cdb25115f1.png) ![](https://storage.googleapis.com/ethereum-hackmd/upload_ee94938bfe98a1a008b0cd4808b0c959.png) ##### Test case See [test_new_justified_is_later_than_store_justified](https://github.com/ethereum/eth2.0-specs/blob/b7e65d2403d34df0e5f2b2f38766578d71d5e102/tests/core/pyspec/eth2spec/test/phase0/unittests/fork_choice/test_on_block.py#L265-L282) [L399](https://github.com/ethereum/eth2.0-specs/blob/b7e65d2403d34df0e5f2b2f38766578d71d5e102/tests/core/pyspec/eth2spec/test/phase0/unittests/fork_choice/test_on_block.py#L399) triggered the last line of `on_block` function and updated `store.justified_checkpoint`. But after the another [`on_tick` call (L417)](https://github.com/ethereum/eth2.0-specs/blob/b7e65d2403d34df0e5f2b2f38766578d71d5e102/tests/core/pyspec/eth2spec/test/phase0/unittests/fork_choice/test_on_block.py#L417), the `store.justified_checkpoint.root` was reverted and then it is not in the chain of `store.finalized_checkpoint`. --- #### Case 2: "Update justified if store justified is not in chain with finalized checkpoint" section ```python # Update justified if store justified is not in chain with finalized checkpoint finalized_slot = compute_start_slot_at_epoch(store.finalized_checkpoint.epoch) ancestor_at_finalized_slot = get_ancestor(store, store.justified_checkpoint.root, finalized_slot) if ancestor_at_finalized_slot != store.finalized_checkpoint.root: # ------------------------ # >>>>>>>> CASE 2 <<<<<<<< # ------------------------ store.justified_checkpoint = state.current_justified_checkpoint # In not, we now call it Case 3 else: # ------------------------ # >>>>>>>> CASE 3 <<<<<<<< # ------------------------ # Do nothing ... ``` ##### Test case See [test_new_finalized_slot_is_not_justified_checkpoint_ancestor](https://github.com/ethereum/eth2.0-specs/blob/b7e65d2403d34df0e5f2b2f38766578d71d5e102/tests/core/pyspec/eth2spec/test/phase0/unittests/fork_choice/test_on_block.py#L426-L438) [L491](https://github.com/ethereum/eth2.0-specs/blob/b7e65d2403d34df0e5f2b2f38766578d71d5e102/tests/core/pyspec/eth2spec/test/phase0/unittests/fork_choice/test_on_block.py#L491) triggered the last line of `on_block` function and updated `store.justified_checkpoint`. But after the another [`on_tick` call (L507)](https://github.com/ethereum/eth2.0-specs/blob/b7e65d2403d34df0e5f2b2f38766578d71d5e102/tests/core/pyspec/eth2spec/test/phase0/unittests/fork_choice/test_on_block.py#L507), the `store.justified_checkpoint.root` was reverted and then it is not in the chain of `store.finalized_checkpoint`. ##### Illustration ![](https://storage.googleapis.com/ethereum-hackmd/upload_d82282994e9fb247950772e5a6d6b515.png) ![](https://storage.googleapis.com/ethereum-hackmd/upload_1bd91229a99917c92fc435801304a665.png) ![](https://storage.googleapis.com/ethereum-hackmd/upload_0f12296e5e75f9c22b0b879e16ac3cda.png) ![](https://storage.googleapis.com/ethereum-hackmd/upload_6be67fa12ca610bf9293a50651b93cdc.png) --- #### Case 3: if store justified is in chain with finalized checkpoint `store.justified_checkpoint` was unchanged after finality checkpoint was updated. (The `store.justified_checkpoint` update checks were applied in the previous code block in `on_block`). ---- ## Solution discussion ### Solution 1: update `store.best_justified_checkpoint` in Case 1 and Case 2 That is: ```python # Update justified if new justified is later than store justified if state.current_justified_checkpoint.epoch > store.justified_checkpoint.epoch: # ------------------------ # >>>>>>>> CASE 1 <<<<<<<< # ------------------------ store.justified_checkpoint = state.current_justified_checkpoint store.best_justified_checkpoint = store.justified_checkpoint return ``` ```python # Update justified if store justified is not in chain with finalized checkpoint finalized_slot = compute_start_slot_at_epoch(store.finalized_checkpoint.epoch) ancestor_at_finalized_slot = get_ancestor(store, store.justified_checkpoint.root, finalized_slot) if ancestor_at_finalized_slot != store.finalized_checkpoint.root: # ------------------------ # >>>>>>>> CASE 2 <<<<<<<< # ------------------------ store.justified_checkpoint = state.current_justified_checkpoint store.best_justified_checkpoint = store.justified_checkpoint return ``` ### Solution 2: add checks in the `on_tick` function ```python def on_tick(store: Store, time: uint64) -> None: ... # Update store.justified_checkpoint if a better checkpoint is known if store.best_justified_checkpoint.epoch > store.justified_checkpoint.epoch: # Check if store.best_justified_checkpoint is on the store.finalized_checkpoint chain finalized_slot = compute_start_slot_at_epoch(store.finalized_checkpoint.epoch) ancestor_at_finalized_slot = get_ancestor(store, store.best_justified_checkpoint.root, finalized_slot) if ancestor_at_finalized_slot == store.finalized_checkpoint.root: store.justified_checkpoint = store.best_justified_checkpoint ```