Garaga

Report a Bug - Request a Feature - Ask a Question

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.

• Cairo
• Python 3.9

Specifically for profiling, the following tools dependencies are required:

• Go
• pprof
• graphviz

make setup

make build

make run-profile

See the open issues for a list of proposed features (and known issues).

• Top Feature Requests (Add your votes using the 👍 reaction)
• Top Bugs (Add your votes using the 👍 reaction)
• Newest Bugs

Reach out to the maintainer at one of the following places:

• GitHub Discussions
• Contact options listed on this GitHub profile

If you want to say thank you or/and support active development of Garaga:

• Add a GitHub Star to the project.
• Tweet about the Garaga.
• Write interesting articles about the project on Dev.to, Medium or your personal blog.

Together, we can make Garaga better!

First off, thanks 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.

Please read our contribution guidelines, and thank you for being involved!

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

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.

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)

Thanks goes to these wonderful people (emoji key):

Feltroid Prime 💻	Abdel @ StarkWare 💻	Tarik K. 💻
Add your contributions

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