Privacy-Preserving Smart Contract Architectures
Guest Lecturer: Zac Williamson, AZTEC

Zero Knowledge Proofs
Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng Zhang

What’s the goal?
▪ From 1st principles, derivate a blockchain architecture which has…

▪ Programmable smart contracts with private state as afirst-class primitive▪ Transactions are end-to-end encrypted▪ No trusted 3rd parties or hardware, only math!
▪ Preserve traditional smart contract semantics▪
▪

contracts can “call” other contracts
accessible to non-cryptographers

2

ZKP MOOC

Prior work and influences▪

(2015) Zerocoin paper, ZCash▪

(2018) ZEXE▪

(2020) Mina protocol▪

…and over 40 years of zk research!
3ZKP MOOC

“Choose your SNARK/STARK”▪

We need…
fast Prover w. minimal resources▪ fast arbitrary-depth recursive proof composition▪

▪
▪

=> small proof sizes

Sumcheck IOP + KZG commitment scheme fits thebill (e.g. Hyperplonk, Honk (TBD))▪

Recursion via Halo2-style curve cycles
4

ZKP MOOC

What is a blockchain?

ZKP MOOC

5
Credit: Faithie/ShutterstockWhat is a private state machine?
What even is a state machine?

ZKP MOOC

6
Credit: Faithie/ShutterstockPrivate state (⅓)▪ State must be encrypted▪ Owner od decryption key “owns” the stateState tree == Merkle tree of encrypted state, but…
▪ Modifying/deleting entry leaks information!
▪ => Merkle trees must be append only
▪ …how do we update state once it’s created?
▪

7

ZKP MOOC

Private state (2/3)
State is deleted via Nullifiers and a nullifier set▪ Nullifier = encryption of encrypted state!
▪

▪

Cannot link nullifier to state w/o decryption key

State is deleted by adding nullifier to nullifier set▪ State is live iff nullifier does not exist in nullifier set▪

Private state has an inherent UTXO structure
8ZKP MOOC

Private state (3/3)
data = “we hold these truths to be self-evident”
owner = bfnklyn.eth

UTXO = Enc(data, owner, owner.sk)

Nullifier = Enc(UTXO, owner.sk)

9ZKP MOOC

Q: Is private UTXO state sufficient?
Can we re-create existing
blockchain apps?

ZKP MOOC

10
Credit: Faithie/ShutterstockNo! We have PROBLEMS…
▪

Race conditions▪

▪

1 UTXO cannot be modified twice in 1 block

Ownership requirement
Cannot perform deterministic state updates w/odecryption keye
▪ e.g. forced collateral liquidations▪

▪

Need UTXO private state *and* account-model
public state
11

ZKP MOOC

The road to a private + public state machine▪

Private state transitions▪

▪

require user-generated proofs of correctness

Public state transitions▪

ordered + executed sequentially by 3rd party e.g.
▪
▪
▪

Miner (Eth 1)
Validator (Eth 2)
Sequencer (L2)12ZKP MOOC

Creating a Smart Contract withprivate + public state

ZKP MOOC

13Credit: Faithie/ShutterstockTime-ordering of state transitions▪ (user submits proof of private state transitions▪ User tx consists of:▪ proof of private state transition algorithm▪ instruction to execute public state transition algorithm▪ Private state transitions happen before public statetransitions▪ How do we present semantics that express this?

14ZKP MOOC

Smart contracts for private blockchains▪ Contract composed of public functions and privatefunctions▪ Private functions▪ Can update UTXO tree
▪ Can update nullifier set▪ Can read from historical public state▪ Can unilaterally call public functions (no returnparams)
15

ZKP MOOC

Contract composed of private and public functions
Private functions

Public functions▪ Can update UTXO tree

▪ Can update UTXO tree

▪ Can update nullifier set▪ Can update nullifier set▪ Can read from historical public state▪ Can read/write public state▪ Can unilaterally call public functions(no return params)

16

ZKP MOOC

Protocol representation of smart contracts▪ Functions defined by ZK SNARK verification keys
▪ “Contract” defined by set of function verification keys
▪ Public inputs of ZK SNARK circuit conforms to auniform ABI

17

ZKP MOOC

Smart contract ABI example
Public input range

Purpose0-9Function argument parameters

10

UTXO tree state root

11

Nullifier tree state root

12

Public tree state root

13

msg.sender (encrypted)

10-19

UTXO leaves to add

20-29

Nullifier leaves to add

30-39

Event parameters

18

ZKP MOOCExecuting private functions▪ Private functions must be executed client-side toavoid leaking information▪ Require proof of correctness of sequence of privatefunction calls▪ …what if a private function calls a function from adifferent contract?
We need call semantics!
19ZKP MOOC

The Private Kernel Circuitor how I learned to stop worrying and love recursion

ZKP MOOC

20
Credit: Faithie/ShutterstockWhat is a “kernel” in general software terms?
▪ A software layer between user code and the CPU &hardware▪ Enforces code execution rules and chooses which app
runs next on the CPU▪ Manages resource access and allows cross-app
communication

21

ZKP MOOC

What is a “kernel” in a ZK SNARK?
▪ A circuit layer between user code (e.g. Noir“contract”) and the protocol execution layer (e.g. L2rollup)▪ Enforces code deployment and execution rules▪ Manages access to data and functions from within acontract▪ Maintains privacy of some information

22

ZKP MOOC

Why do we need a Private Kernel Circuit? (⅓)▪ Privacy▪ Authenticate user w/o revealing identity▪ Hide contract being called▪ Composability▪ Functions should be able to call functions of other▪

contracts
Every contract function is its own circuit && generates
own proofs

23ZKP MOOC

Why do we need a Private Kernel Circuit? (⅔)▪ One TX can contain multiple proofs (1 per function)e.g. User calls A.foo(), A.foo() calls B.bar(0 etc▪ A.foo(), B.bar() each represented by a circuit + proof▪ Who combines them and how?
▪

24

ZKP MOOC

Why do we need a Private Kernel Circuit? (3/3)▪ Combining function proofs

requires privacy▪

What if a.foo() -> b.bar()passes sensitive information?

25

ZKP MOOC

High-level recap of Private Kernel (½)▪ A circuit that validates the correct execution of ONE

private function call
▪ Circuit structure is recursive▪ A sequence of private function calls can be executed
via iteratively computing kernel circuit proofs
Can unwind recursion into 1 layer but will leak info
26

ZKP MOOC

High-level recap of Private Kernel (2/2)▪ User generates proof▪ Preserves privacy ofuser (tx.origin)▪ (nested) function args and return values▪ state reads▪ the function itself▪

▪

User submits a single proof for full execution ofprivate function callstack27ZKP MOOC

For each function call in the callstack..
▪

Prove the following
signed TX request matches first call in callstack▪ function exists in function tree
▪ contract exists in contract tree
▪ commitments referenced by function are in data tree▪

Collect new commitments, nullifiers, contracts▪ Verify previous kernel proof▪ Verify proof for current function being processed▪

28

ZKP MOOC

Inputs to the Private Kernel▪

SignedTxRequest▪

▪

PreviousKernelData▪

▪

Original request from user to call 1st function in the stackKernel is recursive! Accumulated data from previous iterations

PrivateCallData▪

Data relevant to function call being processed

29

ZKP MOOC

Kernel recursion

30

ZKP MOOC

Kernel recursion through callstack

31

ZKP MOOC

Private kernel circuit architecture

32

ZKP MOOC

Kernel Circuit does not:▪

Execute function circuits themselves▪

▪

Done prior to the kernel

Perform tree insertions
Commitments, nullifiers etc…
▪ This is done in a “rollup” circuit by Sequencer/Prover▪

▪

Merge multiple separate TXs▪

Sequencer/prover aggregates TXs in a “rollup” circuit

33

ZKP MOOCThe Public Kernel Circuit:public function execution

ZKP MOOC

34
Credit: Faithie/ShutterstockState of a tx in the public mempool▪ ZK Proof of private kernel

private callstack must be empty▪ public callstack contains functions to be executed▪

Public function execution must be validated via apublic kernel circuit▪ Public kernel proofs generated via Sequencer/Prover▪

35

ZKP MOOC

Computing proofs of public functions▪ Public function proofs computed by 3rd party

sequencer/prover▪ Function proofs wrapped in a public kernel circuit▪ One significant complication:▪ Sequencer must be fairly compensated for the work

they perform

36

ZKP MOOC

User/Sequencer trust problem▪ A function proof can be invalid from 2 causes:

Choice of public inputs creates unsatisfiable
constraints (i.e. transaction throws an error)▪ Witness assignment is deliberately invalid▪

▪

For public functions…
1st failure case caused by tx sender▪ 2nd failure case caused by sequencer▪

37

ZKP MOOC

Public functions require a VM!
▪ A valid tx requires the VM proof to be valid▪
▪

i.e. sequencer can’t grief a userA valid VM proof can return execution result as apublic input▪

i.e. user cannot force sequencer to do unpaid work38

ZKP MOOC

How do VirtualMachines Work?

ZKP MOOC

39
Credit: Faithie/ShutterstockCPU Architectures: high-level▪ Opcode: part of CPU instruction set:treated as atomic operation▪ Microcode: Opcodes split into
micro-opcodes. 1 clock cycle performs 1
microcode operation▪ Registers store data being worked on▪ RAM stores remaining data
▪ Arithmetic instructions executed by“Arithmetic Logic Unit”

40

ZKP MOOC

How does a SNARKVM Work?

ZKP MOOC

41
Credit: Faithie/ShutterstockPC (Program Counter)
OP (Opcode) Registers
MC (Microcode)

Gate Selectors

Memory Table

1 Column = 1 Polynomial Commitment
1 Row = 1 Gate
Opcode Lookups
Selector Lookups
TP TO TMCPC

Runtime columns (committed to by Prover)

Program-speciﬁc lookup table (precomputed)

Runtime lookup table (committed to by Prover)

VM lookup table (precomputed)

4242

ZKP MOOCPC (Program Counter)
OP (Opcode) Registers
MC (Microcode)

Gate Selectors

Memory Table

1 Column = 1 Polynomial Commitment
1 Row = 1 Gate
Opcode Lookups
Selector Lookups
TP TO TMCPC

OP, MC read from Opcode Lookup table (indexed by PC)
Gate Selectors read from Selector Lookup table (indexed by OP, MC)Registers, PC values dependent on Gate Selectors
4343

ZKP MOOCExample SNARK VM Opcodes
OpcodeNum Microcode Ops

Gate Expression

TechniqueAdd1

R1i+1 = R1i + R2i

Custom gate

MOV [R1]1

R1i+1= M[R1i]

Lookup

XOR R1 [R2]1

R1i+1= R1 ^ M[R2i]

Custom gate + Lookup

SHA2563,000

M[R1i] = SHA256(M[R2i])

3,000 gates + lookups!

JUMPI X1

PCi+1 = (R1i == 0) ? PCi + 1 : X

Custom gate

44

44

ZKP MOOC

Rollup Circuit:
Aggregating txs

ZKP MOOC

45
Credit: Faithie/ShutterstockWhy do we need a rollup?
▪ Validation of a block of txns is expensive due toverifier costs!
▪ Ideal if consensus layer only needs to validate proofof block correctness46

ZKP MOOC

Base Rollup Circuit

47

ZKP MOOC

Merge Rollup Circuit

48

ZKP MOOC

Rolling Up▪ We roll 2proofs/circuit▪ Small circuit sizes =fast proofs▪ Helps decentralization

Public kernel proofs

49

ZKP MOOC

Root Rollup Circuit▪ Recursively “devolve” proof systems to reduce vinyl verification cost50

ZKP MOOC

Putting it all together

ZKP MOOC

51
Credit: Faithie/ShutterstockRecap (1 / 2)
▪ 3 State trees (private state, public state, contract state)▪ 1 Nullifier set (private state)▪ Contracts defined via set of verification keys forprivate/public functions

52

ZKP MOOC

Recap (2 / 2)
Private kernel circuit validates private function
execution▪ Public kernel circuit validates public function
execution + private kernel proof▪ Rollup circuit validates public kernel proof + performs
state updates▪ Root rollup circuit validates rollup proof using SNARK
protocol w. low verification costs▪

53

ZKP MOOC

Many thanks toDavid Banks
Suyash Bagad
Michael Connor
Genevieve Birdsall
Joseph Andrews
ZKP MOOC

54
Credit: Faithie/Shutterstock