Эллиптические кривые: где рождаются ключи и коммитменты Zcash

Оригинальное исследование от Annkkitaaa

Улица с односторонним движением, построенная из точек на кривой

Серия: Zcash from First Principles . Статья 2 . Эллиптические кривые Для кого: новички. Мы предполагаем только знание Статьи 1 (конечные поля): арифметики, которая «заворачивается» по модулю простого числа. Никакой другой подготовки не требуется. Что вы поймёте после прочтения: интуитивное и корректное представление об эллиптических кривых, о «ловушке», которая делает их полезными, и о том, как именно Zcash превращает их в ключи и коммитменты.

Статья 1 дала нам идеальную площадку для арифметики: конечное поле. Но само по себе поле — это просто числа. Чтобы построить ключи и «запечатанные конверты» из Статьи 0, Zcash нужен объект с особым типом односторонней трудности: его легко вычислять в прямом направлении и практически невозможно обратить. Этот объект — эллиптическая кривая. В этой статье мы разберём её с самых основ, начиная с интуиции и только потом переходя к алгебре.

1. Почему вам должно быть не всё равно?

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

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

Значит, нам нужна математическая операция, для которой:

• идти вперёд (секрет -> публичный ключ) быстро и легко, а
• идти назад (публичный ключ -> секрет) настолько трудно, что все компьютеры на Земле, работающие всю жизнь Вселенной, не справились бы.

Обычного умножения в конечном поле недостаточно: деление мгновенно его отменяет (в этом и был весь смысл Статьи 1). Нам нужно нечто, у чего нет простой кнопки «отменить». Эллиптические кривые дают именно это и, как бонус, позволяют комбинировать свои точки способом, идеально подходящим для построения коммитментов. Давайте посмотрим, как именно.

2. Интуиция: кривая, точки на которой можно «складывать»

На мгновение забудем о криптографии. Эллиптическая кривая — это просто множество точек (x, y), удовлетворяющих уравнению вида:

y^2 = x^3 + ax + b

Над обычными числами она выглядит как гладкая изгибающаяся кривая, часто с округлой петлёй и двумя «хвостами»:

По-настоящему удивительная часть в другом: вы можете «сложить» две точки на этой кривой и получить третью точку на той же самой кривой. Это не обычное сложение координат. Это геометрическое правило, и его проще увидеть, чем сформулировать словами.

Правило хорды (сложение двух разных точек)

Чтобы сложить P + Q:

1. Проведите прямую через P и Q.
2. Эта прямая пересечёт кривую ровно ещё в одной точке. Назовём её R*.
3. Отразите R* относительно горизонтальной оси. Это отражение и есть ответ: P + Q.

Правило касательной (сложение точки самой с собой)

Чтобы вычислить P + P (записывается как 2P), второй точки для проведения прямой нет, поэтому вместо этого используется касательная к кривой в точке P, а затем применяется тот же рецепт: «третье пересечение, затем отражение».

Это и есть вся операция. Два геометрических правила. Благодаря им точки эллиптической кривой образуют то, что математики называют группой: множество с хорошо устроенной операцией «сложения». У него даже есть свой «ноль».

Точка на бесконечности (ноль кривой)

Любой числовой системе нужен 0 — элемент, который ничего не меняет при сложении. На эллиптической кривой эту роль играет особая дополнительная точка, называемая точкой на бесконечности, обозначаемая O. Её можно представить как точку «бесконечно высоко вверху», место, где встречаются вертикальные прямые. Прибавление O к любой точке ничего не меняет — точно так же, как прибавление 0.

3. От картинок к конечному полю

Гладкая кривая выше — это интуиция. Но Zcash не использует вещественные числа (они округляются и выдают масштаб, как было сказано в Статье 1). Он использует эллиптическую кривую над конечным полем: то же уравнение y^2 = x^3 + ax + b, но со всей арифметикой по модулю простого числа.

Если сделать это, красивая кривая распадается на россыпь несвязанных точек — по одной точке на каждую пару (x, y), которая удовлетворяет уравнению по модулю p. Она вообще перестаёт выглядеть как кривая. Но вот ключевой момент:

Алгебра правила хорды и касательной по-прежнему работает безупречно. Те же формулы, которые геометрически находили P + Q, теперь вычисляют его с помощью арифметики конечного поля. Точки по-прежнему образуют группу с тем же 0 (точкой на бесконечности).

Сделаем это наглядным на маленьком, полностью проверенном примере.

Полная кривая, вычисленная точно

Возьмём y^2 = x^3 + 2x + 2 над конечным полем F_17. Если вычислить все допустимые точки, получится ровно 18 точек плюс точка на бесконечности = 19 точек всего. Некоторые из них:

(0,6) (0,11) (3,1) (3,16) (5,1) (5,16) (6,3) (6,14) (7,6) (7,11) ...

Теперь выберем точку G = (5, 1) и начнём многократно складывать её саму с собой. Посмотрите, что получается (каждая строка ниже действительно вычислена, а не угадана):

Стоит заметить две вещи:

• Она проходит через все 18 конечных точек, а затем попадает в O на 19-м шаге, после чего цикл повторялся бы бесконечно. Начальная точка G «порождает» всю группу, поэтому мы называем её генератором.
• Это действительно группа: например, 1G + 2G = (5,1) + (6,3) = (10,6), а это в точности 3G. Сложение внутренне согласовано, как и требуется для группы.

4. Ловушка: умножение точки на скаляр

Таблица 1G, 2G, 3G, ... — это сердце всей конструкции. Многократное сложение точки самой с собой называется умножением на скаляр: точка kG означает «G, сложенная сама с собой k раз».

А теперь магия. Рассмотрим два направления:

Эта асимметрия и есть та самая улица с односторонним движением, которая была нужна нам в разделе 1. Обратная задача («какое k породило эту точку?») называется задачей дискретного логарифмирования на эллиптической кривой (ECDLP), и для кривых, используемых Zcash, не существует известного метода, который решил бы её раньше тепловой смерти Вселенной.

На нашей игрушечной кривой над F_17 вы могли бы просто прочитать k из таблицы, потому что в ней всего 19 точек. У реальных кривых порядка 2^(255) точек. В такой таблице было бы больше строк, чем атомов во Вселенной, так что «просто прочитать» не получится. Именно малость игрушечной кривой делает её удобной для обучения — и именно поэтому она не является безопасной.

5. Как рождаются ключи (вот и главное)

Теперь у нас есть всё необходимое, чтобы объяснить настоящий криптографический ключ, и это поразительно просто:

Выберите секретное число k. Опубликуйте точку kG. Вот и всё. k — это ваш приватный ключ. kG — это ваш публичный ключ. Улица с односторонним движением (ECDLP) гарантирует, что никто не сможет восстановить k по kG.

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

Бонус: почему точки кривой идеально подходят для коммитментов

Вспомним «запечатанный конверт» (коммитмент) из Статьи 0, который должен был скрывать своё содержимое и при этом быть невозможным для подделки. Эллиптические кривые дают нам чистый способ его построить. Возьмём две фиксированные публичные точки-генераторы G и H, секретное значение v и случайное маскирующее число r, и сформируем:

Commitment  =  v.G  +  r.H

Это коммитмент Педерсена, и у него есть оба нужных нам свойства:

• Сокрытие: случайное r «размазывает» результат по всей кривой, так что точка ничего не раскрывает о v.
• Связывание: ECDLP делает практически невозможным найти другую пару (v, r), дающую ту же точку, так что вы не можете позже изменить решение о том, к чему коммитились.

Ещё одно бонусное свойство позже окажется бесценным: эти коммитменты складываются. Коммитмент к v_1 плюс коммитмент к v_2 — это корректный коммитмент к v_1 + v_2. Именно это «гомоморфное» поведение позволит Zcash позже доказывать, что деньги, входящие в транзакцию, равны деньгам, выходящим из неё, не раскрывая при этом никакие суммы. Этим мы воспользуемся примерно в Статье 6.

6. Где это живёт в Zcash

Следы этого вполне конкретны и проверяемы.

Причины, по которым одну кривую «встраивают» в поле другой, и почему полезен цикл из двух кривых, реальны и важны, но они относятся уже к статьям о системах доказательств. Пока же вывод прост и надёжен: каждый ключ Zcash — это скаляр, умноженный на генератор, а каждый коммитмент Zcash — это сумма точек кривой, живущих на одной из этих именованных кривых.

7. Честная оговорка

Чтобы сохранить читаемость, мы упростили несколько моментов. Мы использовали форму короткого Вейерштрасса (y^2 = x^3 + ax + b); кривые Zcash часто записывают в других эквивалентных формах (Jubjub — это twisted Edwards кривая), выбранных ради эффективности и безопасности, но идея группы остаётся той же самой. Мы не определяли точные формулы сложения точек (это алгебраическая версия правила «третье пересечение, затем отражение») и оставили в стороне тонкости вроде порядка кривой, кофакторов и «pairings», которые становятся важными в статьях о системах доказательств. Всё это не меняет интуицию — только делает её точнее.

8. Краткое резюме

• Системе приватности нужна улица с односторонним движением: легко вперёд, практически невозможно назад. Эллиптические кривые это обеспечивают.
• Эллиптическая кривая — это множество точек, удовлетворяющих y^2 = x^3 + ax + b, а её точки можно складывать по геометрическому правилу хорды и касательной, где специальная точка на бесконечности играет роль нуля.
• Над конечным полем кривая превращается в россыпь точек, но то же сложение продолжает работать, и точки образуют группу. (Проверенный пример: y^2 = x^3 + 2x + 2 над F_17 имеет 19 точек, и G = (5,1) порождает их все.)
• Умножение на скаляр kG легко вычисляется, но практически невозможно обратить: это ECDLP. В этом и состоит ловушка.
• Ключи: приватный ключ k, публичный ключ kG. Коммитменты: форма Педерсена v.G + r.H, которая скрывает, связывает и удобно складывается.
• В Zcash Sapling использует BLS12-381 + Jubjub, а Orchard — кривые Pallas/Vesta (Pasta); каждый ключ и каждый коммитмент живёт на них.

Глоссарий

FAQ

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

Доказано ли, что ECDLP трудна? Её не доказали как невозможную, но за десятилетия интенсивных усилий не было найдено ни одной эффективной атаки на хорошо подобранные кривые. Безопасность основана на этом хорошо проверенном предположении.

Может ли квантовый компьютер это взломать? Достаточно большой квантовый компьютер мог бы взломать ECDLP. Это известная долгосрочная проблема для всей индустрии и активная область исследований; сегодняшние кривые остаются безопасными против классических компьютеров.

Почему Zcash использует больше одной кривой? Потому что задачи разные. Одна кривая несёт систему доказательств с нулевым разглашением; другая (встроенная в поле первой) делает операции с ключами и коммитментами внутри доказательства эффективными. Следующие статьи объяснят, почему это сочетание важно.

Проверьте свою интуицию

Используя проверенную таблицу из раздела 3, чему равно 9G + 10G на нашей игрушечной кривой? И что ответ говорит вам о G? (Ответ ниже.)

Что дальше

Статья 3 . Хеширование и коммитменты: теперь мы как следует откроем этот «магический запечатанный конверт». Вы уже увидели один способ построить коммитмент из точек кривой; дальше мы спросим, что на самом деле означают сокрытие и связывание, познакомимся с хеш-функциями и свяжем всё это с коммитментами note, на которых держится каждый платёж Zcash.

Часть серии Zcash from First Principles для ZecHub. Лицензия CC BY-SA 4.0.