Bitcoin Forum
June 17, 2019, 05:57:52 AM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Question on DER-encoding of signature pair (r, s)  (Read 3015 times)
Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
June 15, 2014, 06:47:20 PM
Last edit: June 15, 2014, 07:00:00 PM by Peter R
 #1

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.  


Run Bitcoin Unlimited (www.bitcoinunlimited.info)
1560751072
Hero Member
*
Offline Offline

Posts: 1560751072

View Profile Personal Message (Offline)

Ignore
1560751072
Reply with quote  #2

1560751072
Report to moderator
1560751072
Hero Member
*
Offline Offline

Posts: 1560751072

View Profile Personal Message (Offline)

Ignore
1560751072
Reply with quote  #2

1560751072
Report to moderator
1560751072
Hero Member
*
Offline Offline

Posts: 1560751072

View Profile Personal Message (Offline)

Ignore
1560751072
Reply with quote  #2

1560751072
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1560751072
Hero Member
*
Offline Offline

Posts: 1560751072

View Profile Personal Message (Offline)

Ignore
1560751072
Reply with quote  #2

1560751072
Report to moderator
piotr_n
Legendary
*
Offline Offline

Activity: 1988
Merit: 1048


aka tonikt


View Profile WWW
June 15, 2014, 07:04:35 PM
Last edit: June 15, 2014, 07:15:37 PM by piotr_n
 #2

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 Smiley

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
June 15, 2014, 07:14:50 PM
 #3

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

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
piotr_n
Legendary
*
Offline Offline

Activity: 1988
Merit: 1048


aka tonikt


View Profile WWW
June 15, 2014, 07:18:24 PM
 #4

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1005


Gerald Davis


View Profile
June 15, 2014, 09:30:22 PM
Last edit: June 15, 2014, 09:40:54 PM by DeathAndTaxes
 #5

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:
<Len_sig><sequence = 0x30><len_rs><integer = 0x02><len_r><r_value><integer 0x02><len_s><s_value><sighash>

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.



Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
June 16, 2014, 07:31:51 AM
 #6

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. 

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1000


View Profile
June 16, 2014, 08:15:39 AM
 #7

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
deepceleron
Legendary
*
Offline Offline

Activity: 1512
Merit: 1000



View Profile WWW
June 18, 2014, 03:47:18 AM
 #8

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):


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

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!