lic transaction information p. Next,
Alice must sign the transaction in
a way that proves her ownership of
the funds being transferred but does
not reveal her identity. Indeed, in
order to do this Alice signs the transaction using the one-time secret key
skA,r′ established during the transaction through which she originally acquired the funds. While this proves
Alice’s ownership over the transferred
funds (since Alice is the only one that
knows skA,r′, using regular digital signatures for the signature would trivially link the two transactions.
To prevent such leakage, CryptoNote
uses ring signatures12 to verify that a specific message was signed by some user
belonging to a group of users, without
revealing the signer’s specific identity.
Thus, Alice creates a transaction (which
includes pkB,r as well as additional information p that will allow Bob to recover
skB,r′ and choses some set of public keys
PK which includes pkA,r from the public
ledger. Alice then signs the transaction
using skA,r ′ and publishes the transaction and PK on a public ledger, thereby
proving her ownership over the coin.
Due to the hiding property of ring signatures, the signature may have originated
from any of the users in PK. Thus, Alice
is able to control the anonymity level of
her transaction with Bob by simply varying the size of the set PK.
Zero-knowledge transactions: Zerocoin. As described earlier, the anonymity level provided by CryptoNote
is directly related to the size of the set
PK. However, the size of PK also affects
the amount of work required by Alice
in order to perform a transaction, thus
hampering the performance of the
cryptocurrency. Alleviating this issue,
Zerocoin25 uses a different approach
that decouples the amount of work required by Alice from the achieved level
of anonymity. Zerocoin works as an
“overlay” over the Bitcoin protocol as
follows: Assume Alice wishes to spend
a (predetermined) number of bitcoins
privately, without revealing her identity. The first step she takes is to mint
a zerocoin by generating a random serial number S and by creating a commitment c to S using randomness r.
Alice then publishes a transaction (for
the amount she wishes to spend) from
her address using c as destination (at
this point, c can be seen as being held
in escrow). The commitment c is then
added by the network to a global, pub-
licly visible set C of minted coins.
When Alice wishes to spend her new
zerocoin, she creates a noninteractive
zero-knowledge-proof-of-knowledge
(NIZKPoK) 35,g proof π of the statement “S
is a valid opening to some commitment
on an unspent zerocoin currently being
held in escrow.” Next, Alice publishes a
transaction with Bob’s address as desti-
nation and with an empty origin address
containing π and S. At this point, due to
the zero-knowledge property of π, there
is no way to link Alice to any specific ze-
rocoin commitment c.h The network ac-
cepts this transaction published by Alice
only if the validation of π succeeds and
S has not been previously spent. In this
case, participants add S to the list of pre-
viously spent coins (see Figure 4).
Practical considerations. To mini-
mize the size of the proof π, Zerocoin25
implements the coin set C as an accu-
mulator, 9 which is a cryptographic con-
struction that allows efficient inser-
tions and proofs of membership. Still,
each spending transaction is 48KB (for
128-bit security level), exceeding the
10KB current limit for Bitcoin trans-
actions. Also, note that the Bitcoin’s
source code does not support the nec-
essary cryptographic operations.
Transactions with zk-SNARKs: Ze-
rocash. Zerocash2 is an alternative
cryptocurrency that, unlike Zerocoin,
hides both origin and destination ad-
dresses. Compared to Zerocoin, it
provides additional functionality, that
is, it handles transactions of arbitrary
denominations, and it provides a way
to give “change” after a transaction.
Moreover, it improves Zerocoin’s veri-
fication efficiency and proof size.
Protocol overview. Similar to Bitcoin, a Zerocash user Alice has a Zerocash address consisting of a public
and secret key pair (pkA, skA). Similar to
Zerocoin, a coin c of value v is minted
by having Alice sample a random serial number S and compute a commitment to the coin’s value, serial
number, and her public key pkA. Next,
Alice publishes a mint transaction
g NIZKPoKs are cryptographic systems similar
to zk-SNARKs but achieving weaker perfor-
mance guarantees for the verifier.
h Recall that unlike a regular Bitcoin transac-
tion, Alice did not publish her identity and the
transaction’s sender.
that sends v bitcoins to the previously
computed commitment c. As a result,
the coin is being held in escrow and
can only be spent by a user that knows
Alice’s secret key skA.
When Alice now wants to send
v coins to Bob, she performs a pour
transaction that is somewhat similar to
the mint transaction: she posts a new
transaction with a new coin c′ with serial number S′ but this time she ties c′
it to Bob’s public key pkB; and she does
not reveal her public address. Next, she
computes a zero-knowledge succinct
non-interactive argument of knowledge
(zk-SNARK) 13 proof π to the following
claim: “( 1) S is a valid opening to some
unspent coin c tied to an address pkA
currently held in escrow; ( 2) I know the
secret key skA corresponding to pkA; ( 3)
c ′ has the same value v as c.” Alice publishes a zerocash transaction containing S, π, c′ without mentioning Bob’s
public address. The network accepts
Alice’s transaction only if π verifies and
S has not been previously spent. In this
case, participants add S to the list of previously spent coins. Notice that unlike
Zerocoin, Bob’s public address is not included as part of Alice’s transaction. In
fact, the only information that ever appears in the ledger in plaintext is the serial number of spent coins. Monitoring
the ledger, Bob can test if a new coin c′
was sent to him by testing it using his secret key skB. At that point, Bob can spend
the coin as he wishes.
Implementing the set of committed
coins. Zerocash does not use an accumulator9 for the set of committed
coins. Instead it uses Merkle hash
trees24 along with zk-SNARKs proofs. 13
Merkle trees have the same interface
with RSA accumulators (they allow efficient insertion of elements and proofs
of membership) but can be encoded in a
zk-SNARK proof much more efficiently
when a “SNARK-friendly” collision-resistant hash function is used.
Practical considerations. The use
of zk-SNARKs drastically changes the
performance of Zerocash from that of
Zerocoin. In particular, the spending
transaction size is reduced to under
1KB and its verification time is less
than 6ms. On the other hand, creating
this transaction takes significantly longer as the zk-SNARK prover algorithm is
particularly demanding (however, this
may be smaller than the block creation