В этой статье подробно анализируется алгоритм MSM, алгоритм добавления точек эллиптической кривой, алгоритм умножения Монтгомери и т. д., а также сравнивается разница в производительности между GPU и FPGA при добавлении точек кривой BLS12_381.
Сценарист: Стар Ли
Технология доказательства с нулевым разглашением все шире используется, например, доказательство конфиденциальности, доказательство вычислений, доказательство консенсуса и так далее. В поисках новых и лучших сценариев приложений многие люди постепенно обнаружили, что доказательство с нулевым разглашением доказывает, что производительность является узким местом. Команда Trapdoor Tech глубоко исследует технологию доказательства с нулевым разглашением с 2019 года и изучает эффективные решения для ускорения доказательства с нулевым разглашением. GPU или FPGA являются относительно распространенными платформами ускорения, представленными в настоящее время на рынке. Эта статья начинается с расчета MSM и анализирует преимущества и недостатки вычислений с нулевым разглашением, ускоренных FPGA и GPU.
TL;DR
ЗКП — технология с широкими перспективами на будущее. Все больше и больше приложений используют технологию доказательства с нулевым разглашением. Однако существует множество алгоритмов ZKP, и в разных проектах используются разные алгоритмы ZKP. В то же время вычислительная производительность доказательства ZKP относительно низкая. В этой статье подробно анализируется алгоритм MSM, алгоритм добавления точек эллиптической кривой, алгоритм умножения Монтгомери и т. д., а также сравнивается разница в производительности между GPU и FPGA при добавлении точек кривой BLS12_381. В целом, с точки зрения вычислений ZKP proof, краткосрочный GPU имеет очевидные преимущества, высокую пропускную способность, высокую стоимость, производительность, программируемость и так далее. Условно говоря, FPGA имеет определенные преимущества в энергопотреблении. В долгосрочной перспективе могут появиться микросхемы FPGA, подходящие для вычислений ZKP, или микросхемы ASIC, адаптированные для ZKP.
Комплекс алгоритмов ЗКП
ZKP — это общий термин для технологии доказательства с нулевым разглашением (Zero Knowledge Proof). В основном существует две классификации: zk-SNARK и zk-STARK. В настоящее время распространенными алгоритмами zk-SNARK являются Groth16, PLONK, PLOOKUP, Marlin и Halo/Halo2. Итерация алгоритма zk-SNARK в основном идет по двум направлениям: 1/необходима ли доверенная установка 2/производительность структуры схемы. Преимущество алгоритма zk-STARK заключается в том, что не требуется доверенной настройки, но количество вычислений проверки логарифмически линейно.
Что касается применения алгоритма zk-SNARK/zk-STARK, алгоритмы доказательства с нулевым разглашением, используемые в разных проектах, относительно разбросаны. В применении алгоритма zk-SNARK, поскольку алгоритм PLONK/Halo2 является универсальным (нет необходимости в доверенной настройке), может быть все больше и больше приложений.
PLONK подтверждает объем вычислений
Взяв в качестве примера алгоритм PLONK, проанализируйте количество вычислений доказательства PLONK.
Сумма расчета части доказательства PLONK состоит из четырех частей:
1/ МСМ - Множественное скалярное умножение. MSM часто используется для вычисления полиномиальных обязательств.
2/ Вычисление NTT - Полиномиальное преобразование между значением точки и представлением коэффициента.
3/ Полиномиальное вычисление - полиномиальное сложение, вычитание, умножение и деление. Полиномиальная оценка (уация) и так далее.
4/ Circuit Synthesize - синтез схемы. Расчет этой части связан с масштабом/сложностью схемы.
Вообще говоря, объем вычислений в части синтеза цепей — это больше суждений и логики циклов, а степень параллелизма относительно низкая, что больше подходит для вычислений ЦП. Вообще говоря, ускорение доказательства с нулевым разглашением обычно относится к ускорению вычислений первых трех частей. Среди них расчетное количество МСМ является относительно большим, за ним следует НТТ.
Что такое МСМ
MSM (множественное скалярное умножение) относится к заданному ряду точек и скаляров на эллиптической кривой и вычисляет точки, соответствующие результатам сложения этих точек.
Например, для набора точек на эллиптической кривой:
Учитывая фиксированный набор точек эллиптической кривой из одной указанной кривой:
[Г_1, Г_2, Г_3, …, Г_n]
и случайные коэффициенты:
и случайно выбранные элементы конечного поля из заданного скалярного поля:
[с_1, с_2, с_3, …, с_n]
MSM - это расчет для получения точки Q эллиптической кривой:
Q = \sum_{i=1}^{n}s_i*G_i
В отрасли обычно используется алгоритм Пиппенджера для оптимизации расчета МСМ. Рассмотрим внимательнее принципиальную схему процесса алгоритма Пиппенджера:
Процесс вычисления алгоритма Пиппенджера делится на два этапа:
1/Скалярное разделение на Windows. Если скаляр 256 бит, а окно 8 бит, то все скаляры делятся на 256/8=32 окна. Каждый уровень окна использует «сегменты» для временного хранения промежуточных результатов. GW_x — точка накопления результата на одном слое. Вычисление GW_x также относительно простое: оно по очереди проходит через каждый скаляр в слое, использует значение скалярного слоя в качестве индекса и добавляет соответствующий G_x к соответствующим сегментам. На самом деле принцип относительно прост: если коэффициенты сложения двух точек одинаковы, сначала добавьте две точки, а затем снова добавьте скаляр, вместо того, чтобы дважды добавлять две точки перед добавлением скаляра.
2/ Баллы, рассчитанные каждым окном, накапливаются путем двойного сложения для получения окончательного результата.
Алгоритм Пиппенджера также имеет множество алгоритмов оптимизации деформации. В любом случае, в основе расчета алгоритма МСМ лежит добавление точек на эллиптическую кривую. Разным алгоритмам оптимизации соответствует разное количество добавленных баллов.
Добавление точки эллиптической кривой (Point Add)
Вы можете посмотреть различные алгоритмы добавления точек на эллиптических кривых с «короткой формой Вейерштрасса» с этого сайта.
Предполагая, что проективные координаты двух точек равны (x1, y1, z1) и (x2, y2, z2) соответственно, результат сложения точек (x3, y3, z3) можно рассчитать по следующей формуле расчета.
Причина подробного описания процесса вычислений состоит в том, чтобы показать, что весь процесс вычислений состоит в основном из целочисленных операций. Разрядность целого числа зависит от параметров эллиптической кривой. Укажите разрядность некоторых распространенных эллиптических кривых:
- BN256 - 256 бит
- BLS12_381 - 381 бит
- BLS12_377 - 377 бит
- Особое внимание следует обратить на то, что эти целочисленные операции являются операциями над полем по модулю. Модульное сложение/вычитание по модулю относительно просто, сосредоточьтесь на принципе и реализации модульного умножения.
模乘（Модульное умножение）
Даны два значения над полем по модулю: x и y. Расчет модульного умножения относится к x*y mod p. Обратите внимание, что разрядность этих целых чисел равна разрядности эллиптической кривой. Классический алгоритм модульного умножения — умножение Монтгомери (MontgomeryMulplication). Перед выполнением умножения Монтгомери множимое необходимо преобразовать в представление Монтгомери:
Формула для вычисления умножения Монтгомери выглядит следующим образом:
Существует много алгоритмов реализации умножения Монтгомери: CIOS (грубо интегрированное сканирование операндов), FIOS (точно интегрированное сканирование операндов), FIPS (точно интегрированное сканирование продуктов) и так далее. В этой статье не представлены подробные сведения о различных реализациях алгоритмов, и заинтересованные читатели могут провести собственное исследование.
Чтобы сравнить разницу в производительности между FPGA и GPU, выберите самый простой метод реализации алгоритма:
Проще говоря, алгоритм модульного умножения можно разделить на два вычисления: умножение больших чисел и сложение больших чисел. Поняв логику вычислений MSM, вы можете выбрать производительность модульного умножения (Throughput), чтобы сравнить производительность FPGA и GPU.
Наблюдай и думай
Можно предположить, что при такой конструкции FPGA весь VU9P может обеспечить пропускную способность в точках BLS12_381 эллиптической кривой. Сложение точек (способ add_mix) требует около 12 модульных умножений. Системные часы FPGA составляют 450M.
При том же алгоритме модульного умножения/сложения модулей, использующем тот же алгоритм сложения точек, точка плюс пропускная способность Nvidia 3090 (с учетом коэффициентов передачи данных) превышает 500 Мбит/с. Конечно, весь расчет включает в себя множество алгоритмов, некоторые алгоритмы могут быть пригодны для FPGA, а некоторые алгоритмы подходят для GPU. Причина использования одного и того же алгоритма сравнения состоит в том, чтобы сравнить основные вычислительные возможности FPGA и GPU.
Основываясь на приведенных выше результатах, подведите итоги сравнения GPU и FPGA с точки зрения производительности доказательства ZKP:
Подведем итог
Все больше и больше приложений используют технологию доказательства с нулевым разглашением. Однако существует множество алгоритмов ZKP, и в разных проектах используются разные алгоритмы ZKP. Исходя из нашего практического инженерного опыта, FPGA является вариантом, но GPU в настоящее время является экономически эффективным вариантом. FPGA предпочитает детерминированные вычисления, преимущества которых заключаются в задержке и энергопотреблении. GPU обладает высокой программируемостью, имеет относительно зрелую высокопроизводительную вычислительную среду, короткий цикл разработки и предпочитает сценарии с пропускной способностью.
