Доведення з нульовим розголошенням (ZKP) набувають все більшого значення для децентралізованих систем. ZK вперше потрапила в поле зору громадськості завдяки своєму успіху в таких проектах, як ZCash, але сьогодні ZK відома як рішення для масштабування Ethereum.
Використовуючи ZK, рівень 2 (наприклад, Scroll і Polygon), також відомий як Rollups, розробляє zkEVM (віртуальна машина zk Ethereum). Ці zkEVM обробляють пакет транзакцій і генерують невеликий доказ (у кілобайтах). Ця атестація може бути використана для перевірки всієї мережі, що пакет транзакцій є дійсним і правильним.
Однак на цьому їх використання не закінчується. ZK дозволяє використовувати різноманітні цікаві програми.
Приватний рівень 1 – Mina, наприклад, приховує деталі транзакцій і дані у своєму блокчейні, дозволяючи користувачам лише доводити дійсність своїх транзакцій, не розкриваючи специфіки самої транзакції. neptune.cash і Aleo також дуже цікаві проекти.
Децентралізована хмарна платформа – FedML і together.xyz дозволяють децентралізовано навчати моделі машинного навчання (ML), передавати обчислення на аутсорсинг мережі та перевіряти правильність обчислень за допомогою ZKP. Druglike створює більш відкриту платформу для пошуку ліків, використовуючи аналогічні технології.
Децентралізоване сховище - Filecoin революціонізує хмарне сховище, і ZK лежить в його основі, дозволяючи постачальникам сховищ довести, що вони зберігали правильні дані протягом певного періоду часу.
GAME - Може з'явитися більш просунута версія Darkforest, яка вимагає доказів у реальному часі. ЗК також може розширити гру, щоб знизити ймовірність шахрайства. Можливо, ви також попрацюєте з децентралізованою хмарною платформою, щоб дозволити грі оплачувати власний хостинг!
Identity - Децентралізована автентифікація тепер також можлива через ZK. Навколо цієї ідеї будується ряд цікавих проектів. Наприклад, блокнот і zkemail (рекомендуємо дізнатися про).
Вплив ЗК і децентралізованих систем величезний, проте розвиток історії не ідеальний, і на сьогоднішній день все ще існує багато перешкод і викликів. Процес включення генерації доведень дуже ресурсозатратний і вимагає безлічі складних математичних операцій. Оскільки розробники прагнуть створювати більш амбітні та складні протоколи та системи з використанням технології ZK, як для генерації доказів, так і для процесів верифікації, розробники вимагають менших розмірів доказів, швидшої продуктивності та кращої оптимізації.
У цій статті ми розглянемо поточний стан апаратного прискорення та те, як воно відіграватиме ключову роль у просуванні впровадження ZK.
Снарк проти Старка
Сьогодні є дві популярні техніки з нульовим розголошенням, zk-STARK і zk-SNARK (у цій статті ми проігнорували куленепробивні пристрої).
| | | |
| --- | --- | --- |
| zk-STARK | zk-SNARK | |
| Складність - Prover | O(N * poly-log(N)) | O(N * log(N)) |
| Складність - Верифікатор | O(poly-log(N)) | О(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 або низькорівнева бібліотека).
Система атестації, яка реалізує дві функції: Prove і Verify.
DSL (доменно-специфічна мова) і низькорівневі бібліотеки
Коли справа доходить до DSL, є багато варіантів, таких як Circom, Halo2, Noir та багато інших. Цирком, мабуть, найпопулярніший на даний момент.
Коли справа доходить до низькорівневих бібліотек, популярним прикладом є Arkworks; Існують також бібліотеки, що знаходяться в розробці, такі як ICICLE, яка є бібліотекою прискорення CUDA.
Ці DSL призначені для виведення обмежених систем. На відміну від звичайної програми, яка зазвичай обчислюється у вигляді x:= y *z, ця ж програма в обмеженому вигляді більше схожа на x-y * z = 0. Представляючи програму як систему обмежень, ми знаходимо, що такі операції, як додавання або множення, можуть бути представлені одним обмеженням. Однак більш складні операції, такі як бітові операції, можуть вимагати сотень обмежень!
В результаті стає складною реалізація деяких хеш-функцій як дружніх до ZK програм. У доведеннях з нульовим розголошенням, хеш-функції часто використовуються для забезпечення цілісності даних та/або для перевірки конкретних властивостей даних, але через велику кількість обмежень бітових операцій деякі хеш-функції важко адаптувати до середовища доведень з нульовим розголошенням. Ця складність може вплинути на ефективність генерації та верифікації доказів, а отже, стати проблемою, яку розробники повинні враховувати та вирішувати при створенні додатків на основі ZK
В результаті, стає складно реалізувати деякі хеш-функції, щоб вони були дружніми до ZK.
Доказ
Систему доказів можна порівняти з програмним забезпеченням, яке виконує два основні завдання: генерування доказів і верифікацію доказів. Системи доказів зазвичай приймають схеми, докази та публічні/приватні параметри як вхідні дані.
Двома найбільш популярними пробними системами є серії Groth16 і PLONK (Plonk, HyperPlonk, UltraPlonk)
Як показано в таблиці 2, Groth16 вимагає надійного процесу налаштування, але Groth16 забезпечує нам швидший час доказу та перевірки, а також постійний розмір доказу.
Plonk надає загальну установку, яка виконує фазу попередньої обробки для схеми, яку ви використовуєте, щоразу, коли генерується доказ. Незважаючи на підтримку багатьох схем, час перевірки Плонк постійний.
Між ними також є відмінності з точки зору обмежень. Groth16 зростає лінійно з точки зору розміру обмежень і йому не вистачає гнучкості, в той час як Plonk більш гнучкий.
Загалом, зрозумійте, що продуктивність безпосередньо пов'язана з кількістю обмежень у вашому додатку ZK. Чим більше обмежень, тим більше операцій повинен обчислити програматор.
Вузьке місце
Система доведення складається з двох основних математичних операцій: мультискалярного множення (МСМ) і швидкого перетворення Фур'є (ШПФ). Сьогодні ми розглянемо системи, де є і те, і інше, де ЧСЧ може займати близько 60% часу виконання, а ШПФ – близько 30%.
MSM вимагає великого доступу до пам'яті, що в більшості випадків споживає багато пам'яті на машині, а також виконує безліч операцій скалярного множення.
Алгоритми ШПФ часто вимагають перестановки вхідних даних у певному порядку для виконання перетворень. Це може вимагати багато переміщення даних і може бути вузьким місцем, особливо для великих розмірів вхідних даних. Використання кешу також може бути проблемою, якщо шаблони доступу до пам'яті не вписуються в ієрархію кешу.
** У цьому випадку апаратне прискорення є єдиним способом повної оптимізації продуктивності ZKP. **
Апаратне прискорення
Коли справа доходить до апаратного прискорення, це нагадує нам про те, як ASIC і GPU домінували в майнінгу Bitcoin та Ethereum.
Хоча оптимізація програмного забезпечення однаково важлива та цінна, вона має свої обмеження. Апаратна оптимізація, з іншого боку, може покращити паралелізм шляхом проектування FPGA з декількома процесорами, такими як зменшення синхронізації потоків або векторизація. Доступ до пам'яті також можна оптимізувати ефективніше, покращивши ієрархію пам'яті та шаблони доступу.
Зараз у просторі ZKP, схоже, змістилася основна тенденція: графічні процесори та FPGA.
У короткостроковій перспективі графічні процесори мають перевагу в ціні, особливо після того, як ETH переходить на proof-of-stake (POS), залишаючи велику кількість майнерів GPU простою та в режимі очікування. Крім того, графічні процесори мають перевагу коротких циклів розробки та забезпечують розробникам багато паралелізму «plug-and-play».
Однак FPGA повинні надолужити згаяне, особливо при порівнянні форм-факторів і енергоспоживання. FPGA також забезпечують меншу затримку для високошвидкісних потоків даних. Коли кілька FPGA згруповані разом, вони забезпечують кращу продуктивність порівняно з кластерами графічних процесорів.
ГРАФІЧНИЙ ПРОЦЕСОР ПРОТИ FPGA
Графічний процесор:
Час розробки: Графічні процесори забезпечують швидкий час розробки. Документація розробників для таких фреймворків, як CUDA та OpenCL, добре розроблена та популярна.
Енергоспоживання: графічні процесори дуже «енергоємні». Навіть коли розробники використовують переваги паралелізму на рівні даних і паралелізму на рівні потоків, графічні процесори все одно споживають багато енергії.
Доступність: Графічні процесори споживчого класу дешеві та легко доступні прямо зараз.
FPGA:
Цикл розробки: FPGA мають складніший цикл розробки та вимагають більш спеціалізованих інженерів. FPGA дозволяють інженерам досягти багатьох «низькорівневих» оптимізацій, які не під силу графічним процесорам.
Затримка: FPGA забезпечують меншу затримку, особливо під час обробки великих потоків даних.
Вартість проти доступності: FPGA дорожчі за графічні процесори та не такі легкодоступні, як графічні процесори.
ZPRIZE
У наш час, коли мова заходить про вузьке місце апаратної оптимізації та 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, то побачимо, що виконуються дві основні операції: FFT (швидке перетворення Фур'є) і MSM (мультискалярне множення); Ці дві основні операції є загальними для багатьох систем доведення. Час їх виконання безпосередньо пов'язане з кількістю обмежень в схемі. Природно, число обмежень збільшується в міру написання більш складних схем.
Щоб отримати уявлення про те, наскільки інтенсивними є обчислювальні операції FFT і MSM, ми можемо ознайомитися з бенчмарком схеми Groth16 від Ingonyama (процес Vanilla C2 від Filecoin, виконаний на секторі об'ємом 32 ГБ), і результати будуть наступними
Як показано на малюнку вище, ЧСЧ (мультискалярне множення) може зайняти багато часу і стати серйозним вузьким місцем продуктивності для багатьох доказів, що робить ЧСЧ одним з найважливіших криптографічних операторів, які потрібно прискорити.
Отже, який обсяг обчислень займає МСМ для пруфера в інших системах доведення ЗК? Це показано на малюнку нижче
У Плонку на ЧСЧ припадає понад 85% накладних витрат, як показано в останній статті Інгоньями «Труба МСМ». **
Отже, як апаратне прискорення має прискорити ЧСЧ? **
ЧСЧ
Перш ніж говорити про те, як прискорити ЧСЧ, потрібно розібратися, що таке ЧСЧ
Мультискалярне множення (МСМ) – це алгоритм обчислення суми кратних скалярних множень у наступному вигляді
де G — точка в еліптичній групі кривих, a — скалярна, а результатом MSM також буде точка еліптичної кривої
Ми можемо розкласти ЧСЧ на два основних підкомпоненти:
Модульне множення
Додавання еліптичної кривої точки
Візьмемо для прикладу Affine(x,y) для виконання наївної операції P+Q.
Коли ми хочемо обчислити P + Q = R, нам потрібно обчислити значення k, за абсцисою k і P,Q
Отримати координати R. Процес обчислення такий, як описано вище, у цьому процесі ми виконуємо 2 рази множення, 1 квадратну операцію, 1 обернену операцію та кілька разів операції додавання та віднімання. Варто відзначити, що вищеописані операції виконуються в скінченному полі, тобто під mod P. В реальності Р буде дуже великим. **
Вартість вищевказаної операції полягає в тому, щоб знайти обернене >> множення** **> **** в квадраті, а витрати на додавання і віднімання незначні.
Тому ми хочемо максимально уникати обернених, тому що вартість одиночної інверсії становить щонайменше стократне множення. Ми можемо зробити це, розширивши систему координат, але ціною збільшення кількості множень у процесі, таких як координати Якобі: XYZ += XYZ, і множення більше 10 разів, залежно від алгоритму додавання. **
GPU VS FPGA прискорений МСМ
У цьому розділі порівнюються дві провідні реалізації МСМ, PipeMSM і Sppark, де PipeMSM реалізується на FPGA, а Sppark – на графічних процесорах.
Sppark і PipeMSM використовують найсучасніший алгоритм Pippenger для реалізації MSM, також відомий як алгоритм сегмента; **
Sppark реалізований за допомогою CUDA; Їхні версії відрізняються високою паралельністю і досягли вражаючих результатів при роботі на новітніх графічних процесорах.
Однак PipeMSM не тільки оптимізує алгоритм, але й забезпечує оптимізацію математичних примітивів модульного множення та додавання EC. PipeMSM обробляє весь «стек МСМ», реалізуючи серію математичних трюків та оптимізацій, спрямованих на те, щоб зробити MSM більш придатним для апаратного забезпечення, та розробляючи апаратну конструкцію, призначену для зменшення затримки з акцентом на розпаралелювання.
Давайте коротко підсумуємо реалізацію PipeMSM.
Низька затримка
PipeMSM призначений для забезпечення низької затримки при виконанні декількох ЧСЧ на великій кількості входів. Графічні процесори не пропонують детерміновано низьку затримку через динамічне масштабування частоти, а графічні процесори регулюють свою тактову частоту залежно від робочих навантажень.
Але завдяки оптимізованому апаратному дизайну, реалізації FPGA можуть забезпечити детерміновану продуктивність і затримку для конкретних робочих навантажень.
Впровадження додавання ЄС
Додавання точок еліптичної кривої (EC Addition) реалізовано у вигляді формули з низькою затримкою, дуже паралельної та завершеної (complete означає, що вона правильно обчислює суму будь-яких двох точок у групі еліптичних кривих). Додавання еліптичної кривої використовується конвеєрним способом у модулі додавання EC для зменшення затримки.
Ми вирішили представити координати як проективні координати, і в алгоритмі додавання ми використовуємо формулу додавання точки еліптичної кривої. Головна перевага полягає в тому, що нам ** не доводиться мати справу з крайніми кейсами**. Повні формули;
Ми реалізували цю формулу додавання конвеєрно і паралельно, і наша схема суматора еліптичної кривої FPGA потребувала лише 12 множень, 17 сум доданків, і ця формула була виконана. Вихідна формула вимагає 15 множення за модулем і 13 додавання. Конструкція FPGA наступна
Мультимод
Ми використовували алгоритми Barrett Reduction і Karatsuba.
Редукція Барретта — це алгоритм, який ефективно обчислює r≡ab mod p (де p є фіксованим). Скорочення Барретта намагається замінити ділення (дорога операція) приблизним діленням. Допуск до помилки може бути обраний для опису діапазону, в якому ми шукаємо правильний результат. Виявлено, що велика толерантність до похибки дозволяє використовувати менші константи скорочення; При цьому зменшується розмір проміжних значень, що використовуються в операціях скорочення за модулем, що зменшує кількість множень, необхідних для обчислення кінцевого результату.
У синьому полі нижче ми бачимо, що через нашу високу толерантність до помилок нам доводиться виконувати кілька перевірок, щоб знайти точний результат.
У двох словах, алгоритм Карацуби використовується для оптимізації множення, яке ми виконуємо в Скорочення Барретта. Алгоритм Карацуби спрощує множення двох n-цифр до множення трьох n/2 цифр; Ці множення можуть спростити кількість цифр, щоб вони були достатньо вузькими, щоб їх можна було безпосередньо обчислити апаратним забезпеченням. Подробиці можна прочитати в статті Інго: Pipe MSM
Використовуючи вищезгадані оператори, ми розробили реалізацію MSM з низькою затримкою, високопаралельну імплементацію.
Основна ідея полягає в тому, що замість того, щоб обчислювати весь ЧСЧ відразу, кожен фрагмент передається в суматор EC паралельно. Результати суматора ЕК акумулюються в підсумковий МСМ.
Кінцевий результат****
На діаграмі вище показано порівняння між Sppark і PipeMSM.
Найбільш помітною є значна економія енергії, яку пропонують FPGA, що може бути надзвичайно важливим для майбутніх великомасштабних операцій з виробництва пробної продукції. Варто зазначити, що наша реалізація була прототипом і порівняльним аналізом під @125MHz, і збільшення тактової частоти до @500MHz могло збільшити час обчислень у 4 рази або більше.
Ще однією перевагою використання наших ПЛІС є те, що їх можна встановлювати на невеликих серверах шасі, оскільки вони споживають менше енергії та генерують менше тепла.
Ми знаходимося на ранніх стадіях розробки FPGA для ZKP і повинні очікувати подальших удосконалень алгоритмів. Крім того, FPGA обчислює MSM, коли центральний процесор простоює, і можна досягти швидшого часу, використовуючи FPGA у поєднанні з системними ресурсами (CPU/GPU).
Зведення
ЗКП стала ключовою технологією для розподілених систем.
Застосування ZKP вийде далеко за рамки простого розширення рівня Ethereum, дозволяючи передавати обчислення на аутсорсинг ненадійним третім сторонам, дозволяючи розробляти раніше неможливі системи, такі як розподілені хмарні обчислення, системи ідентифікації тощо.
Традиційно оптимізація ZKP була зосереджена на вдосконаленні програмного рівня, але в міру зростання попиту на більш високу продуктивність ми побачимо більш просунуті рішення для прискорення, що включають як апаратне, так і програмне забезпечення.
В даний час рішення для прискорення, які ми бачимо, в основному використовують графічні процесори, тому що час розробки з використанням CUDA короткий, а поточні споживчі графічні процесори дуже дешеві та в достатку. Графічний процесор також пропонує неймовірну продуктивність. Тож графічні процесори навряд чи зникнуть із цього простору найближчим часом.
У міру того, як у космос виходять більш складні команди розробників, цілком ймовірно, що ми побачимо FPGA, які лідирують з точки зору енергоефективності та продуктивності. У порівнянні з графічними процесорами, FPGA пропонують більш низькорівневу кастомізацію, а також більше можливостей конфігурації. FPGA пропонують швидшу швидкість розробки та гнучкість, ніж ASIC. Зі швидким розвитком світу ZKP FPGA можна перепрошивати різними програмами для розміщення різних систем та оновлень рішень.
Однак, щоб генерувати докази майже в реальному часі, може знадобитися комбінувати конфігурації GPU/FPGA/ASIC залежно від системи, для якої ми генеруємо докази.
ЗПУ також, ймовірно, буде розвиватися, щоб надавати надзвичайно ефективні рішення для великомасштабних генераторів і малопотужних пристроїв (докладніше див. попередню статтю).
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
Нова ера ZK, зумовлена апаратним прискоренням
Поки що історія
Доведення з нульовим розголошенням (ZKP) набувають все більшого значення для децентралізованих систем. ZK вперше потрапила в поле зору громадськості завдяки своєму успіху в таких проектах, як ZCash, але сьогодні ZK відома як рішення для масштабування Ethereum.
Використовуючи ZK, рівень 2 (наприклад, Scroll і Polygon), також відомий як Rollups, розробляє zkEVM (віртуальна машина zk Ethereum). Ці zkEVM обробляють пакет транзакцій і генерують невеликий доказ (у кілобайтах). Ця атестація може бути використана для перевірки всієї мережі, що пакет транзакцій є дійсним і правильним.
Однак на цьому їх використання не закінчується. ZK дозволяє використовувати різноманітні цікаві програми.
Приватний рівень 1 – Mina, наприклад, приховує деталі транзакцій і дані у своєму блокчейні, дозволяючи користувачам лише доводити дійсність своїх транзакцій, не розкриваючи специфіки самої транзакції. neptune.cash і Aleo також дуже цікаві проекти.
Децентралізована хмарна платформа – FedML і together.xyz дозволяють децентралізовано навчати моделі машинного навчання (ML), передавати обчислення на аутсорсинг мережі та перевіряти правильність обчислень за допомогою ZKP. Druglike створює більш відкриту платформу для пошуку ліків, використовуючи аналогічні технології.
Децентралізоване сховище - Filecoin революціонізує хмарне сховище, і ZK лежить в його основі, дозволяючи постачальникам сховищ довести, що вони зберігали правильні дані протягом певного періоду часу.
GAME - Може з'явитися більш просунута версія Darkforest, яка вимагає доказів у реальному часі. ЗК також може розширити гру, щоб знизити ймовірність шахрайства. Можливо, ви також попрацюєте з децентралізованою хмарною платформою, щоб дозволити грі оплачувати власний хостинг!
Identity - Децентралізована автентифікація тепер також можлива через ZK. Навколо цієї ідеї будується ряд цікавих проектів. Наприклад, блокнот і zkemail (рекомендуємо дізнатися про).
Вплив ЗК і децентралізованих систем величезний, проте розвиток історії не ідеальний, і на сьогоднішній день все ще існує багато перешкод і викликів. Процес включення генерації доведень дуже ресурсозатратний і вимагає безлічі складних математичних операцій. Оскільки розробники прагнуть створювати більш амбітні та складні протоколи та системи з використанням технології ZK, як для генерації доказів, так і для процесів верифікації, розробники вимагають менших розмірів доказів, швидшої продуктивності та кращої оптимізації.
У цій статті ми розглянемо поточний стан апаратного прискорення та те, як воно відіграватиме ключову роль у просуванні впровадження ZK.
Снарк проти Старка
Сьогодні є дві популярні техніки з нульовим розголошенням, zk-STARK і zk-SNARK (у цій статті ми проігнорували куленепробивні пристрої).
| | | | | --- | --- | --- | | zk-STARK | zk-SNARK | | | Складність - Prover | O(N * poly-log(N)) | O(N * log(N)) | | Складність - Верифікатор | O(poly-log(N)) | О(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 або низькорівнева бібліотека).
Система атестації, яка реалізує дві функції: Prove і Verify.
DSL (доменно-специфічна мова) і низькорівневі бібліотеки
Коли справа доходить до DSL, є багато варіантів, таких як Circom, Halo2, Noir та багато інших. Цирком, мабуть, найпопулярніший на даний момент.
Коли справа доходить до низькорівневих бібліотек, популярним прикладом є Arkworks; Існують також бібліотеки, що знаходяться в розробці, такі як ICICLE, яка є бібліотекою прискорення CUDA.
Ці DSL призначені для виведення обмежених систем. На відміну від звичайної програми, яка зазвичай обчислюється у вигляді x:= y *z, ця ж програма в обмеженому вигляді більше схожа на x-y * z = 0. Представляючи програму як систему обмежень, ми знаходимо, що такі операції, як додавання або множення, можуть бути представлені одним обмеженням. Однак більш складні операції, такі як бітові операції, можуть вимагати сотень обмежень!
В результаті стає складною реалізація деяких хеш-функцій як дружніх до ZK програм. У доведеннях з нульовим розголошенням, хеш-функції часто використовуються для забезпечення цілісності даних та/або для перевірки конкретних властивостей даних, але через велику кількість обмежень бітових операцій деякі хеш-функції важко адаптувати до середовища доведень з нульовим розголошенням. Ця складність може вплинути на ефективність генерації та верифікації доказів, а отже, стати проблемою, яку розробники повинні враховувати та вирішувати при створенні додатків на основі ZK
В результаті, стає складно реалізувати деякі хеш-функції, щоб вони були дружніми до ZK.
Доказ
Систему доказів можна порівняти з програмним забезпеченням, яке виконує два основні завдання: генерування доказів і верифікацію доказів. Системи доказів зазвичай приймають схеми, докази та публічні/приватні параметри як вхідні дані.
Двома найбільш популярними пробними системами є серії Groth16 і PLONK (Plonk, HyperPlonk, UltraPlonk)
| | | | | | | | --- | --- | --- | --- | --- | --- | | | Надійне налаштування | Розмір доказу | Складність Prover | Складність верифікатора | Гнучкість | | Грот16 | Специфіка схеми | малий | Низький | Низький | Низький | | Плонк | Універсальна | Великі | Високий | 常数 | Високий |
表2:Groth16 проти Plonk
Як показано в таблиці 2, Groth16 вимагає надійного процесу налаштування, але Groth16 забезпечує нам швидший час доказу та перевірки, а також постійний розмір доказу.
Plonk надає загальну установку, яка виконує фазу попередньої обробки для схеми, яку ви використовуєте, щоразу, коли генерується доказ. Незважаючи на підтримку багатьох схем, час перевірки Плонк постійний.
Між ними також є відмінності з точки зору обмежень. Groth16 зростає лінійно з точки зору розміру обмежень і йому не вистачає гнучкості, в той час як Plonk більш гнучкий.
Загалом, зрозумійте, що продуктивність безпосередньо пов'язана з кількістю обмежень у вашому додатку ZK. Чим більше обмежень, тим більше операцій повинен обчислити програматор.
Вузьке місце
Система доведення складається з двох основних математичних операцій: мультискалярного множення (МСМ) і швидкого перетворення Фур'є (ШПФ). Сьогодні ми розглянемо системи, де є і те, і інше, де ЧСЧ може займати близько 60% часу виконання, а ШПФ – близько 30%.
MSM вимагає великого доступу до пам'яті, що в більшості випадків споживає багато пам'яті на машині, а також виконує безліч операцій скалярного множення.
Алгоритми ШПФ часто вимагають перестановки вхідних даних у певному порядку для виконання перетворень. Це може вимагати багато переміщення даних і може бути вузьким місцем, особливо для великих розмірів вхідних даних. Використання кешу також може бути проблемою, якщо шаблони доступу до пам'яті не вписуються в ієрархію кешу.
** У цьому випадку апаратне прискорення є єдиним способом повної оптимізації продуктивності ZKP. **
Апаратне прискорення
Коли справа доходить до апаратного прискорення, це нагадує нам про те, як ASIC і GPU домінували в майнінгу Bitcoin та Ethereum.
Хоча оптимізація програмного забезпечення однаково важлива та цінна, вона має свої обмеження. Апаратна оптимізація, з іншого боку, може покращити паралелізм шляхом проектування FPGA з декількома процесорами, такими як зменшення синхронізації потоків або векторизація. Доступ до пам'яті також можна оптимізувати ефективніше, покращивши ієрархію пам'яті та шаблони доступу.
Зараз у просторі ZKP, схоже, змістилася основна тенденція: графічні процесори та FPGA.
У короткостроковій перспективі графічні процесори мають перевагу в ціні, особливо після того, як ETH переходить на proof-of-stake (POS), залишаючи велику кількість майнерів GPU простою та в режимі очікування. Крім того, графічні процесори мають перевагу коротких циклів розробки та забезпечують розробникам багато паралелізму «plug-and-play».
Однак FPGA повинні надолужити згаяне, особливо при порівнянні форм-факторів і енергоспоживання. FPGA також забезпечують меншу затримку для високошвидкісних потоків даних. Коли кілька FPGA згруповані разом, вони забезпечують кращу продуктивність порівняно з кластерами графічних процесорів.
ГРАФІЧНИЙ ПРОЦЕСОР ПРОТИ FPGA
Графічний процесор:
Час розробки: Графічні процесори забезпечують швидкий час розробки. Документація розробників для таких фреймворків, як CUDA та OpenCL, добре розроблена та популярна.
Енергоспоживання: графічні процесори дуже «енергоємні». Навіть коли розробники використовують переваги паралелізму на рівні даних і паралелізму на рівні потоків, графічні процесори все одно споживають багато енергії.
Доступність: Графічні процесори споживчого класу дешеві та легко доступні прямо зараз.
FPGA:
Цикл розробки: FPGA мають складніший цикл розробки та вимагають більш спеціалізованих інженерів. FPGA дозволяють інженерам досягти багатьох «низькорівневих» оптимізацій, які не під силу графічним процесорам.
Затримка: FPGA забезпечують меншу затримку, особливо під час обробки великих потоків даних.
Вартість проти доступності: FPGA дорожчі за графічні процесори та не такі легкодоступні, як графічні процесори.
ZPRIZE
У наш час, коли мова заходить про вузьке місце апаратної оптимізації та 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, то побачимо, що виконуються дві основні операції: FFT (швидке перетворення Фур'є) і MSM (мультискалярне множення); Ці дві основні операції є загальними для багатьох систем доведення. Час їх виконання безпосередньо пов'язане з кількістю обмежень в схемі. Природно, число обмежень збільшується в міру написання більш складних схем.
Щоб отримати уявлення про те, наскільки інтенсивними є обчислювальні операції FFT і MSM, ми можемо ознайомитися з бенчмарком схеми Groth16 від Ingonyama (процес Vanilla C2 від Filecoin, виконаний на секторі об'ємом 32 ГБ), і результати будуть наступними
Як показано на малюнку вище, ЧСЧ (мультискалярне множення) може зайняти багато часу і стати серйозним вузьким місцем продуктивності для багатьох доказів, що робить ЧСЧ одним з найважливіших криптографічних операторів, які потрібно прискорити.
Отже, який обсяг обчислень займає МСМ для пруфера в інших системах доведення ЗК? Це показано на малюнку нижче
У Плонку на ЧСЧ припадає понад 85% накладних витрат, як показано в останній статті Інгоньями «Труба МСМ». **
Отже, як апаратне прискорення має прискорити ЧСЧ? **
ЧСЧ
Перш ніж говорити про те, як прискорити ЧСЧ, потрібно розібратися, що таке ЧСЧ
Мультискалярне множення (МСМ) – це алгоритм обчислення суми кратних скалярних множень у наступному вигляді
де G — точка в еліптичній групі кривих, a — скалярна, а результатом MSM також буде точка еліптичної кривої
Ми можемо розкласти ЧСЧ на два основних підкомпоненти:
Модульне множення
Додавання еліптичної кривої точки
Візьмемо для прикладу Affine(x,y) для виконання наївної операції P+Q.
Коли ми хочемо обчислити P + Q = R, нам потрібно обчислити значення k, за абсцисою k і P,Q
Отримати координати R. Процес обчислення такий, як описано вище, у цьому процесі ми виконуємо 2 рази множення, 1 квадратну операцію, 1 обернену операцію та кілька разів операції додавання та віднімання. Варто відзначити, що вищеописані операції виконуються в скінченному полі, тобто під mod P. В реальності Р буде дуже великим. **
Вартість вищевказаної операції полягає в тому, щоб знайти обернене >> множення** **> **** в квадраті, а витрати на додавання і віднімання незначні.
Тому ми хочемо максимально уникати обернених, тому що вартість одиночної інверсії становить щонайменше стократне множення. Ми можемо зробити це, розширивши систему координат, але ціною збільшення кількості множень у процесі, таких як координати Якобі: XYZ += XYZ, і множення більше 10 разів, залежно від алгоритму додавання. **
GPU VS FPGA прискорений МСМ
У цьому розділі порівнюються дві провідні реалізації МСМ, PipeMSM і Sppark, де PipeMSM реалізується на FPGA, а Sppark – на графічних процесорах.
Sppark і PipeMSM використовують найсучасніший алгоритм Pippenger для реалізації MSM, також відомий як алгоритм сегмента; **
Sppark реалізований за допомогою CUDA; Їхні версії відрізняються високою паралельністю і досягли вражаючих результатів при роботі на новітніх графічних процесорах.
Однак PipeMSM не тільки оптимізує алгоритм, але й забезпечує оптимізацію математичних примітивів модульного множення та додавання EC. PipeMSM обробляє весь «стек МСМ», реалізуючи серію математичних трюків та оптимізацій, спрямованих на те, щоб зробити MSM більш придатним для апаратного забезпечення, та розробляючи апаратну конструкцію, призначену для зменшення затримки з акцентом на розпаралелювання.
Давайте коротко підсумуємо реалізацію PipeMSM.
Низька затримка
PipeMSM призначений для забезпечення низької затримки при виконанні декількох ЧСЧ на великій кількості входів. Графічні процесори не пропонують детерміновано низьку затримку через динамічне масштабування частоти, а графічні процесори регулюють свою тактову частоту залежно від робочих навантажень.
Але завдяки оптимізованому апаратному дизайну, реалізації FPGA можуть забезпечити детерміновану продуктивність і затримку для конкретних робочих навантажень.
Впровадження додавання ЄС
Додавання точок еліптичної кривої (EC Addition) реалізовано у вигляді формули з низькою затримкою, дуже паралельної та завершеної (complete означає, що вона правильно обчислює суму будь-яких двох точок у групі еліптичних кривих). Додавання еліптичної кривої використовується конвеєрним способом у модулі додавання EC для зменшення затримки.
Ми вирішили представити координати як проективні координати, і в алгоритмі додавання ми використовуємо формулу додавання точки еліптичної кривої. Головна перевага полягає в тому, що нам ** не доводиться мати справу з крайніми кейсами**. Повні формули;
Ми реалізували цю формулу додавання конвеєрно і паралельно, і наша схема суматора еліптичної кривої FPGA потребувала лише 12 множень, 17 сум доданків, і ця формула була виконана. Вихідна формула вимагає 15 множення за модулем і 13 додавання. Конструкція FPGA наступна
Мультимод
Ми використовували алгоритми Barrett Reduction і Karatsuba.
Редукція Барретта — це алгоритм, який ефективно обчислює r≡ab mod p (де p є фіксованим). Скорочення Барретта намагається замінити ділення (дорога операція) приблизним діленням. Допуск до помилки може бути обраний для опису діапазону, в якому ми шукаємо правильний результат. Виявлено, що велика толерантність до похибки дозволяє використовувати менші константи скорочення; При цьому зменшується розмір проміжних значень, що використовуються в операціях скорочення за модулем, що зменшує кількість множень, необхідних для обчислення кінцевого результату.
У синьому полі нижче ми бачимо, що через нашу високу толерантність до помилок нам доводиться виконувати кілька перевірок, щоб знайти точний результат.
У двох словах, алгоритм Карацуби використовується для оптимізації множення, яке ми виконуємо в Скорочення Барретта. Алгоритм Карацуби спрощує множення двох n-цифр до множення трьох n/2 цифр; Ці множення можуть спростити кількість цифр, щоб вони були достатньо вузькими, щоб їх можна було безпосередньо обчислити апаратним забезпеченням. Подробиці можна прочитати в статті Інго: Pipe MSM
Використовуючи вищезгадані оператори, ми розробили реалізацію MSM з низькою затримкою, високопаралельну імплементацію.
Основна ідея полягає в тому, що замість того, щоб обчислювати весь ЧСЧ відразу, кожен фрагмент передається в суматор EC паралельно. Результати суматора ЕК акумулюються в підсумковий МСМ.
Кінцевий результат****
На діаграмі вище показано порівняння між Sppark і PipeMSM.
Найбільш помітною є значна економія енергії, яку пропонують FPGA, що може бути надзвичайно важливим для майбутніх великомасштабних операцій з виробництва пробної продукції. Варто зазначити, що наша реалізація була прототипом і порівняльним аналізом під @125MHz, і збільшення тактової частоти до @500MHz могло збільшити час обчислень у 4 рази або більше.
Ще однією перевагою використання наших ПЛІС є те, що їх можна встановлювати на невеликих серверах шасі, оскільки вони споживають менше енергії та генерують менше тепла.
Ми знаходимося на ранніх стадіях розробки FPGA для ZKP і повинні очікувати подальших удосконалень алгоритмів. Крім того, FPGA обчислює MSM, коли центральний процесор простоює, і можна досягти швидшого часу, використовуючи FPGA у поєднанні з системними ресурсами (CPU/GPU).
Зведення
ЗКП стала ключовою технологією для розподілених систем.
Застосування ZKP вийде далеко за рамки простого розширення рівня Ethereum, дозволяючи передавати обчислення на аутсорсинг ненадійним третім сторонам, дозволяючи розробляти раніше неможливі системи, такі як розподілені хмарні обчислення, системи ідентифікації тощо.
Традиційно оптимізація ZKP була зосереджена на вдосконаленні програмного рівня, але в міру зростання попиту на більш високу продуктивність ми побачимо більш просунуті рішення для прискорення, що включають як апаратне, так і програмне забезпечення.
В даний час рішення для прискорення, які ми бачимо, в основному використовують графічні процесори, тому що час розробки з використанням CUDA короткий, а поточні споживчі графічні процесори дуже дешеві та в достатку. Графічний процесор також пропонує неймовірну продуктивність. Тож графічні процесори навряд чи зникнуть із цього простору найближчим часом.
У міру того, як у космос виходять більш складні команди розробників, цілком ймовірно, що ми побачимо FPGA, які лідирують з точки зору енергоефективності та продуктивності. У порівнянні з графічними процесорами, FPGA пропонують більш низькорівневу кастомізацію, а також більше можливостей конфігурації. FPGA пропонують швидшу швидкість розробки та гнучкість, ніж ASIC. Зі швидким розвитком світу ZKP FPGA можна перепрошивати різними програмами для розміщення різних систем та оновлень рішень.
Однак, щоб генерувати докази майже в реальному часі, може знадобитися комбінувати конфігурації GPU/FPGA/ASIC залежно від системи, для якої ми генеруємо докази.
ЗПУ також, ймовірно, буде розвиватися, щоб надавати надзвичайно ефективні рішення для великомасштабних генераторів і малопотужних пристроїв (докладніше див. попередню статтю).