mini-stark

In this repo I implement a stark prover for learning purposes using arkworks. Do not use this in a production environment.

• Complete ✅
• Soundness ✅
• Non-interactive ✅
• Succint ✅
• Zero-Knowledge ✅ (see comments)

Fields (with extension > 100 bits) supported out of the box:

• Goldilocks ➰
• BabyBear 🧸

🚧 This repo is WIP 🚧 I intend to add more features with time.

Issues/comments/critics all very welcome.

Roadmap

Planned features(in no specific order):

• FRI
• add Fiat-Shamir
• commit to multiple polynomials
• add support for AIR arithmetization
• extend merkle.rs to get trees with 4/8 nodes
• add zk: random trace padding and domain coset
• Stark PIOP
  • add DEEP to ALI & FRI
• Add rayon for parallelization
• Add criterion and integration tests to benchmark performance
• Additional features such as:
  • griding
  • STIR ??
  • WHIR ??
  • ..

Comments

Zero-Knowledge

The zk property was implemented following stark-by-hand. It was shown in the following paper do not meet the requirements to assert the specific property of zero knowledge. But this is still a topic of discussion.

References / Acknowledgements

Here is a list of some resources, I used which made my life much easier (to the authors: thank you 🙏):

• The IOP has been mostly taken from stark-by-hand by risc0 and to a lesser degree from anatomy of a STARK.
• FRI is based anatomy of a STARK and Chp.8 of zk-learning.org and the following FRI Summary in no specific order.
• The DEEP technique was taken from the orignal paper.
• For the AIR arithmetization, I took great inspiration from OpenZK. Notes on air arithmetization is a very good primer on air.
• For the zk-property this implementation follows stark-by-hand and I am aware of it limitations discussed here.
• I took FRI-batching from risc0 knowledge database
• The quadratic extension of the Goldilocks field from the WHIR implementation ...

The list is not complete, so if you see recognize something who needs attribution, hit me up :)