---
tags: PSE
---

# Folding Circom circuits: a ZKML case study

## Previous work from other groups
* [Zator: Verified inference of a 512-layer neural network using recursive SNARKs 🐊](https://github.com/lyronctk/zator)

## Folding model architecture vs inference
* Folding model architecture
* Pros: get much more compression ratio as we wish per inference
* Cons: require models to be specifically designed for folding, which might not be practical for the current web2 industry
* Folding model inference
* Pros: do not need to modify current models
* Cons: performance still limited by the model depth and complexity

## Let's try to fold model inference!

In order to use [Nova-Scotia](https://github.com/nalinbhardwaj/Nova-Scotia) to fold Circom circuits:
> 
> We write a circuit that takes a list of public inputs (these must be named step_in for the Nova-Scotia interface) and outputs the same number of public outputs (named step_out). These public outputs will then be routed to the next step of recursion as step_in, and this will continue until we reach the end of the recursion iterations. Within a step circuit, besides the public inputs, Circom circuits can input additional private inputs (with any name/JSON structure Circom will accept).

Let's try to write out the `step_in`, `step_out`, and private inputs at each step!

### Scenario 1: Public Data, Private Model

#### Attempt 1: naive approach

| signals | Step 1 | Step 2 | ... | Step N-1 | Step N |
| -------------- | ------------------------------------------------------ | ---------------------------------------------------------- | --- | ------------------------------------------------------------------ | ---------------------------------------------------------------------- |
| $step_{in}$ | $[modelHash,data_1,data_2,...,data_N,0,0,...,0,0]$ | $step_{out,1}$ | ... | $step_{out,N-2}$ | $step_{out,N-1}$ |
| $step_{out}$ | $[modelHash,data_1,data_2,...,data_N,out_1,0,...,0,0]$ | $[modelHash,data_1,data_2,...,data_N,out_1,out_2,...,0,0]$ | ... | $[modelHash,data_1,data_2,...,data_N,out_1,out_2,...,out_{N-1},0]$ | $[modelHash,data_1,data_2,...,data_N,out_1,out_2,...,out_{N-1},out_N]$ |
| private inputs | model weights | model weights | ... | model weights | model weights |

Issues:
* the size of the public outputs (hence the size of the proof) grows linearly
* a lot of switchers need to be used to insert at the correct positions

#### Attempt 2: Merkle root?

| signals | Step 1 | Step 2 | ... | Step N-1 | Step N |
| -------------- | ------------------------------------------------------------ | ----------------------------------------------------------- | ---------------- | --------------------------------------------------------------------- | ----------------------------------------------------------- |
| $step_{in}$ | $[modelHash, zeroRoot, zeroRoot]$ | ... | $step_{out,N-2}$ | $step_{out,N-1}$ | |
| $step_{out}$ | $[modelHash, dataMerkleRoot_1, outputMerkleRoot_1]$ | $[modelHash, dataMerkleRoot_2, outputMerkleRoot_2]$ | ... | $[modelHash, dataMerkleRoot_{N-1}, outputMerkleRoot_{N-1}]$ | $[modelHash, dataMerkleRoot_N, outputMerkleRoot_N]$ |
| private inputs | $[modelWeights, dataLeaf_0, merklePaths_0]$ | $[modelWeights, dataLeaf_1, merklePaths_1]$ | ... | $[modelWeights, dataLeaf_{N-2}, merklePaths_{N-2}]$ | $[modelWeights, dataLeaf_{N-1}, merklePaths_{N-1}]$ |

Improvements:
* less public inputs/outputs

Issues:
* order of data matters!
* relatively cheaper (than Attempt 3) if try to verify the entire tree on chain
* $2\log N$ number of hashes per step
* need to publish Merkle leaves elsewhere

#### Attempt 3: Recursive hashing?

| signals | Step 1 | Step 2 | ... | Step N-1 | Step N |
| -------------- | ---------------------------------------- | ----------------------------------------------------------- | ---------------- | -------------------------------------------------- | ------------------------------------------------ |
| $step_{in}$ | $[modelHash, 0, 0]$ | ... | $step_{out,N-2}$ | $step_{out,N-1}$ | |
| $step_{out}$ | $[modelHash, H(0, data_1), H(0, out_1)]$ | $[modelHash, H(H(0, data_1),data_2), H(H(0, out_1),out_2)]$ | ... | $[modelHash, H(...,data_{N-1}), H(...,out_{N-1})]$ | $[modelHash, H(..., data_1), H(..., out_{N-1})]$ |
| private inputs | $[modelWeights, data_1]$ | $[modelWeights, data_2]$ | ... | $[modelWeights, data_{N-1}]$ | $[modelWeights, data_N]$ |

Improvements:
* only 2 hashes per step
* less signals to pass around

Issues:
* order of data still matters
* very expensive to verify on chain, but luckily we can precompute and commit the final hash
* need to publish raw inputs elsewhere

### Scenario 2: Private Data, Public Model

#### Attempt 1: naive approach

| signals | Step 1 | Step 2 | ... | Step N-1 | Step N |
| -------------- | ----------------------------------------------------- | ------------------------------------------------------------------ | --- | --------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------- |
| $step_{in}$ | $[modelWeights,0,0,...,0,0,0,0,...,0,0]$ | $step_{out,1}$ | ... | $step_{out,N-2}$ | $step_{out,N-1}$ |
| $step_{out}$ | $[modelWeights,dataHash_1,0,...,0,0,out_1,0,...,0,0]$ | $[modelWeights,dataHash_1,dataHash_2,...,0,0,out_1,out_2,...,0,0]$ | ... | $[modelWeights,dataHash_1,dataHash_2,...,dataHash_{N-1},0,out_1,out_2,...,out_{N-1},0]$ | $[modelWeights,dataHash_1,dataHash_2,...,dataHash_{N-1},dataHash_N,out_1,out_2,...,out_{N-1},out_N]$ |
| private inputs | $data_1$ | $data_2$ | ... | $data_{N-1}$ | $data_N$ |

Issues: same as Scenario 1 Attempt 1

#### Solution: see Scenario 1 Attempt 3

Issues:
* we will need to publish the model weights elsewhere