Доказательства с нулевым разглашением (ZKP) становятся все более важными для децентрализованных систем. ZK впервые привлек к себе внимание общественности благодаря своему успеху в таких проектах, как ZCash, но сегодня ZK известен как решение для масштабирования Ethereum.
Используя ZK, уровень 2 (например, Scroll и Polygon), также известный как Rollups, разрабатывает zkEVM (zk Ethereum Virtual Machine). Эти zkEVM обрабатывают пакет транзакций и генерируют небольшое доказательство (в килобайтах). Эту аттестацию можно использовать для проверки всей сети того, что пакет транзакций действителен и правильный.
Однако на этом их использование не заканчивается. ZK позволяет использовать множество интересных областей применения.
Private Layer 1 – Mina, например, скрывает детали транзакций и данные в своем блокчейне, позволяя пользователям только подтверждать действительность своих транзакций, не раскрывая специфику самой транзакции. neptune.cash и Aleo также являются очень интересными проектами.
Децентрализованная облачная платформа - FedML и together.xyz позволяют децентрализованно обучать модели машинного обучения (ML), передавать вычисления на аутсорсинг в сеть и проверять правильность вычислений с помощью ZKP. Druglike создает более открытую платформу для поиска лекарств, используя аналогичные технологии.
Децентрализованное хранилище - Filecoin совершает революцию в облачных хранилищах, и ZK лежит в его основе, позволяя поставщикам хранилищ доказывать, что они хранят правильные данные в течение определенного периода времени.
ИГРА - Может появиться более продвинутая версия Darkforest, которая требует подтверждения в реальном времени. ZK также может расширить игру, чтобы снизить вероятность читерства. Может быть, вы также поработаете с децентрализованной облачной платформой, чтобы игра могла оплачивать собственный хостинг!
Идентификация - Децентрализованная аутентификация теперь также возможна через ZK. Вокруг этой идеи строится ряд интересных проектов. Например, notebook и zkemail (рекомендуется узнать).
Влияние ZK и децентрализованных систем огромно, однако развитие истории не идеально, и сегодня все еще существует множество препятствий и проблем. Процесс включения генерации доказательств очень ресурсоемкий и требует множества сложных математических операций. По мере того, как разработчики стремятся создавать более амбициозные и сложные протоколы и системы с использованием технологии ZK, как для создания доказательств, так и для процессов проверки, разработчики требуют меньших размеров доказательств, более высокой производительности и лучшей оптимизации.
В этой статье мы рассмотрим текущее состояние аппаратного ускорения и то, как оно будет играть ключевую роль в продвижении внедрения ZK.
Снарк против Старка
На сегодняшний день существует два популярных метода нулевого разглашения: zk-STARK и zk-SNARK (в этой статье мы проигнорировали Bulletproofs).
| | | |
| --- | --- | --- |
| зк-СТАРК | зк-СНАРК | |
| Сложность - Прувер | O(N * poly-log(N)) | O(N * log(N)) |
| Сложность - Верификатор | O(полилог(Н)) | О(1) |
| Размер пробы | 45-200 КБ | ~ 288 байт |
| 抗量子 | Да (на основе хеш-функции) | Нет |
| Надежная настройка | Нет | Да |
| Нулевое разглашение | Нет | Нет |
| Интерактивность | Интерактивный или неинтерактивный | Неинтерактивный |
| Документация для разработчиков | Ограниченный, но расширяющийся Хорошо |
表1:Снарк против Старка
Как упоминалось выше, между ними есть различия и компромиссы. Наиболее важным моментом является то, что доверенная настройка системы на основе zk-SNARK зависит по крайней мере от одного честного участника, участвующего в процессе доверенной установки, ключи которого уничтожены в конце процесса. С точки зрения ончейн-верификации, zk-SNARK намного дешевле с точки зрения платы за газ. Кроме того, пруфы zk-SNARK также значительно меньше, что делает их более дешевыми для хранения в блокчейне.
В настоящее время zk-SNARK более популярны, чем zk-STARK. Наиболее вероятная причина заключается в том, что zk-SNARK имеют гораздо более длительную историю. Другая возможная причина заключается в том, что Zcash, один из первых блокчейнов ZK, использовал zk-SNARK, поэтому большинство текущих инструментов разработки и документации вращаются вокруг экосистемы zk-SNARK.
Как создать ZK-приложение
Разработчикам могут потребоваться два компонента для завершения разработки приложения ZK
ZK-дружественный метод вычисления выражений (DSL или низкоуровневая библиотека).
Система аттестации, реализующая две функции: Proof и Verify.
DSL (предметно-ориентированный язык) и низкоуровневые библиотеки
Когда дело доходит до DSL, существует множество вариантов, таких как Circom, Halo2, Noir и многие другие. Circom, пожалуй, самый популярный на данный момент.
Когда дело доходит до низкоуровневых библиотек, популярным примером является Arkworks; Также в разработке находятся библиотеки, такие как ICICLE, которая является библиотекой ускорения CUDA.
Эти DSL предназначены для вывода замкнутых систем. В отличие от обычной программы, которая обычно вычисляется в виде x:= y *z, та же программа в ограниченном виде больше похожа на x-y * z = 0. Представляя программу в виде системы ограничений, мы обнаруживаем, что такие операции, как сложение или умножение, могут быть представлены одним ограничением. Однако более сложные операции, такие как битовые операции, могут потребовать сотен ограничений!
В результате, становится сложно реализовать некоторые хеш-функции в виде ZK-дружественных программ. В доказательствах с нулевым разглашением хэш-функции часто используются для обеспечения целостности данных и/или для проверки конкретных свойств данных, но из-за большого количества ограничений битовых операций некоторые хэш-функции трудно адаптировать к среде доказательств с нулевым разглашением. Эта сложность может повлиять на эффективность генерации и верификации доказательств и, таким образом, стать проблемой, которую разработчикам необходимо учитывать и решать при создании приложений на основе ZK
В результате становится сложно реализовать некоторые хеш-функции, чтобы они были ZK-совместимыми.
Доказательство
Систему доказательств можно сравнить с программным обеспечением, которое выполняет две основные задачи: генерацию доказательств и проверку доказательств. Контрольные системы обычно принимают в качестве входных данных схемы, доказательства и открытые/частные параметры.
Двумя наиболее популярными системами расстойки являются серии Groth16 и PLONK (Plonk, HyperPlonk, UltraPlonk)
Как показано в таблице 2, Groth16 требует надежного процесса настройки, но Groth16 обеспечивает более быстрое время проверки и проверки, а также постоянный размер проверки.
Plonk предоставляет общую настройку, которая выполняет фазу предварительной обработки для схемы, которую вы запускаете, каждый раз, когда генерируется доказательство. Несмотря на поддержку множества каналов, время проверки Plonk постоянно.
Между ними также есть различия с точки зрения ограничений. Groth16 растет линейно с точки зрения размера ограничений и не обладает гибкостью, в то время как Plonk более гибок.
В целом, поймите, что производительность напрямую связана с количеством ограничений в вашем приложении ZK. Чем больше ограничений, тем больше операций должен вычислить проверщик.
узкое место
Система доказательств состоит из двух основных математических операций: мультискалярного умножения (MSM) и быстрого преобразования Фурье (БПФ). Сегодня мы рассмотрим системы, в которых существует и то, и другое, где MSM может занимать около 60% времени выполнения, в то время как БПФ может занимать около 30%.
MSM требует большого доступа к памяти, что в большинстве случаев потребляет много памяти на машине, а также выполняет множество скалярных операций умножения.
Алгоритмы БПФ часто требуют переупорядочивания входных данных в определенном порядке для выполнения преобразований. Это может потребовать большого количества перемещений данных и может стать узким местом, особенно при больших размерах входных данных. Использование кэша также может быть проблемой, если шаблоны доступа к памяти не вписываются в иерархию кэша.
**В данном случае аппаратное ускорение является единственным способом полной оптимизации производительности ZKP. **
Аппаратное ускорение
Когда дело доходит до аппаратного ускорения, это напоминает нам о том, как ASIC и графические процессоры доминировали в майнинге Bitcoin и Ethereum.
Несмотря на то, что оптимизация программного обеспечения не менее важна и ценна, у нее есть свои ограничения. Аппаратная оптимизация, с другой стороны, может улучшить параллелизм за счет разработки FPGA с несколькими процессорами, например, уменьшить синхронизацию потоков или векторизацию. Доступ к памяти также можно оптимизировать более эффективно за счет улучшения иерархий памяти и шаблонов доступа.
Сейчас в пространстве ZKP основная тенденция, похоже, сместилась: графические процессоры и FPGA.
В краткосрочной перспективе графические процессоры имеют преимущество в цене, особенно после того, как ETH переходит на proof-of-stake (POS), оставляя большое количество GPU-майнеров в режиме ожидания и ожидания. Кроме того, графические процессоры имеют преимущество в коротких циклах разработки и предоставляют разработчикам большой параллелизм по принципу «подключи и работай».
Тем не менее, FPGA должны наверстать упущенное, особенно при сравнении форм-факторов и энергопотребления. FPGA также обеспечивают меньшую задержку для высокоскоростных потоков данных. Когда несколько FPGA объединены в кластер, они обеспечивают более высокую производительность по сравнению с кластерами GPU.
ГРАФИЧЕСКИЙ ПРОЦЕССОР ПРОТИВ FPGA
ГРАФИЧЕСКИЙ ПРОЦЕССОР:
Время разработки: графические процессоры обеспечивают быстрое время разработки. Документация для разработчиков таких фреймворков, как CUDA и OpenCL, хорошо проработана и популярна.
Энергопотребление: графические процессоры очень «энергоемкие». Даже когда разработчики используют параллелизм на уровне данных и параллелизм на уровне потоков, графические процессоры по-прежнему потребляют много энергии.
Доступность: Графические процессоры потребительского класса дешевы и легко доступны прямо сейчас.
ПЛИС:
Цикл разработки: ПЛИС имеют более сложный цикл разработки и требуют более специализированных инженеров. FPGA позволяют инженерам достичь многих «низкоуровневых» оптимизаций, которые не могут быть достигнуты графическими процессорами.
Задержка: FPGA обеспечивают меньшую задержку, особенно при обработке больших потоков данных.
Соотношение цены и доступности: FPGA дороже, чем графические процессоры, и не так легко доступны, как графические процессоры.
ЗПРИЗ
В наше время, когда дело доходит до узкого места аппаратной оптимизации и ZKP, существует конкуренция, которой не избежать - ZPRIZE
ZPrize является одной из самых важных инициатив в области ZK на данный момент. ZPrize — это соревнование, которое поощряет команды разрабатывать аппаратное ускорение для ключевых узких мест ZKP (например, MSM, NTT, Poseidon и т. д.) на нескольких платформах (например, FPGA, графических процессорах, мобильных устройствах и браузерах) на основе задержки, пропускной способности и эффективности.
Результат получился очень интересным. Например, улучшения графического процессора огромны:
МСМ в 2^26 увеличился на 131% с 5,86 секунды до 2,52 секунды. С другой стороны, решения FPGA, как правило, не имеют каких-либо тестов по сравнению с результатами GPU, с которыми можно сравнивать предыдущие тесты, и большинство решений FPGA впервые имеют открытый исходный код, и ожидается, что такие алгоритмы будут улучшаться в будущем.
Эти результаты указывают на направление, в котором большинство разработчиков чувствуют себя комфортно при разработке своих решений для аппаратного ускорения. Многие команды соревнуются за категорию GPU, но лишь небольшой процент соревнуется за категорию FPGA. Я не уверен, связано ли это с отсутствием опыта при разработке для FPGA, или с тем, что большинство FPGA-компаний/команд предпочитают разрабатывать тайно, чтобы продавать свои решения на коммерческой основе.
ZPrize предоставила сообществу несколько очень интересных исследований. По мере того, как будут начинаться новые раунды ZPrize, мы будем видеть все больше и больше интересных решений и проблем.
Практические примеры аппаратного ускорения
Если взять в качестве примера Groth16, то при рассмотрении реализации rapidsnark для Groth16 можно заметить, что выполняются две основные операции: БПФ (быстрое преобразование Фурье) и MSM (мультискалярное умножение); Эти две основные операции являются общими для многих систем доказательства. Время их выполнения напрямую связано с количеством ограничений в цепи. Естественно, что количество ограничений увеличивается по мере написания более сложных схем.
Чтобы получить представление о том, насколько ресурсоемкими являются операции БПФ и МСМ, мы можем ознакомиться с тестом Ingonyama для схемы Groth16 (процесс Vanilla C2 от Filecoin, выполненный на секторе 32 ГБ), и результаты будут следующими
Как показано на рисунке выше, MSM (Multiscalar Multiplication) может отнимать много времени и быть серьезным узким местом производительности для многих доказательств, что делает MSM одним из самых важных криптографических операторов, которые необходимо ускорить.
Итак, сколько вычислений занимает МСМ для доказывателя в других системах доказательств ZK? Это показано на рисунке ниже
В Plonk на долю МСМ приходится более 85% накладных расходов, как показано в последней статье Ингоньямы «Трубный МСМ». **
Так как же аппаратное ускорение должно ускорить MSM? **
МСМ
Прежде чем говорить о том, как ускорить МСМ, нужно понять, что такое МСМ
Мультискалярное умножение (MSM) — это алгоритм вычисления суммы кратных скалярных умножений в следующем виде
где G — точка в группе эллиптических кривых, a — скаляр, а результатом МСМ также будет точка эллиптической кривой
Мы можем разложить МСМ на два основных подкомпонента:
Модульное умножение
Сложение точек эллиптической кривой
Возьмем в качестве примера Affine(x,y) для выполнения наивной операции P+Q.
Когда мы хотим вычислить P + Q = R, нам нужно вычислить значение k по абсциссе k и P,Q
Получаем координаты R. Процесс вычисления такой же, как и выше, в этом процессе мы выполняем 2 умножения умножения, 1 операцию квадрата, 1 обратную операцию и несколько раз операции сложения и вычитания. Стоит отметить, что вышеуказанные операции выполняются в конечном поле, т.е. под модулем P. В реальности P будет очень большим. **
Стоимость вышеуказанной операции заключается в нахождении обратной >> умножения** **> **** в квадрате, а стоимость сложения и вычитания ничтожно мала.
Поэтому мы хотим максимально избежать обратных вариантов, потому что стоимость одной инверсии составляет как минимум стократное умножение. Мы можем сделать это, расширив систему координат, но ценой увеличения количества умножений в процессе, таких как координаты Якоби: XYZ += XYZ, и умножения более чем в 10 раз, в зависимости от алгоритма сложения. **
** GPU VS FPGA Accelerated MSM**
В этом разделе сравниваются две ведущие реализации MSM, PipeMSM и Sppark, где PipeMSM реализован на FPGA, а Sppark — на графических процессорах.
Sppark и PipeMSM используют современный алгоритм Pippenger для реализации MSM, также известный как алгоритм корзины; **
Sppark реализован с помощью CUDA; Их версии отличаются высокой степенью параллелизма и достигли впечатляющих результатов при работе на новейших графических процессорах.
Однако PipeMSM не только оптимизирует алгоритм, но и обеспечивает оптимизацию математических примитивов Модульного умножения и Сложения EC. PipeMSM обрабатывает весь «стек MSM», реализуя ряд математических приемов и оптимизаций, направленных на то, чтобы сделать MSM более подходящим для аппаратного обеспечения, и разрабатывая аппаратную конструкцию, предназначенную для уменьшения задержки с акцентом на распараллеливание.
Давайте кратко вспомним реализацию PipeMSM.
Низкая задержка
PipeMSM обеспечивает низкую задержку при выполнении нескольких MSM на большом количестве входов. Графические процессоры не обеспечивают детерминированную низкую задержку из-за динамического масштабирования частоты, а графические процессоры регулируют тактовую частоту в зависимости от рабочих нагрузок.
Но благодаря оптимизированной аппаратной конструкции реализации FPGA могут обеспечить детерминированную производительность и задержку для конкретных рабочих нагрузок.
Реализация дополнения EC
Сложение точек эллиптической кривой (EC Addition) реализовано в виде формулы с низкой задержкой, высокой степенью параллелизма и полной формулы (полная означает, что она правильно вычисляет сумму любых двух точек в группе эллиптических кривых). Добавление точек эллиптической кривой используется конвейерным способом в модуле добавления EC для уменьшения задержки.
Мы решили представить координаты в виде проективных координат, а в алгоритме сложения используем формулу сложения точек полной эллиптической кривой. Главное преимущество в том, что нам не приходится иметь дело с крайними случаями. Полные формулы;
Мы реализовали эту формулу сложения конвейерным и параллельным способом, и нашей схеме сумматора эллиптических кривых FPGA потребовалось всего 12 умножений, 17 сумм сложений, и эта формула была выполнена. Исходная формула требует умножения 15 по модулю и 13 сложений. Конструкция ПЛИС выглядит следующим образом
Мульти мод
Мы использовали алгоритмы редукции Барретта и Карацубы.
Редукция Барретта — это алгоритм, который эффективно вычисляет r≡ab mod p (где p фиксированное). Редукция Барретта пытается заменить деление (дорогостоящая операция) приблизительным делением. Допустимое отклонение может быть выбрано для описания диапазона, в пределах которого мы ищем правильный результат. Мы находим, что большая погрешность позволяет использовать меньшие константы редукции; Это уменьшает размер промежуточных значений, используемых в операциях уменьшения по модулю, что уменьшает количество умножений, необходимых для вычисления конечного результата.
В синем поле ниже мы видим, что из-за нашей высокой устойчивости к ошибкам нам приходится выполнять несколько проверок, чтобы найти точный результат.
В двух словах, алгоритм Карацубы используется для оптимизации умножения, которое мы выполняем в редукции Барретта. Алгоритм Карацубы упрощает умножение двух n-значных чисел до умножения трех n/2-значных чисел; Эти умножения могут упростить количество цифр, сделав их достаточно узкими, чтобы их можно было напрямую вычислить аппаратным обеспечением. Подробности можно прочитать в статье Инго: Pipe MSM
Используя вышеуказанные операторы, мы разработали реализацию MSM с низкой задержкой и высокой степенью параллелизма.
Основная идея заключается в том, что вместо того, чтобы вычислять весь MSM сразу, каждый фрагмент передается в сумматор EC параллельно. Результаты ЕС-сумматора аккумулируются в итоговый МСМ.
Конечный результат****
На диаграмме выше показано сравнение Sppark и PipeMSM.
Наиболее заметным является значительная экономия энергии, предлагаемая FPGA, которая может быть чрезвычайно важна для будущих крупномасштабных операций по производству контрольных изображений. Стоит отметить, что наша реализация была прототипирована и протестирована под @125MHz, и увеличение тактовой частоты до @500MHz может увеличить время вычислений в 4 раза и более.
Еще одно преимущество использования наших FPGA заключается в том, что их можно устанавливать в небольшие серверы, поскольку они потребляют меньше энергии и выделяют меньше тепла.
Мы находимся на ранних стадиях разработки FPGA для ZKP и должны ожидать дальнейших улучшений в алгоритмах. Кроме того, FPGA вычисляет MSM, пока процессор простаивает, и можно достичь более быстрого времени, используя FPGA в сочетании с системными ресурсами (CPU/GPU).
Сводка
ZKP стал ключевой технологией для распределенных систем.
Применение ZKP выйдет далеко за рамки простого расширения уровня Ethereum, позволяя передавать вычисления на аутсорсинг ненадежным третьим сторонам, позволяя разрабатывать ранее невозможные системы, такие как распределенные облачные вычисления, системы идентификации и многое другое.
Традиционно оптимизация ZKP была сосредоточена на улучшениях на программном уровне, но по мере роста спроса на более высокую производительность мы увидим более продвинутые решения для ускорения, включающие как аппаратное, так и программное обеспечение.
В настоящее время решения для ускорения, которые мы видим, в основном используют графические процессоры, потому что время разработки с использованием CUDA короткое, а текущие потребительские графические процессоры очень дешевы и распространены. Графический процессор также предлагает невероятную производительность. Так что графические процессоры вряд ли исчезнут из этого пространства в ближайшее время.
По мере того, как в эту сферу выходят более сложные команды разработчиков, вполне вероятно, что мы увидим, как FPGA будут лидировать с точки зрения энергоэффективности и производительности. По сравнению с графическими процессорами, FPGA предлагают более низкоуровневую настройку, а также больше вариантов конфигурации. FPGA обеспечивают более высокую скорость и гибкость разработки, чем ASIC. С быстрым развитием мира ZKP FPGA могут быть перепрошиты с помощью различных программ для различных систем и обновлений решений.
Однако для создания подтверждений в режиме, близком к реальному времени, может потребоваться комбинирование конфигураций GPU/FPGA/ASIC в зависимости от системы, для которой мы генерируем доказательства.
ZPU также, вероятно, будет развиваться, чтобы обеспечить чрезвычайно эффективные решения для крупномасштабных генераторов доказательств и маломощных устройств (подробнее см. предыдущую статью).
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Новая эра ZK, управляемая аппаратным ускорением
История на данный момент
Доказательства с нулевым разглашением (ZKP) становятся все более важными для децентрализованных систем. ZK впервые привлек к себе внимание общественности благодаря своему успеху в таких проектах, как ZCash, но сегодня ZK известен как решение для масштабирования Ethereum.
Используя ZK, уровень 2 (например, Scroll и Polygon), также известный как Rollups, разрабатывает zkEVM (zk Ethereum Virtual Machine). Эти zkEVM обрабатывают пакет транзакций и генерируют небольшое доказательство (в килобайтах). Эту аттестацию можно использовать для проверки всей сети того, что пакет транзакций действителен и правильный.
Однако на этом их использование не заканчивается. ZK позволяет использовать множество интересных областей применения.
Private Layer 1 – Mina, например, скрывает детали транзакций и данные в своем блокчейне, позволяя пользователям только подтверждать действительность своих транзакций, не раскрывая специфику самой транзакции. neptune.cash и Aleo также являются очень интересными проектами.
Децентрализованная облачная платформа - FedML и together.xyz позволяют децентрализованно обучать модели машинного обучения (ML), передавать вычисления на аутсорсинг в сеть и проверять правильность вычислений с помощью ZKP. Druglike создает более открытую платформу для поиска лекарств, используя аналогичные технологии.
Децентрализованное хранилище - Filecoin совершает революцию в облачных хранилищах, и ZK лежит в его основе, позволяя поставщикам хранилищ доказывать, что они хранят правильные данные в течение определенного периода времени.
ИГРА - Может появиться более продвинутая версия Darkforest, которая требует подтверждения в реальном времени. ZK также может расширить игру, чтобы снизить вероятность читерства. Может быть, вы также поработаете с децентрализованной облачной платформой, чтобы игра могла оплачивать собственный хостинг!
Идентификация - Децентрализованная аутентификация теперь также возможна через ZK. Вокруг этой идеи строится ряд интересных проектов. Например, notebook и zkemail (рекомендуется узнать).
Влияние ZK и децентрализованных систем огромно, однако развитие истории не идеально, и сегодня все еще существует множество препятствий и проблем. Процесс включения генерации доказательств очень ресурсоемкий и требует множества сложных математических операций. По мере того, как разработчики стремятся создавать более амбициозные и сложные протоколы и системы с использованием технологии ZK, как для создания доказательств, так и для процессов проверки, разработчики требуют меньших размеров доказательств, более высокой производительности и лучшей оптимизации.
В этой статье мы рассмотрим текущее состояние аппаратного ускорения и то, как оно будет играть ключевую роль в продвижении внедрения ZK.
Снарк против Старка
На сегодняшний день существует два популярных метода нулевого разглашения: zk-STARK и zk-SNARK (в этой статье мы проигнорировали Bulletproofs).
| | | | | --- | --- | --- | | зк-СТАРК | зк-СНАРК | | | Сложность - Прувер | O(N * poly-log(N)) | O(N * log(N)) | | Сложность - Верификатор | O(полилог(Н)) | О(1) | | Размер пробы | 45-200 КБ | ~ 288 байт | | 抗量子 | Да (на основе хеш-функции) | Нет | | Надежная настройка | Нет | Да | | Нулевое разглашение | Нет | Нет | | Интерактивность | Интерактивный или неинтерактивный | Неинтерактивный | | Документация для разработчиков | Ограниченный, но расширяющийся Хорошо |
表1:Снарк против Старка
Как упоминалось выше, между ними есть различия и компромиссы. Наиболее важным моментом является то, что доверенная настройка системы на основе zk-SNARK зависит по крайней мере от одного честного участника, участвующего в процессе доверенной установки, ключи которого уничтожены в конце процесса. С точки зрения ончейн-верификации, zk-SNARK намного дешевле с точки зрения платы за газ. Кроме того, пруфы zk-SNARK также значительно меньше, что делает их более дешевыми для хранения в блокчейне.
В настоящее время zk-SNARK более популярны, чем zk-STARK. Наиболее вероятная причина заключается в том, что zk-SNARK имеют гораздо более длительную историю. Другая возможная причина заключается в том, что Zcash, один из первых блокчейнов ZK, использовал zk-SNARK, поэтому большинство текущих инструментов разработки и документации вращаются вокруг экосистемы zk-SNARK.
Как создать ZK-приложение
Разработчикам могут потребоваться два компонента для завершения разработки приложения ZK
ZK-дружественный метод вычисления выражений (DSL или низкоуровневая библиотека).
Система аттестации, реализующая две функции: Proof и Verify.
DSL (предметно-ориентированный язык) и низкоуровневые библиотеки
Когда дело доходит до DSL, существует множество вариантов, таких как Circom, Halo2, Noir и многие другие. Circom, пожалуй, самый популярный на данный момент.
Когда дело доходит до низкоуровневых библиотек, популярным примером является Arkworks; Также в разработке находятся библиотеки, такие как ICICLE, которая является библиотекой ускорения CUDA.
Эти DSL предназначены для вывода замкнутых систем. В отличие от обычной программы, которая обычно вычисляется в виде x:= y *z, та же программа в ограниченном виде больше похожа на x-y * z = 0. Представляя программу в виде системы ограничений, мы обнаруживаем, что такие операции, как сложение или умножение, могут быть представлены одним ограничением. Однако более сложные операции, такие как битовые операции, могут потребовать сотен ограничений!
В результате, становится сложно реализовать некоторые хеш-функции в виде ZK-дружественных программ. В доказательствах с нулевым разглашением хэш-функции часто используются для обеспечения целостности данных и/или для проверки конкретных свойств данных, но из-за большого количества ограничений битовых операций некоторые хэш-функции трудно адаптировать к среде доказательств с нулевым разглашением. Эта сложность может повлиять на эффективность генерации и верификации доказательств и, таким образом, стать проблемой, которую разработчикам необходимо учитывать и решать при создании приложений на основе ZK
В результате становится сложно реализовать некоторые хеш-функции, чтобы они были ZK-совместимыми.
Доказательство
Систему доказательств можно сравнить с программным обеспечением, которое выполняет две основные задачи: генерацию доказательств и проверку доказательств. Контрольные системы обычно принимают в качестве входных данных схемы, доказательства и открытые/частные параметры.
Двумя наиболее популярными системами расстойки являются серии Groth16 и PLONK (Plonk, HyperPlonk, UltraPlonk)
| | | | | | | | --- | --- | --- | --- | --- | --- | | | Надежная настройка | Размер пробного образца | Сложность прувера | Сложность верификатора | Гибкость | | Грот16 | Специфичные для схемы | маленький | Низкий | Низкий | Низкий | | Плонк | Универсальность | Большой | Высокий | 常数 | Высокий |
表2:Groth16 vs Plonk
Как показано в таблице 2, Groth16 требует надежного процесса настройки, но Groth16 обеспечивает более быстрое время проверки и проверки, а также постоянный размер проверки.
Plonk предоставляет общую настройку, которая выполняет фазу предварительной обработки для схемы, которую вы запускаете, каждый раз, когда генерируется доказательство. Несмотря на поддержку множества каналов, время проверки Plonk постоянно.
Между ними также есть различия с точки зрения ограничений. Groth16 растет линейно с точки зрения размера ограничений и не обладает гибкостью, в то время как Plonk более гибок.
В целом, поймите, что производительность напрямую связана с количеством ограничений в вашем приложении ZK. Чем больше ограничений, тем больше операций должен вычислить проверщик.
узкое место
Система доказательств состоит из двух основных математических операций: мультискалярного умножения (MSM) и быстрого преобразования Фурье (БПФ). Сегодня мы рассмотрим системы, в которых существует и то, и другое, где MSM может занимать около 60% времени выполнения, в то время как БПФ может занимать около 30%.
MSM требует большого доступа к памяти, что в большинстве случаев потребляет много памяти на машине, а также выполняет множество скалярных операций умножения.
Алгоритмы БПФ часто требуют переупорядочивания входных данных в определенном порядке для выполнения преобразований. Это может потребовать большого количества перемещений данных и может стать узким местом, особенно при больших размерах входных данных. Использование кэша также может быть проблемой, если шаблоны доступа к памяти не вписываются в иерархию кэша.
**В данном случае аппаратное ускорение является единственным способом полной оптимизации производительности ZKP. **
Аппаратное ускорение
Когда дело доходит до аппаратного ускорения, это напоминает нам о том, как ASIC и графические процессоры доминировали в майнинге Bitcoin и Ethereum.
Несмотря на то, что оптимизация программного обеспечения не менее важна и ценна, у нее есть свои ограничения. Аппаратная оптимизация, с другой стороны, может улучшить параллелизм за счет разработки FPGA с несколькими процессорами, например, уменьшить синхронизацию потоков или векторизацию. Доступ к памяти также можно оптимизировать более эффективно за счет улучшения иерархий памяти и шаблонов доступа.
Сейчас в пространстве ZKP основная тенденция, похоже, сместилась: графические процессоры и FPGA.
В краткосрочной перспективе графические процессоры имеют преимущество в цене, особенно после того, как ETH переходит на proof-of-stake (POS), оставляя большое количество GPU-майнеров в режиме ожидания и ожидания. Кроме того, графические процессоры имеют преимущество в коротких циклах разработки и предоставляют разработчикам большой параллелизм по принципу «подключи и работай».
Тем не менее, FPGA должны наверстать упущенное, особенно при сравнении форм-факторов и энергопотребления. FPGA также обеспечивают меньшую задержку для высокоскоростных потоков данных. Когда несколько FPGA объединены в кластер, они обеспечивают более высокую производительность по сравнению с кластерами GPU.
ГРАФИЧЕСКИЙ ПРОЦЕССОР ПРОТИВ FPGA
ГРАФИЧЕСКИЙ ПРОЦЕССОР:
Время разработки: графические процессоры обеспечивают быстрое время разработки. Документация для разработчиков таких фреймворков, как CUDA и OpenCL, хорошо проработана и популярна.
Энергопотребление: графические процессоры очень «энергоемкие». Даже когда разработчики используют параллелизм на уровне данных и параллелизм на уровне потоков, графические процессоры по-прежнему потребляют много энергии.
Доступность: Графические процессоры потребительского класса дешевы и легко доступны прямо сейчас.
ПЛИС:
Цикл разработки: ПЛИС имеют более сложный цикл разработки и требуют более специализированных инженеров. FPGA позволяют инженерам достичь многих «низкоуровневых» оптимизаций, которые не могут быть достигнуты графическими процессорами.
Задержка: FPGA обеспечивают меньшую задержку, особенно при обработке больших потоков данных.
Соотношение цены и доступности: FPGA дороже, чем графические процессоры, и не так легко доступны, как графические процессоры.
ЗПРИЗ
В наше время, когда дело доходит до узкого места аппаратной оптимизации и ZKP, существует конкуренция, которой не избежать - ZPRIZE
ZPrize является одной из самых важных инициатив в области ZK на данный момент. ZPrize — это соревнование, которое поощряет команды разрабатывать аппаратное ускорение для ключевых узких мест ZKP (например, MSM, NTT, Poseidon и т. д.) на нескольких платформах (например, FPGA, графических процессорах, мобильных устройствах и браузерах) на основе задержки, пропускной способности и эффективности.
Результат получился очень интересным. Например, улучшения графического процессора огромны:
МСМ в 2^26 увеличился на 131% с 5,86 секунды до 2,52 секунды. С другой стороны, решения FPGA, как правило, не имеют каких-либо тестов по сравнению с результатами GPU, с которыми можно сравнивать предыдущие тесты, и большинство решений FPGA впервые имеют открытый исходный код, и ожидается, что такие алгоритмы будут улучшаться в будущем.
Эти результаты указывают на направление, в котором большинство разработчиков чувствуют себя комфортно при разработке своих решений для аппаратного ускорения. Многие команды соревнуются за категорию GPU, но лишь небольшой процент соревнуется за категорию FPGA. Я не уверен, связано ли это с отсутствием опыта при разработке для FPGA, или с тем, что большинство FPGA-компаний/команд предпочитают разрабатывать тайно, чтобы продавать свои решения на коммерческой основе.
ZPrize предоставила сообществу несколько очень интересных исследований. По мере того, как будут начинаться новые раунды ZPrize, мы будем видеть все больше и больше интересных решений и проблем.
Практические примеры аппаратного ускорения
Если взять в качестве примера Groth16, то при рассмотрении реализации rapidsnark для Groth16 можно заметить, что выполняются две основные операции: БПФ (быстрое преобразование Фурье) и MSM (мультискалярное умножение); Эти две основные операции являются общими для многих систем доказательства. Время их выполнения напрямую связано с количеством ограничений в цепи. Естественно, что количество ограничений увеличивается по мере написания более сложных схем.
Чтобы получить представление о том, насколько ресурсоемкими являются операции БПФ и МСМ, мы можем ознакомиться с тестом Ingonyama для схемы Groth16 (процесс Vanilla C2 от Filecoin, выполненный на секторе 32 ГБ), и результаты будут следующими
Как показано на рисунке выше, MSM (Multiscalar Multiplication) может отнимать много времени и быть серьезным узким местом производительности для многих доказательств, что делает MSM одним из самых важных криптографических операторов, которые необходимо ускорить.
Итак, сколько вычислений занимает МСМ для доказывателя в других системах доказательств ZK? Это показано на рисунке ниже
В Plonk на долю МСМ приходится более 85% накладных расходов, как показано в последней статье Ингоньямы «Трубный МСМ». **
Так как же аппаратное ускорение должно ускорить MSM? **
МСМ
Прежде чем говорить о том, как ускорить МСМ, нужно понять, что такое МСМ
Мультискалярное умножение (MSM) — это алгоритм вычисления суммы кратных скалярных умножений в следующем виде
где G — точка в группе эллиптических кривых, a — скаляр, а результатом МСМ также будет точка эллиптической кривой
Мы можем разложить МСМ на два основных подкомпонента:
Модульное умножение
Сложение точек эллиптической кривой
Возьмем в качестве примера Affine(x,y) для выполнения наивной операции P+Q.
Когда мы хотим вычислить P + Q = R, нам нужно вычислить значение k по абсциссе k и P,Q
Получаем координаты R. Процесс вычисления такой же, как и выше, в этом процессе мы выполняем 2 умножения умножения, 1 операцию квадрата, 1 обратную операцию и несколько раз операции сложения и вычитания. Стоит отметить, что вышеуказанные операции выполняются в конечном поле, т.е. под модулем P. В реальности P будет очень большим. **
Стоимость вышеуказанной операции заключается в нахождении обратной >> умножения** **> **** в квадрате, а стоимость сложения и вычитания ничтожно мала.
Поэтому мы хотим максимально избежать обратных вариантов, потому что стоимость одной инверсии составляет как минимум стократное умножение. Мы можем сделать это, расширив систему координат, но ценой увеличения количества умножений в процессе, таких как координаты Якоби: XYZ += XYZ, и умножения более чем в 10 раз, в зависимости от алгоритма сложения. **
** GPU VS FPGA Accelerated MSM**
В этом разделе сравниваются две ведущие реализации MSM, PipeMSM и Sppark, где PipeMSM реализован на FPGA, а Sppark — на графических процессорах.
Sppark и PipeMSM используют современный алгоритм Pippenger для реализации MSM, также известный как алгоритм корзины; **
Sppark реализован с помощью CUDA; Их версии отличаются высокой степенью параллелизма и достигли впечатляющих результатов при работе на новейших графических процессорах.
Однако PipeMSM не только оптимизирует алгоритм, но и обеспечивает оптимизацию математических примитивов Модульного умножения и Сложения EC. PipeMSM обрабатывает весь «стек MSM», реализуя ряд математических приемов и оптимизаций, направленных на то, чтобы сделать MSM более подходящим для аппаратного обеспечения, и разрабатывая аппаратную конструкцию, предназначенную для уменьшения задержки с акцентом на распараллеливание.
Давайте кратко вспомним реализацию PipeMSM.
Низкая задержка
PipeMSM обеспечивает низкую задержку при выполнении нескольких MSM на большом количестве входов. Графические процессоры не обеспечивают детерминированную низкую задержку из-за динамического масштабирования частоты, а графические процессоры регулируют тактовую частоту в зависимости от рабочих нагрузок.
Но благодаря оптимизированной аппаратной конструкции реализации FPGA могут обеспечить детерминированную производительность и задержку для конкретных рабочих нагрузок.
Реализация дополнения EC
Сложение точек эллиптической кривой (EC Addition) реализовано в виде формулы с низкой задержкой, высокой степенью параллелизма и полной формулы (полная означает, что она правильно вычисляет сумму любых двух точек в группе эллиптических кривых). Добавление точек эллиптической кривой используется конвейерным способом в модуле добавления EC для уменьшения задержки.
Мы решили представить координаты в виде проективных координат, а в алгоритме сложения используем формулу сложения точек полной эллиптической кривой. Главное преимущество в том, что нам не приходится иметь дело с крайними случаями. Полные формулы;
Мы реализовали эту формулу сложения конвейерным и параллельным способом, и нашей схеме сумматора эллиптических кривых FPGA потребовалось всего 12 умножений, 17 сумм сложений, и эта формула была выполнена. Исходная формула требует умножения 15 по модулю и 13 сложений. Конструкция ПЛИС выглядит следующим образом
Мульти мод
Мы использовали алгоритмы редукции Барретта и Карацубы.
Редукция Барретта — это алгоритм, который эффективно вычисляет r≡ab mod p (где p фиксированное). Редукция Барретта пытается заменить деление (дорогостоящая операция) приблизительным делением. Допустимое отклонение может быть выбрано для описания диапазона, в пределах которого мы ищем правильный результат. Мы находим, что большая погрешность позволяет использовать меньшие константы редукции; Это уменьшает размер промежуточных значений, используемых в операциях уменьшения по модулю, что уменьшает количество умножений, необходимых для вычисления конечного результата.
В синем поле ниже мы видим, что из-за нашей высокой устойчивости к ошибкам нам приходится выполнять несколько проверок, чтобы найти точный результат.
В двух словах, алгоритм Карацубы используется для оптимизации умножения, которое мы выполняем в редукции Барретта. Алгоритм Карацубы упрощает умножение двух n-значных чисел до умножения трех n/2-значных чисел; Эти умножения могут упростить количество цифр, сделав их достаточно узкими, чтобы их можно было напрямую вычислить аппаратным обеспечением. Подробности можно прочитать в статье Инго: Pipe MSM
Используя вышеуказанные операторы, мы разработали реализацию MSM с низкой задержкой и высокой степенью параллелизма.
Основная идея заключается в том, что вместо того, чтобы вычислять весь MSM сразу, каждый фрагмент передается в сумматор EC параллельно. Результаты ЕС-сумматора аккумулируются в итоговый МСМ.
Конечный результат****
На диаграмме выше показано сравнение Sppark и PipeMSM.
Наиболее заметным является значительная экономия энергии, предлагаемая FPGA, которая может быть чрезвычайно важна для будущих крупномасштабных операций по производству контрольных изображений. Стоит отметить, что наша реализация была прототипирована и протестирована под @125MHz, и увеличение тактовой частоты до @500MHz может увеличить время вычислений в 4 раза и более.
Еще одно преимущество использования наших FPGA заключается в том, что их можно устанавливать в небольшие серверы, поскольку они потребляют меньше энергии и выделяют меньше тепла.
Мы находимся на ранних стадиях разработки FPGA для ZKP и должны ожидать дальнейших улучшений в алгоритмах. Кроме того, FPGA вычисляет MSM, пока процессор простаивает, и можно достичь более быстрого времени, используя FPGA в сочетании с системными ресурсами (CPU/GPU).
Сводка
ZKP стал ключевой технологией для распределенных систем.
Применение ZKP выйдет далеко за рамки простого расширения уровня Ethereum, позволяя передавать вычисления на аутсорсинг ненадежным третьим сторонам, позволяя разрабатывать ранее невозможные системы, такие как распределенные облачные вычисления, системы идентификации и многое другое.
Традиционно оптимизация ZKP была сосредоточена на улучшениях на программном уровне, но по мере роста спроса на более высокую производительность мы увидим более продвинутые решения для ускорения, включающие как аппаратное, так и программное обеспечение.
В настоящее время решения для ускорения, которые мы видим, в основном используют графические процессоры, потому что время разработки с использованием CUDA короткое, а текущие потребительские графические процессоры очень дешевы и распространены. Графический процессор также предлагает невероятную производительность. Так что графические процессоры вряд ли исчезнут из этого пространства в ближайшее время.
По мере того, как в эту сферу выходят более сложные команды разработчиков, вполне вероятно, что мы увидим, как FPGA будут лидировать с точки зрения энергоэффективности и производительности. По сравнению с графическими процессорами, FPGA предлагают более низкоуровневую настройку, а также больше вариантов конфигурации. FPGA обеспечивают более высокую скорость и гибкость разработки, чем ASIC. С быстрым развитием мира ZKP FPGA могут быть перепрошиты с помощью различных программ для различных систем и обновлений решений.
Однако для создания подтверждений в режиме, близком к реальному времени, может потребоваться комбинирование конфигураций GPU/FPGA/ASIC в зависимости от системы, для которой мы генерируем доказательства.
ZPU также, вероятно, будет развиваться, чтобы обеспечить чрезвычайно эффективные решения для крупномасштабных генераторов доказательств и маломощных устройств (подробнее см. предыдущую статью).