Skip to content

Latest commit

 

History

History
232 lines (169 loc) · 19.4 KB

README.md

File metadata and controls

232 lines (169 loc) · 19.4 KB
Raw

GitHub Workflow Status Project license Pull Requests welcome

Exploration_Team

About

State-of-the-art Elliptic Curve tooling and SNARKS verification for Cairo & Starknet 🐺.

Garaga enables efficient elliptic curve operations on Starknet. It achieves state of the art performance by

  • using a dedicated builtin made by Starkware for emulated modular arithmetic
  • using a suite of non-deterministic techniques for extension field multiplication, pairings, and multi scalar multiplication to reduce the number of steps to verifiy results.

Garaga currently supports:

  • Scalar & Multi-scalar multiplication for any Weirstrass curve, including BN254, BLS12_381, SECP256/R1, and ED25519. You can add the one you need by specifying the curve parameters.
  • Pairing operations for BN254 and BLS12_381.
  • Groth16 smart contract verifiers generators for BN254 and BLS12_381.

Following supported schemes will be

  • BLS signatures contract generators.
  • Plonk based SNARKs verifier, especially Noir.

Architecture overview

Architecture Overview

Garaga consists of a Pythonic backend with Rust bindings and CairoZero / Cairo libraries.

  • The Pythonic backend is here to define emulated modular arithmetic circuits that can be compiled to Cairo or Cairo1 code. It also handles witnesses generation for the non-deterministic computations, smart contract contract generation for a given proof system and elliptic curve, and calldata generation from a given proof.
  • The CairoZero / Starknet interfaces are responsible for composing and calling the circuits, as well as adding all the extra logic needed to make the algorithms work (Fiat-Shamir heuristic, SNARKS verifiers algorithms, etc).

Quickstart : deploying a SNARK verifier on Starknet

Currently, only Groth16 on BN254 and BLS12_381 is supported with automatic support for json files coming from SnarkJS and Gnark.

  1. Create a new directory for you project, and bring the jsons files for verification key, proof file and public inputs inside it.

  2. Install the garaga pip package with pip install garaga. Python3.10 is mandatory and a virtual environment is recommended. Enter garaga in your terminal to get started.

  3. Run the garaga gen command in your terminal to generate the code for the SNARK verifier given your verification key.

  4. Edit the generated smart contract to fit the needs of your dapp.

  5. Create an environment file .secrets following the .secrets.template file in the root of this repository, containing the Starkner RPC url, your account address, and the private key.

  6. Run the garaga declare command in your terminal to declare the smart contract on Starknet and obtain its class hash. Note that this is an expensive operation.

  7. Run the garaga deploy command in your terminal using the class hash obtained in the previous step to get the contract address.

  8. Run the garaga verify-onchain command in your terminal using the contract address, the verification key, the proof and the public inputs to verify the proof against the SNARK verifier contract.

For more details, please refer to the documentation.

Developer setup

To get started with Garaga, you'll need to have some tools and dependencies installed. Here's everything you need:

Prerequisites

Ensure you have the following installed:

  • Python 3.10 - /!\ Make sure python3.10 is a valid command in your terminal. The core language used for development. Make sure you have the correct dependencies installed (in particular, GMP) for the fastecdsa python package. See here for linux and here for macos.
  • Scarb 2.7.1 - The Cairo package manager. Comes with Cairo inside. Requires Rust.
Optionally :
  • pprof - A tool for visualization and analysis of profiling data. Requires Go.
  • graphviz - Necessary for generating graphical representations of profiling data.

Setup

Once you have the prerequisites installed, clone the repository, and set up your development environment with the following command. Be sure to run this command from the root of the repository.

make setup

At this point, you should have everything you need to start developing with Garaga. Before proceeding, make sure to activate the virtual environment by running source venv/bin/activate.

Benchmarks

OP Weight in steps Comment
MULMOD 8 Equivalent cost of a*b % p with the modulo builtin in VM steps
ADDMOD 4 Equivalent cost of a+b % p with the modulo builtin in VM steps
ASSERT_EQ 2 Equivalent cost of a==b % p with the modulo builtin in VM steps
RLC 28 Cost of writing a field element to the value segment and retrieving random coefficients
POSEIDON 4 LIMBS 17 Cost of hashing the 4 limbs of 384 bits emulated field element with Poseidon
circuit MULMOD ADDMOD ASSERT_EQ POSEIDON RLC ~steps
Derive Point From X 6 2 0 0 0 56
Fp6 SQUARE_TORUS 12 22 0 7 1 324
Fp12 SQUARE 25 11 0 13 1 480
Fp12 MUL 36 22 0 13 1 612
Fp6 MUL_TORUS 36 34 0 13 2 688
MSM 1 points 150 128 0 52 0 2544
MSM 2 points 194 166 0 64 0 3240
MSM 3 points 238 204 0 76 0 3936
MSM 10 points 546 470 0 160 0 8808
MSM 50 points 2306 1990 0 640 0 36648
Miller n=1 BLS12_381 2672 2686 137 790 63 47588
Miller n=1 BN254 3303 3228 177 828 66 53130
Miller n=2 BLS12_381 4418 4525 273 812 63 69558
Miller n=2 BN254 5639 5576 353 852 66 81898
Miller n=3 BLS12_381 6164 6364 409 834 63 91528
Final Exp BN254 4681 7218 3 1931 317 102236
Miller n=3 BN254 7975 7924 529 876 66 110666
Final Exp BLS12_381 5123 9056 3 2333 384 127627
MultiPairing n=1 BN254 7984 10446 180 2759 383 155366
MultiPairing n=1 BLS12_381 7795 11742 140 3123 447 175215
MultiPairing n=2 BN254 10320 12794 356 2783 383 184134
MultiPairing n=2 BLS12_381 9541 13581 276 3145 447 197185
MultiPairing n=3 BN254 12656 15142 532 2807 383 212902
MultiPairing n=3 BLS12_381 11287 15420 412 3167 447 219155
BLS12FinalExp Fp12 Karabina No EXTF Trick 7774 43002 0 0 0 234200

Support & How to Contribute

We warmly welcome contributions and support from the community! Here's how you can help Garaga grow and improve:

Reporting Issues & Requesting Features

  • Spot a bug? Have a feature request? Check out our issues page to see if it's already been reported or to open a new issue.

Contributing to Garaga

  • Interested in contributing? Please take a moment to read our contribution guidelines for details on how to get started. Your contributions make the open-source community an incredible place for learning, inspiration, and creation.

Showing Support

  • Love Garaga? Give us a star on GitHub to show your support.
  • Spread the word: Share your excitement about Garaga on social platforms like Twitter, Dev.to, Medium, or your personal blog.
  • Join the conversation: Connect with us and other Garaga enthusiasts on our Telegram group.

Every contribution, whether it's code, feedback, or spreading the word, greatly benefits everyone and is deeply appreciated. Thank you for being a part of Garaga's journey!

Security

Garaga follows good practices of security, but 100% security cannot be assured. Garaga is provided "as is" without any warranty. Use at your own risk.

For more information and to report security issues, please refer to our security documentation.

License

This project is licensed under the MIT license.

See LICENSE for more information.

Acknowledgements

Resources

Note: This list is not exhaustive, and is not intended to be.

Contributors

For a full list of all authors and contributors, see the contributors page.

Thanks goes to these wonderful people (emoji key):

Feltroid Prime
Feltroid Prime
💻		 Abdel @ StarkWare
Abdel @ StarkWare
💻		 Tarik K.
Tarik K.
💻		 Bachir Arif
Bachir Arif
💻		 Renaud Dubois
Renaud Dubois
💻		 Rodrigo Ferreira
Rodrigo Ferreira
💻		 Luiz Vasconcelos Júnior
Luiz Vasconcelos Júnior
💻
Shramee Srivastav
Shramee Srivastav
💻		 Andrija Novakovic
Andrija Novakovic
💻		 Liam Eagen
Liam Eagen
💻
Add your contributions

This project follows the all-contributors specification. Contributions of any kind welcome!