## Zero-Knowledge Proofs An introduction (=° ω°)ﾉ ---===≡≡≡ X Ivan J. ## What are ZK proofs? * Crypto protocols allowing a prover to prove they have some knowledge of a certain kind, without revealing additional information about that knowledge. #pause * "I know a secret key, and this is how I want to spend my bitcoins" (Digital signature) ## What are ZK proofs? * Camenisch-Stadler notation: π{(w): L(w, x)} #pause * x => "The statement" - Public information, known to the prover and verifier #pause * w => "The witness" - Secret information, known only to the prover and kept hidden from the verifier. #pause * L => "The language" - Condition that the statement and witness have to satisfy #pause "I know a witness w such that the predicate L(w,x) holds for w and x." ## Preliminary - Fields * A fundamental component of many crypto protocols is an algebraic structure known as a "field". * Fields are sets of objects (numbers) with two associated binary operators: + and ×. #pause * If 𝔽 is a finite field, it contains |𝔽| = pᵏ elements for some integer k≥1, and some prime p. * This means that in a finite field, all operations are done modulo p * Whenever we write 𝔽ₚ, we are referring to a prime field which has a prime p number of elements, i.e. k=1. ## Preliminary - Elliptic Curves y² = x³ + ax + b private key | P = x * G ------- Generator | public key #pause EC points are homomorphic: P = (x + y)G = xG + yG ## Sigma protocols for knowledge of discrete log Protocol for the proof scheme π{(x): xG = P} where G is the generator of a finite field 𝔽 of prime order p. ## Sigma protocols for knowledge of discrete log Prover(x, P = xG) Verifier(P) #pause $ k ← 𝔽ₚ #pause K := kG #pause K // Commitment --------------------> #pause $ c ← 𝔽ₚ #pause c // Challenge <------------------- #pause s := k + cx #pause s // Response -------------------> #pause sG ≟ K + cP ## Sigma protocols for knowledge of discrete log Using a random oracle assumption, we can make the proof non-interactive by replacing the challenge with a hash of the commitment. #pause Prover(x, P = xG) Verifier(P) #pause $ k ← 𝔽ₚ #pause K := kG #pause c := H(K) #pause s := k + cx #pause (K, s) // Proof -------------------> #pause sG ≟ K + P*H(K) #pause This trick is known as the "Fiat-Shamir" transformation. ## Schnorr Signature We can easily modify this ZK scheme to use as a digital signature. The idea is simply to include a message m into the challenge hash so it becomes H(K||m). #pause Prover(m, x, P = xG) Verifier(P, m) $ k ← 𝔽ₚ K := kG c := H(K||m) s := k + cx (K, s) // Proof -------------------> sG ≟ K + P*H(K||m) ## Expanding concepts When we do s = k + cx, c is what we call an "independent variable". * We are able to use powers of c to separate values. * K + cK + c²K + ... #pause * P = (x + y)G = xG + yG * Now there are two commitments, R = kG, S = lG * Prover: s = k + cx, t = l + cy * Verifier: sG + tG ≟ R + S + P #pause * We had the proof: π{(x): xG = P} #pause * Now we have: π{(x, y): (x + y)G = P} which is additive #pause * For Pedersen Commitments (which are a type of homomorphic encryption) we can do P = xG + yH, where G and H are generators, and y is a blinding factor for our secret x. ## Pedersen Commitments Commitments to values without revealing them or being able to change. P = xG <= vulnerable to bruteforce #pause P = Commit(x) Commit(x) = xG + rH (where rH is randomness) #pause 1. Commits to x => must know x #pause 2. Homomorphic: Commit(x) + Commit(y) = Commit(x + y) (xG + r₁H) + (yG + r₂H) = (x + y)G + (r₁ + r₂)H ## Expanding concepts * Using the simple Groth Inner Product Proof, we can get multiplication and with that, we have a complete ZK proving system. * Basically a Schnorr proof, with a trick to get multiplication. * With these, we have addition and multiplication in our field, so we can prove anything. ## Proving programs Say we want to prove execution of the foo function: def foo(s, x, y): if s: return x*y else: return x+y We need to apply a concept called arithmetisation: #pause => a AND b = ab => a OR b = a + b - ab => NOT a = 1 - a #pause => Boolean constraint: (a - 0)*(a - 1) == 0 ## Arithmetisation f(s, x, y) = (s * x * y) + (1 - s) * (x + y) #pause Additionally constrain s as bool: (s - 0)(s - 1) = 0 ## How is this helpful in practice? #pause * Digital signatures #pause * Anonymous engineering #pause * Voting (verify the vote was included in the tally) #pause * Payments (hide sender, recipient, amount) #pause * Authentication (no need to exchange secret information) #pause * Finance (prove your income is within some range to get a loan) * Verifiable computation * First time in history we're able to verify computation faster than the time it takes to compute the computation ## Part Two On Saturday, we will go over these concepts in practice in person using pen+paper and SageMath. A notebook PDF will be uploaded with the summary of what we have done, and for people interested, some further reading materials to get you deeper into the topics of cryptography and ZK proofs. See you soon!