Struct ExtendedDataSquare

pub struct ExtendedDataSquare { /* 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::Share;

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

// for each row of the data square, build an nmt
for row in 0..eds.square_width() {
    // check if the root corresponds to the one from the dah
    let root = eds.row_nmt(row).unwrap().root();
    assert_eq!(root, header.dah.row_root(row).unwrap());
}

Implementations

impl ExtendedDataSquare

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

Create a new EDS out of the provided shares.

Shares should be provided in a row-major order, i.e. first shares of the first row, then of the second row and so on.

Errors

Returns an error if:

• shares are of sizes different than SHARE_SIZE
• amount of shares doesn’t allow for forming a square
• width of the square is smaller than MIN_EXTENDED_SQUARE_WIDTH
• width of the square is bigger than max_extended_square_width
• width of the square isn’t a power of 2
• namespaces of shares aren’t in non-decreasing order row and column wise

pub fn from_raw( raw_eds: RawExtendedDataSquare, app_version: AppVersion, ) -> Result<Self>

Creates an ExtendedDataSquare from RawExtendedDataSquare and an AppVersion.

pub fn empty() -> ExtendedDataSquare

Crate a new EDS that represents an empty block

pub fn from_ods( ods_shares: Vec<Vec<u8>>, app_version: AppVersion, ) -> Result<ExtendedDataSquare>

Create a new EDS out of the provided original data square shares.

This method is similar to the ExtendedDataSquare::new but parity data will be encoded automatically using the leopard_codec

Shares should be provided in a row-major order.

Errors

The same errors as in ExtendedDataSquare::new applies. The constrain will be checked after the parity data is generated.

Additionally, this function will propagate any error from encoding parity data.

pub fn data_square(&self) -> &[Share]

The raw data of the EDS.

pub fn codec(&self) -> &str

The codec used to encode parity shares.

pub fn share(&self, row: u16, column: u16) -> Result<&Share>

Returns the share of the provided coordinates.

pub fn row(&self, index: u16) -> Result<Vec<Share>>

Returns the shares of a row.

pub fn row_nmt(&self, index: u16) -> Result<Nmt>

Returns the Nmt of a row.

pub fn column(&self, index: u16) -> Result<Vec<Share>>

Returns the shares of a column.

pub fn column_nmt(&self, index: u16) -> Result<Nmt>

Returns the Nmt of a column.

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

Returns the shares of column or row.

pub fn axis_nmt(&self, axis: AxisType, index: u16) -> Result<Nmt>

Returns the Nmt of column or row.

pub fn square_width(&self) -> u16

Get EDS square length.

pub fn get_namespace_data( &self, namespace: Namespace, dah: &DataAvailabilityHeader, height: u64, ) -> Result<Vec<(RowNamespaceDataId, RowNamespaceData)>>

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 duplicate 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 From<ExtendedDataSquare> for RawExtendedDataSquare

fn from(eds: ExtendedDataSquare) -> RawExtendedDataSquare

Converts to this type from the input type.

impl PartialEq for ExtendedDataSquare

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

Tests for self and other values to be equal, and is used by ==.

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

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 StructuralPartialEq for ExtendedDataSquare