nmt_rs/
namespaced_hash.rs

1use crate::maybestd::{cmp, fmt, marker::PhantomData, vec::Vec};
2use sha2::{Digest, Sha256};
3
4use crate::simple_merkle::tree::MerkleHash;
5/// The length of a hash in bytes
6pub const HASH_LEN: usize = 32;
7/// The default hasher. Currently sha256
8pub type DefaultHasher = Sha256;
9
10/// A domain separator indicating that a node is a leaf
11pub const LEAF_DOMAIN_SEPARATOR: [u8; 1] = [0u8];
12/// A domain separator indicating that a node is internal
13pub const INTERNAL_NODE_DOMAIN_SEPARATOR: [u8; 1] = [1u8];
14
15/// A sha256 hasher which also supports namespacing
16#[derive(Debug, Clone, PartialEq)]
17#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
18pub struct NamespacedSha2Hasher<const NS_ID_SIZE: usize> {
19    ignore_max_ns: bool,
20    _data: PhantomData<[u8; NS_ID_SIZE]>,
21}
22
23impl<const NS_ID_SIZE: usize> NamespaceMerkleHasher<NS_ID_SIZE>
24    for NamespacedSha2Hasher<NS_ID_SIZE>
25{
26    fn with_ignore_max_ns(ignore_max_ns: bool) -> Self {
27        Self {
28            ignore_max_ns,
29            _data: PhantomData,
30        }
31    }
32
33    fn ignores_max_ns(&self) -> bool {
34        self.ignore_max_ns
35    }
36
37    fn hash_leaf_with_namespace(
38        &self,
39        data: &[u8],
40        namespace: NamespaceId<NS_ID_SIZE>,
41    ) -> <Self as MerkleHash>::Output {
42        let mut output = NamespacedHash::with_min_and_max_ns(namespace, namespace);
43        let mut hasher = Sha256::new_with_prefix(LEAF_DOMAIN_SEPARATOR);
44        hasher.update(namespace.as_ref());
45        hasher.update(data.as_ref());
46        output.set_hash(hasher.finalize().as_ref());
47        output
48    }
49}
50
51// For tests, we add a default constructor which ignores the max namespace.
52// For actual use, this default be set at the tree level, not the hasher level.
53#[cfg(test)]
54impl<const NS_ID_SIZE: usize> Default for NamespacedSha2Hasher<NS_ID_SIZE> {
55    fn default() -> Self {
56        Self {
57            ignore_max_ns: true,
58            _data: PhantomData,
59        }
60    }
61}
62
63/// An extension of [`MerkleHash`] indicating that the hasher is namespace aware. This allows for the creation of
64/// namespaced merkle trees and namespaced merkle proofs.
65pub trait NamespaceMerkleHasher<const NS_ID_SIZE: usize>: MerkleHash {
66    /// Create a new hasher which ignores the max namespace
67    fn with_ignore_max_ns(ignore_max_ns: bool) -> Self;
68    /// Check whether the hasher ignores the max namespace
69    fn ignores_max_ns(&self) -> bool;
70    /// Hash the given data and namespace
71    fn hash_leaf_with_namespace(
72        &self,
73        data: &[u8],
74        namespace: NamespaceId<NS_ID_SIZE>,
75    ) -> <Self as MerkleHash>::Output;
76}
77
78impl<const NS_ID_SIZE: usize> MerkleHash for NamespacedSha2Hasher<NS_ID_SIZE> {
79    type Output = NamespacedHash<NS_ID_SIZE>;
80
81    const EMPTY_ROOT: NamespacedHash<NS_ID_SIZE> = NamespacedHash {
82        min_ns: NamespaceId([0; NS_ID_SIZE]),
83        max_ns: NamespaceId([0; NS_ID_SIZE]),
84        hash: [
85            227, 176, 196, 66, 152, 252, 28, 20, 154, 251, 244, 200, 153, 111, 185, 36, 39, 174,
86            65, 228, 100, 155, 147, 76, 164, 149, 153, 27, 120, 82, 184, 85,
87        ],
88    };
89
90    fn hash_leaf(&self, data: &[u8]) -> Self::Output {
91        let namespace_bytes = data[..NS_ID_SIZE].try_into().expect("Leaf of invalid size");
92        let namespace = NamespaceId(namespace_bytes);
93
94        let mut output = NamespacedHash::with_min_and_max_ns(namespace, namespace);
95        let mut hasher = DefaultHasher::new_with_prefix(LEAF_DOMAIN_SEPARATOR);
96        hasher.update(data.as_ref());
97        output.set_hash(hasher.finalize().as_ref());
98        output
99    }
100
101    fn hash_nodes(&self, left: &Self::Output, right: &Self::Output) -> Self::Output {
102        if left.max_namespace() > right.min_namespace() {
103            panic!("Invalid nodes: left max namespace must be <= right min namespace")
104        }
105        let mut hasher = DefaultHasher::new_with_prefix(INTERNAL_NODE_DOMAIN_SEPARATOR);
106        let max_nsid = NamespaceId::<NS_ID_SIZE>::max_id();
107
108        let min_ns = cmp::min(left.min_namespace(), right.min_namespace());
109        let max_ns = if self.ignore_max_ns && left.min_namespace() == max_nsid {
110            max_nsid
111        } else if self.ignore_max_ns && right.min_namespace() == max_nsid {
112            left.max_namespace()
113        } else {
114            cmp::max(left.max_namespace(), right.max_namespace())
115        };
116
117        let mut output = NamespacedHash::with_min_and_max_ns(min_ns, max_ns);
118
119        hasher.update(left.iter().collect::<Vec<_>>());
120        hasher.update(right.iter().collect::<Vec<_>>());
121
122        output.set_hash(hasher.finalize().as_ref());
123        output
124    }
125}
126
127/// A namespace identifier
128#[derive(Debug, PartialEq, PartialOrd, Eq, Ord, Copy, Clone, Hash)]
129#[cfg_attr(any(test, feature = "borsh"), derive(borsh::BorshSerialize))]
130pub struct NamespaceId<const NS_ID_SIZE: usize>(pub [u8; NS_ID_SIZE]);
131
132impl<const NS_ID_SIZE: usize> Default for NamespaceId<NS_ID_SIZE> {
133    fn default() -> Self {
134        Self([0; NS_ID_SIZE])
135    }
136}
137
138impl<const NS_ID_SIZE: usize> NamespaceId<NS_ID_SIZE> {
139    /// The maximum possible namespace id
140    pub const MAX_ID: NamespaceId<NS_ID_SIZE> = NamespaceId([0xff; NS_ID_SIZE]);
141    /// In celestia, 256 namespaces are reserved for "system" data. This is the maximum reserved namespace.
142    pub const MAX_RESERVED_ID_ON_CELESTIA: NamespaceId<NS_ID_SIZE> = {
143        let mut max_reserved = [0; NS_ID_SIZE];
144        max_reserved[NS_ID_SIZE - 1] = 255;
145        Self(max_reserved)
146    };
147
148    /// Returns maximum possible namespace id
149    pub const fn max_id() -> Self {
150        Self::MAX_ID
151    }
152
153    /// Indicates whether the namespace is reserved for system data on Celestia.
154    pub fn is_reserved_on_celestia(&self) -> bool {
155        self <= &Self::MAX_RESERVED_ID_ON_CELESTIA
156    }
157}
158
159impl<const NS_ID_SIZE: usize> AsRef<[u8]> for NamespaceId<NS_ID_SIZE> {
160    fn as_ref(&self) -> &[u8] {
161        self.0.as_ref()
162    }
163}
164
165/// An error indicating that a namespace is invalid
166#[derive(Debug, PartialEq, Copy, Clone)]
167pub struct InvalidNamespace;
168
169impl fmt::Display for InvalidNamespace {
170    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
171        f.write_str("InvalidNamespace")
172    }
173}
174
175#[cfg(feature = "std")]
176impl std::error::Error for InvalidNamespace {}
177
178impl<const NS_ID_SIZE: usize> TryFrom<&[u8]> for NamespaceId<NS_ID_SIZE> {
179    type Error = InvalidNamespace;
180
181    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
182        if value.len() != NS_ID_SIZE {
183            return Err(InvalidNamespace);
184        }
185        Ok(Self(value.try_into().unwrap()))
186    }
187}
188
189/// A hash of some data, together with a namespace range
190#[derive(Debug, PartialEq, Clone, Eq, Hash, PartialOrd, Ord)]
191#[cfg_attr(any(test, feature = "borsh"), derive(borsh::BorshSerialize))]
192pub struct NamespacedHash<const NS_ID_SIZE: usize> {
193    min_ns: NamespaceId<NS_ID_SIZE>,
194    max_ns: NamespaceId<NS_ID_SIZE>,
195    hash: [u8; HASH_LEN],
196}
197
198#[cfg(any(test, feature = "borsh"))]
199impl<const NS_ID_SIZE: usize> borsh::BorshDeserialize for NamespacedHash<NS_ID_SIZE> {
200    fn deserialize_reader<R: borsh::io::Read>(reader: &mut R) -> borsh::io::Result<Self> {
201        let mut min_ns = NamespaceId([0u8; NS_ID_SIZE]);
202        reader.read_exact(&mut min_ns.0)?;
203
204        let mut max_ns = NamespaceId([0u8; NS_ID_SIZE]);
205        reader.read_exact(&mut max_ns.0)?;
206
207        let mut hash = [0u8; HASH_LEN];
208        reader.read_exact(&mut hash)?;
209
210        Ok(NamespacedHash {
211            min_ns,
212            max_ns,
213            hash,
214        })
215    }
216}
217
218#[cfg(feature = "serde")]
219impl<const NS_ID_SIZE: usize> serde::Serialize for NamespacedHash<NS_ID_SIZE> {
220    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
221    where
222        S: serde::Serializer,
223    {
224        use serde::ser::SerializeTuple;
225        let mut seq = serializer.serialize_tuple(NamespacedHash::<NS_ID_SIZE>::size())?;
226        for byte in self.iter() {
227            seq.serialize_element(&byte)?;
228        }
229        seq.end()
230    }
231}
232
233#[cfg(feature = "serde")]
234impl<'de, const NS_ID_SIZE: usize> serde::Deserialize<'de> for NamespacedHash<NS_ID_SIZE> {
235    fn deserialize<D>(deserializer: D) -> Result<Self, <D as serde::Deserializer<'de>>::Error>
236    where
237        D: serde::Deserializer<'de>,
238    {
239        struct ArrayVisitor<T, const NS_ID_SIZE: usize> {
240            element: PhantomData<[T; NS_ID_SIZE]>,
241        }
242
243        impl<'de, T, const NS_ID_SIZE: usize> serde::de::Visitor<'de> for ArrayVisitor<T, NS_ID_SIZE>
244        where
245            T: Default + Copy + serde::Deserialize<'de>,
246        {
247            type Value = NamespacedHash<NS_ID_SIZE>;
248
249            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
250                formatter.write_str(&crate::maybestd::format!(
251                    "an array of length {}",
252                    NamespacedHash::<NS_ID_SIZE>::size()
253                ))
254            }
255
256            fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
257            where
258                A: serde::de::SeqAccess<'de>,
259            {
260                let seq: Vec<u8> = (0..NamespacedHash::<NS_ID_SIZE>::size())
261                    .map(|i| {
262                        seq.next_element()?
263                            .ok_or_else(|| serde::de::Error::invalid_length(i, &self))
264                    })
265                    .collect::<Result<_, _>>()?;
266                let ns_hash = seq
267                    .as_slice()
268                    .try_into()
269                    .map_err(|e: InvalidNamespacedHash| {
270                        serde::de::Error::custom(crate::maybestd::string::ToString::to_string(&e))
271                    })?;
272                Ok(ns_hash)
273            }
274        }
275
276        let visitor = ArrayVisitor {
277            element: PhantomData::<[u8; NS_ID_SIZE]>,
278        };
279
280        deserializer.deserialize_tuple(NamespacedHash::<NS_ID_SIZE>::size(), visitor)
281    }
282}
283
284impl<const NS_ID_SIZE: usize> Default for NamespacedHash<NS_ID_SIZE> {
285    fn default() -> Self {
286        Self {
287            min_ns: NamespaceId::default(),
288            max_ns: NamespaceId::default(),
289            hash: [0u8; HASH_LEN],
290        }
291    }
292}
293
294impl<const NS_ID_SIZE: usize> NamespacedHash<NS_ID_SIZE> {
295    /// Returns the size of the hash in bytes
296    pub const fn size() -> usize {
297        2 * NS_ID_SIZE + HASH_LEN
298    }
299
300    /// Construct a new namespaced hash from the provided components
301    pub const fn new(
302        min_ns: NamespaceId<NS_ID_SIZE>,
303        max_ns: NamespaceId<NS_ID_SIZE>,
304        hash: [u8; HASH_LEN],
305    ) -> Self {
306        Self {
307            min_ns,
308            max_ns,
309            hash,
310        }
311    }
312
313    /// Construct a namespaced hash with the provided namespace range and the zero hash
314    pub fn with_min_and_max_ns(
315        min_ns: NamespaceId<NS_ID_SIZE>,
316        max_ns: NamespaceId<NS_ID_SIZE>,
317    ) -> Self {
318        Self {
319            min_ns,
320            max_ns,
321            ..Default::default()
322        }
323    }
324
325    /// Returns the min namespace id of the hash
326    pub fn min_namespace(&self) -> NamespaceId<NS_ID_SIZE> {
327        self.min_ns
328    }
329
330    /// Returns the max namespace id of the hash
331    pub fn max_namespace(&self) -> NamespaceId<NS_ID_SIZE> {
332        self.max_ns
333    }
334
335    /// Returns the hash without the namespace range
336    pub fn hash(&self) -> [u8; HASH_LEN] {
337        self.hash
338    }
339
340    fn set_hash(&mut self, new_hash: &[u8; HASH_LEN]) {
341        self.hash.copy_from_slice(new_hash)
342    }
343
344    /// Check if the given hash includes the provided namespace under the given hasher
345    pub fn contains<M: NamespaceMerkleHasher<NS_ID_SIZE, Output = Self>>(
346        &self,
347        namespace: NamespaceId<NS_ID_SIZE>,
348    ) -> bool {
349        self.min_namespace() <= namespace
350            && self.max_namespace() >= namespace
351            && !self.is_empty_root::<M>()
352    }
353
354    /// Check if the hash is the empty root under the given hasher
355    pub fn is_empty_root<M: NamespaceMerkleHasher<NS_ID_SIZE, Output = Self>>(&self) -> bool {
356        self == &M::EMPTY_ROOT
357    }
358
359    /// Returns an iterator of the bytes of the namespaced hash
360    pub fn iter(&self) -> impl Iterator<Item = u8> {
361        self.min_ns
362            .0
363            .into_iter()
364            .chain(self.max_ns.0)
365            .chain(self.hash)
366    }
367}
368
369/// The error returned when failing to convert a slice to a namespaced hash
370#[derive(Debug, PartialEq, Copy, Clone)]
371pub struct InvalidNamespacedHash;
372
373impl fmt::Display for InvalidNamespacedHash {
374    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
375        f.write_str("InvalidNamespacedHash")
376    }
377}
378#[cfg(feature = "std")]
379impl std::error::Error for InvalidNamespacedHash {}
380
381impl<const NS_ID_SIZE: usize> TryFrom<&[u8]> for NamespacedHash<NS_ID_SIZE> {
382    type Error = InvalidNamespacedHash;
383
384    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
385        if value.len() != NamespacedHash::<NS_ID_SIZE>::size() {
386            return Err(InvalidNamespacedHash);
387        }
388        Ok(Self {
389            min_ns: value[..NS_ID_SIZE].try_into().unwrap(),
390            max_ns: value[NS_ID_SIZE..2 * NS_ID_SIZE].try_into().unwrap(),
391            hash: value[2 * NS_ID_SIZE..].try_into().unwrap(),
392        })
393    }
394}
395
396#[cfg(test)]
397mod tests {
398    use crate::NamespacedHash;
399    use borsh::de::BorshDeserialize;
400
401    #[test]
402    fn test_namespaced_hash_borsh() {
403        let hash = NamespacedHash::<8>::try_from([8u8; 48].as_ref()).unwrap();
404
405        let serialized = borsh::to_vec(&hash).expect("Serialization to vec must succeed");
406
407        let got =
408            NamespacedHash::deserialize(&mut &serialized[..]).expect("serialized hash is correct");
409
410        assert_eq!(got, hash);
411    }
412
413    #[cfg(feature = "serde")]
414    #[test]
415    fn test_namespaced_hash_serde_json() {
416        let hash = NamespacedHash::<8>::try_from([8u8; 48].as_ref()).unwrap();
417
418        let serialized = serde_json::to_vec(&hash).expect("Serialization to vec must succeed");
419
420        let got: NamespacedHash<8> =
421            serde_json::from_slice(&serialized[..]).expect("serialized hash is correct");
422
423        assert_eq!(got, hash);
424    }
425
426    #[cfg(feature = "serde")]
427    #[test]
428    fn test_namespaced_hash_serde_postcard() {
429        use crate::maybestd::vec::Vec;
430
431        let hash = NamespacedHash::<8>::try_from([8u8; 48].as_ref()).unwrap();
432
433        let serialized: Vec<u8> =
434            postcard::to_allocvec(&hash).expect("Serialization to vec must succeed");
435        let got: NamespacedHash<8> =
436            postcard::from_bytes(&serialized[..]).expect("serialized hash is correct");
437
438        assert_eq!(got, hash);
439    }
440}
nmt_rs/namespaced_hash.rs

nmt_rs/
namespaced_hash.rs
