Write in front:
In the game "Final Fantasy", the all-powerful warrior Basho from the Landis Republic is called the strongest shield. He has been battle-hardened and determined, and is regarded as a hero by his people. In the blockchain world, Zcash, Monero, and zero-knowledge proofs exist. They are also known as the strongest shields of privacy. They can effectively ensure that transaction information is not leaked. However, there is really a secret in this world. The wall?
In this issue of academic sharing, we focus on recommending the latest research result "Side-Chain Attacks on Anonymous Transactions" by Professor Dan Boneh and others from Stanford University.
In the hardcore technical article selection section, we will also see zkSNARK proof optimization, Taproot / Schnorr upgrade, Lightning Network limitations, Substrate and other content.
In addition, in the past week, Ethereum 1.X, Ethereum 2.0, and Layer 2 also ushered in many technological advances.
(Picture from: tuchong.com)
As the largest cryptocurrency, Bitcoin's transactions are actually not anonymous. Many academic studies have shown that Bitcoin's transaction graph can be effectively deanonymized, even for many so-called anonymous cryptocurrencies.
For those users who want to obtain transaction privacy on the public blockchain, anonymous cryptocurrency systems such as Zcash and Monero use fairly advanced cryptographic primitives, such as concise zero-knowledge proofs (ZkSNARKs) and ring signatures, providing a higher degree of unlinkability. Can users rest easy using such a system?
In fact, despite their strong protection of cryptographic primitives, there will still be some protocol-level privacy attack methods that threaten the privacy of these systems. This is also the latest in cryptography bulls such as Stanford University professor Dan Boneh Research results.
Original paper link: https://crypto.stanford.edu/timings/paper.pdf
( Note: The researchers disclosed these attacks to the Zcash and Monero security teams, and they have fixed related vulnerabilities in the latest version of the client. For example, Zcash v2.0.7-3 client introduced initial fixes, v2.1.1- Version 1 client introduced further fixes for the time-side channel in block processing. Monero introduced a fix in the v0.15.0 version client. Users who update the client to the latest version will not be vulnerable to such attacks In addition, because attacks require surveillance and participation in Zcash or Monero networks, such attacks cannot be traced back to previous transactions . )
1.1 Architecture of Anonymous Payment System
Before describing the related attacks, let's first understand some core design concepts of privacy cryptocurrencies (taking Zcash and Monero as examples). These cryptocurrencies are built on Bitcoin's UTXO (Unspent Transaction Output) model, which means that each transaction will consume the output of previous transactions and generate new outputs. These collections of UTXO are recorded in the blockchain and represent the total currency in circulation.
Each user of the currency owns one or more public keys (also known as addresses) and connects to a P2P network to send and receive transactions.
Privacy goal : In Bitcoin, UTXO is an
（amount，pk） tuple, where
pk represents the recipient's public key. In order to use this UTXO later, the receiver generates a signature under the corresponding key. In this way, a transaction shows the amount of currency used, the source of funds (that is, which UTXO was used) and its destination (the public key of the new UTXO owner).
In addition, a user's public key can be linked to a P2P node to which he or she is connected when sending transactions to the network.
Anonymous cryptocurrencies such as Zcash and Monero are designed to provide the following stronger privacy guarantees:
- Confidentiality : The transaction does not disclose the transaction amount;
- Untraceability: When a transaction costs UTXO, it is difficult to identify the transaction that generated the UTXO;
- Unlinkability : Given two transactions sent to the network (at most one sent by an adversary), the adversary cannot determine whether they paid the same address. In addition, given two addresses, the adversary cannot determine whether they belong to the same user;
- User Anonymity : Given a user address (that is, the public key), the adversary cannot determine how the owner of the address is connected to the P2P network;
These privacy guarantees are usually achieved through a combination of cryptographic technologies. Below we will briefly describe these technologies:
- Confidential transaction technology (CT) hides the amount of transaction funds. The UTXO form of a confidential transaction is
(Commit(amount), pk), that is, they only show the cryptographic commitment of the transaction amount. The transaction also includes a proof that its total balance is zero.
- UTXO Anonymous Sets provide untraceability by hiding the identity of transaction inputs. Specifically, anonymous transactions do not show the UTXO it spends, but only a super UTXO set, and a zero-knowledge proof of some UTXO ownership in this set.
- Obfuscated and diverse addresses guarantee unlinkability. To prevent the linkability of transactions sent to the same address, UTXO for anonymous transactions contains a "obfuscated" public key (for example, the promise of the key in Zcash). Diversified addresses (or subaddresses in Monero) enable users to trade anonymously with multiple entities without having to manage multiple keys. With a single key
sk, the user can create multiple public keys
pk1,…… pkn. These keys are not linkable: it is difficult to determine whether the two public keys pk, pk0 are from the same key.
Blockchain scanning is a technical consequence of unlinkability. Because UTXO for anonymous transactions does not clearly show the recipient's public key, users must scan each new transaction and perform various cryptographic operations to check whether the transactions are related to them.
User anonymity is guaranteed by untraceability and unlinkability. Because the transaction does not show the sender's or receiver's public key, the user's public key cannot be linked to the P2P node it uses to send or receive transactions.
Figure 1: Side channels in the life cycle of anonymous transactions
(1) The user's wallet creates a transaction, which involves generating a cryptographic certificate. This calculation can be performed locally or outsourced to a remote service. (2) The wallet sends the new transaction to the P2P node, and the P2P node broadcasts it to the network. (3) The P2P node shares the received transaction with the connected wallet. The connection can be local or remote. During transaction creation, opponent 1a can time outsourced proof generation to leak certain transaction secrets. When a new transaction is processed, the wallet's behavior may change when it acts as the beneficiary of the transaction. If the wallet is connected to a remote node, this can be inferred by opponent 1b observing the communication mode between the wallet and the node, or opponent 3 who controls the node. If the wallet and the node are in the same location, the opponent 2 who interacts with the user's P2P node can infer the change in wallet behavior.
The life cycle of anonymous transactions. Figure 1 illustrates how anonymous transactions can be created over a P2P network and shared with nodes and wallets:
- In order to send new transactions, the user's wallet selects some UTXO and generates a zero-knowledge transaction validity certificate;
- The transaction is sent to a P2P node connected to the wallet and shared with the network. P2P nodes store these transactions in their "mempool";
- P2P nodes share these transactions with the connected wallet. The wallet scans each new transaction to check if it is the payee of the transaction. Once a transaction is included in the block, steps 2 and 3 are performed. When a block is mined, the block and the transactions it contains will be broadcast to all P2P nodes. Block transactions are then shared with the user's wallet.
After understanding the structure of the anonymous payment system, let's briefly understand the consequences of the attacks proposed by the researchers.
It is reported that these attacks use communication modes or time information leaked from different parts of the system. The attacker observes the life cycle of anonymous transactions in the system through a systematic method. At each step, researchers look for side channels and evaluate their impact on user privacy.
During the anonymous transaction life cycle shown in Figure 1, an attacker can observe side channel information at each of these steps and try to understand information about the transaction, such as the identity of the intended payee (for example, their public key Or the IP address of their P2P node), the amount of funds transferred or the source of funds transferred by the transaction.
Here are the findings:
1. In Zcash, the user's wallet and P2P nodes run in a single process. The wallet checks to see if it is the payee of every incoming transaction by trying to decrypt it with its key. This leads to two sources of side channel leakage: (1) if the decryption is successful and the decrypted transaction (called Note plain text) is in the correct format, the wallet will perform an additional Pedersen commitment check; (2) if the decryption is successful, But the decrypted transaction format is incorrect, the wallet will throw an exception, and the exception will be propagated to the node's P2P layer.
In the first case, the time it takes to perform the additional Pedersen commitment check will cause the P2P node's response to subsequent network messages to be delayed.
Therefore, researchers have proposed an attack called PING. The attacker can use the delay in the ping response to infer whether the node is the payee of the transaction. This undermines the unlinkability of transactions.
In the second case, the researchers proposed a REJECT attack in which the attacker carefully handles malformed transactions, encrypts them with a known (but anonymous) public key, and sends them to the target P2P node . If the decryption is successful, an exception is triggered, and the target node sends an explicit "reject" message back to the attacker.
After receiving this message, the attacker can know that the selected public key belongs to the owner of the target P2P node, which violates anonymity.
For more information about PING and REJECT attacks, interested readers please refer to Section IV of the original paper.
2. For Monero, its wallets and nodes also run in separate processes. Studies have shown that payment reception will change the communication mode between the wallet and its nodes.
If the wallet is connected to a remote node (common in a mobile wallet, or when first synchronizing with the network for the first time), a passive network adversary can infer whether the wallet is the recipient of a recent transaction. (For details, see section 5 of the original paper)
In addition, even if the user's wallet and node are in the same location, researchers have shown that remote adversaries can cause and observe the Lock Contention of node resources to infer the wallet-to-node communication mode.
The researchers verified this time attack on the WAN, and an attacker based in London could infer whether the victims (nodes and wallets running in Zurich) had received the payment.
For Zcash and Monero, this type of attack enables remote adversaries to link anonymous transactions by identifying P2P nodes for each transaction payee. As described below, the attack can be further exploited: (1) identify the IP address of their P2P node based on the user's public key; (2) break the unlinkability of various addresses belonging to the same user.
For Zcash, these attacks can also: (3) cause Zcash nodes to crash remotely given a user's public key , and (4) create on (non-constant time) ECDH key exchanges involving users' long-term secret viewing of keys Remote time side channel, which may lead to the leakage of the viewing key .
These attacks could put privacy-conscious cryptocurrency users at risk. For example, an adversary linking a user's anonymous public key to its P2P node can discover the user's true identity or location, and an unlinkable adversary can infer which P2P nodes belong to the user who is conducting a transaction.
3 Side channels in zkSNARK generation. In addition, researchers also observed that in Zcash, the time to generate zkSNARK is not constant, but depends on secret information such as Hamming-weight of the transaction amount . Research experiments show that the current implementation of zkSNARK is not zero-knowledge: the information collected from time leaks will invalidate the zero-knowledge attribute. If the adversary is able to measure the running time of the zkSNARK generation process, this information can be extracted. Of course, as explained below, in the current Zcash system, it may be difficult to exploit this leak.
Overview of attack methods
After understanding the consequences of the attack, we will focus on understanding this type of general attack method and the time attack against zkSNARK Prover, and the specific attack methods against Zcash and Monero will be omitted.
The attack described in this article is a remote side-channel attack. Therefore, it does not require the victim's software to be replaced. We can consider such a remote adversary, as shown in Figure 1:
- An online adversary (adversaries 1a and 1b in Figure 1) monitors encrypted traffic between the victim's wallet and a remote service (such as a node or a validator).
- A P2P opponent (Rival 2) participates in the P2P network. Attackers may deviate from the P2P protocol.
- A remote node adversary (Adversary 3) controls a third-party P2P node and monitors (plaintext) communication between the victim's wallet and that node.
2. Attack type 1: receiver-side channel
The study found that the most practical and common side-channel attack affects the last stage of the anonymous transaction life cycle shown in Figure 1 (that is, when the wallet processes new transactions). These attacks enable remote adversaries to undermine the system's unreachability and anonymity guarantees.
This attack takes advantage of a common design flaw in related anonymous cryptocurrencies, where the user's wallet regularly checks if it is the payee of any new transaction.
Objective: This type of attack is aimed at transaction unlinkability and user anonymity. Therefore, the goals of the attacker are: (1) determine whether two transactions pay the same address, and (2) determine how users with known addresses connect to the P2P network.
This attack targets common deployments of wallets and P2P nodes, and its actual goal is to identify the P2P nodes being used by transaction payees. In a setup where multiple users connect their local wallets to a shared remote P2P node, an attack initiated by a network adversary or a remote node adversary can further identify the actual wallet used by the transaction payee.
Consider two different attack scenarios here:
- The adversary knows an anonymous public key and sends a transaction to the key to confirm the P2P node (or wallet) used by the key owner to receive the transaction.
- An honest user sends a transaction without the opponent knowing the intended payee or its public key. The opponent decides which P2P node (or wallet) the payee of the transaction uses.
In fact, the latter attack scenario encompasses the first case because the adversary can send a carefully crafted transaction to a known public key. The latter scenario will directly lead to the interruption of transaction unlinkability.
Given two transactions sent to the network, the opponent only needs to determine whether the recipient of the two transactions used the same P2P node or wallet. In addition, both attack scenarios represent a disruption in user anonymity and can be used for other privacy violations:
- The IP address is restored, and the adversary can link the public key to the IP address of the owner's P2P node (if connected to a remote node, it can link to its wallet) unless the owner uses an anonymous tool such as Tor. This information can then be used to identify and geolocate victims.
- Linking diverse addresses, given two public keys, an attacker can determine if they belong to the same user. The attacker sends a transaction to each public key and checks if the same node or wallet is identified. This breaks the unlinkability of multiple addresses.
- Recovering private keys, the loopholes behind these attacks, also opened the way to extract the victim's "view" key through a time-side channel. Stealing this key allows the adversary to link all transactions sent to the victim ( but cannot steal the victim's funds ).
The researchers' attack took advantage of the differences in how cryptocurrency wallets (payees and non-payees) handle transactions.
This difference in wallet behavior is not a problem in itself, because remote attackers cannot directly interact with the user's wallet. However, the study found that due to various design flaws, differences in wallet behavior affect the interaction between the wallet and its P2P nodes. This, in turn, allows remote attackers to infer changes in wallet-to-node interactions through various side channels.
In response, researchers have proposed two general attack strategies:
- Strategy 1. Traffic analysis of wallet-to-node communication. If the wallet is connected to a remote node, the network adversary or remote node adversary can observe changes in wallet-to-node interaction.
- Strategy 2. Infer wallet behavior from the P2P layer. If the wallet and node are in the same location, the remote adversary cannot observe their interaction. However, if the change in wallet behavior affects the interaction between the user's P2P node and the remote peer node, information will still be leaked to the opponent.
These two strategies are not only applicable when creating a transaction and sending it to a P2P network, but also when including it in a block. At this point, the block and all of its transactions are shared with each peer, and the wallet reprocesses the transactions to ensure they are valid (e.g. to ensure that they are not double-spend).
3. Attack type 2: Sender-side channel
The attack described above breaks the unlinkability of anonymous cryptocurrency transactions and the anonymity of users, which takes advantage of flaws in the design of P2P clients and wallet systems. Therefore, they are not attacks directly against protocol cryptography protection. In order to expand the investigation of side channel vulnerabilities in anonymous transactions, researchers have also conducted research on cryptographic tools, and these tools ensure the confidentiality and untraceability of transaction creation. The paper specifically mentioned is the current The zk-SNARKs are the most concise zero-knowledge proofs used by the cryptocurrency industry .
Note that the attacks described in this section are actually more theoretical in nature. Although they are unlikely to affect current users, the existence of such attacks once again illustrates the importance of the implementation of sideless cryptography for anonymous systems.
Attack target: The sender of the transaction responsible for ensuring the confidentiality and untraceability of the transaction.
As discussed below, the most likely target of a remote attack is to restore the transaction amount, thereby undermining the confidentiality of the transaction.
However, remote side-channel attacks created against transactions actually face many challenges:
- Non-interactive : users can create transactions without interacting with any other party;
- Transient Secrets : Many transaction secrets (such as transaction amounts, and UTXO-related secrets) are one-off. Therefore, even if there is a side channel, the adversary can try to extract these secrets at once;
- High entropy secrets : long-term secrets used to create transactions (such as the user's key) have high entropy and require the extraction of high-precision side channels;
Research shows that opponents can theoretically overcome these challenges, with the goal being the proof phase of the transaction creation process, and (partly) revealing the confidential amount of the transaction.
We know that zero-knowledge proof is the basic construction technology for anonymous transactions. In the zk-SNARK protocol, the prover has some secret input (called witness) and convinces the verifier that the witness meets the given Assert without revealing any other information about witness. In Zcash and Monero, this type of proof proves the validity of the transaction, while retaining the privacy of the transaction. For example, in Zcash, the proof witness includes a list of used UTXOs, recipient addresses, transaction amounts, and proof that these UTXOs exist and belong to the payer, and all funds are transferred to the receiver.
Time-side channel in zk-SNARK prover. The researcher's thesis is that in the current implementation of zk-SNARK, the time it takes to generate proofs will reveal information about the secret witness's witness, especially the amount of spent coins, however, as mentioned above, due to the The interactive nature, it may be difficult for a remote adversary to obtain a time-side channel during the proof generation process. To make matters worse, the proof generation time may not be sufficient to extract secrets that are transient or have high entropy.
Despite these challenges, we point out below that in some deployment scenarios, a remote time attack on the zk-SNARK prover of anonymous cryptocurrency is possible, and demonstrate the importance of proof generation time, which can reveal the importance of secret transactions information.
Regarding non-interaction, the researchers made two observations:
- If a weak client (such as a mobile wallet) outsources the proof to a remote service, the network adversary can time the prover. Although certification outsourcing is not common, the Zcash protocol supports this feature. The remote certification service is designed for earlier versions of the protocol. Therefore, some users may choose to delegate the certification to a remote service;
- More generally, an adversary can monitor P2P networks to obtain out-of-band information about when the transaction creation process started, and observe when it ends. For example, users can set up recurring payments where transactions are created at a fixed time. An adversary can also trigger a transaction as part of some external agreement. The researchers mapped a time-side channel connection for the digital signature. Although the signature is non-interactive, protocols using it (such as TLS) can introduce remote side channels.
For the attacker, the target of the attack is the transaction volume, which is a non-encrypted value, and even a rough approximation (a single-time leak measurement) constitutes a violation of privacy.
Attack strategy. Researchers have considered a cryptographic time attack that utilizes time variation in arithmetic operations (depending on the value of the operand).
Research takes advantage of the fact that the time to produce a proof is related to the witness's witness value. Since witness contains the transaction amount, the goal of the attack is that the amount is related to the proof time. For example, Zcash's proof decomposes the transaction volume into bits and calculates an elliptic curve operation for each non-zero bit. Therefore, the proof time and the Hamming weight of the transaction amount are closely related, that is, the proof time is also related to the value of the transaction amount .
1.4 Time Attack on zkSNARK Prover
Next, we enter the time attack part of zkSNARK Prover. According to the strategy described above, our goal is to recover information about the amount of confidential transactions from a single time metric generated by the proof.
In the following sections, researchers demonstrate how this time attack can reveal information about transaction volume in Zcash.
For special purpose proofs implemented in Monero, similar attacks are ineffective.
1.Time side channel in Zcash Prover
The researchers said that for Zcash's zkSNARK system, the proof time depends to a large extent on the value of the witness' witness. That is, for anonymous transactions, the proof time is closely related to the secret value of the transaction.
To send a transaction, the sender creates two proofs, one of which proves that UTXO ownership has been spent, and the other proof that the new UTXO is well-structured.
Zcash uses the Groth16 proof system. For the purpose of attack, as long as you know the prover encodes witness into a vector (a1, …, am) field element, and the main calculation of the prover is the following form of "multiple exponential operation" :
Gi is a fixed elliptic curve point, it is important that the implementation of Zcash optimizes
aiGi , where
ai = 0 . Therefore, the proof time is related to the number of non-zero field elements in the witness's witness.
Since the transaction volume in witness is binary coded, its Hamming weight value will affect the proof time. Moreover, since the weight of the binary representation is related to the absolute value of the number, it proves that the duration reveals information about the amount of the confidential transaction.
To evaluate the time attack, the researchers conducted an experiment.
The figure below shows the mean and standard deviation of the proof time for each quantity. The results show that there is a strong correlation between proof time and transaction amount (R = 0.57). Although a time leak can only give a rough approximation of the amount, this is enough to allow the opponent to identify rare transactions of great value.
Figure: Correlation between transaction amount and prover time in Zcash, the correlation coefficient is R = 0.57
Discussion and conclusion
Compared with the attack on Zcash and Monero mentioned in the paper (which has been fixed), the above-mentioned time attack is not easy to apply. It requires the adversary to time the proof generation, which depends on the user's common mode (such as repayment ) Or deployment strategy (for example, outsourcing proof to a remote service).
If a timing opportunity does exist, research suggests that this breach would allow attackers to make rough estimates of the amount of private transactions.
Of course, local side channel attacks would be more effective, however, Zcash explicitly denies this threat.
Ultimately, the existence of such an attack may pose a potential threat to the implementation of non-constant time cryptocurrencies. Zcash developers are developing a more mature version of the elliptic curve algorithm and may deploy it to the master client in the future.
Free and easy comments: The introduction of this type of attack has brought new challenges to the design of anonymous trading systems. The researchers hope that this work will remind relevant project parties and users about the threat of side channel leakage, and promote the development of cryptographic primitives such as the constant time zkSNARK prover.
Second, hard core technical articles of the week
2, 1 zkSNARK proof optimization, reducing the settlement cost of DEX to $ 0.000124 per transaction
In this article, Loopring Chief Architect Brecht Devos explains how to optimize the libsnark source code to reduce the total settlement cost of DEX to $ 0.000124 per transaction and reduce the cost of the prover to 0.000042 per transaction USD, this result is about 15 times lower than the previous verification cost.
Article link: https://medium.com/loopring-protocol/zksnark-prover-optimizations-3e9a3e5578c0
2, 2 Dry Goods | Read the Taproot / Schnorr Upgrade of Bitcoin
In this article, Zou Chuanwei, chief economist of Wanxiang Blockchain and PlatON, introduced the current ECDSA signature algorithm used by Bitcoin and the technical details of the upcoming Taproot / Schnorr signature upgrade.
Article link: https://www.8btc.com/media/562991
2, 3 Breakthrough of the impossible triangle of the blockchain (5): Lightning Network, off-chain technology, and their limitations
Blockchain consensus algorithm scholar maxdeath introduced the basic principles of the Lightning Network, the basic principles of HTLC, and the limitations of this type of offchain technology in this article.
Article link: https://www.8btc.com/media/563219
2, 4 Substrate Minimalist Summary: Functions, Features and Consensus
Author DmitriyKashitsyn introduces the main goals and features of the Substrate framework in this article. Although this is not enough for you to learn to write related code, it will at least give you some advantages of the framework.
Article link: https://www.8btc.com/article/560185
2,5 BM latest works: the trade-offs behind the blockchain
Since 2009, BM has been working on blockchain technology research, and he found that one helpful thing is to think about all the design trade-offs that people can make, which is not like "fastest", "most scalable" , "Most Decentralized" or "Best Governance" is as simple as that. When choosing which blockchain technology is best for your application, this article will explore some less common issues.
Article link: https://www.8btc.com/article/562686
Third, Ethereum development update progress
Ethereum 1.X updates:
- Latest stateless Ethereum client R & D update : Witness format and data retrieval issues;
- The latest Nethermind client solves some peer node problems;
Ethereum 2.0 research and development update content:
- Popular knowledge about the latest knowledge of Ethereum 2.0 ;
- Nimbus client update : discv5, BLS signature, lightweight stack trace;
- Train and Hotel EE ;
- Reward and punishment in Ethereum 2.0 ;
Layer 2 research and development updates:
- Loopring launched DEX based on zk-rollup technology , with an initial TPS of 100;
- Run Fuel optimistic rollup in NodeJS in minutes ;
- PlasmaLeap turned to rollups ;
That's it for this issue, see you next week ~