Salvaging refund protocols from malleability attacks with P2SH

[gmaxwell]

In the fair coin toss thread I pointed out that protocols which depend on precomputed refunds to prevent holdup risk are currently unsafe in Bitcoin because of transaction malleability.  Turns out they can be partially rescued even before we fix malleability— this is good news because completely fixing malleability will likely take a long time.

This applies to protocols like this:

(1) Alice wants to put 1 BTC into a 2 of 2 Alice + Bob escrow,  but is concerned that Bob might try to extort her by refusing to sign according to their prior agreements.

(2) Alice writes a transaction paying to 2of2 Alice,Bob.

(3) Before announcing this transaction Alice also writes a refund transaction, sending that 1 BTC back to Alice, with a lock time sufficiently far in the future.

(4) Alice asks Bob to sign the refund transaction without ever giving bob the escrow payment. Bob signs it.

(5) Alice then announces the escrow payment.  Confident that if all else fails she can get her funds back later using the refund.

The attack is this:

After (5) bob grabs the escrow payment off then network and mutates the signature to produce an equivalent transaction with a different transaction id. E.g. he replaces the signature (r,s) with (r,s+order).  He then gets lucky or pays a miner to mine his instead.

Now alice's refund is no good and bob is free to extort her if she ever wants her 1 BTC back.

But P2SH can save the day:

We change the protocol so that the escrow payment is to P2SH(2 of 2 Alice2, Bob2) and Alice2 and Bob2 are new keys that they've never used elsewhere and Bob does not know Alice2.

Alice computes the refund but instead of telling bob the refund transactions, she tells Bob only the hash value she wants signed with Bob2.

When Alice announces the payment into the escrow, Bob cannot identify it— unless its the only P2SH transaction of the expected value— and so he would have to mutate every possible transaction in order to get a mutant mined instead. This would be much harder/more costly (at least if P2SH were widely used).

After the escrow payment is confirmed Alice can show it to Bob along with the refund, and so Bob is also confident that the protocol has been followed faithfully.

[1714012638]

1714012638

[1714012638]

1714012638

[1714012638]

1714012638

[1714012638]

1714012638

[1714012638]

1714012638

[Peter Todd]

FWIW jl2012 almost described what you just described, except he didn't make it explicit that you need P2SH: https://bitcointalk.org/index.php?topic=255145.msg2756623#msg2756623

Note how to further discourage miners for modifying transactions, you could spend an output of tx1 in a fee paying transaction broadcast at the same time as tx1 is broadcast. Even better would be to pay the tx fee for tx1 via an out-of-band fee paying protocol - like the fidelity-bonded rough consensus balance ideas I've talked about before - that identified transactions solely by txid.

Finally make the protocol allow for Alice to request Bob to sign multiple transactions, spread out over time, so that Bob can't know if Alice is asking him to sign a dummy transaction or because tx1 was modified and Alice needs a new refund tx.

Note that in some cases you'll need to give Bob a SHA256 midstate so Bob knows what nLockTime/nSequence he's signing - the latter could be tricky to apply due to limitations on what information the midstate can hide - you may need an extra txin - so you're better off with a protocol where Bob learns tx-refund prior to relying on it's contents.

EDIT: nah, actually I can't see how you'd prevent Bob from figuring out what tx to mutate based on the nLockTime value, so it looks like you just have to let design the protocol so Bob learns tx-refund (any any dummy's signed) prior to relying on the non-existance of a immediately-mineable refund tx.

[jl2012]

FWIW jl2012 almost described what you just described, except he didn't make it explicit that you need P2SH: https://bitcointalk.org/index.php?topic=255145.msg2756623#msg2756623

Note how to further discourage miners for modifying transactions, you could spend an output of tx1 in a fee paying transaction broadcast at the same time as tx1 is broadcast. Even better would be to pay the tx fee for tx1 via an out-of-band fee paying protocol - like the fidelity-bonded rough consensus balance ideas I've talked about before - that identified transactions solely by txid.

Finally make the protocol allow for Alice to request Bob to sign multiple transactions, spread out over time, so that Bob can't know if Alice is asking him to sign a dummy transaction or because tx1 was modified and Alice needs a new refund tx.

Note that in some cases you'll need to give Bob a SHA256 midstate so Bob knows what nLockTime/nSequence he's signing - the latter could be tricky to apply due to limitations on what information the midstate can hide - you may need an extra txin - so you're better off with a protocol where Bob learns tx-refund prior to relying on it's contents.

EDIT: nah, actually I can't see how you'd prevent Bob from figuring out what tx to mutate based on the nLockTime value, so it looks like you just have to let design the protocol so Bob learns tx-refund (any any dummy's signed) prior to relying on the non-existance of a immediately-mineable refund tx.

I don't understand your point. How would Bob know the nLockTime? Alice doesn't need to show tx-refund to him before tx-1 is confirmed

[jl2012]

If extortion is a real concern, Alice should send it with multiple transactions to minimize the incentive to cheat and potential loss.

More importantly, with the micro-payment channel mechanism, Alice could send ANY value of bitcoin to escrow, and is always able to get the excessive value back. Therefore, it is impossible for Bob to identify the target transactions. If Bob takes a spray and pray strategy, that would be a big disruption to the whole bitcoin network.

In long term, we should forbid malleability, which I'll discuss in another thread: https://bitcointalk.org/index.php?topic=271278.0

[Mike Hearn]

Although these ideas are interesting, my gut feeling is that restricting malleability is a better way to go.

The current implementation of micropayment channels in bitcoinj actually relies on the server to broadcast the contract. The reason is, it's designed so clients can still build channels even if they don't have internet access. So it's a simpler attack as there's no need to race the broadcast.

I will think about adjusting it so when the client *does* have internet access, they broadcast the transaction.

Something else that'd help is if nodes had keys, and then you could encrypt a transaction so only a subset of nodes could decrypt it (using subset difference trees or some other variant of broadcast encryption). Then you could encrypt the contract and pass it through the server, forcing them to race once again. Perhaps you could even encrypt the tx so only a group of miners and a few broadcaster nodes can read it, so making it very likely that it enters the mempools of some miners first.

Such a scheme would help privacy too, by obfuscating the IP that generated a transaction. But it also raises other questions like how you get the encrypted tx to their destinations (direct connect? floodfill?) and how that interacts with anti-flooding controls.

[gmaxwell]

Although these ideas are interesting, my gut feeling is that restricting malleability is a better way to go.

I absolutely agree that should be done, and I didn't intend this to be an alternative. There are protocols which this suggestion cannot help.

But, I believe it will take a minimum of two years remove malleability.

Fully eliminating malleability requires a soft fork with fairly invasive changes in script validation because you need to catch things like "Push onto the stack that had no effect" and "Used something other than the smallest possible push". It may be difficult to convince some alternative implementers to make these relatively risky changes, since the removal of malleability is only really essential for transaction patterns which are nearly non-existent today (chicken and egg: until the malleability is removed, you can't grow the use of transactions which depend on it not being there).

... and this is assuming that it doesn't turn out that there are any more ways to mutate DSA signatures (e.g. by jointly modifying R and S). Adam Black was very concerned that there were.

In any case, having a workaround means that someone who wants to do something the work around works on has an alternative... and doesn't have to wait for the network to believe their use case is justified.  A simple extortion free escrow for doing instant payments or the like is possible this way with entirely standard transactions.

[adam3us]

... and this is assuming that it doesn't turn out that there are any more ways to mutate DSA signatures (e.g. by jointly modifying R and S). Adam Back was very concerned that there were.

I didnt so far find a way to do it with ECDSA, but that is not a proof.  Also there exist other crypto schemes that are self-reblindable (without knowing the private key).

But it seemed to be rather than relying on this additional and perhaps not designed for property of signatures non-malleability (of the anti-malleability-canonicalized serialization) that maybe longer term bitcoin could include the public key in the hashed data rather than the signature.  By definition the signed data must also be unique as txins are spent in full.

We were also talking at the physical meetup about possibility to fix the malleability before forwarding and Greg had mentioned this as a work-around used by blockchain.info as they were unable to modify their wallet due to apple's regressive policies.

Adam

[mmeijeri]

Alice computes the refund but instead of telling bob the refund transactions, she tells Bob only the hash value she wants signed with Bob2.

Doesn't that mean that Bob is blindly signing something? Wouldn't that be incredibly risky? EDIT: never mind, Bob is signing with a brand new key.

[jl2012]

With the ongoing malleability attack, this proposal no longer works. Any hope to save it (except by fixing malleability)?

[mmeijeri]

With the ongoing malleability attack, this proposal no longer works. Any hope to safe it (except by fixing malleability)?

Why does it no longer work?

[jl2012]

With the ongoing malleability attack, this proposal no longer works. Any hope to safe it (except by fixing malleability)?

Why does it no longer work?

Someone is randomly mutating unconfirmed transactions. So the txid of all unconfirmed transactions are not reliable

[mmeijeri]

But isn't that precisely what this proposal is intended to deal with?

[jl2012]

But isn't that precisely what this proposal is intended to deal with?

so he would have to mutate every possible transaction in order to get a mutant mined instead. This would be much harder/more costly (at least if P2SH were widely used).

This proposal assume that Bob would not take a spray-and-pray strategy. As someone is now randomly mutating transactions on the network, the proposal won't work

[omnibrain]

We change the protocol so that the escrow payment is to P2SH(2 of 2 Alice2, Bob2) and Alice2 and Bob2 are new keys that they've never used elsewhere and Bob does not know Alice2.

Alice computes the refund but instead of telling bob the refund transactions, she tells Bob only the hash value she wants signed with Bob2.

Is there a library that supports this?

Let's say I wanted to implement this payment protocol, do I have to "manually" construct the hash value from the unsigned transaction, and later "manually" putting together the transaction that includes Bob2's signature?

And one more question: Does BitcoinJ follow the protocol described above, or is BitcoinJ still prone to transaction malleability?

Any help is greatly appreciated, I'm working on a payment channel implementation for my bachelor thesis

[Peter Todd]

We change the protocol so that the escrow payment is to P2SH(2 of 2 Alice2, Bob2) and Alice2 and Bob2 are new keys that they've never used elsewhere and Bob does not know Alice2.

Alice computes the refund but instead of telling bob the refund transactions, she tells Bob only the hash value she wants signed with Bob2.

Is there a library that supports this?

Any Bitcoin library that gives you sufficiently low-level access to transaction signing will support this. For instance my own python-bitcoinlib lets you, as you can see in the P2SH signing example.

[jl2012]

But isn't that precisely what this proposal is intended to deal with?

so he would have to mutate every possible transaction in order to get a mutant mined instead. This would be much harder/more costly (at least if P2SH were widely used).

This proposal assume that Bob would not take a spray-and-pray strategy. As someone is now randomly mutating transactions on the network, the proposal won't work

My question a year ago has not been answered. As someone may attack the network by randomly mutating txs, just like what we had last year, no txid should be considered as final before it is written in the blockchain.

[gmaxwell]

My question a year ago has not been answered. As someone may attack the network by randomly mutating txs, just like what we had last year, no txid should be considered as final before it is written in the blockchain.

What to answer? That was the limitation here-- pointed out in the post; someone might choose to take that risk-- e.g. if their alternative is to just trust their counterparty instead such a scheme could only be an improvement.

[jl777]

Ignoring compatibility issues, the following would fix this once and for all, wouldnt it?

**********
#define SIGHASH_TXID 0x40

change https://en.bitcoin.it/wiki/OP_CHECKSIG:
Final signature check
An array of bytes is constructed from the serialized txCopy appended by four bytes for the hash type and if SIGHASH_TXID is set followed by the txid. This array is sha256 hashed twice, then the public key is used to check the supplied signature against the hash. The secp256k1 elliptic curve is used for the verification with the given public key.
**********

also the txid cant include the sig. Not sure why the txid calc isnt using the same data as the signature calc.

James

[TierNolan]

Ignoring compatibility issues, the following would fix this once and for all, wouldnt it?

This is a hard fork, since old clients would consider those signatures invalid.  With a hard fork, there are lots of solutions to the problem.

[jl777]

Ignoring compatibility issues, the following would fix this once and for all, wouldnt it?

This is a hard fork, since old clients would consider those signatures invalid.  With a hard fork, there are lots of solutions to the problem.

Lets hardfork!