Вступ Протокол ZEXE (Zero-knowledge EXEcution) з'явився в 2018 році і є криптографічним примітивом децентралізованих приватних обчислень (DPC). Він був створений для усунення двох основних недоліків, від яких страждають децентралізовані реєстри: конфіденційність та масштабованість.
Якщо, наприклад, ми візьмемо Біткойн і Ethereum, то побачимо, що історія всіх транзакцій є загальнодоступною (це може призвести до витоку конфіденційної інформації про постачальників вашої компанії, ваших знайомих або послуг, якими ви користуєтеся). Ethereum пропонує програмованість, але вимагає, щоб кожен вузол виконував операцію, де найменш потужний пристрій виступає як вузьке місце. ZCash вирішує проблему конфіденційності, але не пропонує можливості програмування, а лише приватні транзакції. ZEXE намагається отримати найкраще з обох світів:
Якщо, наприклад, ми візьмемо Біткойн і Ethereum, то побачимо, що історія всіх транзакцій є загальнодоступною (це може призвести до витоку конфіденційної інформації про постачальників вашої компанії, ваших знайомих або послуг, якими ви користуєтеся). Ethereum пропонує програмованість, але вимагає, щоб кожен вузол виконував операцію, де найменш потужний пристрій виступає як вузьке місце. ZCash вирішує проблему конфіденційності, але не пропонує можливості програмування, а лише приватні транзакції. ZEXE намагається отримати найкраще з обох світів: приватний запуск будь-яких програм, можливість виконання обчислень в автономному режимі та надання доказів цілісності обчислень, які можна швидко перевірити в блокчейні. Для огляду протоколу рекомендуємо наш попередній пост про ZEXE. Нагадаю, що протокол пропонує такі функції:
Програмування: ми можемо запускати довільні програми.
Швидка перевірка: ми можемо довести достовірність наших обчислень, використовуючи zk-SNARK (короткі неінтерактивні аргументи знання з нульовим розголошенням), які пропонують короткі докази, які можна перевірити в ланцюжку за кілька мілісекунд.
Конфіденційність даних та функцій: протокол приховує відповідну вхідну інформацію, а також функції, що викликаються при виконанні переходів у реєстрі.
Протокол ZEXE зазнав кількох покращень з моменту своєї появи, щоб підвищити продуктивність. У цьому пості ми проаналізуємо різницю між вихідним протоколом і недавнім версією VERI-ZEXE . Автори VERI-ZEXE порівняли продуктивність свого протоколу з вихідною версією ZEXE та деякими його ранніми модифікаціями. Жодних порівнянь між поточними покращеними версіями протоколу ZEXE та VERI-ZEXE не проводилося.
Компоненти Ми згадали, що протокол ZEXE використовує примітив zk-SNARK, який дозволяє нам надавати докази цілісності для заданих обчислень, які можуть бути перевірені набагато швидше. Найбільша ціна пов'язана з генерацією доказу, що ґрунтується на операціях з еліптичними кривими. Основи деяких систем SNARK ви можете переглянути в нашому попередньому пості.
Сучасні системи доказів мають два основних компоненти: поліноміальний інтерактивний доказ оракула -PIOP- (який перетворює дане обчислення в поліноміальні рівняння) та поліноміальну схему фіксації -PCS-. Залежно від вибору, який ми робимо, ми отримуємо різні доказові системи, кожна з яких має свої переваги і недоліки. Прикладами PIOP є Marlin, PLONK (Перестановки над базисами Лагранжа для екуменічних неінтерактивних аргументів Знання) та всі їх похідні та Spartan. Серед PCS у нас є KZG (Kate-Zaverucha-Goldberg), FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity), Bulletproofs та DARK (групи невизначеного порядку), і це лише деякі з них.
Щоб мати можливість виконувати докази швидко та ефективно, нам потрібні «дружні до SNARK» криптографічні примітиви та операції. Ми могли б сказати, що функція «зручна для SNARK», якщо її подання у вигляді арифметичної схеми невелике. Наприклад, інтуїтивно зрозумілі та прості побітові операції, такі як AND та XOR, мають складне схемне уявлення. Отже, вартість операцій у разі SNARK повинна враховувати складність арифметичної схеми, яка використовується для представлення операції та її змінних.
Більшість вартості систем SNARK посідає:
Мультискалярне множення (ЧСЧ). Це операції виду
де ак - Числа і Pk - точки, що належать еліптичної кривої.
Еліптичні пари кривих. Вони використовуються під час перевірки деяких систем. Вони включають розширення полів та операції між різними групами еліптичних кривих.
Поліноміальні оцінки над нерідними полями.
Перетворення Фіата-Шаміра: для створення завдань потрібне використання хеш-функції. Багато криптографічних примітивів, що добре зарекомендували себе, мають складні уявлення у вигляді арифметичних схем, що робить їх оцінку дорогою.
Дослідницькі зусилля намагаються вирішити усі ці проблеми. Використання GPU або FPGA може прискорити обчислення MSM. Нові хеш-функції та схеми шифрування з більш досконалими арифметичними схемами можуть ще більше знизити складність часто використовуваних криптографічних примітивів (наприклад, Poseidon та Vision and Rescue).
Вибір VERI-ZEXE Для вирішення цих проблем VERI-ZEXE вносить деякі зміни до системи перевірки та криптографічних примітивів. Ось деякі з основних модифікацій:
PLONK як PIOP. За останні роки в PLONK було внесено кілька значних поліпшень, таких як гейти високого ступеня, використання таблиць пошуку і використання полілінійних поліномів (що дозволяє уникнути використання швидкого перетворення Фур'є) (наприклад, turboPLONK, -ultraPLONK і hyperPLONK ).
Полегшена схема верифікатора за схемою накопичення. Протокол виводить перевірку сполучення зі схеми SNARK та відкладає перевірку до валідаторів реєстру.Пакетування доказів. Ми можемо генерувати та перевіряти докази партіями, використовуючи властивості деяких PCS, таких як KZG. Вони дозволяють відкривати
N різних зобов'язань одночасно з витратами, які не масштабуються лінійно за кількістю зобов'язань (тобто ви можете відкрити N зобов'язань вартістю менше, ніж вартість N окремих відкриттів).
Змінна база MSM через довідкову таблицю. MSM виконується шляхом поєднання алгоритму Піппенджера (який розбиває скаляри на блоки) з таблицею пошуку , що знижує вартість додавання еліптичних кривих.
Поліноміальна оцінка по нерідних полях. Схеми що доводить і перевіряє лежать у різних кінцевих полях. Одним із способів упоратися з цим було використання двох пар еліптичних кривих. VERI-ZEXE використовує модульне додавання та множення з перевіркою діапазону з пошуком, що призводить до більш складної схеми.
Дружні до SNARK симетричні примітиви. Використання стійких до колізій хеш-функцій, генераторів псевдовипадкових чисел та схем фіксації з більш простим уявленням схеми (що скорочує кількість операцій), що призводить до меншого використання пам'яті та часу. Наприклад, перетворення Фіата-Шамір використовує конструкцію губки перестановки Rescue.
Використання PLONK та його доповнень разом із більш простими конструкціями криптографічних примітивів призводить до зменшення більш ніж на порядок загальної кількості обмежень, що, у свою чергу, зменшує масштаб МСМ-множень та загальний час доведення.
Схеми накопичення (AS) та інкрементально верифіковані обчислення (IVC)
Перевірка доказів потребує обчислення дорогих операцій сполучення. Оригінальний протокол ZEXE використовував інкрементально верифіковані обчислення для доказу задовільності заданих користувачем предикатів за допомогою рекурсії SNARK: при заданому обчисленні на кроці N перевіряючий отримував стан Zn і доказ π(N-1), що підтверджує правильність виконання попереднього. Потім перевіряючий виконає крок N та генерує доказ π(N), який засвідчує, що “новий стан z′ є результатом правильного виконання і що π(N-1) істинно (іншими словами, що (N-1) попередніх кроків були виконані правильно )”. Саме на цьому останньому кроці виникає обчислювальне навантаження: для перевірки доказу нам необхідно вбудувати обчислення верифікатора у схему перевіряючого, що уповільнює генерацію доказів.
Схема накопичення працює інакше, відкладаючи перевірку остаточного докази валідаторами реєстру. На кожному кроці обчислення прувер отримує поточний стан та накопичення, яке частково верифікується (перевірник перевіряє правильність результатів накопичення, але не обчислює операцію сполучення еліптичних кривих). Для того щоб накопичення не пропускало інформацію про обчислення, групові елементи в накопиченні повинні бути замасковані за допомогою рандомізатора, що виступає в ролі додаткового свідка (секретного входу) для верифікатора накопичення.
Таблиці пошуку та ефективні модульні операції
Використання інтерполяційних таблиць для складання еліптичних кривих у алгоритмі Піппенджера разом із ефективними операціями модульної арифметики призводить до скорочення кількості обмежень PLONK у 6 разів.
Ідея таблиць пошуку для MSM полягає в наступному:
Алгоритм Піппенджера розбиває скаляр a на m вікон довжини c (Наприклад, скаляр - 256-бітове число, і ми вибираємо вікно завдовжки 8 біт). Кожен скаляр може бути записаний як
де кожне значення aij знаходиться у діапазоні 0, 1, . . . 2 c - 1 . Ми можемо обчислити кожної точки Pi всі можливі комбінації значень скалярів 2 Pi , 3 Pi , 4 Pi , . . . , (2 c - 1) Pi.
Тепер ми можемо визначити результат
подивившись на таблицю (яка має простіший опис, ніж операції з чистими еліптичними кривими) і отримати результати j-го дії,
Тепер ми можемо отримати остаточний результат, додавши, нарешті, m-дія,
Подальші покращення від HyperPlonk?
VERI-ZEXE використовує PLONK з таблицями пошуку, що призводить до меншої кількості обмежень та скорочення часу перевірки. Два тижні тому вийшов HyperPLONK, що забезпечує доказ лінійного часу і вентилі високого ступеня. Однією з ключових змін є перехід від одновимірних поліномів (поліномів від однієї змінної, x, таких як
до багатовимірних лінійних поліном (поліном від декількох змінних, де ступінь кожного хk більше одного, наприклад
Ця зміна дозволяє уникнути використання швидкого перетворення Фур'є (FFT) для дуже великих систем (з понад 2²⁰обмежень), який має надлінійну вартість (грубо кажучи, FFT для n-точок вимагає nlog(n) операцій). Попередні дослідження показали, що ця нова версія PLONK має кращу продуктивність для ланцюгів із більш ніж 16000 обмежень порівняно з оптимізованими версіями вихідної пропозиції. Ми розглянемо цю тему наступного посту.
Висновок
Докази ZK є ключем до багатьох нових додатків, таких як децентралізовані фінанси, управління тощо. Протокол ZEXE представив концепцію децентралізованих приватних обчислень, що дозволяє користувачам запускати приватні додатки в публічних реєстрах. Початкова пропозиція була заснована на неуніверсальних системах перевірки, які мають ефективну продуктивність, але потребують нової надійної установки для кожної програми, яку ми хочемо запустити. З того часу було внесено низку серйозних поліпшень до системи перевірки (такі як Marlin та PLONK) та нові «дружні до SNARK» криптографічні примітиви (такі як симетричні шифри та хеш-функції), що призвело до підвищення продуктивності та зниження обчислювальних витрат.