You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
fork_choice: the filtered block tree costs leaves × depth through get_checkpoint_block #811
is_viable_leaf (crates/blockchain/state_transition/src/beacon/fork_choice.rs:1989) calls get_checkpoint_block(index, block_root, finalized_checkpoint.epoch) once per leaf of the justified subtree. Each call walks that leaf back to the finalized epoch's start slot. Every head computation therefore costs leaves × depth.
The #746 measurements (#746 (comment)) put that at 74 ms with 14,851 blocks and 451 leaves. During a finality stall the depth grows by a block every slot. Until #758, a stack overflow capped that depth; now nothing does.
This is out of scope for #758, which only replaces the recursion with an explicit stack and keeps the per-leaf check unchanged.
A fix (Pablo's sketch in the #758 review), using the path stack that #758 adds:
If the justified block's slot is at or above the finalized epoch's start slot, every leaf has the same checkpoint block. One get_ancestor from the justified root answers all of them.
Otherwise the checkpoint block lies on path, between the justified root and the leaf. A partition_point by slot over the frames finds it without walking the index.
The randomized differential test against filter_block_tree_by_scan would cover the change.
Activity