README.md

Stark101

Our objective is to prove that we know $x$ such that $a_{1022} = 2338775057$ in a finite field where $a_n$ is given by the Fibonacci sequence $a_n = a_{n-1} + a_{n-2}$ with $a_0 = 1$ and $a_1 = x$. The order of field is $3 \times 2^{30} - 1 = 3221225473$.

• Notebook 1 - Video 1
• Notebook 2 - Video 2
• Notebook 3 - Video 3
• Notebook 4 - Video 4
• Notebook 5 - Video 5

The implementation is found within the main.rs file. We make use of LambdaWorks's following tools together with our custom field:

• MerkleTree using Sha2_256Backend for Merkle commitments
• Transcript using DefaultTranscript, for the Fiat-Shamir transform
• Polynomial library for polynomial operations
• An additional Proof struct has been written, so that at the end the proof is serialized & saved on disk.

Tip

We stick to the naming conventions used in the tutorial, so it should be easy to follow the code along with the notebooks.

Usage

Run the prover via:

cargo run --release --bin stark101

Tip

debug mode is rather slow especially during the most compute-intensive interpolation part, so we use release mode instead.