How to optimize my circuit? (and avoid Terminated messages)

[drakstik]

Context

Hi!

I've noticed that with enough API calls, we receive a Terminated message at some point. I'm assuming this happens because in my circuit definition I have a couple of loops that have API calls in them, and as I increase the number of times the loop iterates, I get a Terminated message.

My Question

How can one go about "optimizing" their circuit in order to avoid the Terminated message?

ChatGPT suggests I should create "subcircuits" so the API calls are distributed across more circuits, but I'm not sure if ChatGPT is correct here. In my previous question about a small modulo function #1362, the answer uses the test package (https://pkg.go.dev/github.com/consensys/gnark/test) to run small modulo as its own circuit, should I be doing this same thing inside my circuit using the WithValidAssignment option? But then how can I get the quotient and remainder as frontend.Variable, since I need them later? I have to assign the subcircuits on the fly and get a result from them. At the very least I should receive a Boolean from the subcircuit because at the end of the forloop I use the api.Select() function.

Thank you and I hope my question makes sense, I'm still getting used to the language of coding with zk-SNARK circuits.

[ivokub]

It may be indeed, we have optimized some defaults so that the circuit compilation wouldn't take that much memory, but for large circuits you would need tens of GB of memory. Do you have an example circuit? What are the parameters of the machine you are compiling the circuits on?

[drakstik]

Hi!

I'm working on this circuit: https://github.com/drakstik/PhotoGnark_V0/blob/main/src/circuits/cropCirctuit.go

You can run main.go to test it out. Essentially, we have an original, secret 2D array of pixels N*N, which is an image, represented as a 1D array of pixels. In the circuit, I crop the original image according to some cropping parameters and move the remaining pixels to the top left, then assert that a given other image is a cropped version of the secret original image.

You can change the N global variable to see what I'm talking about (see the N global variable here: https://github.com/drakstik/PhotoGnark_V0/blob/main/src/image/image.go). When N is low, the circuit works, when it is higher (for me it maxes out at 14) then eventually you get a Terminated message. I am running 32GB RAM.

Thank you for your help!

[ivokub]

I was testing your circuit and it seems the size of the circuit is approximately 20000 + N^2 * 30000. So for N=14 the circuit size would approximately be 5.9M constraints. Should be doable with 32GB ram, but barely (I had the ram usage at 23GB at some point but then terminated myself). If the circuits would be bigger, then it would relatively increase possibly above the 32GB limit. Swap doesn't help much as then the prover would become unbearably slow.

I would instead try to see why the circuits are that large, I guess there is room for improving the performance. We have profiling tool which allows to introspect the cost per source code line. At compile time you should run the profiler:

diff --git a/src/circuits/generator.go b/src/circuits/generator.go
index 4f0a613..779fdc8 100644
--- a/src/circuits/generator.go
+++ b/src/circuits/generator.go
@@ -12,6 +12,7 @@ import (
        "github.com/consensys/gnark/backend/groth16"
        "github.com/consensys/gnark/frontend"
        "github.com/consensys/gnark/frontend/cs/r1cs"
+       "github.com/consensys/gnark/profile"
 )
 
 type Keys struct {
@@ -57,10 +58,12 @@ func Generator(max_image_size int, security_parameter *big.Int) (Keys, Keys, err
        //------------- Compiling Crop Transformation Keys ------------------------
 
        // Set the security parameter (BN254) and compile a constraint system (aka compliance_predicate)
+       p := profile.Start(profile.WithPath("crop.pprof"))
        compliance_predicate_crop, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &CropCircuit{})
        if err != nil {
                return Keys{}, Keys{}, err
        }
+       p.Stop()
 
        // Generate PCD Keys from the compliance_predicate
        provingKey_crop, vk_crop, err := groth16.Setup(compliance_predicate_crop)

and then view the profile with

go tool pprof -http=":" crop.pprof

[ivokub]

For example, looking at the profile you see

that a lot of constraints come from api.Cmp call. And it makes sense - the comparison performs bitwise decomposition of the inputs which results in possibly 500 constraints per operation. If you would instead use https://pkg.go.dev/github.com/consensys/gnark@v0.11.0/std/math/cmp#BoundedComparator with a better bound (a la N) then it could significantly reduce the circuit size.