In ECDSA, inherent signature malleability is a byproduct of the structure we use to verify a digital signature. It allows anyone to modify the signature in a specific way without access to the private key and yet the signature remains perfectly valid! We can observe that for every single signature there is a perfectly valid second signature; one that is easy to calculate and use.  In the Bitcoin world, this can create problems if the signature is part of the data used to identify transactions.

Bitcoin addresses this in BIP 146.  I've always accepted the solutions without spending too much time thinking about it. In reviewing some notes, I started a deeper dive to fully understand why malleability exists.  

So without further ado, here is a brain dump for posterity. The one caveat: I am not a cryptographer and it has been 20 years since I've taken a math class, so excuse the layman explanation and feel free to comment, correct, or enlighten in the comments.

Let's first start with a simple discussion of ECDSA to establish a common use of variables throughout the discussion. This will be quick as I'm assuming the reader has some familiarity with elliptic curve cryptography. If not, I recommend brushing up in one of the many great articles out there.

First thing we need to consider is that there is a finite set of numbers in use called a finite field.  The field is the size of a prime number. For the sake of this discussion, we called the prime number p and define the field is Fp={0,1,...,p-1}.  

Next we consider an elliptic curve. Elliptic curves have the equation y2=x3+ax+b. Because of that y2, elliptic curves reflect over the x-axis, meaning the same x-coordinate has two possible y-coordinates.

For elliptic curve cryptography, we create an elliptic curve over a finite field and we use point addition. Point addition can be thought of as taking two points of the curve, finding the slope of the line created by those points, finding the third point on the curve, then reflecting it across the x-axis.  When the same point is used, we take the tangent of the point, take that line and find the other intersection point on the curve and reflect it.  This forms the basic operation of point addition, of which we can repeatedly add the same point to achieve scalar multiplication.  That's a lot of word soup, but the main thing to remember is that point addition is basically a one-way function.

So if we take a point on the curve G, we'll call it our generator point, and perform scalar multiplication on it we end up with the equation:

eG=P
  • e is some scalar value
  • G is our generator point
  • P is the resulting point on the curve (with x and y coordinate)

The resulting point P is the public key! It can be shared and it's virtually impossible to know what value e was used to arrive at that point.  As such the value e is our private key.

Another aspect is that we reach some scalar value n that when scalar multiplied against G results in an invalid point.

As a result we require our scalar value to be between 0 and n: 0 <= e < n.

Putting it all together elliptic curve definition for secp256k1, used by Bitcoin, looks like this:

  • p = 2256-232-977
      = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
  • a = 0
  • b = 7
  • Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
  • Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
  • n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

The private key is simply some large number e. For Bitcoin, we generate a 256-bit value between 1 and n-1.  

The corresponding public key is a point on the curve that is generated using our equation eG=P and has two coordinates (x,y).

ECDSA

So with the basics of ECC discussed, lets briefly refresh ECDSA.

An ECDSA signature consists of two parts, r and s, both of which are 256-bit numbers in the case of secp256k1. This is often denoted as the tuple [r, s].

The signature equation for ECDSA is

uG + vP = kG

where

  • u = z/s
  • v = r/s
  • G is our trusty generator point
  • P is our public key point, remember P=eG where e is our private key.
  • k is some arbitrary unguessable and never reused value
  • z is the 32-byte hash of the message that we're signing

r is pretty easy to generate. It is just the x-coordinate of right half of the equation: kG. So we get point R from the equation R=kG, extract the x-coordinate so that r = Rx.  Notice that we're not concerning ourselves with the y-coordinate of this point. Remember that for now.

Next we need s.  If we take our signature equation and some basic algebra we end up with

u*G + v*P = k*G
z/s*G + r/s*e*G = k*G # expand
z/s + re/s = k        # drop G
(z+re)/s = k
(z+re)/k = s

With knowledge of z, k, and e we can generate both pieces of the signature r and s. We can then provide [r, s], z, and P to another party and they can verify it.

Verifying

As stated, to verify a signature, we need

  • z the hash of the message that was signed
  • P their public key corresponding to the private key used to sign the message
  • [r,s] which is the signature

To verify we reconstruct u and v and plug values into our equation. Remember that:

  • u = z/s
  • v = r/s

We then use the equation uG + vP and end up with some point R.  If the x-coordinate of R matches the provided value r in the signature then we have a signature match!

Astute readers will note that we're only comparing the x-coordinate to verify the signature.  As we recall from our refresh of elliptic curves there are two y-coordinates for every x-coordinate.  This is the source of our malleability.

Signature Malleability Maths

As we just saw, to verify a signature we only verify the x-coordinate of the resulting equation. This means that there are two valid points: (r, y) and (r, p-y).  

In the Bitcoin world, BIP146 addresses the malleability by requiring the signature use the low-s value.  This means that the s value must be less than n / 2 and we can trivially find the low s value with n-s.  

If you're a little lost with these last two paragraphs, you're reached the point that started me on this entire journey!  So why is it n-s and not p-s? Why does this translate to the points y and p-y?  After working through the maths we'll see the answer.  I'll describe it and then we'll show some code output to make it concrete.

If you recall, p is the size of the finite field. So p is ultimately driving the values of x and y that constitute some point on the curve.  Because the curve is contained within a finite field it follows that we can't have an x or y value that is larger than p.

Meanwhile, n is the size of the finite cyclic group. Remember from our equation eG=P that e must be less than n.  So n is controlling how we scalar multiply against the generator point.

So we can see that n is controlling the scalars used in the left side of our equation eG=P and p is controlling the values that constituted a point in right side of the equation. Skeptical? Let's take a look at some concrete examples.

First thing, let's consider some point x.  We know that we have two possible y positions y and p-y.

So using our simple private key/public key equation eG=P let's validate that:

eG     = (x,y)
(n-e)G = (x,p-y) 

We start by taking a scalar value e  as one private key then subtracting it from n to create a second private key.  

const prvkey1: bigint = 1n;
// prvkey1   0000000000000000000000000000000000000000000000000000000000000001

const prvkey2: bigint = Secp256k1.N - 1n;
// prvkey2   fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140

The public keys for each should share the same x value and the y values should be be y and p-y.

const pubkey1: CurvePoint = Secp256k1.pubPoint(prvkey1);
// pubkey1.x 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
// pubkey1.y 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

const pubkey2: CurvePoint = Secp256k1.pubPoint(prvkey2);
// pubkey2.x 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
// pubkey2.y b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777

We first validate that both public keys share the same x value. Sure enough, both public keys have an x value  of 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798.  

Next we need to verify the y values. Again, verifying y and p-y also checks out 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 == fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f-b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777!

expect(pubkey1.x).to.equal(pubkey2.x);
expect(pubkey1.y).to.equal(Secp256k1.P - pubkey2.y);

So this is pretty cool. We can see that we can invert either the scalar or the point side of the equation using n or p respectively.  Furthermore, if we invert one side, we know the equation needed to invert the other side.

At this point, it should be starting to make sense why we use n-s to get the low-s  signature, but we'll work through the equations again and show a concrete example.

If we look at the equation for a digital signature, we should be able to verify that using n-s creates the a point p-y as with the following two equations:

z/s    *G + r/s    *P = (r,y)
z/(n-s)*G + r/(n-s)*P = (r, p-y)

Recall that with digital signatures, we're only verifying the x coordinate.  More importantly with malleability, we are able to change the signature without knowledge of the private key. As such z, P, and obviously G remain unchanged.  So our only option is to modify s which is also conveniently part of the signature data (remember the signature consists of the tuple [r, s]).  

From our previous exercise this should all make sense. Since s is a scalar value being multiplied by the generator point G, we invert it using n.  If we do that, we should expect the right side of the equation, the point, to have it's y value flipped equivalently with p-y.

For a concrete example, let's start by generating some value z that we're going to sign along with the private key and public key.

const z: bigint = 2n;
// z       0000000000000000000000000000000000000000000000000000000000000002

const privkey: bigint = 1n;
// prvkey   0000000000000000000000000000000000000000000000000000000000000001

const pubkey: CurvePoint = Secp256k1.pubPoint(privkey);
// pubkey.x 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
// pubkey.y 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

Next we create our first signature

const sig1: EcdsaSig = Ecdsa.sign(privkey, z, false);
// sig1.r 3dd21cd54e1b1178bba113b5c06b4a58c3b101eb007597fe4a0fca796daa67e7
// sig1.s 4e1bf4b3211203e356603c1a900846e8a40b0b0372aeffb6319de96ec8c25a1d

Next we create convert that original signature's s values by subtracting it from n

const sig2: EcdasSig = new EcdsaSig(sig1.r, Secp256k1.N - sig1.s);
// sig2.r 3dd21cd54e1b1178bba113b5c06b4a58c3b101eb007597fe4a0fca796daa67e7
// sig2.s b1e40b4cdeedfc1ca99fc3e56ff7b91616a3d1e33c99a0858e34751e0773e724

As you can see, both signatures have the same r value but we have different (inverted) s values. Finally to test our theory of malleability, we should see if we can verify both signatures with the same pubkey P and message digest z.

expect(Ecdsa.verify(pubkey, z, sig1)).to.equal(true);
expect(Ecdsa.verify(pubkey, z, sig2)).to.equal(true);

Final Thoughts

We've shown how you can invert the scalar and point sides of the equation and how signature malleability works. I will leave one final thought as an exercise for the reader.

In our malleability example we saw how the r value of the signature can come from  either point (r, y) or (r, p-y).  We see that using private key e in the signature creation results in point (r, y).  What is the natural way to obtain point (r, p-y)?  Or more succinctly, what private key do we use to obtain the signature of z that results in (r, p-y)?

If you enjoyed this, feel free to check out the "from scratch" ECC library. The malleability code can be viewed in these tests.