nmt_rs/
nmt_proof.rs

1//! Adds "namespacing" semantics to proofs for the simple merkle tree, enabling
2//! consumers to check that
3//! - A range of leaves forms a complete namespace
4//! - A range of leaves all exists in the same namespace
5use crate::maybestd::{mem, vec::Vec};
6use crate::{
7    namespaced_hash::{NamespaceId, NamespaceMerkleHasher, NamespacedHash},
8    simple_merkle::{
9        db::NoopDb, error::RangeProofError, proof::Proof, tree::MerkleHash,
10        utils::compute_num_left_siblings,
11    },
12    NamespaceMerkleTree,
13};
14
15/// A proof of some statement about a namespaced merkle tree.
16///
17/// This proof may prove the presence of some set of leaves, or the
18/// absence of a particular namespace
19#[derive(Debug, PartialEq, Clone)]
20#[cfg_attr(
21    feature = "borsh",
22    derive(borsh::BorshSerialize, borsh::BorshDeserialize)
23)]
24#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
25pub enum NamespaceProof<M: MerkleHash, const NS_ID_SIZE: usize> {
26    /// A proof that some item is absent from the tree
27    AbsenceProof {
28        /// The range proof against the inner merkle tree
29        proof: Proof<M>,
30        /// Whether to treat the maximum possible namespace as a special marker value and ignore it in computing namespace ranges
31        ignore_max_ns: bool,
32        /// A leaf that *is* present in the tree, if the namespace being proven absent falls within
33        /// the namespace range covered by the root.
34        leaf: Option<NamespacedHash<NS_ID_SIZE>>,
35    },
36    /// A proof that some item is included in the tree
37    PresenceProof {
38        /// The range proof against the inner merkle tree
39        proof: Proof<M>,
40        /// Whether to treat the maximum possible namespace as a special marker value and ignore it in computing namespace ranges
41        ignore_max_ns: bool,
42    },
43}
44
45impl<M, const NS_ID_SIZE: usize> NamespaceProof<M, NS_ID_SIZE>
46where
47    M: NamespaceMerkleHasher<NS_ID_SIZE, Output = NamespacedHash<NS_ID_SIZE>>,
48{
49    /// Verify that the provided *raw* leaves are a complete namespace. This may be a proof of presence or absence.
50    pub fn verify_complete_namespace(
51        &self,
52        root: &NamespacedHash<NS_ID_SIZE>,
53        raw_leaves: &[impl AsRef<[u8]>],
54        namespace: NamespaceId<NS_ID_SIZE>,
55    ) -> Result<(), RangeProofError> {
56        if self.is_of_presence() && raw_leaves.len() != self.range_len() {
57            return Err(RangeProofError::WrongAmountOfLeavesProvided);
58        }
59
60        let tree = NamespaceMerkleTree::<NoopDb, M, NS_ID_SIZE>::with_hasher(
61            M::with_ignore_max_ns(self.ignores_max_ns()),
62        );
63        tree.verify_namespace(root, raw_leaves, namespace, self)
64    }
65
66    /// Verify a that the provided *raw* leaves are a (1) present and (2) form a contiguous subset of some namespace
67    pub fn verify_range(
68        &self,
69        root: &NamespacedHash<NS_ID_SIZE>,
70        raw_leaves: &[impl AsRef<[u8]>],
71        leaf_namespace: NamespaceId<NS_ID_SIZE>,
72    ) -> Result<(), RangeProofError> {
73        if self.is_of_absence() {
74            return Err(RangeProofError::MalformedProof(
75                "Cannot prove that a partial namespace is absent",
76            ));
77        };
78
79        if raw_leaves.len() != self.range_len() {
80            return Err(RangeProofError::WrongAmountOfLeavesProvided);
81        }
82
83        let leaf_hashes: Vec<_> = raw_leaves
84            .iter()
85            .map(|data| {
86                M::with_ignore_max_ns(self.ignores_max_ns())
87                    .hash_leaf_with_namespace(data.as_ref(), leaf_namespace)
88            })
89            .collect();
90        let tree = NamespaceMerkleTree::<NoopDb, M, NS_ID_SIZE>::with_hasher(
91            M::with_ignore_max_ns(self.ignores_max_ns()),
92        );
93        tree.inner.check_range_proof(
94            root,
95            &leaf_hashes,
96            self.siblings(),
97            self.start_idx() as usize,
98        )
99    }
100
101    /// Narrows the proof range: uses an existing proof to create
102    /// a new proof for a subrange of the original proof's range
103    ///
104    /// # Arguments
105    ///  - left_extra_raw_leaves: The data for the leaves that will narrow the range from the left
106    ///    side (i.e. all the leaves from the left edge of the currently proven range, to the left
107    ///    edge of the new desired shrunk range)
108    ///  - right_extra_raw_leaves: Analogously, data for all the leaves between the right edge of
109    ///    the desired shrunken range, and the right edge of the current proof's range
110    pub fn narrow_range<L: AsRef<[u8]>>(
111        &self,
112        left_extra_raw_leaves: &[L],
113        right_extra_raw_leaves: &[L],
114        leaf_namespace: NamespaceId<NS_ID_SIZE>,
115    ) -> Result<Self, RangeProofError> {
116        if self.is_of_absence() {
117            return Err(RangeProofError::MalformedProof(
118                "Cannot narrow the range of an absence proof",
119            ));
120        }
121
122        let leaves_to_hashes = |l: &[L]| -> Vec<NamespacedHash<NS_ID_SIZE>> {
123            l.iter()
124                .map(|data| {
125                    M::with_ignore_max_ns(self.ignores_max_ns())
126                        .hash_leaf_with_namespace(data.as_ref(), leaf_namespace)
127                })
128                .collect()
129        };
130        let left_extra_hashes = leaves_to_hashes(left_extra_raw_leaves);
131        let right_extra_hashes = leaves_to_hashes(right_extra_raw_leaves);
132
133        let proof = self.merkle_proof().narrow_range_with_hasher(
134            &left_extra_hashes,
135            &right_extra_hashes,
136            M::with_ignore_max_ns(self.ignores_max_ns()),
137        )?;
138
139        Ok(Self::PresenceProof {
140            proof,
141            ignore_max_ns: self.ignores_max_ns(),
142        })
143    }
144
145    /// Convert a proof of the presence of some leaf to the proof of the absence of another leaf
146    pub fn convert_to_absence_proof(&mut self, leaf: NamespacedHash<NS_ID_SIZE>) {
147        match self {
148            NamespaceProof::AbsenceProof { .. } => {}
149            NamespaceProof::PresenceProof {
150                proof,
151                ignore_max_ns,
152            } => {
153                let pf = mem::take(proof);
154                *self = Self::AbsenceProof {
155                    proof: pf,
156                    ignore_max_ns: *ignore_max_ns,
157                    leaf: Some(leaf),
158                }
159            }
160        }
161    }
162
163    fn merkle_proof(&self) -> &Proof<M> {
164        match self {
165            NamespaceProof::AbsenceProof { proof, .. }
166            | NamespaceProof::PresenceProof { proof, .. } => proof,
167        }
168    }
169
170    /// Returns the siblings provided as part of the proof
171    pub fn siblings(&self) -> &[NamespacedHash<NS_ID_SIZE>] {
172        self.merkle_proof().siblings()
173    }
174
175    /// Returns the index of the first leaf in the proof
176    pub fn start_idx(&self) -> u32 {
177        self.merkle_proof().start_idx()
178    }
179
180    /// Returns the index *after* the last leaf in the proof
181    pub fn end_idx(&self) -> u32 {
182        self.merkle_proof().end_idx()
183    }
184
185    /// Returns the number of leaves covered by the proof
186    fn range_len(&self) -> usize {
187        self.merkle_proof().range_len()
188    }
189
190    /// Returns the leftmost node to the right of the proven range, if one exists
191    pub fn leftmost_right_sibling(&self) -> Option<&NamespacedHash<NS_ID_SIZE>> {
192        let siblings = self.siblings();
193        let num_left_siblings = compute_num_left_siblings(self.start_idx() as usize);
194        if siblings.len() > num_left_siblings {
195            return Some(&siblings[num_left_siblings]);
196        }
197        None
198    }
199
200    /// Returns the rightmost node to the left of the proven range, if one exists
201    pub fn rightmost_left_sibling(&self) -> Option<&NamespacedHash<NS_ID_SIZE>> {
202        let siblings = self.siblings();
203        let num_left_siblings = compute_num_left_siblings(self.start_idx() as usize);
204        if num_left_siblings != 0 && num_left_siblings <= siblings.len() {
205            return Some(&siblings[num_left_siblings - 1]);
206        }
207        None
208    }
209
210    fn ignores_max_ns(&self) -> bool {
211        match self {
212            Self::AbsenceProof { ignore_max_ns, .. }
213            | Self::PresenceProof { ignore_max_ns, .. } => *ignore_max_ns,
214        }
215    }
216
217    /// Returns true if the proof is an absence proof
218    pub fn is_of_absence(&self) -> bool {
219        match self {
220            Self::AbsenceProof { .. } => true,
221            Self::PresenceProof { .. } => false,
222        }
223    }
224
225    /// Returns true if the proof is a presence proof
226    pub fn is_of_presence(&self) -> bool {
227        !self.is_of_absence()
228    }
229}
nmt_rs/nmt_proof.rs

nmt_rs/
nmt_proof.rs
