celestia_types/
eds.rs

1//! Types related to EDS.
2
3use std::cmp::Ordering;
4use std::fmt::Display;
5
6use bytes::{Buf, BufMut, BytesMut};
7use serde::{Deserialize, Serialize};
8
9use crate::consts::appconsts::SHARE_SIZE;
10use crate::consts::data_availability_header::MIN_EXTENDED_SQUARE_WIDTH;
11use crate::nmt::{NS_SIZE, Namespace, Nmt, NmtExt};
12use crate::row_namespace_data::{RowNamespaceData, RowNamespaceDataId};
13use crate::{DataAvailabilityHeader, Error, InfoByte, Result, Share, bail_validation};
14
15/// Number of bytes needed to represent [`EdsId`] in `multihash`.
16pub const EDS_ID_SIZE: usize = 8;
17
18/// Represents an EDS of a specific Height
19///
20/// # Note
21///
22/// EdsId is excluded from shwap operating on top of bitswap due to possible
23/// EDS sizes exceeding bitswap block limits.
24#[derive(Debug, PartialEq, Clone, Copy)]
25pub struct EdsId {
26    height: u64,
27}
28
29/// Represents either column or row of the [`ExtendedDataSquare`].
30///
31/// [`ExtendedDataSquare`]: crate::eds::ExtendedDataSquare
32#[derive(Copy, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
33#[repr(u8)]
34pub enum AxisType {
35    /// A row of the data square.
36    Row = 0,
37    /// A column of the data square.
38    Col,
39}
40
41impl TryFrom<i32> for AxisType {
42    type Error = Error;
43
44    fn try_from(value: i32) -> Result<Self, Self::Error> {
45        match value {
46            0 => Ok(AxisType::Row),
47            1 => Ok(AxisType::Col),
48            n => Err(Error::InvalidAxis(n)),
49        }
50    }
51}
52
53impl Display for AxisType {
54    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
55        match self {
56            AxisType::Row => write!(f, "Row"),
57            AxisType::Col => write!(f, "Column"),
58        }
59    }
60}
61
62/// The data matrix in Celestia blocks extended with parity data.
63///
64/// It is created by a fixed size chunks of data, called [`Share`]s.
65///
66/// Each share is a cell of the [`ExtendedDataSquare`].
67///
68/// # Structure
69///
70/// The [`ExtendedDataSquare`] consists of four quadrants. The first
71/// quadrant (upper-left) is the original data submitted to the network,
72/// referred to as `OriginalDataSquare`. The other three quadrants are
73/// the parity data encoded row-wise or column-wise using Reed-Solomon
74/// `codec` specified in `EDS`.
75///
76/// The below diagram shows how the `EDS` is constructed. First, the 2nd
77/// and 3rd quadrants are created by computing Reed-Solomon parity data
78/// of the original data square, row-wise for 2nd and column-wise for
79/// 3rd quadrant. Then, the 4th quadrant is computed either row-wise
80/// from 3rd or column-wise from 2nd quadrant.
81///
82/// ```text
83///  ---------------------------
84/// |             |             |
85/// |           --|->           |
86/// |      1    --|->    2      |
87/// |           --|->           |
88/// |    | | |    |             |
89///  -------------+-------------
90/// |    v v v    |             |
91/// |           --|->           |
92/// |      3    --|->    4      |
93/// |           --|->           |
94/// |             |             |
95///  ---------------------------
96/// ```
97///
98/// # Data availability
99///
100/// The [`DataAvailabilityHeader`] is created by computing [`Nmt`] merkle
101/// roots of each row and column of [`ExtendedDataSquare`].
102/// By putting those together there are some key
103/// properties those have in terms of data availability.
104///
105/// Thanks to the parity data, to make original data unrecoverable, a malicious
106/// actor would need to hide more than a half of the data from each row and column.
107/// If we take `k` as the width of the `OriginalDataSquare`, then the attacker
108/// needs to hide more than `(k + 1)^2` shares from the [`ExtendedDataSquare`].
109/// For the `EDS` with a width of 4, the attacker needs to hide more than 50% of
110/// all the shares and that value approaches 25% as the square grows.
111///
112/// This allows for really efficient data sampling, as the sampling node can reach
113/// very high confidence that whole data is available by taking only a few samples.
114///
115/// # Example
116///
117/// This example shows rebuilding the merkle trees for each row of the EDS and compares
118/// them with the root hashes stored in data availability header.
119///
120/// ```no_run
121/// use celestia_types::Share;
122/// # use celestia_types::{ExtendedDataSquare, ExtendedHeader};
123/// # fn get_header(_: usize) -> ExtendedHeader {
124/// #     unimplemented!()
125/// # }
126/// # fn get_eds(_: usize) -> ExtendedDataSquare {
127/// #     unimplemented!()
128/// # }
129///
130/// let block_height = 15;
131/// let header = get_header(block_height);
132/// let eds = get_eds(block_height);
133/// let width = header.dah.square_width();
134///
135/// // for each row of the data square, build an nmt
136/// for row in 0..eds.square_width() {
137///     // check if the root corresponds to the one from the dah
138///     let root = eds.row_nmt(row).unwrap().root();
139///     assert_eq!(root, header.dah.row_root(row).unwrap());
140/// }
141/// ```
142///
143/// [`Nmt`]: crate::nmt::Nmt
144/// [`Share`]: crate::share::Share
145/// [`DataAvailabilityHeader`]: crate::DataAvailabilityHeader
146#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
147#[serde(into = "RawExtendedDataSquare")]
148pub struct ExtendedDataSquare {
149    /// The raw data of the EDS.
150    data_square: Vec<Share>,
151    /// The codec used to encode parity shares.
152    codec: String,
153    /// pre-calculated square length
154    square_width: u16,
155}
156
157impl ExtendedDataSquare {
158    /// Create a new EDS out of the provided shares.
159    ///
160    /// Shares should be provided in a row-major order, i.e. first shares of the first row,
161    /// then of the second row and so on.
162    ///
163    /// # Errors
164    ///
165    /// Returns an error if:
166    ///  - shares are of sizes different than [`SHARE_SIZE`]
167    ///  - amount of shares doesn't allow for forming a square
168    ///  - width of the square is smaller than [`MIN_EXTENDED_SQUARE_WIDTH`]
169    ///  - width of the square isn't a power of 2
170    ///  - namespaces of shares aren't in non-decreasing order row and column wise
171    pub fn new(shares: Vec<Vec<u8>>, codec: String) -> Result<Self> {
172        const MIN_SHARES: usize = MIN_EXTENDED_SQUARE_WIDTH * MIN_EXTENDED_SQUARE_WIDTH;
173
174        if shares.len() < MIN_SHARES {
175            bail_validation!(
176                "shares len ({}) < MIN_SHARES ({})",
177                shares.len(),
178                MIN_SHARES
179            );
180        }
181
182        let square_width = f64::sqrt(shares.len() as f64) as usize;
183
184        if square_width * square_width != shares.len() {
185            return Err(Error::EdsInvalidDimentions);
186        }
187
188        let square_width = u16::try_from(square_width).map_err(|_| Error::EdsInvalidDimentions)?;
189
190        // must be a power of 2
191        if square_width.count_ones() != 1 {
192            return Err(Error::EdsInvalidDimentions);
193        }
194
195        let check_share = |row, col, prev_ns: Option<Namespace>, axis| -> Result<Share> {
196            let idx = flatten_index(row, col, square_width);
197            let share = if is_ods_square(row, col, square_width) {
198                Share::from_raw(&shares[idx])?
199            } else {
200                Share::parity(&shares[idx])?
201            };
202
203            if prev_ns.is_some_and(|prev_ns| share.namespace() < prev_ns) {
204                let axis_idx = match axis {
205                    AxisType::Row => row,
206                    AxisType::Col => col,
207                };
208                bail_validation!("Shares of {axis} {axis_idx} are not sorted by their namespace");
209            }
210
211            Ok(share)
212        };
213
214        // Validate that namespaces of each column are sorted
215        for col in 0..square_width {
216            let mut prev_ns = None;
217
218            for row in 0..square_width {
219                let share = check_share(row, col, prev_ns, AxisType::Col)?;
220                prev_ns = Some(share.namespace());
221            }
222        }
223        // Validate that namespaces of each row are sorted collecting data square
224        let mut data_square = Vec::with_capacity(shares.len());
225        for row in 0..square_width {
226            let mut prev_ns = None;
227
228            for col in 0..square_width {
229                let share = check_share(row, col, prev_ns, AxisType::Row)?;
230                prev_ns = Some(share.namespace());
231                data_square.push(share);
232            }
233        }
234
235        let eds = ExtendedDataSquare {
236            data_square,
237            codec,
238            square_width,
239        };
240
241        Ok(eds)
242    }
243
244    /// Creates an `ExtendedDataSquare` from [`RawExtendedDataSquare`].
245    pub fn from_raw(raw_eds: RawExtendedDataSquare) -> Result<Self> {
246        ExtendedDataSquare::new(raw_eds.data_square, raw_eds.codec)
247    }
248
249    /// Crate a new EDS that represents an empty block
250    pub fn empty() -> ExtendedDataSquare {
251        // ODS in this case it is just one tail padded share.
252        let ods = vec![
253            [
254                Namespace::TAIL_PADDING.as_bytes(),
255                &[InfoByte::new(0, true).unwrap().as_u8()],
256                &[0; SHARE_SIZE - NS_SIZE - 1],
257            ]
258            .concat(),
259        ];
260
261        ExtendedDataSquare::from_ods(ods).expect("invalid EDS")
262    }
263
264    /// Create a new EDS out of the provided original data square shares.
265    ///
266    /// This method is similar to the [`ExtendedDataSquare::new`] but parity data
267    /// will be encoded automatically using the [`leopard_codec`]
268    ///
269    /// Shares should be provided in a row-major order.
270    ///
271    /// # Errors
272    ///
273    /// The same errors as in [`ExtendedDataSquare::new`] applies. The constrain
274    /// will be checked after the parity data is generated.
275    ///
276    /// Additionally, this function will propagate any error from encoding parity data.
277    pub fn from_ods(mut ods_shares: Vec<Vec<u8>>) -> Result<ExtendedDataSquare> {
278        let ods_width = f64::sqrt(ods_shares.len() as f64) as usize;
279        // this couldn't be detected later in `new()`
280        if ods_width * ods_width != ods_shares.len() {
281            return Err(Error::EdsInvalidDimentions);
282        }
283
284        let eds_width = ods_width * 2;
285        let mut eds_shares = Vec::with_capacity(eds_width * eds_width);
286        // take rows of ods and interleave them with parity shares
287        for _ in 0..ods_width {
288            eds_shares.extend(ods_shares.drain(..ods_width));
289            for _ in 0..ods_width {
290                eds_shares.push(vec![0; SHARE_SIZE]);
291            }
292        }
293        // fill bottom half of the square with parity data
294        eds_shares.resize(eds_width * eds_width, vec![0; SHARE_SIZE]);
295
296        // 2nd quadrant - encode parity of rows of 1st quadrant
297        for row in eds_shares.chunks_mut(eds_width).take(ods_width) {
298            leopard_codec::encode(row, ods_width)?;
299        }
300        // 3rd quadrant - encode parity of columns of 1st quadrant
301        for col in 0..ods_width {
302            let mut col: Vec<_> = eds_shares.iter_mut().skip(col).step_by(eds_width).collect();
303            leopard_codec::encode(&mut col, ods_width)?;
304        }
305        // 4th quadrant - encode parity of rows of 3rd quadrant
306        for row in eds_shares.chunks_mut(eds_width).skip(ods_width) {
307            leopard_codec::encode(row, ods_width)?;
308        }
309
310        ExtendedDataSquare::new(eds_shares, "Leopard".to_string())
311    }
312
313    /// The raw data of the EDS.
314    pub fn data_square(&self) -> &[Share] {
315        &self.data_square
316    }
317
318    /// The codec used to encode parity shares.
319    pub fn codec(&self) -> &str {
320        self.codec.as_str()
321    }
322
323    /// Returns the share of the provided coordinates.
324    pub fn share(&self, row: u16, column: u16) -> Result<&Share> {
325        let index = usize::from(row) * usize::from(self.square_width) + usize::from(column);
326
327        self.data_square
328            .get(index)
329            .ok_or(Error::EdsIndexOutOfRange(row, column))
330    }
331
332    /// Returns the mutable share of the provided coordinates.
333    #[cfg(any(test, feature = "test-utils"))]
334    pub(crate) fn share_mut(&mut self, row: u16, column: u16) -> Result<&mut Share> {
335        let index = flatten_index(row, column, self.square_width);
336
337        self.data_square
338            .get_mut(index)
339            .ok_or(Error::EdsIndexOutOfRange(row, column))
340    }
341
342    /// Returns the shares of a row.
343    pub fn row(&self, index: u16) -> Result<Vec<Share>> {
344        self.axis(AxisType::Row, index)
345    }
346
347    /// Returns the [`Nmt`] of a row.
348    pub fn row_nmt(&self, index: u16) -> Result<Nmt> {
349        self.axis_nmt(AxisType::Row, index)
350    }
351
352    /// Returns the shares of a column.
353    pub fn column(&self, index: u16) -> Result<Vec<Share>> {
354        self.axis(AxisType::Col, index)
355    }
356
357    /// Returns the [`Nmt`] of a column.
358    pub fn column_nmt(&self, index: u16) -> Result<Nmt> {
359        self.axis_nmt(AxisType::Col, index)
360    }
361
362    /// Returns the shares of column or row.
363    pub fn axis(&self, axis: AxisType, index: u16) -> Result<Vec<Share>> {
364        (0..self.square_width)
365            .map(|i| {
366                let (row, col) = match axis {
367                    AxisType::Row => (index, i),
368                    AxisType::Col => (i, index),
369                };
370
371                self.share(row, col).map(ToOwned::to_owned)
372            })
373            .collect()
374    }
375
376    /// Returns the [`Nmt`] of column or row.
377    pub fn axis_nmt(&self, axis: AxisType, index: u16) -> Result<Nmt> {
378        let mut tree = Nmt::default();
379
380        for i in 0..self.square_width {
381            let (row, col) = match axis {
382                AxisType::Row => (index, i),
383                AxisType::Col => (i, index),
384            };
385
386            let share = self.share(row, col)?;
387
388            tree.push_leaf(share.as_ref(), *share.namespace())
389                .map_err(Error::Nmt)?;
390        }
391
392        Ok(tree)
393    }
394
395    /// Get EDS square length.
396    pub fn square_width(&self) -> u16 {
397        self.square_width
398    }
399
400    /// Return all the shares that belong to the provided namespace in the EDS.
401    /// Results are returned as a list of rows of shares with the inclusion proof.
402    pub fn get_namespace_data(
403        &self,
404        namespace: Namespace,
405        dah: &DataAvailabilityHeader,
406        height: u64,
407    ) -> Result<Vec<(RowNamespaceDataId, RowNamespaceData)>> {
408        let mut rows = Vec::new();
409
410        for row in 0..self.square_width {
411            if !dah.row_contains(row, namespace)? {
412                continue;
413            }
414
415            let mut shares = Vec::with_capacity(self.square_width.into());
416
417            for col in 0..self.square_width {
418                let share = self.share(row, col)?;
419
420                // Shares in each row of EDS are sorted by namespace, so we
421                // can stop search the row if we reach to a bigger namespace.
422                match share.namespace().cmp(&namespace) {
423                    Ordering::Less => {}
424                    Ordering::Equal => shares.push(share.clone()),
425                    Ordering::Greater => break,
426                }
427            }
428
429            let proof = self.row_nmt(row)?.get_namespace_proof(*namespace);
430            let id = RowNamespaceDataId::new(namespace, row, height)?;
431            let data = RowNamespaceData {
432                proof: proof.into(),
433                shares,
434            };
435
436            rows.push((id, data))
437        }
438
439        Ok(rows)
440    }
441}
442
443impl EdsId {
444    /// Create a new eds id.
445    pub fn new(height: u64) -> Result<Self> {
446        if height == 0 {
447            return Err(Error::ZeroBlockHeight);
448        }
449
450        Ok(EdsId { height })
451    }
452
453    /// A height of the block which contains the data.
454    pub fn block_height(&self) -> u64 {
455        self.height
456    }
457
458    /// Encode eds id into the byte representation.
459    pub fn encode(&self, bytes: &mut BytesMut) {
460        bytes.reserve(EDS_ID_SIZE);
461        bytes.put_u64(self.height);
462    }
463
464    /// Decode eds id from the byte representation.
465    pub fn decode(mut buffer: &[u8]) -> Result<Self> {
466        if buffer.len() != EDS_ID_SIZE {
467            return Err(Error::InvalidLength(buffer.len(), EDS_ID_SIZE));
468        }
469
470        let height = buffer.get_u64();
471
472        EdsId::new(height)
473    }
474}
475
476/// Raw representation of [`ExtendedDataSquare`].
477#[derive(Serialize, Deserialize, Clone)]
478pub struct RawExtendedDataSquare {
479    /// The raw data of the EDS.
480    #[serde(with = "tendermint_proto::serializers::bytes::vec_base64string")]
481    pub data_square: Vec<Vec<u8>>,
482    /// The codec used to encode parity shares.
483    pub codec: String,
484}
485
486impl From<ExtendedDataSquare> for RawExtendedDataSquare {
487    fn from(eds: ExtendedDataSquare) -> RawExtendedDataSquare {
488        RawExtendedDataSquare {
489            data_square: eds
490                .data_square
491                .into_iter()
492                .map(|shr| shr.to_vec())
493                .collect(),
494            codec: eds.codec,
495        }
496    }
497}
498
499/// Returns true if and only if the provided coordinates belongs to Original Data Square
500/// (i.e. first quadrant of Extended Data Square).
501pub(crate) fn is_ods_square(row: u16, column: u16, square_width: u16) -> bool {
502    let ods_width = square_width / 2;
503    row < ods_width && column < ods_width
504}
505
506fn flatten_index(row: u16, col: u16, square_width: u16) -> usize {
507    usize::from(row) * usize::from(square_width) + usize::from(col)
508}
509
510#[cfg(test)]
511mod tests {
512    use super::*;
513    use crate::test_utils::generate_eds;
514    use crate::{Blob, ExtendedHeader};
515
516    #[test]
517    fn axis_type_serialization() {
518        assert_eq!(AxisType::Row as u8, 0);
519        assert_eq!(AxisType::Col as u8, 1);
520    }
521
522    #[test]
523    fn axis_type_deserialization() {
524        assert_eq!(AxisType::try_from(0).unwrap(), AxisType::Row);
525        assert_eq!(AxisType::try_from(1).unwrap(), AxisType::Col);
526
527        let axis_type_err = AxisType::try_from(2).unwrap_err();
528        assert!(matches!(axis_type_err, Error::InvalidAxis(2)));
529        let axis_type_err = AxisType::try_from(99).unwrap_err();
530        assert!(matches!(axis_type_err, Error::InvalidAxis(99)));
531    }
532
533    #[test]
534    fn get_namespaced_data() {
535        let eds_json = include_str!("../test_data/shwap_samples/eds.json");
536        let raw_eds: RawExtendedDataSquare = serde_json::from_str(eds_json).unwrap();
537        let eds = ExtendedDataSquare::from_raw(raw_eds).unwrap();
538
539        let dah_json = include_str!("../test_data/shwap_samples/dah.json");
540        let dah: DataAvailabilityHeader = serde_json::from_str(dah_json).unwrap();
541
542        let height = 45577;
543
544        let rows = eds
545            .get_namespace_data(Namespace::new_v0(&[1, 170]).unwrap(), &dah, height)
546            .unwrap();
547        assert_eq!(rows.len(), 1);
548        let (id, row) = &rows[0];
549        row.verify(*id, &dah).unwrap();
550        assert_eq!(row.shares.len(), 2);
551
552        let rows = eds
553            .get_namespace_data(Namespace::new_v0(&[1, 187]).unwrap(), &dah, height)
554            .unwrap();
555        assert_eq!(rows.len(), 2);
556        assert_eq!(rows[0].1.shares.len(), 1);
557        assert_eq!(rows[1].1.shares.len(), 4);
558        for (id, row) in rows {
559            row.verify(id, &dah).unwrap();
560        }
561    }
562
563    #[test]
564    fn nmt_roots() {
565        let eds_json = include_str!("../test_data/shwap_samples/eds.json");
566        let raw_eds: RawExtendedDataSquare = serde_json::from_str(eds_json).unwrap();
567        let eds = ExtendedDataSquare::from_raw(raw_eds).unwrap();
568
569        let dah_json = include_str!("../test_data/shwap_samples/dah.json");
570        let dah: DataAvailabilityHeader = serde_json::from_str(dah_json).unwrap();
571
572        assert_eq!(dah.row_roots().len(), usize::from(eds.square_width()));
573        assert_eq!(dah.column_roots().len(), usize::from(eds.square_width()));
574
575        for (i, root) in dah.row_roots().iter().enumerate() {
576            let mut tree = eds.row_nmt(i as u16).unwrap();
577            assert_eq!(*root, tree.root());
578
579            let mut tree = eds.axis_nmt(AxisType::Row, i as u16).unwrap();
580            assert_eq!(*root, tree.root());
581        }
582
583        for (i, root) in dah.column_roots().iter().enumerate() {
584            let mut tree = eds.column_nmt(i as u16).unwrap();
585            assert_eq!(*root, tree.root());
586
587            let mut tree = eds.axis_nmt(AxisType::Col, i as u16).unwrap();
588            assert_eq!(*root, tree.root());
589        }
590    }
591
592    #[test]
593    fn ods_square() {
594        assert!(is_ods_square(0, 0, 4));
595        assert!(is_ods_square(0, 1, 4));
596        assert!(is_ods_square(1, 0, 4));
597        assert!(is_ods_square(1, 1, 4));
598
599        assert!(!is_ods_square(0, 2, 4));
600        assert!(!is_ods_square(0, 3, 4));
601        assert!(!is_ods_square(1, 2, 4));
602        assert!(!is_ods_square(1, 3, 4));
603
604        assert!(!is_ods_square(2, 0, 4));
605        assert!(!is_ods_square(2, 1, 4));
606        assert!(!is_ods_square(3, 0, 4));
607        assert!(!is_ods_square(3, 1, 4));
608
609        assert!(!is_ods_square(2, 2, 4));
610        assert!(!is_ods_square(2, 3, 4));
611        assert!(!is_ods_square(3, 2, 4));
612        assert!(!is_ods_square(3, 3, 4));
613    }
614
615    #[test]
616    fn get_row_and_col() {
617        let raw_share = |x, y| {
618            [
619                Namespace::new_v0(&[x, y]).unwrap().as_bytes(),
620                &[0u8; SHARE_SIZE - NS_SIZE][..],
621            ]
622            .concat()
623        };
624        let share = |x, y, parity: bool| {
625            if !parity {
626                Share::from_raw(&raw_share(x, y)).unwrap()
627            } else {
628                Share::parity(&raw_share(x, y)).unwrap()
629            }
630        };
631
632        #[rustfmt::skip]
633        let shares = vec![
634            raw_share(0, 0), raw_share(0, 1), raw_share(0, 2), raw_share(0, 3),
635            raw_share(1, 0), raw_share(1, 1), raw_share(1, 2), raw_share(1, 3),
636            raw_share(2, 0), raw_share(2, 1), raw_share(2, 2), raw_share(2, 3),
637            raw_share(3, 0), raw_share(3, 1), raw_share(3, 2), raw_share(3, 3),
638        ];
639
640        let eds = ExtendedDataSquare::new(shares, "fake".to_string()).unwrap();
641
642        assert_eq!(
643            eds.row(0).unwrap(),
644            vec![
645                share(0, 0, false),
646                share(0, 1, false),
647                share(0, 2, true),
648                share(0, 3, true)
649            ],
650        );
651        assert_eq!(
652            eds.row(1).unwrap(),
653            vec![
654                share(1, 0, false),
655                share(1, 1, false),
656                share(1, 2, true),
657                share(1, 3, true)
658            ],
659        );
660        assert_eq!(
661            eds.row(2).unwrap(),
662            vec![
663                share(2, 0, true),
664                share(2, 1, true),
665                share(2, 2, true),
666                share(2, 3, true)
667            ],
668        );
669        assert_eq!(
670            eds.row(3).unwrap(),
671            vec![
672                share(3, 0, true),
673                share(3, 1, true),
674                share(3, 2, true),
675                share(3, 3, true)
676            ],
677        );
678
679        assert_eq!(
680            eds.axis(AxisType::Row, 0).unwrap(),
681            vec![
682                share(0, 0, false),
683                share(0, 1, false),
684                share(0, 2, true),
685                share(0, 3, true)
686            ],
687        );
688        assert_eq!(
689            eds.axis(AxisType::Row, 1).unwrap(),
690            vec![
691                share(1, 0, false),
692                share(1, 1, false),
693                share(1, 2, true),
694                share(1, 3, true)
695            ],
696        );
697        assert_eq!(
698            eds.axis(AxisType::Row, 2).unwrap(),
699            vec![
700                share(2, 0, true),
701                share(2, 1, true),
702                share(2, 2, true),
703                share(2, 3, true)
704            ],
705        );
706        assert_eq!(
707            eds.axis(AxisType::Row, 3).unwrap(),
708            vec![
709                share(3, 0, true),
710                share(3, 1, true),
711                share(3, 2, true),
712                share(3, 3, true)
713            ],
714        );
715
716        assert_eq!(
717            eds.column(0).unwrap(),
718            vec![
719                share(0, 0, false),
720                share(1, 0, false),
721                share(2, 0, true),
722                share(3, 0, true)
723            ],
724        );
725        assert_eq!(
726            eds.column(1).unwrap(),
727            vec![
728                share(0, 1, false),
729                share(1, 1, false),
730                share(2, 1, true),
731                share(3, 1, true)
732            ],
733        );
734        assert_eq!(
735            eds.column(2).unwrap(),
736            vec![
737                share(0, 2, true),
738                share(1, 2, true),
739                share(2, 2, true),
740                share(3, 2, true)
741            ],
742        );
743        assert_eq!(
744            eds.column(3).unwrap(),
745            vec![
746                share(0, 3, true),
747                share(1, 3, true),
748                share(2, 3, true),
749                share(3, 3, true)
750            ],
751        );
752
753        assert_eq!(
754            eds.axis(AxisType::Col, 0).unwrap(),
755            vec![
756                share(0, 0, false),
757                share(1, 0, false),
758                share(2, 0, true),
759                share(3, 0, true)
760            ],
761        );
762        assert_eq!(
763            eds.axis(AxisType::Col, 1).unwrap(),
764            vec![
765                share(0, 1, false),
766                share(1, 1, false),
767                share(2, 1, true),
768                share(3, 1, true)
769            ],
770        );
771        assert_eq!(
772            eds.axis(AxisType::Col, 2).unwrap(),
773            vec![
774                share(0, 2, true),
775                share(1, 2, true),
776                share(2, 2, true),
777                share(3, 2, true)
778            ],
779        );
780        assert_eq!(
781            eds.axis(AxisType::Col, 3).unwrap(),
782            vec![
783                share(0, 3, true),
784                share(1, 3, true),
785                share(2, 3, true),
786                share(3, 3, true)
787            ],
788        );
789    }
790
791    #[test]
792    fn validation() {
793        ExtendedDataSquare::new(vec![], "fake".to_string()).unwrap_err();
794        ExtendedDataSquare::new(vec![vec![]], "fake".to_string()).unwrap_err();
795        ExtendedDataSquare::new(vec![vec![]; 4], "fake".to_string()).unwrap_err();
796
797        ExtendedDataSquare::new(vec![vec![0u8; SHARE_SIZE]; 4], "fake".to_string()).unwrap();
798        ExtendedDataSquare::new(vec![vec![0u8; SHARE_SIZE]; 6], "fake".to_string()).unwrap_err();
799        ExtendedDataSquare::new(vec![vec![0u8; SHARE_SIZE]; 16], "fake".to_string()).unwrap();
800
801        let share = |n| {
802            [
803                Namespace::new_v0(&[n]).unwrap().as_bytes(),
804                &[0u8; SHARE_SIZE - NS_SIZE][..],
805            ]
806            .concat()
807        };
808
809        ExtendedDataSquare::from_ods(vec![
810            // row 0
811            share(0), // ODS
812        ])
813        .unwrap();
814
815        ExtendedDataSquare::from_ods(vec![
816            // row 0
817            share(1),
818            share(2),
819            // row 1
820            share(1),
821            share(3),
822        ])
823        .unwrap();
824
825        ExtendedDataSquare::from_ods(vec![
826            // row 0
827            share(1),
828            share(2),
829            // row 1
830            share(1),
831            share(1), // error: smaller namespace in 2nd column
832        ])
833        .unwrap_err();
834
835        ExtendedDataSquare::from_ods(vec![
836            // row 0
837            share(1),
838            share(1),
839            // row 1
840            share(2),
841            share(1), // error: smaller namespace in 2nd row
842        ])
843        .unwrap_err();
844
845        // not a power of 2
846        ExtendedDataSquare::new(vec![share(1); 6 * 6], "fake".to_string()).unwrap_err();
847    }
848
849    #[test]
850    fn empty_block_eds() {
851        let s = include_str!("../test_data/chain1/extended_header_block_1.json");
852        let genesis: ExtendedHeader = serde_json::from_str(s).unwrap();
853
854        let eds = ExtendedDataSquare::empty();
855        let dah = DataAvailabilityHeader::from_eds(&eds);
856        assert_eq!(dah, genesis.dah);
857    }
858
859    #[test]
860    fn reconstruct_all() {
861        let eds = generate_eds(8 << (rand::random::<usize>() % 6));
862
863        let blobs = Blob::reconstruct_all(eds.data_square()).unwrap();
864        // first ods row has PFB's, one blob occupies 2 rows, and rest rows have 1 blob each
865        let expected = eds.square_width() as usize / 2 - 2;
866        assert_eq!(blobs.len(), expected);
867    }
868}
celestia_types/eds.rs

celestia_types/
eds.rs
