Математика, лежащая в основе протокола Bitcoin

ONE из причин, по которой Bitcoin может сбивать с толку новичков, заключается в том, что лежащая в его основе Технологии меняет само понятие собственности.

Владеть чем-либо в традиционном смысле, будь то дом или сумма денег, означает либо иметь личное владение вещью, либо передать ее на хранение доверенному лицу, например банку.

Протокол Bitcoin

С Bitcoin дело обстоит иначе. Сами биткойны не хранятся ни централизованно, ни локально, и поэтому ни ONE организация не является их хранителем. Они существуют в виде записей в распределенном реестре, называемом цепочкой блоков, копии которого совместно используются добровольной сетью подключенных компьютеров. «Владеть» Bitcoin просто означает иметь возможность передать контроль над ним кому-то другому, создав запись о передаче в цепочке блоков. Что дает эту возможность? Доступ к ECDSA пара закрытых и открытых ключей. Что это значит и как это защищает Bitcoin?

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

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

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

Но сначала — краткий курс по эллиптическим кривым и конечным полям.

Эллиптические кривые

Эллиптическая кривая алгебраически представляется в виде уравнения вида:

у2 = х3 + ах + б

Для а = 0 и б = 7 (версия, используемая Bitcoin), LOOKS так:

Эллиптические кривые обладают полезными свойствами. Например, невертикальная линия, пересекающая две некасательные точки на кривой, всегда пересечет третью точку на кривой. Еще одно свойство заключается в том, что невертикальная линия, касательная к кривой в ONE точке, пересечет ровно ONE другую точку на кривой.

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

Добавление точек,П + Q = Р,определяется как отражение относительно оси x третьей точки пересеченияР’на линии, которая включает в себяП и В. Проще всего это понять с помощью диаграммы:

Сходным образом,удвоение точек,П + П = Ропределяется путем нахождения касательной к точке, которую нужно удвоить,П, и принимая отражение через ось x точки пересеченияР’на кривой, чтобы получитьР. Вот пример того, как это будет выглядеть:

Вместе эти две операции используются дляскалярное умножение,Р = Р,определяется добавлением точкиПсебеараз. Например:

Р = 7П

Р = П + (П + (П + (П + (П + (П + П)))))

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

Р = 7П

Р = П + 6П

Р = П + 2 (3П)

Р = П + 2 (П + 2П)

Здесь, 7Пбыл разбит на два шага удвоения точек и два шага сложения точек.

Конечные поля

Конечное поле в контексте ECDSA можно рассматривать как предопределенный диапазон положительных чисел, в который должно попадать каждое вычисление. Любое число за пределами этого диапазона «оборачивает» так, чтобы попасть в этот диапазон.

Самый простой способ думать об этом — вычислить остатки, представленные оператором модуля (mod). Например, 9/7 дает 1 с остатком 2:

9 мод 7 = 2

Здесь наше конечное поле равно модулю 7, и все операции по модулю над этим полем дают результат, попадающий в диапазон от 0 до 6.

Собираем все вместе

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

Теперь это набор точек, в которых всех и узначения — целые числа от 0 до 66. Обратите внимание, что «кривая» по-прежнему сохраняет свою горизонтальную симметрию.

Добавление и удвоение точек теперь немного отличаются визуально. Линии, нарисованные на этом графике, будут огибать горизонтальное и вертикальное направления, как в игре Asteroids, сохраняя тот же наклон. Таким образом, добавление точек (2, 22) и (6, 25) LOOKS так:

Третья точка пересечения — (47, 39), а ее точка отражения — (47, 28).

Вернуться к ECDSA и Bitcoin

Протокол, такой как Bitcoin, выбирает набор параметров для эллиптической кривой и ее конечного поля представления, который фиксирован для всех пользователей протокола. Параметры включают уравнениеиспользованный,PRIME по модулюполя, ибазовая точкакоторый попадает на кривую.заказ базовой точки, которая не выбирается независимо, а является функцией других параметров, можно графически представить как количество раз, которое точка может быть добавлена ​​к себе, пока ее наклон не станет бесконечным, или вертикальной линией. Базовая точка выбирается таким образом, чтобы порядок был большим 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, но есть некоторые уравнениякоторые выполняют то же самое в контексте конечных полей. Точечное сложениеп + днайтигопределяется покомпонентно следующим образом:

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

rx = c2 - px - qx

ry = c (px - rx) - py

И точка удвоения, чтобы найтигвыглядит следующим образом:

с = (3px2 + а) / 2py

rx = c2 - 2px

ry = c (px - rx) - py

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

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

Уравнение: y2 = x3 + 7 (то есть a = 0 и b = 7)

PRIME модуль: 67

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

Заказ: 79

Закрытый ключ: 2

Сначала найдем открытый ключ. Поскольку мы выбрали простейший возможный закрытый ключ со значением = 2, то потребуется только одна операция удвоения точки от базовой точки. Расчет LOOKS так:

с = (3 * 22 + 0) / (2 * 22) по модулю 67

с = (3 * 4) / (44) мод 67

с = 12 / 44 мод 67

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

44-1 = 32

Двигаемся дальше:

с = 12 * 32 мод 67

с = 384 мод 67

с = 49

гх = (492 - 2 * 2) мод 67

гх = (2401 - 4) мод 67

rx = 2397 mod 67

рх = 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 числа, представляющих х и укоординаты просто склеены в ONE длинную строку. Мы также можем воспользоваться симметрией эллиптической кривой для создания сжатого открытого ключа, сохраняя только хзначение и отметив, на какой половине кривой находится точка. Из этой частичной информации мы можем восстановить обе координаты.

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

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

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

• Выберите некоторое целое число 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 важно, чтобыкне повторяться в разных подписях и не поддаваться угадыванию третьим лицом. То есть,к должны быть либо случайными, либо сгенерированными детерминированными средствами, которые хранятся в Secret от третьих лиц. В противном случае можно было бы извлечь закрытый ключ из шага 4, поскольку , з,г,ки все известны. Вы можете прочитать о прошлом подвиге этого типаздесь.

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

z = 17 (данные)

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

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

d = 2 (закрытый ключ)

• Выберите случайное число:

k = rand(1, n - 1)

к = слэнд(1, 79 - 1)

k = 3 (это действительно случайно? Хорошо, вы нас поняли, но это упростит наш пример!)

1. Вычислить точку. Это делается так же, как и определение открытого ключа, но для краткости опустим арифметику сложения и удвоения точек.

(х, у) = 3G

(х, у) = Г + 2Г

(х, у) = (2, 22) + (52, 7)

(х, у) = (62, 63)

х = 62

у = 63

1. Находить г:

г = х мод n

г = 62 мод 79

г = 62

1. Находить :

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

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

с = (17 + 124) / 3 мод 79

с = 141 / 3 мод 79

с = 47 мод 79

с = 47

Обратите внимание, что выше мы смогли разделить на 3, так как результат был целым числом. В реальных случаях мы бы использовали обратноек(как и прежде, мы скрыли некоторые кровавые подробности, вычислив их в другом месте):

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

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

с = (17 + 124) / 3 мод 79

с = 141 / 3 мод 79

с = 141 * 3-1 мод 79

с = 141 * 53 мод 79

с = 7473 мод 79

с = 47

1. Наша подпись — это пара (г, ) = (62, 47).

Как и в случае с закрытым и открытым ключами, эта подпись обычно представлена шестнадцатеричной строкой.

Проверка подписи открытым ключом

Теперь у нас есть некоторые данные и подпись для этих данных. Третья сторона, у которой есть наш открытый ключ, может получить наши данные и подпись и проверить, что мы являемся отправителями. Давайте посмотрим, как это работает.

С Впоскольку открытый ключ и другие переменные определены, как и ранее, шаги для проверки подписи следующие:

• Убедитесь, что 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 (данные)

(р, с) = (62, 47) (подпись)

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

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

Q = (52, 7) (открытый ключ)

• Убедитесь, чтоги находятся в диапазоне от 1 до -1. Проверяйте и проверяйте.

г: 1 <= 62 < 79

с: 1 <= 47 < 79

1. Рассчитатьж:

w = s-1 mod n

ш = 47-1 мод 79

ж = 37

1. Рассчитатьты:

u = zw mod n

и = 17 * 37 мод 79

и = 629 мод 79

у = 76

1. Рассчитатьв:

v = rw mod n

v = 62 * 37 мод 79

v = 2294 мод 79

в = 3

1. Рассчитайте точку (х,у):

(x, y) = uG + vQ

Давайте разберем удвоение и сложение точекмкГ и vQотдельно.

мкГ = 76Г

мкГ = 2(38Г)

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

(х, у) = (62, 4) + (11, 20)

(х, у) = (62, 63)

Очевидно, что шаг 5 — это основная часть работы. Для последнего шага,

1. Убедитесь, что r = x mod n

г = х мод n

62 = 62 мод 79

62 = 62

Наша подпись действительна!

Заключение

Для тех из вас, кто увидел все уравнения и пролистал их до конца, что мы только что узнали?

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

Другими словами, именно поэтому обычно говорят, что Bitcoin «подкреплен математикой».

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

Эта статья была переиздана здесь с разрешения автора. Первоначально опубликованоChain.com. Автор выражает особую благодарность Стивену Фелпсу за помощь в написании статьи.

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