Browsed by
Tag: address

Keys, addresses and hashing

Keys, addresses and hashing

A key pair is one of the greatest tools that are used in Bitcoin, but it might be a little unintuitive at first. Don’t worry, you’ll get it!

There’s also a short video I made a few months ago that describes the basics of keys. It doesn’t completely corresponds to our current project, but it might provide you with another point of reference. You can watch it over here – Bitcoin python tutorial for beginners – keys and address.

 

One way function

The name “one way function” is quite self explanatory. These function are very easy to solve in one way but almost impossible to invert. Giving function f, and the input x, I can easily calculate the result y.

f(x) = y <- easy to solve

But given the result y, and the function f, It will be almost impossible to find x

f(?) = y <- almost impossible to guess.

The Bitcoin protocol define the use of some of these one way functions (SHA256, ripmed, ECDSA and murmurhash. More functions are being tested and might be used in the future).  Each one of these function has its own place in the protocol. Some functions will be used more then once and/or will be combined with another function to achieve even a grater level of security. For example, signing a message (usually a transaction message) will be done using the SHA256 function, SHA256("hello!"), finding the checksum of the message payload will be done using the SHA256 function twice SHA256(SHA256(message)).

  • Some people have hard time to accept the concept of “hard to guess”, they feel it’s too ambiguous. Well, technically an extremely powerful computer might be able to iterate through all possible results until it will find the right one (this is called brute force), but in practice, it will take a very – very long time. Trying to brute force the result of a SHA256 function on a 32 bytes message will take about 10^65 years. The age of the universe is only 1.4*10^9 year. I think it’s good enough security.
It’s easy to get the result y of function f for a giving x. But almost impossible to tell what the original input was.

 

Mathematical trapdoor and key pair

Mathematical trapdoor is a special type of one way function. The main difference is that in mathematical trapdoor we may also use few extra pieces of information called keys. Bitcoin uses the mathematical trapdoor function ECDSA or Elliptic Curve Digital Signature Algorithm, to produce two keys, or a key pair -A private key, and a public key – Both keys will always come in pairs! there cannot be a public key that matches two different private keys and vice versa!

The private key is used to solve (sign) the function f for message x. The result is the signed message y.

f(private_key, x) = y <- easy to solve

Now I have two messages. The original message x, and the signed message y. I want to prove that I’m the one who signed the original message x, that I’m the owner of the private key. But I don’t want to give my own private key. Anyone who have my private key will be able to sign in my name on other messages as well. So I’m using the public key. The public key can only be used to prove the solution of the function, but it cannot be used to sign messages

f(public_key, x) = y <- easy to prove

f(public_key, x) = null <- I can't sign message x with the public key. only with the private key

  • Pay attention that when we’re using the public key we’re just proving the equation, not solving it.

Here’s a simple numeric example I found on the wikipedia page on mathematical trapdoor:

An example of a simple mathematical trapdoor is “6895601 is the product of two prime numbers. What are those numbers?” A typical solution would be to try dividing 6895601 by several prime numbers until finding the answer. However, if one is told that 1931 is one of the numbers, one can find the answer by entering “6895601 ÷ 1931” into any calculator. This example is not a sturdy trapdoor function – modern computers can guess all of the possible answers within a second – but this sample problem could be improved by using the product of two much larger primes.

 

Let’s see an example:

Step one – create a key pair:

Create key pair using the ECDSA function and some random numbers
Create key pair using the ECDSA function and some random numbers

Step two – sign a message with the private key:

using the private key and the ECDSA algorithm
using the private key and the ECDSA algorithm

Step three – send the original message alongside the encrypted message and the public key

3 items are needed to validate the message. The public key, the original message and the encrypted message
3 items are needed to validate the message. The public key, the original message and the encrypted message

The code

In our project we’ve defined the Key class under Bitpay/Utils/KeyUtils/keys.py. This class contains all the necesery steps that are required in order to generate a private key, trnsform that private key to a public key and then create a Bitcoin address out of that public key.

step one – create (or receive) the private key

The first thing that we’re going to do is to create our private key. The private key is defined as  a random 32 bytes uint. Our class begins with a simple check. If the user initialize the Key class with an already existing private key, that private key will be saved into self.private_key. Otherwise, we’re using the urandom function in the os module to create a random 32 bytes long number.

def __init__(self, private_key=0):
    if private_key == 0:
        self.private_key = os.urandom(32)
        self.printable_pk = str(binascii.hexlify(self.private_key), "ascii")
    else:
        self.printable_pk = private_key
        self.private_key = binascii.unhexlify(private_key.encode('ascii'))

You might’ve noticed that we’ve also created a printable_pk variable. This variable will store the private key in hexadecimals. This way it is easier to store, copy and/or print the private key.

 

Step two – Use the private key to initialize the signing function

After we got our private key it’s time to use it initialize our ECDSA function. This step is similar to declaring our function f with the private key pr_k.

self.sk = f(pr_k, )

We’re defining the variable self.sk (for Signing Key) and use SigningKey.from_string from the ECDSA module with two arguments, the first one is our self.private key, and the second one is the curve (We haven’t talked about the curve yet, But it represent the mathematical part of our function. This is too advance mathematics so we won’t go into it in this project. But for now we just need to know that the Bitcoin protocol requires us to use the ECDSA function with the mathematical curve SECP256k1)

self.sk = ecdsa.SigningKey.from_string(self.private_key, curve = ecdsa.SECP256k1)

 

Step three – Use the initialized function (self.sk) to get the public key

Now that we got our signing key, we can use it in order to create our public key.

self.vk = self.sk.verifying_key

We’re defining a new variable called self.vk which will hold the verifying key, or the public key that can be sent alongside the signed message and the original message. This key will be used to verify that the message was indeed signed by the owner of that public key. And since every public key matches only one specific private key, it also proves that the one who signed the message also possess the corresponding private key.

 

Step four – Formatting the public key.

The variable self.vk holds the public key that will be used to verify our signed messages. But the Bitcoin protocol requires that we’ll represent this public key in couple of different formats.

The following chart from the Bitcoin wiki site shows the way the public key should be formatted:

Converting the public key to Bitcoin address
Converting the public key to Bitcoin address

 

The first line is the real public key, or in our case the verification key self.vk

this is the real public key - but we can't send it like this. We need to do dome formatting
this is the real public key – but we can’t send it like this. We need to do dome formatting

 

The second line tells us that we need to inser the byte 0x04 at the beginning of our public key

self.public_key =  b"04" + binascii.hexlify(self.vk.to_string())

We’re using the function to_string in order to display the variable self.vk  as a string. Then we convert it to hexadecimals so it will be easier to append the byte 0x04.

This is the public key in Bitcoin terminology. Usually, When looking for the public key in signed transactions, that's what it will look like
This is the public key in Bitcoin terminology. Usually, When looking for the public key in signed transactions, that’s what it will look like

 

The third line tells us to hash the public key twice. once using the SHA256 function, and then again using the ripemd160 function.

ripemd160 = hashlib.new('ripemd160') # <-initializing the ripemd160 function 
ripemd160.update(hashlib.sha256(binascii.unhexlify(self.public_key)).digest())
First hashing the public key using the SHA256 function. Then the result is hashed with the ripemd160 function
First hashing the public key using the SHA256 function. Then the result is hashed with the ripemd160 function

The forth line tells us to add another byte at the beginning of the hashed key.

We're working with the main network so we'll add the byte 0x00
We’re working with the main network so we’ll add the byte 0x00

This is the network ID byte which is used to prevent us from using keys and addresses that were generated in the test network, in the main network (and vice versa). In our example we’re using the main network, so the byte we’ll add will be 0x00.

self.hashed_public_key = b”00″ + binascii.hexlify(ripemd160.digest())

In Bitcoin terminology, the result is the hashed public key. This format is used mostly when creating a transactions.

 

The fifth (and sixth) line tells us to take our hashed public key and hash it again, twice, using the SHA256 function. The first 4 bytes of the result will be the checksum.

self.checksum = binascii.hexlify(hashlib.sha256(hashlib.sha256(binascii.unhexlify(self.hashed_public_key)).digest()).digest()[:4])
The checksum is the first 4 bytes
The checksum is the first 4 bytes

 

The seventh line creates the Bitcoin address in its binary form by appending the hashed public key with the checksum. This is a valid Bitcoin address, but it still need to go through one more process before it can be used with most Bitcoin wallets.

self.binary_addr = binascii.unhexlify(self.hashed_public_key + self.checksum)

 

The last line Finally we’ve reached the end point. There’s only one more thing we need to do before we can get the standard Bitcoin address and that is to convert the binary code of the address into a base58 string. The idea behind this conversion is quite simple. In order to reduce human errors, it was decided that some characters will be omitted from the standard Bitcoin address. characters like capital O, the number 0, lower case l and upper case I, as well as many more characters were omitted.

The final address represented in base 58.
The final address represented in base 58.
self.addr = base58.b58encode(self.binary_addr)
  • You might need to install the base58 module using the command pip install base58.

 

User interface

We’ve also added a tab to our graphical user interface which might help. You can use it to see the public key, hashed public key and Bitcoin address or any given private address.

The user interface for the keys can be found in the second tab
The user interface for the keys can be found in the second tab