Tutorial - Address Generation
In this tutorial, we’ll be creating our own Bitcoin addresses in Ruby. The easy way uses the bitcoin-ruby gem, but this doesn’t teach us much; so we’ll do it ourselves using only basic hashing and an elliptic curve cryptography libraries.
Some high level notes:
We have 3 main components:
- Private keys
- Lets you sign new transactions, thereby spending your bitcoins.
- 256 random bits
- Public Keys
- Proves that you own bitcoins associated with a certain address
- An elliptic curve public key of the above private key
- Public Address
- Give this to people, so that they can send you bitcoins.
- Hash of the public key
- Private keys
The private key deterministically generates the public key, which deterministically generates the public address (the same private key will always generate the same public key and public address).
These “generation” functions involve one-way functions (once you perform the function, you can’t go back and determine the inputs). It’s practically impossible to get the public key from a public address, or a private key from a public key.
Compressed public keys are now widely used amongst the most popular bitcoin software. The public address of a compressed public key is different than the public address of the uncompressed public key.
Disclaimer: I am not a cryptographer, this is for academic experimentation only.
I’ve used some helper functions for common conversions (hex converters, string converters, base58 encoding). This utility file can be downloaded here.
Step 1. Generate 256 random bits.
You can get this from /dev/urandom, flip a coin 256 times, roll a 16-sided dice 64 times, point a webcam at your lavalamp, etc, but here, we’ll just take a hash of a simple phrase. Bear in mind that the elliptic curve is defined over a prime field, so our private key must be less than our chosen prime.
Note: Did I mention that this implementation should only be accepted as academic experimentation? Scammers have already generate addresses based on common words/phrases and steal any bitcoins that get sent to those addresses.
Just to be clear, the private key can be exressed in multiple ways:
- Binary: 1001111001010010010011011110010001111000100101110000101010010110001000011100000011100101001010001001000010000000010111010101111100101000111000110110001000001000100100101011101001101011111110100111000000011011000000100110110001101110111000010000101001010010
- Integer: 71610849129504069670807627525562295685404995395280754758942009276479161043538
- Hex: 9e524de478970a9621c0e52890805d5f28e3620892ba6bfa701b026c6ee10a52
These are merely different representations of the same thing, and are all equivalent. As we proceed, we’ll need to jump around different representations depending on what we’re doing. Don’t be alarmed.
We could actually stop here. These 256 random bits ARE your private key, but if you want to use this key with any mainstream bitcoin application, the private key must be in wallet import format (WIF format). To do that:
Step 2. Prepend version, append compression flag
The version number depends on the network.
- Bitcoin = 0x80
- Testnet = 0xEF (Testnet is a “bitcoin playground” where developers can test their applications against a live, bitcoin-like network where coins have no value)
Compression Flag = 0x01
Note: Compression flag is needed to make private keys completely deterministic. As stated above, compressed and uncompressed public keys generate different public addresses. The compression flag signals which of those addresses this private key should generate.
Step 3. Add checksum
Checksum is the first 4 bytes of the double sha256 hash of our input. It is used to ensure that every bit is correct; if a single bit is off (mistyped), we will know about it.
Step 4. Base58 Encoding
We currently have 38 bytes of data. Using the digits 0-9. we can express this data as a 92 digit long integer. Using hex (16 possible characters) we express this in 76 characters (as shown above). If we use 58 possible characters, the data can be expressed in only 52 characters. The characters used for Base58 are:
a-z except ‘l’ (25)
A-Z except ‘I’,’O’ (24)
I’ve included the bitcoin-ruby base58 encoder here.
Step 5. Evaluate:
This is where Elliptic Curve Cryptography comes in. I’ll go into how this all works in a later post, but for now, we’ll simply use this equation.
= 77 digit long integer that we generated in step 1.
G = the “generator point”, a special point on the elliptic curve
- It has x coordinate: 55066263022277343669578718895168534326250603453777594175500187360389116729240
- and y coordinate: 32670510020758816978083085130507043184471273380659243275938904335757337482424
When we multiply the generator point with our private key, we get a new point on the elliptic curve. The x and y cooordinates of this point act as our public key. Because you can’t easily divide points on an elliptic curve, it’s computationally impractical to generate the private key given our knowledge of the public key and the generator point.
Note: Bitcoin uses the “secp256k1” curve, which defines it’s own generator point. Every application which uses the secp256k1 curve uses the same generator point.
Note: We’re using the “ecdsa gem” because the OpenSSL library is poorly documented and confusing. Explanation here.
Step 6. Compress
Because elliptic curves are symmetric about the x axis; given any x coordinate, there exist only 2 possibilities for the y coordinate. Uncompressed public keys include the full y coordinate (a really big number), but we can save space on the blockchain by indicating which of the 2 possible y-coordinates we use.
If the y coordinate is even, public keys have the form:
- 0x02 + x coordinate
If y coordinate is odd:
- 0x03 + x coordinate
Why must the 2 y coordinates have unique parity? Because the elliptic curve is over a prime finite field, when we change sign, we flip parity. Illustrated simply, 5 modulus 7 = 5 is odd, but -5 modulus 7 = 2, which is even.
We now have our public key.
Step 7. Hash public key
Next, we hash the public key. This compresses our key from 256 bits to 160 bits.
Step 8. Prepend version, append checksum
The version number depends on the network, and is different than the version used in step 2.
- Bitcoin = 0x00
- Testnet = 0x6F
Checksum is computed the same way it was in step 3.
Step 9. Base58 Encode.
We can now share this address with our friends, convert it to a QR code, get it tatooed on our bodies, and watch the bitcoins rush in.
Download the code here.
- Andreas Antonopoulos on Bitcoin Wallet Encryption | youtube.com
- Elliptic Curve Crtyptography | wikipedia.org
- Introducing Ruby ECDSA Gem | davidgrayson.com
- Ruby ECDSA | github.com
- Why does Bitcoin use 2 hash functions? | stackexchange.com
- List of Address Prefixes | bitcoin.it
- Technical Background of Bitcoin Addresses