How are transaction IDs generated and how are they then changed by transaction malleability?

Question

How are the transaction IDs generated for a Bitcoin transaction? How can the transaction ID change due to a transaction malleability attack?

Answer 1

The transaction ID is the SHA256d(signedTransaction) = SHA256(SHA256(signedTransaction)). Sha256d is SHA256 applied two times.

Example: Let us consider the transaction with ID 844c00ca065bc26eb61bfee203df2f7bcbc72a6bb77697a32d2a98dad5941109. The hex encoding of this transaction is:

02000000019e8cc9f5c7e16bc11e6f4050fbdf925e5ea9e0d3c8b430bce4afc61fa7675c53000000006b483045022100efc6e04a4735465257c4f0ff51f9015c3806daebb390ceb1ae18402794a3192c02204616b6cd7c86321d896270d2758db2d245f0c14d60693711c1e891fa2ea5c1010121036a9946621a6428c3719cd992f32c5ebf1fec1c403e2f7796301fc000473bf2b6ffffffff03802b21000000000017a914f896d5607bc2b01309019104d9dd33fa76d79f538751cfa600000000001976a9145a45d570db268e085de17cb5b53d5dba5eeb855d88ac63890100000000001976a9148ae4ce7cbda181e6c2635d15e518dafbbabd5caa88ac00000000

You can check that the SHA256d for this signedTransaction is 091194d5da982a2da39776b76b2ac7cb7b2fdf03e2fe1bb66ec25b06ca004c84 on this page: http://extranet.cryptomathic.com/hashcalc/index (remember to tick the 'Enter as hex' box) by flipping the endianness (Bitcoin uses small-endian representation of hex numbers/byte arrays), you get the expected result:

844c00ca065bc26eb61bfee203df2f7bcbc72a6bb77697a32d2a98dad5941109

Transaction malleability means that you can change the signedTransaction without invalidating it. So someone else has provided the signature but you can change the signed transaction in some way without invalidating the provided signature.

A Bitcoin transaction consists of different fields such as inputs, output amounts, output destinations etc. One of the fields is called scriptSig and this is where the signature goes.

It is possible to change the scriptSig field without invalidating the signature. The scriptSig field consists of instructions (opcodes) where a signature is considered valid if the execution of the scriptSig field followed by the execution of the scriptPubKey field (another field consisting opcodes) leaves the number 1 on top of the stack. The virtual machine that executes the opcodes is a stack machine.

For example you can add the op code OP_NOP (which does nothing) in front of the rest of the scriptSig without invalidating the signature. The signed transaction may still be picked up by miners but the transaction ID (once it is included on the blockchain) will be different than what the signer expects.

Segregated witness transactions solve this problem by removing the signature from the scriptSig field into a new field called the witness field and it also prevents any additional data from entering the scriptSig field thus preventing the malleability. The TXID of a segwit transaction is calculated the same way but it does not include the new field, the witness.