Struct celestia_types::ExtendedDataSquare

pub struct ExtendedDataSquare {
    pub data_square: Vec<Vec<u8>>,
    pub codec: String,
    /* private fields */
}

The data matrix in Celestia blocks extended with parity data.

It is created by a fixed size chunks of data, called Shares. Each share is a cell of the ExtendedDataSquare.

Structure

The ExtendedDataSquare consists of four quadrants. The first quadrant (upper-left) is the original data submitted to the network, referred to as OriginalDataSquare. The other three quadrants are the parity data encoded row-wise or column-wise using Reed-Solomon codec specified in EDS.

The below diagram shows how the EDS is constructed. First, the 2nd and 3rd quadrants are created by computing Reed-Solomon parity data of the original data square, row-wise for 2nd and column-wise for 3rd quadrant. Then, the 4th quadrant is computed either row-wise from 3rd or column-wise from 2nd quadrant.

 ---------------------------
|             |             |
|           --|->           |
|      1    --|->    2      |
|           --|->           |
|    | | |    |             |
 -------------+-------------
|    v v v    |             |
|           --|->           |
|      3    --|->    4      |
|           --|->           |
|             |             |
 ---------------------------

Data availability

The DataAvailabilityHeader is created by computing Nmt merkle roots of each row and column of ExtendedDataSquare. By putting those together there are some key properties those have in terms of data availability.

Thanks to the parity data, to make original data unrecoverable, a malicious actor would need to hide more than a half of the data from each row and column. If we take k as the width of the OriginalDataSquare, then the attacker needs to hide more than (k + 1)^2 shares from the ExtendedDataSquare. For the EDS with a width of 4, the attacker needs to hide more than 50% of all the shares and that value approaches 25% as the square grows.

This allows for really efficient data sampling, as the sampling node can reach very high confidence that whole data is available by taking only a few samples.

Example

This example shows rebuilding the merkle trees for each row of the EDS and compares them with the root hashes stored in data availability header.

use celestia_types::nmt::{Namespace, NamespacedSha2Hasher, Nmt};
use celestia_types::Share;
use nmt_rs::NamespaceMerkleHasher;

let block_height = 15;
let header = get_header(block_height);
let eds = get_eds(block_height);
let width = header.dah.square_len();

// for each row of the data square, build an nmt
for (y, row) in eds.data_square.chunks(width).enumerate() {
    let mut nmt = Nmt::with_hasher(NamespacedSha2Hasher::with_ignore_max_ns(true));

    for (x, leaf) in row.iter().enumerate() {
        if x < width / 2 && y < width / 2 {
            // the `OriginalDataSquare` part of the `EDS`
            let share = Share::from_raw(leaf).unwrap();
            let ns = share.namespace();
            nmt.push_leaf(share.as_ref(), *ns).unwrap();
        } else {
            // the parity data computed using `eds.codec`
            nmt.push_leaf(leaf, *Namespace::PARITY_SHARE).unwrap();
        }
    }

    // check if the root corresponds to the one from the dah
    let root = nmt.root();
    assert_eq!(root, header.dah.row_root(y).unwrap());
}

Fields

data_square: Vec<Vec<u8>>

The raw data of the EDS.

codec: String

The codec used to encode parity shares.

Implementations

impl ExtendedDataSquare

pub fn new(shares: Vec<Vec<u8>>, codec: String) -> Result<Self>

Create a new EDS out of the provided shares. Returns error if number of shares isn’t a square number

pub fn row(&self, index: usize) -> Result<Vec<Vec<u8>>>

Return row with index

pub fn column(&self, index: usize) -> Result<Vec<Vec<u8>>>

Return colum with index

pub fn axis(&self, axis: AxisType, index: usize) -> Result<Vec<Vec<u8>>>

Return column or row with the provided index

pub fn square_len(&self) -> usize

Get EDS square length

pub fn get_namespaced_data( &self, namespace: Namespace, dah: &DataAvailabilityHeader, height: u64 ) -> Result<Vec<NamespacedData>>

Return all the shares that belong to the provided namespace in the EDS. Results are returned as a list of rows of shares with the inclusion proof

Trait Implementations

impl Clone for ExtendedDataSquare

fn clone(&self) -> ExtendedDataSquare

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for ExtendedDataSquare

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for ExtendedDataSquare

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl PartialEq for ExtendedDataSquare

fn eq(&self, other: &ExtendedDataSquare) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for ExtendedDataSquare

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for ExtendedDataSquare

impl StructuralEq for ExtendedDataSquare

impl StructuralPartialEq for ExtendedDataSquare