Zero-knowledge proofs for
Bitcoin scalability and beyond
Madars Virza(based on joint works with Eli Ben-Sasson, Alessandro Chiesa,
Christina Garman, Daniel Genkin, Matthew Green,Shaul Kfir, Ian Miers and Eran Tromer)1Outline
1. A very brief intro to zero-knowledge proofs
2. The power of ZK for Bitcoin scalability
3. Zero-knowledge in practice …
Can zero-knowledge proofs be implemented?
How to “program” zero-knowledge proofs?
How to deploy them in real systems?
2

[GMR89][BFM88][NY90][BDMP91]

Non-Interactive
Zero Knowledge
E.g.
Circuit-SAT

instance witness

prover…

verifier

Completeness:
Soundness:
Zero knowledge:

3

NIZKsOnce: initial
trusted setup

common reference string

Many times

Thm: Impossible for NP (without any help)
Thm: Possible for NP with help of CRS.

[GMR85, GO94][BFM88, NY90, BDMP91]
4

Many scalability problems can betraced back to questions about privacy
Fungibility: if all transactions are public, receiving “wrong”
change for coffee could taint & devalue your coins
Solvency: if proving solvency is privacy liability (thus not done)
you get distrust in traditional service providers
Decentralization: if miners can’t covertly repurpose their work,
you get strong incentives for pooling and miner centralization

Claim: zero-knowledge proofs helpful for all of above!
“Proof”: by example…
5

(based on a scheme by Sanders and Ta-Shma)…
MintSpend“I hereby destroy
1 BTC and create an
anonymous coin withcommitment cm”

Publish sn, nonce

cm3 cm4cm2

HH
Hcm = H(sn, nonce)

cm1rt(2) Publishing sn ensures no double-spending
Zerocash builds upon this adding direct payments, divisibility, …

6(Provisions [DBBCB15])
solvency = “assets > liabilities”
privacy-preserving = “reveal nothing about keys & balances”

Two hiding commitments: cmasset=H(vasset, r) and cmliab = H(vliab, r’)Three kinds of statements:“I can open cmasset and cmliab
to vasset and vliab where vasset > vliab”

2. Each account balance is included in vliab:
User
Alice
BobCharlie

Balance
v1
v2
v3…

…

a) Publish commitments to all balancesb) Prove to user i that cmi opens to vic) Prove that cmliab sums values of all cmi

3. Exchange controls at least vasset BTC:
Fix a large anonymity set of public keys and their balances.
Prove knowledge of private keys for a subset that controls vasset 7

Outline
1. A very brief intro to zero-knowledge proofs
2. The power of ZK for Bitcoin scalability
3. Zero-knowledge in practice …
Can zero-knowledge proofs be implemented?
How to “program” zero-knowledge proofs?
How to deploy them in real systems?
8

NIZKsE.g. Schnorr proofs, CT range proofs

vsSNARKs(Succinct Non-Interactive
Arguments of Knowledge)[Mic00, GW11,BCCT12, BCIOP13]

Efficiency:

Efficiency:

Sufficient assumptions:Sufficient assumptions:- trapdoor permutations- decision linear assumption (DLIN)“Simple” CRS- random oracle- knowledge-of-exponent [D92, HT98]“Complex” CRS

9

Finding a SNARK(i) Theoretical constructions[Killian92, Micali94, Valiant08, Mie08, DL08, Groth10, GLR11, BCCT12, DFH12,BC12, Lipmaa12, BCIOP13, GGPR13, PGHR13, BCGTV13, Lipmaa13, FLZ13,BCCT13, BCTV14a,BCCGLRT14, BCTV14b, Lipmaa14, KPPSST14, ZPK14, DFGK14,WSRBW15, BBFR15, CFHKKNPZ15](ii) Working prototypes
Buffet & Pantry www.pepper-project.org [BFRSBW14, WSRBW15]
libsnark.org[BCGTV13,BCGTV14]libsnark[PGHR13,CFHKKNPZ15]
Pinocchio & Geppetto vc.codeplex.com
Most have full source code available!

(iii) Implemented systems
SNARKs are feasible for certain applications!
E.g.: Zerocash [BCGGTV14], Hawk [MSKK15], …

10

How to program SNARKs
Relation I have in mind:
Hashes, Merkle trees,
digital signatures,…

?

Relations SNARKs understand:Circuitsatisfiability

The “SNARKS for C” approach:P.cP.asm +The program analysis approach:P.c-2. Use a circuit generator for that subset(* - all memory accesses & bounds on loops must be known at compile time)

The “gadget DSL” approach:

SNARK
SHA256
Lots of pre-written verifier EC arithm.

gadgets in libsnark!

11

SNARK performance in practice
Prover performance = base SNARK performance(size of circuit)[MKKS15] prover benchmarks for 470k gate circuit:
Pinocchio: 1242s
libsnark: 33s
Concretely: implementing SHA256 compression function
Approach

Compression “Capacity” of 470k
function sizegate circuit

SNARKS for C / TinyRAM
Pinocchio circuit generator*
libsnark gadgets(* invoked on a SH256 C implementation fromPolarSSL)

Crucial for efficient use: relation engineering- Try to check local properties (“is the tx OK?” not “is the chainOK?”)- Understand and leverage non-determinism- Consider SNARK-friendly crypto [BCTV14b, KZMQCPPSS15]

12

Deploying NIZKs and SNARKs?

Q: In practice, who generates the CRS?
13

Consequences of a “bad” CRS
1) Zero-knowledge still holds:
e.g. Zerocash remains private even with a bad CRS)

2) Soundness breaks:
adversary can prove false statements

Some uses of SNARKs are not consensus-critical

Q: Can consensus-critical SNARKs be deployed?
14

Goal: distributed protocol for CRS of SNARKs
Ideal world

Real world…

Result: a protocol achieving this!

[BCGTV15]

Costs for Zerocash CRS: 4h/party CPU and 13GB/party data.
15

Conclusion
Many scalability problems can be traced back toprivacy.
Zero-knowledge proofs are a very useful tool for building
privacy-preserving systems.
Generic zero-knowledge is not “ten-year-away crypto”… it was “ten-year-away crypto” ten years ago!
Feasible today: can be programmed & can be deployed!
Call for collaboration: help us improve libsnark!
We seek all kinds of contributions: security audits,performance enhancements, new features, …
http://libsnark.org/help
16

Thank you!

http://libsnark.org/help
17