Математика протоколу Bitcoin

ONE з причин, чому Bitcoin може заплутати новачків, є те, що Технології, що стоїть за ним, переосмислює концепцію власності.

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

Протокол Bitcoin

З Bitcoin справа йде інакше. Самі біткойни не зберігаються ні централізовано, ні локально, тому ONE не є їхнім зберігачем. Вони існують у вигляді записів у розподіленій книзі, яка називається ланцюгом блоків, копії якої спільно використовуються добровільною мережею підключених комп’ютерів. «Володіти» Bitcoin просто означає мати можливість передати контроль над ним комусь іншому, створивши запис про передачу в ланцюжку блоків. Що дає цю здатність? Доступ до ан ECDSA пара закритого та відкритого ключів. Що це означає і як це забезпечує захист Bitcoin?

Давайте заглянемо під капот.

ECDSA це скорочення від Elliptic Curve Digital Signature Algorithm. Це процес, який використовує еліптична крива і а кінцеве поле «підписати» дані таким чином, щоб треті сторони могли перевірити автентичність підпису, в той час як підписувач зберігає виняткову можливість створити підпис. У Bitcoin дані, які підписуються, є транзакцією, яка передає право власності.

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

Але спочатку прискорений курс вивчення еліптичних кривих і скінченних полів.

Еліптичні криві

Еліптична крива представляється алгебраїчно у вигляді рівняння виду:

y2 = x3 + ax + b

для а = 0 і b = 7 (версія, яку використовує Bitcoin), це LOOKS так:

Еліптичні криві мають корисні властивості. Наприклад, невертикальна лінія, що перетинає дві недотичні точки на кривій, завжди перетинатиме третю точку на кривій. Ще одна властивість полягає в тому, що невертикальна лінія, дотична до кривої в ONE точці, перетинатиме точно ONE іншу точку на кривій.

Ми можемо використовувати ці властивості для визначення двох операцій: додавання точок і подвоєння точок.

Додавання балів, P + Q = R, визначається як відображення через вісь x третьої точки перетину Р' на лінії, яка включає П і Q. Зрозуміти це найпростіше за схемою:

Так само подвоєння точки, P + P = R визначається шляхом знаходження прямої, дотичної до точки, яку потрібно подвоїти, П, і взявши відбиття через вісь x точки перетину Р' на кривій отримати Р. Ось приклад того, як це виглядатиме:

Разом ці дві операції використовуються для скалярне множення, R = a P, визначається додаванням точки П собі a разів. Наприклад:

R = 7P

R = P + (P + (P + (P + (P + (P + P)))))

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

R = 7P

R = P + 6P

R = P + 2 (3P)

R = P + 2 (P + 2P)

тут, 7P було розбито на два етапи подвоєння балів і два етапи додавання балів.

Кінцеві поля

Скінченне поле в контексті ECDSA можна розглядати як попередньо визначений діапазон додатних чисел, у межах якого повинен знаходитися кожен обчислення. Будь-яке число за межами цього діапазону «обертається», щоб потрапити в діапазон.

Найпростіший спосіб подумати про це — обчислити залишки, представлені оператором модуля (mod). Наприклад, 9/7 дає 1 із залишком 2:

9 mod 7 = 2

Тут наше скінченне поле дорівнює модулю 7, і всі модифікаційні операції над цим полем дають результат у діапазоні від 0 до 6.

Збираємо це разом

ECDSA використовує еліптичні криві в контексті скінченного поля, що значно змінює їх зовнішній вигляд, але не основні рівняння чи спеціальні властивості. Те саме рівняння, зображене вище, у скінченному полі за модулем 67 LOOKS так:

Тепер це набір точок, у якому всі x і р значення є цілими числами від 0 до 66. Зауважте, що «крива» все ще зберігає свою горизонтальну симетрію.

Додавання та подвоєння балів тепер візуально дещо відрізняються. Лінії, намальовані на цьому графіку, обертатимуться навколо горизонтального та вертикального напрямків, як у грі в астероїди, зберігаючи той самий нахил. Отже, додавання точок (2, 22) і (6, 25) LOOKS так:

Третя точка перетину — (47, 39), а її точка відбиття — (47, 28).

Повернемося до ECDSA та Bitcoin

Такий протокол, як Bitcoin, вибирає набір параметрів для еліптичної кривої та її представлення кінцевого поля, яке є фіксованим для всіх користувачів протоколу. Параметри включають в себе рівняння використовується, PRIME модуль поля, і a базова точка що падає на криву. The порядок базової точки, яка не вибирається незалежно, а є функцією інших параметрів, можна уявити графічно як кількість разів, коли точка може бути додана сама до себе, поки її нахил не стане нескінченним, або вертикальна лінія. Базова точка вибирається таким чином, щоб порядок був великим PRIME числом.

Bitcoin використовує дуже великі числа для базової точки, PRIME модуля та порядку. Насправді всі практичні застосування ECDSA використовують величезні значення. Безпека алгоритму залежить від того, що ці значення є великими, а отже, непрактичними для грубої сили або зворотного проектування.

У випадку з Bitcoin:

Рівняння еліптичної кривої: y2 = x3 + 7

PRIME модуль = 2256 – 232 – 29 – 28 – 27 – 26 – 24 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Базова точка = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Замовлення = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Хто обрав ці цифри і чому? Дуже багато дослідження, і неабияку кількість інтрига, оточує вибір відповідних параметрів. Зрештою, велике, здавалося б, випадкове число може приховувати бекдорний метод реконструкції закритого ключа. Коротко кажучи, ця конкретна реалізація має назву secp256k1 і є частиною сімейства рішень еліптичної кривої над скінченними полями, запропонованих для використання в криптографії.

Приватні та відкриті ключі

Усунувши ці формальності, ми тепер можемо зрозуміти приватні та відкриті ключі та їх взаємозв’язок. Ось у двох словах: в ECDSA приватний ключ — це непередбачувано вибране число між 1 і порядком. Відкритий ключ виходить із закритого ключа шляхом скалярного множення базової точки на кількість разів, що дорівнює значенню закритого ключа. Виражається у вигляді рівняння:

відкритий ключ = закритий ключ * базова точка

Це показує, що максимально можлива кількість закритих ключів (і, отже, Bitcoin адрес) дорівнює порядку.

У безперервному полі ми могли б побудувати дотичну лінію та визначити відкритий ключ на The Graph, але є деякі рівняння які виконують те саме в контексті скінченних полів. Точкове додавання p + q знайти r визначається покомпонентно наступним чином:

c = (qy - py) / (qx - px)

rx = c2 - px - qx

ry = c (px - rx) - py

І подвоєння точки знайти r полягає в наступному:

c = (3px2 + a) / 2py

rx = c2 - 2px

ry = c (px - rx) - py

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

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

Рівняння: y2 = x3 + 7 (тобто a = 0 і b = 7)

PRIME модуль: 67

Базова точка: (2, 22)

Замовлення: 79

Приватний ключ: 2

Спочатку давайте знайдемо відкритий ключ. Оскільки ми вибрали найпростіший приватний ключ із значенням = 2, для цього знадобиться лише одна операція подвоєння точки від базової точки. Розрахунок LOOKS так:

c = (3 * 22 + 0) / (2 * 22) за модулем 67

c = (3 * 4) / (44) mod 67

c = 12 / 44 mod 67

Тут ми повинні зупинитися, щоб BIT помандрувати: як ми виконуємо ділення в контексті кінцевого поля, де результат завжди має бути цілим числом? Ми повинні помножити на обернене значення, яке простір не дозволяє нам визначити тут (ми посилаємося на тут і тут якщо цікаво). У даному випадку ви повинні довіряти нам на даний момент, що:

44-1 = 32

Рухаючись праворуч:

c = 12 * 32 mod 67

c = 384 mod 67

c = 49

rx = (492 - 2 * 2) mod 67

rx = (2401 - 4) mod 67

rx = 2397 mod 67

rx = 52

ry = (49 * (2 - 52) - 22) mod 67

ry = (49 * (-50) - 22) mod 67

ry = (-2450 - 22) mod 67

ry = -2472 mod 67

ry = 7

Таким чином, наш відкритий ключ відповідає пункту (52, 7). Усе це працює для закритого ключа 2!

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

Таким чином, перехід від приватного ключа до відкритого ключа є задумом одностороннім.

Як і закритий ключ, відкритий ключ зазвичай представлений шістнадцятковим рядком. Але зачекайте, як нам дістатися від точки на площині, описаної двома числами, до одного числа? У нестисненому відкритому ключі два 256- BIT числа, що представляють x і р координати просто склеєні в ONE довгий рядок. Ми також можемо скористатися перевагами симетрії еліптичної кривої для створення стисненого відкритого ключа, зберігаючи лише x значення та зауваження, на якій половині кривої знаходиться точка. З цієї часткової інформації ми можемо відновити обидві координати.

Підпис даних закритим ключем

Тепер, коли у нас є пара закритого та відкритого ключів, давайте підпишемо деякі дані!

Дані можуть бути будь-якої довжини. Звичайним першим кроком є ​​хешування даних для генерації числа, яке містить таку саму кількість бітів (256), що й порядок кривої. Тут, задля простоти, ми пропустимо етап хешування та просто підпишемо необроблені дані з. Ми подзвонимо Г базова точка, порядок і d закритий ключ. Рецепт підписання такий:

• Виберіть деяке ціле число k від 1 до n - 1.
• Обчисліть точку (x, y) = k * G, використовуючи скалярне множення.
• Знайти r = x mod n. Якщо r = 0, поверніться до кроку 1.
• Знайдіть s = (z + r * d) / k mod n. Якщо s = 0, поверніться до кроку 1.
• Підписом є пара (r, s)

Нагадуємо, що на кроці 4, якщо числа дають дріб (а в реальному житті майже завжди), чисельник слід помножити на обернений знаменник. На кроці 1 важливо, щоб k не повторюватися в різних підписах і щоб його не могла вгадати третя сторона. тобто k має бути або випадковим, або згенерованим детермінованими засобами, які зберігаються в Secret від третіх сторін. Інакше було б можливо витягнути закритий ключ із кроку 4, оскільки, з, r, k і всі відомі. Ви можете прочитати про минулий експлойт такого типу тут.

Давайте виберемо наші дані як число 17 і Соціальні мережі рецепт. Наші змінні:

z = 17 (дані)

n = 79 (порядок)

G = (2, 22) (базова точка)

d = 2 (приватний ключ)

• Виберіть випадкове число:

k = rand(1, n - 1)

k = ранд(1, 79 - 1)

k = 3 (це справді випадково? Добре, ви нас зрозуміли, але це спростить наш приклад!)

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

(x, y) = 3G

(x, y) = G + 2G

(x, y) = (2, 22) + (52, 7)

(x, y) = (62, 63)

х = 62

y = 63

1. знайти r:

r = x mod n

r = 62 mod 79

r = 62

1. знайти:

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 47 mod 79

s = 47

Зверніть увагу, що вище ми змогли поділити на 3, оскільки результат був цілим числом. У реальних випадках ми б використовували зворотне значення k (як і раніше, ми приховали деякі криваві деталі, обчисливши це в іншому місці):

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 141 * 3-1 mod 79

s = 141 * 53 mod 79

s = 7473 за модулем 79

s = 47

1. Наш підпис - це пара (r, ) = (62, 47).

Як і у випадку з закритим і відкритим ключами, цей підпис зазвичай представлено шістнадцятковим рядком.

Перевірка підпису відкритим ключем

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

с Q будучи відкритим ключем та іншими змінними, визначеними як і раніше, кроки для перевірки підпису такі:

• Переконайтеся, що r і s знаходяться між 1 і n - 1.
• Обчисліть w = s-1 mod n
• Обчисліть u = z * w mod n
• Обчисліть v = r * w mod n
• Обчисліть точку (x, y) = uG + vQ
• Переконайтеся, що r = x mod n. Підпис недійсний, якщо це не так.

Чому ці кроки працюють? Ми пропускаємо доказ, але ви можете прочитати деталі тут. Давайте Соціальні мережі , як це працює, за рецептом. Ще раз наші змінні:

z = 17 (дані)

(r, s) = (62, 47) (підпис)

n = 79 (порядок)

G = (2, 22) (базова точка)

Q = (52, 7) (відкритий ключ)

• Перевірте це r і знаходяться між 1 і - 1. Перевірте і перевірте.

r: 1 <= 62 < 79

s: 1 <= 47 < 79

1. Обчислити w:

w = s-1 mod n

w = 47-1 mod 79

w = 37

1. Обчислити u:

u = zw mod n

u = 17 * 37 mod 79

u = 629 за модулем 79

u = 76

1. Обчислити v:

v = rw mod n

v = 62 * 37 mod 79

v = 2294 mod 79

v = 3

1. Обчисліть точку (x, р):

(x, y) = uG + vQ

Давайте розберемо подвоєння точки та додавання uG і vQ окремо.

uG = 76G

uG = 2(38G)

uG = 2( 2(19G) )

uG = 2( 2(G + 18G) )

uG = 2( 2(G + 2(9G) ) )

uG = 2( 2(G + 2(G + 8G) ) )

uG = 2( 2(G + 2(G + 2(4G) ) ) )

uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

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

Ми працюємо зсередини назовні:

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )

uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )

uG = 2( 2(G + 2(G + 2(25, 17) ) ) )

uG = 2( 2(G + 2( (2, 22) + (21, 42) ) ) )

uG = 2( 2(G + 2(13, 44) ) )

uG = 2( 2( (2, 22) + (66, 26) ) )

uG = 2( 2(38, 26) )

uG = 2(27, 40)

uG = (62, 4)

А тепер для vQ:

vQ = 3Q

vQ = Q + 2Q

vQ = Q + 2(52, 7)

vQ = (52, 7) + (25, 17)

vQ = (11, 20)

З’єднавши їх разом:

(x, y) = uG + vQ

(x, y) = (62, 4) + (11, 20)

(x, y) = (62, 63)

Зрозуміло, що крок 5 – це основна частина роботи. Для останнього кроку,

1. Переконайтеся, що r = x mod n

r = x mod n

62 = 62 mod 79

62 = 62

Наш підпис дійсний!

Висновок

Що ми щойно дізналися для тих із вас, хто бачив усі рівняння та перескочив до кінця?

Ми розвинули певну інтуїцію про глибокий математичний зв’язок, який існує між відкритим і закритим ключами. Ми бачили, як навіть у найпростіших прикладах математика, що стоїть за підписами та перевіркою, швидко ускладнюється, і ми можемо оцінити величезну складність, яка має бути задіяна, коли задіяні параметри є 256- BIT числами. Ми побачили, як розумне застосування найпростіших математичних процедур може створити односторонні функції «люка», необхідні для збереження інформаційної асиметрії, яка визначає право власності на Bitcoin. І ми знову знайшли впевненість у надійності системи за умови, що ми ретельно зберігаємо знання наших особистих ключів.

Іншими словами, саме тому прийнято говорити, що Bitcoin «підкріплений математикою».

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

Ця стаття була перепублікована тут з дозволу автора. Спочатку опубліковано на Chain.com. Автор висловлює особливу подяку Стівену Фелпсу за допомогу в написанні цієї статті.

Ерік Риквальдер — інженер-програміст і ONE із Chain.comзасновники.