“Gentle” Introduction to Zero Knowledge Proof for Blockchain Developers

Angel “Java” Lopez�@ajlopez�https://github.com/ajlopez

​

Agenda

• Ethereum Scalability
• Off-chain Processing
• From Code to Proof
• Prover and Verifier
• Some Workflows

​

https://ethworks.io/ethereum-scaling-report

https://zkp.science/

https://github.com/matter-labs/awesome-zero-knowledge-proofs

https://medium.com/@angeljavalopez/learning-zero-knowledge-proof-b2581f728a31

Transactions in Ethereum

• Execution (in every node)
• Storage (in every node)
• Limited quantity per block

Alice -> Bob 3 ETH�Bob -> Charlie 2 ETH�Charlie -> Dan 1 ETH

Moving Processing to Off-Chain

• So the computation does not involve all the nodes
• Avoid the use of distributed storage
• Bitcoin Lightning Network
• Ethereum Raiden
• Zero Knowledge Proof
• Giving a short proof of offline computation

First Paper

http://groups.csail.mit.edu/cis/pubs/shafi/1985-stoc.pdf

Zero Knowledge Proof

A Simple Use Case

Alice, Bob and the Balls

Alice View

Bob View

Bob and Alice

Alice

Bob

First Interaction

Alice

Bob

Bob and Alice

Alice

Bob

Same!

Bob and Alice

Alice

Bob

Different!

Result

• Alice gives a proof that she can see the colors (based on repeated interactions)
• Bob is convinced that Alice can see the colors
• Bob still does not know the colors of the balls
• Bob does not learn any method to distinguish the colors from Alice

Zero Knowledge Proof for Transactions

Rules for a Transaction

• Account Balance > 0
• Tx.in == Tx.out
• Tx signature is valid

Transformations

• Rules are transformed to Code
• Code is transformed to Zero Knowledge Circuit (not trivial step)
• A Prover is built: program that can generate a proof of knowledge for inputs that satisfies the circuit/rules
• A Verifier is built: program that can verify any valid proof generated by the prover (without running the code, the transactions, and without learning details about the transaction)

From Rules to ZK Circuit to Prover and Verifier

Rules

Circuit

Prover

Verifier

From Transaction To Verification of Proof

Alice sends 2 ETH to Bob

Prover

Proof

Verifier

OK

Zero Knowledge Proof for Transactions in Blockchain

SNARK

• Succint: the proof is significantly smaller than the data it represents and can be verified quickly
• Non-interactive: only one set of information is sent by the prover to the verifier, thus there’s no back-and-forth interaction between them.
• Argument of Knowledge: the proof is considered computationally sound— a malicious prover isn’t likely to cheat the system without possessing the knowledge to support its statement.
• SNARKs used in scalablility solutions require a trusted setup between the prover and the verifier.
• ​
• ​

STARK

• Transparent
• Does not require trusted setup
• Proof size is greater than SNARKs

Offline Processing

• Executed in other machines (it could be a blockchain or not)
• Transactions with predefined rules (ie no double spend)
• Exchange of value (ie Tokens)
• The initial value is locked on-chain
• Any player could have off-line value
• A player could want to withdraw the value on-chain

Initial Setup

Operator

Prover

Blockchain

zkRollup Smart Contract

Verifier

Alice’s Wallet�20 ETH

�zkRollup contract�0 ETH

Alice Transfers to zkRollup 15 ETH

Operator

Prover

Blockchain

zkRollup Smart Contract

Verifier

Alice’s Wallet�5 ETH

�zkRollup contract�15 ETH

Offline Operations

Operator

Prover

Blockchain

zkRollup Smart Contract

Verifier

Alice’s Wallet�5 ETH

�zkRollup contract�15 ETH

Alice -> Bob �3 ETH�Bob -> Charlie�2 ETH�Charlie’s exit�2 ETH

Charlie’s Proof

Operator

Prover

Blockchain

zkRollup Smart Contract

Verifier

Alice’s Wallet�5 ETH

�zkRollup contract�15 ETH

Alice -> Bob �3 ETH�Bob -> Charlie�2 ETH�Charlie’s exit�2 ETH

Proof

New State

Operator

Prover

Blockchain

zkRollup Smart Contract

Verifier

Alice’s Wallet�5 ETH

�zkRollup contract�15 ETH��Charlie’s Wallet�2 ETH

Alice -> Bob �3 ETH�Bob -> Charlie�2 ETH�Charlie’s exit�2 ETH

Not So “Gentle” Introduction

From Code to Proof and Beyond

The Circuit

a

b

c

+

*

*

(a+b)*b*c

Homomorphic Hiding (HH)

An HH E(x) of a number x is a function satisfying the following properties:

• For most x’s, given E(x) it is hard to find x.
• Different inputs lead to different outputs – so if x≠y, then E(x)≠E(y).
• If someone knows E(x) and E(y), they can generate the HH of arithmetic expressions in x and y. For example, they can compute E(x+y) from E(x) and E(y).

​

Using E(x)

• Suppose Alice wants to prove to Bob she knows numbers x,y such that x+y=7
• Alice sends E(x) and E(y) to Bob
• Bob computes E(x+y) from these values
• Bob also computes E(7), and now checks whether E(x+y)=E(7)

Polynomial Evaluation

A Polynomial Over a Field

Evaluation at s

Evaluation at E(s)�P(s) = P(E(s))

From Computation to Polynomials

• THE TRICKY PART
• The circuit could be converted to polynomials, representing the code (one polynomial for left input, right input, and output)
• Each multiplication operation is assigned a number: 1, 2, 3…. These are the “target points”
• Alice, knowing a, b, c, can build a new polynomial P(x), combining the L, R, O polynomials and her inputs a,b,c. And additional polynomial H
• Bob chooses a random point s
• Alice computes E(L(s)), E(R(s)), E(O(s)), E(H(s))
• Bob verifies a condition E(L(s)R(s) - O(s)) = E(T(s)H(s))

From Polynomials to Elliptic Curve Points

• Calculate E(T(s)H(s)): it is not easy for a general HH function
• Instead of a number field, start using elliptic curve points
• Some elliptic curves has “pairings” (a mathematical property)
• In those curves, given two HH E1(x), E2(y) we can compute E(xy)
• In SNARKs there is a Common Reference String (CRS), containing E1 and E2 evaluation at various points
• Alice proof is the evaluation of E1(P(s)) and E2(P(s)) using various points from the CRS
• Bob verify the computation

https://www.menti.com/3trm1i61ui