Struct FriVerifier 

pub struct FriVerifier<E, C, H, R, V>
where
    E: FieldElement,
    C: VerifierChannel<E, Hasher = H>,
    H: ElementHasher<BaseField = E::BaseField>,
    R: RandomCoin<BaseField = E::BaseField, Hasher = H>,
    V: VectorCommitment<H>,
{ /* private fields */ }

Implements the verifier component of the FRI protocol.

Given a small number of evaluations of some function f over domain D and a FRI proof, a FRI verifier determines whether f is a polynomial of some bounded degree d, such that d < |D| / 2.

The verifier is parametrized by the following types:

• B specifies the base field of the STARK protocol.
• E specifies the field in which the FRI protocol is executed. This can be the same as the base field B, but it can also be an extension of the base field in cases when the base field is too small to provide desired security level for the FRI protocol.
• C specifies the type used to simulate prover-verifier interaction. This type is used as an abstraction for a FriProof. Meaning, the verifier does not consume a FRI proof directly, but reads it via VerifierChannel interface.
• H specifies the Hash function used by the prover to commit to polynomial evaluations.

Proof verification is performed in two phases: commit phase and query phase.

Commit phase

During the commit phase, which is executed when the verifier is instantiated via new() function, the verifier receives a list of FRI layer commitments from the prover (via VerifierChannel). After each received commitment, the verifier draws a random value α from the entire field, and sends it to the prover. In the non-interactive version of the protocol, α values are derived pseudo-randomly from FRI layer commitments.

Query phase

During the query phase, which is executed via verify() function, the verifier sends a set of positions in the domain D to the prover, and the prover responds with polynomial evaluations at these positions (together with corresponding opening proofs) across all FRI layers. The verifier then checks that:

• The opening proofs are valid against the layer commitments the verifier received during the commit phase.
• The evaluations are consistent across FRI layers (i.e., the degree-respecting projection was applied correctly).
• The degree of the polynomial implied by evaluations at the last FRI layer (the remainder) is smaller than the degree resulting from reducing degree d by folding_factor at each FRI layer.

Implementations

impl<E, C, H, R, V> FriVerifier<E, C, H, R, V>

where E: FieldElement, C: VerifierChannel<E, Hasher = H, VectorCommitment = V>, H: ElementHasher<BaseField = E::BaseField>, R: RandomCoin<BaseField = E::BaseField, Hasher = H>, V: VectorCommitment<H>,

pub fn new( channel: &mut C, public_coin: &mut R, options: FriOptions, max_poly_degree: usize, ) -> Result<Self, VerifierError>

Returns a new instance of FRI verifier created from the specified parameters.

The max_poly_degree parameter specifies the highest polynomial degree accepted by the returned verifier. In combination with blowup_factor from the options parameter, max_poly_degree also defines the domain over which the tested polynomial is evaluated.

Creating a FRI verifier executes the commit phase of the FRI protocol from the verifier’s perspective. Specifically, the verifier reads FRI layer commitments from the channel, and for each commitment, updates the public_coin with this commitment and then draws a random value α from the coin.

The verifier stores layer commitments and corresponding α values in its internal state, and, thus, an instance of FRI verifier can be used to verify only a single proof.

Errors

Returns an error if:

• max_poly_degree is inconsistent with the number of FRI layers read from the channel and folding_factor specified in the options parameter.
• An error was encountered while drawing a random α value from the coin.

pub fn max_poly_degree(&self) -> usize

Returns maximum degree of a polynomial accepted by this verifier.

pub fn domain_size(&self) -> usize

Returns size of the domain over which a polynomial commitment checked by this verifier has been evaluated.

The domain size can be computed by rounding max_poly_degree to the next power of two and multiplying the result by the blowup_factor from the protocol options.

pub fn num_partitions(&self) -> usize

Returns number of partitions used during FRI proof generation.

For non-distributed proof generation, number of partitions is usually set to 1.

pub fn options(&self) -> &FriOptions

Returns protocol configuration options for this verifier.

pub fn verify( &self, channel: &mut C, evaluations: &[E], positions: &[usize], ) -> Result<(), VerifierError>

Executes the query phase of the FRI protocol.

Returns Ok(()) if values in the evaluations slice represent evaluations of a polynomial with degree <= max_poly_degree at x coordinates specified by the positions slice.

Thus, positions parameter represents the positions in the evaluation domain at which the verifier queries the prover at the first FRI layer. Similarly, the evaluations parameter specifies the evaluations of the polynomial at the first FRI layer returned by the prover for these positions.

Evaluations of layer polynomials for all subsequent FRI layers the verifier reads from the specified channel.

Errors

Returns an error if:

• The length of evaluations is not equal to the length of positions.
• An unsupported folding factor was specified by the options for this verifier.
• Decommitments to polynomial evaluations don’t match the commitment value at any of the FRI layers.
• The verifier detects an error in how the degree-respecting projection was applied at any of the FRI layers.
• The degree of the remainder at the last FRI layer is greater than the degree implied by max_poly_degree reduced by the folding factor at each FRI layer.