Demystifying Zero-Knowledge Proofs

Elena Nadolinski

@leanthebean

elena@beanstalk.network

​

​

Who is this workshop for:

• No prior knowledge necessary
• Some experience with Solidity smart contracts
• Basic math

Where to get these slides & links

​

Twitter: @leanthebean

What we’ll go over

Part 1 - theory

• Some background knowledge
• Overview of how ZKPs work

Part 2 - coding

• Use Zokrates to make a smart contract that will generate NFT tokens only if the correct proof to a puzzle is given

Coding Part:

What we’ll go over

Part 2 - coding

• https://github.com/leanthebean/puzzle-hunt
• Install Docker & Zokrates

What is a ZKP?

What is a ZKP?

The ability to prove honest computation �without revealing inputs

ZKPs ≠ privacy

SNARKs

STARKs

Bulletproofs

ZKPs ==

honest computation

f(x) = y

• proof

f(x) = y

• Merkle path to my commitment notes that cover my transaction
• Entire Blockchain

f(x) = y

• Change to a smart contract
• One machine does the computation, all others accept new state change with a proof

​

History

• 1985 "The Knowledge Complexity of Interactive Proof-Systems"
• Shafi Goldwasser, Silvio Micali, and Charles Rackoff

​

• http://web.mit.edu/~ezyang/Public/graph/svg.html

Projects using ZKPs

SNARKs

​

​

Zcash: has optional shielded transactions that use zk-SNARKs

Has a ceremony for the trusted setup per circuit upgrade

​

​

Projects using ZKPs

SNARKs

​

​

Use recursive SNARKs to give a merkle root of latest global state with a proof

New nodes do not have to sync from the genesis block to build up their in-memory global state

Projects using ZKPs

Bulletproofs

​

​

Use Bulletproofs for more efficient range proofs only and not for privacy directly

Projects using ZKPs

zk-STARKs

​

​

Batching transactions off-chain for a decentralized exchange (DEX)

Open Source Projects

Modular Math

22 (mod 12) = 10

Because 12 divides 22 one time evenly with 10 as the remainder

3 + 16 (mod 12) = 7

And so on

​

​

Diffie Hellman (1976)

• First published method of public-key cryptography
• Secret sharing of an encryption key

​

​

(Learn more on early cryptography from The Code Book)

Diffie Hellman (1976)

• p = 23 (modulus) g = 5 (base)

​

Diffie Hellman (1976)

• p = 23 (modulus) g = 5 (base)
• Alice chooses a secret a = 4, and sends Bob A = g^a mod p
• A = 5⁴ mod 23 = 4

​

Diffie Hellman (1976)

• p = 23 (modulus) g = 5 (base)
• Alice chooses a secret a = 4, and sends Bob A = g^a mod p
• A = 5⁴ mod 23 = 4
• Bob chooses a secret b = 3, and sends Alice B = g^b mod p
• B = 5³ mod 23 = 10

​

Diffie Hellman (1976)

• p = 23 (modulus) g = 5 (base)
• Alice chooses a secret a = 4, and sends Bob A = g^a mod p
• A = 5⁴ mod 23 = 4
• Bob chooses a secret b = 3, and sends Alice B = g^b mod p
• B = 5³ mod 23 = 10
• Alice computes s = B^a mod p
• s = g^{b a} mod p = 10⁴ mod 23 = 18

​

​

Diffie Hellman (1976)

• p = 23 (modulus) g = 5 (base)
• Alice chooses a secret a = 4, and sends Bob A = g^a mod p
• A = 5⁴ mod 23 = 4
• Bob chooses a secret b = 3, and sends Alice B = g^b mod p
• B = 5³ mod 23 = 10
• Alice computes s = B^a mod p
• s = g^{b a} mod p = 10⁴ mod 23 = 18
• Bob computes s = A^b mod p
• s = g^{a b} mod p = 4³ mod 23 = 18

​

Diffie Hellman (1976)

• p = 23 (modulus) g = 5 (base)
• Alice chooses a secret a = 4, and sends Bob A = g^a mod p
• A = 5⁴ mod 23 = 4
• Bob chooses a secret b = 3, and sends Alice B = g^b mod p
• B = 5³ mod 23 = 10
• Alice computes s = B^a mod p
• s = g^{b a} mod p = 10⁴ mod 23 = 18
• Bob computes s = A^b mod p
• s = g^{a b} mod p = 4³ mod 23 = 18

Now Alice and Bob know to encrypt/decrypt their messages using the shared secret 18

​

RSA (1977)

• One of the first public key cryptosystems
• Uses Diffie-Hellman
• Digital Signatures

RSA

• Choose 2 primes: p = 5 q = 11

n = p * q = 55

​

RSA

• Choose 2 primes: p = 5 q = 11

n = p * q = 55

• lcm(p-1, q-1) = 20 (totient)

​

RSA

• Choose 2 primes: p = 5 q = 11

n = p * q = 55

• lcm(p-1, q-1) = 20 (totient)
• Choose a private key e that is 1 < e < 20 (coprime to 20)

e = 7

​

RSA

• Choose 2 primes: p = 5 q = 11

n = p * q = 55

• lcm(p-1, q-1) = 40 (totient)
• Choose a private key e that is 1 < e < 20 (coprime to 20)

e = 7

• Choose a public key d such that

d * e mod(totient) = 1

d = 23

RSA

private key e = 7 and public key d = 23

message to sign= 8

​

​

RSA

private key e = 7 and public key d = 23

message to sign= 8

​

c = 8⁷ mod 55 = 2

​

​

RSA

private key e = 7 and public key d = 23

message to sign= 8

​

c = 8⁷ mod 55 = 2

​

Anyone can check the signature using the public key 23

​

​

RSA

private key e = 7 and public key d = 23

message to sign= 8

​

c = 8⁷ mod 55 = 2

​

Anyone can check the signature using the public key 23

​

m = 2²³ mod 55 = 8

​

Fiat-Shamir (1986)

• Interactive proof of knowledge
• “Grandfather” of ZKPs
• Allows one to prove information about a number, without revealing the number

​

Fiat-Shamir

• g is a number (called generator) everyone knows

Fiat-Shamir

• g is a number (called generator) everyone knows
• Alice wants to prove that she knows x, such that y = g^x

Fiat-Shamir

• g is a number (called generator) everyone knows
• Alice wants to prove that she knows x, such that y = g^x
• She picks a random v, and sends t such that t = g^v

Fiat-Shamir

• g is a number (called generator) everyone knows
• Alice wants to prove that she knows x, such that y = g^x
• She picks a random v, and sends t such that t = g^v
• Bob pics a random c, and sends that to Alice

Fiat-Shamir

• g is a number (called generator) everyone knows
• Alice wants to prove that she knows x, such that y = g^x
• She picks a random v, and sends t such that t = g^v
• Bob pics a random c, and sends that to Alice
• Alice sends back r = v - cx

Fiat-Shamir

• g is a number (called generator) everyone knows
• Alice wants to prove that she knows x, such that y = g^x
• She picks a random v, and sends t such that t = g^v
• Bob pics a random c, and sends that to Alice
• Alice sends back r = v - cx
• Bob checks t = g^ry^c

​

Fiat-Shamir

• g is a number (called generator) everyone knows
• Alice wants to prove that she knows x, such that y = g^x
• She picks a random v, and sends t such that t = g^v
• Bob pics a random c, and sends that to Alice
• Alice sends back r = v - cx
• Bob checks t = g^ry^c
• Since g^ry^c = g^v-cx g^xc = g^v = t

Fiat-Shamir

• g is a number (called generator) everyone knows
• Alice wants to prove that she knows x, such that y = g^x
• She picks a random v, and sends t such that t = g^v
• Bob pics a random c, and sends that to Alice
• Alice sends back r = v - cx
• Bob checks t = g^ry^c
• Since g^ry^c = g^v-cx g^xc = g^v = t
• Bob knows that Alice knows the “preimage” x

Elliptic Curve Cryptography

• Much more powerful and efficient tool than exponentiation & modular math

​

Elliptic Curve Cryptography

• Much more powerful and efficient tool than exponentiation & modular math
• Great tutorial by Andrea Corbellini
• (much of which we’ll go over here)

y² = x³ + ax + b

(where 4a³ + 27b² ≠ 0)

Elliptic Curve Cryptography

~ ¾ of 100k top websites use ECDHE (https://) � (Elliptic Curve Diffie-Hellman Exchange)

96.1% of those use P256 curve (a NIST standard): � y² = x³ - 3x + b (mod p)

Parameters generated from hashing a seed

​

From a video by Dan Boneh

​

Elliptic Curve Cryptography

~ ¾ of 100k top websites use ECDHE (https://) � (Elliptic Curve Diffie-Hellman Exchange)

96.1% of those use P256 curve (a NIST standard): � y² = x³ - 3x + b (mod p)

Parameters generated from hashing a seed

​

From a video by Dan Boneh

​

NSA Conspiracy Theory

Elliptic Curve Cryptography

​

Abelian Group Properties for a set 𝔾

• Closure: if a and b are members of 𝔾 then a + b is also
• Associativity: (a + b) + c = a + (b + c)
• Identity: a + 0 = 0 + a = a
• Inverse: for every a, there exists b such that a + b = 0
• Commutativity: a + b = b + a

​

​

ECC - Addition

​

Given 3 aligned non-zero points, their sum is: P + Q + R = 0

​

ECC - Addition

​

If P + Q + R = 0, then P + Q = -R

​

​

If we draw a line between 2 pts P and Q, it’ll intersect at a point R

​

Since P + Q = -R we can easily find R and use it to compute addition of two points from it

ECC - Addition

​

P + Q = -R

​

m = (3x_P³ + a) / 2y_P

x_R = m² - x_p - x_Q

y_R = y_P + m(x_R - x_P) = y_Q + m(x_R - x_Q)

ECC - Addition

​

P + P = -R for Q = P = (1, 2) on y² = x³ - 7x + 10

​

m = (3x_P³ + a) / 2y_P = -1

x_R = m² - x_p - x_Q = -1

y_R = y_P + m(x_R - x_P) = y_Q + m(x_R - x_Q) = 4

​

So P + P = (-1, -4)

​

ECC - Multiplication

nP = P + P + … + P

​

​

​

(We have clever optimization techniques to do this fast)

​

n times

ECC - Multiplication

nP = P + P + … + P

​

nP = Q : fairly easily to compute

n = Q/P : very hard to compute (no efficient method)

​

Logarithm Problem (it’s not called division for conformity reasons)

​

​

​

​

​

n times

ECC - Multiplication

nP = P + P + … + P

​

nP = Q : fairly easily to compute

n = Q/P : very hard to compute (no efficient method)

​

Logarithm Problem (it’s not called division for conformity reasons)

​

But we’re missing cycles

n times

ECC - Finite Fields & Discrete Log

Finite field 𝔽p: set of elements (mod p) where p is prime

y² = x³ + ax + b (mod p)

y² = x³ - 7x + 10

​

​

p = 19

​

p = 127

​

p = 97

​

p = 487

​

ECC - Finite Fields (Addition)

P + P = ? in a finite field

​

ECC - Finite Fields (Addition)

P + P = ? in a finite field

P + P = (-1, -4) on y² = x³ - 7x + 10

​

For a finite field on p = 19

-1 (mod 19) = 18

-4 (mod 19) = 15

​

So P + P on y² = x³ - 7x + 10 (mod 19) = (18, 15)

ECC - Groups

y² = x³ + 2x + 3 (mod 97) at point P(3, 6)

​

Let’s calculate some multiples of P

n = 0

n = 1

n = 2

n = 3

​

n = 4

n = 5

Same as n = 0

n = 6

Same as n = 1

n = 7

Same as n = 2

n = 8

Same as n = 3

n = 9

Same as n = 4

n = 10

Same as n = 5, 0

n = 11

Same as n = 1, 6

n = 12

Same as n = 2, 7

… and the pattern continues

ECC - Groups

y² = x³ + 2x + 3 (mod 97) on P(3, 6) we saw a cycle

​

There are just 5 distinct points:

0, P, 2P, 3P, 4P

ECC - Groups

y² = x³ + 2x + 3 (mod 97) on P(3, 6) we saw a cycle

​

There are just 5 distinct points:

0, P, 2P, 3P, 4P

These five points are closed under addition. However you add 0, P, 2P, 3P or 4P, the result is always one of these five points.

​

ECC - Groups

The point P(3, 6) on y² = x³ + 2x + 3 (mod 97)

is therefore said to be a generator

or base point of the cyclic subgroup

​

and the order of this subgroup is

therefore 5

(the smallest n such that nP=0)

​

ECC - Groups

Q = nP mod p : easy to calculate

n = P/Q mod p : discrete logarithm problem

​

If you choose your curve, parameters, and generator point carefully, finding n becomes very very very hard

​

And this is exactly how the ECDSA signature scheme works

​

ECDSA

ECDSA signature (used in Bitcoin, Ethereum, etc):

• private key random integer d from {1, … n-1} where n is the order of the subgroup
• public key where G is the base point H = dG

ECDSA

A Bitcoin private key is 256 bits and gives 128-bit security level

​

To achieve the same security with RSA you would need 3092 bit length key

​

​

​

Pedersen Commitments

Tool for Confidential Transaction: Pedersen Commitment

​

Used in privacy coin Grin

​

Learn more about how Grin works

​

Pedersen Commitments

You could use Q = vG to “hash” or hide amounts per tx

But that’s susceptible to ‘Rainbow table’ attacks as one could precompute popular amount denominations

​

Pedersen Commitments

You could use Q = vG to “hash” or hide amounts per tx

But that’s susceptible to ‘Rainbow table’ attacks as one could precompute popular amount denominations

Solution: add a blinding factor

Com(v) = vG + bH

​

Pedersen Commitments

You could use Q = vG to “hash” or hide amounts per tx

But that’s susceptible to ‘Rainbow table’ attacks as one could precompute popular amount denominations

Solution: add a blinding factor

Com(v) = vG + bH

Where G and H are generator points

b is random number used as a blinding factor

​

​

Pedersen Commitments

The cool property of Pedersen Commitments (or sometimes called hashes) is that you can add them to check equality

Com(v1) = v1G + b1H

Com(v2) = v2G + b2H

Such that:

v2G + b2H + v1G + b1H = G(v2 + v1) + H(b1 + b2)

​

​

Bulletproofs (Range Proofs)

Proving that a number is within a range

v ​∈ [0,2ⁿ)

Zero Knowledge about the Inner Product of Two Vectors

​

Learn more how Bulletproofs work

​

​

​

​

​

Bulletproofs (Range Proofs)

Any number can be represented as inner product of two vectors.

​

5 = <[1, 0, 1] , [2², 2¹, 2⁰]>

5 equals inner product of 2 vectors [1, 0, 1] and [2², 2¹, 2⁰]

​

​

​

​

Bulletproofs (Range Proofs)

​

This is also how binary works

101_binary = 5_decimal since 1(2²) + 0(2¹) + 1(2⁰)

​

​

​

Bulletproofs (Range Proofs)

v = <a, 2ⁿ>

Example:

v = 5 and we wanted to prove that 5 is in range of 0 to 2ⁿ without showing 5

​

v ​∈ [0,2ⁿ)

​

​

Bulletproofs (Range Proofs)

​

5_decimal = 101_binary = 1(2²) + 0(2¹) + 1(2⁰)

Need at least 3 bits to represent 5: n has to be at least 3

2³ = 8

Therefore it’s clear that 5 must be in range of 0 to 2ⁿ

​

​

​

​

​

​

​

​

Bulletproofs (Range Proofs)

v = <a, 2ⁿ>

We need to prove that:

• That assignment of a is correct
• We can commit to secret values using Pedersen commitments and prove we know the value using a technique similar to Fiat-Shamir

Learn more how Bulletproofs work

STARKs

Please refer to Remco from 0x for all your STARK questions :)

SNARKs

There are many (50+) variants of SNARKs

​

QAP variant (quadratic arithmetic program):

Computation → Arithmetic Circuit → R1CS → QAP → SNARK

​

Check out this excellent primer by Decentriq

And Zcash’s explainer

​

SNARKs - Computation

x * y + 4 = 10

Prover wants to prove that they know values x and y

SNARKs - Arithmetic Circuit

x * y + 4 = 10

​

x

y

4

​

*

+

10

constraint 1

output₁

constraint 2

SNARKs - Arithmetic Circuit

x

y

4

​

*

+

10

constraint 1

output₁

Constraint 1:

output₁ = x * y

​

Constraint 2:

output₁ + 4 = 10

​

Constraint 3:

Equality constraint

​

constraint 2

SNARKs - R1CS

x

y

4

​

*

+

10

constraint 1

output₁

constraint 2

Constraint has a left input, right input and output

​

Such that:

left(L) * right(R) = output(O)

​

With 3 vectors:

<L, v> * <R, v> = <O, v>

​

v is the variable vector

v = [1, x, y, output₁]

​

SNARKs - Arithmetic Circuit

<L, v> * <R, v> = <O, v>

v = [1, x, y, output₁]

​

Constraint 1: x * y = output₁

L = [0, 1, 0, 0] // x

R = [0, 0, 1, 0] // y

O = [0, 0, 0, 1] // output₁

​

Constraint 2: (output₁ + 4) * 1 = 10

L = [4, 0, 0, 1] // output₁ + 5

R = [1, 0, 0, 0] // 1

O = [10, 0, 0, 0] // 10

​

x

y

4

​

*

+

10

constraint 1

output₁

constraint 2

SNARKs - QAP

Create polynomials for each constraint using Lagrange interpolation

​

L * R = O

​

Constraint 1:

L = [0, 1, 0, 0] // x

R = [0, 0, 1, 0] // y

O = [0, 0, 0, 1] // output₁

​

Constraint 2:

L = [4, 0, 0, 1] // output₁ + 5

R = [1, 0, 0, 0] // 1

O = [10, 0, 0, 0] // 10

​

L₁[1] = 0 (look at 1st constraint, 1st element of L)

L₁[2] = 4 (look at 2nd constraint, 1st element of L)

​

2 points: (1, 0) and (2, 4). We can use Lagrange interpolation to get a polynomial: 4x - 4

​

L₁(x) = 4x - 4

​

And we do this for each constraint, for each variable L_i(x), R_i(x), O_i(x)

SNARKs - QAP

L * R = O

​

Constraint 1:

L = [0, 1, 0, 0] // x

R = [0, 0, 1, 0] // y

O = [0, 0, 0, 1] // output₁

​

Constraint 2:

L = [4, 0, 0, 1] // output₁ + 5

R = [1, 0, 0, 0] // 1

O = [10, 0, 0, 0] // 10

​

L₁(x) = 4x - 4

L₂(x) = -1x + 2

L₃(x) = 0

L₄(x) = 1x - 1

​

​

SNARKs - QAP

L(x) * R(x) = O(x) for x in {1, 2} (since we have 2 constraints)

​

​

​

​

SNARKs - QAP

L(x) * R(x) = O(x) for x in {1, 2} (since we have 2 constraints)

​

P = L(x) * R(x) - O(x)

​

​

​

SNARKs - QAP

L(x) * R(x) = O(x) for x in {1, 2} (since we have 2 constraints)

​

P = L(x) * R(x) - O(x) = T(x) * H(x)

T(x) is a publicly known evaluation used for Verification

​

SNARKs - QAP

L(x) * R(x) = O(x) for x in {1, 2} (since we have 2 constraints)

​

P = L(x) * R(x) - O(x) = T(x) * H(x)

T(x) is a publicly known evaluation used for Verification

H(x) is provided by the Prover and divides �L(x) * R(x) - O(x) evenly (without remainder)

​

​

SNARKs - QAP

L(x) * R(x) - O(x) = T(x) * H(x)

The Prover would send evaluations of x for L, R, O, and H polynomials

But how would we ensure that:

• This “x” is hidden
• Prover actually uses its polynomials

​

SNARKs - QAP

L(s) * R(s) - O(s) = T(s) * H(s)

s is a linear combination of (g, s⋅g ,…, s^d⋅g) of length d (which corresponds to the max degrees of these polynomials)

This achieves two things:

• We’re forcing the Prover to evaluate s on its polynomials
• This s is encrypted, or “hidden”

​

SNARKs

How can we evaluate a value that is encrypted?

Ex: Instead of sending s plaintext, we can send E(s)

E(s) = sG

(where G is a generator point on a elliptic curve)

​

​

SNARKs

We can still do evaluations of E(s), even though it’s encrypted (sometimes called homomorphic addition):

​

Example:

E(3) + E(4) = E(3 + 4) = E(7)

​

​

SNARKs

L(s) * R(s) - O(s) = T(s) * H(s)

Using encrypted s, the Prover would send back:

E(L(s)), E(L(s)), E(O(s)), E(L(s)),

​

SNARKs

L(s) * R(s) - O(s) = T(s) * H(s)

Using encrypted s, the Prover would send back:

E(L(s)), E(L(s)), E(O(s)), E(L(s)),

But we still don’t have zero-knowledge as some information about the assignment is leaked

SNARKs

L(s) * R(s) - O(s) = T(s) * H(s)

Adding zero-knowledge:

The Prover simply adds a form of a blinding factor to the L, R, O evaluations

SNARKs - Protocol

• Setup: E(s) is known to everyone, T(s) is known to everyone (s itself is thrown away, “toxic waste”)
• Prover has L, R, O and H polynomials
• Prover sends E(L(s)), E(R(s)), E(O(s)), E(H(s))
• Anyone in the network can verify:�E(L(s)) * E(R(s)) - E(O(s)) = E(H(s)) * E(T(s))

SNARKs - what’s left

• This is a huge oversimplification, and we skipped some details regarding “blinding factors”
• Pairing of Elliptic Curves for the Verifier
• This went over the Pinocchio Protocol (PGHR) 2013�Better proving systems already out there: Groth16

SNARKs - the Future

• Enormous effort in research for further optimization
• Research in pairings
• Research in optionality of elliptic curves
• Lattice-based SNARKs
• And a lot, lot more

Let’s Go Ahead and Build One!

Part 2:

Zokrates