# notes on zero knowledge proofs

**Published by:** [rw](https://paragraph.com/@rw-2/)
**Published on:** 2021-11-02
**URL:** https://paragraph.com/@rw-2/notes-on-zero-knowledge-proofs

## Content

ty to ember 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 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? 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 zero-knowledge interactive proofs schnorr: basis of schnorr signatures sigma protocol — 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 instead of sending c (verifier sending a random number in the interaction) uses hashes c = hash of the transcript of the protocol 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 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? 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 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/ 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 PLONK stark-ish PLONK uses “Kate commitments”

## Publication Information

- [rw](https://paragraph.com/@rw-2/): Publication homepage
- [All Posts](https://paragraph.com/@rw-2/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@rw-2): Subscribe to updates