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::test_utils::{generate_dummy_eds, generate_eds};
283
284    #[test]
285    fn round_trip() {
286        let ns = Namespace::new_v0(&[0, 1]).unwrap();
287        let data_id = RowNamespaceDataId::new(ns, 5, 100).unwrap();
288        let cid = CidGeneric::from(data_id);
289
290        let multihash = cid.hash();
291        assert_eq!(multihash.code(), ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE);
292        assert_eq!(multihash.size(), ROW_NAMESPACE_DATA_ID_SIZE as u8);
293
294        let deserialized_data_id = RowNamespaceDataId::try_from(cid).unwrap();
295        assert_eq!(data_id, deserialized_data_id);
296    }
297
298    #[test]
299    fn from_buffer() {
300        let bytes = [
301            0x01, // CIDv1
302            0xA0, 0xF0, 0x01, // CID codec = 7820
303            0xA1, 0xF0, 0x01, // multihash code = 7821
304            0x27, // len = ROW_NAMESPACE_DATA_ID_SIZE = 39
305            0, 0, 0, 0, 0, 0, 0, 64, // block height = 64
306            0, 7, // row = 7
307            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,
308            1, // NS = 1
309        ];
310
311        let cid = CidGeneric::<ROW_NAMESPACE_DATA_ID_SIZE>::read_bytes(bytes.as_ref()).unwrap();
312        assert_eq!(cid.codec(), ROW_NAMESPACE_DATA_CODEC);
313        let mh = cid.hash();
314        assert_eq!(mh.code(), ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE);
315        assert_eq!(mh.size(), ROW_NAMESPACE_DATA_ID_SIZE as u8);
316        let data_id = RowNamespaceDataId::try_from(cid).unwrap();
317        assert_eq!(data_id.namespace(), Namespace::new_v0(&[1]).unwrap());
318        assert_eq!(data_id.block_height(), 64);
319        assert_eq!(data_id.row_index(), 7);
320    }
321
322    #[test]
323    fn namespaced_data_id_size() {
324        // Size MUST be 39 by the spec.
325        assert_eq!(ROW_NAMESPACE_DATA_ID_SIZE, 39);
326
327        let data_id = RowNamespaceDataId::new(Namespace::new_v0(&[1]).unwrap(), 0, 1).unwrap();
328        let mut bytes = BytesMut::new();
329        data_id.encode(&mut bytes);
330        assert_eq!(bytes.len(), ROW_NAMESPACE_DATA_ID_SIZE);
331    }
332
333    #[test]
334    fn multihash_invalid_code() {
335        let multihash =
336            Multihash::<ROW_NAMESPACE_DATA_ID_SIZE>::wrap(888, &[0; ROW_NAMESPACE_DATA_ID_SIZE])
337                .unwrap();
338        let cid =
339            CidGeneric::<ROW_NAMESPACE_DATA_ID_SIZE>::new_v1(ROW_NAMESPACE_DATA_CODEC, multihash);
340        let axis_err = RowNamespaceDataId::try_from(cid).unwrap_err();
341        assert_eq!(
342            axis_err,
343            CidError::InvalidMultihashCode(888, ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE)
344        );
345    }
346
347    #[test]
348    fn cid_invalid_codec() {
349        let multihash = Multihash::<ROW_NAMESPACE_DATA_ID_SIZE>::wrap(
350            ROW_NAMESPACE_DATA_ID_MULTIHASH_CODE,
351            &[0; ROW_NAMESPACE_DATA_ID_SIZE],
352        )
353        .unwrap();
354        let cid = CidGeneric::<ROW_NAMESPACE_DATA_ID_SIZE>::new_v1(4321, multihash);
355        let axis_err = RowNamespaceDataId::try_from(cid).unwrap_err();
356        assert_eq!(axis_err, CidError::InvalidCidCodec(4321));
357    }
358
359    #[test]
360    fn test_roundtrip_verify() {
361        // random
362        for _ in 0..5 {
363            let eds = generate_dummy_eds(2 << (rand::random::<usize>() % 8));
364            let dah = DataAvailabilityHeader::from_eds(&eds);
365
366            let namespace = eds.share(1, 1).unwrap().namespace();
367
368            for (id, row) in eds.get_namespace_data(namespace, &dah, 1).unwrap() {
369                let mut buf = BytesMut::new();
370                row.encode(&mut buf);
371                let decoded = RowNamespaceData::decode(id, &buf).unwrap();
372
373                decoded.verify(id, &dah).unwrap();
374            }
375        }
376
377        // parity share
378        let eds = generate_dummy_eds(2 << (rand::random::<usize>() % 8));
379        let dah = DataAvailabilityHeader::from_eds(&eds);
380        for (id, row) in eds
381            .get_namespace_data(Namespace::PARITY_SHARE, &dah, 1)
382            .unwrap()
383        {
384            let mut buf = BytesMut::new();
385            row.encode(&mut buf);
386            let decoded = RowNamespaceData::decode(id, &buf).unwrap();
387
388            decoded.verify(id, &dah).unwrap();
389        }
390    }
391
392    #[test]
393    fn verify_absent_ns() {
394        // parity share
395        let eds = generate_dummy_eds(2 << (rand::random::<usize>() % 8));
396        let dah = DataAvailabilityHeader::from_eds(&eds);
397
398        // namespace bigger than pay for blob, smaller than primary reserved padding, that is not
399        // used
400        let ns = Namespace::const_v0([0, 0, 0, 0, 0, 0, 0, 0, 0, 5]);
401        for (id, row) in eds.get_namespace_data(ns, &dah, 1).unwrap() {
402            assert!(row.shares.is_empty());
403            row.verify(id, &dah).unwrap();
404        }
405    }
406
407    #[test]
408    fn reconstruct_all() {
409        for _ in 0..3 {
410            let eds = generate_eds(8 << (rand::random::<usize>() % 6));
411            let dah = DataAvailabilityHeader::from_eds(&eds);
412
413            let mut namespaces: Vec<_> = eds
414                .data_square()
415                .iter()
416                .map(|shr| shr.namespace())
417                .filter(|ns| !ns.is_reserved())
418                .collect();
419            namespaces.dedup();
420
421            // first namespace should have 2 blobs over 3 rows
422            let namespace_data = eds.get_namespace_data(namespaces[0], &dah, 1).unwrap();
423            assert_eq!(namespace_data.len(), 3);
424            let shares = namespace_data.iter().flat_map(|(_, row)| row.shares.iter());
425
426            let blobs = Blob::reconstruct_all(shares).unwrap();
427            assert_eq!(blobs.len(), 2);
428
429            // rest of namespaces should have 1 blob each
430            for ns in &namespaces[1..] {
431                let namespace_data = eds.get_namespace_data(*ns, &dah, 1).unwrap();
432                assert_eq!(namespace_data.len(), 1);
433                let shares = namespace_data.iter().flat_map(|(_, row)| row.shares.iter());
434
435                let blobs = Blob::reconstruct_all(shares).unwrap();
436                assert_eq!(blobs.len(), 1);
437            }
438        }
439    }
440
441    #[test]
442    fn namespace_data_roundtrip() {
443        let proof = nmt_rs::nmt_proof::NamespaceProof::<
444            crate::nmt::NamespacedSha2Hasher,
445            { crate::nmt::NS_SIZE },
446        >::AbsenceProof {
447            proof: crate::nmt::Proof {
448                siblings: vec![
449                    nmt_rs::NamespacedHash::new(
450                        nmt_rs::NamespaceId([
451                            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
452                            0, 0, 0, 0, 4,
453                        ]),
454                        nmt_rs::NamespaceId([
455                            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
456                            0, 0, 0, 0, 4,
457                        ]),
458                        [
459                            180, 43, 29, 197, 134, 127, 103, 202, 217, 240, 11, 18, 15, 47, 140,
460                            136, 58, 134, 117, 174, 162, 95, 216, 114, 31, 71, 90, 238, 49, 228,
461                            95, 89,
462                        ],
463                    ),
464                    nmt_rs::NamespacedHash::new(
465                        nmt_rs::NamespaceId::MAX_ID,
466                        nmt_rs::NamespaceId::MAX_ID,
467                        [
468                            126, 112, 141, 49, 103, 177, 23, 186, 153, 245, 110, 62, 165, 4, 39,
469                            125, 171, 55, 116, 176, 36, 153, 101, 171, 25, 253, 200, 61, 226, 43,
470                            81, 52,
471                        ],
472                    ),
473                ],
474                range: 1..2,
475            },
476            ignore_max_ns: true,
477            leaf: Some(nmt_rs::NamespacedHash::new(
478                nmt_rs::NamespaceId([
479                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 115, 111, 118, 45,
480                    116, 101, 115, 116, 45, 112,
481                ]),
482                nmt_rs::NamespaceId([
483                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 115, 111, 118, 45,
484                    116, 101, 115, 116, 45, 112,
485                ]),
486                [
487                    132, 118, 183, 139, 217, 27, 43, 49, 209, 15, 142, 136, 209, 205, 230, 67, 247,
488                    102, 202, 206, 118, 16, 124, 41, 208, 225, 148, 103, 192, 184, 59, 155,
489                ],
490            )),
491        };
492
493        let row = RowNamespaceData {
494            proof: proof.into(),
495            shares: vec![],
496        };
497
498        // JSON works,
499        let row_j = serde_json::to_value(&row).unwrap();
500        let d_from_json: RowNamespaceData = serde_json::from_value(row_j).unwrap();
501        assert_eq!(d_from_json, row);
502
503        // binary
504        let s_row = postcard::to_allocvec(&row).unwrap();
505        let d_row: RowNamespaceData = postcard::from_bytes(&s_row).unwrap();
506        assert_eq!(row, d_row);
507    }
508}
celestia_types/row_namespace_data.rs

celestia_types/
row_namespace_data.rs
