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 element is 126 in Circom. Therefore, if we want to have 128 bits security strength as mentioned previously, we need to have a modulus size of 6144 bits. For Paillier, as the modulus is the square of the key size (the product of two prime numbers), which needs to be 3072 bits to achieve the 128 bits security strength. If the number of bits in a field element can only be up to 126, that means we will need 25 elements in the field elements array to represent a keysize that is at least 3072 bits.

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). The carbon emissions prototype circuits with the Paillier encryption added were compiled, and the circom compiler reported that it has ~142 million constraints (as shown below). The trusted setup required to kick off the zkSNARK system, which uses the Groth16 protocol, will therefore have to be able to support up to 2^28 constraints, which is the maximum snarkjs can support currently. The high number of constraints causes the Powers of Tau ceremony for the trusted setup to take a very long time (days!). However, I could not even complete the experiment with a keysize bigger than 1000bits on my laptop, as it doesn’t have enough memory to carry out the trusted setup and proof generation.

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 provided customer share was correctly encrypted, and then 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 using the Paillier cryptosystem. If we can find a way to prove that within a SNARK proof, without having to input the data of every customer at once (a data centre could potentially have thousands or even millions of customers!), then we won’t need to apply the Paillier cryptosystem at all.

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

Circom does not support recursion, so for the past couple of weeks I have been experimenting two different methods: 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. zkVM provides a virtual environment that generates zk-proofs, abstracted away the complexity of circuit logic and provides a more developer-friendly language (e.g. Rust) to write circuits. Within the last five or six years there has been lots of effort to improve the performance of zkVM.

It would be very interesting to see the results from these two methods!

I tried the o1js framework first. First impression was already a win from my experiment with Circom. I am able to express my circuits within a few lines, and the readily available modules are sufficient for me to write the same emissions proof prototype. With the support of recursion, I am now able to do the customer share additions one by one in each proof, and then verify the final output from the recusive proof is indeed a 100.

Right now I am trying to learn about RiscZero and SP1. So far RiscZero’s protocol and framwork makes more sense to me, with SP1 it has abstracted the zero-knowledge proving part so much that it is quite difficult to express my intention using their framework. It is very much designed for writing proofs that can be deployed to smart contracts.

In terms of performace, initial observation (without measurements) is that they take substantially more compute power and time to generate a proof. Verification is still very fast and small.

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

[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)