An idea for simplifying complex circuit components

[aybehrouz]

Hi
I've written a short text about an idea for simplifying components that have a large circuit complexity. I'm not sure if I've explained it well and I don't know if my idea is anything useful. 😅

I'd be more than happy if you take a look and possibly give me some feedback:

https://github.com/aybehrouz/argennon/blob/main/pdf/Selected.pdf

[ivokub]

Hi I've written a short text about an idea for simplifying components that have a large circuit complexity. I'm not sure if I've explained it well and I don't know if my idea is anything useful. 😅

I'd be more than happy if you take a look and possibly give me some feedback:

https://github.com/aybehrouz/argennon/blob/main/pdf/Selected.pdf

So on the high level, do I get the idea correctly. Lets say there is a sub-component of a circuit (f) which takes k input variables and outputs k output variables. Lets say that cost of computing f is N*k constraints in-circuit. Instead of computing f in-circuit, we instead construct a circuit which computes only f only and hashes of in_1, ..., in_k, out_1, ..., out_k (and the hash is also part of witness). Then, in the "main" circuit we only check the hash only instead of computing f. If we separately verify the new circuit (f and digest of inputs/outputs), then the combination (main circuit with f replaced with digest + new circuit) is sound and the prover complexity is smaller.

I think the idea in general works, but there is a big caveat -- computing hashes in-circuit is really expensive (think at least 300 constraints per input for SNARK-friendly hashes). So if approximately N > 2 * 300, then it is beneficial to use your idea, otherwise it is cheaper to compute f in-circuit. There are more considerations though -- at some point we do FFTs (which have complexity m log(m)), so checking two proofs may be better, but there is some overhead involved, so it isn't that straightforward.

We recently added a cheap way of computing a Pedersen commitment over variables in-circuit (see frontend.Compiler.Commit()), which can essentially be used as a hash function, but the base for Pedersen commitment depends on the underlying circuit and using it to connect two circuits is difficult.

[ivokub]

Oh, and we have the commitment only for Groth16 for now.

[aybehrouz]

Thank you so much for your feedback. I'm so sorry, I think I've really explained it very poorly. Please let me explain it in a different way:

Assume we have a state transition function T which defines our state transition T(S_i) := S_{i+1}. We need to verify that a state transition from S_0 to S_n is produced by our state transition function. Therefore, we need to verify that a sequence of states: S_0, S_1, S_2, ... , S_n can be generated by T. We assume that T can be defined by a set of sub-components. Each component is a function and based on the input state a number of these sub components are activated and each one produces a part of the next state.

For example, say T is defined by three sub-components f,g and h. At each state, based on some properties of the input state, only one of these sub-components gets activated and produces the next state based on the previous state. I've assumed (I'm not sure this assumption is correct) that the circuit for this problem is something like this:

       [ f ] \                          [ f ] \
S_0 -> [ g ] -- [Multiplexer] -> S_1 -> [ g ] -- [Multiplexer] -> S_2 -> ...
       [ h ] /                          [ h ] /  

Now let's say that f is a complex sub-component and it will be active only for 2 state transitions. (of course we can't say which two transitions unless we generate the trace). However, its circuit is repeated for n times. We want to replace it with a simpler circuit and at the end in a simpler circuit we repeat f only for two times.

Here is a subtlety. f is NOT essentially a memory-less (state-less) component. Also note that it is not active in every step and it will not see every state. Let's say it is active in states: S_12 and S_210, if we want to represent it as a mathematical function we have to denote it with something like this f((S_12, S_210)) := (S_13, S_211).

I'm not sure but I think we can assume that the complexity of f is N (not N*k) and if N > 2*300 and f is only used in a few steps the method may work.

[aybehrouz]

I mean, in_1, in_2, .... , in_k are actually inputs to f at different computation steps.

[aybehrouz]

I also updated the pdf file and tried to fix it and explain the idea more clearly.