# Deploy a Elastic Prover
In this tutorial, we'll show you how to deploy a template Poseidon Hash prover service on Snarkify Network.
## Deploy a Elastic Prover
1. Log in [Snarkify Console](https://console.snarkify.io) with your GitHub account.
2. For first time users, we have prepared a demo prover for you to try it out. Just Click `Try It First` to get started. You will be redirected to github for some configurations if this is the first service on your team.
3. Once the configuration is done, you can continue to deploy the demo prover. You can simply use the default values and directly click `Deploy` .π
{% hint style="info" %}
Deploying a demo prover will clone the template repository into your github account first, don't get surprised : )
{% endhint %}
4. The service will be rendered `Unready` for about 5 minutes while our backend pipeline is actively building and deploying your code. Grab some coffee :).
5. Once the deployment succeeds, the service status will become `Ready` , and an **Endpoint** will be generated and shown. Note the **Endpoint** of your deployed service, and we will need it to issue a proof generation request to your prover.
6. Alternatively, you can also deploy your own prover implementation on the Snarkify Network. Please checkout [Integrate Elastic Prover SDK](/serverless-gpu-proving/deploy-a-elastic-prover/integrate-elastic-prover-sdk).
## Issue a Proof Generation Request
In this section, we will show you how to issue a proof generation request to your prover and how to query the generated proof from the command line.
### Create an API key
* Go to the "Access Keys" tab, click the `Create Key` button, and give it a good name.
* Upon clicking the `Create` button, your key will be generated and shown. **Please save your access key securely, as the key will only be shown once.**
### Issue a Proof Generation Request
Get your **endpoint** and **access key** ready, and type the following command in your terminal.
```
ENDPOINT=
ACCESS_KEY=
```
Use the following curl command to issue your proof generation request against the demo prover:
```sh
curl --request POST $ENDPOINT \
--header "x-api-key: $ACCESS_KEY" \
--header "Content-Type: application/json" \
--data-raw '{
"input": {
"private_input": [0, 1, 2, 3, 4],
"public_input": "20304616028358001435806807494046171997958789835068077254356069730773893150537"
}
}
'
```
Requests are processed asynchronously by your prover service. You will receive a confirmation response with a `PENDING` state like the following,
```json
{
"service_id": "0872ccea325846ee9dd6f697b9af1863",
"task_id": "ec5e67fecbab4f66b5c4a1551105e795",
"service_name": "poseidon",
"creator_id": "5a5fd35f890349aea7ac9dc17d97d32b",
"result": null,
"state": "PENDING",
"input": "{\"private_input\": [0, 1, 2, 3, 4], \"public_input\": \"13037709793114148810823325920380362524528554380279235267325741570708489436263\"}",
"started": null,
"finished": null,
"created": "2023-11-04T03:14:25"
}
```
Please note the `task_id` for the next step.
### Query results
#### **From Command Line**
Get your **task ID** and **access key** ready, and type the following command in your terminal.
```
TASK_ID=
ACCESS_KEY=
```
The proof generation result can be queried with the following command,
curl --request GET "https://api.snarkify.io/v1/tasks/$TASK_ID" \
--header "x-api-key: $ACCESS_KEY"
Then you will see the task information like below once the task is processed:
```json
{
"service_id": "aa143bd5b48647569720096ab7493cd2",
"task_id": "4b1fd782a0f44f499a88a8cab31f066f",
"service_name": "poseidon",
"creator_id": "e95d87b33f8f45ea9e1f845eca18031d",
"result": "\"nc/6L2N4Jo1DU1SQ5IsVJ4EnqYo0pJBr1Zfv/Reez2LvtaFnHc/GzVpb2EBfAQhWBbk3OJNr5CBgS7TIJEtpQvPzw4PokhbAsvBsS6oK5Nu/zvJwVS4xrWgHD3uPT3ZWO7/U4n6YzZHBwgSN1bAK4ofFGQl7czSsS52ROInTJyVMGLtza6/UUh9IZmRkbw6ibZkJC5CIPfADf9LpNh71ZgAP3E66q8iqclzXdN4/i3fQ64i8KqrkGRUtPJYBWzxIvJXotC2OF3X/se371MTit0i3cR8C9eNLK4UglouWUCvJAyMdhlsrf7xKb/DI1V7I8jmKp0IGFt6hc6EDy/IOLEkzIGeqRmmmuLdfP+TwkQ+7ldAue56d0/NC22x2NJQpe8DwF6y/FHJxyi394HZEAZ8lYDhH2gjdW9FOj7jgLmZ0PyVM0i+hnssUSztiI+Lz0i6f7qmSQJZWR49QotjbbugIthJoYyrRF+aJh6dUSyv1d1cw06RhWcRa5H5q0j9hyW1z8pzghUhushcV66aUd1CYDefvVuvn2SygfOf1pm09cWyUewBDpSbHMpuMxhs7UODdbmoXDyq5THQ0jYKqSR57X5iO9c6dzVTGl4vEsbRVpMzgXNnoyfi/5+QuA1AHMhsRdSUkvBLpy+AhljqqQeieP3dokZesgrDqimBZdyXKFEXVaPfmCNbi+VWM1u1mCxZQI8fcCdNipBct65BfKgk+Nyn/EvJp5pYam0cy2cdq0gKPnRngzIRoCsOk1L4BxhXILjLgynovD3cJmwXvnQdcRyq9HCVU0lPhMXu3ChBJrS6PIroUubLGizech9OkHlzqEYFdcAs9F6VtpPAvEdD2l8tAr9xroLrOA1fi90Fc59yjt7FCD2EXrV6mCUQOkxD7lJCxpKn/Bsuh0SB8x8xtan2VhNkwpoUzTLW+aQNL4ZeqEVyQVxPa/dySh8MBZia2CQGjxJc4M/ckr1prLs3WZhLUPNFAD3y2MOk0kfAx52Y2eJxLBXGcp3DKXDoAAItHLdwq/UD2cp7Y4vKMdeXF6BHV+8OAm6UOXrkCwQoTM+EL+s/idxN9hrXb1gsOT3L2/Ux6EDOAJrdz6E0WDyUUFKEjkfV3br+ttjP3LfebI01QrEYq3nkx2Yhx6zYO687og2OnSv8mRnenrtF65SwNEHfzyrifv/rKKPUirRAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAPJ+1N1xPqDv/jbTB8n4sdug9JFw0mj5ChBpyjSlZIQA/jj/p1pOEuOErZ7wCWHaiYL1C7rK4ag5+cNr0LR1ER5O4P/zKVookId/m03cXQRc+83SatpTGH4fb6yDJNpFI9zgHqu4XzmpLM45WRGffhCqzyBuSppY0S6/sD8ISO8Hqs7NaiSHxMFVegF81lV6y/dx4nYdsFVRyEy8QwUbCArOnGo5cMEBKkRxA6FV4q1jvTx661HoVlZTVXLAo0SYF09V4JBvJIgTYy/E/QDTOb/WQFgPM8FaS0VOiyfj0xIQV1Bi2DVRtFP5eWLtzEYIRD+/BuI2abL+tGaRQ/SJmBhy2493gBXBrW/ISxdg2KZ1UxnhegBJOT7vImz2UsdBBj71BOni2oTA21oWTSFtOrXp4nuOjwT8tH+FarKu89QD0svTzabKDbtexD/xDS9LcpKYZ5DydKjMzFbKg9ARii6n7feSnTerZdN+ip1994wl13EfCIZM1cG66OQ6888IK7UlPvZN+9r+bMXiO+6AwH1us4SEhaGmVgSbYH5iCkQfR+rzR1k0crPCsAsquUg5xnS4USskd3SMZxGBzyL0HB8JDzvzGYFIIePw/vAwvaFLrdHGwTUEDkeWN4Iir5QiBTc4ajpCnrzkVfMMwRg81HGFoOuSfQOHrUBYysCxzLcgFlz/63SClAh9CJCUzogHaLTuvn+zltCYGQ1FsjxhV1i+ZXb6wK9fXC55YVMHQGH+ve/1PFik6ta0gJoBSlKnI9BaGK/2BU6C2r8cZWxm2WtEN0jMIBvxfejgyx+0vMlc\"",
"state": "SUCCESS",
"input": "{\"private_input\": [0, 1, 2, 3, 4], \"public_input\": \"20304616028358001435806807494046171997958789835068077254356069730773893150537\"}",
"started": "2023-11-10T02:08:22",
"finished": "2023-11-10T02:08:23",
"created": "2023-11-10T02:08:22"
}
```
#### **From Cloud Console**
Alternatively, you can also check your task history through our UI:
1. click the setting button
2. Go to the `Task Hisotry` page
## What's Next
Following this [tutorial](/serverless-gpu-proving/deploy-a-elastic-prover/integrate-elastic-prover-sdk) to make your own ZK circuits *cloud-ready* with the **`snarkify-sdk`**.
# Integrate Elastic Prover SDK
## Introduction
The Snarkify Elastic Prover SDK is a Rust-based library that offers a comprehensive interface for engaging with the Snarkify Network. It allows for the swift conversion of your existing circuit code into a deployable prover. With the SDK's streamlined process, you can easily tap into the capabilities of Snarkify Network using just a handful of straightforward steps.
## Installation
```shell
cargo add snarkify-sdk async-trait serde
```
## Implement your prover
1. Create a new file `snarkify.rs` in your `src/bin` directory
2. Implement the `ProofHandler` trait and `prove` method for proof creation
3. Invoke `snarkify_sdk::run::<{YourProofHandler}>()` in the main function
Here's a snippet of code illustrating how to use the SDK:
```rust
use async_trait::async_trait;
use serde::{Deserialize, Serialize};
use snarkify_sdk::prover::ProofHandler;
use std::io;
struct MyProofHandler;
#[derive(Deserialize)]
struct MyInput {
public_input: String,
}
#[derive(Serialize)]
struct MyOutput {
proof: String,
}
#[async_trait]
impl ProofHandler for MyProofHandler {
type Input = MyInput;
type Output = MyOutput;
type Error = ();
async fn prove(data: Self::Input) -> Result {
Ok(MyOutput {
proof: data.public_input.chars().rev().collect(),
})
}
}
fn main() -> Result<(), io::Error> {
snarkify_sdk::run::()
}
```
Please also checkout this [library](https://github.com/snarkify/poseidon_circuit) for a ready-to-deploy example of Poseidon hash prover.
### Testing locally
To run your prover locally, simply run,
```
cargo run --bin snarkify
```
and you can test the prover locally with a sample request like
```
curl --location --request POST 'http://localhost:8080' \
--header 'Content-Type: application/json' \
--header 'ce-specversion: 1.0' \
--header 'ce-id: abcdef123456' \
--header 'ce-source: test' \
--header 'ce-type: com.test.example' \
--data-raw '{
"public_input": "aloha"
}'
```
# Snakrify CLI
## Introduction
In addition to our user-friendly web console, we've developed Snarkify CLI tools tailored for command line aficionados. These tools are designed to simplify your service deployment on our platform, allowing for quick and efficient setup with just a few commands. Furthermore, users have the convenience of invoking the prover and managing requests directly through the CLI, enhancing productivity and ease of use.
# Installation
## Prerequisites
* Python: Version 3.8 or higher
* Docker: Latest version recommended
## Installation
```
pip install snarkify-cli
```
# Authentication
## 1. Create your API key
First of all, get an API key from our [cloud console](https://cloud.snarkify.io/keys). Please be aware that new API keys will be only displayed once in the popup dialog, make sure you copy it before closing.
## 2. Login with Snarkify CLI
Simply run:
```bash
snarkify login
```
You will be prompted to input your API key first. Upon successful authentication, you will also be asked to select an active team. If you want to switch to a different team later, just run the `snarkify team switch` command.
## 3. Logout with Snarkify CLI
If you want to logout, simply run
```
snarkify logout
```
Once logout, you are not able to interact with other Snarkify commands unless you login again.
# Service Initialization
## Integrate with Snarkify SDK
{% hint style="info" %}
You can skip this section if you have already followed the steps in [Integrate Elastic Prover SDK](/serverless-gpu-proving/deploy-a-elastic-prover/integrate-elastic-prover-sdk)and verified your change locally.
{% endhint %}
Switch to your project root directly, and run the following command:
```bash
snarkify init
```
It is simply a shortcut for:
1. Add `snarkify-sdk` cargo dependency to Cargo.toml
2. Create a template `snarkify.rs` file under `/src/bin`, in which you have to implement the `ProofHandler` with your own proof generation logic.
## Create your new service
Once your code is ready, running the following command will create a new service on Snarkify platform:
```
snarkify service create {service_name}
```
The new service will automatically link to your current project directory, ensuring that all future build and deploy commands seamlessly synchronizes the changes from your working directory to the cloud.
{% hint style="info" %}
Currently, our platform supports the creation of one service per code directory. We are actively working to enhance this feature, aiming to enable the support of multiple services from a single repository in the near future. Stay tuned for updates!
{% endhint %}
## Query your service
You can use the `snarkify service info` command to check the status of your service and get the RPC endpoint (`service url` field) once the deployment is done. Below is an example output:
ββββββββββββββββ¬ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β service id β 6b72fa8b01bc4d968f49658e6cf2f5f2 β
β service name β poseidon_test β
β team name β test β
β state β READY β
β created β 2024-01-22T23:16:51 β
β service url β https://2omfk53be1.execute-api.us-west-2.amazonaws.com/v1/services/6b72fa8b01bc4d968f49658e6cf2f5f2 β
β image tag β feature_a β
ββββββββββββββββ΄ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
# Build & Deployment
## Build Your Container
### Option 1: Snarkify command (recommended)
Simply run:
```
snarkify build
```
* To build from a sub-directory, simply use the `--base_dir={path_to_sub_dir}` option.
{% hint style="warning" %}
Heads up! The first build is like brewing a fine cup of coffeeβit takes a bit longer, but it's worth the wait. Patience is a virtue, and great things are brewing!
{% endhint %}
### Option 2: Docker command
Alternatively, it's also possible to use native `docker` command to build your image by following these steps:
1. Have a Dockerfile ready to build your code. Here is a template Dockerfile to invoke the snarkify binary.
```
# Use a smaller, specific version of the Rust image for building
FROM --platform=linux/amd64 rust:latest AS builder
# Create a new empty project
RUN USER=root cargo new --bin snarkify
WORKDIR /snarkify
# Copy over your manifests
COPY ./Cargo.lock ./Cargo.toml ./
# Cache dependencies by building a dummy project
RUN cargo build --release && \
rm src/*.rs && \
rm ./target/release/deps/snarkify*
# Build your project for release
COPY ./src ./src
RUN cargo build --release
# Use a slim variant for the runtime stage to reduce size
FROM --platform=linux/amd64 ubuntu:22.04
# Copy the build artifact from the build stage
COPY --from=builder /snarkify/target/release/snarkify /usr/local/bin/snarkify
# Set the startup command to run your binary
CMD ["/usr/local/bin/snarkify"]
```
2. Use docker command to build an image
```
docker build -t {your_image_name} .
```
## Deploy Your Container
Once your Docker image has been successfully built, you're just one step away from launching your service. To proceed, simply execute the following command:
```
snarkify deploy
```
* You can assign a unique tag to each deployment for easy reference by using the `--tag` option.
* Should you need to set environment variables, you can conveniently update them using the `--env` flag. For example, `snarkify deploy --env foo=bar --env hello=aloha`.
* If you use the second option (Docker command) to build your image, you need to specify the image using `--image` option.
# Proof Generation
## Create a task
To generate a proof, you need to create a task. The input for this task should be in JSON format. You can provide this either as a JSON string using `--json` or as a path to a JSON file using `--file`.
In your project's root directory, execute the following command:
```bash
snarkify task create --json {input_of_your_proof}
```
After successfully executing this command, it will display `snarkify task info {task_id}`, which you can use to check the status of your task and retrieve the proof later.
## Query a task
To check the status of your task and access the proof once it's successfully completed, use the `snarkify task info` command. Here's an example of the output:
```
ββββββββββββββββ¬ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β service name β poseidon_test β
ββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β task id β e5ec45e4682b424b9204a116ba009fc9 β
ββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β state β SUCCESS β
ββββββββββββββββΌββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β result url β https://snarkify-task-result-test.s3.us-west-2.amazonaws.com/e5ec45e4682b424b9204a116ba009fc9 β
ββββββββββββββββ΄ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
```
For more detailed information about the task, including the proof in the result field, use the `-d` flag.
# Team Management
## List teams
To view the teams available for interaction via Snarkify CLI, execute the command:
```
snarkify team list
```
This command displays all the teams you're a part of, with the current active team highlighted. This active team is where all services and tasks are created and queried.
## Switch team
To switch to a different team, use the command:
```
snarkify team switch
```
Upon running this, you'll be prompted to choose a new active team.
# GPU Shell Management
A GPU Shell is a managed GPU container on our platform with ssh capability, providing developers isolated development environments with various GPU configurations. Developers could use shells to develop and test their code while integrating with our SDK before deploying as a service in production.
## Create a Shell
You can create a shell with selected GPUs to accelerate your project development:
```
snarkify shell create {shell_name}
```
You'll be prompted to select the type of GPU during shell creation.
Note the the `shell_name` is optional. If it is not provided, a default name will be assigned based on the shell ID.
{% hint style="info" %}
It may take a few minutes for a new Shell to become READY
{% endhint %}
## Query a Shell
You can use the `info` command to check the status of your shell and retrieve the necessary access information.
```
snarkify shell info {shell_id}
```
## Access a Shell
Once you get the `shell_id` you would like to connect to, you can run the following command to ssh into it
```
snarkify shell connect {shell_id}
```
It will then prompt for the password, the default password is randomly generated and retrievable using the same `snarkfy sell info` command above.
## List Shells
You can use the `list` command to list all shells under your team.
```
snarkify shell list
```
## Delete a Shell
You can permanently delete a shell using the following command:
```
snarkify shell delete {shell_id}
```
# Advanced Topics
# Webhook
As proof generation is an asynchronous process, instead of keeping polling the task results, developers are encouraged to use webhooks to passively wait for the results. And it can be set up conveniently by:
1. Going to the setting page of the service you want to listen to:
2. Click `Add New Webhook` , fill in the name and url, then save it.
3. Start receiving results!
# zkEVM Halo2 GPU Prover
Snarkify's cuSnark library is a C++/CUDA project which provides a set of API functions, with rust bindings, designed to be plugged into the Halo2 proof system, replacing various compute-intensive operations with an accelerated GPU backend.
The following tables outline the performance improvements yielded when all of these optimizations are employed. The impact on end-to-end (e2e) proof time each optimization has depends on the size of the proof, which can be generally characterized by the number of rows and columns in the proof's trace table. Two proofs with different dimensions have been selected to demonstrate the variance in optimization impact. These benchmarks were obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.
### Proof 1 (aggregation): 2^25 rows, 5 columns
This document outlines the following GPU modules and the acceleration they provide for Halo2 proofs of various dimensions:
* [Multi-Scalar Multiplication (MSM)](/high-performance-zkp/zkevm-halo2-gpu-prover/msm)
* [Number Theoretic Transform (NTT)](/high-performance-zkp/zkevm-halo2-gpu-prover/ntt)
* [Polynomial Evaluation](/high-performance-zkp/zkevm-halo2-gpu-prover/quotient-polynomial-evaluation)
* [KZG Multiopen](/high-performance-zkp/zkevm-halo2-gpu-prover/kzg-multiopen)
* [Polynomial Inversion](/high-performance-zkp/zkevm-halo2-gpu-prover/polynomial-inversion)
* [Permutation Generation](/high-performance-zkp/zkevm-halo2-gpu-prover/permutation-generation)
# MSM
## Overview
The Multi-Scalar Multiplication (MSM) operation consists of multiplying a vector of finite field elements by a vector of elliptic curve points and summing the resulting vector into a single point. The Pippenger bucketing algorithm is typically applied, and well-documented in existing literature \[REF]. The cuSnark library utilizes a generalized version of the winning 2022 zprize MSM implementation, documentation of which can be found here \[REF].
## Performance
The following table outlines the performance improvements yielded with just the cuSnark MSM employed, showing the (CPU baseline) and accelerated results for the different proof stages in a set of proofs of various sizes. Times are in seconds, obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.
Proof Stage
2^20 rows, 1135 columns
2^25 rows, 5 columns
Initialization
(6.04) 6.08
(1.40) 1.41
Generate Instance
(0.05) 0.05
(1.05) 1.05
Generate Advice
(381.78) 339.69
(6.68) 4.07
Generate Lookups
(57.99) 57.19
(2.10) 1.86
Commit Permutations
(146.59) 75.80
(23.72) 13.74
Eval_h
(1069.09) 1070.57
(66.55) 66.75
Compute Evaluations
(9.81) 7.49
(35.75) 6.10
Multiopen
(18.71) 18.94
(28.82) 11.61
Total
(1690.05) 1575.82
(166.10) 106.59
# NTT
## Overview
The Number Theoretic Transform (NTT) operation is used to convert an array of finite field elements representing a polynomial between coefficient and evaluation forms. The cuSnark library wraps Supranational's [sppark](https://github.com/supranational/sppark) NTT implementation.
## Performance
The following table outlines the performance improvements yielded with just the cuSnark NTT employed, showing the (CPU baseline) and accelerated results for the different proof stages in a set of proofs of various sizes. Times are in seconds, obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.
Proof Stage
2^20 rows, 1135 columns
2^25 rows, 5 columns
Initialization
(6.04) 6.16
(1.40) 1.41
Generate Instance
(0.05) 0.05
(1.05) 1.05
Generate Advice
(381.78) 379.87
(6.68) 4.07
Generate Lookups
(57.99) 58.24
(2.10) 1.86
Commit Permutations
(146.59) 117.29
(23.72) 13.74
Eval_h
(1069.09) 696.53
(66.55) 66.75
Compute Evaluations
(9.81) 9.58
(35.75) 6.10
Multiopen
(18.71) 18.76
(28.82) 11.61
Total
(1690.05) 1380.08
(166.10) 124.82
# Quotient Polynomial Evaluation
## Overview
The quotient polynomial evaluation stage of Halo2, denoted as "Eval\_h" in the table below, is the most computationally expensive stage of the Halo2 proof generation process, taking between 1/3 and 2/3 of the total proof runtime, depending on the specific proof. This stage consists of applying a large graph of simple arithmetic operations (addition, subtraction, multiplication, etc) to a set of input polynomials (fixed, advice, instance, etc) in the extended coset domain, combining them into a single output polynomial H.
## GPU Implementation
The individual operations (addition, subtraction, multiplication, etc) that comprise the quotient polynomial evaluation are trivially implemented on the GPU, where each arithmetic operation is applied in parallel to the corresponding coefficients of the polynomials used as inputs to the operation. However, two difficulties arise: a) some method is required for transpiling the evaluation graph into GPU code; the graphs are big enough such that doing so manually is intractable and explicitly writing every operation into a kernel can lead to hours-long NVCC compilation of the kernel, and b) a large proof will have far more input and intermediate polynomials than can be stored in device memory at once.\
\
The cuSnark library addresses these difficulties by using a single kernel which processes the evaluation graph as a list of opcodes, taking as an argument a set of input polynomials, storing intermediate computations in a buffer, and writing any output values to a set of output polynomials. A python script is used to break up the evaluation graph into smaller opcode lists that comprise sequential launches of this generic kernel, such that the number of input/output arrays needed by any individual kernel launch do not exceed available device memory.
## Performance
The following table outlines the performance improvements yielded with just the cuSnark polynomial evaluation employed, showing the (CPU baseline) and accelerated results for the different proof stages in a set of proofs of various sizes. Times are in seconds, obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.
Proof Stage
2^20 rows, 1135 columns
2^25 rows, 5 columns
Initialization
(6.04) 6.09
(1.40) 1.39
Generate Instance
(0.05) 0.05
(1.05) 1.05
Generate Advice
(381.78) 382.20
(6.68) 6.82
Generate Lookups
(57.99) 58.27
(2.10) 2.14
Commit Permutations
(146.59) 146.10
(23.72) 23.45
Eval_h
(1069.09) 42.13
(66.58) 5.68
Compute Evaluations
(9.81) 10.03
(35.79) 36.29
Multiopen
(18.71) 18.79
(28.82) 27.80
Total
(1690.05) 663.66
(166.15) 104.61
# KZG Multiopen
## Overview
The Multiopen stage of Halo2 proof generation consists of composing a set of numerator polynomials from linear combination of sets of input polynomials, dividing a set of roots out of each numerator, and reducing the resulting quotients into a single polynomial via another linear combination.
## GPU Implementation
The linear combination steps of multiopen are trivially implemented on the GPU by summing the corresponding coefficients of each input polynomial in parallel. The polynomial division operation is more complex but can be cast as a modified prefix-scan operation for which highly efficient GPU solutions are readily available.
## Performance
The following table outlines the performance improvements yielded with just the cuSnark KZG Multiopen employed, showing the (CPU baseline) and accelerated results for the different proof stages in a set of proofs of various sizes. Times are in seconds, obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.
Proof Stage
2^20 rows, 1135 columns
2^25 rows, 5 columns
Initialization
(6.04) 6.06
(1.40) 1.39
Generate Instance
(0.05) 0.05
(1.05) 1.06
Generate Advice
(381.78) 381.82
(6.68) 6.66
Generate Lookups
(57.99) 58.43
(2.10) 2.11
Commit Permutations
(146.59) 146.91
(23.72) 25.28
Eval_h
(1069.09) 1071.40
(66.58) 66.95
Compute Evaluations
(9.81) 9.95
(35.79) 35.91
Multiopen
(18.71) 7.67
(28.82) 1.71
Total
(1690.05) 1682.28
(166.15) 141.06
# Polynomial Inversion
## Overview
At multiple points in the Halo2 proof generation process, large sets of finite field elements must be inverted, which can be a significant computational expense.
## GPU Implementation
These inversions can be trivially implemented on the GPU by simply computing the inverse of each element concurrently.
## Performance
The following table outlines the performance improvements yielded with just the cuSnark polynomial inversion employed, showing the (CPU baseline) and accelerated results for the different proof stages in a set of proofs of various sizes. Times are in seconds, obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.
Proof Stage
2^20 rows, 1135 columns
2^25 rows, 5 columns
Initialization
(6.04) 6.12
(1.40) 1.41
Generate Instance
(0.05) 0.05
(1.05) 1.08
Generate Advice
(381.78) 355.14
(6.68) 5.53
Generate Lookups
(57.99) 57.92
(2.10) 2.12
Commit Permutations
(146.59) 145.17
(23.72) 23.58
Eval_h
(1069.09) 1070.33
(66.58) 66.70
Compute Evaluations
(9.81) 9.85
(35.79) 35.39
Multiopen
(18.71) 18.93
(28.82) 28.69
Total
(1690.05) 1663.51
(166.15) 164.48
# Permutation Generation
## Overview
One component of lookup generation in Halo2 involves constructing permutations of columns of the trace table, which can be computationally demanding. Different versions of Halo2 follow different methods for this construction. One method involves creating permutations A' and S' of columns A and S, such that (A'\[i] - A'\[i+1])\*(S'\[i] - A'\[i]) = 0.
## GPU Implementation
The GPU algorithm used in the cuSnark library to efficiently construct these permutations is as follows:
\
1\) Apply a hash function H to each element of A to determine an index into a pair of hash tables storing the total count of that element's value, and a corresponding index in A where that value exists.
2\) Perform exclusive prefix scan on the count hash table to determine the starting index in A' for the grouping of each unique value in A
3\) Insert each element of A into A', using the hash function & tables, and the result of the prefix scan above, to determine the correct index in A'. For the first occurrence of a given value in A', also set the corresponding value in S', and a boolean "set" flag at the same index in a flag array indicating that index of S' has been set.
4\) For each element of S, use the hash tables to look up if that element has been inserted into S' already. If so, set the corresponding element of a boolean "used" flag array to true.
5\) Perform inclusive prefix scans to sum the elements of the "set" and "used" flag arrays
6\) Use the summed set array to create a mapping between \[index in a list of leftover elements in S] and \[index in S'].
7\) For each element of S which has not yet been used in S', use the summed used array to determine the element's index in the leftover list, and map that leftover index to an index in S'. Then, write the leftover element into S'.
## Performance
As mentioned above, not all versions of Halo2 use this method for constructing permutations, so this acceleration is not used in the benchmark proofs referenced by earlier sections. In another Halo2 version which does use this construction, on a proof with 2^24 rows and 1 lookup operation, the CPU lookup generation takes **39.32 seconds**, while the GPU accelerated version (using a single RTX 4090 card) takes **3.94 seconds**.
# ZPrize
### Setting the pace in ZK acceleration
[**ZPrize**](https://www.zprize.io/) is the most respected competition focused on advancing zero-knowledge proof performance across hardware platforms. It brings together contributors from industry, academia, and open-source communities to push the limits of whatβs possible in provable computation.
**Snarkify is the only team in the industry to achieve six ZPrize wins in different categories**, consistently delivering top performance across GPU, FPGA, and browser-based proving. Our co-founder, [Niall Emmart](https://x.com/Niall_Emmart), played a key role in shaping ZPrize outcomes β open-source breakthrough approaches that have since been adopted and extended by many leading ZK teams.
Weβre proud to be part of the ZPrize initiative and to continue raising the performance baseline for the entire zero-knowledge community.
### Performance Highlights
#### ZPrize 2022
* **1st place GPU MSM Acceleration:** [2.33Γ speedup over baseline](https://www.zprize.io/blog/announcing-zprize-results)
* **1st place WASM MSM Acceleration:** [5.4Γ improvement in browser-based finite-field and elliptic curve operations](https://www.zprize.io/blog/announcing-zprize-results)
#### ZPrize 2023
* **1st place WASM MSM Acceleration (BLS 12-377):** [Up to 150Γ faster than baseline](https://www.zprize.io/blog/announcing-the-2023-zprize-winners)
* **1st place WASM MSM Acceleration (Twisted Edwards):** [\~136Γ faster than baseline](https://www.zprize.io/blog/announcing-the-2023-zprize-winners)
* **1st place FPGA MSM Acceleration:** [>99% pipeline efficiency with a batched affine pipeline design](https://www.ingonyama.com/post/deep-dive-into-the-latest-msm-hardware-implementation)
* **1st place End-to-End zkSNARK GPU Proving:** [0.54 seconds per proof, \~900Γ speedup over CPU baseline](https://hackmd.io/@Cysic/SJxWcI4R1ye)
All of our work was open-sourced, reproducible, and focused on real-world relevance for zero-knowledge systems.
### Our take on achieving real-time proving
Snarkifyβs recent ZPrize results in end-to-end proving show that real-time zkSNARK generation is no longer theoretical β itβs an achievable milestone, made possible through thoughtful system design and engineering. This progress opens the door to new possibilities in on-chain validity proofs, blockchainsβ interoperability, and broader zero-knowledge innovation.
Through extensive work across hardware environments, weβve come to a clear conclusion: GPUs offer the most practical and scalable path to real-time proving today. Their combination of performance, programmability, cost-efficiency, and continuous advancements makes GPUs well-suited for the evolving demands of zero-knowledge infrastructure.
For more on our perspective and why weβre betting on GPUs to power the future of ZK proving, read our [full thread](https://x.com/Snarkify_ZKP/status/1858584102842364402).
# Introduction
**Sirius is an open-source plonkish folding framework for** [**halo2**](https://github.com/zcash/halo2) **circuits.**
> Sirius, renowned as the most luminous star in the night sky, deceives the naked eye by appearing as a solitary point of light when, in fact, it is a binary star system. Inspired by this duality, our project bears the name Sirius, capturing the essence of folded instances that give the illusion of being a singular entity.
Within the context of an Incrementally Verifiable Computation (IVC) scheme, the prover's role is to demonstrate that, upon consecutively applying a step function `F` exactly `n` times to an initial value $z\_0$, the result is $z\_n$. Here, the step function `F` takes two inputs $z\_i$ and $w$, and yields an output $z\_{i+1}$.
## Architecture
The `Sirius` folding framework is designed with a three-tiered architecture.
### **Arithmetization Layer**
The arithmetization layer, a.k.a. the front-end, serves as the interface of the constraint system. User-defined circuits and witness data are converted into an intermediate representation format defined by the folding scheme. Our current implementation follows the special-sound interactive protocol (SPS) from [Protostar](https://eprint.iacr.org/2023/620).
Supported front-ends:
* [halo2](https://github.com/zcash/halo2): Sirius accepts circuits expressed with halo2. See the [Fold a Fibonacci Circuit](/sirius-folding/examples/fold-a-fibonacci-circuit) or the [Fold the zkevm-circuits](/sirius-folding/examples/fold-the-zkevm-circuits) example.
### **Folding Scheme Layer**
At the heart of the framework is the folding scheme IVC circuit that accumulates the computations of multiple steps. At each step, the prover first calculates the instance-witness pairs from the previous step and folds them into the accumulator, then computes the auxiliary data that is needed by the folding scheme verifier. An IVC circuit then takes the outputs from the prover and performs the following steps: apply the step function `F`, fold the previous step's instance into the accumulator instance, and verify the inputs of the IVC circuit.
The format and process of auxiliary data depend on the underlying folding scheme. We have implemented two types of folding schemes.
* [Protogalaxy](https://eprint.iacr.org/2023/1106): the prover calculates two polynomials defined in the main protocol and sends them to the verifier. Protogalaxy supports the folding of multiple instances per step.
* [Sangria](https://geometry.xyz/notebook/sangria-a-folding-scheme-for-plonk) (deprecating): the prover calculates cross terms and error vectors for the folded instance-witness pairs as the auxiliary data. The elliptic curve multiplications in the folding verifier circuit scale linearly with the degree of the custom gates. Also, Sangria IVC scheme only supports the folding of one instance per step.
### **SNARK Layer**
The SNARK layer leverages Polynomial Interactive Oracle Proofs (PIOP) and Polynomial Commitment Schemes (PCS) to generate zkSNARKs for succinct and zero-knowledge verification. Polynomial relation checks of the IVC decider are converted to the *multivariate sum-check protocol*. The evaluation phase of the sum-check protocol depends on the polynomial commitment scheme, e.g. `hyperkzg` commitment scheme.
# Quickstart
This guide will help you set up a basic example that folds a circuit that describes the identify function $$F(X) = X$$. The entire code can be found at .
### *Step 1:* Create a New Rust Project
1. Install rust with [rustup](https://rustup.rs/)
```bash
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
```
2. Create a new project with cargo
```bash
cargo new my-project --bin;
cd my-project;
```
3. Add 'sirius' to dependencies
```bash
cargo add --git https://github.com/snarkify/sirius/ --tag v0.1.1;
```
### Step 2: Implement \`MyStepCircuit\`
Full code can be found at
Let's break down each section of this code
#### Import Necessary Modules
First, import the necessary modules and types from the Sirius library:
```rust
use std::path::Path;
use sirius::{
ff::Field,
ivc::{
step_circuit::{trivial, AssignedCell, ConstraintSystem, Layouter},
SynthesisError,
},
prelude::{
bn256::{new_default_pp, C1Affine, C1Scalar, C2Affine, C2Scalar},
CommitmentKey, PrimeField, StepCircuit, IVC,
},
};
```
This block imports modules for handling fields, circuits, and the incremental verification process. It also sets up the types for the BN256 and Grumpkin elliptic curves.
#### Define Constants and Circuit Structure
Define constants and the structure for your custom circuit:
```rust
/// Number of folding steps
const FOLD_STEP_COUNT: usize = 5;
// === PRIMARY ===
/// Arity: Input/output size per fold-step for the primary step-circuit
const A1: usize = 1;
/// Initial input for the primary circuit
const PRIMARY_Z_0: [C1Scalar; A1] = [C1Scalar::ZERO];
/// Key size for the Primary Circuit
const PRIMARY_COMMITMENT_KEY_SIZE: usize = 19;
/// Table size for the Primary Circuit
const PRIMARY_CIRCUIT_TABLE_SIZE: usize = 17;
// === SECONDARY ===
/// Arity: Input/output size per fold-step for the secondary step-circuit
const A2: usize = 1;
/// Initial input for the secondary circuit
const SECONDARY_Z_0: [C2Scalar; A1] = [C2Scalar::ZERO];
/// Table size for the Secondary Circuit
const SECONDARY_CIRCUIT_TABLE_SIZE: usize = 17;
/// Key size for the Secondary Circuit
const SECONDARY_COMMITMENT_KEY_SIZE: usize = 19;
```
**Explanation:**
* Folding Steps (`FOLD_STEP_COUNT`): Specifies the number of steps the IVC process will execute. Each step represents a round of computation in the circuit.
* Arity (`A1` and `A2`): Defines the input/output size per step for the primary and secondary circuits. Set to `1` in this example, meaning one input and one output per step.
* Initial Inputs (`PRIMARY_Z_0` and `SECONDARY_Z_0`): These are the starting values passed to the circuits at the zero step. Here, they are initialized to zero (`C1Scalar::ZERO` and `C2Scalar::ZERO`), but in a real circuit, you should replace these with the actual values required by your circuit.
* Commitment Key Size (`PRIMARY_COMMITMENT_KEY_SIZE` and `SECONDARY_COMMITMENT_KEY_SIZE`): Defines the size of the commitment keys for the circuits. Start with the provided values, but increase if your circuit requires more.
* Table Size (`PRIMARY_CIRCUIT_TABLE_SIZE` and `SECONDARY_CIRCUIT_TABLE_SIZE`): Specifies the lookup table sizes. A minimum of 17 is needed, but increase the size if your circuit demands more complex operations.
#### Implement the StepCircuit Trait
Next, define a basic implementation of the StepCircuit trait:
```rust
/// This structure is a template for configuring your circuit
///
/// It should store information about your PLONKish structure
#[derive(Debug, Clone)]
struct MyConfig {}
/// This page is a template for your circuit
/// Within this code - it returns the input unchanged
struct MyStepCircuit {}
impl StepCircuit for MyStepCircuit {
/// This is a configuration object that stores things like columns.
type Config = MyConfig;
/// Configure the step circuit. This method initializes necessary
/// fixed columns and advice columns.
fn configure(_cs: &mut ConstraintSystem) -> Self::Config {
MyConfig {}
}
/// Sythesize the circuit for a computation step and return variable
/// that corresponds to the output of the step z_{i+1}
/// this method will be called when we synthesize the IVC_Circuit
///
/// Return `z_out` result
fn synthesize_step(
&self,
_config: Self::Config,
_layouter: &mut impl Layouter,
z_i: &[AssignedCell; A],
) -> Result<[AssignedCell; A], SynthesisError> {
// For this example we do not modify anything, we return the input unchanged
Ok(z_i.clone())
}
}
```
In this section, the `StepCircuit` trait is implemented for the `MyStepCircuit` struct:
* `struct MyConfig` Acts as a template for configuring your circuit. Although it's empty in this example, it usually stores important constrain system configuration details.
* `struct MyStepCircuit` Represents the actual step-circuit logic. In this example, it simply returns the input unchanged, making it a trivial circuit. This is useful as a starting point or for testing purposes, but real circuits would involve more complex operations.
* `fn configure`This method is where the circuit's configuration is set up. It initializes any necessary columns & gates & lookups in the constraint system. The method currently returns an empty configuration, but in a more advanced circuit, it would be populated with the relevant data.
* `fn synthesize_step`This is the core of the circuit, where the computation for each step happens. It takes the configuration and an array of input variables (z\_i), and returns the next step's output. In this trivial example, the output is simply the input, but this is where you would implement the actual logic for your step-circuit's step function.
This example serves as a basic template. When developing your own circuits, you would replace the trivial operations with the actual logic needed for your application.
Check [\`StepCircuit\` trait](/sirius-folding/sirius-folding-apis/stepcircuit-trait) for more details
#### Set Up Commitment Keys
Next, we need to set up the commitment keys for our circuits. This involves generating or loading keys for the elliptic curves used in the primary and secondary circuits.
```rust
// This folder will store the commitment key so that we don't have to generate it every time.
//
// NOTE: since the key files are not serialized, but reflected directly from memory, the
// functions to load them is `unsafe`
let key_cache = Path::new(".cache");
println!("start setup primary commitment key: bn256");
// Safety: because the cache file is correct
let primary_commitment_key = unsafe {
CommitmentKey::::load_or_setup_cache(
key_cache,
"bn256",
PRIMARY_COMMITMENT_KEY_SIZE,
)
.unwrap()
};
println!("start setup secondary commitment key: grumpkin");
// Safety: because the cache file is correct
let secondary_commitment_key = unsafe {
CommitmentKey::::load_or_setup_cache(
key_cache,
"grumpkin",
SECONDARY_COMMITMENT_KEY_SIZE,
)
.unwrap()
};
```
**Explanation:**
* Storing Generated Keys: The commitment keys are generated and stored in the `.cache` folder. This is done to avoid the need to regenerate the keys every time you run the program, which saves time and computational resources.
* First Key Generation: The first time the keys are generated, it can take a significant amount of time. This is because key generation for cryptographic curves involves complex computations. Once generated, these keys are cached for future use.
* Elliptic Curves: In this example, keys are generated for two different elliptic curves: `bn256` for the primary circuit and `grumpkin` for the secondary circuit.
* Use of `unsafe`: The `unsafe` block is necessary because the functions that load or generate the keys operate directly on memory-mapped files. This approach is used for performance reasons - mapping keys directly from memory is faster than serializing and deserializing them. However, it also requires careful handling to ensure the integrity of the cached files.
This setup is crucial for ensuring that your circuits can efficiently use these cryptographic keys without incurring unnecessary delays in key generation each time the program is executed.
#### Initialize PublicParams
```rust
let pp = new_default_pp::(
SECONDARY_CIRCUIT_TABLE_SIZE as u32,
&primary_commitment_key,
&sc1,
PRIMARY_CIRCUIT_TABLE_SIZE as u32,
&secondary_commitment_key,
&sc2,
);
```
**Explanation:**
* `new_default_pp`: This function initializes the `PublicParams` with mostly default settings. It simplifies the setup process by automatically configuring the majority of parameters. However, if your circuit requires specific customizations or more advanced settings, you should create the `PublicParams` manually, specifying types and values directly.
* `PublicParams`: This structure not only store essential configuration data but also lock in the structure of the PLONKish constraint system for the entire IVC process. \
When you create `pp`, the `configure` and `synthesize` methods of your circuits are called internally to collect and organize the constraints, ensuring consistency across all folding steps in the IVC.
Check [\`PublicParams\` Struct](/sirius-folding/sirius-folding-apis/publicparams-struct) for more details
#### Perform Folding Steps and Verification
Finally, perform the folding steps and verify the computation:
```rust
let mut ivc = IVC::new(&pp, &sc1, PRIMARY_Z_0, &sc2, SECONDARY_Z_0, true)
.expect("failed to create `IVC`");
println!("ivc created");
for step in 1..FOLD_STEP_COUNT {
// you can modify circuit data here
ivc.fold_step(&pp, &sc1, &sc2)
.expect("failed to run fold step");
println!("folding step {step} was successful");
}
ivc.verify(&pp).expect("failed to verify ivc");
println!("verification successful");
```
**Explanation:**
* `IVC::new`: This function initializes the Incrementally Verifiable Computation (IVC) instance and automatically performs the zero step using the provided initial inputs (`PRIMARY_Z_0` and `SECONDARY_Z_0`). This zero step sets up the initial state for the folding process, ensuring that the IVC begins with the correct starting conditions.
* `IVC::fold_step`: During each call to fold\_step, the circuit's configure and synthesize methods are invoked few times. These methods define and execute the circuit's constraints and logic for that step. In a real-world circuit, you should update the circuit's witness (private inputs) between steps to reflect the changing state of the computation. This ensures that each folding step processes the correct data as the IVC progresses.
* 'DebugMode': The debug\_mode argument (set to true in this example) enables additional checks at each folding step. Specifically, it invokes the `MockProver` from the Halo2 library to verify the correctness of the computation at each step. While this mode is invaluable for debugging and ensuring correctness during development, it introduces a performance overhead. If you disable `debug_mode` for performance reasons (by setting it to false), errors will only be detected at the end of the entire computation during the call to `IVC::verify`.
* `IVC::verify`: The verify method is called at the end of the IVC process to check the validity of the entire computation. However, it only reports whether the computation was successful or if an error occurred at some point during the process. If `debug_mode` is disabled, this method lacks the detailed information to pinpoint where the error happenedβonly whether the final result is valid or not.
Check [\`IVC\` struct](/sirius-folding/sirius-folding-apis/ivc-struct) for more details
## Step 3: Run
### Running the Example
#### 1. First Run
To run the example for the first time, use the following command:
```bash
cargo run --release
```
This will compile the project in release mode, which is optimized for speed. During this initial run, the [#set-up-commitment-keys](#set-up-commitment-keys "mention") for the BN256 and Grumpkin curves will be generated and cached. This process may take some time, so running in release mode ensures it completes as quickly as possible.
#### 2. Subsequent Runs
For subsequent runs, you can use the following command without the --release flag:
```bash
cargo run
```
This will reuse the previously generated commitment keys, so the process will be faster, and thereβs no need to recompile in release mode unless you're making significant changes or need the performance optimization again.
#### 3. Expected Output
When the example runs successfully, you should see output indicating that the folding steps were executed and verified successfully:
```
start setup primary commitment key: bn256
start setup secondary commitment key: grumpkin
ivc created
folding step 1 was successful
folding step 2 was successful
folding step 3 was successful
folding step 4 was successful
folding step 5 was successful
verification successful
success
```
### Summary
In this Quickstart, we explored setting up a basic example with Sirius IVC, including initializing with `PublicParams`, performing folding steps, and understanding the role of debug mode and verification. We implemented a trivial step circuit that returns its input unchanged, laying the groundwork for more complex circuits.
For a deeper dive into implementing a real step circuit with dynamic witness management, check out the [Fold a Summation Circuit](/sirius-folding/examples/fold-a-summation-circuit) section.
# Examples
In this section, we will provide practical advice to get you started using Sirius
# Fold a Summation Circuit
The example extends the [Quickstart](/sirius-folding/quickstart) by introducing a summation circuit $$F(X) = X+X$$.
While the quickstart features a basic identity mapping ($$F(X) = X$$), this example replaces it with a custom `StepCircuit` that performs a summation operation, offering a more practical and detailed exploration of the Sirius framework.
The entire code for this example can be found at
All changes from the quickstart are captured in this commit:
**Why Build a Simple Example?**
This example demonstrates how to move beyond basic operations by implementing a circuit that actively processes inputs, specifically summing them with themselves. This approach provides a clearer understanding of how to create and configure custom circuits using Sirius, making it an ideal next step after completing the quickstart.
#### Understanding Gates in Halo2 Frontend
In Halo2, a **gate** is a core component used to enforce specific constraints in a cryptographic circuit. At a high level, a gate defines a mathematical relationship between different values within the circuit, ensuring that certain conditions are met. For example, a multiplication gate might ensure that the product of two input values equals an output value.
Gates use symbolic expressions to represent these relationships, which are later enforced during the proof generation process. These expressions are crucial in ensuring the circuit operates correctly and can be verified by both the prover and the verifier.
For more details, please check our page on [Terminologies](/sirius-folding/terminologies#plonkish)
#### Circuit Configuration in `fn configure`
In this section, we describe the specific changes made in the `fn configure` function within the `MyStepCircuit` implementation. This function is responsible for setting up the necessary components of the circuit to perform a simple summation operation.
```rust
fn configure(cs: &mut ConstraintSystem) -> Self::Config {
let config = Self::Config {
s: cs.selector(),
input: cs.advice_column(),
output: cs.advice_column(),
};
// Allow equality check for `input` to ensure consistency with `z_in`
cs.enable_equality(config.input);
// Creating a gate that enforces input + input = output
cs.create_gate("sum", |meta| {
let s = meta.query_selector(config.s);
let input = meta.query_advice(config.input, Rotation::cur());
let output = meta.query_advice(config.output, Rotation::cur());
vec![s * (input.clone() + input - output)]
});
config
}
```
**Explanation**
1. Selector (`s`):
* The selector `s` is initialized using `cs.selector()`. This selector is used to control when the summation gate is active, ensuring that the gateβs constraints are only enforced during the appropriate operations.
2. Advice Columns (`input`, `output`)**:**
* Two advice columns are introduced:
* `input`: This column holds the input values, which will be used in the summation operation.
* `output`: This column stores the results of the summation (`input + input`).
* The equality check is enabled for the `input` column with `cs.enable_equality(config.input)`, ensuring that the same value is used consistently within the circuit.
3. Gate Definition:
* A gate named `"sum"` is created using `cs.create_gate`. This gate enforces the condition that the value in the `output` column must be equal to the sum of the `input` column value with itself (i.e., `input + input`).
* The equation is constructed as `s * (input.clone() + input - output)`, where `s` is the selector controlling the gate, and `input` and `output` are the values from the respective columns. This ensures that the circuit correctly performs the summation operation.
This configuration sets up the circuit to handle a simple summation operation, demonstrating how to use selectors and advice columns within the Halo2 framework.
#### Circuit Synthesis in `fn synthesize_step`
In this section, we describe the specific changes made in the `fn synthesize_step` function within the `MyStepCircuit` implementation. This function is responsible for assigning values to the circuit's cells and enforcing the constraints defined during the configuration phase.
```rust
fn synthesize_step(
&self,
config: Self::Config,
layouter: &mut impl Layouter,
z_i: &[AssignedCell; A],
) -> Result<[AssignedCell; A], SynthesisError> {
let output = layouter.assign_region(
|| "main",
|mut region| {
z_i.iter()
.enumerate() // we need an index to use as offset
.map(|(i, cell)| {
// Enable selector to trigger the gate
config.s.enable(&mut region, i)?;
// Assign the input value to the `input` column
let input = region.assign_advice(
|| "input",
config.input,
i,
|| cell.value().copied(),
)?;
// Check at the constraint system level that the cells are equal
region.constrain_equal(cell.cell(), input.cell())?;
// Perform the operation and place the result in the `output` column
let output = region.assign_advice(
|| "output",
config.output,
i,
|| input.value().copied() + input.value(),
)?;
Ok(output)
})
.collect::, _>>()
},
)?;
Ok(output
.try_into() // convert to array
.expect("safe, because collect from input array"))
}
```
**Explanation**
1. Region Assignment:
* The `layouter.assign_region` function is used to define a region in which the circuit's logic will be executed. Each iteration over `z_i` represents a step in the circuit, with operations performed on each input value.
2. Selector Activation:
* The selector `s` is enabled for each row in the region using `config.s.enable(&mut region, i)`. This activates the gate that enforces the summation operation defined in the configuration step. This gate will not work on the other lines. It is important that gates should be enabled regardless of the input on the same offsets.
3. Input Assignment:
* The input value is assigned to the `input` column using `region.assign_advice`. This step copies the value from `z_i` into the `input` column, where it will be used in the summation operation.
4. Equality Constraint:
* The `region.constrain_equal(cell.cell(), input.cell())` function ensures that the original input cell (`z_i`) is equal to the newly assigned `input` cell. This check enforces consistency in the values being used across the circuit.
5. Summation and Output Assignment:
* The summation operation is performed, and the result is placed in the `output` column using `region.assign_advice`. Specifically, the input value is doubled (`input.value().copied() + input.value()`) and assigned to the `output` column.
6. Result Collection:
* The results from all iterations are collected into a vector and then converted into an array using `try_into`. This array represents the output values (`z_out`) of the circuit for this step.
This function synthesizes the circuit by assigning values and ensuring that all constraints are satisfied, effectively performing the summation operation defined in the configuration.
### Running the Example
#### 1. First Run
To run the example for the first time, use the following command:
```bash
cargo run --release
```
This will compile the project in release mode, which is optimized for speed. During this initial run, the [#set-up-commitment-keys](#set-up-commitment-keys "mention") for the BN256 and Grumpkin curves will be generated and cached. This process may take some time, so running in release mode ensures it completes as quickly as possible.
#### 2. Subsequent Runs
For subsequent runs, you can use the following command without the --release flag:
```bash
cargo run
```
This will reuse the previously generated commitment keys, so the process will be faster, and thereβs no need to recompile in release mode unless you're making significant changes or need the performance optimization again.
#### 3. Expected Output
When the example runs successfully, you should see output indicating that the folding steps were executed and verified successfully:
```
start setup primary commitment key: bn256
start setup secondary commitment key: grumpkin
ivc created
folding step 1 was successful
folding step 2 was successful
folding step 3 was successful
folding step 4 was successful
folding step 5 was successful
verification successful
success
```
### Summary
In this section, we explored the implementation of the `fn configure` and `fn synthesize_step` functions within the `MyStepCircuit` in the Sirius Simple Example. These functions work together to define and synthesize a simple step circuit that performs a summation operation.
* `fn configure`: This function sets up the circuit by defining the necessary components, including a selector and advice columns for `input` and `output`. A custom gate is created to enforce the summation logic, where the input is doubled and stored in the output column.
* `fn synthesize_step`: This function assigns values to the circuit's cells and ensures that all constraints are correctly enforced. It activates the selector, assigns the input values, performs the summation, and places the result in the output column, synthesizing the circuit for each computation step.
Together, these functions illustrate how to configure and synthesize a simple custom circuit within the Sirius framework, providing a clear example of circuit creation and execution. This example helps developers understand the practical steps involved in building and running custom circuits in a cryptographic context.
# Fold a Fibonacci Circuit
Realization of a Fibonacci step circuit
This example builds upon the [Quickstart](/sirius-folding/quickstart) by introducing a more complex and meaningful circuit $$F(\[X\_i, X\_{i+1}]) = \[X\_{i+N}, X\_{i+1+N}]$$, where $$X\_i = X\_{i-2} + X\_{i-1}$$. While the Quickstart features a basic identity mapping, this example demonstrates how to compute Fibonacci numbers iteratively using the Sirius framework, offering a deeper exploration of the framework's capabilities.
The entire code for this example can be found at .
All changes from the Quickstart are captured in this commit:
#### Why Build a Fibonacci Example?
This example demonstrates how to implement and configure a circuit that calculates Fibonacci numbers across multiple folding steps. It provides a more detailed understanding of the Sirius framework's flexibility and power, making it an ideal next step after completing the Quickstart.
[Fold a Summation Circuit](/sirius-folding/examples/fold-a-summation-circuit#understanding-gates-in-halo2-frontend)
#### Circuit Configuration in `fn configure`
In this section, we describe the specific changes made in the `fn configure` function within the `FibonacciCircuit` implementation. This function sets up the necessary components of the circuit to compute Fibonacci numbers.
```rust
/// Configure the step circuit. This method initializes necessary
/// fixed columns and advice columns
fn configure(cs: &mut ConstraintSystem) -> Self::Config {
let config = Self::Config {
s: cs.selector(),
e: cs.advice_column(),
};
cs.enable_equality(config.e);
cs.create_gate("fibo-block", |meta| {
let s = meta.query_selector(config.s);
let e1 = meta.query_advice(config.e, Rotation(-2));
let e2 = meta.query_advice(config.e, Rotation(-1));
let e3 = meta.query_advice(config.e, Rotation(0));
vec![s * (e1 + e2 - e3)]
});
config
}
```
**Explanation**
* Selector (`s`): The selector `s` is initialized using `cs.selector()`. This selector controls when the Fibonacci gate is active, ensuring that the constraints are enforced only when necessary.
* Advice Column (`e`): An advice column is introduced to store the Fibonacci numbers as they are computed. The column is enabled for equality checks to ensure that values are coKnsistent across the circuit.
* **Gate Definition**: A gate named "fibo-block" is created using `cs.create_gate`. This gate enforces the Fibonacci relation $$a\_n = a\_{n-2} + a\_{n-1}$$β, ensuring that each output value is correctly computed as the sum of the previous two inputs.
This configuration prepares the circuit to handle the iterative computation of Fibonacci numbers, demonstrating how to use selectors and advice columns in the Halo2 frontend.
#### Circuit Synthesis in `fn synthesize_step`
In this section, we describe the specific changes made in the `fn synthesize_step` function within the `FibonacciCircuit` implementation. This function is responsible for assigning values to the circuit's cells and enforcing the constraints defined during the configuration phase.
```rust
/// Sythesize the circuit for a computation step and return variable
/// that corresponds to the output of the step z_{i+1}
/// this method will be called when we synthesize the IVC_Circuit
///
/// Return `z_out` result
fn synthesize_step(
&self,
config: Self::Config,
layouter: &mut impl Layouter,
z_i: &[AssignedCell; 2],
) -> Result<[AssignedCell; 2], SynthesisError> {
let z_out = layouter.assign_region(
|| "main",
|mut region| {
let [a, b] = z_i;
FibonacciIter(a.value().copied(), b.value().copied())
.enumerate()
.map(|(offset, value)| {
let assigned = region.assign_advice(
|| "element of sequence",
config.e,
offset,
|| value,
)?;
// Enforce equality constraints on the first two elements.
//
// For all other - enable gate with check. Note that the gate starts work
// at index 2, because the gate references the -2 cell internally
match offset {
0 => {
region.constrain_equal(a.cell(), assigned.cell())?;
}
1 => {
region.constrain_equal(b.cell(), assigned.cell())?;
}
_ => {
config.s.enable(&mut region, offset)?;
}
}
Ok(assigned)
})
.take(N + A1)
.skip(N) // We only need the last two elements (A1 := 2)
.collect::, _>>()
},
)?;
Ok(z_out.try_into().unwrap())
}
```
**Explanation**
* Region Assignment: The `layouter.assign_region` function defines a region where the circuit logic is executed. Each iteration over `z_i` represents a computation step, with operations performed to generate the next Fibonacci number.
* Selector Activation: The selector `s` is enabled for each relevant row in the region using `config.s.enable(&mut region, offset)`. This ensures that the Fibonacci relation is enforced only at the correct positions in the sequence.
* Input and Equality Constraint: The input values are assigned to the advice column `a`, and equality constraints are enforced to maintain consistency with the previous step's outputs.
* Summation and Output Assignment: The Fibonacci numbers are computed by summing the previous two values, and the results are stored in the advice column.
* Result Collection: The results are collected into an array, representing the output values (`z_out`) for this computation step.
This function synthesizes the circuit by assigning values and ensuring that all constraints are satisfied, effectively computing the Fibonacci sequence as defined in the configuration.
#### Running the Example
**1. First Run**
To run the example for the first time, use the following command:
```bash
cargo run --release
```
This will compile the project in release mode, optimizing for speed. During the initial run, the setup for commitment keys for the BN256 and Grumpkin curves will be generated and cached. This process may take some time, so running in release mode ensures it completes quickly.
**2. Subsequent Runs**
For subsequent runs, use the following command:
```bash
cargo run
```
This command reuses the previously generated commitment keys, making the process faster. There's no need to recompile in release mode unless you make significant changes or need performance optimization again.
**3. Expected Output**
When the example runs successfully, you should see output indicating that the folding steps were executed and verified:
```
textCopy codestart setup primary commitment key: bn256
start setup secondary commitment key: grumpkin
ivc created
folding step 1 was successful
folding step 2 was successful
folding step 3 was successful
folding step 4 was successful
folding step 5 was successful
verification successful
success
```
#### Summary
In this section, we explored the implementation of the `fn configure` and `fn synthesize_step` functions within the `FibonacciCircuit` in the Sirius Fibonacci Example. These functions work together to define and synthesize a circuit that computes Fibonacci numbers iteratively.
* `fn configure`: This function sets up the circuit by defining the necessary components, including a selector and an advice column. A custom gate is created to enforce the Fibonacci relation.
* `fn synthesize_step`: This function assigns values to the circuit's cells and ensures that all constraints are correctly enforced. It activates the selector, assigns the input values, computes the Fibonacci numbers, and places the results in the output column.
Together, these functions illustrate how to configure and synthesize a more complex custom circuit within the Sirius framework, providing a clear example of how to build and execute iterative computations in a cryptographic context.
# Fold a Halo2 Circuit
You can reuse chips & gadgets from the halo2 ecosystem without restriction, as well as reuse the implementation code of the circuit itself. However, you must allocate at the logic level the part of the circuit that will be used as input and output (`z_in` & `z_out`) from the circuit, checking the consistency of steps
Suppose we have a halo2 circuit that proves opcodes for VM. Then when turning such a circuit into a step-circuit, we must represent the state of the VM-like memory into a fixed-size array (e.g. using a hash function) and check the consistency of this memory at the beginning and end of the circuit synthetize. This way, no matter how many execution steps there are, you will always get a mathematical proof that each step is consistent with the previous one.
Consider a simple case, we have a circuit proving a hash function and we want to have a step-circuit proving an arbitrary number of nested hashes for a fixed data set. Then the only task will be to take the argument of the hash function as input (`z_in`) and return `AssignedCell` representing the ready hash (`z_out`). Then IVC will be able to prove any number of nested hashes without overhead in the proof step.
## The \`ShuffleChip\` Example
This section documents the iterative process of evolving a Sirius project by integrating a Halo2's [ShuffleChip](https://github.com/snarkify/halo2/blob/snarkify/dev.scroll.alpha.2/halo2_proofs/examples/shuffle_api.rs). The development process is captured through specific commits, each introducing new functionality or improving the existing implementation.
### Initial Fork from Sirius Quickstart
The project began by forking the [sirius-quickstart](https://github.com/snarkify/sirius-quickstart) repository. This initial step provided a working example of a simple `StepCircuit` in the Sirius framework, which performed a trivial operationβreturning the input unchanged over multiple folding steps.
* **Commit:** [Sirius Quickstart Init](https://github.com/snarkify/sirius-halo2-chip-usage/commit/55daf62a838e8e4b89abbcdfc7b1e23cd9aad8a0)
#### Key Features:
* **Trivial StepCircuit:** A basic `StepCircuit` implementation that served as the foundation for further development.
* **Initial Configuration:** Basic setup for primary and secondary circuits using BN256 and Grumpkin elliptic curves.
### Adding Halo2's ShuffleChip
#### Integrating the ShuffleChip Example
In this phase, the project was extended by incorporating the [`ShuffleChip` example](https://github.com/snarkify/halo2/blob/snarkify/dev.scroll.alpha.2/halo2_proofs/examples/shuffle_api.rs) from the Halo2 library. The adaptation required minimal changesβmainly making some fields public to fit the existing Sirius framework. This straightforward integration highlights how easily Halo2 components can be used within Sirius. Also at this stage, we have copied the halo2 circuit implementation inside the step circuit trait implementation without modification.
* **Commit:** [Add ShuffleChip Example](https://github.com/snarkify/sirius-halo2-chip-usage/commit/b530edf0969735b88e50679deb977c141c80d30c)
#### Key Changes:
* **ShuffleChip Module:** Added the `ShuffleChip` as a module in the project.
* **Minimal Adaptation:** The only changes needed were making some fields public, demonstrating the seamless compatibility between Halo2 chips and Sirius.
### Enhancing Circuit Logic and Input Handling
#### Add Consistency Between Steps
With the integration of the `ShuffleChip`, the next step involved refining how inputs were handled across different folding steps. The input handling was improved by moving `input_0` from a simple private signal to being passed as `z_in` for each step. This change made the circuit consistent across all folding steps.
* **Commit:** [Implement Step-Circuit with Enhanced Input Handling](https://github.com/snarkify/sirius-halo2-chip-usage/commit/515f8f0f8e29d3593be745e4c6d2f5a44b8af869)
#### Key Enhancements:
* **Input Consistency:** By tying `input_0` directly to `z_in`, the circuit now ensures consistent data flow across folding steps, enhancing the integrity of the computation.
* **Increased Commitment Key Size:** The number of columns in the circuit increased, requiring a larger commitment key size to accommodate the added complexity.
* **Array Usage for Inputs:** Arrays replaced `Vec` for inputs and shuffles to guarantee consistent sizes across all steps, a necessary condition for correct step synthesis.
### Code Explanation
#### Configuring the Circuit
```rust
fn configure(meta: &mut ConstraintSystem) -> Self::Config {
let input_0 = meta.advice_column();
meta.enable_equality(input_0);
let input_1 = meta.fixed_column();
let shuffle_0 = meta.advice_column();
let shuffle_1 = meta.advice_column();
ShuffleChip::configure(meta, input_0, input_1, shuffle_0, shuffle_1)
}
```
Here we repeat the `halo2_proofs::plonk::Circuit::configure` code almost verbatim, however, we add a call to `enable_equality` to perform an equality check with `z_in` in the `synthesize_step`.
### Synthesizing the Step-Circuit
```rust
fn synthesize_step(
&self,
config: Self::Config,
layouter: &mut impl Layouter,
z_i: &[AssignedCell; A],
) -> Result<[AssignedCell; A], SynthesisError> {
let ch = ShuffleChip::::construct(config);
layouter.assign_region(
|| "load inputs",
|mut region| {
for (i, (input_0, input_1)) in z_i.iter().zip(self.input_1.iter()).enumerate() {
input_0.copy_advice(|| "input 0", &mut region, ch.config.input_0, i)?;
region.assign_fixed(
|| "input_1",
ch.config.input_1,
i,
|| Value::known(*input_1),
)?;
ch.config.s_input.enable(&mut region, i)?;
}
Ok(())
},
)?;
let z_out = layouter.assign_region(
|| "load shuffles",
|mut region| {
self.shuffle_0
.iter()
.zip(self.shuffle_1.iter())
.enumerate()
.map(|(i, (shuffle_0, shuffle_1))| {
region.assign_advice(
|| "shuffle_1",
ch.config.shuffle_1,
i,
|| *shuffle_1,
)?;
ch.config.s_shuffle.enable(&mut region, i)?;
region.assign_advice(|| "shuffle_0", ch.config.shuffle_0, i, || *shuffle_0)
})
.collect::, _>>()
},
)?;
// For this commit - ignore processing of input
Ok(z_out.try_into().unwrap())
}
```
Here we also repeat the code of `halo2_proofs::plonk::Circuit::synthesize` implementation, but there are two important differences:
* Handling the input with an equality check (`copy_advice`). We don't just have to switch from private input to `z_in`, but also add a check at the `ConstraintSystem` level.
* Storing `shuffle_0` cells and returning them from step synthesis so that they can be reused in subsequent steps, ensuring step-circuit consistency within the IVC framework
### Summary
This iterative development process highlights the flexibility of the Sirius framework in accommodating and integrating Halo2's chips, like `ShuffleChip`. The minimal adaptation needed for the integration demonstrates how seamlessly Sirius can work with existing cryptographic components. Each commit represents a step towards building a more complex and functional circuit, starting from a basic template to a fully integrated solution
# Fold the zkevm-circuits
In previous section, we have illustrate how to use Sirius to fold user defined circuits. While these example serves a good start, they are more like toy examples. In this section, we will explain how to use Sirius to fold one important real-world application: zkEVM.
The EVM can be modeled as a state transition function. It specifies a transition function `F` that, given an initial world state `S` and a transaction `T`, outputs a new world state `Sβ: f(S,T) = S'`. This fits into the realm of IVC perfectly. In zkEVM circuit, we process the transactions as well as other blockchain data into circuit witness. The `super_circuit` proves that the state root is updated correctly.
[zkEVM circuit](https://github.com/scroll-tech/zkevm-circuits/) is co-authored by PSE and Scroll using [halo2](https://github.com/scroll-tech/halo2) library. It has very complex structures that contains multiple sub-circuits and their interactions. These sub-circuits is put together into a giant halo2 circuit called `super_circuit`. This is the user defined step circuit that Sirius will fold. It turned out this is made possible by about 400 lines of codes. We will describe how to turn the `super_circuit` into a step circuit.
## Transform zkEVM into step circuit
### Circuit modification
In order to make zkEVM circuit as a step circuit, we just need to implement the `StepCircuit` trait. This trait is very similar to the halo2's Circuit trait except that the `synthesize` method is replaced with `synthesize_step` where we must expose `z_in` and `z_out`.
The most natural way is to define the `prev_state_root` as `z_in`, witness as auxiliary inputs, `cur_state_root` as `z_out`. i.e. we have `z_out = F(w,z_in)` . In sub-circuit `pi_circuit` (`pi` stands for public input), `prev_state_root` and `cur_state_root` are calculated and assigned, and there is no need to modify the circuit layout. By slightly modify the internal functions, the `pi_circuit` will expose them to `super_circuit` . Then next thing is to adapt the super\_circuit configuration and synthesize methods, which is straightforward and most of the code can be reused.
### Code snippet
All major changes are from `zkevm-circuits` repo and can be found in this [PR](https://github.com/snarkify/zkevm-circuits/pull/2). Some minor changes to the entry point is also necessary, which can be found in this [PR](https://github.com/snarkify/scroll-prover/pull/1).
Here we will highlight a few important modifications on `zkemv-circuits`
**Step 1**
Add `prev_state_cells` and `last_state_cells` in `PiCircuit` so that we can expose them in `super_circuit` later.
```rust
#[derive(Clone, Debug)]
pub struct PiCircuit {
/// PublicInputs data known by the verifier
pub public_data: PublicData,
_marker: PhantomData,
connections: RefCell>>,
tx_value_cells: RefCell>>>,
prev_state_cells: RefCell>>>,
last_state_cells: RefCell>>>,
}
```
**Step 2**
Expose `(prev_state_root, last_state_root)` in `fn assign_pi_bytes`. By directly modify the following code, we avoid modifying the existing `pi_circuit` structure. In the return of `assign_pi_bytes` , we have both `pi_hash_cells` which is `last_state_cells` as well as newly added `prev_state_cells`
```rust
fn assign_pi_bytes() {
// skip codes
// Added the return of rpi_byte_cells, it includes prev_state_root to be exposed
// last_state_root is already exposed by this function as pi_hash_cells
let (rpi_cells, rpi_byte_cells): (Vec>, Vec>>) =
[
public_data.chain_id.to_be_bytes().to_vec(),
public_data.prev_state_root.to_fixed_bytes().to_vec(),
public_data.next_state_root.to_fixed_bytes().to_vec(),
public_data.withdraw_trie_root.to_fixed_bytes().to_vec(),
].iter() // skip the rest of code for simplicity
let prev_state_cells = rpi_byte_cells[1].clone();
// skip codes
// we expose pi_hash_cells (i.e. last_state_cells) as well as prev_state_cells
Ok(((pi_hash_cells, prev_state_cells), connections))
}
```
**Step 3**
Add a helper function to export state root cells. This is `z_in` and `z_out` when we turn the `super_circuit` into a `step_circuit`
```rust
/// (3) export state root cells for step circuit z_in and z_out
pub fn export_io(&self) -> StepCircuitIO {
(self.prev_state_cells, self.last_state_cells)
}
```
**Step 4**
With all the preparations of previous steps, we can implement the required `Sirius::StepCircuit` trait with slightly modification from the implementation of `halo2::Circuit` trait. Usually, when we convert a halo2 circuit into Sirius step circuit, `fn configuration` stays the same. The logic of `fn synthesize_step` will be very similar to `fn synthesize` except that in `fn synthesize_step` accept the `z_in` as parameter.
More precisely, the input `z_in` is an array of fixed length assigned cells, these cells located in the "outer" of step circuit. We use copy constraint to assign them inside step circuit region. The rest of the logic is same as `synthesize` . At the end of function, we return the assigned cells `z_out` so that the "outer" circuit can use it later on.
```rust
/// (4) Implement StepCircuit trait for SuperCircuit
impl SuperCircuit // skip generics for simplicity
{
// exactly same as `fn configure` in halo2::Circuit
// so we skip paste it here
fn configure();
/// Helper function
/// almost the same as synthesize_sub of super_circuit
fn synthesize_sub_with_io(
&self,
config: &SuperCircuitConfig,
challenges: &crate::util::Challenges>,
layouter: &mut impl Layouter,
) -> Result {
// skip codes
// in the end return z_in and z_out
Ok(self.pi_circuit.export_io())
}
// this is the key function of StepCircuit trait
// very similar to synthesize function
fn synthesize_step(
&self,
(config, challenges): Self::Config,
layouter: &mut impl Layouter,
z_i: &[AssignedCell; ARITY],
) -> Result<[AssignedCell; ARITY], SynthesisError> {
let challenges = challenges.values(layouter);
config.u8_table.load(layouter)?;
config.u16_table.load(layouter)?;
// the key difference here is that the super_circuit now
// is part of Sirius's ivc folding circuit
// Sirius is responsible to pass the input z_in to super_circuit
// and get the z_out from super_circuit (i.e. by copy constraints)
let (z_in, z_out) = self.synthesize_sub_with_io(&config, &challenges, layouter)?;
assert_eq!(z_i.len(), z_in.len());
z_i.iter().zip(z_in).try_for_each(|(lhs, rhs)| {
layouter.assign_region(
|| "constrain step circuit z_in",
move |mut region| region.constrain_equal(lhs.cell(), rhs.cell()),
)?;
Ok::<(), Error>(())
})?;
Ok(z_out
.try_into()
.unwrap_or_else(|v: Vec>| {
panic!("ARITY {} must be equal {}", v.len(), ARITY)
}))
}
}
```
## Check it out
You can try it out here:
```bash
// checkout the repo
git clone https://github.com/snarkify/scroll-prover;
cd scroll-prover;
// run the example
TRACE_PATH="tests/extra_traces/batch_495/chunk_495" make test-fold-prove;
```
This repo is just the entry point which depends on our modified[ zkevm-circuits](https://github.com/snarkify/zkevm-circuits/tree/step-circuit) repo.
Currently, it can be compiled successfully. However, it will have runtime error like this:
```
thread 'test_fold_prove' panicked at /Users/chao/.cargo/git/checkouts/sirius-fc7a02d83db739dc/30174b4/src/ivc/step_folding_circuit.rs:242:13:
You can't use instance column
```
This is because we are still missing several features to fully support the folding zkevm circuit. We listed a few [important features](https://github.com/snarkify/sirius/milestone/4) in the following sub-section.
### Challenges
Although we only have about 400 lines to modify the circuits as well as adding the folding prover. There are some challenges during this process. To solve these challenges, we need implement several new features. Here we list important ones.
**Folding of public inputs**
During the folding of zkevm circuit, the prover treats witness data as private inputs, after folding of multiple steps, the verifier is unable to verify the data source. The normal way of accumulate the public input of each step will not work well because during folding we use random linear combination to accumulate the public inputs. The random number depends on the commitment of witness of each step. The final verifier (i.e. decider) doesn't have access. Thus, the decider cannot compute the accumulated public inputs offline without knowing these challenges from each step.
Thus, the prover must accumulate the public IO of each step in a way such that the verifier can easily compute and verify it at the end. To the best of our knowledge, this part is neither clearly documented nor enforcized in existing literature or libraries. We added this feature in Sirius to accumulate step circuit's public IO so that the verifier can easily verify.
**Large number of gates**
`super_circuit` has about 2000+ custom gates. If we use powers of random linear number to combine them together as expression, the degree of the combined polynomial will be too high to deal with. Instead, we use Protogalaxy to evaluate each of them separately and combine their values together.
**Large number of columns**
`super_circuit` has about 800+ columns. In folding, we try to minimize the total number of commitments. To do this, we usually concatenate all the columns into one big vector and use a large commitment key (larger than the key for each column). However, with 800+ columns, it means the key size is increased by about 2^10.
The tradeoff is to make some balance between the size of commitment key and the number of commitments to be folded.
## Compare with proof aggregation
The zkEVM prover first parses the execution trace from geth into a vector of `Block` which serves as the circuit inputs. Then feed the inputs into the `super_circuit`. Then the prover can synthesize the circuit and create a proof. However, when the number of blocks is too large to fit into a single circuit, prover has to split the execution traces into multiple chunks and aggregate them recursively into one final proof.
In Scroll's current design, zkEVM prover used 4-layers aggregation architecture. The first layer is to create one proof per chunk. After that, each layer consists of either compressing or aggregating proofs from previous layer. It worth to emphasize that the prover has to create a fully workable proof in order to move to next layer.
With Sirius folding scheme, the prover directly folds each chunk into accumulate instance per step. The total number of folding steps is specified by prover's choice. At the last step, prover uses decider to prove the accumulated instance. This approach eliminates the need of layered architecture as well as the individual proofs created by each layer.
# Terminologies
## ZKP
In the context of Zero-Knowledge Proofs (ZKP), a **circuit** is a mathematical representation of a computation. It is a structured way to encode logical and arithmetic operations that need to be verified. In essence, a circuit in ZKP serves as the blueprint for proving that a particular computation was carried out correctly without revealing the inputs or intermediate steps.
**Key Concepts:**
* **Arithmetic Circuits**: These are circuits that represent computations over finite fields. They consist of gates that perform basic operations like addition and multiplication. The wires connecting the gates represent variables or values.
* **Constraints**: Circuits are composed of constraints that must be satisfied for the computation to be considered valid. In ZKP, these constraints are often represented as polynomial equations over a finite field.
* **Witness**: The witness refers to the private inputs to the circuit that the prover uses to demonstrate that they know a valid solution to the circuitβs constraints.
* **Public Inputs and Outputs**: These are the values that are known to both the prover and verifier. The circuit ensures that the outputs are correctly computed from the inputs according to the circuit's logic.
* **Prover and Verifier**: In a ZKP system, the prover uses the circuit to demonstrate that a computation is correct, while the verifier checks the proof without needing to know the private inputs (witness).
## Circuit
In ZKP systems, circuits are used to express complex computations that can be verified succinctly. The circuit breaks down the computation into small, verifiable steps, ensuring that every operation adheres to the defined constraints. This allows the verifier to be confident that the prover has correctly executed the computation, even without seeing the actual inputs or the complete computation process.
For example, in recursive proof systems like Nova, circuits are used to represent each step of an incremental computation. These circuits ensure that every step is independently verifiable, allowing for the entire computation to be verified incrementally.
Understanding the concept of a circuit is fundamental to grasping how ZKP systems function, as it forms the backbone of how computations are encoded, verified, and proven.
## Step Circuit
Check [#circuit](#circuit "mention") first.
#### StepCircuit
The `StepCircuit` trait is a core component in the [\`IVC\` struct](/sirius-folding/sirius-folding-apis/ivc-struct). It represents a single step in an incremental computation process, providing the necessary structure for handling inputs, configuring the step-circuit, and producing outputs at each step.
#### Why \`Step\`?
The `Step` prefix denotes the fact that this circuit will be called at each step of the folding, rather than once. This also adds the concept of fixed-size input and output. That is, unlike a regular circuit, Sirius also have a mechanism for linking circuit states between steps.
## PLONKish
Within the Sirius framework, we use PLONKish. For a mathematical description of the arithmetic, please refer to
Within this constraint system, we have a matrix over a field (each matrix element is a finite field element over a prime number.
### Phases
As part of the step-circuit implementation in Sirius, we have two phases:
* Configuration, when we set the circuit constraint strcuture, we create a matrix over the field that we will populate. This phase should not depend on the circuit-input in any way.
* Synthesis, when we fill the table and check if the generated witness falls under the constraints
#### API
For more details check [Quickstart](/sirius-folding/quickstart)
```rust
#[derive(Debug, Clone)]
struct MyConfig {}
struct MyStepCircuit {}
impl StepCircuit for MyStepCircuit {
/// This is a configuration object that stores things like columns.
type Config = MyConfig;
/// Configure the step circuit. This method initializes necessary
/// fixed columns and advice columns
fn configure(_cs: &mut ConstraintSystem) -> Self::Config {
todo!("impl `configure`")
}
/// Sythesize the circuit for a computation step and return variable
/// that corresponds to the output of the step z_{i+1}
/// this method will be called when we synthesize the IVC_Circuit
///
/// Return `z_out` result
fn synthesize_step(
&self,
_config: Self::Config,
_layouter: &mut impl Layouter,
_z_i: &[AssignedCell; A],
) -> Result<[AssignedCell; A], SynthesisError> {
todo!("impl `synthesize_step`")
}
}
```
### Columns
* Fixed (this also includes Selector & TableColumn) - immutable constants
* Instance - inputs to the circuit (provided externally)
* Advice - values depending on inputs
#### API
```rust
use sirius::halo2_proofs::plonk::{Advice, Column, Fixed, Instance, Selector, TableColumn};
struct Config {
selector: Selector,
advice: Column,
fixed: Column,
instance: Column,
table_column: TableColumn,
}
```
### Column Relationships (Gates)
Example: "5th column plus 4th column minus 9th column should equal 0"'
#### API
From [Fold a Summation Circuit](/sirius-folding/examples/fold-a-summation-circuit):
```rust
fn configure(cs: &mut ConstraintSystem) -> Self::Config {
...
// Creating a gate that reflects the sum
cs.create_gate("sum", |meta| {
let s = meta.query_selector(config.s);
let input = meta.query_advice(config.input, Rotation::cur());
let output = meta.query_advice(config.output, Rotation::cur());
vec![s * (input.clone() + input - output)]
});
...
}
```
### Allowed Values for Relationships (Lookup)
Example: "5th column plus 4th column minus 9th column should be something from 1st column"
#### API
```rust
fn configure(cs: &mut ConstraintSystem) -> Self::Config {
...
let allowed = cs.lookup_table_column();
let advice = cs.advice_column();
cs.lookup("main", |table| {
let advice = table.query_advice(advice, Rotation::cur());
vec![(advice, allowed)]
});
...
}
```
### Equalities Between Cells (Copy-Constraint)
Simply put, this is the only type of relationship not between columns but between cells.
#### API
From [Fold a Summation Circuit](/sirius-folding/examples/fold-a-summation-circuit)
```rust
fn configure(cs: &mut ConstraintSystem) -> Self::Config {
...
// Allow equality check for `input`
// for check consistency with `z_in`
cs.enable_equality(config.input);
...
}
/// Sythesize the circuit for a computation step and return variable
/// that corresponds to the output of the step z_{i+1}
/// this method will be called when we synthesize the IVC_Circuit
///
/// Return `z_out` result
fn synthesize_step(
&self,
config: Self::Config,
layouter: &mut impl Layouter,
z_i: &[AssignedCell; A],
) -> Result<[AssignedCell; A], SynthesisError> {
...
// Check at the constraint system level that the cells are equal
region.constrain_equal(cell.cell(), input.cell())?;
...
}
```
## IVC
Incrementally Verifiable Computation (IVC) allows the creation of proofs for each step of a computation incrementally, meaning proofs are generated as the computation progresses. This approach is efficient for long-running or stateful processes, as it avoids the need to re-compute the entire proof from scratch. IVC is particularly useful in blockchain and other systems where verifying sequential computations without re-running them is crucial. It supports efficient and scalable verification by enabling step-by-step proof generation and later combining these into a single proof.
# Sirius Folding APIs
This module will provide you with a comprehensive description of the key Sirius components required to develop solutions based on Sirius
# \`StepCircuit\` trait
Check [Terminologies](/sirius-folding/terminologies#step-circuit) first.
Also, due to the support of the halo2 ecosystem, you can learn more [Terminologies](/sirius-folding/terminologies#circuit) development from the [halo2 book](https://zcash.github.io/halo2/).
#### Trait
```rust
pub trait StepCircuit {
type Config: Clone;
fn configure(cs: &mut ConstraintSystem) -> Self::Config;
fn synthesize_step(
&self,
config: Self::Config,
layouter: &mut impl Layouter,
z_i: &[AssignedCell; ARITY],
) -> Result<[AssignedCell; ARITY], SynthesisError>;
fn process_step(
&self,
z_i: &[F; ARITY],
k_table_size: u32,
) -> Result<[F; ARITY], SynthesisError>;
}
```
* `const ARITY: usize` - Each step of [\`IVC\` struct](/sirius-folding/sirius-folding-apis/ivc-struct)has an input and an output (`z_in`, `z_out`), this parameter determines the size of this input.
* `type Config`- This type stores information about which columns and challenges we need for the circuit.
* `fn configure`- The function should create Config, as well as create all gates.\
\
Gadgets and chips from halo2 can be reused in this method.
* `fn synthesize_step` - Directly synthesize the witness, at this stage the PLONKish table must be filled in using `Layouter`.\
\
Gadgets and chips from halo2 can be reused in this method.
* `fn process_step` (optional for implementation) - This function must do the same `F(z_in) -> z_out` as `synthesize_step`. Due to some restrictions, we must supply as one of the public inputs (instance column) inside the folding scheme a hash that depends on `z_out`. \
\
By default, this method is done through the `synthesize_step` call, however, if the synthesis is long, it is possible to optimize it through a manual implementation in the off-circuit mode.
# \`PublicParams\` Struct
## New Default Public Params
Let us consider the simple case presented in [Quickstart](/sirius-folding/quickstart)
```rust
use sirius::prelude::bn256::new_default_pp;
let public_params = new_default_pp::(
secondary_circuit_k_table_size,
&primary_commitment_key,
&primary,
primary_circuit_k_table_size,
&secondary_commitment_key,
&secondary,
);
```
This is where the public parameters for bn256\grumpkin pairwise curves are created. All constants are taken by default, except for the main ones
* `ARITY`- Input and output size (`z_in`, `z_out`) for the corresponding step-circuit
* `k_circuit_table_size` - the size of the table the circuit should use. It must start with 17, otherwise there is not enough table size for IVC needs. Otherwise determined by the logic of your [\`StepCircuit\` trait](/sirius-folding/sirius-folding-apis/stepcircuit-trait).
* `&commitment_key` - the key that will be used by the scheme to commit metadata. Its size strongly depends on the step-circuit, its calculation is not trivial. It is recommended to choose the minimum key by selection method or for testing purposes generate a large key once and reuse it every time.
* `&step_circuit` It will be synthesized internally, to collect data about the PLONKish struct and reuse it later. The calling party retains possession of it, as further modification of the circuit is implied.
## Constructor
If you need other curves or want to pick other parameters for IVC, you can create public params directly
```rust
PublicParams::<
'_,
PRIMARY_ARITY,
SECONDARY_ARITY,
MAIN_GATE_SIZE,
PrimaryCurveAffine,
SecondaryCurveAffine,
PrimaryStepCircuit,
SecondaryStepCircuit,
PrimaryRandomOracle,
SecondaryRandomOracle,
>::new(
CircuitPublicParamsInput::new(
primary_k_table_size,
primary_commitment_key,
primary_random_oracle_constant,
primary_step_circuit,
),
CircuitPublicParamsInput::new(
secondary_k_table_size,
secondary_commitment_key,
secondary_random_oracle_constant,
secondary_step_circuit,
),
limb_width,
limbs_count_limit,
)
```
You can learn about the parameters `ARITY` & `k_table_size` & `commitment_key` & `step_circuit`- in the [#new-default-public-params](#new-default-public-params "mention")
* `RandomOracle`- you can specify the on-circuit\off-circuit random oracle to be used for the IVC circuit. Currently, only the poseidon variant is available from the box at the path `sirius::poseidon::PoseidonRO`.
* `random_oracle_constant` - according to the `RandomOracle` type, you must provide constants that will be used to initialize the random oracle. For poseidon it will be `sirius::poseidon::Spec`.
* `limbs_count_limit` & `limb_width` - during the execution of the IVC scheme in each of the two circuits, pairwise curve calculations will be performed on-circuit. These parameters determine the efficiency of these calculations.
# \`IVC\` struct
Check [Terminologies](/sirius-folding/terminologies#ivc) first
### Example
```rust
// Create IVC
// The zero step will be executed internally
let mut ivc = IVC::new(
&public_params,
&primary,
primary_initial_z_in,
&secondary,
secondary_initial_z_in,
false,
)
.expect("Error while create IVC");
// Performs the folding steps
//
// Inside the synthesis circuit will be called multiple times and therefore the state will
// change outside `fold_step`
//
// Also there must be a continuity of steps within the step-circuit, it must take into account
// that the next step `z_in` will be `z_out` from the previous step
for _ in 1..5 {
primary.update(input);
secondary.update(input);
ivc.fold_step(&public_params, &primary, &secondary)
.expect("Error while fold step");
}
// Verify that the folding was successful.
ivc.verify(&public_params).expect("Error while verify");
```
### Create IVC
#### Public Params
Please check [\`PublicParams\` Struct](/sirius-folding/sirius-folding-apis/publicparams-struct)
#### Primary & Secondary Circuit
IVC uses two step-circuits. Each of them is wrapped inside into a regular \`StepFoldingCircuit' and in addition to the step-circuit synthesis logic, the folding of the paired circuit is verified (secondary verifies the folding of primary and vice versa).
Therefore, the second circuit can always be a `sirius::step_circuit::trivial::Circuit` and have no payload whatsoever.
#### \`z\_in\` & \`z\_out\`
Each step-circuit has an input and an output at each step. Only the first input is specified in `IVC::new`, the others are chained `z_out` of step `n` is transmitted as `z_in` on step `n+1`
#### Debug Mode
In order to get a detailed error, you can enable `debug_mode`, then at each `fold_step` the `MockProver` from the halo2 library will be enabled and check your circuit. Otherwise, any error will only occur at the `verify` step.
### Fold Step IVC
Each folding step synthesizes primary & secondary circuits and performs off-circuit calculations to fold the plonk structure & witness. The developer's task here, between steps, is to modify the circuits (over which he retains ownership), also keeping in mind the `z_in` & `z_out` continuity.
### Verify
This step verifies that the constraint system is correct. If you started IVC not in `debug_mode` mode, in this case, only at the moment of `verify` call it is possible to detect violations of the constraint system at any of the steps.
# Benchmarks
# Advanced Topics
