fix(blockchain): select proof by marginal coverage when proposer aggregation is off - #505

🤖 Kimi Code Review

Overall Assessment: The PR correctly fixes a liveness issue where smaller attestation subnets could be starved when proposer aggregation is disabled. The logic prioritizes marginal coverage (new voters) over absolute attestation size, aligning non-aggregating behavior with the union-coverage goal of compact_attestations.

Critical Issues

1. Missing build_running_votes definition (Line 120)
   The function build_running_votes(head_state) is invoked but not defined in this diff. Verify that:
   • It correctly scans state.previous_epoch_attestations and state.current_epoch_attestations (or equivalent state fields) to build the HashMap<H256, HashSet<u64>> mapping target roots to validator indices already counted in-state.
   • It handles epoch boundaries correctly (e.g., when the target is from a previous epoch).
   • Its complexity is O(validators) or O(attestations in state), not O(validators²).

Minor Issues & Suggestions

2. Rust MSRV Check (Line 705)
   The use of Option::is_none_or (stabilized in Rust 1.82) requires verifying the project's Minimum Supported Rust Version. If supporting older versions, replace with:

   prior.map_or(true, |voted| !voted.contains(vid))

3. Performance Micro-optimization (Lines 698-710)
   The current implementation collects all indices into groups before selecting the best. This requires iterating the entries twice. While clarity is preferred here, consider that entries could be large (though bounded by MAX_ATTESTATIONS per block). The current approach is acceptable but monitor profiling if block packing becomes a bottleneck.

4. Test Helper Safety (Line 1343)
   In the test keep_best_proof_per_data_prefers_marginal_coverage_over_absolute_size, ensure SingleMessageAggregate::empty(make_bits(&[...])) creates a proof where participant_indices() returns exactly the indices passed to make_bits. If the bit-to-index mapping is offset or compressed differently than make_bits assumes, the test passes for the wrong reason.

Code Quality Positives

• The tie-breaking logic using max_by_key with (marginal, absolute, Reverse(idx)) is idiomatic and correct (Line 706).
• Doc comments at lines 661-670 accurately describe the new behavior.
• The regression tests cover both the "marginal wins" and "fresh target" (absolute count) scenarios.

Consensus Safety

• The change only affects block packing when enable_proposer_aggregation == false, not attestation validation or fork choice rules.
• The algorithm is deterministic given the state, ensuring all honest proposers select the same "best" proof for each AttestationData when presented with the same input attestations and state.

Action Required
Verify the implementation of build_running_votes before merging. If it incorrectly computes the in-state voter set (e.g., misses slashed validators, wrong epoch), the marginal coverage calculation will be wrong, potentially causing liveness failures.

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

🤖 Codex Code Review

1. crates/blockchain/src/block_builder.rs:711 still measures “new” voters only against head_state’s stored votes, not against votes already contributed by earlier selected attestations in the same block. That diverges from both the proposer’s own selection model, which updates projected.current_votes across rounds (block_builder.rs:205), and the STF, which accumulates votes per target.root across all attestations in block order (state_transition/src/lib.rs:338). In enable_proposer_aggregation = false mode, two distinct AttestationData entries can share one target.root; with this patch, the later group can still keep a proof whose voters were already supplied by the earlier group, so the built block may miss a projected justify/finalize threshold. I’d suggest carrying the projected per-target voter map into compaction, or at least maintaining a local running set while iterating groups in first-occurrence order, and adding a regression test for “same target root, different data roots”.

No other material issues stood out in the diff. I couldn’t run cargo test here because the sandboxed environment blocks rustup from creating temp files under /home/runner/.rustup/tmp.

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

🤖 Claude Code Review

I have enough context from reading the diff and surrounding code. Here's my review.

Review: fix(blockchain): select proof by marginal coverage when proposer aggregation is off

Summary

Solid, well-targeted fix. The root cause analysis in the PR description is correct: keep_best_proof_per_data previously picked the survivor by absolute count_ones(), which can permanently starve a small subnet whose votes are the only ones still missing from a target's in-state coverage. Switching the selection key to marginal coverage over running_votes (built from state.justifications_validators) is the right fix and reuses an already-established pattern (score_entry in select_attestations does the same marginal-coverage computation against the same data source). The two new tests directly exercise the bug and the no-regression case.

Correctness

1. Tie-break determinism is sound (block_builder.rs:707-724). The key tuple is (marginal, absolute_count, Reverse(idx)). Since idx is unique per candidate, the tuple is never actually tied, so max_by_key's "last element wins on tie" behavior never triggers — the comparison is fully decided by Reverse(idx), which correctly favors the earliest occurrence. Good, no correctness issue there despite max_by_key's documented tie behavior being an easy footgun.

2. Fresh-target behavior preserved — confirmed by keep_best_proof_per_data_keeps_largest_when_target_is_fresh. When running_votes.get(&target.root) is None, is_none_or makes every participant count as "new," so marginal == absolute, reproducing old behavior. Correct.

3. Snapshot staleness across groups sharing a target root (block_builder.rs:120-121, 711): running_votes is a single snapshot built once via build_running_votes(head_state) before the loop over order. If selected contains two distinct AttestationData groups that share the same target.root (e.g., differing head due to a fork, or differing source), the marginal computation for the second group won't account for voters just "kept" by the first group's chosen proof — each group is scored independently against the frozen state snapshot only. This is strictly better than the old absolute-count behavior (which had the same blind spot), and it's a narrow edge case since groups here already collapsed from the same AttestationData's proof list — but worth a one-line doc callout since select_attestations explicitly does incrementally update current_votes across rounds/targets (block_builder.rs:234-238) while this function does not. Not blocking, just an inconsistency between the two "running votes" semantics worth flagging in the doc comment so a future reader doesn't assume it's already cross-group-aware.

Efficiency (minor)

build_running_votes(head_state) is now computed twice per build_block call when aggregation is disabled: once inside select_attestations (block_builder.rs:208) and again at the call site for keep_best_proof_per_data (block_builder.rs:120). Both walk justifications_roots.len() * validator_count bits. It's probably small in absolute terms (bounded justification window), but since select_attestations already builds this exact map, consider having it return the final projected.current_votes (or exposing build_running_votes's result) so build_block doesn't recompute it. Not a blocker, just avoidable duplicate work in the hot proposer path.

Style / minor

• The doc comment update (block_builder.rs:661-670) is accurate and clear; the "NEW voters" emphasis is a nice touch given the subtlety.
• proof.participant_indices().filter(...).count() is O(participants) per candidate per group, versus the old O(1)-ish count_ones(). Fine given this path only runs when aggregation is off and groups are small (duplicate subnets for one data), but worth noting as the tradeoff being made (correctness for speed) is intentional, not accidental.

Tests

Both new tests are well-targeted:

• keep_best_proof_per_data_prefers_marginal_coverage_over_absolute_size reproduces the exact starvation scenario from the PR description.
• keep_best_proof_per_data_keeps_largest_when_target_is_fresh guards the no-regression path.

Confirmed the PR description states the first test was written test-first and failed before the fix (left: 3, right: 2), which is good practice.

Verdict

Approve with the minor suggestions above (doc note on cross-group snapshot staleness, and optionally dedupe the build_running_votes call). No blocking correctness or security issues found.

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

Greptile Summary

This PR fixes a justification-stalling bug in the non-aggregation proposer path: keep_best_proof_per_data was selecting the proof with the largest absolute participant count, which caused a large subnet already fully recorded in state to keep winning even though it added zero new validators. The fix scores each candidate proof by marginal coverage — new voters relative to the in-state justifications_validators bitmap — so a small subnet holding the only missing votes now correctly beats a larger one already counted in state.

• keep_best_proof_per_data is refactored to collect all same-data proof indices into groups first, then select the winner using a three-level key: marginal new voters → absolute count → earliest occurrence (Reverse(idx)).
• build_running_votes(head_state) is called before the function to supply the per-target-root in-state voter set used for marginal scoring.
• Two new unit tests cover the marginal-coverage preference and the fresh-target no-regression case; the existing build_block integration test continues to pass.

Confidence Score: 4/5

Safe to merge; the change is isolated to the non-aggregation path and is well-covered by targeted unit tests plus the existing integration test.

The core logic is sound and the fix matches the intent described in the PR. build_running_votes is called a second time in the non-aggregation path (already called inside select_attestations), introducing redundant O(V×J) work. The running_votes map is also not updated between data groups that share the same target root, so if two distinct AttestationData entries target the same root, the marginal baseline can over-count new voters for the second group. Both are minor and neither represents a regression from the old code.

crates/blockchain/src/block_builder.rs — specifically the interaction between the build_running_votes call at line 120 and the one already made inside select_attestations.

Flowchart

%%{init: {'theme': 'neutral'}}%%
flowchart TD
    A[build_block] --> B{enable_proposer_aggregation?}
    B -- yes --> C[compact_attestations\nmerge proofs via leanVM]
    B -- no --> D[build_running_votes head_state\nper-target in-state voter set]
    D --> E[keep_best_proof_per_data\nselected entries + running_votes]
    E --> F[Group entries by AttestationData]
    F --> G{Single entry\nper data?}
    G -- yes --> H[Fast path: return as-is]
    G -- no --> I[For each group:\nmax_by_key marginal new voters\n→ absolute count\n→ Reverse idx]
    I --> J[Extract winning proof\nper AttestationData]
    C --> K[Seal block with compacted attestations]
    J --> K
    H --> K

%%{init: {'theme': 'base', 'themeVariables': {"darkMode": true, "background": "#0d1117", "primaryColor": "#21262d", "primaryTextColor": "#e6edf3", "primaryBorderColor": "#8b949e", "lineColor": "#8b949e", "textColor": "#e6edf3", "edgeLabelBackground": "#161b22", "actorBkg": "#21262d", "actorBorder": "#8b949e", "actorTextColor": "#e6edf3", "actorLineColor": "#8b949e", "signalColor": "#8b949e", "signalTextColor": "#e6edf3", "noteBkgColor": "#373320", "noteBorderColor": "#d4a72c", "noteTextColor": "#f0e6c0", "labelBoxBkgColor": "#21262d", "labelBoxBorderColor": "#8b949e", "labelTextColor": "#e6edf3", "loopTextColor": "#e6edf3", "activationBkgColor": "#30363d", "activationBorderColor": "#8b949e"}}}%%
flowchart TD
    A[build_block] --> B{enable_proposer_aggregation?}
    B -- yes --> C[compact_attestations\nmerge proofs via leanVM]
    B -- no --> D[build_running_votes head_state\nper-target in-state voter set]
    D --> E[keep_best_proof_per_data\nselected entries + running_votes]
    E --> F[Group entries by AttestationData]
    F --> G{Single entry\nper data?}
    G -- yes --> H[Fast path: return as-is]
    G -- no --> I[For each group:\nmax_by_key marginal new voters\n→ absolute count\n→ Reverse idx]
    I --> J[Extract winning proof\nper AttestationData]
    C --> K[Seal block with compacted attestations]
    J --> K
    H --> K

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:120-121
**Redundant `build_running_votes` call in the non-aggregation path**

`build_running_votes(head_state)` is now called twice when `enable_proposer_aggregation` is false: once here (line 120) and once inside `select_attestations` at line 208, where the same `head_state` is used to seed `projected.current_votes`. For large validator sets (O(V × J) scan), this doubles the work. The projected state returned by `select_attestations` already contains the fully-built map; threading it out (or threading the initial map in) would avoid the duplicate computation.

### Issue 2 of 2
crates/blockchain/src/block_builder.rs:704-724
**`running_votes` not updated between data groups sharing the same target root**

When two distinct `AttestationData` entries share the same `target.root` (e.g., same target epoch but different `head` or `source`), both groups are scored against the same static `running_votes` baseline. If D1's winning proof covers validators `{3,7}`, those validators still appear as "new" when scoring D2's candidates, because `running_votes` is never incremented between groups. A proof covering `{3,7}` and one covering `{8,9}` look equally marginal, even though `{3,7}` has already been claimed in this block. This is an edge case (different `AttestationData`, same target root) and is not a regression introduced here, but documenting it near the loop would help future maintainers who might otherwise assume the baseline is always current.

_{Reviews (1): Last reviewed commit: "style: restore canonical rustfmt import ..." | Re-trigger Greptile}