Proving tools and techniques
In this document, we provide a brief outline of the proving tool called PILSTARK and the two proving techniques namely FRI and STARK.
PILSTARK¶
PILSTARK proof/verification consists of three components; Setup, Prover, and Verifier.

Setup refers to the preprocessing of all data required by the Prover and Verifier. It takes the PIL description of the State Machine being proved and verified as well as the STARK configuration JSONfile as inputs.

Prover requires some input values in the form of a JSONfile together with the evaluations of the constant polynomials, the
constTree
and thestarkInfo
from the preprocessing. It outputs the STARK proof and public values calledpublics
. 
The Verifier receives the STARK proof and public values from the Prover, as well as the
starkInfo
andconstRoot
from the Setup phase. The Verifier’s output is either anAccept
if the proof is accepted, or aReject
if the proof is rejected.
The full details of the PILSTARK process are given here, while the following diagram summarizes entire PILSTARK process.
Role of FRI¶
The zkProver uses an extended version of the STARK protocol, dubbed eSTARK, which is especially designed to prove PIL specifications. It is so called because it is not confined to proving polynomials equalities, but extends to arguments such as lookups, permutations or even copyconstraints (called connection arguments).
The eSTARK protocol is composed of two main phases; the lowdegree reduction phase and the FRI phase.
Info
What is FRI
FRI refers to Fast ReedSolomon Interactive Oracle Proof of Proximity. The FRI protocol consists of two phases: a commit phase and query phase. You can read more about the protocol in this document by StarkWare Team.

Lowdegree reduction phase
During this phase, we receive a FRI polynomial, which codifies the validity of the execution trace values according to the PIL code into the fact that it has a low degree. This polynomial, along with numerous other polynomials required to provide consistency checks, is committed to the Verifier.

FRI phase
Following the acquisition of the FRI polynomial, the Prover and Verifier communicate using the standard FRI Protocol, with the goal of precisely demonstrating and verifying that the committed polynomial has a low degree.
More specifically, it demonstrates that the committed values of the polynomials raise a function that is suffuciently near to a low degree polynomial.
eSTARK protocol¶
On a high level, the description of the eSTARK protocol can be broken down into several rounds. Here’s what each rounds aims to achieve:

\(Round\ 1\): Given the trace column polynomials after interpolating the execution trace, the Prover commits to these polynomials.

\(Round\ 2\): For each lookup argument, the Prover commits to the socalled \(h\)polynomials of the modified Plookup version described in PlonKup.

\(Round\ 3\): The Prover commits to the grandproduct polynomials for each of the arguments appearing in the PIL code, together with some intermediate polynomials used to reduce the degree of the grand products. This is due to the fact that PILSTARK imposes a degree bound when committing to a polynomial.
See Plookup or Plonk for the specification of the grandproducts of each of the different arguments allowed in PIL.

\(Round\ 4\): The Prover commits to two polynomials \(Q_1\) and \(Q_2\) arising from the splitting of the quotient polynomial \(Q\).

\(Round\ 5\): The Prover provides the Verifier with all the necessary evaluations of the polynomials so that corresponding checks can be executed.

\(Round\ 6\): The Prover receives two random values from the Verifier, which are used to construct the FRI polynomial. Then the Prover and the Verifier get engaged (nonInteractively) in a FRI Protocol, which ends with the Prover sending the corresponding FRI proof to the Verifier.
After the proof is generated, it is sent to the Verifier instance for the verification procedure to begin. The final output is either an accept
or a reject
, indicating whether the proof was accepted or rejected.