Zerocash: Decentralized Anonymous Payments from Bitcoin (extended version) Eli Ben-Sasson∗ Alessandro Chiesa† Christina Garman‡ Matthew Green‡ Ian Miers‡ Eran Tromer§ Madars Virza† May 18, 2014 Abstract Bitcoin is the first digital currency to see widespread adoption. Although payments are conducted between pseudonyms, Bitcoin cannot offer strong privacy guarantees: payment transactions are recorded in a public decentralized ledger, from which much information can be deduced. Zerocoin (Miers et al., IEEE S&P 2013) tackles some of these privacy issues by unlinking transactions from the payment’s origin. Yet it still reveals payment destinations and amounts, and is limited in functionality. In this paper, we construct a full-fledged ledger-based digital currency with strong privacy guarantees. Our results leverage recent advances in zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs). We formulate and construct decentralized anonymous payment schemes (DAP schemes). A DAP scheme lets users pay each other directly and privately: the corresponding transaction hides the payment’s origin, destination, and amount. We provide formal definitions and proofs of the construction’s security. We then build Zerocash, a practical instantiation of our DAP scheme construction. In Zerocash, transactions are less than 1kB and take under 6ms to verify — orders of magnitude more efficient than the less-anonymous Zerocoin and competitive with plain Bitcoin. Keywords: Bitcoin, decentralized electronic cash, zero-knowledge proofs ∗Technion, [email protected] †MIT, {alexch, madars}@mit.edu ‡Johns Hopkins University, {cgarman, imiers, mgreen}@cs.jhu.edu §Tel Aviv University, [email protected] 1 Contents 1 Introduction 3 1.1 zk-SNARKs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Centralizedanonymouspaymentsystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Decentralizedanonymouspaymentschemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Zerocash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Paperorganization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Background on zk-SNARKs 10 2.1 Informaldefinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 ComparisonwithNIZKs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Knownconstructionsandsecurity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 zk-SNARKimplementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Definition of a decentralized anonymous payment scheme 13 3.1 Datastructures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.4 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4 Construction of a decentralized anonymous payment scheme 18 4.1 Cryptographicbuildingblocks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 zk-SNARKsforpouringcoins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 Algorithmconstructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.4 Completenessandsecurity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5 Zerocash 20 5.1 Instantiationofbuildingblocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.2 Arithmeticcircuitforpouringcoins. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6 Integration with existing ledger-based currencies 26 6.1 Integrationbyreplacingthebasecurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6.2 Integrationbyhybridcurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 6.3 ExtendingtheBitcoinprotocoltosupportthecombinedsemantics . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.4 Additionalanonymityconsiderations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 7 Experiments 28 7.1 Performanceofzk-SNARKsforpouringcoins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.2 PerformanceofZerocashalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.3 Large-scalenetworksimulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 8 Optimizations and extensions 33 8.1 Everlastinganonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 8.2 Fastblockpropagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 8.3 Improvedstoragerequirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 9 Concurrent work 36 10Conclusion 36 Acknowledgments 37 A Overview of Bitcoin and Zerocoin 38 A.1 Bitcoin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 A.2 Zerocoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 B Completeness of DAP schemes 39 C Security of DAP schemes 40 C.1 Ledgerindistinguishability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 C.2 Transactionnon-malleability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 C.3 Balance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 D Proof of Theorem 4.1 44 D.1 Proofofledgerindistinguishability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 D.2 Proofoftransactionnon-malleability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 D.3 Proofofbalance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 References 54 2 1 Introduction Bitcoin is the first digital currency to achieve widespread adoption. The currency owes its rise in part to the fact that, unlike traditional e-cash schemes [Cha82, CHL05, ST99], it requires no trusted parties. Instead of appointing a central bank, Bitcoin uses a distributed ledger known as the block chain to store transactions carried out between users. Because the block chain is massively replicated by mutually-distrustful peers, the information it contains is public. While users may employ many identities (or pseudonyms) to enhance their privacy, an increasing body of research shows that anyone can de-anonymize Bitcoin by using information in the block chain [RM11, BBSU12, RS12, MPJ+13], such as the structure of the transaction graph as well as the value and dates of transactions. As a result, Bitcoin fails to offer even a modicum of the privacy provided by traditional payment systems, let alone the robust privacy of anonymous e-cash schemes. While Bitcoin is not anonymous itself, those with sufficient motivation can obfuscate their transaction history with the help of mixes (also known as laundries or tumblers). A mix allows users to entrust a set of coins to a pool operated by a central party and then, after some interval, retrieve different coins (with the same total value) from the pool. However, mixes suffer from three limitations: (i) the delay to reclaim coins must be large to allow enough coins to be mixed in; (ii) the mix operator can trace coins; and (iii) the mix operator may steal coins.1 For users with “something to hide”, these risks may be acceptable. But typical legitimate users (1) wish to keep their spending habits private from their peers, (2) are risk-averse and do not wish to expend continual effort in protecting their privacy, and (3) are often not sufficiently aware that their privacy has been compromised. To protect their privacy, users thus need an instant, risk-free, and, most importantly, automatic guarantee that data revealing their spending habits and account balances is not publicly accessible by their neighbors, co-workers, and the merchants with whom they do business. Anonymous transactions also ensure that the market value of a coin is independent of its history, thus ensuring that legitimate users’ coins remain fungible.2 Zerocoin: a decentralized mix. Miers et al. [MGGR13] proposed Zerocoin, which extends Bitcoin to provide strong anonymity guarantees. Like many e-cash protocols (e.g., [CHL05]), Zerocoin employs zero-knowledge proofs to prevent transaction graph analyses. Unlike earlier practical e-cash protocols, however, Zerocoin does not rely on digital signatures to validate coins, nor does it require a central bank to prevent double spending. Instead, Zerocoin authenticates coins by proving, in zero-knowledge, that they belong to a public list of valid coins (which can be maintained on the block chain). Yet rather than a full-fledged anonymous currency, Zerocoin is a decentralized mix, where users may periodically “wash” their bitcoins via the Zerocoin protocol. Routine day-to-day transactions must be conducted via Bitcoin, due to reasons that we now review. The first reason is performance. Redeeming zerocoins requires double-discrete-logarithm proofs of knowledge, which have size that exceeds 45kB and require 450ms to verify (at the 128-bit security level).3 These proofs must be broadcast through the network, verified by every node, and permanently stored in the ledger. The entailed costs are higher, by orders of magnitude, than those in Bitcoin and can seriously tax a Bitcoin network operating at normal scale. 1CoinJoin [Max13], an alternative proposal, replaces the central party of a mix with multi-signature transactions that involve many collaborating Bitcoin users. CoinJoin can thus only mix small volumes of coins amongst users who are currently online, is prone to denial-of-service attacks by third parties, and requires effort to find mixing partners. 2Whilethemethodswedetailinthispaperaccomplishthis,thesametechniquesopenthedoorforprivacy-preserving accountability and oversight (see Section 10). 3These published numbers [MGGR13] actually use a mix of parameters at both 128-bit and 80-bit security for different components of the construction. The cost is higher if all parameters are instantiated at 128-bit security. 3 The second reason is functionality. While Zerocoin constitutes a basic e-cash scheme, it lacks critical features required of full-fledged anonymous payments. First, Zerocoin uses coins of fixed denomination: it does not support payments of exact values, nor does it provide a means to give change following a transaction (i.e., divide coins). Second, Zerocoin has no mechanism for one user to pay another one directly in “zerocoins”. And third, while Zerocoin provides anonymity by unlinking a payment transaction from its origin address, it does not hide the amount or other metadata about transactions occurring on the network. Our contribution. Addressing this challenge, this work offers two main contributions. (1) We introduce the notion of a decentralized anonymous payment scheme, which formally captures the functionality and security guarantees of a full-fledged decentralized electronic currency with strong anonymity guarantees. We provide a construction of this primitive and prove its security under specific cryptographic assumptions. The construction leverages recent advances in the area of zero-knowledge proofs. Specifically, it uses zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) [Gro10, Lip12, BCI+13, GGPR13, PGHR13, BCG+13, Lip13, BCTV14]. (2) We implement the above primitive, via a system that we call Zerocash. Our system (at 128 bits of security): • reduces the size of transactions spending a coin to under 1kB (an improvement of over 97.7%); • reduces the spend-transaction verification time to under 6ms (an improvement of over 98.6%); • allows for anonymous transactions of variable amounts; • hides transaction amounts and the values of coins held by users; and • allows for payments to be made directly to a user’s fixed address (without user interaction). To validate our system, we measured its performance and established feasibility by conducting experiments in a test network of 1000 nodes (approximately 1 of the unique IPs in the Bitcoin 16 network and 1 of the nodes reachable at any given time [DW13]). This inspires confidence that 3 Zerocash can be deployed as a fork of Bitcoin and operate at the same scale. Thus, due to its substantially improved functionality and performance, Zerocash makes it possible to entirely replace traditional Bitcoin payments with anonymous alternatives. Concurrent work. The idea of using zk-SNARKs in the Bitcoin setting was first presented by one of the authors at Bitcoin 2013 [Ben13]. In concurrent work, Danezis et al. [DFKP13] suggest using zk-SNARKs to reduce proof size and verification time in Zerocoin; see Section 9 for a comparison. 1.1 zk-SNARKs A zk-SNARK is an efficient variant of a zero-knowledge proof of knowledge [GMR89], which we first informally describe via an example. Suppose Alice wishes to prove to Bob the statement “I (Alice) own 30 bitcoins”. A simple method for Alice to do so is to point to 30 coins on the block chain and, for each of them, sign a message (“hello, world”) using the secret key that controls that coin. Alas, this method leaks knowledge to Bob, by identifying which coins are Alice’s. A zero-knowledge proof of knowledge allows Alice to achieve the same goal, while revealing no information to Bob (beyond the fact that she knows some secret keys that control 30 coins). Crucially, such proofs can be obtainedforanystatementthatcanbeverifiedtobetruebyuseofanefficientcomputationinvolving auxiliary inputs such as trapdoors and passwords (such statements are called “NP statements”). We now sketch in more technical terms the definition of a zk-SNARK; see Section 2 for more details. A zk-SNARK is a non-interactive zero-knowledge proof of knowledge that is succinct, i.e., for which proofs are very short and easy to verify. More precisely, let L be an NP language, and let C be a nondeterministic decision circuit for L on a given instance size n. A zk-SNARK can be used 4 to prove and verify membership in L, for instances of size n, as follows. After taking C as input, a trusted party conducts a one-time setup phase that results in two public keys: a proving key pk and a verification key vk. The proving key pk enables any (untrusted) prover to produce a proof π attesting to the fact that x ∈ L, for an instance x (of size n) of his choice. The non-interactive proof π is zero knowledge and a proof of knowledge. Anyone can use the verification key vk to verify the proof π; in particular zk-SNARK proofs are publicly verifiable: anyone can verify π, without ever having to interact with the prover who generated π. Succinctness requires that (for a given security level) π has constant size and can be verified in time that is linear in |x| (rather than linear in |C|). 1.2 Centralized anonymous payment systems Before describing our new decentralized payment system, we put it in context by recalling two pre-Bitcoin payment schemes, both of which relied on a bank, acting as a central trusted party. Anonymous e-cash. Chaum [Cha82] first obtained anonymous e-cash. In Chaum’s scheme, the minting of a coin involves both a user, Alice, and the bank: to mint a coin of a given value v, Alice first selects a random secret serial number sn (unknown to the bank); then, the bank, after deducting v from Alice’s balance, signs sn via a blind signature. Afterwards, if Alice wants to transfer her coin to Bob, she reveals sn to him and proves that sn was signed by the bank; during this transfer, Bob (or the bank) cannot deduce Alice’s identity from the revealed information. Double-spending is prevented because the bank will not honor a coin with a previously-seen serial number. Unforgeable e-cash. One problem with Chaum’s scheme is that coins can be forged if the bank’s secret key is compromised. Sander and Ta-Shma [ST99] addressed this, as follows. The bank maintains a public Merkle tree of “coin commitments”, and users periodically retrieve its root rt; in particular, the bank maintains no secrets. When Alice requests a coin (of unit value), she picks a random serial number sn and auxiliary string r, and then sends cm := CRH(sn(cid:107)r) to the bank, where CRH is a collision-resistant hash; the bank deducts the appropriate amount from Alice’s balance and then records cm as a leaf in the Merkle tree. Afterwards, to pay Bob, Alice sends him sn along with a zero-knowledge proof of knowledge π of the following NP statement: “there exists r such that CRH(sn(cid:107)r) is a leaf in a Merkle tree with root rt”. In other words, Alice can convince Bob that sn is the serial number contained in some coin commitment in the Merkle tree; but the zero-knowledge property prevents Bob from learning information about which coin commitment is Alice’s, thereby protecting Alice’s identity. Later, Bob can “cash out” Alice’s coin by showing sn and π to the bank.4 Moving to a fungible anonymous decentralized system. In this paper, like [ST99], we hash a coin’s serial number and use Merkle trees to compactly represent the set of minted coins. Unlike [ST99], we also ensure the privacy of a coin’s value and support transactions that split and merge coins, thus achieving (and implementing) a new kind of fully-fungible and divisible payment scheme. As in Bitcoin (and in stark contrast to previous e-cash schemes), we do not rely on a trusted bank. Therefore, we require a new set of definitions and protocols, designed to protect Alice’s anonymity while preventing her from falsely increasing her balance under the veil of her boosted privacy. An informal description of our payment scheme follows. 1.3 Decentralized anonymous payment schemes We construct a decentralized anonymous payment (DAP) scheme, which is a decentralized e-cash scheme that allows direct anonymous payments of any amount. See Section 3 for a formal definition. 4We omit details about how the bank can identify Alice in the event that she double spends her coin. 5 Here, we outline our construction in six incremental steps; the construction details are in Section 4. Our construction functions on top of any ledger-based base currency, such as Bitcoin. At any given time, a unique valid snapshot of the currency’s ledger is available to all users. The ledger is a sequence of transactions and is append-only. Transactions include both the underlying currency’s transactions, as well as new transactions introduced by our construction. For concreteness, we focus thediscussionbelowonBitcoin(thoughlaterdefinitionsandconstructionsarestatedabstractly). We assume familiarity with Bitcoin [Nak09] and Zerocoin [MGGR13]; both are reviewed in Appendix A. Step 1: user anonymity with fixed-value coins. We first describe a simplified construction, in which all coins have the same value of, e.g., 1BTC. This construction, similar to the Zerocoin protocol, shows how to hide a payment’s origin. In terms of tools, we make use of zk-SNARKs (recalled above) and a commitment scheme. Let COMM denote a statistically-hiding non-interactive commitment scheme (i.e., given randomness r and message m, the commitment is c := COMM (m); r subsequently, c is opened by revealing r and m, and one can verify that COMM (m) equals c). r In the simplified construction, a new coin c is minted as follows: a user u samples a random serial number sn and a trapdoor r, computes a coin commitment cm := COMM (sn), and sets r c := (r,sn,cm). A corresponding mint transaction tx , containing cm (but not sn or r), is sent to Mint the ledger; tx is appended to the ledger only if u has paid 1BTC to a backing escrow pool (e.g., Mint the 1BTC may be paid via plaintext information encoded in tx ). Mint transactions are thus Mint certificates of deposit, deriving their value from the backing pool. Subsequently, letting CMList denote the list of all coin commitments on the ledger, u may spend c by posting a spend transaction tx that contains (i) the coin’s serial number sn; and (ii) a Spend zk-SNARK proof π of the NP statement “I know r such that COMM (sn) appears in the list CMList r of coin commitments”. Assuming that sn does not already appear on the ledger (as part of a past spend transaction), u can redeem the deposited amount of 1BTC, which u can either keep, transfer to someone else, or mint a new coin. (If sn does already appear on the ledger, this is considered double spending, and the transaction is discarded.) User anonymity is achieved because the proof π is zero-knowledge: while sn is revealed, no information about r is, and finding which of the numerous commitments in CMList corresponds to a particular spend transaction tx is equivalent to inverting f(x) := COMM (sn), which is Spend x assumed to be infeasible. Thus, the origin of the payment is anonymous. Step 2: compressing the list of coin commitments. In the above NP statement, CMList is specified explicitly as a list of coin commitments. This naive representation severely limits scalability because the time and space complexity of most protocol algorithms (e.g., the proof verification algorithm) grow linearly with CMList. Moreover, coin commitments corresponding to already-spent coins cannot be dropped from CMList to reduce costs, since they cannot be identified (due to the same zero-knowledge property that provides anonymity). As in [ST99], we rely on a collision-resistant function CRH to avoid an explicit representation of CMList. We maintain an efficiently-updatable append-only CRH-based Merkle tree Tree(CMList) over the (growing) list CMList and let rt denote the root of Tree(CMList). It is well-known that rt can be updated to account for the insertion of new leaves with time and space proportional to just the tree depth. Hence, the time and space complexity is reduced from linear in the size of CMList to logarithmic. With this in mind, we modify the NP statement to the following one: “I know r such that COMM (sn) appears as a leaf in a CRH-based Merkle tree whose root is rt”. Compared with r the naive data structure for CMList, this modification increases exponentially the size of CMList that a given zk-SNARK implementation can support. (Concretely: using Merkle trees of depth 64, Zerocash supports 264 coins.) Step 3: extending coins for direct anonymous payments. So far, the coin commitment 6 cm of a coin c is a commitment to the coin’s serial number sn. However, this creates a problem when transferring c to another user. Indeed, suppose that a user u created c, and u sends c to A A another user u . First, since u knows sn, the spending of c by u is both non-anonymous (since B A B u sees when c is spent, by recognizing sn) and risky (since u could still spend c first). Thus, u A A B must immediately spend c and mint a new coin c(cid:48) to protect himself. Second, if u in fact wants A to transfer to u , e.g., 100BTC, then doing so is both unwieldy (since it requires 100 transfers) B and non-anonymous (since the amount of the transfer is leaked). And third, transfers in amounts that are not multiples of 1BTC (the fixed value of a coin) are not supported. Thus, the simplified construction described is inadequate as a payment scheme. We address this by modifying the derivation of a coin commitment, and using pseudorandom functions to target payments and to derive serial numbers, as follows. We use three pseudorandom functions (derived from a single one). For a seed x, these are denoted PRFaddr(·), PRFsn(·), and x x PRFpk(·). We assume that PRFsn is moreover collision-resistant. x To provide targets for payments, we use addresses: each user u generates an address key pair (a ,a ), the address public key and address private key respectively. The coins of u contain the pk sk value a and can be spent only with knowledge of a . A key pair (a ,a ) is sampled by selecting pk sk pk sk a random seed a and setting a := PRFaddr(0). A user can generate and use any number of sk pk a sk address key pairs. Next, we redesign minting to allow for greater functionality. To mint a coin c of a desired value v, the user u first samples ρ, which is a secret value that determines the coin’s serial number as sn := PRFsn(ρ). Then, u commits to the tuple (a ,v,ρ) in two phases: (a) u computes a pk sk k := COMM (a (cid:107)ρ) for a random r; and then (b) u computes cm := COMM (v(cid:107)k) for a random s. r pk s The minting results in a coin c := (a ,v,ρ,r,s,cm) and a mint transaction tx := (v,k,s,cm). pk Mint Crucially, due to the nested commitment, anyone can verify that cm in tx is a coin commitment Mint of a coin of value v (by checking that COMM (v(cid:107)k) equals cm) but cannot discern the owner (by s learning the address key a ) or serial number (derived from ρ) because these are hidden in k. As pk before, tx is accepted by the ledger only if u deposits the correct amount, in this case v BTC. Mint Coins are spent using the pour operation, which takes a set of input coins, to be consumed, and “pours” their value into a set of fresh output coins — such that the total value of output coins equals thetotalvalueoftheinputcoins. Supposethatu,withaddresskeypair(aold,aold),wishestoconsume pk sk his coin cold = (aold,vold,ρold,rold,sold,cmold) and produce two new coins cnew and cnew, with total pk 1 2 value vnew+vnew = vold, respectively targeted at address public keys anew and anew. (The addresses 1 2 pk,1 pk,2 anew and anew may belong to u or to some other user.) The user u, for each i ∈ {1,2}, proceeds as pk,1 pk,2 follows: (i) u samples serial number randomness ρniew; (ii) u computes kinew := COMMrinew(anpekw,i(cid:107)ρniew) for a random rinew; and (iii) u computes cmniew := COMMsniew(vinew(cid:107)kinew) for a random sniew. This yields the coins cnew := (anew,vnew,ρnew,rnew,snew,cmnew) and cnew := (anew,vnew,ρnew, 1 pk,1 1 1 1 1 1 2 pk,2 2 2 rnew,snew,cmnew). Next, u produces a zk-SNARK proof π for the following NP statement, which 2 2 2 POUR we call POUR: “Given the Merkle-tree root rt, serial number snold, and coin commitments cmnew,cmnew, I 1 2 know coins cold,cnew,cnew, and address secret key aold such that: 1 2 sk • The coins are well-formed: for cold it holds that kold = COMM (aold(cid:107)ρold) and cmold = rold pk COMM (vold(cid:107)kold); and similarly for cnew and cnew. sold 1 2 • The address secret key matches the public key: aold = PRFaddr(0). pk aold sk • The serial number is computed correctly: snold := PRFsn (ρold). aold sk • The coin commitment cmold appears as a leaf of a Merkle-tree with root rt. • The values add up: vnew +vnew = vold.” 1 2 7 A resulting pour transaction tx := (rt,snold,cmnew,cmnew,π ) is appended to the ledger. Pour 1 2 POUR (As before, the transaction is rejected if the serial number sn appears in a previous transaction.) Now suppose that u does not know, say, the address secret key anew that is associated with the sk,1 public key anew. Then, u cannot spend cnew because he cannot provide anew as part of the witness pk,1 1 sk,1 of a subsequent pour operation. Furthermore, when a user who knows anew does spend cnew, the sk,1 1 user u cannot track it, because he knows no information about its revealed serial number, which is snnew := PRFsn (ρnew). 1 anew 1 sk,1 Also observe that tx reveals no information about how the value of the consumed coin was Pour divided among the two new fresh coins, nor which coin commitment corresponds to the consumed coin, nor the address public keys to which the two new fresh coins are targeted. The payment was conducted in full anonymity. More generally, a user may pour Nold ≥ 0 coins into Nnew ≥ 0 coins. For simplicity we consider the case Nold = Nnew = 2, without loss of generality. Indeed, for Nold < 2, the user can mint a coin withvalue0andthenprovideitasa“null”input, andforNnew < 2, theusercancreate(anddiscard) a new coin with value 0. For Nold > 2 or Nnew > 2, the user can compose logNold +logNnew of the 2-input/2-output pours. Step 4: sending coins. Suppose that anew is the address public key of u . In order to allow u pk,1 1 1 to actually spend the new coin cnew produced above, u must somehow send the secret values in 1 cnew to u . One way is for u to send u a private message, but the requisite private communication 1 1 1 channel necessitates additional infrastructure or assumptions. We avoid this “out-of-band” channel and instead build this capability directly into our construction by leveraging the ledger as follows. We modify the structure of an address key pair. Each user now has a key pair (addr ,addr ), pk sk where addr = (a ,pk ) and addr = (a ,sk ). The values (a ,a ) are generated as before. pk pk enc sk sk enc pk sk In addition, (pk ,sk ) is a key pair for a key-private encryption scheme [BBDP01]. enc enc Then, ucomputestheciphertextC thatistheencryptionoftheplaintext(vnew,ρnew,rnew,snew), 1 1 1 1 1 under pknew (which is part of u ’s address public key addrnew), and includes C in the pour enc,1 1 sk,1 1 transaction tx . The user u can then find and decrypt this message (using his sknew ) by Pour 1 enc,1 scanning the pour transactions on the public ledger. Again, note that adding C to tx leaks 1 Pour neither paid amounts, nor target addresses due to the key-private property of the encryption scheme. (The user u does the same with cnew and includes a corresponding ciphertext C in tx .) 2 2 Pour Step 5: public outputs. The construction so far allows users to mint, merge, and split coins. But how can a user redeem one of his coins, i.e., convert it back to the base currency (Bitcoin)? For this, we modify the pour operation to include a public output. When spending a coin, the user u also specifies a nonnegative v and a transaction string info ∈ {0,1}∗. The balance equation pub in the NP statement POUR is changed accordingly: “vnew +vnew +v = vold”. Thus, of the input 1 2 pub value vold, a part v is publicly declared, and its target is specified, somehow, by the string info. pub The string info can be used to specify the destination of these redeemed funds (e.g., a Bitcoin wallet public key).5 Both v and info are now included in the resulting pour transaction tx . (The pub Pour public output is optional, as the user u can set v = 0.) pub Step 6: non-malleability. To prevent malleability attacks on a pour transaction tx (e.g., Pour embezzlement by re-targeting the public output of the pour by modifying info), we further modify the NP statement POUR and use digital signatures. Specifically, during the pour operation, the user u (i) samples a key pair (pk ,sk ) for a one-time signature scheme; (ii) computes h := CRH(pk ); sig sig Sig sig (iii) computes the two values h := PRFpk (h ) and h := PRFpk (h ), which act as MACs to 1 aold Sig 2 aold Sig sk,1 sk,2 5Thesepublicoutputscanbeconsideredasan“input”toaBitcoin-styletransaction,wherethestringinfocontains the Bitcoin output scripts. This mechanism also allows us to support Bitcoin’s public transaction fees. 8 “tie” h to both address secret keys; (iv) modifies POUR to include the three values h ,h ,h and Sig Sig 1 2 prove that the latter two are computed correctly; and (v) uses sk to sign every value associated sig with the pour operation, thus obtaining a signature σ, which is included, along with pk , in tx . sig Pour Since the aold are secret, and with high probability h changes for each pour transaction, the sk,i Sig values h ,h are unpredictable. Moreover, the signature on the NP statement (and other values) 1 2 binds all of these together, as argued in more detail in Appendix C and Appendix D. This ends the outline of the construction, which is summarized in part in Figure 1. We conclude by noting that, due to the zk-SNARK, our construction requires a one-time trusted setup of public parameters. The soundness of the proofs depends on this trust, though anonymity continues to hold even if the setup is corrupted by a malicious party. (a) Merke tree over (cm ,cm ,…) (b) coin rt = Merkle-tree root 1 2 cm = coin commitment rt c = ((a ,pk ), v, ρ, r, s, cm) pk enc sn = serial number CRH (c) coin commitment (d) serial number v = coin value cm sn r, s = commitment rand. CRH CRH ρ = serial number rand. sn COMMs PRF (cid:2) (apk,pkenc) = address public key (cid:5)(cid:3) CRH (a ,sk ) = address secret key sk enc v CRH CRH COMM r ρ CRH CRH CRH CRH (cid:2)(cid:4)(cid:3) PRFaddr (cid:1) cm1cm2cm3cm4cm5cm6cm7cm8 … (cid:2)(cid:5)(cid:3) Figure 1: (a) Illustration of the CRH-based Merkle tree over the list CMList of coin commitments. (b) A coin c. (c) Illustration of the structure of a coin commitment cm. (d) Illustration of the structure of a coin serial number sn. 1.4 Zerocash We outline Zerocash, a concrete implementation, at 128 bits of security, of our DAP scheme construction; see Section 5 for details. Zerocash entails carefully instantiating the cryptographic ingredients of the construction to ensure that the zk-SNARK, the “heaviest” component, is efficient enough in practice. In the construction, the zk-SNARK is used to prove/verify a specific NP statement: POUR. While zk-SNARKs are asymptotically efficient, their concrete efficiency depends on the arithmetic circuit C that is used to decide the NP statement. Thus, we seek instantiations for which we can design a relatively small arithmetic circuit C for verifying the NP statement POUR. POUR Our approach is to instantiate all of the necessary cryptographic ingredients (commitment schemes, pseudorandom functions, and collision-resistant hashing) based on SHA256. We first design a hand-optimized circuit for verifying SHA256 computations (or, more precisely, its compression function, which suffices for our purposes).6 Then, we use this circuit to construct C , which POUR verifies all the necessary checks for satisfying the NP statement C . POUR This, along with judicious parameter choices, and a state-of-the-art implementation of a zk-SNARK for arithmetic circuits [BCTV14] (see Section 2.4), results in a zk-SNARK prover 6Alternatively,wecouldhaveoptedtorelyonthecircuitgenerators[PGHR13,BCG+13,BCTV14],whichsupport variousclassesofCprograms,bywritingCcodeexpressingthePOURchecks. However,asdiscussedlater,thesegeneric approaches are more expensive than our hand-optimized construction. 9 running time of a few minutes and zk-SNARK verifier running time of a few milliseconds. This allows the DAP scheme implementation to be practical for deployment, as our experiments show. Zerocash can be integrated into Bitcoin or forks of it (commonly referred to as “altcoins”); we later describe how this is done. 1.5 Paper organization The remainder of this paper is organized as follows. Section 2 provides background on zk-SNARKs. We define DAP schemes in Section 3, and our construction thereof in Section 4. Section 5 discusses the concrete instantiation in Zerocash. Section 6 describes the integration of Zerocash into existing ledger-based currencies. Section 7 provides microbenchmarks for our prototype implementation, as well as results based on full-network simulations. Section 8 describes optimizations. We discuss concurrent work in Section 9 and summarize our contributions and future directions in Section 10. 2 Background on zk-SNARKs The main cryptographic primitive used in this paper is a special kind of Succinct Non-interactive ARgument of Knowledge (SNARK). Concretely, we use a publicly-verifiable preprocessing zero- knowledge SNARK, or zk-SNARK for short. In this section we provide basic background on zk-SNARKs, provide an informal definition, compare zk-SNARKs with the more familiar notion of NIZKs, and recall known constructions and implementations. 2.1 Informal definition We informally define zk-SNARKs for arithmetic circuit satisfiability. We refer the reader to, e.g., [BCI+13] for a formal definition. For a field F, an F-arithmetic circuit takes inputs that are elements in F, and its gates output elements in F. We naturally associate a circuit with the function it computes. To model nonde- terminism we consider circuits that have an input x ∈ Fn and an auxiliary input a ∈ Fh, called a witness. The circuits we consider only have bilinear gates.7 Arithmetic circuit satisfiability is defined analogously to the boolean case, as follows. Definition 2.1. The arithmetic circuit satisfiability problem of an F-arithmetic circuit C: Fn × Fh → Fl is captured by the relation R = {(x,a) ∈ Fn × Fh: C(x,a) = 0l}; its language is C L = {x ∈ Fn : ∃a ∈ Fh s.t. C(x,a) = 0l}. C Given a field F, a (publicly-verifiable preprocessing) zk-SNARK for F-arithmetic circuit satisfiability is a triple of polynomial-time algorithms (KeyGen,Prove,Verify): • KeyGen(1λ,C) → (pk,vk). On input a security parameter λ (presented in unary) and an F- arithmetic circuit C, the key generator KeyGen probabilistically samples a proving key pk and a verification key vk. Both keys are published as public parameters and can be used, any number of times, to prove/verify membership in L . C • Prove(pk,x,a) → π. On input a proving key pk and any (x,a) ∈ R , the prover Prove outputs a C non-interactive proof π for the statement x ∈ L . C 7A gate with inputs y ,...,y ∈ F is bilinear if the output is (cid:104)(cid:126)a,(1,y ,...,y )(cid:105)·(cid:104)(cid:126)b,(1,y ,...,y )(cid:105) for some 1 m 1 m 1 m (cid:126)a,(cid:126)b∈Fm+1. These include addition, multiplication, negation, and constant gates. 10