Highlight to Annotate. Click to Learn.
Zerocash: Decentralized Anonymous Payments from Bitcoin
(extended version)
Eli BenSasson^{∗} 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 fullfledged ledgerbased digital currency with strong privacy guarantees. Our results leverage recent advances in zeroknowledge Succinct Noninteractive ARguments of Knowledge (zkSNARKs).
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 1 kB and take under 6 ms to verify — orders of magnitude more efficient than the lessanonymous Zerocoin and competitive with plain Bitcoin.
Keywords: Bitcoin, decentralized electronic cash, zeroknowledge proofs
∗Technion, eli@cs.technion.ac.il
†MIT, {alexch, madars}@mit.edu
‡Johns Hopkins University, {cgarman, imiers, mgreen}@cs.jhu.edu
Tel Aviv University, tromer@cs.tau.ac.il
§
Contents
 Introduction 3
 Background on zkSNARKs 10
 Definition of a decentralized anonymous payment scheme 13
 Data structures 13
 Algorithms 14
 Completeness 16
 Security 16
 Construction of a decentralized anonymous payment scheme 18
 Zerocash 20
 Integration with existing ledgerbased currencies 26
 Experiments 28
 Optimizations and extensions 33
 Concurrent work 36
 Conclusion 36
 Overview of Bitcoin and Zerocoin 38
 Completeness of DAP schemes 39
 Security of DAP schemes 40
 Proof of Theorem 4.1 44
References 54
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 ecash 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 mutuallydistrustful 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 deanonymize 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 ecash 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 riskaverse 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, riskfree, and, most importantly, automatic guarantee that data revealing their spending habits and account balances is not publicly accessible by their neighbors, coworkers, 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 ecash protocols (e.g., [CHL05]), Zerocoin employs zeroknowledge proofs to prevent transaction graph analyses. Unlike earlier practical ecash 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 zeroknowledge, that they belong to a public list of valid coins (which can be maintained on the block chain). Yet rather than a fullfledged anonymous currency, Zerocoin is a decentralized mix, where users may periodically “wash” their bitcoins via the Zerocoin protocol. Routine daytoday transactions must be conducted via Bitcoin, due to reasons that we now review.
The first reason is performance. Redeeming zerocoins requires doublediscretelogarithm proofs of knowledge, which have size that exceeds 45 kB and require 450 ms to verify (at the 128bit 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 multisignature 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 denialofservice attacks by third parties, and requires effort to find mixing partners. 2While the methods we detail in this paper accomplish this, the same techniques open the door for privacypreserving
accountability and oversight (see Section 10).
3These published numbers [MGGR13] actually use a mix of parameters at both 128bit and 80bit security for different components of the construction. The cost is higher if all parameters are instantiated at 128bit security.
The second reason is functionality. While Zerocoin constitutes a basic ecash scheme, it lacks critical features required of fullfledged 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.
 We introduce the notion of a decentralized anonymous payment scheme, which formally captures the functionality and security guarantees of a fullfledged 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 zeroknowledge proofs. Specifically, it uses zeroknowledge Succinct Noninteractive ARguments of Knowledge (zkSNARKs) [Gro10, Lip12, BCI^{+}13, GGPR13, PGHR13, BCG^{+}13, Lip13, BCTV14].
 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 1 kB (an improvement of over 97.7%);
 reduces the spendtransaction verification time to under 6 ms (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}
16
of the unique IPs in the Bitcoin
network and ^{1}
3
of the nodes reachable at any given time [DW13]). This inspires confidence that
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 zkSNARKs 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 zkSNARKs to reduce proof size and verification time in Zerocoin; see Section 9 for a comparison.
zkSNARKs
A zkSNARK is an efficient variant of a zeroknowledge 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 zeroknowledge 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 obtained for any statement that can be verified to be true by use of an efficient computation involving auxiliary inputs such as trapdoors and passwords (such statements are called “NP statements”).
We now sketch in more technical terms the definition of a zkSNARK; see Section 2 for more details. A zkSNARK is a noninteractive zeroknowledge 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 zkSNARK can be used
to prove and verify membership in L, for instances of size n, as follows. After taking C as input, a trusted party conducts a onetime 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 noninteractive proof π is zero knowledge and a proof of knowledge. Anyone can use the verification key vk to verify the proof π; in particular zkSNARK 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).
Centralized anonymous payment systems
Before describing our new decentralized payment system, we put it in context by recalling two preBitcoin payment schemes, both of which relied on a bank, acting as a central trusted party.
Anonymous ecash. Chaum [Cha82] first obtained anonymous ecash. 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. Doublespending is prevented because the bank will not honor a coin with a previouslyseen serial number.
Unforgeable ecash. One problem with Chaum’s scheme is that coins can be forged if the bank’s secret key is compromised. Sander and TaShma [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”r) to the bank, where CRH is a collisionresistant 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 zeroknowledge proof of knowledge π of the following NP statement: “there exists r such that CRH(sn”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 zeroknowledge 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 fullyfungible and divisible payment scheme. As in Bitcoin (and in stark contrast to previous ecash 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.
Decentralized anonymous payment schemes
We construct a decentralized anonymous payment (DAP) scheme, which is a decentralized ecash 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.
Here, we outline our construction in six incremental steps; the construction details are in Section 4. Our construction functions on top of any ledgerbased 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 appendonly. Transactions include both the underlying currency’s transactions, as well as new transactions introduced by our construction. For concreteness, we focus the discussion below on Bitcoin (though later definitions and constructions are stated abstractly). We assume familiarity with Bitcoin [Nak09] and Zerocoin [MGGR13]; both are reviewed in Appendix A.
Step 1: user anonymity with ftxedvalue coins. We first describe a simplified construction, in which all coins have the same value of, e.g., 1 BTC. This construction, similar to the Zerocoin protocol, shows how to hide a payment’s origin. In terms of tools, we make use of zkSNARKs (recalled above) and a commitment scheme. Let COMM denote a statisticallyhiding noninteractive commitment scheme (i.e., given randomness r and message m, the commitment is c := COMM_{r}(m); subsequently, c is opened by revealing r and m, and one can verify that COMM_{r}(m) equals c).
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_{r}(sn), and sets c := (r, sn, cm). A corresponding mint transaction tx_{Mint}, containing cm (but not sn or r), is sent to the ledger; tx_{Mint} 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 information encoded in tx_{Mint}). Mint transactions are thus 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_{Spend} that contains (i) the coin’s serial number sn; and (ii) a zkSNARK proof π of the NP statement “I know r such that COMM_{r}(sn) appears in the list CMList 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 1 BTC, 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 zeroknowledge: 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_{Spend} is equivalent to inverting f (x) := COMM_{x}(sn), which is 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 alreadyspent coins cannot be dropped from CMList to reduce costs, since they cannot be identified (due to the same zeroknowledge property that provides anonymity).
As in [ST99], we rely on a collisionresistant function CRH to avoid an explicit representation of CMList. We maintain an efficientlyupdatable appendonly CRHbased Merkle tree Tree(CMList) over the (growing) list CMList and let rt denote the root of Tree(CMList). It is wellknown 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_{r}(sn) appears as a leaf in a CRHbased Merkle tree whose root is rt”. Compared with the naive data structure for CMList, this modification increases exponentially the size of CMList that a given zkSNARK implementation can support. (Concretely: using Merkle trees of depth 64, Zerocash supports 2^{64} coins.)
Step 3: extending coins for direct anonymous payments. So far, the coin commitment
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_{A} created c, and u_{A} sends c to another user u_{B}. First, since u_{A} knows sn, the spending of c by u_{B} is both nonanonymous (since u_{A} sees when c is spent, by recognizing sn) and risky (since u_{A} could still spend c first). Thus, u_{B} must immediately spend c and mint a new coin c^{j} to protect himself. Second, if u_{A} in fact wants to transfer to u_{B}, e.g., 100 BTC, then doing so is both unwieldy (since it requires 100 transfers) and nonanonymous (since the amount of the transfer is leaked). And third, transfers in amounts that are not multiples of 1 BTC (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 PRF^{addr}(·), PRF^{sn}(·), and
x x
PRF^{pk}(·). We assume that PRF^{sn} is moreover collisionresistant.
x
To provide targets for payments, we use addresses: each user u generates an address key pair (a_{pk}, a_{sk}), the address public key and address private key respectively. The coins of u contain the value a_{pk} and can be spent only with knowledge of a_{sk}. A key pair (a_{pk}, a_{sk}) is sampled by selecting a random seed a_{sk} and setting a_{pk} := PRF^{addr}(0). A user can generate and use any number of
ask
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 := PRF^{sn} (ρ). Then, u commits to the tuple (a_{pk}, v, ρ) in two phases: (a) u computes k := COMM_{r}(a_{pk}“ρ) for a random r; and then (b) u computes cm := COMM_{s}(v“k) for a random s. The minting results in a coin c := (a_{pk}, v, ρ, r, s, cm) and a mint transaction tx_{Mint} := (v, k, s, cm). Crucially, due to the nested commitment, anyone can verify that cm in tx_{Mint} is a coin commitment of a coin of value v (by checking that COMM_{s}(v“k) equals cm) but cannot discern the owner (by learning the address key a_{pk}) or serial number (derived from ρ) because these are hidden in k. As before, tx_{Mint} is accepted by the ledger only if u deposits the correct amount, in this case v BTC.
ask
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
the total value of the input coins. Suppose that u, with address key pair (a^{old}, a^{old}), wishes to consume
pk sk
his coin c^{old} = (a^{old}, v^{old}, ρ^{old}, r^{old}, s^{old}, cm^{old}) and produce two new coins c^{new} and c^{new}, with total
pk 1 2
value v^{new} + v^{new} = v^{old}, respectively targeted at address public keys a^{new} and a^{new} . (The addresses
1 2 pk,1 pk,2
and a
new pk,1
a
new pk,2
may belong to u or to some other user.) The user u, for each i ∈ {1, 2}, proceeds as
follows: (i) u samples serial number randomness ρ^{new}; (ii) u computes k^{new} := COMM_{r}new (a^{new}“ρ^{new})
i
i
i
pk,i
i
for a random r^{new}; and (iii) u computes cm^{new} := COMM_{s}new (v^{new}“k^{new}) for a random s^{new}.
i
i
i
i
i
i
This yields the coins c^{new} := (a^{new} , v^{new}, ρ^{new}, r^{new}, s^{new}, cm^{new}) and c^{new} := (a^{new} , v^{new}, ρ^{new},
1 pk,1 1
1 1 1 1
2 pk,2 2 2
r^{new}, s^{new}, cm^{new}). Next, u produces a zkSNARK proof π_{POUR} for the following NP statement, which
2 2 2
we call POUR:
“Given the Merkletree root rt, serial number sn^{old}, and coin commitments cm^{new}, cm^{new}, I
1 2
know coins c^{old}, c^{new}, c^{new}, and address secret key a^{old} such that:
1 2 sk


 The coins are wellformed: for c^{old} it holds that k^{old} = COMMrold (a^{old}“ρ^{old}) and cm^{old} =

pk
COMMsold (v^{old}“k^{old}); and similarly for c^{new} and c^{new}.
1
2


 The address secret key matches the public key: a^{old} = PRF^{addr}(0).

a
pk


 The serial number is computed correctly: sn^{old} := PRF^{sn}

sk
aold
old sk
(ρ^{old}).


 The coin commitment cm^{old} appears as a leaf of a Merkletree with root rt.
 The values add up: v^{new} + v^{new} = v^{old}.”

1
2
A resulting pour transaction tx_{Pour} := (rt, sn^{old}, cm^{new}, cm^{new}, π_{POUR}) is appended to the ledger.
1 2
(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 a^{new} that is associated with the public key a^{new} . Then, u cannot spend c^{new} because he cannot provide a^{new} as part of the witness
sk,1
pk,1 1 sk,1
of a subsequent pour operation. Furthermore, when a user who knows a^{new} does spend c^{new}, the
sk,1 1
user u cannot track it, because he knows no information about its revealed serial number, which is
new sn new
sn := PRF new (ρ ).
1 a 1
sk,1
Also observe that tx_{Pour} reveals no information about how the value of the consumed coin was
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 N ^{old} 0 coins into N ^{new} 0 coins. For simplicity we consider the case N ^{old} = N ^{new} = 2, without loss of generality. Indeed, for N ^{old} < 2, the user can mint a coin with value 0 and then provide it as a “null” input, and for N ^{new} < 2, the user can create (and discard) a new coin with value 0. For N ^{old} > 2 or N ^{new} > 2, the user can compose log N ^{old} + log N ^{new} of the 2input/2output pours.
≥ ≥
Step 4: sending coins. Suppose that a^{new} is the address public key of u_{1}. In order to allow u_{1}
pk,1
to actually spend the new coin c^{new} produced above, u must somehow send the secret values in c^{new} to u_{1}. One way is for u to send u_{1} a private message, but the requisite private communication channel necessitates additional infrastructure or assumptions. We avoid this “outofband” 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_{pk}, addr_{sk}), where addr_{pk} = (a_{pk}, pkenc) and addr_{sk} = (a_{sk}, sk_{enc}). The values (a_{pk}, a_{sk}) are generated as before.
1
1
In addition, (pkenc, sk_{enc}) is a key pair for a keyprivate encryption scheme [BBDP01].
Then, u computes the ciphertext C_{1} that is the encryption of the plaintext (v^{new}, ρ^{new}, r^{new}, s^{new}),
1 1 1 1
under pk^{new} (which is part of u_{1}’s address public key addr^{new}), and includes C_{1} in the pour
enc,1
sk,1
transaction tx_{Pour}. The user u_{1} can then find and decrypt this message (using his sk^{new}
enc,1
) by
scanning the pour transactions on the public ledger. Again, note that adding C_{1} to tx_{Pour} leaks neither paid amounts, nor target addresses due to the keyprivate property of the encryption scheme. (The user u does the same with c^{new} and includes a corresponding ciphertext C_{2} in tx_{Pour}.)
2
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_{pub} and a transaction string info 0, 1 ^{∗}. The balance equation in the NP statement POUR is changed accordingly: “v^{new} + v^{new} + v_{pub} = v^{old}”. Thus, of the input
∈ { }
1 2
value v^{old}, a part v_{pub} is publicly declared, and its target is specified, somehow, by the string info. The string info can be used to specify the destination of these redeemed funds (e.g., a Bitcoin wallet public key).^{5} Both v_{pub} and info are now included in the resulting pour transaction tx_{Pour}. (The public output is optional, as the user u can set v_{pub} = 0.)
Step 6: nonmalleability. To prevent malleability attacks on a pour transaction tx_{Pour} (e.g., embezzlement by retargeting 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 (pksig, sk_{sig}) for a onetime signature scheme; (ii) computes h_{Sig} := CRH(pksig);
 computes the two values h_{1} := PRF^{pk}
aold
sk,1
(h_{Sig}) and h_{2} := PRF^{pk}
sk,2
aold
(h_{Sig}), which act as MACs to
5These public outputs can be considered as an “input” to a Bitcoinstyle transaction, where the string info contains the Bitcoin output scripts. This mechanism also allows us to support Bitcoin’s public transaction fees.
“tie” h_{Sig} to both address secret keys; (iv) modifies POUR to include the three values h_{Sig}, h_{1}, h_{2} and prove that the latter two are computed correctly; and (v) uses sk_{sig} to sign every value associated with the pour operation, thus obtaining a signature σ, which is included, along with pksig, in tx_{Pour}.
Since the a^{old} are secret, and with high probability h_{Sig} changes for each pour transaction, the
sk,i
values h_{1}, h_{2} are unpredictable. Moreover, the signature on the NP statement (and other values) 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 zkSNARK, our construction requires a onetime 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.
rt

 coin
c = ((a
,pk
), v, ρ, r, s, cm)
rt = Merkletree root
cm = coin commitment
pk enc
CRH
CRH
CRH
sn = serial number

 coin commitment
cm
COMM
s
PRFsn
asfi
v
COMM
r
ρ
CRH

 serial number
sn
v = coin value
r, s = commitment rand.
ρ = serial number rand. (apk,pkenc) = address public key (ask,skenc) = address secret key
CRH
CRH
CRH
CRH
CRH
CRH
cm1 cm2 cm3 cm4 cm5 cm6 cm7 cm8 …
apfi 0
Figure 1: (a) Illustration of the CRHbased 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.
sfi
PRFaddr
a
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 zkSNARK, the “heaviest” component, is efficient enough in practice. In the construction, the zkSNARK is used to prove/verify a specific NP statement: POUR. While zkSNARKs 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_{POUR} for verifying the NP statement POUR. Our approach is to instantiate all of the necessary cryptographic ingredients (commitment schemes, pseudorandom functions, and collisionresistant hashing) based on SHA256. We first design a handoptimized 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_{POUR}, which
verifies all the necessary checks for satisfying the NP statement C_{POUR}.
This, along with judicious parameter choices, and a stateoftheart implementation of a zkSNARK for arithmetic circuits [BCTV14] (see Section 2.4), results in a zkSNARK prover
6Alternatively, we could have opted to rely on the circuit generators [PGHR13, BCG^{+}13, BCTV14], which support various classes of C programs, by writing C code expressing the POUR checks. However, as discussed later, these generic approaches are more expensive than our handoptimized construction.
running time of a few minutes and zkSNARK 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.
Paper organization
The remainder of this paper is organized as follows. Section 2 provides background on zkSNARKs. 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 ledgerbased currencies. Section 7 provides microbenchmarks for our prototype implementation, as well as results based on fullnetwork simulations. Section 8 describes optimizations. We discuss concurrent work in Section 9 and summarize our contributions and future directions in Section 10.
Background on zkSNARKs
The main cryptographic primitive used in this paper is a special kind of Succinct Noninteractive ARgument of Knowledge (SNARK). Concretely, we use a publiclyverifiable preprocessing zero knowledge SNARK, or zkSNARK for short. In this section we provide basic background on zkSNARKs, provide an informal definition, compare zkSNARKs with the more familiar notion of NIZKs, and recall known constructions and implementations.
Informal definition
We informally define zkSNARKs for arithmetic circuit satisfiability. We refer the reader to, e.g., [BCI^{+}13] for a formal definition.
For a field F, an Farithmetic 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. Arithmetic circuit satisfiability is defined analogously to the boolean case, as follows.
Deftnition 2.1. The arithmetic circuit satisfiability problem of an Farithmetic circuit C : Fn × Fh → Fl is captured by the relation R_{C} = {(x, a) ∈ Fn × Fh : C(x, a) = 0^{l}}; its language is L_{C} = {x ∈ Fn : ∃ a ∈ Fh s.t. C(x, a) = 0^{l}}.
Given a field F, a (publiclyverifiable preprocessing) zkSNARK for Farithmetic circuit satisfiability is a triple of polynomialtime 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_{C} , the prover Prove outputs a noninteractive proof π for the statement x ∈ L_{C} .
7A gate with inputs y1, . . . , ym ∈ F is bilinear if the output is (˙a, (1, y1, . . . , ym)) · (˙b, (1, y1, . . . , ym)) for some
˙a,˙b ∈ Fm+1. These include addition, multiplication, negation, and constant gates.
 Verify(vk, x, π) → b. On input a verification key vk, an input x, and a proof π, the verifier Verify
outputs b = 1 if he is convinced that x ∈ L_{C} .
A zkSNARK satisfies the following properties.
Completeness. For every security parameter λ, any Farithmetic circuit C, and any (x, a) ∈ R_{C} , the honest prover can convince the verifier. Namely, b = 1 with probability 1 − negl(λ) in the following experiment: (pk, vk) ← KeyGen(1^{λ}, C); π ← Prove(pk, x, a); b ← Verify(vk, x, π).
Succinctness. An honestlygenerated proof π has O_{λ}(1) bits and Verify(vk, x, π) runs in time O_{λ}(x). (Here, O_{λ} hides a fixed polynomial factor in λ.)
Proof of knowledge (and soundness). If the verifier accepts a proof output by a bounded prover, then the prover “knows” a witness for the given instance. (In particular, soundness holds against bounded provers.) Namely, for every poly(λ)size adversary A, there is a poly(λ)size extractor E such that Verify(vk, x, π) = 1 and (x, a) ƒ∈ R_{C} with probability negl(λ) in the following experiment: (pk, vk) ← KeyGen(1^{λ}, C); (x, π) ← A(pk, vk); a ← E (pk, vk).
Perfect zero knowledge. An honestlygenerated proof is perfect zero knowledge.^{8} Namely, there is a polynomialtime simulator Sim such that for all stateful distinguishers D the following two probabilities are equal:
. (pk, vk) ← KeyGen(1^{λ}, C)
. (pk, vk, trap) ← Sim(1^{λ}, C)
Pr (x, a) ∈ R_{C}
D(π) = 1 .
(x, a) ← D(pk, vk)
π ← Prove(pk, x, a)
and
Pr (x, a) ∈ R_{C}
D(π) = 1 .
(x, a) ← D(pk, vk) . π ← Sim(trap, x)
(the probability that D(π) = 1 on an honest proof)
(the probability that D(π) = 1 on a simulated proof)
Remark. Both proof of knowledge and zero knowledge are essential to the use of zkSNARKs in this paper. Indeed, we consider circuits C that verify assertions about cryptographic primitives (such as using a knowledge of SHA256 preimage as a binding commitment). Thus it does not suffice to merely know that, for a given input x, a witness for x ∈ L_{C} exists. Instead, proof of knowledge ensures that a witness can be efficiently found (by extracting it from the prover) whenever the verifier accepts a proof. As for zero knowledge, it ensures that a proof leaks no information about the witness, beyond the fact that x ∈ L_{C} .
Remark. In the security proofs (see Appendix D), we deal with provers producing a vector of inputs
˙x together with a vector of corresponding proofs ˙π. In such cases, it is convenient to use an extractor that can extract a vector of witnesses ˙a containing a valid witness for each valid proof. This “multi instance” extraction follows from the “singleinstance” one described above [BCCT12, BCCT13]. Namely, if (KeyGen, Prove, Verify) is a zkSNARK, then for any poly(λ)size prover adversary A there exists a poly(λ)size extractor E such that
Pr ∃ i s.t.
Verify(vk, x_{i}, π_{i}) = 1 (x_{i}, a_{i}) ∈/ R_{C} .
(pk, vk) ← KeyGen(1^{λ}, C)
(˙x, ˙π) ← A(pk, vk) ≤ negl(λ) .
˙a ← E (pk, vk)
Comparison with NIZKs
zkSNARKs are related to a familiar cryptographic primitive: noninteractive zeroknowledge proofs of knowledge (NIZKs). Both zkSNARKs and NIZKs require a onetime trusted setup of public
8While most zkSNARK descriptions in the literature only mention statistical zero knowledge, all zkSNARK constructions can be made perfect zero knowledge by allowing for a negligible error probability in completeness.
parameters (proving and verification keys for zkSNARKs, and a common reference string for NIZKs). Both provide the same guarantees of completeness, proof of knowledge, and zero knowledge. The difference lies in efficiency guarantees. In a NIZK, the proof length and verification time depend on the NP language being proved. For instance, for the language of circuit satisfiability, the proof length and verification time in [GOS06b, GOS06a] are linear in the circuit size. Conversely, in a zkSNARK, proof length depends only on the security parameter, and verification time depends only on the instance size (and security parameter) but not on the circuit or witness size.
Thus, zkSNARKs can be thought of as “succinct NIZKs”, having short proofs and fast verifica tion times. Succinctness comes with a caveat: known zkSNARK constructions rely on stronger assumptions than NIZKs do (see below).
Known constructions and security
There are many zkSNARK constructions in the literature [Gro10, Lip12, BCI^{+}13, GGPR13, PGHR13, BCG^{+}13, Lip13, BCTV14]. We are interested in zkSNARKs for arithmetic circuit satisfiability, and the most efficient ones for this language are based on quadratic arithmetic programs [GGPR13, BCI^{+}13, PGHR13, BCG^{+}13, BCTV14]; such constructions provide a linear time KeyGen, quasilineartime Prove, and lineartime Verify.
Security of zkSNARKs is based on knowledgeofexponent assumptions and variants of Diffie– Hellman assumptions in bilinear groups [Gro10, BB04, Gen04]. While knowledgeofexponent assumptions are fairly strong, there is evidence that such assumptions may be inherent for con structing zkSNARKs [GW11, BCCT12].
Remark (fullysuccinct zkSNARKs). The key generator KeyGen takes a circuit C as input. Thus, KeyGen’s running time is at least linear in the size of the circuit C. One could require KeyGen to not have to take C as input, and have its output keys work for all (polynomialsize) circuits C. In such a case, KeyGen’s running time would be independent of C. A zkSNARK satisfying this stronger property is fully succinct. Theoretical constructions of fullysuccinct zkSNARKs are known, based on various cryptographic assumptions [Mic00, Val08, BCCT13]. Despite achieving essentiallyoptimal asymptotics [BFLS91, BGH^{+}05, BCGT13b, BCGT13a, BCCT13] no implementations of them have been reported in the literature to date.
zkSNARK implementations
There are three published implementations of zkSNARKs: (i) Parno et al. [PGHR13] present an implementation of zkSNARKs for programs having no data dependencies;^{9} (ii) BenSasson et al. [BCG^{+}13] present an implementation of zkSNARKs for arbitrary programs (with data dependencies); and (iii) BenSasson et al. [BCTV14] present an implementation of zkSNARKs that supports programs that modify their own code (e.g., for runtime code generation); their implementation also reduces costs for programs of larger size and allows for universal key pairs.
Each of the works above also achieves zkSNARKs for arithmetic circuit satisfiability as a stepping stone towards their respective higherlevel efforts. In this paper we are only interested in a zkSNARK for arithmetic circuit satisfiability, and we rely on the implementation of [BCTV14] for such a zkSNARK.^{10} The implementation in [BCTV14] is itself based on the protocol of Parno et al. [PGHR13]. We thus refer the interested reader to [PGHR13] for details of the protocol, its
9They only support programs where array indices are restricted to be known compiletime constants; similarly, loop iteration counts (or at least upper bounds to these) must be known at compile time.
10In [BCTV14], one optimization to the verifier’s runtime requires preprocessing the verification key vk; for simplicity,
we do not use this optimization.
intuition, and its proof of security; and to [BCTV14] for the implementation and its performance. In terms of concrete parameters, the implementation of [BCTV14] provides 128 bits of security, and the field F is of a 256bit prime order p.
Definition of a decentralized anonymous payment scheme
We introduce the notion of a decentralized anonymous payment scheme (DAP scheme), extending the notion of decentralized ecash [MGGR13]. Later, in Section 4, we provide a construction.
Data structures
We begin by describing, and giving intuition about, the data structures used by a DAP scheme. The algorithms that use and produce these data structures are introduced in Section 3.2.
Basecoin ledger. Our protocol is applied on top of a ledgerbased base currency such as Bitcoin; for generality we refer to this base currency as Basecoin. At any given time T , all users have access to L_{T} , the ledger at time T , which is a sequence of transactions. The ledger is appendonly (i.e., T < T ^{j} implies that L_{T} is a prefix of L_{T} j ).^{11} The transactions in the ledger include both Basecoin transactions as well as two new transaction types described below.
Public parameters. A list of public parameters pp is available to all users in the system. These are generated by a trusted party at the “start of time” and are used by the system’s algorithms.
Addresses. Each user generates at least one address key pair (addr_{pk}, addr_{sk}). The public key addr_{pk} is published and enables others to direct payments to the user. The secret key addr_{sk} is used to receive payments sent to addr_{pk}. A user may generate any number of address key pairs.
Coins. A coin is a data object c, to which we associate the following.
 A coin commitment, denoted cm(c): a string that appears on the ledger once c is minted.
 A coin value, denoted v(c): the denomination of c, as measured in basecoins, as an integer between 0 and a maximum value v_{max} (which is a system parameter).
 A coin serial number, denoted sn(c): a unique string associated with c, used to prevent double spending.
 A coin address, denoted addr_{pk}(c): an address public key, representing who owns c.
Any other quantities associated with a coin c (e.g., various trapdoors) are implementation details.
New transactions. Besides Basecoin transactions, there are two new types of transactions.
 Mint transactions. A mint transaction tx_{Mint} is a tuple (cm, v, ∗), where cm is a coin commitment, v is a coin value, and ∗ denotes other (implementationdependent) information. The transaction tx_{Mint} records that a coin c with coin commitment cm and value v has been minted.
 Pour transactions. A pour transaction tx_{Pour} is a tuple (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, info, ∗),
1
2
1
2
where rt is a root of a Merkle tree, sn^{old}, sn^{old} are two coin serial numbers, cm^{new}, cm^{new} are
1 2 1 2
two coin commitments, v_{pub} is a coin value, info is an arbitrary string, and ∗ denotes other
(implementationdependent) information. The transaction tx_{Pour} records the pouring of two input (and now consumed) coins c^{old}, c^{old}, with respective serial numbers sn^{old}, sn^{old}, into two
1 2 1 2
new output coins c^{new}, c^{new}, with respective coin commitments cm^{new}, cm^{new}, as well as a public
1 2 1 2
output v_{pub} (which may be zero). Furthermore, tx_{Pour} also records an information string info
(perhaps containing information on who is the recipient of v_{pub} basecoins) and that, when this transaction was made, the root of the Merkle tree over coin commitments was rt (see below).
11In reality, the Basecoin ledger (such as the one of Bitcoin) is not perfect and may incur temporary inconsistencies. In this respect our construction is as good as the underlying ledger. We discuss the effects of this on anonymity and mitigations in Section 6.4.
Commitments of minted coins and serial numbers of spent coins. For any given time T ,
 CMList_{T} denotes the list of all coin commitments appearing in mint and pour transactions in L_{T} ;
 SNList_{T} denotes the list of all serial numbers appearing in pour transactions in L_{T} .
While both of these lists can be deduced from L_{T} , it will be convenient to think about them as separate (as, in practice, these may be separately maintained for efficiency reasons; cf. Section 8.3).
Merkle tree over commitments. For any given time T , Tree_{T} denotes a Merkle tree over CMList_{T} and rt_{T} its root. Moreover, the function Path_{T} (cm) gives the authentication path from a coin commitment cm appearing in CMList_{T} to the root of Tree_{T} .^{12} For convenience, we assume that L_{T} also stores rt_{T} j for all T ^{j} ≤ T (i.e., it stores all past Merkle tree roots).
Algorithms
A DAP scheme Π is a tuple of polynomialtime algorithms
(Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) with the following syntax and semantics.
System setup. The algorithm Setup generates a list of public parameters:
Setup


 inputs: security parameter λ
 outputs: public parameters pp

The algorithm Setup is executed by a trusted party. The resulting public parameters pp are published and made available to all parties (e.g., by embedding them into the protocol’s implementation). The setup is done only once; afterwards, no trusted party is needed, and no global secrets or trapdoors are kept.
Creating payment addresses. The algorithm CreateAddress generates a new address key pair:
CreateAddress


 inputs: public parameters pp
 outputs: address key pair (addr_{pk}, addr_{sk})

Each user generates at least one address key pair (addr_{pk}, addr_{sk}) in order to receive coins. The public key addr_{pk} is published, while the secret key addr_{sk} is used to redeem coins sent to addr_{pk}. A user may generate any number of address key pairs; doing so does not require any interaction.
Minting coins. The algorithm Mint generates a coin (of a given value) and a mint transaction:
Mint


 inputs:
 public parameters pp
 coin value v ∈ {0, 1, . . . , v_{max}}
 destination address public key addr_{pk}
 outputs: coin c and mint transaction tx_{Mint}
 inputs:

A system parameter, v_{max}, caps the value of any single coin. The output coin c has value v and coin address addr_{pk}; the output mint transaction tx_{Mint} equals (cm, v, ∗), where cm is the coin commitment of c.
12While we refer to Mekle trees for simplicity, it is straightforward to extend the definition to allow other data structures representing sets with fast insertion and efficient proofs of membership.
Pouring coins. The Pour algorithm transfers value from input coins into new output coins, marking the input coins as consumed. Moreover, a fraction of the input value may be publicly revealed. Pouring allows users to subdivide coins into smaller denominations, merge coins, and transfer ownership of anonymous coins, or make public payments.^{13}
Pour


 inputs:
 public parameters pp
 the Merkle root rt
 old coins c^{old}, c^{old}
 inputs:

1 2



 old addresses secret keys addr^{old} , addr^{old}


sk,1 sk,2



 authentication path path1 from commitment cm(c^{old}) to root rt, authentication path path2 from commitment cm(c^{old}) to root rt


1
2



 new values v^{new}, v^{new}


1 2



 new addresses public keys addr^{new} , addr^{new}
 public value v_{pub}
 transaction string info


pk,1
pk,2


 outputs: new coins c^{new}, c^{new} and pour transaction tx_{Pour}

1
2
Thus, the Pour algorithm takes as input two distinct input coins c^{old}, c^{old}, along with corresponding
1 2
address secret keys addr^{old} , addr^{old}
(required to redeem the two input coins). To ensure that
sk,1 sk,2
c^{old}, c^{old} have been previously minted, the Pour algorithm also takes as input the Merkle root rt
1 2
(allegedly, equal to the root of Merkle tree over all coin commitments so far), along with two
authentication paths path1, path2 for the two coin commitments cm(c^{old}), cm(c^{old}). Two input values
1 2
v^{new}, v^{new} specify the values of two new anonymous coins c^{new}, c^{new} to be generated, and two input
1 2 1 2
address public keys addr^{new} , addr^{new} specify the recipients of c^{new}, c^{new}. A third value, v_{pub}, specifies
pk,1 pk,2 1 2
the amount to be publicly spent (e.g., to redeem coins or pay transaction fees). The sum of output
values v^{new} + v^{new} + v_{pub} must be equal to the sum of the values of the input coins (and cannot
1 2
exceed v_{max}). Finally, the Pour algorithm also receives an arbitrary string info, which is bound into
the output pour transaction tx_{Pour}.
The Pour algorithm outputs two new coins c^{new}, c^{new} and a pour transaction tx_{Pour}. The
1 2
transaction tx_{Pour} equals (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, info, ∗), where cm^{new}, cm^{new} are the two
1
2
1
2
1
2
coin commitments of the two output coins, and ∗ denotes other (implementationdependent) information. Crucially, tx_{Pour} reveals only one value, the public value v_{pub} (which may be zero); it does not reveal the payment addresses or values of the old or new coins.
Verifying transactions. The algorithm VerifyTransaction checks the validity of a transaction:
VerifyTransaction


 inputs:
 public parameters pp
 a (mint or pour) transaction tx
 the current ledger L
 outputs: bit b, equals 1 iff the transaction is valid
 inputs:

Both mint and pour transactions must be verified before being considered wellformed. In practice, transactions can be verified by the nodes in the distributed system maintaining the ledger, as well
13We consider pours with 2 inputs and 2 outputs, for simplicity and (as discussed in Section 1.3) without loss of generality.
as by users who rely on these transactions.
Receiving coins. The algorithm Receive scans the ledger and retrieves unspent coins paid to a particular user address:
Receive


 inputs:
 recipient address key pair (addr_{pk}, addr_{sk})
 the current ledger L
 outputs: set of (unspent) received coins
 inputs:

When a user with address key pair (addr_{pk}, addr_{sk}) wishes to receive payments sent to addr_{pk}, he uses the Receive algorithm to scan the ledger. For each payment to addr_{pk} appearing in the ledger, Receive outputs the corresponding coins whose serial numbers do not appear on the ledger L. Coins received in this way may be spent, just like minted coins, using the Pour algorithm. (We only require Receive to detect coins paid to addr_{pk} via the Pour algorithm and not also detect coins minted by the user himself.)
Next, we describe completeness (Section 3.3) and security (Section 3.4).
Completeness
Completeness of a DAP scheme requires that unspent coins can be spent. More precisely, consider a ledger sampler S outputting a ledger L. If c_{1} and c_{2} are two coins whose coin commitments appear in (valid) transactions on L, but their serial numbers do not appear in L, then c_{1} and c_{2} can be spent using Pour. Namely, running Pour results in a pour transaction tx_{Pour} that VerifyTransaction accepts, and the new coins can be received by the intended recipients (by using Receive); moreover, tx_{Pour} correctly records the intended v_{pub} and transaction string info. This property is formalized via an incompleteness experiment INCOMP.
Deftnition 3.1. A DAP scheme Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) is complete if no polynomialsize ledger sampler S wins INCOMP with more than negligible probability. (See Appendix B for details.)
Security
Security of a DAP scheme is characterized by three properties, which we call ledger indistinguishability, transaction nonmalleability, and balance.
Deftnition 3.2. A DAP scheme Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) is secure if it satisfies ledger indistinguishability, transaction nonmalleability, and balance.
Below, we provide an informal overview of each property, and defer formal definitions to Appendix C.
Each property is formalized as a game between an adversary A and a challenger C. In each game, the behavior of honest parties is realized via a DAP scheme oracle ODAP, which maintains a ledger L and provides an interface for executing CreateAddress, Mint, Pour and Receive algorithms for honest parties. To elicit behavior from honest parties, A passes a query to C, which (after sanity checks) proxies the query to ODAP. For each query that requests an honest party to perform an action, A specifies identities of previous transactions and the input values, and learns the resulting transaction, but not any of the secrets or trapdoors involved in producing that transaction. The oracle ODAP also provides an Insert query that allows A to directly add aribtrary transactions to the ledger L.
Ledger indistinguishability. This property captures the requirement that the ledger reveals no new information to the adversary beyond the publiclyrevealed information (values of minted coins, public values, information strings, total number of transactions, etc.), even when the adversary can adaptively induce honest parties to perform DAP operations of his choice. That is, no bounded adversary A can distinguish between two ledgers L_{0} and L_{1}, constructed by A using queries to two DAP scheme oracles, when the queries to the two oracles are publicly consistent : they have matching type and are identical in terms of publiclyrevealed information and the information related to addresses controlled by A.
Ledger indistinguishability is formalized by an experiment LIND that proceeds as follows.
First, a challenger samples a random bit b and initializes two DAP scheme oracles ODAP and
0
ODAP, maintaining ledgers L_{0} and L_{1}. Throughout, the challenger allows A to issue queries to
1
ODAP and ODAP, thus controlling the behavior of honest parties on L_{0} and L_{1}. The challenger
0
1
provides the adversary with the view of both ledgers, but in randomized order: L_{Left} := L_{b} and L_{Right} := L_{1−}_{b}. The adversary’s goal is to distinguish whether the view he sees corresponds to (L_{Left}, L_{Right}) = (L_{0}, L_{1}), i.e. b = 0, or to (L_{Left}, L_{Right}) = (L_{1}, L_{0}), i.e. b = 1.
At each round of the experiment, the adversary issues queries in pairs Q, Q^{j} of matching query type. If the query type is CreateAddress, then the same address is generated at both oracles. If it is to Mint, Pour or Receive, then Q is forwarded to L_{0} and Q^{j} to L_{1}; for Insert queries, query Q is forwarded to L_{Left} and Q^{j} is forwarded to L_{Right}. The adversary’s queries are restricted in the sense that they must maintain the public consistency of the two ledgers. For example, the public values for Pour queries must be the same, as well as minted amounts for Mint queries.
At the conclusion of the experiment, A outputs a guess b^{j}, and wins when b = b^{j}. Ledger indistinguishability requires that A wins LIND with probability at most negligibly greater than 1/2.
Transaction nonmalleability. This property requires that no bounded adversary A can alter any of the data stored within a (valid) pour transaction tx_{Pour}. This transaction nonmalleability prevents malicious attackers from modifying others’ transactions before they are added to the ledger (e.g., by retargeting the Basecoin public output of a pour transaction).
Transaction nonmalleability is formalized by an experiment TRNM, in which A adaptively interacts with a DAP scheme oracle ODAP and then outputs a pour transaction tx^{∗}. Letting T denote the set of pour transactions returned by ODAP, and L denote the final ledger, A wins the game if there exists tx ∈ T , such that (i) tx^{∗} ƒ= tx; (ii) tx^{∗} reveals a serial number contained in tx; and (iii) both tx and tx are valid with respect to the ledger L containing all transactions preceding tx on L. In other words, A wins the game if tx^{∗} manages to modify some previous pour transaction to spend the same coin in a different way.
∗ j
Transaction nonmalleability requires that A wins TRNM with only negligible probability. (Note that A can of course produce valid pour transactions that are unrelated to those in T ; the condition that tx reveals a serial number of a previouslyspent coin captures nonmalleability.)
∗
Balance. This property requires that no bounded adversary A can own more money than what he minted or received via payments from others.
Balance is formalized by an experiment BAL, in which A adaptively interacts with a DAP scheme oracle ODAP and then outputs a set of coins S_{coin}. Letting ADDR be set of addresses returned by CreateAddress queries (i.e., addresses of “honest” users), A wins the game if the total value he can spend or has spent (either as coins or Basecoin public outputs) is greater than the value he has minted or received. That is, A wins if v_{Unspent} + v_{Basecoin} + v_{A→ADDR} > v_{Mint} + v_{ADDR→A} where:
 v_{Unspent} is the total value of unspent coins in S_{coin}; (ii) v_{Basecoin} is the total value of public outputs placed by A on the ledger; (iii) v_{Mint} is the total value of A’s mint transactions; (iv) v_{ADDR→A} is the total value of payments received by A from addresses in ADDR; (v) v_{A→ADDR} is the total value
of payments sent by A to addresses in ADDR.
Balance requires that A wins BAL with only negligible probability.
Construction of a decentralized anonymous payment scheme
We show how to construct a DAP scheme (introduced in Section 3) using zkSNARKs and other building blocks. Later, in Section 5, we give a concrete instantiation of this construction.
Cryptographic building blocks
We first introduce notation for the standard cryptographic building blocks that we use. We assume familiarity with the definitions of these building blocks; for more details, see, e.g., [KL07]. Throughout, λ denotes the security parameter.
Collisionresistant hashing. We use a collisionresistant hash function CRH : {0, 1}∗ → {0, 1}O(λ).
Pseudorandom functions. We use a pseudorandom function family PRF = {PRF_{x} : {0, 1}∗ →
{0, 1}O(λ)}_{x} where x denotes the seed. From PRF_{x}, we derive three “nonoverlapping” pseudorandom functions, chosen arbitrarily as PRF^{addr}(z) := PRF_{x}(00″z) , PRF^{sn}(z) := PRF_{x}(01″z) , PRF^{pk}(z) :=
x
x
x
PRF_{x}(10″z). Furthermore, we assume that PRF^{sn} is also collision resistant, in the sense that it is infeasible to find (x, z) ƒ= (x^{j}, z^{j}) such that PRF^{sn}(z) = PRF^{sn}(z^{j}).
x
xj
Statisticallyhiding commitments. We use a commitment scheme COMM where the bind ing property holds computationally, while the hiding property holds statistically. It is denoted
{COMM_{x} : {0, 1}∗ → {0, 1}O(λ)}_{x} where x denotes the commitment trapdoor. Namely, to reveal a
commitment cm to a value z, it suffices to provide z and the trapdoor x; then one can check that
cm = COMM_{x}(z).
Onetime stronglyunforgeable digital signatures. We use a digital signature scheme Sig = (G_{sig}, K_{sig}, S_{sig}, V_{sig}) that works as follows.
 G _{sig}(1^{λ}) → ppsig. Given a security parameter λ (presented in unary), G_{sig} samples public parameters
ppsig for the encryption scheme.
 K _{sig}(ppsig) → (pksig, sk_{sig}). Given public parameters ppsig, K_{sig} samples a public key and a secret key for a single user.
 S _{sig}(sk_{sig}, m) → σ. Given a secret key sk_{sig} and a message m, S_{sig} signs m to obtain a signature σ.
 V _{sig}(pksig, m, σ) → b. Given a public key pksig, message m, and signature σ, V_{sig} outputs b = 1 if the signature σ is valid for message m; else it outputs b = 0.
The signature scheme Sig satisfies the security property of onetime strong unforgeability against chosenmessage attacks (SUF1CMA security).
Keyprivate publickey encryption. We use a publickey encryption scheme Enc = (G_{enc}, K_{enc},
E_{enc}, D_{enc}) that works as follows.
 G _{enc}(1^{λ}) → ppenc. Given a security parameter λ (presented in unary), G_{enc} samples public parameters ppenc for the encryption scheme.
 K _{enc}(ppenc) → (pkenc, sk_{enc}). Given public parameters ppenc, K_{enc} samples a public key and a secret key for a single user.
 E _{enc}(pkenc, m) → c. Given a public key pkenc and a message m, E_{enc} encrypts m to obtain a ciphertext c.
 D _{enc}(sk_{enc}, c) → m. Given a secret key sk_{enc} and a ciphertext c, D_{enc} decrypts c to produce a message m (or ⊥ if decryption fails).
The encryption scheme Enc satisfies two security properties: (i) ciphertext indistinguishability under chosenciphertext attack (INDCCA security); and (ii) key indistinguishability under chosenciphertext
attack (IKCCA security). While the first property is standard, the second is less known; informally, IKCCA requires that ciphertexts cannot be linked to the public key used to encrypt them, or to other ciphertexts encrypted with the same public key. For definitions, we refer the reader to [BBDP01].
zkSNARKs for pouring coins
As outlined in Section 1.3, our construction invokes a zkSNARK for a specific NP statement, POUR, which we now define. We first recall the context motivating POUR. When a user u pours “old” coins c^{old}, c^{old} into new coins c^{new}, c^{new}, a corresponding pour transaction
1 2 1 2
tx_{Pour} = (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, info, ∗)
1
2
1
2
is generated. In our construction, we need to provide evidence in “∗” that various conditions were respected by the pour operation. Concretely, tx_{Pour} should demonstrate that (i) u owns c^{old}, c^{old}; (ii) coin commitments for c^{old}, c^{old} appear somewhere on the ledger; (iii) the revealed
1 2 1 2
serial numbers sn^{old}, sn^{old} are of c^{old}, c^{old}; (iv) the revealed coin commitments cm^{new}, cm^{new}
are
1 2 1 2 1 2
of c^{new}, c^{new}; (v) balance is preserved. Our construction achieves this by including a zkSNARK
1 2
proof π_{POUR} for the statement POUR which checks the above invariants (as well as others needed for
nonmalleability).
The statement POUR. Concretely, the NP statement POUR is defined as follows.
 Instances are of the form x = (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, h_{Sig}, h_{1}, h_{2}). Thus, an instance x
1
2
1
2
specifies a root rt for a CRHbased Merkle tree (over the list of commitments so far), the two serial numbers of the consumed coins, two coin commitments for the two new coins, a public value, and fields h_{Sig}, h_{1}, h_{2} used for nonmalleability.
 Witnesses are of the form a = (path1, path2, c^{old}, c^{old}, addr^{old} , addr^{old} , c^{new}, c^{new}) where, for each
i ∈ {1, 2}:
1 2 sk,1
sk,2 1 2
cold = (addrold , vold, ρold, rold, sold, cmold) ,
i pk,i i i i i i
c^{new} = (addr^{new}, v^{new}, ρ^{new}, r^{new}, s^{new}, cm^{new}) for the same cm^{new} as in x,
i pk,i i i i i i i
addr^{old} = (a^{old} , pk^{old} ) ,
pk,i
pk,i
enc,i
addr^{new} = (a^{new}, pk^{new} ) ,
pk,i
pk,i
enc,i
addr^{old} = (a^{old} , sk^{old} ) .
sk,i
sk,i
enc,i
Thus, a witness a specifies authentication paths for the two new coin commitments, the entirety of coin information about both the old and new coins, and address secret keys for the old coins.
Given a POUR instance x, a witness a is valid for x if the following holds: 1.For each i ∈ {1, 2}:
 The coin commitment cm^{old} of c^{old} appears on the ledger, i.e., pathi is a valid authentication
i i
path for leaf cm^{old} with respect to root rt, in a CRHbased Merkle tree.
i
a
 The address secret key a^{old}
matches the address public key of c^{old}, i.e., a^{old}
= PRF^{addr}(0).
sk,i
i pk,i
old sk,i
 The serial number sn^{old} of c^{old} is computed correctly, i.e., sn^{old} = PRF^{sn} (ρ^{old}).
i i i
a
old i
sk,i
 The coin c^{old} is wellformed, i.e., cm^{old} = COMM old (COMM old (a^{old} “ρ^{old})”v^{old}).
i
i
si
ri
pk,i
i
i
 The coin c^{new} is wellformed, i.e., cm^{new} = COMM_{s}new (COMM_{r}new (a^{new}“ρ^{new})”v^{new}).
i
i
i
i
pk,i
i
i
 The address secret key a^{old}
sk,i
ties h_{Sig} to h_{i}, i.e., h_{i} = PRF^{pk}
sk,i
aold
(i“h_{Sig}).
2. Balance is preserved: v^{new} + v^{new} + v_{pub} = v^{old} + v^{old} (with v^{old}, v^{old} ≥ 0 and v^{old} + v^{old} ≤ v_{max}).
1
2
1
2
1
2
1
2
Recall that in this paper zkSNARKs are relative to the language of arithmetic circuit satisfiability (see Section 2); thus, we express the checks in POUR via an arithmetic circuit, denoted C_{POUR}. In particular, the depth d_{tree} of the Merkle tree needs to be hardcoded in C_{POUR}, and we thus make it a parameter of our construction (see below); the maximum number of supported coins is then 2^{d}tree .
Algorithm constructions
We proceed to describe the construction of the DAP scheme Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) whose intuition was given in Section 1.3. Figure 2 gives the pseudocode for each one of the six algorithms in Π, in terms of the building blocks introduced in Section 4.1 and Section 4.2. In the construction, we hardcode two quantities: the maximum value of a coin, v_{max}, and the depth of the Merkle tree, d_{tree}.
Completeness and security
Our main theorem states that the above construction is indeed a DAP scheme.
Theorem 4.1. The tuple Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive), as de fined in Section 4.3, is a complete (cf. Definition 3.1) and secure (cf. Definition 3.2) DAP scheme.
We provide a proof of Theorem 4.1 in Appendix D. We note that our construction can be modified to yield statistical (i.e., everlasting) anonymity; see the discussion in Section 8.1.
Remark (trusted setup). Security of Π relies on a trusted party running Setup to generate the public parameters (once and for all). This trust is needed for the transaction nonmalleability and balance properties but not for ledger indistinguishability. Thus, even if a powerful espionage agency were to corrupt the setup, anonymity will still be maintained. Moreover, if one wishes to mitigate the trust requirements of this step, one can conduct the computation of Setup using secure multiparty computation techniques; we leave this to future work.
Remark (use of pp). According to the definition of a DAP scheme (see Section 3), the public parameters pp are given as input to each one of the six algorithms; this is also how we presented our construction in Figure 2. However, in our construction, the public parameters pp equal a tuple (pkPOUR, vk_{POUR}, ppenc, ppsig), and not every algorithm needs every component of pp. Concretely, CreateAddress only needs ppenc; Mint only the security parameter λ; Pour only pkPOUR and ppsig; VerifyTransaction only vk_{POUR}; and Receive only λ. In particular, since we rely on zkSNARKs to prove/verify POUR, pkPOUR is of constant, but large, size, and is only required by Pour. All other components of pp are of small constant size.
Remark (checking received coins in ledger). The algorithm Receive tests whether the serial number of a received coin already appears on the ledger, in order not to output coins that the user has already received and spent by himself. Other users are, in any case, unable to spend coins addressed to this user.
Zerocash
We describe a concrete instantiation of a DAP scheme; this instantiation forms the basis of Zerocash. Later, in Section 6, we discuss how Zerocash can be integrated with existing ledgerbased currencies.
Setup
 Construct CPOUR for POUR at security λ.
λ
Pour
 inputs:
 public parameters pp
 the Merkle root rt
 old coins c^{old}, c^{old}
 Compute ( pk_{POUR}, vkPOUR) := KeyGen(1 , CPOUR).
1 2
old
old
 Compute pp
:= Genc(1^{λ}).
 old addresses secret keys addrsk,1, addrsk,2
enc
λ
– path path from commitment cm(c^{old}) to root rt,
 Compute ppsig := G_{sig}(1 ).
1
path path
1
from commitment cm(c^{old}) to root rt
 Set pp := (pk_{POUR}, vkPOUR, pp_{enc}, pp_{sig}).
2
new
2
new
 Output pp.
 new values v_{1} , v_{2}
 new addresses public keys addr^{new} , addr^{new}
CreateAddress
 public value v_{pub}
 transaction string info
pk,1
pk,2
 inputs: public parameters pp
 outputs: address key pair (addr_{pk}, addr_{sk})
1.Compute ( pk_{enc}, skenc) := Kenc(pp_{enc}).
 outputs: new coins c_{1} , c_{2} and pour transaction tx_{Pour}
 For each i 1, 2 :
new new
∈ { }

 Parse c^{old} as (addr^{old} , v^{old}, ρ^{old}, r^{old}, s^{old}, cm^{old}).
 Randomly sample a PRF^{addr} seed a .
i pk,i i
i i i i
sk (b)Parse addr^{old} as (a^{old} , sk^{old} ).
 Compute a_{pk} = PRF^{addr}(0).
sk,i
sk,i
enc,i
ask

 Compute sn^{old} := PRF^{sn}
(ρ^{old}).
 Set addr_{pk}
:= (a_{pk}
, pkenc).
i
new
enc,i
new
old i
sk,i
a
 Set addr_{sk} := (a_{sk}
, skenc).

 Parse addrpk,i as (apk,i, pk^{new} ).
 Output ( addr_{pk}
, addr_{sk}).

 Randomly sample a PRF^{sn} seed ρ^{new}.
 Randomly sample two COMM trapdoors r^{new}, s^{new}. (g)Compute k^{new} := COMM_{r}new (a^{new} “ρ^{new}).
i
i i
Mint
i
new
i pk,i i


 Compute cm_{i} := COMM_{s}new (v^{new}“k^{new}).

 inputs:
new
new
new i i i
new


 Set c_{i} := (addrpk

, v_{i} , ρ^{new}, r^{new}, s^{new}, cm_{i} ).

 public parameters pp
,i i i i


 Set Ci := Eenc(pk^{new} , (v^{new}, ρ^{new}, r^{new}, s^{new})).
 coin value v ∈ {0, 1, . . . , vmax}

enc,i i
i i i

 destination address public key addr_{pk}
 outputs: coin c and mint transaction tx_{Mint}
 Parse addr_{pk} as (a_{pk}, pkenc).
 Generate ( pksig , sk_{sig}) := K_{sig}(ppsig ).
 Compute h_{Sig} := CRH(pksig ).
 Compute h_{1} := PRF^{pk} (1 h_{Sig}) and h_{2} := PRF^{pk}
aold
aold
”
sk,1 sk,2
(2″h_{Sig}).
sn 5.Set x := (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, h_{Sig}, h_{1}, h_{2}).
 Randomly sample a PRF
seed ρ.
1 2 1 2
6.Set a := (path , path , c^{old}, c^{old}, addr^{old} , addr^{old} , c^{new}, c^{new}).
 Randomly sample two COMM trapdoors r, s.
1 2 1 2
sk,1
sk,2 1 2
 Compute k := COMM_{r}(a_{pk}“ρ). 5.Compute cm := COMMs(v“k). 6.Set c := (addr_{pk}, v, ρ, r, s, cm).
 Set tx_{Mint} := (cm, v, ∗), where ∗ := (k, s).
 Compute πPOUR := Prove(pk_{POUR}, x, a).
 Set m := (x, πPOUR, info, C1, C2). 9.Compute σ := S_{sig}(sk_{sig}, m).
10.Set tx_{Pour} := (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, info, ∗), where
1 2 1 2
 Output c and tx_{Mint}.
VerifyTransaction
 inputs:
 public parameters pp
 a (mint or pour) transaction tx
 the current ledger L
 outputs: bit b, equals 1 iff the transaction is valid 1.If given a mint transaction tx = tx_{Mint}:
 Parse tx_{Mint} as (cm, v, ∗), and ∗ as (k, s).
 Set cm := COMMs(v k).
”
j

 Output b := 1 if cm = cm^{j}, else output b := 0.
2.If given a pour transaction tx = tx_{Pour}:
:= (pk_{sig}, h1, h2, πPOUR, C1, C2, σ).
11.Output c^{new}, c^{new} and tx_{Pour}.
∗
1 2
Receive
 inputs:
 public parameters pp
 recipient address key pair (addr_{pk}, addr_{sk})
 the current ledger L
 outputs: set of received coins
1.Parse addr_{pk} as (a_{pk}, pkenc). 2.Parse addr_{sk} as (a_{sk}, sk_{enc}).
 For each Pour transaction tx_{Pour} on the ledger:
 Parse tx_{Pour} as (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, info, ∗),
1
2
1
2
 Parse tx_{Pour} as (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, info, ∗), and
1
2
1
2
and ∗ as (pk_{sig}, h1, h2, πPOUR, C1, C2, σ).
∗ as (pk_{sig}, h1, h2, πPOUR, C1, C2, σ).
 If sn^{old} or sn^{old} appears on L (or sn^{old} = sn^{old}), output b := 0. (c)If the Merkle root rt does not appear on L, output b := 0. (d)Compute h_{Sig} := CRH(pk ).
1
2
1
2
sig
 For each i ∈ {1, 2}:
 Compute ( vi, ρi, ri, si) := Denc(skenc, Ci). ii.If Denc’s output is not ⊥, verify that:
 cm equals COMM_{s} (v_{i}“COMM_{r} (a_{pk}“ρ_{i}));
 Compute ( vi, ρi, ri, si) := Denc(skenc, Ci). ii.If Denc’s output is not ⊥, verify that:
new
i
i
i
ask
sn
 Set x := (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v , h , h , h ).
1
2
1
2
pub
Sig
1
2
 sni := PRF (ρi) does not appear on L.
 Set m := (x, πPOUR, info, C1, C2). (g)Compute b := V_{sig}(pksig , m, σ).
(h)Compute b^{j} := Verify(vkPOUR, x, πPOUR), and output b ∧ b^{j}.
 If both checks succeed, output
c_{i} := (addr_{pk}, v_{i}, ρ_{i}, r_{i}, s_{i}, cm^{new}).
i
Figure 2: Construction of a DAP scheme using zkSNARKs and other ingredients.
Instantiation of building blocks
We instantiate the DAP scheme construction from Section 4 (see Figure 2), aiming at a level of security of 128 bits. Doing so requires concrete choices, described next.
CRH, PRF, COMM from SHA256. Let H be the SHA256 compression function, which maps a 512bit input to a 256bit output. We mostly rely on H, rather than the “full” hash, since this suffices for our fixedsize singleblock inputs, and it simplifies the construction of C_{POUR} (see Section 5.2). We instantiate CRH, PRF, COMM via H (under suitable assumptions on H).
First, we instantiate the collisionresistant function CRH as H(z) for z ∈ {0, 1}512; this function
compresses “twotoone”, so it can be used to construct binary Merkle trees.
Next, we instantiate the pseudorandom function PRF_{x}(z) as H(x“z), with x ∈ {0, 1}256 as the seed, and z ∈ {0, 1}256 as the input.^{15} Thus, the derived functions are:
PRF^{addr}(z) := H(x“00”z) , PRF^{sn}(z) := H(x“01”z) , PRF^{pk}(z) := H(x“10”z) ,
x x x
with x ∈ {0, 1}256 and z ∈ {0, 1}254.
As for the commitment scheme COMM, we only use it in the following pattern:
k := COMM_{r}(a_{pk}“ρ) ,
cm := COMM_{s}(v“k) .
Due to our instantiation of PRF, a_{pk} is 256 bits. So we can set ρ also to 256 bits and r to 256 + 128 = 384 bits; then we can compute
k := COMM_{r}(a_{pk}“ρ) as H(r“[H(a_{pk}“ρ)]_{128}) .
Above, [·]_{128} denotes that we are truncating the 256bit string to 128 bits (say, by dropping least significant bits, as in our implementation). Heuristically, for any string z ∈ {0, 1}128, the distribution induced by H(r“z) is 2^{−128}close to uniform, and this forms the basis of the statisticallyhiding property. For computing cm, we set coin values to be 64bit integers (so that, in particular, v_{max} = 2^{64} − 1 in our implementation), and then compute
cm := COMM_{s}(v“k) as H(k“0^{192}“v) .
Noticeably, above we are ignoring the commitment randomness s. The reason is that we already know that k, being the output of a statisticallyhiding commitment, can serve as randomness for the next commitment scheme.
Instantiating the NP statement POUR. The above choices imply a concrete instantiation of the NP statement POUR (see Section 4.2). Specifically, in our implementation, POUR checks that the following holds, for each i ∈ {1, 2}:

 pathi is an authentication path for leaf cm^{old} with respect to root rt, in a CRHbased Merkle tree;
i
sk,i
old pk,i
 a
= H(a^{old} “0^{256});

 sn^{old} = H(a^{old} “01”[ρ^{old}]_{254});
i
sk,i
i

 cm^{old} = H(H(r^{old}“[H(a^{old} “ρ^{old})]_{128})”0^{192}“v^{old});
i
i
pk,i
i
i
14A single exception: we still compute h_{Sig} according to the full hash SHA256, rather than its compression function,
because there is no need for this computation to be verified by CPOUR.
15This assumption is reminiscent of previous works analyzing the security of hashbased constructions (e.g., [Bel06]). However in this work we assume that a portion of the compression function is the seed for the pseudorandom function, rather than using the chaining variable as in [Bel06].

 cm^{new} = H(H(r^{new}“[H(a^{new}“ρ^{new})]_{128})”0^{192}“v^{new}); and
i
i
pk,i
i
i

 h_{i} = H(a^{old} “10”b_{i}“[h_{Sig}]_{253}) where b_{1} := 0 and b_{2} := 1.
sk,i
Moreover, POUR checks that v^{new} + v^{new} + v_{pub} = v^{old} + v^{old}, with v^{old}, v^{old} ≥ 0 and v^{old} + v^{old} < 2^{64}.
1
2
1
2
1
2
1
2
Finally, as mentioned, in order for C_{POUR} to be welldefined, we need to fix a Merkletree depth
d_{tree}. In our implementation, we fix d_{tree} = 64, and thus support up to 2^{64} coins.
Instantiating Sig. For the signature scheme Sig, we use ECDSA to retain consistency and compatibility with the existing bitcoind source code. However, standard ECDSA is malleable: both (r, s) and (r, −s) verify as valid signatures. We use a nonmalleable variant, where s is restricted to the “lower half” of field elements. While we are not aware of a formal SUF1CMA proof for this variant, its use is consistent with proposals to resolve Bitcoin transaction malleability [Wui14].^{16}
Instantiating Enc. For the encryption scheme Enc, we use the keyprivate EllipticCurve Integrated Encryption Scheme (ECIES) [Cer00]; it is one of the few standardized keyprivate encryption schemes with available implementations.
Arithmetic circuit for pouring coins
Our DAP scheme construction from Section 4 (see Figure 2) also requires zkSNARKs relative to the NP statement POUR. These are obtained by invoking a zkSNARK for arithmetic circuit satisfiability (see Section 2.4) on an arithmetic circuit C_{POUR}, which verifies the NP statement POUR. In our instantiation, we rely on the implementation of [BCTV14] for the basic zkSNARK (see Section 2.4), and apply it to the circuit C_{POUR} whose construction is described next.
An arithmetic circuit for verifying SHA256’s compression function
The vast majority of the “verification work” in POUR is verifying computations of H, the compression function of SHA256 (see Section 5.1). Thus, we begin by discussing our construction of an arithmetic circuit C_{H} for verifying SHA256 computations. Later, in Section 5.2.2, we discuss the construction of C_{POUR}, given the circuit C_{H}.
We wish to construct an arithmetic circuit C_{H} such that, for every 256bit digest h and 512bit
input z, (h, z) ∈ R_{C}H if and only if h = H(z). Naturally, our goal is to minimize the size of C_{H}. Our highlevel strategy is to construct C_{H}, piece by piece, by closely following the SHA256 official specification [Nat12]. For each subcomputation of SHA256, we use nondeterminism and field operations to verify the subcomputation using as few gates as possible.
Overview of SHA256’s compression function. The primitive unit in SHA256 is a 32bit word. All subcomputations are simple word operations: three bitwise operations (and, or, xor), shiftright, rotateright, and addition modulo 2^{32}. The compression function internally has a state of 8 words, initialized to a fixed value, and then transformed in 64 successive rounds by following the 64word message schedule (deduced from the input z). The 256bit output is the concatenation of the 8 words of the final state.
Representing a state. We find that, for each word operation (except for addition modulo 2^{32}), it is more efficient to verify the operation when its inputs are represented as separate wires, each carrying a bit. Thus, C_{H} maintains the 8word state as 256 individual wires, and the 64word message schedule as 64 · 32 wires.
Addition modulo 32. To verify addition modulo 2^{32} we use techniques employed in previous
work [PGHR13, BCG^{+}13, BCTV14]. Given two words A and B, we compute α := Σ31 2^{i}(A_{i} + B_{i}).
i=0
16In practice, one might replace this ECDSA variant with an ECSchnorr signature satisfying SUF1CMA security with proper encoding of EC group elements; the performance would be similar.
Because F has characteristic larger than 2^{33}, there is no wrap around; thus, field addition coincides with integer addition. We then make a nondeterministic guess for the 33 bits α_{i} of α (including
carry), and enforce consistency by requiring that α = Σ32 2^{i}α_{i}. To ensure that each α_{i} ∈ {0, 1},
i=0
−
we use a 33gate subcircuit computing α_{i}(α_{i} 1), all of which must be 0 for the subcircuit to be
satisfiable. Overall, verifying addition modulo 2^{32} only requires 34 gates. This approach extends in a straightforward way to summation of more than two terms.
Verifying the SHA256 message schedule. The first 16 words W_{i} of the message schedule are the 16 words of the 512bit input z. The remaining 48 words are computed as W_{t} := σ_{1}(W_{t}_{−2}) + W_{t}_{−7} + σ_{0}(W_{t}_{−15}) + W_{t}_{−16}, where σ_{0}(W ) := rotr7(W ) ⊕ rotr18(W ) ⊕ shr3(W ) and σ_{1} has the same structure but different rotation and shift constants.
The rotation and shift amounts are constants, so rotates and shifts can be achieved by suitable wiring to previously computed bits (or the constant 0 for highorder bits in shr). Thus, since the XOR of 3 bits can be computed using 2 gates, both σ_{0} and σ_{1} can be computed in 64 gates. We then compute (or more precisely, guess and verify) the addition modulo 2^{32} of the four terms.
Verifying the SHA256 round function. The round function modifies the 8word state by changing two of its words and then permuting the 8word result.
Each of the two modified words is a sum modulo 2^{32} of (i) roundspecific constant words K_{t};
 message schedule words W_{t}; and (iii) words obtained by applying simple functions to state words. Two of those functions are bitwise majority (Maj(A, B, C)_{i} = 0 if A_{i} + B_{i} + C_{i} ≤ 1 else 1) and bitwise choice (Ch(A, B, C)_{i} = B_{i} if A_{i} = 1, else C_{i}). We verify correct computation of Maj using 2 gates per output bit, and Ch with 1.
Then, instead of copying 6 unchanged state words to obtain the permuted result, we make the permutation implicit in the circuit’s wiring, by using output wires of previous subcomputations (sometimes reaching 4 round functions back) as input wires to the current subcomputation.
Performance. Overall, we obtain an arithmetic circuit C_{H} for verifying SHA256’s compression function with less than 30 000 arithmetic gates. See Figure 3 for a breakdown of gate counts.
Gate count for  CH 
Message schedule  8032 
All rounds  19 584 
1 round (of 64)  306 
Finalize  288 
Total  27 904 
Figure 3: Size of circuit CH for SHA256’s compression function.
Comparison with generic approaches. We constructed the circuit C_{H} from scratch. We could have instead opted for more generic approaches: implement SHA256’s compression function in a higherlevel language, and use a circuit generator to obtain a corresponding circuit. However, generic approaches are significantly more expensive for our application, as we now explain.
Starting from the SHA256 implementation in PolarSSL (a popular cryptographic library) [Pol13], it is fairly straightforward to write a C program for computing H. We wrote such a program, and gave it as input to the circuit generator of [PGHR13]. The output circuit had 58160 gates, more than twice larger than our handoptimized circuit.
Alternatively, we also compiled the same C program to TinyRAM, which is the architecture supported in [BCG^{+}13]; we obtained a 5371instruction assembly code that takes 5704 cycles to execute on TinyRAM. We could then invoke the circuit generator in [BCG^{+}13] when given this TinyRAM program and time bound. However, each TinyRAM cycle costs ≈ 1000 gates, so the resulting circuit would have at least 5.7 · 10^{6} gates, i.e., over 190 times larger than our circuit. A
similar computation holds for the circuit generator in [BCTV14], which supports an even more flexible architecture.
Thus, overall, we are indeed much better off constructing C_{H} from scratch. Of course, this is not surprising, because a SHA256 computation is almost a “circuit computation”: it does not make use of complex program flow, accesses to memory, and so on. Thus, relying on machinery developed to support much richer classes of programs does not pay off.
Arithmetic circuit for POUR
The NP statement POUR requires verifying membership in a Merkle tree based on H, a few additional invocations of H, and integer addition and comparison. We construct the circuit C_{POUR} for POUR by combining various subcircuits verifying each of these. There remains to to discuss the subcircuits for verifying membership in a Merkle tree (using the aforementioned subcircuit C_{H} for verifying invocations of H), and integer addition and comparison.
Merkle tree membership. We need to construct an arithmetic circuit that, given a root rt, authentication path path, and coin commitment cm, is satisfied if and only if path is a valid authentication path for the leaf cm with respect to the root rt. The authentication path path includes, for each layer i, an auxiliary hash value h_{i} and a bit r_{i} specifying whether h_{i} was the left (r_{i} = 0) or the right (r_{i} = 1) child of the parent node. We then check membership in the Merkle tree by verifying invocations of H, bottomup. Namely, for d = 64, we set k_{d}_{−1} = cm; then, for each i = d − 1, . . . , 1, we set B_{i} = h_{i}“k_{i} if r_{i} = 0 else k_{i}“h_{i}, and compute k_{i}_{−1} = H(B_{i}). Finally we check that the root k_{0} matches the given root rt.
Integer addition. We need to construct an arithmetic circuit that, given 64bit integers A, B, C
(presented as binary strings), is satisfied if and only if C = A + B over the integers. Again relying
on the fact that F’s characteristic is sufficiently large, we do so by checking that Σ63 2^{i}c_{i} =
Σ63 i
i=0
i=0 2 (b_{i} + a_{i}) over F; this is enough, because there is no wrap around.
Integer comparison. We need to construct an arithmetic circuit that, given two 64bit integers
A, B (represented in binary), is satisfied if and only if A + B fits in 64 bits (i.e. A + B < 2^{64}). We
do so by checking that Σ63 2^{i}(b_{i} + a_{i}) = Σ63 c_{i} for some c_{i} ∈ {0, 1}. Indeed, if A + B < 2^{64} then
i=0
i=0
it suffices to take c_{i} as the binary representation of A + B. However, if A + B ≥ 2^{64} then no choice
of c_{i} can satisfy the constraint as Σ63 c_{i} ≤ 2^{64} − 1. Overall, this requires 65 gates (1 gate for the
i=0
equality check, and 64 gates for ensuring that c_{0}, . . . , c_{63} are boolean).
Overall circuit sizes. See Figure 4 for the size of C_{POUR}. More than 99% of the gates are devoted to verifying invocations of H.
Gate count for CPOUR  
Ensure cm^{old} is in Merkle tree
1 (1 layer out of 64) Ensure cm^{old} is in Merkle tree 2 (1 layer out of 64) Check computation of sn^{old}, sn^{old} 1 2 Check computation of a^{old} , a^{old} pk,1 pk,2 Check computation of cm^{old}, cm^{old}, cm^{new}, cm^{new} 1 2 1 2 Check computation of h1, h2 Ensure that v^{new} + v^{new} + v_{pub} = v^{old} + v^{old} 1 2 1 2 Ensure that v^{old} + v^{old} < 2^{64} 1 2 Miscellaneous 
1 802 304
(28 161) 1 802 304 (28 161) 2 × 27 904 2 × 27 904 4 × 83 712 2 × 27 904 1 65 2384 
Total  4 109 330 
Figure 4: Size of the circuit CPOUR, which verifies the statement POUR.
Integration with existing ledgerbased currencies
Zerocash can be deployed atop any ledger (even one maintained by a central bank). Here, we briefly detail integration with the Bitcoin protocol. Unless explicitly stated otherwise, in the following section when referring to Bitcoin, and its unit of account bitcoin (plural bitcoins), we mean the underlying protocol and software, not the currency system. (The discussion holds, with little or no modification, for many forks of Bitcoin, also known as “altcoins”, such as Litecoin.)
By introducing new transaction types and payment semantics, Zerocash breaks compatibility with the Bitcoin network. While Zerocash could be integrated into Bitcoin (the actual currency and its supporting software) via a “flag day” where a supermajority of Bitcoin miners simultaneously adopt the new software, we neither expect nor advise such integration in the near future and suggest using Zerocash in a separate altcoin.
Integrating Zerocash into Bitcoin consists of adding a new transaction type, Zerocash transactions, and modifying the protocol and software to invoke Zerocash’s DAP interface to create and verify these transactions. There are at least two possible approaches to this integration. The first approach replaces all bitcoins with zerocoins, making all transactions anonymous at the cost of losing any additional Bitcoin functionality provided by, e.g., the Bitcoin scripting language (see Section 6.1). The second approach maintains this functionality, adding a parallel Zerocash currency, zerocoin, which can be converted to and from bitcoin at a onetoone rate (see Section 6.2). Options for protocollevel modifications for the later approach are discussed in Section 6.3; the former can be readily inferred. In Section 6.4 we discuss anonymizing the network layer of Bitcoin and anonymity safeguards.
Integration by replacing the base currency
One approach is to alter the underlying system so that all monetary transactions are done using Zerocash, i.e., by invoking the DAP interface and writing/reading the associated transactions in the distributed ledger.
As seen in Section 3, this suffices to offer the core functionality of payments, minting, merging, splitting, etc., while assuring users that all transactions using this currency are anonymous. However, this has several drawbacks: (1) All pour transactions incur the cost of generating a zkSNARK proof.
(2) If Bitcoin supports additional features, such as a scripting language for specifying conditions for claiming bitcoins (as in Bitcoin), then these features are lost.^{17} (3) Bitcoin allows the flexibility of spending unconfirmed transactions; instead, with a Zerocashonly Bitcoin, this flexibility is lost: transactions must be confirmed before they can be spent. (And this imposes a minimal delay between receiving funds and spending them.)
Integration by hybrid currency
A different approach is to extend Bitcoin with a parallel, anonymized currency of “zerocoins”, existing alongside bitcoins, using the same ledger, and with the ability to convert freely between the two. The behavior and functionality of regular bitcoins is unaltered; in particular, they may support functionality such as scripting.
In this approach, the Bitcoin ledger consists of Bitcoinstyle transactions, containing inputs and outputs [Nak09]. Each input is either a pointer to an output of a previous transaction (as in plain Bitcoin), or a Zerocash pour transaction (which contributes its public value, v_{pub}, of bitcoins to this transaction). Outputs are either an amount and destination public address/script (as in plain
17However, in principle POUR could be extended to include a scripting language interpreter.
Bitcoin), or a Zerocash mint transaction (which consumes the input bitcoins to produce zerocoins). The usual invariant over bitcoins is maintained and checked in plain view: the sum of bitcoin inputs (including pours’ v_{pub}) must be at least the sum of bitcoin outputs (including mints’ v), and any difference is offered as a transaction fee. However, the accounting for zerocoins consumed and produced is done separately and implicitly by the DAP scheme.
The life cycle of a zerocoin is as follows.
Creating new zerocoins. A mint transaction consumes v worth of bitcoins as inputs, and outputs coin commitment worth v zerocoins. The v bitcoins are effectively destroyed, in exchange for the newlyminted zerocoins.
Spending zerocoins. Zerocoins can then be transferred, split, and merged into other zerocoins arbitrarily, via pour transactions which, instead of explicit inputs, include zeroknowledge proofs that such inputs exist. Pour transactions may optionally reveal a nonzero public output v_{pub}. This is either left unclaimed as a transaction fee,^{18} placed into a standard Bitcoin transaction output (e.g., one paying to a public key) or consumed by a mint transaction. Thus, v_{pub} bitcoins are created ex nihilo (similarly to how coinbase transactions produce bitcoin outputs as mining reward), in exchange for destroying that amount of zerocoins. The Bitcoin outputs must be included in the transaction string info, which is included as part of a pour transaction; transaction nonmalleability ensures that all this information is bound together.
Spending multiple zerocoins. To allow for pours to span more than two input and output coins, tx_{Pour} structures may be chained together within one transaction by marking some output coin commitments as intermediates and having subsequent pours in the same transaction constructed relative to an ephemeral Merkle tree consisting of only the intermediates commitments. For example, a transaction might accept four input coins, with the first two Pour operations combining two of the inputs to produce an intermediate commitment each and a final Pour combining the two intermediate commitments into a final output new coin. Since the intermediate results are consumed instantly within the transaction, they need not be recorded in the global Merkle tree or have their serial numbers marked as spent.
Transaction fees. Collecting transaction fees is done as usual, via a coinbase transaction added to each block, which pays as mining reward the difference between the total inputs (bitcoin and pours’ v_{pub}) and total outputs (bitcoin and mints’ v) in this block. Payment is either in bitcoins or in newlyminted zerocoins (via a Mint).
Validation and block generation. All transactions are verified via VerifyTransaction when they are received by a node. Any plain Bitcoin inputs and outputs are processed as usual, and any Zerocash inputs and outputs are checked using VerifyTransaction with the entire Bitcoin transaction fed in as info for authentication. Once these transactions are assembled into a candidate block, each transaction needs to be verified again to ensure its serial number has not become spent or its Merkle root invalid. If these checks pass, the set of new coin commitments and spent serial numbers output by the included transactions are added to the global sets, and the new Merkle root and a digest of the serial number list is stored in the new block.^{19} Embedding this data simplifies statekeeping and allows nodes to readily verify they have the correct coin list and serial number list. Upon receiving a candidate block, nodes validate the block is formed correctly with respect to the above procedure.
Receiving payments. In order to receive payments to an address, users may scan the block chain by running the Receive on every pour transaction. Alternatively they may receive coin information
18Since transaction fees may potentially be claimed by any node in the network, they represent the sole zerocoin output that cannot be hidden from public view even in a Zerocashonly system.
19This can be stored in the coinbase transaction, as certain other data currently is, or in a new field in the block
header.
via some outofband mechanism (e.g., via encrypted email). The former process is nearly identical to the one proposed for “stealth addresses” for Bitcoin. In the worst case, scanning the block chain requires a trial decryption of every ciphertext C. We expect many scenarios to provide explicit notification, e.g., in interactive purchases where a communication channel already exists from the payer to the payee. (Implementations may opt to drop the receive mechanism entirely, and require outofband notification, in order to avoid storing the ciphertexts in the block chain.)
Extending the Bitcoin protocol to support the combined semantics
While the section above describes the lifecycle of a zerocoin and semantics of the system, there remains the question of how transactions acquire the above necessary semantics. Two implementation approaches are possible, with different engineering tradeoffs.
The first approach is to extend the protocol and its implementation with hardcoded validation of Zerocash transactions, reading them from new, designated fields in transactions and running VerifyTransaction. In this case the zkSNARK itself effectively replaces the scripting language for Zerocash transactions.
The second approach is to extend Bitcoin’s scripting language by adding an opcode that invokes VerifyTransaction, with the requisite arguments embeded alongside the opcode script. Such transactions must be exempt from the requirement they reference an input (as they are Zerocash transactions are selfcontained), and, like coinbase transactions, be able to create bitcoins ex nihilo (to account for v_{pub}). Moreover, while VerifyTransaction is run at the standard point in the Bitcoin transaction processing flow for evaluating scripts, the coin commitments and spent serial numbers are not actually added to CMList (resp., SNList) until their containing block is accepted (i.e., merely verifying a transaction does not have side effects).
Additional anonymity considerations
Zerocash only anonymizes the transaction ledger. Network traffic used to announce transactions, retrieve blocks, and contact merchants still leaks identifying information (e.g., IP addresses). Thus users need some anonymity network to safely use Zerocash. The most obvious way to do this is via Tor [DMS04]. Given that Zerocash transactions are not low latency themselves, Mixnets (e.g., Mixminion [DDM03]) are also a viable way to add anonymity (and one that, unlike Tor, is not as vulnerable to traffic analysis). Using mixnets that provide emaillike functionality has the added benefit of providing an outofband notification mechanism that can replace Receive.
Additionally, although in theory all users have a single view of the block chain, a powerful attacker could potentially fabricate an additional block solely for a targeted user. Spending any coins with respect to the updated Merkle tree in this “poisonpill” block will uniquely identify the targeted user. To mitigate such attacks, users should check with trusted peers their view of the block chain and, for sensitive transactions, only spend coins relative to blocks further back in the ledger (since creating the illusion for multiple blocks is far harder).
Experiments
To measure the performance of Zerocash, we ran several experiments. First, we benchmarked the performance of the zkSNARK for the NP statement POUR (Section 7.1) and of the six DAP scheme algorithms (Section 7.2). Second, we studied the impact of a higher block verification time via a simulation of a Bitcoin network (Section 7.3).
Performance of zkSNARKs for pouring coins
Our zkSNARK for the NP statement POUR is obtained by constructing an arithmetic circuit C_{POUR} for verifying POUR, and then invoking the generic implementation of zkSNARK for arithmetic circuit satisfiability of [BCTV14] (see Section 2.4). The arithmetic circuit C_{POUR} is built from scratch and handoptimized to exploit nondeterministic verification and the large field characteristic (see Section 5.2) .
Figure 5 reports performance characteristics of the resulting zkSNARK for POUR. This includes three settings: singlethread performance on a laptop machine; and singlethread and multithread performance on a desktop machine. (The time measurements are the average of 10 runs, with standard deviation under 2.5%.) For instance, with singlethread code on the laptop machine, we obtain that:

 Key generation takes 7 min 48 s, and results in a proving key pkPOUR of 896 MiB and a verification key vk_{POUR} of 749 B. This is performed only once, as part of the Setup algorithm.
 Producing a proof π_{POUR} requires about 3 minutes; proofs have a constant size of 288 B. Proof generation is a subroutine of the Pour algorithm, and the resulting proof is included in the corresponding pour transaction.
 A proof π_{POUR} can be verified in only 8.5 ms. Proof verification is a subroutine of the VerifyTransaction algorithm, when it is given as input a pour transaction to verify.
Figure 5: Performance of our zkSNARK for the NP statement POUR. (N = 10, σ ≤ 2.5%)
Performance of Zerocash algorithms
In Figure 6 we report performance characteristics for each of the six DAP scheme algorithms in our implementation (singlethread on our desktop machine). For VerifyTransaction, we separately report the cost of verifying mint and pour transactions and, in the latter case, we exclude the cost of scanning L (e.g., to check if a serial number is duplicate);^{20} for the case of Receive, we report the cost to process a given pour transaction in L.
We obtain that:

 Setup takes about 5 minutes to run; its running time is dominated by the running time of KeyGen on C_{POUR}. (Either way, Setup is run only once.) The size of the resulting public parameters pp is dominated by the size of pkPOUR.
 CreateAddress takes 326.0 ms to run. The size of the resulting address key pair is just a few
hundred bytes.
20Naturally, if SNList has 2^{64} serial numbers (the maximum possible in our implementation), then scanning is very expensive! However, we do not expect that a system like Zerocash will grow to 2^{64} transactions. Still, such a system may grow to the point that scanning SNList is too expensive. We detail possible mitigations to this in Section 8.3.2.

 Mint takes 23 µs to run. It results in a coin of size 463 B and mint transaction of size 72 B.
 Pour takes about 2 minutes to run. Besides Setup, it is the only “expensive” algorithm to run; as expected, its running time is dominated by the running time of Prove. For a transaction string info, it results in (two new coins and) a pour transaction of size 996 B + info.
 VerifyTransaction takes 8.3 µs to verify a mint transaction and 5.7 ms to verify a pour transaction; the latter’s time is dominated by that of Verify, which checks the zkSNARK proof π_{POUR}.
 Receive takes 1.6 ms per pour transaction.
Note that the above numbers do not include the costs of maintaining the Merkle tree because doing so is not the responsibility of the DAP scheme algorithms. Nevertheless, these additional costs are not large: (i) each update of the root of the CRHbased Merkle tree only requires d_{tree} invocations of CRH, and (ii) an authentication path consists of only d_{tree} digests of CRH. In our implementation, where CRH = H (the SHA256 compression function) and d_{tree} = 64, each update requires 64 invocations of H and an authentication path requires 64 · 32 B = 2 KiB of storage.
Remark. If one does not want to rely on the ledger to communicate coins, via the ciphertexts C_{1}, C_{2}, and instead rely instead on some outofband mechanism (e.g., encrypted email), then the Receive algorithm is not needed, and moreover, many of the aforementioned sizes decrease because some pieces of data are not needed anymore; we denoted these pieces of data with “>” in Figure 6. (E.g., the size of an address key pair is reduced to only 64 B, and the size of a coin to only 120 B.)
Largescale network simulation
Because Bitcoin mining typically takes place on dedicated GPUs or ASICs, the CPU resources to execute the DAP scheme algorithms are often of minimal consequence to network performance. There is one potential exception to this rule: the VerifyTransaction algorithm must be run by all of the network nodes in the course of routine transaction validation. The time it takes to perform this verification may have significant impact on network performance.
In the Zerocash implementation (as in Bitcoin), every Zerocash transaction is verified at each hop as it is forwarded though the network and, potentially, again when blocks containing the transaction are verified. Verifying a block consists of checking the proof of work and validating the contained transactions. Thus Zerocash transactions may take longer to spread though the network and blocks containing Zerocash transactions may take longer to verify. While we are concerned with the first issue, the potential impact of the second issue is cause for greater concern. This is because Zerocash transactions cannot be spent until they make it onto the ledger.
Because blocks are also verified at each hop before they are forwarded through the network, delays in block verification slow down the propagation of new blocks through the network. This causes nodes to waste CPUcycles mining on outofdate blocks, reducing the computational power of the network and making it easier to mount a “51% attack” (dishonest majority of miners) on the distributed ledger.
It is a priori unclear whether this potential issue is a real concern. Bitcoin caches transaction verifications, so a transaction that was already verified when it propagated through the network need not be verified again when it is seen in a block. The unknown is what percentage of transactions in a block are actually in any given node’s cache. We thus conduct a simulation of the Bitcoin network to investigate both the time it takes Zerocash transactions to make it onto the ledger and establish the effects of Zerocash transactions on block verification and propagation. We find that Zerocash transactions can be spent reasonably quickly and that the effects of increased block validation time are minimal.
Figure 6: Performance of Zerocash algorithms. Above, we report the sizes of ppenc and ppsig as 0 B, because these parameters are “hardcoded” in the libraries we rely on for Enc and Sig. (N = 10 with σ ≤ 2.5% for all except that, due to variability at short timescales, σ(Mint) ≤ 3.3 µs and σ(VerifyTransaction) ≤ 1.9 µs)
Simulation design. Because Zerocash requires breaking changes to the Bitcoin protocol, we cannot test our protocol in the live Bitcoin network or even in the dedicated testnet. We must run our own private testnet. For efficiency and cost reasons, we would like to run as many Bitcoin nodes as possible on the least amount of hardware. This raises two issues. First, reducing the proof of work to practical levels while still preserving a realistic rate of new blocks is difficult (especially on
virtualized hardware with variable performance). Second, the overhead of zkSNARK verification prevents us from running many Bitcoin nodes on one virtualized server.
The frequency of new blocks can be modeled as a Poisson process with a mean of Λ_{block} seconds.^{21} To generate blocks stochastically, we modify bitcoind to fix its block difficulty at a trivial level ^{22} and run a Poisson process, on the simulation control server, which trivially mines a block on a randomly selected node. This preserves the distribution of blocks, without the computational overhead of a real proof of work. Another Poisson process triggering mechanism, with a different mean Λ_{tx}, introduces new transactions at random network nodes.
To differentiate which transactions represent normal Bitcoin expenditures versus which contain Zerocash pour transactions, simulated Zerocash transactions pay a unique amount of bitcoins (we set this value arbitrarily at 7 BTC). If a transaction’s output matches this preset value, and it is not in verification cache, then our modified Bitcoin client inserts a 10 ms delay simulating the runtime of VerifyTransaction.^{23} Otherwise transactions are processed as specified by the Bitcoin protocol. We vary the amount of simulated Zerocash traffic by varying the number of transactions with this particular output amount. This minimizes code changes and estimates only the generic impact of verification delays and not of any specific implementation choice.
Methodology. Recent research [DW13] suggests that the Bitcoin network contains 16,000 distinct nodes though most are likely no longer participating: approximately 3,500 are reachable at any given time. Each node has an average of 32 open connections to randomly selected peers. As of November 2013, the peak observed transaction rate for Bitcoin is slightly under one transaction per second [Lee13].
In our simulation, we use a 1000node network in which each node has an average of 32 peers, transactions are generated with a mean of Λ_{tx} = 1 s, a duration of 1 hour, and a variable percentage s of Zerocash traffic. To allow for faster experiments, instead of generating a block every 10 minutes as in Bitcoin, we create blocks at an average of every Λ_{block} = 150 s (as in Litecoin, a popular altcoin).
We run our simulation for different traffic mixes, where s indicates the percentage of Zerocash transactions and s ∈ {0%, 25%, 50%, 75%, 100%}. Each simulation is run on 200 Amazon EC2 generalpurpose m1.medium instances, in one region on a 10.10./16 private network. On each instance, we deploy 5 instances of bitcoind.^{24}
Results. Transactions are triggered by a blocking function call on the simulation control node that must connect to a random node and wait for it to complete sending a transaction. Because the Poisson process modeling transactions generates delays between such calls and not between the exact points when the node actuals sends the transactions, the actual transaction rate is skewed. In our experiments the real transaction rate shifts away from our target of one per second to an average of one every 1.4 seconds.
In Figure 7 we plot three metrics for s ∈ {0%, 25%, 50%, 75%, 100%}. Each is the average defined over the data from the entire run of the simulation for a given s (i.e., they include multiple transactions and blocks).^{25} Transaction latency is the interval between a transaction’s creation and
21Since computational power is added to the Bitcoin network faster than the 2week difficulty adjustment period, the frequency of block generation is actually skewed. As our experiments run for at most an hour, we ignore this.
22These code modifications have been rendered moot by the subsequent inclusion of a “regtest” mode in Bitcoin 0.9
that allows for precisely this type of behavior and block generation on command. At the time of our experiments, this feature was not available in a stable release. Future work should use this feature.
23We used a generous delay of 10 ms (higher than the time reported in Figure 6) to leave room for machines slower
24Higher densities of nodes per VM resulted in issues initializing all of the bitcoind instances on boot.
25Because our simulated Bitcoin nodes ran on shared EC2 instances, they were subject to variable external load,
its inclusion in a block. Block propagation time comes in two flavors: (1) the average time for a new block to reach a node computed over the times for all nodes, and (2) the same average computed over only the last node to see the block.
Block verification time is the average time, over all nodes, required to verify a block. If verification caching was not effective, we would expect to see a marked increase in both block verification time and propagation time. Since blocks occur on average every 150 s, and we expect approximately one transaction each second, we should see 150 × 10 ms = 1500 ms of delay if all transactions were noncached Zerocash transactions. Instead, we see worst case 80 ms and conclude caching is effective. This results in a negligible effect on block propagation (likely because network operations dominate). The time needed for a transaction to be confirmed, and hence spendable, is roughly 190 s. For slower block generation rates (e.g., Bitcoin’s block every 10 minutes) this should mean users must
wait only one block before spending received transactions.
Zerocash 
180
160
140
time in seconds
time in seconds
120
100
80
60
40
20
0
0% 20% 40% 60% 80% 100%
ε
(a) Transaction latency
4.5
4
last node
every node 
3.5
time in milliseconds
3
2.5
2
1.5
1
0.5
0
0% 20% 40% 60% 80% 100%
ε
 Block propagation time
80
70
Zerocash 
60
50
40
30
20
10
0
0% 20% 40% 60% 80% 100%
ε
 Block verification time
Figure 7: The average values of the three metrics we study, as a function of g, the percentage of transactions that are Zerocash transactions. Note that, in (a), latency is undefined when g = 0 and hence omitted.
Optimizations and extensions
We outline several optimizations and extensions to Zerocash: everlasting anonymity (Section 8.1), faster block propagation (Section 8.2), and improved storage requirements (Section 8.3).
Everlasting anonymity
Since transactions may persist virtually forever on the ledger, users may wish to ensure the anonymity of their transactions also lasts forever, even if particular primitives are eventually broken (by cryptanalytic breakthrough, engineering progress, or quantum computers). As we now explain, the DAP scheme construction described in Section 4 is only computationally private, but can be modified to achieve everlasting anonymity.
Recall that every Pour operation publishes a pour transaction tx_{Pour} = (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new},
1 2 1 2
v_{pub}, info, ∗), where ∗ = (pksig, h_{1}, h_{2}, π_{POUR}, C_{1}, C_{2}, σ) and C_{i} = E_{enc}(pk^{new} , (v^{new}, ρ^{new}, r^{new}, s^{new})).
Observe that:
enc,i i
i i i
limiting the benchmark precision. Still, it clearly demonstrates that the mild additional delay does not cause catastrophic network effects.

 Since h_{Sig} = CRH(pksig) and h_{i} = PRF old (h_{Sig}), an unbounded adversary A can iterate over all x
pk
ask,i
until PRF^{pk}(h_{Sig}) equals h_{i}; with overwhelming probability, there is only one such x, in which
x
case it equals a^{old} . Thus, A learns a^{old} , and hence a^{old}
a
sk,i
sk,i
pk,i
old sk,i
:= PRF^{addr}(0). This identifies the sender.

 An unbounded A can also decrypt C_{i}, so to learn (v^{new}, ρ^{new}, r^{new}, s^{new}); then, A can try all
i
i
i
i
possible x until COMM_{s}new (v^{new}“COMM_{r}new (PRF^{addr}(0)”ρ^{new})) equals cm^{new}; with overwhelming
i
i
i
x
i
i
probability, there is only one such x, in which case it equals a^{new}. This identifies the recipient.
sk,i
The above attacks can be prevented as follows. First, every sender must use any given address only once (for receiving or sending coins): after receiving a coin c, a user u should immediately generate a new address and pour c into a fresh one c^{j} relative to the new address; only afterwards can u spend the coin. Second, a user should not put any data in a ciphertext C_{i} to communicate a coin’s information, but must instead use some (informationallysecure) outofband channel to do so. With these modifications (and recalling that COMM is statistically hiding and π_{POUR} is a perfectzeroknowledge proof), one can verify that the pour transaction tx_{Pour} is statistically hiding, i.e., leaks no information even to unbounded adversaries.^{26}
Fast block propagation
As mentioned in Section 7.3, the higher blockverification time of Zerocash compared to, e.g., Bitcoin does not affect much block propagation. Even so, we note a simple modification that further mitigates concerns. Upon receiving a block, a node validates the proof of work and (optionally) transactions other than mint and pour, and then forward the block right away. Only afterwards, the node executes VerifyTransaction on any mint/pour transactions, before accepting it for use in transacting. Thus, blocks are still validated by every node (so the security properties are unhampered), and propagation delays in the broadcast of blocks are reduced.
In principle, this opens the possibility of a denialofservice attack, in which the network is spammed with invalid blocks which pass the proofofwork check but contain invalid mint or pour transactions. However, this attack appears unrealistic given the enormous (by design) cost of creating blocks passing the proofofwork check.
Improved storage requirements
Beyond the ledger L, users need to maintain two lists: CMList, the list of all coin commitments, and SNList, the list of all serial numbers of spent coins (see Section 3.1). In our construction, CMList is required to deduce authentication paths to create new pour transactions (via Pour), while SNList is used to verify pour transactions (via VerifyTransaction). As the ledger grows, both CMList and SNList grow in size, and can eventually impose substantial storage requirements (though both are derived from, and smaller than, the block chain per se). We now explain how these storage requirements can be mitigated, by relying on smaller representations of CMList and SNList that suffice within our construction.
Supporting many coin commitments
To execute the Pour algorithm to spend a coin c, a user u needs to provide an authentication path from c’s coin commitment to rt, the Merkletree root over CMList. If we make the following protocol modifications, u does not need all of CMList to compute this authentication path.
26As for mint transactions, one can verify that they are already statistically hiding, without any modifications.
In each block B of transactions, we store the Merkletree path pathB from the first coin commitment in B to the root rt_{B} of the Merkle tree over CMList when the last block in the ledger is B. (In Zerocash, the additional perblock storage cost to store this information is only 2 KiB.)
Note that, given a block B and its successor block B^{j}, the corresponding authentication paths pathB and pathBj can be easily checked for consistency as follows. Let CMList_{B} and CMList_{B}j be the two lists of coin commitments corresponding to the two ledgers ending in block B and B^{j} respectively; since CMList_{B} (i.e., coin commitments to “to the left” of pathB ) is a prefix of CMList_{B}j , pathBj can be computed from pathB and B in time O(Bd_{tree}), where d_{tree} is the tree depth.
When the user u first receives (or mints) the coin c, and its coin commitment is included in a
block B, u immediately computes pathB , by using the predecessor block and its authentication path. Afterwards, each time a new block is added to the ledger, u obtains a new path for c by using the new block and the old path for c. Thus, u only needs to act each time a new block is added, and each such update costs O(d_{tree}) per transaction in the block.
Overall, u incurs a storage requirement of only O(d_{tree}) for each coin he owns, and does not need to store CMList anymore.
Supporting many spent serial numbers
To execute the VerifyTransaction algorithm on a pour transaction tx_{Pour}, a user u needs access to SNList (in order to check for duplicate serial numbers). Note, in Bitcoin, nodes need to maintain only the list of unspent transaction outputs, which is pruned as outputs are spent. In a DAP scheme, in contrast, nodes have to maintain SNList, which is a list that always grows. We now explain how to mitigate this storage requirement, in three incremental steps.
Step 1. The first step is to build a Merkle tree over SNList so to allow easytoverify nonmembership proofs for SNList; this can be done by letting the leaves of the Merkle tree be the intervals of unspent serial numbers. Then, given the root rt of such tree, a serial number sn claimed to be unspent, and an authentication path path for an interval I, the user can check that path is valid for rt and that sn lies in I; the root rt and path path would be part of the pour transaction tx_{Pour} to be verified. The problem with this approach, however, is that generating path (and also updating rt) requires knowledge of all of SNList.
Step 2. Next, instead of maintaining SNList in a single Merkle tree, we divide SNList, maintaining its chronological order, into sublists of serial numbers SNList_{0}, SNList_{1}, . . . and build a Merkle tree over the intervals induced by each sublist (i.e., apply Step 1 to each sublist). This modification implies a corresponding modification for the auxiliary information stored in a pour transaction that allows VerifyTransaction to check it. Now, however, producing such auxiliary information is less expensive. Indeed, a user with a coin c should maintain a list of authentication paths pathc,0, pathc,1, . . . (one for each sublist). Only the last path, corresponding to the active sublist, needs to be updated when a serial number is added; the other sublists and authentication paths remain unchanged (and these old sublists can in fact be discarded). When the user spends the coin, he can simply include these paths in the pour transaction. While updating these paths is an efficient operation, computing the initial paths for c is not, as it still requires the full set of sublists.
Step 3. To enable users to avoid the initial cost of computing paths for a new coin, we proceed as follows. First, a coin c is extended to contain a time stamp T_{c} corresponding to when c is created (minted or poured into); the coin’s commitment is modified to depend on the timestamp, and the timestamp is included in the clear within the transaction that creates the coin. Then, a user, upon spending c, produces a zkSNARK for the following NP statement: “for each Merkletree root created (or updated) after T_{c} there is an interval and an authentication path for that interval
such that the serial number of c is in that interval”. Depending on the number of Merkle trees in such an NP statement, such proofs may already be more efficient to produce, compared to the naive (Step 1) solution, using existing zkSNARK implementations.
Concurrent work
Danezis et al. [DFKP13] suggest using zkSNARKs to reduce proof size and verification time in Zerocoin. Our work differs from [DFKP13] in both supported functionality and scalability.
First, [DFKP13]’s protocol, like Zerocoin, only supports fixedvalue coins, and is best viewed as a decentralized mix. Instead, we define, construct, and implement a fullfledged decentralized electronic currency, which provides anonymous payments of any amount.
Second, in [DFKP13], the complexity of the zkSNARK generator, prover, and verifier all scale superlinearly in the number of coins, because their arithmetic circuit computes, explicitly, a product over all coins. In particular, the number of coins “mixed together” for anonymity cannot be large. Instead, in our construction, the respective complexities are polylogarithmic, polylogarithmic, and constant in the number of coins; our approach supports a practicallyunbounded number of coins. While we do not rely on Pedersen commitments, our approach also yields statistical (i.e.,
everlasting) anonymity; see the discussion in Section 8.1.
Conclusion
Decentralized currencies should ensure a user’s privacy from his peers when conducting legitimate financial transactions. Zerocash provides such privacy protection, by hiding user identities, trans action amounts, and account balances from public view. This, however, may be criticized for hampering accountability, regulation, and oversight. Yet Zerocash need not be limited to enforcing the basic monetary invariants of a currency system. The underlying zkSNARK cryptographic proof machinery is flexible enough to support a wide range of policies. It can, for example, let a user prove that he paid his due taxes on all transactions without revealing those transactions, their amounts, or even the amount of taxes paid. As long as the policy can be specified by efficient nondeterministic computation using NP statements, it can (in principle) be enforced using zkSNARKs, and added to Zerocash. This can enable automated, privacypreserving verification and enforcement of a wide range of compliance and regulatory policies that would otherwise be invasive to check directly or might be bypassed by corrupt authorities. This raises research, policy, and engineering questions regarding which such policies are desirable and practically realizable.
Another research question is what new functionality can be realized by augmenting the capabilities already present in Bitcoin’s scripting language with zkSNARKs that allow fast verification of expressive statements.
Acknowledgments
We thank Amazon for their assistance and kind donation of EC2 resources, and Gregory Maxwell for his advice regarding the Bitcoin codebase. We thank Iddo BenTov and the SCIPR Lab members
— Daniel Genkin, Lior Greenblatt, Shaul Kfir, Gil Timnat, and Michael Riabzev — for inspiring discussions. We thank Sharon Kessler for editorial advice.
This work was supported by: Amazon.com through an AWS in Education research grant; the Broadcom Foundation and Tel Aviv University Authentication Initiative; the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF0939370; the Check Point Institute for Information Security; the U.S. Defense Advanced Research Projects Agency (DARPA) and the Air Force Research Laboratory (AFRL) under contract FA87501120211; the European Community’s Seventh Framework Programme (FP7/20072013) under grant agreement number 240258; the Israeli Centers of Research Excellence ICORE program (center 4/11); the Israeli Ministry of Science and Technology; the Office of Naval Research under contract N000141110470; the Simons Foundation, with a Simons Award for Graduate Students in Theoretical Computer Science; and the Skolkovo Foundation with agreement dated 10/26/2011.
The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense or the U.S. Government.
Overview of Bitcoin and Zerocoin
We provide an overview of the Bitcoin and Zerocoin protocols. For more details, we refer the reader to Nakamoto [Nak09] and Miers et al. [MGGR13] respectively.
Bitcoin
Bitcoin [Nak09] is a decentralized currency operated by a collection of mutuallydistrusting peers. It consists of three basic components: (i) a peertopeer network for broadcasting new transactions;
 semantics for identifying and validating new transactions; and (iii) a protocol for maintaining a decentralized ledger, known as the block chain, that stores the history of all valid transactions so far. Identities in Bitcoin are represented via ECDSA public keys. Each user u generates an ECDSA key pair (vk_{u}, sk_{u}) and, to receive payments, publishes the verification key vk_{u} (or its hash) as an address. (In fact, there is no limit to the number of addresses that an individual user may possess.)
Transactions. A transaction tx represents a payment from a list of input transactions to a list of output recipients. More precisely, tx is specified by a list {I_{j}}_{j} of inputs and a list {O_{j}}_{j} of outputs. Each output O_{j} specifies a value v_{j}, denominated in Satoshi (10 Satoshi amounts to 1 bitcoin), and a recipient specification r_{j}, called ScriptPubKey. The specification r_{j} is given in Bitcoin script, a stackbased nonTuringcomplete language similar to Forth, and specifies the identity of the recipient of the v_{j} Satoshi. Each input I_{j} references an output of a previous transaction tx_{j}: the reference is specified by a tuple (h_{j}, k_{j}, σ_{j}), where h_{j} is the hash of tx_{j}, k_{j} is an index specifying which output of tx_{j} is referenced, and σ_{j}, called ScriptSig, is a an input satisfying the ScriptPubKey of the k_{j}th output of tx_{j}. Typically, the ScriptPubKey specifies a public key that must sign the transaction spending the output and σ_{j} contains such a signature, hence their names. Inputs can only be claimed by one transaction to prevent double spending.
Σ
9
The total number of bitcoins output by a transaction, j v_{j}, cannot exceed the total value of the referenced outputs. Any difference between these two quantities is claimed as a transaction fee (see below). Thus, any unspent inputs to a transaction become a fee, and transactions typically
have at least two outputs: one to the payment’s recipient and one back to the sender as “change”.
The block chain. Transactions are broadcast in the Bitcoin peertopeer network, but are considered valid only once they have been added to the the block chain. To assemble the block chain, miners (usually but not necessarily, network nodes) collect transactions from the Bitcoin network and bundle them into blocks. Miners then compete for the opportunity to append their own candidate block B to the block chain by searching for a string s such that the integer specified by SHA256(SHA256(B“s)) is below some threshold. To incentivize block creation, miners receive a protocolspecified reward (currently 25 BTC) for adding a new block and, moreover, receive pertransaction fees (whose value is specified by the transaction’s creator).
The proof of work protects a block against tampering and also ensures that meaningful compu tational resources were devoted to finding it. This prevents a sybil attack since all the sybils share the same total computational resources (e.g., the server they are virtualized on). Bitcoin assumes that provided more than half the computational work is held by honest nodes, the blockchain is secure. (Though recent work [ES13] has suggested that the threshold may be larger than 50%.)
Zerocoin
Zerocoin extends Bitcoin by creating two new transaction types: mint and spend. A mint transaction allows a user to exchange a quantity of bitcoins for the right to mint a new zerocoin. Each zerocoin consists of a digital commitment cm to a random serial number sn. At a later point, a (potentially
different) user may issue a spend transaction containing a destination identity, the serial number sn, and a noninteractive zeroknowledge proof for the NP statement “I know secret cm and r such that (i) cm can be opened to sn with commitment randomness r, and (ii) cm was previously minted at some point in the past”. Crucially, the proof, being zero knowledge, does not link the spend transaction to any particular mint transaction (among all mint transactions so far). If the proof verifies correctly and the serial number has not been spent previously, the protocol semantics transfer a corresponding amount of bitcoins to the destination address. In this fashion, Zerocoin functions as a decentralized mix.
Zerocoin uses Pedersen commitments over a prime field F_{p}, i.e., cm := g^{sn}h^{r}, for random generators g, h of a subgroup of F∗p. The corresponding zeroknowledge proofs are constructed by first accumulating (via the StrongRSA accumulator of [CL01]) the set of commitments of all
minted zerocoins, and then proving knowledge of the corresponding commitment randomness and membership in this set. For technical reasons, the proof requires a doublediscretelogarithm (DDL) Fiat–Shamir proof of size ≈ pλ, where λ is the security parameter. In practice, the size of these proofs exceeds 45 kB at the 128bit security level, and require 450 ms or more to verify.
Also note that, in Zerocoin, computing the witness for the accumulator requires access to the entire set of commitments so far (though the witness can be incrementally updated for each insertion). This technique supports an unlimited number of coins. In contrast, our construction places a cap N on the number of coins (in our implementation, N = 2^{64}) but needs only log N updates to issue N new coins (and these updates can be efficiently batched, cf. Section 8.3.1).
Completeness of DAP schemes
A DAP scheme Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) is complete if no polynomialsize ledger sampler S can win the incompleteness experiment with more than negligible probability. In Section 3.4 we informally described this property; we now formally define it.
Deftnition B.1. Let Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) be a (candi date) DAP scheme. We say that Π is complete if, for every poly(λ)size ledger sampler S and sufficiently large λ,
Adv^{INCOMP}(λ) < negl(λ) ,
Π,S
where Adv^{INCOMP}(λ) := Pr[INCOMP(Π, S, λ) = 1] is S’s advantage in the incompleteness experiment.
Π,S
We now describe the incompleteness experiment mentioned above. Given a (candidate) DAP scheme Π, a ledger sampler S, and a security parameter λ, the (probabilistic) experiment INCOMP(Π, S, λ) consists of an interaction between S and a challenger C, terminating with a binary output by C.
At the beginning of the experiment, C samples pp ← Setup(1^{λ}) and sends pp to S. Then, S
sends a ledger, two coins to be spent, and parameters for a pour transaction; more precisely, sends (1) a ledger L; (2) two coins c^{old}, c^{old}; (3) two address secret keys addr^{old} , addr^{old} ; (4) two
C S
1 2 sk,1 sk,2
values v^{new}, v^{new}; (5) new address key pairs (addr^{new} , addr^{new}), (addr^{new} , addr^{new}); (6) a public value
1 2 pk,1
sk,1
pk,2
sk,2
v_{pub}; and (7) a transaction string info. Afterwards, C performs various checks on S’s message.
Concretely, C first checks that c^{old} and c^{old} are valid unspent coins, i.e., checks that: (i) c^{old}
1
2
1
and c^{old} are wellformed; (ii) their coin commitments cm^{old} and cm^{old} appear in (valid) transactions
2 1 2
on L; (iii) their serial numbers sn^{old} and sn^{old} do not appear in (valid) transactions on L. Next, C
1
2
checks that v^{new} + v^{new} + v_{pub} = v^{old} + v^{old} (i.e., the values suggested by S preserve balance) and
1
2
1
2
v^{old} + v^{old} ≤ v_{max} (i.e., the maximum value is not exceeded). If any of these checks fail, C aborts
1
2
and outputs 0.
Otherwise, C computes rt, the Merkletree root over all coin commitments in L (appearing in valid transactions), and, for i ∈ {1, 2, }, pathi, the authentication path from commitment cm^{old} to
i
the root rt. Then, C attempts to spend c^{old}, c^{old} as instructed by S:
1
2
(c^{new}, c^{new}, tx_{Pour}) ← Pour(pp, rt, c^{old}, c^{old}, addr^{old} , addr^{old} , path1, path2, v^{new}, v^{new}, addr^{new} , addr^{new} , v_{pub}, info) .
1
2
1
2
sk,1
sk,2
1
2
pk,1
pk,2
Finally, C outputs 1 if and only if any of the following conditions hold:

 tx_{Pour} =ƒ (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, info, ∗), where cm^{new}, cm^{new} are the coin commitments
1 2 1 2 1 2
of c^{new}, c^{new}; OR
1 2

 tx_{Pour} is not valid, i.e., VerifyTransaction(pp, tx_{Pour}, L) outputs 0; OR
 for some i ∈ {1, 2}, the coin c^{new} is not returned by Receive(pp, (addr^{new}, addr^{new}), L^{j}), where L^{j}
i
is the ledger obtained by appending tx_{Pour} to L.
pk,i
sk,i
Remark. There is no need for the challenger C check that, in turn, both c^{new} and c^{new} are spendable,
1
2
because this follows by induction. Namely, if c^{new}, c^{new} were not spendable, a different sampler Sj
1
2
(that simulates S and then computes and outputs c^{new} and c^{new}) would provide a counterexample
1 2
to the above definition.
Security of DAP schemes
A DAP scheme Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) is secure if it satis fies ledger indistinguishability, transaction nonmalleability, and balance. (See Definition 3.2.) In Section 3.4 we informally described these three properties; we now formally define them.
Each of the definitions employs an experiment involving a (stateful) DAP oracle ODAP that
receives and answers queries from an adversary A (proxied via a challenger C, which performs the experimentspecific sanity checks). Below, we first describe how ODAP works.
The oracle ODAP is initialized by a list of public parameters pp and maintains state. Internally, ODAP stores: (i) L, a ledger; (ii) ADDR, a set of address key pairs; (iii) COIN, a set of coins. All of L, ADDR, COIN start out empty. The oracle ODAP accepts different types of queries, and each query causes different updates to L, ADDR, COIN and outputs. We now describe each type of query Q.

 Q = (CreateAddress)
1.Compute ( addr_{pk}, addr_{sk}) := CreateAddress(pp). 2.Add the address key pair ( addr_{pk}, addr_{sk}) to ADDR. 3.Output the address public key addr_{pk}.
The ledger L and coin set COIN remain unchanged.

 Q = (Mint, v, addr_{pk})
1.Compute ( c, tx_{Mint}) := Mint(pp, v, addr_{pk}). 2.Add the coin c to COIN.
3.Add the mint transaction tx_{Mint} to L. 4.Output ⊥.
The address set ADDR remains unchanged.

 Q = (Pour, idx^{old}, idx^{old}, addr^{old} , addr^{old} , info, v^{new}, v^{new}, addr^{new} , addr^{new} , v_{pub})
1
2
pk,1
pk,2
1
2
pk,1
pk,2
 Compute rt, the root of a Merkle tree over all coin commitments in L. 2.For each i 1, 2 :
∈ { }

 Let cm^{old} be the idx^{old}th coin commitment in L.
i i

 Let tx_{i} be the mint/pour transaction in L that contains cm^{old}. (c)Let c^{old} be the first coin in COIN with coin commitment cm^{old}.
i
i i
 Let ( addr^{old} , addr^{old} ) be the first key pair in ADDR with addr^{old} being c^{old}’s address.
pk,i
sk,i
pk,i i
 Compute pathi, the authentication path from cm^{old} to rt.
i
 Compute (c^{new}, c^{new}, tx_{Pour}) := Pour(pp, rt, c^{old}, c^{old}, addr^{old} , addr^{old} , path1, path2, v^{new}, v^{new},
1 2 1 2
sk,1
sk,2 1 2
addr^{new} , addr^{new} , v_{pub}, info).
pk,1 pk,2
 Verify that VerifyTransaction(pp, tx_{Pour}, L) outputs 1.
 Add the coin c^{new} to COIN. 6.Add the coin c^{new} to COIN.
1
2
7.Add the pour transaction tx_{Pour} to L. 8.Output ⊥.
If any of the above operations fail, the output is ⊥ (and L, ADDR, COIN remain unchanged).

 Q = (Receive, addr_{pk})
1.Look up ( addr_{pk}, addr_{sk}) in ADDR. (If no such key pair is found, abort.) 2.Compute ( c_{1}, . . . , c_{n}) ← Receive(pp, (addr_{pk}, addr_{sk}), L).
 Add c_{1}, . . . , c_{n} to COIN.
 Output ( cm_{1}, . . . , cm_{n}), the corresponding coin commitments. The ledger L and address set ADDR remain unchanged.
 Q = (Insert, tx)
1.Verify that VerifyTransaction(pp, tx, L) outputs 1. (Else, abort.) 2.Add the mint/pour transaction tx to L.
 Run Receive for all addresses addr_{pk} in ADDR; this updates the COIN with any coins that might have been sent to honest parties via tx.
 Output ⊥.
The address set ADDR remains unchanged.
Remark. The oracle ODAP provides A with two ways to cause a pour transaction to be added to L. If A has already obtained address public keys addr_{pk}_{,}_{1} and addr_{pk}_{,}_{2} (via previous CreateAddress queries), then A can use a Pour query to elicit a pour transaction tx_{Pour} (despite not knowing address secret keys addr_{sk}_{,}_{1}, addr_{sk}_{,}_{2} corresponding to addr_{pk}_{,}_{1}, addr_{pk}_{,}_{2}). Alternatively, if A has himself generated both address public keys, then A knows corresponding address secret keys, and can invoke Pour “in his head” to obtain a pour transaction tx_{Pour}, which he can add to L by using an Insert query. In the first case, both addresses belong to honest users; in the second, both to A. But what about pour transactions where one address belongs to an honest user and one to A?
Such pour transactions might arise from MPC computations (e.g., to make matching donations). The ledger oracle ODAP, as defined above, does not support such queries. While extending the definition is straightforward, for simplicity we leave handling such queries to future work.
Ledger indistinguishability
Ledger indistinguishability is characterized by an experiment LIND, which involves a polynomialsize adversary A attempting to break a given (candidate) DAP scheme.
Deftnition C.1. Let Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) be a (candi date) DAP scheme. We say that Π is LIND secure if, for every poly(λ)size adversary A and sufficiently large λ,
Adv^{LIND}(λ) < negl(λ) ,
Π,A
where Adv^{LIND}(λ) := 2 · Pr[LIND(Π, A, λ) = 1] − 1 is A’s advantage in the LIND experiment.
Π,A
We now describe the LIND experiment mentioned above. Given a (candidate) DAP scheme Π, adversary A, and security parameter λ, the (probabilistic) experiment LIND(Π, A, λ) consists of an interaction between A and a challenger C, terminating with a binary output by C.
At the beginning of the experiment, C samples b ∈ {0, 1} at random, samples pp ← Setup(1^{λ}),
and sends pp to A; next, C initializes (using pp) two separate DAP oracles ODAP and ODAP (i.e.,
0 1
the two oracles have separate ledgers and internal tables).
The experiment proceeds in steps and, at each step, C provides to A two ledgers (L_{Left}, L_{Right}), where L_{Left} := L_{b} is the current ledger in ODAP and L_{Right} := L_{1−}_{b} the one in ODAP; then A sends
j b 1−b
to C a pair of queries (Q, Q ), which must be of the same type (i.e., one of CreateAddress, Mint,
Pour, Receive, Insert). The challenger C acts differently depending on the query type, as follows.

 If the query type is Insert, C forwards Q to ODAP, and Q^{j} to ODAP. This allows A to insert his
b
own transactions directly in L_{Left} and L_{Right}.
1−b

 For any other query type, C first ensures that Q, Q^{j} are publicly consistent (see below) and then forwards Q to ODAP, and Q^{j} to ODAP; letting (a_{0}, a_{1}) be the two oracle answers, C replies to A
0
1
with (a_{b}, a_{1−}_{b}). This allows A to elicit behavior from honest users. However note that A does not know the bit b, and hence the mapping between (L_{Left}, L_{Right}) and (L_{0}, L_{1}); in other words, A does not know if he elicits behavior on (L_{0}, L_{1}) or on (L_{1}, L_{0}).
At the end of the experiment, A sends C a guess b^{j} ∈ {0, 1}. If b = b^{j}, C outputs 1; else, C outputs 0.
Public consistency. As mentioned above, A sends C pairs of queries (Q, Q^{j}), which must be of the same type and publicly consistent, a property that we now define. If Q, Q are both of type CreateAddress or Receive, then they are always publicly consistent. In the special case of CreateAddress we require that both oracles generate the same address. If they are both of type Mint, then the minted value in Q must equal that in Q^{j}. Finally, if they are both of type Pour, the following restrictions apply.
j
First, Q, Q^{j} must be individually wellformed; namely, (i) the coin commitments referenced by
Q (via the two indices idx^{old}, idx^{old}) must correspond to coins c^{old}, c^{old} that appear in the ledger
1 2 1 2
oracle’s coin table COIN; (ii) the two coins c^{old}, c^{old} must be unspent (i.e. their serial numbers must
1 2
not appear in a valid pour transactions on the corresponding oracle’s ledger); (iii) the address public
keys specified in Q must match those in c^{old}, c^{old}; and (iv) the balance equation must hold (i.e.,
1 2
vnew + vnew + vpub = vold + vold).
1 2 1 2
Furthermore, Q, Q^{j} must be jointly consistent with respect to public information and ’s view; namely: (i) the public values in Q and Q^{j} must equal; (ii) the transaction strings in Q and Q^{j} must equal; (iii) for each i ∈ {1, 2}, if the ith recipient addresses in Q is not in ADDR (i.e., belongs to A) then v^{new} in both Q and Q^{j} must equal (and vice versa for Q^{j}); and (iv) for each i ∈ {1, 2}, if the ith index in Q references (in L_{0}) a coin commitment contained in a transaction that was posted via an Insert query, then the corresponding index in Q^{j} must reference (in L_{1}) a coin commitment that also appears in a transaction posted via an Insert query and, moreover, v^{old} in both Q and Q^{j} must equal (and vice versa for Q^{j}). The challenger C learns v^{old} by lookingup the corresponding coin c^{old}
A
i
i
i
i
in the oracle’s coin set COIN. (v) for each i ∈ {1, 2} if the ith index in Q must not reference a coin that has previously been spent.
Transaction nonmalleability
Transaction nonmalleability is characterized by an experiment TRNM, which involves a polynomial size adversary A attempting to break a given (candidate) DAP scheme.
Deftnition C.2. Let Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) be a (candi date) DAP scheme. We say that Π is TRNM secure if, for every poly(λ)size adversary A and sufficiently large λ,
Adv^{TRNM}(λ) < negl(λ) ,
Π,A
where Adv^{TRNM}(λ) := Pr[TRNM(Π, A, λ) = 1] is A’s advantage in the TRNM experiment.
Π,A
We now describe the TRNM experiment mentioned above. Given a (candidate) DAP scheme Π, adversary A, and security parameter λ, the (probabilistic) experiment TRNM(Π, A, λ) consists of an interaction between A and a challenger C, terminating with a binary output by C.
At the beginning of the experiment, C samples pp ← Setup(1^{λ}) and sends pp to A; next, C initializes a DAP oracle ODAP with pp and allows A to issue queries to ODAP. At the end of the experiment, A sends C a pour transaction tx^{∗}, and C outputs 1 if and only if the following conditions hold. Letting T be the set of pour transactions generated by ODAP in response to Pour queries,
there exists tx ∈ T such that: (i) tx^{∗} = tx; (ii) VerifyTransaction(pp, tx^{∗}, L^{j}) = 1, where L^{j} is the
portion of the ledger preceding tx;^{27} and (iii) a serial number revealed in tx^{∗} is also revealed in tx.
Balance
Balance is characterized by an experiment BAL, which involves a polynomialsize adversary A
attempting to break a given (candidate) DAP scheme.
Deftnition C.3. Let Π = (Setup, CreateAddress, Mint, Pour, VerifyTransaction, Receive) be a (can didate) DAP scheme. We say that Π is BAL secure if, for every poly(λ)size adversary A and sufficiently large λ,
Adv^{BAL}(λ) < negl(λ) ,
Π,A
where Adv^{BAL}(λ) := Pr[BAL(Π, A, λ) = 1] is A’s advantage in the BAL experiment.
Π,A
We now describe the BAL experiment mentioned above. Given a (candidate) DAP scheme Π, adversary A, and security parameter λ, the (probabilistic) experiment BAL(Π, A, λ) consists of an interaction between A and a challenger C, terminating with a binary output by C.
At the beginning of the experiment, C samples pp ← Setup(1^{λ}), and sends pp to A; next, C (using pp) initializes a DAP oracle ODAP and allows A to issue queries to ODAP. At the conclusion of the experiment, A sends C a set of coins S_{coin}. Recalling that ADDR is the set of addresses returned by CreateAddress queries (i.e., addresses of “honest” users), C computes the following five quantities.

 v_{Unspent}, the total value of all spendable coins in S_{coin}. The challenger C can check if a coin c S_{coin} is spendable as follows: mint a fresh coin c of value 0 (via a Mint query) and check if a corresponding Pour query consuming c, c^{j} yields a pour transaction tx_{Pour} that is valid.
∈
j

 v_{Mint}, the total value of all coins minted by A. To compute v_{Mint}, the challenger C sums up the values of all coins that (i) were minted via Mint queries using addresses not in ADDR, or
 whose mint transactions were directly placed on the ledger via Insert queries.
 v_{ADDR→A}, the total value payments received by A from addresses in ADDR. To compute v_{ADDR→A}, the challenger C looks up all pour transactions placed on the ledger via Pour queries and sums up the values that were transferred to addresses not in ADDR.
27That is, L^{j} is the longest ledger prefix that can be used to spend at least one of the coins spent in tx.

 v_{A→ADDR}, the total value of payments sent by A to addresses in ADDR. To compute v_{A→ADDR}, the challenger C first deduces the set S^{j} ⊆ COIN of all coins received by honest parties and then sums up the values of coins in S^{j}. (Note that C can compute S^{j} by selecting all coins in COIN that are both tied to an address in ADDR and arose from transactions placed on the ledger by Insert queries.)
 v_{Basecoin}, the total value of public outputs placed by A on the ledger. To compute v_{Basecoin}, the challenger C looks up all pour transactions placed on the ledger by Insert and sums up the corresponding v_{pub} values.
At the end of the experiment, C outputs 1 if v_{Unspent} + v_{Basecoin} + v_{A→ADDR} > v_{Mint} + v_{ADDR→A}; else,
C outputs 0.
Remark. There are two methods for A to spend more publicoutput money than he owns: (i) by directly inserting transactions on the ledger, and (ii) by asking honest parties to create such transactions. The first method is accounted for in the computation of v_{Basecoin}, while the second method is accounted for in the computation of v_{A→ADDR} (since A must first pay the honest party).
Proof of Theorem 4.1
We prove Theorem 4.1. We omit a formal proof of the completeness claim; one can verify that the DAP scheme’s completeness follows, in a straightforward way, from the completeness of the construction’s building blocks. Next, we argue security via three separate proofs, respectively showing that our construction satisfies (i) ledger indistinguishability, (ii) transaction nonmalleability, and

 balance.
Proof of ledger indistinguishability
We describe a simulation 3_{sim} in which the adversary A interacts with a challenger C, as in the LIND experiment. However 3_{sim} differs from the LIND experiment in a critical way: all answers sent to A are computed independently of the bit b, so that A’s advantage in 3_{sim} is 0. The remainder of the proof is devoted to showing that Adv^{LIND}(λ) (i.e., A’s advantage in the LIND experiment) is at most negligibly different than A’s advantage in 3_{sim}.
Π,A
The simulation. The simulation 3_{sim} works as follows. First, after sampling b ∈ {0, 1} at random, C samples pp ← Setup(1^{λ}), with the following modification: the zkSNARK keys are generated as (pkPOUR, vk_{POUR}, trap) ← Sim(1^{λ}, C_{POUR}), to obtain the zeroknowledge trapdoor trap. Then, as in the LIND experiment, C sends pp to A, and then initializes two separate DAP oracles ODAP and ODAP.
0
1
Afterwards, as in LIND, 3_{sim} proceeds in steps and, at each step, C provides to A two ledgers (L_{Left}, L_{Right}), where L_{Left} := L_{b} is the current ledger in ODAP and L_{Right} := L_{1−}_{b} the one in ODAP;
j b 1−b
then A sends to C a message (Q, Q ), which consist of two (publiclyconsistent) queries of the same
type. The challenger C acts differently depending on the query type, as follows.

 Answering CreateAddress queries. In this case, Q = Q^{j} = CreateAddress.
To answer Q, C behaves as in LIND, except for the following modification: after obtaining (addr_{pk}, addr_{sk}) ← CreateAddress(pp), C replaces a_{pk} in addr_{pk} with a random string of the appro priate length; then, C stores addr_{sk} in a table and returns addr_{pk} to A.
Afterwards, C does the same for Q^{j}.

 Answering Mint queries. In this case, Q = (Mint, v, addr_{pk}) and Q^{j} = (Mint, v, addr^{j}pk).
To answer Q, C behaves as in LIND, except for the following modification: the Mint algorithm computes the commitment k as COMM_{r}(τ “ρ), for a random string τ of the appropriate length, instead of as COMM_{r}(a_{pk}“ρ), where a_{pk} is the value specified in addr_{pk}.
Afterwards, C does the same for Q^{j}.

 Answering Pour queries. In this case, Q and Q^{j} both have the form (Pour, cm^{old}, cm^{old}, addr^{old} ,
addr^{old} , info, v^{new}, v^{new}, addr^{new} , addr^{new} , v^{new}).
1 2 pk,1
pk,2 1 2
pk,1
pk,2
pub
To answer Q, C modifies the way some values are computed:


 Compute rt_{i} by accumulating all of the valid coin commitments on L_{i}. 2.Set v_{pub} and info to the corresponding input values.

 For each j 1, 2 :
∈ { }

 Sample a uniformly random sn^{old}.
j

 If addr^{new}
pk,j
is an address generated by a previous query to CreateAddress, (i) sample
a coin commitment cm^{new} on a random input, (ii) run K_{enc}(ppenc) → (pkenc, sk_{enc}) and compute C^{new} := E_{enc}(pkenc, r) for a random r of suitable length.
j
j

 Otherwise, calculate ( cm^{new}, C^{new}) as in the Pour algorithm.^{28}
i i
 Set h_{1} and h_{2} to be random strings of the appropriate length.
 Compute all remaining values as in the Pour algorithm
 The pour proof is computed as π_{POUR} := Sim(trap, x), where x := (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, h_{1}, h_{2}).
Afterwards, C does the same for Q^{j}.
1 2 1 2

 Answering Receive queries. In this case, Q = (Receive, addr_{pk}) and Q^{j} = (Receive, addr^{j}pk). The answer to each query proceeds as in the LIND experiment.
 Answering Insert queries. In this case, Q = (Insert, tx) and Q = (Insert, tx^{j}). The answer to each query proceeds as in the LIND experiment.
In each of the above cases, the response to A is computed independently of the bit b. Thus, when
A outputs a guess b^{j}, it must be the case that Pr [ b = b^{j} ] = 1/2, i.e., A’s advantage in 3_{sim} is 0.
Proof that the simulation is indistinguishable from the real experiment. We now describe a sequence of hybrid experiments (3_{real}, 3_{1}, 3_{2}, 3_{3}, 3_{sim}) in each of which a challenger C conducts a modification of the LIND experiment with A. We define 3_{real} to be the original LIND experiment, and 3_{sim} to be the simulation described above.
With a slight abuse of notation, given experiment 3, we define Adv^{3} to be the absolute value of the difference between (i) the LIND advantage of A in 3 and (ii) the LIND advantage of A in 3_{real}. Also, let


 q_{CA} be the total number of CreateAddress queries issued by A,
 q_{P} be the total number of Pour queries issued by A, and

q_{M} be the total number of Mint queries issued by .
 A
Finally, define Adv^{Enc} to be ’s advantage in Enc’s INDCCA and IKCCA experiments, Adv^{PRF} to be
A
COMM
A’s advantage in distinguishing the pseudorandom function PRF from a random one, and Adv
to be A’s advantage against the hiding property of COMM. We now describe each of the hybrid experiments.
i
28Note that by the restrictions of the experiment, the value v^{new} is identical between Q_{Left} and Q_{Right}.

 Experiment 3_{1}. The experiment 3_{1} modifies 3_{real} by simulating the zkSNARKs. More precisely, we modify 3_{real} so that C simulates each zkSNARK proof, as follows. At the beginning of the experiment, instead of invoking KeyGen(1^{λ}, C_{POUR}), C invokes Sim(1^{λ}, C_{POUR}) and obtains (pkPOUR, vk_{POUR}, trap). At each subsequent invocation of the Pour algorithm, C computes π_{POUR} ← Sim(trap, x), without using any witnesses, instead of using Prove. Since the zkSNARK system is perfect zero knowledge, the distribution of the simulated π_{POUR} is identical to that of the proofs computed in 3_{real}. Hence Adv^{3}1 = 0.
 Experiment 3_{2}. The experiment 3_{2} modifies 3_{1} by replacing the ciphertexts in a pour transaction by encryptions of random strings. More precisely, we modify 3_{1} so that, each time issues a Pour query where one of the output addresses (addr^{new} , addr^{new} ) is in the set of addresses
A
pk,1 pk,2
previously generated by a CreateAddress query, the two ciphertexts C^{new}, C^{new} are generated
1 2
as follows: (i) (pk^{new}, sk^{new}) ← K_{enc}(ppenc); (ii) for each j ∈ {1, 2}, C^{new} := E_{enc}(pk^{new} , r) where r
enc
enc
j
enc,j
is a message sampled uniformly from the plaintext space of the encryption scheme. By Lemma D.1
(see below), Adv^{3}2 − Adv^{3}1  ≤ 4 · q_{P} · Adv^{Enc}.

 Experiment 3_{3}. The experiment 3_{3} modifies 3_{2} by replacing all PRFgenerated values with random strings. More precisely, we modify 3_{2} so that:
 each time A issues a CreateAddress query, the value a_{pk} within the returned addr_{pk} is substituted with a random string of the same length;
 each time A issues a Pour query, each of the serial numbers sn^{old}, sn^{old} in tx_{Pour} is substituted
1
2
with a random string of the same length, and h_{info} with a random string of the same length.
By Lemma D.2 (see below), Adv^{3}3 − Adv^{3}2  ≤ q_{CA} · Adv^{PRF}.

 Experiment 3_{sim}. The experiment 3_{sim} is already described above. For comparison, we explain how it differs from 3_{3}: the coin commitments are replaced with commitments to random inputs. More precisely, we modify 3_{3} so that:
 each time A issues a Mint query, the coin commitment cm in tx_{Mint} is substituted with a commitment to a random input; and
 each time A issues a Pour query, then, for each j ∈ {1, 2}, if the output address addr^{new} is in the set of addresses previously generated by an CreateAddress query, cm is substituted
j
new
pk,j
with a commitment to a random input.
By Lemma D.3 (see below), Adv^{3}sim − Adv^{3}3  ≤ (q_{M} + 4 · q_{P}) · Adv^{COMM}.
As argued above, the responses provided to A in 3_{sim} are independent of the bit b, so that Adv^{3}sim = 0. Then, by summing over A’s advantages in the hybrid experiments, we can bound A’s advantage in 3real by
Adv^{LIND}(λ) ≤ 4 · q_{P} · Adv^{Enc} + q_{CA} · Adv^{PRF} + (q_{M} + 4 · q_{P}) · Adv^{COMM} ,
Π,A
which is negligible in λ. This concludes the proof of ledger indistinguishability. Below, we sketch proofs for the lemmas used above (Lemma D.1, Lemma D.2, and Lemma D.3).
Lemma D.1. Let Adv^{Enc} be the maximum of:


 A ’s advantage in the INDCCA experiment against the encryption scheme Enc, and
 A ’s advantage in the IKCCA experiment against the encryption scheme Enc. Then after q_{P} Pour queries, Adv^{3}2 − Adv^{3}1  ≤ 4 · q_{P} · Adv^{Enc}.

Proof sketch. Define s := Adv^{3}2 − Adv^{3}1 . Using A, we first show how to construct a solver with advantage ≥ s in the IKCCA or INDCCA experiments. We use a hybrid H, intermediate between
·
3_{1} and 3
2 q_{P}
2; concretely, H modifies 3_{1}
so that each ciphertext (where the corresponding public key
appears in the set generated by a CreateAddress query) is replaced with the encryption of the same plaintext, but under a new, random public key generated via the K_{enc} algorithm. (For comparison, 3_{2} modifies H so that each plaintext is replaced with a random plaintext drawn from the plaintext space.) We now argue that A’s advantage in distinguishing H and 3_{1} is at most 2 · q_{P} · Adv^{Enc}, and so is for distinguishing 3_{2} and H. Overall, we deduce that Adv^{3}2 − Adv^{3}1  ≤ 4 · q_{P} · Adv^{Enc}.
First, we discuss H and 3_{1}. For some j ∈ {1, . . . , q_{CA}}, when A makes the jth query of the form CreateAddress, query the IKCCA challenger to obtain two public keys (pkenc,0, pkenc,1) and return pkenc := pkenc,0 in the response to A. At the time A issues a Pour query that results in the
 th ciphertext C_{i} being encrypted under pkenc, query the IKCCA challenger on the corresponding plaintext m and receive C^{∗} = E_{enc}(pkenc,¯b, m) where ¯b is the bit chosen by the IKCCA challenger. Substitute C_{i} := C^{∗} and write the resulting tx_{Pour} to the Ledger. When A outputs b^{j} we return this guess as our guess in the IKCCA experiment. We note that when ¯b = 0 then A’s view of the interaction is distributed identically to that of 3_{1}, and when ¯b is 1 then A’s view represents an
intermediate hybrid where one key has been substituted. By a standard hybrid argument over each
of the 2 q_{P} ciphertexts, we note that over the random coins of the experiment, our solver must succeed in the IKCCA experiment with advantage ^{s} . If we assume a maximum adversarial
≥
·
2·q_{P}
advantage Adv^{Enc} against the IKCCA experiment for the encryption scheme, then we get that
H 3_{2} Enc
. .Adv − Adv ≤ 2 · q · Adv .
P
Next, we discuss 3_{2} and H; the argument is similar to the above one. This time, rather than replacing the key used to encrypt, we replace the plaintext with a random message drawn from the plaintext space; this final distribution is the same as in 3_{2}. We omit the formal description of the resulting INDCCA solver (which essentially follows the pattern above), and simply note that
3 H Enc_{2}
.Adv − Adv . ≤ 2 · q_{P} · Adv .
Lemma D.2. Let Adv^{PRF} be A’s advantage in distinguishing the pseudorandom function PRF from a random function. Then, after q_{CA} CreateAddress queries, Adv^{3}3 − Adv^{3}2  ≤ q_{CA} · Adv^{PRF}.
Proof sketch. We first describe a hybrid H, intermediate between 3_{2} and 3_{3}, in which all values computed using the first (rather than all) oraclegenerated key a_{sk} are replaced with random strings. Then, we show that A’s advantage in distinguishing between H and 3_{2} is at most Adv^{PRF}. Finally, we extend the argument to all q_{CA} oraclegenerated keys (corresponding to what happens in 3_{3}).
We now describe H. On receiving A’s first CreateAddress query, replace the public address
addr_{pk} = (a_{pk}, pkenc) with addr_{pk} = (τ, pkenc) where τ is a random string of the appropriate length.
On each subsequent Pour query, for each i ∈ {1, 2}, if addr^{old} = addr_{pk} then:
pk,i

 in the output tx_{Pour}, replace sn^{old} with a random string of appropriate length;
i

 in the output tx_{Pour}, replace each of h_{1}, h_{2} with a random string of appropriate length. 3.simulate the zkSNARK proof π_{POUR} for the new transaction.
Note that the above modifications do not affect the computation of the zkSNARK proof π_{POUR},
because π_{POUR} is simulated with the help of a trapdoor.
We now argue that A’s advantage in distinguishing between H and 3_{2} is at most Adv^{PRF}. Let a_{sk} be the random, secret seed for PRF generated by the oracle in answering the first CreateAddress query. In 3_{2} (as in 3_{real}):
addr
 a_{pk} := PRFask (0);
sn
 for each i ∈ {1, 2}, sn_{i} := PRFask (ρ) for a random (and not previously used) ρ
 for each i ∈ {1, 2}, h_{i} := PRFask (i“h_{Sig}) and, with overwhelming probability, h_{Sig} is unique.
pk
Moreover, each of PRF^{addr}, PRF^{sn} , PRF^{pk} are constructed from PRF_{a} as specified in Section 4.1.
ask
ask
a_{sk} sk
Note that, with overwhelming probability, no two calls to PRF_{a}sk are made on the same input. First,
even identical inputs passed to PRF^{addr}, PRF^{sn} , PRF^{pk} produce different underlying calls to PRF_{a} .
ask
ask
a_{sk} sk
Second, within each construction, there is exactly one call to PRF^{addr}, and the calls to PRF^{sn} are
ask ask
each by definition unique. Finally, with overwhelming probability, the calls to PRF^{pk} from different
ask
transactions each reference a distinct digest h_{Sig}, and, within a given transaction, the two calls each begin with a distinct prefix.
Now let O be an oracle that implements either PRF_{a}sk or a random function. We show that if A distinguishes H from 3_{2} with probability s, then we can construct a distinguisher for the two cases of O. In either case we use O to generate all values computed using PRF^{addr}, PRF^{sn} , PRF^{pk} .
ask
ask
ask
Clearly, when O implements PRF_{a}sk , the distribution of the experiment is identical to 3_{2}; instead, when implements a random function, the distribution of the experiment is identical to H. Thus,
O
PRF
A’s advantage is at most Adv .
Finally, by a standard hybrid argument, we extend the above to all q_{CA} oraclegenerated addresses; then, A’s differential distinguishing advantage is at most q_{CA} · Adv^{PRF}. Because this final hybrid is equal to 3_{3}, we deduce that Adv^{3}3 − Adv^{3}2  ≤ q_{CA} · Adv^{PRF}.
Lemma D.3. Let Adv^{COMM} be A’s advantage against the hiding property of COMM. After q_{M}
Mint queries and q_{P} Pour queries, Adv^{3}sim − Adv^{3}3  ≤ (q_{M} + 4 · q_{P}) · Adv^{COMM}.
Proof sketch. We only provide a short sketch, because the structure of the argument is similar to the one used to prove Lemma D.2 above.
For the first Mint or Pour query, replace the “internal” commitment k := COMM_{r}(a_{pk}“ρ) with a random string of the appropriate length. Since ρ is random (and unique), then A’s advantage in distinguishing this modified experiment from 3_{2} is at most Adv^{COMM}. Then, if we similarly modify all q_{M} Mint queries and all q_{P} Pour queries, by replacing the resulting q_{M} + 2 · q_{P} internal commitments with random strings, we can bound A’s advantage by (q_{M} + 2 · q_{P}) · Adv^{COMM}.
Next, in a similar vein, if replace the coin commitment in the first Pour with a commitment to a random value, then ’s advantage in distinguishing this modified experiment from the above one is at most Adv^{COMM}. Then, if we similarly modify all q_{P} Pour queries, by replacing the resulting 2 · q_{P} coin commitments with random strings, we obtain the experiment 3_{sim}, and deduce that
A
Adv^{3}sim − Adv^{3}3  ≤ (q_{M} + 4 · q_{P}) · Adv^{COMM}.
Proof of transaction nonmalleability
Letting be the set of pour transactions generated by ^{DAP} in response to Pour queries, recall that wins the TRNM experiment whenever it outputs tx^{∗} such that there exists tx^{j} such that:
A ∈ T
T O
 tx^{∗} = tx^{j}; (ii) VerifyTransaction(pp, tx^{∗}, L^{j}) = 1, where L^{j} is the portion of the ledger preceding tx^{j}; and (iii) a serial number revealed in tx^{∗} is also revealed in tx^{j}. Being a pour transaction, tx^{∗} has the form (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, info, ∗), where ∗ := (pksig, h_{1}, h_{2}, π_{POUR}, C_{1}, C_{2}, σ); set
ƒ
1
2
1
2
h_{Sig} := CRH(pksig). Let pk^{j}sig be the corresponding public key in tx^{j} and set h^{j}Sig := CRH(pk^{j}sig).
Define s := Adv^{TRNM}(λ), and let Q_{CA} = {a_{sk}_{,}_{1}, . . . , a_{sk}_{,q} } be the set of internal address keys
Π,A
CA
created by C in response to A’s CreateAddress queries. Let Q_{P} = (pksig,1, . . . , pksig,qP ) be the set of signature public keys created by C in response to A’s Pour queries. We decompose the event in which A wins into the following four disjoint events.
 Event_{sig}: A wins, and there is pk^{j}sjig ∈ Q_{P} such that pksig = pk^{j}sjig.
 Event_{col}: A wins, the above event does not occur, and there is pk^{j}sjig ∈ Q_{P} such that h_{Sig} =
CRH(pk^{j}sjig).
 Event_{mac}: A wins, the above two events do not occur, and h_{i} = PRFa (i“h_{Sig}) for some i ∈ {1, 2} and a ∈ Q_{CA}.
pk
 Event_{key}: A wins, the above three events do not occur, and h_{i}
a
and a ∈ Q_{CA}.
PRF^{pk}(i“h_{Sig}) for all i ∈ {1, 2}
Clearly, s = Pr [ Event_{sig} ] + Pr [ Event_{col} ] + Pr [ Event_{key} ] + Pr [ Event_{mac} ]. Hence, to show that s is negligible in λ, it suffices to argue that each of these probabilities is negligible in λ.
Bounding the probability of Event_{sig}. Define s_{1} := Pr [ Event_{sig} ]. Let σ be the signature in tx^{∗}, and σ^{jj} be the signature in the first pour transaction tx^{jj} ∈ T that contains pk^{j}sjig. When Event_{sig} occurs, since pksig = pk^{j}sjig, the two signatures are with respect to the same public key. Moreover, since tx^{∗} is valid, _{sig}(pksig, m, σ) = 1 where m is everything in tx^{∗} but for σ. Let m^{jj} consist of all elements in tx^{jj} but for σ^{jj}. Observe that whenever tx^{∗} = tx^{jj} we also have (m, σ)
ƒ
V
= (m^{jj}, σ^{jj}). We use this fact below to show that forges a signature with nonnegligible probability.
ƒ A
First, we argue that, conditioned on Event_{sig}, tx^{∗} = tx^{jj} with overwhelming probability; we do so by way of contradiction. First, since wins, by definition there is tx^{j} such that tx^{∗} = tx^{j} and yet each of tx^{∗} and tx^{j} share one serial number. Therefore: (i) tx^{∗} = tx^{j}; and (ii) if tx^{∗} = tx^{jj} then tx^{jj} and tx^{j} also share a serial number. However the probability that tx^{j} and tx^{jj} share a serial number is bounded by the probability p˜ that contains two transactions that share the same serial number. Because each serial number is computed as PRF^{sn} (ρ), where ρ is random, p˜ is negligible. We conclude that tx^{∗} ƒ= tx^{jj} with all but negligible probability.
ƒ
T
ask
A ∈ T ƒ
ƒ
Next, we describe an algorithm B, which uses A as a subroutine, that wins the SUF1CMA game against Sig with probability s_{1}/q_{P}. After receiving a verification key pk^{j}sjig from the SUF1CMA challenger, the algorithm B performs the following steps.

 B selects a random index j ← {1, . . . , q_{P}}.
 B conducts the TRNM experiment with A, except that, when A issues the jth Pour query, B executes Pour as usual, but modifies the resulting pour transaction tx^{jj} as follows: (i) it substitutes pk^{j}sjig for the signature public key in tx^{jj}; (ii) it queries the SUF1CMA challenger to obtain σ^{jj} on the appropriate message m^{jj}; and (iii) it substitutes σ^{jj} for the signature in tx^{jj}.
 When A outputs tx^{∗}, B looks into tx^{∗} to obtain pksig, m, and σ.
 If pksig ƒ= pk^{j}sjig then B aborts; otherwise B outputs (m, σ) as a forgery for Sig.
jj
Note that tx has the same distribution has an “untampered” pour transaction; thus, all transactions
returned to A are distributed as in the TRNM experiment. Since the index j is selected at random, B succeeds in the experiment with probability at least s_{1}/q_{P}. Because Sig is SUF1CMA, s_{1} must be negligible in λ.
Bounding the probability of Event_{col}. Define s_{2} := Pr [ Event_{col} ]. When Event_{col} occurs,
A receives a transaction tx^{j} containing a public key pk^{j}sjig, and subsequently outputs a transaction
tx^{∗} containing a public key pksig such that (i) pksig pk^{j}sjig, but (ii) CRH(pksig) = CRH(pk^{j}sig). In
particular, A finds collisions for CRH with probability s_{2}. Because CRH is collision resistant, s_{2}
must be negligible in λ.
Bounding the probability of Event_{mac}. Define s_{3} := Pr [ Event_{mac} ]. We first define an exper iment 3_{1}, which modifies the TRNM experiment as follows. When C samples pp ← Setup(1^{λ}), the subcall to (pkPOUR, vk_{POUR}) ← KeyGen(1^{λ}, C_{POUR}) is replaced by (pkPOUR, vk_{POUR}, trap) ← Sim(1^{λ}, C_{POUR}), so to obtain the zeroknowledge trapdoor trap. Afterwards, each time A issues a Pour query, C replaces the zkSNARK proof in the resulting pour transaction with a simulated proof, obtained by running Sim(trap, x) for an appropriate input x. Because the zkSNARK is perfect zero knowledge, Pr [ Event_{mac} ] = s_{3} in the 3_{1} experiment as well.
Assume by way of contradiction that s_{3} is nonnegligible. We now show how to construct an attacker B, which uses A as a subroutine, that distinguishes PRF from a random function RAND with nonnegligible probability. The algorithm B, which has access either to O = PRF or O = RAND, “interfaces” between A and C in the experiment 3_{1} above, as follows.
 First, B selects a random index j ← {1, . . . , q_{CA}}, which identifies a_{sk}_{,j} ∈ Q_{CA}.
 Next, B uses the oracle O instead of PRF_{a}sk,j , i.e., anytime a value needs to be computed depending on PRF_{a}sk,j (z), for some z, O(z) is used instead. (For instance, the public address key a_{pk}_{,j} is one such value.)
 Finally, after A outputs tx^{∗}:
 if O has been previously evaluated the expression “PRF^{pk} (i“h_{Sig})” using O, B aborts
ask,j
and outputs 1;

 otherwise, B evaluates the expression “PRF^{pk} (i“h_{Sig})” by using O; if the result equals
ask,j
h_{i}, B outputs 1, else it outputs 0.
Conducting the above strategy does not require knowledge of a_{sk}_{,j} because, having the simulation
trapdoor, B does not ne.ed Σwitnesses to genΣ erate Σ(valid) zkSNARΣK. proofs.
We now argue that .Pr BPRF (1^{λ}) = 1 − Pr BRAND(1^{λ}) = 1 . is nonnegligible.
 Case 1: O = RAND. Observe that:
Pr Σ BRAND(1^{λ}) = 1  BRAND(1^{λ}) does not abort Σ = 2^{−}^{ω} .
where ω is the output length of PRF. Hence:
Pr Σ BRAND(1^{λ}) = 1 Σ = .1 − Pr Σ BRAND(1^{λ}) aborts ΣΣ · 2^{−}^{ω} + Pr Σ BRAND(1^{λ}) aborts Σ.
 Case 2: O = PRF. In this case the distribution of the simulation is identical to that of 3_{1}, and B has set a_{sk}_{,j} equal to the seed used by O. Recall that, when Event_{mac} holds, h_{i} = PRF^{pk}(i“h_{Sig}) for some a ∈ Q_{CA}. Since A’s view of the experiment is independent of j, the probability that
a
a = a_{sk}_{,j} is at least 1/q_{CA}, and the probability that h_{i} = PRF^{pk} (i“h_{Sig}) is at least s_{3}/q_{CA}.
ask,j
Hence:
Thus:
Pr Σ BPRF (1^{λ}) = 1  BPRF (1^{λ}) does not abort Σ = s_{3}/q_{CA} .
Pr Σ BPRF (1^{λ}) = 1 Σ = .1 − Pr Σ BPRF (1^{λ}) aborts ΣΣ · s_{3}/q_{CA} + Pr Σ BPRF (1^{λ}) aborts Σ.
thaΣt .Pr BPRF (1^{λ}) = 1Σ − Pr ΣBRAND(1^{λ}) = 1 . Σis nonnegligible, it suffices to show that each of
Clear.ly, Σ2^{−}^{ω} is negligibΣle; moΣreover, if s_{3} is nΣo.nnegligible, then so is s_{3}/q_{CA}. Thus, to show
Pr
BRAND(1^{λ}) aborts
and Pr
BPRF (1^{λ}) aborts
is negligible.
To do so, recall that B aborts if and only if it has previously evaluated the expression
pk
“PRF
ask,j
(i“h_{Sig})” using O prior to receiving A’s output. First note that B’s only calls to O occur
when it evaluates the functions PRF^{addr}, PRF^{sn} and PRF^{pk}. Moreover, due to the construction
of these functions it is not possible to evaluate the expression PRF^{pk} (i“h_{Sig}) using any calls to
ask,j
PRF^{addr} or PRF^{sn}. Thus B aborts if and only if it has previously queried PRF^{pk} on the expression
pk
PRF
ask,j
(i“h_{Sig}). However it is easy to see that this cannot happen under the conditions of Event_{mac},
since such a query would imply the condition Event_{sig} or Event_{col}, each of which is excluded by
Event_{mac}. Hence the probability of either condition occurring is 0.
Bounding the probability of Event_{key}. Define s_{4} := Pr [ Event_{key} ], and let E be the zkSNARK extractor for A. Assume by way of contradiction that s_{4} is nonnegligible. We construct an algorithm
sn
sn
B that finds collisions for PRF with nonnegligible probability (contradicting the fact that PRF
is collision resistant). The algorithm B works as follows.
 Run A (simulating its interaction with the challenger C) to obtain tx^{∗}.
 Run (pkPOUR, vk_{POUR}) to obtain a witness a for the zkSNARK proof π_{POUR} in tx^{∗}.
E
 If a is not a valid witness for the instance x := (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, h_{Sig}, h_{1}, h_{2}),
abort and output 0.
1 2 1 2
 Parse a as (path1, path2, c^{old}, c^{old}, addr^{old} , addr^{old} , c^{new}, c^{new}).
1 2 sk,1 sk,2 1 2
 For each i ∈ {1, 2}, parse c^{old} as (addr^{old} , v^{old}, ρ^{old}, r^{old}, s^{old}, cm^{old}).
i
pk,i
i
i
i
i
i
 For each i ∈ {1, 2}, parse addr^{old} as (a^{old} , sk^{old} ).
sk,i
sk,i
enc,i
(Note that, since a is a valid witness, sn^{old} = PRF^{sn}
a
(ρ^{old}) for all i ∈ {1, 2}.)
 For each i ∈ {1, 2}:
i old i
sk,i
 Look for a pour transaction tx that contains sn^{old}.
i
∈ T
 If one tx is found, let a_{sk} and ρ be the seed and input used to compute sn^{old} in tx; thus,
sni = PRFask (ρ). If ask,i ƒ= a_{sk}, output
Note that, whenever Event_{key} holds:
(ask,i, ρi ), (a_{sk}, ρ)
as a collision for PRF
.
old sn
old
. old
old Σ i sn
 the proof π_{POUR} is valid and, with all but negligible probability, the witness a is valid;
 the serial number sn^{old} or sn^{old} appears in some previous pour transaction in T ;
1 2
pk pk
 whenever a is valid, it holds that h_{1} = PRF old (h_{Sig}) and h_{2} = PRF old (h_{Sig}), so that it cannot
ask,1
ask,2
be that a^{old}
sk,1
old sk,2
= a_{sk} (as this contradicts the conditions of the event Event_{key}).
Overall, we conclude that B finds a collision for PRF^{sn} with probability s_{4} − negl(λ).
= a
Proof of balance
Define s := Adv^{BAL}(λ); our goal is to show that s is negligible in λ. Recall that ADDR is the set of
Π,A
addresses returned by A’s CreateAddress queries.
Augmenting the ledger with witnesses. We modify the BAL experiment in a way that does not affect A’s view: the challenger C computes, for each pour transaction tx_{Pour} on the ledger L (maintained by the oracle ODAP), a witness a = (path1, path2, c^{old}, c^{old}, addr^{old} , addr^{old} , c^{new}, c^{new})
1
2
sk,1
sk,2
1
2
for the zkSNARK instance x = (rt, sn^{old}, sn^{old}, cm^{new}, cm^{new}, v_{pub}, h_{Sig}, h_{1}, h_{2}) corresponding to
1 2 1 2
tx_{Pour}.^{29} In this way, C obtains an augmented ledger (L, ˙a), where a_{i} is a witness for the zkSNARK instance x_{i} of the ith pour transaction in L. Note that we can parse (L, ˙a) as a list of matched pairs (tx_{Pour}, a) where tx_{Pour} is a pour transaction in L and a is its corresponding witness.
The discussion below is relative to the above modification of the BAL experiment.
Balanced ledgers. We say that an augmented ledger (L, ˙a) is balanced if the following holds.
 Each (tx_{Pour}, a) in (L, ˙a) contains openings (i.e., decommitments) of two distinct coin com mitments cm^{old} and cm^{old}; also, each cm^{old} is the output coin commitment of a pour or mint
1 2 i
transaction that precedes tx_{Pour} on L.
 No two ( tx_{Pour}, a) and (a^{j}, tx^{j}Pour) in (L, ˙a) contain openings of the same coin commitment.
29 Concretely, for pour transactions in L not inserted by A, C simply retains the witness a internally used by ODAP to generate the transaction. As for the (valid) pour transactions inserted by A, C uses the zkSNARK multiinstance knowledge extractor corresponding to A; see Section 2.1. (If knowledge extraction fails, C aborts and outputs 1. However, this only happens with negligible probability.)
 Each (tx_{Pour}, a) in (L, ˙a) contains openings of cm^{old}, cm^{old}, cm^{new}, cm^{new} to values v^{old}, v^{old},
1 2 1 2 1 2
v^{new}, v^{new} (respectively), with the condition that v^{old} + v^{old} = v^{new} + v^{new} + v_{pub}.
1 2 1 2 1 2
 For each ( tx_{Pour}, a) in (L, ˙a) and for each i ∈ {1, 2}, the following conditions hold:
 If cm^{old} is also the output of a mint transaction tx_{Mint} on L, then the public value v in
i
tx_{Mint} is equal to v^{old}.
i

 If cm^{old} is also the output of a pour transaction tx^{j} on L, then its witness a^{j} contains
i Pour
an opening of cm^{old} to a value v^{j} that is equal to v^{old}.
i i
 For each (tx_{Pour}, a) in (L, ˙a), where tx_{Pour} was inserted by , it holds that, for each i 1, 2 , if cm^{old} is the output of an earlier mint or pour transaction tx^{j}, then the public address of the ith output of tx^{j} is not contained in ADDR.
i
A ∈ { }
Intuitively, the above conditions ensure that, in L, A did not spend money that was not previously minted, or paid to an address under A’s control. Concretely, one can prove by induction that if (L, ˙a) is balanced then vUnspent + vBasecoin + vA→ADDR > vMint + vADDR→A.
In light of the above, it suffices to argue that the augmented ledger induced by the (modified) BAL experiment is balanced with all but negligible probability. Suppose, by way of contradiction, that is is not the case: A induces, with nonnegligible probability, an augmented ledger (L, ˙a) that is not balanced. We distinguish between five cases, corresponding to which one of the above conditions does not hold with nonnegligible probability. In each case, we show how to reach a contradiction, concluding the proof.
A violates Condition I. Suppose that Pr [ A wins but violates Condition I ] is nonnegligible. By construction of ODAP, every (tx_{Pour}, a) in (L, ˙a) for which tx_{Pour} was not inserted by A satisfies Condition I; thus, the violation can only originate from a pair (tx_{Pour}, a) in (L, ˙a) for which tx_{Pour} was inserted by A and such that: (i) cm^{old} = cm^{old}; or (ii) there is i ∈ {1, 2} such that cm^{old} has no
1
2
i
corresponding output coin commitment in any pour or mint transaction that precedes tx_{Pour} on L. Observe that the validity of tx_{Pour} implies that:
 The two serial numbers sn^{old} and sn^{old} are distinct. Moreover, recalling that each sn^{old} equals
1
2
i
PRF^{sn} (ρ^{old}), this also implies that (a^{old} , ρ^{old}) ƒ= (a^{old} , ρ^{old}).
a
old sk,i
i
sk,1
1
sk,2
2
 The witness a contains two valid authentication paths path1, path2 for a Merkle tree constructed using only coin commitments of transactions preceding tx_{Pour} in L.
In either (i) or (ii), we reach a contradiction. Indeed:
 If cm^{old} = cm^{old}, then the fact that sn^{old} ƒ= sn^{old} implies that the witness a contains two
1
2
1
2
distinct openings of cm^{old} (the first opening contains (a^{old} , ρ^{old}), while the second opening
1 sk,1 1
contains (a^{old} , ρ^{old})). This violates the binding property of the commitment scheme COMM.
sk,2 2
 If there is i ∈ {1, 2} such that cm^{old} does not previously appear in L, then pathi is an invalid authentication path, and thus yields a collision in the function CRH. This violates the collision resistance of CRH.
i
A violates Condition II. Suppose that Pr [ A wins but violates Condition II ] is nonnegligible. Observe that, when Condition II is violated, L contains two pour transactions tx_{Pour}, tx^{j}Pour spending the same coin commitment cm, and revealing two serial numbers sn and sn^{j}. Since tx_{Pour}, tx^{j}Pour are valid, it must be the case that sn = sn^{j}. However (as argued already above), if both transactions spend cm but produce different serial numbers, then the corresponding witnesses a, a^{j} contain different openings of cm. This contradicts the binding property of the commitment scheme COMM.
ƒ
A violates Condition III. Suppose that Pr [ A wins but violates Condition III ] is nonnegligible. In this case, the contradiction is immediate: whenever Condition III is violated, the equation
v^{old} + v^{old} = v^{new} + v^{new} + v_{pub} does not hold, and thus, by construction of the statement POUR, the
1 2 1 2
soundness of the zkSNARK is violated as well.
A violates Condition IV. Suppose that Pr [ A wins but violates Condition IV ] is nonnegligible. Observe that, when Condition IV is violated, L contains:
 a pour transaction tx_{Pour} in which a coin commitment cm^{old} is opened to a value v^{old}; and also
 a (mint or pour) transaction tx^{j} that opens cm^{old} to a value v^{j} different from v^{old}. This contradicts the binding property of the commitment scheme COMM.
A violates Condition V. Suppose that Pr [ A wins but violates Condition V ] is nonnegligible. Observe that, when Condition V is violated, L contains an inserted pour transaction tx_{Pour} that spends the output of a previous transaction tx^{j} whose public address addr_{pk} = (a_{pk}, pkenc) lies in ADDR; moreover, the witness associated to tx^{j} contains a_{sk} such that a_{pk} = PRF^{addr}(0). We omit the full argument, but one can verify that, in this case, we can construct a new adversary B that uses A to distinguish, with nonnegligible probability, PRF from a random function.
ask
References
[BB04] Dan Boneh and Xavier Boyen. Secure identity based encryption without random oracles. In Proceedings of the 24th Annual International Cryptology Conference, CRYPTO ’04, pages 443–459, 2004.
[BBDP01] Mihir Bellare, Alexandra Boldyreva, Anand Desai, and David Pointcheval. Keyprivacy in public key encryption. In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ’01, pages 566–582, 2001.
[BBSU12] Simon Barber, Xavier Boyen, Elaine Shi, and Ersin Uzun. Bitter to better – how to make Bitcoin a better currency. In Proceedings of the 16th International Conference on Financial Cryptography and Data Security, FC ’12, pages 399–414, 2012.
[BCCT12] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct noninteractive arguments of knowledge, and back again. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, pages 326–349, 2012.
[BCCT13] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for SNARKs and proofcarrying data. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC ’13, pages 111–120, 2013.
[BCG^{+}13] Eli BenSasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C: verifying program executions succinctly and in zero knowledge. In Proceedings of the 33rd Annual International Cryptology Conference, CRYPTO ’13, pages 90–108, 2013.
[BCGT13a] Eli BenSasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference, ITCS ’13, pages 401–414, 2013.
[BCGT13b] Eli BenSasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. On the concrete efficiency of probabilisticallycheckable proofs. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC ’13, pages 585–594, 2013.
[BCI^{+}13] Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct non interactive arguments via linear interactive proofs. In Proceedings of the 10th Theory of Cryptography Conference, TCC ’13, pages 315–333, 2013.
[BCTV14] Eli BenSasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct noninteractive zero knowledge for a von Neumann architecture. In Proceedings of the 23rd USENIX Security Symposium, Security ’14, pages ???–???, 2014. Available at http://eprint.iacr.org/2013/879.
[Bel06] Mihir Bellare. New proofs for NMAC and HMAC: security without collisionresistance. In Proceedings of the 26th Annual International Conference on Advances in Cryptology, CRYPTO ’06, pages 602–619, 2006.
[Ben13] Eli BenSasson. Universal and affordable computational integrity, May 2013. Bitcoin 2013: The Future of Payments. URL: http://www.youtube.com/watch?v=YRcPReUpkcU&feature=youtu.be&t=26m6s.
[BFLS91] La´szlo´ Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polyloga rithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC ’91, pages 21–32, 1991.
[BGH^{+}05] Eli BenSasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Short PCPs verifiable in polylogarithmic time. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, CCC ’05, pages 120–134, 2005.
[Cer00] Certicom Research. SEC 1: Elliptic curve cryptography, 2000. URL: http://www.secg.org/collateral/ sec1_final.pdf.
[Cha82] David Chaum. Blind signatures for untraceable payments. In Proceedings of the 2nd Annual International Cryptology Conference, CRYPTO ’82, pages 199–203, 1982.
[CHL05] Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. Compact ecash. In Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT ’05, pages 302–321, 2005.
[CL01] Jan Camenisch and Anna Lysyanskaya. An efficient system for nontransferable anonymous credentials with optional anonymity revocation. In Proceedings of the 20th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT ’01, pages 93–118, 2001.
[DDM03] George Danezis, Roger Dingledine, and Nick Mathewson. Mixminion: Design of a type III anonymous remailer protocol. In Proceedings of the 2003 IEEE Symposium on Security and Privacy, SP ’03, pages 2–15, 2003.
[DFKP13] George Danezis, Cedric Fournet, Markulf Kohlweiss, and Bryan Parno. Pinocchio Coin: building Zerocoin from a succinct pairingbased proof system. In Proceedings of the 2013 Workshop on Language Support for Privacy Enhancing Technologies, PETShop ’13, 2013. URL: http://www0.cs.ucl.ac.uk/staff/G. Danezis/papers/DanezisFournetKohlweissParno13.pdf.
[DMS04] Roger Dingledine, Nick Mathewson, and Paul Syverson. Tor: the secondgeneration onion router. In
Proceedings of the 13th USENIX Security Symposium, Security ’04, pages 21–21, 2004.
[DW13] Christian Decker and Roger Wattenhofer. Information propagation in the Bitcoin network. In Proceedings of the 13th IEEE International Conference on PeertoPeer Computing, P2P ’13, pages 1–10, 2013.
[ES13]Ittay Eyal and Emin Gu¨n Sirer. Majority is not enough: Bitcoin mining is vulnerable, 2013.
[Gen04] Rosario Gennaro. Multitrapdoor commitments and their applications to proofs of knowledge secure under concurrent maninthemiddle attacks. In Proceedings of the 24th Annual International Cryptology Conference, CRYPTO ’04, pages 220–236, 2004.
[GGPR13] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Proceedings of the 32nd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT ’13, pages 626–645, 2013.
[GMR89] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186–208, 1989. Preliminary version appeared in STOC ’85.
[GOS06a] Jens Groth, Rafail Ostrovsky, and Amit Sahai. Noninteractive Zaps and new techniques for NIZK. In Proceedings of the 26th Annual International Conference on Advances in Cryptology, CRYPTO ’06, pages 97–111, 2006.
[GOS06b] Jens Groth, Rafail Ostrovsky, and Amit Sahai. Perfect noninteractive zero knowledge for NP. In Proceedings of the 25th Annual International Conference on Advances in Cryptology, EUROCRYPT ’06, pages 339–358, 2006.
[Gro10] Jens Groth. Short pairingbased noninteractive zeroknowledge arguments. In Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ’10, pages 321–340, 2010.
[GW11] Craig Gentry and Daniel Wichs. Separating succinct noninteractive arguments from all falsifiable assumptions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC ’11, pages 99–108, 2011.
[KL07] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman & Hall/CRC, 2007. [Lee13] Timothy B. Lee. Bitcoin needs to scale by a factor of 1000 to compete with Visa. here’s how to do it.
The Washington Post (http://www.washingtonpost.com), November 2013.
[Lip12] Helger Lipmaa. Progressionfree sets and sublinear pairingbased noninteractive zeroknowledge argu ments. In Proceedings of the 9th Theory of Cryptography Conference on Theory of Cryptography, TCC ’12, pages 169–189, 2012.
[Lip13] Helger Lipmaa. Succinct noninteractive zero knowledge arguments from span programs and linear errorcorrecting codes. In Proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ’13, pages 41–60, 2013.
[Max13] Greg Maxwell. CoinJoin: Bitcoin privacy for the real world, August 2013. Bitcoin Forum. URL:
https://bitcointalk.org/index.php?topic=279249.0.
[MGGR13] Ian Miers, Christina Garman, Matthew Green, and Aviel D. Rubin. Zerocoin: Anonymous distributed ecash from bitcoin. In Proceedings of the 2013 IEEE Symposium on Security and Privacy, SP ’13, pages 397–411, 2013.
[Mic00] Silvio Micali. Computationally sound proofs. SIAM Journal on Computing, 30(4):1253–1298, 2000.
Preliminary version appeared in FOCS ’94.
[MPJ^{+}13] Sarah Meiklejohn, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M. Voelker, and Stefan Savage. A fistful of Bitcoins: Characterizing payments among men with no names. In Proceedings of the 2013 Conference on Internet Measurement Conference, IMC ’13, pages 127–140, 2013.
[Nak09] Satoshi Nakamoto. Bitcoin: a peertopeer electronic cash system, 2009. URL: http://www.bitcoin. org/bitcoin.pdf.
[Nat12] National Institute of Standards and Technology. FIPS PUB 1804: Secure Hash Standard. http:
//csrc.nist.gov/publications/PubsFIPS.html, 2012.
[PGHR13] Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova. Pinocchio: nearly practical verifiable computation. In Proceedings of the 34th IEEE Symposium on Security and Privacy, Oakland ’13, pages 238–252, 2013.
[Pol13]PolarSSL. PolarSSL. http://polarssl.org, Oct 2013.
[RM11] Fergal Reid and Harrigan Martin. An analysis of anonymity in the Bitcoin system. In Proceedings of the 3rd IEEE International Conference on Privacy, Security, Risk and Trust and on Social Computing, SocialCom/PASSAT ’11, pages 1318–1326, 2011.
[RS12] Dorit Ron and Adi Shamir. Quantitative analysis of the full Bitcoin transaction graph. Cryptology ePrint Archive, Report 2012/584, 2012.
[ST99] Tomas Sander and Amnon TaShma. Auditable, anonymous electronic cash. In Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’99, pages 555–572, 1999.
[Val08] Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency.
In Proceedings of the 5th Theory of Cryptography Conference, TCC ’08, pages 1–18, 2008.
[Wui14] Pieter Wuille. Proposed BIP for dealing with malleability. Available at https://gist.github.com/ sipa/8907691, 2014.