jellyfish
jellyfish copied to clipboard
Eliminate quadratic bottlenecks in Reed-Solomon decoder
reed_solomon_erasure_decode_rou
currently uses quadratic-time Lagrange interpolation. Switch to a quasi-linear-time interpolation such as this: Reed-Solomon erasure code recovery in n*log^2(n) time with FFTs - Sharding - Ethereum Research
https://github.com/EspressoSystems/jellyfish/blob/3e8b7d6d1908345951e299eed63e656420e4e401/primitives/src/reed_solomon_code/mod.rs#L151
At this time, the primary use case for Reed-Solomon is VID. For this use case we expect decoding to be used only rarely, under adverse network conditions. Hence, this issue is currently low-priority.