Crate polkadot_erasure_coding

As part of Polkadot’s availability system, certain pieces of data for each block are required to be kept available.

The way we accomplish this is by erasure coding the data into n pieces and constructing a merkle root of the data.

Each of n validators stores their piece of data. We assume n = 3f + k, 0 < k ≤ 3. f is the maximum number of faulty validators in the system. The data is coded so any f+1 chunks can be used to reconstruct the full data.

Structs

• Branches
  An iterator that yields merkle branches and chunk data for all chunks to be sent to other validators.

Enums

• Error
  Errors in erasure coding.

Functions

• branch_hash
  Verify a merkle branch, yielding the chunk hash meant to be present at that index.
• branches
  Construct a trie from chunks of an erasure-coded value. This returns the root hash and an iterator of merkle proofs, one for each validator.
• obtain_chunks
  Obtain erasure-coded chunks, one for each validator.
• obtain_chunks_v1
  Obtain erasure-coded chunks for v1 AvailableData, one for each validator.
• reconstruct
  Reconstruct decodable data from a set of chunks.
• reconstruct_from_systematic
  Reconstruct the available data from the set of systematic chunks.
• reconstruct_from_systematic_v1
  Reconstruct the v1 available data from the set of systematic chunks.
• reconstruct_v1
  Reconstruct the v1 available data from a set of chunks.
• recovery_threshold
  Obtain a threshold of chunks that should be enough to recover the data.
• systematic_recovery_threshold
  Obtain the threshold of systematic chunks that should be enough to recover the data.