#erasure-coding #polkadot #availability #system #root #data #merkle

polkadot-erasure-coding

Erasure coding used for Polkadot's availability system (polkadot v1.10.0)

11 major breaking releases

11.0.0 Apr 8, 2024
10.0.0 Mar 18, 2024
9.0.0 Feb 26, 2024
8.0.0 Feb 13, 2024
0.0.0 Nov 21, 2022

#2011 in Magic Beans

Download history 162/week @ 2023-12-31 168/week @ 2024-01-07 141/week @ 2024-01-14 211/week @ 2024-01-21 149/week @ 2024-01-28 284/week @ 2024-02-04 424/week @ 2024-02-11 433/week @ 2024-02-18 1135/week @ 2024-02-25 513/week @ 2024-03-03 413/week @ 2024-03-10 849/week @ 2024-03-17 844/week @ 2024-03-24 892/week @ 2024-03-31 785/week @ 2024-04-07 582/week @ 2024-04-14

3,143 downloads per month
Used in 17 crates (7 directly)

GPL-3.0-only

17KB
234 lines

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.

Dependencies

~27MB
~540K SLoC