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

Aberta
#811 0 comentários 0 reações 0 responsáveis Ver no GitHub

Mantenedores costumam responder em até 6 dias

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
4/5
Tempo estimado
3-5 dias
Facilidade para iniciantes
58/100
Tipo de issue
Bug
Clareza
Claramente especificada
Status de atividade
Ativa
Stack de tecnologia
rust
Domínio
backend, performance

Direção de pesquisa

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.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

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.

Linguagem predominante
Rust
Estrelas
86
Forks
34
Merge médio
9d 20h
PRs com merge (30d)
77

Preparar o ambiente

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de lambdaclass/ethlambda

Todas as issues de lambdaclass/ethlambda

Issues semelhantes

Mais issues de Rust

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.