Integrating with bitcoin clients

libzerocoin provides the core cryptographic routines for the Zerocoin protocol. It is not, however, a complete Zerocoin implementation. On this page we provide a short overview of the additional transaction types and functionality required to add Zerocoin to a Bitcoin client.

Note that this is a high level overview and not a precise description of the message format. We believe those decisions are best left to the Bitcoin/altcoin community.

Note: See the Advanced Integration page for details on incremental deployment, reducing proof bandwidth, etc.

Choosing zerocoin denomination(s)

Unlike Bitcoin, Zerocoin is a coin-based protocol where all coins have some fixed denomination. For example, the value of 1 zerocoin (ZC) might be set at 1 BTC. This value is arbitrary and should be set by protocol convention.

In practice it may be convenient to run several independent Zerocoin instances, where each instance uses a different coin denomination (this is analogous to issuing $1, $5 and $10 bills.) libzerocoin provides native support for multiple denominations. See supporting multiple denominations (TODO) for more on the tradeoffs involved.

Parameter generation

All parties in a Zerocoin deployment must share a common public parameter N. This parameter must be generated by a trusted party and distributed with all clients. See generating Zerocoin parameters for more details.

Coin Minting

To mint a new zerocoin, the user first constructs a new PrivateCoin object, then extracts the public portion of the coin using the getPublicCoin() method. The resulting PublicCoin object can be serialized using the << constructor to obtain a binary array.

The client must now formulate a new ZEROCOIN_MINT transaction to send to the network. This transaction will include:

1. Bitcoin inputs summing to the denomination of one zerocoin + transaction fees
2. (OPTIONAL) the denomination of the coin, if more than one denomination is in use
3. The serialized PublicCoin.

The precise format of the ZEROCOIN_MINT message is left to implementers. Since public coins are relatively small, it may even be possible to 'hack' this capability into a standard Bitcoin transaction without changing the protocol. However you choose to do it, there must be no way for users to redeem the inputs except via a Zerocoin spend transaction.

The client must store the PrivateCoin object in a secure wallet. This object contains the secrets required to spend the coin. NOTE: IF THESE SECRETS ARE COMPROMISED (EVEN AFTER YOU SPEND THE COIN) YOU COULD LOSE BOTH THE COIN AND THE ANONYMITY OF THE COIN. THEY SHOULD BE DESTROYED IMMEDIATELY UPON SPENDING.

Coin validation

Each client (or miner) who receives a ZEROCOIN_MINT transaction must validate the transaction before performing any operations on it. Validation involves the following steps:

1. Verifying that all Bitcoin inputs are correct and unspent. (These should also authenticate the rest of the transaction including PublicCoin.)
2. Verifying that all inputs total to the denomination of the coin requested (+ fees).
3. Deserializing and validating the PublicCoin.
4. Verifying that this PublicCoin has not appeared in any previous ZEROCOIN_MINT transactions.

Steps (1) and (2) are Bitcoin-specific and require no Zerocoin cryptography. Step (4) requires the client/miner to keep a list of previously minted coins. libzerocoin currently does not provide a data structure for this purpose.

The validation in step (3) will be performed automatically if you use the stream (deserialization) constructor for PublicCoin. If for some reason you don't, you can manually perform validation using the validate() method of that class.

A ZEROCOIN_MINT transaction should be considered confirmed only after it has been included in a certain number of blocks. This number is at the discretion of the implementer.

Validation is as important as normal Bitcoin transaction validation and should happen at the same points. Failure to validate a new Zerocoin could allow double-spending.

Overview of the Spend process

Spending a Zerocoin involves several steps. We first provide a brief overview of the full process, then break out each step in the sections that follow.

1. The client (spender) first identifies a set of confirmed ZEROCOIN_MINT transactions (by all users) in the block chain (this set must include the zerocoin she intends to spend). We'll call this the confirmed transaction set. She chooses one of these transactions at random and verifies that it has not been redeemed (i.e., it is not referenced in another ZEROCOIN_SPEND transaction). We'll refer to this as the redemption transaction.

2. She then computes an Accumulator over all the PublicCoin values in the confirmed transaction set. The network can assist with the Accumulator calculation (see 'Calculating the Accumulator' below).

3. She computes a Witness over the confirmed transaction set and the PrivateCoin she intends to spend.

4. She then computes a ZEROCOIN_SPEND transaction that includes (A) the identity of the redemption transaction as a Bitcoin input, (B) one or more arbitrary destination Bitcoin addresses as a Bitcoin output, (C) a serial number and signature on the transaction, both of which are computed using the CoinSpend class. The computation of CoinSpend is based on the hash of the transaction, the Accumulator and Witness as well as the unspent PrivateCoin.

5. The network (particularly the miners) compute the Accumulator over the same transaction set. They perform the following checks: (A) extract the serial number from the CoinSpend object and verify that it has not been used in any other (valid) ZEROCOIN_SPEND transaction, (B) verify the CoinSpend signature (using the included libzerocoin CoinSpend.Verify() method), (C) verify that the specified Bitcoin inputs (referenced in the redemption transaction) have not previously been redeemed by another ZEROCOIN_SPEND.

6. The network (particularly the miners) confirm the checks of Step [5]. If all checks pass, the ZEROCOIN_SPEND transaction is accepted and confirmed into the block chain. The transaction represents a transfer of value from the inputs of the redemption transaction to the destination Bitcoin addresses specified in the ZEROCOIN_SPEND outputs. Any unclaimed bitcoins are retained by the miner as transaction fees.

The following sections elaborate on each of the steps above.

Calculating the Accumulator

In order to generate or verify ZEROCOIN_SPEND transactions each participant must first compute an Accumulator on the set of confirmed ZEROCOIN_MINT transactions. The accumulator is deterministic (non-randomized) and can be incrementally computed. Calculation can be accomplished in two ways:

• The spender/verifier can compute the full accumulator themselves. This is accomplished by instantiating a fresh Accumulator object and using the += or accumulate() methods to add the PublicCoin value from all confirmed ZEROCOIN_MINT transactions.

• To reduce clients' computational burden, the miners can incrementally compute the accumulator. This is accomplished by placing an 'Accumulator Checkpoint' within each block. The Accumulator Checkpoint for block i is computed by deserializing the Accumulator Checkpoint in block i-1 into an Accumulator class, then accumulating all valid ZEROCOIN_MINT (PublicCoin) values in block i. If i = 0 an empty Accumulator class is used for the previous Checkpoint.

NOTE: When using Accumulator Checkpoints, all nodes in the network MUST validate each Accumulator Checkpoint before accepting a proposed block. This is done by re-computing the Accumulator Checkpoint using the identical inputs. FAILURE TO VERIFY THE CORRECTNESS OF ACCUMULATOR CHECKPOINTS COULD LEAD TO DOUBLE SPENDING.

Coin spending (detailed)

This section elaborates on Steps [1-4] of the overview above.

1. The client (spender) first identifies the confirmed transaction set, i.e. the set of confirmed ZEROCOIN_MINT transactions in the block chain. In our expected usage this set will consist of all confirmed transactions. However some clients might choose to use a smaller set -- for example, by selecting only transactions within a specific block range (see 'Using Transaction Windows' on the Advanced Integration page).

2. The client (spender) now picks at random one confirmed ZEROCOIN_MINT transaction that has not been redeemed (spent) by any ZEROCOIN_SPEND transaction in the block chain. This is the redemption transaction. Note that the redemption transaction is not (except by random chance) the same as the original MINT transaction.

3. The client (spender) calculates an Accumulator over all confirmed ZEROCOIN_MINT transactions in the first set (specifically, she accumulates the PublicCoin values from each transaction.) She can do this independently, or with the assistance of the Bitcoin network (see 'Calculating the Accumulator').

4. The client (spender) formats a ZEROCOIN_SPEND transaction. This transaction specifies the set of ZEROCOIN_MINT transactions used to compute the Accumulator (i.e., it might specify block numbers 0-B for some block number B). It also includes the identity of the ZEROCOIN_MINT transaction selected in step (2) as a Bitcoin input. It embeds an arbitrary set of Bitcoin outputs.

5. The client (spender) generates a CoinSpend signature on the transaction that includes the hash of the transaction as well as the Accumulator and PrivateCoin object. The resulting CoinSpend embeds both a coin serial number and a set of zero-knowledge proofs that prove (A) that the spender knows a coin in the transaction set, (B) that the serial number is consistent with the coin, and (C) the spender knows the secret values for the coin. These are all tied to the transaction hash. The client (spender) serializes the CoinSpend object and transmits the completed ZEROCOIN_SPEND transaction to the network.

6. Once the ZEROCOIN_SPEND transaction has been confirmed by the network, the spender MUST destroy the PrivateCoin and all secrets to prevent later compromise and de-anonymization.

Coin spend verification (detailed)

This section elaborates on Steps [5, 6] of the overview above.

1. The network nodes compute the Accumulator over the same transaction set as the spender (this information is taken from the sender's COIN_SPEND transaction).

2. They now perform the following checks: (A) they extract the serial number from the CoinSpend object and verify that it has not been used in any other (valid) ZEROCOIN_SPEND transaction, (B) verify the CoinSpend signature (using the included libzerocoin CoinSpend.Verify() method), (C) verify that the Bitcoins from the redemption transaction have not previously been redeemed by another ZEROCOIN_SPEND and (D) verify that the Bitcoin input and outputs are consistent.

3. The network (particularly the miners) confirm the checks of Step [2]. If all checks pass, the ZEROCOIN_SPEND transaction is accepted and confirmed into the block chain. The transaction represents a transfer of value from the inputs of the redemption transaction to the destination Bitcoin address. Any unclaimed bitcoins are retained by the miner as transaction fees.