Skip to main content

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 Pi(x)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 kk publicly known Rule Checking Polynomials, R0,R1,...,Rk1R_0, R_1, ..., R_{k-1}, in terms of the private Trace Polynomials, the Prover generates kk Constraint Polynomials, Cj(x)C_j(x).

      • The key point about these polynomials is that for each of the kk rules and each input zz that's associated with the trace, Cj(z)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, CjC_j into a single Mixed Constraint Polynomial, CC, by computing C(x)=α0C0(x)++αk1Ck1(x).C(x)=\alpha^0C_0(x)+\ldots+\alpha^{k-1}C_{k-1}(x).

      • Note that if each CjC_j returns 0 at some point zz, then CC will also return 0 at zz.
    • Using a publicly known Zeros Polynomial, the Prover computes the High Degree Validity Polynomial, V(x)=C(x)Z(x)V(x)=\frac{C(x)}{Z(x)}.

      • The Zeros Polynomial Z(x)Z(x) is a divisor of any honest construction of C(x)C(x). In other words, an honest prover will construct V(x)V(x) to be a polynomial of lower degree than C(x)C(x). We call VV "high degree" relative to the Trace Polynomials, PiP_i.
    • The Prover splits the High Degree Validity Polynomial into 4 Low Degree Validity Polynomials, v0(x),v1(x),...,v3v_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, zz.

Phase 3: The DEEP Technique

  • The Verifier would like to check the asserted relation between CC, ZZ, and VV at the DEEP Test Point, zz. Namely, the Verifier would like to confirm that V(z)Z(z)=C(z)V(z)Z(z)=C(z).
    • The Prover sends the evaluations of each viv_i at zz, which allows the Verifier to compute V(z)V(z).
    • Computing C(z)C(z) is slightly more complicated. Because rule checks can check relationships across multiple columns and multiple clock cycles, evaluating C(z)C(z) requires numerous evaluations of the form Pi(ωnz)P_i(\omega^nz) for varying columns ii and cycles nn. The Prover sends these necessary evaluations of each PiP_i to allow the Verifier to evaluate C(z)C(z). We refer to the necessary evaluations Pi(ωnz)P_i(\omega^nz) as the taps of PiP_i at zz.
    • The Verifier can now check V(z)Z(z)=C(z)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 PiP_i at zz as (x1,Pi(x1)),,(xn,Pi(xn))(x_1,P_i(x_1)),\ldots,(x_n,P_i(x_n)), the Prover constructs the DEEP polynomial Pi(x)=Pi(x)Pi(x)(xx1)(xxn)P'_i(x)=\frac{P_i(x)-\overline{P_i}(x)}{(x-x_1)\ldots(x-x_n)} where Pi(x)\overline{P_i}(x) is the polynomial formed by interpolating the taps of PiP_i. The Prover computes PiP'_i, runs an iNTT on the result, and sends the coefficients of PiP'_i to the Verifier. Using this technique, the Prover constructs and sends a DEEP polynomial for each PiP_i and each viv_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

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