What is ECDSA?⌗

  • ECDSA is a signature generation scheme which uses a key pair consisting of a public key and a private key.

  • The "EC" relates to this scheme being a variant based on an Elliptic Curve.

  • ECDSA requires agreement of three parameters:

    1. \$G\$ — the generator point

    2. \$n\$ — the multiplicative order of the point \$G\$

ECDSA in bitcoin⌗

Transaction signatures⌗

Bitcoin uses digital signatures to authorise spending of UTXOs. In general, once a new transaction has been created the private key of each (input) UTXO in the transaction must sign the entire transaction. However this is not always necessarily the case…​

There is a parameter in the signature called the SIGHASH and this can be changed to reflect which sub-parts of the transaction you want the signature related to this input to be signing. There are three ways signatures can commit to outputs:

  1. SIGHASH_ALL — commit to all outputs

  2. SIGHASH_SINGLE — commit to output at same index as input

  3. SIGHASH_NONE — commit to no outputs! more outputs can be added without invalidating your signature

…​and two ways to commit to inputs:

  1. ANYONECANPAY is not set — no one can change any input without invalidating your signature

  2. ANYONECANPAY is set — inputs can be changed, added or removed; anyone can pay

Any combination of input and output SIGHASH types can be used which gives 6 combinations.

A "standard" transaction for example would probably combine SIGHASH_ALL with an unset ANYONECANPAY to commit to the entire transaction.

SIGHASH_NOINPUT now renamed to SIGHASH_ANYPREVOUT is a proposal for a sighash where the identifier for the UTXO being spent is not signed, allowing the signature to be used with any UTXO that’s protected by a similar script (i.e. uses the same public keys).

secp256k1 parameters⌗

The elliptic curve chosen for bitcoin by Satoshi was secp256k1. Parameters for this curve can be found here and below:

The elliptic curve domain parameters over \$bbb"F"_p\$ associated with a Koblitz curve secp256k1 are specified by the sextuple \$T = (p, a, b, G, n, h)\$ where the finite field \$bbb"F"_p\$ is defined by:

\$p = tt"FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F"\$

or

\$p = 2^256 −2^32 −2^9 −2^8 −2^7 −2^6 −2^4 −1\$

The curve \$E: y^2 = x^3 +ax + b\$ over \$bbb"F"_p\$ is defined by:

\$a = tt"00000000 00000000 00000000 00000000"\$

\$b = tt"00000000 00000000 00000000 00000007"\$

The base point \$G\$ in compressed form is:

\$G = tt"02 79BE667E F9DCBBAC 59F2815B 16F81798"\$

and in uncompressed form is:

\$G = tt"04 79BE667E F9DCBBAC 59F2815B 16F81798 483ADA77 A6855419 9C47D08F FB10D4B8 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 55A06295 CE870B07 029BFCDB 2DCE28D9 55A06295 CE870B07 029BFCDB 2DCE28D9 26A3C465 5DA4FBFC 0E1108A8 FD17B448"\$

Finally the order \$n\$ of \$G\$ and the cofactor are:

\$n = tt"FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141"\$

\$h= tt"01"\$

  • This curve can be used with some other signature algorithms, for example it is compatible with the Schnorr scheme.

  • Once a private key \$k\$ on the curve has been generated a public key \$K\$ can be generated by multiplying by the generator point, \$G\$.

    Therefore to calculate the public key \$P\$, we effectively want to find the multiple \$kG\$ of the generator point \$G\$, which is the same as adding \$G\$ to itself, \$k\$ times in a row.

    In elliptic curves, adding a point to itself is the equivalent of drawing a tangent line on the point and finding where it intersects the curve again, then reflecting that point on the x-axis.

Malleability⌗

Malleability uses⌗

Certain malleability can be useful in bitcoin because it allows us to create more complex types of transactions such as multi-sig and lightning channels. These types of transactions generally rely on malleability so that signatories can manipulate inputs and/or outputs independently. Therefore it is important to consider that "transaction malleability" in bitcoin is not necessarily a negative concept.

Types of malleability⌗

In 2014 at least 7 forms of transaction malleability were known, as detailed by the motivation for BIP 62. The 5th of these relating to the ESDSA signature malleability under discussion here:

Inherent ECDSA signature malleability ECDSA signatures themselves are already malleable: taking the negative of the number \$S\$ inside (modulo the curve order) does not invalidate it.

We would distinguish this type of malleability from "script malleability" — modifications to input scripts in transaction messages — and "input/ouput malleability" — modifications to the list of inputs and outputs in transaction messages.

ECDSA malleability⌗

For every ECDSA signature \$(r,s)\$, the signature \$(r,s-N)\$, which is effectively \$r\$ modulo the curve order \$N\$, is a valid signature of the same message. Note that the new signature has the same size as the original, as opposite as the malleability of padding, source.

Given a signature \$(r,s)\$ it’s possible to calculate the complementary signature without knowing the ECDSA private keys. The complementary signature has a different hash, so using the complementary signature will result in a new txid. In bitcoin terms, this means that an attacker can change a txid by broadcasting a variation of the transaction that uses the complementary ECDSA signature. This is because the txid calculation includes the ECDSA signatures of the transaction.

As the only use case for this "third party signature malleability" is for a would-be attacker to obscure a legitimate transaction in the mempool/UTXO set, we would like to remove this source of malleability.

With ECDSA signature malleability it is possible for an attacker to malleate a transaction so that it is syntactically different, but semantically identical. That is to say, they cannot change the meaning of the transaction; which inputs are spending to which outputs.

ECDSA malleability fix⌗

The fix for this is to enforce a canonical signature representation. The Bitcoin core developers decided to use the following scheme:

  • Both signature values are calculated, but only the signature with the smaller (or "lower") "S-value" is considered valid. That is, the correct representation is the form with the smaller unsigned integer representation.

Bitcoin Core added a mechanism to make the signing code always produce signatures with "even S" in PR 2131 in August 2013.

Later in October 2015 a mechanism was added to enforce low S-values as part of transaction standardness with PR #6769. Validation of the rule is done with the transaction script standardness flag SCRIPT_VERIFY_LOW_S, which all recent Bitcoin implementations now use. This prevents non-"low S" transactions from being relayed or entering the mempool, but they can still technically be added by a miner to a block.

From Greg Maxwell in the commit message for PR 6769:

If widely deployed this change would eliminate the last remaining known vector for nuisance malleability on boring SIGHASH_ALL p2pkh transactions. On the down-side it will block most transactions made by sufficiently out of date software.

This does not replace the need for BIP62 or similar, as miners can still cooperate to break transactions. Nor does it replace the need for wallet software to handle malleability sanely[1]. This only eliminates the cheap and irritating DOS attack.

— Greg Maxwell

The ECDSA signing flaw was originally supposed to be fixed by BIP62, which was later withdrawn.

SegWit⌗

SegWit also helps address the issue; when we think of a transaction, we really just care about the inputs, outputs, and payment amounts. ECDSA signatures are essential to the Bitcoin security model, but don’t actually affect these transaction details. Segwit transactions continue to include a legacy txid as described above, but also include a new wtxid.

In a SegWit transaction the txid does not include the ECDSA signature data however the wtxid does include the signature data. This means that:

  • For a SegWit transaction the txid is not vulnerable to 3rd party ECDSA malleability.

  • For a SegWit transaction the wtxid is vulnerable to to 3rd party ECDSA malleability.

Tip
 Note that even with SegWit active on the network, non-SegWit transactions still have meallable txids (i.e. they remain unchanged).

Malleability with the Schnorr algorithm⌗

The motivation of BIP 340 states that:

Non-malleability: The SUF-CMA security of Schnorr signatures implies that they are non-malleable. On the other hand, ECDSA signatures are inherently malleable[1]; a third party without access to the secret key can alter an existing valid signature for a given public key and message into another signature that is valid for the same key and message. This issue is discussed in BIP62 and BIP146.

Questions⌗

  1. Are "low S" and "even S" equivalent?

    In Jonas Nick’s blog post Reducing Bitcoin Transaction Sizes with x-only Pubkeys he describes how "x only" pubkeys is planned for the Schnorr scheme. Based on this post, and the definition of LOW_S in BIP 146:

    We require that the \$S\$ value inside ECDSA signatures is at most the curve order divided by 2 (essentially restricting this value to its lower half range). Every signature passed to OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG, or OP_CHECKMULTISIGVERIFY, to which ECDSA verification is applied, MUST use a \$S\$ value between \$tt"0x1"\$ and \$tt"0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0"\$ (inclusive) with strict DER encoding (see BIP66).

    If a signature passing to ECDSA verification does not pass the Low S value check and is not an empty byte array, the entire script evaluates to false immediately.

    A high \$S\$ value in signature could be trivially replaced by \$S' = tt"0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141" - S\$.

Additional sources⌗

  • Eklitske has a good post on Bitcoin Transaction Malleability from 2017.

  • On the Malleability of Bitcoin Transactions by Marcin Andrychowicz, Stefan Dziembowski⋆, Daniel Malinowski† and Łukasz Mazurek offers good technical insight into the issues.

1. If (r,s) is a valid ECDSA signature for a given message and key, then (r,n-s) is also valid for the same message and key. If ECDSA is restricted to only permit one of the two variants (as Bitcoin does through a policy rule on the network), it can be proven non-malleable under stronger than usual assumptions.