celestia_types/nmt/
namespace_proof.rs

1use std::ops::{Deref, DerefMut};
2
3use celestia_proto::celestia::core::v1::proof::NmtProof as RawNmtProof;
4use celestia_proto::proof::pb::Proof as RawProof;
5use nmt_rs::simple_merkle::proof::Proof as NmtProof;
6use serde::{Deserialize, Serialize};
7use tendermint_proto::Protobuf;
8
9use crate::nmt::{NS_SIZE, NamespacedHash, NamespacedHashExt, NamespacedSha2Hasher};
10use crate::{Error, Result};
11
12type NmtNamespaceProof = nmt_rs::nmt_proof::NamespaceProof<NamespacedSha2Hasher, NS_SIZE>;
13
14/// A helper constant to be used as leaves when verifying the [`NamespaceProof`] of absence.
15pub const EMPTY_LEAVES: &[&[u8]] = &[];
16
17/// Merkle proof of inclusion or absence of some data in the [`Nmt`].
18///
19/// # Example
20///
21/// ```
22/// use nmt_rs::NamespaceMerkleHasher;
23/// use celestia_types::nmt::{Namespace, Nmt, NamespacedSha2Hasher, EMPTY_LEAVES};
24///
25/// let ns1 = Namespace::new_v0(&[1]).unwrap();
26/// let ns2 = Namespace::new_v0(&[2]).unwrap();
27/// let ns3 = Namespace::new_v0(&[3]).unwrap();
28/// let ns4 = Namespace::new_v0(&[4]).unwrap();
29///
30/// let leaves = [
31///     (ns1, b"leaf0"),
32///     (ns2, b"leaf1"),
33///     (ns2, b"leaf2"),
34///     (ns4, b"leaf3"),
35/// ];
36///
37/// // create the nmt and feed it with data
38/// let mut nmt = Nmt::with_hasher(NamespacedSha2Hasher::with_ignore_max_ns(true));
39///
40/// for (namespace, data) in leaves {
41///     nmt.push_leaf(data, *namespace);
42/// }
43///
44/// // create and verify the proof of inclusion of namespace 2 data
45/// let root = nmt.root();
46/// let proof = nmt.get_namespace_proof(*ns2);
47/// assert!(proof.is_of_presence());
48/// assert!(
49///     proof.verify_complete_namespace(&root, &["leaf1", "leaf2"], *ns2).is_ok()
50/// );
51///
52/// // create and verify the proof of absence of namespace 3 data
53/// let proof = nmt.get_namespace_proof(*ns3);
54/// assert!(proof.is_of_absence());
55/// assert!(
56///     proof.verify_complete_namespace(&root, EMPTY_LEAVES, *ns3).is_ok()
57/// );
58/// ```
59///
60/// [`Nmt`]: crate::nmt::Nmt
61#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
62#[serde(try_from = "RawProof", into = "RawProof")]
63pub struct NamespaceProof(NmtNamespaceProof);
64
65impl NamespaceProof {
66    /// Convert the proof to the underlying [`nmt_rs`] equivalent.
67    pub fn into_inner(self) -> NmtNamespaceProof {
68        self.0
69    }
70
71    /// Get the hash of the leaf following the [`Namespace`] which absence is being proven.
72    ///
73    /// If the tree had contained the proven namespace, it should be in the tree
74    /// right before the leaf returned by this function.
75    ///
76    /// This function returns [`None`] if the proof isn't an [`AbsenceProof`] or the
77    /// proven [`Namespace`] is not in the range of the tree root [`NamespacedHash`].
78    ///
79    /// [`Namespace`]: crate::nmt::Namespace
80    /// [`AbsenceProof`]: NmtNamespaceProof::PresenceProof
81    /// [`NamespacedHash`]: crate::nmt::NamespacedHash
82    pub fn leaf(&self) -> Option<&NamespacedHash> {
83        match &self.0 {
84            NmtNamespaceProof::AbsenceProof { leaf, .. } => leaf.as_ref(),
85            _ => None,
86        }
87    }
88
89    /// Returns true if the proof ignores all the leaves inserted with
90    /// [`Namespace::PARITY_SHARE`].
91    ///
92    /// [`Namespace::PARITY_SHARE`]: crate::nmt::Namespace::PARITY_SHARE
93    pub fn max_ns_ignored(&self) -> bool {
94        match &self.0 {
95            NmtNamespaceProof::AbsenceProof { ignore_max_ns, .. }
96            | NmtNamespaceProof::PresenceProof { ignore_max_ns, .. } => *ignore_max_ns,
97        }
98    }
99
100    /// Returns total amount of leaves in a tree for which proof was constructed.
101    ///
102    /// This method only works if the proof is created for a single leaf and it
103    /// assumes that the tree is perfect, i.e. it's amount of leaves is power of 2.
104    pub(crate) fn total_leaves(&self) -> Option<usize> {
105        // If the proof is for a single leaf, then it must contain a sibling
106        // for each tree level. Based on that we can recompute the total amount
107        // of leaves in a tree.
108        if self.end_idx().saturating_sub(self.start_idx()) == 1 {
109            Some(1 << self.siblings().len())
110        } else {
111            None
112        }
113    }
114}
115
116impl Deref for NamespaceProof {
117    type Target = NmtNamespaceProof;
118
119    fn deref(&self) -> &Self::Target {
120        &self.0
121    }
122}
123
124impl DerefMut for NamespaceProof {
125    fn deref_mut(&mut self) -> &mut Self::Target {
126        &mut self.0
127    }
128}
129
130impl From<NamespaceProof> for NmtNamespaceProof {
131    fn from(value: NamespaceProof) -> NmtNamespaceProof {
132        value.0
133    }
134}
135
136impl From<NmtNamespaceProof> for NamespaceProof {
137    fn from(value: NmtNamespaceProof) -> NamespaceProof {
138        NamespaceProof(value)
139    }
140}
141
142impl Protobuf<RawProof> for NamespaceProof {}
143
144impl TryFrom<RawProof> for NamespaceProof {
145    type Error = Error;
146
147    fn try_from(value: RawProof) -> Result<Self, Self::Error> {
148        let siblings = value
149            .nodes
150            .iter()
151            .map(|bytes| NamespacedHash::from_raw(bytes))
152            .collect::<Result<Vec<_>>>()?;
153
154        let mut proof = NmtNamespaceProof::PresenceProof {
155            proof: NmtProof {
156                siblings,
157                range: value.start as u32..value.end as u32,
158            },
159            ignore_max_ns: value.is_max_namespace_ignored,
160        };
161
162        if !value.leaf_hash.is_empty() {
163            proof.convert_to_absence_proof(NamespacedHash::from_raw(&value.leaf_hash)?);
164        }
165
166        Ok(NamespaceProof(proof))
167    }
168}
169
170impl From<NamespaceProof> for RawProof {
171    fn from(value: NamespaceProof) -> Self {
172        RawProof {
173            start: value.start_idx() as i64,
174            end: value.end_idx() as i64,
175            nodes: value.siblings().iter().map(|hash| hash.to_vec()).collect(),
176            leaf_hash: value.leaf().map(|hash| hash.to_vec()).unwrap_or_default(),
177            is_max_namespace_ignored: value.max_ns_ignored(),
178        }
179    }
180}
181
182impl TryFrom<RawNmtProof> for NamespaceProof {
183    type Error = Error;
184
185    fn try_from(value: RawNmtProof) -> Result<Self, Self::Error> {
186        let raw_proof = RawProof {
187            start: value.start as i64,
188            end: value.end as i64,
189            nodes: value.nodes,
190            leaf_hash: value.leaf_hash,
191            is_max_namespace_ignored: true,
192        };
193
194        raw_proof.try_into()
195    }
196}
197
198impl From<NamespaceProof> for RawNmtProof {
199    fn from(value: NamespaceProof) -> Self {
200        let raw_proof = RawProof::from(value);
201        RawNmtProof {
202            start: raw_proof.start as i32,
203            end: raw_proof.end as i32,
204            nodes: raw_proof.nodes,
205            leaf_hash: raw_proof.leaf_hash,
206        }
207    }
208}
209
210#[cfg(test)]
211mod tests {
212    use super::*;
213
214    #[test]
215    fn test_serialize_namespace_proof_binary() {
216        let nmt_proof = NmtNamespaceProof::PresenceProof {
217            proof: NmtProof {
218                siblings: vec![],
219                range: 0..1,
220            },
221            ignore_max_ns: false,
222        };
223        let proof = NamespaceProof::from(nmt_proof);
224        let serialized = postcard::to_allocvec(&proof).unwrap();
225        let deserialized: NamespaceProof = postcard::from_bytes(&serialized).unwrap();
226        assert_eq!(proof, deserialized);
227    }
228}
celestia_types/nmt/namespace_proof.rs

celestia_types/nmt/
namespace_proof.rs
