Modern ZK Crypto - Session 1 Exercises

# Modern ZK Crypto - Session 1 Exercises Today's exercises are mostly taken from this [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 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).