Wallet Import Format

[TT]

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

[etotheipi]

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

[TT]

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

[TT]

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

[casascius]

Look on the Wiki for "Base58Check".

[TT]

AHHH!!!

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

Thank you!

-TT

[TT]

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

"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

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

[casascius]

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

[TT]

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

[TT]

So this, huh?

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'

[etotheipi]

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 and nothing else).  Then you can do something like the following:

Python/PyBtcEngine Example code on gist

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.

[TT]

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

[etotheipi]

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

[casascius]

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.

[TT]

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

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

[TT]

I got it!

Thank you very much, you guys!

I appreciate the help.

-TT

[pointbiz]

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

[TT]

Patience 

[TT]

I think the wiki base58Check article 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:

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);
}

[TT]

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

-TT