10 releases (5 breaking)
|new 0.6.1||Mar 29, 2023|
|0.5.1||Feb 20, 2023|
|0.4.2||Nov 14, 2022|
|0.4.0||Apr 29, 2022|
|0.2.0||Aug 24, 2021|
#117 in Cryptography
3,641 downloads per month
Used in 5 crates (4 directly)
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.
To generate a proof that a computation was executed correctly, you will need to do the following:
- Define algebraic intermediate representation (AIR) for your computation. This can be done by implementing
Airtrait (see air crate for more info).
- Define an execution trace for your computation. This can be done by implementing
Tracetrait. Alternatively, you can use
TraceTablestruct which already implements
Tracetrait in cases when this generic implementation works for your use case.
- Execute your computation and record its execution trace.
- Define your prover(#Prover) by implementing
Provertrait. 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 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.
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). Besides these, a prover must provide implementations for two 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.
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 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:
- Lengths of all columns in the execution trace must be the same.
- 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:
- The first closure is responsible for initializing the first state of the computation (the first row of the execution trace).
- 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.
This crate can be compiled with the following features:
std- enabled by default and relies on the Rust standard library.
stdand 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
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.
This project is MIT licensed.