# Winter FRI
This crate contains an implementation of FRI prover and verifier 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.

## Prover
FRI proofs are generated by a [FRI prover](src/prover/mod.rs) in two steps:

1. First, the commit phase of the protocol is executed via `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()` 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.

## Verifier
FRI proofs are verified by a [FriVerifier](src/verifier/mod.rs) 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()` 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()` function. Note that query values at the first FRI layer are provided to the `verify()` function directly. The values at remaining layers, the verifier reads from the specified verifier channel.

## Protocol parameters
This crates 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.

## Crate features
This crate can be compiled with the following features:

* `std` - enabled by default and relies on the Rust standard library.
* `concurrent` - implies `std` and also enables multi-threaded proof generation.
* `no_std` - does not rely on the Rust standard library and enables compilation to WebAssembly.

To compile with `no_std`, disable default features via `--no-default-features` flag.

### Concurrent execution
When this crate is compiled with `concurrent` feature enabled, `FriProver` will build FRI layers using multiple threads. The number of threads can be configured via `RAYON_NUM_THREADS` environment variable, and usually defaults to the number of logical cores on the machine.

## 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)


License
-------

This project is [MIT licensed](../LICENSE).