Математика Биткойна: Теория

math-behind-bitcoin-630x376Одна из причин, почему Биткойн многих сбивает с толку, заключается в том, что эта технология пересматривает одну из базовых концепций человеческого общества: понятие собственности.

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

С Биткойном эта простая схема не работает. Сами по себе биткойны не хранятся ни централизованно, ни локально — и поэтому нельзя сказать, кто отвечает за их доверенное хранение. Биткойны существуют лишь как записи в распределенной бухгалтерской книге, называемой блокчейном, копии которой распределены среди добровольной сети подключенных компьютеров. Быть «владельцем» биткойнов просто означает иметь возможность передать контроль над этими записями кому-то еще, зафиксировав факт этой передачи на блокчейне. Что дает вам эту способность? Эксклюзивный доступ к паре ключей ECDSA: секретному и публичному. Хорошо, но что конкретно это означает, и почему это вдруг гарантирует безопасность этих самых биткойнов?

Давайте-ка попробуем заглянуть под капот.

Что это за ECDSA такая?

ECDSA — это акроним для Алгоритма Цифровой Подписи с Эллиптическими Кривыми. Это процесс, который использует эллиптические кривые и конечные поля, чтобы «подписать» данные таким образом, что третьи лица могут легко проверить подлинность подписи, но при этом сам подписывающий оставляет за собой эксклюзивную возможность создавать подписи. В случае Биткойна «данные», которые подписываются — это транзакция, которая передает право собственности на биткойны.

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

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

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

В эллиптических кривых нет ничего сложного. Алгебраически каждая такая кривая может быть представлена как уравнение вида:

y² = x³ + ах + b

Для а = 0 и b = 7 (а это именно та версия, которую использует Биткойн) эта кривая выглядит так:

elliptic-curves

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

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

Для сложения точек, P + Q = R мы проводим через точки P и Q прямую, которая, по свойствам эллиптических кривых, пересекает кривую в некоторой третьей точке R. Затем мы находим точку на кривой, симметричную точке R относительно оси X. Именно эта точка R и будет считаться суммой P и Q. Это легче всего понять, глядя на следующую схему:

point-addition

Это все хорошо, но как бы нам сложить точку саму с собой? Для этого определяется операция удвоения точки, P + P = R. При удвоении мы проводим прямую, касательную к данной эллиптической кривой в точке P, которая, согласно свойствам кривой, должна пересекать ее еще в одной точке R‘. Точка R, симметричная Rотносительно оси X, и будет считаться точкой удвоения P. На графике это выглядит следующим образом:

point-doubling

Эти две операции можно использовать, чтобы определить операцию скалярного умножения, 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 (Р + 2P)

Здесь операция 7P была разбита на два этапа удвоения точек и два сложения точек — в итоге, вместо 7 операций нужно произвести всего четыре.

Собственно, теперь вы знаете об эллиптических кривых все, что о них стоит знать.

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

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

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

9 MOD 7 = 2

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

Скрещиваем кривые с полями

ECDSA использует не просто эллиптические кривые, а эллиптические кривые в контексте конечного поля, что значительно меняет их ​​внешний вид. Причем, меняет его так, что теперь эти самые кривые даже родная мама не узнает. Допустим, та же самая красивая эллиптическая кривая Биткойна, y² = x³ + 7, которая изображена выше, но только определенная на конечном поле по модулю 67, выглядит как такая вот странная крякозябра:

putting-it-together

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

Правда, процесс операций над точками: сложения и удвоения — сейчас будет немного отличаться визуально. «Прямые линии», нарисованные на этом графике, теперь будут оборачиваться «вокруг поля», как только они достигнут магического барьера 67, как в древней аркадной игре «Asteroids», и продолжаться с другого его конца, сохраняя прежний наклон, но со сдвигом. Поэтому сложение точек (2, 22) и (6, 25) в данном дискретном варианте выглядит следующим образом:

putting-together-2

«Оборачивающаяся прямая», проходящая через эти две точки, в итоге уперлась в третью точку (47, 39), а симметричная ей «относительно оси X» будет (47, 28). Вот эта-то точка и станет результатом нашей операции.

Применим свою математическую мудрость к криптографии

Чтобы использовать ECDSA, такой протокол как Биткойн должен зафиксировать набор параметров для эллиптической кривой и ее конечного поля, чтобы эти параметры знали и применяли все пользователи протокола. Иначе каждый будет решать свои собственные уравнения, которые не будут сходиться друг с другом, и они никогда ни о чем не договорятся.

Эти зафиксированные параметры включают в себя уравнение кривой, значение модуля поля и базовую точку, которая лежит на кривой. Последним параметром является порядок базовой точки, который в графическом виде можно представить себе как количество раз, которое базовая точка может быть прибавлена к себе до тех пор, пока ее касательная кривая не станет вертикальной. Этот параметр подбирается таким образом, чтобы он являлся очень большим простым числом.

Для всех этих параметров Биткойн использует очень-очень большие (ну просто офигенно невообразимо огромные) числа. Это важно. На самом деле, все практические применения ECDSA используют огромные числа. Ведь безопасность этого алгоритма опирается на то, что эти значения слишком большие, чтобы подобрать что-то простым перебором или «брутфорсом».

В случае Биткойна эти значения таковы (запись чисел дана не в десятичном, а в более компактном шестнадцатеричном виде, привычном программистам):

Уравнение эллиптической кривой: y² = x³ + 7

Простой модуль = 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

Кто выбрал эти цифры, и почему? Большое количество исследований и изрядная интрига всегда окружают выбор соответствующих параметров. В конце концов, большое и, казалось бы, случайное число может скрывать в себе какую-нибудь «заднюю дверцу» для упрощения вычислений, которая может быть доступна только посвященным. Если вкратце, данная конкретная реализация ECDSA известна как secp256k1 и является частью семейства стандартов, предлагаемых для использования в криптографии.

Вооружившись всеми этими базовыми знаниями, в следующей статье мы будем готовы применить эту математику к Биткойну и выяснить, наконец, что же там происходит в недрах нашего биткойн-клиента, когда мы нажимаем на кнопку «Оплатить». Ну а пока вы ждете второй части, можете слегка освежить свои знания относительно анатомии биткойн-адресов и транзакций. А если вы разработчик, то можно полюбопытствовать, что же там происходит внутри этого таинственного API биткойн-протокола.

(Продолжение следует)

Источник: Coindesk

Aвтор: Eric Rykwalder



Categories: Криптография, Разработчикам, Технологии

Tags:

Leave a Reply

22 Комментарий на "Математика Биткойна: Теория"

Notify of
avatar
trackback
Как работает Биткойн: Основы | Bit•Новости

[…] программу-клиент, и если она работает в соответствии с математикой Биткойна, этой программой можно будет успешно пользоваться для […]

trackback
Биткойн — что это такое? | Kollektor OF - Everything about bitcoin

[…] Математика Биткойна: Теория и Практика […]

trackback
Опенсорсный проект пытается изобрести деньги заново | Bit•Новости

[…] «Биткойн» полагается на так называемую «эллиптическую криптографию«, которая хотя и хорошо проработана теоретически, […]

trackback
Математика Биткойна: Практика | CryptoNews

[…] предыдущей статье, мы рассмотрели теоретические основы эллиптической […]

trackback
Проблемы криптовалют: масштабируемость и метки времени | Bit•Новости

[…] нахождения дискретного логарифма на эллиптической кривой не может быть решена за время меньшее […]

trackback
Математика Биткойна: Практика | Bit•Новости

[…] предыдущей статье, мы рассмотрели теоретические основы эллиптической […]

trackback
Биткойн — изобретем финансы заново! | Bit•Новости

[…] у вас есть цифровые монеты, только вы и никто другой являетесь владельцем этих монет. Вы можете осуществлять платежи без […]

Юрий
Гость

Уж если Коиндеск опустился до уровня объяснения криптографии эллиптических кривых для спекулянтов, то писать действительно больше не о чем. Тем более, что это у тому же копипаст, оригинал здесь http://blog.chain.com/post/95218566791/the-math-behind-bitcoin

Александр Петров
Гость

Очень понравилось разъяснение. Когда сам начинал использовать ECDSA, долго пытался понять основы подписи и в конце-концов просто воспользовался готовым кодом в примере.

Вася
Гость

А вот вопрос: если я хочу сложить две точки R’+P (см. 3 график, где P, R и R’ есть), то я должен провести прямую через эти точки (она проведена на графике) и там где прямая будет третий раз пересекать эллиптическую кривую, СТОП ведь прямая больше ее не пересекает, т.к. она касательная в точке P.
Так либо такая сумма не определена, либо результат это зеркальное отражение точки P, мол прямая два раза пересекает эллиптическую кривую в точке P.

arvicco
Администратор

Интуитивно, если проходящая через R’ и P прямая является касательной в точке P, то она должна «считаться дважды», то есть результатом R’+P будет P’ (симметричная к P). Так ли это на самом деле, думаю нам могут подсказать математики, которые сюда иногда заглядывают, чтобы все покритиковать… 😉

Влад
Гость

Вот еще неплохие ссылочки на эту тему

http://habrahabr.ru/post/191240/
http://habrahabr.ru/post/188958/

В этом нужно разобраться, чтобы уметь самостоятельно создавать себе биткоин адреса.

Novickoff
Гость

Какое отношение к названию и содержанию статьи имеет безумная преамбула о пересмотре концепции(!) собственности? Заманухи ради?

arvicco
Администратор

Это просто перевод, так было в оригинальной статье Coindesk.

А что в ней особо безумного? Права собственности всегда определялись либо физическим владением (мое, потому что находится в моих руках, и только попробуйте отобрать), либо ссылкой на авторитет третьей стороны (мое, потому что вот бумажка с королевской печатью, где это написано). В случае с биткойном, ни то, ни другое не работает, права собственности определяются математически. А раз так, нужно как минимум постараться в этой математике разобраться.

Анонимно
Гость

Я бы даже больше добавил, что биткоинов в привычном нам понимании не существует

Vetal
Гость

Права собственности на биткойн определяются не матиматикой, а консенсусом. То есть достигается полное согласие огромного количества участников, а кто не согласен, тот просто не участвует. Математика – лишь инструмент достижения консенсуса. Очень удобный иструмент, так как существует чёткий алгоритм достижения консенсуса, который никто не сможет незаметно нарушить.

arvicco
Администратор

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

pianisteg
Гость

кто это переводил? «Целочисленное модуло»

pianisteg
Гость

2256 — это так записали 2^256?

pianisteg
Гость

Prime modulo == простой модуль.

А вообще, админ, добавьте чтобы по Ctrl-Enter опечатки отсылать можно было. Ужас сколько непонимания математики переводчиком в статье.

arvicco
Администратор

Очевидно, переводил не профессиональный математик. Потому что, профессиональные математики, готовы свысока указывать на чужие ошибки, но сами переводить и писать «для профанов» ничего не берутся. Я, скажем, до этой статьи не видел ни одного внятного описания математики эллиптических кривых, так чтобы там можно было хоть что-то понять непрофессионалу. За поправки спасибо, внесем в статью.

pianisteg
Гость

О том и речь, что для этого и дается фича «ctrl-enter».

Что касается текста и перевода, то термины можно посмотреть все в Википедии.

wpDiscuz