Pavlov_dog January 18, 2017 at 16:41

Bitcoin in a nutshell - Cryptography

One of the reasons why Bitcoin continues to attract so much attention is its exceptional “math”. Satoshi Nakamoto managed to create a system that is able to function in the complete absence of trust between its participants. All interactions are based on rigorous mathematics, no human factor - that was the idea of revolution, and not in a peer-to-peer network, as many people think. Therefore, I decided to devote the first chapter to the mathematical foundations of Bitcoin.

Below I will try to explain to you the most basic things - elliptic curves, ECC, private / public keys and so on. If possible, I will illustrate my words with code examples, mainly in Python 2.7, if something is not clear - ask in the comments.

intro

Book

Table of content

Introduction
Elliptic curve
Digital signature
Private key
Public key
Formats & address
Sign
Verify
Formats
Links

Introduction

As I said above, cryptography is a fundamental part of Bitcoin. Without it, nothing would have worked at all, so you need to start from here.

Bitcoin uses the so-called cryptography on elliptic curves ( Elliptic curve cryptography, ECC ). It is based on some special function - an elliptic curve (not to be confused with an ellipse). What this function is and why it is so remarkable I will tell further.

Elliptic curve

Эллипти́ческая крива́я над полем $K$ — неособая кубическая кривая на проективной плоскости над ${\ hat {K}}$ (алгебраическим замыканием поля $K$ ), задаваемая уравнением 3-й степени с коэффициентами из поля $K$ и «точкой на бесконечности» — Wikipedia

Если на пальцах, то эллиптическая кривая — это внешне довольно простая функция, как правило, записываемая в виде так называемой формы Вейерштрасса: $y ^ {2} = x ^ {3} + ax + b$

В зависимости от значений параметров $a$ и $b$ , график данной функции может выглядеть по разному:

elliptic curves

Скрипт для отрисовки графика на Python:

import numpy as np
import matplotlib.pyplot as plt
def main():
    a = -1
    b = 1
    y, x = np.ogrid[-5:5:100j, -5:5:100j]
    plt.contour(x.ravel(), y.ravel(), pow(y, 2) - pow(x, 3) - x * a - b, [0])
    plt.grid()
    plt.show()
if __name__ == '__main__':
    main()

If you believe the wiki, then for the first time this function was lit up in the writings of Diophantus, and later, in the 17th century, Newton himself became interested in it. His research led in many respects to the formulas for adding points on an elliptic curve, which we will now meet. Hereinafter, we will consider some elliptic curve $\ alpha$ .

Let there be two points $P, Q \ in \ alpha$ . Their sum is called the point $R \ in \ alpha$ , which in the simplest case is defined as follows: we draw a line through $P$ and $Q$ - it intersects the curve $\ alpha$ at a single point, we call it $-R$ . Changing the $y$ coordinate of the point $-R$ to the opposite sign, we get a point $R$ , which we will call the sum $P$ and $Q$ , that is $P + Q = R$ .

ellitic_curve_addiction

I consider it necessary to note that we are just introducing such an addition operation - if you add up the points in the usual sense, that is, add up the corresponding coordinates, you will get a completely different point $R '(x_1 + x_2, y_1 + y_2)$ , which most likely has nothing to do with $R$ or $-R$ and does not lie on the curve at all $\ alpha$ .

The most quick-witted ones have already asked themselves - what will happen if, for example, a straight line is drawn through two points having the coordinates of the view $P (a, b)$ and $Q (a, -b)$ that is, a straight line passing through them is parallel to the ordinate axis (third frame in the picture below).

elliptic_curve_parallel

It is easy to see that in this case there is no third intersection with the curve $\ alpha$ that we called $-R$ . To avoid this mishap, we introduce the so-called point at infinity (point of infinity), usually denoted by $O$ or just

like the picture. And we will say that in the absence of intersection $P + Q = O$ .

Of particular interest to us is the case when we want to add a point to itself (2 frames, a point $Q$ ). In this case, we simply draw a tangent to the point $Q$ and reflect the resulting intersection point with respect to $y$ .

Now, with a flick of the wrist, you can enter the operation of multiplying a point by some $\ mathbb {N}$ number. As a result, we get a new point $K = G * k$ , that is, $K = G + G + ... + G, \ k$ time. Everything should become clear with the picture:

Elliptic curve multiplication

Elliptic curve over a finite field

The ECC is used in exactly the same curve, only considered over a finite field ${F} _ {p} = \ mathbb {Z} / \ mathbb {Z} _p = \ {0, 1, ..., p - 1 \}, where$ $p$ - prime. I.e

$y ^ 2 \ mod \ p = x ^ 3 + ax + b \ (mod \ p)$

All of these properties (addition, multiplication, point at infinity) for such a function remain valid, although if you try to draw this function, it will only resemble a familiar elliptic curve remotely (at best). And the concept of “tangent to a function at a point” generally loses all meaning, but that's okay. Here is an example of a function $y ^ 2 = x ^ 3 + 7$ for $p = 17$ :

elliptic_curve_over_17

But for $p = 59$ , there is generally an almost chaotic set of points. The only thing that still reminds of the origin of this graph is the symmetry about the axis $X$ .

elliptic_curve_59

PS If you are interested, as in the case of a curve above a finite field, calculate the coordinates of a point $R (x_3, y_3)$ , knowing the coordinates $P (x_1, y_1)$ and $Q (x_2, y_2)$ - you can scroll through“An Introduction to Bitcoin, Elliptic Curves and the Mathematics of ECDSA” by N. Mistry , everything is detailed there, it’s enough to know math at the 8th grade level.

PPS In case my examples did not satisfy your inquiring mind, here is a site for drawing curves of all sorts, experiment.

SECP256k1

Returning to Bitcoin, it uses the SECP256k1 curve . It has the form $y ^ 2 = x ^ 3 + 7$ and is considered above the field $F_p$ , where $p$ is a very large prime number, namely $2 ^ {256} - 2 ^ {32} - 2 ^ {9} - 2 ^ {8} - 2 ^ {7} - 2 ^ {6} - 2 ^ {4} - 1$ .

The so-called base point is also defined for SECP256k1 , it is also the generator point - it is just a point, usually indicated $G$ , lying on this curve. It is needed to create a public key, which will be described below.

A simple example: using Python, check if the point of the $G (x, y)$ curve belongs to SECP256k1

>>> p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
>>> y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
>>> (x ** 3 + 7) % p == y**2 % p
True

Digital signature

Electronic signature (EDS), Electronic digital signature (EDS) - the details of an electronic document obtained as a result of cryptographic conversion of information using a private signature key and allowing to verify the absence of information distortion in an electronic document from the moment the signature was generated (integrity), the signature belongs to the owner of the key certificate signatures (authorship), and in case of successful verification confirm the fact of signing an electronic document (non-repudiation) - Wikipedia

The general idea is this: Alice wants to transfer 1 BTC to Bob. To do this, she creates a message like:

{
    "from" : 1FXySbm7jpJfHEJRjSNPPUqnpRTcSuS8aN, // Alice's address
    "to" : 1Eqm3z1yu6D4Y1c1LXKqReqo1gvZNrmfvN, // Bob's address
    "amount" : 1 // Send 1 BTC
}

Then Alice takes her private key (for now, you can assume that this is a number known only to Alice), a message hash, and a view function $sign \ _text (private \ _key, text)$ . At the output, she receives the signature of her message - in the case of ECDSA it will be a pair of integers, for other algorithms the signature may look different. After that, she sends all network participants an initial message, signature and her public key.

As a result, each Vasya will be able to take this trinity, a view function, $validate \ _signature (public \ _key, signature, text)$ and check whether the owner of the private key actually signed this message or not. And if everyone inside the network knows what $public \ _key$ belongs to Alice, then you can understand whether she sent the money or if someone is trying to do it on her behalf.

digital_signature_scheme

Moreover, suppose that there was a person standing between Alice and the rest of the network. Let him intercept Alice's message and change something in it, literally 1 bit out of a billion. But even in this case, checking the signature for validity $validate \ _signature (public \ _key, signature, text ')$ will show that the message has been changed.

This is a very important feature for Bitcoin, because the network is distributed . We cannot know in advance who our transaction will get with the demand to transfer 1000 BTC. But he will not be able to change it (for example, indicate his address as the recipient), because the transaction is signed by your private key, and the rest of the network participants will immediately understand that something is wrong here.

AHTUNG!In fact, the process is quite different from the above. Here I just showed on my fingers what an electronic digital signature is and why it is needed. The real algorithm is described in the chapter “Bitcoin in a nutshell - Transactions” .

Private key

A private key is a fairly general term and various types of private keys can be used in various electronic signature algorithms.

As you may have noticed, Bitcoin uses the ECDSA algorithm - in its case, the private key is some kind of 256-bit integer, that is, the most common integer from $1$ to $2 ^ {256}$ . Technically, even the number 123456 will be a valid private key, but very soon you will find out that your coins “belong” to you right up to the moment the attacker has your private key, and values like 123456 are very easy to find.

It is important to note that today it is impossible to sort through all the keys due to the fact that $2 ^ {256}$ this is a fantastically large number.

We will try to imagine it: according to this article , there are a little fewer $10 ^ {22}$ grains of sand on the whole Earth . We will use that $2 ^ {10} \ approx10 ^ {3}$ , that is, $10 ^ {22} \ approx2 ^ {80}$ grains of sand. And all the addresses we have $2 ^ {256}$ , approximately ${2 ^ {80}} ^ 3$ .

So, we can take all the sand on Earth, turn every grain of sand into a new Earth, in the resulting pile of planets, turn every grain of sand on every planet into a new Earth, and the total number of grains of sand will still be orders of magnitude less than the number of possible private keys.

For the same reason, when creating a private key, most Bitcoin clients simply take 256 random bits - the probability of collision is extremely small.

Python

>>> import random
>>> private_key = ''.join(['%x' % random.randrange(16) for x in range(0, 64)])
>>> private_key
'9ceb87fc34ec40408fd8ab3fa81a93f7b4ebd40bba7811ebef7cbc80252a9815'
>>> # or
>>> import os
>>> private_key = os.urandom(32).encode('hex')
>>> private_key
'0a56184c7a383d8bcce0c78e6e7a4b4b161b2f80a126caa48bde823a4625521f'

Python, ECDSA

>>> import binascii
>>> import ecdsa # sudo pip install ecdsa
>>> private_key = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)
>>> binascii.hexlify(private_key.to_string()).decode('ascii').upper()
u'CE47C04A097522D33B4B003B25DD7E8D7945EA52FA8931FD9AA55B315A39DC62'

Bitcoin-cli

$ bitcoin-cli getnewaddress
14RVpC4su4PzSafjCKVWP2YBHv3f6zNf6U
$ bitcoin-cli dumpprivkey 14RVpC4su4PzSafjCKVWP2YBHv3f6zNf6U
L3SPdkFWMnFyDGyV3vkCjroGi4zfD59Wsc5CHdB1LirjN6s2vii9

Public key

Let $k$ - our private key, $G$ - base point, then the public key $K = G * k$ . That is, in fact, the public key is a certain point lying on the curve SECP256k1.

Two important nuances. First, it is easy to see that the operation of obtaining a public key is uniquely determined, that is, a single private key always corresponds to a single public key. Secondly, the reverse operation is computationally difficult and, in the general case, obtaining a private key from a public one is possible only by exhaustive search of the first.

Below you will find out that exactly the same connection exists between the public key and the address, but the whole point is that the hash functions are irreversible.

keys_to_address

Python, ECDSA

>>> import binascii
>>> import ecdsa
>>> private_key = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)
>>> public_key = private_key.get_verifying_key()
>>> binascii.hexlify(public_key.to_string()).decode('ascii').upper()
u'D5C08F1BFC9C26A5D18FE9254E7923DEBBD34AFB92AC23ABFC6388D2659446C1F04CCDEBB677EAABFED9294663EE79D71B57CA6A6B76BC47E6F8670FE759D746'

C ++, libbitcoin

#include 
#include 
int main() {
    // Private key
    bc::ec_secret secret = bc::decode_hash(
    "038109007313a5807b2eccc082c8c3fbb988a973cacf1a7df9ce725c31b14776");
    // Get public key
    bc::ec_point public_key = bc::secret_to_public_key(secret);
    std::cout << "Public key: " << bc::encode_hex(public_key) << std::endl;
}

To compile and run, we use (pre-installing libbitcoin):

$ g++ -o public_key  $$(pkg-config --cflags --libs libbitcoin)
$ ./public_key
Public key: 0202a406624211f2abbdc68da3df929f938c3399dd79fac1b51b0e4ad1d26a47aa

You can see that the formats of the public keys in the first and second examples are different (at least in length), I will discuss this in more detail below.

Formats & address

Base58Check encoding

This encoding will be met by us constantly throughout the book, so you should understand how it works and why it is needed at all.

Its essence is to write down the sequence of bytes in the most readable format as briefly as possible and at the same time make the probability of possible typos even less. I think you yourself understand that in the case of Bitcoin, security is never superfluous. One wrong character and money will go to the address, keys to which most likely no one will ever find. Here is a comment on this encoding from in base58.h :

// Why base-58 instead of standard base-64 encoding?
// - Don't want 0OIl characters that look the same in some fonts and
//      could be used to create visually identical looking account numbers.
// - A string with non-alphanumeric characters is not as easily accepted as an account number.
// - E-mail usually won't line-break if there's no punctuation to break at.
// - Doubleclicking selects the whole number as one word if it's all alphanumeric.

The brevity of recording is easiest to implement using the fairly common Base64 encoding , that is, using the base 64 number system, where numbers 0,1,...,9, letters a-zand A-Zare used for writing - this gives 62 characters, the remaining two can be anything, depending on the implementation.

The first difference with Base58Check is that characters are removed 0,O,l,Iin case someone decides to mix them up. It turns out 58 characters, you can check

b58 = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
def base58encode(n):
    result = ''
    while n > 0:
        result = b58[n%58] + result
        n /= 58
    return result
# print "Base58 encode for '123123':", base58encode(123123)
# # Base58 encode for '123123': dbp

The second difference is the same check . At the end of the line, checksum is added again - the first 4 bytes SHA256(SHA256(str)). Well, you also need to add as many units to the beginning as there were leading zeros before the encoding in base58, this is already a technical matter.

import hashlib
def base58encode(n):
    b58 = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
    result = ''
    while n > 0:
        result = b58[n % 58] + result
        n /= 58
    return result
# Will be used to decode raw bytes and then encode them to the base58
def base256decode(s):
    result = 0
    for c in s:
        result = result * 256 + ord(c)
    return result
def countLeadingZeroes(s):
    count = 0
    for c in s:
        if c == '\0':
            count += 1
        else:
            break
    return count
def base58CheckEncode(prefix, payload):
    s = chr(prefix) + payload
    checksum = hashlib.sha256(hashlib.sha256(s).digest()).digest()[0:4]
    result = s + checksum
    return '1' * countLeadingZeroes(result) + base58encode(base256decode(result))

Private key formats

The most obvious way to store a private key is to write 256 bits as a bunch of zeros and ones. But, probably, any technically competent person understands that it will be much easier to present the same sequence in the form of 32 bytes, where each byte corresponds to two characters in a hexadecimal notation. Let me remind you that in this case, numbers 0,1,...,9and letters are used A,B,C,D,E,F. I used this format in the examples above, for beauty it is sometimes sometimes separated by spaces.

E9 87 3D 79 C6 D8 7D C0 FB 6A 57 78 63 33 89 F4 45 32 13 30 3D A6 1F 20 BD 67 FC 23 3A A3 32 62

Another more advanced format is WIF ( Wallet Import Format ). It is built quite simply:

Take a private key, for example 0C28FCA386C7A227600B2FE50B7CAE11EC86D3BF1FBE471BE89827E19D72AA1D
We write it to Base58Check with a prefix 0x80. All.

private_key = '0a56184c7a383d8bcce0c78e6e7a4b4b161b2f80a126caa48bde823a4625521f'
def privateKeyToWif(key_hex):
    return base58CheckEncode(0x80, key_hex.decode('hex'))
# print "Private key in WIF format:", privateKeyToWif(private_key)
# # Private key in WIF format: 5HtqcFguVHA22E3bcjJR2p4HHMEGnEXxVL5hnxmPQvRedSQSuT4

Public key formats

Just in case, let me remind you that the public key is just a point on the line SECP256k1. The first and most common variant of its recording is an uncompressed format, 32 bytes each for X and Y coordinates. To avoid confusion, the prefix of 0x04that 65 bytes is also used.

import ecdsa
private_key = '0a56184c7a383d8bcce0c78e6e7a4b4b161b2f80a126caa48bde823a4625521f'
def privateKeyToPublicKey(s):
    sk = ecdsa.SigningKey.from_string(s.decode('hex'), curve=ecdsa.SECP256k1)
    vk = sk.verifying_key
    return ('\04' + sk.verifying_key.to_string()).encode('hex')
uncompressed_public_key = privateKeyToPublicKey(private_key)
# print "Uncompressed public key: {}, size: {}".format(uncompressed_public_key, len(uncompressed_public_key) / 2)
# # Uncompressed public key: 045fbbe96332b2fc2bcc1b6a267678785401ee3b75674e061ca3616bbb66777b4f946bdd2a6a8ce419eacc5d05718bd718dc8d90c497cee74f5994681af0a1f842, size: 65

However, as the name suggests, this is not the best way to store a public key.

You will be surprised, but the second format is called compressed . Its essence is as follows: a public key is a point on a curve, that is, a pair of numbers satisfying the equation $y ^ 2 \ mod \ p = x ^ 2 + ax + b \ (mod \ p)$ . So it is possible to write down only the X coordinate, and if we need the Y coordinate, we simply solve the equation. Thus, we reduce the size of the public key by almost 50%!

The only caveat is that if the point lies on the curve, then obviously there are two solutions to this equation for its X coordinate (look at the graphs above if in doubt). Usually we would just save the sign for the Y coordinate, but when it comes to functions over a finite field, we need to use the following property:if there are solutions to the equation for the X coordinate, then one of the points will have an even Y coordinate, and the second will have an odd one (again, you can see for yourself).

In the first case, the prefix is used 0x02, in the second - 0x03. Here is an illustration of the process:

Compressed public key

Address

As already mentioned, the address is obtained from the public key in a unique way. Moreover, it is impossible to carry out the reverse operation, since cryptographically strong hash functions are used - RIPEMD160 and SHA256 . Here is the algorithm for translating the public key to the address:

Take a private key, for example 45b0c38fa54766354cf3409d38b873255dfa9ed3407a542ba48eb9cab9dfca67
We will get the public key from it in uncompressed format, in this case 04162ebcd38c90b56fbdb4b0390695afb471c944a6003cb334bbf030a89c42b584f089012beb4842483692bdff9fcab8676fed42c47bffb081001209079bbcb8db.
We believe RIPEMD160(SHA256(public_key))that it turns out5879DB1D96FC29B2A6BDC593E67EDD2C5876F64C
We translate the result into Base58Check with the prefix 0x00- 17JdJpDyu3tB5GD3jwZP784W5KbRdfb84X. This is the address.

def pubKeyToAddr(s):
    ripemd160 = hashlib.new('ripemd160')
    ripemd160.update(hashlib.sha256(s.decode('hex')).digest())
    return base58CheckEncode(0, ripemd160.digest())
def keyToAddr(s):
    return pubKeyToAddr(privateKeyToPublicKey(s))
# print keyToAddr("45b0c38fa54766354cf3409d38b873255dfa9ed3407a542ba48eb9cab9dfca67")
# # '17JdJpDyu3tB5GD3jwZP784W5KbRdfb84X'

Sign & verify

I don’t think you need to know the technical details of exactly how ECDSA signs and checks messages, anyway you will use ready-made libraries everywhere. The main thing is that you have a common understanding of why this is necessary, but if you are still interested, look through the Layman's Guide to Elliptic Curve Digital Signatures , there is a beautiful visualization of the whole process below, you can try it yourself.

That's it for me, the next chapter: Bitcoin in a nutshell - Transaction .

Links

Tags:

Bitcoin in a nutshell - Cryptography

Book

Table of content

Introduction

Elliptic curve

Elliptic curve over a finite field

SECP256k1

Digital signature

Private key

Python

Python, ECDSA

Bitcoin-cli

Public key

Python, ECDSA

C ++, libbitcoin

Formats & address

Base58Check encoding

Private key formats

Public key formats

Address

Sign & verify

Links

Also popular now: