bitcoin transaction malleability

bitcoin transaction malleabilityOne week. Four headline events. Culprit: Transaction Malleability. Although the media grouped the events under the single banner of Transaction Malleability, a closer look reveals that the three incidents involving Mt.Gox, a DDoS attack, Silk Road 2.0 and the Bitcoin client were in fact each unique and in two cases not even related to transaction malleability at all.

To understand Transaction Malleability we have to define some terms:

Malleability – the quality of being pliable without breaking – often used in reference to metals, but in this context it simply means “changeable without breaking the transaction”

Hash – a hash function is an algorithm that maps data of arbitrary length to data of a fixed length. The fixed length data so obtained is called a hash and it is irreversible, ie. the original data cannot be deduced from it’s hash.

Signature – a digital signature is a mathematical scheme for demonstrating the authenticity of a digital message, document, or in this case, a digital transaction. Bitcoin uses public and private key pairs to secure bitcoin transactions and digitally sign them.

 

Transactions and Malleability

The transaction id that we’re familiar with is a hash of all of the components that make up a Bitcoin transaction. The transaction components include various facts (transaction amount, date, target address, etc), as well as, digital objects such as encryption signatures and what are referred to as “inputs”. Transaction inputs contain information about previous transactions involving the same bitcoins currently being spent. To protect this data from tampering, hashes of certain components are calculated and signed – amongst them the transaction inputs, whose signature (called “input.scriptSig”) is also used to sign the entire transaction and this produces the hash we know as the transaction id.

bitcoin transaction

Since it is not logically possible for a signature to sign itself (chickens and eggs!), a final signature will always be an appendage – an attached but separate part of the digital package (in this case a transaction) it has signed. Whilst the transaction as a whole, or in part, cannot be changed without breaking validity in relation to the signature, the signature can be changed. The extent to which the signature can be changed before the change breaks validity in relation to the transaction is what is referred to as “Malleability”.

So, given a transaction and its accompanying valid digital signature, it is possible for someone to generate an equivalent signature, but with the caveat that the transaction id hash will also change in response. When injected into the network, both the original and malleated version of the transaction are equally “real” as far as the nodes on the network are concerned. Remember that the transaction itself has not changed. In fact, a change to any aspect of the transaction other than the input.scriptSig would render the entire transaction invalid and it would be rejected by network nodes. Since nothing about the transaction inputs or outputs (amount, timestamp, target address) has changed, our malleated transaction may be included in a block by a miner, thereby being confirmed, and the receiving party will get paid. The equally valid original transaction will in this case be picked up as an attempt to double spend and the network will reject it. Hence, transaction malleability does not pose a security threat on the network and it’s exploitation does not make double-spending possible in the normal protocol flow.

bitcoin transaction confirmation
Mt.Gox

Transaction Malleablity score: 1/10

Whereas the Bitcoin protocol and standard wallet are able to function correctly in the face of malleated transactions – which kind of renders “malleation” pointless – the scenario changes quite drastically when we consider a non-standard wallet that has failed to make provision for transaction malleability in its design. If a custom wallet were to, say, use transaction id as a primary identifier when looking to the network for transaction confirmation, then malleation would compromise its ability to do so.

Miners have no preference (or ability to distinguish) between an original transaction and its malleated version, so it is a matter of fate as to which one gets mined first and thus confirmed on the network. Confirmation is made by transaction id: whichever version of the transaction confirms first, that will be the txn id referenced in each subsequent confirmation. If the original version confirms first then all is well: the recipient gets paid and the custom wallet will see the confirmation by looking for the transaction id in the blockchain. However, were the malleated transaction  confirmed first, then the scenario for the custom wallet becomes an exception: although the receiver would have been paid (and the malleated version of the transaction confirmed); the custom wallet will not see confirmation of the original txnid it sent out. Combine this with a support policy of resubmitting payment of unconfirmed transactions and you can see the exploit:

A person withdraws bitcoins from their Mt.Gox account to their private wallet and at the same time injects a malleated version of the transaction into the network. If the malleated version is confirmed first then it would be certain that Mt.Gox will not receive confirmation of the original. The person then emails support: “I withdrew 10BTC yesterday – it left my account but i never received it…” Support staff look for confirmation of the transaction and don’t find it, although the BTC had clearly left the customer’s account. And, so, they resubmit payment – but not via the same transaction id or transaction inputs – but a completely new transaction spending different coins!

Had Mt.Gox only used the same inputs as used in the original unconfirmed transaction, that would have registered on the network as a double-spend and would have set off some alarm bells. That this definitely happened at Mt.Gox can be deduced from both their actions and statements during the past several months. The extent to which this affected them is unknown, but it certainly was severe enough to halt all BTC withdrawals, risk customer defection and leave them to watch their exchange for BTCUSD get traded into the ground.

bitcoin transaction malleabilityDistributed Denial of Service (DDoS) Attack

Transaction Malleablity score: 7/10

After Mt.Gox publicized the issue of malleability, and word got about of their wallet not taking it into account, it was only a matter of time before some opportunists turned it on the Bitcoin network. The attackers took full advantage of the transaction malleability issue and opened the flood gates. Poor custom wallet implementations at Bitstamp and BTC-e were immediately shown up and their suspension of BTC withdrawals indicated that they were using transaction id to verify confirmations.

The Bitcoin developers offered support in the IRC channels and soon the DDoS attack was circumvented and BTC withdrawals were resumed. Note that the DDoS affected those exchanges that had poor wallet implementations – the Bitcoin network remained unscathed thanks to proper implementation of the standard Bitcoin QT wallet.

 

Bitcoin QT Wallet Client

Transaction Malleablity score: 0/10

The client was not handling the display of attempted double-spend gracefully and during the past week this issue came to the fore. The score here is zero because the wallet is implemented with transaction malleability in mind and the bug being fixed for the upcoming release is merely a display bug. Due to the complexity of the Bitcoin protocol’s encryption and signature model, the developers only expect to eliminate this issue after a few years. In IRC, Jeff Garzik said in response to a question about whether transaction malleability can be solved:

 

<@jgarzik> not 100%, no – it is “solved” by getting your transaction confirmed

 

 

Silk Road 2.0

Transaction Malleablity score: 0/10

The spin that transaction malleability caused all client funds to be stolen from the Silk Road mainframe is so thin that no-one even bothers to debate it!