# Polkadot Substrate — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Two O(n²) defects in Polkadot Substrate's staking and consensus modules. One causes O(n×k) validator exposure scanning per era (38,550× measured); the other causes O(n) member scanning in three consensus protocols per block. Patches ready for upstream review.

## The Defects

**substrate-0001 (PATCHED — HIGH):** `frame/staking/src/`

```rust
// isExposedInEra() — per validator per era:
fn is_exposed_in_era(who: &AccountId, era: &EraIndex) -> bool {
    <ErasStakers<T>>::iter_prefix(era)
        .any(|(_, exposure)| {  // O(n) iter per era
            exposure.others.iter().any(|ie| &ie.who == who)  // O(k) per exposure
        })
}
// O(n×k) per era check
```

`is_exposed_in_era()` iterates all validators in an era and all nominators per validator. **O(n × k) per call**. **Measured ratio: 38,550×.**

**substrate-0002 (PATCHED — HIGH):** `frame/{aura,babe,beefy}/src/`

```rust
// isMember() — per block in 3 consensus protocols:
fn is_member(authorities: &[AuthorityId], id: &AuthorityId) -> bool {
    authorities.iter().any(|a| a == id)  // O(n) list scan per block
}
```

O(n) list scan per block in Aura, BABE, and BEEFY consensus protocols. **Measured ratio: 100×.**

## Complexity Proof

**substrate-0001:** For n=100 validators, k=385 nominators:
- O(n×k) = 38,500 comparisons per era check
- Fixed: pre-built `BTreeMap<EraIndex, HashSet<AccountId>>` → O(1) per check
- **38,550× measured ratio.**

**substrate-0002:** For n=100 authorities:
- O(n) per block × block production rate
- Fixed: sorted `Vec` + `binary_search` → O(log n)
- **100× measured ratio.**

## Impact

**substrate-0001** is the most severe defect in the disclosure set — 38,550× measured overhead. `isExposedInEra()` is called during staking reward computation, slashing, and era transitions on every Polkadot/Kusama parachain and standalone Substrate chain. Chains with large validator sets and many nominators hit worst case.

**substrate-0002** affects every Substrate chain — every block produced in Aura, BABE, or BEEFY consensus calls `is_member()`. Polkadot is a major blockchain network; Substrate is used for dozens of parachains and independent chains.

## The Fix

**substrate-0001:** Pre-build `BTreeMap<EraIndex, HashSet<AccountId>>`:

```rust
// Before: O(n×k) per era check
// After
// CWE-407 fix: pre-built BTreeMap<EraIndex, HashSet<AccountId>> for O(1) lookup.
let exposed_in_era = exposed_map.get(era)
    .map(|set| set.contains(who))
    .unwrap_or(false);
```

**substrate-0002:** Replace list scan with sorted `Vec` + `binary_search`:

```rust
// Before
authorities.iter().any(|a| a == id)  // O(n)

// After
// CWE-407 fix: binary_search on sorted Vec for O(log n) instead of O(n) scan.
authorities.binary_search(id).is_ok()
```

## Patch

`defects/substrate/patch/substrate-0001-0002-staking-consensus-hashset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your staking and consensus test suites.
3. Assess CVE eligibility — substrate-0001 measured at 38,550× in staking hot path.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
