celestia_types/
row_namespace_data.rs

1//! Types related to the namespaced data.
2//!
3//! Namespaced data in Celestia is understood as all the [`Share`]s within
4//! the same [`Namespace`] in a single row of the [`ExtendedDataSquare`].
5//!
6//! [`Share`]: crate::Share
7//! [`ExtendedDataSquare`]: crate::eds::ExtendedDataSquare
8
9use blockstore::block::CidError;
10use bytes::{BufMut, BytesMut};
11use celestia_proto::shwap::{RowNamespaceData as RawRowNamespaceData, Share as RawShare};
12use cid::CidGeneric;
13use multihash::Multihash;
14use prost::Message;
15use serde::{Deserialize, Serialize};
16
17use crate::nmt::{NS_SIZE, Namespace, NamespaceProof};
18use crate::row::{ROW_ID_SIZE, RowId};
19use crate::{DataAvailabilityHeader, Error, Result, Share, bail_validation};
20
21/// Number of bytes needed to represent [`RowNamespaceDataId`] in `multihash`.
22pub const ROW_NAMESPACE_DATA_ID_SIZE: usize = ROW_ID_SIZE + NS_SIZE;
23/// The code of the [`RowNamespaceDataId`] hashing algorithm in `multihash`.
24pub const ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE: u64 = 0x7821;
25/// The id of codec used for the [`RowNamespaceDataId`] in `Cid`s.
26pub const ROW_NAMESPACE_DATA_CODEC: u64 = 0x7820;
27
28/// Identifies [`Share`]s within a [`Namespace`] located on a particular row of the
29/// block's [`ExtendedDataSquare`].
30///
31/// [`Share`]: crate::Share
32/// [`ExtendedDataSquare`]: crate::eds::ExtendedDataSquare
33#[derive(Debug, PartialEq, Clone, Copy)]
34pub struct RowNamespaceDataId {
35    row_id: RowId,
36    namespace: Namespace,
37}
38
39/// `RowNamespaceData` contains up to a row of shares belonging to a particular namespace and a proof of their inclusion.
40///
41/// It is constructed out of the ExtendedDataSquare. If, for particular EDS, shares from the namespace span multiple rows,
42/// one needs multiple RowNamespaceData instances to cover the whole range.
43#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
44#[serde(into = "RawRowNamespaceData", try_from = "RawRowNamespaceData")]
45pub struct RowNamespaceData {
46    /// Proof of data inclusion
47    pub proof: NamespaceProof,
48    /// Shares with data
49    #[serde(deserialize_with = "celestia_proto::serializers::null_default::deserialize")]
50    pub shares: Vec<Share>,
51}
52
53impl RowNamespaceData {
54    /// Verifies the proof inside `RowNamespaceData` using a row root from [`DataAvailabilityHeader`]
55    ///
56    /// # Example
57    ///
58    /// ```no_run
59    /// use celestia_types::nmt::Namespace;
60    /// # use celestia_types::{ExtendedDataSquare, ExtendedHeader};
61    /// # fn get_extended_data_square(height: usize) -> ExtendedDataSquare {
62    /// #    unimplemented!()
63    /// # }
64    /// # fn get_extended_header(height: usize) -> ExtendedHeader {
65    /// #    unimplemented!()
66    /// # }
67    /// #
68    /// let block_height = 100;
69    /// let eds = get_extended_data_square(block_height);
70    /// let header = get_extended_header(block_height);
71    ///
72    /// let namespace = Namespace::new_v0(&[1, 2, 3]).unwrap();
73    ///
74    /// let rows = eds.get_namespace_data(namespace, &header.dah, block_height as u64).unwrap();
75    /// for (id, namespace_data) in rows {
76    ///     namespace_data.verify(id, &header.dah).unwrap()
77    /// }
78    /// ```
79    ///
80    /// [`DataAvailabilityHeader`]: crate::DataAvailabilityHeader
81    pub fn verify(&self, id: RowNamespaceDataId, dah: &DataAvailabilityHeader) -> Result<()> {
82        if (self.shares.is_empty() && self.proof.is_of_presence())
83            || (!self.shares.is_empty() && self.proof.is_of_absence())
84        {
85            return Err(Error::WrongProofType);
86        }
87
88        let namespace = id.namespace();
89        let row = id.row_index();
90        let root = dah.row_root(row).ok_or(Error::EdsIndexOutOfRange(row, 0))?;
91
92        self.proof
93            .verify_complete_namespace(&root, &self.shares, *namespace)
94            .map_err(Error::RangeProofError)
95    }
96
97    /// Encode RowNamespaceData into the raw binary representation.
98    pub fn encode(&self, bytes: &mut BytesMut) {
99        let raw = RawRowNamespaceData::from(self.clone());
100
101        bytes.reserve(raw.encoded_len());
102        raw.encode(bytes).expect("capacity reserved");
103    }
104
105    /// Decode RowNamespaceData from the binary representation.
106    ///
107    /// # Errors
108    ///
109    /// This function will return an error if protobuf deserialization
110    /// fails and propagate errors from [`RowNamespaceData::from_raw`].
111    pub fn decode(id: RowNamespaceDataId, buffer: &[u8]) -> Result<Self> {
112        let raw = RawRowNamespaceData::decode(buffer)?;
113        Self::from_raw(id, raw)
114    }
115
116    /// Recover RowNamespaceData from it's raw representation.
117    ///
118    /// # Errors
119    ///
120    /// This function will return error if proof is missing or invalid, shares are not in
121    /// the expected namespace, and will propagate errors from [`Share`] construction.
122    pub fn from_raw(id: RowNamespaceDataId, namespace_data: RawRowNamespaceData) -> Result<Self> {
123        let Some(proof) = namespace_data.proof else {
124            return Err(Error::MissingProof);
125        };
126
127        // extract all shares according to the expected namespace
128        let shares: Vec<_> = namespace_data
129            .shares
130            .into_iter()
131            .map(|shr| {
132                if id.namespace != Namespace::PARITY_SHARE {
133                    Share::from_raw(&shr.data)
134                } else {
135                    Share::parity(&shr.data)
136                }
137            })
138            .collect::<Result<_>>()?;
139
140        // and double check they all have equal namespaces
141        if !shares.iter().all(|shr| shr.namespace() == id.namespace) {
142            bail_validation!("Namespace data must have equal namespaces");
143        }
144
145        Ok(RowNamespaceData {
146            shares,
147            proof: proof.try_into()?,
148        })
149    }
150}
151
152impl From<RowNamespaceData> for RawRowNamespaceData {
153    fn from(namespaced_data: RowNamespaceData) -> RawRowNamespaceData {
154        RawRowNamespaceData {
155            shares: namespaced_data
156                .shares
157                .into_iter()
158                .map(|shr| RawShare { data: shr.to_vec() })
159                .collect(),
160            proof: Some(namespaced_data.proof.into()),
161        }
162    }
163}
164
165impl TryFrom<RawRowNamespaceData> for RowNamespaceData {
166    type Error = Error;
167
168    fn try_from(value: RawRowNamespaceData) -> std::result::Result<Self, Self::Error> {
169        let Some(proof) = value.proof else {
170            return Err(Error::MissingProof);
171        };
172        let proof = proof.try_into()?;
173
174        let mut shares = Vec::with_capacity(value.shares.len());
175        for raw_share in value.shares {
176            shares.push(Share::try_from(raw_share)?);
177        }
178        Ok(RowNamespaceData { proof, shares })
179    }
180}
181
182impl RowNamespaceDataId {
183    /// Create a new [`RowNamespaceDataId`] for given block, row and the [`Namespace`].
184    ///
185    /// # Errors
186    ///
187    /// This function will return an error if the block height
188    /// or row index is invalid.
189    pub fn new(namespace: Namespace, row_index: u16, block_height: u64) -> Result<Self> {
190        Ok(Self {
191            row_id: RowId::new(row_index, block_height)?,
192            namespace,
193        })
194    }
195
196    /// A height of the block which contains the shares.
197    pub fn block_height(&self) -> u64 {
198        self.row_id.block_height()
199    }
200
201    /// Row index of the [`ExtendedDataSquare`] that shares are located on.
202    ///
203    /// [`ExtendedDataSquare`]: crate::eds::ExtendedDataSquare
204    pub fn row_index(&self) -> u16 {
205        self.row_id.index()
206    }
207
208    /// A namespace of the [`Share`]s.
209    ///
210    /// [`Share`]: crate::Share
211    pub fn namespace(&self) -> Namespace {
212        self.namespace
213    }
214
215    /// Encode row namespace data id into the byte representation.
216    pub fn encode(&self, bytes: &mut BytesMut) {
217        bytes.reserve(ROW_NAMESPACE_DATA_ID_SIZE);
218        self.row_id.encode(bytes);
219        bytes.put(self.namespace.as_bytes());
220    }
221
222    /// Decode row namespace data id from the byte representation.
223    pub fn decode(buffer: &[u8]) -> Result<Self> {
224        if buffer.len() != ROW_NAMESPACE_DATA_ID_SIZE {
225            return Err(Error::InvalidLength(
226                buffer.len(),
227                ROW_NAMESPACE_DATA_ID_SIZE,
228            ));
229        }
230
231        let (row_bytes, ns_bytes) = buffer.split_at(ROW_ID_SIZE);
232        let row_id = RowId::decode(row_bytes)?;
233        let namespace = Namespace::from_raw(ns_bytes)?;
234
235        Ok(Self { row_id, namespace })
236    }
237}
238
239impl<const S: usize> TryFrom<CidGeneric<S>> for RowNamespaceDataId {
240    type Error = CidError;
241
242    fn try_from(cid: CidGeneric<S>) -> Result<Self, Self::Error> {
243        let codec = cid.codec();
244        if codec != ROW_NAMESPACE_DATA_CODEC {
245            return Err(CidError::InvalidCidCodec(codec));
246        }
247
248        let hash = cid.hash();
249
250        let size = hash.size() as usize;
251        if size != ROW_NAMESPACE_DATA_ID_SIZE {
252            return Err(CidError::InvalidMultihashLength(size));
253        }
254
255        let code = hash.code();
256        if code != ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE {
257            return Err(CidError::InvalidMultihashCode(
258                code,
259                ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE,
260            ));
261        }
262
263        RowNamespaceDataId::decode(hash.digest()).map_err(|e| CidError::InvalidCid(e.to_string()))
264    }
265}
266
267impl From<RowNamespaceDataId> for CidGeneric<ROW_NAMESPACE_DATA_ID_SIZE> {
268    fn from(namespaced_data_id: RowNamespaceDataId) -> Self {
269        let mut bytes = BytesMut::with_capacity(ROW_NAMESPACE_DATA_ID_SIZE);
270        namespaced_data_id.encode(&mut bytes);
271        // length is correct, so the unwrap is safe
272        let mh = Multihash::wrap(ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE, &bytes[..]).unwrap();
273
274        CidGeneric::new_v1(ROW_NAMESPACE_DATA_CODEC, mh)
275    }
276}
277
278#[cfg(test)]
279mod tests {
280    use super::*;
281    use crate::Blob;
282    use crate::consts::appconsts::AppVersion;
283    use crate::test_utils::{generate_dummy_eds, generate_eds};
284
285    #[test]
286    fn round_trip() {
287        let ns = Namespace::new_v0(&[0, 1]).unwrap();
288        let data_id = RowNamespaceDataId::new(ns, 5, 100).unwrap();
289        let cid = CidGeneric::from(data_id);
290
291        let multihash = cid.hash();
292        assert_eq!(multihash.code(), ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE);
293        assert_eq!(multihash.size(), ROW_NAMESPACE_DATA_ID_SIZE as u8);
294
295        let deserialized_data_id = RowNamespaceDataId::try_from(cid).unwrap();
296        assert_eq!(data_id, deserialized_data_id);
297    }
298
299    #[test]
300    fn from_buffer() {
301        let bytes = [
302            0x01, // CIDv1
303            0xA0, 0xF0, 0x01, // CID codec = 7820
304            0xA1, 0xF0, 0x01, // multihash code = 7821
305            0x27, // len = ROW_NAMESPACE_DATA_ID_SIZE = 39
306            0, 0, 0, 0, 0, 0, 0, 64, // block height = 64
307            0, 7, // row = 7
308            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,
309            1, // NS = 1
310        ];
311
312        let cid = CidGeneric::<ROW_NAMESPACE_DATA_ID_SIZE>::read_bytes(bytes.as_ref()).unwrap();
313        assert_eq!(cid.codec(), ROW_NAMESPACE_DATA_CODEC);
314        let mh = cid.hash();
315        assert_eq!(mh.code(), ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE);
316        assert_eq!(mh.size(), ROW_NAMESPACE_DATA_ID_SIZE as u8);
317        let data_id = RowNamespaceDataId::try_from(cid).unwrap();
318        assert_eq!(data_id.namespace(), Namespace::new_v0(&[1]).unwrap());
319        assert_eq!(data_id.block_height(), 64);
320        assert_eq!(data_id.row_index(), 7);
321    }
322
323    #[test]
324    fn namespaced_data_id_size() {
325        // Size MUST be 39 by the spec.
326        assert_eq!(ROW_NAMESPACE_DATA_ID_SIZE, 39);
327
328        let data_id = RowNamespaceDataId::new(Namespace::new_v0(&[1]).unwrap(), 0, 1).unwrap();
329        let mut bytes = BytesMut::new();
330        data_id.encode(&mut bytes);
331        assert_eq!(bytes.len(), ROW_NAMESPACE_DATA_ID_SIZE);
332    }
333
334    #[test]
335    fn multihash_invalid_code() {
336        let multihash =
337            Multihash::<ROW_NAMESPACE_DATA_ID_SIZE>::wrap(888, &[0; ROW_NAMESPACE_DATA_ID_SIZE])
338                .unwrap();
339        let cid =
340            CidGeneric::<ROW_NAMESPACE_DATA_ID_SIZE>::new_v1(ROW_NAMESPACE_DATA_CODEC, multihash);
341        let axis_err = RowNamespaceDataId::try_from(cid).unwrap_err();
342        assert_eq!(
343            axis_err,
344            CidError::InvalidMultihashCode(888, ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE)
345        );
346    }
347
348    #[test]
349    fn cid_invalid_codec() {
350        let multihash = Multihash::<ROW_NAMESPACE_DATA_ID_SIZE>::wrap(
351            ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE,
352            &[0; ROW_NAMESPACE_DATA_ID_SIZE],
353        )
354        .unwrap();
355        let cid = CidGeneric::<ROW_NAMESPACE_DATA_ID_SIZE>::new_v1(4321, multihash);
356        let axis_err = RowNamespaceDataId::try_from(cid).unwrap_err();
357        assert_eq!(axis_err, CidError::InvalidCidCodec(4321));
358    }
359
360    #[test]
361    fn test_roundtrip_verify() {
362        // random
363        for _ in 0..5 {
364            let eds = generate_dummy_eds(2 << (rand::random::<usize>() % 8), AppVersion::V2);
365            let dah = DataAvailabilityHeader::from_eds(&eds);
366
367            let namespace = eds.share(1, 1).unwrap().namespace();
368
369            for (id, row) in eds.get_namespace_data(namespace, &dah, 1).unwrap() {
370                let mut buf = BytesMut::new();
371                row.encode(&mut buf);
372                let decoded = RowNamespaceData::decode(id, &buf).unwrap();
373
374                decoded.verify(id, &dah).unwrap();
375            }
376        }
377
378        // parity share
379        let eds = generate_dummy_eds(2 << (rand::random::<usize>() % 8), AppVersion::V2);
380        let dah = DataAvailabilityHeader::from_eds(&eds);
381        for (id, row) in eds
382            .get_namespace_data(Namespace::PARITY_SHARE, &dah, 1)
383            .unwrap()
384        {
385            let mut buf = BytesMut::new();
386            row.encode(&mut buf);
387            let decoded = RowNamespaceData::decode(id, &buf).unwrap();
388
389            decoded.verify(id, &dah).unwrap();
390        }
391    }
392
393    #[test]
394    fn verify_absent_ns() {
395        // parity share
396        let eds = generate_dummy_eds(2 << (rand::random::<usize>() % 8), AppVersion::V2);
397        let dah = DataAvailabilityHeader::from_eds(&eds);
398
399        // namespace bigger than pay for blob, smaller than primary reserved padding, that is not
400        // used
401        let ns = Namespace::const_v0([0, 0, 0, 0, 0, 0, 0, 0, 0, 5]);
402        for (id, row) in eds.get_namespace_data(ns, &dah, 1).unwrap() {
403            assert!(row.shares.is_empty());
404            row.verify(id, &dah).unwrap();
405        }
406    }
407
408    #[test]
409    fn reconstruct_all() {
410        for _ in 0..3 {
411            let eds = generate_eds(8 << (rand::random::<usize>() % 6), AppVersion::V2);
412            let dah = DataAvailabilityHeader::from_eds(&eds);
413
414            let mut namespaces: Vec<_> = eds
415                .data_square()
416                .iter()
417                .map(|shr| shr.namespace())
418                .filter(|ns| !ns.is_reserved())
419                .collect();
420            namespaces.dedup();
421
422            // first namespace should have 2 blobs over 3 rows
423            let namespace_data = eds.get_namespace_data(namespaces[0], &dah, 1).unwrap();
424            assert_eq!(namespace_data.len(), 3);
425            let shares = namespace_data.iter().flat_map(|(_, row)| row.shares.iter());
426
427            let blobs = Blob::reconstruct_all(shares, AppVersion::V2).unwrap();
428            assert_eq!(blobs.len(), 2);
429
430            // rest of namespaces should have 1 blob each
431            for ns in &namespaces[1..] {
432                let namespace_data = eds.get_namespace_data(*ns, &dah, 1).unwrap();
433                assert_eq!(namespace_data.len(), 1);
434                let shares = namespace_data.iter().flat_map(|(_, row)| row.shares.iter());
435
436                let blobs = Blob::reconstruct_all(shares, AppVersion::V2).unwrap();
437                assert_eq!(blobs.len(), 1);
438            }
439        }
440    }
441
442    #[test]
443    fn namespace_data_roundtrip() {
444        let proof = nmt_rs::nmt_proof::NamespaceProof::<
445            crate::nmt::NamespacedSha2Hasher,
446            { crate::nmt::NS_SIZE },
447        >::AbsenceProof {
448            proof: crate::nmt::Proof {
449                siblings: vec![
450                    nmt_rs::NamespacedHash::new(
451                        nmt_rs::NamespaceId([
452                            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
453                            0, 0, 0, 0, 4,
454                        ]),
455                        nmt_rs::NamespaceId([
456                            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
457                            0, 0, 0, 0, 4,
458                        ]),
459                        [
460                            180, 43, 29, 197, 134, 127, 103, 202, 217, 240, 11, 18, 15, 47, 140,
461                            136, 58, 134, 117, 174, 162, 95, 216, 114, 31, 71, 90, 238, 49, 228,
462                            95, 89,
463                        ],
464                    ),
465                    nmt_rs::NamespacedHash::new(
466                        nmt_rs::NamespaceId::MAX_ID,
467                        nmt_rs::NamespaceId::MAX_ID,
468                        [
469                            126, 112, 141, 49, 103, 177, 23, 186, 153, 245, 110, 62, 165, 4, 39,
470                            125, 171, 55, 116, 176, 36, 153, 101, 171, 25, 253, 200, 61, 226, 43,
471                            81, 52,
472                        ],
473                    ),
474                ],
475                range: 1..2,
476            },
477            ignore_max_ns: true,
478            leaf: Some(nmt_rs::NamespacedHash::new(
479                nmt_rs::NamespaceId([
480                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 115, 111, 118, 45,
481                    116, 101, 115, 116, 45, 112,
482                ]),
483                nmt_rs::NamespaceId([
484                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 115, 111, 118, 45,
485                    116, 101, 115, 116, 45, 112,
486                ]),
487                [
488                    132, 118, 183, 139, 217, 27, 43, 49, 209, 15, 142, 136, 209, 205, 230, 67, 247,
489                    102, 202, 206, 118, 16, 124, 41, 208, 225, 148, 103, 192, 184, 59, 155,
490                ],
491            )),
492        };
493
494        let row = RowNamespaceData {
495            proof: proof.into(),
496            shares: vec![],
497        };
498
499        // JSON works,
500        let row_j = serde_json::to_value(&row).unwrap();
501        let d_from_json: RowNamespaceData = serde_json::from_value(row_j).unwrap();
502        assert_eq!(d_from_json, row);
503
504        // binary
505        let s_row = postcard::to_allocvec(&row).unwrap();
506        let d_row: RowNamespaceData = postcard::from_bytes(&s_row).unwrap();
507        assert_eq!(row, d_row);
508    }
509}
celestia_types/row_namespace_data.rs

celestia_types/
row_namespace_data.rs
