Transaction Malleability

Malleability is a concept in the fields of cryptography and computer science relating generally to the to ability to modify a message without altering its apparent validity.

In the context of Bitcoin, transaction malleability relates to the transaction messages passed between peers and users of the system, and the digital signatures used to validate those messages.

In general, the inputs of Bitcoin transactions will contain at least one digital signature used to facilitate the transfer of control of ownership of bitcoins. A digital signature in a transaction input must be valid in order for the transaction as a whole to be deemed a valid transaction that can be subsequently timestamped in the Bitcoin blockchain.

Transaction malleability therefore refers to the modification of a signed transaction such that the signature(s), and thus the transaction itself, is not invalidated. There are two core types of transaction malleability that fall under this definition:

   Script malleability - modifications to input scripts in transaction messages.

   Input/Output malleability - modifications to the list of inputs and outputs in transaction messages.

These types of transaction malleability can be used to achieve complex functionality of Bitcoin transactions, such as multi-party contract negotiation and the creation of data channels.

Transaction malleability also has the effect of allowing the transaction hash (TXID) of a valid signed transaction to be modified before it is mined. This makes transaction malleability a consideration for users of payments and applications as it is possible for a transaction of interest to be confirmed in a block under an unexpected hash.

However, in most circumstances the risk of such a malicious modification may be considered an aspect of implementation and may be mitigated using practical techniques.

It should be noted that transaction malleability here does not refer to the malleability of messages due to the ECDSA scheme itself used to sign transactions, as considerations relating to ECDSA malleability can be mitigated using best practices.

Script Malleability

Parts of a transaction not signed by a signature.

Script malleability is a type of transaction malleability that makes use of how the OP_CHECKSIG operator functions when validating a signature.

In particular, script malleability exploits the fact that a signature in a transaction input does not sign the input script in which it appears. This is because the message signed by the signature must necessarily exclude the signature itself. The parts of a transaction that are not signed by input signatures is shown in the figure (right).

Due to this fact, it is possible to modify the remainder of the input script that includes the signature such that the TXID of the transaction containing the signature is changed but the signature remains valid for the transaction. The input script may be modified either by adding or removing data to or from the input script. The signature remains valid for the transaction after modification, despite its data and TXID having changed, because the message signed by the signature always excludes this input script irrespective of its content.

Example

This type of transaction malleability is shown in the figure (below).

Two non-identical transactions valid under the same signature.

The first transaction, denoted by $TXID$, contains a signature corresponding to public key $P_{A}$. The parts of the transaction signed by this signature are shown in green, and the part that is not signed is shown in red. The second transaction, denoted by $TXID^{'}$, differs from $TXID$ only by the addition of an arbitrary data packet $<Data>$ to its input script. The two transactions are non-identical, meaning that their hashes are also non-identical by definition $TXID\neq TXID^{'}$.

In this scenario, the transaction message has changed but both transactions $TXID$ and $TXID^{'}$ are equally valid because the signature $SigP_{A}$ is valid for both transactions. This is because the message signed by the ECDSA signature has not changed because the modification was made to the input script, which was never part of the signed message.

Input and Output Malleability

Input and output malleability (or SIGHASH flag malleability) make use of the fact that different SIGHASH flags can be chosen to allow a signature to sign over the inputs and outputs of a transaction selectively.

DER encoding for a Bitcoin transaction signature.

An ECDSA signature used to sign a Bitcoin transaction is first encoded using the distinguished encoding rules (DER) standard before being appended with a SIGHASH flag. This is shown in the diagram (right).

There are six possible SIGHASH flags that may be appended to a signature in a Bitcoin transaction, whereby each flag selects a different combination of the transaction inputs and outputs to sign. Note that when an input is signed this excludes the input script.

The fact that SIGHASH flags allow for some inputs and outputs to be excluded from the message signed by a given signature, it is possible to have multiple signatures in a Bitcoin transaction which each sign different messages. This also means that transactions can be constructed such that inputs and outputs can be added to the input and output lists for a transaction after a signature has signed the initial list.

This allows for Bitcoin transactions to be constructed to cater for different use cases where the order in which the signatures are created is important. These scenarios may benefit from one signer being able to sign a transaction that will eventually be signed by many other participants to cover the cost of a payment for example.

Example

The diagram (below) shows how a transaction can be constructed such that it includes signatures which sign different transaction messages.

Constructing a transaction using different SIGHASH flags.

In this scenario Alice creates a first transaction, denoted by $TXID$, which is signed with $SigP_{A}$ using the flag SIGHASH_SINGLE|ANYONECANPAY. This choice of flag means that the signature generated by Alice only signs her input and the output at the same index position in the output list as her input in the input list.

The transaction created by broadcast is valid and may be mind immediately. However, Alice's choice of SIGHASH flag means it is also possible for a second party, Bob, to add inputs and outputs to the original transaction.

In the diagram, Bob adds an input and an output, and creates the signature $SigP_{B}$ that signs over the entire list of inputs and outputs using the flag SIGHASH_ALL. The additional input and output create a new transaction, denoted by $TXID^{'}$, where $TXID\neq TXID^{'}$.

We now have two distinct transactions, $TXID$ and $TXID^{'}$ which are both valid under both of the signatures $SigP_{A}$ and $SigP_{B}$. This is true because the two signatures sign different messages because their respective SIGHASH flags mean that they have selectively signed different parts of the overall transaction message.

This is therefore an example of transaction malleability as Alice created a transaction message $TXID$ under her signature, and Bob has now created a modified form of the original transaction message $TXID^{'}$ that is also valid under the same signature.

ECDSA Signature Malleability

The ECDSA signature scheme itself is vulnerable to a form of malleability, due to the fact that for every ECDSA signature $(r,s)$, the signature $(r,-s\ mod\ N)$ is a valid signature of the same message. <ref><https://bitcointalk.org/index.php?topic=8392.msg1245898#msg1245898</ref>> However, this is an implementation detail that is addressed simply by restricting the range of possible s values in a signature to a maximum of $N/2$. In other words, taking the smaller of the two values $s$ and $-s\ mod\ N$ is sufficient to overcome this. <ref><https://eklitzke.org/bitcoin-transaction-malleability</ref>>