On 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 analyzed in detail the principles of the operation of confidential transactions in Monero, and also conducted a comparative review of the technologies existing 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 implementing anonymity and confidentiality (for example, Mobius or Aztec ) attempted to replicate the UTXO model in smart contracts.
In February 2019, a group of researchers from Stanford University and Visa Research released preprint "Zether: Towards privacy in the world of smart contracts." The authors for the first time 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 the recipient and sender) transactions. We find the proposed technology interesting and would like to share it with the device, as well as talk about why the anonymity problem in account-based blockchains is considered very complex and whether the authors managed to solve it fully.
In the UTXO model, the transaction consists of “inputs” and “outputs”. A direct counterpart to “outs” is the bills in your wallet: each “exit” has some kind of denomination. When you pay with someone (form a transaction) you spend one or several "exits", at the same time they become the "inputs" of the transaction, and the blockchain marks them as spent. In this case, the recipient of your payment (or you yourself, if you need a change) receives the newly generated “exits”. Schematically, this can be represented as:
')
Account-based blockchains are roughly like your bank account. They operate only with the amount on your account and the amount of transfer. When you transfer some amount from your account, you do not burn any “exits”, the networks do not need to remember which coins are spent and which are not. In the simplest case, verification of a transaction is reduced to verifying the sender's signature and the amount on his balance sheet:
Next, we'll talk about how Zether hides the transaction amount, the recipient and the sender. In the course of describing the principles of his work, we will note the differences in the confidential and anonymous version. Since it is much easier to ensure confidentiality in account-based blockchains, some of the restrictions imposed by anonymization will be irrelevant for the confidential version of the technology.
To encrypt balances and transfer amounts, Zether uses an ElGamal encryption scheme . It works as follows. When Alice wants to send Bob the b coins to the address (his public key) Y , she chooses a random number r and encrypts the amount:
where C is the encrypted amount, D is the auxiliary value needed to decrypt this amount, G is a fixed point on the elliptic curve, by multiplying the secret key by which the public key is obtained.
When Bob receives these values, he simply adds them to his encrypted balance in the same way, and this scheme is convenient.
Similarly, Alice subtracts the same values ​​from her balance, only using her public key as Y.
The mixing of “exits” in UTXO appeared at the dawn of cryptocurrency and helps to hide the sender. To do this, the sender himself, when making a transfer, enters random “exits” in the blockchain and mixes them with his own. Then he signs "exits" with a ring signature - a cryptographic mechanism, which allows convincing the verifier that the sender's coins are among the implicated "exits". The coins themselves are, of course, not spent.
However, to conceal the recipient, we will not be able to generate fake "exits." Therefore, in UTXO, each “exit” has its own unique address, and it is cryptographically connected with the recipient address of these coins. At the moment there is no way to identify the connection between the unique address of the "exit" and the address of the recipient, without knowing his secret keys.
In the account-based model, we cannot use one-time addresses (otherwise it will already be a “exit” model). Therefore, the recipient and the sender have to knead among other accounts in the blockchain. At the same time, encrypted 0 coins are written off from the kneaded accounts (or 0 is added - in the case of mixing the recipient), without actually changing their real balance.
Since both the sender and recipient always have a permanent address, here it becomes necessary to use the same groups for mixing to the same addresses. It's easier to look at this with an example.
Suppose Alice decided to make a contribution to Bob’s charitable foundation, but prefers that this translation remain anonymous for a casual observer. Then, in order to disguise herself in the field of the sender, she enters more accounts of Adam and Adele. And to hide Bob - in the field of the recipient in addition Ben and Bill accounts. Making the next installment, Alice decided to type 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 will be only one intersecting pair of participants - Alice and Bob, which de-anonymizes these transactions.
As we have already mentioned, in order to hide his balance in account-based systems, the user encrypts his balance and the amount of transfer. However, he must prove that the balance on his account remains non-negative. The problem is that by forming a transaction, the user builds a proof regarding his current account status. And what will happen if Bob sends a transaction to Alice, and she will be accepted earlier than Alice sent? Then Alice’s transaction will be considered invalid, since the proof of the balance was built before accepting the transaction by Bob.
The first decision that comes up in such a situation is to freeze the account before the transaction. But this approach is not suitable, since in addition to the complexity of solving such a problem in a distributed system, it will not be clear in an anonymous scheme, whose account will be blocked.
To solve this problem, the technology separates incoming and outgoing transactions: the expenditure of funds has an immediate effect on the state of balance, and receipts - deferred. For this purpose, the concept of "epoch" is introduced - a group of blocks of fixed size. The current "epoch" is determined by dividing the height of the block by the size of the group. Processing the transaction, the network updates the balance of the sender immediately, and the recipient’s funds are put into the drive. Accumulated funds are available to the payee only when a new “era” arrives.
As a result, the user can send transactions regardless of how often he receives funds (as far as his balance allows, of course). The size of an epoch is determined based on how quickly the blocks propagate through the network and how quickly the transaction enters the block.
This solution works well for confidential transfers, but with anonymous transactions, as we will see later, it creates serious problems.
In the 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 created by the owner of this key. But what if the attacker who listened to the transmission channel intercepts this message and sends the exact same second one? The verifier will verify the signature of the transaction and will be convinced of its authorship, and the network will write off the same amount from the balance of the sender again.
This attack is called a replay attack. In the UTXO model, such attacks are not relevant, since 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 field with random data, which is called nonce or simply "salt", is embedded in the transaction. When resubmitting a transaction with a “salt”, the verifier checks whether the nonce has been used before and, if not, considers the transaction valid. In order not to store the entire history of nonce-s in the blockchain, usually in the very first transaction it is taken equal to zero, and then increased by one. The network only needs to check that the nonce of a new transaction differs from the previous one by one.
In an anonymous translation scheme, the problem of validating transaction nonce arises. We cannot bind nonce in an explicit way to the sender's address, since, obviously, this will de-anonymize the transfer. We also cannot add one to the nonce of all participating accounts, since this may conflict with other transfers that are being processed.
Zether authors propose to generate nonce cryptographically - depending on the "era". For example:
Here, x is the sender's secret key, and G epoch is an additional generator for the epoch, obtained by hashing a string like 'Zether +'. Now the problem would seem to be solved - we do not reveal the nonce of the sender and do not interfere in the nonce of non-involved participants. But this approach imposes a serious limitation: one account can send no more than one transaction per “epoch”. 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 does not spend a negative amount, otherwise it becomes possible to generate new coins from the air (why this is possible, we wrote in one of the previous articles ). And also to sign "entrances" with a ring signature to prove that among the kneaded coins there are funds belonging to him.
In an anonymous version of the account-based blockchain, expressions for proof are much more complicated. The sender proves that:
For such a complex proof, the authors use a mixture of Bulletproof (one of the authors, by the way, was involved in its creation) and the Sigma protocol , which is called Sigma-bullets. Formal proof of such an assertion is a rather complicated task, and it severely limits the number of people who want to start implementing the technology.
In our opinion, the Zether part, which brings confidentiality 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, you shouldn’t discount the fact that the authors released it just a few months ago, and perhaps someone else will find a solution to the problems that exist today. After all, this is how science is done.
In February 2019, a group of researchers from Stanford University and Visa Research released preprint "Zether: Towards privacy in the world of smart contracts." The authors for the first time 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 the recipient and sender) transactions. We find the proposed technology interesting and would like to share it with the device, as well as talk about why the anonymity problem in account-based blockchains is considered very complex and whether the authors managed to solve it fully.
About the device of these data models
In the UTXO model, the transaction consists of “inputs” and “outputs”. A direct counterpart to “outs” is the bills in your wallet: each “exit” has some kind of denomination. When you pay with someone (form a transaction) you spend one or several "exits", at the same time they become the "inputs" of the transaction, and the blockchain marks them as spent. In this case, the recipient of your payment (or you yourself, if you need a change) receives the newly generated “exits”. Schematically, this can be represented as:
')
Account-based blockchains are roughly like your bank account. They operate only with the amount on your account and the amount of transfer. When you transfer some amount from your account, you do not burn any “exits”, the networks do not need to remember which coins are spent and which are not. In the simplest case, verification of a transaction is reduced to verifying the sender's signature and the amount on his balance sheet:
Technology analysis
Next, we'll talk about how Zether hides the transaction amount, the recipient and the sender. In the course of describing the principles of his work, we will note the differences in the confidential and anonymous version. Since it is much easier to ensure confidentiality in account-based blockchains, some of the restrictions imposed by anonymization will be irrelevant for the confidential version of the technology.
Hiding balances and transfer amounts
To encrypt balances and transfer amounts, Zether uses an ElGamal encryption scheme . It works as follows. When Alice wants to send Bob the b coins to the address (his public key) Y , she chooses a random number r and encrypts the amount:
where C is the encrypted amount, D is the auxiliary value needed to decrypt this amount, G is a fixed point on the elliptic curve, by multiplying the secret key by which the public key is obtained.
When Bob receives these values, he simply adds them to his encrypted balance in the same way, and this scheme is convenient.
Similarly, Alice subtracts the same values ​​from her balance, only using her public key as Y.
Hiding the addressee and sender
The mixing of “exits” in UTXO appeared at the dawn of cryptocurrency and helps to hide the sender. To do this, the sender himself, when making a transfer, enters random “exits” in the blockchain and mixes them with his own. Then he signs "exits" with a ring signature - a cryptographic mechanism, which allows convincing the verifier that the sender's coins are among the implicated "exits". The coins themselves are, of course, not spent.
However, to conceal the recipient, we will not be able to generate fake "exits." Therefore, in UTXO, each “exit” has its own unique address, and it is cryptographically connected with the recipient address of these coins. At the moment there is no way to identify the connection between the unique address of the "exit" and the address of the recipient, without knowing his secret keys.
In the account-based model, we cannot use one-time addresses (otherwise it will already be a “exit” model). Therefore, the recipient and the sender have to knead among other accounts in the blockchain. At the same time, encrypted 0 coins are written off from the kneaded accounts (or 0 is added - in the case of mixing the recipient), without actually changing their real balance.
Since both the sender and recipient always have a permanent address, here it becomes necessary to use the same groups for mixing to the same addresses. It's easier to look at this with an example.
Suppose Alice decided to make a contribution to Bob’s charitable foundation, but prefers that this translation remain anonymous for a casual observer. Then, in order to disguise herself in the field of the sender, she enters more accounts of Adam and Adele. And to hide Bob - in the field of the recipient in addition Ben and Bill accounts. Making the next installment, Alice decided to type 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 will be only one intersecting pair of participants - Alice and Bob, which de-anonymizes these transactions.
Transaction Racing
As we have already mentioned, in order to hide his balance in account-based systems, the user encrypts his balance and the amount of transfer. However, he must prove that the balance on his account remains non-negative. The problem is that by forming a transaction, the user builds a proof regarding his current account status. And what will happen if Bob sends a transaction to Alice, and she will be accepted earlier than Alice sent? Then Alice’s transaction will be considered invalid, since the proof of the balance was built before accepting the transaction by Bob.
The first decision that comes up in such a situation is to freeze the account before the transaction. But this approach is not suitable, since in addition to the complexity of solving such a problem in a distributed system, it will not be clear in an anonymous scheme, whose account will be blocked.
To solve this problem, the technology separates incoming and outgoing transactions: the expenditure of funds has an immediate effect on the state of balance, and receipts - deferred. For this purpose, the concept of "epoch" is introduced - a group of blocks of fixed size. The current "epoch" is determined by dividing the height of the block by the size of the group. Processing the transaction, the network updates the balance of the sender immediately, and the recipient’s funds are put into the drive. Accumulated funds are available to the payee only when a new “era” arrives.
As a result, the user can send transactions regardless of how often he receives funds (as far as his balance allows, of course). The size of an epoch is determined based on how quickly the blocks propagate through the network and how quickly the transaction enters the block.
This solution works well for confidential transfers, but with anonymous transactions, as we will see later, it creates serious problems.
Replay protection
In the 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 created by the owner of this key. But what if the attacker who listened to the transmission channel intercepts this message and sends the exact same second one? The verifier will verify the signature of the transaction and will be convinced of its authorship, and the network will write off the same amount from the balance of the sender again.
This attack is called a replay attack. In the UTXO model, such attacks are not relevant, since 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 field with random data, which is called nonce or simply "salt", is embedded in the transaction. When resubmitting a transaction with a “salt”, the verifier checks whether the nonce has been used before and, if not, considers the transaction valid. In order not to store the entire history of nonce-s in the blockchain, usually in the very first transaction it is taken equal to zero, and then increased by one. The network only needs to check that the nonce of a new transaction differs from the previous one by one.
In an anonymous translation scheme, the problem of validating transaction nonce arises. We cannot bind nonce in an explicit way to the sender's address, since, obviously, this will de-anonymize the transfer. We also cannot add one to the nonce of all participating accounts, since this may conflict with other transfers that are being processed.
Zether authors propose to generate nonce cryptographically - depending on the "era". For example:
Here, x is the sender's secret key, and G epoch is an additional generator for the epoch, obtained by hashing a string like 'Zether +'. Now the problem would seem to be solved - we do not reveal the nonce of the sender and do not interfere in the nonce of non-involved participants. But this approach imposes a serious limitation: one account can send no more than one transaction per “epoch”. This problem, unfortunately, remains unresolved, and currently makes an anonymous version of Zether, in our opinion, hardly suitable for use.
The complexity of the evidence with zero disclosure
In UTXO, the sender must prove to the network that he does not spend a negative amount, otherwise it becomes possible to generate new coins from the air (why this is possible, we wrote in one of the previous articles ). And also to sign "entrances" with a ring signature to prove that among the kneaded coins there are funds belonging to him.
In an anonymous version of the 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 transfer amounts (including zero);
- The balance of the balance varies only with the sender and receiver;
- The sender owns the secret key of his account and he is indeed present in the list of senders (among those implicated);
- The nonce used in the transaction is correct.
For such a complex proof, the authors use a mixture of Bulletproof (one of the authors, by the way, was involved in its creation) and the Sigma protocol , which is called Sigma-bullets. Formal proof of such an assertion is a rather complicated task, and it severely limits the number of people who want to start implementing the technology.
What is the result?
In our opinion, the Zether part, which brings confidentiality 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, you shouldn’t discount the fact that the authors released it just a few months ago, and perhaps someone else will find a solution to the problems that exist today. After all, this is how science is done.
Source: https://habr.com/ru/post/452184/
All Articles