Proposed BIP for dealing with malleability

gistfile1.mediawiki

This document has been promoted to BIP 62.

Please find the updated text at https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki

There is another solution to this malleability problem: Remove the signature scripts before hashing the transaction when computing the TxID. ... I suppose such a radical change is all but impossible at this stage of Bitcoin's life.

Peter, please correct me if I'm wrong, but as far as I understand it, the malleability factor was first raised long ago (circa 2011), and there exists innovations that have been gradually implemented since (which includes this gist). The current furore has much more to do with MtGox's own proprietary wallet - or more specifically, spending freshly mined coins before the 100-block maturation.

If we do not fix this then any wallet that spends unconfirmed coins-sent-to-self may risk creating invalid transactions (including bitcoin-qt).
E.g. If a client sends a payment based on the unmodified (unconfirmed) tx, and a modified version of that tx gets mined, then the client sends an invalid transaction.
Let's get this fixed.

@janmoller it's not "invalid" it's orphaned (and will be forever). (I'm bothering to point out this bit of pedantry just because someone showed up in IRC concerned that they cause DOS bans).

Sadly this cannot be fixed quickly, if you're concerned about mutated change, you should avoid spending unconfirmed change. Bitcoin-QT will only do so as a last resort because of this exposure.

Re: spending unconfirmed mutated change, could you broadcast a new mutant-change-spending transaction whenever you see someone mutating your parent tx's? Then hopefully all nodes end up with a compatible chain of your tx's, and it doesn't matter which gets confirmed. Potential problems I see are

1. a new attack of getting others to help spam the P2P network by feeding them mutants of their own tx
2. depending on how the propagation pans out, you still might not be able to get your change-spending tx into the same block as its parent anyway
3. could be more difficult to implement than it's worth. My understanding is that this proposal would stop most known malleability, so mutant change countermeasures are not so important, right?

Apologies if this is a clueless comment. I'm sure you guys are inundated with suggestions from people who don't really know what they're talking about. :)

Rule #3 could be problematic for some complex scripts. The rest is reasonable.

Other deeper change to avoid 1) is modify the ECDSA method. Now you have:

r = [kQ]_x mod p

This only dependency on x-part of the resulting point is the key to manipulate s. But it can be changed to

r = H(kQ) mod p

where H is the bitcoin hash function (double SHA256). This yields an unforgeable s.

It is a major change, I know. But it worths to take on this whenever some other protocol major upgrade occurs.

I don't see anything about the VAR_INT describing the length of scriptSig. I suspect non-canonical VAR_INTs are non-standard, at least.

@etotheipi: Transactions are always reserialized before hashing, so the length of scriptSigs or the number of inputs or outputs is always normalized already.

@oleganza: You can always choose to create an nVersion=1 transaction instead of an nVersion=3 one. In that case you also give up the protection from malleability that nVersion=3 offers. However, if you're working with complex scripts, you're likely already dealing with mutable transactions anyway.

@roconnor @mpancorbo: Changing the scripting language itself is probably the only complete solution, and I expect we will at some point want that. That's a much more involved change (but one that can improve many other things too).

Am I missing something? Why don't we just add a signature that is calculated based on every single bit of data in the transaction? That way, if any part of the transaction was modified, including by any of #s 1-8 above, the signature would no longer be valid, and it would be rejected by all relaying nodes. The key that would be used to sign the transaction as a whole would be some mathematical combination of all private keys associated with addresses that being used to sent money in the transaction. I know, in RSA, you can sign/encrypt a message to an arbitrary number of different recipients, so I'm assuming hopefully it would be possible to sign a Bitcoin transaction with all applicable keys as well?

Or would signing the entire transaction simply with one of the private keys associated with an address in the transaction be sufficient?

...
9. ECC signatures are based on a random number and will always be modifiable by the sender.

So either add 9 to the list or remove 7/8 altogether - true malleability is only when you as a 3rd party can modify the hash. As a sender you will always be able to modify it.

Also, why introduce a new transaction version for this purpose ? Wouldn't it be more elegant to simply let the next bitcoin version "prettify" all relayed transactions as deterministic transactions fulfilling the scheme 1-6 effectively blocking any malleability attack? If miners would upgrade then all transactions in blocks would have a deterministic hash. Then in a version later one could block relay of non deterministic transactions, as well as the acceptance of blocks with non-confrming transactions.

@gronager: Miners could prettify my transactions, but how am I supposed to find them afterwards?

Thanks OP for documenting this!

Typo? "S-length: 1-byte length descriptor of the R [should be S] value that follows."

I imagine that block explorers could use these rules to undo modifications and index any standard transaction by its original hash (as well as the hash in the blockchain). This would let innocent senders look up their transaction by the original txid and see the possibly modified txid as mined. Have I overlooked any obstacles?

Why not enforce a consensus rule that invalidates any nVersion=1 transaction which contain any scripts that are "too malleable?" This would restrict, but still allow, future use of nVersion=1 transactions to a "simplified" set of allowable OP_codes. And/or, if it looks like the transaction is structured to allow malleability, reject the transaction.
"Complex" scripts would then have to use nVersion=3 transaction flag which are subject to the new rules to prevent malleability. This doesn't have to be "all or nothing." To assist both the existing approach as well as this idea, perhaps transactions can be assigned a "malleability score" that is based, for example, on the amout of padding, use of certain OP_codes, etc. This score can then be used to filter incoming transactions by miner nodes that are not equipped or don't want to handle malleable transactions. Or, I suppose, by miscreant nodes seeking to take advantage of such maleable transactions, but that's life, I suppose.

Just my 0.0000002 BTC.

@ckehrlich I think the point is that by creating a nVersion=1 transaction, the client is already stating that he is accepting the risk of malability. You can write clients that don't care about malability at all (e.g. not spending change before it's in the blockchain and identifying its own transactions in the blockchain by inputs instead of txid). As long as clients have the option to send a non-malable nVersion=3 transaction I see no reason to enforce additional rules for nVersion=1 transactions.

@jtobey Thanks, fixed.

@ckehrlich It's just safer to not introduce any extra rules for existing transactions, as that requires a forking point at which wallets and nodes need to be upgraded by. By making the malleability protection optional to request and to enforce, these is no such problem.

@gronager: For completeness, I've added reissues by the sender as an extra known source of malleability.