Malleability

[AdamISZ]

Kept forgetting to add this as its own issue. Haven't had enough time to look into it yet, but my memory is that it isn't an issue for "first phase" (TX0/1) since we wait for confirms, but it is certainly an issue w.r.t monitoring the backouts. Some reworking of blockchaininterface monitoring mechanism is, I think, needed (labeled as 'enhancement' on the basis that this work needs doing). I won't let this block a testnet release though, so marked "0.1".

[chris-belcher]

I believe I have a solution here: https://bitcointalk.org/index.php?topic=303088.msg18149691#msg18149691

The solution is for each side to demand multiple signatures for the refund transactions TX2 and TX3 before continuing with the protocol. One signature for each possible malleation of the the funding transactions TX0 and TX1. That way if malleation of TX0/1 does happen then the victim already has a valid signature to use and can get their money back.

Now, for p2pkh inputs the only possible method of third-party malleation is to flip low-S and high-S. So each input has two possible signatures, and a transaction with N inputs has 2^N possible signatures, which isn't too bad as long as N is low. For example if funding transaction TX0 has 5 inputs, 32 signatures must be transmitted.

[AdamISZ]

I believe I have a solution here: https://bitcointalk.org/index.php?topic=303088.msg18149691#msg18149691

Yes, that's a good thought, I seem to have heard it somewhere recently. We would need certainty though that there isn't some script malleability, right.

[chris-belcher]

I believe we only need to handle the malleability with the funding transactions TX0/1, and they could be made to only have p2pkh inputs. Then the highS thing is the only malleability method.

P2SH multisig has malleability possibilities (such as the dummy arg in OP_CHECKMULTISIG) but I don't believe it causes problems for coinswap.

[AdamISZ]

See this note from @NicolasDorier: https://twitter.com/NicolasDorier/status/873737676234543104

Mailing list: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-August/013014.html (as noted, some useful discussion follows)

Relevant to https://github.com/bitcoin/bips/blob/master/bip-0199.mediawiki which is an attempt to genericize these contracts.

As I currently understand, I see no disadvantage to modifying the script to OP_DEPTH 3 OP_EQUAL OP_IF <etc.> ; will test this update shortly. It's a simple change.

[NicolasDorier]

Just for reference, sent that to author of the BIP

Hey,

I saw BIP199, I think the HLTC contract should be improved.

---------------
OP_IF
        [HASHOP] <digest> OP_EQUALVERIFY OP_DUP OP_HASH160 <seller pubkey hash>            
    OP_ELSE
        <num> [TIMEOUTOP] OP_DROP OP_DUP OP_HASH160 <buyer pubkey hash>
    OP_ENDIF
OP_EQUALVERIFY
OP_CHECKSIG
----------------

For taking first branch, script sig is

-------------
<sig> <pubkey> <preimage> 1
-------------

Problem is, "1" can be malleated by any third party.

This can be prevented with this

---------------
OP_DEPTH 3 OP_EQUAL OP_IF
        [HASHOP] <digest> OP_EQUALVERIFY OP_DUP OP_HASH160 <seller pubkey hash>          
    OP_ELSE
        <num> [TIMEOUTOP] OP_DROP OP_DUP OP_HASH160 <buyer pubkey hash>
    OP_ENDIF
OP_EQUALVERIFY
OP_CHECKSIG
----------------

and  script sig would be

-------------
<sig> <pubkey> <preimage>
-------------

Check also https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-September/013095.html

This is also the approach we take in tumblebit.

[AdamISZ]

Implemented this idea in 7d302ba , but keeping it as pubkey not pubkey hash on both branches, and so using OP_DEPTH 2 instead of 3 (it's (sig, preimage) for IF and just (sig,) for ELSE). Also I didn't bother to take the checksig out of the if/else, but, trivial point.

So to sum up, CoinSwapTX23 scriptPubKey is:

OP_DEPTH 2 OP_EQUAL OP_IF
       OP_HASH160 <digest> OP_EQUALVERIFY <pubkey1> OP_CHECKSIG
    OP_ELSE
        <num> OP_CHECKLOCKTIMEVERIFY OP_DROP <pubkey2> OP_CHECKSIG
    OP_ENDIF
`

[AdamISZ]

Some discussions on IRC led us all to realise that there is a serious issue here, far more than I'd originally thought:

The backouts are invalid if the original TX0/TX1 is malleated before being confirmed. It's third party malleability that's really the issue here; Alice will not want to spend her TX0 with a txid that invalidates her own backout, and likewise Carol for TX1. But if a miner (or say Carol is a miner) malleates in-flight a TX0/1 which is not their own, then Alice e.g. is left with a deadlock on retrieving her funds from TX0, since her previously agreed backout TX2 is invalid.

Malleability here could be something like this example from @fivepiece (see the first input). We can stick to script malleability since as mentioned, high/low s isn't a problem. But it is possible specifically to add OP_NOP to a scriptSig without affecting validation, but creating a new txid. OP_DEPTH doesn't help here because OP_NOP disappears from the stack.

According to my/our current understanding, this breaks the Coinswap design used here. Accounting for all possible such malleation and storing all possible txids appears to be infeasible.

[NicolasDorier]

OP_DEPTH helps only for malicious non-miner third parties. Without the OP_DEPTH, anybody can create a standard malleated transaction, which will be propagated and mined even by non malicious miners.

I don't understand why CoinSwap design is broken? You just have to wait that the HTLC transactions are confirmed before cashing out. I don't see either how segwit would help, as this should be done with segwit also anyway.

I think you are mixing with the old design which relied only on nLockTime, and that was more complex. (there was no CLTV at the time). I quote:

both sides prepare a spend-in (TX-0, TX-1) to the 2 2-of-2 addresses, and pass over the txid. Alice passes over the hash of X. Then both sides prepare the same TX-2 and TX-3 backout transactions, with scriptPubKeys as above (p2sh wrapped of course), and both sign and pass signatures, so both sides have broadcast-able versions of these backouts in advance of publishing TX-0 and TX-1.

The difference is that thanks to CLTV, TX-0 and TX-1 can be safely broadcasted without risk of deadlock.
It should be corrected to

both side prepare a spend-in (Tx 0, Tx 1), broadcast them, wait to have a conf....

Once confirmed, Alice announce Tx0 + merkleproof to Carol.
Carol verifies and track the scriptPubKey of the HLTC scriptPubKey (use importaddress+importprunedfunds rpc to track and verify with Core) and pass Tx1 + merkleproof to Alice.

Alice cashout.
Carol learns the hash and cashout as well.

[fivepiece]

@NicolasDorier , TX0 and TX1 aren't the HTLCs, but the normal 2-of-2 multisigs that pay into the HTLCs (TX2 and TX3). So in a successful coinswap, the HTLCs wouldn't be published to the network at all as the swap happens between TX0 -> TX4 and TX1 -> TX5. The breakage here happens when either of TX0 or TX1 txid's are changed and one side's backout (TX0 -> TX2 or TX1 -> TX3) becomes invalid. In this case, the other side has complete control as they can just refuse to continue the protocol, redeem their own backout when possible for them, then they can hold the other side hostage for more coins (needs both keys to spend from the mallealated TX).
If we first broadcast TX0 and TX1 before having some backout set, how will we set the backout in case one TX confirms and the other doesn't, or even if both do confirm but one side just vanishes?
Sorry if I just missed your point, appreciate the input.

Another thing, not very related but worth writing down, even if we could request a signature for the sighash only without revealing a txid, it's still vulnerable to the same issue (miner will see this sighash once the tx is in their mempool).

[NicolasDorier]

oh sorry, for some reason I thought CoinSwapCS was a cross chain swap done in the same chain. (which , by thinking about it, would have made no sense as it would be possible to link by using the common hash)

I need to read more slowly your README so I understand better this protocol.

[AdamISZ]

@NicolasDorier sorry the documentation is a bit "nascent", I recommend going to docs/ directory, read coinswap_tweak.md in conjunction with the diagram at the bottom of coinswap_new.pdf

At the same time, could you point me in the direction of the exact protocol you mean by "cross chain swap"?

[AdamISZ]

I suspect this works: the destination 2 of 2 for TX0 is replaced with a "2 of 2 or timeout" (IF 2-2 OR CLTV timeout, locked to Alice) and likewise for TX1.

The timeout would have to be >> L0, L1 (the existing timeouts for the existing backouts TX2, TX3), I think.

The idea would be that if TX0 ends up getting confirmed with an unexpected txid due to malleability, Alice would just stop and wait for timeout to recover. But she couldn't do that during the following of the existing protocol (i.e. if TX0 were not malleated), since the timeout is way outside.

Even if I'm right about that, I am not exactly enthused by the idea of making it even more complicated. Will keep thinking about it.

Edit: just realized that this idea has a huge disadvantage: we lose the anonymity set of vanilla 2/2, 2/3 : the redemptions in normal runs TX0->TX4, TX1->TX5 now have customised scripts.

[NicolasDorier]

Cross chain swap:

• Alice wants to exchange 1 BTC against 1 LTC with Bob
• Alice gives H=Hash(preimage) to Bob.
• Bob makes an output of 1 LTC which can be unlocked (preimage+Alice OR timeout1+Bob)
• Alice makes an output of 1 BTC which can be unlocked (preimage+Bob OR timeout2+Alice)
• Alice broadcasts the BTC transaction and wait a confirmation, then gives it to Bob
• Bob broadcasts the LTC transaction.
• Alice fetch get LTC output, revealing preimage
• Bob fetch get BTC output with the preimage

Need timeout1 < timeout2 such that when Alice takes the LTC, Bob is sure he can take the BTC.

If you do both on the samechain, the two addresses can be linked by the H which appear in both transaction though. (might have a crypto trick to prevent that, but never thought about it deeply enough)

I will review coinswap idea a bit later.

[AdamISZ]

@NicolasDorier that is exactly the protocol described here :), including the same backout scripts, see the diagram at the bottom of coinswap_new.pdf.

EDIT: No it's not exactly the same, there is one, perhaps very significant difference. I'll think about it and update when I understand how it changes

The 1st difference (this was originally noted in the CoinSwap thread, but was also used by you guys in tumblebit) is that you don't need to broadcast the custom/backout transactions with preimages, you can "overwrite" them with cooperative outputs. Only this cooperative form gains a strong delinking/privacy advantage. (based on wrong understanding, ignore)

I did add "source" and "destination" chain to the initial handshake for future cross-chain implementation (but haven't looked at it all yet, see #7).

I also added extra outputs to the two intermediate backout txs (the ones with the custom scripts), to make fees charging possible, see here, which came out of #8, but this is a bit complicated, so let's set it aside from any discussion for now I guess.

If you do both on the samechain, the two addresses can be linked by the H which appear in both transaction though. (might have a crypto trick to prevent that, but never thought about it deeply enough)

I don't see this as an issue - because if you do indeed use the backout transactions for redemption, then the redeem script is exposed (including H(X)), so in backout there is no possibility of hiding that it's a CoinSwap (i.e. snoopers can easily recognize the matching pair).

[NicolasDorier]

The main difference is that in cross chain swap, you don't need the 2-2. (Tx0 and Tx1 are useless for cross chain swap)

[AdamISZ]

@NicolasDorier yes I've just been thinking it through, and basically understand it now. Your protocol doesn't create a privacy effect (debatable, but I'd say so), but it's much simpler. And it doesn't have any malleability issue, right.

[chris-belcher]

Getting back to our problem with OP_NOP.

If you read bip62 you'll find even more malleability methods that a miner could do: https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki#motivation

I've been doing something thinking and I think this proposition might work:

1. Use gmaxwell's trick in this OP (https://bitcointalk.org/index.php?topic=303088.0) to hide the transaction so a miner doesn't know which transaction to mutate. To do the attack they'll have to mutate all transactions in their mempools until they get lucky.

2. (optional) Detect randomly mutated transactions and shut down if they are found because this indicates the above is happening.

3. Simply accept that malleability might happen and educate people about the risks. Allow the coinswap fees to rise to take the risks into account. Lots of people already throw many bitcoins at bitfinex/bitmex/poloniex margin lending and they are FAR riskier than coinswap malleability. There should still be enough liquidity to greatly improve bitcoin's privacy and fungibility, and it would still use much less block space than doing 10-20 coinjoins, and all the other benefits of coinswap.

[AdamISZ]

@chris-belcher

(re bip62: yes)

Use gmaxwell's trick in this OP (https://bitcointalk.org/index.php?topic=303088.0) to hide the transaction so a miner doesn't know which transaction to mutate. To do the attack they'll have to mutate all transactions in their mempools until they get lucky.

The linked-to fair coin toss protocol in there was very interesting, and somehow both those threads had totally slipped under my radar so thanks!

I was a bit bemused though that Greg thought this was likely to be a meaningful salvage attempt. It's indeed a smart idea to give Bob (thread parlance) only the sighash and make sure he doesn't know the rest (as mentioned in thread, because he's using an ephemeral key there's no risk to him). But I can't imagine a practical scenario where the amounts and/or locktimes (no that's on redeem; hmm, i guess it's mostly just the amount..) of the broadcast txs aren't going to give it away (or other metadata).

But anyway I think there is another reason this approach doesn't make sense for this version of CoinSwap: as designed, both backout transactions TX2 and TX3 offer backout paths for both parties, meaning you can't preference one over the other (you can't have Alice require Carol blind-sign TX2, as TX2 is part of Carol's safety mechanism. and vice versa).

[AdamISZ]

On that last point, I guess there's yet a further subtlety. For "phase 1" (that ends with conf of TX0 and TX1), only the cltv backout paths matter. If phase1 is complete with valid backouts, and we're in phase2, the malleability threat is finished with. At that point Carol can ensure that her secret backout path is present in TX2 and vice versa for Alice, before continuing. A bit tricky.

Still, isn't the amounts giving it away rather a big deal?

[AdamISZ]

Further developments of the above ideas:

Context: we want nobody, especially including our counterparty, to know which transaction broadcast on the network is our TX0 or TX1 funding transaction, so no one knows what to malleate to lock up our funds.

Proposed solution: the bitcointalk thread above from Greg Maxwell on "only pass over the sighash" idea. Issue: the output amount of the transaction (if we agree on it in advance) gives away to the counterparty what it is.

First, it occurred to me that the blinding amount in the fees idea (again, see docs/fees.md) helps on Carol's side, or it could: Carol doesn't need to tell Alice the size of the blinding amount used in TX1 before creating and broadcasting this transaction; she already advertises a maximum and minimum and chooses something random within it, so Alice has enough info (that it's in an acceptable range).

Then it occurred to me that really, the same argument applies just as well to Alice's side. Carol (in this design) advertises a range of acceptable coinswap amounts, and a fee policy. There's no need for Carol to know which amount Alice has chosen at the point of signing the sighash for the backout transaction TX2 (for TX0).

@chris-belcher and I chatted briefly about this on IRC. Something like this, we think, can work:

• Carol advertises coinswap amount range 1-5btc, blinding amount range 0.5-2.5btc
• Alice constructs a TX0 for say 2.3btc and a TX2 in the normal form, but passes over only the sighash for the redeem of the 2of2 outpoint of TX0 into TX2 for Carol to sign with the ephemeral pubkey she chose for that 2of2.
• Alice broadcasts TX0 at some time later (not quickly else it's too obvious), Carol does not recognize it as does not know the amount or the TXID (is this hiding good enough? we hope it hides well in all the p2sh in that period - but only the ones in the amount range 1-5btc in this ex.)
• After TX0 confirms N blocks, and it wasn't malleated, Alice is safe on her timelock branch of the redeem script of TX2, since its input from TX0 is valid. Now she sends Carol the TX0id and the TX2 complete TX including script.
• Carol confirms that the TX2 outpoint redeemscript has the right structure (Carol secret, Alice timeout L0) as intended. As in the existing protocol, she receives a sig on it from Alice, checks it's valid, constructs her own and passes that back. So TX2 backout is now completely set.
• Then Carol follows the exact same process as above to construct and broadcast TX1, and the end point will be completely signed TX3 backout.
• When TX1 has N confirms and is not malleated, proceed to phase 2 as before.

Will think this through a bit more. Good side of it is it doesn't change the structure at all, just the information passing.
In this flow "and is not malleated" means that, if it is, the malleated side is forced to rely on the cooperation of the other side to retrieve funds. But the purpose of the steps listed is to make malleation of it very hard indeed (hiding amongst many thousands of p2sh txs over a long period, would need huge hashpower to malleate all of them). Is this good enough, we don't know, probably it's within my risk tolerance.

[fivepiece]

Then Carol follows the exact same process as above to construct and broadcast TX1, and the end point will be completely signed TX3 backout

At this stage, carol knows a 2-of-2 input which she is part in control of. Asking Alice to sign an arbitrary sighash, Alice can't know that she isn't signing a sighash of TX0 -> Carol, I think?

Wrong, Alice won't be signing with the TX0 pubkey.
Still, signing arbitrary sighashes, once the "blind" signers learn the midstate that they signed, they should verify their own signature with sighash ALL over that message. Best to verify that the other side didn't make you sign e.g. sighash NONE that will enable them to redeem the 2-of-2 to a different script than the expected backout, or to double spend the swap. Actually I'm sure that's what you meant already.

[AdamISZ]

In my opinion it's a logical inevitability that there can be no risk in signing with an ephemeral pubkey you have not yet used for anything. You just need to make sure you have accurate info once you are about to commit funds.

Thus concretely Alice provides a pubkey for the 2of2 (2_2_CB written in some places for 'Carol, Bob', it's the TX1 outpoint), and another for the secret branch of the TX3 outpoint. Carol then asks for a signature on a sighash. If Carol does it in any naughty way, Alice will recognize it after TX1 has confirmed and Carol is required to give the full form of TX3 (as well as, crucially its outpoint p2sh script). If Alice sees a protocol violation, she just doesn't continue (and backs out her timeout branch of TX2 from TX0, and Carol, assuming she didn't screw over herself in doctoring the backout, does the same on TX1).

Hmm, you wrote "Best to verify ... Actually I'm sure that's what you meant already." so I doubt there's a confusion, but I'll leave that para. in in case it helps any discussion.

I'm not sure all this ends up being important, but it's worth enumerating it in any case, I guess.

[fivepiece]

I was less worried about Carol's side in this case and more for Alice's who broadcasts first. Carol signs a sighash of outpoint at TX0 and she assumes this is TX0 -> TX2. After TX0 confirms and Alice reveals TX0's txid, TX2 and her own signature for TX0 -> TX2, At this point, carol might have already signed a spend from TX0 to anywhere. If she only checks Alice's signature for TX0 -> TX2 and not her own then she has to stop the protocol. If she ends up relaying TX1, then she only has a chance getting the funds back from TX2. She will have to compete with Alice's double spend of TX0.

[fivepiece]

But now I remember that TX1 will not be relayed before a signature from Alice is received for its back out.

[AdamISZ]

At this point, carol might have already signed a spend from TX0 to anywhere. If she only checks Alice's signature for TX0 -> TX2 and not her own then she has to stop the protocol. If she ends up relaying TX1

Yeah but that's just it; at that point (creation/broadcast/confirm of TX0) Carol hasn't committed any funds at all. She can not even start the TX1 side until she sees that TX2 is correctly formed. And Alice doesn't risk at that stage either, because she created TX2 so she knows her timelock backout is correct.

So yeah Carol has to check her own sig on TX2 before proceeding. Although I can't remember if you can do the TX1 side at all simultaneously, but for sure you can do the entire TX0 side first, then the TX1 side. Well, I will definitely look at it again but it seems kind of clear.

[fivepiece]

Agreed. You can do TX0 side fully while Carol validates her own commitments after she learns the midstate. Thanks!

[AdamISZ]

Fwiw, a segwit implementation is now working in the segwit branch. Here "segwit" specifically means that the wallets used by the participants are p2sh/p2wpkh; the backout transactions are not segwit-style (didn't seem necessary, at least for now). I'm still unsure what to do about all the above; the "fix" we talked about is fragile/partial and a bit of a pain.

Thanks all, let me know if you have other thoughts on the topic.

[AdamISZ]

I have merged the segwit code into master. It seems of little interest to keep looking at other malleability workarounds now. Closing.