russell@unturf.com 82c6916fe2 outreach: reconcile 3 overstate claims with measured wall-clock benches

Each of the 3 briefs flagged by bench_consistency.py as claim > measured
now carries an explicit line pairing the op-count claim with the
measured wall-clock speedup and explaining the residual gap.

  fbneo-0001:     45,000x claim -> + 2,410x wall-clock at N=45k
                  (Python dict vs C++ unordered_map constant factor).
  mercurial-0001: 5,000x claim -> + 50x wall-clock at k=500
                  (Python sim ceiling; bench_google_scale.py projects
                  to Google-scale via ops ratio).
  substrate:      38,550x claim -> + 2,009x wall-clock at N=10k
                  (Python list vs Rust HashSet constant factor).

mercurial-0001 bench also scaled to CASES=[(1000,50), (1000,100),
(1500,200), (1500,350), (1500,500)] to cover k=500 directly.

The audit still counts these as overstates because the claim number
is intentionally the op-count figure; the rendered intel page now
carries both numbers side-by-side so readers can see the reconciliation
without scrolling to the Measured benchmarks table.

2026-04-24 16:11:22 -04:00

3.7 KiB

Raw Permalink Blame History

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/

// 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/

// 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 (op-count at n=100 validators × k=385 nominators per era check).
2,009× measured wall-clock speedup at N=10,000 in the Python complexity-class bench (defects/substrate/bench/results.txt). The residual op-count vs wall-clock gap reflects Python list.__contains__ vs Rust HashSet constant factors; the claim remains the op-count number since the bench cannot model the Rust hasher overhead.

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>>:

// 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:

// 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

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

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

3.7 KiB Raw Permalink Blame History Unescape Escape