The challenge of signing CoinJoin in a hardware signer

Author: Pavol Rusnak

Source: https://btctranscripts.com/advancing-bitcoin/2022/challenges-in-implementing-coinjoin-in-hardware-wallets

The original text is a transcript of the author's speech at the Advancing Bitcoin 2022 conference, transcribed by delcin-raj via review.btctranscripts.com.

Speech video: https://www.youtube.com/watch?v=gqINXwsR33g

introduction

Hi everyone, I'm Pavol Rusnak, and in the Bitcoin community I'm known as Stik. I'm the co-founder of Satoshi Labs, where we developed the Trezor hardware signer. Today I'm going to talk about the challenges of signing CoinJoin transactions using a hardware signer.

Why is privacy necessary?

Let's first talk about the significance of privacy. Among many reasons, I believe these are the most important.

• Autonomy : Privacy allows individuals to control their own personal information, enabling them to make independent choices and decisions.
• Personal safety : Privacy protects individuals from harm and threats such as stalking, harassment, and identity theft.
• Freedom of expression : Privacy encourages free expression and open communication.
• Trust : Privacy is a prerequisite for building trust between individuals and between institutions.
• Equality : Privacy helps everyone receive equal treatment, regardless of race, gender, religion, etc.
• Democracy : Privacy is crucial to maintaining democracy, as it allows citizens to communicate freely with each other and with their representatives.
• Innovation : Privacy encourages innovation by providing a safe environment for individuals and companies to experiment with and develop new ideas and technologies without theft or abuse.

In summary, privacy is a fundamental human right that protects individual autonomy, personal safety and freedom, while encouraging trust, equality, democracy and innovation.

Privacy in Bitcoin

The current state of Bitcoin privacy

In Bitcoin, transactions are recorded on a public blockchain, allowing anyone to track and analyze them, even tracing back to the past. The true identities of transaction participants are not necessarily known, but these identities are often linked through various means, such as IP address tracking and public information leaks. Examples of transactions being linked to identities include posting donation-receiving addresses in Twitter or Nostr profiles; if the person reuses the address, it's even worse. But none of this is as damaging as the practices of exchanges and their customers.

What are some relevant privacy protection technologies?

• "Confidential transactions" are one type, concealing the transaction amount. However, we need to verify that no new Bitcoins are issued (or destroyed) during this process. This is typically deployed on a sidechain. At the Bitcoin base layer, we do not yet have confidential transaction technology.
• The Lightning Network also contributes to privacy because the blockchain only shows transactions that open and close channels, not every single transaction a user makes within them.
• Some services, such as Tor and private virtual networks, can help you hide your IP address (and thus your geographical location). This also makes it more difficult to link numerous transactions together. For example, on Tor, you can switch identities when sending different transactions, so they will be treated as different people on the network.
• Of course, CoinJoin is one of them.

CoinJoin

Okay, so what is "CoinJoin"? It's a technology that enhances privacy and improves the anonymity of Bitcoin transactions. Multiple participants combine their transactions (that is, aggregate their respective inputs and outputs) and then sign a larger transaction. The final transaction makes it more difficult to associate the inputs and outputs with their respective owners. CoinJoin can be much larger than what I've shown here, but this example is illustrative enough.

Case

Suppose there are three participants who agree to join the same transaction, resulting in 5 + 3 outputs (the extra 3 are for change outputs). Assume there are 3 inputs. You might be able to guess which person each change output belongs to. But with the other outputs, you can't be sure. You can't tell which output belongs to which person. The key here is creating outputs of the same value. This cluster of outputs of the same value creates what we call a "k-anonymity set." In this case, the outputs belong to the same k-anonymity set, where k is 5. Again, you can't guess which person owns which output.

A CoinJoin phase

1. Input Registration : Each participant registers their input with a coordinator. This is typically done via Tor, with each input originating from a Tor identity. After successful input registration, the coordinator gives the participant something (which I call a "token"), but it's not a cryptocurrency token. It could be, for example, a blind signature in Wasabi 1 or an anonymous certificate that can be verified using a key in Wasabi 2. I won't go into further details, but the key point is that this token can be used in the second phase, output registration.
2. Output Registration : Each participant registers their output with the coordinator (using a different Tor identity). The key point here is that because the identity a participant uses is different from the identity they used in the input registration, no association will be detected. Each output registration consumes one token, which is proof that you are entitled to register an output of a specific size. This token is "burned," meaning the coordinator marks it as used. Typically, this token is also tied to a CoinJoin round and cannot be used in another CoinJoin round. This design is also good because this list of tokens can be discarded after the current CoinJoin round, instead of growing indefinitely over time. In some technologies, these tokens can be used indefinitely, but that's usually the case with various e-cash implementations, such as Cashu and Fedimint. Returning to CoinJoin, these tokens can only be used within the current round.
3. Signature : After both inputs and outputs are registered, we combine them into a transaction and send it to each participant for their signature. We can use different identities, but that's not the point. We can even use identities from the first phase, because if you registered an input in the first phase, you're 100% certain you'll sign the same input in this phase. All participants must provide a signature. If the final combined transaction is valid, the CoinJoin is successful, and the transaction is broadcast to the network.

Signing CoinJoin in a hardware signer

status quo

So, what does this have to do with the hardware signature generator? Generally, if you're signing a regular transaction (not a CoinJoin), the hardware signature generator will complete the signing with user intervention. This means the user will confirm the output address (i.e., the output script); then confirm the output amount and mining fees (usually the sum of the inputs minus the sum of the outputs). There's an asterisk here because, typically, the hardware signature generator won't prompt the user unless it detects extremely high fees. I'll elaborate on this later.

challenge

For CoinJoin transactions, we need to complete the transaction signature without user intervention. Why?

Because we don't know when others are ready to sign or when we can enter the signing phase. Typically, we need to participate in multiple rounds of CoinJoin to succeed once. And we don't want users sitting in front of their computers waiting (for two days or more). Therefore, the hardware signer needs to do several things. It needs to check if the sum of the inputs equals the sum of the outputs plus a small difference (i.e., mining fees, coordinator fees, etc.). The difficulty lies in how to correctly identify which input is mine, which output is mine, and their amounts.

Segregated Witness was previously targeted by a fee attack (forging input amounts).

The mining fee is the sum of the input amounts minus the sum of the output amounts. However, the transaction inputs do not contain any monetary information. They only contain the hash value of the preceding transaction and the index number of the output. So, what happens if an attacker lies about the input amount? For example, the input is 10 BTC, but it's falsely claimed to be 1 BTC. Please note that this is on a hardware signature device; you can only verify the output amount, not the input amount. This would cause the user to have 9 BTC converted into transaction fees.

(Translator's note: The author's assumption here is that the attacker tampered with the user's wallet software—in the context of hardware signatureers, "wallet software is untrustworthy" is a common assumption.)

How Trezor mitigates this attack?

Therefore, with Trezor, we always need to pass in the complete preceding transaction so that the hardware signer can calculate the actual value of the input being spent. This can sometimes cause a small problem—the transaction you're spending can be very large. And, as I mentioned, Trezor will display a warning when the fee is very high. If the fee is extremely high, we will directly indicate an error. As long as the fee is below this threshold, we will allow it to pass.

Does Segregated Witness v0 solve this problem?

• The BIP-143 signature also promises the amount of the input to be spent, which is a good thing.
• If an attacker lies about the amount of UTXO, then the signature is invalid and will not be recognized by the Bitcoin network.

The problem with this solution

So we've solved it? No. SegWit v0 doesn't completely fix this problem. Why do I say that?

Suppose a victim has two BIP-143 (SegWit v0) UTXOs, one worth 15 BTC and the other 20 BTC. The malware prompts the user to confirm a transaction. The first input to this transaction is the 15 BTC UTXO, and the second input is set to 5 BTC plus 1 satoshi. The user then selects an output and a change output (if necessary). The user confirms the transaction. However, they only confirm the output. They believe they are spending 20 BTC plus 1 satoshi.

Then, the malware indicates an error and asks the user to confirm the transaction again. This time, however, the malware uses a 1-satoshi denomination in the first input and a 20-BTC UTXO in the second input, and sends it to the hardware signer. From the user's perspective, they can only see the output, not the input. They assume it's the same transaction they signed previously. So the user confirms again, spending 20 BTC plus 1 satoshi.

However, they actually spent 15 + 20 BTC because malware could combine the two signatures to create a transaction that spent both UTXOs. This means that 15 BTC unknowingly became transaction fees.

Does Segregated Witness v1 solve this problem?

Now, BIP341 (Taproot) signatures promise the denomination of all inputs. That's good. So, all signatures in the transaction promise the denomination of all inputs. They also promise the script of the inputs. That's good too. This way, attackers cannot modify the input script. So, is this a complete solution?

question

What do you think? No, not yet. An attacker can still lie about the input script, saying that the input doesn't belong to this wallet. Then they can trick the hardware signer into not taking that input into account. Then, you can perform the same signing twice, extract and collect the two signatures, and then combine them. The attack method is exactly the same.

Solution

This issue was discovered by my colleague Andrew Kozlik in 2020 when developing CoinJoin signatures. He immediately proposed that BIP341 signatures should commit to the scripts of all inputs, not just the script of the input being signed. Fortunately, the discussion progressed quickly, and everyone agreed that this should be done. There was no reason not to. So Segregated Witness v1 did indeed fix this problem. Segregated Witness v1 input signatures commit to the hash of the preceding transaction, the index number of the output being spent, the amount being signed, the total amount of the transaction, the script of the input being signed, and all input scripts. This is where CoinJoin truly benefits from Taproot.

Taproot and CoinJoin

Having the signature commit everything is great for automated transactions that involve external input. For example, in CoinJoin, an attacker cannot change the denomination of the input or the script because if they did, the entire transaction would be invalidated due to the faulty signature.

Certificate of Ownership

However, another point we need to clarify is that attackers can still withhold some information. For example, whether an input belongs to this wallet. Perhaps the attacker doesn't want to tell the hardware signer which BIP32 path was used, and the hardware signer can't figure that out on its own. Then that input won't be evaluated. Therefore, we need some way to determine ownership of all inputs. So how do we do that? This is important for all transactions with external inputs. Not just CoinJoin transactions, but also lightning channels for two-way funding, and so on. So we need a mechanism to reliably determine which input belongs to this wallet. How do we do that?

SLIP 19 Evidence of Ownership

This is called "SLIP 19". SLIP is to Satoshi Labs what BIP is to Bitcoin. The name SLIP 19 stands for "Proof of Ownership", and as the name suggests, it is essentially obtaining three pieces of information with signatures.

1. The first piece of information is the "ownership identifier," which allows us to efficiently determine whether this wallet can spend a UTXO with a given script public key. This is a very simple construction, basically deriving a symmetric key from a seed and then processing this key using HMAC (Hash Message Authentication Code), with the script public key as its message.

HMAC-SHA256(key = 对称密钥; message = 脚本公钥)

1. The other piece of information is the script's public key itself.

2. We also have additional, unrestricted commitment data. You can omit it if you don't want to. But basically, it's a random 256-bit value; in CoinJoin transactions, we use a 192-bit CoinJoin coordinator ID and a 64-bit CoinJoin round ID. But it can be any value, depending on what kind of application you're developing.

Everything will be signed, using a method described in the March 2020 release of BIP322 "General Signed Message Format".

Why don't people use CoinJoin much?

1. First, I think the real problem is a lack of awareness, and I hope we can gradually change this situation.

   1. People are unaware that CoinJoin exists.
   2. People don't understand why privacy is necessary at all.
   3. People don't care about privacy at all. I think we live in a bubble where probably 99% of people don't care about this.

2. Complexity. I mean, there might be thousands of new pieces of information that you have to process in minutes, and you don't even know what you're doing.

3. There is a lack of hardware signature integration. Since CoinJoin wallets are typically networked wallets, you wouldn't want to keep all your satoshis in a networked wallet.

4. Finally, and not insignificantly, there may be legal consequences.

in conclusion

Therefore, I hope the integration of Trezor and the Wasabi coordinator will solve the four problems mentioned above, which will be released later this month. That concludes my presentation. We should have five minutes left to answer some questions.

Q&A

[Audience Member]: I know that Adam Gibson held a workshop on CoinJoin last year, and he seemed to mention another issue, which is that we don't know who the other participants are. Therefore, there seems to be another fear: perhaps all the other participants are from the same entity trying to target you. What are your thoughts on this?

[Pavol Rusnak]: I think Max might be able to give a more detailed answer. But what I'm thinking is that we should try to make CoinJoin as large as possible. I don't know the current limit on the number of participants in a single CoinJoin at the Wasabi coordinator, but I think it allows at least 150 inputs. If there are only 5 inputs, it's obviously much, much easier to attack you, but if there are… I mean, hopefully this integration will attract more people to CoinJoin, and I think we can start increasing the limit. That's about it.

[Audience]: (Unidentified) For example, if I want to deposit money into an exchange, can they refuse the output of CoinJoin transactions?

[Pavol Rusnak]: So, the question is, what is the relationship between exchanges and CoinJoin trading, or rather, how do they view CoinJoin trading? I guess that's their problem, not mine. But I think not all exchanges adopt the same behavior. Some of them will flag all CoinJoin outputs as illegal; they don't want to accept CoinJoin outputs. I know some exchanges are even more extreme, tracking your transactions after you withdraw funds. They'll say you seem to have participated in CoinJoin a few days after withdrawing from the exchange, and we don't like that. I think that's going too far. But I also think what we're doing now is attracting more users to CoinJoin. In the past, it was easy for exchanges to enforce the practice of treating CoinJoin as illegal trading, but if thousands of law-abiding users do the same, then maybe they'll change their approach. If they don't change, I guess they'll run into problems. So, it's like playing a game of strategy, or four-dimensional chess.

[Audience]: Hi, my name is Robert, and I'm running a Start9 node. What's the most important legal defense for using CoinJoin? They're arresting developers, aren't they? How do you defend yourself against it?

[Pavol Rusnak]: How do I defend myself? For example, there's a very large chain store in the Czech Republic that sells electronics. I like to buy electronics from that store using Bitcoin. But I have absolutely no intention of telling them how many satoshis I have. However, if I didn't use CoinJoin, it would be very easy to expose; you could just look at the transactions on the blockchain and immediately see that this person bought electronics. You could say that I've already registered for KYC at that store because I'll have them ship the goods to my address. They might not do that, but they can if they want to. So by using CoinJoin, I'm basically building a firewall between the coins—the coins I spend and the coins still in my wallet.

(over)