Question on DER-encoding of signature pair (r, s)

deepceleron

legendary

Activity: 1512

Merit: 1036

The signature data is encoded using ASN.1 stream encoding. Although Bitcoin implementations just shove signature bytes where they should go, it would be more correct to actually use an ASN library to make the DER-encoded signatures. That way there would not be mystery undocumented bit-set data such as the tag identifier, which are not just arbitrary bytes, but define the encoding method of the following bytes.

I documented this a bit before, walking through each byte of a transaction with the DER docs in hand (although I didn't make a pretty table):

Quote from: deepceleron on December 30, 2013, 04:37:32 AM

Transaction data format version (uint32_t):
01000000

TXIN:
TX_IN count (number of Transaction inputs, satoshi VarInt):
01
TXIN DATA:
Previous txout hash:
21eb234bbd61b7c3d31034762126a64ff046b074963bf359eaa0da0ab59203a0
Previous txout index:
01000000
Script Length:
8b
Signature Length: (48h = 72 bytes)
48
ECDSA Signature (X.690 DER-encoded):
ASN.1 tag identifier (20h = constructed + 10h = SEQUENCE and SEQUENCE OF):
30
DER length octet, definite short form (45h = 69 bytes) (Signature r+s length)
45
ASN.1[/url] tag identifier (02 = INTEGER):
02
Signature r length (DER length octet):
20
Signature r (unsigned binary int, big-endian):
263325fcbd579f5a3d0c49aa96538d9562ee41dc690d50dcc5a0af4ba2b9efcf
ASN.1[/url] tag identifier (02 = INTEGER):
02
Signature s length (DER length octet):
21
Signature s (first byte is 00 pad to protect MSB 1 unsigned int):
00fd8d53c6be9b3f68c74eed559cca314e718df437b5c5c57668c5930e14140502
Signature end byte (SIGHASH_ALL):
01

Key length:
41
Public Key prefix:
04
Public Key part x
52eca3b9b42d8fac888f4e6a962197a386a8e1c423e852dfbc58466a8021110e
Public Key part y
c5f1588cec8b4ebfc4be8a4d920812a39303727a90d53e82a70adcd3f3d15f09
Sequence Number:
ffffffff

TXOUT:
txout number:
01
Value in base units:
a086010000000000
Script Length (107 bytes):
6b

Script (if we were to run it):
OP_PUSHDATA1 - The next byte contains the number of bytes to be pushed onto the stack:
4c
Bytes (68 = 104 bytes):
68
STACK DATA 104 bytes:
4c554b452d4a522049532041205045444f5048494c4521204f682c20616e6420
676f642069736e2774207265616c2c207375636b612e2053746f7020706f6c6c
7574696e672074686520626c6f636b636861696e207769746820796f7572206e
6f6e73656e73652e

Lock Time (cannot be included before this block):
00000000

amaclin

legendary

Activity: 1260

Merit: 1019

Quote

As piotr_n pointed out the bitcoin expects the highest bit to be zero so if it isn't an extra zero byte is added. This means that r & s will always be 32 or 33 bytes.

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

Peter R

legendary

Activity: 1162

Merit: 1007

Thanks Gerald. Your explanation was perfectly clear.

I'm starting to really appreciate the collaborative open-source development bitcoin promotes (which is new for me). Instead of getting stuck and wasting a day spinning my wheels, I just post a question, move on to something else, and I when I check back often the problem is solved. Hopefully lurkers read these posts and it answers some of their questions too.

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

As piotr_n pointed out the bitcoin expects the highest bit to be zero so if it isn't an extra zero byte is added. This means that r & s will always be 32 or 33 bytes. Don't quote me but I believe this is a bug in OpenSSL which was copied and now everyone has to keep the bug in the code to ensure it remains compatible.

Quote

You can't think of a signature as a curve point (x,y), right? A signature is a pair of 256-bit numbers (r,s), not a point on secp256k1.

Correct. A point in computed in the creation of the signature (k x G) but it is not the signature itself. r & s are not an x & y value.

Quote

Did I mark-up the image correctly (r comes before s)?

Yes.

Quote

If I know r and s as 256-bit integers (big numbers), how exactly do I DER encode them?

You will also need to know the sighash. Given r,s, and sighash they are arranged in the following order:

All elements are 1 byte except r & s which will be 32 or 33 bytes. Also be sure to read up carefully on sighash because it is "moved" (for reasons that are beyond me). Another Satoshi-ism I guess.

r_value = Convert r into a little endian byte array. If the leading bit is not zero then prepend a zero value byte.
s_value = Convert s into a little endian byte array. If the leading bit is not zero then prepend a zero value byte.
r_len = number of bytes for r (always 20 or 21)
s_len = number of bytes for s (always 20 or 21)
sequence = always 0x30
integer = always 0x02
len_rs = r_len + s_len + 2 (two extra bytes for the two integer bytes)
len_sig = len_rs + 3 (three extra bytes for the len_rs byte, the sequence byte and the sighash byte

What follows next is whatever is needed to complete the script which is encumbering the outputs. The PubKey then follows when redeeming Pay2PubKeyHash outputs but is not universally present in other output types (i.e. Pay2PubKey).

Quote

An aside: Besides DER being the standard format of OpenSSL, is there really any benefit to DER encoding? It seems to me we could simply pack r and s and have all signatures exactly 64 bytes long.

Correct. There is very little reason to use DER encoding other than satoshi did it that way. A new version of the tx format could created which is more space efficient. The major advantage of DER encoding is sharing information between incompatible systems. It is excessively verbose to facilitate a data interchange. Putting DER signature inside propreitary data makes no sense. Knowing DER doesn't allow you to decode a Bitcoin tx, and if you can decode a Bitcoin tx you could just follow explicit rules to decode r,s, sighash, pubkeys, etc just like you need to follow explicit rules to decode the tx version, number of inputs, sequence, etc.

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: Peter R on June 15, 2014, 02:14:50 PM

Awesome. Thanks piotr_n. I am assuming that I was correct and that r comes before s in the signature pair, too, right?

Yes, R comes before S.

Also there is a hash type byte at the end (SIGHASH_ALL in your case)
Be careful with this; if it would happen that there was more than one extra byte after S, hash type is always the last one of them (anything else you ignore)
There are transaction inside the chain with signatures screwed like this and if you don't handle such cases properly you will loose time on investigating it.

Peter R

legendary

Activity: 1162

Merit: 1007

Awesome. Thanks piotr_n. I am assuming that I was correct and that r comes before s in the signature pair, too, right?

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

If the highest bit of the most significant byte is set, then you need to put 00 in front of it.

That is why fa gets 00 in front, but 46, 6f, and 15 do not

It comes from the protocol rule that the highest bit of the number means it is negative.
It's a bit screwed up in there (because these numbers are never negative), but many things in bitcoin protocol are screwed up and it still somehow works

And yes, the most significant bytes come fist - but only here. Not in the hashes or scripts other places, where you have the opposite order.

Peter R

legendary

Activity: 1162

Merit: 1007

I've been working through the byte-level details of bitcoin transactions and I need some help on DER-encoding.

I understand how to (manually) sign a transaction to determine the signature pair (r, s), but I don't understand how I take these two 256-bit numbers and pack them in the right order and with the proper padding for DER.

For example, here are two inputs to a transaction that I would think should have equal-length signature scripts but they don't. The difference is circled in red (there are 33 bytes in the first component of the signature for INPUT 2 instead of 32).

I found this excellent article on raw bitcoin transactions by Ken Shirriff. Here's a table Ken made to explain the byte-level packing:

Although this was extremely helpful, I think some things are not clear. For instance:

   - You can't think of a signature as a curve point (x,y), right? A signature is a pair of 256-bit numbers (r,s), not a point on secp256k1.

   - Did I mark-up the image correctly (r comes before s)?

   - If I know r and s as 256-bit integers (big numbers), how exactly do I DER encode them?

An aside: Besides DER being the standard format of OpenSSL, is there really any benefit to DER encoding? It seems to me we could simply pack r and s and have all signatures exactly 64 bytes long.

Topic: Question on DER-encoding of signature pair (r, s) (Read 3201 times)