engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/defects/bitcoin/patch/CLEAN.md
russell@unturf.com a7b08c7e05 blockchain-p2p: solang/tor/bitcoin/transmission/libtorrent/solc CWE-407 scan 
solang-0001: add_external_functions emits_events Vec::contains O(F×E²) MEDIUM
  src/sema/external_functions.rs:93-103 — dedup accumulator Vec uses linear scan
  for each event per function; fix: IndexSet (already a dependency) for O(1) dedup

tor/bitcoin/transmission/libtorrent/solc: CLEAN markers added after full scan
  Tor: nodes_have_common_family_id F=1-3 IDs, O(N×F²) ≈ O(9N), not scalable issue
  Bitcoin: TxGraph/sets throughout, no linear scan in hot paths
  Transmission: bitfields for piece tracking, sorted binary search for string table
  libtorrent: sorted vectors with lower_bound, DHT uses binary search on results
  solc: unordered_set/set throughout OverrideChecker, SMTEncoder, FunctionCallGraph
2026-03-29 19:49:57 -04:00

1.4 KiB
Raw Permalink Blame History

CLEAN — Bitcoin Core

Scanned 2026-03-29 for CWE-407 (algorithmic complexity: O(N²) linear membership tests, O(2^D) diamond recursion).

Scope

  • src/txmempool.cpp / src/txmempool.h — mempool ancestor/descendant tracking
  • src/node/mini_miner.cpp — MiniMiner block template builder
  • src/policy/packages.cpp — package deduplication
  • src/net.cpp — peer connection tracking

Findings

  • Mempool ancestor/descendant tracking — uses CTxGraph::GetAncestors/GetDescendants backed by std::set and hash maps (O(log N) per lookup). CLEAN.
  • MiniMiner::DeleteAncestorPackage — std::find on m_entries vector to locate an ancestor before erase. m_entries is a sorted vector used purely for O(N log N) re-sort each iteration; the O(|ancestors|) find per removal is dominated by the O(E log E) sort already on that path. m_entries_by_txid (hash map) handles fast txid lookup. Effective complexity is O(E log E) per iteration. Not a scalable O(N²). CLEAN.
  • policy/packages.cpp — uses std::unordered_set<COutPoint> for input dedup. CLEAN.
  • net.cpp m_onion_binds — constant-size list (number of configured bind addresses). CLEAN.
  • Address management — uses bucket-based hash tables throughout. CLEAN.

Result: No actionable CWE-407 defects. Bitcoin Core uses hash-based sets and sorted structures for all scalable membership tests.