-
-
Published
Linked with GitHub
# 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
```