Investigating Bitcoin Transaction Malleability Attacks

Introduction

This project was built to demonstrate the malleability attacks on Bitcoin Transactions. This post assumes initial knowledge of how the blockchain works in general and will not cover into what exactly is blockchain.

It has been said that transactions are fully secure, but there have been attacks that show how transactions can be hijacked. One particular way is via a transaction malleability attack, where attacks can ‘re-create’ the same transaction.

Overview of the Bitcoin Ecosystem

When Alice wants to send some Bitcoins over to Bob, it is usually done through this thing called a Transaction. The transaction (tx) eventually gets “minted”, or solidifed onto the blockchain. The tx is said to be secure and can never be forged once on the blockchain.

A tx involves many components. In general, a tx involves a set of inputs and outputs.

The key points to note are the following:

1. Transaction ID - it is a hash of the inputs ond outputs of a transaction.
2. Transaction Input - Contains a transaction signature.
3. Transaction Output - Contains some extra stuff

What is a Transaction (Tx) Malleability Attack?

A tx malleability attack occurs when a tx can actually be forged or altered. A tx that has been altered will have the exact same contents - same signature, same input and output. However, the TxID will be different. This means that the Bitcoin System still believes it was sent by the same user because everything else is the same.

Using a Mailbox analogy, imagine that Alice wants to send 50BTC to Bob. She writes a letter (a transaction) and places the letter in her mailbox (Bitcon Memory Pool). This transaction has an ID = 1234. Miners are now looking to validate that the letter is indeed from Alice.

Mel, an attacker, manages to duplicate the letter and places the duplicated letter into the Memory Pool. This duplicated transaction has an ID = 4567. Even though the contents are similar, the ID is different, but the Bitcoin system does not do validation on the ID. The Bitcoin Miners now work to validate both letters (transactions).

There is a race here. The moment one transaction gets validated, the second transaction will be ignored, because it will be recognised as a duplicate since the contents are exactly the same.

If the second transaction from the attacker gets validated, it is disastrous because:

1. The Bitcoins will be sent over to Bob, since the contents are the same, and the actions taken by the blockchain will be the same. Bob will receive 50 BTC.
2. Alice will find that her transaction has failed but she will have 50 BTC deducted from her account.
3. Bob can now say that he did not receive any BTC, and Alice must resend 50BTC because there is no way for Alice to check (you need the TxID) if Bob indeed received 50BTC from her.

Attack Anatomy

Observe that a TxID is made out of (1) inputs and (2) outputs. To modify TxID, we will need to either modify (1) or (2).

In this case, what is actually modifiable is the Transaction Signature, which can be found in (1).

The reason is that signatures are malleable because signatures stem from mathematical algorithms, they can be altered while still being computed by machines as the same value. You can read this post for more information. See more on signature malleability.

Think of the following 2 scenarios:

1. Signature A = “3”
2. Signature B = “000003”

They are both different, but they both resolve to the same number, 3. Changing a signature is similar to the above example, unnecessary items are added to the signature which results in a new signature that is totally different, but perceived by machines to be the same.

In the Demo, we wrote a script that shows ECDSA signature malleability.

1. A mock account is created on the Ethereum Blockchain. This mock account has an address, and private key to sign transactions.
2. We create a message and hash that message.
3. This message is then signed with an original signature.
4. We manipulate the ECDSA signature and produce a totally new signature.
5. We use a function to recover the original signer address with the totally new signature, but passing in the message and new signature.
6. The function outputs the original account address, which shows that the new signature is intepreted the same as the old signature.

Solution

The solution to the problem is called Segregated Witness, or “SegWit”. It is a simple solution that became complex and I will not discuss it’s entirety here.

In general, the solution separates the non-crucial data into a location called the Witness. The Signature is now no longer found on the tx input. Hence, nothing inside the input or output can be malleated without the Bitcoin System recognising that there has been tampering done on the transaction.

The Witness is not longer stored on the exact same blockchain as Bitcoin. Instead, it runs on something called a sidechain, which is just another chain of hashes that runs in parallel to the Bitcoin blockchain.

To dive just a little deeper, understand that Bitcoin blocks consist of many things like the block header and data. The block header is what is “Chained” to one another.

In the above photo, the Witness data is now separated and lives alongside the block. You would have known that Bitcoin blocks use a data structure called the Merkle Tree, which is just an efficient way of storing and validating data. A Merkle Tree is a hash of hashes of hashes.

1. Each tx in a block is hashed. We called them hash1s.
2. Pairs of hash1s are concatenated and re-hashed to form a second layer of hash. We call them hash2s.
3. Repeat till you are left with the Root Hash.

The Witness Data forms its own merkle tree. Each Signature now has its own hash, and will cummulate into a Witness Tree Root Hash. This Root Hash is stored on the Coinbase Transaction, which is the very first transaction of every blockchain.

This is how the Witness Data are linked to the blocks.

Yes, there is still signature malleability on the witness data. But it no longer affects the Bitcoin Block Header and even if attackers change the witness data, there are no (known) sideeffects.

Conclusion

SegWit does have its own concerns and ramifications. Because of SegWit, there have been divisions in the BTC community. Furthermore, SegWit requires miners to actually upgrade their nodes in order to be effective. This might not happen as miners have no incentive to do so.

SegWit does have benefits other than solving transaction malleability. Most notable is that SegWit actually helped Bitcoin to scale, since it increases the bitcoin block size, essentially more transactions can be stored in a BTC block. But, these are all topics for another day.

Hope you learnt something new today!