[Epic] Add support for coinjoin / Wasabi

[slush0]

To support Trezor in coinjoin wallets like Wasabi (zkSNACKs/zIPs#30), some basic functionality for auto-signing / pre-confirmed signing needs to be implemented in Trezor Core.

Let's discuss how this can be possible in secure way and eventually implement it as standalone firmware app.

---

This epic consists of (edited by @tsusanka):

• Implement SLIP-0019 (support external inputs) #1052 Implement SLIP-0019 (support external inputs)
• Implement the CoinJoin signing flow #1053 Implement the CoinJoin signing flow
• Implement CoinJoin PoC #1054 Implement CoinJoin PoC
• Implement unattended mode #1055 Implement unattended mode

[prusnak]

Supporting EXTERNAL script type is kind of prerequisite here: #38

[prusnak]

What needs to be done is the following:

Create a new message CoinJoinSignTx which resembles SignTx (minus the shitcoin stuff). Signing would be more-or-less the same as normal signing with the following exceptions:

• most of the inputs (TxInputType) would be external (script_type==EXTERNAL)
• at least one input (TxInputType) would be internal (TxInputType with script_type==SPENDWITNESS)
• most of the outputs (TxOutputType) would be bech32 native script_type==PAYTOADDRESS
• at least one (but not necessarily one, can be more) outputs (TxOutputType) would be script_type==PAYTOWITNESS

The transaction is valid ONLY if sum(my_inputs) == sum(my_outputs) + fee_coinjoin + fee_miners

• fee_miners is the same like we do now (compare with maxfee/byte if higher issue warning/error)
• fee_coinjoin is computed like this (0.3% * anonymity_set * denomination) - (anonymity_set is the number of outputs with the same denomination aka value)

[kristapsk]

This looks really Wasabi specific, but with some modifications could work for JoinMarket yield generator bots too, I guess (haven't looked too much into details currently). The rules for ordinary JM CoinJoin tx'es (not PayJoin ones) curently are somewhat like this:

• All inputs are p2sh-segwit
• Zero or one legacy p2pkh or bech32 output, all other outputs also p2sh-segwit
• Will likely be changed to use of bech32 native segwit instead of p2sh-segwit at some point in future
• For maker sum(my_outputs) >= sum(my_inputs) - my_tx_fee_contribution (configurable, default 0)

There was an old issue about this in old JoinMarket's github, see JoinMarket-Org/joinmarket#537 (current codebase is https://github.com/JoinMarket-Org/joinmarket-clientserver).

[prusnak]

Will likely be changed to use of bech32 native segwit instead of p2sh-segwit at some point in future

ETA?

[kristapsk]

Not sure, some support in code already exists (see JoinMarket-Org/joinmarket-clientserver#268), but I think there haven't clear decision about path forward in this regard made yet. Maybe you could catch waxwing, as you are in the same town now, and ask him in a person. Comment from the linked PR few months ago:

Obviously implementing a BIP84 wallet for users can, and probably will be done later, but it will involve us deciding what path forward we want with respect to Joinmarket wallets. One option is to have multiple wallets from one seed, on the different HD paths; another (not necessarily different) possibility might be having totally mixed-address coinjoins. Sounds complicated, but I'm really not sure. I guess the 'easy' option is to just migrate to p2wpkh at some point, which will be the most space-economical, but as we've observed historically, there are of course costs to migrating.

But, yeah, I understand native bech32 p2wpkh is simpler than p2sh-segwit. And I guess it would important only for the maker's wallet protected by a hardware device, other participiants of CoinJoin could in theory use whatever type of inputs or outputs they want, right?

Anyway, looking at the current JoinMarket orderbook, there are market makers keeping tens and hundreths of BTC in their hot wallets currently, so they, very likely, would be ready to pay some significiant amount for a hardware device to have better security for their funds. And others currently are afraid to run yield generator just because of security concerns.

[nothingmuch]

A relevant concern has been raised by Greg Sanders in the context of PSBT based coinjoins w/ hardware wallets is when the host is compromised and lies by omission to the wallet about the which inputs are under its control, effectively a split-brain situation (although it's the same device, i think it makes to think of it this way since the signing device is necessarily unaware of the signing state of transactions).

The proposed solution is ownership proofs, similar to the ones provided during Zerolink input registration but such that a hardware wallet can always reliably know for all inputs in a tx, which are its own when attempting to enforce the amount invariants.

Note that this was raised in the context of using a Ledger, not a Trezor, and I'm not familiar with the details of the host<->wallet communication details, but I still think it's worth noting here.

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014843.html

[prusnak]

@nothingmuch Thanks for the info. Good point. This observation is not specific for coin-join, but rather for all inputs with the EXTERNAL type.

TL;DR: Solution is to add an ownership proof to every EXTERNAL input.

[nopara73]

As discussed ownership proof is not possible since cj has to be signed even when others dont sign (so the coordinator can filter out the DoS attacker.)

[instagibbs]

@nopara73 Can you elaborate more? If you're signing(with sighash all) you know all the UTXOs, why could the signer not be handed a proof along with the UTXO information?

[nopara73]

I was wrong. We have currently ownership proof at registration phase so the backend can always propagate the ownership proofs with the unsigned coinjoin.

[nothingmuch]

edit: sorry @nopara73, i spent so long writing this response I didn't realize you already responded

CcjClient currently proves ownership of a UTXO by signing the blinded output submitted during registration:

https://github.com/zkSNACKs/WalletWasabi/blob/368f0ac75e95efc7380b79b2552171b9c7ee0b1d/WalletWasabi/Services/CcjClient.cs#L534

Assuming a hardware wallet is actually signing these input proofs (I don't see any other way to do this safely, but someone please correct me if I'm wrong as this is a critical assumption I'm making), it should only be signing values that it knows are safe, otherwise a malicious host might be able to use this to obtain signatures that authorize a transaction spending the input. I think the simplest way of ensuring this is not possible is to have the hardware wallet generate the output, blind it, and sign that independently of the host.

Now suppose the response from /api/v3/btc/ChaumianCoinJoin/coinjoin also included these input proofs, so that each signer could independently verify all other inputs have followed the registration. This adds nothing of value right now, but as far as I can tell it's compatible with filtering, since the coordinator can simply omit the irrelevant input proofs on a subsequent signing attempt [1].

However, if the hardware only auto-signs transactions if it sees valid proofs for all inputs, then it can reliably and statelessly identify its own inputs and enforce the fee delta condition. In fact, I'm pretty sure this can be done with no changes to the input proofs as they are currently structured, since the blinding factor could serve the same purpose as the secret x value proposed by @instagibbs, so the condition for auto-signing would be to verify all input ownership proofs, and ensure that all the values that can be unblinded are present as outputs with the correct amount in the proposed transaction. If i'm not mistaken, since BIP 143 signatures also commit to the input amount, if the host lies about these the transaction signature would be invalid on chain, so I believe that is not a concern.

Finally, since the proofs can be optionally obtained in a separate call (instead of modifying the /api/v3/btc/ChaumianCoinJoin/coinjoin response type), I believe this can all be done as a backwards compatible change to the current Zerolink API. This does mean that participants would learn the pubkeys behind with input addresses earlier in the protocol, though I don't think this is a substantial change as those are necessarily revealed to the coordinator anyway.

[1] this is a bit of a tangent, but I don't understand how the coordinator knows which outputs to omit when filtering like this, doesn't this require reregistering outputs? furthermore, wouldn't the coordinator be able to identify all input<->output mappings with a logarithmic number filtered txns, unless the clients enforce that the filtering is monotone and doesn't remove more than some threshold number of inputs?

[instagibbs]

X = HMAC(fixed_key, utxo)
Key corresponding to A signed utxo||amount||X' (amount and X' are provided as PSBT fields)
X==X' -> A is owned by device

If A is owned by device, the host is responsible for giving the device a derivation path to A. The amount field is also only trusted if the derivation path is given and is correct.

N.B. the full previous transactions are required to make this, or any auto-signing scheme secure until segwit v1 where fee is signed.

[prusnak]

@instagibbs We need the opposite thing though. We need a proof that the key DOES NOT belong to the device. What you describe is not enough.

The solution is the following:

X = HMAC(utxo_path, utxo)
proof = (X, utxo_path)

That way Trezor can verify proof of ownership and because it knows the path, it can verify the UTXO does NOT belong to the device itself. (By generating privkey using the path and seing the message was not signed using this key).

[nothingmuch]

If the derivation path is included in the proof, since proofs are known to the coordinator and other participants, and address chains are sequential, this has problematic implications for privacy as they provide identifying entropy for linking otherwise unlikable addresses.

This could be worked around by going against BIP 44 address discovery considerations, i.e. if all outputs use the same derivation path, by using the round ID as the index in the chain, or something like that, but it seems horribly complex.

However I think @instagibbs's latest suggestion is viable. Since the device can recognize as its own all the proofs for which it has derivation path, so long as the outputs are accurately accounted for then the condition on the amount ensures that no signatures will be made if some of the inputs aren't accounted for.

There is one more complication which is that set of outputs summing to an amount could be used for multiple disjoint subsets of the inputs which sum to the same amount, but I think can be addressed by binding the outputs to the inputs, the host must prove to the wallet (without involving the other coinjoin participants). I think the simplest way to ensure this is to make the proofs also include an HMAC(input_key, output).

[prusnak]

Since the device can recognize as its own all the proofs for which it has derivation path

Can you elaborate more on that? How does HMAC(input_key, output) used as a proof actually prove that the input DOES NOT come from the device? Remember, we need to prove not only the other party HAS the private key, but that the other party is not tricking Trezor by providing the ownership proof obtained earlier from the same device. Thus we need to prove the input does NOT come from the currently used device.

[instagibbs]

We need the opposite thing though. We need a proof that the key DOES NOT belong to the device. What you describe is not enough.

It indeed is a proof that it does not belong. Being able to re-generate X', or not, is the identifying trait. If it doesn't match, then it knows it's not its own. It's a slight modification of my original scheme to make sure that the particular X' is never repeated across different UTXOs, and you'd never "bind" that to a UTXO you don't control.

To generate the proof you of course have to supply it the derivation path(so it doesn't HMAC a utxo it doesn't control), and of course for signing later.

[nothingmuch]

Can you elaborate more on that? How does HMAC(input_key, output) used as a proof actually prove that the input DOES NOT come from the device?

It would not, but that is achieved by @instagibbs's scheme so long as it commits to the amount as well.

I was suggesting adding an additional field to the proof. However, I'm sorry, but I made a stupid mistake (coffee underflow error). To reliably determine the amount, the wallet also needs to know which outputs belong to, and withholding the derivation path is possible there too. But host can only trick the wallet into accepting a larger amount in total, so this is unnecessary.

The concern about privacy is still relevant and very important in the Wasabi use case though.

[AdamISZ]

Not sure, some support in code already exists (see JoinMarket-Org/joinmarket-clientserver#268), but I think there haven't clear decision about path forward in this regard made yet. Maybe you could catch waxwing, as you are in the same town now, and ask him in a person. Comment from the linked PR few months ago:

Obviously implementing a BIP84 wallet for users can, ...

Just to answer this point, BIP84 wallet is already implemented now. It can be used for PayJoin (you can set native=true in the config, it's mentioned in the PayJoin doc), but as you note there's always a troublesome point in thinking about updating Joinmarket coinjoins, given the consensus-y nature. Thanks for raising the point though @kristapsk !

[prusnak]

Let's refactor the signing code first: #617

[andrewkozlik]

I wrote up a spec for proofs of ownership (SLIP-0019), which is currently under review. However, I have been thinking that for some applications we might not even need proofs of ownership. The idea that I am contemplating is this:

If Trezor is asked to sign a transaction with external inputs, all of which have already been signed, then it can safely sign the remaining inputs to the transaction without risking the kind of attack described here and here.

Of course for this to work, Trezor needs to be able to verify the signatures of all the external inputs against their scriptPubKeys, so the implementation still involves quite a bit of work in Trezor. The major advantage to this solution is that the other parties providing inputs don't need to support SLIP-0019 and there is no need to exchange the proofs. In particular this could be used in certain PayJoin applications like BIP-0079 (BustaPay). However, I wonder if this idea isn't overlooking some vulnerability...

[Hannsek]

We do not need to have this epic anymore. Therefore I am closing it now.