2014 IEEE Symposium on Security and Privacy

Zerocash: Decentralized Anonymous Payments from Bitcoin
Eli Ben-Sasson∗ , Alessandro Chiesa† , Christina Garman‡ , Matthew Green‡ , Ian Miers‡ , Eran Tromer§ , Madars Virza†∗ Technion, eli@cs.technion.ac.il† MIT, {alexch,madars}@mit.edu
imiers, mgreen}@cs.jhu.edu§ Tel Aviv University, tromer@cs.tau.ac.il‡ Johns Hopkins University, {cgarman,

Abstract—Bitcoin is the first digital currency to see widespread
adoption. While payments are conducted between pseudonyms,
Bitcoin cannot offer strong privacy guarantees: payment transactions are recorded in a public decentralized ledger, fromwhich much information can be deduced. Zerocoin (Miers etal., IEEE S&P 2013) tackles some of these privacy issues by
unlinking transactions from the payment’s origin. Yet, it still
reveals payments’ destinations and amounts, and is limited infunctionality.
In this paper, we construct a full-fledged ledger-based digitalcurrency with strong privacy guarantees. Our results leverage
recent advances in zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs).
First, we formulate and construct decentralized anonymous
payment schemes (DAP schemes). A DAP scheme enables users to
directly pay each other privately: the corresponding transaction
hides the payment’s origin, destination, and transferred amount.
We provide formal definitions and proofs of the construction’s
security.
Second, we 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 less-anonymous Zerocoin and competitive withplain Bitcoin.

party and then, after some interval, retrieve different coins(with the same total value) from the pool. Yet, mixes sufferfrom three limitations: (i) the delay to reclaim coins must belarge to allow enough coins to be mixed in; (ii) the mix can
trace coins; and (iii) the mix may steal coins.1 For users with“something to hide,” these risks may be acceptable. But typicallegitimate users (1) wish to keep their spending habits private
from their peers, (2) are risk-averse and do not wish to expend
continual effort in protecting their privacy, and (3) are often
not sufficiently aware of their compromised privacy.
To protect their privacy, users thus need an instant, risk-free,and, most importantly, automatic guarantee that data revealing
their spending habits and account balances is not publicly
accessible by their neighbors, co-workers, and merchants.
Anonymous transactions also guarantee that the market valueof a coin is independent of its history, thus ensuring legitimate
users’ coins remain fungible.2
Zerocoin: a decentralized mix. Miers et al. [8] proposed
Zerocoin, which extends Bitcoin to provide strong anonymity
guarantees. Like many e-cash protocols (e.g., [2]), Zerocoin
employs zero-knowledge proofs to prevent transaction graphanalyses. Unlike earlier practical e-cash protocols, however,Zerocoin does not rely on digital signatures to validate coins,nor does it require a central bank to prevent double spending.
Instead, Zerocoin authenticates coins by proving, in zeroknowledge, that they belong to a public list of valid coins(which can be maintained on the block chain). Yet, rather thana full-fledged anonymous currency, Zerocoin is a decentralized
mix, where users may periodically “wash” their bitcoins via
the Zerocoin protocol. Routine day-to-day transactions must
be conducted via Bitcoin, due to reasons that we now review.
The first reason is performance. Redeeming zerocoinsrequires double-discrete-logarithm proofs of knowledge, whichhave size that exceeds 45 kB and require 450 ms to verify (atthe 128-bit security level).3 These proofs must be broadcast

Keywords: Bitcoin, decentralized electronic cash, zero knowledge

I. I NTRODUCTION
Bitcoin is the first digital currency to achieve widespread
adoption. The currency owes its rise in part to the fact that,
unlike traditional e-cash schemes [1, 2, 3], it requires no trusted
parties. Instead of appointing a central bank, Bitcoin leverages a
distributed ledger known as the block chain to store transactions
made between users. Because the block chain is massively
replicated by mutually-distrustful peers, the information it
contains is public.
While users may employ many identities (or pseudonyms)
to enhance their privacy, an increasing body of research showsthat anyone can de-anonymize Bitcoin by using information in
the block chain [4, 5, 6], 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 ofanonymous e-cash schemes.
While Bitcoin is not anonymous itself, those with sufficientmotivation can obfuscate their transaction history with the helpof mixes (also known as laundries or tumblers). A mix allows
users to entrust a set of coins to a pool operated by a central© 2014, Eli Ben-Sasson. Under license to IEEE.
DOI 10.1109/SP.2014.36

1 CoinJoin [7], an alternative proposal, replaces the central party of a mix
with multi-signature transactions that involve many collaborating Bitcoin users.
CoinJoin can thus only mix small volumes of coins amongst users who are
currently online, is prone to denial-of-service attacks by third parties, andrequires effort to find mixing partners.
2 While the methods we detail in this paper accomplish this, the same
techniques open the door for privacy preserving accountability and oversight(see Section X).
3 These published numbers [8] actually use a mix of parameters at both128-bit and 80-bit security for different components of the construction. The
cost is higher if all parameters are instantiated at the 128-bit security level.

459

through the network, verified by every node, and permanently
stored in the ledger. The entailed costs are higher, by ordersof magnitude, than those in Bitcoin and can seriously tax a
Bitcoin network operating at normal scale.
The second reason is functionality. While Zerocoin constitutes a basic e-cash scheme, it lacks critical features requiredof full-fledged anonymous payments. First, Zerocoin uses
coins of fixed denomination: it does not support paymentsof exact values, nor does it provide a means to make change
following a transaction (i.e., divide coins). Second, Zerocoin
has no mechanism for one user to pay another one directlyin “zerocoins.” And third, while Zerocoin provides anonymity
by unlinking a payment transaction from its origin address, itdoes not hide the amount or other metadata about transactions
occurring on the network.
Our contribution. In this work we address the aforementioned issues via two main contributions.

is succinct, i.e., for which proofs are very short and easy toverify. More precisely, let L be an NP language, and let C be anondeterministic decision circuit for L on a given instance sizen. A zk-SNARK can be used to prove and verify membershipin L, for instances of size n, as follows. After taking C as
input, a trusted party conducts a one-time setup phase that
results in two public keys: a proving key pk and a verification
key vk. The proving key pk enables any (untrusted) prover
to produce a proof π attesting to the fact that x ∈ L, for an
instance x (of size n) of his choice. The non-interactive proof
π is zero knowledge and a proof of knowledge. Anyone canuse the verification key vk to verify the proof π; in particularzk-SNARK proofs are publicly verifiable: anyone can verify π,
without ever having to interact with the prover that generated
π. Succinctness requires that (for a given security level) π hasconstant size and can be verified in time that is linear in |x|(rather than linear in |C|).

(1) We introduce the notion of a decentralized anonymous
payment scheme, which formally captures the functionality andsecurity guarantees of a full-fledged decentralized electronic
currency with strong anonymity guarantees. We provide a construction of this primitive and prove its security under specificcryptographic assumptions. The construction leverages recent
advances in the area of zero-knowledge proofs. Specifically, it
uses zero-knowledge Succinct Non-interactive ARguments ofKnowledge (zk-SNARKs) [9, 10, 11, 12, 13, 14, 15, 16].

B. Decentralized anonymous payment schemes(2) We achieve an implementation of the above primitive, viaa system that we call Zerocash. Compared to Zerocoin, oursystem (at 128 bits of security):• Reduces the size of transactions spending a coin by 97.7%.
• Reduces the spend-transaction verification time by 98.6%.
• Allows for anonymous transactions of variable amounts.
• Hides transaction amounts and the values of coins held byusers.
• Allows for payments to be made directly to a user’s fixed
address (without user interaction).
To validate our system, we measured its performance andestablished feasibility by conducting experiments in a test1
network of 1000 nodes (approximately 16of the unique IPs
1in the Bitcoin network and 3 of the nodes reachable at any
given time [17]). This inspires confidence that Zerocash canbe deployed as a fork of Bitcoin and operate at the same
scale. Thus, due to its significantly improved functionality andperformance, Zerocash makes it possible to entirely replace
traditional Bitcoin payments with anonymous alternatives.
Concurrent work. The idea of using zk-SNARKs in thesetting of Bitcoin was first presented by one of the authors
at Bitcoin 2013 [18]. In concurrent work, Danezis et al. [19]suggest using zk-SNARKs to reduce proof size and verification
time in Zerocoin; see Section IX for a comparison.
A. zk-SNARKs
We now sketch in more technical terms the definition ofa zk-SNARK; see Section II for more details. A zk-SNARK
is a non-interactive zero-knowledge proof of knowledge that460

We construct a decentralized anonymous payment (DAP)
scheme, which is a decentralized e-cash scheme that allows
direct anonymous payments of any amount. See Section III for
a formal definition. Here, we outline our construction in six
incremental steps; the construction details are in Section IV.
Our construction functions on top of any ledger-based basecurrency, 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’stransactions, as well as new transactions introduced by ourconstruction. For concreteness, we focus the discussion below
on Bitcoin (though later definitions and constructions arestated abstractly). We assume familiarity with Bitcoin [20]and Zerocoin [8].
Step 1: user anonymity with fixed-value coins. We firstdescribe a simplified construction, in which all coins havethe 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 zk-SNARKs (recalled
above) and a commitment scheme. Let COMM denote a
statistically-hiding non-interactive commitment scheme (i.e.,
given randomness r and message m, the commitment is
c := COMMr (m); subsequently, c is opened by revealingr and m, and one can verify that COMMr (m) equals c).
In the simplified construction, a new coin c is minted asfollows: a user u samples a random serial number sn and a
trapdoor r, computes a coin commitment cm := COMMr (sn),and sets c := (r, sn, cm). A corresponding mint transaction
txMint , containing cm (but not sn or r), is sent to the ledger;
txMint is appended to the ledger only if u has paid 1 BTC
to a backing escrow pool (e.g., the 1 BTC may be paid via
plaintext information encoded in txMint ). Mint transactions
are thus certificates of deposit, deriving their value from thebacking pool.
Subsequently, letting CMList denote the list of all coincommitments on the ledger, u may spend c by posting a spendtransaction txSpend that contains (i) the coin’s serial number
sn; and (ii) a zk-SNARK proof π of the NP statement “I know
r such that COMMr (sn) appears in the list CMList of coincommitments”. 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 for
himself, transfer to someone else, or immediately deposit into
a new coin. (If sn does already appear on the ledger, this isconsidered 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 txSpend isequivalent to inverting f (x) := COMMx (sn), which is assumed
to be infeasible. Thus, the origin of the payment is anonymous.

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 apk
seed x these are denoted PRFaddr(·), PRFsnxx (·), and PRFx (·).
sn
We assume that PRF is moreover collision-resistant.
To provide targets for payments, we use addresses: eachuser u generates an address key pair (apk , ask ). The coins ofu contain the value apk and can be spent only with knowledgeof ask . A key pair (apk , ask ) is sampled by selecting a random
seed ask and setting apk := PRFaddr
ask (0). A user can generate
and use any number of address key pairs.
Next, we re-design minting to allow for greater functionality.
To mint a coin c of a desired value v, the user u first samples ρ,which is a secret value that determines the coin’s serial number
as sn := PRFsn
ask (ρ). Then, u commits to the tuple (apk , v, ρ) in
two phases: (a) u computes k := COMMr (apk kρ) for a randomr; and then (b) u computes cm := COMMs (vkk) for a randoms. The minting results in a coin c := (apk , v, ρ, r, s, cm) and amint transaction txMint := (v, k, s, cm). Crucially, due to thenested commitment, anyone can verify that cm in txMint isa coin commitment of a coin of value v (by checking that
COMMs (vkk) equals cm) but cannot discern the owner (bylearning the address key apk ) or serial number (derived fromρ) because these are hidden in k. As before, txMint is acceptedby the ledger only if u deposits the correct amount, in thiscase v BTC.
Coins are spent using the pour operation, which takes a setof 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 thatoldu, with address key pair (aoldpk , ask ), wishes to consume hisoldold old old old oldcoin c = (apk , v , ρ , r , s , cmold ) and produce two
newnew coins cnew
and cnew+ v2new = v old ,1
2 , with total value v1
newrespectively targeted at address public keys anew
pk,1 and apk,2 .
new(The addresses anew
and
a
may
belong
to
u
or
to
some
pk,1
pk,2
other user.) The user u, for each i ∈ {1, 2}, proceeds as follows:(i) u samples serial number randomness ρnewi ; (ii) u computes
newnewkinew := COMMrinew (anewpk,i kρi ) for a random ri ; and (iii) u
new
new
new
new
computes cmi := COMMsi (vi kki ) for a random snewi .
new new new newThis yields the coins cnew:= (anew
,
v
,
ρ
,
r
,
s
,
1
1
1
1
1
pk,1
new
new new new new
new
cmnew
:= (anew1 ) and c2
pk,2 , v2 , ρ2 , r2 , s2 , cm2 ).
Next, u produces a zk-SNARK proof πPOUR for the following
NP statement, which we call POUR:

Step 2: compressing the list of coin commitments. In theabove NP statement, CMList is specified explicitly as a list ofcoin commitments. This naive representation severely limits
scalability because the time and space complexity of mostprotocol algorithms (e.g., the proof verification algorithm)
grows linearly with CMList. Moreover, coin commitments
corresponding to already spent coins cannot be dropped from
CMList to reduce costs, since they cannot be identified (due tothe same zero-knowledge property that provides anonymity).
As in [3], we rely on a collision-resistant hash function CRH
to avoid an explicit representation of CMList. We maintainan efficiently updatable append-only CRH-based Merkle tree
Tree(CMList) over the (growing) list CMList. Letting rt denote
the root of Tree(CMList), it is well-known that updating rt toaccount for insertion of new leaves can be done with time andspace proportional to the tree depth. Hence, the time and spacecomplexity 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 COMMr (sn) appears as
a leaf in a CRH-based Merkle tree whose root is rt”. Comparedwith the naive data structure for CMList, this modification
increases exponentially the size of CMList which a given
zk-SNARK implementation can support (concretely, using treesof depth 64, Zerocash supports 264 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
uA created c, and uA sends c to another user uB . First, sinceuA knows sn, the spending of c by uB is both not anonymous(since uA sees when c is spent, by recognizing sn) and risky(since uA could still spend c first). Thus, uB must immediately
spend c and mint a new coin c0 to protect himself. Second, if
uA in fact wants to transfer to uB , e.g., 100 BTC, then doing
so is both unwieldy (since it requires 100 transfers) and notanonymous (since the amount of the transfer is leaked). And
third, transfers in amounts that are not multiples of 1 BTC (thefixed 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

“Given the Merkle-tree root rt, serial number snold ,newand coin commitments cmnew
1 , cm2 , I know coins
old new newc , c1 , c2 , and address secret key aoldsk such that:old• The coins are well-formed: for c
it holds that k old =oldoldCOMMrold (aold= COMMsold (v old kk old );pk kρ ) and cmnewnewand similarly for c1 and c2 .
old
• The address secret key matches the public key: apk =addr
PRFaold (0).
skold• The serial number is computed correctly: sn:=
sn
PRFaold (ρold ).
skold• The coin commitment cm
appears as a leaf of a Merkle-

461

•

tree with root rt.
The values add up: v1new + v2new = v old .”A resulting pour transaction txPour := (rt, snold , cmnew
1 ,
cmnew
,
π
)
is
appendedtotheledger.
(As
before,thePOUR2transaction is rejected if the serial number sn appears in aprevious transaction.)
Now suppose that u does not know, say, the address secretnew
key anewsk,1 that is associated with the public key apk,1 . Then, u
newcannot spend cnew
becausehecannotprovidea1sk,1 as part of
the witness of a subsequent pour operation. Furthermore, whennewa user that knows anew
sk,1 does spend c1 , the user u cannot
track it, because he knows no information about its revealed
serial number, which is snnew:= PRFsn
(ρnew
anew
1
1 ).
sk,1
Also observe that txPour reveals no information about how
the value of the consumed coin was divided among the two
new fresh coins, nor which coin commitment corresponds tothe consumed coin, nor the address public keys to which thetwo new fresh coins are targeted. The payment was conductedin 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 canmint 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 newcoin with value 0. For N old > 2 or N new > 2, the user cancompose log N old + log N new of the 2-input/2-output pours.
Step 4: sending coins. Suppose that anew
pk,1 is the address public
key of u1 . In order to allow u1 to actually spend the new coincnew
produced above, u must somehow send the secret values
1
in cnew
to u1 . One way is for u to send u1 a private message,
1
but the requisite private communication channel necessitates
additional infrastructure or assumptions. We avoid this “outof-band” channel and instead build this capability directly into
our construction by leveraging the ledger as follows.
We modify the structure of an address key pair. Each
user now has a key pair (addrpk , addrsk ), where addrpk =(apk , pkenc ) and addrsk = (ask , skenc ). The values (apk , ask )are generated as before. In addition, (pkenc , skenc ) is a key pair
for a key-private encryption scheme [21].
Then, u computes the ciphertext C1 that is the encryption
new
new newof the plaintext (v1new , ρnew
1 , r1 , s1 ), under pkenc,1 (which
newis part of u1 ’s address public key addrsk,1 ), and includes C1
in the pour transaction txPour . The user u1 can then find anddecrypt this message (using his sknew
enc,1 ) by scanning the pourtransactions on the public ledger. Again, note that adding C1
to txPour leaks neither paid amounts, nor target addresses dueto the key-private property of the encryption scheme. (Theuser u does the same with cnew
and includes a corresponding
2
ciphertext C2 in txPour .)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 apublic output. When spending a coin, the user u also specifies
a nonnegative vpub and an arbitrary string info. The balance

equation in the NP statement POUR is changed accordingly:“v1new + v2new + vpub = v old ”. Thus, of the input value v old ,a part vpub 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).4 Both vpub and info are now included in the
resulting pour transaction txPour . (The public output is optional,
as the user u can set vpub = 0.)
Step 6: non-malleability. To prevent malleability attacks ona pour transaction txPour (e.g., embezzlement by re-targetingthe 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 , sksig ) for a one-time signature scheme;(ii) computes hSig := CRH(pksig ); (iii) computes the two values
h1 := PRFpk(hSig ) and h2 := PRFpk(hSig ), which act as
aold
aold
sk,1
sk,2
MACs to “tie” hSig to both address secret keys; (iv) modifies
POUR to include the three values hSig , h1 , h2 and prove thatthe latter two are computed correctly; and (v) uses sksig to sign
every value associated with the pour operation, thus obtaining
a signature σ, which is included, along with pksig , in txPour .
Since the aoldsk,i are secret, and with high probability hSig changes
for each pour transaction, the values h1 , h2 are unpredictable.
Moreover, the signature on the NP statement (and other values)
binds all of these together.
This ends the outline of the construction, which is summarizedin part in Figure 1. We conclude by noting that, due tothe zk-SNARK, our construction requires a one-time trusted
setup of public parameters. The trust affects soundness of theproofs, though anonymity continues to hold even if the setup
is corrupted by a malicious party.
C. Zerocash
We outline Zerocash, a concrete implementation, at 128
bits of security, of our DAP scheme construction; see Section V for details. Zerocash entails carefully instantiating
the cryptographic ingredients of the construction to ensurethat the zk-SNARK, the “heaviest” component, is efficientenough in practice. In the construction, the zk-SNARK isused to prove/verify a specific NP statement: POUR. While
zk-SNARKs are asymptotically efficient, their concrete efficiency depends on the arithmetic circuit C that is used todecide the NP statement. Thus, we seek instantiations for which
we can design a relatively-small arithmetic circuit CPOUR for
verifying the NP statement POUR.
Our approach is to instantiate all of the necessary cryptographic ingredients (commitment schemes, pseudorandomfunctions, and collision-resistant hashing) based on SHA256.
We first design a hand-optimized circuit for verifying SHA256
computations (or, more precisely, its compression function,
4 These public outputs can be considered as an “input” to a Bitcoin-styletransaction, where the info string contains the Bitcoin output scripts. Thismechanism also allows us to support Bitcoin’s public transaction fees.

462

(a) Merke tree over (cm1,cm2,…)
rt
CRH
CRH

(b) coinc = ((apk,pkenc), v, ρ, r, s, cm)(c) coin commitment(d) serial number

cm

sn

CRH

CRH
CRH
CRH

CRH

COMM

PRFsn

s



v
CRH

CRH

COMM

r

cm1 cm2 cm3 cm4 cm5 cm6 cm7 cm8 …

(ask,skenc) = address secret keyρCRH
PRFaddr

rt = Merkle-tree root
cm = coin commitment
sn = serial numberv = coin valuer, s = commitment rand.
ρ = serial number rand.
(apk,pkenc) = address public key



Fig. 1: (a) Illustration of the CRH-based Merkle tree over the list CMList of coin commitments. (b) A coin c. (c) Illustration of the structureof a coin commitment cm. (d) Illustration of the structure of a coin serial number sn.

which suffices for our purposes).5 Then, we use this circuit inconstructing CPOUR , which verifies all the necessary checks forsatisfying the NP statement CPOUR .
This, along with judicious parameter choices, and a state-ofthe-art implementation of a zk-SNARK for arithmetic circuits[16] (see Section II-C), results in a zk-SNARK prover running
time of few minutes and zk-SNARK verifier running time offew 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.

A. Informal definition

D. Paper organization

Definition II.1. The arithmetic circuit satisfiability problemof an F-arithmetic circuit C : Fn × Fh → Fl is captured by the
relation RC = {(x, a) ∈ Fn ×Fh : C(x, a) = 0l }; its language
is LC = {x ∈ Fn : ∃ a ∈ Fh s.t. C(x, a) = 0l }.

We informally define zk-SNARKs for arithmetic circuit
satisfiability. We refer the reader to, e.g., [11] for a formal
definition.
For a field F, an F-arithmetic circuit takes inputs that areelements in F, and its gates output elements in F. We naturally
associate a circuit with the function it computes. To model
nondeterminism 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.6 Arithmetic
circuit satisfiability is defined analogously to the boolean case,as follows.

The remainder of this paper is organized as follows.
Section II provides background on zk-SNARKs. We define
DAP schemes in Section III, and our construction thereof in
Section IV. Section V discusses the concrete instantiation in
Zerocash. Section VI describes the integration of Zerocash
into existing ledger-based currencies. Section VII provides
microbenchmarks for our prototype implementation, as well
as results based on full-network simulations. Section VIII
describes optimizations. We discuss concurrent work in Section IX and summarize our contributions and future directionsin Section X.
II. BACKGROUND ON ZK -SNARK S
The main cryptographic primitive used in this paper isa special kind of Succinct Non-interactive ARgument ofKnowledge (SNARK). Concretely, we use a publicly-verifiable
preprocessing zero-knowledge SNARK, or zk-SNARK for short.
In this section we provide basic background on zk-SNARKs,
provide an informal definition, and recall known constructions
and implementations.
5 Alternatively, we could have opted to rely on the circuit generators [13, 14,16], 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 hand-optimized construction.

Given a field F, a (publicly-verifiable preprocessing)zk-SNARK for F-arithmetic circuit satisfiability is a tripleof polynomial-time algorithms (KeyGen, Prove, Verify):
λ• KeyGen(1 , C) → (pk, vk). On input a security parameterλ (presented in unary) and an F-arithmetic circuit C, thekey 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, toprove/verify membership in LC .
• Prove(pk, x, a) → π. On input a proving key pk and any(x, a) ∈ RC , the prover Prove outputs a non-interactive
proof π for the statement x ∈ LC .
• Verify(vk, x, π) → b. On input a verification key vk, an input
x, and a proof π, the verifier Verify outputs b = 1 if he isconvinced that x ∈ LC .
A zk-SNARK satisfies the following properties.
Completeness. For every security parameter λ, any Farithmetic circuit C, and any (x, a) ∈ RC , the honest prover
6 A gate with inputs y , . . . , ym ∈ F is bilinear if the output is1
h~a, (1, y1 , . . . , ym )i · h~b, (1, y1 , . . . , ym )i for some ~a, ~b ∈ Fm+1 . These
include addition, multiplication, negation, and constant gates.

463

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, π).

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 zk-SNARKs forarithmetic circuit satisfiability as a stepping stone towards
their respective higher-level efforts. In this paper we are onlyinterested in a zk-SNARK for arithmetic circuit satisfiability,
and we rely on the implementation of [16] for such a
zk-SNARK.9 The implementation in [16] is itself based on the
protocol of Parno et al. [13]. We thus refer the interested reader
to [13] for details of the protocol, its intuition, and its proof of
security; and to [16] for the implementation and its performance.
In terms of concrete parameters, the implementation of [16]provides 128 bits of security, and the field F is of a 256-bit
prime order p.

Succinctness. An honestly-generated 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) 6∈ RC with probability negl(λ)
in the following experiment: (pk, vk) ← KeyGen(1λ , C);(x, π) ← A(pk, vk); a ← E(pk, vk).
Perfect zero knowledge. An honestly-generated proof is perfect zero knowledge.7 Namely, there is a poly(λ)-size simulator
Sim such that for all stateful poly(λ)-size distinguishers D thefollowing two probabilities are equal:• The probability that D(π) = 1 on an honest proof.

Pr 
•

(x, a) ∈ RC
D(π) = 1

III. D EFINITION OF A DECENTRALIZED ANONYMOUS
PAYMENT SCHEME

We introduce the notion of a decentralized anonymous
payment scheme (DAP scheme), extending the notion ofdecentralized e-cash [8]. Later, in Section IV, we provide
a construction.

(pk, vk) ← KeyGen(C)(x, a) ← D(pk, vk) π ← Prove(pk, x, a)

The probability that D(π) = 1 on a simulated proof.
Pr (x, a) ∈ RC
D(π) = 1

A. Data structures(pk, vk, trap) ← Sim(C)(x, a) ← D(pk, vk) π ← Sim(pk, x, trap)

We begin by describing, and giving intuition about, the data
structures used by a DAP scheme. The algorithms that use andproduce these data structures are introduced in Section III-B.

B. Known constructions and security

Basecoin ledger. Our protocol is applied on top of a ledgerbased base currency such as Bitcoin; for generality we referto this base currency as Basecoin. At any given time T , allusers have access to LT , the ledger at time T , which is asequence of transactions. The ledger is append-only (i.e., T <T 0 implies that LT is a prefix of LT 0 ).10 The transactions in
the ledger include both Basecoin transactions as well as two
new transaction types described below.

There are many zk-SNARK constructions in the literature[9, 10, 11, 12, 13, 14, 15, 16]. We are interested in zk-SNARKs
for arithmetic circuit satisfiability, and the most efficient ones
for this language are based on quadratic arithmetic programs[12, 11, 13, 14, 16]; such constructions provide a linear-time
KeyGen, quasilinear-time Prove, and linear-time Verify.
Security of zk-SNARKs is based on knowledge-of-exponent
assumptions and variants of Diffie–Hellman assumptions inbilinear groups [9, 22, 23]. While knowledge-of-exponent
assumptions are fairly strong, there is evidence that suchassumptions may be inherent for constructing zk-SNARKs[24, 25].

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 (addrpk , addrsk ). The public key addrpk is published andenables others to direct payments to the user. The secret key
addrsk is used to receive payments sent to addrpk . A user may
generate any number of address key pairs.

C. zk-SNARK implementations
There are three published implementations of zk-SNARKs:(i) Parno et al. [13] present an implementation of zk-SNARKs
for programs having no data dependencies;8 (ii) Ben-Sasson
et al. [14] present an implementation of zk-SNARKs forarbitrary programs (with data dependencies); and (iii) BenSasson et al. [16] present an implementation of zk-SNARKs

Coins. A coin is a data object c, to which we associate thefollowing:• A coin commitment, denoted cm(c): a string that appearson the ledger once c is minted.

7 While most zk-SNARK descriptions in the literature only mention statisticalzero knowledge, all zk-SNARK constructions can be made perfect zeroknowledge by allowing for a negligible error probability in completeness.
8 They only support programs where array indices are restricted to be known
compile-time constants; similarly, loop iteration counts (or at least upperbounds to these) must be known at compile time.

9 In [16], one optimization to the verifier’s runtime requires preprocessing
the verification key vk; for simplicity, we do not use this optimization.
10 In reality, the Basecoin ledger (such as the one of Bitcoin) is not perfectand may incur temporary inconsistencies. In this respect our construction isas good as the underlying ledger. We discuss the effects of this on anonymity
and mitigations in Section VI-C.

464

A coin value, denoted v(c): the denomination of c, as
measured in basecoins, as an integer between 0 and amaximum value vmax (which is a system parameter).
• A coin serial number, denoted sn(c): a unique string
associated with the c, used to prevent double spending.
• A coin address, denoted addrpk (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 txMint is a tuple(cm, v, ∗), where cm is a coin commitment, v is a coin value,and ∗ denotes other (implementation-dependent) information.
The transaction txMint records that a coin c with coincommitment cm and value v has been minted.
• Pour transactions. A pour transaction txPour is a tuple
old
new
new
(rt, snold
1 , sn2 , cm1 , cm2 , vpub , info, ∗), where rt is a rootoldof a Merkle tree, sn1 , snold
2 are two coin serial numbers,
new
cmnew
are two coin commitments, vpub is a coin
1 , cm2
value, info is an arbitrary string, and ∗ denotes other(implementation-dependent) information. The transaction
txPour records the pouring of two input (and now consumed)
old
old
old
coins cold
1 , c2 , with respective serial numbers sn1 , sn2 ,new new
into two new output coins c1 , c2 , with respective coinnewcommitments cmnew
1 , cm2 , as well as a public output vpub
(which may be zero). Furthermore, txPour also records aninformation string info (perhaps containing information on
who is the recipient of vpub basecoins) and that, when thistransaction was made, the root of the Merkle tree over coincommitments was rt (see below).
Commitments of minted coins and serial numbers of spentcoins. For any given time T ,• CMListT denotes the list of all coin commitments appearing
in mint and pour transactions in LT ;• SNListT denotes the list of all serial numbers appearing inpour transactions in LT .
While both of these lists can be deduced from LT , it will be
convenient to think about them as separate (as, in practice,these may be separately maintained due to efficiency reasons).
Merkle tree over commitments. For any given time T ,TreeT denotes a Merkle tree over CMListT and rtT its root.
Moreover, the function PathT (cm) gives the authentication
path from a coin commitment cm appearing in CMListT to
the root of TreeT .11 For convenience, we assume that LT also
stores rtT 0 for all T 0 ≤ T (i.e., it stores all past Merkle treeroots).

with the following syntax and semantics.
System setup. The algorithm Setup generates a list of publicparameters:

•

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, notrusted 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 (addrpk , addrsk )Each user generates at least one address key pair(addrpk , addrsk ) in order to receive coins. The public key addrpk
is published, while the secret key addrsk is used to redeemcoins sent to addrpk . A user may generate any number ofaddress key pairs; doing so does not require any interaction.
Minting coins. The algorithm Mint generates a coin (of agiven value) and a mint transaction:
Mint• INPUTS :– public parameters pp– coin value v ∈ {0, 1, . . . , vmax }– destination address public key addrpk• OUTPUTS : coin c and mint transaction txMint
A system parameter, vmax , caps the value of any single coin.
The output coin c has value v and coin address addrpk ; theoutput mint transaction txMint equals (cm, v, ∗), where cm isthe coin commitment of c.
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 ownershipof anonymous coins, or make public payments.12
Pour• INPUTS :– public parameters pp– the Merkle root rtold– old coins cold
1 , c2old– old addresses secret keys addrold
sk,1 , addrsk,2– authentication path path1 from commitment cm(cold1 ) toroot rt,B. Algorithms
A DAP scheme Π is a tuple of polynomial-time algorithms(Setup, CreateAddress, Mint, Pour, VerifyTransaction,
Receive)
11 While we refer to Mekle trees for simplicity, it is straightforward to extend
the definition to allow other data structures representing sets with fast insertionand short proofs of membership.

12 We consider pours with 2 inputs and 2 outputs, for simplicity and (asdiscussed in Section I-B) without loss of generality.

465

When a user with address key pair (addrpk , addrsk ) wishes toreceive payments sent to addrpk , he uses the Receive algorithm
to scan the ledger. For each payment to addrpk appearing in theledger, Receive outputs the corresponding coins whose serial
numbers do not appear on the ledger L. Coins received inthis way may be spent, just like minted coins, using the Pouralgorithm. (We only require Receive to detect coins paid to
addrpk via the Pour algorithm and not also detect coins minted
by the user himself.)authentication path path2 from commitment cm(cold2 ) toroot rt– new values v1new , v2new
new– new addresses public keys addrnew
pk,1 , addrpk,2– public value vpub
– transaction string info
new new• OUTPUTS : new coins c1 , c2
and pour transaction txPour
Thus, the Pour algorithm takes as input two distinct input
oldcoins cold
1 , c2 , along with corresponding address secret keys
oldaddrold,addr
sk,1
sk,2 (required to redeem the two input coins). To
oldensure that cold
1 , c2 have been previously minted, the Pouralgorithm also takes as input the Merkle root rt (allegedly,
equal to the root of Merkle tree over all coin commitments sofar), along with two authentication paths path1 , path2 for theoldtwo coin commitments cm(cold1 ), cm(c2 ). Two input values
new new
v1 , v2 specify the values of two new anonymous coins
newcnew
to be generated, and two input address public keys
1 , c2
new
new new
addrnew,addr
pk,1
pk,2 specify the recipients of c1 , c2 . A third
value, vpub , specifies the amount to be publicly spent (e.g.,
to redeem coins or pay transaction fees). The sum of output
values v1 + v2 + vpub must be equal to the sum of the valuesof the input coins (and cannot exceed vmax ). Finally, the Pouralgorithm also receives an arbitrary string info, which is boundinto the output pour transaction txPour .
new
The Pour algorithm outputs two new coins cnew
1 , c2and a pour transaction txPour . The transaction txPour equals
old
new
new
(rt, snold
where cmnew
1 , sn2 , cm1 , cm2 , vpub , info, ∗),
1 ,
cmnew
are
the
two
coin
commitments
of
the
two
outputcoins,
2and ∗ denotes other (implementation-dependent) information.
Crucially, txPour reveals only one currency value, the public
value vpub (which may be zero); it does not reveal the payment
addresses or values of the old or new coins.

Next, we describe completeness (Section III-C) and security(Section III-D).
C. CompletenessCompleteness of a DAP scheme requires that unspent coins
can be spent. More precisely, consider a ledger sampler S
outputting a ledger L. If c1 and c2 are two coins whose coincommitments appear in (valid) transactions on L, but theirserial numbers do not appear in L, then c1 and c2 can bespent using Pour. Namely, running Pour results in a pourtransaction txPour that VerifyTransaction accepts, and the newcoins can be received by the intended recipients (by using
Receive); moreover, txPour correctly records the intended vpub
and transaction string info. This property is formalized via an
incompleteness experiment INCOMP.
Definition III.1. A DAP scheme Π = (Setup, CreateAddress,
Mint, Pour, VerifyTransaction, Receive) is complete if nopolynomial-size ledger sampler S wins INCOMP with morethan negligible probability.
D. Security
Security of a DAP scheme is characterized by three properties, which we call ledger indistinguishability, transaction
non-malleability, and balance.

Verifying transactions. The algorithm VerifyTransaction
checks the validity of a transaction:

Definition III.2. A DAP scheme Π = (Setup, CreateAddress,
Mint, Pour, VerifyTransaction, Receive) is secure if it satisfies
ledger indistinguishability, transaction non-malleability, andbalance.

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

Below, we provide an informal overview of each property,
and defer formal definitions to the extended version of thispaper [26].
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 anaction, 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.

Both mint and pour transactions must be verified before being
considered well-formed. In practice, transactions can be verified
by the nodes in the distributed system maintaining the ledger,
as well as by users who rely on these transactions.
Receiving coins. The algorithm Receive scans the ledger andretrieves unspent coins paid to a particular user address:
Receive• INPUTS :– recipient address key pair (addrpk , addrsk )– the current ledger L• OUTPUTS : set of (unspent) received coins466

Ledger indistinguishability. This property captures therequirement that the ledger reveals no new information to
the adversary beyond the publicly-revealed information (valuesof minted coins, public values, information strings, total numberof 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 L0 and L1 , 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 identicalin terms of publicly-revealed information and the information
related to addresses controlled by A.
Ledger indistinguishability is formalized by an experiment
L-IND that proceeds as follows. First, a challenger samples arandom bit b and initializes two DAP scheme oracles O0DAP
and O1DAP , maintaining ledgers L0 and L1 . Throughout, thechallenger allows A to issue queries to O0DAP and O1DAP , thus
controlling the behavior of honest parties on L0 and L1 . The
challenger provides the adversary with the view of both ledgers,
but in randomized order: LLeft := Lb and LRight := L1−b . The
adversary’s goal is to distinguish whether the view he sees
corresponds to (LLeft , LRight ) = (L0 , L1 ), i.e. b = 0, or to(LLeft , LRight ) = (L1 , L0 ), i.e. b = 1.
At each round of the experiment, the adversary issues queries
in pairs Q, Q0 of matching query type. If the query type isCreateAddress, then the same address is generated at both
oracles. If it is to Mint, Pour or Receive, then Q is forwarded
to L0 and Q0 to L1 ; for Insert queries, query Q is forwarded
to LLeft and Q0 is forwarded to LRight . The adversary’s queries
are restricted in the sense that they must maintain the publicconsistency 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 b0 ,and wins when b = b0 . Ledger indistinguishability requires that
A wins L-IND with probability at most negligibly greater than
1/2.
Transaction non-malleability. This property requires thatno bounded adversary A can alter any of the data stored
within a (valid) pour transaction txPour . 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 non-malleability is formalized by an experiment
TR-NM, 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 , andL denote the final ledger, A wins the game if there exists
tx ∈ T , such that (i) tx∗ 6= tx; (ii) tx∗ reveals a serial number
contained in tx; and (iii) both tx and tx∗ are valid with respect
to the ledger L0 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 adifferent way.
Transaction non-malleability requires that A wins TR-NM
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 non-malleability.)
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 thenoutputs a set of coins Scoin . Letting Saddr 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) isgreater than the value he has received or mined. That is, A
wins if vUnspent + vBasecoin + vA→ADDR > vMint + vADDR→A
where: (i) vUnspent is the total value of unspent coins in Scoin ;(ii) vBasecoin is the total value of public outputs placed by A on
the ledger; (iii) vMint is the total value of A’s mint transactions;(iv) vADDR→A is the total value of payments received by A
from addresses in Saddr ; (v) vA→ADDR is the total value of
payments sent by A to addresses in Saddr .
Balance requires that A wins BAL with only negligible
probability.
IV. C ONSTRUCTION OF A DECENTRALIZED ANONYMOUS
PAYMENT SCHEME

We show how to construct a DAP scheme (introducedin Section III) using zk-SNARKs and other building blocks.
Later, in Section V, we give a concrete instantiation of thisconstruction.
A. Cryptographic building blocks
We first introduce notation for the standard cryptographic
building blocks that we use. We assume familiarity with thedefinitions of these building blocks; for more details, see, e.g.,[27]. Throughout, λ denotes the security parameter.
Collision-resistant hashing. We use a collision-resistant hashfunction CRH : {0, 1}∗ → {0, 1}O(λ) .
Pseudorandom functions. We use a pseudorandom function
family PRF = {PRFx : {0, 1}∗ → {0, 1}O(λ) }x where x denotes the seed. From PRFx , we derive three “non-overlapping”
pseudorandom functions, chosen arbitrarily as PRFaddr(z) :=x
pk
PRFx (00kz) , PRFsn
x (z) := PRFx (01kz) , PRFx (z) :=PRFx (10kz). Furthermore, we assume that PRFsn is also
collision resistant, in the sense that it is infeasible to findsn 0(x, z) 6= (x0 , z 0 ) such that PRFsn
x (z) = PRFx0 (z ).
Statistically-hiding commitments. We use a commitment
scheme COMM where the binding property holds computationally, while the hiding property holds statistically. It is
denoted {COMMx : {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 = COMMx (z).
One-time strongly-unforgeable digital signatures. We use adigital signature scheme Sig = (Gsig , Ksig , Ssig , Vsig ) that works
as follows.

467

Gsig (1λ ) → ppsig . Given a security parameter λ (presented
in unary), Gsig samples public parameters ppenc for theencryption scheme.
• Ksig (ppsig ) → (pksig , sksig ). Given public parameters ppsig ,Ksig samples a public key and a secret key for a single user.
• Ssig (sksig , m) → σ. Given a secret key sksig and a messagem, Ssig signs m to obtain a signature σ.
• Vsig (pksig , m, σ) → b. Given a public key pksig , message m,and signature σ, Vsig 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
one-time strong unforgeability against chosen-message attacks(SUF-1CMA security).
Key-private public-key encryption. We use a public-key
encryption scheme Enc = (Genc , Kenc , Eenc , Denc ) that works
as follows.
λ• Genc (1 ) → ppenc . Given a security parameter λ (presented
in unary), Genc samples public parameters ppenc for theencryption scheme.
• Kenc (ppenc ) → (pkenc , skenc ). Given public parameters ppenc ,Kenc samples a public key and a secret key for a single user.
• Eenc (pkenc , m) → c. Given a public key pkenc and a message
m, Eenc encrypts m to obtain a ciphertext c.
• Denc (skenc , c) → m. Given a secret key skenc and a ciphertext
c, Denc decrypts c to produce a message m (or ⊥ if
decryption fails).
The encryption scheme Enc satisfies two security properties:(i) ciphertext indistinguishability under chosen-ciphertext attack(IND-CCA security); and (ii) key indistinguishability underchosen-ciphertext attack (IK-CCA security). While the first
property is standard, the second is less known; informally,
IK-CCA requires that ciphertexts cannot be linked to the public
key used to encrypt them, or to other ciphertexts encryptedwith the same public key. For definitions, we refer the reader
to [21].
•B. zk-SNARKs for pouring coins
As outlined in Section I-B, our construction invokes a
zk-SNARK for a specific NP statement, POUR, which we now
define. We first recall the context motivating POUR. When aold
new new
user u pours “old” coins cold
1 , c2 into new coins c1 , c2 ,a corresponding pour transaction

old
new
new
Instances are of the form ~x = (rt, snold
1 , sn2 , cm1 , cm2 ,vpub , hSig , h1 , h2 ). Thus, an instance ~x specifies a root rt for
a CRH-based Merkle tree (over the list of commitments sofar), the two serial numbers of the consumed coins, two coincommitments for the two new coins, a public value, andfields hSig , h1 , h2 used for non-malleability.
old• Witnesses are of the form ~a = (path1 , path2 , cold
1 , c2 ,oldold
new new
addrsk,1 , addrsk,2 , c1 , c2 ) where, for each i ∈ {1, 2}:•old
old old old oldoldcold
i = (addrpk,i , vi , ρi , ri , si , cmi ) ,new new new newnewcnew= (addrnew
i
pk,i , vi , ρi , ri , si , cmi )for the same cmnew
as in ~x,i
old
old
addrold
pk,i = (apk,i , pkenc,i ) ,newnew
addrnew
pk,i = (apk,i , pkenc,i ) ,oldoldaddroldsk,i = (ask,i , skenc,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 thefollowing holds:
1) For each i ∈ {1, 2}:a) The coin commitment cmoldof cold
appears on theiiledger, i.e., pathi is a valid authentication path forleaf cmoldwith respect to root rt, in a CRH-basedi
Merkle tree.
b) The address secret key aoldsk,i matches the address publicoldold
key of ci , i.e., apk,i = PRFaddr
(0).
aold
sk,i
old
c) The serial number snoldofciscomputed correctly,
i
i
sn
old
i.e., snold
=
PRF
(ρ
).
old
i
ask,i id) The coin cold
is well-formed, i.e., cmold
=
i
i
old
old
old
COMMsold
(COMM
kρ
)kv
).
old (a
r
i
i
pk,i
i
i
e) The coin cnew
is well-formed, i.e., cmnew
=
i
i
new
new
new
new (aCOMMsnew
(COMM
kρ
)kv
).
r
i
i
pk,i
i
i
f) The address secret key aoldsk,i ties hSig to hi , i.e., hi =PRFpk
(hSig ).
aold
sk,i

old
new
new
txPour = (rt, snold
1 , sn2 , cm1 , cm2 , vpub , info, ∗)is generated. In our construction, we need to provide evidence in“∗” that various conditions were respected by the pour operation.
oldConcretely, txPour should demonstrate that (i) u owns cold
1 , c2 ;old old(ii) coin commitments for c1 , c2 appear somewhere on theoldledger; (iii) the revealed serial numbers snold
are of
1 , sn2old old
newc1 , c2 ; (iv) the revealed coin commitments cm1 , cmnew
2new
are of cnew
1 , c2 ; (v) balance is preserved. Our construction
achieves this by including a zk-SNARK proof πPOUR for thestatement POUR which checks the above invariants (as well asothers needed for non-malleability).
The statement POUR. Concretely, the NP statement POUR
is defined as follows.

4682) Balance is preserved: v1new + v2new + vpub = v1old + v2old (with
v1old , v2old ≥ 0 and v1old + v2old ≤ vmax ).
Recall that in this paper zk-SNARKs are relative to thelanguage of arithmetic circuit satisfiability (see Section II);
thus, we express the checks in POUR via an arithmetic circuit,denoted CPOUR . In particular, the depth dtree of the Merkle
tree needs to be hardcoded in CPOUR , and we thus make ita parameter of our construction (see below); the maximum
number of supported coins is then 2dtree .
C. Algorithm constructions
We proceed to describe the construction of the DAP schemeΠ = (Setup, CreateAddress, Mint, Pour, VerifyTransaction,
Receive) whose intuition was given in Section I-B. Figure 2
gives the pseudocode for each one of the six algorithms in Π,
in terms of the building blocks introduced in Section IV-A and
Section IV-B. In the construction, we hardcode two quantities:

SetupPour• INPUTS : security parameter λ• OUTPUTS : public parameters pp• INPUTS :– public parameters pp– the Merkle root rtold– old coins cold
1 , c2old– old addresses secret keys addrold
sk,1 , addrsk,2old– path path1 from commitment cm(c1 ) to root rt,path path2 from commitment cm(cold2 ) to root rt– new values v1new , v2new
new– new addresses public keys addrpk,1 , addrnew
pk,2– public value vpub
– transaction string info
new and pour transaction tx• OUTPUTS : new coins cnew
Pour
1 , c2
1) For each i ∈ {1, 2}:
old
old
old
old
old
old
old
a) Parse ci as (addrpk,i , vi , ρi , ri , si , cmi ).
oldoldb) Parse addrold
sk,i as (ask,i , skenc,i ).
snoldc) Compute sni := PRFaold (ρoldi ).

1) Construct CPOUR for POUR at security λ.
2) Compute (pkPOUR , vkPOUR ) := KeyGen(1λ , CPOUR ).
3) Compute ppenc := Genc (1λ ).
4) Compute ppsig := Gsig (1λ ).
5) Set pp := (pkPOUR , vkPOUR , ppenc , ppsig ).
6) Output pp.
CreateAddress• INPUTS : public parameters pp• OUTPUTS : address key pair (addrpk , addrsk )1) Compute (pkenc , skenc ) := Kenc (ppenc ).
2) Randomly sample a PRFaddr seed ask .
3) Compute apk = PRFaddr
ask (0).
4) Set addrpk := (apk , pkenc ).
5) Set addrsk := (ask , skenc ).
6) Output (addrpk , addrsk ).

sk,i

new
new
d) Parse addrnew
pk,i as (apk,i , pkenc,i ).
e) Randomly sample a PRFsn seed ρnewi .
f) Randomly sample two COMM trapdoors rinew , snewi .
newg) Compute kinew := COMMrinew (anewpk,i kρi ).
h) Compute cmnew:= COMMsnew(vinew kkinew ).
iinewnew , ρnew , r new , snew , cmnew ).
i) Set cnew
:=
(addr
,
v
pk,i ii
i
i
i
i
new new new newj) Set Ci := Eenc (pknew
enc,i , (vi , ρi , ri , si )).
2) Generate (pksig , sksig ) := Ksig (ppsig ).
3) Compute hSig := CRH(pksig ).
4) Compute h1 := PRFpkold (hSig ) and h2 := PRFpkold (hSig ).

Mint• INPUTS :– public parameters pp– coin value v ∈ {0, 1, . . . , vmax }– destination address public key addrpk• OUTPUTS : coin c and mint transaction txMint
1) Parse addrpk as (apk , pkenc ).
2) Randomly sample a PRFsn seed ρ.
3) Randomly sample two COMM trapdoors r, s.
4) Compute k := COMMr (apk kρ).
5) Compute cm := COMMs (vkk).
6) Set c := (addrpk , v, ρ, r, s, cm).
7) Set txMint := (cm, v, ∗), where ∗ := (k, s).
8) Output c and txMint .

ask,1VerifyTransaction• 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 = txMint :a) Parse txMint as (cm, v, ∗), and ∗ as (k, s).
b) Set cm0 := COMMs (vkk).
c) Output b := 1 if cm = cm0 , else output b := 0.
2) If given a pour transaction tx = txPour :
old
new
new
a) Parse txPour as (rt, snold
1 , sn2 , cm1 , cm2 , vpub , info, ∗), and ∗ as
(pksig , h1 , h2 , πPOUR , C1 , C2 , σ).
old
old
old
b) If snold
1 or sn2 appears on L (or sn1 = sn2 ), output b := 0.
c) If the Merkle root rt does not appear on L, output b := 0.
d) Compute hSig := CRH(pksig ).
old
new
new
e) Set ~x := (rt, snold
1 , sn2 , cm1 , cm2 , vpub , hSig , h1 , h2 ).
f) Set m := (~x, πPOUR , info, C1 , C2 )g) Compute b := Vsig (pksig , m, σ).
h) Compute b0 := Verify(vkPOUR , ~x, πPOUR ), and output b ∧ b0 .

ask,2

old
new
new
5) Set ~x := (rt, snold
1 , sn2 , cm1 , cm2 , vpub , hSig , h1 , h2 ).
old , addrold , addrold , cnew , cnew ).
6) Set ~a := (path1 , path2 , cold
,
c
1
2
2
sk,1
sk,2 1
7) Compute πPOUR := Prove(pkPOUR , ~x, ~a).
8) Set m := (~x, πPOUR , info, C1 , C2 ).
9) Compute σ := Ssig (sksig , m).
old
new
new
10) Set txPour := (rt, snold
1 , sn2 , cm1 , cm2 , vpub , info, ∗), where∗ := (pksig , h1 , h2 , πPOUR , C1 , C2 , σ).
new and tx11) Output cnew
Pour .
1 , c2

Receive• INPUTS :– public parameters pp– recipient address key pair (addrpk , addrsk )– the current ledger L• OUTPUTS : set of received coins
1) Parse addrpk as (apk , pkenc ).
2) Parse addrsk as (ask , skenc ).
3) For each Pour transaction txPour on the ledger:
old
new
new
a) Parse txPour as (rt, snold
1 , sn2 , cm1 , cm2 , vpub , info, ∗),and ∗ as (pksig , h1 , h2 , πPOUR , C1 , C2 , σ).
b) For each i ∈ {1, 2}:i) Compute (vi , ρi , ri , si ) := Denc (skenc , Ci ).
ii) If Denc ’s output is not ⊥, verify that:• cmnew
equals COMMsi (vi kCOMMri (apk kρi ));isn• sni := PRFa (ρi ) does not appear on L.
skiii) If both checks succeed, output
ci := (addrpk , vi , ρi , ri , si , cmnew
i ).

Fig. 2: Construction of a DAP scheme using zk-SNARKs and other ingredients.

the maximum value of a coin, vmax , and the depth of the
Merkle tree, dtree .

is a complete (cf. Definition III.1) and secure (cf. Definition III.2) DAP scheme.

D. Completeness and security

We provide a proof of Theorem IV.1 in the extended version ofthis paper [26]. We note that our construction can be modified toyield statistical (i.e., everlasting) anonymity; see the discussion
in the extension section of the full version of this paper.

Our main theorem states that the above construction is indeed
a DAP scheme.
Theorem IV.1. The tuple Π = (Setup, CreateAddress, Mint,
Pour, VerifyTransaction, Receive), as defined in Section IV-C,

Remark (trusted setup). Security of Π relies on a trusted party469

running Setup to generate the public parameters (once and forall). This trust is needed for the transaction non-malleability
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.

CRH, PRF, COMM from SHA256. Let H be the SHA256
compression function, which maps a 512-bit input to a 256bit output. We mostly rely on H, rather than the “full”
hash, since this suffices for our fixed-size single-block inputs,
and it simplifies the construction of CPOUR . We instantiate
CRH, PRF, COMM via H (under suitable assumptions on H).
First, we instantiate the collision-resistant hash function CRH
as H(z) for z ∈ {0, 1}512 ; this function compresses “two-toone”, so it can be used to construct binary Merkle trees.13
Next, we instantiate the pseudorandom function PRFx (z) as
H(xkz), with x ∈ {0, 1}256 as the seed, and z ∈ {0, 1}256 as
the input.14 Thus, the derived functions are PRFaddr(z) :=xpk
H(xk00kz), PRFsn
x (z) := H(xk01kz) and PRFx (z) :=H(xk10kz), with x ∈ {0, 1}256 and z ∈ {0, 1}254 .
As for the commitment scheme COMM, we only use it in
the following pattern:

above we are ignoring the commitment randomness s. The
reason is that we already know that k, being the output of astatistically-hiding commitment, can serve as randomness forthe next commitment scheme.
Instantiating the NP statement POUR. The above choices
imply a concrete instantiation of the NP statement POUR
(see Section IV-B). Specifically, in our implementation, POUR
checks that the following holds, for each i ∈ {1, 2}:old• pathi is an authentication path for leaf cmi
with respect
to root rt, in a CRH-based Merkle tree;
old
old
256
• apk,i = H(ask,i k0
);
old
old
old
• sni = H(ask,i k01k[ρi ]254 );
old
old
old
old
192
• cmi = H(H(ri k[H(apk,i kρi )]128 )k0
kviold );
new
new
new
new
192
• cmi
= H(H(ri k[H(apk,i kρi )]128 )k0 kvinew ); andold• hi = H(ask,i k10k[hSig ]254 ).
Moreover, POUR checks that v1new + v2new + vpub = v1old + v2old ,with v1old , v2old ≥ 0 and v1old + v2old < 264 .
Finally, as mentioned, in order for CPOUR to be well-defined,
we need to fix a Merkle tree depth dtree . In our implementation,
we fix dtree = 64, and thus support up to 264 coins.
Instantiating Sig. For the signature scheme Sig, we use
ECDSA to retain consistency and compatibility with theexisting bitcoind source code. However, standard ECDSA ismalleable: both (r, s) and (r, −s) verify as valid signatures. We
use a non-malleable variant, where s is restricted to the “lower
half” of field elements. While we are not aware of a formal
SUF-CMA proof for this variant, its use is consistent withproposals to resolve Bitcoin transaction malleability [29].15
Instantiating Enc. For the encryption scheme Enc, we use
the key-private Elliptic-Curve Integrated Encryption Scheme(ECIES) [30, 31]; it is one of the few standardized key-private
encryption schemes with available implementations.
For further details about efficiently realizing these in thearithmetic circuit for POUR, see the full version of this paper.

k := COMMr (apk kρ)VI. I NTEGRATION WITH EXISTING LEDGER - BASED

V. Z EROCASHWe describe a concrete instantiation of a DAP scheme; thisinstantiation forms the basis of Zerocash. Later, in Section VI,
we discuss how Zerocash can be integrated with existing ledgerbased currencies.
A. Instantiation of building blocks
We instantiate the DAP scheme construction from Section IV(see Figure 2), aiming at a level of security of 128 bits. Doingso requires concrete choices, described next.

CURRENCIES

cm := COMMs (vkk)

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 unitof 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,a.k.a. “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 newsoftware, we neither expect nor advise such integration in thenear future and suggest using Zerocash in a separate altcoin.

Due to our instantiation of PRF, apk is 256 bits. So we canset ρ also to 256 bits and r to 256 + 128 = 384 bits; then wecan compute k := COMMr (apk kρ) as H(rk[H(apk kρ)]128 ).
Above, [·]128 denotes that we are truncating the 256-bit string
to 128 bits (say, by dropping least-significant bits, as in our
implementation). Heuristically, for any string x ∈ {0, 1}128 ,the distribution induced by H(rkx) is 2−128 -close to uniform,
and this forms the basis of the statistically-hiding property. For
computing cm, we set coin values to be 64-bit integers (so that,in particular, vmax = 264 − 1 in our implementation), and thencompute cm := COMMs (vkk) as H(kk0192 kv). Noticeably,
13 A single exception: we still compute h
Sig according to the full hash
SHA256, rather than its compression function, because there is no need forthis computation to be verified by CPOUR .
14 This assumption is reminiscent of previous works analyzing the securityof hash-based constructions (e.g., [28]). However in this work we assume
that a portion of the compression function is the seed for the pseudorandomfunction, rather than using the chaining variable as in [28].

15 In practice, one might replace this ECDSA variant with an EC-Schnorr
signature satisfying SUF-CMA security with proper encoding of EC groupelements; the performance would be similar.

470

Integrating Zerocash into Bitcoin consists of adding a newtransaction type, Zerocash transactions, and modifying theprotocol and software to invoke Zerocash’s DAP interface tocreate and verify these transactions. Two approaches to doing
so are described next, followed by a discussion of anonymizing
the network layer.
A. Integration by replacing the base currency

fabricate an additional block solely for a targeted user. Spending
any coins with respect to the updated Merkle tree in this“poison-pill” 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).
VII. E XPERIMENTS

One approach is to alter the underlying system so that
all monetary transactions are done using Zerocash, i.e., byinvoking the DAP interface and writing/reading the associatedtransactions in the distributed ledger.
As seen in Section III, this suffices to offer the corefunctionality of payments, minting, merging, splitting, etc.,
while assuring users that all transactions using this currency
are anonymous. However, this has several drawbacks: alltransactions incur the cost of generating a zk-SNARK proof;
the scripting feature of Bitcoin is lost; and Bitcoin’s ability tospend unconfirmed transactions is lost.

To measure the performance of Zerocash, we ran several
experiments. First, we benchmarked the performance of thezk-SNARK for the NP statement POUR (Section VII-A) andof the six DAP scheme algorithms (Section VII-B). Second,
we studied the impact of a higher block verification time via asimulation of a Bitcoin network (Section VII-C).
A. Performance of zk-SNARKs for pouring coins
Our zk-SNARK for the NP statement POUR is obtained byconstructing an arithmetic circuit CPOUR for verifying POUR,
and then invoking the generic implementation of zk-SNARK
for arithmetic circuit satisfiability of [16] (see Section II-C).
The arithmetic circuit CPOUR is built from scratch and handoptimized to exploit nondeterministic verification and the large
field characteristic.
Figure 3 reports performance characteristics of the resulting
zk-SNARK for POUR. This includes three settings: singlethread performance on a laptop machine; and single-thread
and multi-thread performance on a desktop machine. (Thetime measurements are the average of 10 runs, with standard
deviation under 2.5%.)

B. 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 Bitcoin-styletransactions, containing inputs and outputs [20]. Each input iseither a pointer to an output of a previous transaction (as in plain
Bitcoin), or a Zerocash pour transaction (which contributes its
public value, vpub , of bitcoins to this transaction). Outputs
are either an amount and destination public address/script(as in plain 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’ vpub ) mustbe 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.

B. Performance of Zerocash algorithms
In Figure 4 we report performance characteristics for eachof the six DAP scheme algorithms in our implementation. Notethat these numbers do not include the costs of maintaining the
Merkle tree because doing so is not the responsibility of thesealgorithms. Moreover, for VerifyTransaction, we separately
report the cost of verifying mint and pour transactions and, inthe latter case, we exclude the cost of scanning L (as this costdepends on L). Finally, for the case of Receive, we report thecost to process a given pour transaction in L.

C. Additional anonymity considerations

C. Large-scale network simulation

Zerocash only anonymizes the transaction ledger. Network
traffic used to announce transactions, retrieve blocks, andcontact merchants will still leak identifying information (e.g.,
IP addresses). Thus users need some anonymity network tosafely use Zerocash. The most obvious way to do this is via
Tor [32]. Given that Zerocash transactions are not low latency
themselves, Mixnets (e.g., Mixminion [33]) are also a viable
way to add anonymity (and one that is not as vulnerable totraffic analysis as Tor). Using mixnets that provide email-likefunctionality has the added benefit of providing an out-of-band
notification mechanism as a replacement to Receive.
Additionally, although in theory all users have a single
view of the block chain, a powerful attacker could potentially

Because Bitcoin mining typically takes place on dedicatedGPUs 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: theVerifyTransaction 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 can 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 thetransaction are verified. Verifying a block consists of checking
the proof of work and validating the contained transactions.

471

KeyGenProve
VerifyTime
Proving key
Verification key
Time
Proof
Time

Intel
Core i7-2620M@ 2.70GHz
12GB of RAM
1 thread
7 min 48 s

2 min 55 s
8.5 msIntel Core i7-4770 @ 3.40GHz with 16GB of RAM (1 thread)
Setup
Time
5 min 17 s
pp
896 MiB
CreateAddressTime
326.0 ms
addrpk
343 B
addrsk
319 B
Mint
Time
23 µs
Coin c463 B
txMint
72 B
Pour
Time
2 min 2.01 s
txPour996 B16
VerifyTransactionmint
8.3 µspour (excludes L scan)
5.7 ms
Receive
Time (per pour tx)
1.6 msIntel
Core i7-4770@ 3.40GHz
16GB of RAM
1 thread
8 threads
5 min 17 s
4 min 11 s
896 MiB
749 B
2 min 2 s
1 min 3 s
288 B
5.4 msFig. 3: Performance of our zk-SNARK for the NP statement POUR.
(N = 10, σ ≤ 2.5%)

Fig. 4: Performance of Zerocash algorithms.
(N = 10, σ ≤ 2.5%17 )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 firstissue, the potential impact of the second issue is cause forgreater 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 CPU-cycles mining on out-of-date
blocks, reducing the computational power of the network andmaking it easier to mount a “51% attack” (dishonest majorityof miners) on the distributed ledger.
It is a priori unclear whether this potential issue is areal concern. Bitcoin caches transaction verifications, so atransaction that was already verified when it propagated throughthe 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 thetime 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.

nodes on one virtualized server.
The frequency of new blocks can be modeled as a Poissonprocess with a mean of Λblock seconds. To generate blocks
stochastically, we modify bitcoind to fix its block difficulty
at a trivial level 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 vs. 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.18
Otherwise transactions are processed as specified by the Bitcoin
protocol. We vary the amount of simulated Zerocash traffic byvarying the number of transactions with this particular output
amount. This minimizes code changes and estimates only thegeneric impact of verification delays and not of any specificimplementation choice.
Methodology. Recent research [17] 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 [34].
In our simulation, we use a 1000-node 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  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).

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 theleast amount of hardware. This raises two issues. First, reducing
the proof of work to practical levels while still preserving arealistic rate of new blocks is difficult (especially on virtualized
hardware with variable performance). Second, the overhead of
zk-SNARK verification prevents us from running many Bitcoin
16 346 B of this are due to the ciphertexts C , C . Future implementations
1
2
may significantly reduce this overhead or discard these (cf. Section VI-C).
17 We note that σ for both Mint and VerifyTransaction (mint) is higher
than 2.5% due to the variability at such short timescales. Respectively, it is
3.3 µs and 1.9 µs.

18 Subsequent optimizations lowered the cost of VerifyTransaction below
this, after our experiments.

472

200

4.5

80

180

4

70

160

3.5

120
100
80
60

60

time in milliseconds

time in seconds

time in seconds

140

3
2.5
2
1.5

0.5

20
0
0%

Zerocash
20%

40%

60%

80%

100%

0
0%

30

10

last node
every node
20%

40%

ε

(a) Transaction latency

40

20

1

40

50

60%

80%

100%

0
0%

Zerocash
20%

40%

ε

60%

80%

100%

ε

(b) Block propagation time(c) Block verification time

Fig. 5: The average values of the three metrics we study, as a function of , the percentage of transactions that are Zerocash transactions. Note
that, in (a), latency is undefined when  = 0 and hence omitted.

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.

We run our simulation for different traffic mixes, where indicates the percentage of Zerocash transactions and  ∈{0%, 25%, 50%, 75%, 100%}. Each simulation is run on 200
Amazon EC2 general-purpose m1.medium instances, in one
region on a 10.10./16 private network. On each instance,
we deploy 5 instances of bitcoind.
Results. Transactions are triggered by a blocking function callon 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 thenode actuals sends the transactions, the actual transaction rateis 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 5 we plot three metrics for  ∈ {0%, 25%, 50%,
75%, 100%}. Each is the average defined over the data fromthe entire run of the simulation for a given  (i.e., they include
multiple transactions and blocks).19 Transaction latency is theinterval between a transaction’s creation and its inclusion ina 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 noteffective, 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 non-cached Zerocashtransactions. Instead, we see worst case 80 ms and conclude
caching is effective. This results in a negligible effect on blockpropagation (likely because network operations dominate).
The time needed for a transaction to be confirmed, and hence

VIII. O PTIMIZATIONS AND EXTENSIONS
See the extended version of this paper [26] for extensions
on everlasting anonymity, batched Merkle tree updates, fasterblock propagation, and scaling to 264 serial numbers.
IX. C ONCURRENT WORK
Danezis et al. [19] suggest using zk-SNARKs to reduce
proof size and verification time in Zerocoin. Our work differsfrom [19] in both supported functionality and scalability.
First, [19]’s protocol, like Zerocoin, only supports fixed-value
coins, and is best viewed as a decentralized mix. Instead, we
define, construct, and implement a full-fledged decentralized
electronic currency, which provides anonymous payments ofany amount.
Second, in [19], the complexity of the zk-SNARK generator,
prover, and verifier all scale superlinearly in the number ofcoins, 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 ourconstruction, the respective complexities are polylogarithmic,
polylogarithmic, and constant in the number of coins; ourapproach supports a practically-unbounded number of coins.
X. C ONCLUSION
Decentralized currencies should ensure a user’s privacy fromhis peers when conducting legitimate financial transactions.
Zerocash provides such privacy protection, by hiding user
identities, transaction amounts, and account balances frompublic view. This, however, may be criticized for hampering
accountability, regulation, and oversight. Yet, Zerocash neednot be limited to enforcing the basic monetary invariants ofa currency system. The underlying zk-SNARK cryptographic
proof machinery is flexible enough to support a wide range ofpolicies. 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

19 Because our simulated Bitcoin nodes ran on shared EC2 instances, they
were subject to variable external load, limiting the benchmark precision. Still, it
clearly demonstrates that the mild additional delay does not cause catastrophic
network effects.

473

as the policy can be specified by efficient nondeterministic
computation using NP statements, it can (in principle) be
enforced using zk-SNARKs, and added to Zerocash. Thiscan enable privacy-preserving verification and enforcementof a wide range of compliance and regulatory policies thatwould otherwise be invasive to check directly or might bebypassed by corrupt authorities. This raises research, policy,
and engineering questions over what policies are desirable andpractically realizable.
Another research question is what new functionality canbe realized by augmenting the capabilities already present in
Bitcoin’s scripting language with zk-SNARKs that allow fast
verification of expressive statements.

[10] H. Lipmaa, “Progression-free sets and sublinear pairing-based noninteractive zero-knowledge arguments,” in TCC ’12.
[11] N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, and O. Paneth, “Succinct
non-interactive arguments via linear interactive proofs,” in TCC ’13.
[12] R. Gennaro, C. Gentry, B. Parno, and M. Raykova, “Quadratic span
programs and succinct NIZKs without PCPs,” in EUROCRYPT ’13.
[13] B. Parno, C. Gentry, J. Howell, and M. Raykova, “Pinocchio: nearly
practical verifiable computation,” in Oakland ’13.
[14] E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza, “SNARKs
for C: verifying program executions succinctly and in zero knowledge,”in CRYPTO ’13.
[15] H. Lipmaa, “Succinct non-interactive zero knowledge arguments fromspan programs and linear error-correcting codes,” in ASIACRYPT ’13.
[16] E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza, “Succinct noninteractive arguments for a von Neumann architecture,” ePrint 2013/879.
[17] C. Decker and R. Wattenhofer, “Information propagation in the Bitcoin
network,” in P2P ’13.
[18] E. Ben-Sasson, “Universal and affordable computational integrity,” May
2013, bitcoin 2013: The Future of Payments. [Online]. Available:
http://www.youtube.com/watch?v=YRcPReUpkcU[19] G. Danezis, C. Fournet, M. Kohlweiss, and B. Parno, “Pinocchio
Coin: building Zerocoin from a succinct pairing-based proof system,”in PETShop ’13. [Online]. Available: http://www0.cs.ucl.ac.uk/staff/G.
Danezis/papers/DanezisFournetKohlweissParno13.pdf[20] S. Nakamoto, “Bitcoin: a peer-to-peer electronic cash system,” 2009.
[Online]. Available: http://www.bitcoin.org/bitcoin.pdf[21] M. Bellare, A. Boldyreva, A. Desai, and D. Pointcheval, “Key-privacy
in public-key encryption,” in ASIACRYPT ’01.
[22] D. Boneh and X. Boyen, “Secure identity based encryption without
random oracles,” in CRYPTO ’04.
[23] R. Gennaro, “Multi-trapdoor commitments and their applications toproofs of knowledge secure under concurrent man-in-the-middle attacks,”
in CRYPTO ’04.
[24] C. Gentry and D. Wichs, “Separating succinct non-interactive argumentsfrom all falsifiable assumptions,” in STOC ’11.
[25] N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer, “From extractable
collision resistance to succinct non-interactive arguments of knowledge,
and back again,” in ITCS ’12.
[26] E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and
M. Virza, “Zerocash: Decentralized anonymous payments from Bitcoin(extended version),” Cryptology ePrint Archive, 2014.
[27] J. Katz and Y. Lindell, Introduction to Modern Cryptography. Chapman& Hall/CRC, 2007.
[28] M. Bellare, “New proofs for NMAC and HMAC: security without
collision-resistance,” in CRYPTO ’06.
[29] P. Wuille, “Proposed BIP for dealing with malleability,” Available athttps://gist.github.com/sipa/8907691, 2014.
[30] V. Shoup, “A proposal for an ISO standard for public key encryption(version 2.1),” IACR E-Print Archive, 2001.
[31] Certicom Research, “SEC 1: Elliptic curve cryptography,” 2000. [Online].
Available: http://www.secg.org/collateral/sec1 final.pdf[32] R. Dingledine, N. Mathewson, and P. Syverson, “Tor: the secondgeneration onion router,” in Security ’04.
[33] G. Danezis, R. Dingledine, and N. Mathewson, “Mixminion: design ofa type III anonymous remailer protocol,” in SP ’03.
[34] T. B. Lee, “Bitcoin needs to scale by a factor of 1000 to competewith Visa. here’s how to do it.” The Washington Post (http://www.
washingtonpost.com), November 2013.

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 Ben-Tov and the SCIPR
Lab members — Daniel Genkin, Lior Greenblat, Shaul Kfir,
Gil Timnat and Michael Riabzev — for inspiring discussions.
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 CCF-0939370; 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 FA875011-2-0211; the European Community’s Seventh Framework
Programme (FP7/2007-2013) under grant agreement number
240258; the Israeli Centers of Research Excellence I-CORE
program (center 4/11); the Israeli Ministry of Science andTechnology; the Office of Naval Research under contract
N00014-11-1-0470; the Simons Foundation, with a SimonsAward for Graduate Students in Theoretical Computer Science;and the Skolkovo Foundation under grant agreement 6926059.
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.
R EFERENCES[1] D. Chaum, “Blind signatures for untraceable payments,” in CRYPTO’82.
[2] J. Camenisch, S. Hohenberger, and A. Lysyanskaya, “Compact e-cash,”in EUROCRYPT ’05.
[3] T. Sander and A. Ta-Shma, “Auditable, anonymous electronic cash,” in
CRYPTO ’99.
[4] F. Reid and H. Martin, “An analysis of anonymity in the Bitcoin system,”in SocialCom/PASSAT ’11.
[5] S. Barber, X. Boyen, E. Shi, and E. Uzun, “Bitter to better - how tomake Bitcoin a better currency,” in FC ’12.
[6] D. Ron and A. Shamir, “Quantitative analysis of the full Bitcointransaction graph,” ePrint 2012/584, 2012.
[7] G. Maxwell, “CoinJoin: Bitcoin privacy for the real world,” August
2013, bitcoin Forum. [Online]. Available: https://bitcointalk.org/index.
php?topic=279249.0[8] I. Miers, C. Garman, M. Green, and A. D. Rubin, “Zerocoin: Anonymous
distributed e-cash from bitcoin,” in SP ’13.
[9] J. Groth, “Short pairing-based non-interactive zero-knowledge arguments,”
in ASIACRYPT ’10.

474