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

celestia_types/
eds.rs
