1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

// 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 Merkle tree 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)

#![cfg_attr(not(feature = "std"), no_std)]

#[cfg(not(feature = "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;