java-topology/defects/substrate/substrate-0001-staking-is-exposed-in-era.md

substrate-0001: CWE-407 — staking is_exposed_in_era full table scan (O(V × N))

Severity: HIGH File: substrate/frame/staking/src/pallet/impls.rs:2081 Also: substrate/frame/staking-async/src/pallet/impls.rs:1684 Function: is_exposed_in_era Caller: substrate/frame/fast-unstake/src/lib.rs:569

Description

is_exposed_in_era(who, era) determines whether a nominator is exposed to any validator in a given era. The implementation uses ErasStakers::iter_prefix(era) to scan ALL validators stored for that era, and for each validator iterates ALL nominators in the exposure page.

With V validators and N nominators per validator, a single call is O(V × N). fast-unstake calls this inside unchecked_eras_to_check.iter().any(|e| ...), so for E eras and B stashes per batch the total is O(B × E × V × N).

Polkadot production parameters: V≈300 validators, N≈256 nominators/page, E=28 eras to check. Each on_idle batch processes up to BatchSize stashes. Single call cost: ~300 × 256 = 76,800 storage reads per (stash, era) pair.

Root Cause

// staking/src/pallet/impls.rs:2084
ErasStakers::<T>::iter_prefix(era).any(|(validator, exposures)| {
    validator == *who || exposures.others.iter().any(|i| i.who == *who)
})

No index exists for "which validators was nominator X exposed to in era Y". The code scans the entire era's staker storage.

Fix

For the validator case: use Validators::<T>::contains_key(who) which is O(1). For the nominator case: use ErasStakersOverview or a nominator→validator reverse index if one can be maintained. Short-term: at minimum fast-path the validator check to avoid iterating all exposures when who is a validator.

A complete fix would add a NominatorExposureIndex::<T> storage map keyed (era, nominator) → Vec<validator> populated during ErasStakers writes.

Speedup

Validator fast-path alone eliminates the inner loop for ~1/300 callers. Full reverse index: O(1) per call = 76,800× reduction per (stash, era) pair. Practical fast-unstake batch: 10×–100× on validator-heavy eras.

Status

PATCHED (see patch/substrate-0001-is-exposed-validator-fastpath.patch)