sp-trie Crate Security and Correctness Review

[n13]

sp-trie Crate Security and Correctness Review

Critical Issues

1. ESCAPE_HEADER collides with valid node first bytes

[node_codec.rs](primitives/trie/src/node_codec.rs) line 88 sets ESCAPE_HEADER: Option<u8> = Some(0x01), and [lib.rs](primitives/trie/src/lib.rs) line 820 defines the constant. This value is used by trie_db in compact proof decoding to distinguish escaped/placeholder nodes from real encoded nodes by checking the first byte.

With the new 8-byte LE header format, the nibble count occupies the low bytes. Any node with nibble_count % 256 == 1 (e.g. 1, 257, 513...) has 0x01 as its first byte. This collides with the escape header, meaning valid branch or leaf nodes with these nibble counts could be misidentified as escape sequences during compact proof processing.

// lib.rs:820 - ESCAPE_COMPACT_HEADER = 0x01
// But Branch(true, 1) encodes to [0x01, 0x00, ..., 0x10] - first byte is 0x01!

Fix: Choose an escape byte that cannot appear as the first byte of any valid node. Since nibble counts are stored in the low 32 bits and type codes in bits 60-63, a value like 0x00 is already taken by Null. Consider using a byte that falls in the unused bits 32-59 range, e.g. a value where the low byte is a non-nibble-count sentinel. Or set ESCAPE_HEADER: Option<u8> = None if compact proofs are not used, or redesign the escape mechanism for this header format.

2. Integer overflow in ByteSliceInput::take

[node_codec.rs](primitives/trie/src/node_codec.rs) line 46:

fn take(&mut self, count: usize) -> Result<Range<usize>, codec::Error> {
    if self.offset + count > self.data.len() { // <-- wrapping overflow possible

If a malicious node encodes a count close to usize::MAX (from the 8-byte LE length field), self.offset + count can wrap around to a small value, passing the bounds check. On 64-bit platforms this requires count = u64::MAX which is unlikely in practice but exploitable in adversarial contexts.

Fix: Use self.offset.checked_add(count).map_or(true, |end| end > self.data.len()).

3. CompactProof::to_storage_proof does not validate root

[storage_proof.rs](primitives/trie/src/storage_proof.rs) lines 198-209:

pub fn to_storage_proof<H: Hasher>(
    &self, expected_root: Option<&H::Out>,
) -> Result<...> {
    let storage_proof = StorageProof::new(self.encoded_nodes.clone());
    match expected_root {
        Some(root) => Ok((storage_proof, *root)),   // just echoes the root back!
        None => Ok((storage_proof, H::Out::default())),
    }
}

The expected_root is returned as-is without verifying the proof actually produces that root. Callers expecting root validation get none. Similarly, to_memory_db (line 216) has the same pattern.

Fix: Either validate the root by recomputing the trie from the proof nodes, or rename the parameter and document that no validation occurs.

---

High-Severity Issues

4. NodeHeader encode/decode 32-bit truncation

[node_header.rs](primitives/trie/src/node_header.rs) line 86:

let nibble_count = (value & 0xFFFFFFFF) as usize; // Extract bits 31-0

Encoding stores the full usize as u64, but decoding masks to 32 bits. If nibble_count > 0xFFFF_FFFF on 64-bit platforms, encode writes a value that decode truncates. This creates a silent data corruption path.

Fix: Either validate nibble_count < 2^32 on encode and reject larger values, or decode the full 60-bit nibble count field (bits 0-59).

5. LayoutV0 and LayoutV1 are functionally identical

[lib.rs](primitives/trie/src/lib.rs) lines 91-187: Both layouts have identical MAX_INLINE_VALUE: Some(31), same NodeCodec, and nearly identical TrieConfiguration implementations. Upstream Substrate distinguishes V0 (no inline limit) from V1 (external value nodes at 33+ bytes). If any code path relies on V0/V1 behavioral differences, it will silently break.

Additionally, LayoutV0::trie_root log messages incorrectly say "LayoutV1" (lines 114, 119, 130, 135), indicating careless copy-paste.

6. No count upper-bound validation in decoder

[node_codec.rs](primitives/trie/src/node_codec.rs) lines 144, 165: The 8-byte LE length is cast directly to usize and used in input.take(count). While ByteSliceInput::take bounds-checks against the data length, a very large count could still cause issues (see issue 2 on overflow). Adding an explicit upper bound (e.g. count <= MAX_NODE_SIZE) provides defense-in-depth.

---

Medium-Severity Issues

7. PrefixedMemoryDB::default_with_root vs hashed_null_node potential mismatch

[lib.rs](primitives/trie/src/lib.rs) lines 229-232: default_with_root() delegates to memory_db::MemoryDB::default_with_root(), which inserts &[] (empty slice) and returns H::hash(&[]) as root. But NodeCodec::hashed_null_node returns H::hash(&[0u8; 8]) (the 8-byte Null header). If any code path compares these roots, they will differ.

decode_plan handles empty data (&[]) by returning NodePlan::Empty, so the trie "works", but is_empty_node checks data == &[0u8; 8], which would not match &[]. This inconsistency could surface in edge cases around empty trie detection.

8. &PrefixedMemoryDB / &MemoryDB as_hash_db_mut panics

[lib.rs](primitives/trie/src/lib.rs) lines 283-284 and 379-380:

fn as_hash_db_mut<'a>(&'a mut self) -> &'a mut (dyn hash_db::HashDB<H, trie_db::DBValue> + 'a) {
    unreachable!("Cannot get mutable reference from shared reference")
}

This implements AsHashDB for &PrefixedMemoryDB/&MemoryDB with a panic in as_hash_db_mut. If any code path accidentally reaches this (e.g. through a trait object), the process aborts without a recoverable error.

9. branch_has_value default for non-branch headers

[node_codec.rs](primitives/trie/src/node_codec.rs) lines 112-117:

let branch_has_value = if let NodeHeader::Branch(has_value, _) = &header {
    *has_value
} else {
    true  // default true for Leaf, HashedValueLeaf, Null, HashedValueBranch
};

For Leaf/HashedValueLeaf/Null headers, branch_has_value is set to true. This variable is only read in the branch match arm, so it is currently harmless. But it is a maintenance hazard -- a refactor could easily introduce a bug here.

10. Bitmap bit-shift beyond 16 children

[node_codec.rs](primitives/trie/src/node_codec.rs) line 423: Bitmap::value_at uses 1u64 << i where i ranges 0..16 in decode. This is correct for the 16-nibble trie. However, there is no bounds check on i. If called with i >= 64, undefined behavior via shift-overflow could occur (though Rust panics in debug mode and wraps in release).

---

Low-Severity / Code Quality

11. Excessive log::debug! in hot paths

Production hot paths (decode_plan, hashed_null_node, empty_trie_root, trie_root) contain log::debug! calls with {:02x?} formatting that materializes full node data into strings. Even with the log crate's lazy evaluation, the format arguments are still evaluated on every call. This adds overhead in production.

12. Tests contain emoji and verbose println

Tests throughout [lib.rs](primitives/trie/src/lib.rs) use emoji characters and verbose println! output. While harmless, this adds noise to CI output and is inconsistent with typical Rust test style.

13. trie_constants::EMPTY_TRIE is u64 but used as bytes

[lib.rs](primitives/trie/src/lib.rs) line 819: EMPTY_TRIE is a u64 constant. Some uses call .to_le_bytes() on it, others use it directly. Since it's always 0, the distinction doesn't matter, but making it [u8; 8] would be more self-documenting.

14. append_extension uses debug_assert!(false) instead of unreachable!

[trie_stream.rs](primitives/trie/src/trie_stream.rs) line 191: Uses debug_assert!(false, ...) which is a no-op in release builds, meaning extensions would silently produce corrupt data in release mode. The branch encoding path correctly uses unreachable!().

---

Encode/Decode Consistency (Verified Correct)

• Branch node layout: [8B header][partial (felt-aligned)][8B bitmap][value?][children...] -- consistent between branch_node_nibbled and decode_plan.
• Leaf node layout: [8B header][prefix_pad][partial][trailing_pad][8B length][value (felt-aligned)] -- consistent between leaf_node/trie_stream and decode_plan.
• Child references: [8B LE length][data], classified as Hash when count == H::LENGTH -- consistent with MAX_INLINE_THRESHOLD = 31 < H::LENGTH = 32.
• Bitmap: 8-byte LE u64 with u64::decode (SCALE fixed-width LE for u64) -- consistent.

[n13]

Most of these are deep into code that's not ours - may not be worth fixing