How Bitcoin Addresses are Generated
This thread will only cover P2PKH address i.e. the bitcoin address starting with '1', also known as Legacy Address. I will create another thread in future about how to create P2SH or Bech32 addresses.
Ok! So let's start with the topic. To use Bitcoin, user generally needs two things: Private Key and Bitcoin Address. Bitcoin Address is an identifier which looks like this: 18J6ai34uzGofUuzbiwhXJzKzdx1efDBqA. User have to share it with sender to receive payment. Whereas private key is a key which user have to input in wallet to access the funds received.
You may be already knowing what I have just said above. But did you ever wonder how these pair of keys are generated? Let's dive deep into topic and create our own code for generating key pair. The main and the most important component of Bitcoin Address is Private Key. Let's discuss it first:
Private Key
In simple words, anything can be private key if it fulfills two conditions. Condition one, it must not be 0. Second, it must be lower than the value of
N defined by SECG for secp256k1 curve. However, the value of N is very, very large so practically every 256-bits number is valid private key.
Now the question arises how to generate private key. As I said in the starting that anything can be private key. For example, this string: "I am a string to generate private key" can be converted into private key. All you have to do is, to convert this string into 256-bits value and check if it is lower than the
N.
But is it suggested to generate private key this way? Actually no! It is popular saying that human is the worst random generator. If we use custom strings or numbers like this, it may be possible that someone else uses the exact same string which may result into compromise of private key. So better be safe than sorry and only rely on random generators to generate private key.
But again another problem arises. Most of the generators such as Math library of Javascript (Math.random() function) use fixed patterns to generate random number. So using such generators will generate more miseries than keys.
So what is the ultimate solution? The best way is to use the keys generated by wallets but if you want to independently dive into the quest, use secure generators like this one:
strong pseudorandom generator.
Enough said on private keys, let's go to bitaddress.org and generate an address. First we will create address on bitaddress.org and then try to create the same through our own code to learn the mathematics behind key generation.
Here is the key pair I generated. You may find that there are more than one format for both public key and private key. Let's discuss about them in brief before jumping to the coding part:
1. Public Address
This is the P2PKH format of bitcoin address. It is widely used for sending/receiving bitcoins. Public Key once generated through Elliptic Curve cryptography is then hashed using sha-256 and ripemd-160 algorithm and later checksum is attached in the end of hash which forms public address. We will try to achieve that later in this thread with real code.
2. WIF Private Key
WIF or Wallet Import Format is the format of private key in which wallets such as Electrum import private key. If you paste the bare hex of private key then Electrum won't open the wallet. You have to convert private key into WIF format to use it in wallets. We will write code to convert private key into WIF too.
3. Uncompressed Public Key
Ok! So I haven't discussed so far how public key is generated. The process is actually complex. We take a special generator point defined as
G by SECG which is located on secp256k1 curve i.e. one of the elliptic curve. Then we multiply this generator point with private key. The resulting multiplication will give us two coordinates, one is X and the other is Y. Uncompressed Public Key is nothing but : 04 + X + Y. So first two numbers of public key are 04 which signifies that key is uncompressed. Next 64 characters (32 bytes since every 2 characters of hex make 1 byte) are X coordinate and last 64 characters (32 bytes) are Y coordinate. Total length of uncompressed public key is 130 or 65 bytes.
4. Compressed Public Key
Since, it is possible to find Y coordinate if X coordinate is given. So we generally drop the Y coordinate from our public key. Hence, last 64 characters are removed. As a result, compressed public key is made up of 66 characters (32 bytes). First two characters can be either 02 or 03 (instead of 04) and the next 64 characters (32 bytes) will be X coordinate. If the value of Y coordinate is even then 02 is put. If the value of Y coordinate is odd then 03 is put. In the above photo, the value of Y-coordinate was odd so we have 03 in our key.
5. Private Key Hexadecimal Form
As we discussed earlier the private key must be 256-bits or 32 bytes (8 bits = 1 byte) which is when converted into hexadecimal form is of 64 characters. So you can convert any value into hex and it will be of 64 characters. This is very handy for our bitcoin code because we will use hex form of private key to start generating key pair. So as I was saying earlier that we can even use strings like "I am a string to generate private key" to generate private key, so here is the secret. We will first convert such strings into hex and then use 64 characters of hex to generate key pair.
6. Private Key Base64 Form
Not very popular format of private key. But we can even encode/decode our private key into Base64 using native conversion.
Enough for the head start. Now let's dive straight into code and generate the above key.
As I am fan of Javascript (because I think it is the easiest programming language and can be used in full-stack development), I will be using JS in Node.JS environment for this guide. But if you are comfortable with other language then you can easily interpret my JS code into your code. At last, if you aren't comfortable with coding at all then leave that, just read the text and pictures below and I promise you will have the best idea on how keys are generated.
Before starting let's prepare the setup. First step is to create a folder. Inside folder create a file with .js extension. File name can be anything like index.js or app.js.
Next step is to download node.js on your computer. It is very easy to download node.js, it is similar to downloading any other computer software. Next step is to download some code editor, I suggest Visual Studio Code (easy to use IDE).
Once the above steps are done, open the folder in Visual Studio Code and head to your terminal. There is inbuilt terminal in Visual Studio Code, you can use that too. If not, you can use native terminal of Mac or Windows but make sure you have opened the folder in terminal. Once folder is opened in both Visual Studio Code and terminal, run the following commands in terminal to install 2 dependencies for the project:
npm init -y
npm i ripemd160 --save
npm i bs58 --save
We need two hashing and one encoding functions in our code namely sha256, ripemd160 and base58 apart from elliptic curve cryptography. sha256 is already present in native crypto library of nodejs. We can either code other two on our own or just import them. For the simplicity of this guide, we installed ripemd160 and bs58 npm packages above and will use these in our code. I have verified the source code of both packages and it's completely safe to use these in code.
Now let's start the real fun. Open your file and start with the code. The code is in chronological order. The Step 1 code will go at the top of file and step 2 code will start where step one code ends and so on:
Step 1. Creating hashing functions
const crypto = require('crypto');
const RIPEMD160 = require('ripemd160');
const BS58 = require('bs58');
const sha256 = input => crypto.createHash('sha256').update(input).digest();
const ripemd160 = input => new RIPEMD160().update(input).digest();
const bs58 = input => BS58.encode(input);
Ok! So in first three lines of code, we have imported the code of all three hashing and encoding functions in our file. Next, we created functions for these. It is not mandatory to create functions but in that case we have to write whole code again and again whenever we need to hash something. For example, if we don't write these three functions then every time we have to create sha256 hash of something we have to write
crypto.createHash('sha256').update(something).digest() but with above code, we just have to write
sha256(something) from next time. Cool? Let's move forward.
Step 2. Creating Elliptic Curve Function
const generateECPoints = privateKey => {
const Pcurve = BigInt('0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F');
const Gx = BigInt('55066263022277343669578718895168534326250603453777594175500187360389116729240');
const Gy = BigInt('32670510020758816978083085130507043184471273380659243275938904335757337482424');
const G = [Gx, Gy];
const modInverse = (a, n) => {
a = (a % n + n) % n
const dArray = [];
let b = n;
while(b) {
[a, b] = [b, a % b];
dArray.push({a, b});
}
if (a !== BigInt(1)) {
return null;
}
let x = BigInt(1);
let y = BigInt(0);
for(let i = dArray.length - 2; i >= 0; --i) {
[x, y] = [y, x - y * BigInt(dArray[i].a / dArray[i].b)];
}
return (y % n + n) % n;
}
const modOf = (a,b) => {
const r = ((a % b) + b)% b;
return r;
}
const ECAdd = (a,b) => {
const lamAdd = modOf((b[1] - a[1]) * BigInt(modInverse(b[0] - a[0], Pcurve)), Pcurve);
const x = modOf((lamAdd*lamAdd - a[0] - b[0]), Pcurve);
const y = modOf((lamAdd*(a[0] - x) - a[1]), Pcurve);
return [x, y];
}
const ECDouble = a => {
const lamda = modOf(((BigInt(3)*a[0]*a[0])*(modInverse(BigInt(2)*a[1], Pcurve))), Pcurve);
const x = modOf((lamda*lamda - BigInt(2)*a[0]), Pcurve);
const y = modOf((lamda*(a[0] - x) - a[1]), Pcurve);
return [x, y];
};
const ECMultiply = (genPoint, pvtKey) => {
const scalarBinary = BigInt('0x'+pvtKey).toString(2);
let GP = genPoint;
for (let i=1; i < scalarBinary.length; i++) {
GP = ECDouble(GP)
if (scalarBinary[i] === '1') {
GP = ECAdd(GP, genPoint);
}
}
return GP;
}
return ECMultiply(G, privateKey);
}
The above code is my version of Elliptic Curve Multiplication. This maybe only pure Javascript coding of elliptic curve you will find on the entire internet. I think it would be inappropriate to explain the whole above code in this thread as the main motive of this thread is to generate key pair. So for now use the above code as it is. I will create separate thread for Elliptic Curve Cryptography after 3-4 days and explain the same above code in that thread.
Step 3. Generating X and Y coordinates of Public Key from above function and Private Key
const privateKey = "6EBD5FAB742ED0734B37C63BD2A3CE8797FE4AC63C9A99781F8BEDDF6307094E";
const publicKey = generateECPoints(privateKey);
In this step we have taken the hex value of private key (5th item from the image) and put it in generateECPoints function as created in Step 2. This will give us X and Y coordinates of Public Key which will look like this:
[26552980488606060638326679080566574626825610331305555186819497546906082384636n, 106820354128014061768597493909158935631153585355120117243602895828064095418195n]
You may notice
n at the last of each coordinate. This
n means we are dealing with extra large numbers here, known as Big Integers in Javascript. Also you may notice that these coordinates are not matching the X and Y in the image above. Well, we have generated numbers for now. We have to convert these into hexadecimals to get uncompressed key and compressed key. Let's do that in next step.
