About Reed Solomon Codes
Implementation and documentation for Reed-Solomon encoding is in the
risc0-zkp-core Rust crate.
A RISC Zero receipt demonstrates the validity of the associated execution trace by encoding the execution instructions and the trace data into polynomials and then making various assertions about those polynomials. We refer to this process as arithmetization of the trace, and RISC Zero's arithmetization is based on Reed Solomon encoding.
Adding a parity bit to a binary string offers a form of error detection. Error correcting codes extend this line of thinking: when sending data that may get corrupted, we can allow the recipient to detect and correct errors by adding some error correcting bits. Reed-Solomon codes are an industry standard for error correction; they're used in many signal processing applications, including cell communication, QR codes, and STARKs.
In the context of RISC Zero's receipts, the relevance of Reed-Solomon codes is quite a bit more nuanced than the standard error correction use cases. The error amplification of Reed-Solomon encoding provides cryptographic soundness to RISC Zero's computational receipts. During the process of generating a receipt, any errors in the trace are amplified by the process of arithmetization. This error amplification means that even a single error in the execution trace can be easily identified.
Suggested Reading and Videos
- Slides, recording, and practice problems from RISC Zero Study Club
- 3blue1brown has two videos that offer a great introduction to error correcting codes: Part 1 and Part 2.
- Mary Wootters has a fantastic course on Algebraic Coding Theory. The YouTube and the course website are both great resources.
- The Reed-Solomon paper is quite clear and only a few pages long.
- The Proximity Gaps for Reed-Solomon Codes paper is central to the soundness of the RISC Zero proof system.
- See also Dan Carmon's talk at the IEEE Symposium on the Foundations of Computer Science