Shiba to lion workshop, third session

Fifteen days have passed since the last workshop, and we met up for the third time at the INSA Lyon library in order to learn how are generated key pairs !

Multiple encodings

On Bitcoin (and therefore Insacoin) there are many key encodings used in order to simplify the utilisation of the asymetric cryptography used to determine the property of tokens (bitcoins, insacoins, ..).

Base58

An address is a 160bits hash of a public key. It can be represented as a 20 characters hexadecimal number but it’s not so convenient for the end user. Satoshi decided to use a larger sample of characters to reduce the size of the address, but the base64 encoding comonly used for big amount of data presents some drawbacks : the use of characters which could confuse the spelling of the address, such as O and 0 (capital “o” and zero) or I and l (lowercase “L” and capital “i”), and the use of characters which could break copy with a double click (such as “/”). Base58 encoding is a base64 encoding without “/”, “+”, “I”, “l”, “0” and “o”.

Base58Check

To avoid usage of non-Bitcoin addresses, Satoshi decided to encode addresses in Base58Check.
To get an a Bitcoin address we so make a ripemd160(sha256()) hash of the public key, to which we add a “version prefix”. It is a (usually one-byte) number indicated which network the address belongs : it is 0x00 on Bitcoin, 0x66 on Insacoin. We then take the last four bytes of the sha256(sha256()) hash of this payload, which we append to it : this is the checksum. The base58 encoding of this whole payload (version + hash160(pubkey) + checksum) is our address.

WIF

Wallet Import Format is a private key encoding used to display and manage them. It is a base58Check encoding of the private key + 0x01, with a prefix of 0x80 on Bitcoin and 0xb0.

Encodings Python implementation

Here is an implementation of these functions in Python.

def sizeof(n):
    """
    get the size in bytes of an integer, https://stackoverflow.com/questions/14329794/get-size-of-integer-in-python

    :param n: the integer to get the size from
    :return: the size in bytes of the int passed as the first parameter.
    """
    if n == 0:
        return 1
    return int(log(n, 256)) + 1


def hash160(bytes, bin=False):
    """
    Returns the ripemd160(sha256(data)), used a lot in Bitcoin.

    :param bin: If set to true, returns bytes.
    """
    rip = hashlib.new('ripemd160')
    rip.update(hashlib.sha256(bytes).digest())
    if bin:
        return rip.digest()  # type : bytes
    else:
        return rip.hexdigest()  # type : str


def double_sha256(bytes, bin=False):
    """
    Returns the sha256(sha256(data)), used a lot in Bitcoin.

    :param bin: If set to true, returns bytes.
    """
    h = hashlib.sha256(bytes)
    if bin:
        return hashlib.sha256(h.digest()).digest()  # type : bytes
    else:
        return hashlib.sha256(h.digest()).hexdigest()  # type : str

def b58encode(payload):
    """
    Takes a number (int or bytes) and returns its base58_encoding.

    :param payload: The data to encode, can be bytes or int
    :return: the number passed as first parameter as a base58 encoded str.
    """
    if isinstance(payload, bytes):
        n = int.from_bytes(payload, 'big')
    elif isinstance(payload, int):
        n = payload
    else:
        raise ValueError('b58encode takes bytes or int')

    alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
    x = n % 58
    rest = n // 58
    if rest == 0:
        return alphabet[x]
    else:
        return b58encode(rest) + alphabet[x]


def b58decode(string):
    """Takes a base58-encoded number and returns it in base10.
    :param string: the number to base58_decode (as str).
    :return: the number passed as first parameter, base10 encoded.
    """
    alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
    # Populating a dictionary with base58 symbol chart
    dict = {}
    k = 0
    for i in alphabet:
        dict[i] = k
        k += 1
    n = 0  # Result
    pos = 0  # Cf https://www.dcode.fr/conversion-base-n
    for i in string:
        for y in alphabet:
            if i == y:
                n = n * 58 + dict[i]
        pos += 1
    return n


def encode_check(payload):
    """Returns the base58 encoding with a 4-byte checksum.

    :param payload: The data (as bytes) to encode.
    """
    checksum = double_sha256(payload, True)[:4]
    if payload[0] == 0x00:
        # Again, the leading 0 problem which results in nothing during int conversion
        return b58encode(b'\x00') + b58encode(payload[1:] + checksum)
    else:
        return b58encode(payload + checksum)


def decode_check(string):
    """Returns the base58 decoded value, verifying the checksum.

    :param string: The data to decode, as a string.
    """
    number = b58decode(string)
    # Converting to bytes in order to verify the checksum
    payload = number.to_bytes(sizeof(number), 'big')
    if payload and double_sha256(payload[:-4], True)[:4] == payload[-4:]:
        return payload[:-4]
    else:
        return None


def wif_encode(data, prefix=b'\xb0'):
    """
    WIF-encode the data (which would likely be a Bitcoin private key) provided.

    :param data: The bytes to WIF-encode.
    """
    return encode_check(prefix + data) # str


def wif_decode(string):
    """
    WIF-decode the provided string (which would likely be a WIF-encoded Bitcoin private key).
    """
    dec = decode_check(string)
    if string[0] == 'T': # For Bitcoin the condition is if string[0] == 'K' or 'L'
        return dec[1:-1] # bytes
    else:
        return dec[1:] # bytes

Generating a key pair

A key pair is what you could call an Insacoin (/Bitcoin) account : it consists of a private key used to sign transactions (send coins) and a public key used so you are the only one able to sign this transaction (receive coins).

Private key

A private key is a random (256 bits) number. You could just toss a coin 256 times with 1 given to head and 0 to tail, and you would generate the basis of an Insacoin (/Bitcoin) account. It is important to remark that anyone is able to generate a random number and therefore get an Insacoin/Bitcoin account, you don’t ask for an account, you generate it whether anyone gives its permission or not.
In Python it can be implemented this way :

def gen_random():
    """
    Generates a random number from a CSRNG.
    """
    seconds = int(time.time())
    entrop1 = double_sha256(seconds.to_bytes(sizeof(seconds), 'big'), True)
    entrop2 = double_sha256(os.urandom(256), True)
    entrop3 = double_sha256(uuid.uuid4().bytes, True)
    return double_sha256(entrop1 + entrop2 + entrop3, True)

def gen_privkey():
    while True:
        n = int.from_bytes(gen_random(), 'big')
        if 0 < n < 115792089237316195423570985008687907852837564279074904382605163141518161494337:
            return n.to_bytes(sizeof(n), 'big') + b'\x01'

The condition in the gen_privkey() function is here to certify the generated random number is less than the secp256k1 curve order, because the private key is a point on this Ellliptic Curve, and we will use this point to derive the public key corresponding to it.

Public key

A public key is derived on the secp256k1 curve, from a given point : the private key from the previous section. I won’t detail the process of the derivation but if you want to know more about it you can checkout these links : * Mastering Bitcoin, from Andreas M. Antonopoulos for an applicated point of view (on Bitcoin) * Introducing Elliptic Curves for a broader point of view.

Address

Most of of it have been said in the encoding section, I won’t repeat myself but I can give an example implementation (still in Python 😉 ) to complete what I previously said :

def get_address(pubkey):
    version = b'\x66'
    hash = hash160(pubkey, bin=True)
    return encode_check(version + hash)

Compression

The private key is a point on the secp256k1 curve. The public key is a point on the secp256k1 curve. Both being points they are represented by an abscissa and an ordinate.
Ok, so what ?
Public keys are stored inside transactions, which are themselves stored inside blocs, and… bloc size is limited. The public key size thus directly affects the network capacity in terms of transaction/second : the smaller the transactions, the higher the number of them that can be put in a block each time one is generated. The secp256k1 curve is defined by the equation y^2 = x^3 + 7 so we can easily calculate the ordinate of a point (concretely, the public key) from its abscissa. But there is one more thing to consider : the sign of y.
The secp256k1 curve
You can see on this image representing the curve that every x value has 2 corresponding y values, thus 2 different points (therefore 2 different public keys). In order to “remember” the correct point we need to store the sign of y. So here is the rule :
* If the public key is compressed and y is even, we store it as 0x02 + x * If the public key is compressed and y is odd, we store it as 0x03 + x * If the public key is not compressed, we store it as 0x04 + x + y with + meaning “concatenation” here.
Another rule is : * Append 0x01 to a private key which is used to derive compressed public keys. It is called a compressed private key (and a compressed private key is longer than an uncompressed one, yes). A compressed private will begin with a different character when WIF-encoded (“K” or “L” on Bitcoin, and “T” on Insacoin).
Here is the snippet to get a public key from a private key (I use the secp256k1 lib written by Vitalik Butterin for ECC with secp256k1).

def get_pubkey(privkey):
    if len(privkey) == 33: # Meaning if the privkey has a 0x01 prefix, otherwise it would be 32 bytes long
        (x, y) = secp256k1.privtopub(privkey[1:])
        if y % 2:
            return b'\x02' + x.to_bytes(sizeof(x), 'big')
        else:
            return b'\x03' + x.to_bytes(sizeof(x), 'big')
    else:
        (x, y) = secp256k1.privtopub(privkey)
        return b'\x04' + x.to_bytes(sizeof(x), 'big') + y.to_bytes(sizeof(y), 'big')

Generating a key pair with our functions

All the functions can be found on the repo used for the workshop.

def get_keypair():
    pk = gen_privkey()
    addr = get_address(get_pubkey(pk))
    print('Privkey : ', wif_encode(pk))
    print('Address : ', addr)

if __name__ == '__main__':
    get_keypair()

Which would output something like :

Privkey :  T789W3NaQ4fEJcCDzwMc2th7UQ7D1Ak2H558RzuMRPWrGHAxvbrS
Address :  iRw9KMcP2oxVT1o67x6XFpuxKeaA9DM93b

And just changing the base58Check prefixes to those used on Bitcoin (0x80 for WIF and 0x00 for addresses) would output :

Privkey :  Kzb2sAtToJjHqMS4URPqsFqwVTuf9czfArV8foWcauWGw1A81FVq
Address :  18GcF7hyuKgAVgRvmhCUeyt6sLQ4nQNULK

Both pairs are valid and you can check them out on the Insacoin explorer and Bitcoin explorer.