# notes on zero knowledge proofs By [rw](https://paragraph.com/@rw-2) · 2021-11-02 --- ty to [ember](https://mmou.github.io/) for the casual talk / discussion!!! / zero knowledge proofs * prove you know something w/o having to reveal what that something is * applications: * private transactions, anonymous voting ![](https://storage.googleapis.com/papyrus_images/8ff0e39d0b441f0be30e3eb65e6e3528bf7a5d33c916a4bee9ab130d9a27e50e.png) * proof systems * prover and a verifier * prover gives verifier a proof * define R(): a relation fun * takes a public set of parameters, called x, and a solution/witness called w * solution is private * the parameters are public (x) * proof system needs to satisfy properties: * 1 - complete * i.e. if w is valid solution, R = 1 * verifier needs to accept the proof * (completeness: if r is valid, verifier accepts the proof) * 2 - soundness * if w is not a valid solution, verifier should reject with high probability * ?: why high probability * in cryptography — information theoretic security * mathematically impossible to find the value * but what makes cryptography practical / performant / usable for us — we state security in terms of probabilities * it’s secure if it’s very hard for attacker to distinguish or retrieve something * 3 - knowledge soundness property * if verifier accepts the proof, that must mean the prover must know what the solution (w) actually is * 4 - optional: zero knowledge * the proof reveals nothing about w (the solution) * analogy: * R is the rules of sudoku * x is a particular puzzle instance * w is a solution for that sudoku puzzle * so: R(x,w) = 1 * proving knowledge of an assignment * arithmetic circuit * turning an equation into a graph * how to represent instance / problem the witness/solution is solving? ![](https://storage.googleapis.com/papyrus_images/e6732f973a16ca8b5f4f0491e93d32e76e1ad789c767c47a8195cb2f2451a3a7.png) * examples of how to represent problems in this format: (arithmetic circuits) * e.g. range proof - can represent as polynomials * e.g. verifiable shuffle - prove permutations * range proof in transactions * want to prove that the exchange equals out (not creating/destroying money) * need to prove that the amount is >=0 * use polynomials ![](https://storage.googleapis.com/papyrus_images/5db52f45a9477b5f0dd3445305fcdd9a935947c223fd004e345e849bc14e3dcd.png) * zero-knowledge interactive proofs * schnorr: basis of [schnorr signatures](https://en.wikipedia.org/wiki/Schnorr_signature) * [sigma protocol](https://en.wikipedia.org/wiki/Proof_of_knowledge#Sigma_protocols) — a set of proof of knowledge that greeks invented * i have a secret key * want to reveal that i have a secret key w/o revealing the key * show it to another person by providing a signature with the key * steps: \*\*\* * alpha is secret key, prover want to prover they know alpha * Y = alpha \* G * Y is public key * alpha is the secret key * 1 - R is commitment. R = r \* G * r is random scalar in this group * G is a generator of the group * when you multiply r\*G you get a public key, basically. a public commitment to that secret value * 2 - verifier generates a random scalar, c * 3 - prover computs s = r + c \* a * 4 - verifier checks: * s \* G = R + c \* Y * if equal, then verified * “discrete logs are hard” * schnorr proof of knowledge * using [fiat-shamir](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) * instead of sending c (verifier sending a random number in the interaction) * uses hashes * c = hash of the transcript of the protocol ![](https://storage.googleapis.com/papyrus_images/8d8dbea56e77468d437f652af26269f864508482874c82c7ed42ac4a68eb2eb5.png) * steps: * same but: * we replace verifier sending c * c <- H(Y, R) * by sending the hash instead of generating a c, * c is “basically random” * hash — you know that the person on the other side can’t choose an incorrect value * fiat shamir transform — same property * result: prover can just send everything in one message * sigma protocol: s looks like the “back and forth” lol * you just send over s because you know all the other values * you both agree on H already so you can send all the values over in one interaction * fiat-shamir transform * original proof should be a public-coin proof * the random numbers being sent are public * allows for interactive -> non interactive * succinct NARGs -> zkSNARKS * succinct * an argument is only sound against computationally bound provers * how to make succinct? * PCP theorem + merkle trees * idea: turn everything into polynomials * zkSNARKS * hard part is succinctness * 1 - turn problem into polynomials * 2 - how do we prove that two polynomials are equal? * [schwartz-zippel lemma](https://zeroknowledge.fm/the-missing-explanation-of-zk-snarks-part-1/) * two polynomials that are different, are different in most places * two different polynomials of degree 1 intersect in at most 1 point * two diff polynomials of degree 2 intersect in at most 2 points * two different polynomials of degree n can intersect in at most n points * how to turn a problem into a set of polynomials you can input into zksnark? ![](https://storage.googleapis.com/papyrus_images/6d5d621027fd18a575c3baf88db7ccc1fa8acf7b2833fb21d7dc07d3daf21dd8.png) * kind of a grind lol * rank 1 constraint system (R1CS) representation of circuits * an equation of matrices in this form * Quadratic Arithmetic Program (QAP) - represent arithmetic equations * trusted setup: for ZKPs, some have trusted set up and some don’t * a result of doing a trusted setup, it can speed up the subsequent verifications * the fastest ZKPs today still require trusted setup * zkSTARKS: don’t require trusted setup * zcash: [ceremony](https://www.wnycstudios.org/podcasts/radiolab/articles/ceremony) * downside of trusted setup: requires trusting someone to do the setup * zcash: there’s “toxic waste” — but failed to throw away something “toxic” that allowed ppl to double-spend counterfeit money * [https://electriccoin.co/blog/zcash-counterfeiting-vulnerability-successfully-remediated/](https://electriccoin.co/blog/zcash-counterfeiting-vulnerability-successfully-remediated/) * need to generate parameter w certain properties * an intermediate of that process — that data can allow you to break the privacy guarantees of the system * should be thrown away — but if you have the intermediates, that lets you break the system * trusted setup: * 1 - five ppl do diff parts on diff computer * 2 - organized a mailing list and allowed anyone join the trusted setup, w the idea that if anyone is honest and throws away their thing, then you can’t break the system * limited set of ppl: each sets up a part of public and private key pair. everyone destroys the private keys at the end * but they kept some transcript value in the output/typo in the original paper. a lot of implementations just followed the paper * CRS: common reference string. output of the trusted setup, used in the subsequent proofs * ?: how often do u have to do this trusted setup? * depends on the proof system * some proof systems require trusted setup, per transaction * others are trusted setup but transparent (zkSTARKs) and updatable * ppl can keep adding themselves to the trusted setup? * examples * constructions of zk proof systems: * e.g. zksnarks, bulletproofs, zkstarks, PLONK, halo, grof * considerations: proof size, prover work, verifier work, post-quantum, trusted setup * ?: how big of a concern / soon is quantum computing? * discrete log problem — a lot of crytpography depends on this being hard * schnorrs algorithm — a quantum computer would make it easy to solve the discrete log problem * so if we have quantum computers fast enough, all these systems would be broken * how many qubits … how powerful does a qcomp need to be for cryptographic consideration? * 100? 1000? qubits? * e.g. bulletproofs — rely on discrete log problem * very fat * but not post-quantum resistant * e.g. sha3 * algorithms are not post quantum safe * some standards / working groups consider it when choosing a standard paik? algorithm * depends on the problem … the nature/scale … security assumptions, if the trade off is worth the extra complexity for post quantum resistance * e.g. penumbra ![](https://storage.googleapis.com/papyrus_images/5051dbbffb96073de073e9da553f3b210750d86e5fa287fc26ee0bbf06fbbbd4.png) ![](https://storage.googleapis.com/papyrus_images/5320a36940316242ea5f46b6514f64a9cfda9adc91333301ca798def880ce14a.png) * [PLONK](https://vitalik.ca/general/2019/09/22/plonk.html) * stark-ish * PLONK uses “Kate commitments” --- *Originally published on [rw](https://paragraph.com/@rw-2/notes-on-zero-knowledge-proofs)*