The following content was written by webtricks on February 04, 2020, 05:05:40 PM in the thread How Bitcoin Addresses are generated? Understand the Math behind Bitcoin. All content is owned by the author of the bitcointalk.org post. (original)
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:
Code:
npm init -y
npm i ripemd160 –save
npm i bs58 –save
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
Code:
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);
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
Code:
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);
}
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
Code:
const privateKey = “6EBD5FAB742ED0734B37C63BD2A3CE8797FE4AC63C9A99781F8BEDDF6307094E”;
const publicKey = generateECPoints(privateKey);
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.
The following content was written by webtricks on February 04, 2020, 05:06:05 PM in the thread How Bitcoin Addresses are generated? Understand the Math behind Bitcoin. All content is owned by the author of the bitcointalk.org post. (original)
Step 4. Creating Compressed and Uncompressed Public Key
Code:
const checkKey = key => key.length < 64 ? ‘0’.repeat(64 – key.length) : key;
const publicKeyX = checkKey(publicKey[0].toString(16));
const publicKeyY = checkKey(publicKey[1].toString(16));
const uncompressedKey = ’04’+publicKeyX+publicKeyY;
let compressedKey;
if (publicKey[1]%BigInt(2)===BigInt(1)) {
compressedKey = ’03’+publicKeyX;
} else {
compressedKey = ’02’+publicKeyX;
}
const publicKeyX = checkKey(publicKey[0].toString(16));
const publicKeyY = checkKey(publicKey[1].toString(16));
const uncompressedKey = ’04’+publicKeyX+publicKeyY;
let compressedKey;
if (publicKey[1]%BigInt(2)===BigInt(1)) {
compressedKey = ’03’+publicKeyX;
} else {
compressedKey = ’02’+publicKeyX;
}
Bingo! We have achieved the first target. We have created uncompressed and compressed public key. In the code above, we have first of all created checkKey function. This function is doing an interesting thing. It may be possible that while converting X and Y coordinates from number to hexadecimal that the resultant length of X and Y is not 64. But as we discussed previously that the length of uncompressed key is 130 where first two characters are 04 then 64 characters of X and then 64 of Y. So it fill the void, we are adding zeros if length is lower than 64. For example, if the length of X is 63 characters, we will add one 0 to make it 64.
Then we defined hexadecimal value of X coordinate as publicKeyX and Y as publicKeyY. You may see we using toString(16) in second and third line. This code is converting number to hex and then overall wrapper of checkkey is checking if the length is lower than 64 then add 0, if not then return same key.
Then we defined uncompressed key as uncompressedKey and then compressed key as 03+X if Y is odd and 02+X if Y is even.
Step 5. Generating P2PKH Key
Before starting with code let’s discuss the process of generating P2PKH key. It is to notice that uncompressed and compressed key we generated in step 4 was not Bitcoin specific. There are several other services like Gmail or Facebook using Elliptic Curve cryptography to create public/private keys. However, this very step is where we will convert our public key into Bitcoin-specific format i.e. P2PKH. Following is the pictorial representation of the process, yes the artist is back
So we start with uncompressed key as generated in step 4 (we can also start with compressed key which will generate different P2PKH address but can be used interchangeably and belongs to same private key). Next we perform sha256 on the uncompressed key. Then ripemd160 hashing on the previous. Then we add 00 in front of previous hash. This is our 21-bytes of binary address. To generate next 4-bytes of binary address. We have to perform double sha256 hashing on first 21 bytes. Take the first 4 bytes of resulting hash i.e. first eight characters of the resulting hash and add it in the end of 21 bytes. Finally we get 25-bytes Binary address and we have to convert this into Base58 code. Now let’s see the final code.
Code:
const keyHex = Buffer.from(uncompressedKey, ‘hex’);
const ripedHashedKey = ripemd160(sha256(keyHex));
const mainRipeKeyString = ’00’+ripedHashedKey.toString(‘hex’);
const mainRipeKey = Buffer.from(mainRipeKeyString, ‘hex’);
const doubleHashedKey = sha256(sha256(mainRipeKey)).toString(‘hex’);
const checkSum = doubleHashedKey.substr(0, 8);
const binaryAddress = Buffer.from(mainRipeKeyString+checkSum, ‘hex’);
const publicAddress = bs58(binaryAddress);
const ripedHashedKey = ripemd160(sha256(keyHex));
const mainRipeKeyString = ’00’+ripedHashedKey.toString(‘hex’);
const mainRipeKey = Buffer.from(mainRipeKeyString, ‘hex’);
const doubleHashedKey = sha256(sha256(mainRipeKey)).toString(‘hex’);
const checkSum = doubleHashedKey.substr(0, 8);
const binaryAddress = Buffer.from(mainRipeKeyString+checkSum, ‘hex’);
const publicAddress = bs58(binaryAddress);
The above code is nothing but the same 8 steps I detailed in picture above. Bingo! We have successfully generated our Bitcoin Address. Now let’s move to final step and generate our WIF private key from hexadecimal of private key.
Step 6. Generating WIF from Private Key
Similar to the previous approach, let’s discuss the process before actually moving to the code. Generating WIF from private key is actually simpler than previous step. Converting raw hex of private key into WIF actually has many benefit. First it is smaller and simpler than raw hex. Second it has inbuilt-checksum to verify that private key is valid. Let’s see the pictorial representation from artist first:
First step is simple, we are taking hexadecimal form of private key and adding 80 in front of it. Note that all these addition we are making throughout code isn’t actually numbers. They are hex codes, for example, 80 here when converted to decimal form is 128. Ok next, we are performing double rounds of sha256 hashing. Then we take first 4 bytes of the resultant hex and add them at the end of extended hex of private key. Finally we perform Base58 encoding on the result and we get our WIF key. Code time:
Code:
const pvtKeyExtended = “80”+privateKey;
const extended = Buffer.from(pvtKeyExtended, ‘hex’);
const hashedExtended = sha256(sha256(extended)).toString(‘hex’);
const checksum = hashedExtended.substr(0, 8);
const finalHex = pvtKeyExtended+checksum;
const WIF = bs58(Buffer.from(finalHex, ‘hex’));
const extended = Buffer.from(pvtKeyExtended, ‘hex’);
const hashedExtended = sha256(sha256(extended)).toString(‘hex’);
const checksum = hashedExtended.substr(0, 8);
const finalHex = pvtKeyExtended+checksum;
const WIF = bs58(Buffer.from(finalHex, ‘hex’));
Nothing special in code this time too. We are simply performing all six steps as mentioned in picture above. If you have any doubt regarding any code, you can ask in thread or PM me.
Good work! We have finally completed the process and generated our Bitcoin Address along with WIF Key. Great, now let’s test the code next.
The following content was written by webtricks on February 04, 2020, 05:06:18 PM in the thread How Bitcoin Addresses are generated? Understand the Math behind Bitcoin. All content is owned by the author of the bitcointalk.org post. (original)
TESTING
Code:
console.log(`This is Bitcoin Address: ${publicAddress}
This is WIF Key: ${WIF}
This is Uncompressed Public Key: ${uncompressedKey}
This is compressed Public Key: ${compressedKey}
Thisi is hexadecimal of Private Key: ${privateKey}`);
This is WIF Key: ${WIF}
This is Uncompressed Public Key: ${uncompressedKey}
This is compressed Public Key: ${compressedKey}
Thisi is hexadecimal of Private Key: ${privateKey}`);
After writing above code in file, save the file and open terminal. Now run the following command in terminal. Make sure, folder is opened in terminal:
node index.js (file name can be different for you)
You will get address, WIF, public keys, private key in terminal and these will match bitaddress generated keys. You can try different private key. Just change the private key in Step 3 and you are good to go.
But let’s not forget the fact that this thread is still for learning purpose. Always use the keys generated by wallets like Electrum and MyCelium, unless you are completely sure what are you doing.
Hope you liked this guide. Do let me know if you still get any doubts, I will address them.
For full code in order, visit: https://webtricks.website/keyGeneration.html
Watch code in action, visit: https://key-generation-by-webby.herokuapp.com/
