What process do you use to generate an address from a private key?
You use computer software to do it, because the math involved is tedious and time consuming. A computer can do such repetitive tasks quite quickly, but you wouldn't want to do it by hand with paper and pencil.
Specifically:
Start with identifying the curve being used and the base point of prime order on the curve.
In the case of Bitcoin, the curve is the Secp256k1 curve.
This is the curve described by the function:
y
2 = x
3 + ax + b
Where:
a=0 and b=7
In the case of Bitcoin, the base point is the point on the curve with the (x,y) coordinates of:
(881060208356437498713259502322696549220009655260441506808002997766225867667840, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
Next, perform elliptic curve point multiplication multiplying the base point by the private key scalar.
Elliptic curve multiplication in this case is the process of repeatedly adding the base point, so if your private key is 3, then your public key would be determined by adding the base point 3 times. The process of point addition is defined as taking two points along the curve and computing where a line through them intersects the curve. The negative of the intersection point is used as the result of the addition
Obviously if you are adding a point to itself, then you only have 1 point on the line for the first calculation. The process of adding a point to itself (point doubling) is defined as taking the tangent of the point on the curve and computing where the tangent line intersects the curve.
Since private keys are extremely large numbers, it would take a prohibitively long time to just add the base point repeatedly to the result of each calculation that many times. Instead elliptic curve point multiplication has a shortcut. You can repeatedly double, to get through many iterations very quickly, and then add to these larger results as needed to reach the appropriate number of iterations. For example, if the private key was 100, you could do the find the public key in 8 operations (rather than 100 individual additions):
If the base point is G and the private key is 100...
double G to get 2 X G
add G to get 3 X G
double 3 X G to get 6 X G
double 6 X G to get 12 X G
double 12 X G to get 24 X G
add G to get 25 X G
double 25 X G to get 50 X G
double 50 X G to get 100 X G
The process for figuring out when to double and when to add can be described with the following process:
Start with the private key as the "number of remaining additions".
- If the number of remaining additions is even, then write down a "D" (to represent "Double"). If the number of remaining additions is odd, then write down "A" (to represent "Add")
- If the point was odd, (and you therefore wrote an "A") then subtract 1 from the number of remaining additions
- If the point was even, (and you therefore wrote a "D") then divide the number of remaining additions in half
- Repeat this process until the number of remaining additions is 1
Now, you can step through the list you wrote down in reverse, doubling or adding as indicated. We can see this with our example of 100:
100 is even (D)
50 is even (D)
25 is odd (A)
24 is even (D)
12 is even (D)
6 is even (D)
3 is odd (A)
2 is even (D)
In reverse we get the instructions we saw earlier: Double, Add, Double, Double, Double, Add, Double, Double.
When you complete your elliptic curve point multiplication,
the resulting point is your public key.
Next you need to calculate the SHA-256 hash of your public key. I'm sorry, but I'm not going to try and walk you through that mathematics. You can read about it here:
http://en.wikipedia.org/wiki/SHA-256The result will be a 256 bit number.
Next you take a RIPEMD-160 hash of the result of the SHA-256 hash. I'm sorry, but I'm not going to try and walk you through that mathematics. You can read about it here:
http://en.wikipedia.org/wiki/RIPEMD-160The result will be a 160 bit number.
The result of this hash is what is actually used in the transactions and blockchain to represent where the bitcoins are "sent to". Bitcoin addresses are we know them are not stored in the blockchain at all. They are this 160 bit number with a checksum (to help wallets catch a typo so you don't accidentally send to the wrong RIPEMD-160 hash), and a version number and then converted from a 160 bit binary number to a form of base58 (so you only need to type, write, print, or display 34 alphanumeric characters instead of 160 ones and zeros).
To add the version number, just put 8 zeros on the front of the 160 bit binary number.
To calculate the checksum:
- Calculate a SHA-256 hash of the RIPEMD-160 hash result
- Calculate a SHA-256 hash of this SHA-256 hash result
- Take the first 32 ones and zeros from this SHA-256 hash result
Append these 32 ones and zeros to the end of the RIPEMD-160 160 bit binary number.
The leading character '1', which has a value of zero in base58, is reserved for representing an entire leading zero byte, as when it is in a leading position, has no value as a base-58 symbol. There can be one or more leading '1's when necessary to represent one or more leading zero bytes. Count the number of leading zero bytes. Each leading zero byte shall be represented by its own character '1' in the final result.
Now,
to get the bitcoin address, convert the rest of the 200 bit binary number to base58 using the representation defined here:
