To erasure code `N`

source chunks of the records (as scalars in `Fr`

of the BLS12-381 curve) and source commitments (as `G1`

points on the same curve) to `2N`

, we use the following approach:

- Inverse FFT (in Fr or G1, respectively) to interpolate a degree
`N-1`

polynomial - FFT to evaluate it over domain of size
`2N`

Then to recover the source chunks from a random sample of `N`

chunks we use a known approach described by Vitalik here. @Chen_Feng_2023 was kind to explain it on a simple example:

Consider a simple polynomial `f(x) = x + 1`

over `Z_5`

. Note that 2 is a primitive 4th root of unity. We have the following evaluations:

```
f(2^0) = 2,
f(2^1) = 3,
f(2^2) = 0,
f(2^3) = 4
```

Say, we are missing two evaluations, `f(2^1) = 3`

and `f(2^3) = 4`

. How can we recover `f(x)`

using FFT-based algorithms?

Input:

```
f(2^0) = 2,
f(2^1) = null,
f(2^2) = 0,
f(2^3) = null
```

By definition, we have `Z(x) = (x - 2^1)(x - 2^3)`

, `D(x) = f(x)`

, and `E(x)`

that evaluates to our input with erasures:

```
E(2^0) = 2
E(2^1) = 0
E(2^2) = 0
E(2^3) = 0
```

Clearly, we have `D(x) Z(x) = E(x) Z(x)`

. Also,

```
E(2^0)*Z(2^0) = 2 * 2 = 4
E(2^1)*Z(2^1) = 0 * 0 = 0
E(2^2)*Z(2^2) = 0 * 2 = 0
E(2^3)*Z(2^3) = 0 * 0 = 0
```

By interpolating the above four points, we have a unique polynomial

`g(x) = (x - 2^1) (x - 2^2) (x - 2^3)`

. If we can prove that `D(x) Z(x) = g(x)`

, then we can recover `D(x)`

, which is the source `f(x)`

.

Note that, by construction, `g(x)`

is of degree at most 3, and `Z(x)`

is of degree 2. Also, by definition, `f(x)`

is of degree at most 1.

**Proof by contradiction**. Suppose that we have another polynomial `fâ€™(x)`

of degree at most 1 such that `fâ€™(x) Z(x) = f(x) Z(x)`

. Then, we have `fâ€™(2^0) = f(2^0)`

and `fâ€™(2^2) = f(2^2)`

. Thus, `fâ€™(x) - f(x)`

has at least two zeros. This a contradiction because `fâ€™(x) - f(x)`

is of degree at most 1.

How can we compute `g(x)/Z(x)`

?

Method 1: Extended Euclidean algorithm.

Method 2: Introducing a random `k`

as suggested by Vitalik. **Note that k shouldnâ€™t be** in the set

`{2^0, 2^1, 2^2, 2^3 }`

. Vitalik hasnâ€™t emphasized this.**Open questions**

Can the recovery algorithm as above be adapted to work with `G1`

points so we can recover erased commitments? I feel like it could since we can do FFT in `G1`

, but Iâ€™m hesitant about `E(x)*Z(x)`

multiplication

Alternatively, is there another algorithm that works in `G1`

?