Feedback on the Reed-Solomon module

[kevaundray]

This has been taken from Benedikt Wagner's document.

Batching together all of the comments for the RS crate since there were quite a lot.

Unique decoding comment unclear

• Make it clearer what unique means here:

  rust-eth-kzg/cryptography/erasure_codes/src/reed_solomon.rs

  Line 11 in e043452

  /// of unique decoding.

We can modify this to contract with list decoding for example.

RS vs Poly

• Could the Rs module and the poly module be merged into one?

Comment on acceptable_num_block_erasures

Link:

rust-eth-kzg/cryptography/erasure_codes/src/reed_solomon.rs

Line 98 in e043452

/// before we are not able to recover the message.

This might not be correct in general, but only if expansion_factor is 2.
In general, this should be `(expansion_factor-1) * block_size / expansion_factor`.

codeword_with_erasures parameter on recover_polynomial_coefficient is unclear

Given the description and the type, it is not clear how the `codeword_with_erasures` parameter encodes *where* the erasures are

Cells vs Blocks

The RS code makes no mention of the word "Cells". Some docs would be good to explain how they relate, or rephrasing the block terminology into Cell.

Inconsistent comment in construct_vanishing_poly_from_block_erasures

The comment above says we will turn `X-r` into `X^3 - r^3`.
From the implementation it seems, we would turn `X-r` into `X^3 - r`. 

Variable renamings

To be more concise and spec aligned: 

`data_eval` -> `e_eval`
`z_x_eval` -> `z_eval`
`dz_poly` -> `dz_coeff`
`coset_dz_eval` -> `dz_coset_eval`
`inv_coset_z_x_eval` -> `z_inv_coset_eval`
`coset_quotient_eval` -> `d_eval`
`coefficients` -> `d_coeff`

Comment regarding evaluation of vanishing polynomial is confusing/wrong

"the vanishing polynomial evaluated at the missing points" does not make sense: by definition, it evaluates to 0 at the missing points. Should this be changed to say "evaluated over the entire evaluation domain"? 

Wrong comment equating (D * Z)(X) and (E * Z)(X)

The comment for reference is:

// Compute (D * Z)(X) or (E * Z)(X) (same polynomials)

These are not the same as polynomials.
In particular, `D*Z` has lower degree than `E*Z`.
The important part is that these two polynomials agree over the entire evaluation domain of size `poly_len * expansion_factor`, and that `D*Z` has degree at most `poly_len * expansion_factor - 1`, so it is fully determined by the evaluations of `E*Z` that we have.

Error parameter is not precise

Link:

rust-eth-kzg/cryptography/erasure_codes/src/reed_solomon.rs

Line 317 in e043452

num_coefficients: coefficients.len(),

Technically coefficients.len() is not what we want to return here. In the good case, where there are no errors, coefficients.len() will not equal `self.poly_len` -- it will equal `self.poly_len * expansion_factor.

It might not be worth it to check for this, though it should be easy by getting the position of the non-zero coefficient and adding `self.poly_len` to it.

Related to #246

Note: I've paraphrased a lot of this, so any mistakes are mine.