# ZK Frontiers: Week 1 Exercises This week's exercises are hands-on coding exercises. Try writing the following circuits on your own. If you get stuck, you can check the solutions. We'll go over these circuits in the second Optional Session in Week 2. If you need to look up circom language features or syntax, take a look at the [circom docs](https://docs.circom.io/circom-language/signals/). I recommend trying to build these circuits in [zkREPL](zkrepl.dev), 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 treated as numbers modulo this big prime: ``` r = 21888242871839275222246405745257275088548364400416034343698204186575808495617 ``` This is a 254-bit prime known as the BabyJubJub prime. All addition, subtraction, and multiplication in circom is implicitly happening modulo `r`. For those interested in where this number comes from: `r` is the curve order for BN254, a pairing-friendly elliptic curve used by Ethereum and (formerly) ZCash. If you're very mathematically inclined, you can read more about BN254 in Jonathan Wang's excellent document [here](https://hackmd.io/@jpw/bn254). ### 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](https://github.com/iden3/circomlib/blob/master/circuits/bitify.circom#L25) ### 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](https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom#L24) ### 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](https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom#L37) ### 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](https://github.com/darkforest-eth/circuits/blob/master/perlin/QuinSelector.circom) ### 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)](https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom#L89) ### Extra Credit: 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](https://github.com/iden3/circomlib/blob/master/circuits/compconstant.circom), 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](https://github.com/iden3/circomlib/blob/master/circuits/sign.circom#L23) - **Understanding check**: Why can’t we just use LessThan or one of the comparator circuits from the previous exercise? ### Extra Credit: 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](https://github.com/darkforest-eth/circuits/blob/master/perlin/perlin.circom#L44) (ignore the second parameter SQRT_P; that is extraneous) ## Optional: Additional Understanding Questions If you want to check your understanding of ZK, try these questions from 0xPARC's [ZK Topic Sampler](https://learn.0xparc.org/materials/circom/prereq-materials/topic-sampler/). ### ZKP for 3-coloring Demo Visit http://web.mit.edu/~ezyang/Public/graph/svg.html and play around with the interactive demo. This is a programmatic version of the 3-coloring example we went over in class. - Answer Exercise 1 at the bottom of the page. ### Optional - ZKP for DLOG Implement a non-interactive ZKP for discrete log in code! To do this, you'll need to read and understand the first section of [this handout](https://people.eecs.berkeley.edu/~jfc/cs174/lecs/lec24/lec24.pdf), as well as the [Fiat-Shamir heuristic](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic). Specifically, you should implement: - a function dlogProof(x, g, p) that returns (1) a residue y, evaluated as g^x (mod p) and (2) a proof of knowledge pf that you know x that is the discrete log of y. - a function verify(y, g, p, pf) that evaluates to true if pf is a valid proof of knowledge, and false otherwise. The prover should only be able to compute a valid proof with non-negligible probability if they do indeed know valid x. If you need help, a reference implementation in Javascript with comments can be found [here](https://github.com/gubsheep/zk-beginner). This exercise may take you a few hours. For an additional challenge, try implementing a non-interactive ZKP for proof of 3-coloring as well! ### zkmessage.xyz This is a preview of Core Session 3. Create an account and post a message on [zkmessage](https://zkmessage.xyz), a zkSNARK-powered anonymous message board. - Explain why you need to generate and save a "secret" value. - Write out a plain-English explanation of what statement is being proven in ZK. - Log into the same zkmessage account, from a different browser or computer. Explain why zkmessage can't just use a simple "username/password" system like most social apps. If you're curious, we go much deeper into the construction of zkmessage [here](https://0xparc.org/blog/zk-group-sigs).
Last changed by  
 
gubsheep
384

Read more

ZK Frontiers: Week 3 Exercises

For this week's exercise, you will write a spec for one of the following proposed applications. If you are working on a project, you're automatically "exempt," as you'll already be building one of these! In your spec, you should: Outline precisely the ZK circuit(s) you'll be using. You can use our template from class if you'd like. Describe the business logic of the major components of the application: the server (what it stores, what it verifies, etc.) smart contracts (if applicable), clients (what they store, what they prove, etc.), and any additional services (for example, an auxiliary server that stores, verifies, and serves Merkle groups). WhaleChat

6/14/2023
ZK Frontiers: Week 2 Exercises

ZK Passwords In this exercise, you will implement a ZK-based password verifier! Instructions can be found in the README of the scaffolding repo. You are aiming to produce something that looks like this video demo. You can start with the scaffolding repo, or you can roll your own from scratch. If you use the scaffold repo, make sure to check out circom-starter, the base repo which this is based on! Extension: make proving happen in-browser. We’ll go over this during next week’s Monday optional session. You may also find this circom and snarkjs diagram useful.

6/6/2023
Zupass Resources for Developers

Zupass Official Repo: https://github.com/proofcarryingdata/zupass The README provides a starting point for devs. Usage Examples for Devs: https://consumer-client.onrender.com This page contains examples for devs on how to integrate Zupass into various application flows, such as authentication, proof generation/consumption. Code for these examples is in the official Zupass repo. Example Application: Zuzalu Confessions: https://confessions-client.onrender.com/ This is a fully-functional anonymous message board built on Zupass, demonstrating authentication and identity-hiding proofs. For development/demonstration/reference purposes only! Zuzalu Confessions Reference Code: https://github.com/proofcarryingdata/zuzalu-confessions

4/11/2023
Syncing Your Zuzalu Passport

The Zuzalu Passport is an app that lets you prove that you are a Zuzalu resident or visitor (using zero-knowledge cryptography!). You'll use it to access both digital and physical spaces at Zuzalu. For example, your Passport will generate a QR code that you can show on mobile, that can be scanned for access to Zuzalu co-working spaces. Your Passport also allows you to log into the Zuzalu website, to sign up for Zuzalu events. Once you've created your Passport, if you want to use your Passport on a device other than the one you first logged in on, you'll need to follow two easy steps. Step 1: Copy your Passport Key from your original device To do this, hit the settings icon in the top right-corner of the Passport app, and then tap "Copy Key for Sync."

4/7/2023
Read more from gubsheep
Published on HackMD