Report

ZeroCash: ZeroCoin meets SCIPR-lab www.zerocoin.org www.SCIPR-lab.org Eli Ben-Sasson (Technion), Joint work with Alessandro Chiesa (MIT), Christina Garman (JHU), Matthew Green (JHU), Ian Miers (JHU), Eran Tromer (TAU), Madars Virza (MIT) Bitcoin’s Anonimity Problem (BAP) • BAP: – If Alice pays Bob in Bitcoins, she gains information about his spending of those coins … – … And Bob gains information about Alice’s spending of her other Bitcoins • How? Analyze transaction-graph [Reid, Harrigan`11; …] • Solution: Use a bitcoin mix/laundry/tumbler – give Bitcoins to trusted pool, retrieve later – Problems: (1) every tx must go thru mix, (2) trust mix? – Acceptable if have much to hide, not so for average honest user • ZeroCash practically solves Bitcoin’s anonymity problem Should we solve Bitcoin’s Anonymity Problem? • Is ZeroCash good or evil? • To answer that, first answer – Is Bitcoin good? Is a decentralized payment system good? Yes! – (Is a decentralized info./comm. system – Internet – good?) Yes! – Is it good for such a system to leak (part of) your spending information to every one of your payers and payees? No Ergo, ZeroCash is good • But what about regulation? – It is up to society to agree on the acceptable regulation of Bitcoin and similar decentralized payment systems – Jury still out (ditto for Internet) – When decisions are made, the “engine” under ZeroCash’s hood (Zero Knowledge Proofs) can help implement! Talk outline • Anonymous electronic payments – Pre-bitcoin – e-cash and beyond – Post-bitcoin – Zerocoin, PinnochioCoin – Introducing ZeroCash • Zero Knowledge (ZK) – SNARKs – SCIPR-lab • ZeroCash: a peek under the hood Pre-bitcoin anonymous e-cash (BAP: Blockchain structure leaks information to payer and payee) • E-cash [Chaum `82,…] – Anonymous – Blind signatures by bank’s secret key used to mint coins – Problems: (1) central secret, (2) central trusted party • [Sander, Ta-Shma `99] removed need for secret – Bank mints coins using Zero-Knowledge (ZK) arguments and Merkle trees (more on these later) – Anonymous, secret-less, efficient* e-cash system – Problems: (2) central trusted party, (3) divisibility * Assuming efficient non-interactive ZK arguments of knowledge. Post-bitcoin anonymous e-cash • Zerocash: divisible anonymous e-cash on ofSander • [based Solves the problems zerocoin andTa-Shma pinnochio-coin: `99] • – Efficiency ZeroCoin Garman, Green, Rubin `13] * at 128-bit • 288 [Miers, bytes/spend security level, – – –– – • Uses efficient* ZK9ms/spend proofs and* RSA-accumulator • Verification: Extends Bitcoin3min./spend with `decentralized laundry’ * on single • Tx created core i7 @ 2.7 GHz No Bank, only trusted ledger (e.g., Blockchain) Tx-generation scales logarithmically with #coins Implemented as Bitcoin extension! Fine print – – – – Relatively new crypto assumptions – pairing-based cryptography, knowledgeof-exponent, … -- can use more cryptanalysis To spend, need (public) key of size 0.9Gb (downloaded only once) Public key must be set up (only once) by trusted party using a random trapdoor which must be destroyed (no secrets afterwards) … otherwise party with trapdoor can forge tx, but cannot break anonymity (up to 264 coins) – Fungible and divisible, hides payer, payee, and denomination • Usual restrictions and disclaimers, read fine print Problems •• Fine print – Efficiency: 25Kb/spend, must appear on blockchain Non-fungible, non-divisible, single-denomination system (allowing –– Relatively new crypto assumptions – pairing-based fungibility/divisibility compromises anonymity) cryptography, knowledge-of-exponent, … -- can use more cryptanalysis • Pinocchio-Coin [Danezis, Fournet, Kohlweiss, Parno ‘13] –– To spend, need (public) key of size 0.9Gb (downloaded only Done concurrently to, and independently of, ZeroCash – once) Solves efficiency problem: 344 bytes/spend* ! based on “Pinnochio” [Parno et al. `13] –– Public key must beZKset up (only once) by trusted party using a – random Scalabilitytrapdoor problem: tx-generation time linearly with which must begrows destroyed (no#coins secrets – afterwards) Non-fungible/divisble, single-denomination (same as Zerocoin) – … otherwise party with trapdoor can forge tx, but cannot * Size of break anonymity the ZK-proof part of a spend-tx; actual spend-tx size is larger Talk outline • Anonymous electronic payments – Pre-bitcoin – e-cash and beyond – Post-bitcoin – Zerocoin, PinnochioCoin – Introducing ZeroCash • Zero Knowledge (ZK) – SNARKs – SCIPR-lab • ZeroCash: a peek under the hood Zero Knowledge [Goldwasser, Micali, Rackoff ‘89] • Concrete bitcoin-based statement+proofs • ZK-proof of knowledge: cryptographic proof that – Statement: “I own 30 bitcoins with total value 123.5 BTC” Ownership means knowledge of coin-keys. – proof: point to 30 coins on blockchain, use each coin-key to encrypt a message – Problem: proof leaks knowledge about coin-ownership! – – – – • cannot be (efficiently) generated without knowing keys can be efficiently generated with keys can be easily verified reveals no information about coins ZK-proofs exist for any statement that can be efficiently computable with auxiliary secrets/trapdoors (NP-statement) – How? Magic! (2009 Godel award; 2012 Turing Award to Goldwasser+Micali) • Efficiency of ZK-proofs is a huge research topic, • ZeroCash uses cutting-edge techniques from SCIPR-lab Academic pedigree of ZeroCash’s “ZK engine” • Theory – We use a ZK preprocessing Succinct Noninteractive ARgument of Knowledge (SNARK for short), aka succinct NIZK, succinct CS proof, ZKA, … – Construction relies on pairings over elliptic curves, quadratic span programs, linear PCPs, FFTs, quasilinear PCPs, … […; Groth; Lipmaa; Ishai, Kushilevitz, Ostrovsky; Gennaro, Gentry, Parno, Raykova; Bitansky, Chiesa, Ishai, Ostrovsky, Paneth; Ben-Sasson, Chiesa, Genkin, Tromer; … 2010-14] • Implementations (for general purpose programs) – Pinnochio [Parno, Gentry, Howell, Raykova `13] – “SNARKs for C” [B, Chiesa, Genkin, Tromer, Virza `13] by SCIPR-lab www.SCIPR-lab.org “… is an academic collaboration of researchers from MIT, Technion, and Tel Aviv University, seeking to bring to practice cryptographic proof systems that provide Succinct Computational Integrity and PRrivacy.” • Started in summer 2009 with Eran Tromer (co-PI), Alessandro Chiesa, Daniel Genkin. Madars Virza joined 2012 • Initial funding: European Research Council (grant # 240258), major source of support for programming team: Ohad Barta*, Lior Greenblat, Shaul Kfir, Michael Riabzev, Gil Timnat, Arnon Yogev* (* emeritus) [Ad: seeking superb crypto+math programmer!] SCIPR-lab meets ZeroCoin • Both presented at Bitcoin 2013, San Jose ZeroCoin video SCIPR-lab video – SCIPR-lab builds general-purpose programs (“Turing complete”) CRYPTO`13 video Powerful, yet cumbersome systems – ZeroCoin needs specific optimized program • … ZeroCash Talk outline • Anonymous electronic payments – Pre-bitcoin – e-cash and beyond – Post-bitcoin – Zerocoin, PinnochioCoin – Introducing ZeroCash • Zero Knowledge (ZK) – SNARKs – SCIPR-lab • ZeroCash: a peek under the hood ZeroCash and Base-currency • ZeroCash works over any base-currency with – public ledger and consensus mechanism (like PoW) – Like BitCoin and its offspring • ZeroCash supports – Transactions of base-currency – Converting coins to ZeroCash and vice versa – Fully anonymous ZeroCash transactions … • Fungible and divisible, • Splitting and merging of coins, • Hidden coin-owner and coin values – … with public transaction fees (and other payments) on them ZeroCash transactions • Mint: (no ZK-SNARK) – Converts a base-currency coin with value v into new ZeroCash coin c with value v • Pour: (uses ZK-SNARK) – Takes the sum value v of (up to) 2 ZeroCash coins and – Pours v into (up to) • 2 new ZeroCash coins (hidden values), • 1 public payment (public value) Disclaimer: Simplified ZeroCash protocol, real one to appear in paper Pour-tx, viewed by Full-node (verifier) • • – – • Full-nodes (verifiers) maintain – Merkle tree of all previous coins – List of all previously exposed serial numbers – Crucial: observer cannot link sn to c ! a1= H(c1, c2) a2= H(c3, c4) Pour-tx is (sn, sn’, r, vpub, c’’,c’’’, π,…) – – – – – • addrpub = f(addrsec), f is pseudorandom function (PRF) Serial number is sn = f(addrsec, rserial), “destroys” coin when displayed on ledger … • r= H(z1, z2) Coin is commitment c:= hash(val, rserial , addrpub), controlled by secret address addrsec sn, sn’ destroy 2 old coins (preventing double-spend) c1 r is root of (current) Merkle tree vpub is public value (used, e.g., for tx-fee) c’’, c’’’ new coins π is a 288-byte long ZK-SNARK for a statement described later c2 c3 c4 … L={sn1, sn2, … } When full-node sees new pour-tx: 1. 2. 3. Verifies π (9 ms) Checks that sn, sn’ haven’t appeared and adds them to L If 1,2 pass, then adds c’’, c’’’ to tree, updates root r, and collects vpub Disclaimer: Simplified ZeroCash protocol, real one to appear in paper Constructing Pour-tx (prover) • Coin is commitment c:= hash(val, rserial , addrpub) r= H(z1, z2) • controlled by secret address addrsec – addrpub = f(addrsec), f is pseudorandom function (PRF) – Serial number is sn = f(addrsec, rserial), “destroys” coin when displayed on ledger • Inputs … – 2 coins c, c’, hidden information, and location in tree – Information for new coins: • values v’’,v’’’,vpub • Public addresses of payees addr’’pub, addr’’’pub – Proving key (0.9 Gb long) • Pour-tx is (sn, sn’, r, vpub, c’’,c’’’, π, …) π is a ZK-SNARK proof of statement: • What about Bitcoin/ZeroCash regulation? c1 c2 c3 c4 … L={sn1, sn2, … } – When society decides on appropriate measures, efficient ZKproofs can help implement them “know location of coins c, c’ in tree with root r, know coin values v, v’ and computed correctly serial numbers as sn, sn’, know hidden values v’’, v’’’ of c’’, c’’’ and sum of old coins (v+v’) equals that of new ones paid (v’’+v’’’+vpub) and … “ due taxes and contributed 10% to charity …“ Disclaimer: Simplified ZeroCash protocol, real one to appear in paper ZeroCash: SCIPR-lab meets ZeroCoin • First fungible, divisible, anonymous payment system based on decentralized ledger (like Bitcoin), with implementation, • which solves Bitcoin’s Anonymity Problem, • using cutting-edge constructions of ZK-proofs When will ZeroCash be ready? – Paper published May 18 @ “Oakland Security” conference (hopefully earlier online) – Code to be open-sourced when ready – No further comments on deployment [Ad: SCIPR-lab needs superb crypto+math programmer]