Winterfell STARK verifier

This crate contains an implementation of a STARK verifier which can verify proofs generated by a prover from the prover crate.

Usage

To verify a proof you can use verifier::verify() function, which has the following signature:

pub fn verify<AIR, HashFn, RandCoin>(
    proof: StarkProof,
    pub_inputs: AIR::PublicInputs,
    acceptable_options: &AcceptableOptions,
) -> Result<(), VerifierError> 
where 
    AIR: Air, 
    HashFn: ElementHasher<BaseField = AIR::BaseField>,
    RandCoin: RandomCoin<BaseField = AIR::BaseField, Hasher = HashFn>,

where:

• AIR is a type implementing Air trait for your computation (see air crate for more info).
• HashFn is a type defining the hash function used by the prover during proof generation.
• RandCoin is a type defining the methodology for drawing random values during proof generation.
• proof is the proof generated by the prover attesting that the computation was executed correctly against some set of public inputs.
• pub_inputs is the set of public inputs against which the computation was executed by the prover.
• acceptable_options defines a set of security parameters for the proofs which can be accepted by the verifier.

For example, if we have a struct FibAir which implements the Air trait and describes a computation of a Fibonacci sequence (see examples crate for the concrete implementation), we could verify that the prover computed the 1,048,576th term of the sequence correctly, by executing the following:

let min_sec = AcceptableOptions::MinConjecturedSecurity(95);
let fib_result = BaseElement::new(226333832811148522147755045522163790995);
match verifier::verify::<FibAir, Blake3, DefaultRandomCoin<Blake3>>(proof, fib_result, &min_sec) {
    Ok(_) => println!("Proof verified!"),
    Err(err) => println!("Failed to verify proof: {}", err),
}

where, 226333832811148522147755045522163790995 is the 1,048,576th term of the Fibonacci sequence when the sequence is computed in a 128-bit field with modulus 2¹²⁸ - 45 * 2⁴⁰.

Performance

Proof verification is extremely fast and is nearly independent of the complexity of the computation being verified. In vast majority of cases proofs can be verified in 3 - 5 ms on a modern mid-range laptop CPU (using a single core).

There is one exception, however: if a computation requires a lot of sequence assertions (see air crate for more info), the verification time may grow beyond 5 ms. But for the impact to be noticeable, the number of asserted values would need to be in tens of thousands. And even for hundreds of thousands of sequence assertions, the verification time should not exceed 50 ms.

Crate features

This crate can be compiled with the following features:

• std - enabled by default and relies on the Rust standard library.
• 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.

License

This project is MIT licensed.