Trait winter_prover::Prover

pub trait Prover {
    type BaseField: StarkField + ExtensibleField<2> + ExtensibleField<3>;
    type Air: Air<BaseField = Self::BaseField>;
    type Trace: Trace<BaseField = Self::BaseField>;
    type HashFn: ElementHasher<BaseField = Self::BaseField>;
    type RandomCoin: RandomCoin<BaseField = Self::BaseField, Hasher = Self::HashFn>;
    type TraceLde<E>: TraceLde<E, HashFn = Self::HashFn>
       where E: FieldElement<BaseField = Self::BaseField>;
    type ConstraintEvaluator<'a, E>: ConstraintEvaluator<E, Air = Self::Air>
       where E: FieldElement<BaseField = Self::BaseField>;

    // Required methods
    fn get_pub_inputs(
        &self,
        trace: &Self::Trace
    ) -> <<Self as Prover>::Air as Air>::PublicInputs;
    fn options(&self) -> &ProofOptions;
    fn new_trace_lde<E>(
        &self,
        trace_info: &TraceInfo,
        main_trace: &ColMatrix<Self::BaseField>,
        domain: &StarkDomain<Self::BaseField>
    ) -> (Self::TraceLde<E>, TracePolyTable<E>)
       where E: FieldElement<BaseField = Self::BaseField>;
    fn new_evaluator<'a, E>(
        &self,
        air: &'a Self::Air,
        aux_rand_elements: AuxTraceRandElements<E>,
        composition_coefficients: ConstraintCompositionCoefficients<E>
    ) -> Self::ConstraintEvaluator<'a, E>
       where E: FieldElement<BaseField = Self::BaseField>;

    // Provided methods
    fn prove(&self, trace: Self::Trace) -> Result<StarkProof, ProverError> { ... }
    fn build_constraint_commitment<E>(
        &self,
        composition_poly_trace: CompositionPolyTrace<E>,
        num_constraint_composition_columns: usize,
        domain: &StarkDomain<Self::BaseField>
    ) -> (ConstraintCommitment<E, Self::HashFn>, CompositionPoly<E>)
       where E: FieldElement<BaseField = Self::BaseField> { ... }
}

Defines a STARK prover for a computation.

A STARK prover can be used to generate STARK proofs. The prover contains definitions of a computation’s AIR (specified via Air associated type), execution trace (specified via Trace associated type) and hash function to be used (specified via HashFn associated type), and exposes prove() method which can be used to build STARK proofs for provided execution traces.

Thus, once a prover is defined and instantiated, generating a STARK proof consists of two steps:

1. Build an execution trace for a specific instance of the computation.
2. Invoke Prover::prove() method generate a proof using the trace from the previous step as a witness.

The generated proof is built using protocol parameters defined by the ProofOptions struct return from Prover::options method.

To further customize the prover, implementers can specify custom implementations of the RandomCoin, TraceLde, and ConstraintEvaluator associated types (default implementations of these types are provided with the prover). For example, providing custom implementations of TraceLde and/or ConstraintEvaluator can be beneficial when some steps of proof generation can be delegated to non-CPU hardware (e.g., GPUs).

Required Associated Types

type BaseField: StarkField + ExtensibleField<2> + ExtensibleField<3>

Base field for the computation described by this prover.

type Air: Air<BaseField = Self::BaseField>

Algebraic intermediate representation (AIR) for the computation described by this prover.

type Trace: Trace<BaseField = Self::BaseField>

Execution trace of the computation described by this prover.

type HashFn: ElementHasher<BaseField = Self::BaseField>

Hash function to be used.

type RandomCoin: RandomCoin<BaseField = Self::BaseField, Hasher = Self::HashFn>

PRNG to be used for generating random field elements.

type TraceLde<E>: TraceLde<E, HashFn = Self::HashFn> where E: FieldElement<BaseField = Self::BaseField>

Trace low-degree extension for building the LDEs of trace segments and their commitments.

type ConstraintEvaluator<'a, E>: ConstraintEvaluator<E, Air = Self::Air> where E: FieldElement<BaseField = Self::BaseField>

Constraints evaluator used to evaluate AIR constraints over the extended execution trace.

Required Methods

fn get_pub_inputs( &self, trace: &Self::Trace ) -> <<Self as Prover>::Air as Air>::PublicInputs

Returns a set of public inputs for an instance of the computation defined by the provided trace.

Public inputs need to be shared with the verifier in order for them to verify a proof.

fn options(&self) -> &ProofOptions

Returns ProofOptions which this prover uses to generate STARK proofs.

Proof options defines basic protocol parameters such as: number of queries, blowup factor, grinding factor etc. These properties directly inform such metrics as proof generation time, proof size, and proof security level.

fn new_trace_lde<E>( &self, trace_info: &TraceInfo, main_trace: &ColMatrix<Self::BaseField>, domain: &StarkDomain<Self::BaseField> ) -> (Self::TraceLde<E>, TracePolyTable<E>)

where E: FieldElement<BaseField = Self::BaseField>,

Takes the main trace segment columns as input, interpolates them into polynomials in coefficient form, and evaluates the polynomials over the LDE domain.

Returns a tuple containing a TracePolyTable with the trace polynomials for the main trace and a new TraceLde instance from which the LDE and trace commitments can be obtained.

fn new_evaluator<'a, E>( &self, air: &'a Self::Air, aux_rand_elements: AuxTraceRandElements<E>, composition_coefficients: ConstraintCompositionCoefficients<E> ) -> Self::ConstraintEvaluator<'a, E>

where E: FieldElement<BaseField = Self::BaseField>,

Returns a new constraint evaluator which can be used to evaluate transition and boundary constraints over the extended execution trace.

Provided Methods

fn prove(&self, trace: Self::Trace) -> Result<StarkProof, ProverError>

Returns a STARK proof attesting to a correct execution of a computation defined by the provided trace.

The returned StarkProof attests that the specified trace is a valid execution trace of the computation described by Self::Air and generated using some set of secret and public inputs. Public inputs must match the value returned from Self::get_pub_inputs() for the provided trace.

fn build_constraint_commitment<E>( &self, composition_poly_trace: CompositionPolyTrace<E>, num_constraint_composition_columns: usize, domain: &StarkDomain<Self::BaseField> ) -> (ConstraintCommitment<E, Self::HashFn>, CompositionPoly<E>)

where E: FieldElement<BaseField = Self::BaseField>,

Extends constraint composition polynomial over the LDE domain and builds a commitment to its evaluations.

The extension is done by first interpolating the evaluations of the polynomial so that we get the composition polynomial in coefficient form; then breaking the polynomial into columns each of size equal to trace length, and finally evaluating each composition polynomial column over the LDE domain.

The commitment is computed by hashing each row in the evaluation matrix, and then building a Merkle tree from the resulting hashes.

Object Safety

This trait is not object safe.

Implementors