nmt_rs/simple_merkle/
proof.rs

1use core::{cmp::Ordering, ops::Range};
2
3use super::{
4    db::NoopDb,
5    error::RangeProofError,
6    tree::{MerkleHash, MerkleTree},
7    utils::compute_num_left_siblings,
8};
9use crate::maybestd::vec::Vec;
10
11/// A proof of some statement about a namespaced merkle tree.
12///
13/// This proof may prove the presence of some set of leaves, or the
14/// absence of a particular namespace
15#[derive(Debug, PartialEq, Clone)]
16#[cfg_attr(
17    feature = "borsh",
18    derive(borsh::BorshSerialize, borsh::BorshDeserialize)
19)]
20#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
21pub struct Proof<M: MerkleHash> {
22    /// The siblings to be used to build the path to the root.
23    pub siblings: Vec<M::Output>,
24    /// The range of indices covered by the proof.
25    pub range: Range<u32>,
26}
27
28impl<M: MerkleHash> Default for Proof<M> {
29    fn default() -> Self {
30        Self {
31            siblings: Default::default(),
32            range: Default::default(),
33        }
34    }
35}
36
37impl<M> Proof<M>
38where
39    M: MerkleHash + Default,
40{
41    /// Verify a range proof
42    pub fn verify_range(
43        &self,
44        root: &M::Output,
45        leaf_hashes: &[M::Output],
46    ) -> Result<(), RangeProofError> {
47        if leaf_hashes.len() != self.range_len() {
48            return Err(RangeProofError::WrongAmountOfLeavesProvided);
49        }
50
51        let tree = MerkleTree::<NoopDb, M>::new();
52        tree.check_range_proof(
53            root,
54            leaf_hashes,
55            self.siblings(),
56            self.start_idx() as usize,
57        )
58    }
59}
60
61impl<M> Proof<M>
62where
63    M: MerkleHash,
64{
65    /// Verify a range proof
66    pub fn verify_range_with_hasher(
67        &self,
68        root: &M::Output,
69        leaf_hashes: &[M::Output],
70        hasher: M,
71    ) -> Result<(), RangeProofError> {
72        if leaf_hashes.len() != self.range_len() {
73            return Err(RangeProofError::WrongAmountOfLeavesProvided);
74        }
75
76        let tree = MerkleTree::<NoopDb, M>::with_hasher(hasher);
77        tree.check_range_proof(
78            root,
79            leaf_hashes,
80            self.siblings(),
81            self.start_idx() as usize,
82        )
83    }
84
85    /// Narrows the proof range: uses an existing proof to create
86    /// a new proof for a subrange of the original proof's range
87    ///
88    /// # Arguments
89    ///  - left_extra_leaves: The hashes of the leaves that will narrow the range from the left
90    ///    side (i.e. all the leaves from the left edge of the currently proven range, to the left
91    ///    edge of the new desired shrunk range)
92    ///  - right_extra_leaves: Analogously, hashes of all the leaves between the right edge of
93    ///    the desired shrunken range, and the right edge of the current proof's range
94    pub fn narrow_range_with_hasher(
95        &self,
96        left_extra_leaves: &[M::Output],
97        right_extra_leaves: &[M::Output],
98        hasher: M,
99    ) -> Result<Self, RangeProofError> {
100        let new_leaf_len = left_extra_leaves
101            .len()
102            .checked_add(right_extra_leaves.len())
103            .ok_or(RangeProofError::TreeTooLarge)?;
104        match new_leaf_len.cmp(&self.range_len()) {
105            Ordering::Equal => {
106                // We cannot prove the empty range!
107                return Err(RangeProofError::NoLeavesProvided);
108            }
109            Ordering::Greater => return Err(RangeProofError::WrongAmountOfLeavesProvided),
110            Ordering::Less => { /* Ok! */ }
111        }
112
113        // Indices relative to the leaves of the entire tree
114        let new_start_idx = (self.start_idx() as usize)
115            .checked_add(left_extra_leaves.len())
116            .ok_or(RangeProofError::TreeTooLarge)?;
117        let new_end_idx = new_start_idx
118            .checked_add(self.range_len())
119            .and_then(|i| i.checked_sub(new_leaf_len))
120            .ok_or(RangeProofError::TreeTooLarge)?;
121
122        let mut tree = MerkleTree::<NoopDb, M>::with_hasher(hasher);
123        tree.narrow_range_proof(
124            left_extra_leaves,
125            new_start_idx..new_end_idx,
126            right_extra_leaves,
127            &mut self.siblings().as_slice(),
128            self.start_idx() as usize,
129        )
130    }
131
132    /// Returns the siblings provided as part of the proof.
133    pub fn siblings(&self) -> &Vec<M::Output> {
134        &self.siblings
135    }
136
137    /// Returns the index of the first leaf covered by the proof.
138    pub fn start_idx(&self) -> u32 {
139        self.range.start
140    }
141
142    /// Returns the index *after* the last leaf included in the proof.
143    pub fn end_idx(&self) -> u32 {
144        self.range.end
145    }
146
147    /// Returns the length of the range covered by the proof.
148    pub fn range_len(&self) -> usize {
149        self.range.end.saturating_sub(self.range.start) as usize
150    }
151
152    /// Returns the leftmost node to the right of the proven range, if one exists.
153    pub fn leftmost_right_sibling(&self) -> Option<&M::Output> {
154        let siblings = self.siblings();
155        let num_left_siblings = compute_num_left_siblings(self.start_idx() as usize);
156        if siblings.len() > num_left_siblings {
157            return Some(&siblings[num_left_siblings]);
158        }
159        None
160    }
161
162    /// Returns the rightmost node to the left of the proven range, if one exists.
163    pub fn rightmost_left_sibling(&self) -> Option<&M::Output> {
164        let siblings = self.siblings();
165        let num_left_siblings = compute_num_left_siblings(self.start_idx() as usize);
166        if num_left_siblings != 0 && num_left_siblings <= siblings.len() {
167            return Some(&siblings[num_left_siblings - 1]);
168        }
169        None
170    }
171}
nmt_rs/simple_merkle/proof.rs

nmt_rs/simple_merkle/
proof.rs
