sui_sdk_types/
merkle.rs

1//! Blake2b256 Merkle tree.
2//!
3//! This module implements a binary Merkle tree using Blake2b256 and the
4//! RFC-6962-style domain-separation scheme:
5//!
6//! - leaves are hashed as `BLAKE2b-256(0x00 || leaf_bytes)`,
7//! - inner nodes are hashed as `BLAKE2b-256(0x01 || left_bytes || right_bytes)`,
8//! - empty subtrees are represented as the all-zero 32-byte node.
9//!
10//! Levels with an odd number of nodes are padded with one [`Node::Empty`]
11//! sibling on the right.
12//!
13//! None of the types in this module implement `Serialize` or `Deserialize`:
14//! the Merkle tree and its proofs are in-memory constructs. Code that needs
15//! to transport a proof across a process boundary should define its own wire
16//! representation and convert at the boundary.
17
18use serde::Serialize;
19
20use crate::Digest;
21use crate::hash::Hasher;
22
23/// Byte length of a Merkle digest (32 bytes; Blake2b256).
24pub const DIGEST_LEN: usize = 32;
25
26/// Domain-separation prefix applied to every leaf before hashing.
27pub const LEAF_PREFIX: [u8; 1] = [0x00];
28
29/// Domain-separation prefix applied to every inner node before hashing.
30pub const INNER_PREFIX: [u8; 1] = [0x01];
31
32/// The 32-byte representation of an empty subtree.
33pub const EMPTY_NODE: [u8; DIGEST_LEN] = [0u8; DIGEST_LEN];
34
35/// A node in the Merkle tree.
36///
37/// `Empty` represents an empty subtree (used to pad odd-sized levels and to
38/// represent the root of a tree built from zero leaves). `Digest` carries the
39/// 32-byte Blake2b256 hash of either a leaf or an inner node.
40#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
41pub enum Node {
42    /// A subtree with no leaves underneath it.
43    Empty,
44    /// A non-empty node carrying its 32-byte hash.
45    Digest([u8; DIGEST_LEN]),
46}
47
48impl Node {
49    /// Returns the 32-byte representation of this node. `Empty` is rendered
50    /// as the all-zero digest.
51    pub fn bytes(&self) -> [u8; DIGEST_LEN] {
52        match self {
53            Self::Empty => EMPTY_NODE,
54            Self::Digest(value) => *value,
55        }
56    }
57}
58
59impl AsRef<[u8]> for Node {
60    fn as_ref(&self) -> &[u8] {
61        match self {
62            Self::Empty => &EMPTY_NODE,
63            Self::Digest(value) => value.as_ref(),
64        }
65    }
66}
67
68impl From<[u8; DIGEST_LEN]> for Node {
69    fn from(value: [u8; DIGEST_LEN]) -> Self {
70        Self::Digest(value)
71    }
72}
73
74impl From<Digest> for Node {
75    fn from(value: Digest) -> Self {
76        Self::Digest(value.into_inner())
77    }
78}
79
80/// An error returned by Merkle tree construction or proof verification.
81#[derive(Debug, PartialEq, Eq)]
82pub enum MerkleError {
83    /// The proof does not authenticate the leaf at the given index against
84    /// the provided root.
85    InvalidProof,
86    /// The caller supplied an invalid argument (e.g. a leaf index out of
87    /// bounds, or a leaf that could not be BCS-serialized).
88    InvalidInput,
89}
90
91impl std::fmt::Display for MerkleError {
92    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
93        match self {
94            Self::InvalidProof => f.write_str("invalid merkle proof"),
95            Self::InvalidInput => f.write_str("invalid merkle input"),
96        }
97    }
98}
99
100impl std::error::Error for MerkleError {}
101
102/// An inclusion proof for a leaf in a [`MerkleTree`].
103///
104/// The path lists each sibling hash on the way from the leaf up to the root.
105#[derive(Clone, Debug, PartialEq, Eq)]
106pub struct MerkleProof {
107    path: Vec<Node>,
108}
109
110impl MerkleProof {
111    /// Construct a proof directly from a sibling path. Mostly useful for
112    /// tests and for callers reconstructing a proof from out-of-band data;
113    /// most users obtain proofs via [`MerkleTree::get_proof`].
114    pub fn new(path: Vec<Node>) -> Self {
115        Self { path }
116    }
117
118    /// The sibling hashes on the path from the leaf to the root, leaf-side
119    /// first.
120    pub fn path(&self) -> &[Node] {
121        &self.path
122    }
123
124    /// Verify that the leaf identified by the given canonical bytes at
125    /// position `leaf_index` is included in the tree whose root is `root`.
126    ///
127    /// `leaf_bytes` must be the same byte representation that was hashed
128    /// into the tree when it was built — for trees built via
129    /// [`MerkleTree::build_from_unserialized`] that is the leaf's BCS
130    /// encoding. Most callers that already have the leaf in its structured
131    /// form should use [`verify_proof`] instead, which performs that BCS
132    /// step internally.
133    ///
134    /// [`verify_proof`]: MerkleProof::verify_proof
135    pub fn verify_proof_with_leaf_bytes(
136        &self,
137        root: &Node,
138        leaf_bytes: &[u8],
139        leaf_index: usize,
140    ) -> Result<(), MerkleError> {
141        match self.compute_root(leaf_bytes, leaf_index) {
142            Some(computed) if &computed == root => Ok(()),
143            _ => Err(MerkleError::InvalidProof),
144        }
145    }
146
147    /// Verify that `leaf` at position `leaf_index` is included in the tree
148    /// whose root is `root`.
149    ///
150    /// The leaf is BCS-encoded internally to obtain the canonical byte
151    /// representation that the tree commits to. Use
152    /// [`verify_proof_with_leaf_bytes`] when the caller already has those
153    /// bytes.
154    ///
155    /// [`verify_proof_with_leaf_bytes`]: MerkleProof::verify_proof_with_leaf_bytes
156    pub fn verify_proof<L: Serialize>(
157        &self,
158        root: &Node,
159        leaf: &L,
160        leaf_index: usize,
161    ) -> Result<(), MerkleError> {
162        let bytes = bcs::to_bytes(leaf).map_err(|_| MerkleError::InvalidInput)?;
163        self.verify_proof_with_leaf_bytes(root, &bytes, leaf_index)
164    }
165
166    /// Recompute the root from the proof and `leaf` at `leaf_index`.
167    ///
168    /// Returns `None` if `leaf_index` cannot fit in a tree of
169    /// `self.path.len()` levels (which would imply the proof was tampered
170    /// with or never matched this index).
171    pub fn compute_root(&self, leaf: &[u8], leaf_index: usize) -> Option<Node> {
172        if leaf_index >> self.path.len() != 0 {
173            return None;
174        }
175        let mut current = leaf_hash(leaf);
176        let mut level_index = leaf_index;
177        for sibling in &self.path {
178            current = if level_index.is_multiple_of(2) {
179                inner_hash(&current, sibling)
180            } else {
181                inner_hash(sibling, &current)
182            };
183            level_index /= 2;
184        }
185        Some(current)
186    }
187
188    /// Whether this proof identifies the right-most leaf in its tree.
189    ///
190    /// A right-most proof has the property that every step where the leaf is
191    /// a left child carries an `Empty` sibling — the only way to be on the
192    /// extreme right of a padded power-of-two tree.
193    pub fn is_right_most(&self, leaf_index: usize) -> bool {
194        let mut level_index = leaf_index;
195        for sibling in &self.path {
196            if level_index.is_multiple_of(2) && sibling.as_ref() != EMPTY_NODE.as_ref() {
197                return false;
198            }
199            level_index /= 2;
200        }
201        true
202    }
203}
204
205/// A Blake2b256 Merkle tree.
206///
207/// The tree is built once from a set of leaves and then queried for its
208/// [`root`] or for [`MerkleProof`]s.
209///
210/// [`root`]: MerkleTree::root
211#[derive(Debug)]
212pub struct MerkleTree {
213    /// Nodes laid out level by level, leaves first. Padding `Empty` nodes
214    /// are pushed in-band so the buffer is contiguous.
215    nodes: Vec<Node>,
216    n_leaves: usize,
217}
218
219impl MerkleTree {
220    /// Build a tree by hashing each input as a leaf.
221    pub fn build_from_serialized<I>(iter: I) -> Self
222    where
223        I: IntoIterator,
224        I::IntoIter: ExactSizeIterator,
225        I::Item: AsRef<[u8]>,
226    {
227        let leaf_hashes = iter
228            .into_iter()
229            .map(|leaf| leaf_hash(leaf.as_ref()))
230            .collect::<Vec<_>>();
231        Self::build_from_leaf_hashes(leaf_hashes)
232    }
233
234    /// Build a tree by BCS-encoding each input and using its hash as a leaf.
235    ///
236    /// Returns [`MerkleError::InvalidInput`] if any leaf fails BCS
237    /// serialization, which in practice can only happen for unusual `Serialize`
238    /// impls (e.g. infinite recursion); ordinary value types do not fail.
239    pub fn build_from_unserialized<I>(iter: I) -> Result<Self, MerkleError>
240    where
241        I: IntoIterator,
242        I::IntoIter: ExactSizeIterator,
243        I::Item: Serialize,
244    {
245        let leaf_hashes = iter
246            .into_iter()
247            .map(|leaf| {
248                bcs::to_bytes(&leaf)
249                    .map_err(|_| MerkleError::InvalidInput)
250                    .map(|bytes| leaf_hash(&bytes))
251            })
252            .collect::<Result<Vec<_>, _>>()?;
253        Ok(Self::build_from_leaf_hashes(leaf_hashes))
254    }
255
256    /// Build a tree directly from already-hashed leaves.
257    ///
258    /// Each input node is interpreted as a leaf hash; callers are responsible
259    /// for applying the [`LEAF_PREFIX`] before hashing.
260    pub fn build_from_leaf_hashes<I>(iter: I) -> Self
261    where
262        I: IntoIterator,
263        I::IntoIter: ExactSizeIterator<Item = Node>,
264    {
265        let iter = iter.into_iter();
266        let mut nodes = Vec::with_capacity(n_nodes(iter.len()));
267        nodes.extend(iter);
268
269        let n_leaves = nodes.len();
270        let mut level_nodes = n_leaves;
271        let mut prev_level_index = 0;
272
273        while level_nodes > 1 {
274            if level_nodes.is_multiple_of(2) {
275                // Even level: nothing to do.
276            } else {
277                nodes.push(Node::Empty);
278                level_nodes += 1;
279            }
280            let new_level_index = prev_level_index + level_nodes;
281            (prev_level_index..new_level_index)
282                .step_by(2)
283                .for_each(|index| nodes.push(inner_hash(&nodes[index], &nodes[index + 1])));
284            prev_level_index = new_level_index;
285            level_nodes /= 2;
286        }
287
288        Self { nodes, n_leaves }
289    }
290
291    /// The Merkle root.
292    ///
293    /// An empty tree (built from zero leaves) returns [`Node::Empty`].
294    pub fn root(&self) -> Node {
295        self.nodes.last().copied().unwrap_or(Node::Empty)
296    }
297
298    /// The number of leaves the tree was built from.
299    pub fn n_leaves(&self) -> usize {
300        self.n_leaves
301    }
302
303    /// Build an inclusion proof for the leaf at `leaf_index`.
304    ///
305    /// Returns [`MerkleError::InvalidInput`] if `leaf_index >= n_leaves`.
306    pub fn get_proof(&self, leaf_index: usize) -> Result<MerkleProof, MerkleError> {
307        if leaf_index >= self.n_leaves {
308            return Err(MerkleError::InvalidInput);
309        }
310        let path_capacity = self
311            .n_leaves
312            .checked_ilog2()
313            .map(|log| log as usize + 1)
314            .unwrap_or(0);
315        let mut path = Vec::with_capacity(path_capacity);
316        let mut level_index = leaf_index;
317        let mut n_level = self.n_leaves;
318        let mut level_base_index = 0;
319        while n_level > 1 {
320            // Every level has an even number of nodes (padding is in-band).
321            n_level = n_level.next_multiple_of(2);
322            let sibling_index = if level_index.is_multiple_of(2) {
323                level_base_index + level_index + 1
324            } else {
325                level_base_index + level_index - 1
326            };
327            path.push(self.nodes[sibling_index]);
328            level_index /= 2;
329            level_base_index += n_level;
330            n_level /= 2;
331        }
332        Ok(MerkleProof { path })
333    }
334
335    /// Build a non-inclusion proof showing that `target` does not appear in
336    /// this tree.
337    ///
338    /// The tree must have been built from `sorted_leaves` in sorted order;
339    /// the caller is responsible for passing the same sorted slice it built
340    /// the tree from. Returns [`MerkleError::InvalidInput`] if `target` is
341    /// actually present in `sorted_leaves`.
342    pub fn compute_non_inclusion_proof<L>(
343        &self,
344        sorted_leaves: &[L],
345        target: &L,
346    ) -> Result<MerkleNonInclusionProof<L>, MerkleError>
347    where
348        L: Ord + Clone,
349    {
350        let position = sorted_leaves.partition_point(|leaf| leaf <= target);
351        if position > 0 && &sorted_leaves[position - 1] == target {
352            return Err(MerkleError::InvalidInput);
353        }
354
355        let left_leaf = if position > 0 {
356            Some((
357                sorted_leaves[position - 1].clone(),
358                self.get_proof(position - 1)?,
359            ))
360        } else {
361            None
362        };
363
364        let right_leaf = if position < sorted_leaves.len() {
365            Some((sorted_leaves[position].clone(), self.get_proof(position)?))
366        } else {
367            None
368        };
369
370        Ok(MerkleNonInclusionProof {
371            index: position,
372            left_leaf,
373            right_leaf,
374        })
375    }
376}
377
378/// A non-inclusion proof for a tree built over **sorted** leaves.
379///
380/// The proof shows that a target leaf does not appear in the tree by
381/// presenting its two neighbours in sorted order (with their inclusion
382/// proofs) and asserting `left < target < right`.
383///
384/// Edge cases:
385/// - For an empty tree, both neighbours are `None` and `index` is `0`; any
386///   target is automatically non-included.
387/// - When the target sorts before every leaf, `left_leaf` is `None`,
388///   `right_leaf` is the first leaf, and `index` is `0`.
389/// - When the target sorts after every leaf, `right_leaf` is `None` and
390///   `left_leaf` is the right-most leaf in the tree (which is detected via
391///   [`MerkleProof::is_right_most`] during verification).
392#[derive(Clone, Debug, PartialEq, Eq)]
393pub struct MerkleNonInclusionProof<L> {
394    /// The position where `target` would be inserted into the sorted leaf
395    /// list to keep it sorted. `left_leaf` lives at `index - 1` (when
396    /// present), `right_leaf` at `index`.
397    index: usize,
398    /// Inclusion proof for the leaf immediately less than `target`, or
399    /// `None` if `target` sorts before every leaf.
400    left_leaf: Option<(L, MerkleProof)>,
401    /// Inclusion proof for the leaf immediately greater than `target`, or
402    /// `None` if `target` sorts after every leaf.
403    right_leaf: Option<(L, MerkleProof)>,
404}
405
406impl<L> MerkleNonInclusionProof<L> {
407    /// Construct a proof directly from its parts. Mostly useful for
408    /// reconstructing a proof from out-of-band data; the usual way to
409    /// produce a proof is [`MerkleTree::compute_non_inclusion_proof`].
410    pub fn new(
411        index: usize,
412        left_leaf: Option<(L, MerkleProof)>,
413        right_leaf: Option<(L, MerkleProof)>,
414    ) -> Self {
415        Self {
416            index,
417            left_leaf,
418            right_leaf,
419        }
420    }
421
422    /// The position where `target` would be inserted to keep the leaf list
423    /// sorted.
424    pub fn index(&self) -> usize {
425        self.index
426    }
427
428    /// The left neighbour leaf and its inclusion proof, if any.
429    pub fn left_leaf(&self) -> Option<&(L, MerkleProof)> {
430        self.left_leaf.as_ref()
431    }
432
433    /// The right neighbour leaf and its inclusion proof, if any.
434    pub fn right_leaf(&self) -> Option<&(L, MerkleProof)> {
435        self.right_leaf.as_ref()
436    }
437}
438
439impl<L> MerkleNonInclusionProof<L>
440where
441    L: Serialize,
442{
443    /// Verify that no leaf whose projected key equals `target_key` appears
444    /// in the tree whose root is `root`, where each leaf is projected to
445    /// its comparison key via `key_of`.
446    ///
447    /// The bracketing inequalities are evaluated on `key_of(leaf)` instead
448    /// of on the whole leaf, which is useful when the tree's leaves carry
449    /// more than just the field that the caller wants to prove absent
450    /// (e.g. an `ObjectReference` tree where the natural question is "is
451    /// any leaf with this object id present?").
452    ///
453    /// Soundness depends on the tree being sorted by an order whose
454    /// projection through `key_of` is monotonic — that is, all leaves
455    /// sharing the same key must be contiguous in the sorted leaf list.
456    /// This is the analogue of the sorted-leaf invariant on
457    /// [`verify_proof`](Self::verify_proof); the caller is responsible
458    /// for it, since the verifier cannot inspect the rest of the tree.
459    pub fn verify_proof_by_key<K, F>(
460        &self,
461        root: &Node,
462        target_key: &K,
463        key_of: F,
464    ) -> Result<(), MerkleError>
465    where
466        K: Ord + ?Sized,
467        F: Fn(&L) -> &K,
468    {
469        // An empty tree contains nothing, so non-inclusion is trivial.
470        if root.as_ref() == EMPTY_NODE.as_ref() {
471            return Ok(());
472        }
473
474        let right_leaf_index = self.index;
475        let left_leaf_with_index = self.left_leaf.as_ref().zip(self.index.checked_sub(1));
476
477        if let Some(((left_leaf, left_proof), left_leaf_index)) = left_leaf_with_index {
478            left_proof.verify_proof(root, left_leaf, left_leaf_index)?;
479            if key_of(left_leaf) >= target_key {
480                return Err(MerkleError::InvalidProof);
481            }
482        } else if right_leaf_index != 0 || self.right_leaf.is_none() {
483            // Without a left neighbour we must be inserting at the very
484            // start of the leaf list and there must be a right neighbour
485            // to compare against.
486            return Err(MerkleError::InvalidProof);
487        }
488
489        if let Some((right_leaf, right_proof)) = &self.right_leaf {
490            right_proof.verify_proof(root, right_leaf, right_leaf_index)?;
491            if key_of(right_leaf) <= target_key {
492                return Err(MerkleError::InvalidProof);
493            }
494        } else if let Some(((_, left_proof), left_leaf_index)) = left_leaf_with_index {
495            // Without a right neighbour the left neighbour must be the
496            // tree's right-most leaf, otherwise the gap is fictional.
497            if !left_proof.is_right_most(left_leaf_index) {
498                return Err(MerkleError::InvalidProof);
499            }
500        } else {
501            return Err(MerkleError::InvalidProof);
502        }
503
504        Ok(())
505    }
506}
507
508impl<L> MerkleNonInclusionProof<L>
509where
510    L: Ord + Serialize,
511{
512    /// Verify that `target` is not in the tree whose root is `root`.
513    ///
514    /// Thin wrapper over [`verify_proof_by_key`](Self::verify_proof_by_key)
515    /// with the identity projection — the leaf itself is its own key.
516    pub fn verify_proof(&self, root: &Node, target: &L) -> Result<(), MerkleError> {
517        self.verify_proof_by_key(root, target, |leaf| leaf)
518    }
519}
520
521/// Hash a leaf with the [`LEAF_PREFIX`] domain separator.
522pub(crate) fn leaf_hash(input: &[u8]) -> Node {
523    let mut hasher = Hasher::new();
524    hasher.update(LEAF_PREFIX);
525    hasher.update(input);
526    Node::Digest(hasher.finalize().into_inner())
527}
528
529/// Hash two child nodes with the [`INNER_PREFIX`] domain separator.
530fn inner_hash(left: &Node, right: &Node) -> Node {
531    let mut hasher = Hasher::new();
532    hasher.update(INNER_PREFIX);
533    hasher.update(left.bytes());
534    hasher.update(right.bytes());
535    Node::Digest(hasher.finalize().into_inner())
536}
537
538/// Total number of nodes stored when building a tree of `n_leaves` leaves
539/// (including in-band `Empty` padding on every level).
540pub(crate) fn n_nodes(n_leaves: usize) -> usize {
541    let mut lvl_nodes = n_leaves;
542    let mut tot_nodes = 0;
543    while lvl_nodes > 1 {
544        lvl_nodes += lvl_nodes % 2;
545        tot_nodes += lvl_nodes;
546        lvl_nodes /= 2;
547    }
548    tot_nodes + lvl_nodes
549}
550
551#[cfg(test)]
552mod tests {
553    use super::*;
554
555    #[cfg(target_arch = "wasm32")]
556    use wasm_bindgen_test::wasm_bindgen_test as test;
557
558    const TEST_INPUT: [&[u8]; 9] = [
559        b"foo", b"bar", b"fizz", b"baz", b"buzz", b"fizz", b"foobar", b"walrus", b"fizz",
560    ];
561
562    #[test]
563    fn n_nodes_formula() {
564        assert_eq!(n_nodes(0), 0);
565        assert_eq!(n_nodes(1), 1);
566        assert_eq!(n_nodes(2), 3);
567        assert_eq!(n_nodes(3), 7);
568        assert_eq!(n_nodes(4), 7);
569        assert_eq!(n_nodes(5), 13);
570        assert_eq!(n_nodes(6), 13);
571        assert_eq!(n_nodes(7), 15);
572        assert_eq!(n_nodes(8), 15);
573        assert_eq!(n_nodes(9), 23);
574    }
575
576    #[test]
577    fn empty_tree_root_is_empty_node() {
578        let tree = MerkleTree::build_from_serialized::<[&[u8]; 0]>([]);
579        assert_eq!(tree.root().bytes(), EMPTY_NODE);
580    }
581
582    #[test]
583    fn single_element_tree_root_is_leaf_hash() {
584        let leaf = b"Test";
585        let tree = MerkleTree::build_from_serialized([leaf.as_ref()]);
586        // Direct comparison with the leaf hash construction.
587        let mut hasher = Hasher::new();
588        hasher.update(LEAF_PREFIX);
589        hasher.update(leaf);
590        assert_eq!(tree.root().bytes(), hasher.finalize().into_inner());
591    }
592
593    #[test]
594    fn empty_element_tree_root_is_hash_of_empty_leaf() {
595        let tree = MerkleTree::build_from_serialized([&[][..]]);
596        let mut hasher = Hasher::new();
597        hasher.update(LEAF_PREFIX);
598        hasher.update::<&[u8]>(&[]);
599        assert_eq!(tree.root().bytes(), hasher.finalize().into_inner());
600    }
601
602    #[test]
603    fn get_proof_out_of_bounds() {
604        for i in 0..TEST_INPUT.len() {
605            let tree = MerkleTree::build_from_serialized(&TEST_INPUT[..i]);
606            assert_eq!(
607                tree.get_proof(i.next_power_of_two()),
608                Err(MerkleError::InvalidInput),
609            );
610        }
611    }
612
613    #[test]
614    fn every_proof_round_trips() {
615        for i in 0..TEST_INPUT.len() {
616            let tree = MerkleTree::build_from_serialized(&TEST_INPUT[..i]);
617            for (index, leaf) in TEST_INPUT[..i].iter().enumerate() {
618                let proof = tree.get_proof(index).unwrap();
619                proof
620                    .verify_proof_with_leaf_bytes(&tree.root(), leaf, index)
621                    .unwrap();
622            }
623        }
624    }
625
626    #[test]
627    fn proof_fails_for_wrong_index() {
628        for i in 1..TEST_INPUT.len() {
629            let tree = MerkleTree::build_from_serialized(&TEST_INPUT[..i]);
630            for (index, leaf) in TEST_INPUT[..i].iter().enumerate() {
631                let proof = tree.get_proof(index).unwrap();
632                assert_eq!(
633                    proof.verify_proof_with_leaf_bytes(&tree.root(), leaf, index + 1),
634                    Err(MerkleError::InvalidProof),
635                );
636            }
637        }
638    }
639
640    #[test]
641    fn proof_fails_for_tampered_leaf() {
642        let tree = MerkleTree::build_from_serialized(TEST_INPUT);
643        let proof = tree.get_proof(3).unwrap();
644        let tampered = b"not-the-real-leaf";
645        assert_eq!(
646            proof.verify_proof_with_leaf_bytes(&tree.root(), tampered, 3),
647            Err(MerkleError::InvalidProof),
648        );
649    }
650
651    #[test]
652    fn proof_fails_against_wrong_root() {
653        let tree = MerkleTree::build_from_serialized(TEST_INPUT);
654        let proof = tree.get_proof(2).unwrap();
655        let wrong_root = Node::Digest([0xab; DIGEST_LEN]);
656        assert_eq!(
657            proof.verify_proof_with_leaf_bytes(&wrong_root, TEST_INPUT[2], 2),
658            Err(MerkleError::InvalidProof),
659        );
660    }
661
662    #[test]
663    fn is_right_most_detects_last_leaf() {
664        for i in 1..TEST_INPUT.len() {
665            let tree = MerkleTree::build_from_serialized(&TEST_INPUT[..i]);
666            for j in 0..i {
667                let proof = tree.get_proof(j).unwrap();
668                let expected = j == i - 1;
669                assert_eq!(proof.is_right_most(j), expected);
670            }
671        }
672    }
673
674    /// Non-inclusion proof for an empty tree: any target is trivially
675    /// non-included, both neighbours are absent, and the index is zero.
676    #[test]
677    fn non_inclusion_empty_tree() {
678        let tree = MerkleTree::build_from_unserialized::<[&[u8]; 0]>([]).unwrap();
679        let leaves: [&[u8]; 0] = [];
680        let proof = tree
681            .compute_non_inclusion_proof(&leaves, &b"foo".as_ref())
682            .unwrap();
683        assert!(proof.left_leaf().is_none());
684        assert!(proof.right_leaf().is_none());
685        assert_eq!(proof.index(), 0);
686        proof.verify_proof(&tree.root(), &b"foo".as_ref()).unwrap();
687        proof.verify_proof(&tree.root(), &b"bar".as_ref()).unwrap();
688    }
689
690    /// Single-leaf tree: a different target is non-included; the leaf
691    /// itself cannot have a non-inclusion proof constructed.
692    #[test]
693    fn non_inclusion_single_leaf() {
694        let leaves: [&[u8]; 1] = [b"foo"];
695        let tree = MerkleTree::build_from_unserialized(&leaves).unwrap();
696
697        let proof = tree
698            .compute_non_inclusion_proof(&leaves, &b"bar".as_ref())
699            .unwrap();
700        proof.verify_proof(&tree.root(), &b"bar".as_ref()).unwrap();
701
702        // Re-using a proof against a leaf that is in the tree must fail.
703        assert_eq!(
704            proof.verify_proof(&tree.root(), &b"foo".as_ref()),
705            Err(MerkleError::InvalidProof),
706        );
707
708        // Asking for a non-inclusion proof of a leaf that is in the tree
709        // is a caller error.
710        assert_eq!(
711            tree.compute_non_inclusion_proof(&leaves, &b"foo".as_ref()),
712            Err(MerkleError::InvalidInput),
713        );
714    }
715
716    /// Many-leaf tree: every non-tree target verifies as non-included, and
717    /// every tree-member target is rejected by the constructor.
718    #[test]
719    fn non_inclusion_multiple_leaves() {
720        const RAW: [&str; 9] = [
721            "foo", "bar", "fizz", "baz", "buzz", "fizz", "foobar", "walrus", "fizz",
722        ];
723        let mut sorted: Vec<&str> = RAW.to_vec();
724        sorted.sort();
725        sorted.dedup();
726        let tree = MerkleTree::build_from_unserialized(&sorted).unwrap();
727
728        // Mix of targets that are not in the tree and targets that are.
729        let probes = ["fuzz", "yankee", "aloha", "foo", "bar", "fizz", "walrus"];
730        for probe in probes {
731            let result = tree.compute_non_inclusion_proof(&sorted, &probe);
732            if sorted.contains(&probe) {
733                assert_eq!(result, Err(MerkleError::InvalidInput));
734            } else {
735                let proof = result.unwrap();
736                proof.verify_proof(&tree.root(), &probe).unwrap();
737            }
738        }
739    }
740
741    /// Targets at the extremes of the sort order land in the two
742    /// asymmetric branches (no left neighbour, or no right neighbour with
743    /// the left neighbour being the right-most leaf).
744    #[test]
745    fn non_inclusion_at_extremes() {
746        let sorted: [&str; 3] = ["bar", "foo", "qux"];
747        let tree = MerkleTree::build_from_unserialized(&sorted).unwrap();
748
749        // Before everything.
750        let before = tree.compute_non_inclusion_proof(&sorted, &"aaa").unwrap();
751        assert!(before.left_leaf().is_none());
752        assert!(before.right_leaf().is_some());
753        assert_eq!(before.index(), 0);
754        before.verify_proof(&tree.root(), &"aaa").unwrap();
755
756        // After everything.
757        let after = tree.compute_non_inclusion_proof(&sorted, &"zzz").unwrap();
758        assert!(after.left_leaf().is_some());
759        assert!(after.right_leaf().is_none());
760        assert_eq!(after.index(), sorted.len());
761        after.verify_proof(&tree.root(), &"zzz").unwrap();
762    }
763
764    /// Forged proof that claims `index = 0` while also supplying a left
765    /// neighbour does not panic and does not verify. Mirrors upstream's
766    /// regression test for `is_valid_neighbor` returning sensibly.
767    #[test]
768    fn non_inclusion_forged_zero_index_with_left_leaf() {
769        let leaves: [&[u8]; 1] = [b"foo"];
770        let tree = MerkleTree::build_from_unserialized(&leaves).unwrap();
771        let fake: &[u8] = b"fake";
772
773        let forged = MerkleNonInclusionProof::new(
774            0,
775            Some((fake, tree.get_proof(0).unwrap())),
776            Some((fake, tree.get_proof(0).unwrap())),
777        );
778        assert_eq!(
779            forged.verify_proof(&tree.root(), &fake),
780            Err(MerkleError::InvalidProof),
781        );
782    }
783
784    /// Pinned root for `TEST_INPUT` under our `LEAF_PREFIX`/`INNER_PREFIX`/
785    /// `EMPTY_NODE` scheme. This was captured from upstream
786    /// `fastcrypto::merkle::MerkleTree<Blake2b256>::root()`, so a regression
787    /// in any of the load-bearing pieces of the hash construction (leaf
788    /// prefix, inner prefix, empty-node bytes, padding rule) would change
789    /// this value and fail the test.
790    #[test]
791    fn root_matches_upstream_for_known_input() {
792        const EXPECTED_ROOT: [u8; DIGEST_LEN] = [
793            0x8d, 0x01, 0x06, 0x76, 0xde, 0x3d, 0x66, 0x08, 0x77, 0xcc, 0x8c, 0x27, 0xa4, 0x2d,
794            0xcf, 0xf9, 0xc1, 0x15, 0x97, 0x20, 0x36, 0x1a, 0x82, 0x36, 0xd2, 0xd2, 0x07, 0xb6,
795            0x8b, 0x72, 0x9b, 0x0c,
796        ];
797
798        let tree = MerkleTree::build_from_serialized(TEST_INPUT);
799        assert_eq!(tree.root().bytes(), EXPECTED_ROOT);
800    }
801
802    /// Property-based tests for the proof machinery. Each property covers
803    /// a contract that the hand-written unit tests above only spot-check.
804    ///
805    /// Gated on `feature = "proptest"` to match the rest of the crate's
806    /// proptest surface (see `serialization_proptests.rs`).
807    #[cfg(feature = "proptest")]
808    mod proptests {
809        use super::*;
810
811        use proptest::collection::vec;
812        use proptest::prelude::*;
813        use test_strategy::proptest;
814
815        // Explicit `test` binding so `#[proptest]`'s expansion to
816        // `#[test]` resolves unambiguously: the parent `mod tests` brings
817        // the wasm-bindgen-test alias into scope via `use super::*` here,
818        // which would otherwise conflict with the built-in `#[test]`
819        // attribute. An explicit `use` dominates both the glob and the
820        // outer scope, matching the pattern in `serialization_proptests`.
821        #[cfg(target_arch = "wasm32")]
822        use wasm_bindgen_test::wasm_bindgen_test as test;
823
824        /// Non-empty `Vec<u32>` of length 1..=32. u32 is convenient
825        /// because it is `Ord + Serialize` (so it works for both
826        /// inclusion and non-inclusion trees) and its BCS encoding is a
827        /// fixed 4 bytes per leaf.
828        fn small_leaves() -> impl Strategy<Value = Vec<u32>> {
829            vec(any::<u32>(), 1..=32)
830        }
831
832        /// Sorted, deduplicated `Vec<u32>` of length 0..=32. Required
833        /// shape for `compute_non_inclusion_proof`, whose sorted-leaf
834        /// invariant is what makes neighbour-based non-inclusion sound.
835        fn sorted_unique_leaves() -> impl Strategy<Value = Vec<u32>> {
836            vec(any::<u32>(), 0..=32).prop_map(|mut v| {
837                v.sort();
838                v.dedup();
839                v
840            })
841        }
842
843        /// For any non-empty leaf set, the proof produced by
844        /// [`MerkleTree::get_proof`] verifies for every leaf at its
845        /// reported index.
846        #[proptest]
847        fn inclusion_proof_round_trips(#[strategy(small_leaves())] leaves: Vec<u32>) {
848            let tree = MerkleTree::build_from_unserialized(leaves.iter()).unwrap();
849            let root = tree.root();
850            for (index, leaf) in leaves.iter().enumerate() {
851                let proof = tree.get_proof(index).unwrap();
852                proof
853                    .verify_proof(&root, leaf, index)
854                    .expect("freshly-built proof must verify");
855            }
856        }
857
858        /// Reusing a proof at index `i` to "verify" a different leaf
859        /// value at the same index is rejected. The duplicate-leaves
860        /// edge case (where two indices happen to share the same value
861        /// and the proof actually does verify) is filtered out
862        /// explicitly — that is correct behaviour for a leaf-bytes
863        /// merkle tree, not a regression.
864        #[proptest]
865        fn inclusion_proof_rejects_wrong_leaf(#[strategy(small_leaves())] leaves: Vec<u32>) {
866            prop_assume!(leaves.len() >= 2);
867            let tree = MerkleTree::build_from_unserialized(leaves.iter()).unwrap();
868            let root = tree.root();
869            for (index, leaf) in leaves.iter().enumerate() {
870                let other_index = (index + 1) % leaves.len();
871                if leaves[other_index] == *leaf {
872                    continue;
873                }
874                let proof = tree.get_proof(index).unwrap();
875                prop_assert!(
876                    proof
877                        .verify_proof(&root, &leaves[other_index], index)
878                        .is_err(),
879                    "proof for index {index} must not verify a different leaf at the same index",
880                );
881            }
882        }
883
884        /// For any sorted leaf set and any target that does not appear
885        /// in it, the non-inclusion proof produced for the target
886        /// verifies against the tree's root.
887        #[proptest]
888        fn non_inclusion_proof_round_trips(
889            #[strategy(sorted_unique_leaves())] leaves: Vec<u32>,
890            target: u32,
891        ) {
892            // The target is drawn independently of the leaves; skip the
893            // (rare) cases where it collides with one of them.
894            prop_assume!(leaves.binary_search(&target).is_err());
895            let tree = MerkleTree::build_from_unserialized(leaves.iter()).unwrap();
896            let root = tree.root();
897            let proof = tree.compute_non_inclusion_proof(&leaves, &target).unwrap();
898            proof
899                .verify_proof(&root, &target)
900                .expect("freshly-built non-inclusion proof must verify");
901        }
902
903        /// Constructing a non-inclusion proof for a target that *is* in
904        /// the tree is a caller error.
905        #[proptest]
906        fn non_inclusion_rejects_present_target(
907            #[strategy(sorted_unique_leaves())] leaves: Vec<u32>,
908        ) {
909            prop_assume!(!leaves.is_empty());
910            let tree = MerkleTree::build_from_unserialized(leaves.iter()).unwrap();
911            for present in &leaves {
912                prop_assert_eq!(
913                    tree.compute_non_inclusion_proof(&leaves, present),
914                    Err(MerkleError::InvalidInput),
915                );
916            }
917        }
918
919        /// `is_right_most(j)` holds for exactly the last leaf index of
920        /// the tree, for every other index it does not. This pins the
921        /// behaviour used by [`MerkleNonInclusionProof::verify_proof`]
922        /// when the target sorts past every present leaf.
923        #[proptest]
924        fn is_right_most_only_for_last_leaf(#[strategy(small_leaves())] leaves: Vec<u32>) {
925            let tree = MerkleTree::build_from_unserialized(leaves.iter()).unwrap();
926            let last = leaves.len() - 1;
927            for j in 0..leaves.len() {
928                let proof = tree.get_proof(j).unwrap();
929                prop_assert_eq!(proof.is_right_most(j), j == last);
930            }
931        }
932    }
933}
sui_sdk_types/merkle.rs

sui_sdk_types/
merkle.rs
