Privacy Analysis and Evaluation Policy of Blockchain-based Anonymous Cryptocurrencies

In Zerocash [15], all coins are encrypted in the shared ledger. The seemingly unrelated two identifiers, a coin commitment $cm$ and a serial number $sn$ (Figure 7), are used to identify each coin produced by the previous transaction sender. A transaction sender uses $cm$($cm^{new}$) as an identifier of the coin (called $c^{new}$ from the viewpoint of the transaction sender), while the corresponding recipient uses $sn$($sn^{old}$) as another identifier of the same coin (called $c^{old}$ from the viewpoint of transaction recipient). Consequently, this makes it difficult for most Zerocash users, including even the sender of $c^{new}$, to link the two identifiers of the same coin recorded in the shared ledger (only the recipient of $c^{old}$ can link those).

However, people cannot use it in that shape because the recipient cannot verify whether the coins sent from the sender is valid (i.e., the shared secrets sent from the sender are well-formed). Therefore, the sender also includes a zero-knowledge proof $\pi_{pour}$ in each transaction to prove that the identifiers and the secret parameters of each coin are consistent.

• •

  $cm^{old}$ is properly calculated from the secret information of the coin $c^{old}$ held by the sender (note that $cm^{old}$ is also secret information to the sender.)

• •

  $cm^{new}$ is properly calculated from the secret information of the coin $c^{new}$ produced and sent to the recipient by the sender.

• •

  The public key $a_{pk}$ used as an address when the sender has received $cm^{old}$ is properly generated from the sender’s secret key $a_{sk}$ (the proof of the proper recipient $a_{pk}$ of $cm^{old}$).

• •

  $sn^{old}$ is properly calculated from the secret information of the coin $c^{old}$ held by the sender and the sender’s secret key $a_{sk}$.

• •

  The secret information $cm^{old}$ is included in the $cm$ list recorded in the shared ledger (the proof of the fact that $cm^{old}$ had already existed when the sender received the coin $c^{old}$).

• •

  The total amount of old coins ($v_{1}^{old}+v_{2}^{old}+...$) included in the transaction input is equal to the total amount of new coins ($v_{1}^{new}+v_{2}^{new}+...$) included in the transaction output (note that amount of each coin is secret information).

Preventing double-spending of the coin $c^{old}$ does not need to be proved using zero-knowledge proofs. Verifying that $sn^{old}$ has not yet appeared in each of the transaction inputs recorded in the shared ledger is sufficient.

In Zerocash, $cm$ and $sn$ are the only values recorded in the shared ledger. Since $cm$ is generated by a commitment scheme and $sn$ is a returned value by a pseudo-random function, all those values are recognized as random by any third party, and it is difficult for them to link any two values recorded in the shared ledger.

Therefore, Zerocash is SLLA-resistant.

When a sender $a_{pk}$ (a victim in RCCLA) sends a new coin $c^{new}$ to a recipient $b_{pk}$ (an attacker in RCCLA) through a transaction $tx_{new}$, the sender discloses to the recipient the serial number $sn^{old}$ of the consumed coin $c^{old}$ and the shared parameters of the sent coin $c^{new}$, e.g., $b_{pk}$, $v^{new}$, $\rho^{new}$, $r^{new}$, $s^{new}$, and $cm^{new}$.

The following is our logical verification on whether the recipient $b_{pk}$ of the coin $c^{new}$ can obtain any unknown information about the sender $a_{pk}$ by the medium of each of the shared parameters of the coin $c^{new}$. Note that since RCCLA is an attack model under the condition that the attacker can receive coins with any parameter from the victim, we assume that the attacker can make the recipient send coins with maliciously induced parameters as needed.

1. 1)

   Serial Number: $sn^{old}$
   Since the recipient needs the secret key $z_{sk}$ of the sender $z_{pk}$ of the coin $c^{old}$ in addition to the parameters of the coin $c^{old}$ to calculate the coin commitment $cm^{old}$, the recipient cannot link $sn^{old}$ with $cm^{old}$.

   Next, the serial number $sn^{old}$ cannot appear in any other transactions than $tx_{new}$, because the secondary use of the serial number is regarded as double-spending.

   Therefore, the attacker $b_{pk}$ cannot obtain any unknown information about the sender $a_{pk}$ by the medium of the serial number $sn^{old}$.

2. 2)

   Recipient’s Address: $b_{pk}$
   The recipient’s address $b_{pk}$ is their address of the attacker.

   Therefore, the attacker $b_{pk}$ cannot obtain any unknown information about the sender $a_{pk}$ by the medium of the recipient’s address $b_{pk}$.

3. 3)

   Amount of Coin: $v^{new}$
   Since the new coins $(c^{new}_{i})$ are always produced by the sender $a_{pk}$ every time the old coins $(c^{old}_{i})$ are consumed, where the old coins $(c^{old}_{i})$ are merged or split into the new coins $(c^{new}_{i})$, the same amount $v^{old}$ of one of the old coins $(c^{old}_{i})$ is not used as an amount $v^{new}$ of one of the new coins $(c^{new}_{i})$ unless the sender intentionally reuses it.

   Therefore, the attacker $b_{pk}$ cannot obtain any unknown information about the sender $a_{pk}$ by the medium of the amount of coin $v^{new}$.

4. 4)

   Random Parameters: $\rho^{new}$, $r^{new}$, and $s^{new}$
   Since a new coin $c^{new}$ is always produced by the sender $a_{pk}$ every time the old coin $c^{old}$ is consumed, the same random parameters $\rho^{old}$, $r^{old}$, and $s^{old}$ of the old coin $c^{old}$ are not used as random parameters $\rho^{new}$, $r^{new}$, and $s^{new}$ of the new coins $c^{new}$ unless the sender intentionally reuses it.

   Therefore, the attacker $b_{pk}$ cannot obtain any unknown information about the sender $a_{pk}$ by the medium of the random parameters $\rho^{new}$, $r^{new}$, and $s^{new}$.

5. 5)

   Coin Commitment: $cm^{new}$
   The recipient $b_{pk}$ can calculate the serial number $sn^{new}$ of the coin $c^{new}$ using their secret key $b_{sk}$, identify the corresponding coin commitment $cm^{new}$ in a transaction $tx_{new}$ on the shared ledger, and hence link $sn^{new}$ with $cm^{new}$ and $sn^{old}$. However, the recipient cannot link $cm^{new}$ and $sn^{old}$ with anymore.

   Next, the coin commitment $cm^{new}$ cannot appear in any other transactions than $tx_{new}$, because CMList is not allowed to include the same two or more coin commitments at the same time.

   Therefore, the attacker $b_{pk}$ cannot obtain any unknown information about the sender $a_{pk}$ by the medium of the coin commitment $cm^{new}$.

In the end, the attacker $b_{pk}$ in RCCLA cannot obtain any unknown information about a victim $a_{pk}$ from the coins sent from the victim to link with the information they already have.

Therefore, Zerocash is RCCLA-resistant.

When a sender $a_{pk}$ (an attacker in SCCLA) sends a $c^{new}$ to a recipient $b_{pk}$ (a victim in SCCLA) through a transaction $tx_{new}$, the sender discloses to the recipient the $sn^{old}$ of the consumed $c^{old}$ and the shared parameters of the sent $c^{new}$, e.g., $b_{pk}$, $v^{new}$, $\rho^{new}$, $r^{new}$, $s^{new}$, and $cm^{new}$.

The following is our logical verification on whether the sender $a_{pk}$ of $c^{new}$ can obtain any unknown information about the recipient $b_{pk}$ from the $c^{next}$ sent to a colluder $c_{pk}$ by the recipient by the medium of each of the shared parameters of $c^{new}$. Note that since SCCLA is an attack model under the condition that the attacker can send coins with any parameter to the victim, we assume that the attacker can send coins with maliciously manipulated parameters as needed.

1. 1)

   Serial Number: $sn^{old}$
   The recipient $b_{pk}$ does not use the serial number $sn^{old}$ to consume the coin $c^{new}$. Furthermore, since even the sender cannot calculate the serial number $sn^{new}$ of the sent coin $c^{new}$ because anyone who wants to calculate $sn^{new}$ needs the secret key $b_{sk}$ of the recipient $b_{pk}$, the sender cannot link $sn^{old}$ and $sn^{new}$.

   Therefore, the attacker $a_{pk}$ cannot obtain any unknown information about the recipient $b_{pk}$ by the medium of the serial number $sn^{old}$ and $sn^{new}$.

2. 2)

   Recipient’s Address: $b_{pk}$
   Since the recipient is not explicitly notified of any address in the Zerocash protocol, the recipient’s address $b_{pk}$ is not transmitted to any third party (who may collude with the sender) $c_{pk}$ unless the recipient intentionally notifies the third party of its address outside the protocol.

   Therefore, the recipient’s address $b_{pk}$ is not spread to anyone, and the attacker $a_{pk}$ cannot obtain any unknown information about the recipient $b_{pk}$ by the medium of the recipient’s address $b_{pk}$.

3. 3)

   Amount of Coin: $v^{new}$
   The sender $a_{pk}$ can set an amount of a coin $v^{new}$ to any intentional value, e.g., 0.07007007ZEC, to track the recipient’s behavior. However, since the next coins $(c^{next}_{i})$ are always produced by the recipient $b_{pk}$ every time the new coins $(c^{new}_{i})$ are consumed, where the new coins $(c^{new}_{i})$ are merged or split into the next coins $(c^{next}_{i})$, the same amount $v^{new}$ of one of the new coins $(c^{new}_{i})$ is not used as an amount $v^{next}$ of one of the next coins $(c^{next}_{i})$ unless the recipient intentionally reuses it.

   Therefore, the amount of coin $v^{new}$ is not spread to anyone other than the recipient $b_{pk}$, and the attacker $a_{pk}$ cannot obtain any unknown information about the recipient $b_{pk}$ by the medium of the amount of coin $v^{new}$.

4. 4)

   Random Parameters: $\rho^{new}$, $r^{new}$, and $s^{new}$
   Since a next coin $c^{next}$ is always produced by the recipient $b_{pk}$ every time the new coin $c^{new}$ is consumed, the same random parameters $\rho^{new}$, $r^{new}$, and $s^{new}$ of the new coin $c^{new}$ are not used as random parameters $\rho^{next}$, $r^{next}$, and $s^{next}$ of the next coins $c^{next}$ unless the recipient intentionally reuses it.

   Therefore, the random parameters $\rho^{new}$, $r^{new}$, and $s^{new}$ are not spread to anyone other than the recipient $b_{pk}$, and the attacker $a_{pk}$ cannot obtain any unknown information about the recipient $b_{pk}$ by the medium of the random parameters $\rho^{new}$, $r^{new}$, and $s^{new}$.

5. 5)

   Coin Commitment: $cm^{new}$
   Since the coin commitment $cm^{next}$ that the recipient $b_{pk}$ will produce is calculated from the random parameters $\rho^{next}$, $r^{next}$, and $s^{next}$, etc., $cm^{next}$ cannot be the same value as $cm^{new}$.

   Therefore, the coin commitment $cm^{new}$ is not spread to anyone other than the recipient $b_{pk}$, and the attacker $a_{pk}$ cannot obtain any unknown information about the recipient $b_{pk}$ by the medium of the coin commitment $cm^{new}$.

In the end, the attacker $a_{pk}$ in SCCLA and their colluder $c_{pk}$ cannot obtain any unknown information about a victim $b_{pk}$ from the coins sent to the victim to link with the information they already have.

Therefore, Zerocash is SCCLA-resistant.

CryptoNote [13], which is mainly designed based on Bitcoin, enhances its anonymity using schemes named stealth address and one-time ring signature.

In CryptoNote, the transaction sender first provides a one-time randomized recipient address (stealth address) generated from a one-time random value $r$ sampled by the sender and a pair of public keys $(A,B)$ generated by the recipient. Therefore, the recipient’s stealth address varies every time, even if the sender sends two or more transactions to the same recipient, thus making CryptoNote achieve recipient anonymity.

However, the stealth address scheme is not sufficient because it still allows de-anonymizing attackers to construct a transaction graph and analyze it. Therefore, CryptoNote provides another anonymization scheme (one-time ring signature), where the signer who consumes each coin bundles their public key and $(n-1)$ other user’s dummy public keys to generate a non-interactive zero-knowledge proof that suggests that the coin is signed (or consumed) by the secret key corresponding to one of the bundled public keys (although which key pair is used is not disclosed). Due to this scheme, the de-anonymization attack using the transaction graph is challenging in CryptoNote. However, the success rate of the de-anonymization attack cannot be reduced to below $1/n$ ($n$ is the number of bundled public keys). The degree of sender anonymity depends on $n$. Note that the one-time ring signature scheme has almost the same effect as Bitcoin’s mixing techniques [27][32].

Whether a sender uses a different stealth address (i.e., different $r$) for each transaction depends on the sender. However, the verifying algorithm of double-spending in one-time ring signature does not allow the recipient to consume both coins signed with the same stealth address.

Note that the amount of coin in CryptoNote has already been encrypted by the method named Ring Confidential Transactions (Ring CT) [33].

In the case of CryptoNote, transactions, coins (UTXOs), a sender of each coin, and a recipient of each coin are entirely disclosed to an unspecified large number of users on a shared ledger.

However, since each address of the coin recipients and thus senders is randomized by stealth address, any two coins are unlinkable by the medium of the sender’s nor recipient’s address, which means that the coins achieve sender and recipient anonymity (III-C).

On the other hand, although one-time ring signature scrambles the signer who consumes the coin, linking the received coin with a sent coin is possible (success rate is $1/n$). Therefore, the attackers of SLLA can construct a probabilistic transaction graph.

Therefore, CryptoNote is not SLLA-resistant (but weakly SLLA-resistant).

When a sender $a_{pk}$ (a victim in RCCLA) sends a new coin $c^{new}$ to a recipient $b_{pk}$ (an attacker in RCCLA) through a transaction $tx_{new}$, the sender discloses to the recipient the destination key $P$, the amount of coin $v^{new}$, and the tx public key $R$.

The following is our logical verification whether the recipient $b_{pk}$ of the coin $c^{new}$ can obtain any unknown information about the sender $a_{pk}$ by the medium of each of the shared parameters of the coin $c^{new}$.

1. 1)

   Destination Key: $P$
   The destination key $P$ of the coin $c^{new}$ is a stealth address of the recipient $b_{pk}$. Since the stealth address is exclusively generated for each coin, the recipient cannot find it in any other coins.

   Therefore, the attacker $b_{pk}$ cannot obtain any unknown information about the sender $a_{pk}$ by the medium of the destination key $P$.

2. 2)

   Amount of Coin: $v^{new}$
   Since the new coins $c^{new}_{i}$ are always produced by the sender $a_{pk}$ every time the old coins $c^{old}_{i}$ are consumed, where the old coins $c^{old}_{i}$ are merged or split into the new coins $c^{new}_{i}$, the same amount $v^{old}$ of one of the old coins $c^{old}_{i}$ is not used as an amount $v^{new}$ of one of the new coins $c^{new}_{i}$ unless the sender intentionally reuses it.

   Therefore, the attacker $b_{pk}$ cannot obtain any unknown information about the sender $a_{pk}$ by the medium of the amount of coin $v^{new}$.

3. 3)

   Tx Public Key: $R$
   The tx public key $R$ of the transaction $tx^{new}$ is a corresponding public key to the one-time random value $r$. If using the same $r$ in different transactions is prohibited, the recipient cannot find it in any other transaction.

   Therefore, the attacker $b_{pk}$ cannot obtain any unknown information about the sender $a_{pk}$ by the medium of the tx public key $R$.

In the end, the attacker $b_{pk}$ in RCCLA cannot obtain any unknown information about a victim $a_{pk}$ from the coins sent from the victim to link with the information they already have.

Therefore, CryptoNote is RCCLA-resistant.

In Mimblewimble [28], the amount of each coin $v$ is hidden in Pedersen commitment [34], $p=rG+vH$, which is used as a token of a coin. If someone wants to send the coins to another, the sender sends the commitments with their secrets $r_{i}$ and $v_{i}$ to the recipient, the recipient constructs a transaction named Confidential Transactions [35], including the sent old commitments and the new commitments that the recipient newly creates at that moment. The recipient sends the transaction to the shared ledger. In Mimblewimble, only the recipient of the old commitments consumes the coins because they know the secrets of the old commitments. Thus, they can construct a transaction of Confidential Transactions, in which the sum of all the commitments is zero.

Although the sender still knows the secrets of the old commitments, they cannot consume the old coins after the recipient sends the transaction to the shared ledger because the miners do not allow anyone to double-spend. On the other hand, since only the recipient knows the secrets of the new commitments, the new coins cannot be consumed by anyone else. Additionally, in the transaction of Confidential Transactions, the total amount of new coins is made to equal the total amount of the old coins. Therefore, the ownership of the coins is correctly and safely transferred from the sender to the recipient.

In summary, the possession of a coin is determined by holding the secrets of the commitment, and the transfer of the coin is achieved by sending the secrets of the commitment. Therefore, address information for identifying the users is not required; thus, it is not included in each coin in Mimblewimble. That is, we do not have to anonymize the address in Mimblewimble.

In the case of Mimblewimble, the transactions of Confidential Transactions, including the Pedersen commitments, are disclosed to an unspecified large number of users on a shared ledger.

Since the amount of each coin is hidden in a commitment and each address of the coin senders and recipients is not included in the coin, any two coins are unlinkable by the medium of sender’s address or recipient’s address, which means that the coins achieve sender and recipient anonymity (III-C). Having no address brings substantial unlinkability by the medium of any address, avoiding de-anonymization of anyone.

However, since the identifier of the sent coin and that of the received coin is the same, anyone can construct the transaction graph.

Therefore, Mimblewimble is not SLLA-resistant.

When a sender $a_{pk}$ (a victim in RCCLA) sends an old coin $c^{old}$ to a recipient $b_{pk}$ (an attacker in RCCLA), the sender discloses the old commitments with their secrets $r$ and $v$ to the recipient.

However, since the recipient just consumes the old commitments, the recipient is no longer interested in the commitment. Although the recipient can still construct the transaction graph, they cannot obtain unknown information more than an attacker in SLLA about a victim $a_{pk}$ knows from the coins sent from the victim to link with the information they already have.

Therefore, Mimblewimble is RCCLA-resistant.

When a sender $a_{pk}$ (an attacker in SCCLA) sends an old coin $c^{old}$ to a recipient $b_{pk}$ (a victim in SCCLA), the sender discloses the old commitments with their secrets $r$ and $v$ to the recipient.

Since the sender can track the new coin $c^{new}$ by the medium of the old commitments, they will be able to know when the new coin will be consumed.

In the end, the attacker $a_{pk}$ in SCCLA can obtain some unknown information about a victim $b_{pk}$ by the medium of the coins sent to the victim to link with the information they already have.

Therefore, Mimblewimble is not SCCLA-resistant.