Skip to main content

Circom Workshop 2

Description​

The second circom workshop: we dig deeper into a few key circuits such as zk-group-sig, isZero, and Num2Bits.

🔑 Group signatures are a cryptographic tool that allows members of a group to generate message signatures that proves their membership to the group without revealing which specific member they are. Group signatures are unforgeable (i.e. no one can sign a message on behalf of a group they are not part of) and provide cryptographic anonymity (i.e. no one in the group can identify which group member the signer is).

Pre-Session Reading/Setup​

Circom workshop #1 would be helpful as they build on each other.

https://docs.google.com/presentation/d/1H_Z8GlUi7_aPU2B8JVo9oH05ChOERjjsKDg6-4SnmXY/edit?usp=sharing

To check your understanding, we'd recommend trying to implement any of IsZero, IsEqual, Num2Bits, GreaterThan, QuinSelector, RangeProof, IsNegative, or Modulo by hand without just copy-pasting code from circomlib or references.

  • IsZero, IsEqual, Num2Bits, GreaterThan can be found in circomlib (comparators and bitify), and do what you'd expect them to do.
  • QuinSelector is a circuit that takes as input an array in[nElements], an index index, and outputs the value of in[index].
  • RangeProof is a circuit that takes in upper lower and test, outputs 1 if test is in the range and 0 otherwise.
  • IsNegative is a circuit that takes in an input, outputs 1 if input is negative and 0 otherwise. We define a convention: "Negative" is by convention considered to be any residue in (p/2, p-1], and Positive is anything in [1, p/2)
  • Modulo (hard) takes in a dividend and divisor, and outputs a quotient and remainder. it is acceptable to first range proof your dividend and divisor to be at most some large number (say 1e12), and assume that everything is positive.
  • QuinSelector, RangeProof, IsNegative, and Modulo can be found in the dark forest circuits repo https://github.com/darkforest-eth/circuits/tree/master/perlin

Check-in Questions​

(1) Implementing Group Signatures: In the GroupSig() Circom circuit:

  • Why does msgHash need to be accepted as an input signal?
  • What is the role of MiMC here?
  • How does the circuit provide cryptographic anonymity?

Fun Fact: Gubsheep adds a dummy msgHash^2 constraint at the end of the circuit. Adding an artificial square constraint to defend Groth16 proofs from replay attacks (i.e. reusing the same proof for different messages) has historically been a “best practice” — but alas this has been shown to be a popular urban legend! The dummy sqare constraint is not technically needed, so long as the mshHash is accepted as an input signal. Check out more in Geometry’s blog post!

/* I know the private key corresponding to 1 of 3 public keys */
template GroupSig() {
    signal input sk;
    signal input pk1;
    signal input pk2;
    signal input pk3;
    signal input msgHash;  // (a) why is this needed?
    
    // (b) pk generation
    component pkGen = MIMCSponge(1, 220, 1);
    pkGen.ins[0] <== sk;
    signal pk;
    pk <== pkGen.outs[0];
    
    // (c) constraints checking pk 
    signal interm;
    interm <== (pk - pk1) * (pk - pk2);
    interm * (pk - pk3) === 0;
    
    // fun fact! 
    signal dummy;
    dummy <== mshHash * mshHash;
}

(2) Under-constrained Circuits: The following circuit is meant to prove that a prover knows two non identity factors (factors that don’t equal 1) of the public input val. What constraint is currently missing from the circuit?

template NonIdentityFactors() {
    signal factorOne;
    signal factorTwo;
    signal val;

    val === factorOne * factorTwo;
}

component main{public [val]} = Factors();
Sample Answers

(1) Implementing Group Signatures: GroupSig() circuit:

  • mshHash needs to be accepted as an input signal in order to bound the group signature to the specific message that is posted (i.e. this proof is only valid for the inputted message). Otherwise, the proof could be valid for any arbitrary message (called a ‘replay attack’) because we are not committing to the message in any way in the circuit itself.
  • MiMC (a SNARK-friendly hash) is used to derive the corresponding public key from the provided secret key.
  • We subtract the generated pk from each provided pk because we want to hide which pk the sk corresponds to.

Check out the 0xPARC zk-group-sigs blog post to read more!

(2) Under-constrained Circuits: The circuit is under-constrained because there is no constraint forcing the prover to use values other than 1 for factorOne or factorTwo. Thus, the prover could use (1, val) as inputs (which are not valid non-identity factors of val) and still produce a proof accepted by the verifier. In other words, the proof would be valid even though it shouldn’t be. This is why it is very important to check that your Circom code is correctly and exactly modeling all constraints in the problem you want to check. Check out the 0xPARC bugtracker tool for more!

Learning Group 1 lecture video and slides for reference.