Мульти-скалярное умножение: Стратегии и Проблемы
Ссылка на оригинал статьи: https://www.entropy1729.com/multiscalar-multiplication/
Мой Дискорд: useless_dorozhkina#1394
Небольшой конспект о мульти-скалярном умножении
Генерирование zk-SNARK (краткого не интерактивного аргумента знания с нулевым разглашением), использующегося в Aleo, включает в себя множество криптографических вычислений, почти все из которых происходят внутри эллиптической кривой в конечном поле.
Эллиптические кривые
Данная статья — краткое изложение этого материала.
Точка эллиптической кривой — это пара таких чисел (x, y) в конечном поле (вы можете рассматривать конечное поле как Zp, целые числа по модулю от некого очень большого простого числа; хотя иногда все сложнее), которые удовлетворяют следующему выражению:
для неких a и b в конечном поле.
Вы можете сложить точки эллиптической кривой, но только не традиционным методом. Вместо
Для данного выражения имеется два исключения:
- Когда (x1, y1) = (x2, y2).
- Когда x1 = x2, но y1 ≠ y2. В таком случае y1 = −y2, поскольку иного решения не существует.
В обоих этих случаях приведенное выше выражение не определено (нам пришлось бы делить на нуль), поэтому вместо него мы сделаем следующее:
1. Сумма точки с самой собой — это, как и прежде, точка (x3, y3) лишь в одном случае:
(Здесь a — это коэффициент, определяющий приведенное выше уравнение кривой).
2. В данном случае результатом сложения является особая точка, которую мы произвольно добавляем к кривой; она называется точкой на бесконечности и записывается как 0. Эта точка работает как нуль для нашей суммы, т.е.
Примитивные операции
Криптография эллиптических кривых в конечном счете опирается на две примитивные операции, сложение точек (суммирование двух разных точек) и удвоение точек (прибавление точки к самой себе), которые мы называем ECADD и ECDBL.
Если мы пытаемся прибавить точку к самой себе много раз, мы можем применить алгоритм double-and-add. Как уже объяснялось в одной из наших статей, идея проста: если мы хотим вычислить, скажем, 9P для некой точки P кривой вместо выполнения 9 сложений мы можем выполнить
P + P = 2P 2P + 2P = 4P 4P + 4P = 8P 4P + P = 9P
— всего лишь 4 операции сложения.
Когда нам приходится складывать множество точек k1P1 + k2P2 + ... + knPn, большинство методов предполагают, что эти примитивы даны, и сосредотачиваются на том, как выполнять скалярные умножения kiPi и сложение, минимизировав количество ECADD и ECDBL.
MSM (мульти-скалярное умножение)
Задача мульти-скалярного умножения заключается в том, чтобы в данной эллиптической кривой, вычислить
для неких скаляров (целых чисел по модулю определенного простого числа) ki, для неких точек эллиптической кривой Pi = (xi, yi) и для некого n (в задаче Aleo оно равно 2^26).
Имейте в виду, что операция суммирования здесь та же, что обсуждалась в предыдущем разделе. Аналогично, kiPi означает "Pi, добавленное к самому себе ki раз", и сумма остается такой же, что была приведена выше.
Подсчитано, что около 80% времени генерирования доказательств zk-SNARK тратится на выполнение MSM, поэтому его оптимизация очень важна для производительности.
Метод скользящего окна
Мы можем разбить MSM на меньшие суммы и сократить общее число операций, многократно использовав метод скользящего окна. Если мы хотим вычислить каждое произведение kiPi, мы можем разбить его на окна размером c
С учетом этого, задача MSM может быть представлена в виде
Теперь мы можем изменить порядок сложения
Иными словами, сначала мы делим скаляры на окна, а затем объединяем все точки в каждом окне. Теперь мы можем сосредоточиться на том, как эффективно вычислить все Bj:
где суммирование по u(λ) выполняется только с точками, коэффициент которых равен λ. Например, если c = 3 и нам даны 15 точек
мы можем разделить сложение по коэффициентам λ, принимающим значения от 1 до 7. Для λ = 1: ∑uPu = P4 (потому что P4 — единственная точка с коэффициентом 1), для λ = 4: ∑uPu = P1 + P5 и так далее. Таким образом мы просто расставляем все точки с общим коэффициентом λ по λ-окнам. Итак,
Мы можем вычислить это выражение с минимальным количеством сложений точек, используя частичные суммы.
Каждая такая операция содержит в себе лишь одно сложение точек эллиптической кривой. Конечный результат может быть вычислен с помощью сложения частичных сумм:
Мы можем улучшить вычисления, изменив разложение коэффициентов ki. В двоичном представлении вес Хэмминга — это число ненулевых битов; в идеале мы хотели бы, чтобы этот вес был как можно меньше, чтобы уменьшить количество сумм (Например, 65537, т.е. 2^16 + 1 различными способами используется как публичный ключ для криптосистемы RSA. Алгоритмы возведения в квадрат и мультипликации требуют лишь двух умножений). Средний вес Хэмминга в двоичном представлении равен 1/2; если мы введем двоичное представление со знаком (−1, 0, 1), средний вес снизится до 1/3 с последующим уменьшением количества операций (в среднем).
BLS 12-377
Кривая, которая используется в Aleo, называется BLS 12-377. Базовое поле (конечное поле) имеет порядок q (377-битное простое число) и имеет степень вложения 12. И порядок группы G1 эллиптических кривых r, и конечное поле являются 2-адическими числами (это значит, что и q, и r могут быть записаны как (2^α)r + 1, где r — нечетное, а α больше 40). Порядки q и r связаны степенью вложения: r ∣ q^12 − 1. Уравнение эллиптической кривой:
Дополнительно мы можем задать вторую группу G2 над квадратичным расширением поля Fq; уравнение такой кривой:
где B — параметр. Дополнительную информацию о параметрах кривых вы можете найти здесь.
BLS 12-377 бирационально эквивалентна кривым Монтгомери и скрученным кривым Эдвардса. Это дает нам возможность выполнять сложение точек и скалярное произведение быстрее, избегая дорогостоящих инверсий поля. В случае кривых Монтгомери возможно выполнять скалярные произведения за постоянное время, что делает эту операцию устойчивой к атакам по времени.
Реализации кривой BLS 12-377 и (бирационально эквивалентной) скрученной кривой Эдвардса представлены в данном репозитории.
BLS 12-377 является одной из кривых, удобных для сопряжения; это можно применять для коротких цифровых подписей, которые можно эффективно агрегировать, схем полиномиальных обязательств и однократного обмена несколькими ключами.
Причина, по которой мы имеем дело с двумя уравнениями для кривой BLS и две группы связана с сопряжением. Сопряжение — это билинейное отображение: оно принимает две точки, каждая из группы простого порядка r. По техническим причинам эти группы должны быть разными. Так как первоначальная кривая имеет только одну группу порядка r, нам нужно произвести расширение поля, чтобы иметь возможность найти другие группы порядка r. Степень вложения показывает, насколько нам нужно расширить поле, чтобы найти другие группы. В качестве дополнения, расширенное поле содержит в себе все корни r степени из единицы.
Заметка о расширении поля
Степень вложения является также и степенью расширения поля, которое нам нужно использовать. Знакомыми примерами расширения полей являются действительные числа, R (расширение поля рациональных чисел Q, которое является трансцендентальным) и комплексные числа, C (расширение R). Последнее не может быть расширено далее, поскольку в C неприводимых многочленов не существует (мы можем сказать, что комплексные числа — это алгебраически замкнутое поле).
Если мы хотим создать квадратичное расширение Fq, мы можем представить его как полином a0 + a1x, где a0 и a1 — элементы поля Fq. Это сложение является простым, поскольку мы добавляем независимые и линейные члены отдельно. Для умножения с заданными элементами a и b
Чтобы избежать выхода за пределы линейных многочленов, мы можем уменьшить степень, используя неприводимый многочлен, такой как x^2 + 1, и установив, что x^2 + 1 = 0. Если мы подставим это в уравнение выше
что напоминает умножение в комплексных числах.
Условия выбора полинома следующие:
- Он должен иметь тот же порядок, что и поле расширения (в нашем случае второй).
- Он должен быть неприводимым в поле, которое мы расширяем, это значит, что мы не можем разделить этот многочлен на полиномы меньшей степени.
На практике, когда мы хотим создать расширение поля Fq12, мы можем сделать это, последовательно расширяя меньшие поля: используя башню расширений (такую, как Q → R → C).
Ускорение с помощью Карацубы, Тоома-Кука и БПФ
Потенциальное применение БПФ возникает при реализации примитивов ECADD и ECDBL. Эти операции могут быть выполнены в разных системах координат. Как утверждалось здесь, проективные координаты обычно намного быстрее, потому что они позволяют избежать инверсии конечного поля, которая затрачивает намного больше, чем умножения и сложения.
При использовании проективных координат вычисления выполняются быстрее, потому что мы меняем деления на умножения. Это означает, что предстоит выполнить много умножений, поэтому нам нужны эффективные методы для умножения целых чисел, в которых алгоритмы Карацубы, Тоома или БПФ могут стать привлекательными, поскольку мы имеем дело с умножением больших целых чисел. Оптимальный алгоритм будет зависеть от размера целых чисел.