Next Generation ZKPs

Levels of this talk

• What is possible with next generation of zktooling
• A little about constraint hacking with circom
• A little about constraint hacking with ultra plonk
• A little about implications of new zkps

What do we currently use

​

• Circom/ Groth 16
• A*B = C
• Two phase trusted setup
• Specialized hash (mimc/posidon) (high cost in evm)
• Specialized signature (eddsa)
• Very inefficient support for binary primitives (xor, and)

​

Xor with circom

• Check A * B = C
• Xor gate

​

​

Xor with circom

• Check A * B = C
• Xor gate
• out <== a + b - 2*a*b;

​

​

• https://github.com/iden3/circomlib/blob/243d2ec4fc9855780632fc498d24415b5534019f/circuits/gates.circom#L21
• This compiles to
• A_2 = a*2
• A_2 * b + a + b = out

​

Xor with circom

• Check A * B = C
• Xor gate
• out <== a + b - 2*a*b;

​

​

• https://github.com/iden3/circomlib/blob/243d2ec4fc9855780632fc498d24415b5534019f/circuits/gates.circom#L21
• This compiles to
• A_2 = a*2
• A_2 * b + a + b = out
• What about binary constirnats ?
• If a = 2 , b = 2 out = ?

​

Binary constraint circom

• A = 0 or 1
• B = 0 or 1
• Out = ??

Custom constraints

• Currently we have a single component A * B = C
• Like building everything with xor, and, nand , or gates
• With custom constraints we can save by specializing the gates we need.

​

Plookup

• 12345* 12309 = ?
• Write a python script that reads in a csv file and prints to screen

Plookup

• 12345* 12309 = ?
• Write a python script that reads in a csv file and prints to screen
• How will you do this ? … google it ..
• Plookup means committing to a set of possible things and then letting the prover look up any of them
• Make a table
• Table = {0,1,2,3,4,5,6,7}
• Can add a single constraint to check membership in static table
• Notes about table size < = size_of_circuit

​

​

Xor with Plookup

​

​

Binary constraint with Plookup

​

• What in our table ?
• ​

Binary constraint with Plookup

​

• What in our table ?
• 0 or 1
• So now we have 1 constraint binary check

Plookup Key Value

• Can also do key, value tables
• Table = {0:0:0 , 1:1:0. 0:1:1: 1:0:1}

Big int addition with circom

• Input_1 + input_2 = output % 2**256
• Output overflows at ~2**253

Big int addition with circom

• Input_1 + input_2 = output % 2**256
• Output overflows at ~2**253
• Break into limbs and then add them piece by piece

Big integer addition with circom

• Input_1 + input_2 = output % 2**256
• A + B = input_1
• A = 128 bits
• B = 128 bits
• D + E = input_2
• D = 128 bits
• E = 128 bits
• A + D = output_lower
• B + E = output_upper

Big integer addition with plookup

• Whats our table ?
• Do we want key value ?

Recursion adding functions to zkps

• No functions
• Just run things inside a giant loop
• The tools above allow us to add recursion, i.e. let a proof validate another proof.

​

How recursion works

• ZKP verification
• Exponentiation = additions , multipictions % another field
• Pairing check
• We do exponentiation of many zkps inside and then check the pairing outside
• Use this to batch together many zkps

Recursion implications

• Interop
• Dark forest was not able to talk to tornado cash
• You had to commit to how coins where spent. Instead of letting users define their own rules inside zkp
• Helped proving
• Can break proof into many parts, LIke private part and public part
• Torado cash for example
• Proof of membership in tree can be separated proof
• New language paradigms
• Could make a zk focused VM
• Could have weird compiler optimizations

Conclucion

• New generation of zkps are here
• They change a bunch of stuff by enabling
• Functions
• Efficient arithmetic gadgets
• Support tooling is required like
• Prover
• Better languages
• In this new world what is possible ?

Thanks

• Questions
• Links
• https://github.com/zcash/halo2

Plookup

• Its similar to have merkle tree and prove membership