winter_fri/

lib.rs

// Copyright (c) Facebook, Inc. and its affiliates.
//
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree.

//! This crate contains an implementation of the FRI protocol used by the Winterfell STARK prover
//! and verifier.
//!
//! FRI stands for Fast Reed-Solomon Interactive Oracle Proof of Proximity, and is used in the
//! STARK protocol for low-degree testing. Specifically, given a commitment to a set of evaluations
//! of some function over domain *D*, the verifier can be convinced that the function is a
//! polynomial of degree at most *d*, by making a small number of queries to the commitment.
//!
//! # Proof generation
//! FRI proofs are generated by a [FriProver] in two steps:
//!
//! 1. First, the commit phase of the protocol is executed via
//!    [build_layers()](prover::FriProver::build_layers()) function. During this phase, the degree
//!    of the polynomial is repeatedly reduced by applying a degree-respecting projection, until the
//!    size of the domain over which the polynomial is evaluated falls under `max_remainder_size`
//!    parameter. While performing the reduction, the prover writes a set of layer commitments into
//!    the [ProverChannel]. These commitments should be recorded and sent to the verifier as they
//!    will be needed during the proof verification procedure.
//! 2. Then, the query phase of the protocol is executed via
//!    [build_proof()](prover::FriProver::build_proof()) function. The output of this function is an
//!    instance of the [FriProof] struct. When FRI is executed as a part of the STARK protocol, FRI
//!    proof is included into a STARK proof.
//!
//! When the crate is compiled with `concurrent` feature enabled, proof generation will be
//! performed in multiple threads (usually, as many threads as there are logical cores on the
//! machine). The number of threads can be configured via `RAYON_NUM_THREADS` environment variable.
//!
//! # Proof verification
//! FRI proofs are verified by a [FriVerifier] as follows:
//! 1. First, a FRI proof needs to be converted into a [VerifierChannel]. This crate provides a
//!    default implementation of the verifier channel, but when FRI proof verification is executed
//!    as a part of the larger STARK protocol, STARK verifier handles this conversion.
//! 2. Then, a [FriVerifier] should be instantiated (via [new()](FriVerifier::new()) function). This
//!    will execute the commit phase of the FRI protocol from the verifier's perspective - i.e., the
//!    verifier will read FRI layer commitments from the channel, and generates random values needed
//!    for layer folding.
//! 3. Finally, the query phase of the FRI protocol should be executed via
//!    [verify()](FriVerifier::verify()) function. Note that query values at the first FRI layer are
//!    provided to the [verify()](FriVerifier::verify()) function directly. The values at remaining
//!    layers, the verifier reads from the specified verifier channel.
//!
//! # Protocol parameters
//! The current implementation supports executing FRI protocol with dynamically configurable
//! parameters including:
//!
//! * Base STARK field,
//! * Extension field,
//! * Domain blowup factor,
//! * Hash function (used for building vector commitments),
//! * Folding factor (used for degree reduction for each FRI layer),
//! * Maximum size of the last FRI layer.
//!
//! # References
//! * StarkWare's blog post on [Low Degree Testing](https://medium.com/starkware/low-degree-testing-f7614f5172db)
//! * [Fast Reed-Solomon Interactive Oracle Proofs of Proximity](https://eccc.weizmann.ac.il/report/2017/134/)
//! * [DEEP-FRI: Sampling Outside the Box Improves Soundness](https://eprint.iacr.org/2019/336)
//! * Swastik Kooparty's [talk on DEEP-FRI](https://www.youtube.com/watch?v=txo_kPSn59Y&list=PLcIyXLwiPilWvjvNkhMn283LV370Pk5CT&index=6)

#![no_std]

#[macro_use]
extern crate alloc;

pub mod folding;

mod prover;
pub use prover::{DefaultProverChannel, FriProver, ProverChannel};

mod verifier;
pub use verifier::{DefaultVerifierChannel, FriVerifier, VerifierChannel};

mod options;
pub use options::FriOptions;

mod proof;
pub use proof::FriProof;

mod errors;
pub use errors::VerifierError;

pub mod utils;