fork_choice: the filtered block tree costs leaves × depth through get_checkpoint_block

未关闭
#811 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 6 天内回复

还没有人认领这个 Issue。

评估

难度
4/5
预计耗时
3-5 天
新手友好度
58/100
Issue 类型
缺陷
描述清晰度
描述清楚
活跃度
活跃
技术栈
rust

调研方向

Start in crates/blockchain/state_transition/src/beacon/fork_choice.rs at is_viable_leaf and read the get_checkpoint_block calls alongside the path stack added by #758. Compare the proposed ancestor and partition_point lookup with filter_block_tree_by_scan; the issue identifies a randomized differential test as coverage. Done means checkpoint lookup no longer walks each leaf's ancestry and the differential test passes.

由索引模型根据 Issue 内容生成。

描述

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 (https://github.com/lambdaclass/ethlambda/pull/746#issuecomment-6533272351) 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 lambdaclass/ethlambda#758, a stack overflow capped that depth; now nothing does.

This is out of scope for lambdaclass/ethlambda#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.

主要语言
Rust
星标
86
派生
34
平均合并
9 天 20 小时
30 天内合并 PR
77

环境准备

从这里开始

  1. 先读完整个 Issue,再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库,在一个分支上完成修改。
  4. 提交 Pull Request,并在描述里引用这个 Issue 编号。

lambdaclass/ethlambda 的其他 Issue

查看 lambdaclass/ethlambda 的全部 Issue

相似的 Issue

更多 Rust Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。