nomt_core/
trie.rs

1//! This module defines the types of a binary merkle trie, generalized over a 256 bit hash function.
2//! All lookup paths in the trie are 256 bits.
3//!
4//! All nodes are 256 bits. There are three kinds of nodes.
5//!   1. Internal nodes, which each have two children. The value of an internal node is
6//!       given by hashing the concatenation of the two child nodes and setting the MSB to 0.
7//!   2. Leaf nodes, which have zero children. The value of a leaf node is given by hashing
8//!       the concatenation of the 256-bit lookup path and the hash of the value stored at the leaf,
9//!       and setting the MSB to 1.
10//!   3. [`TERMINATOR`] nodes, which have the special value of all 0s. These nodes have no children
11//!      and serve as a stand-in for an empty sub-trie at any height. Terminator nodes enable the
12//!      trie to be tractably represented.
13//!
14//! All node preimages are 512 bits.
15
16use crate::hasher::NodeHasher;
17
18/// A node in the binary trie. In this schema, it is always 256 bits and is the hash of either
19/// an [`LeafData`] or [`InternalData`], or zeroed if it's a [`TERMINATOR`].
20///
21/// [`Node`]s are labeled by the [`NodeHasher`] used to indicate whether they are leaves or internal
22/// nodes. Typically, this is done by setting the MSB.
23pub type Node = [u8; 32];
24
25/// The path to a key. All paths have a 256 bit fixed length.
26pub type KeyPath = [u8; 32];
27
28/// The hash of a value. In this schema, it is always 256 bits.
29pub type ValueHash = [u8; 32];
30
31/// The terminator hash is a special node hash value denoting an empty sub-tree.
32/// Concretely, when this appears at a given location in the trie,
33/// it implies that no key with a path beginning with the location has a value.
34///
35/// This value may appear at any height.
36pub const TERMINATOR: Node = [0u8; 32];
37
38/// Whether the node hash indicates the node is a leaf.
39pub fn is_leaf<H: NodeHasher>(hash: &Node) -> bool {
40    H::node_kind(hash) == NodeKind::Leaf
41}
42
43/// Whether the node hash indicates the node is an internal node.
44pub fn is_internal<H: NodeHasher>(hash: &Node) -> bool {
45    H::node_kind(hash) == NodeKind::Internal
46}
47
48/// Whether the node holds the special `EMPTY_SUBTREE` value.
49pub fn is_terminator<H: NodeHasher>(hash: &Node) -> bool {
50    H::node_kind(hash) == NodeKind::Terminator
51}
52
53/// The kind of a node.
54#[derive(Debug, Clone, Copy, PartialEq, Eq)]
55pub enum NodeKind {
56    /// A terminator node indicates an empty sub-trie.
57    Terminator,
58    /// A leaf node indicates a sub-trie with a single leaf.
59    Leaf,
60    /// An internal node indicates at least two values.
61    Internal,
62}
63
64impl NodeKind {
65    /// Get the kind of the provided node.
66    pub fn of<H: NodeHasher>(node: &Node) -> Self {
67        H::node_kind(node)
68    }
69}
70
71/// The data of an internal (branch) node.
72#[derive(Debug, Clone, PartialEq, Eq)]
73pub struct InternalData {
74    /// The hash of the left child of this node.
75    pub left: Node,
76    /// The hash of the right child of this node.
77    pub right: Node,
78}
79
80/// The data of a leaf node.
81#[derive(Debug, Default, Clone, PartialEq, Eq)]
82#[cfg_attr(
83    feature = "borsh",
84    derive(borsh::BorshDeserialize, borsh::BorshSerialize)
85)]
86#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
87pub struct LeafData {
88    /// The total path to this value within the trie.
89    ///
90    /// The actual location of this node may be anywhere along this path, depending on the other
91    /// data within the trie.
92    pub key_path: KeyPath,
93    /// The hash of the value carried in this leaf.
94    pub value_hash: ValueHash,
95}
nomt_core/trie.rs

nomt_core/
trie.rs
