Module trie 

This module defines the types of a binary merkle trie, generalized over a 256 bit hash function. All lookup paths in the trie are 256 bits.

All nodes are 256 bits. There are three kinds of nodes.

1. Internal nodes, which each have two children. The value of an internal node is given by hashing the concatenation of the two child nodes and setting the MSB to 0.
2. Leaf nodes, which have zero children. The value of a leaf node is given by hashing the concatenation of the 256-bit lookup path and the hash of the value stored at the leaf, and setting the MSB to 1.
3. TERMINATOR nodes, which have the special value of all 0s. These nodes have no children and serve as a stand-in for an empty sub-trie at any height. Terminator nodes enable the trie to be tractably represented.

All node preimages are 512 bits.

Structs

InternalData

The data of an internal (branch) node.

LeafData

The data of a leaf node.

Enums

NodeKind

The kind of a node.

Constants

TERMINATOR

The terminator hash is a special node hash value denoting an empty sub-tree. Concretely, when this appears at a given location in the trie, it implies that no key with a path beginning with the location has a value.

Functions

is_internal

Whether the node hash indicates the node is an internal node.

is_leaf

Whether the node hash indicates the node is a leaf.

is_terminator

Whether the node holds the special EMPTY_SUBTREE value.

Type Aliases

KeyPath

The path to a key. All paths have a 256 bit fixed length.

Node

A node in the binary trie. In this schema, it is always 256 bits and is the hash of either an LeafData or InternalData, or zeroed if it’s a TERMINATOR.

ValueHash

The hash of a value. In this schema, it is always 256 bits.