Malleability, deposits and atomic cross chain transfers

[TierNolan]

Atomic cross-chain transactions require refund transactions to be created.  Transaction malleability means that the refund transaction can be invalidated by change the transaction.

A creates a "funding" transaction of the form

TX0: 1 BTC output requires signature by A and B to spend

A refund transaction is created by A.

TXR: Pay 1 BTC from <TX0>, locked until 24 hours in the future, signed by A

A then sends it to B and B returns it signed

TXR2: Pay 1 BTC from <TX0>, locked until 24 hours in the future, signed by A & B

When A received TXR2, he broadcasts TX0.

If B disappears at that point, A can broadcast TXR2 24 hours later to get his money back.

The attack is that B could try to modify TX0 into TX0' using transaction malleability.  If he can get TX0' accepted into the chain, then the refund transaction won't work anymore, since it refers to TX0.

This means that B can hold A's money hostage.

A tweak would be to have B deposit some money into TX0.

B creates a transaction TX0

TX0: pays 1 BTC, requires signature by B

NOTE: This should be a new private key

B sends hash(TX0) to A

A creates TX1

TX1
Input 1: 1 BTC (from A) signed
Input 2: 1 BTC (from hash(TX0))
Output: 2 BTC, requires signature by A and B to spend

A computes hash(TX1) for signing by B.  This is the signature hash (it removes input scripts).

B signs TX1's hash, which is the same as signing TX1.  This allows TX1 to be signed without A having to show TX1 to B.

A creates TXR and sends it to B

TXR:
Input 1: 2 BTC from TX1 signed by A
Output 1: 1 BTC to A's public key
Output 2: 1 BTC to B's public key

B signs TXR to give TXR2 and sends it back to A

TXR2:
Input 1: 2 BTC from TX1 signed by A & B
Output 1: 1 BTC to A's public key
Output 2: 1 BTC to B's public key

A sends TX1 to B.  B can verify that it is a valid transaction and that TX0 and TXR2 form a chain which refunds B.

Release of transactions

B can release TX0 unconditionally.  If TX0 is modified, B can just sign a refund and TX1 and TXR2 are invalidated.  This is fail-safe.

Either can publish TX1.  This is still weak to modification.  However, if it is modified, then both A and B have 1 BTC locked in the transaction. 

If TX1 is accepted by the chain, then either party can release TXR' to refund the BTC back to A & B's addresses.

If there is a 15% chance of getting TX1 into the block chain and 50% of users agree to a 75% to 25% split of the refund, then the payoff for a hostage taker is

85%: 1 BTC refunded (transaction failed)
7.5%: money lost (ransom refused)
7.5%: 1.5 BTC (ransom success)

That gives a ROI of 96.25%, so it isn't in the interests of attackers to try for a ransom.  With fees, it makes it even less useful.

In practice, TX1 would be more complex, as it has to have the hash(x) type stuff for cross chain transfers.

[k99]

Another idea how to mitigate the blackmail attack due tx malleability would be to create a 3of3 MultiSig and delete the 3rd key directly after signing. So there is no possibility that this transaction can be changed in favor of the blackmailer.
Of course it will not help against unintendedly changed transactions (not sure if that is a real risk with malleability as well?).
And the key deletion cannot be proven, so that is a weak point as well (but maybe more theoretical).

Here is the idea presented in the old version of our P2P Fiat-BTC exchange paper. In the current version (https://docs.google.com/document/d/1d3EiWZdaM89-P6MVhS53unXv2-pDpSFsN3W4kCGXKgY) we don't need that anymore as blackmail prevention is covered by using arbitrators).

"...To solve that we could use a 3of3 Multisig for the deposit. Bob creates a 3rd key, use that for creating the 3of3 Multisig address for the deposit tx, and immediately creates the payout/refund tx and sign the input with the 3rd. key and DELETE that key afterwards.
That way he created the ONE AND ONLY possible spending tx. This 3rd temporary key serves only for protecting the predefined output setting. As it is destroyed after the initial tx creation, there is no way to change the output distribution with a modified tx.
The prove for key deletion is impossible but if Bob is honest he has no incentive to keep the key and Alice is in the more powerful Blackmail position. Even if he silently keep the key he can deny it. The software will do that all for the traders and only hacks or manipulated software could work around that. There will be probably not many people who cheat the system to keep the key secretly, and therefore the blackmailer has a very low probability to really hit another cheater who is capable to change the tx."
See in full context here: https://docs.google.com/document/d/1pofc0j8FHLwZbK-ANJan7lD01Q5usy9XbA1wPn0FAKA/edit#heading=h.950d4t4cwl3q

Full credit for the 3rd key deletion idea goes to dansmith!

EDIT:
I asked at IRC bitcoin-wizards and it seems that malleability can happen also without malicious intention, so the above proposal will not be sufficient.

Manfred_Karrer:I have a question regarding malleability: Can malleability happen without malicious intention? Like due different implementation or optimization?
stonecoldpat: i remember being told that it can
stonecoldpat: that it just happens from time to time
Ademan: Manfred_Karrer: yes it can, but it requires some sort of intention
Ademan: I recall gmaxwell mentioning nodes that would re-canonicalize transactions before relaying them, not sure if that was a hypothetical or not though
maaku: Ademan Manfred_Karrer: transactions can be mutated without any mallicious intention
maaku: especially if they are non-canonical to start with
maaku: it's not hard to imagine someone running custom code accidentally re-serializing transactions during relay in a way that makes them canonical or otherwise does not preserve round-trip serialization

[k99]

I posted here (https://bitcointalk.org/index.php?topic=193281.msg5833231#msg5833231) a proposal to solve the malleability problem with cross chain trades.

[Bitalo_Maciej]

Another idea how to mitigate the blackmail attack due tx malleability would be to create a 3of3 MultiSig and delete the 3rd key directly after signing. So there is no possibility that this transaction can be changed in favor of the blackmailer.
Of course it will not help against unintendedly changed transactions (not sure if that is a real risk with malleability as well?).

It is a real risk, as it was demostraded on February that someone changed few thousand transactions for no particular reason.

[k99]

Another idea how to mitigate the blackmail attack due tx malleability would be to create a 3of3 MultiSig and delete the 3rd key directly after signing. So there is no possibility that this transaction can be changed in favor of the blackmailer.
Of course it will not help against unintendedly changed transactions (not sure if that is a real risk with malleability as well?).

It is a real risk, as it was demostraded on February that someone changed few thousand transactions for no particular reason.

Yes I was not sure first if its only due malicious behaviour, but people in bitcoin IRC channel told me that it can happen for varios reasons. So that 3rd key deletion proposal would not work. But in the link I posted before (https://bitcointalk.org/index.php?topic=193281.msg5833231#msg5833231) there is a proposal which could work.