Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: TT on October 30, 2011, 07:05:16 AM

Title: Wallet Import Format
Post by: TT on October 30, 2011, 07:05:16 AM

Hi,

I've been trying to find some documentation on bitcoin ECDSA key formats, the exact specifications,
the reason for why the particular hash steps were chosen, the algorithm to verify whether keys are valid,
how the checksums work, etc...and have only been able to find little tidbits here and there but no nice
comprehensive document.

This article is pretty helpful: https://en.bitcoin.it/wiki/Address
I've managed to implement those exact steps and it works, even though I can see many developers who
haven't had a lot of experience working with crypto libraries tripping over certain details
(i.e., are the hashes on strings of hex digits? if so, is it case-sensitive? or are the hashes on binary numerical
formats? what about dealing with base64 encoding? should the base64 encoded string be hashed? or its
numerical value? etc...).

Not that this stuff is particularly difficult to grasp, but a concise description with rigorous steps
for generating/validating key pairs seems desperately needed.

Even worse, though, when looking up the private key specification, all I can find on the bitcoin wikis is
https://en.bitcoin.it/wiki/Private_key#Base_58_Wallet_Import_format

and
https://en.bitcoin.it/wiki/Wallet_import_format

which say almost nothing...

And the documentation on the mini private key format is even more lacking...and quite frankly doesn't
make sense to me from a security standpoint...after all, the whole point of having a long private key
is that it makes it difficult for an attacker to guess by brute-force. Having mini private keys seems to
defeat the whole purpose of this...or am I just missing some brilliant insight?

Could someone please point me to an exact set of steps for generating wallet import format base 58
privkey? And also, I'd love to understand the validation algorithms/checksums/etc...

If nobody has yet put together a good document on all this, I volunteer to write one and to make it
available for the bitcoin community.

Thanks.
- TT

Title: Re: Wallet Import Format
Post by: etotheipi on October 30, 2011, 01:40:46 PM

I have broken down the entire process from the bit level, to the application level, in an effort to write my own client. And it took me a while, but I eventually did figure out everything you seek to find, except for the mini private keys. And actually, Base58 private keys... I'm not sure how those are generated, but I do know how ECDSA works...

First of all, for BTC addresses, start with my post in the middle of this page: https://bitcointalk.org/index.php?topic=29416.0 (https://bitcointalk.org/index.php?topic=29416.0). The other two images on that page are useful for understanding BTC, but not as important. That image in the middle shows you exactly how to get from an ECDSA public key to a Base58 address. It's not trivial, but I've been able to recreate it from scratch on the first try with the aid of that diagram.

Second of all, a fellow forum goer "Lis" wrote this very useful, dependency-less ECDSA module in python: https://bitcointalk.org/index.php?topic=23241.0 (https://bitcointalk.org/index.php?topic=23241.0). I ended up using this in my code and it works beautifully. While I understand ECDSA, it would be a pain to reimplement it. FYI: a private key is just a 32-byte integer and a public key is two 32-byte integers cryptographically related to the private key. There's lots of different ways to encode these things, but in the end they are just big numbers.

Additionally, in that first link, you can see the "OP_CHECKSIG" diagram. That explains how you get from an unsigned transaction you just created, to a binary string that you can sign with your ECDSA key. It is stupidly complicated... but that's why I made these diagrams! :)

One of the big trip-ups in everything BTC related is the endianness. Most things are little-endian, except for three things: mainly whatever is in TxIn/TxOut scripts, the DER-encoded public key integers before they are converted to B58 addresses, and the final hash that you sign right at the end of the OP_CHECKSIG.

I'll be happy to answer any questions, or perhaps you will benefit from looking at the pybtcengine.py script in my github repo (look at the link in my signature). That python file has everything-- it allows you to supply raw numbers for pub/priv keys and verify linked transactions directly from the blockchain. I've spent a lot of time figuring this stuff out the past couple months. I hope I can help someone avoid the pain I went through! :)

EDIT: oh and to answer one of your questions directly: you only ever apply hashes to binary representations of data. Never on the hex or base58 representations. It must always be in binary and you must make sure the endian-ness is right for whatever you are hashing (usually little-endian, but in the case of tx-signing, big-endian)

Title: Re: Wallet Import Format
Post by: TT on November 02, 2011, 02:21:57 AM

Thank you! You're probably going to end up saving me a lot of time!
-TT

Title: Re: Wallet Import Format
Post by: TT on November 02, 2011, 02:31:05 AM

I understand the mathematics behind ECDSA for the most part. Same idea used in a lot of crypto: Find a representation for a cyclic group of known order for which it's relatively simple to compute powers but very difficult to compute the log. In the case of ECDSA, the representation is point multiplication on an elliptic curve.

What I still don't get well enough are the specific encodings. And most urgent for my current application is understanding the wallet import formats specifically.

-TT

Title: Re: Wallet Import Format
Post by: casascius on November 02, 2011, 02:32:16 AM

Look on the Wiki for "Base58Check".

Title: Re: Wallet Import Format
Post by: TT on November 02, 2011, 04:49:37 AM

AHHH!!!

So that's what steps 5-9 here are: https://en.bitcoin.it/wiki/Address

Thank you!

-TT

Title: Re: Wallet Import Format
Post by: TT on November 02, 2011, 05:51:03 AM

Everything in https://en.bitcoin.it/wiki/Base58Check (https://en.bitcoin.it/wiki/Base58Check) makes perfect sense except for:

Quote

"Base58Check encoding is also used for encoding private keys in the Wallet Import Format. This is formed exactly the same as a Bitcoin address, except that 0x80 is used for the version/application byte, and the payload is 32 bytes instead of 20 (a private key in Bitcoin is a single 32-byte unsigned big-endian integer)."

The output of RIPEMD160 will always be 20 bytes. Obviously, the private key format cannot be merely a hash. So what encoding for the Bitcoin private key should I use to generate the Base58Check? And what OpenSSL command can I use to get it?

Something like

Quote

openssl ecparam -genkey -name secp256k1 -out ecKey.pem

generates 160 characters of a base64 encoding, but I imagine this encoding also contains the curve parameters, initial point, etc...

So how do I get the 32-byte private key from this?

-TT

Title: Re: Wallet Import Format
Post by: casascius on November 02, 2011, 06:33:33 AM

Someone else wrote a shell script a while back that successfully generates bitcoin addresses using openssl. It was called "BOTG" or Bitcoins-Off-The-Grid.

It may have some imperfections (e.g. it throws out some keys and rolls the dice again if the keys don't fit certain convenient criteria, rather than trying to format them correctly) and is probably untested (any address generator should be rigorously tested to avoid possible risk of bad addresses and permanent LOSS of bitcoins) but it certainly serves as a good place to start.

https://bitcointalk.org/index.php?topic=23081.0

Title: Re: Wallet Import Format
Post by: TT on November 02, 2011, 09:35:50 AM

Wouldn't it just be better to dissect bitcoind, in that case? We know that that implementation seems to work pretty well. I'm pretty sure I could figure it out if I spent enough time poking into the innards of the OpenSSL library and certain source files like key.h, wallet.h, wallet.cpp, and all that...but I was hoping this stuff was already documented somewhere so I don't have to do that.

-TT

Title: Re: Wallet Import Format
Post by: TT on November 02, 2011, 09:40:46 AM

So this, huh?

Quote

hexsize=$(openssl ec -text -noout -in data.pem | head -5 | tail -3 | fmt -120 | sed 's/[: ]//g' )

while [ ${#hexsize} -ne 64 ]
do
openssl ecparam -genkey -name secp256k1 | tee data.pem &>/dev/null && hexsize=$(openssl ec -text -noout -in data.pem | head -5 | tail -3 | fmt -120 | sed 's/[: ]//g' )
done

openssl ec -text -noout -in data.pem | head -5 | tail -3 | fmt -120 | sed 's/[: ]//g'

Title: Re: Wallet Import Format
Post by: etotheipi on November 02, 2011, 12:12:53 PM

What is the goal here? Are we creating new keys? Trying to insert them into your wallet? Extract existing ones from your wallet? I can't help you with the openssl library, or PEM formats or anything. But I can offer you some code and diagrams that will help you figure out what's going on. The middle link of my signature has a diagram of the address-conversion process (halfway down the page), starting from the two 32-byte public-key integers and ending up at the final BTC address. It sounds like to me, that the private key format is very similar except you're skipping the top half of that diagram and using a full 32-byte repr of the private key, instead of a hash.

So a regular address looks like (where netbyte==0x00 for main network)

Code:

[NetByte  |  20-byte Hash  |  4-byte-hash-of-first-21-bytes]  ==> 25 bytes

Instead, the private key format would look like:

Code:

[0x80  |  32-byte private key (BE)  |  4-byte-hash-of-first-33-bytes] ==> 37 bytes

If it's anything like the address conversion, the private key will probably have to be big-endian before the hash is applied. My signature has a a link to PyBtcEngine which has a ton of great python tools for playing with this stuff (you can actually ignore all the C++ code, you only need pybtcengine.py (https://github.com/etotheipi/PyBtcEngine/blob/master/pybtcengine.py) and nothing else). Then you can do something like the following:

Python/PyBtcEngine Example code on gist (https://gist.github.com/1333473)

And here's the output of the above code:

Code:

Creating new address:
  BTC Address:      13KHLsKV1wVSFGAR7ohMWmvdEdcJsVdK52 (BinaryLE=19656185d9ba7af25bb8a3f3182833a39b79ae45)
  Have Public Key:  True
  Have Private Key: True
  Public Key Hex (Big-Endian):  
     04 869499bad9e3b4bf1c94dc772faf8a37d1182581697947b902e7d246dd7e7517
        9f6ffe719917b111f87253dda6c4beb31808bcfe45d1a6bd8272fd65f102258d
  Private key (integer): 89186423366759378937952085459266693389487184404252697411501348684075646220810
  Private key (hex, BE): c52dba0d191411cc7142da6979e47c8faa65ac9708f553c8fb6ce0517e4e7a0a
  Encoded privkey: 80c52dba0d191411cc7142da6979e47c8faa65ac9708f553c8fb6ce0517e4e7a0a4095c005
  Base58 privkey:  5KK8F9VQF6KMxDMgM1juEDd11XZXhLxVbeMb8hTPtt1bpV58diL

Recovering private key from base58 encoding:
  Valid checksum!
  Recovered address information:
  BTC Address:      13KHLsKV1wVSFGAR7ohMWmvdEdcJsVdK52 (BinaryLE=19656185d9ba7af25bb8a3f3182833a39b79ae45)
  Have Public Key:  True
  Have Private Key: True
  Public Key Hex (Big-Endian):  
     04 869499bad9e3b4bf1c94dc772faf8a37d1182581697947b902e7d246dd7e7517
        9f6ffe719917b111f87253dda6c4beb31808bcfe45d1a6bd8272fd65f102258d

Obviously, then you can examine what the python code is doing (just remember my hash256() == sha256(sha256())). Be aware, that the python random-number-generator is probably not the best PRNG to be using for real money, but it is perfectly sufficient for playing around. In any software I produce, I'll probably be making calls to the C++ cryptopp libraries to get random numbers. (you could also generate your own random 32-bytes offline (or integer less than 2^256), and then plug it in at the appropriate line above.

P.S. in the python code, I called the method "binary_to_addrStr" and "addrStr_to_binary" because I was expecting to only use it for address strings, but it works fine for private keys, too.

Title: Re: Wallet Import Format
Post by: TT on November 02, 2011, 01:52:30 PM

My only missing pieces are getting the correct encoding for the keys prior to that whole Base58Check thing. I've got both the pem stuff and the Base58Check thing down.

-TT

Title: Re: Wallet Import Format
Post by: etotheipi on November 02, 2011, 01:57:30 PM

Quote from: TT on November 02, 2011, 01:52:30 PM

My only missing pieces are getting the correct encoding for the keys prior to that whole Base58Check thing. I've got both the pem stuff and the Base58Check thing down.

-TT

If I understand correctly, doesn't the first half of my post cover that? Convert private key to 32-byte big-endian binary string. Prefix a 0x80 byte to it. Then double-sha256 and add the first 4 bytes of the result to the 0x80+PrivKey string.

I am not familiar with these import formats, but my experience with address strings and the description you provided makes me pretty confident that's what you're looking for (if it's not right try encoding the private-key in little-endian before hashing).

Title: Re: Wallet Import Format
Post by: casascius on November 02, 2011, 02:59:32 PM

Definitely big endian.

Must be unsigned. (OpenSSL may add a 0x00 byte to represent a positive sign for a total of 33 bytes and you must remove this)

Must be 32 bytes (OpenSSL may give you 31 bytes if the first byte was 0x00... Or 30 bytes if 0x00 twice... Etc. You must readd missing zero bytes.

Title: Re: Wallet Import Format
Post by: TT on November 03, 2011, 03:32:48 AM

Thanks, I think I got it. I'm still not sure why that bash script calls

Quote

openssl ec -text -noout -in data.pem | head -5 | tail -3 | fmt -120 | sed 's/[: ]//g'

multiple times...but it does seem to give me 32-byte or 33-byte output.

I guess it just ignores the 33-byte cases rather than removing the leading zero byte. But the output is in hex, so it doesn't really matter since leading zeros are ignored when I convert it into big-endian integers.

-TT

Title: Re: Wallet Import Format
Post by: TT on November 03, 2011, 07:36:02 AM

I got it!

Thank you very much, you guys!

I appreciate the help.

-TT

Title: Re: Wallet Import Format
Post by: pointbiz on November 05, 2011, 02:31:30 AM

so, where's the new doc? I struggled with this too initially :D

Title: Re: Wallet Import Format
Post by: TT on November 05, 2011, 11:25:50 AM

Patience 8)

Title: Re: Wallet Import Format
Post by: TT on November 13, 2011, 05:20:14 AM

I think the wiki base58Check article https://en.bitcoin.it/wiki/Base58Check_encoding (https://en.bitcoin.it/wiki/Base58Check_encoding) covered it pretty well...but I'll sum up:

1) Add the version byte as the most significant byte to the data
2) Compute checksum = sha256(sha256(data))
3) Take the first four bytes of checksum, append them to the end of data
4) Convert to base58
5) Pad with necessary leading zeros (represented with 1's in base58)

And yes, etotheipi, you did cover a lot of the details. It's nice to see the steps summed up succinctly, though :)
Endianness is as you say...little endian for this part of the process.

-TT

php code that does the above:

Quote

function hexToBase58Check($version, $payload, $length, $padding) {
   // prepend version
   $data = $version . $payload;

   // compute checksum
   $checksum = hash("sha256", hex2str($data));
   $checksum = hash("sha256", hex2str($checksum));
   $checksum = substr( $checksum, 0, 8 );

   // append checksum
   $data .= $checksum;
   return str_pad(bcdec58(bchexdec($data)), $length, $padding, STR_PAD_LEFT);
}

Title: Re: Wallet Import Format
Post by: TT on November 13, 2011, 05:24:19 AM

Better documentation is pending further research. Unfortunately, this stuff doesn't pay my bills...yet.

-TT

Title: Re: Wallet Import Format
Post by: TT on November 13, 2011, 05:39:06 AM

As for ECDSA key generation, the following OpenSSL commands work, which I got from that bitcoin-off-the-grid link casascius gave:

#To generate the key and save it to the file ecKey.pem:
openssl ecparam -genkey -name secp256k1 -out ecKey.pem

#To pull out a 32-byte private key as hex:
openssl ec -text -noout -in ecKey.pem | head -5 | tail -3 | fmt -120 | sed 's/[: ]//g'

#To get ripemd160(sha256(public key)), which is what bitcoin uses for addresses, as hex:
openssl ec -in ecKey.pem -pubout -outform DER | tail -c 65 | openssl dgst -sha256 -binary | openssl dgst -rmd160 -binary | xxd -p -c 80

There's surely a more efficient method for performing these steps, but they seem to do the trick for now. Perhaps
later I'll document usage of the OpenSSL API from within a single process, to avoid the overhead of starting additional processes.

Once you have the 32-private key and the 20-byte hash of the public key, apply the base58Check steps to them.

-TT

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 06:21:16 AM

OK, I have the following raw data:

Quote

Private key: 24ed089647b7f330588c491309e527c44cbf5e04444540782d6b88f8c44b3105 length: 64
Public key hash: 211f0c809a1a14f46af53ae59aa32d02aaf72724 length: 40
------------------------
Wallet import format: 5J6YocBZpn5j9hcPWv1wPEGtfXvHP8g2ZPSSTrjgr9PxUhALeYM length: 51
Address: 1428VeCoiJR81vVjdtXe9sb5G15qjYyLwo length: 34

PrevTx - Raw Data
-----------------
0100000001e1877fe168c04e1f91a170c37320d8d6e6dbac94cb1edf56eab2d075f548cb9300000 0008c493046022100b0ac6689455d95fb81f0012f38b9285d44ae75f64b4c82ea9d1e96c2541392 7c022100bcf31e15dde4d83b567f848cf6b4a708a23f0a71a206d858bfaea0285fca350f014104c 6420d1b499b277a1f4e284cb4bc4cc327539adfc24bc6fd212577af5665395886660c9777484448 745868e8e5c5159d34c929706941e941f9de2fa6a18817f4ffffffff023000c901000000001976a 9145d9536d605d7ddf4f51f57006d1dddc38bb3f79c88ac80969800000000001976a914211f0c80 9a1a14f46af53ae59aa32d02aaf7272488ac00000000

PrevTx - Human Readable
-----------------------
Hash: e52fa8a693eaff60f644b5006798215e0798e54a2dfc82aaec045c99cf70e4fb
Data format version: 1
Input 0 - 1LL8GeU5AxAhG7NuopgSrfeKCnzz46AaGM
Previous out: 93cb48f575d0b2ea56df1ecb94acdbe6d6d82073c370a1911f4ec068e17f87e1#0
scriptSig: 493046022100b0ac6689455d95fb81f0012f38b9285d44ae75f64b4c82ea9d1e96c25413927c022 100bcf31e15dde4d83b567f848cf6b4a708a23f0a71a206d858bfaea0285fca350f014104c6420d 1b499b277a1f4e284cb4bc4cc327539adfc24bc6fd212577af5665395886660c977748444874586 8e8e5c5159d34c929706941e941f9de2fa6a18817f4
sequence: 0xffffffff
Output 0 - 19XpbRe7XRT2c9FKGP6jTwcbjVwyyGBKiS
Value: 0.29950000
scriptPubKey: 76a9145d9536d605d7ddf4f51f57006d1dddc38bb3f79c88ac
Output 1 - 1428VeCoiJR81vVjdtXe9sb5G15qjYyLwo
Value: 0.10000000
scriptPubKey: 76a914211f0c809a1a14f46af53ae59aa32d02aaf7272488ac

NewTx - Raw Data
----------------
0100000001fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe501000 0008b48304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03 022100d0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2a30141043ef 1593aa79bab3c6a21f4f82f348b12e68d107f95f577e610466aca7d0f2e4ebcfd9a9bafcad72076 18ec4e5e78358dbac3dff4a432b833bf8a9cee85834ac0ffffffff0180969800000000001976a91 48073e789954e05c5938c5cc493308f9021539bb588ac00000000

NewTx - Human Readable
----------------------
Hash: 460fcfa566eaf7906cf7768f22d624c4f2e8dc1ba00474b497ad7bbacd696f14
Data format version: 1
Input 0 - 1428VeCoiJR81vVjdtXe9sb5G15qjYyLwo
Previous out: e52fa8a693eaff60f644b5006798215e0798e54a2dfc82aaec045c99cf70e4fb#1
scriptSig: 48304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e0302210 0d0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2a30141043ef1593a a79bab3c6a21f4f82f348b12e68d107f95f577e610466aca7d0f2e4ebcfd9a9bafcad7207618ec4 e5e78358dbac3dff4a432b833bf8a9cee85834ac0
sequence: 0xffffffff
Output 0 - 1CiCLjhX1291hwjxZxBNCq1k9Ptkb4YNgR
Value: 0.10000000
scriptPubKey: 76a9148073e789954e05c5938c5cc493308f9021539bb588ac

Can you show me exactly what needs to be hashed and signed to generate the signature?

-TT

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 06:36:25 AM

Specifically, I couldn't find the hash type and wasn't sure what to enter for the hash type code. where is the hashtype byte? and what 4 bytes do I need to enter for the code? and do these 4 bytes need to be big-endian? or little-endian?

-TT

Title: Re: Wallet Import Format
Post by: etotheipi on November 16, 2011, 01:35:53 PM

Sorry to break the news to you: but you're asking about OP_CHECKSIG which is really complicated. But, see my post here (https://bitcointalk.org/index.php?topic=29416.0) for a description of how it works (about halfway down the page). It tells you exactly how to construct the string to be signed.

And everything should be in little-endian unless otherwise stated, including the hashcode. Just make sure the final hash is big-endian before signing. Yeah, it's ridiculous...that's why I made this diagram!

-Eto

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 04:45:00 PM

Right, I saw your diagram. I think I get all of it except for the hashTypeCode.

So NewTx broken down looks like:

NewTx
-----
01000000 <---version (big endian)
01 <----tx_in count

fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe5 <-PrevTx hash (big endian)
01000000 <------ index (big endian)

8b <----- scriptSig length (139 bytes = 2 opcodes + 72 for sig + 65 for pubKey)
48 <---- push the next 72 bytes onto stack OpCode
304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03022100d 0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2a301 <---- 72 bytes (sig)
41 <----- push the next 65 bytes onto stack OpCode
043ef1593aa79bab3c6a21f4f82f348b12e68d107f95f577e610466aca7d0f2e4ebcfd9a9bafcad 7207618ec4e5e78358dbac3dff4a432b833bf8a9cee85834ac0 <---- 65 bytes (pubKey)

ffffffff <------sequence
01 <----- tx_out count
8096980000000000 <------- value (big-endian)
19 <--- pk_script length (25 bytes)
76a9148073e789954e05c5938c5cc493308f9021539bb588ac <---- pk_script
00000000 <----- lock time

.....
so where exactly is the hashTypeCode?

-TT

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 04:47:11 PM

The signature is:

304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03022100d 0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2 <--- 70 bytes

a301 <---- two additional bytes. what hashTypeCode does this correspond to and
how do we expand it to 4 bytes?

Or am I missing something?

Title: Re: Wallet Import Format
Post by: etotheipi on November 16, 2011, 04:50:36 PM

Quote from: TT on November 16, 2011, 04:45:00 PM

so where exactly is the hashTypeCode?

It's the very last byte of the 72-byte signature (bolded below):

304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03022100d 0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2a301

Expand that 0x01 to four bytes, little-endian, and attach it to the modified, serialized txCopy before signing.

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 05:12:51 PM

OK,

So we have:

01000000 <-----NewTx up to before sigScript
01
fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe5
01000000

76a914211f0c809a1a14f46af53ae59aa32d02aaf7272488ac <----- pkScript for PrevTx

00000000 <---- lock time for NewTx

00000001 <---- expanded hashTypeCode (little-endian)

.....
so all together, now:
0100000001fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe501000 00076a914211f0c809a1a14f46af53ae59aa32d02aaf7272488ac0000000000000001

and so this is what gets signed?

I tried signing sha256^2 of it using the private key
24ed089647b7f330588c491309e527c44cbf5e04444540782d6b88f8c44b3105
and got:

304302200a4637d31ac9f9edceeeb3b1095e79e48a49b4048f9177030659f8ae560521f9021f0bf 8515fc5ea6a51c1a8d9c809f7cc62d9914a1c5152947dccd5155c3b52e7

but the signature should be:
304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03022100d 0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2

also, what's with the extra a3 byte before the hashTypeCode?

-TT

Title: Re: Wallet Import Format
Post by: etotheipi on November 16, 2011, 05:23:10 PM

Quote from: TT on November 16, 2011, 05:12:51 PM

OK,

So we have:

01000000 <-----NewTx up to before sigScript
01
fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe5
01000000

76a914211f0c809a1a14f46af53ae59aa32d02aaf7272488ac <----- pkScript for PrevTx

00000000 <---- lock time for NewTx

00000001 <---- expanded hashTypeCode (little-endian)

.....
so all together, now:
0100000001fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe501000 00076a914211f0c809a1a14f46af53ae59aa32d02aaf7272488ac0000000000000001

and so this is what gets signed?

I tried signing it using the private key
24ed089647b7f330588c491309e527c44cbf5e04444540782d6b88f8c44b3105
and got:

304302200a4637d31ac9f9edceeeb3b1095e79e48a49b4048f9177030659f8ae560521f9021f0bf 8515fc5ea6a51c1a8d9c809f7cc62d9914a1c5152947dccd5155c3b52e7

but the signature should be:
304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03022100d 0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2

also, what's with the extra a3 byte before the hashTypeCode?

-TT

I'm at work, and don't have my python/btc tools here, but from manual inspection that a3 appears to be part of the signature. The signature is represented as an r and s value, and in this case the s-value is actually 33 bytes, not 32. I haven't counted it all up, but I could see how that would lead you to believe there's an extra byte (if you look at the s-value, you'll notice it's actually 32-bytes, but has an extra 0x00 leading byte to remove sign ambiguity).

As for signing: don't forget that the process for generating a signature involves a random number. Every signature you generate on the exact same data will produce a completely different-looking signature. The only way to know for sure whether you did it right is if you used the same random number both times, or (more likely) execute your verification algorithm to check if the signature is valid.

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 05:35:13 PM

Oh, right...I forgot about that random number.

So it's impossible to generate an exact tx that is identical...you can only verify that the signature is valid...

Would you happen to know how I can verify an ECDSA signature using openssl from the command line?

-TT

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 10:10:40 PM

OK, I've managed to get the OpenSSL library working in C...I can generate an ECDSA signature and verify it.

However, it is telling me that this particular signature for this particular example is invalid.

Can we go over the steps?

NewTx - Raw Data
----------------
0100000001fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe501000 000

8b48304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03022 100d0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2a30141043ef159 3aa79bab3c6a21f4f82f348b12e68d107f95f577e610466aca7d0f2e4ebcfd9a9bafcad7207618e c4e5e78358dbac3dff4a432b833bf8a9cee85834ac0

ffffffff0180969800000000001976a91 48073e789954e05c5938c5cc493308f9021539bb588ac00000000

NewTx - scriptSig removed
------------------------------
0100000001fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe501000 000
ffffffff0180969800000000001976a91 48073e789954e05c5938c5cc493308f9021539bb588ac00000000

PrevTx - scriptPubKey
------------------------
76a914211f0c809a1a14f46af53ae59aa32d02aaf7272488ac

NewTx scriptSig replaced by PrevTx scriptPubKey and hashTypeCode appended
------------------------------------------------------
0100000001fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe501000 000
76a914211f0c809a1a14f46af53ae59aa32d02aaf7272488ac
ffffffff0180969800000000001976a91 48073e789954e05c5938c5cc493308f9021539bb588ac00000000
00000001

NewTx sig
------------
304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03022100d 0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2a3

key.pem
------------
-----BEGIN EC PARAMETERS-----
BgUrgQQACg==
-----END EC PARAMETERS-----
-----BEGIN EC PRIVATE KEY-----
MHQCAQEEICTtCJZHt/MwWIxJEwnlJ8RMv14EREVAeC1riPjESzEFoAcGBSuBBAAK
oUQDQgAEPvFZOqebqzxqIfT4LzSLEuaNEH+V9XfmEEZqyn0PLk68/Zqbr8rXIHYY
7E5eeDWNusPf9KQyuDO/ipzuhYNKwA==
-----END EC PRIVATE KEY-----

Now in principle, as long as the signature was in fact generated with the key above, sig should be valid for sha256^2(NewTx with scriptSig replaced by PrevTx scriptPubKey and hashTypeCode appended), correct?

-TT

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 10:27:23 PM

You can check that the private key I'm using does in fact match the bitcoin address for the scriptPubKey here:

https://bitcointools.appspot.com/?k=5J6YocBZpn5j9hcPWv1wPEGtfXvHP8g2ZPSSTrjgr9PxUhALeYM

I've tried verifying the hash in both big endian and little endian and neither worked. What am I still missing?

Title: Re: Wallet Import Format
Post by: etotheipi on November 16, 2011, 10:27:43 PM

There's a lot of data there, so it's tough for me to parse all of it by eye. But it looks like you're appending a big-endian hashcode instead of little-endian. Also, try switching the endianness after the sha256^2 operation. You might have to do some guess-and-check for this part.

Also don't forget to add the 1-byte hashcode to the end of the signature you generated. It may not be relevant for OpenSSL, but if you're signing transactions to be put in the blockchain, you'll need that 0x01 byte at the end of the pubkey script.

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 10:32:55 PM

I tried appending 00000001 and 01000000,
I tried verifying the data in both endiannesses.
None of the combinations work.

-TT

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 10:34:39 PM

It's easier to see the data when you compare it to:
https://bitcointalk.org/index.php?topic=50330.msg620292#msg620292

Title: Re: Wallet Import Format
Post by: etotheipi on November 16, 2011, 10:38:30 PM

I don't know if it helps at all, but here's my python code for verifying signatures (which is the same for signing up until step 10). Default output for all numbers/values is little-endian. The "binary_switchEndian" call at the end converts the hash to big-endian just before signing.

You can double-check your process against this, as this method is works reliably on real data from the blockchain.

Code:

def checkSig(self, binSig, binPubKey, txOutScript, txInTx, txInIndex, stack, lastOpCodeSep=None):
      # 1. Pop key and sig from the stack 
      binPubKey = stack.pop()
      binSig    = stack.pop()

      # 2. Subscript is from latest OP_CODESEPARATOR until end... if DNE, use whole script
      subscript = txOutScript
      if lastOpCodeSep:
         subscript = subscript[lastOpCodeSep:]
      
      # 3. Signature is deleted from subscript
      #    I'm not sure why this line is necessary - maybe for non-standard scripts?
      lengthInBinary = int_to_binary(len(binSig))
      subscript = subscript.replace( lengthInBinary + binSig, "")

      # 4. Hashtype is popped and stored
      hashtype = binary_to_int(binSig[-1])
      justSig = binSig[:-1]

       # 5. Make a copy of the transaction -- we will be hashing a modified version
      txCopy = PyTx().unserialize( txInTx.serialize() )

      # 6. Remove all OP_CODESEPARATORs
      subscript.replace( int_to_binary(OP_CODESEPARATOR), '')

      # 7. All the TxIn scripts in the copy are blanked (set to empty string)
      for txin in txCopy.inputs:
         txin.binScript = ''

      # 8. Script for the current input in the copy is set to subscript
      txCopy.inputs[txInIndex].binScript = subscript

      # 9. Prepare the signature and public key
      senderAddr = PyBtcAddress().createFromPublicKey(binPubKey)
      binHashCode = int_to_binary(hashtype, widthBytes=4)
      toHash = txCopy.serialize() + binHashCode

      hashToVerify = hash256(toHash)
      hashToVerify = binary_switchEndian(hashToVerify)

      # 10. Apply ECDSA signature verification
      return senderAddr.verifyDERSignature(hashToVerify, justSig)

Title: Re: Wallet Import Format
Post by: TT on November 16, 2011, 10:47:11 PM

Thanks,

I appreciate all the help.

I'm really close.

Title: Re: Wallet Import Format
Post by: TT on November 17, 2011, 05:51:49 AM

Hmmm...still missing something.

Would it be possible to tell me exactly what the data needs to look like before the hash + verify are performed for my specific example? Unfortunately, the example given at https://en.bitcoin.it/wiki/OP_CHECKSIG is for a transaction involving generated bitcoin.

PrevTx - Raw Data
-----------------
0100000001e1877fe168c04e1f91a170c37320d8d6e6dbac94cb1edf56eab2d075f548cb9300000 0008c493046022100b0ac6689455d95fb81f0012f38b9285d44ae75f64b4c82ea9d1e96c2541392 7c022100bcf31e15dde4d83b567f848cf6b4a708a23f0a71a206d858bfaea0285fca350f014104c 6420d1b499b277a1f4e284cb4bc4cc327539adfc24bc6fd212577af5665395886660c9777484448 745868e8e5c5159d34c929706941e941f9de2fa6a18817f4ffffffff023000c901000000001976a 9145d9536d605d7ddf4f51f57006d1dddc38bb3f79c88ac80969800000000001976a914211f0c80 9a1a14f46af53ae59aa32d02aaf7272488ac00000000

NewTx - Raw Data
----------------
0100000001fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe501000 0008b48304502205ea291ce55ecc95f346f6be2c198993dcb1a72cc4eddf520f173ed9ac85a1e03 022100d0ae6c394d014de8fecb44d034904a0c6142e6335a394aa4629d7a839aaaa2a30141043ef 1593aa79bab3c6a21f4f82f348b12e68d107f95f577e610466aca7d0f2e4ebcfd9a9bafcad72076 18ec4e5e78358dbac3dff4a432b833bf8a9cee85834ac0ffffffff0180969800000000001976a91 48073e789954e05c5938c5cc493308f9021539bb588ac00000000

String to verify = ????

Title: Re: Wallet Import Format
Post by: TT on November 17, 2011, 06:00:01 AM

Also, I was wondering in your diagram what SCRIPT_PART4 refers to? is that a nonstandard transaction type? or am I really completely lost? all the scripts I've seen so far end with OP_CHECKSIG

Title: Re: Wallet Import Format
Post by: etotheipi on November 17, 2011, 06:07:32 AM

Quote from: TT on November 17, 2011, 06:00:01 AM

Also, I was wondering in your diagram what SCRIPT_PART4 refers to? is that a nonstandard transaction type? or am I really completely lost? all the scripts I've seen so far end with OP_CHECKSIG

My diagram is showing an arbitrarily complex script, which would definitely not be standard. In fact, we were just having a conversation on IRC about how we're not even sure if OP_CODESEPARATOR scripts can actually be useful in any application (I'm sure there is, we just couldn't think of it)! For your purposes, you can ignore everything in subscript except for that chunk of standard TxOut script:

Code:

OP_DUP OP_HASH160 <ADDR> OP_EQUALVERIFY OP_CHECKSIG

If that's all I put in the diagram, then steps 2-4 would do nothing since they have no effect on standard scripts. I figured that was too boring, so that's why I added the other stuff.

I am really busy right now, but if you haven't solved your problem by Friday I'll dig in a bit to see if I can help. Good luck!

Title: Re: Wallet Import Format
Post by: TT on November 17, 2011, 06:44:24 AM

I got it!!!!

I ended up adding a bunch of tracers into the satoshi client to give me hex dumps of stuff so I would have some concrete examples to work with.

Thanks for all the help. I'm sure I'll have other issues later on, though :)

Title: Re: Wallet Import Format
Post by: TT on November 17, 2011, 12:53:56 PM

In case anyone's interested in the hex dump of the data to be hashed in the above example, it's

0100000001fbe470cf995c04ecaa82fc2d4ae598075e21986700b544f660ffea93a6a82fe501000 0001976a914211f0c809a1a14f46af53ae59aa32d02aaf7272488acffffffff0180969800000000 001976a9148073e789954e05c5938c5cc493308f9021539bb588ac0000000001000000

Title: Re: Wallet Import Format
Post by: hashman on November 21, 2011, 02:13:44 PM

Thanks for your work here !

I'm still waiting for somebody to put together a nice RFC to describe these things.. does that seem a possibility for the future?

Title: Re: Wallet Import Format
Post by: TT on November 24, 2011, 02:49:06 AM

Man, it's so frickin' hard to find good OpenSSL library documentation... :(

It's a little frustrating.

Would anyone happen to know how to create an ECDSA key using only the 32-byte private key format rather than the 279 byte DER format?

For the 279 byte DER format, I know you can do something like:

Quote

EC_KEY* pKey;
d2i_ECPrivateKey(&pKey, &privateKey, privateKeyLength);

But this only seems to work for the 279 byte DER form for the private key.

I'd like to know what sequence of calls to the OpenSSL library to use to get the full 279 byte DER private key from a 32-byte private key...as, for instance, https://bitcointools.appspot.com/ (https://bitcointools.appspot.com/) can do.

Thanks.

-TT

Title: Re: Wallet Import Format
Post by: TT on November 24, 2011, 08:33:05 PM

Ah, I got it!

It's all in the key.h source that's part of the satoshi client.
https://github.com/bitcoin/bitcoin/blob/master/src/key.h (https://github.com/bitcoin/bitcoin/blob/master/src/key.h)

CKey::GetPrivKey and CKey::SetPrivKey are accessor methods for the 279-byte DES private key.
CKey::GetSecret and CKey::SetSecret are accessor methods for the 32-byte private key.

Those of you who are interested in the OpenSSL calls needed, it's all spelled out in key.h

-TT

Title: Re: Wallet Import Format
Post by: casascius on November 26, 2011, 01:52:48 AM

Quote from: TT on November 24, 2011, 02:49:06 AM

Would anyone happen to know how to create an ECDSA key using only the 32-byte private key format rather than the 279 byte DER format?

Sure, just pick a random 32-byte number.

Nearly all 32-byte numbers are valid private keys. The ones that aren't valid as private keys all start with a large number (at least forty-eight) of zero bits, or a large number of one bits, all in a row. At random, the likelihood of hitting them is so low as to be ignorable.