miden-crypto/src/merkle/smt/mod.rs
src/merkle/smt/mod.rsRaw
1use winter_math::StarkField;
2
3use crate::{
4 hash::rpo::{Rpo256, RpoDigest},
5 Word,
6};
7
8use super::{MerkleError, MerklePath, NodeIndex, Vec};
9
10mod simple;
11pub use simple::SimpleSmt;
12
13// CONSTANTS
14// ================================================================================================
15
16/// Minimum supported depth.
17pub const SMT_MIN_DEPTH: u8 = 1;
18
19/// Maximum supported depth.
20pub const SMT_MAX_DEPTH: u8 = 64;
21
22// SPARSE MERKLE TREE
23// ================================================================================================
24
25/// An abstract description of a sparse Merkle tree.
26///
27/// A sparse Merkle tree is a key-value map which also supports proving that a given value is indeed
28/// stored at a given key in the tree. It is viewed as always being fully populated. If a leaf's
29/// value was not explicitly set, then its value is the default value. Typically, the vast majority
30/// of leaves will store the default value (hence it is "sparse"), and therefore the internal
31/// representation of the tree will only keep track of the leaves that have a different value from
32/// the default.
33///
34/// All leaves sit at the same depth. The deeper the tree, the more leaves it has; but also the
35/// longer its proofs are - of exactly `log(depth)` size. A tree cannot have depth 0, since such a
36/// tree is just a single value, and is probably a programming mistake.
37///
38/// Every key maps to one leaf. If there are as many keys as there are leaves, then
39/// [Self::Leaf] should be the same type as [Self::Value], as is the case with
40/// [crate::merkle::SimpleSmt]. However, if there are more keys than leaves, then [`Self::Leaf`]
41/// must accomodate all keys that map to the same leaf.
42///
43/// [SparseMerkleTree] currently doesn't support optimizations that compress Merkle proofs.
44pub(crate) trait SparseMerkleTree<const DEPTH: u8> {
45 /// The type for a key
46 type Key: Clone;
47 /// The type for a value
48 type Value: Clone + PartialEq;
49 /// The type for a leaf
50 type Leaf;
51 /// The type for an opening (i.e. a "proof") of a leaf
52 type Opening: From<(MerklePath, Self::Leaf)>;
53
54 /// The default value used to compute the hash of empty leaves
55 const EMPTY_VALUE: Self::Value;
56
57 // PROVIDED METHODS
58 // ---------------------------------------------------------------------------------------------
59
60 /// Returns an opening of the leaf associated with `key`. Conceptually, an opening is a Merkle
61 /// path to the leaf, as well as the leaf itself.
62 fn open(&self, key: &Self::Key) -> Self::Opening {
63 let leaf = self.get_leaf(key);
64
65 let mut index: NodeIndex = {
66 let leaf_index: LeafIndex<DEPTH> = Self::key_to_leaf_index(key);
67 leaf_index.into()
68 };
69
70 let merkle_path = {
71 let mut path = Vec::with_capacity(index.depth() as usize);
72 for _ in 0..index.depth() {
73 let is_right = index.is_value_odd();
74 index.move_up();
75 let InnerNode { left, right } = self.get_inner_node(index);
76 let value = if is_right { left } else { right };
77 path.push(value);
78 }
79
80 MerklePath::new(path)
81 };
82
83 (merkle_path, leaf).into()
84 }
85
86 /// Inserts a value at the specified key, returning the previous value associated with that key.
87 /// Recall that by definition, any key that hasn't been updated is associated with
88 /// [`Self::EMPTY_VALUE`].
89 ///
90 /// This also recomputes all hashes between the leaf (associated with the key) and the root,
91 /// updating the root itself.
92 fn insert(&mut self, key: Self::Key, value: Self::Value) -> Self::Value {
93 let old_value = self.insert_value(key.clone(), value.clone()).unwrap_or(Self::EMPTY_VALUE);
94
95 // if the old value and new value are the same, there is nothing to update
96 if value == old_value {
97 return value;
98 }
99
100 let leaf = self.get_leaf(&key);
101 let node_index = {
102 let leaf_index: LeafIndex<DEPTH> = Self::key_to_leaf_index(&key);
103 leaf_index.into()
104 };
105
106 self.recompute_nodes_from_index_to_root(node_index, Self::hash_leaf(&leaf));
107
108 old_value
109 }
110
111 /// Recomputes the branch nodes (including the root) from `index` all the way to the root.
112 /// `node_hash_at_index` is the hash of the node stored at index.
113 fn recompute_nodes_from_index_to_root(
114 &mut self,
115 mut index: NodeIndex,
116 node_hash_at_index: RpoDigest,
117 ) {
118 let mut value = node_hash_at_index;
119 for _ in 0..index.depth() {
120 let is_right = index.is_value_odd();
121 index.move_up();
122 let InnerNode { left, right } = self.get_inner_node(index);
123 let (left, right) = if is_right { (left, value) } else { (value, right) };
124 self.insert_inner_node(index, InnerNode { left, right });
125 value = Rpo256::merge(&[left, right]);
126 }
127 self.set_root(value);
128 }
129
130 // REQUIRED METHODS
131 // ---------------------------------------------------------------------------------------------
132
133 /// The root of the tree
134 fn root(&self) -> RpoDigest;
135
136 /// Sets the root of the tree
137 fn set_root(&mut self, root: RpoDigest);
138
139 /// Retrieves an inner node at the given index
140 fn get_inner_node(&self, index: NodeIndex) -> InnerNode;
141
142 /// Inserts an inner node at the given index
143 fn insert_inner_node(&mut self, index: NodeIndex, inner_node: InnerNode);
144
145 /// Inserts a leaf node, and returns the value at the key if already exists
146 fn insert_value(&mut self, key: Self::Key, value: Self::Value) -> Option<Self::Value>;
147
148 /// Returns the leaf at the specified index.
149 fn get_leaf(&self, key: &Self::Key) -> Self::Leaf;
150
151 /// Returns the hash of a leaf
152 fn hash_leaf(leaf: &Self::Leaf) -> RpoDigest;
153
154 /// Maps a key to a leaf index
155 fn key_to_leaf_index(key: &Self::Key) -> LeafIndex<DEPTH>;
156}
157
158// INNER NODE
159// ================================================================================================
160
161#[derive(Debug, Default, Clone, PartialEq, Eq)]
162#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
163pub(crate) struct InnerNode {
164 pub left: RpoDigest,
165 pub right: RpoDigest,
166}
167
168impl InnerNode {
169 pub fn hash(&self) -> RpoDigest {
170 Rpo256::merge(&[self.left, self.right])
171 }
172}
173
174// LEAF INDEX
175// ================================================================================================
176
177/// The index of a leaf, at a depth known at compile-time.
178#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Hash)]
179#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
180pub struct LeafIndex<const DEPTH: u8> {
181 index: NodeIndex,
182}
183
184impl<const DEPTH: u8> LeafIndex<DEPTH> {
185 pub fn new(value: u64) -> Result<Self, MerkleError> {
186 if DEPTH < SMT_MIN_DEPTH {
187 return Err(MerkleError::DepthTooSmall(DEPTH));
188 }
189
190 Ok(LeafIndex { index: NodeIndex::new(DEPTH, value)? })
191 }
192
193 pub fn value(&self) -> u64 {
194 self.index.value()
195 }
196}
197
198impl LeafIndex<SMT_MAX_DEPTH> {
199 pub const fn new_max_depth(value: u64) -> Self {
200 LeafIndex {
201 index: NodeIndex::new_unchecked(SMT_MAX_DEPTH, value),
202 }
203 }
204}
205
206impl<const DEPTH: u8> From<LeafIndex<DEPTH>> for NodeIndex {
207 fn from(value: LeafIndex<DEPTH>) -> Self {
208 value.index
209 }
210}
211
212impl<const DEPTH: u8> TryFrom<NodeIndex> for LeafIndex<DEPTH> {
213 type Error = MerkleError;
214
215 fn try_from(node_index: NodeIndex) -> Result<Self, Self::Error> {
216 if node_index.depth() != DEPTH {
217 return Err(MerkleError::InvalidDepth {
218 expected: DEPTH,
219 provided: node_index.depth(),
220 });
221 }
222
223 Self::new(node_index.value())
224 }
225}
226
227impl From<Word> for LeafIndex<SMT_MAX_DEPTH> {
228 fn from(value: Word) -> Self {
229 // We use the most significant `Felt` of a `Word` as the leaf index.
230 Self::new_max_depth(value[3].as_int())
231 }
232}
233
234impl From<RpoDigest> for LeafIndex<SMT_MAX_DEPTH> {
235 fn from(value: RpoDigest) -> Self {
236 Word::from(value).into()
237 }
238}