What exactly Circom circuit constraint a*b proves?

Question

I use this circuit as per official documentation:

pragma circom 2.0.0;

/*This circuit template checks that c is the multiplication of a and b.*/  

template Multiplier2 () {  

   // Declaration of signals.  
   signal input a;  
   signal input b;  
   signal output c;  

   // Constraints.  
   c <== a * b;  
}

and feed the following input file (input.json):

{"a": "3", "b": "11"}

Then compile and generate witness/proof, and verify:

circom multiplier2.circom --r1cs --wasm --sym --c

node generate_witness.js multiplier2.wasm input.json witness.wtns

snarkjs powersoftau new bn128 12 pot12_0000.ptau -v
snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="First contribution" -v
snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v
snarkjs groth16 setup multiplier2.r1cs pot12_final.ptau multiplier2_0000.zkey
snarkjs zkey contribute multiplier2_0000.zkey multiplier2_0001.zkey --name="1st Contributor Name" -v
snarkjs zkey export verificationkey multiplier2_0001.zkey verification_key.json
snarkjs groth16 prove multiplier2_0001.zkey witness.wtns proof.json public.json
snarkjs groth16 verify verification_key.json public.json proof.json

It tells:

[INFO]  snarkJS: OK!

The documentation says it proves that I know factors of 33. But I don't input 33 anywhere, moreover I get the same result if I change the circuit to:

template Multiplier2 () {  

   // Declaration of signals.  
   signal input a;  
   signal input b;  
   signal output c;  

   // Constraints.  
   c <== a * b * -1;  
}

The question how I prove that I know factors of 33 if I don't input 33 anywhere?

Salford

Answer 1

The way this proves you know the factors of "33" is that you have verifiably computed the multiplication circuit with inputs a and b, and have resulted in finding 33. Since a and b are not declared to be public, they are kept secret from the verifiers. So, when your proof is verified, it tells the verifier "whoever generated this proof, indeed provided factors a and b to obtain 33, so they must know the factors of 33".

You should see 33 in public.json as the comment says. I think the huge number you see there is the result of 3 * 11 * -1, because a negative number is represented with some other positive number in the finite field.

Alternatively, you could input 33 as a public input c and write c === a * b, which would essentially be the same thing as far as I know. I would prefer outputting the value rather than doing this though.

One more thing: notice that you could have generated a proof using a=1 and b=33, which would still be valid for this circuit although you wouldn't know the factors. That is a soundness problem! You could introduce additional constraints to ensure that inputs are not equal to 1 and such.

Gobbet

Answer 2

The public.json file includes 33. If you change it, the verification will fail.

Congregationalist

Hmm, I looked into public.json, there is some strange data: [ "21888242871839275222246405745257275088548364400416034343698204186575808495584" ] – Salford

Wow!! Based on its length, it seems that it should be part of either the proof key or the verification key! Could you please let me know the content of input.json file? – Congregationalist

input.json {"a": "3", "b": "11"} – Salford

Answer 3

input.json contains private signal(s), meanwhile the public.json contains the output users of circuits have to prove.

In particular, using the multiplier2, we will prove that we are able to provide the two factors of the number 33. That is, we will show that we know two integers a and b such that when we multiply them, it results in the number 33.

https://docs.circom.io/getting-started/proving-circuits/

ZK proofs are essentially signatures which require knowledge of a value satisfying a specific function in order to generate correctly (so they prove knowledge of the value); however, they do not reveal these values to any validator (so they are zero-knowledge). Surprisingly, ZK proofs can be constructed for any computable function.

Seldon