Transaction Malleability in Bitcoin
The transaction malleability was something discovered in 2015, which means it was there for a long time until someone stumbled upon the error. But more than that, there was more than one weakness and the other one was only discovered 3 months later. Some say this weakness was used to con exchanges and business and that it may be responsible for Mt Gox ending.
In this article, I will explain these two known bugs and what was made to counter the attacks.
OpenSSL and DER ASN.1 verification
Until July 4th, 2015 it was possible for a bad actor running a full node to broadcast a valid transaction with a totally different TXID (transaction identifier), causing an invalid double-spend on the network and canceling the real transaction. This bug is believed to be heavily used against Mt Gox.
The attack was not that complex. First, you have to own Bitcoin in some exchange. Then you ask for a withdraw to your address. If you own a full-node that is a peer to the exchange’s full-node, you can change your withdraw’s TXID as follows.
The OpenSSL used in Bitcoin had an error when verifying the signatures using DER ASN.1. This verification ignored white spaces (zeroes) at the end of a signature, and the signature is used to calculate the transaction’s TXID. That means that just adding one 0 to a valid signature would completely change its TXID. The actor then broadcasts this “new” transaction to its peers and someone expecting it to be included in a block would think it failed. But remember, your withdraw would be eventually included in a block under a new TXID.
The next step would be to contact the exchange and tell them your withdraw had disappeared from the mempool and that they had to re-do it. Exchanges didn’t know about it back then and if you did this repeatedly you could withdraw a large sum in Bitcoins before they notice they have been compromised.
This error was corrected in block 363,724 through a soft-fork following BIP66 implementation on July 4th, 2015. The correction was made by Pieter Wuille and changed 4 verification in OpenSSL’s DER ASN.1 code, rendering the attack useless from this block on.
The changes were made so these verifications would result in an error:
- S1' P1 CHECKSIG: The signature (S1’) is valid for the public key (P1) but isn’t a valid DER signature;
- F’ P1 CHEGSIG NOT: The signature (F’) is invalid for the public key (P1) and isn’t a valid DER signature;
- 0 S1' S2 2 P1 P2 2 CHECKMULTISIG: The first signature (S1') is valid for the first public key (P1) but isn’t a valid DER signature (in a multi-signed transaction);
- 0 F S2' 2 P1 P2 2 CHECKMULTISIG NOT: The first signature (F) is invalid for the first public key (P1) but is a valid DER signature, The second signature (S2') is valid for the second public key (P2) but isn’t a valid DER signature (in a multi-signed transaction).
ECDSA’s Complementary Signature
Until October 2015 a new bug was used to change a transaction’s TXID using the Complementary Signature of a valid one.
The Bitcoin signature scheme is known as ECDSA, which is a DSA signature over an Elliptic Curve. The signature consists in a pair of coordinates (r,s) from an elliptic curve of order n, because of how the math involved in elliptic curves works, we can calculate a new signature (r,−s mod n) from the other side of the curve without knowing its private key.
This means that someone could repeat the last attack to, for an example, an exchange just by modifying the signature with its complementary one, changing the transaction’s hash and consequently its TXID.
This bug was discovered by Sergio Lerner and corrected, again, by Pieter Wuille through a soft-fork in PR #6769, where the clients started using the opcode SCRIPT_VERIFY_LOW_S in every transaction validation to guarantee the signature contained the even s, the one with the last bit 0 meaning it is the low s. Also, to publish a transaction on the network, you have to calculate both signatures and use the even one.
The fact that we didn’t hear anything related to transaction malleability after the last bug was corrected didn’t mean the community stopped looking for other ways to make the network more secure. A discussion started back in late 2015 and was only implemented via soft-fork in November 2017 using the code from BIP141. The way chosen by Eric Lombrozo, Johnson Lau and Pieter Wuille was to create a new transaction identifier that didn’t use any part of the signature to create the hash. This new identifier is known as WTXID (witness transaction identifier).
To understand more about SegWit, read my other article discussing its technical aspects here.