May 20, 2019 at 14:13About anonymity in account-based blockchains
We have long been interested in the topic of anonymity in cryptocurrencies and try to follow the development of technologies in this area. In our articles, we have already examined in detail the principles of operation of confidential transactions in Monero, and also conducted a comparative review of the technologies that exist in this field. However, all anonymous cryptocurrencies today are built on the data model proposed by Bitcoin - Unspent Transaction Output (hereinafter UTXO). For account-based blockchains like Ethereum, existing solutions for the implementation of anonymity and confidentiality (for example, Mobius or Aztec ) tried to repeat the UTXO model in smart contracts.
In February 2019, a group of researchers from Stanford University and Visa Research releasedpreprint "Zether: Towards privacy in the world of smart contracts." The authors first proposed an approach to ensuring anonymity in account-based blockchains and presented two options for a smart contract: for confidential (hiding balances and transfer amounts) and anonymous (hiding recipient and sender) transactions. We find the proposed technology interesting and would like to share its device, as well as talk about why the anonymity problem in account-based blockchains is considered to be very complex and whether the authors managed to solve it in full.
In the UTXO model, a transaction consists of “inputs” and “outputs”. A direct analogue to the “exits” is the banknote in your wallet: each “outlet” has a certain denomination. When you pay with someone (form a transaction) you spend one or more “outputs”, while they become “inputs” of the transaction, and the blockchain marks them as spent. At the same time, the recipient of your payment (or yourself, if you need a change) receives the newly generated “outputs”. Schematically, this can be represented as follows:
Account-based blockchains are structured like your bank account. They only operate on the amount in your account and the transfer amount. When you transfer a certain amount from your account, you don’t burn any “exits”, the network does not need to remember which coins are spent and which are not. In the simplest case, verification of a transaction is reduced to checking the signature of the sender and the amount on its balance sheet:
Next, we'll talk about how Zether hides the amount of transactions, the recipient and the sender. In the course of the description of the principles of his work, we will note the differences in confidential and anonymous version. Since ensuring privacy in account-based blockchains is much simpler, some of the restrictions imposed by anonymization will not be relevant for a confidential version of the technology.
Zether uses the El Gamal encryption scheme to encrypt balances and transfer amounts . It works as follows. When Alice wants to send Bob b coins at the address (his public key) Y , she chooses a random number r and encrypts the amount:
where C is the encrypted sum, D is the auxiliary value needed to decrypt this sum, G is the fixed point on the elliptic curve, when the secret key is multiplied by which the public key is obtained.
When Bob receives these values, he simply adds them to his balance, encrypted in the same way, which is convenient for this scheme.
Similarly, Alice subtracts the same values from her balance sheet, only uses Y as her public key.
The mixing of “exits” in UTXO appeared at the dawn of cryptocurrencies and helps to hide the sender. To do this, the sender, when making a transfer, collects random “exits” in the blockchain and kneads them with his own. Then he signs the “exits” with a ring signature - a cryptographic mechanism that allows him to convince the verifier that among the involved “exits” there are sender coins. The implicated coins themselves, of course, are not wasted.
However, to conceal the recipient, we will not be able to generate fake “outputs”. Therefore, in UTXO, each “exit” has its own unique address, and it is cryptographically associated with the address of the recipient of these coins. At the moment, there is no way to identify the relationship between the unique “exit” address and the address of the recipient without knowing his secret keys.
In an account-based model, we cannot use one-time addresses (otherwise it will already be a model of "exits"). Therefore, the recipient and sender have to be kneaded among other accounts in the blockchain. At the same time, encrypted 0 coins are debited from the kneaded accounts (or 0 is added - in the case of a recipient kneading), without actually changing their real balance.
Since both the sender and the recipient always have a permanent address, here it becomes necessary to use the same groups for mixing to the same addresses. It is easier to consider this with an example.
Suppose Alice decided to contribute to Bob’s charity, but prefers that the transfer remains anonymous to an outside observer. Then, in order to disguise herself in the sender’s field, she also enters Adam and Adele accounts. And to hide Bob - in the recipient field additionally Ben and Bill accounts. Making the next installment, Alice decided to enter Alex and Amanda next to her, and Bruce and Bengen next to Bob. In this case, when analyzing the blockchain in these two transactions, there is only one intersecting pair of participants - Alice and Bob, which deanonymizes these transactions.
As we already mentioned, in order to hide his balance in account-based systems, the user encrypts his balance and the transfer amount. Moreover, he must prove that the balance in his account remains non-negative. The problem is that when forming a transaction, the user builds evidence regarding his current state of the account. And what happens if Bob sends a transaction to Alice, and it will be accepted earlier than sent by Alice? Then Alice’s transaction will be considered invalid, because the proof of balance was built before the adoption of the transaction Bob.
The first solution that comes in such a situation is to freeze your account before the transaction. But this approach is not suitable, because in addition to the complexity of solving such a problem in a distributed system, in an anonymous scheme it will not be clear whose account to block.
To solve this problem, the technology separates incoming and outgoing transactions: spending money has an immediate effect on the balance sheet, and income is deferred. For this, the concept of “era” is introduced - a group of blocks of a fixed size. The current “era” is determined by dividing the block height by the size of the group. Processing the transaction, the network updates the sender’s balance immediately, and adds the recipient’s funds to the drive. The accumulated funds are available to the payee only when a new “era” sets in.
As a result, the user can send transactions regardless of how often they receive funds (as far as his balance allows, of course). The size of an epoch is determined based on how quickly the blocks spread across the network and how quickly the transaction falls into the block.
This solution works well in the case of confidential transfers, but with anonymous transactions, as we will see later, it creates serious problems.
In account-based blockchains, each transaction is signed by the sender's private key, which convinces the verifier that the transaction has not been changed and was created by the owner of this key. But what if the attacker who was listening to the transmission channel intercepts this message and sends the exact same second? The verifier will verify the signature of the transaction and be convinced of its authorship, and the network will debit the same amount from the sender's balance again.
This attack is called a replay attack. In the UTXO model, such attacks are not relevant, because the attacker will try to use the spent outputs, which in itself is not valid and is rejected by the network.
To prevent this from happening, a random data field is inserted into the transaction, which is called nonce or simply “salt”. When resubmitting a transaction with a salt, the reviewer looks to see if this nonce has been used before and, if not, considers this transaction to be valid. In order not to store the entire history of nonce users on the blockchain, it is usually taken to be zero in the very first transaction, and then increased by one. The network can only verify that the nonce of the new transaction differs from the past by one.
In an anonymous translation scheme, the problem of validating nonce transactions arises. We cannot bind nonce explicitly to the sender's address, because, obviously, this deanonymizes the translation. We also cannot add one to the nonce of all participating accounts, because this may conflict with other translations that are being processed.
The authors of Zether propose to generate nonce cryptographically - depending on the "era". For instance:
Here x is the sender's secret key, and G epoch is an additional generator for the era, obtained by hashing a string of the form 'Zether +'. Now the problem, it would seem, is being solved - we do not disclose the nonce of the sender and do not interfere with the nonce of the uninvolved participants. But this approach imposes a serious limitation: one account can send no more than one transaction in the “era”. This problem, unfortunately, remains unresolved, and currently makes an anonymous version of Zether, in our opinion, hardly suitable for use.
In UTXO, the sender must prove to the network that he is not spending a negative amount, otherwise it becomes possible to generate new coins from the air (why this was possible, we wrote in one of the previous articles ). And also sign the “inputs” with a ring signature to prove that among the kneading coins there are funds belonging to him.
In the anonymous version of account-based blockchain, expressions for proof are much more complicated. The sender proves that:
For such complex proof, the authors use a mixture of Bulletproof (one of the authors, by the way, took part in its creation) and the Sigma protocol , which is called Sigma-bullets. Formal proof of such a statement is a rather difficult task, and it severely limits the number of people who want to take up the implementation of the technology.
In our opinion, the part of Zether, which adds privacy to account-based blockchains, may well be used now. But at the moment, an anonymous version of the technology imposes serious restrictions on its use, and its complexity on implementation. However, do not forget that the authors released it only a few months ago, and perhaps someone else will find a solution to the problems today. Indeed, this is how science is done.
In February 2019, a group of researchers from Stanford University and Visa Research releasedpreprint "Zether: Towards privacy in the world of smart contracts." The authors first proposed an approach to ensuring anonymity in account-based blockchains and presented two options for a smart contract: for confidential (hiding balances and transfer amounts) and anonymous (hiding recipient and sender) transactions. We find the proposed technology interesting and would like to share its device, as well as talk about why the anonymity problem in account-based blockchains is considered to be very complex and whether the authors managed to solve it in full.
About the device of these data models
In the UTXO model, a transaction consists of “inputs” and “outputs”. A direct analogue to the “exits” is the banknote in your wallet: each “outlet” has a certain denomination. When you pay with someone (form a transaction) you spend one or more “outputs”, while they become “inputs” of the transaction, and the blockchain marks them as spent. At the same time, the recipient of your payment (or yourself, if you need a change) receives the newly generated “outputs”. Schematically, this can be represented as follows:
Account-based blockchains are structured like your bank account. They only operate on the amount in your account and the transfer amount. When you transfer a certain amount from your account, you don’t burn any “exits”, the network does not need to remember which coins are spent and which are not. In the simplest case, verification of a transaction is reduced to checking the signature of the sender and the amount on its balance sheet:
Technology parsing
Next, we'll talk about how Zether hides the amount of transactions, the recipient and the sender. In the course of the description of the principles of his work, we will note the differences in confidential and anonymous version. Since ensuring privacy in account-based blockchains is much simpler, some of the restrictions imposed by anonymization will not be relevant for a confidential version of the technology.
Concealment of balances and transfer amounts
Zether uses the El Gamal encryption scheme to encrypt balances and transfer amounts . It works as follows. When Alice wants to send Bob b coins at the address (his public key) Y , she chooses a random number r and encrypts the amount:
where C is the encrypted sum, D is the auxiliary value needed to decrypt this sum, G is the fixed point on the elliptic curve, when the secret key is multiplied by which the public key is obtained.
When Bob receives these values, he simply adds them to his balance, encrypted in the same way, which is convenient for this scheme.
Similarly, Alice subtracts the same values from her balance sheet, only uses Y as her public key.
Concealment of the addressee and sender
The mixing of “exits” in UTXO appeared at the dawn of cryptocurrencies and helps to hide the sender. To do this, the sender, when making a transfer, collects random “exits” in the blockchain and kneads them with his own. Then he signs the “exits” with a ring signature - a cryptographic mechanism that allows him to convince the verifier that among the involved “exits” there are sender coins. The implicated coins themselves, of course, are not wasted.
However, to conceal the recipient, we will not be able to generate fake “outputs”. Therefore, in UTXO, each “exit” has its own unique address, and it is cryptographically associated with the address of the recipient of these coins. At the moment, there is no way to identify the relationship between the unique “exit” address and the address of the recipient without knowing his secret keys.
In an account-based model, we cannot use one-time addresses (otherwise it will already be a model of "exits"). Therefore, the recipient and sender have to be kneaded among other accounts in the blockchain. At the same time, encrypted 0 coins are debited from the kneaded accounts (or 0 is added - in the case of a recipient kneading), without actually changing their real balance.
Since both the sender and the recipient always have a permanent address, here it becomes necessary to use the same groups for mixing to the same addresses. It is easier to consider this with an example.
Suppose Alice decided to contribute to Bob’s charity, but prefers that the transfer remains anonymous to an outside observer. Then, in order to disguise herself in the sender’s field, she also enters Adam and Adele accounts. And to hide Bob - in the recipient field additionally Ben and Bill accounts. Making the next installment, Alice decided to enter Alex and Amanda next to her, and Bruce and Bengen next to Bob. In this case, when analyzing the blockchain in these two transactions, there is only one intersecting pair of participants - Alice and Bob, which deanonymizes these transactions.
Transaction Racing
As we already mentioned, in order to hide his balance in account-based systems, the user encrypts his balance and the transfer amount. Moreover, he must prove that the balance in his account remains non-negative. The problem is that when forming a transaction, the user builds evidence regarding his current state of the account. And what happens if Bob sends a transaction to Alice, and it will be accepted earlier than sent by Alice? Then Alice’s transaction will be considered invalid, because the proof of balance was built before the adoption of the transaction Bob.
The first solution that comes in such a situation is to freeze your account before the transaction. But this approach is not suitable, because in addition to the complexity of solving such a problem in a distributed system, in an anonymous scheme it will not be clear whose account to block.
To solve this problem, the technology separates incoming and outgoing transactions: spending money has an immediate effect on the balance sheet, and income is deferred. For this, the concept of “era” is introduced - a group of blocks of a fixed size. The current “era” is determined by dividing the block height by the size of the group. Processing the transaction, the network updates the sender’s balance immediately, and adds the recipient’s funds to the drive. The accumulated funds are available to the payee only when a new “era” sets in.
As a result, the user can send transactions regardless of how often they receive funds (as far as his balance allows, of course). The size of an epoch is determined based on how quickly the blocks spread across the network and how quickly the transaction falls into the block.
This solution works well in the case of confidential transfers, but with anonymous transactions, as we will see later, it creates serious problems.
Replay attack protection
In account-based blockchains, each transaction is signed by the sender's private key, which convinces the verifier that the transaction has not been changed and was created by the owner of this key. But what if the attacker who was listening to the transmission channel intercepts this message and sends the exact same second? The verifier will verify the signature of the transaction and be convinced of its authorship, and the network will debit the same amount from the sender's balance again.
This attack is called a replay attack. In the UTXO model, such attacks are not relevant, because the attacker will try to use the spent outputs, which in itself is not valid and is rejected by the network.
To prevent this from happening, a random data field is inserted into the transaction, which is called nonce or simply “salt”. When resubmitting a transaction with a salt, the reviewer looks to see if this nonce has been used before and, if not, considers this transaction to be valid. In order not to store the entire history of nonce users on the blockchain, it is usually taken to be zero in the very first transaction, and then increased by one. The network can only verify that the nonce of the new transaction differs from the past by one.
In an anonymous translation scheme, the problem of validating nonce transactions arises. We cannot bind nonce explicitly to the sender's address, because, obviously, this deanonymizes the translation. We also cannot add one to the nonce of all participating accounts, because this may conflict with other translations that are being processed.
The authors of Zether propose to generate nonce cryptographically - depending on the "era". For instance:
Here x is the sender's secret key, and G epoch is an additional generator for the era, obtained by hashing a string of the form 'Zether +'. Now the problem, it would seem, is being solved - we do not disclose the nonce of the sender and do not interfere with the nonce of the uninvolved participants. But this approach imposes a serious limitation: one account can send no more than one transaction in the “era”. This problem, unfortunately, remains unresolved, and currently makes an anonymous version of Zether, in our opinion, hardly suitable for use.
Zero-Confidence Evidence
In UTXO, the sender must prove to the network that he is not spending a negative amount, otherwise it becomes possible to generate new coins from the air (why this was possible, we wrote in one of the previous articles ). And also sign the “inputs” with a ring signature to prove that among the kneading coins there are funds belonging to him.
In the anonymous version of account-based blockchain, expressions for proof are much more complicated. The sender proves that:
- The amount sent is positive;
- The balance remains non-negative;
- The sender correctly encrypted the amount of transfers (including zero);
- The balance balance is changed only by the sender and the recipient;
- The sender owns the secret key from his account and he really is in the list of senders (among those involved);
- The nonce used in the transaction is correctly composed.
For such complex proof, the authors use a mixture of Bulletproof (one of the authors, by the way, took part in its creation) and the Sigma protocol , which is called Sigma-bullets. Formal proof of such a statement is a rather difficult task, and it severely limits the number of people who want to take up the implementation of the technology.
What is the result?
In our opinion, the part of Zether, which adds privacy to account-based blockchains, may well be used now. But at the moment, an anonymous version of the technology imposes serious restrictions on its use, and its complexity on implementation. However, do not forget that the authors released it only a few months ago, and perhaps someone else will find a solution to the problems today. Indeed, this is how science is done.