Randomness, signature scripts, and transaction malleability

Segregated witness brought along with its activation a host of changes including fixing transaction malleability — the ability of a transaction’s identifier, a SHA256 hash of the transaction, to change without the underlying transaction changing. A transaction object typically contains the following fields: version, transaction inputs (containing previous hash, previous index, signature script, and sequence), transaction outputs (containing amount and public key scripts), and the locktime.

These fields, except for the signature script, cannot be changed without invalidating the transaction. The field containing the unlocking script is emptied (a signature should not sign itself) before the transaction is hashed thus making it possible to change the unlocking script without rendering the transaction useless. Because of this reason, different unlocking scripts can represent the same transaction. How is this so? Initially, I thought that it had to do with how signatures are calculated, given that randomness is embedded in the signing algorithm used to sign transactions.

From my perspective, understanding the basic underlying mathematics of the signing process could provide some insights. Hence, in this article, I will explain my understanding of the basic math of signing, how different signatures, and in extension, unlocking scripts, can apply to the same transaction, and how segwit fixed transaction malleability.

Basic mathematics of signing

Signing is a way to prove the knowledge and possession of a secret number, i.e. private/signing key (e) without revealing this number. We know that in asymmetric cryptographic systems

Equation 1: Calculating public key from private key and generator point

where G is the generator point and P is the public key.

To sign a transaction hash, a random number k is selected such that

Equation 2: Calculating signature’s r value

I assumed that because G lies on the elliptic curve, R lies on it too so that the summation of two points on the curve will give the position of R (addition is closed in a finite field). These points (u, v) can be selected by the signer as depicted in the image below.

Figure 1: Elliptic curve with uG, vP and kG points on the curve

Equation 3: Discrete Logarithm Problem (DLP)

Knowing that eG = P, and rearranging

Equation 4: Target of the signing

Equation 4 can be considered as another way to represent the discrete log problem (DLP) because you either have knowledge of e, to select k such that (k — u)/v is equal to e (thus solving eG = P), or you try a brute force approach by selecting several combinations of (k, u, v).

In generating a valid signature S(r,s) for a transaction, we:

• hash the transaction to get z (the transaction hash) — taking note to empty the unlocking script and append appropriate signature hash flags,
• choose a random unique k,
• calculate kG = R(r,y) and select its x-coordinate (r),
• and calculate s such that the transaction hash (z), and signing key (e) are incorporated into the signature by selecting u and v as shown below:

Composing r and s gives a valid signature for the transaction.

Why different signature scripts can apply to the same transaction

As can be seen, any combination of k (must be unique for a signature), u, and v that satisfies the equation is valid for the given transaction hash z. From the signer’s perspective, this is fine. The signer of a transaction can sign the transaction many times, generating different signatures valid for the said transaction. This signature is then embedded in the signature script of the transaction, and then broadcast to the network.

However, some malicious users on the network can receive the broadcast transaction and modify it in different ways to generate a new valid but malleated transaction, which is essentially the same as the initially broadcasted transaction, albeit with a different transaction ID. These transactions spend the same inputs, transferring the same value to the same outputs, thus creating a conflict where only one of these transactions will be mined and added to the ledger. If the malleated transaction is mined, other transactions referencing outputs from the original transaction cannot spend from it.

How is this transaction malleability possible? The malicious user can modify the signature format of, add extra instructions to, or use cryptographic tricks on the signature script (Rosenbaum, 2019). Basically, by changing the signature script of the transaction, which changes the serialized transaction, and the transaction identifier.

Segwit and fixing transaction malleability

Segwit proposed to move the signature script data into another field — the witness field — that is not used for calculating the transaction ID, so that changes to the signature script field cannot impact the transaction identifier.

Conclusion

Randomness and the selection of a unique k value per signature allow signers to mutate transaction objects. They can generate different signatures for a transaction although one is selected and embedded into the unlocking script. In broadcasting their signed transaction, pre-segwit, users could experience a malleability attack that allowed malicious users to modify the signature script field of the broadcast transaction and change the transaction’s identifier. With segwit, moving the data from the signature script into a field that does not impact the calculation of the transaction ID, eliminated the malleability attack vector.

Note:

I would deeply appreciate any feedback you can provide. If you found this article helpful/useful or found factual misrepresentation, please do not hesitate to comment or contact me here or on Twitter @engb_os.

References

1. Antonopoulos, A. (2017). Mastering bitcoin: Programming the open blockchain
2. Song, J. (2019). Programming bitcoin: Learn how to program bitcoin from scratch
3. Rosenbaum, K. (2019). Grokking Bitcoin