State of the STARK

Eli Ben-Sasson, Chief Scientist (East) | October 2018

Overview

• What’s a STARK?
• STARK comparison to
• SNARKs (Zcash)
• Recursive SNARKs (Coda)
• Bulletproofs (Monero)
• Benefits of STARK for scalability
• Potential use-cases

Scalability, Privacy & Proofs

Proofs of Computational Integrity

• Integrity: the quality of being honest (Dictionary)

​

zk-STARK | October 2018

Proofs of Computational Integrity

• Integrity: the quality of being honest (Dictionary)
• Computational Integrity: the quality of a computation being executed honestly (correctly)

​

zk-STARK | October 2018

Proofs of Computational Integrity

• Integrity: the quality of being honest (Dictionary)
• Computational Integrity: the quality of a computation being executed honestly (correctly)
• Grocery receipts are proofs of computational integrity
• Verification via naive re-execution of computation
• Proof is (i) deterministic, (ii) error free, (iii) one-shot (non-interactive)

​

zk-STARK | October 2018

Proofs of Computational Integrity

• Integrity: the quality of being honest (Dictionary)
• Computational Integrity: the quality of a computation being executed honestly (correctly)
• Grocery receipts are proofs of computational integrity
• Verification via naive re-execution of computation
• Proof is (i) deterministic, (ii) error free, (iii) one-shot (non-interactive)
• Modern CI proofs have (i) randomness, (ii) small error, (iii) interaction; in return, offer many benefits…

​

zk-STARK | October 2018

Modern proofs of Computational Integrity

• Invented by Goldwasser, Micali, Rackoff in 1985;

​

zk-STARK | October 2018

Modern proofs of Computational Integrity

• Invented by Goldwasser, Micali, Rackoff in 1985;
• Zero knowledge (ZK): private inputs are shielded

​

zk-STARK | October 2018

Modern proofs of Computational Integrity

• Invented by Goldwasser, Micali, Rackoff in 1985;
• Zero knowledge (ZK): private inputs are shielded
• Scalability: for computation lasting T cycles, proofs
• generated in ~ T cycles (quasi-linear in T), and
• verified exponentially faster than T (~ log T cycles)

​

zk-STARK | October 2018

Modern proofs of Computational Integrity

• Invented by Goldwasser, Micali, Rackoff in 1985;
• Zero knowledge (ZK): private inputs are shielded
• Scalability: for computation lasting T cycles, proofs
• generated in ~ T cycles (quasi-linear in T), and
• verified exponentially faster than T (~ log T cycles)
• Universality (Turing Completeness): apply to any computation

zk-STARK | October 2018

Modern proofs of Computational Integrity

• Invented by Goldwasser, Micali, Rackoff in 1985;
• Zero knowledge (ZK): private inputs are shielded
• Scalability: for computation lasting T cycles, proofs
• generated in ~ T cycles (quasi-linear in T), and
• verified exponentially faster than T (~ log T cycles)
• Universality (Turing Completeness): apply to any computation
• Examples of things one can prove
• Paid taxes on all my cryptocurrency tx’s for 2017
• Control at least 10 BTC as of today
• Crypto exchange is in the black as of today (pf of solvency)
• ...

zk-STARK | October 2018

ZK-STARK: core attributes

Many flavors of proof systems

Variety of theoretical constructions

• PCP based, linear PCPs, elliptic curve+pairing based succinct NIZKs, quadratic span/arithmetic programs (QAP/QSP), interactive oracle proofs (IOP), …

​

zk-STARK | October 2018

Many flavors of proof systems

Variety of theoretical constructions

• PCP based, linear PCPs, elliptic curve+pairing based succinct NIZKs, quadratic span/arithmetic programs (QAP/QSP), interactive oracle proofs (IOP), …

And implementations

• Pinocchio, libsnark, zcash, pepper, ligero, bulletproofs, libstark, aurora, ...

See zkp.science

zk-STARK | October 2018

zk-STARK definition

A proof system is a zk-STARK if it satisfies:

• zk: zero knowledge, private inputs are shielded

​

zk-STARK | October 2018

zk-STARK definition

A proof system is a zk-STARK if it satisfies:

• zk: zero knowledge, private inputs are shielded
• Scalable: proofs for CI of computation lasting T cycles are
1. generated in roughly T cycles (quasi-linear in T), and
2. verified exponentially faster than T (roughly log T cycles)

​

zk-STARK | October 2018

zk-STARK definition

A proof system is a zk-STARK if it satisfies:

• zk: zero knowledge, private inputs are shielded
• Scalable: proofs for CI of computation lasting T cycles are
• generated in roughly T cycles (quasi-linear in T), and
• verified exponentially faster than T (roughly log T cycles)
• Transparent: verifier messages are random coins; no trusted setup

​

zk-STARK | October 2018

zk-STARK definition

A proof system is a zk-STARK if it satisfies:

• zk: zero knowledge, private inputs are shielded
• Scalable: proofs for CI of computation lasting T cycles are
• generated in roughly T cycles (quasi-linear in T), and
• verified exponentially faster than T (roughly log T cycles)
• Transparent: verifier messages are random coins; no trusted setup
• ARgument of Knowledge: proof can be generated only by party knowing private input (formally: an efficient procedure can extract the secrets from a prover)

​

zk-STARK | October 2018

zk-STARK definition

A proof system is a zk-STARK if it satisfies:

• zk: zero knowledge, private inputs are shielded
• Scalable: proofs for CI of computation lasting T cycles are
• generated in roughly T cycles (quasi-linear in T), and
• verified exponentially faster than T (roughly log T cycles)
• Transparent: verifier messages are random coins; no trusted setup
• ARgument of Knowledge: proof can be generated only by party knowing private input (formally: an efficient procedure can extract the secrets from a prover)
• STARKs may be interactive (use blockchain as source of transparent randomness), gives shorter & safer proofs
• 1st STARK: SCI-POC [BCG+16]; 1st zk-STARK: libstark [BBHR18]

zk-STARK | October 2018

Stark vs. Snark & Bulletproofs

Scalability - Stark vs naive verification

• Naive: Verification = proving

zk-STARK | October 2018

Computation time

Proof activity time

Naive

Scalability - Stark vs naive verification

• Naive: Verification = proving
• STARK:
• Quasi-linear proving
• Poly-logarithmic verification

zk-STARK | October 2018

Verifier

Prover

Naive

Computation time

Proof activity time

Scalability - Stark vs Snark (Zcash)

zk-STARK | October 2018

Verifier

Prover

Naive

Verifier

Prover

Trusted setup

Computation time

Proof activity time

Computation time

Proof activity time

STARK

SNARK

Scalability - Stark vs Snark (Zcash)

zk-STARK | October 2018

Verifier

Prover

Naive

Verifier

Prover

Trusted setup

Computation time

Proof activity time

Computation time

Proof activity time

STARK

SNARK

Trusted setup

Scales linearly with compute time

Scalability - Stark vs recursive Snark (Coda)

zk-STARK | October 2018

Verifier

Prover

Naive

STARK

Recursive SNARK

Computation time

Proof activity time

Computation time

Proof activity time

Scalability - Stark vs recursive Snark (Coda)

zk-STARK | October 2018

Verifier

Prover

Naive

STARK

Recursive SNARK

Computation time

Proof activity time

Computation time

Proof activity time

Trusted setup

Large proving time

Scalability - Stark vs recursive Snark (Coda)

zk-STARK | October 2018

Verifier

Prover

Naive

STARK

Recursive SNARK

Computation time

Proof activity time

Computation time

Proof activity time

Trusted setup

Large proving time

1 block delay

Stark vs BulletProofs (Monero)

zk-STARK | October 2018

Verifier

Prover

Naive

STARK

BulletProofs

Proof length

Prover

Verifier

Computation time

Proof activity time

Computation time

Proof activity time

Stark vs BulletProofs (Monero)

zk-STARK | October 2018

Verifier

Prover

Naive

STARK

BulletProofs

Proof length

Prover

Verifier

Computation time

Proof activity time

Computation time

Proof activity time

Linear verifier time

Stark vs BulletProofs verification measurements

T440 laptop

i7-8550U CPU

@ 1.80GHz

Single thread

32 GB DDR4 RAM

​

zk-STARK | October 2018

# Pedersen hashes

BulletProof paper

Naive

dalek-cryptography

BulletProofs

Proof length

Prover

Verifier

STARK verifier

verifier time (ms)

Computation time

Proof activity time

Scalability - Stark vs naive verification

Verifier

Prover

Naive

Computation time

Proof activity time

Zoom in

Scalability - Stark vs naive verification

T440 laptop

i7-8550U CPU

@ 1.80GHz

Single thread

32 GB DDR4 RAM

​

zk-STARK | October 2018

Verifier

Prover

Naive

#Pedersen hashes (log scale)

STARK verifier

Naive

Computation time

Proof activity time

Proof activity time (ms)

Zoom in

STARK prover

Scalability - Stark vs naive verification

T440 laptop

i7-8550U CPU

@ 1.80GHz

Single thread

32 GB DDR4 RAM

​

zk-STARK | October 2018

Verifier

Prover

Naive

#Pedersen hashes (log scale)

STARK verifier

Naive

Computation time

Proof activity time

Proof activity time (ms)

Zoom in

STARK prover

STARK Prover/Naive ratio ~ 100X

Virtues of Transparency (no trusted setup)

• Eliminate single point of failure (trusted setup)

​

zk-STARK | October 2018

Virtues of Transparency (no trusted setup)

• Eliminate single point of failure (trusted setup)
• Facilitates continuous deployment of minor upgrades

​

zk-STARK | October 2018

Virtues of Transparency (no trusted setup)

• Eliminate single point of failure (trusted setup)
• Facilitates continuous deployment of minor upgrades
• Reduces trust assumptions: nothing up your sleeve, no need to trust setup ceremony

​

zk-STARK | October 2018

Virtues of Transparency (no trusted setup)

• Eliminate single point of failure (trusted setup)
• Facilitates continuous deployment of minor upgrades
• Reduces trust assumptions: nothing up your sleeve, no need to trust setup ceremony
• Additional virtues of reliance on symmetric cryptography
• Post-quantum security
• Faster proving and verification time
• Simpler, more reliable trust assumptions (CRH/Fiat-Shamir)
• Reliance on “old” peer-reviewed principles (PCP Theorem, interactive knowledge extractors, …)

zk-STARK | October 2018

STARK for Scalability

zk-STARK | October 2018

39

STARK for Scalability: Space

zk-STARK | October 2018

40

STARK Science & Engineering:

Peek under the hood

How to build efficient STARKs?

• Convert computation to Algebraic Intermediate Representation (AIR)
• Generalization of R1CS constraints (used by SNARKs)
• State of computation is sequence of field elements
• Program expressed as set of polynomial relations over consecutive states
• Then apply more crypto+algebra …

​

zk-STARK | October 2018

How to build efficient STARKs?

• Convert computation to Algebraic Intermediate Representation (AIR)
• Generalization of R1CS constraints (used by SNARKs)
• State of computation is sequence of field elements
• Program expressed as set of polynomial relations over consecutive states
• Then apply more crypto+algebra …
• Long term: tool-chain converting programs to AIRs

​

zk-STARK | October 2018

How to build efficient STARKs?

• Convert computation to Algebraic Intermediate Representation (AIR)
• Generalization of R1CS constraints (used by SNARKs)
• State of computation is sequence of field elements
• Program expressed as set of polynomial relations over consecutive states
• Then apply more crypto+algebra …
• Long term: tool-chain converting programs to AIRs
• Mid term: domain specific languages for composing crypto-primitives

​

zk-STARK | October 2018

How to build efficient STARKs?

• Convert computation to Algebraic Intermediate Representation (AIR)
• Generalization of R1CS constraints (used by SNARKs)
• State of computation is sequence of field elements
• Program expressed as set of polynomial relations over consecutive states
• Then apply more crypto+algebra …
• Long term: tool-chain converting programs to AIRs
• Mid term: domain specific languages for composing crypto-primitives
• Short term: hand-optimize AIRs for specific computations

​

zk-STARK | October 2018

Example: Pedersen Merkle path

• Statement proved: I know a leaf in Merkle-tree of depth d with Merkle root r

​

zk-STARK | October 2018

Example: Pedersen Merkle path

• Statement proved: I know a leaf in Merkle-tree of depth d with Merkle root r
• Useful for
• Shielded Txs (major component in Zcash Sapling circuit)
• Verifiable Delay Functions (VDFs)
• Scalability solutions (more on this later)

​

zk-STARK | October 2018

Example: Pedersen Merkle path

• Statement proved: I know a leaf in Merkle-tree of depth d with Merkle root r
• Useful for
• Shielded Txs (major component in Zcash Sapling circuit)
• Verifiable Delay Functions (VDFs)
• Scalability solutions (more on this later)
• StarkWare’s first major milestone: implementing STARK for this
• Let’s examine the numbers

zk-STARK | October 2018

STARK measurements - Pedersen Merkle path

T440 laptop

i7-8550U CPU

@ 1.80GHz

Single thread

32 GB DDR4 RAM

​

zk-STARK | October 2018

seconds

ms

Path length

Path length

Prover

Verifier

STARK measurements - Pedersen Merkle path

T440 laptop

i7-8550U CPU

@ 1.80GHz

Single thread

32 GB DDR4 RAM

​

zk-STARK | October 2018

Prover time

Verifier time

ms

seconds

Path length

Path length

STARK proof length - Pedersen Merkle path

zk-STARK | October 2018

51

Proof size (KB)

Pedersen 128

Pedersen 80

Path length

STARK verifier complexity

zk-STARK | October 2018

52

# hashes to verify

Pedersen 128

Pedersen 80

#hashes in path

StarkWare Tech4Token progress

StarkWare: Company Essentials

zk-STARK | October 2018

54

We’re here this week - come talk to us! (info@starkware.co)

Raised

$10M�Seed &

Ethereum grant

Funds

Investors

R&D

15�engineers

Strong�scientific consultants

and others!

Plans

Tech 4 Token (T4T)

1st - EF grant

Scalability Product(s)

Next part

1st T4T: Ethereum Foundation grant update

• STARK-friendly hash functions
• Defined complexity parameters of STARK friendly primitives

​

zk-STARK | October 2018

1st T4T: Ethereum Foundation grant update

• STARK-friendly hash functions
• Defined complexity parameters of STARK friendly primitives
• Teamed with Prof. Vincent Rijmen, Dr. Tomer Ashur and Siemen Dhooghe
• Rijndael/AES-based constructions (over binary fields)
• Jarvis - STARK-friendly cypher candidate
• Friday - STARK-friendly hash candidate, ~25X STARK-friendlier than Pedersen
• Next: expert+community review, including cypher-breaking competition

​

zk-STARK | October 2018

1st T4T: Ethereum Foundation grant update

• STARK-friendly hash functions
• Defined complexity parameters of STARK friendly primitives
• Teamed with Prof. Vincent Rijmen, Dr. Tomer Ashur and Siemen Dhooghe
• Rijndael/AES-based constructions (over binary fields)
• Jarvis - STARK-friendly cypher candidate
• Friday - STARK-friendly hash candidate, ~25X STARK-friendlier than Pedersen
• Next: expert+community review, including cypher-breaking competition
• 2-year performance and milestone-based grant
• Requested Milestone: STARK proofs at rate of 100 hash/sec on quad-core
• Latest: 100 Pedersens/3 sec on single thread of this laptop (1.8Ghz)

zk-STARK | October 2018

STARK proof length estimates, repeated hash

zk-STARK | October 2018

58

Pedersen 120

Pedersen 80

Jarvis 120

Jarvis 80

#hashes

Proof size (KB)

Demo

One more thing…

Questions?

STARK Use Cases

Avihu Levy, Head of Product | October 2018

Potential Uses

• Scalability
• Infrastructure level (layer 1 / layer 2)
• Application level (STARK-powered dapp)
• Privacy
• Bootstrap & Sync
• STARK-based primitives
• VDF
• Signature aggregation
• ...

zk-STARK | October 2018

Scalability

zk-STARK | October 2018

64

Verifying 10K Txs costs only 3x of verifying single Tx!

Scalability

by offchaining:

Complex computations

Batches of simple computations

Storage

What’s Done On-Chain Vs. Off-Chain?

zk-STARK | October 2018

65

On Chain

Verifier

Off Chain

Native Computation

Prover

Scalability by batching

zk-STARK | October 2018

66

Payment Txs: In a Nutshell

zk-STARK | October 2018

67

Increase the network throughput (e.g. of Ethereum)

Users register to the contract, �and only then can interact with one another

Reduce Tx fees�(for native Ether and ERC-20 tokens)

Significant saving�(> 10X)

Payment Txs: How Is This Achieved?

zk-STARK | October 2018

68

Increasing network throughput by 1 OOM

Less transmission, �less computation

No need to send and verify signatures

Covered by proof

State storage taken off chain, state root stored on-chain

Proof proves state changes

Centralization trade-off (unless done by miners)

Scalability

zk-STARK | October 2018

Tx

Tx

Tx

Tx

Tx

Tx

Tx

Tx

STARK Proof

Tx

Tx

Tx

Tx

Tx

Tx

Tx

Tx

+

Native Computation

State

Transmission

Computation

Storage

+

State root

DEX: In a Nutshell

zk-STARK | October 2018

70

Provide users with “best of all worlds”:

Later add (cheap) transfers and shielded Txs�through DEX

Users keep custody of their funds

Low latency

At a negligible blockchain cost

Breaking the gas-induced ceiling on volume/liquidity

DEX: How Is This Achieved?

zk-STARK | October 2018

71

lowering blockchain costs* by 1-2 OOM

*Blockchain costs are currently the dominant DEX costs

Less transmission, �less computation

No need to send and verify maker/taker signatures

Covered by proof

Trader balances taken off chain, state root stored on-chain

Proof proves balance changes

Centralization not an issue in this case

Overview

• What’s a STARK?
• STARK comparison to
• SNARKs (Zcash)
• Recursive SNARKs (Coda)
• Bulletproofs (Monero)
• Benefits of STARK for scalability
• Potential use-cases

zk-STARK | October 2018

Bootstrap & Sync

• Problem: new clients bootstrapping process is heavy, as well as keeping your client sync
• Solution: Download a state and a proof for the validity of the state, rather than download & recompute the whole history

zk-STARK | October 2018

Bootstrap & Sync

• Block headers for light clients
• E.g. (Ethereum): ~500 bytes header, ~3MB headers/day
• Instead, a stark proof for block header having X work behind it since genesis/ last known checkpoint
• Proof size ~100KB with 20 ms verification time
• Full Clients
• Prove that the state computed based on previous block state/ genesis block is valid

zk-STARK | October 2018

VDF

• Problem: randomness from block data is hard, if the block creator knows the output of the random function
• Solution: a function that take time to compute, so when fixing the input the output is unknown
• We do want a fast verification of the output

zk-STARK | October 2018

VDF

zk-STARK | October 2018

f(x)

f(x)

Input

...

f(x)

Output

+

STARK Proof