Implement circomlib-mpc 0.1

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

• Implement ArithmeticCircuit evaluation #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

[brech1]

So should we perhaps split this issue or keep this one for the 0.1 release (with @voltrevo assigned) and then create a new one for later versions?

[namnc]

Makes sense, once we have the good integration this should proceed faster.

[namnc]

Changed to ciromlib-mpc 0.1