Modern ZK Crypto - Session 2 Exercises

Today's exercises are hands-on coding exercises. Try writing the following circuits on your own. If you get stuck, you can check the solutions.

If you need to look up circom language features or syntax, take a look at the circom docs. I recommend trying to build these circuits in zkREPL, for fast iteration.

I recommend doing these exercises in order, as later circuits may build on previous ones.

References

Field Size

All signals in circom are field elements in the prime field of order

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

This is a 254-bit prime known as the BabyJubJub prime. It's the curve order for BN254, a pairing-friendly elliptic curve used by Ethereum and (formerly) ZCash. You can read more about BN254 in Jonathan Wang's excellent document here.

Recommendations and Common Issues

If you are testing your circuits using zkREPL's input comment functionality (particularly if you are using negative numbers), be aware that you'll need to surround numbers in quotations marks, and you'll need to write them as non-negative residues. This is due to the interpretation of the signal input JSON as a Javascript object, with biginteger values.

For example, testing an input signal x with the value -1 should look like this:

"x": "21888242871839275222246405745257275088548364400416034343698204186575808495616"

Forgetting these quotation marks is a common source of failing tests.

Exercises

Num2Bits

• Parameters: nBits
• Input signal(s): in
• Output signal(s): b[nBits]

The output signals should be an array of bits of length nBits equivalent to the binary representation of in. b[0] is the least significant bit.

Solution

IsZero

• Parameters: none
• Input signal(s): in
• Output signal(s): out

Specification: If in is zero, out should be 1. If in is nonzero, out should be 0. This one is a little tricky!

Solution

IsEqual

• Parameters: none
• Input signal(s): in[2]
• Output signal(s): out

Specification: If in[0] is equal to in[1], out should be 1. Otherwise, out should be 0.

Solution

Selector

• Parameters: nChoices
• Input signal(s): in[nChoices], index
• Output: out

Specification: The output out should be equal to in[index]. If index is out of bounds (not in [0, nChoices)), out should be 0.

Solution

IsNegative

NOTE: Signals are residues modulo p (the Babyjubjub prime), and there is no natural notion of “negative” numbers mod p. However, it is pretty clear that that modular arithmetic works analogously to integer arithmetic when we treat p-1 as -1. So we define a convention: "Negative" is by convention considered to be any residue in (p/2, p-1], and nonnegative is anything in [0, p/2)

• Parameters: none
• Input signal(s): in
• Output signal(s): out

Specification: If in is negative according to our convention, out should be 1. Otherwise, out should be 0. You are free to use the CompConstant circuit, which takes a constant parameter ct, outputs 1 if in (a binary array) is strictly greater than ct when interpreted as an integer, and 0 otherwise.

Solution

• Understanding check: Why can’t we just use LessThan or one of the comparator circuits from the previous exercise?

LessThan

• Parameters: none
• Input signal(s): in[2]. Assume that it is known ahead of time that these are at most
  $2^{252}-1$.
• Output signal(s): out

Specification: If in[0] is strictly less than in[1], out should be 1. Otherwise, out should be 0.

• Extension 1: If you know that the input signals are at most 2^k - 1 (k ≤ 252), how can you reduce the total number of constraints that this circuit requires? Write a version of this circuit parametrized in k.
• Extension 2: Write LessEqThan (tests if in[0] is ≤ in[1]), GreaterThan, and GreaterEqThan

Solution (with extension 1)

IntegerDivide

NOTE: This circuit is pretty hard!

• Parameters: nbits. Use assert to assert that this is at most 126!
• Input signal(s): dividend, divisor
• Output signal(s): remainder, quotient

Specification: First, check that the dividend and divisor are at most nbits in bitlength. Next, compute and constrain remainder and quotient.

• Extension: How would you modify the circuit to handle negative dividends?

Solution (ignore the second parameter SQRT_P; that is extraneous)