Struct FriProver 

pub struct FriProver<E, C, H, V>
where
    E: FieldElement,
    C: ProverChannel<E, Hasher = H>,
    H: ElementHasher<BaseField = E::BaseField>,
    V: VectorCommitment<H>,
{ /* private fields */ }

Implements the prover component of the FRI protocol.

Given evaluations of a function f over domain D (evaluations), a FRI prover generates a proof that f is a polynomial of some bounded degree d, such that d < |D| / blowup_factor. The proof is succinct: it exponentially smaller than evaluations and the verifier can verify it exponentially faster than it would have taken them to read all evaluations.

The prover is parametrized with the following types:

• E specifies the field in which the FRI protocol is executed.
• C specifies the type used to simulate prover-verifier interaction.
• H specifies the hash function used to build for each layer the vector of values committed to using the specified vector commitment scheme. The same hash function must be used in the prover channel to generate pseudo random values.
• V specifies the vector commitment scheme used in order to commit to each layer.

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

Commit phase

During the commit phase, which is executed via build_layers() function, the prover repeatedly applies a degree-respecting projection (DRP) to evaluations (see folding). With every application of the DRP, the degree of the function f (and size of the domain over which it is evaluated) is reduced by the folding_factor until the remaining evaluations correspond to a polynomial, called remainder polynomial, with a number of coefficients less than or equal to remainder_max_degree_plus_1.

At each layer of reduction, the prover commits to the current set of evaluations. This is done by building a vector commitment to hashed evaluations and sending the commitment string to the verifier (via ProverChannel). The vector commitment is build in such a way that all evaluations needed to compute a single value in the next FRI layer are grouped into the same leaf (the number of evaluations needed to compute a single element in the next FRI layer is equal to the folding_factor). This allows us to decommit all these values using a single individual opening proof.

After committing to the set of evaluations at the current layer, the prover draws a random field element α from the channel, and uses it to build the next FRI layer. In the interactive version of the protocol, the verifier draws α uniformly at random from the entire field and sends it to the prover. In the non-interactive version, α is pseudo-randomly generated based on the values the prover has written into the channel up to that point.

The prover keeps all FRI layers (consisting of evaluations and corresponding vector commitments) in its internal state.

Query phase

In the query phase, which is executed via build_proof() function, the prover receives a set of positions in the domain D from the verifier. The prover then decommits evaluations corresponding to these positions across all FRI layers (except for the remainder layer) and builds a FriProof from these evaluations. The remainder polynomial is included in the proof in its entirety.

In the interactive version of the protocol, the verifier draws the position uniformly at random from domain D. In the non-interactive version, the positions are pseudo-randomly selected based on the values the prover has written into the channel up to that point.

Since the positions are drawn from domain D, they apply directly only to the first FRI layer. To map these positions to the positions in all subsequent layers, the prover uses fold_positions procedure.

After the proof is generated, the prover deletes all internally stored FRI layers.

Calling build_layers() when the internal state is dirty, or calling build_proof() on a clean state will result in a panic.

Implementations

impl<E, C, H, V> FriProver<E, C, H, V>

where E: FieldElement, C: ProverChannel<E, Hasher = H>, H: ElementHasher<BaseField = E::BaseField>, V: VectorCommitment<H>,

pub fn new(options: FriOptions) -> Self

Returns a new FRI prover instantiated with the provided options.

pub fn folding_factor(&self) -> usize

Returns folding factor for this prover.

pub fn domain_offset(&self) -> E::BaseField

Returns offset of the domain over which FRI protocol is executed by this prover.

pub fn num_layers(&self) -> usize

Returns number of FRI layers computed during the last execution of the build_layers() method.

pub fn reset(&mut self)

Clears a vector of internally stored layers.

pub fn build_layers(&mut self, channel: &mut C, evaluations: Vec<E>)

Executes the commit phase of the FRI protocol.

During this phase we repeatedly apply a degree-respecting projection (DRP) to evaluations which contain evaluations of some function f over domain D. With every application of the DRP the degree of the function (and size of the domain) is reduced by folding_factor until the remaining evaluations can be represented by a remainder polynomial with at most remainder_max_degree_plus_1 number of coefficients. At each layer of reduction the current evaluations are committed to using a vector commitment scheme, and the commitment string of this vector commitment is written into the channel. After this the prover draws a random field element α from the channel, and uses it in the next application of the DRP.

Panics

Panics if the prover state is dirty (the vector of layers is not empty).

pub fn build_proof(&mut self, positions: &[usize]) -> FriProof

Executes query phase of FRI protocol.

For each of the provided positions, corresponding evaluations from each of the layers (excluding the remainder layer) are recorded into the proof together with a batch opening proof against the sent vector commitment. For the remainder, we send the whole remainder polynomial resulting from interpolating the remainder layer evaluations. The coefficients of the remainder polynomial are sent in reverse order so as to make evaluating it on the verifier’s end, using Horner’s evaluation method, easier.

Panics

Panics is the prover state is clean (no FRI layers have been build yet).