Transaction malleability

Transaction malleability is an artifact of how Bitcoin transactions are signed. As I mentioned in my last post, the input signatures are there to, in part, protect your transaction from being modified by third parties. Without access to the private key used to sign a transaction, there's no way for an attacker to change where that transaction sends its satoshis without invalidating the signature. However, the signature itself is not protected from change, and herein lies the rub; changing the signature will change the hash of a transaction, essentially creating a new equivalent transaction, that is still valid. This has a number of issues, and due to, apparently, a bored Russian hacker, malleability has recently gone from a theoretical problem to something pretty much all Bitcoin software has to deal with all the time, my wallet software being no exception.

What does it look like?

I recently broadcast a simple transaction that can serve as an example of what exactly malleability looks like. The transaction sends two unspent outputs to a new address and hashes to 3d9ae35ec8e5b4c9b9cdad8c1fe7bd9afc465646485a9d5932fb71cbff586294. It has already gotten a few confirmations and can be viewed in detail on blockchain.info.

 This is how it looked on my wallet just before I broadcast it, let call this transaction A:

Transaction: 3d9ae35ec8e5b4c9b9cdad8c1fe7bd9afc465646485a9d5932fb71cbff586294, version 1

Input: tx 389a80eaccc69ce8504de8f60cbbb5ecb0c975be6197e77d91326417ab8166ff (output index 1) => 17pZuDHfXNLKxyA7hsd1cGrSSPtUrhnxTq
Signature: 3044022035e0595694e040591bd9ca90015a889318ce1e5eb247c547672ea3974eecd7fb02205004cd171a1b282cb75ab7e285d840a6ec1facffbc50aa6e651e969e6103bc6201

Input: tx e4231428afe4a2fd1574a2e7d9eaec392db6c6b75ee53c99e34ed1c141b01aa0 (output index 0) => 18WPbS5dxLUjE16DymRpv1q7W9JmPz8u9u
Signature: 30460221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec022100a013b18159b5737f0d7dec9f0e95815cd3cfd82e461baad6c42d37e93d55bb4001

Output: 30000 satoshis (0.300000 mBTC) to script: OP_DUP OP_HASH160 13ZsFbiWrDeyyBwwtFpmssA47Tv7v7tZNX OP_EQUALVERIFY OP_CHECKSIG 

Within seconds, the connected nodes indicated that transaction A had been added to their mempools and regarded as a valid transaction. Then, roughly 8 seconds after the broadcast, one node notifies my wallet that it has a transaction with hash b4f3c62159a222ea9eccf5d0f9057c555d0d519cfe580412c4c185c244d8bb30 paying one of its addresses. The wallet software promptly fetches the transaction, and this is how it looks (lets call this transaction B):

Transaction: b4f3c62159a222ea9eccf5d0f9057c555d0d519cfe580412c4c185c244d8bb30, version 1

Input: tx 389a80eaccc69ce8504de8f60cbbb5ecb0c975be6197e77d91326417ab8166ff (output index 1) => 17pZuDHfXNLKxyA7hsd1cGrSSPtUrhnxTq
Signature: 3044022035e0595694e040591bd9ca90015a889318ce1e5eb247c547672ea3974eecd7fb02205004cd171a1b282cb75ab7e285d840a6ec1facffbc50aa6e651e969e6103bc6201

Input: tx e4231428afe4a2fd1574a2e7d9eaec392db6c6b75ee53c99e34ed1c141b01aa0 (output index 0) => 18WPbS5dxLUjE16DymRpv1q7W9JmPz8u9u
Signature: 30450221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec02205fec4e7ea64a8c80f2821360f16a7ea1e6df04b8692cf564fba526a392e0860101
The 
Output: 30000 satoshis (0.300000 mBTC) to script: OP_DUP OP_HASH160 13ZsFbiWrDeyyBwwtFpmssA47Tv7v7tZNX OP_EQUALVERIFY OP_CHECKSIG 

At first glance it looks like the same transaction. In fact, transaction A and B both uses the same inputs to pay the same output the same amount. The only reason they have different hashes, and thus show up as two unique transactions, is a change to the signature on the second input.

Input signatures

Every transaction input has a signature field, and for standard transactions it contains two objects; a DER-encoded signature of the transaction, and the unhashed version of the public key the consumed output was originally sent to (only the actual signature is shown in the transactions above).

So what has changed between transaction A and transaction B.

• Second input to A:
  30460221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec022100a013b18159b5737f0d7dec9f0e95815cd3cfd82e461baad6c42d37e93d55bb4001
• Second input to B:30450221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec02205fec4e7ea64a8c80f2821360f16a7ea1e6df04b8692cf564fba526a392e0860101

The signature actually consists of two numbers, R and S, and they are encode as follows

• Signature: 0x30 <total length (one byte)> R(encoded) S(encoded) 0x01
• where the last byte is a signature hash code that isn't really part of the signature.
• R and S (encoded): 0x02 <length (one byte)> <actual number>

As we can see, R is unchanged whereas S has changed. Although there's a large number of valid ECDSA signatures for any given data (this helps avoid leaking information if you were to, say, sign the same data twice), you'd think creating a new signature required knowing the private key. There is however a quirk in how an ECDSA signature works allowing for two valid values of S in any signature, and crucially for this attack, the relationship between the two Ses is really simple. It turns out that for any valid ECDSA signature (with the particular parameters used in Bitcoin), the signature will still be valid if S is replaced with S' = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 - S.

In our case transaction A has Sa = 00a013b18159b5737f0d7dec9f0e95815cd3cfd82e461baad6c42d37e93d55bb40 and transaction B has Sb = fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 - Sa = 5fec4e7ea64a8c80f2821360f16a7ea1e6df04b8692cf564fba526a392e08601.

This is simple math, and basically something anyone can do. In fact, the way the signature is encoded is loosely enough defined to open up for countless modification that don't involve any math at all. For this particular transaction, it would for instance be possible to just strip the leading 0x00 from Sa, yielding the signature 30450221008a162fbaf43f2f10db622d9443f89a50574f83d9c57b66dd14ec276130dafeec0220..a013b18159b5737f0d7dec9f0e95815cd3cfd82e461baad6c42d37e93d55bb4001 and the transaction hash b5514b39d578be2c0889382930780ac33997571b4bb1611990f8e897380dcefb; a third unique but equivalent transaction. For a list all known ways to modify signatures without invalidating them, as well as the proposed fixes to the Bitcoin protocol, see BIP-0062.

Consequences and short term solutions

Even though transaction malleability doesn't change the essence of a transaction, and once one is confirmed by a miner, the other one(s) will be clearly invalid, the period of uncertainty before that happens can be quite a nuisance (essentially all versions of a transaction must be treated as equally valid/invalid as there's no way to tell which one was the original one, or which one will end up sticking). Naively implemented wallets (including mine at this point) can double count incoming transfers, messing up the account balance. Worse though, transactions made using the change output from a recent, not-yet-confirmed transaction, may turn out to be invalid if a miner confirms the modified transaction rather than the original.

Take for instance the following transaction proposed my wallet before the malleability issue above was settled (let's call this transaction C):

Transaction: 3e90b646873675f6728f7878484dda5f7693f66ccc0b0b30a0145f02d9d4797a, version 1

Input: tx b4f3c62159a222ea9eccf5d0f9057c555d0d519cfe580412c4c185c244d8bb30 (output index 0) => 13ZsFbiWrDeyyBwwtFpmssA47Tv7v7tZNX
Signature: 3046022100f5622225b11cd4ecc35625f9ebedfb4b10059941d41ab20f68b1bc60bd9a7c91022100ad99b6e367e830916abc20e71eb4dbfbe25251d6dd5c0724099c4db0f1a453f201

Output: 20000 satoshis (0.200000 mBTC) to script: OP_DUP OP_HASH160 1L9SmY5i3bQ17RJreX4CoJJJBrWK6oN5HF OP_EQUALVERIFY OP_CHECKSIG 

 

It's trying to use an output from transaction B to form a new transaction, something that would be considered valid by a significant fraction of the network (any node that saw transaction B before A), before eventually ending up being an invalid transaction once transaction A was mined, rendering transaction B invalid.

I could program the wallet to disregard outputs from transaction B, after all it knows which one was the original one, but that wouldn't stop miners from confirming transaction B if they happened to see that before A.

A better solution would probably be to keep track of all the modified versions of the original transaction, and create corresponding versions of any new transaction spending the outputs. Ideally these should then be forwarded to miners with compatible views of the world for inclusion in their next block, so miners who believe transaction B is the valid one are sent C as it stand above, while miners who think transaction A is the valid one are sent C(a), where the corresponding output of A is used instead of the one from B. This process might be hard to get accurate, but sending C(a) back to nodes that sent us A, while sending C(b) back to nodes that sent us B, will probably not be too far off. In any case, putting both versions of C out there will ensure that one is still valid once the network has decided on the A vs B situation.

With this solution implemented, the wallet should be able to function as normal even during malleability attacks like the one that's currently ongoing, without having to wait for protocol level improvements (like those proposed in BIP-0062). I'll write a new post on this topic once I have this functionality implemented and ready for testing.