Skip to content

Trie::get_node returns empty for nodes it should be able to address #7175

Description

@MegaRedHand

Trie::get_node returns an empty vector for two classes of node that it should be able to address. Both make the snap-sync GetTrieNodes server under-answer: it replies "no such node" for nodes that exist.

Found while reviewing #7173, which fixes a third, unrelated bug in the same function (the extension arm was deriving the child's database key from the wrong path). These two were left out of that PR because they are a different bug family and the fix is a behaviour change rather than a key correction.

Callers: crates/storage/store.rs (the GetTrieNodes responder, two call sites).

1. The full-32-byte-path shape can never return a node

get_node documents and explicitly accepts two input shapes:

/// Allows usage of full paths (byte slice of 32 bytes) or compact-encoded nibble slices (with length lower than 32)
let partial_path = match partial_path.len() {
    n if n < 32 => Nibbles::decode_compact(partial_path),
    32 => Nibbles::from_bytes(partial_path),
    _ => return Ok(vec![]),
};

Nibbles::from_bytes is from_raw(bytes, true), which appends the leaf-flag nibble 16. So a 32-byte input becomes 65 nibbles, not 64. A node is only returned when the path is exhausted on arrival:

if partial_path.is_empty() {
    return Ok(node.encode_to_vec());
}

A leaf always retains its own partial path, so on arrival at the target leaf the path is not empty, and the Node::Leaf(_) => Ok(vec![]) arm wins. The 32-byte shape therefore always returns empty. Trie::get on the same key returns the value, so the node demonstrably exists.

Either the leaf arm should return the node when the remaining path equals leaf.partial, or the 32-byte shape should not be accepted. Worth checking what geth's snap server does before picking: it appears to take only hex/compact paths, and ethrex only ever serves GetTrieNodes, never sends it, so the shape may be dead by design — in which case rejecting it explicitly beats silently answering empty.

2. A path terminating at a branch node's own value returns empty

The branch arm consumes the next nibble through next_choice(), which pops it and then filters for < 16:

Node::Branch(branch_node) => match partial_path.next_choice() {
    Some(idx) => { /* descend */ }
    _ => Ok(vec![]),
}

When the nibble is the leaf flag the path terminates at this branch, and the answer should be the branch node itself. Instead the _ arm returns empty, and branch_node.value is never consulted anywhere in the function.

Test coverage

get_node had no test coverage at all before #7173, which is why the key bug it fixes shipped. That PR adds three tests (get_node_partial_path_crossing_extension_node, get_node_full_path_crossing_extension_node, get_node_missing_paths_return_empty). The second of those currently asserts the empty return described in (1) above, since that is the behaviour as it stands — it will need updating along with the fix, and its current form deliberately documents the defect rather than blessing it.

Found while reviewing #7173 (issue #5825).

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    • Status
      No status

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions