winterfell-verification.md

// 1 ----- trace commitment -------------------------------------------------------------------
// Read the commitments to evaluations of the trace polynomials over the LDE domain sent by the
// prover. The commitments are used to update the public coin, and draw sets of random elements
// from the coin (in the interactive version of the protocol the verifier sends these random
// elements to the prover after each commitment is made). When there are multiple trace
// commitments (i.e., the trace consists of more than one segment), each previous commitment is
// used to draw random elements needed to construct the next trace segment. The last trace
// commitment is used to draw a set of random coefficients which the prover uses to compute
// constraint composition polynomial.

// 2 ----- constraint commitment --------------------------------------------------------------
// read the commitment to evaluations of the constraint composition polynomial over the LDE
// domain sent by the prover, use it to update the public coin, and draw an out-of-domain point
// z from the coin; in the interactive version of the protocol, the verifier sends this point z
// to the prover, and the prover evaluates trace and constraint composition polynomials at z,
// and sends the results back to the verifier.

// 3 ----- OOD consistency check --------------------------------------------------------------
// make sure that evaluations obtained by evaluating constraints over the out-of-domain frame
// are consistent with the evaluations of composition polynomial columns sent by the prover

// read the out-of-domain trace frames (the main trace frame and auxiliary trace frame, if
// provided) sent by the prover and evaluate constraints over them; also, reseed the public
// coin with the OOD frames received from the prover.

// read evaluations of composition polynomial columns sent by the prover, and reduce them into
// a single value by computing sum(z^i * value_i), where value_i is the evaluation of the ith
// column polynomial at z^m, where m is the total number of column polynomials; also, reseed
// the public coin with the OOD constraint evaluations received from the prover.

// 4 ----- FRI commitments --------------------------------------------------------------------
// draw coefficients for computing DEEP composition polynomial from the public coin; in the
// interactive version of the protocol, the verifier sends these coefficients to the prover
// and the prover uses them to compute the DEEP composition polynomial. the prover, then
// applies FRI protocol to the evaluations of the DEEP composition polynomial.


// 5 ----- trace and constraint queries -------------------------------------------------------
// read proof-of-work nonce sent by the prover and update the public coin with it

// draw pseudo-random query positions for the LDE domain from the public coin; in the
// interactive version of the protocol, the verifier sends these query positions to the prover,
// and the prover responds with decommitments against these positions for trace and constraint
// composition polynomial evaluations.

// read evaluations of trace and constraint composition polynomials at the queried positions;
// this also checks that the read values are valid against trace and constraint commitments

// 6 ----- DEEP composition -------------------------------------------------------------------
// compute evaluations of the DEEP composition polynomial at the queried positions


// 7 ----- Verify low-degree proof -------------------------------------------------------------
// make sure that evaluations of the DEEP composition polynomial we computed in the previous
// step are in fact evaluations of a polynomial of degree equal to trace polynomial degree