# Advancing SNARKs-in-STARKs verification with Garaga: getting closer to maturity and efficiency

## I. An Introduction to Garaga
Garaga[^1] is a modern cryptographic library written in Cairo0 that emerged in December 2022. It is built upon the foundational efforts of Tekkac and Nethermind[^2][^3]. Licensed under MIT, the project is housed within the "Keep Starknet Strange"[^4] organization. It's worth acknowledging the invaluable trust and support extended by [@abdelhamidbakta](https://twitter.com/dimahledba) in bringing this endeavor to life.

The integration of SNARKs into Starknet to enhance privacy has long been a sought-after goal. However, the inherent cost of performing cryptographic operations for SNARK verification in Cairo has made it a costly endeavor. To this day, finding a cost-effective method to verify SNARKs, as well as other pairing-based cryptographic methods like BLS-Signatures or KZG Commitments continues to be a challenge.

However change is on the horizon. The library has undergone significant enhancements, drawing a wealth of inspiration from the work of Youssef El Housny and Ivo Kubjas at Consensys [^5]. By harmonizing these advancements with specific optimizations for Cairo, Garaga now promises a resource-efficient and accessible experience.

## II. Operational Workflow: Making It Happen.

Consider the Groth16 SNARK over the BN254 Curve.

They are mainly two ways one could verify a SNARK proof on Starknet.

### 1. Direct Smart Contract Deployment
The first one would be to deploy a smart contract using the Garaga library and provide endpoints to cryptographic operations such as `pairing()`, `groth16_verifier()`, `bls_sig_verif()`, etc.


While this approach is theoretically streamlined, practical implementation faces challenges:
1) Presently, the Groth16 verification process via Garaga (~3M steps) demands computational resources that exceed Starknet's current permissible limits per tx (~1M steps). However:

- The current computational boundaries are flexible and can be expanded. The limit is expected to be raised to 3M steps in the next 0.12.2 release[^45].
- Computation could be splitted into multiple transactions
- There remains room for further efficiency within Garaga.
2) Garaga uses extensively "*hints*" to enable cheaper computation. Hints are computations made outside the Cairo program. Cairo itself uses a lot of hints for its core library under the hood. Yet:
- Cairo0 is going to be deprecated on Starknet in some months with the Regenesis, when only Cairo smart contracts written in Sierra will be allowed. This makes the whitelisting of Garaga's Cairo0 hints useless in the long run.
- Cairo hints, are integrated into so-called "libfuncs" that are part of the Cairo compiler. It's a less straightforward process made for security of Starknet. Cairo compiles to Sierra, that compiles to CASM (Cairo Assembly). The Sierra-to-Casm process is where the hints are happenning[^22]. To add compatibility with Garaga, one would need to rewrite completey Garaga in Cairo1, and add libfuncs for all the hints in the Cairo compiler, which is a long and difficult process.

### 2. Off-chain operations
Another strategy is to execute more tasks off-chain. This method aims to address both computational constraints and challenges related to hints. This will also improve gas costs on-chain and allow faster innovation.


To bring this to fruition, all phases, namely (1), (2), and (3), require dedicated efforts. Yet, in the near term, this strategy is more attainable compared to the first approach. Gaining expertise in this procedure is vital for harnessing the capabilities of client-side proving within blockchain systems.

#### (1) Run the Cairo program that verifies the SNARK proof

Given that Garaga is built with Cairo0, its primary runner is cairo-lang[^6], developed in Python. This framework, while robust, often results in slow program execution and extended trace generation times. In contrast, the Cairo-VM[^7] from LambdaClass has been evolving and maturing. Crafted in Rust, it offers substantial improvements in running the Cairo program. Some challenges remain, particularly concerning hint implementations in Rust, but the available documentation[^8] provides very valuable guidance. By leveraging the Cairo-VM from LambdaClass, the generation of traces for Garaga programs should be expedited to just a few seconds or even less.

#### (2) Prove the Cairo program and output a STARK proof

Open-source provers designed for Cairo programs have seen significant advancements. Notably, Andrew Milson's development of a STARK prover using Sandstorm[^9] has successfully passed the STARK verifier contract on the Ethereum blockchain[^10]. Parallelly, LambdaClass is making outstanding progress with its Lambda Stark Platinum prover[^55], positioning it as a potential leader for modularity in the near future.
Starkware has also indicated plans to unveil the code for their prover [very soon](https://medium.com/starkware/open-sourcing-the-battle-tested-stone-prover-1fe71aaab3b7), anticipated to fuel innovation within the Cairo provers ecosystem.

However, a crucial aspect requires attention. Despite the optimistic trajectory for proving capabilities in the upcoming periods, it's essential to ensure that the verification of STARK proofs on Starknet remains cost-effective on-chain.

#### (3) Verify the STARK proof on Starknet

In the realm of STARK proof verification, the bulk of the process revolves around field operations, which Cairo natively supports, in conjunction with hashing. The cost-effectiveness of this process largely hinges on the hash function employed during the proving phase, which is reiterated in the verification phase. Essentially, the selection of the hash function should align with the most economical option available on the platform where the STARK proof is verified. For instance, while Ethereum favors keccak256 as its cost-effective hash function, Cairo leans towards the Poseidon hash function. Notably, Poseidon hashes can be executed at a significantly lower cost in Cairo, courtesy of its specialized built-in[^44].

To harness this efficiency, provers should be adapted to validate the Cairo program using Starknet's Poseidon hash function. By doing so, verifying a STARK proof on Starknet could become substantially more economical, paving the way for a plethora of off-chain computing scenarios.

## III. Garaga's roadmap
### Faster Running (trace generation)
- Transition from cairo-lang to the Cairo-VM of LambdaClass by incorporating Garaga's hints.

### Faster Proving time
- Pursue ongoing improvements in Garaga to minimize the number of steps to prove.
- Contribute to the optimization of open-source provers, including GPU utilization and built-in functions specific to Garaga.

### Cheaper on-chain gast costs
- **Push the open-souce Cairo provers ecosystem for a Poseidon-based STARK prover.**

### Streamlined User Experience

- End-to-end scripts to Verify a SNARK (or other pairing-based cryptography) in a Garaga program, STARK-prove the program, automate the Cairo code generation to verify the proof and extract the output on Starknet.

### More functionalities
- Incorporate batching techniques into Garaga, such as Multiple Groth16 verifier, Multi Scalar Multiplication, and Delegated Pairing techniques.
- Integrate support for novel verification schemes like UltraPlonk to enable verification of Noir circuits from Aztec[^21].

### Cairo1 codebase transition
1) Initiate the rewrite of the Garaga library in Cairo1, using mocked libfuncs.
2) Collaborate closely with Starkware to determine the optimal approach for incorporating the necessary libfuncs.
3) Launch the Garaga contracts directly on-chain.

### Madara integration for SNARK-specific appchains
Madara[^77][^78] is a Starknet sequencer that has gainded popularity over the last months. It enables the creation of Cairo-powered app-chains that could settle on Ethereum or Starknet directly. To be able to settle on Starknet, Madara faces the same problem of cheap STARK verification. As soon as provers get tweaked to make their corresponding Starknet verifier cheap, one could easily deploy an appchain with embedded Garaga support, bypassing the long process of integrating libfuncs to Cairo1.
## IV. Conclusion

Navigating the complex realms of cryptographic verification, Garaga is setting new benchmarks in integrating SNARKs into Starknet. Embracing the potential of client-side proving, Garaga exemplifies the transformative power of off-chain computations, shifting hefty workloads away from the blockchain. As we've delved into its intricacies, the future, although challenging, seems not only promising but also ripe with opportunities for more scalable and efficient solutions.

It's not just about advancing technology, but fostering a community driven by a shared vision. If you resonate with Garaga's mission and see potential in furthering the cause, we invite you to join our Telegram group.

=> https://t.me/GaragaPairingCairo

Together, we can pave the way for a more secure and efficient Starknet ecosystem!

### Sources
[^1]: https://github.com/keep-starknet-strange/garaga
[^2]: https://github.com/tekkac/cairo-alt_bn128
[^3]: https://github.com/NethermindEth/optimized_ecc_cairo
[^4]: https://github.com/keep-starknet-strange/
[^5]: https://eprint.iacr.org/2022/1162
[^6]: https://github.com/starkware-libs/cairo-lang
[^22]: https://github.com/starkware-libs/cairo/blob/50f9cfaca6a46cd4e336b7a336fced73fb9e7441/crates/cairo-lang-sierra-to-casm/src/invocations/int/unsigned256.rs#L45
[^7]: https://github.com/lambdaclass/cairo-vm/
[^8]: https://github.com/lambdaclass/cairo-vm/tree/main/docs/hint_processor
[^9]: https://github.com/andrewmilson/sandstorm
[^10]: https://twitter.com/andrewmilson/status/1686292241990692864
[^45]:https://github.com/starkware-libs/cairo-lang/releases/tag/v0.12.2
[^21]:https://noir-lang.org/index.html
[^55]:https://github.com/lambdaclass/lambdaworks_stark_platinum
[^44]:https://starkware.medium.com/builtins-and-dynamic-layouts-e419a73e29e
[^77]: https://github.com/keep-starknet-strange/madara
[^78]:https://starkware.co/resource/harnessing-the-beast-madara-and-the-revolution-of-starknet-appchains/