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