jmt/types/proof/definition.rs
1// Copyright (c) The Diem Core Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4//! This module has definition of various proofs.
5use core::marker::PhantomData;
6
7use super::{SparseMerkleInternalNode, SparseMerkleLeafNode, SparseMerkleNode};
8use crate::{
9 storage::Node,
10 types::nibble::nibble_path::{skip_common_prefix, NibblePath},
11 Bytes32Ext, KeyHash, RootHash, SimpleHasher, ValueHash, SPARSE_MERKLE_PLACEHOLDER_HASH,
12};
13use alloc::vec::Vec;
14use anyhow::{bail, ensure, format_err, Result};
15use serde::{Deserialize, Serialize};
16
17/// A proof that can be used to authenticate an element in a Sparse Merkle Tree given trusted root
18/// hash. For example, `TransactionInfoToAccountProof` can be constructed on top of this structure.
19#[derive(Serialize, Deserialize, borsh::BorshSerialize, borsh::BorshDeserialize)]
20pub struct SparseMerkleProof<H: SimpleHasher> {
21 /// This proof can be used to authenticate whether a given leaf exists in the tree or not.
22 /// - If this is `Some(leaf_node)`
23 /// - If `leaf_node.key` equals requested key, this is an inclusion proof and
24 /// `leaf_node.value_hash` equals the hash of the corresponding account blob.
25 /// - Otherwise this is a non-inclusion proof. `leaf_node.key` is the only key
26 /// that exists in the subtree and `leaf_node.value_hash` equals the hash of the
27 /// corresponding account blob.
28 /// - If this is `None`, this is also a non-inclusion proof which indicates the subtree is
29 /// empty.
30 // Prevent serde from adding a spurious Serialize/Deserialize bound on H
31 #[serde(bound(serialize = "", deserialize = ""))]
32 leaf: Option<SparseMerkleLeafNode>,
33
34 /// All siblings in this proof, including the default ones. Siblings are ordered from the bottom
35 /// level to the root level. The siblings contain the node type information to be able to efficiently
36 /// coalesce on deletes.
37 siblings: Vec<SparseMerkleNode>,
38
39 /// A marker type showing which hash function is used in this proof.
40 #[borsh(bound(serialize = "", deserialize = ""))]
41 phantom_hasher: PhantomData<H>,
42}
43
44// Deriving Debug fails since H is not Debug though phantom_hasher implements it
45// generically. Implement Debug manually as a workaround to enable Proptest
46impl<H: SimpleHasher> core::fmt::Debug for SparseMerkleProof<H> {
47 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
48 f.debug_struct("SparseMerkleProof")
49 .field("leaf", &self.leaf)
50 .field("siblings", &self.siblings)
51 .field("phantom_hasher", &self.phantom_hasher)
52 .finish()
53 }
54}
55
56// Manually implement PartialEq to circumvent [incorrect auto-bounds](https://github.com/rust-lang/rust/issues/26925)
57// TODO: Switch back to #[derive] once the perfect_derive feature lands
58impl<H: SimpleHasher> PartialEq for SparseMerkleProof<H> {
59 fn eq(&self, other: &Self) -> bool {
60 self.leaf == other.leaf && self.siblings == other.siblings
61 }
62}
63
64// Manually implement Clone to circumvent [incorrect auto-bounds](https://github.com/rust-lang/rust/issues/26925)
65// TODO: Switch back to #[derive] once the perfect_derive feature lands
66impl<H: SimpleHasher> Clone for SparseMerkleProof<H> {
67 fn clone(&self) -> Self {
68 Self {
69 leaf: self.leaf.clone(),
70 siblings: self.siblings.clone(),
71 phantom_hasher: Default::default(),
72 }
73 }
74}
75
76impl<H: SimpleHasher> SparseMerkleProof<H> {
77 /// Constructs a new `SparseMerkleProof` using leaf and a list of siblings.
78 pub(crate) fn new(leaf: Option<SparseMerkleLeafNode>, siblings: Vec<SparseMerkleNode>) -> Self {
79 SparseMerkleProof {
80 leaf,
81 siblings,
82 phantom_hasher: Default::default(),
83 }
84 }
85
86 /// Returns the leaf node in this proof.
87 pub fn leaf(&self) -> Option<SparseMerkleLeafNode> {
88 self.leaf.clone()
89 }
90
91 /// Returns the list of siblings in this proof.
92 pub(crate) fn siblings(&self) -> &[SparseMerkleNode] {
93 &self.siblings
94 }
95
96 pub(crate) fn take_siblings(self) -> Vec<SparseMerkleNode> {
97 self.siblings
98 }
99
100 /// Verifies an element whose key is `element_key` and value is
101 /// `element_value` exists in the Sparse Merkle Tree using the provided proof.
102 pub fn verify_existence<V: AsRef<[u8]>>(
103 &self,
104 expected_root_hash: RootHash,
105 element_key: KeyHash,
106 element_value: V,
107 ) -> Result<()> {
108 self.verify(expected_root_hash, element_key, Some(element_value))
109 }
110
111 /// Verifies the proof is a valid non-inclusion proof that shows this key doesn't exist in the
112 /// tree.
113 pub fn verify_nonexistence(
114 &self,
115 expected_root_hash: RootHash,
116 element_key: KeyHash,
117 ) -> Result<()> {
118 self.verify(expected_root_hash, element_key, None::<&[u8]>)
119 }
120
121 /// If `element_value` is present, verifies an element whose key is `element_key` and value is
122 /// `element_value` exists in the Sparse Merkle Tree using the provided proof. Otherwise
123 /// verifies the proof is a valid non-inclusion proof that shows this key doesn't exist in the
124 /// tree.
125 pub fn verify<V: AsRef<[u8]>>(
126 &self,
127 expected_root_hash: RootHash,
128 element_key: KeyHash,
129 element_value: Option<V>,
130 ) -> Result<()> {
131 ensure!(
132 self.siblings.len() <= 256,
133 "Sparse Merkle Tree proof has more than {} ({}) siblings.",
134 256,
135 self.siblings.len(),
136 );
137
138 match (element_value, self.leaf.clone()) {
139 (Some(value), Some(leaf)) => {
140 // This is an inclusion proof, so the key and value hash provided in the proof
141 // should match element_key and element_value_hash. `siblings` should prove the
142 // route from the leaf node to the root.
143 ensure!(
144 element_key == leaf.key_hash,
145 "Keys do not match. Key in proof: {:?}. Expected key: {:?}.",
146 leaf.key_hash,
147 element_key
148 );
149 let hash: ValueHash = ValueHash::with::<H>(value);
150 ensure!(
151 hash == leaf.value_hash,
152 "Value hashes do not match. Value hash in proof: {:?}. \
153 Expected value hash: {:?}",
154 leaf.value_hash,
155 hash,
156 );
157 }
158 (Some(_value), None) => bail!("Expected inclusion proof. Found non-inclusion proof."),
159 (None, Some(leaf)) => {
160 // This is a non-inclusion proof. The proof intends to show that if a leaf node
161 // representing `element_key` is inserted, it will break a currently existing leaf
162 // node represented by `proof_key` into a branch. `siblings` should prove the
163 // route from that leaf node to the root.
164 ensure!(
165 element_key != leaf.key_hash,
166 "Expected non-inclusion proof, but key exists in proof.",
167 );
168 ensure!(
169 element_key.0.common_prefix_bits_len(&leaf.key_hash.0) >= self.siblings.len(),
170 "Key would not have ended up in the subtree where the provided key in proof \
171 is the only existing key, if it existed. So this is not a valid \
172 non-inclusion proof.",
173 );
174 }
175 (None, None) => {
176 // This is a non-inclusion proof. The proof intends to show that if a leaf node
177 // representing `element_key` is inserted, it will show up at a currently empty
178 // position. `sibling` should prove the route from this empty position to the root.
179 }
180 }
181
182 let current_hash = self
183 .leaf
184 .clone()
185 .map_or(SPARSE_MERKLE_PLACEHOLDER_HASH, |leaf| leaf.hash::<H>());
186 let actual_root_hash = self
187 .siblings
188 .iter()
189 .zip(
190 element_key
191 .0
192 .iter_bits()
193 .rev()
194 .skip(256 - self.siblings.len()),
195 )
196 .fold(current_hash, |hash, (sibling_node, bit)| {
197 if bit {
198 SparseMerkleInternalNode::new(sibling_node.hash::<H>(), hash).hash::<H>()
199 } else {
200 SparseMerkleInternalNode::new(hash, sibling_node.hash::<H>()).hash::<H>()
201 }
202 });
203
204 ensure!(
205 actual_root_hash == expected_root_hash.0,
206 "Root hashes do not match. Actual root hash: {:?}. Expected root hash: {:?}.",
207 actual_root_hash,
208 expected_root_hash.0,
209 );
210
211 Ok(())
212 }
213
214 /// This function computes a new merkle path on split insertion (ie when inserting a new value creates
215 /// a key split).
216 ///
217 /// Add the correct siblings of the new merkle path by finding the splitting nibble and
218 /// adding the default leaves to the path
219 ///
220 /// To compute the number of default leaves we need to add, we need to:
221 /// - Compute the number of default leaves to separate the old leaf from the new leaf in the last nibble
222 /// - Compute the number of default leaves to traverse the common prefix
223 /// - Compute the number of default leaves remaining to select the former old leaf in the former last nibble
224 /// (this leaf becomes an internal node, hence the path needs to be fully specified)
225 fn compute_new_merkle_path_on_split<V: AsRef<[u8]>>(
226 mut self,
227 leaf_node: SparseMerkleLeafNode,
228 new_element_key: KeyHash,
229 new_element_value: V,
230 ) -> SparseMerkleProof<H> {
231 let new_key_path = NibblePath::new(new_element_key.0.to_vec());
232 let old_key_path = NibblePath::new(leaf_node.key_hash.0.to_vec());
233
234 // The verify_nonexistence check from before ensure that the common prefix nibbles_len is greater than the
235 // siblings len
236 let mut new_key_nibbles = new_key_path.nibbles();
237 let mut old_key_nibbles = old_key_path.nibbles();
238
239 let common_prefix_len = skip_common_prefix(&mut new_key_nibbles, &mut old_key_nibbles);
240
241 let num_siblings = self.siblings().len();
242
243 // The number of default leaves we need to add to the path.
244 let default_leaves_to_add_to_the_path =
245 ((4 * (common_prefix_len + 1) - num_siblings) / 4) * 4;
246
247 // This variable contains the number of default siblings that are inserted within the last nibble subtree to distinguish
248 // between the former and the new key. Since we are splitting the former key, we are creating a new level of the jmt
249 // that only contains the new and the former key. When converted into a binary tree, we need to add default leaves to
250 // reach the binary tree level that can distinguish the two keys. This amounts adding as many default leaves as there
251 // are bits in common in the last nibble of both keys.
252 let mut default_siblings_leaf_nibble = 0;
253
254 // We can safely unwrap these values as the check have been already performed in verify_nonexistence
255 let mut new_key_bits = new_key_nibbles.bits();
256 let mut old_key_bits = old_key_nibbles.bits();
257
258 // Hence, we have to add the number of bits in common in both keys.
259 while new_key_bits.next() == old_key_bits.next() {
260 default_siblings_leaf_nibble += 1;
261 }
262
263 // The number of default leaves we need to add to the previous root. When splitting a leaf node, we create a new internal node
264 // in place of the former leaf that has two leaf children. Hence we need to add some default siblings because the leaf node may
265 // not be at the last level of the subtree of the last nibble.
266 // To get this number, we need to take the number of siblings modulo 4 (this yields the hight of the splitted leaf in the last binary subtree,
267 // or the number of bits in the last nibble of the splitted leaf), substract it to 4 (to get the number of bits needed to complete the last nibble)
268 // and then take the result modulo 4 (in case num_siblings % 4 is zero, which happens when the leaf is at the lowest height of the last binary subtree).
269 let default_siblings_prev_root = (4 - (num_siblings % 4)) % 4;
270
271 let num_default_siblings = default_siblings_prev_root
272 + default_leaves_to_add_to_the_path
273 + default_siblings_leaf_nibble
274 - 4;
275
276 let mut new_siblings: Vec<SparseMerkleNode> = Vec::with_capacity(
277 num_default_siblings + 1 + self.siblings.len(), /* The default siblings, the current leaf that becomes a sibling and the former siblings */
278 );
279
280 // Add the previous leaf node
281 new_siblings.push(SparseMerkleNode::Leaf(SparseMerkleLeafNode {
282 key_hash: leaf_node.key_hash,
283 value_hash: leaf_node.value_hash,
284 }));
285
286 // Fill the siblings with the former default siblings
287 new_siblings.resize(num_default_siblings + 1, SparseMerkleNode::Null);
288
289 // Finally add the other siblings
290 new_siblings.append(&mut self.siblings);
291
292 // Step 2: we compute the new Merkle path (we build a new [`SparseMerkleProof`] object)
293 // In this case the siblings are left unchanged, only the leaf value is updated
294 SparseMerkleProof::new(
295 Some(SparseMerkleLeafNode::new(
296 new_element_key,
297 ValueHash::with::<H>(new_element_value),
298 )),
299 new_siblings,
300 )
301 }
302
303 /// Checks the old value against the root hash and computes the new root hash based on
304 /// the new key value pair
305 fn check_compute_new_root<V: AsRef<[u8]>>(
306 self,
307 old_root_hash: RootHash,
308 new_element_key: KeyHash,
309 new_element_value: Option<V>,
310 ) -> Result<RootHash> {
311 if let Some(new_element_value) = new_element_value {
312 // A value have been supplied, we need to prove that we inserted a given value at the new key
313
314 match self.leaf {
315 // In the case there is a leaf in the Merkle path, we check that this leaf exists in the tree
316 // The inserted key is going to update an existing leaf
317 Some(leaf_node) => {
318 // First verify that the old merkle path is valid
319 ensure!(self.root_hash() == old_root_hash);
320 if new_element_key == leaf_node.key_hash {
321 // Step 2: we compute the new Merkle path (we build a new [`SparseMerkleProof`] object)
322 // In this case the siblings are left unchanged, only the leaf value is updated
323 let new_merkle_path: SparseMerkleProof<H> = SparseMerkleProof::new(
324 Some(SparseMerkleLeafNode::new(
325 new_element_key,
326 ValueHash::with::<H>(new_element_value),
327 )),
328 self.siblings,
329 );
330
331 // Step 3: we compute the new Merkle root
332 Ok(new_merkle_path.root_hash())
333 } else {
334 let new_merkle_path = self.compute_new_merkle_path_on_split(
335 leaf_node,
336 new_element_key,
337 new_element_value,
338 );
339
340 // Step 3: we compute the new Merkle root
341 Ok(new_merkle_path.root_hash())
342 }
343 }
344
345 // There is no leaf in the Merkle path, which means the key we are going to insert does not update an existing leaf
346 None => {
347 ensure!(self
348 .verify_nonexistence(old_root_hash, new_element_key)
349 .is_ok());
350
351 // Step 2: we compute the new Merkle path (we build a new [`SparseMerkleProof`] object)
352 // In that case, the leaf is none so we don't need to change the siblings
353 let new_merkle_path: SparseMerkleProof<H> = SparseMerkleProof::new(
354 Some(SparseMerkleLeafNode::new(
355 new_element_key,
356 ValueHash::with::<H>(new_element_value),
357 )),
358 self.siblings,
359 );
360
361 // Step 3: we compute the new Merkle root
362 Ok(new_merkle_path.root_hash())
363 }
364 }
365 } else {
366 // No value supplied, we need to prove that the previous value was deleted
367 if let Some(leaf_node) = self.leaf {
368 ensure!(self.root_hash() == old_root_hash);
369 ensure!(
370 new_element_key == leaf_node.key_hash,
371 "Key {:?} to remove doesn't match the leaf key {:?} supplied with the proof",
372 new_element_key,
373 leaf_node.key_hash
374 );
375
376 // Step 2: we compute the new Merkle tree path.
377 // In case of deletion, we need to rewind the nibble until we reach the first non-default hash
378 // to simulate node coalescing.
379 // Then, when we reach the first non-default hash, we have to compute the new merkle path
380 // We have two different cases:
381 // - the first non-default sibling is an internal node: we don't apply coalescing.
382 // - the first non-default sibling is a leaf node: we apply coalescing
383 let mut siblings_it = self.siblings.into_iter().peekable();
384 let mut next_non_default_sib = SparseMerkleNode::Null;
385 while let Some(next_sibling) = siblings_it.peek() {
386 if *next_sibling != SparseMerkleNode::Null {
387 next_non_default_sib = *next_sibling;
388 break;
389 }
390 siblings_it.next();
391 }
392
393 let new_merkle_hash = match next_non_default_sib {
394 SparseMerkleNode::Internal(_) => {
395 // We need to keep the internal node in the iterator and simply compute the merkle path using the
396 // default leave as the root
397 let remaining_siblings_len = siblings_it.len();
398
399 // If the sibling is an internal node, it doesn't get coalesced after deletion.
400 RootHash(
401 siblings_it
402 .zip(
403 new_element_key
404 .0
405 .iter_bits()
406 .rev()
407 .skip(256 - remaining_siblings_len),
408 )
409 .fold(Node::new_null().hash::<H>(), |hash, (sibling_node, bit)| {
410 if bit {
411 SparseMerkleInternalNode::new(
412 sibling_node.hash::<H>(),
413 hash,
414 )
415 .hash::<H>()
416 } else {
417 SparseMerkleInternalNode::new(
418 hash,
419 sibling_node.hash::<H>(),
420 )
421 .hash::<H>()
422 }
423 }),
424 )
425 }
426 SparseMerkleNode::Leaf(_) => {
427 // We need to remove the leaf from the iterator
428 siblings_it.next();
429
430 // We have to remove the default leaves left in the siblings before the next root: coalescing
431 while let Some(next_sibling) = siblings_it.peek() {
432 if *next_sibling != SparseMerkleNode::Null {
433 break;
434 }
435 siblings_it.next();
436 }
437
438 let remaining_siblings_len = siblings_it.len();
439
440 // If the sibling is a leaf, we need to start computing the merkle hash from the leaf value
441 // because the node gets coalesced
442 RootHash(
443 siblings_it
444 .zip(
445 new_element_key
446 .0
447 .iter_bits()
448 .rev()
449 .skip(256 - remaining_siblings_len),
450 )
451 .fold(
452 next_non_default_sib.hash::<H>(),
453 |hash, (sibling_node, bit)| {
454 if bit {
455 SparseMerkleInternalNode::new(
456 sibling_node.hash::<H>(),
457 hash,
458 )
459 .hash::<H>()
460 } else {
461 SparseMerkleInternalNode::new(
462 hash,
463 sibling_node.hash::<H>(),
464 )
465 .hash::<H>()
466 }
467 },
468 ),
469 )
470
471 // Step 3: we compute the new Merkle root
472 }
473 SparseMerkleNode::Null => RootHash(SPARSE_MERKLE_PLACEHOLDER_HASH),
474 };
475
476 Ok(new_merkle_hash)
477 } else {
478 // We just return the old root hash if we try to remove the empty node
479 // because there isn't any changes to the merkle tree
480 Ok(old_root_hash)
481 }
482 }
483 }
484
485 pub fn root_hash(&self) -> RootHash {
486 let current_hash = self
487 .leaf
488 .clone()
489 .map_or(SPARSE_MERKLE_PLACEHOLDER_HASH, |leaf| leaf.hash::<H>());
490 let actual_root_hash = self
491 .siblings
492 .iter()
493 .zip(
494 self.leaf()
495 .expect("need leaf hash for root_hash")
496 .key_hash
497 .0
498 .iter_bits()
499 .rev()
500 .skip(256 - self.siblings.len()),
501 )
502 .fold(current_hash, |hash, (sibling_node, bit)| {
503 if bit {
504 SparseMerkleInternalNode::new(sibling_node.hash::<H>(), hash).hash::<H>()
505 } else {
506 SparseMerkleInternalNode::new(hash, sibling_node.hash::<H>()).hash::<H>()
507 }
508 });
509
510 RootHash(actual_root_hash)
511 }
512}
513
514#[derive(Debug, Serialize, Deserialize, borsh::BorshSerialize, borsh::BorshDeserialize)]
515pub struct UpdateMerkleProof<H: SimpleHasher>(
516 #[borsh(bound(serialize = "", deserialize = ""))] Vec<SparseMerkleProof<H>>,
517);
518
519impl<H: SimpleHasher> UpdateMerkleProof<H> {
520 pub fn new(merkle_proofs: Vec<SparseMerkleProof<H>>) -> Self {
521 UpdateMerkleProof(merkle_proofs)
522 }
523
524 /// Verifies an update of the [`JellyfishMerkleTree`], proving the transition from an `old_root_hash` to a `new_root_hash` ([`RootHash`])
525 /// Multiple cases to handle:
526 /// - Insert a tuple `new_element_key`, `new_element_value`
527 /// - Update a tuple `new_element_key`, `new_element_value`
528 /// - Delete the `new_element_key`
529 /// This function does the following high level operations:
530 /// 1. Verify the Merkle path provided against the `old_root_hash`
531 /// 2. Use the provided Merkle path and the tuple (`new_element_key`, `new_element_value`) to compute the new Merkle path.
532 /// 3. Compare the new Merkle path against the new_root_hash
533 /// If these steps are verified then the [`JellyfishMerkleTree`] has been soundly updated
534 ///
535 /// This function consumes the Merkle proof to avoid uneccessary copying.
536 pub fn verify_update<V: AsRef<[u8]>>(
537 self,
538 old_root_hash: RootHash,
539 new_root_hash: RootHash,
540 updates: impl AsRef<[(KeyHash, Option<V>)]>,
541 ) -> Result<()> {
542 let updates = updates.as_ref();
543 ensure!(
544 updates.len() == self.0.len(),
545 "Mismatched number of updates and proofs. Received {} proofs for {} updates",
546 self.0.len(),
547 updates.len()
548 );
549 let mut curr_root_hash = old_root_hash;
550
551 for (merkle_proof, (new_element_key, new_element_value)) in
552 self.0.into_iter().zip(updates.iter())
553 {
554 // Checks the old root hash and computes the new root
555 curr_root_hash = merkle_proof.check_compute_new_root(
556 curr_root_hash,
557 *new_element_key,
558 new_element_value.as_ref(),
559 )?;
560 }
561
562 ensure!(
563 curr_root_hash == new_root_hash,
564 "Root hashes do not match. Actual root hash: {:?}. Expected root hash: {:?}.",
565 curr_root_hash,
566 new_root_hash,
567 );
568
569 Ok(())
570 }
571}
572
573/// Note: this is not a range proof in the sense that a range of nodes is verified!
574/// Instead, it verifies the entire left part of the tree up to a known rightmost node.
575/// See the description below.
576///
577/// A proof that can be used to authenticate a range of consecutive leaves, from the leftmost leaf to
578/// the rightmost known one, in a sparse Merkle tree. For example, given the following sparse Merkle tree:
579///
580/// ```text
581/// root
582/// / \
583/// / \
584/// / \
585/// o o
586/// / \ / \
587/// a o o h
588/// / \ / \
589/// o d e X
590/// / \ / \
591/// b c f g
592/// ```
593///
594/// if the proof wants show that `[a, b, c, d, e]` exists in the tree, it would need the siblings
595/// `X` and `h` on the right.
596#[derive(Eq, Serialize, Deserialize, borsh::BorshSerialize, borsh::BorshDeserialize)]
597pub struct SparseMerkleRangeProof<H: SimpleHasher> {
598 /// The vector of siblings on the right of the path from root to last leaf. The ones near the
599 /// bottom are at the beginning of the vector. In the above example, it's `[X, h]`.
600 right_siblings: Vec<SparseMerkleNode>,
601 _phantom: PhantomData<H>,
602}
603
604// Manually implement PartialEq to circumvent [incorrect auto-bounds](https://github.com/rust-lang/rust/issues/26925)
605// TODO: Switch back to #[derive] once the perfect_derive feature lands
606impl<H: SimpleHasher> PartialEq for SparseMerkleRangeProof<H> {
607 fn eq(&self, other: &Self) -> bool {
608 self.right_siblings == other.right_siblings
609 }
610}
611
612// Manually implement Clone to circumvent [incorrect auto-bounds](https://github.com/rust-lang/rust/issues/26925)
613// TODO: Switch back to #[derive] once the perfect_derive feature lands
614impl<H: SimpleHasher> Clone for SparseMerkleRangeProof<H> {
615 fn clone(&self) -> Self {
616 Self {
617 right_siblings: self.right_siblings.clone(),
618 _phantom: self._phantom.clone(),
619 }
620 }
621}
622
623// Manually implement Debug to circumvent [incorrect auto-bounds](https://github.com/rust-lang/rust/issues/26925)
624// TODO: Switch back to #[derive] once the perfect_derive feature lands
625impl<H: SimpleHasher> core::fmt::Debug for SparseMerkleRangeProof<H> {
626 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
627 f.debug_struct("SparseMerkleRangeProof")
628 .field("right_siblings", &self.right_siblings)
629 .field("_phantom", &self._phantom)
630 .finish()
631 }
632}
633
634impl<H: SimpleHasher> SparseMerkleRangeProof<H> {
635 /// Constructs a new `SparseMerkleRangeProof`.
636 pub(crate) fn new(right_siblings: Vec<SparseMerkleNode>) -> Self {
637 Self {
638 right_siblings,
639 _phantom: Default::default(),
640 }
641 }
642
643 /// Returns the right siblings.
644 pub(crate) fn right_siblings(&self) -> &[SparseMerkleNode] {
645 &self.right_siblings
646 }
647
648 /// Verifies that the rightmost known leaf exists in the tree and that the resulting
649 /// root hash matches the expected root hash.
650 pub fn verify(
651 &self,
652 expected_root_hash: RootHash,
653 rightmost_known_leaf: SparseMerkleLeafNode,
654 left_siblings: Vec<[u8; 32]>,
655 ) -> Result<()> {
656 let num_siblings = left_siblings.len() + self.right_siblings.len();
657 let mut left_sibling_iter = left_siblings.iter();
658 let mut right_sibling_iter = self.right_siblings().iter();
659
660 let mut current_hash = rightmost_known_leaf.hash::<H>();
661 for bit in rightmost_known_leaf
662 .key_hash()
663 .0
664 .iter_bits()
665 .rev()
666 .skip(256 - num_siblings)
667 {
668 let (left_hash, right_hash) = if bit {
669 (
670 *left_sibling_iter
671 .next()
672 .ok_or_else(|| format_err!("Missing left sibling."))?,
673 current_hash,
674 )
675 } else {
676 (
677 current_hash,
678 right_sibling_iter
679 .next()
680 .ok_or_else(|| format_err!("Missing right sibling."))?
681 .hash::<H>(),
682 )
683 };
684 current_hash = SparseMerkleInternalNode::new(left_hash, right_hash).hash::<H>();
685 }
686
687 ensure!(
688 current_hash == expected_root_hash.0,
689 "Root hashes do not match. Actual root hash: {:?}. Expected root hash: {:?}.",
690 current_hash,
691 expected_root_hash,
692 );
693
694 Ok(())
695 }
696}
697
698#[cfg(test)]
699mod serialization_tests {
700 //! These tests ensure that the various proofs supported by the JMT can actually be serialized and deserialized
701 //! when instantiated with a specific hasher. This is done as a sanity check to ensure the trait bounds inferred by Rustc
702 //! are not too restrictive.
703
704 use sha2::Sha256;
705
706 use crate::{
707 proof::{SparseMerkleInternalNode, SparseMerkleLeafNode, SparseMerkleNode},
708 KeyHash, ValueHash,
709 };
710
711 use super::{SparseMerkleProof, SparseMerkleRangeProof};
712
713 fn get_test_proof() -> SparseMerkleProof<Sha256> {
714 SparseMerkleProof {
715 leaf: Some(SparseMerkleLeafNode::new(
716 KeyHash([1u8; 32]),
717 ValueHash([2u8; 32]),
718 )),
719 siblings: alloc::vec![SparseMerkleNode::Internal(SparseMerkleInternalNode::new(
720 [3u8; 32], [4u8; 32]
721 ))],
722 phantom_hasher: Default::default(),
723 }
724 }
725
726 fn get_test_range_proof() -> SparseMerkleRangeProof<Sha256> {
727 SparseMerkleRangeProof {
728 right_siblings: alloc::vec![SparseMerkleNode::Internal(SparseMerkleInternalNode::new(
729 [3u8; 32], [4u8; 32]
730 ))],
731 _phantom: Default::default(),
732 }
733 }
734
735 #[test]
736 fn test_sparse_merkle_proof_roundtrip_serde() {
737 let proof = get_test_proof();
738 let serialized_proof = serde_json::to_string(&proof).expect("serialization is infallible");
739 let deserialized =
740 serde_json::from_str(&serialized_proof).expect("serialized proof is valid");
741
742 assert_eq!(proof, deserialized);
743 }
744
745 #[test]
746 fn test_sparse_merkle_proof_roundtrip_borsh() {
747 use borsh::BorshDeserialize;
748 let proof = get_test_proof();
749 let serialized_proof = borsh::to_vec(&proof).expect("serialization is infallible");
750 let deserialized =
751 SparseMerkleProof::<Sha256>::deserialize(&mut serialized_proof.as_slice())
752 .expect("serialized proof is valid");
753
754 assert_eq!(proof, deserialized);
755 }
756
757 #[test]
758 fn test_sparse_merkle_range_proof_roundtrip_serde() {
759 let proof = get_test_range_proof();
760 let serialized_proof = serde_json::to_string(&proof).expect("serialization is infallible");
761 let deserialized =
762 serde_json::from_str(&serialized_proof).expect("serialized proof is valid");
763
764 assert_eq!(proof, deserialized);
765 }
766
767 #[test]
768 fn test_sparse_merkle_range_proof_roundtrip_borsh() {
769 use borsh::BorshDeserialize;
770 let proof = get_test_range_proof();
771 let serialized_proof = borsh::to_vec(&proof).expect("serialization is infallible");
772 let deserialized =
773 SparseMerkleRangeProof::<Sha256>::deserialize(&mut serialized_proof.as_slice())
774 .expect("serialized proof is valid");
775
776 assert_eq!(proof, deserialized);
777 }
778}