Proof System Sequence Diagram and Spec

When the RISC Zero zkVM executes, it produces a Receipt that serves as a proof of validity of a given Session. RISC Zero's receipts are built on the shoulders of several recent advances in the world of Zero-Knowledge Cryptography: zk-STARKs, PLONK, and DEEP-ALI.

In this document, we present a succinct introduction to the RISC Zero Proof system, including a sequence diagram and a step-by-step description of the RISC Zero Non-Interactive Argument of Knowledge. We encourage readers to follow along with STARK by Hand for a more concrete description of the protocol.

To invite collaboration and open source development, this is an early-release of documentation-in-progress. The implementation in code can be seen here. If you have questions/feedback or if you find errors, please let us know on Twitter or Discord.

sequenceDiagram Note over Prover,Verifier: Phase 1: Committing the Execution Trace Note over Prover: Prover runs iNTTs to construct <br/>a Trace Polynomial for each Trace Column, then runs NTTs <br/>to evaluate each Trace Polynomial over an Evaluation Domain,<br/>and commits those evaluations to Merkle Trees. Note right of Prover: Prover sends Merkle Roots <br/>for Trace Data Polynomials <br/>and Trace Control Polynomials Prover->>Verifier: Note left of Verifier: Verifier returns PLONK <br/>mixing parameters Verifier->>Prover: Note right of Prover: Prover sends Merkle Roots for <br/>PLONK Polynomials Prover->>Verifier: Note over Prover,Verifier: Phase 2: Validating the Trace Note left of Verifier: Verifier returns constraint <br/>mixing parameter, alpha Verifier->>Prover: Note over Prover: Prover uses alpha to mix Constraint Polynomials <br/>into a Mixed Constraint Polynomial, <br/>then divides by the public Zeroes Polynomial <br/>to construct the High Degree Validity Polynomial,<br/> splits it into a few Low Degree Validity Polynomials, and finally <br/>commits evaluations of the Low Degree Validity Polynomial a to Merkle Tree. Note right of Prover: Prover sends Merkle Root <br/>for Low Degree Validity Polynomials Prover->>Verifier: Note over Prover,Verifier: Phase 3: The DEEP Technique Note left of Verifier: Verifier chooses a DEEP test point Verifier->>Prover: Note over Prover: To support DEEP test, Prover computes "necessary evaluations" <br/> of Trace Polynomials and Low Degree Validity Polynomials. Note over Prover: Prover also computes the coefficients of the DEEP polynomials Note right of Prover: Prover sends "necessary evaluations" <br/>and coefficients of DEEP polynomials Prover->>Verifier: Note left of Verifier: Verifier returns a DEEP mixing parameter Verifier->>Prover: Note over Prover: Prover uses DEEP Mixing Parameter to mix <br/> the DEEP polynomials, forming the FRI polynomial. Note right of Prover: Prover sends Merkle Root <br/> for the FRI polynomial Prover->>Verifier: Note over Prover,Verifier: Phase 4: The FRI Protocol. <br/>We omit the details of the <br/>FRI protocol for brevity.

The RISC Zero Proof System: A Step-By-Step Description

Phase 1: Committing the Execution Trace

• The Prover runs a computation in order to generate an Execution Trace.
  • The trace is organized into columns, and the columns are categorized as control columns, data columns, and PLONK columns.
    • The control columns handle system initialization and shutdown, the initial program code to load into memory before execution, and other control signals that don't depend on the program execution.
    • The data columns contain the input and the computation data, both of which are private. These columns are committed in two orderings:
      • in order of program execution, and
      • re-ordered by register first and clock cycle second. The re-ordered columns allow for efficient validation of RISC-V memory operations.
    • The PLONK columns are used to show the validity that the re-ordered data columns are a valid permutation of the original data, as per the PLONK permutation argument.
  • After computing the data columns and PLONK columns, the Prover adds some random noise to the end of those columns in order to ensure that the protocol is zero-knowledge.
• The Prover encodes the trace as follows:
  • The Prover converts each column into a polynomial using an iNTT. We'll refer to these as Trace Polynomials, denoted $P_i(x)$.
  • The Prover evaluates the data polynomials and the control polynomials over an expanded domain and commits the evaluations into two separate Merkle Trees.
  • Using these Merkle roots as an entropy-source, we use Fiat-Shamir to choose PLONK mixing parameters, using a SHA-2 CRNG.
  • Then, the Prover uses the PLONK mixing parameters to generate the PLONK columns, interpolates them to form the PLONK polynomials, evaluates those polynomials over a larger domain, and commits those evaluations to a Merkle tree (see the PLONK paper for details).
  • The Prover sends the Merkle root of each tree to the Verifier.
  • Using these three Merkle roots as an entropy-source, we use Fiat-Shamir to choose a constraint mixing parameter $\alpha$, using a SHA-2 CRNG.

Phase 2: Validating the Trace: the Core of the STARK Proof

• The Prover uses the constraint mixing parameter, the Trace Polynomials, and the Rule Checking Polynomials to construct a few Low Degree Validity Polynomials. The details are as follows:

  • By writing $k$ publicly known Rule Checking Polynomials, $R_0, R_1, ..., R_{k-1}$, in terms of the private Trace Polynomials, the Prover generates $k$ Constraint Polynomials, $C_j(x)$.

    • The key point about these polynomials is that for each of the $k$ rules and each input $z$ that's associated with the trace, $C_j(z)$ will return 0 if the trace "passes the test," so to speak.

  • Using the constraint mixing parameter $\alpha$, the Prover combines the Constraint Polynomials, $C_j$ into a single Mixed Constraint Polynomial, $C$, by computing $C(x)=\alpha^0C_0(x)+\ldots+\alpha^{k-1}C_{k-1}(x).$

    • Note that if each $C_j$ returns 0 at some point $z$, then $C$ will also return 0 at $z$.

  • Using a publicly known Zeros Polynomial, the Prover computes the High Degree Validity Polynomial, $V(x)=\frac{C(x)}{Z(x)}$.

    • The Zeros Polynomial $Z(x)$ is a divisor of any honest construction of $C(x)$. In other words, an honest prover will construct $V(x)$ to be a polynomial of lower degree than $C(x)$. We call $V$ "high degree" relative to the Trace Polynomials, $P_i$.

  • The Prover splits the High Degree Validity Polynomial into 4 Low Degree Validity Polynomials, $v_0(x), v_1(x), ..., v_3$.

  • The Prover evaluates the Low Degree Validity Polynomials, encodes them in a Merkle Tree, and sends the Merkle root to the Verifier.

  • We use Fiat-Shamir to choose the DEEP Test Point, $z$.

Phase 3: The DEEP Technique

• The Verifier would like to check the asserted relation between $C$, $Z$, and $V$ at the DEEP Test Point, $z$. Namely, the Verifier would like to confirm that $V(z)Z(z)=C(z)$.
  • The Prover sends the evaluations of each $v_i$ at $z$, which allows the Verifier to compute $V(z)$.
  • Computing $C(z)$ is slightly more complicated. Because rule checks can check relationships across multiple columns and multiple clock cycles, evaluating $C(z)$ requires numerous evaluations of the form $P_i(\omega^nz)$ for varying columns $i$ and cycles $n$. The Prover sends these necessary evaluations of each $P_i$ to allow the Verifier to evaluate $C(z)$. We refer to the necessary evaluations $P_i(\omega^nz)$ as the taps of $P_i$ at $z$.
  • The Verifier can now check $V(z)Z(z)=C(z)$.
  • Although these asserted evaluations have no associated Merkle branches, the DEEP technique offers an alternative to the usual Merkle proof.
• The Prover constructs the DEEP polynomials using the taps:
  • Denoting the taps of $P_i$ at $z$ as $(x_1,P_i(x_1)),\ldots,(x_n,P_i(x_n))$, the Prover constructs the DEEP polynomial $P'_i(x)=\frac{P_i(x)-\overline{P_i}(x)}{(x-x_1)\ldots(x-x_n)}$ where $\overline{P_i}(x)$ is the polynomial formed by interpolating the taps of $P_i$. The Prover computes $P'_i$, runs an iNTT on the result, and sends the coefficients of $P'_i$ to the Verifier. Using this technique, the Prover constructs and sends a DEEP polynomial for each $P_i$ and each $v_i$.
• At this point, the claim of trace validity has been reduced to the claim that each of the DEEP polynomials is actually a low-degree polynomial. To conclude the proof, the Prover mixes the DEEP polynomials into the FRI Polynomial using a DEEP mixing parameter and use the FRI protocol to show that the FRI Polynomial is a low-degree polynomial.

Phase 4: The FRI Protocol

• We omit the details of the FRI Protocol for brevity.

Thanks for reading! If you have questions or feedback, we'd love to hear from you on Discord or Twitter.