Skip to main content

About Reed Solomon Codes

Reed Solomon codes (RS codes) are a family of error correcting codes based on polynomials over finite fields.

Documentation​

Implementation and documentation for Reed-Solomon encoding is in the risc0-zkp-core Rust crate.

Basic Function​

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.

Background​

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​