celestia_types/
nmt.rs

1//! Namespaces and Namespaced Merkle Tree.
2//!
3//! [`Namespace`] is a key to your data in Celestia. Whenever you publish blobs
4//! to the Celestia network, you have to assign them to a namespace. You can
5//! later use that namespace to acquire the data back from the network.
6//!
7//! All the data in each block is ordered by its [`Namespace`]. Things like
8//! transactions or trailing bytes have its own namespaces too, but those are reserved
9//! for block producers and cannot be utilized when submitting data.
10//!
11//! The fact that data in Celestia blocks is ordered allows for various optimizations
12//! when proving data inclusion or absence. There is a namespace-aware implementation
13//! of merkle trees, called 'Namespaced Merkle Tree', shortened as [`Nmt`].
14//!
15//! The generic implementation of this merkle tree lives in [`nmt-rs`]. This module is
16//! a wrapper around that with Celestia specific defaults and functionalities.
17//!
18//! [`nmt-rs`]: https://github.com/sovereign-labs/nmt-rs
19
20#[cfg(feature = "uniffi")]
21use crate::error::UniffiError;
22use base64::prelude::*;
23use blockstore::block::CidError;
24use celestia_proto::serializers::cow_str::CowStr;
25use cid::CidGeneric;
26use multihash::Multihash;
27use serde::{Deserialize, Deserializer, Serialize, Serializer};
28use tendermint::hash::SHA256_HASH_SIZE;
29#[cfg(all(feature = "wasm-bindgen", target_arch = "wasm32"))]
30use wasm_bindgen::prelude::*;
31
32mod namespace_proof;
33mod namespaced_hash;
34mod namespaced_merkle_tree;
35
36pub use self::namespace_proof::{NamespaceProof, EMPTY_LEAVES};
37pub use self::namespaced_hash::{
38    NamespacedHashExt, RawNamespacedHash, HASH_SIZE, NAMESPACED_HASH_SIZE,
39};
40pub use self::namespaced_merkle_tree::{MerkleHash, NamespacedSha2Hasher, Nmt, NmtExt};
41
42use crate::{Error, Result};
43
44pub use nmt_rs::NamespaceMerkleHasher;
45
46/// Namespace version size in bytes.
47pub const NS_VER_SIZE: usize = 1;
48/// Namespace id size in bytes.
49pub const NS_ID_SIZE: usize = 28;
50/// Namespace size in bytes.
51pub const NS_SIZE: usize = NS_VER_SIZE + NS_ID_SIZE;
52/// Size of the user-defined namespace suffix in bytes. For namespaces in version `0`.
53pub const NS_ID_V0_SIZE: usize = 10;
54
55/// The code of the [`Nmt`] hashing algorithm in `multihash`.
56pub const NMT_MULTIHASH_CODE: u64 = 0x7700;
57/// The id of codec used for the [`Nmt`] in `Cid`s.
58pub const NMT_CODEC: u64 = 0x7701;
59/// The size of the [`Nmt`] hash in `multihash`.
60pub const NMT_ID_SIZE: usize = 2 * NS_SIZE + SHA256_HASH_SIZE;
61
62/// Hash that carries info about minimum and maximum [`Namespace`] of the hashed data.
63///
64/// [`NamespacedHash`] can represent leaves or internal nodes of the [`Nmt`].
65///
66/// If it is a hash of a leaf, then it will be constructed like so:
67///
68/// `leaf_namespace | leaf_namespace | Sha256(0x00 | leaf_namespace | data)`
69///
70/// If it is a hash of its children nodes, then it will be constructed like so:
71///
72/// `min_namespace | max_namespace | Sha256(0x01 | left | right)`
73pub type NamespacedHash = nmt_rs::NamespacedHash<NS_SIZE>;
74/// Proof of some statement about namesapced merkle tree. It can either prove presence
75/// of a set of shares or absence of a particular namespace.
76pub type Proof = nmt_rs::simple_merkle::proof::Proof<NamespacedSha2Hasher>;
77
78/// Namespace of the data published to the celestia network.
79///
80/// The [`Namespace`] is a single byte defining the version
81/// followed by 28 bytes specifying concrete ID of the namespace.
82///
83/// Currently there are two versions of namespaces:
84///
85///  - version `0` - the one allowing for the custom namespace ids. It requires an id to start
86///    with 18 `0x00` bytes followed by a user specified suffix (except reserved ones, see below).
87///  - version `255` - for secondary reserved namespaces. It requires an id to start with 27
88///    `0xff` bytes followed by a single byte indicating the id.
89///
90/// Some namespaces are reserved for the block creation purposes and cannot be used
91/// when submitting the blobs to celestia. Those fall into one of the two categories:
92///
93///  - primary reserved namespaces - those use version `0` and have id lower or equal to `0xff`
94///    so they are always placed in blocks before user-submitted data.
95///  - secondary reserved namespaces - those use version `0xff` so they are always placed after
96///    user-submitted data.
97#[derive(Copy, Clone, Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
98#[cfg_attr(
99    all(feature = "wasm-bindgen", target_arch = "wasm32"),
100    wasm_bindgen(inspectable)
101)]
102#[cfg_attr(feature = "uniffi", derive(uniffi::Object))]
103pub struct Namespace(nmt_rs::NamespaceId<NS_SIZE>);
104
105impl Namespace {
106    /// Primary reserved [`Namespace`] for the compact [`Share`]s with [`cosmos SDK`] transactions.
107    ///
108    /// [`Share`]: crate::share::Share
109    /// [`cosmos SDK`]: https://docs.cosmos.network/v0.46/core/transactions.html
110    pub const TRANSACTION: Namespace = Namespace::const_v0([0, 0, 0, 0, 0, 0, 0, 0, 0, 1]);
111
112    /// Primary reserved [`Namespace`] for the compact [`Share`]s with [`MsgPayForBlobs`] transactions.
113    ///
114    /// [`Share`]: crate::share::Share
115    /// [`MsgPayForBlobs`]: celestia_proto::celestia::blob::v1::MsgPayForBlobs
116    pub const PAY_FOR_BLOB: Namespace = Namespace::const_v0([0, 0, 0, 0, 0, 0, 0, 0, 0, 4]);
117
118    /// Primary reserved [`Namespace`] for the [`Share`]s used for padding.
119    ///
120    /// [`Share`]s with this namespace are inserted after other shares from primary reserved namespace
121    /// so that user-defined namespaces are correctly aligned in [`ExtendedDataSquare`]
122    ///
123    /// [`Share`]: crate::share::Share
124    /// [`ExtendedDataSquare`]: crate::eds::ExtendedDataSquare
125    pub const PRIMARY_RESERVED_PADDING: Namespace = Namespace::MAX_PRIMARY_RESERVED;
126
127    /// Maximal primary reserved [`Namespace`].
128    ///
129    /// Used to indicate the end of the primary reserved group.
130    ///
131    /// [`PRIMARY_RESERVED_PADDING`]: Namespace::PRIMARY_RESERVED_PADDING
132    pub const MAX_PRIMARY_RESERVED: Namespace =
133        Namespace::const_v0([0, 0, 0, 0, 0, 0, 0, 0, 0, 0xff]);
134
135    /// Minimal secondary reserved [`Namespace`].
136    ///
137    /// Used to indicate the beginning of the secondary reserved group.
138    pub const MIN_SECONDARY_RESERVED: Namespace = Namespace::const_v255(0);
139
140    /// Secondary reserved [`Namespace`] used for padding after the blobs.
141    ///
142    /// It is used to fill up the `original data square` after all user-submitted
143    /// blobs before the parity data is generated for the [`ExtendedDataSquare`].
144    ///
145    /// [`ExtendedDataSquare`]: crate::eds::ExtendedDataSquare
146    pub const TAIL_PADDING: Namespace = Namespace::const_v255(0xfe);
147
148    /// The [`Namespace`] for `parity shares`.
149    ///
150    /// It is the namespace with which all the `parity shares` from
151    /// [`ExtendedDataSquare`] are inserted to the [`Nmt`] when computing
152    /// merkle roots.
153    ///
154    /// [`ExtendedDataSquare`]: crate::eds::ExtendedDataSquare
155    pub const PARITY_SHARE: Namespace = Namespace::const_v255(0xff);
156
157    /// Create a new [`Namespace`] from the raw bytes.
158    ///
159    /// # Errors
160    ///
161    /// This function will return an error if the slice length is different than
162    /// [`NS_SIZE`] or if the namespace is invalid. If you are constructing the
163    /// version `0` namespace, check [`new_v0`] for more details.
164    ///
165    /// # Example
166    ///
167    /// ```
168    /// use celestia_types::nmt::{Namespace, NS_SIZE};
169    /// let raw = [0; NS_SIZE];
170    /// let namespace = Namespace::from_raw(&raw).unwrap();
171    /// ```
172    ///
173    /// [`new_v0`]: crate::nmt::Namespace::new_v0
174    pub fn from_raw(bytes: &[u8]) -> Result<Self> {
175        if bytes.len() != NS_SIZE {
176            return Err(Error::InvalidNamespaceSize);
177        }
178
179        Namespace::new(bytes[0], &bytes[1..])
180    }
181
182    /// Create a new [`Namespace`] from the version and id.
183    ///
184    /// # Errors
185    ///
186    /// This function will return an error if provided namespace version isn't supported
187    /// or if the namespace is invalid. If you are constructing the
188    /// version `0` namespace, check [`new_v0`] for more details.
189    ///
190    /// # Example
191    ///
192    /// ```
193    /// use celestia_types::nmt::Namespace;
194    /// let namespace = Namespace::new(0, b"custom-ns").unwrap();
195    /// ```
196    ///
197    /// [`new_v0`]: crate::nmt::Namespace::new_v0
198    pub fn new(version: u8, id: &[u8]) -> Result<Self> {
199        match version {
200            0 => Self::new_v0(id),
201            255 => Self::new_v255(id),
202            n => Err(Error::UnsupportedNamespaceVersion(n)),
203        }
204    }
205
206    /// Create a new [`Namespace`] version `0` with given id.
207    ///
208    /// The `id` must be either:
209    ///  - a 28 byte slice specifying full id
210    ///  - a 10 or less byte slice specifying user-defined suffix
211    ///
212    /// [`Namespace`]s in version 0 must have id's prefixed with 18 `0x00` bytes.
213    ///
214    /// # Errors
215    ///
216    /// This function will return an error if the provided id has incorrect length
217    /// or if the `id` has 28 bytes and have doesn't have mandatory 18x`0x00` bytes prefix
218    ///
219    /// # Example
220    ///
221    /// ```
222    /// use celestia_types::nmt::Namespace;
223    ///
224    /// // construct using 28 byte slice
225    /// let id = [0u8; 28];
226    /// let namespace = Namespace::new_v0(&id).unwrap();
227    ///
228    /// // construct using <=10 byte suffix
229    /// let namespace = Namespace::new_v0(b"any-suffix").unwrap();
230    ///
231    /// // invalid
232    /// let mut id = [0u8; 28];
233    /// id[4] = 1;
234    /// let namespace = Namespace::new_v0(&id).unwrap_err();
235    /// ```
236    pub fn new_v0(id: &[u8]) -> Result<Self> {
237        let id_pos = match id.len() {
238            // Allow 28 bytes len
239            NS_ID_SIZE => NS_ID_SIZE - NS_ID_V0_SIZE,
240            // Allow 10 bytes len or less
241            n if n <= NS_ID_V0_SIZE => 0,
242            // Anything else is an error
243            _ => return Err(Error::InvalidNamespaceSize),
244        };
245
246        let prefix = &id[..id_pos];
247        let id = &id[id_pos..];
248
249        // Validate that prefix is all zeros
250        if prefix.iter().any(|&x| x != 0) {
251            return Err(Error::InvalidNamespaceV0);
252        }
253
254        let mut bytes = [0u8; NS_SIZE];
255        bytes[NS_SIZE - id.len()..].copy_from_slice(id);
256
257        Ok(Namespace(nmt_rs::NamespaceId(bytes)))
258    }
259
260    pub(crate) const fn new_unchecked(bytes: [u8; NS_SIZE]) -> Self {
261        Namespace(nmt_rs::NamespaceId(bytes))
262    }
263
264    /// Create a new [`Namespace`] version `0` with a given id.
265    ///
266    /// # Example
267    ///
268    /// ```
269    /// use celestia_types::nmt::Namespace;
270    ///
271    /// const NAMESPACE: Namespace = Namespace::const_v0([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
272    /// ```
273    pub const fn const_v0(id: [u8; NS_ID_V0_SIZE]) -> Self {
274        let mut bytes = [0u8; NS_SIZE];
275        let start = NS_SIZE - NS_ID_V0_SIZE;
276
277        bytes[start] = id[0];
278        bytes[start + 1] = id[1];
279        bytes[start + 2] = id[2];
280        bytes[start + 3] = id[3];
281        bytes[start + 4] = id[4];
282        bytes[start + 5] = id[5];
283        bytes[start + 6] = id[6];
284        bytes[start + 7] = id[7];
285        bytes[start + 8] = id[8];
286        bytes[start + 9] = id[9];
287
288        Namespace(nmt_rs::NamespaceId(bytes))
289    }
290
291    /// Create a new [`Namespace`] version `255` with a given id.
292    ///
293    /// # Example
294    ///
295    /// ```
296    /// use celestia_types::nmt::Namespace;
297    ///
298    /// const NAMESPACE: Namespace = Namespace::const_v255(0xff);
299    ///
300    /// assert_eq!(NAMESPACE, Namespace::PARITY_SHARE);
301    /// ```
302    pub const fn const_v255(id: u8) -> Self {
303        let mut bytes = [255u8; NS_SIZE];
304        bytes[NS_ID_SIZE] = id;
305        Namespace(nmt_rs::NamespaceId(bytes))
306    }
307
308    /// Create a new [`Namespace`] version `255` with a given id.
309    ///
310    /// [`Namespace`]s with version `255` must have ids prefixed with 27 `0xff` bytes followed by a
311    /// single byte with an actual id.
312    ///
313    /// # Errors
314    ///
315    /// This function will return an error, if the provided id has incorrect length
316    /// or if the `id` prefix is incorrect.
317    ///
318    /// # Example
319    ///
320    /// ```
321    /// use celestia_types::nmt::Namespace;
322    ///
323    /// // construct using 28 byte slice
324    /// let id = [255u8; 28];
325    /// let namespace = Namespace::new_v255(&id).unwrap();
326    /// ```
327    pub fn new_v255(id: &[u8]) -> Result<Self> {
328        if id.len() != NS_ID_SIZE {
329            return Err(Error::InvalidNamespaceSize);
330        }
331
332        // safe after the length check
333        let (id, prefix) = id.split_last().unwrap();
334
335        if prefix.iter().all(|&x| x == 0xff) {
336            Ok(Namespace::const_v255(*id))
337        } else {
338            Err(Error::InvalidNamespaceV255)
339        }
340    }
341
342    /// Converts the [`Namespace`] to a byte slice.
343    pub fn as_bytes(&self) -> &[u8] {
344        &self.0 .0
345    }
346
347    /// Returns the first byte indicating the version of the [`Namespace`].
348    pub fn version(&self) -> u8 {
349        self.as_bytes()[0]
350    }
351
352    /// Returns the trailing 28 bytes indicating the id of the [`Namespace`].
353    pub fn id(&self) -> &[u8] {
354        &self.as_bytes()[1..]
355    }
356
357    /// Returns the 10 bytes user-defined suffix of the [`Namespace`] if it's a version 0.
358    pub fn id_v0(&self) -> Option<&[u8]> {
359        if self.version() == 0 {
360            let start = NS_SIZE - NS_ID_V0_SIZE;
361            Some(&self.as_bytes()[start..])
362        } else {
363            None
364        }
365    }
366
367    /// Returns true if the namespace is reserved for special purposes.
368    ///
369    /// # Example
370    ///
371    /// ```
372    /// use celestia_types::nmt::Namespace;
373    ///
374    /// let ns = Namespace::new_v0(b"lumina").unwrap();
375    /// assert!(!ns.is_reserved());
376    ///
377    /// assert!(Namespace::PAY_FOR_BLOB.is_reserved());
378    /// assert!(Namespace::PARITY_SHARE.is_reserved());
379    /// ```
380    pub fn is_reserved(&self) -> bool {
381        *self <= Namespace::MAX_PRIMARY_RESERVED || *self >= Namespace::MIN_SECONDARY_RESERVED
382    }
383}
384
385#[cfg(all(feature = "wasm-bindgen", target_arch = "wasm32"))]
386#[wasm_bindgen]
387impl Namespace {
388    /// Namespace size in bytes.
389    #[wasm_bindgen(js_name = NS_SIZE, getter)]
390    pub fn js_ns_size() -> usize {
391        NS_SIZE
392    }
393
394    /// Primary reserved [`Namespace`] for the compact `Share`s with `cosmos SDK` transactions.
395    #[wasm_bindgen(js_name = TRANSACTION, getter)]
396    pub fn js_transaction() -> Namespace {
397        Namespace::TRANSACTION
398    }
399
400    /// Primary reserved [`Namespace`] for the compact Shares with MsgPayForBlobs transactions.
401    #[wasm_bindgen(js_name = PAY_FOR_BLOB, getter)]
402    pub fn js_pay_for_blob() -> Namespace {
403        Namespace::PAY_FOR_BLOB
404    }
405
406    /// Primary reserved [`Namespace`] for the `Share`s used for padding.
407    ///
408    /// `Share`s with this namespace are inserted after other shares from primary reserved namespace
409    /// so that user-defined namespaces are correctly aligned in `ExtendedDataSquare`
410    #[wasm_bindgen(js_name = PRIMARY_RESERVED_PADDING, getter)]
411    pub fn js_primary_reserved_padding() -> Namespace {
412        Namespace::PRIMARY_RESERVED_PADDING
413    }
414
415    /// Maximal primary reserved [`Namespace`].
416    ///
417    /// Used to indicate the end of the primary reserved group.
418    #[wasm_bindgen(js_name = MAX_PRIMARY_RESERVED, getter)]
419    pub fn js_max_primary_reserved() -> Namespace {
420        Namespace::MAX_PRIMARY_RESERVED
421    }
422
423    /// Minimal secondary reserved [`Namespace`].
424    ///
425    /// Used to indicate the beginning of the secondary reserved group.
426    #[wasm_bindgen(js_name = MIN_SECONDARY_RESERVED, getter)]
427    pub fn js_min_secondary_reserved() -> Namespace {
428        Namespace::MIN_SECONDARY_RESERVED
429    }
430
431    /// Secondary reserved [`Namespace`] used for padding after the blobs.
432    ///
433    /// It is used to fill up the `original data square` after all user-submitted
434    /// blobs before the parity data is generated for the `ExtendedDataSquare`.
435    #[wasm_bindgen(js_name = TAIL_PADDING, getter)]
436    pub fn js_tail_padding() -> Namespace {
437        Namespace::TAIL_PADDING
438    }
439
440    /// The [`Namespace`] for `parity shares`.
441    ///
442    /// It is the namespace with which all the `parity shares` from
443    /// `ExtendedDataSquare` are inserted to the `Nmt` when computing
444    /// merkle roots.
445    #[wasm_bindgen(js_name = PARITY_SHARE, getter)]
446    pub fn js_parity_share() -> Namespace {
447        Namespace::PARITY_SHARE
448    }
449
450    /// Create a new [`Namespace`] version `0` with given id.
451    ///
452    /// Check [`Namespace::new_v0`] for more details.
453    ///
454    /// [`Namespace::new_v0`]: https://docs.rs/celestia-types/latest/celestia_types/nmt/struct.Namespace.html#method.new_v0
455    #[wasm_bindgen(js_name = newV0)]
456    pub fn js_new_v0(id: Vec<u8>) -> Result<Self> {
457        Self::new_v0(&id.to_vec())
458    }
459
460    /// Create a new [`Namespace`] from the raw bytes.
461    ///
462    /// # Errors
463    ///
464    /// This function will return an error if the slice length is different than
465    /// [`NS_SIZE`] or if the namespace is invalid. If you are constructing the
466    /// version `0` namespace, check [`newV0`].
467    #[wasm_bindgen(js_name = fromRaw)]
468    pub fn js_from_raw(raw: Vec<u8>) -> Result<Self> {
469        Self::from_raw(&raw.to_vec())
470    }
471
472    /// Converts the [`Namespace`] to a byte slice.
473    #[wasm_bindgen(js_name = asBytes)]
474    pub fn js_as_bytes(&self) -> Vec<u8> {
475        self.as_bytes().to_vec()
476    }
477
478    /// Returns the first byte indicating the version of the [`Namespace`].
479    #[wasm_bindgen(js_name = version, getter)]
480    pub fn js_version(&self) -> u8 {
481        self.version()
482    }
483
484    /// Returns the trailing 28 bytes indicating the id of the [`Namespace`].
485    #[wasm_bindgen(js_name = id, getter)]
486    pub fn js_id(&self) -> Vec<u8> {
487        self.id().to_vec()
488    }
489}
490
491#[cfg(feature = "uniffi")]
492#[uniffi::export]
493impl Namespace {
494    /// Create a new [`Namespace`] from the version and id.
495    ///
496    /// # Errors
497    ///
498    /// This function will return an error if provided namespace version isn't supported
499    /// or if the namespace is invalid. If you are constructing the
500    /// version `0` namespace, check [`new_namespace_v0`] for more details.
501    ///
502    /// [`new_namespace_v0`]: crate::nmt::Namespace::new_namespace_v0
503    #[uniffi::constructor(name = "new")]
504    fn uniffi_new(version: u8, id: Vec<u8>) -> Result<Self, UniffiError> {
505        Ok(Namespace::new(version, &id)?)
506    }
507
508    /// Create a new [`Namespace`] version `0` with given id.
509    ///
510    /// The `id` must be either:
511    ///  - a 28 byte slice specifying full id
512    ///  - a 10 or less byte slice specifying user-defined suffix
513    ///
514    /// [`Namespace`]s in version 0 must have id's prefixed with 18 `0x00` bytes.
515    ///
516    /// # Errors
517    ///
518    /// This function will return an error if the provided id has incorrect length
519    /// or if the `id` has 28 bytes and have doesn't have mandatory 18x`0x00` bytes prefix
520    #[uniffi::constructor(name = "new_v0")]
521    fn uniffi_new_v0(id: Vec<u8>) -> Result<Self, UniffiError> {
522        Ok(Namespace::new_v0(&id)?)
523    }
524
525    /// Return the [`Namespace`] as a byte slice.
526    #[uniffi::method]
527    pub fn bytes(&self) -> Vec<u8> {
528        self.as_bytes().to_vec()
529    }
530
531    /// Returns the first byte indicating the version of the [`Namespace`].
532    #[uniffi::method(name = "version")]
533    pub fn uniffi_version(&self) -> u8 {
534        self.version()
535    }
536
537    /// Returns the trailing 28 bytes indicating the id of the [`Namespace`].
538    #[uniffi::method(name = "id")]
539    pub fn uniffi_id(&self) -> Vec<u8> {
540        self.id().to_vec()
541    }
542
543    /// Returns the 10 bytes user-defined suffix of the [`Namespace`] if it's a version 0.
544    #[uniffi::method(name = "id_v0")]
545    pub fn uniffi_id_v0(&self) -> Option<Vec<u8>> {
546        self.id_v0().map(ToOwned::to_owned)
547    }
548
549    /// Returns true if the namespace is reserved for special purposes.
550    #[uniffi::method(name = "is_reserved")]
551    pub fn uniffi_is_reserved(&self) -> bool {
552        self.is_reserved()
553    }
554}
555
556impl From<Namespace> for nmt_rs::NamespaceId<NS_SIZE> {
557    fn from(value: Namespace) -> Self {
558        value.0
559    }
560}
561
562impl From<nmt_rs::NamespaceId<NS_SIZE>> for Namespace {
563    fn from(value: nmt_rs::NamespaceId<NS_SIZE>) -> Self {
564        Namespace(value)
565    }
566}
567
568impl std::ops::Deref for Namespace {
569    type Target = nmt_rs::NamespaceId<NS_SIZE>;
570
571    fn deref(&self) -> &Self::Target {
572        &self.0
573    }
574}
575
576impl Serialize for Namespace {
577    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
578    where
579        S: Serializer,
580    {
581        let s = BASE64_STANDARD.encode(self.0);
582        serializer.serialize_str(&s)
583    }
584}
585
586impl<'de> Deserialize<'de> for Namespace {
587    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
588    where
589        D: Deserializer<'de>,
590    {
591        // base64 needs more buffer size than the final output
592        let mut buf = [0u8; NS_SIZE * 2];
593
594        let s = CowStr::deserialize(deserializer)?;
595
596        let len = BASE64_STANDARD
597            .decode_slice(s, &mut buf)
598            .map_err(|e| serde::de::Error::custom(e.to_string()))?;
599
600        Namespace::from_raw(&buf[..len]).map_err(|e| serde::de::Error::custom(e.to_string()))
601    }
602}
603
604/// A pair of two nodes in the [`Nmt`], usually the siblings.
605pub struct NodePair(NamespacedHash, NamespacedHash);
606
607impl NodePair {
608    fn validate_namespace_order(&self) -> Result<()> {
609        let NodePair(left, right) = self;
610
611        left.validate_namespace_order()?;
612        right.validate_namespace_order()?;
613
614        if left.max_namespace() > right.min_namespace() {
615            return Err(Error::InvalidNmtNodeOrder);
616        }
617
618        Ok(())
619    }
620}
621
622impl TryFrom<NodePair> for CidGeneric<NMT_ID_SIZE> {
623    type Error = CidError;
624
625    fn try_from(nodes: NodePair) -> Result<Self, Self::Error> {
626        nodes
627            .validate_namespace_order()
628            .map_err(|e| CidError::InvalidDataFormat(e.to_string()))?;
629
630        let hasher = NamespacedSha2Hasher::with_ignore_max_ns(true);
631        let digest = hasher.hash_nodes(&nodes.0, &nodes.1).to_array();
632
633        let mh = Multihash::wrap(NMT_MULTIHASH_CODE, &digest).unwrap();
634
635        Ok(CidGeneric::new_v1(NMT_CODEC, mh))
636    }
637}
638
639#[cfg(test)]
640mod tests {
641    use super::*;
642
643    #[cfg(target_arch = "wasm32")]
644    use wasm_bindgen_test::wasm_bindgen_test as test;
645
646    #[test]
647    fn namespace_id_8_bytes() {
648        let nid = Namespace::new_v0(&[1, 2, 3, 4, 5, 6, 7, 8]).unwrap();
649
650        let expected_nid = Namespace(nmt_rs::NamespaceId([
651            0, // version
652            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
653            0, 0, 1, 2, 3, 4, 5, 6, 7, 8, // id with left padding
654        ]));
655
656        assert_eq!(nid, expected_nid);
657    }
658
659    #[test]
660    fn namespace_id_8_bytes_with_prefix() {
661        let nid = Namespace::new_v0(&[
662            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
663            0, 0, 1, 2, 3, 4, 5, 6, 7, 8, // id
664        ])
665        .unwrap();
666
667        let expected_nid = Namespace(nmt_rs::NamespaceId([
668            0, // version
669            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
670            0, 0, 1, 2, 3, 4, 5, 6, 7, 8, // id
671        ]));
672
673        assert_eq!(nid, expected_nid);
674    }
675
676    #[test]
677    fn namespace_id_10_bytes() {
678        let nid = Namespace::new_v0(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]).unwrap();
679        let expected_nid = Namespace(nmt_rs::NamespaceId([
680            0, // version
681            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
682            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // id
683        ]));
684
685        assert_eq!(nid, expected_nid);
686    }
687
688    #[test]
689    fn namespace_id_max() {
690        let nid = Namespace::new(0xff, &[0xff; 28]).unwrap();
691        let expected_nid = Namespace::PARITY_SHARE;
692
693        assert_eq!(nid, expected_nid);
694    }
695
696    #[test]
697    fn namespace_id_const_v0() {
698        let nid = Namespace::const_v0([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
699        let expected_nid = Namespace(nmt_rs::NamespaceId([
700            0, // version
701            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
702            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // id
703        ]));
704
705        assert_eq!(nid, expected_nid);
706    }
707
708    #[test]
709    fn namespace_id_const_v255() {
710        let nid = Namespace::const_v255(0xab);
711        let expected_nid = Namespace(nmt_rs::NamespaceId([
712            0xff, // version
713            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
714            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
715            0xff, // prefix
716            0xab, // id
717        ]));
718
719        assert_eq!(nid, expected_nid);
720    }
721
722    #[test]
723    fn namespace_id_10_bytes_with_prefix() {
724        let nid = Namespace::new_v0(&[
725            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
726            1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
727        ])
728        .unwrap();
729
730        let expected_nid = Namespace(nmt_rs::NamespaceId([
731            0, // version
732            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
733            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // id
734        ]));
735
736        assert_eq!(nid, expected_nid);
737    }
738
739    #[test]
740    fn namespace_id_with_invalid_prefix() {
741        let e = Namespace::new_v0(&[
742            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, // prefix
743            1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
744        ])
745        .unwrap_err();
746
747        assert!(matches!(e, Error::InvalidNamespaceV0));
748    }
749
750    #[test]
751    fn namespace_id_11_bytes() {
752        let e = Namespace::new_v0(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]).unwrap_err();
753
754        assert!(matches!(e, Error::InvalidNamespaceSize));
755    }
756
757    #[test]
758    fn namespace_id_v255_too_long() {
759        let e = Namespace::new_v255(&[0xff; 29]).unwrap_err();
760
761        assert!(matches!(e, Error::InvalidNamespaceSize));
762    }
763
764    #[test]
765    fn namespace_id_v255_too_short() {
766        let e = Namespace::new_v255(&[0xff; 27]).unwrap_err();
767
768        assert!(matches!(e, Error::InvalidNamespaceSize));
769    }
770
771    #[test]
772    fn namespace_id_max_invalid_prefix() {
773        let namespace = &[
774            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
775            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff,
776        ];
777        let e = Namespace::new_v255(namespace).unwrap_err();
778
779        assert!(matches!(e, Error::InvalidNamespaceV255));
780    }
781
782    #[test]
783    fn namespace_id_from_raw_bytes() {
784        let nid = Namespace::from_raw(&[
785            0, // version
786            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
787            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // id
788        ])
789        .unwrap();
790
791        let expected_nid = Namespace(nmt_rs::NamespaceId([
792            0, // version
793            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
794            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // id
795        ]));
796
797        assert_eq!(nid, expected_nid);
798    }
799
800    #[test]
801    fn namespace_id_with_28_raw_bytes() {
802        let e = Namespace::from_raw(&[
803            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
804            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // id
805        ])
806        .unwrap_err();
807
808        assert!(matches!(e, Error::InvalidNamespaceSize));
809    }
810
811    #[test]
812    fn namespace_id_with_30_raw_bytes() {
813        let e = Namespace::from_raw(&[
814            0, // extra
815            0, // version
816            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // prefix
817            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, // id
818        ])
819        .unwrap_err();
820
821        assert!(matches!(e, Error::InvalidNamespaceSize));
822    }
823
824    #[test]
825    fn max_namespace_id_from_raw_bytes() {
826        let nid = Namespace::from_raw(&[
827            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
828            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
829            0xff,
830        ])
831        .unwrap();
832
833        let expected_nid = Namespace::PARITY_SHARE;
834
835        assert_eq!(nid, expected_nid);
836    }
837
838    #[test]
839    fn invalid_max_namespace_id_from_raw_bytes() {
840        let e = Namespace::from_raw(&[
841            0xff, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
842            0,
843        ])
844        .unwrap_err();
845
846        assert!(matches!(e, Error::InvalidNamespaceV255));
847
848        let e = Namespace::from_raw(&[
849            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
850            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
851            0xff,
852        ])
853        .unwrap_err();
854
855        assert!(matches!(e, Error::InvalidNamespaceV255));
856    }
857
858    #[test]
859    fn invalid_version() {
860        let e = Namespace::from_raw(&[
861            254, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
862        ])
863        .unwrap_err();
864
865        assert!(matches!(e, Error::UnsupportedNamespaceVersion(254)));
866    }
867
868    #[test]
869    fn test_generate_inner_multihash() {
870        let ns0 = Namespace::new_v0(&[1]).unwrap();
871        let ns1 = Namespace::new_v0(&[2]).unwrap();
872        let ns2 = Namespace::new_v0(&[3]).unwrap();
873
874        let nodes = NodePair(
875            NamespacedHash::with_min_and_max_ns(*ns0, *ns1),
876            NamespacedHash::with_min_and_max_ns(*ns1, *ns2),
877        );
878
879        let cid = CidGeneric::try_from(nodes).unwrap();
880        assert_eq!(cid.codec(), NMT_CODEC);
881
882        let hash = cid.hash();
883        assert_eq!(hash.code(), NMT_MULTIHASH_CODE);
884        assert_eq!(hash.size(), NAMESPACED_HASH_SIZE as u8);
885
886        let hash = NamespacedHash::from_raw(hash.digest()).unwrap();
887        assert_eq!(hash.min_namespace(), *ns0);
888        assert_eq!(hash.max_namespace(), *ns2);
889    }
890
891    #[test]
892    fn invalid_ns_order_result() {
893        let ns0 = Namespace::new_v0(&[1]).unwrap();
894        let ns1 = Namespace::new_v0(&[2]).unwrap();
895        let ns2 = Namespace::new_v0(&[3]).unwrap();
896
897        let nodes = NodePair(
898            NamespacedHash::with_min_and_max_ns(*ns1, *ns2),
899            NamespacedHash::with_min_and_max_ns(*ns0, *ns0),
900        );
901        let result = CidGeneric::try_from(nodes).unwrap_err();
902
903        assert_eq!(
904            result,
905            CidError::InvalidDataFormat("Invalid nmt node order".to_string())
906        );
907    }
908
909    #[test]
910    fn test_read_multihash() {
911        let multihash = [
912            0x81, 0xEE, 0x01, // code = 7701
913            0x5A, // len = NAMESPACED_HASH_SIZE = 90
914            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
915            1, // min ns
916            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
917            9, // max ns
918            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
919            0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
920            0xFF, 0xFF, 0xFF, 0xFF, // hash
921        ];
922
923        let mh = Multihash::<NAMESPACED_HASH_SIZE>::from_bytes(&multihash).unwrap();
924        assert_eq!(mh.code(), NMT_CODEC);
925        assert_eq!(mh.size(), NAMESPACED_HASH_SIZE as u8);
926        let hash = NamespacedHash::from_raw(mh.digest()).unwrap();
927        assert_eq!(hash.min_namespace(), *Namespace::new_v0(&[1]).unwrap());
928        assert_eq!(hash.max_namespace(), *Namespace::new_v0(&[9]).unwrap());
929        assert_eq!(hash.hash(), [0xFF; 32]);
930    }
931}
celestia_types/nmt.rs

celestia_types/
nmt.rs
