nomt_core/
hasher.rs

1//! Hashers (feature-gated) and utilities for implementing them.
2
3use crate::trie::{InternalData, LeafData, Node, NodeKind, TERMINATOR};
4
5/// A trie node hash function specialized for 64 bytes of data.
6///
7/// Note that it is illegal for the produced hash to equal [0; 32], as this value is reserved
8/// for the terminator node.
9///
10/// A node hasher should domain-separate internal and leaf nodes in some specific way. The
11/// recommended approach for binary hashes is to set the MSB to 0 or 1 depending on the node kind.
12/// However, for other kinds of hashes (e.g. Poseidon2 or other algebraic hashes), other labeling
13/// schemes may be required.
14pub trait NodeHasher {
15    /// Hash a leaf. This should domain-separate the hash
16    /// according to the node kind.
17    fn hash_leaf(data: &LeafData) -> [u8; 32];
18
19    /// Hash an internal node. This should domain-separate
20    /// the hash according to the node kind.
21    fn hash_internal(data: &InternalData) -> [u8; 32];
22
23    /// Get the kind of the given node.
24    fn node_kind(node: &Node) -> NodeKind;
25}
26
27/// A hasher for arbitrary-length values.
28pub trait ValueHasher {
29    /// Hash an arbitrary-length value.
30    fn hash_value(value: &[u8]) -> [u8; 32];
31}
32
33/// Get the node kind, according to a most-significant bit labeling scheme.
34///
35/// If the MSB is true, it's a leaf. If the node is empty, it's a [`TERMINATOR`]. Otherwise, it's
36/// an internal node.
37pub fn node_kind_by_msb(node: &Node) -> NodeKind {
38    if node[0] >> 7 == 1 {
39        NodeKind::Leaf
40    } else if node == &TERMINATOR {
41        NodeKind::Terminator
42    } else {
43        NodeKind::Internal
44    }
45}
46
47/// Set the most-significant bit of the node.
48pub fn set_msb(node: &mut Node) {
49    node[0] |= 0b10000000;
50}
51
52pub fn unset_msb(node: &mut Node) {
53    node[0] &= 0b01111111;
54}
55
56/// A simple trait for representing binary hash functions.
57pub trait BinaryHash {
58    /// Given a bit-string, produce a 32-bit hash.
59    fn hash(input: &[u8]) -> [u8; 32];
60
61    /// An optional specialization of `hash` where there are two 32-byte inputs, left and right.
62    fn hash2_32_concat(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
63        let mut buf = [0u8; 64];
64        buf[0..32].copy_from_slice(left);
65        buf[32..64].copy_from_slice(right);
66        Self::hash(&buf)
67    }
68}
69
70/// A node and value hasher constructed from a simple binary hasher.
71///
72/// This implements a [`ValueHasher`] and [`NodeHasher`] where the node kind is tagged by setting
73/// or unsetting the MSB of the hash value.
74///
75/// The binary hash wrapped by this structure must behave approximately like a random oracle over
76/// the space 2^256, i.e. all 256 bit outputs are valid and inputs are uniformly distributed.
77///
78/// Functions like Sha2/Blake3/Keccak/Groestl all meet these criteria.
79pub struct BinaryHasher<H>(core::marker::PhantomData<H>);
80
81impl<H: BinaryHash> ValueHasher for BinaryHasher<H> {
82    fn hash_value(value: &[u8]) -> [u8; 32] {
83        H::hash(value)
84    }
85}
86
87impl<H: BinaryHash> NodeHasher for BinaryHasher<H> {
88    fn hash_leaf(data: &LeafData) -> [u8; 32] {
89        let mut h = H::hash2_32_concat(&data.key_path, &data.value_hash);
90        set_msb(&mut h);
91        h
92    }
93
94    fn hash_internal(data: &InternalData) -> [u8; 32] {
95        let mut h = H::hash2_32_concat(&data.left, &data.right);
96        unset_msb(&mut h);
97        h
98    }
99
100    fn node_kind(node: &Node) -> NodeKind {
101        node_kind_by_msb(node)
102    }
103}
104
105/// Blanket implementation for all implementations of `Digest`
106impl<H: digest::Digest<OutputSize = digest::typenum::U32> + Send + Sync> BinaryHash for H {
107    fn hash(input: &[u8]) -> [u8; 32] {
108        H::digest(input).into()
109    }
110}
111
112#[cfg(any(feature = "blake3-hasher", test))]
113pub use blake3::Blake3Hasher;
114
115/// A node hasher making use of blake3.
116#[cfg(any(feature = "blake3-hasher", test))]
117pub mod blake3 {
118    use super::{BinaryHash, BinaryHasher};
119
120    /// A [`BinaryHash`] implementation for Blake3.
121    pub struct Blake3BinaryHasher;
122
123    /// A wrapper around Blake3 for use in NOMT.
124    pub type Blake3Hasher = BinaryHasher<Blake3BinaryHasher>;
125
126    impl BinaryHash for Blake3BinaryHasher {
127        fn hash(value: &[u8]) -> [u8; 32] {
128            blake3::hash(value).into()
129        }
130
131        fn hash2_32_concat(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
132            let mut hasher = blake3::Hasher::new();
133            hasher.update(left);
134            hasher.update(right);
135            hasher.finalize().into()
136        }
137    }
138}
139
140#[cfg(feature = "sha2-hasher")]
141pub use sha2::Sha2Hasher;
142
143/// A node and value hasher making use of sha2-256.
144#[cfg(feature = "sha2-hasher")]
145pub mod sha2 {
146    use super::{BinaryHash, BinaryHasher};
147    use sha2::{Digest, Sha256};
148
149    /// A [`BinaryHash`] implementation for Sha2.
150    pub struct Sha2BinaryHasher;
151
152    /// A wrapper around sha2-256 for use in NOMT.
153    pub type Sha2Hasher = BinaryHasher<Sha2BinaryHasher>;
154
155    impl BinaryHash for Sha2BinaryHasher {
156        fn hash(value: &[u8]) -> [u8; 32] {
157            let mut hasher = Sha256::new();
158            hasher.update(value);
159            hasher.finalize().into()
160        }
161
162        fn hash2_32_concat(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
163            let mut hasher = Sha256::new();
164            hasher.update(left);
165            hasher.update(right);
166            hasher.finalize().into()
167        }
168    }
169}
nomt_core/hasher.rs

nomt_core/
hasher.rs
