Fun with recursion

Following on from the previous blog post regarding the prototype I built to generate carbon emissions proofs, I found out that the maximum number of bits that can be packed into a field array is 126 in Circom. Therefore, if we want to have 128bits security strength as mentioned previously, we need to have a modulus size of 3072bits. For Paillier, as the modulus is the square of the product of two prime numbers, the key size (the product of two prime numbers) is therefore 1536bits (i.e. 768bits primes). If the number of bits in a field array can only be up to 126, that means we will need 13 elements in the field array to represent a keysize that is at least 1536bits.

It is also not a straightforward task to write the Paillier encryption in circuits, instead of a basic exponentiation computation (the randomness number r needs to be raised to the power of the key, n) by calling something like r**n and let the compiler/runtime engine deals with the rest, the circuit needs to include r**n as part of the proof and hence reduce it to “Rank-1 Constraints Satisfaction” (R1CS) system (there are other interpretation to what ‘S’ stands for, e.g. System, Satisfactory). In R1CS the algebraic circuits are expressed as a set of vectors and matrices, which in turn are converted to a set of polynomials to be used for the rest of the zkSNARK pipeline. So how do you express r**n as algebraic circuits in the first place?

At first I tried the naive approach and simply created a loop (Circom supports loops) for r to multiply itself n times. This turned out to have very bad performance. Then, with my supervisor Martin’s help, I was able to apply the Square and Multiply method into a Circom circuit, which makes it way more performant. The circuit looks like this:

However, it is still too big (in terms of the number of constraints). With that many constraints (~142 million), the trusted setup required to kick off the zkSNARK system, which uses the Groth16 protocol, will have to be able to support up to 2^28 constraints, which is the maximum snarkjs can support currently. With this size it takes a very long time to complete the Powers of Tau ceremony for the trusted setup (days!). I cannot complete the full experiment with a keysize bigger than 1000bits on my laptop anyway, as it doesn’t have enough memory to carry out the trusted setup and proof generation. The circom circuit did compile though (took about 20mins):

non-linear constraints: 142769486
linear constraints: 0
public inputs: 28
private inputs: 65
public outputs: 1
wires: 141986048
labels: 149556141
Written successfully: ./emissions_proof.r1cs
Written successfully: ./emissions_proof.sym
thread 'main' panicked at code_producers/src/wasm_elements/wasm_code_generator.rs:9:5:
the size of memory needs addresses beyond 32 bits long. This circuit cannot be run on WebAssembly

So, the experiment with Circom didn’t feel satisfactory because of the Paillier encryption. Taking a step back, the Paillier encryption was added to prove that the customer shares were correctly encrypted, and outside of zkSNARK we can verify that all customers’ shares reported by the data centre operator add up to a 100% of the total power usage by using Paillier cryptosystem. If we can find a way to do the same prove within zkSNARK but without having to input the data of every customer in a single proof, then we don’t need to apply the Paillier cryptosystem at all.

One way to do it is through recursive SNARK[1]. The input to a proof can be limited to one customer share at a time and we add each share to the previous one recursively. Through enough recursive steps to go through the whole customer base, the final proof's output should be 100!

Circom does not support recursion, so I have been experimenting two other approaches: one is to use a framework called o1js, a TypeScript library provided as part of the Mina blockchain protocol, created and maintained by O(1)Labs and Mina Foundation; another one is to use a zkVM, e.g. RiscZero, SP1 and Jolt[2]. zkVM provides a virtual environment that generates zk-proofs, abstracted away the complexity of writing circuits and provides a more developer-friendly language (e.g. Rust) for writing circuits. There has been a lot of effort to improve the performance of zkVM, especially within the last five or six years.

I tried the o1js framework first. First impression was already a win comparing with my Circom experiment. I was able to express my circuit within a few lines of code, and the readily available modules are sufficient for me to write the same emissions proof. With the support of recursion, I was also able to add customer shares one after another in each proof. The final output from the recusive proof can be verified by comparing it with a known value - 100.

I am still trying to learn RiscZero and SP1. So far RiscZero’s protocol and framwork makes more sense to me. SP1 seems to have abstracted the zero-knowledge part so much that it is quite difficult to express my circuit. It is designed for verifiable proofs deployed on blockchains and smart contracts.

In terms of performace, initial observation (without measurements yet) is that the zkVMs take substantially more compute power and time to generate a proof comparing with o1js. Verification is still very fast and small though.

I will write more about these experiments and results in future blogs. For the next blog though, I think I will go back to why I am trying to use zkp and explore the use cases more.

[1] Bitansky, N., Canetti, R., Chiesa, A. and Tromer, E., 2013, June. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing (pp. 111-120)

[2] Arun, A., Setty, S. and Thaler, J., 2024, April. Jolt: Snarks for virtual machines via lookups. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 3-33). Cham: Springer Nature Switzerland