Bitcoin Forum

In the fair coin toss thread I pointed out (https://bitcointalk.org/index.php?topic=277048.msg3220914#msg3220914) 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.

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

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

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.

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.

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

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.

With the ongoing malleability attack, this proposal no longer works. Any hope to save 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

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

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

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

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 (https://github.com/petertodd/python-bitcoinlib/blob/master/examples/spend-p2sh-txout.py).

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.

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

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!

From what I can tell, bip65 is a better way to solve the problem in OP

https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki#Noninteractive_timelocked_refunds

It can be implemented with a softfork and also allows many other applications as well as timelocked refunds.

Of course this would be a great thing.

Still dont you feel that allowing ANYBODY to just mess with your txid a bit wrong? The real world analogy would be that ANYBODY at ANYTIME could theoretically just change the check # for a check that you send to someone.

Alice: "I sent you check #1234, didnt you get it?"
Bob: "No, but I did get check #7364 for the same amount from you. Are you sure you know what you are doing?"
Alice: "Of course, it was the malleability gremlin that just changed the checknumber. Dont worry, bitcoin is 100% secure"

James

Well... yeah.

We'll just have to build our software to never rely on the txid unless its already been mined.

Alice and Bob shouldnt talk about txid but instead addresses or whatever comes after addresses in bip70.

I've been thinking about this a lot recently.

Since the last post, highS signatures have been made non-standard so they won't propagate on the p2p network. However this malleability can still be done by a miner and recently this happened (https://www.reddit.com/r/Bitcoin/comments/5ylle1/transaction_malleability_is_a_real_problem_as/).

Another way to deal with s-malleability is for Alice to mutate the transactions herself and require Bob to sign two transaction hashes. One for each of the highS and lowS versions. Then if the transaction gets mutated that way Alice can use the other signature to get her coins back.

Only problem is, for N inputs there are 2^N ways of mutating the transaction, so transactions with many inputs require a lot more data to be transferred between Alice and Bob.


(My earlier comments on this thread 18 month ago sound a bit ignorant hah, I get it now)

Waxwing, arubi and I were discussing this for coinswap. We think we came up with another method of malleability that could cause serious problems.

In my above post I only thought about highS/lowS malleability, but there is another way involving adding OP_NOP opcodes to the scriptSig. See here (https://testnet.smartbit.com.au/tx/c72c3154eece6ff65f1a47ba8214fbb04ed4cbf4c3587030b03ade7f75e213a6) (click the </> symbol on the top right, the first input has OP_NOP added)

I think this is non-standard but valid on the bitcoin mainnet. Which means a miner could be either Alice or Carol in the coinswap protocol and then mine a malleated paying-in TX0 to hold the other party's money to ransom. Also a miner could do this to random transactions as a way of attacking the network.

There's basically an infinite number of ways to add opcodes to scriptSig, so we can't use the same trick as above of signing every possible backout transaction.

If there's no way to fix this then we can't safely do coinswap. One thing we need to check if whether this thing is really non-standard but valid.

> There's basically an infinite number of ways to add opcodes to scriptSig, so we can't use the same trick as above of signing every possible backout transaction.

Further to this point, following up more feedback from arubi: non-push opcodes are not allowed in the scriptSig, but OP_NOP is allowed, as I understand it (please correct me if I'm wrong); if that's right, the issue is specifically related to the NOP opcodes, and extra data can be disallowed with OP_DEPTH (or does cleanstack cover that? only for standard?).

(Also logging any thoughts on this here: https://github.com/AdamISZ/CoinSwapCS/issues/25 ).