Q:

What is Transaction Malleability?

The Bitcoin exchange MtGox has stated in this press release that "transaction malleability" caused them to stop sending bitcoins. A recent question asked if it really is an issue. But what is transaction malleability in the first place?

A:

Bitcoin transactions have a transaction id (txid) formed as a hash over the data involved in the transaction. That suggests that it is a unique identifier for a transaction.
However, the tx-id of a transaction is only unique once the exact data in the transaction has been finalized by being incorporated into the blockchain (and confirmed). Until then, there are hacks that allow altering the underlying data and hash. This is not a security issue because it is not possible to alter how many bitcoins are transferred from what input to what output. But details such as what format the cryptogaphic signature confirming that the input authorizes the transaction takes, or the exact signature script used, can be changed: They are malleable, making the hash or transaction id malleable as well.
This should not be a big issue at all. But it is if you built your Bitcoin handling on the assumption that transaction ids are not malleable, as MtGox may have. You also need to be careful about spending unconfirmed transactions, because this only works if nobody changes the intermediate transaction ids. None of this is an issue in the standard Bitcoin client, but if you roll your own, especially if you wish to use only a single Bitcoin address to handle many individual transactions, rapid-firing transactions directly building upon the unconfirmed previous one is an easy mistake to make. If people altered transaction ids from MtGox withdrawals, and MtGox adopted such a rapid-fire approach, this may explain why there have been many complaints of never arriving withdrawals: Altering one transaction id in the chain of unconfirmed transactions invalidates all successor transactions, until the originator resynchronizes with the blockchain rather than its own idea of which transaction ids it has sent.
EDIT: A much more elaborate explanation can be found in this Quartz news article

