Bitcoin in a nutshell — Cryptography

Одна з причин, чому Bitcoin продовжує залучати стільки уваги — це його виняткова «математичность». Сатоши Накамото вдалося створити систему, яка здатна функціонувати при повній відсутності довіри між її учасниками. Всі взаємодії засновані на суровій математики, ніякого людського чинника — ось у чому була революційність ідеї, а не в одноранговій мережі, як багато хто думає. Тому першу главу я вирішив присвятити саме математичним основам Bitcoin.

Нижче я спробую пояснити вам самі базові речі — еліптичні криві, ECC, приватні / публічні ключі і так далі. По можливості я буду ілюструвати свої слова прикладами коду, переважно на Python 2.7, якщо щось незрозуміло — запитуйте в коментарях.

intro


Table of content
  1. Вступ
  2. Elliptic curve
  3. Digital signature
  4. Private key
  5. Public key
  6. Formats & address
  7. Sign
  8. Verify
  9. Formats
  10. Links
Вступ
Як я вже сказав вище, криптографія — це фундаментальна частина Bitcoin. Без неї взагалі б нічого не запрацювало, тому починати потрібно саме звідси.

В Bitcoin використовується так звана криптографія на еліптичних кривих (Elliptic curve cryptography, ECC). Вона заснована на деякій особливої функції — еліптичної кривої (не плутати з еліпсом). Що це за функція і чим вона так примітна я розповім далі.

Elliptic curve
Еліптична крива над полем K— неособая кубічна крива на проективної площині над {\hat {K}}(алгебраїчним замиканням поля K), задається рівнянням 3-го ступеня з коефіцієнтами з поля Kі «точкою на нескінченності» — Wikipedia
Якщо на пальцях, то еліптична крива — це зовні досить проста функція, як правило, записана у вигляді так званої форми Вейєрштрасса: y^{2}=x^{3}+ax+b

В залежності від значень параметрів ab, графік даної функції може виглядати по різному:

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()

Якщо вірити вікі, то вперше ця функція засвітилася ще в працях Діофанта, а пізніше, в 17 столітті, їй зацікавився сам Ньютон. Його дослідження багато в чому призвели до формул додавання точок еліптичної кривої, з якими ми зараз познайомимося. Тут і надалі ми будемо розглядати деяку еліптичну криву \alpha.

Нехай є дві точки P, Q \in \alpha. Їх сумою називається точка R \in \alpha, яка в найпростішому випадку визначається наступним чином: проведемо пряму через PQ— вона перетне криву \alphaв єдиній точці, назвемо її -R. Помінявши yкоординату точки -Rна протилежну за знаком, ми отримаємо точку R, яку і будемо називати сумою PQ, P + Q = R.

ellitic_curve_addiction

Вважаю за необхідне зазначити, що ми саме вводимо таку операцію додавання — якщо ви будете складати точки в звичному розумінні, тобто складаючи відповідні координати, то отримаєте зовсім іншу точку R' (x_1 + x_2, y_1 + y_2), яка, швидше за все, не має нічого спільного з Rабо -Rі взагалі не лежить на кривій \alpha.

Найкмітливіші вже задалися питанням — а що буде, якщо провести пряму через дві точки, що мають координати виду P (a, b)Q (a, -b), тобто пряма, що проходить через них, буде паралельна осі ординат (третій кадр на картинці нижче).

elliptic_curve_parallel

Нескладно побачити, що в цьому випадку відсутній третє перетин з кривою \alpha, яке ми називали -R. Для того, щоб уникнути цього казусу, введемо так звану крапку в нескінченності (point of infinity), обозначаемую зазвичай Oабо просто , як на картинці. І будемо говорити, що в разі відсутності перетину P + Q = O.

Особливий інтерес для нас представляє випадок, коли ми хочемо скласти точку саму з собою (2 кадр, точка Q). У цьому випадку просто проведемо дотичну до точки Qі відобразимо отриману точку перетину щодо y.

Тепер, легким рухом руки можна ввести операцію множення точки на якесь \mathbb{N}кількість. У результаті одержимо нову точку K = G*k, тобто K = G + G + ... + G \ kразів. З картинкою все має стати зрозуміло:

Elliptic curve multiplication

Elliptic curve over a finite field

ECC використовується точно така ж крива, тільки розглянута над деяким кінцевим полем {F} _{p}=\mathbb{Z} / \mathbb{Z}_p = \{0, 1, ..., p - 1\}, деp— просте число. Тобто

y^2\ mod\ p = x^2 + ax + b \ (mod\ p)
Всі названі властивості (додавання, множення, точка в нескінченності) для такої функції залишаються в силі, хоча, якщо спробувати намалювати цю функцію, то нагадувати звичну еліптичну криву вона буде лише віддалено (в кращому випадку). А поняття «дотичної до функції в точці» взагалі втрачає всякий сенс, але це нічого страшного. Ось приклад функції y^2 = x^3 + 7p=17:

elliptic_curve_over_17

А ось для p=59, тут взагалі майже хаотичний набір точок. Єдине, що все ще нагадує про походження цього графіка, так це симетрія відносно осі X.

elliptic_curve_59

p.s. Якщо вам цікаво, як у випадку з кривою над кінцевим полем обчислити координати точки R (x_3, y_3), знаючи координати P(x_1, y_1)Q(x_2, y_2)— можете погортати «An Introduction to Bitcoin, Elliptic Curves and the Mathematics of ECDSA» by N. Mistry, там все докладно розписано, достатньо знати математику на рівні 8 класу.

P. P. S. На випадок, якщо мої приклади не задовольнили ваш допитливий розум, ось сайт для малювання кривих всіх сортів, поекспериментуйте.

SECP256k1

Повертаючись до Bitcoin, в ньому використовується крива SECP256k1. Вона має вигляд y^2 = x^3 + 7і розглядається над полем F_p, де p— дуже велике просте число, а саме 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1.

Так само для SECP256k1 визначена так звана base point, вона ж generator point — це просто точка, як правило, позначається G, що лежить на даній кривій. Вона потрібна для створення публічного ключа, про який буде розказано нижче.

Простий приклад: використовуючи Python, перевіримо, чи належить точка G (x, y)кривий SECP256k1

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

Digital signature
Електронний підпис (ЕП), Електронний цифровий підпис (ЕЦП) — реквізит електронного документа, отриманий в результаті криптографічного перетворення інформації з використанням закритого ключа підпису, що дозволяє перевірити відсутність спотворення інформації в електронному документі з моменту формування підпису (цілісність), належність підпису власника сертифіката ключа підпису (авторство), а в разі успішної перевірки підтвердити факт підписання електронного документа (неспростовності) — Wikipedia
Загальна ідея така: Аліса хоче перевести 1 BTC Бобу. Для цього вона створює повідомлення типу:

{
"з" : 1FXySbm7jpJfHEJRjSNPPUqnpRTcSuS8an, // alice's address
"to" : 1Eqm3z1yu6D4Y1c1LXKqReqo1gvZNrmfvn, // bob's address
"amount" : 1 // Send 1 BTC
}


Потім Аліса бере свій приватний ключ (поки що можете вважати, що це число, відоме тільки Алісі), хеш повідомлення і функцію виду sign\_text(private\_key, text). На виході вона отримує підпис свого повідомлення — у разі ECDSA це буде пара цілих чисел, для інших алгоритмів підпис може виглядати по іншому. Після цього вона розсилає всім учасникам мережі вихідне повідомлення, підпис і свій публічний ключ.

В результаті, кожен Вася при бажанні зможе взяти цю трійцю, функцію виду validate\_signature(public\_key, signature, text)і перевірити, чи дійсно власник приватного ключа підписував це повідомлення чи ні. А якщо всередині мережі всі знають, що public\_keyналежить Алісі, то можна зрозуміти, відправила ці гроші вона або ж хто-то намагається зробити це від її імені.

digital_signature_scheme

Більш того, припустимо, що знайшлася людина, що встав між Алісою та іншою мережею. Нехай він перехопив повідомлення Аліси і що-то в ньому змінив, буквально 1 біт з мільярда. Але навіть у цьому випадку перевірка підпису на валідність validate\_signature(public\_key, signature, text')покаже, що повідомлення було змінено.

Це дуже важлива фіча для Bitcoin, бо як мережа розподілена. Ми не можемо заздалегідь знати, до кого потрапить наша транзакція з вимогою перевести 1000 BTC. Але змінити її (наприклад вказати свою адресу з якості одержувача) він не зможе, бо як транзакція підписана вашим приватним ключем, і інші учасники мережі відразу зрозуміють, що тут щось не так.

AHTUNG! насправді процес досить сильно відрізняється від вищеописаного. Тут я просто на пальцях показав, що з себе представляє електронно-цифровий підпис і навіщо вона потрібна. Реальний алгоритм описаний у розділі «Bitcoin in a nutshell — Transactions».

Private key
Приватний ключ — це досить загальний термін і в різних алгоритмах електронного підпису можуть використовуватися різні типи приватних ключів.

Як ви вже могли помітити, в Bitcoin використовується алгоритм ECDSA — в його випадку приватний ключ — це деяке натуральне 256 бітне число, тобто звичайне ціле число від 12^{256}. Технічно, навіть число 123456 буде коректним приватним ключем, але дуже скоро ви дізнаєтеся, що ваші монети «належать» вам рівно до того моменту, як у зловмисника виявиться ваш приватний ключ, а значення типу 123456 дуже легко перебираються.

Важливо відзначити, що на сьогоднішній день перебрати всі ключі неможливо в силу того, що 2^{256}— це фантастично велике число.

Постараємося його уявити: згідно цієї статті, на всій Землі трохи менше 10^{22}піщинок. Скористаємося тим, що 2^{10} ≈ 10^3, 10^{22} ≈ 2^{80}піщинок. А всього адрес у нас 2^{256}, приблизно {2^{80}}^3.

Значить, ми можемо взяти весь пісок на Землі, перетворити кожну піщинку в нову Землю, отриманої купі планет кожну піщинку на кожній планеті знову перетворити в нову Землю, і сумарне число піщинок все одно буде на порядки менше числа можливих приватних ключів.

З цієї ж причини більшість Bitcoin клієнтів при створенні приватного ключа просто беруть 256 випадкових біт — імовірність колізії вкрай мала.

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
Нехай k— наш приватний ключ, G— base point, тоді публічний ключ K=G*k. Тобто, фактично, публічний ключ — це деяка точка, що лежить на кривій SECP256k1.

Два важливих нюанси. По-перше, нескладно бачити, що операція отримання публічного ключа визначена однозначно, тобто конкретного приватного ключа завжди відповідає один єдиний публічний ключ. По-друге, зворотна операція є обчислювально важким і, в загальному випадку, отримати приватний ключ з публічного можна тільки повним перебором першого.

Нижче ви дізнаєтеся, що точно така ж зв'язок існує між публічним ключем і адресою, тільки там вся справа в незворотності хеш-функцій.

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 <bitcoin/bitcoin.hpp>
#include < iostream>

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;
}

Для компіляції і запуску використовуємо (попередньо встановивши libbitcoin):

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

Ви можете бачити, що формати публічних ключів в першому і другому прикладі відрізняються (як мінімум завдовжки), про це я детальніше розповім нижче.

Formats & address

Base58Check encoding

Ця кодування буде зустрічатися нам постійно протягом всієї книги, тому варто розуміти, як вона працює і навіщо вона взагалі потрібна.

Її суть у тому, щоб максимально коротко записати послідовність байт в легкочитаємом форматі і при цьому зробити ймовірність можливих помилок ще менше. Я думаю ви самі розумієте, що в разі Bitcoin безпека зайвою не буває. Один неправильний символ і гроші підуть на адресу, ключів до якого швидше за все ніхто ніколи не знайде. Ось коментар до цієї кодуванні з 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.

Стислість запису найпростіше реалізувати, використовуючи досить поширену кодування Base64, тобто використовуючи систему числення з основою 64, де для запису використовуються цифри
0,1,...,9
, літери
a-z
та
A-Z
— це дає 62 символу, два можуть бути чим завгодно, залежно від реалізації.

Перша відмінність Base58Check в тому, що прибрані символи
0,O,l,I
на випадок, якщо хто-небудь вирішить їх переплутати. Виходить 58 символів, можете перевірити

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

Друга відмінність — це той самий check. В кінець рядка знову додається checksum — перші 4 байти
SHA256(SHA256(str))
. Ну і ще потрібно додати в початок стільки одиниць, скільки провідних нулів було до кодування в base58, це вже справа техніки.

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©
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

Самий очевидний спосіб зберігати приватний ключ — це записати 256 біт у вигляді купи нулів і одиниць. Але, напевно, будь технічно грамотна людина розуміє, що буде сильно простіше уявити ту ж саму послідовність у вигляді 32 байт, де кожному байту відповідає два символи в шістнадцятковій запису. Нагадаю, що в цьому випадку використовуються цифри
0,1,...,9
і букви
A,B,C,D,E,F
. Цей формат я використовував в прикладах вище, для краси його ще іноді поділяють пробілами.

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

Інший більш прогресивний формат — WIF (Wallet Import Format). Будується він досить просто:
  1. Беремо приватний ключ, наприклад
    0C28FCA386C7A227600B2FE50B7CAE11EC86D3BF1FBE471BE89827E19D72AA1D
  2. Записуємо його в Base58Check з префіксом
    0x80
    . Всі.


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

На всяк випадок нагадаю, що публічний ключ — це просто точка на прямій SECP256k1. Перший і найпоширеніший варіант його записи — uncompressed формат, по 32 байти для X і Y координат. Щоб не виникало плутанини, використовується префікс
0x04
і того 65 байт.

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

Однак, як можна здогадатися з назви, це не самий оптимальний спосіб зберігати публічний ключ.

Ви здивуєтеся, але другий формат називається compressed. Суть його в наступному: публічний ключ — це точка на кривій, тобто пара чисел задовольняє рівнянню y^2\ mod\ p = x^2 + ax + b \ (mod\ p). А значить можна записати тільки координату Х і якщо нам знадобиться Y координата — просто вирішуємо рівняння. Тим самим ми зменшуємо розмір публічного ключа майже на 50%!

Єдиний нюанс — якщо точка лежить на кривій, то для її координати Х очевидно існує два рішення такого рівняння (подивіться на графіки вище, якщо сумніваєтеся). Зазвичай ми б просто зберегли знак для Y координати, але коли мова йде про функції над кінцевим полем, то потрібно скористатися наступним властивістю: якщо для Х координати існують рішення рівняння, то одна з точок буде мати парну Y-координату, а друга — непарну (знову ж, можете самі в цьому переконатися).

У першому випадку використовується префікс
0x02
, у другому —
0x03
. Ось ілюстрація процесу:

Compressed public key

Address

Як вже було сказано, адреса виходить з публічного ключа однозначним чином. Більше того, провести зворотну операцію неможливо, так як використовуються криптографічно стійкі хеш функції — RIPEMD160 і SHA256. Ось алгоритм переведення публічного ключа на адресу:
  1. Візьмемо приватний ключ, наприклад
    45b0c38fa54766354cf3409d38b873255dfa9ed3407a542ba48eb9cab9dfca67
  2. Отримаємо з нього публічний ключ uncompressed форматі, в даному випадку це
    04162ebcd38c90b56fbdb4b0390695afb471c944a6003cb334bbf030a89c42b584f089012beb4842483692bdff9fcab8676fed42c47bffb081001209079bbcb8db
    .
  3. Вважаємо
    RIPEMD160(SHA256(public_key))
    , виходить
    5879DB1D96FC29B2A6BDC593E67EDD2C5876F64C
  4. Переводимо результат Base58Check з префіксом
    0x00
    17JdJpDyu3tB5GD3jwZP784W5KbRdfb84x
    . Це і є адреса.


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
Не думаю, що вам обов'язково потрібно знати технічні подробиці того, як саме ECDSA підписує і перевіряє повідомлення, все одно ви скрізь будете користуватися готовими бібліотеками. Головне, щоб у вас було спільне розуміння того, навіщо це потрібно, але якщо вам все-таки цікаво — погортайте Layman's Guide to Elliptic Curve Digital Signatures, там внизу є красива візуалізація всього процесу, можете самі спробувати.

У мене на цьому все, наступна глава: Bitcoin in a nutshell — Transaction.

Links

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.