Winterfell STARK prover

This crate contains Winterfell STARK prover.

This prover can be used to generate proof of computational integrity using the STARK protocol. The prover supports multi-threaded proof generation (including multi-threaded execution trace generation) but is limited to a single machine.

Usage

To generate a proof that a computation was executed correctly, you will need to do the following:

1. Define algebraic intermediate representation (AIR) for your computation. This can be done by implementing Air trait (see air crate for more info).
2. Define an execution trace for your computation. This can be done by implementing Trace trait. Alternatively, you can use TraceTable struct which already implements Trace trait in cases when this generic implementation works for your use case.
3. Execute your computation and record its execution trace.
4. Define your prover(#Prover) by implementing Prover trait. Then execute Prover::prove() function passing the trace generated in the previous step into it as a parameter. The function will return a instance of StarkProof.

The resulting StarkProof object can be serialized and sent to a verifier for verification. The size of proof depends on the specifics of a given computation, but for most computations it should be in the range between 15 KB (for very small computations) and 300 KB (for very large computations).

Proof generation time is also highly dependent on the specifics of a given computation, but also depends on the capabilities of the machine used to generate the proofs (i.e. on number of CPU cores and memory bandwidth). For some high level benchmarks, see the performance section of the root README.

Prover

To define a prover for a computation, you'll need implement the Prover trait. This trait specifies the computation's AIR (via the Air associated type) and the shape of its execution trace (via the Trace associated type). The trait also requires specifying several other associated types, but for most of these default implementations provided by Winterfell should be used. Besides these, a prover must provide implementations for three methods:

• get_pub_inputs(), which describes how a set of public inputs can be extracted from a given instance of an execution trace. These inputs will need to be shared with the verifier in order for them to verify the proof.
• new_trace_lde(), which constructs a new instance of trace low-degree extension. Unless your prover needs to implement specialized optimizations for performing low-degree extensions, this method can just return a default trace low-degree extension provided by Winterfell.
• new_evaluator(), which constructs a new instance of the AIR constraint evaluator. Unless your prover needs to implement specialized optimizations for evaluating constraints, this method can just return a default constraint evaluator provided by Winterfell.
• options(), which defines STARK protocol parameters to be used during proof generation. These parameters include number of queries, blowup factor, grinding factor, hash function to be used during proof generation etc.. Values of these parameters directly inform such metrics as proof generation time, proof size, and proof security level. See air crate for more info.

A prover exposes a prove() method which can be used to generate a STARK proof using a given execution trace as a witness.

Execution trace

Execution trace is a two-dimensional matrix in which each row represents the state of the computation at a single point in time and each column corresponds to an algebraic register tracked over all steps of the computation. A big part of defining AIR for a computation is coming up with an efficient way to represent the computation's execution trace. Check out the examples crate for more info.

In Winterfell, an execution trace can be represented by any struct which implements the Trace trait. This trait defines a few property accessors (e.g., width and length) and defines a way of converting the struct into a vector of columns.

In most cases, defining a custom structure for an execution trace may be an overkill. Thus, Winterfell also provides a TraceTable struct which already implements the Trace trait. There are two ways to instantiate this struct.

First, you can use the TraceTable::init() function which takes a set of vectors as a parameter, where each vector contains values for a given column of the trace. This approach allows you to build the execution trace as you see fit, as long as it meets basic execution trace requirements. These requirements are:

1. Lengths of all columns in the execution trace must be the same.
2. The length of the columns must be some power of two.

The other approach is to instantiate TraceTable struct using TraceTable::new() function, which takes trace width and length as parameters. This function will allocate memory for the trace, but will not fill it with data. To fill the execution trace, you can use the fill() method, which takes two closures as parameters:

1. The first closure is responsible for initializing the first state of the computation (the first row of the execution trace).
2. The second closure receives the previous state of the execution trace as input, and must update it to the next state of the computation.

This second option is usually simpler to use and also makes it easy to implement concurrent trace generation.

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 proof generation

When this crate is compiled with concurrent feature enabled, proof generation will be performed in 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.

For computations which consist of many small independent computations, we can generate the execution trace of the entire computation by building fragments of the trace in parallel, and then joining these fragments together.

For this purpose, TraceTable struct exposes fragments() method, which takes fragment length as a parameter, breaks the execution trace into equally sized fragments, and returns an iterator over these fragments. You can then use fragment's fill() method to fill all fragments with data in parallel. The semantics of the fragment's fill() method are identical to the fill() method of the execution trace.

License

This project is MIT licensed.