Difference between revisions of "Transaction Malleability"

 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
=Disclaimer=
+
'''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.
This page has been copied directly from https://en.bitcoin.it/wiki/Transaction_malleability and may need extensive editing
 
  
22 October 2019
+
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.
  
Review by 1 November 2019
+
In general, the inputs of [[Bitcoin_Transactions|Bitcoin transactions]] will contain at least one [[Digital_Signatures_in_Bitcoin|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.
  
While [[Bitcoin_Transactions|transaction]]s are signed, the signature does not currently cover all the data in a transaction that is hashed to create the transaction hash. Thus, while uncommon, it is possible for a node on the network to change a transaction you send in such a way that the hash is invalidated. Note that this just changes the hash; the output of the transaction remains the same and the bitcoins will go to their intended recipient. However this does mean that, for instance, it is not safe to accept a chain of unconfirmed transactions under any circumstance because the later transactions will depend on the hashes of the previous transactions, and those hashes can be changed until they are confirmed in a block (and potentially even after a confirmation if the block chain is reorganized). In addition, clients must always actively scan for transactions to them; assuming a txout exists because the client created it previously is unsafe.
+
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.
  
== Signature Malleability ==
+
Transaction malleability also has the effect of allowing the [[TXID|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.
  
The first form of malleability is in the signatures themselves. Each signature has exactly one DER-encoded ASN.1 octet representation, but OpenSSL does not enforce this, and as long as a signature isn't horribly malformed, it will be accepted.<ref>https://bitcointalk.org/index.php?topic=8392.msg122410#msg122410</ref> In addition 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, in most circumstances the risk of such a malicious modification may be considered an aspect of implementation and may be mitigated using practical techniques.
  
As of block 363724<ref>[http://bitcoin.stackexchange.com/a/38438/21052 When did BIP66 switch from activation to enforcement?], answer by StephenM347, 6 July 2015, Bitcoin.StackExchange</ref>, the [https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki BIP66 soft fork] has made it mandatory for all new transactions in the block chain to strictly follow the DER-encoded ASN.1 standard.
+
It should be noted that transaction malleability here does not refer to the malleability of messages due to the [[Elliptic_Curve_Digital_Signature_Algorithm|ECDSA]] scheme itself used to sign transactions, as considerations relating to [[Transaction_Malleability#ECDSA Signature Malleability|ECDSA malleability]] can be mitigated using best practices.
Further efforts are still under way to close other possible malleability within DER signatures.
 
  
Signatures can still be changed by anyone who has access to the corresponding private keys.
+
==Script Malleability==
  
== scriptSig Malleability ==
+
[[File:script_malleability.png|thumb|Parts of a transaction not signed by a signature.]]
  
The [[OP_CHECKSIG|signature algorithm]] used in Bitcoin does not sign any of the scriptSig to create the signature. While signing the whole scriptSig would be impossible - the signature would be signing itself - this does mean that additional data can be added such that it will be pushed on the stack prior to the required signatures and public keys. Similarly OP_DROP can be added to leave the stack exactly as before prior to scriptPubKey execution.
+
''Script malleability'' is a type of transaction malleability that makes use of how the [[OP_CHECKSIG|OP_CHECKSIG]] operator functions when validating a signature.
  
Preventing scriptSig malleability is being considered as well. Currently transactions with anything other than data push operations in their scriptSig are considered non-standard and are not relayed, and eventually this rule may extend to enforcing that the stack have exactly one item after execution. However doing that may interfere with later extensions to Bitcoin.
+
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).
 +
 
 +
[[File:script_malleability_example.png|thumb|Two non-identical transactions valid under the same signature.]]
 +
 
 +
The first transaction, denoted by <math>TXID</math>, contains a signature corresponding to public key <math>P_{A}</math>. 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 <math>TXID^{'}</math>, differs from <math>TXID</math> only by the addition of an arbitrary data packet <math><Data></math> to its input script. The two transactions are non-identical, meaning that their hashes are also non-identical by definition <math>TXID \ne TXID^{'}</math>.
 +
 
 +
In this scenario, the transaction message has changed but both transactions <math>TXID</math> and <math>TXID^{'}</math> are equally valid because the signature <math>Sig P_{A}</math> 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|SIGHASH flags]] can be chosen to allow a signature to sign over the inputs and outputs of a transaction selectively.
 +
 
 +
[[File:list_malleability.png|thumb|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.
 +
 
 +
[[File:list_malleability_example.png|thumb|Constructing a transaction using different SIGHASH flags.]]
 +
 
 +
In this scenario Alice creates a first transaction, denoted by <math>TXID</math>, which is signed with <math>Sig P_A</math> 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 <math>Sig P_B</math> 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 <math>TXID^{'}</math>, where <math>TXID \neq TXID^{'}</math>.
 +
 
 +
We now have two distinct transactions, <math>TXID</math> and <math>TXID^{'}</math> which are both valid under both of the signatures <math>Sig P_A</math> and <math>Sig P_B</math>. 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 <math>TXID</math> under her signature, and Bob has now created a modified form of the original transaction message <math>TXID^{'}</math> 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 <math>(r,s)</math>, the signature <math>(r, -s \ mod\ N)</math> 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 <math>N/2</math>. In other words, taking the smaller of the two values <math>s</math> and <math>-s\ mod\ N</math> is sufficient to overcome this.
 +
<ref><https://eklitzke.org/bitcoin-transaction-malleability</ref>>

Latest revision as of 03:25, 22 April 2022

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 , contains a signature corresponding to public key . 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 , differs from only by the addition of an arbitrary data packet to its input script. The two transactions are non-identical, meaning that their hashes are also non-identical by definition .

In this scenario, the transaction message has changed but both transactions and are equally valid because the signature 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 , which is signed with 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 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 , where .

We now have two distinct transactions, and which are both valid under both of the signatures and . 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 under her signature, and Bob has now created a modified form of the original transaction message 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 , the signature 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 . In other words, taking the smaller of the two values and is sufficient to overcome this. <ref><https://eklitzke.org/bitcoin-transaction-malleability</ref>>