Table of Contents
Efficient pairing library using polynomial representation of field elements, written in Cairo 🐺.
Garaga can enable efficient pairing operations in StarkNet, by using polynomial representation of field elements. 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: would enable privacy-preserving computations on StarkNet.
- KZG cryptographic commitment scheme.
- Identity-based encryption schemes.
- Attribute-based encryption schemes.
- BLS (Boneh–Lynn–Shacham) Digital Signature scheme.
We are exploring many optimizations techniques. For example, we are currently working on a new technique to reduce the number of constraints in the pairing computation. This technique is based on the idea of using a polynomial representation of field elements.
Specifically for profiling and testing, the following tools dependencies are required:
make setupmake buildmake go make runmake run-profileprotostar test-cairo0 --max-steps 10000000 -x
protostar test-cairo0 --max-steps 10000000 tests/protostar_tests/bn254/test_e2.cairo
protostar test-cairo0 --max-steps 10000000 tests/protostar_tests/bn254/test_pair.cairo::test_final_exp
protostar test-cairo0 --max-steps 10000000 tests/protostar_tests/bls12_381/test_e12.cairo
| Operation on curve BN254 | Cairo steps or estimation |
|---|---|
| miller_loop | 320 848 |
| multi_miller_loop (N points) | ~ N * 260441 + 60407 |
| final_exponentiation | 270 215 |
| Groth16 circuit example (4 public inputs) | 1 671 116 |
| Operation on curve BLS12-381 | Cairo steps (number) (OBSOLETE: Wait for optimisation, expect /8) |
|---|---|
| miller_loop | 2 177 205 |
| miller_loop with pre-computed G2 values | 1 974 939 |
| final_exponentiation | 3 666 209 |
| e(P:G1, Q:G2) | 5 843 414 |
| e(P:G1, Q:G2) with pre-computed G2 values | 5 641 148 |
Work is in progress to convert fq_bigint library to built-ins, which should reduce the above costs by more than 70%.
Reach out to the maintainer at one of the following places:
See the open issues for
a list of proposed features (and known issues).
Please read our contribution guidelines, and thank you
for being involved!
If you want to say thank you or/and support active development of Garaga:
- Add a GitHub Star to the project.
- Tweet about Garaga.
- Write interesting articles about the project on Dev.to, Medium or your personal blog.
Thank you for taking the time to contribute! Contributions are what make the open-source community such an amazing place to learn, inspire, and create. Any contributions you make will benefit everybody else and are greatly appreciated.
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.
This project is licensed under the MIT license.
See LICENSE for more information.
- 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.
Here are some interesting resources about pairing-based cryptography:
Note: This list is not exhaustive, and is not intended to be.
- Document A :: Pairing for beginners : A beginner-friendly overall introduction of the concept and techniques, including Towered extension fields in section 7.3. (2012)
- Document B :: Efficient Hardware Implementation of IFp-Arithmetic for Pairing-Friendly Curves : Fast Fp modular multiplication using polynomial representation of field elements. Currently being implemented. (2012)
- Document C :: High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves Useful, relatively effective ready-to-use formulas including for Fp, Fp12 arithmetics. Should be composable with Document B.
- Document D :: Efficient Multiplication over Extension Fields Generalized Arithmetic on any extension field using polynomial representation of field elements. This work could enable polynomial representation of elements of finite field of any prime order, and thus very efficient pairing for any BN curve, including alt_bn128.
- Document E :: Accelerated tower arithmetic Close to state-of-the art solution for Fp12 arithmetics. Similar to Document D but harder. (2019)
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!