Signature ECDSA

[bytcoin]

Today I was watching some 2018 transactions and it https://btc.bitaps.com/raw/transaction/20f8f32ff141caaf014373241f65dbe718970d08fa81708ccf3d0dc37e88fc8f  got me confused!



473044022100b55d62280cad71235b7b9ff771e3f6839ae7f02ff117cc620511d027068063b3021f63c7c0b9561e8b59dfde896d2203d4e990df42bd0062ec12cce615b91ce1c501

Between r and s I thought that only 0220 or 022100 was valid. I tried to create 2 testnet transactions with only 02 between r and s but it was not accepted.

[achow101]

0220 and 022100 are not magic separators. They are part of the DER encoding of the signature. DER encodes data in a Type Length Value format. 0x02 is a type. The byte that follows (0x20, 0x21, or in this case, 0x1f) is the length of the data. The 0x00 in 022100 is actually the first byte of the s value.

So in this signature, the length of the s value is 31 (0x1f) bytes rather than 32 (0x20) or 33 (0x21). This can happen occasionally, although it has a low probability. However you can't just change a signature to use 0x1f for the length, or remove the length entirely. That would make it invalid.

[bytcoin]

Now I understand it perfectly. 1f is just the byte My mistake was having included it as part of the value s. Thank you for the explanation

[NotATether]

From an old post here: The R and S values don't get as small as 31 bytes. There's a exponentially decreasing probability that the signature created will be a couple of bytes smaller.

To be correct: R & S usually are 32 or 33 bytes. But can be smaller.
If highest bit of 256-bit integer is set we got 33 bytes ( probability is 1/2 )
If highest byte is greater than 0 and smaller than 128 we got 32 bytes ( probability 127/256 )
If highest byte is 0 - we should take R as 248-bit integer and repeat these steps

There are signatures in blockchain where the length of R or S is 29, 30, 31

In other words the more zeros that are at the beginning of the private key hex, you'll end up with either an N+1 or N+2 length S (N is the byte length of the privkey excluding the zero bytes at the end, so 32 for this hypothetical example), or R, or even more rarely both of them.

The 0x00 in 022100 is actually the first byte of the s value.

Isn't that the first byte of the R value in this DER?

[pooya87]

In other words the more zeros that are at the beginning of the private key hex, you'll end up with either an N+1 or N+2 length S (N is the byte length of the privkey excluding the zero bytes at the end, so 32 for this hypothetical example), or R, or even more rarely both of them.

Bit-length of r and s have nothing to do with bit-length of the private key. For starters r is the x coordinate of the pubkey R which is computed using the ephemeral key not the private key. And s is computed using r (and e and k).

Isn't that the first byte of the R value in this DER?

Not exactly. The initial 0 is the padding to indicate the integer is positive.

To truly understand how signature is encoded you have to understand how DER encoding works. It is a very simple stream of bytes that uses the Tag Length Value (TLV for short) encoding scheme meaning
* everything always starts with a "tag" telling you the type of the "value" to expect, for example a sequence (0x30), an integer (0x02), a string (0x0C), boolean (0x01), null (0x00),... We only use sequence and integer tags in bitcoin.
* it is followed by the "length" of the value" encoded using a special way

* and finally the value itself

So when you see 0x3044022100b55d62280cad71235b7b9ff771e3f6839ae7f02ff117cc620511d027068063b3021 f63c7c0b9561e8b59dfde896d2203d4e990df42bd0062ec12cce615b91ce1c501 it translates into:

Code:

[sequence]
[0x44 byte length]
[value=
  [integer][0x21 byte length][value=00b55d62280cad71235b7b9ff771e3f6839ae7f02ff117cc620511d027068063b3]
  [integer][0x1f byte length][value=63c7c0b9561e8b59dfde896d2203d4e990df42bd0062ec12cce615b91ce1c5]
]

When we encode integers as arbitrary length byte arrays, in order the interpreter whether it is positive or negative we have 2 methods, one is using an additional byte (which is what we do here) if the highest bit of the highest byte is set.
0x63=0b01100011 -> not set -> don't need 0x00
0xb5=0b10110101 -> is set -> we need 0x00