jellyfish icon indicating copy to clipboard operation
jellyfish copied to clipboard

Eliminate quadratic bottlenecks in Reed-Solomon decoder

Open ggutoski opened this issue 1 year ago • 0 comments

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.

ggutoski avatar Jun 26 '23 16:06 ggutoski