celestia_types/
eds.rs

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

celestia_types/
eds.rs
