Implement `circomlib-mpc`

[brech1]

Implement our version of circomlib in order to support basic functions.

This is needed due to circomlib being done to work with R1CS, not working for execution.

[namnc]

circomlib has not been updated for 2 years, we can keep it as a submodule here and work on circomlib-mpc

[brech1]

• 13 has to be completed in order to do this task, since we can't test the circuits.

[voltrevo]

I'd love to get more into circom and help out with this issue. Can we put a list together of what "basic functions" we'd like to accomplish for this issue?

[namnc]

Sure, here's the thing. Within circomlib we can categorize the templates into 2 types: crypto and non crypto. Crypto = template for cryptographic primitives such as ECDSA or Poseidon. Non-crypto = template for scalar-based primitives such as comparators, sign, switcher.

For crypto type we have to wait for typing as we need to describe the computation in mod p. For non-crypto type we can divide the templates into two sub-categories as well: binary-based and arithmetic-based. Again the binary-based type we have to wait to typing as we need to describe the computation in mod 2. I think what is left for 0.1 is the arithmetic-based templates that are:

0. I think these need no change at all: mux1.circom ... mux4.circom and switcher.circom.
1. The following is a bit tricky https://github.com/iden3/circomlib/blob/cff5ab6288b55ef23602221694a6a38a0239dcc0/circuits/comparators.circom
   • template IsZero() --> straightforward, meaning we just write inside the template a comparison with 0, i.e. out <== (in == 0);
   • template IsEqual() --> straightforward in fact not need to change as it is now doing subtraction and also using IsZero for checking the result to be 0 or not;
   • (*) template LessThan(n) (and same goes for GT, LTE, and GTE) --> a bit tricky because now it passes n as an argument where n is the number of bits and inside it does bit decomposition using Num2Bits (component n2b = Num2Bits(n+1);) whereas in MPC we just need to do a subtraction and a sign check (using template Sign() in https://github.com/iden3/circomlib/blob/cff5ab6288b55ef23602221694a6a38a0239dcc0/circuits/sign.circom) where also the input is a bitvector of len 254.
   • same goes for https://github.com/iden3/circomlib/blob/cff5ab6288b55ef23602221694a6a38a0239dcc0/circuits/compconstant.circom

As we support equality check and also comparison in our interpreter, i.e. we just add a gate for the ==, <, >, <=, >= we can just scrap all of the comparators templates. If one write a new circom program for MPC then they can just use the ops directly.

The whole point of this issue is to allow one to run MPC with a circom program that was written for zk using the templates above (with the bit decomposition thingy). This issue presents two challenges:

• bit decomposition requires binary typing (0.2)
• comparator templates describe a low level method of doing comparison using binary representation of a number, we ideally want this to be done with our "translator"/"optimizer" from a circom-gate (front-end, intuitive such as LT, GT, EQ, etc. and back-end agnostic) to a native-gate supported by back-end (e.g. only NOT, XOR and AND), which means the comparator templates might not make use of the best of the back-end (e.g. EQ, LT, etc. are native in MP-SPDZ).

I don't know (if there is and what is) a clean way to solve this.

@voltrevo ^^^

[namnc]

I think we can push the tricky part to 0.2 (with typing so everything is natural).

[namnc]

This could be related, ZK vs MPC for division. Say we want to do a divided by b (a >= b) In MPC we just write q <== a \ b in ZK we write q <-- a \ b; r <-- a - b q; a === b q + r

My idea would be to wrap this in a template says template divide() with input a, b and provide a ZK and an MPC version and the interpreter should find the correct file to point to: For MPC we can have q and potentially r as an output (so we need also r <== a % b) For ZK we can have q as input and r as input and then do as above.

e.g. ZK version: https://github.com/socathie/circomlib-ml/blob/c82b3072d7946a76487a8c1be463fc407045391c/circuits/Dense.circom#L24 MPC version: https://github.com/namnc/circomlib-ml-patches/blob/master/circuits/Dense.circom.patch