Garaga

Garaga is a suite of elliptic curve tooling and SNARKs verification for Cairo and Starknet. It provides efficient elliptic curve operations on Starknet by using a dedicated builtin for emulated modular arithmetic and non-deterministic techniques for extension field multiplication, pairings, and multi-scalar multiplication (MSM).

Supported features include:

• Scalar & Multi-scalar multiplication (MSM): For any Weierstrass curve (e.g., BN254, BLS12_381, SECP256/R1, ED25519) by specifying curve parameters.
• Pairing operations: For BN254 and BLS12_381.
• Groth16 smart contract verifier generators: For BN254 and BLS12_381.
• Noir smart contract verifier generators: For ultra keccak honk flavour.

Garaga provides high-performance cryptographic tooling for Starknet, including:

• ZK Proof Verification: Groth16, Honk, Noir, RISC Zero, and SP1.
• Signature Verification: ECDSA, Schnorr, and EdDSA.
• Elliptic Curve Operations: Multi-scalar multiplication (MSM) and pairing operations for curves like BN254 and BLS12-381.
• Other Cryptography: Hashing (SHA-512, Poseidon), drand verification, and time-lock encryption.

Supported curves include: BN254, BLS12-381, SECP256K1, SECP256R1, ED25519, and GRUMPKIN.

The corelib_imports package provides controlled access to non-public functions, structs, and traits from the Cairo Corelib library via selective re-exports. It is designed to expose performance-critical operations for cryptographic computations, such as optimized bounded integer arithmetic and circuit operations, which are otherwise inaccessible due to Cairo's visibility rules.

To access specific internal APIs, this package utilizes feature flags (e.g., #[feature("bounded-int-utils")]).

Garaga provides tools to deploy custom SNARK verifiers on Starknet. Currently, the project supports the following verifier types:

• Groth16: Standard zk-SNARK verifier.
• Noir: Verifiers generated from the Noir domain-specific language.

Each verifier type has its own specific implementation and deployment guide within the repository.

Time-Lock Encryption (tlock) allows you to encrypt a 16-byte message for a future drand round. The message remains undecryptable until drand publishes the signature for that specific round.

Workflow:

1. Off-chain Encryption: Choose a future drand round $N$. Encrypt a 16-byte message using drand's public key and round $N$. This produces a CipherText consisting of a G2Point ($U$) and two 16-byte arrays ($V$ and $W$).
2. On-chain Decryption: Once drand publishes the signature for round $N$, the signature is used to recover the key via a BLS pairing check ($e(signature, U)$). The original message is then recovered via XOR decryption.

Important Constraint: tlock only encrypts a 16-byte (128-bit) message. To encrypt larger payloads, you must encrypt a symmetric key using tlock and then use that key to encrypt your larger data off-chain.

To make complex operations like MSM or signature verification efficient on-chain, Garaga uses a hybrid off-chain/on-chain model:

1. Off-chain (SDK): Use the Garaga SDK (Python, Rust, or TypeScript) to perform the heavy computation and generate verification hints.
2. Calldata: Pass the results and the generated hints as calldata to the Starknet transaction.
3. On-chain (Cairo): The Cairo library deserializes the calldata and verifies that the provided hints are correct, ensuring the computation was performed accurately without re-running the entire expensive operation.

Garaga maintains specific smart contracts that are declared on both Starknet Sepolia and Mainnet.

Key usage rules:

• Use Library Syscalls: These contracts are declared but not deployed. You must interact with them using library syscalls via their class hashes. Do not attempt to use a contract address, as they do not exist unless you deploy them yourself.
• Version Matching is Critical: The SDK generates calldata (hints) that are specific to the contract version. You must use the same Garaga SDK version that corresponds to the release of the class hashes you are using. Mismatched versions will cause verification to fail.
• Source Code: The source code for these contracts is located in the src/contracts directory of the main Garaga repository.

The template follows a standard directory structure for zkVM applications, separating the Host code (which manages the execution and proof generation) from the Guest code (the code that runs inside the zkVM).

project_name
├── Cargo.toml
├── host
│   ├── Cargo.toml
│   └── src
│       └── main.rs                    <-- [Host code goes here]
└── methods
    ├── Cargo.toml
    ├── build.rs
    ├── guest
    │   ├── Cargo.toml
    │   └── src
    │       └── method_name.rs         <-- [Guest code goes here]
    └── src
        └── lib.rs

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

• Pythonic Backend: Defines emulated modular arithmetic circuits (compilable to Cairo or Cairo1), handles witness generation for non-deterministic computations, generates smart contracts for specific proof systems/curves, and generates calldata from proofs.
• CairoZero / Starknet Interfaces: Composes and calls the circuits and implements additional logic like the Fiat-Shamir heuristic and SNARKs verifier algorithms.

All Garaga packages (Python, Cairo, Rust, and npm) are released with matching version numbers. To guarantee compatibility when using multiple Garaga components in a single project, you must ensure they all use the same version number.

Example for version 1.1.0:

• Python: pip install garaga==1.1.0
• Cairo: garaga = "1.1.0" in Scarb.toml
• Rust: tag = "v1.1.0" in Cargo.toml
• npm: npm install garaga@1.1.0

To ensure calldata is correctly formatted for on-chain verification, you must match SDK versions across your toolchain. All packages (Python, Rust, npm, Cairo) are released with synchronized version numbers.

• For generated contracts (Groth16, Noir): Use the exact SDK version that was used to generate the verifier contract.
• For maintained contracts (RISC Zero, SP1, drand): Use the SDK version that matches the Garaga release where those specific contract class hashes were declared.

Example: If using version 1.1.0, ensure pip install garaga==1.1.0 and garaga = "1.1.0" in Scarb.toml are used together.