Garaga

Report a Bug - Request a Feature - Ask a Question

About

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

Garaga can enable efficient elliptic curve pairing and scalar multiplication 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.

This is a work in progress, and is not yet ready for production use.

Here are some interesting use cases enabled by Garaga:

• SNARKs on StarkNet: Groth16 and Plonk (in the near future).
• KZG cryptographic commitment scheme.
• Identity-based encryption schemes.
• Attribute-based encryption schemes.
• BLS (Boneh–Lynn–Shacham) Digital Signature scheme.

Architecture overview (in progress.)

Garaga consists of a Pythonic backend and CairoZero / Starknet interfaces.

• 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.
• 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, etc).

Getting Started

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 - The core language used for development.
• Go - Required for profiling and testing.
• pprof - A tool for visualization and analysis of profiling data.
• graphviz - Necessary for generating graphical representations of profiling data.
• A functional SageMath installation or an operational Docker daemon with non-sudo privileges.

If you're using SageMath directly, make sure the edit the default parameter use_docker to False in the EcipCLI class inside tools/ecip_cli.py

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.

Compile & Run .cairo files (interactive script!)

make run

Benchmarks

OP	Weight in steps
MULMOD	8
ADDMOD	4
ASSERT_EQ	2
RLC	28
POSEIDON BN254	14
POSEIDON BLS12_381	17

circuit	MULMOD	ADDMOD	ASSERT_EQ	POSEIDON	RLC	~steps
Derive Point From X	6	2	0	0	0	56
Double Step BLS12_381	24	26	2	0	0	300
Double Step BN254	26	26	2	0	0	316
Fp6 SQUARE_TORUS	12	22	0	7	1	324
Mul L by L	18	8	0	11	1	380
Double-and-Add Step BLS12_381	34	47	4	0	0	468
Fp12 SQUARE	25	11	0	13	1	480
Triple Step	38	43	4	0	0	484
Mul LL by L	26	13	0	13	1	496
Double-and-Add Step BN254	38	47	4	0	0	500
Mul by L	28	15	0	13	1	520
Mul LL by LL	32	18	0	13	1	564
Mul by LL	34	20	0	13	1	588
Fp12 MUL	36	22	0	13	1	612
Fp6 MUL_TORUS	36	34	0	13	2	688
MSM 1 points	159	130	0	52	0	2624
MSM 2 points	203	168	0	64	0	3320
MSM 3 points	247	206	0	76	0	4016
MSM 10 points	555	472	0	160	0	8888
MSM 50 points	2315	1992	0	640	0	36728
Miller n=1 BLS12_381	4936	4966	137	1580	131	90154
Miller n=1 BN254	5984	5927	177	1810	153	101558
Final Exp BN254	4686	7223	3	1931	317	102296
Final Exp BLS12_381	5128	9061	3	2333	384	127687
Miller n=2 BLS12_381	8030	8171	273	2276	199	141734
Miller n=2 BN254	10132	10107	353	2740	241	167298
Miller n=3 BLS12_381	11356	11608	409	3088	267	198070
MultiPairing n=1 BN254	10670	13150	180	3741	470	203854
MultiPairing n=1 BLS12_381	10064	14027	140	3913	515	217841
BLS12FinalExp Fp12 Karabina No EXTF Trick	7774	43002	0	0	0	234200
Miller n=3 BN254	14456	14463	529	3758	329	236382
MultiPairing n=2 BLS12_381	13158	17232	276	4609	583	269421
MultiPairing n=2 BN254	14818	17330	356	4671	558	269594
MultiPairing n=3 BLS12_381	16484	20669	412	5421	651	325757
MultiPairing n=3 BN254	19142	21686	532	5689	646	338678

	Final Exp BN254	Final Exp BLS12_381	Miller n=1 BLS12_381	Miller n=1 BN254	Miller n=2 BLS12_381	Miller n=2 BN254	Miller n=3 BLS12_381	Miller n=3 BN254
EXTF_SQUARE	0	0	63	65	63	65	63	65
EXTF_MUL_DENSE	62	33	0	0	5	22	63	66
MUL_TORUS	62	33	0	0	0	0	0	0
SQUARE_TORUS	189	315	0	0	0	0	0	0
Double Step	0	0	58	44	116	88	174	132
Double-and-Add Step	0	0	4	21	8	42	12	63
Triple Step	0	0	1	0	2	0	3	0
MUL_L_BY_L	0	0	5	22	68	88	73	110
MUL_LL_BY_LL	0	0	0	0	5	22	5	23
MUL_LL_BY_L	0	0	0	0	0	0	58	44
MUL_BY_L	0	0	58	44	0	0	0	0
MUL_BY_LL	0	0	5	22	58	44	5	21

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

• Huge props to tekkac and feltroidprime for their initial work on provable pairing-based cryptography in StarkNet.
• Credits to Nethermind for their initial work on optimized modular arithmetic.
• Herodotus for supporting this project.
• Gnark project and team, especially yelhousni for his amazing knowledge and support.
• OnlyDust and Starkware.
• Liam Eagen and Andrija Novakovic for their support and amazing research.

Resources

• Craig Costello, Pairing for beginners
• Y. El Housni, "Pairings in Rank-1 Constraint Systems," Cryptology ePrint Archive, Report 2022/1162, 2022. Available: https://eprint.iacr.org/2022/1162.
• feltroidprime. "Faster Extension Field multiplications for Emulated Pairing Circuits." HackMD, https://hackmd.io/@feltroidprime/B1eyHHXNT.
• Liam Eagen, "Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity," Cryptology ePrint Archive, Report 2022/596, 2022. Available: https://eprint.iacr.org/2022/596
• Andrija Novakovic and Liam Eagen, "On Proving Pairings," Cryptology ePrint Archive, Paper 2024/640, 2024. Available: https://eprint.iacr.org/2024/640

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 💻	Abdel @ StarkWare 💻	Tarik K. 💻	Bachir Arif 💻	Renaud Dubois 💻
Add your contributions

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