# UNDF: UNDF-2026-000000504
# substrate-0003: npos-elections Node::root visited Vec — O(D²) cycle detection

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in hot loop)
**Speedup:** ~D/2 × at chain depth D (e.g. 50× at D=100, 500× at D=1000)
**Target:** polkadot-sdk (paritytech/polkadot-sdk)
**File:** `substrate/primitives/npos-elections/src/node.rs:123-136`

## Description

`Node::root()` finds the root of a parent-chain (Union-Find style) by following
`parent` pointers. To detect cycles it maintains a `visited: Vec<NodeRef<A>>`
and checks membership with `visited.contains(next_parent)`. Because `Vec::contains`
is an O(N) linear scan, each call to `root()` on a chain of depth D costs O(D²)
total for the visited-membership tests.

`root()` is called twice per `(voter, target)` pair inside `reduce_all()`, which
itself iterates over all assignment edges. For an election with V voters, T targets,
and chains of depth D, the total cost of visited-membership tests is O(V·T·D²).

```rust
// substrate/primitives/npos-elections/src/node.rs:123–136 (DEFECT)
pub fn root(start: &NodeRef<A>) -> (NodeRef<A>, Vec<NodeRef<A>>) {
    let mut parent_path: Vec<NodeRef<A>> = Vec::new();
    let mut visited: Vec<NodeRef<A>> = Vec::new();   // ← O(D) contains() scan

    parent_path.push(start.clone());
    visited.push(start.clone());
    let mut current = start.clone();

    while let Some(ref next_parent) = current.clone().borrow().parent {
        if visited.contains(next_parent) {            // ← O(D) per iteration
            break;
        }
        parent_path.push(next_parent.clone());
        current = next_parent.clone();
        visited.push(current.clone());
    }

    (current, parent_path)
}
```

## Fix

Replace `visited: Vec<NodeRef<A>>` with a `BTreeSet<NodeId<A>>` (since `NodeId`
derives `Ord` but not `Hash`, and `IdentifierT` only requires `Ord`). Keep the
returned `parent_path: Vec<NodeRef<A>>` unchanged — only the lookup structure
changes.

```diff
--- a/substrate/primitives/npos-elections/src/node.rs
+++ b/substrate/primitives/npos-elections/src/node.rs
@@ -18,7 +18,7 @@
 //! (very) Basic implementation of a graph node used in the reduce algorithm.

-use alloc::{rc::Rc, vec::Vec};
+use alloc::{collections::BTreeSet, rc::Rc, vec::Vec};
 use core::{cell::RefCell, fmt};

@@ -120,10 +120,11 @@ impl<A: PartialEq + Eq + Clone + fmt::Debug> Node<A> {
     pub fn root(start: &NodeRef<A>) -> (NodeRef<A>, Vec<NodeRef<A>>) {
         let mut parent_path: Vec<NodeRef<A>> = Vec::new();
-        let mut visited: Vec<NodeRef<A>> = Vec::new();
+        let mut visited_ids: BTreeSet<NodeId<A>> = BTreeSet::new(); // CWE-407 fix: O(log D) membership

         parent_path.push(start.clone());
-        visited.push(start.clone());
+        visited_ids.insert(start.borrow().id.clone());
         let mut current = start.clone();

         while let Some(ref next_parent) = current.clone().borrow().parent {
-            if visited.contains(next_parent) {  // CWE-407: O(D) linear scan
+            if visited_ids.contains(&next_parent.borrow().id) {  // CWE-407 fix: O(log D)
                 break;
             }
             parent_path.push(next_parent.clone());
             current = next_parent.clone();
-            visited.push(current.clone());
+            visited_ids.insert(current.borrow().id.clone());
         }

         (current, parent_path)
     }
```

## Complexity

| | Before | After |
|---|---|---|
| `root()` single call | O(D²) | O(D log D) |
| `reduce_all()` total | O(V·T·D²) | O(V·T·D log D) |

Where D = parent-chain depth, V = voter count, T = target count.

At D=100: 50× speedup. At D=1000: 500× speedup.

## Affected Versions

polkadot-sdk: all versions through 2026-03-29 (latest main).

Defect-Id: SUBSTRATE-003
Severity: MEDIUM
CWE: CWE-407
