fix: tiered attestation scoring for block building

[MegaRedHand]

Description / Motivation

Replaces the target.slot ASC sort + STF-advance fixed point in build_block with a tiered greedy modeled on Prysm's sortByProfitability. The previous loop committed attestations in arbitrary chain order and re-ran the STF after each batch to detect justification advance, which:

• Doesn't prioritize attestations that finalize or justify under the MAX_ATTESTATIONS_DATA = 16 cap.
• Pays for a full STF execution every outer iteration.
• Has no signal for "this entry adds marginal voters worth packing" — it's all-or-nothing per data entry.

The new selection algorithm scores each candidate against a projected post-state and picks the highest-tier entry per round.

Scoring tiers

Tier	Predicate	Notes
1	applying the entry finalizes its source	3SF-mini: no slot in (source.slot, target.slot) is still justifiable per slot_is_justifiable_after, so source and target are consecutive justified checkpoints in the projected post-state
2	applying the entry justifies its target	total voters (prior + new) crosses ⅔
3	adds marginal new voters	not enough to cross ⅔, but contributes toward future rounds

Within a tier: more new_voters wins, then smaller target_slot (older chain progress first), then smaller att_slot, then data_root for determinism.

What Changed

Three commits on this branch:

Commit	Subject
6336ce7	feat(blockchain): tiered attestation scoring for block building
5ccc938	refactor(blockchain): simplify attestation scoring helpers
d59d41b	refactor(blockchain): extract block_builder module

Key code:

• New module crates/blockchain/src/block_builder.rs containing build_block, select_attestations, pick_best_candidate, score_entry, entry_passes_filters, the EntryScore / ChainContext / ProjectedState types, plus compact_attestations and extend_proofs_greedily (moved out of store.rs).
• build_running_votes(state) deserializes the flattened state.justifications_validators bitlist into HashMap<H256, HashSet<u64>> — the analog of Prysm/Lighthouse's participation flags. Selection seeds from this and updates it incrementally.
• Projection of justified_slots and finalized_slot happens in-loop after each tier 1/2 selection so dependent attestations (whose source is the just-justified slot) become eligible on the next round without running the STF.
• The final STF still runs once on the assembled block to seal state_root and validate that the proposed block is sound.

Correctness / Behavior Guarantees

• Final STF unchanged: process_slots + process_block still run on the selected attestations before state_root is set. Any divergence between projection and the actual STF produces an error here.
• Filter invariants preserved: entry_passes_filters enforces the same predicates the previous loop did (head known, source justified, chain-match, target not already justified) plus the genesis self-vote bypass.
• 3SF-mini finalize predicate: tier 1 elevation requires (source.slot + 1..target.slot).all(|s| !slot_is_justifiable_after(s, projected_finalized_slot)) — matches try_finalize exactly, including the implicit "source and target must be consecutive justified checkpoints" constraint (any already-justified slot between them is by construction still justifiable).
• Cap preserved: still bounded by MAX_ATTESTATIONS_DATA = 16 distinct AttestationData entries.
• Genesis self-vote handling preserved: (source.slot == 0 && target.slot == 0) entries are scored as tier 3 (fork-choice only) and bypass the "target already justified" filter.

Tests Added / Run

• All existing tests pass: 20 unit tests in ethlambda-blockchain (incl. build_block_caps_attestation_data_entries and build_block_absorbs_older_but_justified_source), 84 fork-choice spec tests, 11 signature spec tests. Full make test = 415 passed / 0 failed / 6 ignored.
• Tests moved alongside the code into block_builder::tests.

Related Issues / PRs

• Modeled after Prysm's proposerAtts.sortByProfitability in beacon-chain/operations/attestations/.
• 3SF-mini reference for justifiability deltas: https://github.com/ethereum/research/blob/c003fe1c1a785797e7b53e3cbf9569b989be6e93/3sf-mini/consensus.py#L52-L54

Verification Checklist

• Ran make fmt — clean
• Ran make lint (clippy with -D warnings) — clean
• Ran cargo test --workspace --release — all passing

[github-actions]

🤖 Codex Code Review

1. High: the proposer-side projection can now treat attestations as justifying/finalizing even when the real STF will reject them. In crates/blockchain/src/store.rs and crates/blockchain/src/store.rs, the new selector no longer checks target.slot > source.slot or slot_is_justifiable_after(target.slot, finalized_slot), but is_valid_vote still requires both in crates/blockchain/state_transition/src/lib.rs and crates/blockchain/state_transition/src/lib.rs. That means a non-genesis vote with target.slot == source.slot is scored as tier 1, and an unjustifiable target can be projected as justified/finalized in crates/blockchain/src/store.rs. Once that happens, later entries can be “unlocked” against a projected state the STF will never reach, so block packing can diverge and waste the 16-entry budget. I’d mirror the exact is_valid_vote predicates before scoring or mutating the projected state.

2. Medium: this adds a fairly heavy proposer-path hot loop. crates/blockchain/src/store.rs rebuilds per-root voter HashSets from SSZ state every proposal, then crates/blockchain/src/store.rs rescans all candidates each round, and crates/blockchain/src/store.rs clones the current voter set per candidate before unioning proofs. In a large attestation pool this is a lot of heap churn for a per-slot path. Using bitsets/bitlists or caching per-target coverage would make this much cheaper and more predictable.

I couldn’t run the Rust tests here: cargo/rustup attempted a toolchain sync, but the environment has no network access and the default rustup temp path is read-only.

---

Automated review by OpenAI Codex · gpt-5.4 · custom prompt

[github-actions]

🤖 Claude Code Review

Now I have enough of the diff to write a thorough review. Let me produce the review output.

---

PR 382 Review: Tiered Attestation Scoring for Block Building

Overview

This PR replaces the old target.slot ASC sort + STF-per-iteration fixed-point loop in build_block with a tiered greedy selection algorithm modeled on Prysm's sortByProfitability. It also extracts the block building logic into a dedicated block_builder module. The primary gains are:

• Performance: eliminates O(n_iterations × STF_cost) — the old loop ran a full process_slots + process_block after every batch; the new algorithm projects checkpoint advancement in-loop and runs the STF exactly once.
• Correctness: the old approach had no signal for "this attestation finalizes its source"; it only learned about justification/finalization after the fact. The new tiers prioritize finalization-critical attestations under the 16-entry cap.

The refactoring is generally clean and well-motivated.

---

Correctness Analysis

Projection vs. STF consistency

The tiered algorithm projects justification/finalization incrementally (ProjectedState) and uses the final process_block call as a validation backstop. This is sound: any divergence between the projection and the actual STF produces an error from build_block, not a silent consensus failure. The predicates used for tier-1 and tier-2 elevation (is_slot_justified, slot_is_justifiable_after) match those in try_finalize / process_attestation, so the projection should rarely diverge from the real STF.

Tier 1 finalization predicate (score_entry:364-366)

let finalizes = crosses_2_3
    && (att_data.source.slot + 1..att_data.target.slot)
        .all(|s| !slot_is_justifiable_after(s, projected_finalized_slot));

When source.slot + 1 >= target.slot (adjacent slots), the range is empty and all returns true — so a supermajority attestation spanning consecutive slots (slot N → slot N+1) is correctly elevated to tier 1. This matches the 3SF-mini consecutiveness requirement.

new_voters consistency with extend_proofs_greedily

score_entry computes new_voters as the union of all validators across all proofs that aren't in prior_voters. extend_proofs_greedily starts from an empty covered set and greedily adds proofs until none add coverage. A validator appearing in any proof is guaranteed to end up in covered (some proof selecting it will be chosen eventually). So prior_count + new_voters.len() correctly represents the post-selection total. The consistency here is non-obvious but holds.

---

Potential Issues

Potential Issue 1 — build_running_votes: HashMap overwrite on duplicate roots (block_builder.rs:422-435)

for (i, root) in state.justifications_roots.iter().enumerate() {
    // ...
    votes.insert(*root, voters);  // overwrites if root appears twice
}

If justifications_roots ever contains duplicate roots (two separate slots justifying the same root), only the last iteration's voter set survives. The correct behavior would be to union the voter sets. In practice this is unlikely, but it would silently under-count votes for that root and could prevent a tier-2 elevation for a genuinely justified target.

Suggested fix:

votes.entry(*root).or_default().extend(voters);

Potential Issue 2 — Missing test for tier 1 finalization elevation

There are tests for the cap (build_block_caps_attestation_data_entries) and for gap-closing (build_block_absorbs_older_but_justified_source), but no test exercises the tier 1 path — the case where selecting an attestation should advance the projected finalized_slot and unlock dependent attestations in subsequent rounds. This is the most novel and critical new logic. A test with a chain where one attestation finalizes slot N and a second depends on that finalization to become eligible would significantly increase confidence.

Potential Issue 3 — Validator count = 0 edge case (score_entry:359)

let crosses_2_3 = 3 * total >= 2 * validator_count;

If validator_count = 0, this is always true, scoring every attestation with new voters as tier 1 or 2. This only matters in tests or degenerate state. The existing test helpers use State::from_genesis(1000, vec![]) which has zero validators — compact_attestations_* tests are safe because they never reach score_entry, but worth keeping in mind if new tests call select_attestations directly on a zero-validator state.

Potential Issue 4 — pick_best_candidate iterates already-filtered entries every round

The pick_best_candidate function rescans all aggregated_payloads (including already-processed entries) on every round, relying on the processed_data_roots.contains() short-circuit. With MAX_ATTESTATIONS_DATA = 16 rounds and a large payload pool, this is O(16 × n) hash lookups — acceptable but could be tightened by draining processed entries from an auxiliary structure. Not a blocker at current scale.

---

Minor / Style Notes

• block_builder.rs:80: The expect("attestation count exceeds limit") on the try_into() is guarded by the MAX_ATTESTATIONS_DATA round cap, so it cannot panic under correct logic. A brief comment explaining the invariant would help future readers who see a bare expect.

• lib.rs: pub mod block_builder makes the module externally visible, which is correct since PostBlockCheckpoints is pub and needs to be accessible to callers outside the crate. Consider whether PostBlockCheckpoints should be pub(crate) instead; looking at the old store.rs it was already pub, suggesting an external caller (likely in bin/ethlambda) uses it.

• The validator_indices import was removed from store.rs but it was used in the old trace-logging block. Confirmed: the new code omits that trace block, so the removal is clean.

---

Summary

The algorithm is correct, the STF safety net is good design, and the module extraction is clean. The main actionable items before merging:

1. Fix build_running_votes duplicate-root handling (use entry().or_default().extend() instead of insert).
2. Add a tier 1 test: construct a state where attestation A finalizes its source, and attestation B targets that source — verify B becomes eligible only after A is selected and the projected finalized slot advances.

Everything else is minor. The performance improvement (eliminating the inner STF loop) is significant and the projection invariants hold.

---

Automated review by Claude (Anthropic) · sonnet · custom prompt

[greptile-apps]

Greptile Summary

This PR replaces the old build_block STF-per-round loop in store.rs with a tiered greedy attestation selection algorithm (modelled on Prysm's sortByProfitability) extracted into a new block_builder module. The new algorithm scores each candidate against a projected post-state, avoiding full STF re-runs per round while still running the STF once at the end to seal state_root.

• New module block_builder.rs contains build_block, select_attestations, pick_best_candidate, score_entry, entry_passes_filters, compact_attestations, extend_proofs_greedily, and supporting types (EntryScore, ChainContext, ProjectedState, PostBlockCheckpoints).
• build_running_votes seeds a per-target-root voter map from state.justifications_validators so each scoring round knows which validators have already contributed, enabling incremental supermajority tracking without re-running the STF.
• Projection is updated incrementally: after a tier-1 or tier-2 selection the projected_justified_slots / projected_finalized_slot advance so dependent entries become eligible on the next round without re-running the STF.

Confidence Score: 4/5

Safe to merge with two minor hardening suggestions; the final STF run acts as a correctness backstop for any projection divergence.

The tiered greedy algorithm is logically sound: new_voters deduplication via HashSet, incremental projection updates, and the finalizes predicate all match the 3SF-mini spec. The two suggestions are defensive quality improvements rather than fixes for observable wrong behavior.

crates/blockchain/src/block_builder.rs — the score_entry and tier-1 projection code near lines 197–202 and 352–353 are worth a second look for the guards described in the review comments.

Important Files Changed

Filename	Overview
crates/blockchain/src/block_builder.rs	New 1084-line module containing the tiered greedy attestation selection algorithm. Core logic is sound: new_voters deduplication, projection updates, and finalization predicate all appear correct. Two minor guards are worth adding (zero-validator-count supermajority check and a debug_assert for tier-1 monotonicity).
crates/blockchain/src/store.rs	Old build_block, compact_attestations, extend_proofs_greedily, and union_aggregation_bits functions removed; now delegates to block_builder module. Remaining store logic is unchanged and looks clean.
crates/blockchain/src/lib.rs	Adds pub mod block_builder declaration. Trivial, correct change.

Flowchart

%%{init: {'theme': 'neutral'}}%%
flowchart TD
    A[build_block] --> B[select_attestations]
    B --> C[build_running_votes\nseeds current_votes\nfrom state.justifications_validators]
    C --> D{Round loop\nup to MAX_ATTESTATIONS_DATA=16}
    D --> E[pick_best_candidate\niterate aggregated_payloads]
    E --> F{entry_passes_filters}
    F -- fail --> G[trace skipped]
    G --> E
    F -- pass --> H[score_entry\ncompute new_voters\ntier 1/2/3]
    H -- zero new_voters --> G
    H -- scored --> I[compare ordering_key\npick best]
    I --> D
    D -- best candidate found --> J[extend_proofs_greedily\ngreedy proof selection]
    J --> K[update projected.current_votes\nwith new_voters]
    K --> L{tier <= 2?}
    L -- yes --> M[set_justified target.slot\nremove target bucket]
    M --> N{tier == 1?}
    L -- no --> D
    N -- yes --> O[shift_window by delta\nadvance finalized_slot]
    O --> D
    N -- no --> D
    D -- no candidate / cap hit --> P[compact_attestations\nmerge same-data proofs]
    P --> Q[process_slots + process_block\nSTF seals state_root]
    Q --> R[return Block + PostBlockCheckpoints]

Loading

Prompt To Fix All With AI

Fix the following 2 code review issues. Work through them one at a time, proposing concise fixes.

---

### Issue 1 of 2
crates/blockchain/src/block_builder.rs:352-353
`crosses_2_3` is trivially `true` when `validator_count == 0` because `3 * total >= 0` holds for any non-negative `total`. A chain with zero validators is not a production scenario, but tests that construct a `State` with an empty validator set (e.g. `State::from_genesis(t, vec![])`) will silently mis-tier every entry with at least one participant as tier 2 or tier 1, rather than tier 3. Adding an explicit guard makes the invariant visible and future-proofs unit tests that intentionally use small validator sets.

```suggestion
    let total = prior_count + new_voters.len();
    let crosses_2_3 = validator_count > 0 && 3 * total >= 2 * validator_count;
```

### Issue 2 of 2
crates/blockchain/src/block_builder.rs:197-202
The tier-1 branch silently accepts `att_data.source.slot < projected.finalized_slot` via `saturating_sub`, which would clamp `delta` to zero while still overwriting `projected.finalized_slot` with the smaller (incorrect) source slot. The combination of `entry_passes_filters` and the `finalizes` range check guarantees `source.slot >= projected.finalized_slot` whenever tier == 1, but this invariant is invisible at the call site. A `debug_assert` makes the guarantee explicit and will cheaply catch regressions if the tier-assignment logic ever changes.

```suggestion
        if score.tier == 1 {
            let new_finalized = att_data.source.slot;
            debug_assert!(
                new_finalized >= projected.finalized_slot,
                "tier-1 finalization must be monotone: new={new_finalized} < current={}",
                projected.finalized_slot
            );
            let delta = new_finalized.saturating_sub(projected.finalized_slot) as usize;
            justified_slots_ops::shift_window(&mut projected.justified_slots, delta);
            projected.finalized_slot = new_finalized;
        }
```

_{Reviews (2): Last reviewed commit: "Merge branch 'main' into build-block-sco..." | Re-trigger Greptile}

[github-actions]

🤖 Kimi Code Review

Overall this is a high-quality refactor that improves separation of concerns and replaces the iterative STF-loop with a more efficient tiered greedy algorithm. The logic for 3SF-mini justification/finalization projection appears correct.

Critical Issues

None.

High Priority

1. Determinism robustness in pick_best_candidate (line 192-237)
   The function iterates over a HashMap to find the minimum score. While the ordering_key tuple includes data_root as a final tiebreaker (ensuring deterministic ordering), relying on HashMap iteration order is fragile. If the comparison logic is ever modified incorrectly, the proposer could produce different blocks on re-runs with the same inputs, causing consensus failures.
   Suggestion: Collect candidates into a Vec upfront or use a BTreeMap keyed by ordering_key to make the selection algorithm explicitly deterministic independent of tiebreaker logic.

2. Performance: cloning large XMSS proofs (line 521)
   extend_proofs_greedily clones AggregatedSignatureProof (potentially 253KB each per the test) when pushing to selected. These are cloned again during compact_attestations processing. For a block with 16 attestations each aggregating multiple proofs, this adds significant memory pressure.
   Suggestion: Consider using Arc<AggregatedSignatureProof> in the intermediate selection structures to share ownership without cloning the underlying proof data.

Medium Priority

3. Panic risk in union_aggregation_bits (line 547)
   AggregationBits::with_length(max_len).expect(...) panics if max_len exceeds the protocol limit. While max_len is derived from existing bitfields (which should be valid), defensive validation would be safer.
   Suggestion: Return a Result or use ? operator instead of expect, propagating as StoreError::InternalError or similar.

4. Inefficient scanning in pick_best_candidate (line 197)
   The function scans all aggregated_payloads including already-processed entries

---

Automated review by Kimi (Moonshot AI) · kimi-k2.5 · custom prompt

[github-actions]

🤖 Codex Code Review

1. crates/blockchain/src/block_builder.rs:285-314 and :182-201 project justification/finalization from a weaker filter than the real STF. entry_passes_filters() no longer mirrors state_transition::is_valid_vote(): it omits both target.slot > source.slot and slot_is_justifiable_after(target.slot, projected_finalized_slot). Because select_attestations() then marks any tier-1/2 candidate as justified/finalized in the projected state, an invalid attestation can unlock dependent attestations in later rounds even though process_block() will ignore it. That is a real 3SF-mini correctness/liveness regression in the fixed-point block builder.

2. crates/blockchain/src/block_builder.rs:325-378 and :539-590 score candidates by marginal voters relative to current_votes[target_root], but extend_proofs_greedily() starts from an empty covered set. For targets that already have many prior voters, this can select large proofs that add zero marginal value before the proof that actually contributes new voters. After compaction, those redundant participants are re-aggregated into the final XMSS proof, inflating proof size and block payloads unnecessarily. covered should be seeded from the already-counted voter set, or the marginal voter set from score_entry() should drive proof selection directly.

I did not run cargo test: the environment failed before compilation because rustup could not create temp files under /home/runner/.rustup/tmp (Read-only file system). Aside from the two points above, the module extraction itself looks clean and the surrounding tests were moved over sensibly.

---

Automated review by OpenAI Codex · gpt-5.4 · custom prompt

[github-actions]

🤖 Claude Code Review

Now I have a thorough understanding of the changes. Let me write the review.

---

Review: PR #382 — Tiered Attestation Scoring for Block Building

Overall: The algorithm is well-conceived and the implementation is correct. The refactoring to block_builder.rs is clean, the incremental projection avoids N full-STF executions, and the final STF backstop catches any divergence. A few points below, roughly ordered by significance.

---

Item 1 — Non-deterministic proof selection in extend_proofs_greedily (medium)

remaining_indices is a HashSet<usize>, so iteration order is unspecified. When two proofs tie on uncovered validator count, max_by_key returns whichever the hasher serves up first.

// block_builder.rs, extend_proofs_greedily
let mut remaining_indices: HashSet<usize> = (0..proofs.len()).collect();

let best = remaining_indices
    .iter()
    .map(|&idx| { ... })
    .max_by_key(|&(_, count)| count);

This doesn't affect total coverage (the union is identical regardless of pick order) and doesn't affect block validity. It does mean two independent re-runs of the proposer on the same payload can produce structurally different proof selections — relevant if you ever need replay-determinism for debugging or test snapshots.

Fix: Use a Vec<usize> sorted by index as the remaining set, or add a secondary tiebreak on idx in the max_by_key:

.max_by_key(|&(idx, count)| (count, std::cmp::Reverse(idx)))

---

Item 2 — score_entry computes new_voters across all proofs, extend_proofs_greedily may omit redundant proofs (verify invariant holds) (low, verify)

score_entry builds new_voters as the union of ALL proofs' participants minus prior voters:

// block_builder.rs ~L347–353
for proof in proofs {
    for vid in proof.participant_indices() {
        if prior_voters.is_none_or(|prior| !prior.contains(&vid)) {
            new_voters.insert(vid);
        }
    }
}

Then, after selection, the full new_voters set is written into current_votes[target_root] even though extend_proofs_greedily may omit proofs that add zero new coverage. This is safe because the greedy loop terminates exactly when all participants in new_voters are covered — so the union of selected proofs' participants always equals new_voters. The implicit invariant is:

the coverage achieved by extend_proofs_greedily == union of all proofs' participants minus prior_voters

This holds (greedy stops at zero-new-coverage), but it is not stated anywhere in the code. A short comment would prevent future confusion when someone modifies either function.

---

Item 3 — No test for cascading round-dependency (low, coverage gap)

The PR description specifically highlights: "Projection of justified_slots and finalized_slot happens in-loop after each tier 1/2 selection so dependent attestations become eligible on the next round."

No test exercises this path. A test where:

• Round 1 selects an attestation that justifies slot S (tier 2 projection)
• Round 2 selects an attestation whose source = S (which would have been filtered as source_not_justified before the round-1 projection)

...would verify the primary motivation for incremental projection over the old single-pass approach.

---

Item 4 — pick_best_candidate tracks two parallel Options (minor, clarity)

// block_builder.rs ~L226–227
let mut best: Option<(H256, EntryScore, HashSet<u64>)> = None;
let mut best_key: Option<(u8, std::cmp::Reverse<usize>, u64, u64, H256)> = None;

best_key is always the ordering_key of best. You could drop best_key and derive it on comparison:

if best.as_ref().is_none_or(|(br, bs, _)| candidate_key < bs.ordering_key(*br)) {
    best = Some((*data_root, score, new_voters));
}

Minor, but removes the mental overhead of keeping them in sync.

---

Item 5 — Tier ordering: finalizes-implies-justifies is correctly handled (confirm correctness)

The code gates tier 1 inside else if finalizes only after the !crosses_2_3 path is taken by tier 3:

let tier = if is_genesis_self_vote(att_data) || !crosses_2_3 {
    3
} else if finalizes {
    1
} else {
    2
};

And the projection update applies tier-2 updates first, then tier-1 finalization:

if score.tier <= 2 {  // tier 1 or 2: justify target
    justified_slots_ops::extend_to_slot(...);
    justified_slots_ops::set_justified(...);
    projected.current_votes.remove(&target_root);
}
if score.tier == 1 {  // additionally finalize source
    justified_slots_ops::shift_window(...);
    projected.finalized_slot = new_finalized;
}

This ordering is correct: justifying the target before shifting the window preserves the relative indices used by set_justified. The shift_window then advances the base, keeping target.slot accessible in the new window as long as target.slot - source.slot < window_size — which holds for any consecutive justified checkpoints in practice.

---

Item 6 — build_running_votes length assumption (minor, latent)

// block_builder.rs ~L427–430
for j in 0..validator_count {
    if state.justifications_validators.get(i * validator_count + j) == Some(true) {
        voters.insert(j as u64);
    }
}

If state.justifications_validators.len() < (i + 1) * validator_count, the get(...) returns None (treated as false). This silently under-counts voters rather than panicking. In practice, the SSZ serialization guarantees the correct length, so this is defensive-by-accident. A debug_assert on the length would make the invariant explicit, but it's low priority.

---

Item 7 — Removed per-round trace diagnostics (informational)

The old loop emitted iter_selected, iter_skipped, and advanced on every inner loop pass. The new code emits only selected per winner and converged on exit. The new logs are cleaner for production, but if you ever need to debug a stall you've lost the per-round candidate breakdown. Consider keeping the round number in the selected trace line (the loop already has _round):

trace!(
    round = _round,      // add this
    tier = score.tier,
    ...
    "selected"
);

---

Summary

• Items 1–2: worth a fix before merge; neither is a correctness bug, but Item 1 can cause surprising replay behavior and Item 2 hides a subtle coupling.
• Items 3–4: low-cost improvements (one test, one variable removed).
• Items 5–7: informational / confirmed correct.

The algorithm itself — incremental projection, greedy tier selection, final STF backstop — is sound.

---

Automated review by Claude (Anthropic) · sonnet · custom prompt