Reed-Muller or other locally decodable erasure codes

[cavemanloverboy]

Currently, the solana-ledger rust crate uses Reed-Solomon erasure codes. For Firedancer's ledger, it may be worth considering and benchmarking locally decodable erasure codes.

Are there any existing highly optimized C libraries that implement locally decodable erasure codes e.g. Reed-Muller?

[ripatel-fd]

For Firedancer, I think the team is likely to create an optimized Reed-Solomon implementation from scratch. We generally try to minimize the amount of external dependencies. I'm also not aware of plans to change the erasure coding algorithm.

[ptaffet-jump]

I'm not too familiar with solana-ledger yet, but I think it uses Reed-Solomon because Turbine does. We're first working on implementing something compatible with the current Turbine before we decide to propose breaking changes.

[cavemanloverboy]

Thanks for the info. It makes sense to match functionality first. To give some context for my question, I'm designing a distributed ledger and have been looking at locally decodable codes and fountain codes. Wanted to see if the firedancer team was cooking up something in this regard.

Here's a recent paper I read with a bit more info

http://article.sapub.org/10.5923.j.jwnc.20160601.02.html#Sec1

RS has O(N^2) decoding time w/ block size N vs DF Raptor code which is O(N) with smaller constant. I recently found a C library that implements raptor codes https://github.com/obolo/freeRaptor, which may or may not be worth checking out (at the very least as a reference implementation). Going to check it out this week and test/benchmark with the other codes I've been trying.

edit: also tried raptorQ

[ptaffet-jump]

I'm not sure if you're still interested in this topic, but I just pushed our Reed-Solomon encoder. It's O(N*log N) using some techniques in recent papers and also has a very low constant coefficient. See #244 for more details.

[mmcgee-jump]

Closing for now, we probably have lower hanging fruit than changing codes at this point.