in prover/src/lib.rs [198:408]
fn generate_proof<E, H>(&self, trace: Self::Trace) -> Result<StarkProof, ProverError>
where
E: FieldElement<BaseField = Self::BaseField>,
H: ElementHasher<BaseField = Self::BaseField>,
{
// 0 ----- instantiate AIR and prover channel ---------------------------------------------
// serialize public inputs; these will be included in the seed for the public coin
let pub_inputs = self.get_pub_inputs(&trace);
let mut pub_inputs_bytes = Vec::new();
pub_inputs.write_into(&mut pub_inputs_bytes);
// create an instance of AIR for the provided parameters. this takes a generic description
// of the computation (provided via AIR type), and creates a description of a specific
// execution of the computation for the provided public inputs.
let air = Self::Air::new(trace.get_info(), pub_inputs, self.options().clone());
// make sure the specified trace is valid against the AIR. This checks validity of both,
// assertions and state transitions. we do this in debug mode only because this is a very
// expensive operation.
#[cfg(debug_assertions)]
trace.validate(&air);
// create a channel which is used to simulate interaction between the prover and the
// verifier; the channel will be used to commit to values and to draw randomness that
// should come from the verifier.
let mut channel = ProverChannel::<Self::Air, E, H>::new(&air, pub_inputs_bytes);
// 1 ----- Commit to the execution trace --------------------------------------------------
// build computation domain; this is used later for polynomial evaluations
#[cfg(feature = "std")]
let now = Instant::now();
let domain = StarkDomain::new(&air);
#[cfg(feature = "std")]
debug!(
"Built domain of 2^{} elements in {} ms",
log2(domain.lde_domain_size()),
now.elapsed().as_millis()
);
// extend the execution trace and build a Merkle tree from the extended trace
let (trace_commitment, trace_polys) =
self.build_trace_commitment::<H>(trace.into_matrix(), &domain);
// commit to the extended trace by writing the root of the Merkle tree into the channel
channel.commit_trace(trace_commitment.root());
// 2 ----- evaluate constraints -----------------------------------------------------------
// evaluate constraints specified by the AIR over the constraint evaluation domain, and
// compute random linear combinations of these evaluations using coefficients drawn from
// the channel; this step evaluates only constraint numerators, thus, only constraints with
// identical denominators are merged together. the results are saved into a constraint
// evaluation table where each column contains merged evaluations of constraints with
// identical denominators.
#[cfg(feature = "std")]
let now = Instant::now();
let constraint_coeffs = channel.get_constraint_composition_coeffs();
let evaluator = ConstraintEvaluator::new(&air, constraint_coeffs);
let constraint_evaluations = evaluator.evaluate(&trace_commitment, &domain);
#[cfg(feature = "std")]
debug!(
"Evaluated constraints over domain of 2^{} elements in {} ms",
log2(constraint_evaluations.num_rows()),
now.elapsed().as_millis()
);
// 3 ----- commit to constraint evaluations -----------------------------------------------
// first, build constraint composition polynomial from the constraint evaluation table:
// - divide all constraint evaluation columns by their respective divisors
// - combine them into a single column of evaluations,
// - interpolate the column into a polynomial in coefficient form
// - "break" the polynomial into a set of column polynomials each of degree equal to
// trace_length - 1
#[cfg(feature = "std")]
let now = Instant::now();
let composition_poly = constraint_evaluations.into_poly()?;
#[cfg(feature = "std")]
debug!(
"Converted constraint evaluations into {} composition polynomial columns of degree {} in {} ms",
composition_poly.num_columns(),
composition_poly.column_degree(),
now.elapsed().as_millis()
);
// then, build a commitment to the evaluations of the composition polynomial columns
let constraint_commitment =
self.build_constraint_commitment::<E, H>(&composition_poly, &domain);
// then, commit to the evaluations of constraints by writing the root of the constraint
// Merkle tree into the channel
channel.commit_constraints(constraint_commitment.root());
// 4 ----- build DEEP composition polynomial ----------------------------------------------
#[cfg(feature = "std")]
let now = Instant::now();
// draw an out-of-domain point z. Depending on the type of E, the point is drawn either
// from the base field or from an extension field defined by E.
//
// The purpose of sampling from the extension field here (instead of the base field) is to
// increase security. Soundness is limited by the size of the field that the random point
// is drawn from, and we can potentially save on performance by only drawing this point
// from an extension field, rather than increasing the size of the field overall.
let z = channel.get_ood_point();
// evaluate trace and constraint polynomials at the OOD point z, and send the results to
// the verifier. the trace polynomials are actually evaluated over two points: z and z * g,
// where g is the generator of the trace domain.
let ood_frame = trace_polys.get_ood_frame(z);
channel.send_ood_evaluation_frame(&ood_frame);
let ood_evaluations = composition_poly.evaluate_at(z);
channel.send_ood_constraint_evaluations(&ood_evaluations);
// draw random coefficients to use during DEEP polynomial composition, and use them to
// initialize the DEEP composition polynomial
let deep_coefficients = channel.get_deep_composition_coeffs();
let mut deep_composition_poly = DeepCompositionPoly::new(&air, z, deep_coefficients);
// combine all trace polynomials together and merge them into the DEEP composition
// polynomial
deep_composition_poly.add_trace_polys(trace_polys, ood_frame);
// merge columns of constraint composition polynomial into the DEEP composition polynomial;
deep_composition_poly.add_composition_poly(composition_poly, ood_evaluations);
// raise the degree of the DEEP composition polynomial by one to make sure it is equal to
// trace_length - 1
deep_composition_poly.adjust_degree();
#[cfg(feature = "std")]
debug!(
"Built DEEP composition polynomial of degree {} in {} ms",
deep_composition_poly.degree(),
now.elapsed().as_millis()
);
// make sure the degree of the DEEP composition polynomial is equal to trace polynomial
// degree
assert_eq!(domain.trace_length() - 1, deep_composition_poly.degree());
// 5 ----- evaluate DEEP composition polynomial over LDE domain ---------------------------
#[cfg(feature = "std")]
let now = Instant::now();
let deep_evaluations = deep_composition_poly.evaluate(&domain);
// we check the following condition in debug mode only because infer_degree is an expensive
// operation
debug_assert_eq!(
domain.trace_length() - 1,
infer_degree(&deep_evaluations, domain.offset())
);
#[cfg(feature = "std")]
debug!(
"Evaluated DEEP composition polynomial over LDE domain (2^{} elements) in {} ms",
log2(domain.lde_domain_size()),
now.elapsed().as_millis()
);
// 6 ----- compute FRI layers for the composition polynomial ------------------------------
#[cfg(feature = "std")]
let now = Instant::now();
let mut fri_prover = FriProver::new(air.options().to_fri_options());
fri_prover.build_layers(&mut channel, deep_evaluations);
#[cfg(feature = "std")]
debug!(
"Computed {} FRI layers from composition polynomial evaluations in {} ms",
fri_prover.num_layers(),
now.elapsed().as_millis()
);
// 7 ----- determine query positions ------------------------------------------------------
#[cfg(feature = "std")]
let now = Instant::now();
// apply proof-of-work to the query seed
channel.grind_query_seed();
// generate pseudo-random query positions
let query_positions = channel.get_query_positions();
#[cfg(feature = "std")]
debug!(
"Determined {} query positions in {} ms",
query_positions.len(),
now.elapsed().as_millis()
);
// 8 ----- build proof object -------------------------------------------------------------
#[cfg(feature = "std")]
let now = Instant::now();
// generate FRI proof
let fri_proof = fri_prover.build_proof(&query_positions);
// query the execution trace at the selected position; for each query, we need the
// state of the trace at that position + Merkle authentication path
let trace_queries = trace_commitment.query(&query_positions);
// query the constraint commitment at the selected positions; for each query, we need just
// a Merkle authentication path. this is because constraint evaluations for each step are
// merged into a single value and Merkle authentication paths contain these values already
let constraint_queries = constraint_commitment.query(&query_positions);
// build the proof object
let proof = channel.build_proof(trace_queries, constraint_queries, fri_proof);
#[cfg(feature = "std")]
debug!("Built proof object in {} ms", now.elapsed().as_millis());
Ok(proof)
}