FAST,PRIVATE,FLEXIBLEBLOCKCHAIN CONTRACTS

Oleg Andreev

Tel Aviv, Israel

September 11-12, 2019

ZkVM

TL;DRZkVM is a multi-asset blockchain architecture withcontracts and confidentiality.
It is designed to scale, it is fast, and it’s written in pure Rust.
github.com/stellar/slingshot

AGENDA
1. Explain the good parts.
2. Explain away the bad parts.

IS IT ABOUT BITCOIN?
ZkVM is a unique combination of the best ideas from Bitcoin devs.
It is a preview of what Bitcoin may look like in the future.
bitcoinzcashethereumpayment channels
musig
mimblewimble
bls signaturesmonerocoinjoinlinear types

txo mmrobject capabilities
zksnarks

utreexo

recursive snarks
ristretto

ring signaturesbulletproofs
taproot

ZkVM ARCHITECTURE

TRANSACTIONS
tx 1

tx 2

tx 3

input

input

input

input

outputoutputoutputoutputoutputTx = program that transfers assets from inputs to outputs.
Transactions can also issue arbitrary assets.

UTREEXO
based on original proposal by Thaddeus Dryja

blockchain state...

unspent outputs
spent output
spending proofUTREEXO
Pros• Storage is free: simplifies protocol.
• More nodes can be full nodes.
Cons• Every node has to update their utxo proofs.
• Extra bandwidth overhead (negligible with caching).

PROGRAM EXECUTION
TX
programzk proof

Transaction is a program, cryptographic proof and some metadata.

PROGRAM EXECUTION
TX
programzk proofrun

VM
programstacktxlog

constraintsystem

VM instantiated per transaction; discarded after tx is processed.
High-level instructions enforce network rules.
Not turing-complete by design.

PROGRAM EXECUTION
TX
programrunzk proof

VM
program
stack

txlog

constraintsystemverifyInstructions build a constraint system (CS) on the fly.
CS enforces both network rules and custom, per-contract rules.
Single aggregated proof is used to verify all the constraints.

PROGRAM EXECUTION
TX
programzk proof

run

apply

VM
program
stack

txlog

blockchain
state

constraint
systemTransaction verification is stateless.
Created/deleted outputs are recorded in the transaction log.
Transactions log is applied to the blockchain state separately.

CONTRACTS
contract
predicate
item 1item 2
item 3

Each unspent output is a contract object.
Contract has arbitrary payload (assets, data) protected by a predicate.
Saved via output instruction, loaded via input instruction.

CONTRACTS
contract
predicateverifyitem 1item 2
item 3

item 1signature

unlockitem 2
item 3

Predicate is satisfied with either a signature...

CONTRACTS
contract
predicateexecuteitem 1item 2
item 3

item 1sub-program

unlockitem 2
item 3

Predicate is satisfied with either a signature or a sub-program.

TAPROOT

based on original proposal by Gregory Maxwell

Compresses contract logic into a single public key.
Either sign with K, or reveal a branch and execute it.

P = K + hash(K, R)·B
pubkeyK = k·B
program 1

program 2program 3

program 4

INSTRUCTIONS
Stack

Variables

Constraints

ValuesContracts

push:n:x

const

neg

issue

input

program:n:x

var

add

borrow

output:k

drop

alloc

mul

retirecontract:k

dup:kmintimeeq

cloak:m:nlog

roll:kmaxtimerange:ncall

unblindandsigntxorsignidnotsigntag

verifyINSTRUCTIONS
Stack

Variables

Constraints

ValuesContracts

push:n:x

const

neg

issue

input

program:n:xvar

addborrow

output:kdrop

alloc

mul

retirecontract:k

dup:kmintimeeq

cloak:m:nlog

roll:kmaxtimerange:ncall

unblindandsigntx

orsignid

notsigntag

verifyBitcoin: 88

Ethereum: 77

Miniscript: 26

ZkVM: 33 instructions

CRYPTOGRAPHY STACK

Curve25519-Dalek

Vectorized elliptic curve operations.

CRYPTOGRAPHY STACK

Ristretto255

Safe prime order group.

Curve25519-Dalek

Vectorized elliptic curve operations.

CRYPTOGRAPHY STACK

Bulletproofs

Versatile zero-knowledge proof system.

Ristretto255

Safe prime order group.

Curve25519-Dalek

Vectorized elliptic curve operations.

CRYPTOGRAPHY STACK

Cloak

Network rules.

Bulletproofs

Versatile zero-knowledge proof system.

Ristretto255

Safe prime order group.

Curve25519-Dalek

Vectorized elliptic curve operations.

CRYPTOGRAPHY STACK

Cloak

Constraints

Network rules + custom rules.

Bulletproofs

Versatile zero-knowledge proof system.

Ristretto255

Safe prime order group.

Curve25519-Dalek

Vectorized elliptic curve operations.

CRYPTOGRAPHY STACK
Instructions
Cloak

Constraints

Arithmetic + boolean operations.
Network rules + custom rules.

Bulletproofs

Versatile zero-knowledge proof system.

Ristretto255

Safe prime order group.

Curve25519-Dalek

Vectorized elliptic curve operations.

CRYPTOGRAPHY STACKYour protocol

Vaults, payment channels, order books, ...

Instructions

Arithmetic + boolean operations.

Cloak

Constraints

Network rules + custom rules.

Bulletproofs

Versatile zero-knowledge proof system.

Ristretto255

Safe prime order group.

Curve25519-Dalek

Vectorized elliptic curve operations.

CRYPTOGRAPHY STACKYour protocol

Vaults, payment channels, order books, ...

Instructions

Arithmetic + boolean operations.

Cloak
pure RustConstraints

Network rules + custom rules.

Bulletproofs

Versatile zero-knowledge proof system.

Ristretto255

Safe prime order group.

Curve25519-Dalek

Vectorized elliptic curve operations.

CONSTRAINTS
Ad-hoc composition of arithmetic and boolean expressions:(P = B + R·T) OR (X = Y)

R T mul B add P eq X Y eq or verify

CONSTRAINTS

EX: CUSTOM CONSTRAINTS
Stack

Variables

Constraints

ValuesContracts

push:n:x

const

neg

issue

input

program:n:xvar

addborrow

output:k

drop

allocmulretire

contract:k

dup:kmintimeeq

cloak:m:nlog

roll:kmaxtimerange:ncall

unblindandsigntx

orsignidnotsigntag

verifyCreate variables from commitments, make expressions,form constraints and add them to the constraint system.

EX: CUSTOM CONSTRAINTS
Stack

Variables

Constraints

ValuesContracts

push:n:x

const

neg

issue

input

program:n:x

var

add

borrow

drop

alloc

mul

dup:k

mintimeeq

roll:kmaxtimerange:ncall

unblindandsigntx

orsignidnotsigntag–V+V

output:k

retirecontract:kcloak:m:nlog

verifyA variable defines a payment constraint with borrow + output.
Negative value is mixed with an actual payment in the cloak.

LINEAR TYPES + CAPABILITIESIn ZkVM contracts imperatively express their requirements,
entirely avoiding bugs like confused deputy problem.

ZkVM TRADEOFFSNOT TURING-COMPLETE
ZkVM optimized for financial uses, not arbitrary computations:• issuing tokens and fundraising,• multi-party vaults,• derivative instruments,• payment channels.

O(n) BLOCKCHAIN• Only zkSNARKs allow efficient compression (e.g. Coda).
• SPV clients use ≈50x less traffic than full blocks.
• Bootstrap from trusted source via Utreexo roots.

PRIVACY FEATURES
PrivateNot private

Asset types

Programs

Asset quantities

Transaction graph

Data parameters
In-transaction flow

PRIVACY FEATURES
PrivateNot private

Asset types

Programs

Asset quantities

Transaction graph

Data parameters
In-transaction flow

Taproot reveals only indispute and only aspecific branch.

PRIVACY FEATURES

Taproot reveals only indispute and only aspecific branch.

PrivateNot private

Asset types

Programs

Asset quantities

Transaction graph

Data parameters
In-transaction flow

CoinJoin scales better.
Hiding UTXO links requires
O(n) storage (nullifiers).

PERFORMANCEPERFORMANCE
1Fast<1 ms per output (up to 1000 tx/sec).
••••

vectorized implementation of Curve25519,
signature aggregation,state of the art multi-scalar multiplication,≈1.5 Kb/proof, marginal cost 0.2–0.5 Kb/transfer.

PERFORMANCE
1Fast<1 ms per output (up to 1000 tx/sec).

2Always fast

Custom constraints are relatively cheap.
• rangeproofs for output values bear most of the cost,• signatures and custom constraints: 1-5% overhead.

PERFORMANCE1Fast<1 ms per output (up to 1000 tx/sec).

2

Always fast

Custom constraints are relatively cheap.

3

Scales with privacy

Aggregation saves space and time.

• proof size is log(N), marginal cost goes to zero,• larger batches of ECC operations take N/log(N) time.

PERFORMANCE
1Fast<1 ms per output (up to 1000 tx/sec).

2

Always fast

Custom constraints are relatively cheap.

3

Scales with privacy

4Free storage Utreexo makes storage costs negligible.

Aggregation saves space and time.

• storage costs log(N) (≈1 kilobyte without caching),• bandwidth overhead is 5-10% with caching(+ tens of megabytes)

SMALL AND SAFE
Small, pure-Rust codebase:
6K LOCzkvm + utreexo + blockchain (w/o consensus)

7K LOCschnorr + musig + keytree + bulletproofs

14K LOC

curve25519 + ristretto255

Assumptions:
ECDLP on Curve25519
Keccak (SHAKE128) is a random oracle

LEARN MORE & PARTICIPATE
Code and specs:
github.com/stellar/slingshot
See also:
github.com/dalek-cryptography/bulletproofs
ristretto.groupmerlin.cool

THANK YOUbulleOleg Andreev@oleganza

Project Slingshot is sponsored by Stellar Development Foundation.

ZkVMt p ro ofs