What is a Reed-Solomon code used for in blockchains?

Two things. In data availability it lets a verifier sample a few positions of an encoded block and gain confidence that the whole block is retrievable. In proving it underpins FRI-style polynomial commitments, which achieve short proofs by folding the code recursively.

Why replace Reed-Solomon inside sumcheck?

Over binary fields the product of two binary messages under Reed-Solomon is no longer binary, so the prover's first and most expensive round grows by a logarithmic factor. A binary-preserving code from algebraic geometry removed that growth and cut what the prover sends in that round by more than three times.

Reed-Solomon

Also: Reed-Solomon code · RS code

An error-correcting code that underpins both data availability sampling and the polynomial commitments inside most modern proof systems.

A Reed-Solomon code encodes a message as evaluations of a polynomial over a finite field. Any sufficiently large subset of those evaluations recovers the message, which makes the code useful twice over: for recovering data that is partly missing, and for proving something about a polynomial by checking it in a few places.

Where it appears in proving

Hash-based polynomial commitments built on FRI get short proofs by recursively folding Reed-Solomon codes, and the first few folding rounds operate on the largest codewords. That is where prover work concentrates, and it is what recent schemes attack directly.

It also carries a cost that is easy to miss. Over binary fields the product of two binary messages under Reed-Solomon is no longer binary, so the prover's most expensive sumcheck round grows by a logarithmic factor. A binary-preserving code built from algebraic geometry removed that growth and cut what the prover sends in that round by more than three times.

Where it appears in data availability

The same property supports sampling. Encode a block, and a verifier checking a small number of positions gains confidence that the whole block is retrievable without downloading it.

Questions

What is a Reed-Solomon code used for in blockchains?: Two things. In data availability it lets a verifier sample a few positions of an encoded block and gain confidence that the whole block is retrievable. In proving it underpins FRI-style polynomial commitments, which achieve short proofs by folding the code recursively.
Why replace Reed-Solomon inside sumcheck?: Over binary fields the product of two binary messages under Reed-Solomon is no longer binary, so the prover's first and most expensive round grows by a logarithmic factor. A binary-preserving code from algebraic geometry removed that growth and cut what the prover sends in that round by more than three times.

All 39 terms