Trie node types

Merkle-Patricia trie node forms, references, and decoding (YP Appendix D).

type InlineNode

A self-contained trie-node encoding shorter than 32 bytes.

struct InlineNode = {
    data : b256,
    len : range(0, 31),
}

let MPT_HASH_LENGTH

let MPT_HASH_LENGTH : int(32) = WORD_BYTE_LENGTH

type TrieLeafValue

A leaf value retained by trie assembly. Authenticated witness and transaction leaves borrow immutable input bytes; newly encoded state, receipt, and withdrawal leaves borrow the scratch arena.

union TrieLeafValue = {
    /* a leaf borrowing immutable stateless input bytes */
    InputTrieLeaf : StatelessInputSlice,
    /* a leaf borrowing freshly encoded scratch bytes */
    ScratchTrieLeaf : ScratchSlice,
}

function inline_node_from_scratch_slice

Copies a sub-32-byte scratch node encoding into an inline node value.

function inline_node_from_scratch_slice(bytes : ScratchSlice) -> InlineNode = {
    let length = bytes.len;
    if length < MPT_HASH_LENGTH then {
        let encoded = slice_load(bytes, 0);
        struct { data = word_to_hash(encoded), len = length }
    } else {
        fatal_error(WitnessDeficient)
    }
}

function inline_node_from_input_slice

Copies a sub-32-byte input node encoding into an inline node value.

function inline_node_from_input_slice(bytes : StatelessInputSlice) -> InlineNode = {
    let length = bytes.len;
    if length < MPT_HASH_LENGTH then {
        let encoded = slice_load(bytes, 0);
        struct { data = word_to_hash(encoded), len = length }
    } else {
        fatal_error(WitnessDeficient)
    }
}

function inline_node_slice

Materializes an inline node in scratch memory as a byte slice.

function inline_node_slice(node : InlineNode) -> ScratchSlice = {
    let start = scratch_reserve(node.len);
    scratch_push_b256(node.data, node.len);
    scratch_finish(start)
}

function inline_node_hash

Hashes an inline node from its existing scratch representation.

function inline_node_hash(node : InlineNode) -> hash = {
    let mark = scratch_begin();
    let encoded = inline_node_slice(node);
    let digest = keccak256(encoded);
    scratch_rewind(mark);
    digest
}

type NodeRef

A reference to a trie node: empty, inline (encodings under 32 bytes), or by KECCAK-256 hash (YP Appendix D, Eq. 207).

union NodeRef = {
    /* the empty node */
    EmptyRef : unit,
    /* an authenticated node embedded in witness input */
    InputInlineRef : StatelessInputSliceAtMost(31),
    /* a freshly encoded node embedded in a generated parent */
    ScratchInlineRef : InlineNode,
    /* a node referenced by its KECCAK-256 hash */
    HashRef : hash,
}

type BranchRefs

The sixteen child references of a branch, indexed by nibble.

type BranchRefs = vector(16, dec, NodeRef)

type branch_content_length

The RLP payload of a branch contains sixteen child references of at most 33 bytes and one empty value byte.

type branch_content_length = range(0, 529)

function branch_content_length_add

Advances the branch payload length while preserving its structural bound.

function branch_content_length_add(current : branch_content_length, addition : range(0, 33)) -> branch_content_length =
    if addition <= 529 - current then {
        current + addition
    } else {
        fatal_error(RlpDecode)
    }