On Anonymity in Account-Based Blockchains

We have been interested in the topic of anonymity in cryptocurrencies for quite some time and are keenly following developments in this area. In our articles, we have already delved into the principles of operation of confidential transactions in Monero, and have also conducted comparative review research on technologies existing in this field. However, all anonymous cryptocurrencies today are built on the data model proposed by Bitcoin — Unspent Transaction Output (UTXO). For account-based blockchains like Ethereum, existing solutions for implementing anonymity and privacy (for example, Mobius or Aztec) have tried to replicate the UTXO model in smart contracts.

In February 2019, a group of researchers from Stanford University and Visa Research was released released a preprint titled "Zether: Towards Privacy in Smart Contracts". The authors proposed an approach for ensuring anonymity in account-based blockchains for the first time and presented two types of smart contracts: for confidential (hiding balances and transaction amounts) and anonymous (hiding recipient and sender) transactions. We find the proposed technology interesting and would like to share its structure, as well as discuss why the issue of anonymity in account-based blockchains is considered very complex and whether the authors have fully resolved it.

On the structure of these data models

In the UTXO model, a transaction consists of 'inputs' and 'outputs'. The direct analogy to 'outputs' is the bills in your wallet: each 'output' has a certain denomination. When you pay someone (create a transaction), you spend one or more 'outputs', which then become 'inputs' of the transaction, and the blockchain marks them as spent. Meanwhile, the recipient of your payment (or yourself if you require change) receives newly generated 'outputs'. This can be visually represented as follows:

Account-based blockchains operate similarly to your bank account. They only deal with the amount in your account and the transaction amount. When you transfer a certain amount from your account, you do not burn any 'outputs'; the network does not need to remember which coins have been spent and which have not. In the simplest case, verifying a transaction boils down to checking the sender's signature and the amount in their balance:

Analysis of the technology

Next, we will discuss how Zether conceals the amount of transactions, the recipient, and the sender. Throughout the description of its operating principles, we will note the differences between confidential and anonymous versions. Since ensuring confidentiality in account-based blockchains is much simpler, some of the limitations imposed by anonymization will be irrelevant for the confidential version of the technology.

Concealing balances and transaction amounts

For encrypting balances and transaction amounts in Zether, an encryption scheme is used of ElGamal.It works as follows. When Alice wants to send Bob b coins to an address (his public key), Yshe chooses a random number r and encrypts the amount:

where C — the encrypted amount, D — an auxiliary value needed to decrypt this amount, G — a fixed point on the elliptic curve, from which the public key is derived by multiplying the secret key.

When Bob receives these values, he simply adds them to his similarly encrypted balance, which makes this scheme convenient.

Similarly, Alice subtracts the same values from her balance, just using her public key as Y an input.

Concealing the recipient and sender

Mixing ‘outputs’ in UTXO originated early in the history of cryptocurrencies and helps conceal the sender. To do this, the sender, when making a transfer, selects random ‘outputs’ from the blockchain and mixes them with their own. Then they sign the ‘outputs’ using a ring signature—a cryptographic mechanism that allows the verifier to be convinced that among the mixed ‘outputs’ are coins belonging to the sender. The mixed coins, of course, are not spent.

However, to conceal the recipient, we cannot generate false ‘outputs’. Therefore, in UTXO, each ‘output’ has its own unique address, which is cryptographically linked to the address of the recipient of these coins. Currently, there is no way to identify the connection between the unique ‘output’ address and the recipient's address without knowing their secret keys.

In the account-based model, we cannot use one-time addresses (otherwise it would be the 'outputs' model). Therefore, the sender and receiver must be mixed among other accounts on the blockchain. At the same time, an encrypted 0 coins are deducted from the mixed accounts (or added 0 — in the case of mixing the receiver), effectively not changing their actual balance.

Since both the sender and the receiver always have a permanent address, there is a need to use the same groups for mixing when transferring to the same addresses. This is easier to illustrate with an example.

Suppose Alice decided to make a donation to Bob's charity but prefers to keep this transfer anonymous from external observers. To disguise herself in the sender field, she includes Adam and Adele’s accounts. To hide Bob, she additionally includes Ben and Bill in the receiver field. For her next contribution, Alice decided to include Alex and Amanda next to herself, and Bruce and Benjen next to Bob. In this case, when analyzing the blockchain, there will be just one intersecting pair of participants in these two transactions — Alice and Bob, which deanonymizes these transactions.

Transaction Races

As we mentioned, to conceal their balance in account-based systems, the user encrypts their balance and the transfer amount. They must prove that the balance in their account remains non-negative. The problem is that, when forming a transaction, the user constructs a proof regarding their current account state. But what if Bob sends a transaction to Alice, and it is accepted before Alice's transaction? Then Alice's transaction will be considered invalid, since the balance proof was built before Bob's transaction was accepted.

The first solution that comes to mind in such a situation is to freeze the account until the transaction is completed. However, this approach is not suitable, as aside from the complexity of solving such a task in a distributed system, it will be unclear in an anonymous scheme which account to block.

To address this issue, the technology separates incoming and outgoing transactions: spending has an immediate effect on the balance, while income is delayed. This introduces the concept of an 'epoch' — a group of fixed-size blocks. The current 'epoch' is determined by dividing the block height by the group size. When processing a transaction, the network updates the sender's balance immediately, while the recipient's funds are held in a vault. The accumulated funds are accessible to the payment recipient only upon the onset of a new 'epoch.'

As a result, users can send transactions regardless of how frequently they receive funds (as long as their balance permits, of course). The size of the epoch is determined by how quickly blocks propagate through the network and how swiftly a transaction is included in a block.

This solution works well for confidential transfers; however, with anonymous transactions, as we will see later, it creates serious issues.

Protection against replay attacks

In account-based blockchains, each transaction is signed with the sender's private key, which assures the verifier that the transaction has not been altered and was generated by the owner of that key. But what if an attacker intercepting the transmission channel captures this message and sends an identical duplicate? The verifier will check the transaction's signature and will be convinced of its authenticity, and the network will deduct the same amount from the sender's balance again.

This type of attack is called a replay attack. In the UTXO model, such attacks are not relevant, as the attacker will attempt to use spent outputs, which is invalid in itself and rejected by the network.

To prevent this, a field containing random data is embedded in the transaction, referred to as a nonce or simply 'salt.' When resending a transaction with 'salt,' the verifier checks whether this nonce has been used previously, and if not, considers the transaction valid. To avoid storing the entire history of nonces of users in the blockchain, it is typically set to zero in the very first transaction, and incremented by one thereafter. The network only needs to verify that the nonce of the new transaction is different from the previous one by one.

In an anonymous transaction scheme, the problem of validating nonces arises. We cannot explicitly bind the nonce to the sender's address, as this would obviously de-anonymize the transaction. We also cannot increment the nonces of all involved accounts, as this may conflict with other transactions that are being processed.

The authors of Zether propose to generate nonces cryptographically—depending on the "epoch." For example:

Here x — the sender's secret key, and Gepoch — an additional generator for the epoch, obtained by hashing a string of the form 'Zether + '. Now the problem seems to be solved—we do not reveal the sender's nonce and do not interfere with the nonces of uninvolved participants. However, this approach imposes a serious limitation: one account can send no more than one transaction in an "epoch." This problem, unfortunately, remains unresolved, and at present makes the anonymous version of Zether, in our view, barely usable.

Zero-knowledge proof complexity

In UTXO, the sender must prove to the network that they are not spending a negative amount; otherwise, the generation of new coins from thin air becomes possible (we wrote about why this is possible in one of the previous articles). They must also sign the "inputs" with a ring signature to prove that among the mixed coins, there are funds belonging to them. articles)

In the anonymous version of the account-based blockchain, the expressions for proof become much more complex. The sender proves that:

1. The amount sent is positive;
2. The balance remains non-negative;
3. The sender has correctly encrypted the transfer amounts (including zeroes);
4. The balance is changed only for the sender and the recipient;
5. The sender owns the secret key for their account, and it is indeed present in the list of senders (among the mixed participants);
6. The nonce used in the transaction is constructed correctly.

For such complex proofs, the authors use a mixture of Bulletproof (one of the authors, by the way, participated in its creation) and Sigma protocol, which they call Sigma-bullets. The formal proof of such a statement is quite a challenging task, and it greatly limits the number of those willing to implement the technology.

What’s the result?

In our opinion, the part of Zether that introduces privacy to account-based blockchains could be used right now. However, at the moment, the anonymous version of the technology imposes serious limitations on its use, and its complexity affects implementation. However, we shouldn't forget that the authors released it only a few months ago, and perhaps someone else will find a solution to the existing problems. After all, that's how science progresses.

Source: habr.com