资源描述：
Zerocash Decentralized Anonymous Payments from Bitcoinextended versionEli Ben-Sasson Alessandro Chiesay Christina Garmanz Matthew GreenzIan Miersz Eran Tromerx Madars VirzayMay 18, 2014AbstractBitcoin is the rst digital currency to see widespread adoption. Although payments areconducted between pseudonyms, Bitcoin cannot o er strong privacy guarantees paymenttransactions are recorded in a public decentralized ledger, from which much ination canbe deduced. Zerocoin Miers et al., IEEE S ii the mix operator can trace coins; and iii the mix operator may steal coins.1 For userswith \something to hide“, these risks may be acceptable. But typical legitimate users 1 wish tokeep their spending habits private from their peers, 2 are risk-averse and do not wish to expendcontinual e ort in protecting their privacy, and 3 are often not su ciently aware that their privacyhas been compromised.To protect their privacy, users thus need an instant, risk-free, and, most importantly, automaticguarantee that data revealing their spending habits and account balances is not publicly accessibleby their neighbors, co-workers, and the merchants with whom they do business. Anonymoustransactions also ensure that the market value of a coin is independent of its history, thus ensuringthat legitimate users’ coins remain fungible.2Zerocoin a decentralized mix. Miers et al. [MGGR13] proposed Zerocoin, which extendsBitcoin to provide strong anonymity guarantees. Like many e-cash protocols e.g., [CHL05],Zerocoin employs zero-knowledge proofs to prevent transaction graph analyses. Unlike earlierpractical 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 authenticatescoins by proving, in zero-knowledge, that they belong to a public list of valid coins which can bemaintained on the block chain. Yet rather than a full- edged anonymous currency, Zerocoin isa 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 rst reason is perance. Redeeming zerocoins requires double-discrete-logarithm proofsof knowledge, which have size that exceeds 45 kB and require 450 ms to verify at the 128-bitsecurity level.3 These proofs must be broadcast through the network, veri ed by every node, andpermanently stored in the ledger. The entailed costs are higher, by orders of magnitude, than thosein 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 transactionsthat involve many collaborating Bitcoin users. CoinJoin can thus only mix small volumes of coins amongst users whoare currently online, is prone to denial-of-service attacks by third parties, and requires e ort to nd mixing partners.2While the s we detail in this paper accomplish this, the same techniques open the door for privacy-preservingaccountability and oversight see Section 10.3These published numbers [MGGR13] actually use a mix of parameters at both 128-bit and 80-bit security fordi erent components of the construction. The cost is higher if all parameters are instantiated at 128-bit security.3The second reason is functionality. While Zerocoin constitutes a basic e-cash scheme, it lackscritical features required of full- edged anonymous payments. First, Zerocoin uses coins of xeddenomination it does not support payments of exact values, nor does it provide a means to givechange following a transaction i.e., divide coins. Second, Zerocoin has no mechanism for oneuser to pay another one directly in \zerocoins“. And third, while Zerocoin provides anonymityby unlinking a payment transaction from its origin address, it does not hide the amount or othermetadata about transactions occurring on the network.Our contribution. Addressing this challenge, this work o ers two main contributions.1 We introduce the notion of a decentralized anonymous payment scheme, which ally capturesthe functionality and security guarantees of a full- edged decentralized electronic currency withstrong anonymity guarantees. We provide a construction of this primitive and prove its securityunder speci c cryptographic assumptions. The construction leverages recent advances in the area ofzero-knowledge proofs. Speci cally, it uses zero-knowledge Succinct Non-interactive ARguments ofKnowledge zk-SNARKs [Gro10, Lip12, BCI13, GGPR13, PGHR13, BCG13, Lip13, BCTV14].2 We implement the above primitive, via a system that we call Zerocash. Our system at 128bits of securityreduces the size of transactions spending a coin to under 1 kB an improvement of over 977;reduces the spend-transaction veri cation time to under 6 ms an improvement of over 986;allows for anonymous transactions of variable amounts;hides transaction amounts and the values of coins held by users; andallows for payments to be made directly to a user’s xed address without user interaction.To validate our system, we measured its perance and established feasibility by conductingexperiments in a test network of 1000 nodes approximately 116 of the unique IPs in the Bitcoinnetwork and 13 of the nodes reachable at any given time [DW13]. This inspires con dence thatZerocash can be deployed as a fork of Bitcoin and operate at the same scale. Thus, due to itssubstantially improved functionality and perance, Zerocash makes it possible to entirely replacetraditional Bitcoin payments with anonymous alternatives.Concurrent work. The idea of using zk-SNARKs in the Bitcoin setting was rst presented by oneof the authors at Bitcoin 2013 [Ben13]. In concurrent work, Danezis et al. [DFKP13] suggest usingzk-SNARKs to reduce proof size and veri cation time in Zerocoin; see Section 9 for a comparison.1.1 zk-SNARKsA zk-SNARK is an e cient variant of a zero-knowledge proof of knowledge [GMR89], which we rstinally describe via an example. Suppose Alice wishes to prove to Bob the statement \I Aliceown 30 bitcoins“. A simple 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 leaks knowledge to Bob, by identifying which coins are Alice’s. A zero-knowledge proofof knowledge allows Alice to achieve the same goal, while revealing no ination to Bob beyondthe fact that she knows some secret keys that control 30 coins. Crucially, such proofs can beobtained for any statement that can be veri ed to be true by use of an e cient computation involvingauxiliary s such as trapdoors and passwords such statements are called \NP statements“.We now sketch in more technical terms the de nition of a zk-SNARK; see Section 2 for moredetails. 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 letC be a nondeterministic decision circuit for L on a given instance size n. A zk-SNARK can be used4to prove and verify membership in L, for instances of size n, as follows. After taking C as , atrusted party conducts a one-time setup phase that results in two public keys a proving key pkand a veri cation key vk. The proving key pk enables any untrusted prover to produce a proof attesting to the fact that x2L, for an instance x of size n of his choice. The non-interactive proofis zero knowledge and a proof of knowledge. Anyone can use the veri cation key vk to verify theproof ; in particular zk-SNARK proofs are publicly veri able anyone can verify , without everhaving to interact with the prover who generated . Succinctness requires that for a given securitylevel has constant size and can be veri ed in time that is linear in jxj rather than linear in jCj.1.2 Centralized anonymous payment systemsBefore describing our new decentralized payment system, we put it in context by recalling twopre-Bitcoin payment schemes, both of which relied on a bank, acting as a central trusted party.Anonymous e-cash. Chaum [Cha82] rst obtained anonymous e-cash. In Chaum’s scheme, theminting of a coin involves both a user, Alice, and the bank to mint a coin of a given value v, Alicerst selects a random secret serial number sn unknown to the bank; then, the bank, after deductingv from Alice’s balance, signs sn via a blind signature. Afterwards, if Alice wants to transfer her cointo Bob, she reveals sn to him and proves that sn was signed by the bank; during this transfer, Bobor the bank cannot deduce Alice’s identity from the revealed ination. Double-spending isprevented 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’ssecret key is compromised. Sander and Ta-Shma [ST99] addressed this, as follows. The bankmaintains a public Merkle tree of \coin commitments“, and users periodically retrieve its root rt; inparticular, the bank maintains no secrets. When Alice requests a coin of unit value, she picksa random serial number sn and auxiliary string r, and then sends cm CRHsnkr to the bank,where CRH is a collision-resistant hash; the bank deducts the appropriate amount from Alice’sbalance and then records cm as a leaf in the Merkle tree. Afterwards, to pay Bob, Alice sends himsn along with a zero-knowledge proof of knowledge of the following NP statement \there existsr such that CRHsnkr is a leaf in a Merkle tree with root rt“. In other words, Alice can convinceBob that sn is the serial number contained in some coin commitment in the Merkle tree; but thezero-knowledge property prevents Bob from learning ination about which coin commitment isAlice’s, thereby protecting Alice’s identity. Later, Bob can \cash out“ Alice’s coin by showing snand to the bank.4Moving to a fungible anonymous decentralized system. In this paper, like [ST99], wehash 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 andmerge coins, thus achieving and implementing a new kind of fully-fungible and divisible paymentscheme. As in Bitcoin and in stark contrast to previous e-cash schemes, we do not rely on atrusted bank. Therefore, we require a new set of de nitions and protocols, designed to protectAlice’s anonymity while preventing her from falsely increasing her balance under the veil of herboosted privacy. An inal description of our payment scheme follows.1.3 Decentralized anonymous payment schemesWe construct a decentralized anonymous payment DAP scheme, which is a decentralized e-cashscheme that allows direct anonymous payments of any amount. See Section 3 for a al de nition.4We omit details about how the bank can identify Alice in the event that she double spends her coin.5Here, 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 anygiven time, a unique valid snapshot of the currency’s ledger is available to all users. The ledger is asequence of transactions and is append-only. Transactions include both the underlying currency’stransactions, as well as new transactions introduced by our construction. For concreteness, we focusthe discussion below on Bitcoin though later de nitions and constructions are stated abstractly. Weassume familiarity with Bitcoin [Nak09] and Zerocoin [MGGR13]; both are reviewed in Appendix A.Step 1 user anonymity with xed-value coins. We rst describe a simpli ed construction,in which all coins have the same value of, e.g., 1 BTC. This construction, similar to the Zerocoinprotocol, shows how to hide a payment’s origin. In terms of tools, we make use of zk-SNARKsrecalled above and a commitment scheme. Let COMM denote a statistically-hiding non-interactivecommitment scheme i.e., given randomness r and message m, the commitment is c COMMrm;subsequently, c is opened by revealing r and m, and one can verify that COMMrm equals c.In the simpli ed construction, a new coin c is minted as follows a user u samples a randomserial number sn and a trapdoor r, computes a coin commitment cm COMMrsn, and setsc r;sn;cm. A corresponding mint transaction txMint, containing cm but not sn or r, is sent tothe ledger; txMint is appended to the ledger only if u has paid 1 BTC to a backing escrow pool e.g.,the 1 BTC may be paid via plaintext ination encoded in txMint. Mint transactions are thuscerti cates of deposit, deriving their value from the backing pool.Subsequently, letting CMList denote the list of all coin commitments on the ledger, u may spendc by posting a spend transaction txSpend that contains i the coin’s serial number sn; and ii azk-SNARK proof of the NP statement \I know r such that COMMrsn appears in the list CMListof coin commitments“. Assuming that sn does not already appear on the ledger as part of a pastspend transaction, u can redeem the deposited amount of 1 BTC, which u can either keep, transferto someone else, or mint a new coin. If sn does already appear on the ledger, this is considereddouble spending, and the transaction is discarded.User anonymity is achieved because the proof is zero-knowledge while sn is revealed, noination about r is, and nding which of the numerous commitments in CMList correspondsto a particular spend transaction txSpend is equivalent to inverting fx COMMxsn, which isassumed 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 isspeci ed explicitly as a list of coin commitments. This naive representation severely limits scalabilitybecause the time and space complexity of most protocol algorithms e.g., the proof veri cationalgorithm grow linearly with CMList. Moreover, coin commitments corresponding to already-spentcoins cannot be dropped from CMList to reduce costs, since they cannot be identi ed due to thesame zero-knowledge property that provides anonymity.As in [ST99], we rely on a collision-resistant function CRH to avoid an explicit representationof CMList. We maintain an e ciently-updatable append-only CRH-based Merkle tree TreeCMListover the growing list CMList and let rt denote the root of TreeCMList. It is well-known that rtcan be updated to account for the insertion of new leaves with time and space proportional to justthe tree depth. Hence, the time and space complexity is reduced from linear in the size of CMList tologarithmic. With this in mind, we modify the NP statement to the following one \I know r suchthat
展开阅读全文