# 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).

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up