1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302
use super::{
BTreeMap, BTreeSet, EmptySubtreeRoots, InnerNodeInfo, MerkleError, MerklePath, MerkleTreeDelta,
NodeIndex, Rpo256, RpoDigest, StoreNode, TryApplyDiff, Vec, Word,
};
#[cfg(test)]
mod tests;
// SPARSE MERKLE TREE
// ================================================================================================
/// A sparse Merkle tree with 64-bit keys and 4-element leaf values, without compaction.
///
/// The root of the tree is recomputed on each new leaf update.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
pub struct SimpleSmt {
depth: u8,
root: RpoDigest,
leaves: BTreeMap<u64, Word>,
branches: BTreeMap<NodeIndex, BranchNode>,
empty_hashes: Vec<RpoDigest>,
}
impl SimpleSmt {
// CONSTANTS
// --------------------------------------------------------------------------------------------
/// Minimum supported depth.
pub const MIN_DEPTH: u8 = 1;
/// Maximum supported depth.
pub const MAX_DEPTH: u8 = 64;
/// Value of an empty leaf.
pub const EMPTY_VALUE: Word = super::EMPTY_WORD;
// CONSTRUCTORS
// --------------------------------------------------------------------------------------------
/// Returns a new [SimpleSmt] instantiated with the specified depth.
///
/// All leaves in the returned tree are set to [ZERO; 4].
///
/// # Errors
/// Returns an error if the depth is 0 or is greater than 64.
pub fn new(depth: u8) -> Result<Self, MerkleError> {
// validate the range of the depth.
if depth < Self::MIN_DEPTH {
return Err(MerkleError::DepthTooSmall(depth));
} else if Self::MAX_DEPTH < depth {
return Err(MerkleError::DepthTooBig(depth as u64));
}
let empty_hashes = EmptySubtreeRoots::empty_hashes(depth).to_vec();
let root = empty_hashes[0];
Ok(Self {
root,
depth,
empty_hashes,
leaves: BTreeMap::new(),
branches: BTreeMap::new(),
})
}
/// Returns a new [SimpleSmt] instantiated with the specified depth and with leaves
/// set as specified by the provided entries.
///
/// All leaves omitted from the entries list are set to [ZERO; 4].
///
/// # Errors
/// Returns an error if:
/// - If the depth is 0 or is greater than 64.
/// - The number of entries exceeds the maximum tree capacity, that is 2^{depth}.
/// - The provided entries contain multiple values for the same key.
pub fn with_leaves<R, I>(depth: u8, entries: R) -> Result<Self, MerkleError>
where
R: IntoIterator<IntoIter = I>,
I: Iterator<Item = (u64, Word)> + ExactSizeIterator,
{
// create an empty tree
let mut tree = Self::new(depth)?;
// check if the number of leaves can be accommodated by the tree's depth; we use a min
// depth of 63 because we consider passing in a vector of size 2^64 infeasible.
let entries = entries.into_iter();
let max = 1 << tree.depth.min(63);
if entries.len() > max {
return Err(MerkleError::InvalidNumEntries(max, entries.len()));
}
// append leaves to the tree returning an error if a duplicate entry for the same key
// is found
let mut empty_entries = BTreeSet::new();
for (key, value) in entries {
let old_value = tree.update_leaf(key, value)?;
if old_value != Self::EMPTY_VALUE || empty_entries.contains(&key) {
return Err(MerkleError::DuplicateValuesForIndex(key));
}
// if we've processed an empty entry, add the key to the set of empty entry keys, and
// if this key was already in the set, return an error
if value == Self::EMPTY_VALUE && !empty_entries.insert(key) {
return Err(MerkleError::DuplicateValuesForIndex(key));
}
}
Ok(tree)
}
// PUBLIC ACCESSORS
// --------------------------------------------------------------------------------------------
/// Returns the root of this Merkle tree.
pub const fn root(&self) -> RpoDigest {
self.root
}
/// Returns the depth of this Merkle tree.
pub const fn depth(&self) -> u8 {
self.depth
}
/// Returns a node at the specified index.
///
/// # Errors
/// Returns an error if the specified index has depth set to 0 or the depth is greater than
/// the depth of this Merkle tree.
pub fn get_node(&self, index: NodeIndex) -> Result<RpoDigest, MerkleError> {
if index.is_root() {
Err(MerkleError::DepthTooSmall(index.depth()))
} else if index.depth() > self.depth() {
Err(MerkleError::DepthTooBig(index.depth() as u64))
} else if index.depth() == self.depth() {
// the lookup in empty_hashes could fail only if empty_hashes were not built correctly
// by the constructor as we check the depth of the lookup above.
Ok(RpoDigest::from(
self.get_leaf_node(index.value())
.unwrap_or_else(|| *self.empty_hashes[index.depth() as usize]),
))
} else {
Ok(self.get_branch_node(&index).parent())
}
}
/// Returns a value of the leaf at the specified index.
///
/// # Errors
/// Returns an error if the index is greater than the maximum tree capacity, that is 2^{depth}.
pub fn get_leaf(&self, index: u64) -> Result<Word, MerkleError> {
let index = NodeIndex::new(self.depth, index)?;
Ok(self.get_node(index)?.into())
}
/// Returns a Merkle path from the node at the specified index to the root.
///
/// The node itself is not included in the path.
///
/// # Errors
/// Returns an error if the specified index has depth set to 0 or the depth is greater than
/// the depth of this Merkle tree.
pub fn get_path(&self, mut index: NodeIndex) -> Result<MerklePath, MerkleError> {
if index.is_root() {
return Err(MerkleError::DepthTooSmall(index.depth()));
} else if index.depth() > self.depth() {
return Err(MerkleError::DepthTooBig(index.depth() as u64));
}
let mut path = Vec::with_capacity(index.depth() as usize);
for _ in 0..index.depth() {
let is_right = index.is_value_odd();
index.move_up();
let BranchNode { left, right } = self.get_branch_node(&index);
let value = if is_right { left } else { right };
path.push(value);
}
Ok(MerklePath::new(path))
}
/// Return a Merkle path from the leaf at the specified index to the root.
///
/// The leaf itself is not included in the path.
///
/// # Errors
/// Returns an error if the index is greater than the maximum tree capacity, that is 2^{depth}.
pub fn get_leaf_path(&self, index: u64) -> Result<MerklePath, MerkleError> {
let index = NodeIndex::new(self.depth(), index)?;
self.get_path(index)
}
// ITERATORS
// --------------------------------------------------------------------------------------------
/// Returns an iterator over the leaves of this [SimpleSmt].
pub fn leaves(&self) -> impl Iterator<Item = (u64, &Word)> {
self.leaves.iter().map(|(i, w)| (*i, w))
}
/// Returns an iterator over the inner nodes of this Merkle tree.
pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_ {
self.branches.values().map(|e| InnerNodeInfo {
value: e.parent(),
left: e.left,
right: e.right,
})
}
// STATE MUTATORS
// --------------------------------------------------------------------------------------------
/// Updates value of the leaf at the specified index returning the old leaf value.
///
/// This also recomputes all hashes between the leaf and the root, updating the root itself.
///
/// # Errors
/// Returns an error if the index is greater than the maximum tree capacity, that is 2^{depth}.
pub fn update_leaf(&mut self, index: u64, value: Word) -> Result<Word, MerkleError> {
let old_value = self.insert_leaf_node(index, value).unwrap_or(Self::EMPTY_VALUE);
// if the old value and new value are the same, there is nothing to update
if value == old_value {
return Ok(value);
}
let mut index = NodeIndex::new(self.depth(), index)?;
let mut value = RpoDigest::from(value);
for _ in 0..index.depth() {
let is_right = index.is_value_odd();
index.move_up();
let BranchNode { left, right } = self.get_branch_node(&index);
let (left, right) = if is_right { (left, value) } else { (value, right) };
self.insert_branch_node(index, left, right);
value = Rpo256::merge(&[left, right]);
}
self.root = value;
Ok(old_value)
}
// HELPER METHODS
// --------------------------------------------------------------------------------------------
fn get_leaf_node(&self, key: u64) -> Option<Word> {
self.leaves.get(&key).copied()
}
fn insert_leaf_node(&mut self, key: u64, node: Word) -> Option<Word> {
self.leaves.insert(key, node)
}
fn get_branch_node(&self, index: &NodeIndex) -> BranchNode {
self.branches.get(index).cloned().unwrap_or_else(|| {
let node = self.empty_hashes[index.depth() as usize + 1];
BranchNode { left: node, right: node }
})
}
fn insert_branch_node(&mut self, index: NodeIndex, left: RpoDigest, right: RpoDigest) {
let branch = BranchNode { left, right };
self.branches.insert(index, branch);
}
}
// BRANCH NODE
// ================================================================================================
#[derive(Debug, Default, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
struct BranchNode {
left: RpoDigest,
right: RpoDigest,
}
impl BranchNode {
fn parent(&self) -> RpoDigest {
Rpo256::merge(&[self.left, self.right])
}
}
// TRY APPLY DIFF
// ================================================================================================
impl TryApplyDiff<RpoDigest, StoreNode> for SimpleSmt {
type Error = MerkleError;
type DiffType = MerkleTreeDelta;
fn try_apply(&mut self, diff: MerkleTreeDelta) -> Result<(), MerkleError> {
if diff.depth() != self.depth() {
return Err(MerkleError::InvalidDepth {
expected: self.depth(),
provided: diff.depth(),
});
}
for slot in diff.cleared_slots() {
self.update_leaf(*slot, Self::EMPTY_VALUE)?;
}
for (slot, value) in diff.updated_slots() {
self.update_leaf(*slot, *value)?;
}
Ok(())
}
}