PoS side-chain blocks re-verify the whole branch per arrival: quadratic total work, zero-marginal-cost DoS triggers

[nullPointerEnjoyer]

Summary

check_block_header_impl runs reorganize_in_memory for every PoS block (and the first header of a batch) whose parent is off the main chain, before the arriving block's own consensus check (chainstate/src/detail/chainstateref/mod.rs:683-703). The reorg's connect side is unbounded:

• get_new_chain walks ancestors while !is_block_in_main_chain with no length cap (chainstateref/mod.rs:454-469)
• the connect loop fetches and fully re-verifies every branch block (in_memory_reorg.rs:71-107, connect_transaction per tx in default_strategy.rs:73-90), buffering the entire branch delta + up to 1000 disconnect undos in RAM until consume() (in_memory_reorg.rs:109)
• the reorg-depth check (chainstateref/mod.rs:585-605) bounds only the disconnect side (common-ancestor depth ≤ max_depth_for_reorg); it does not bound branch length above the ancestor
• checkpoints (still enforced past the last configured checkpoint via parent_checkpoint_to_height, common/src/chain/config/checkpoints.rs:81-88) pin the fork ancestor but impose no bound on branch height
• there is no chain-trust pre-filter: the reorg is structurally required to build the state needed to validate PoS at all, and losing-branch blocks are persisted regardless (integrate_block, detail/mod.rs:360-407)

Consequences

1. Accepting an N-block side chain costs O(N²) total. Each new branch block re-verifies all its ancestors. Measured (see below): 0.68s / 3.23s / 9.96s for N = 100/200/400 on an in-memory store; real deployments add LMDB and much heavier blocks.
2. Per-arrival cost grows linearly with branch length. A node near tip pays an O(N) full re-verification for every PoS block that isn't attached to the tip — including every honest orphan/competing branch block.
3. Zero-marginal-cost DoS triggers. Because the reorg precedes the arriving header's consensus check, a consensus-invalid block with a valid parent passes parent/size/checkpoint/depth checks, pays the full reorg, and only then fails (ban score 100 — attacker just reconnects). After building one valid branch (stake-gated, but seal grinding is offline and parallelizable), an attacker can trigger O(N) work on the victim for ~one TCP+Noise connection each, with fresh block ids per trigger (duplicates skip only if previously checked OK). On the P2P path the cost is doubled: preliminary_block_check (p2p/src/sync/peer/block_manager.rs:805) re-runs check_block read-only before process_block re-runs it in the write tx (:842).

Measurements

Reproducible bench (branch bench/pos-sidechain-reorg-growth, chainstate/test-suite/benches/reorg_growth.rs, modeled on the existing pos_reorg bench; in-memory store, instant-difficulty genesis pool, losing side chain with a 10-block main-chain margin; medians of 5 arrivals):

branch length	N=100	N=200	N=400
0	3.47 ms	5.61 ms	11.35 ms
~N/4	4.01 ms	6.88 ms	14.59 ms
~N/2	5.42 ms	10.16 ms	21.52 ms
~3N/4	6.31 ms	16.89 ms	25.25 ms
N−1	7.72 ms	16.20 ms	31.43 ms
garbage block @ N (rejected)	7.90 ms	16.34 ms	34.82 ms

Total time to accept the side chain: 0.68s (N=100) → 3.23s (N=200) → 9.96s (N=400) — quadratic in N. Per-arrival growth is linear (≈0.05 ms/branch-block on top of the disconnect baseline, which itself scales with main-chain height above the fork: 3.5 → 11.4 ms baseline as the main chain grows 110 → 410).

Extrapolation: a branch kept alive at a few thousand blocks (well within max_depth_for_reorg, timestamps only need +1s spacing) makes every trigger cost seconds of single-threaded block-processing on the hot path — serialized against tip advancement — at near-zero attacker cost per trigger.

Possible directions (design decision for maintainers)

• Cache branch state across arrivals: keep the TransactionVerifierDelta/EpochDataCache for a branch tip so subsequent arrivals on the same branch extend it instead of rebuilding from scratch (turns branch growth O(N²)→O(N) and makes garbage triggers O(cached)). Subtleties: invalidation when the main chain moves, epoch-seal data, bounded cache size.
• Configured cap on connect-side length per in-memory reorg as a pure DoS bound (would need a fallback/behavior for over-long valid branches — a consensus-behavior decision).
• Cheap pre-checks before the reorg (timestamp/target ordering; full seal validation fundamentally needs post-reorg state, so this only trims the garbage-trigger cost).

Reproduce

git checkout bench/pos-sidechain-reorg-growth
cargo bench --offline -p chainstate-test-suite --bench reorg_growth