На прошлой неделе я опубликовал версию 1.1 curve25519-dalek, которая имеет две основные функции по сравнению с 1.0: новый бэкэнд SIMD с использованием инструкций IFMA и новый API, который позволяет использовать предварительные вычисления для проверочных проверок. Насколько мне известно, бэкэнд IFMA - самый быстрый Curve25519 из когда-либо существовавших; Я писал об этом в предыдущем посте, и теперь он интегрирован в выпущенную библиотеку.

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

Мультискалярное умножение против множественного скалярного умножения

Многие протоколы эллиптических кривых тратят большую часть своего времени на выполнение операций скалярного умножения: вычисления a*A для точки кривой A и скаляра (целое число по модулю порядка кривой) a. В этом посте я буду использовать заглавные буквы A,B,P,Q,... для точек кривой и строчные буквы a,b,x,y,... для скаляров, чтобы всегда можно было отличить тип от имени переменной.

Часто, вместо того, чтобы просто вычислять одно скалярное умножение, реализации необходимо вычислить уравнение, подобное

a_1*A_1 + ... + a_n*A_n

Оказывается, выполнение этого вычисления как одной операции (мультискалярное умножение) потенциально намного более эффективно, чем вычисление n индивидуальных скалярных умножений.

На высоком уровне это связано с тем, что указание всей проблемы сразу («вычислить все уравнение»), а не указание нескольких подзадач («вычислить эту часть, затем эту часть, затем эту часть ”) Позволяет реализации распределять работу между различными частями, что невозможно, когда скалярные умножения выполняются индивидуально.

Например, один метод вычисления скалярного умножения разделяет операцию скалярного умножения на последовательность сложений и удвоений; при мультискалярном умножении удвоения можно разделить между всеми точками, а не делать один раз для каждой точки. (Подробнее см. Во внутренней документации curve25519-dalek.)

Эта операция обеспечивается в curve25519-dalek чертами MultiscalarMul и VartimeMultiscalarMul, которые выполняют операции постоянного времени и переменного времени соответственно. Эти интерфейсы принимают итераторы точек и скаляров, что позволяет очень гибко использовать их, как в этих примерах.

Экономия времени с предварительным вычислением

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

Например, реализация может сэкономить время, построив справочные таблицы с небольшими кратными точками, а затем используя их для выполнения «фрагментов» скалярного умножения. Таблицы большего размера экономят больше времени (за счет большего объема памяти), но когда точки не известны заранее, временные затраты на предварительные вычисления также должны быть сопоставлены с экономией времени.

Определение проблемы на высоком уровне

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

a_1*A_1 + ... + a_n*A_n + b_1*B_1 + ... + b_m*B_m,

где B_1,...,B_m - это точки, фиксированные заранее, а A_1,...,A_n - точки, которые меняются при каждом вычислении.

Признак VartimePrecomputedMultiscalarMul

Эта функциональность теперь предоставляется в curve25519-dalek чертой VartimePrecomputedMultiscalarMul, которая берет фиксированные точки B_1,...,B_m в конструкторе и возвращает структуру предварительного вычисления с тремя немного разными вариантами проблемы:

  • vartime_multiscalar_mul, который обрабатывает особый случай, когда n=0 и нет динамических точек;
  • vartime_mixed_multiscalar_mul, который принимает динамические точки как уже проверенные Point и является безошибочным;
  • optional_mixed_multiscalar_mul, который принимает динамические точки как Option<Point>s и возвращает Option<Point>, так что проверка сжатых данных точки может включать декомпрессию / проверку точки во входные итераторы.

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

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

Ускорение зависит от размера задачи, но для средних размеров может дать приличное ускорение на 20–30%.

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

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