Cхеми агрегації доказів — SnarkPack і aPlonk

Переклад на українську. Оригінал статті.

Вступ

zk-SNARK — це потужні криптографічні примітиви, які дозволяють одній стороні, відомій як прувер, показати іншій стороні, верифікатору, що він знає певний секрет, не розкриваючи нічого про нього. Це має застосування, наприклад, у децентралізованих приватних обчисленнях, де ми можемо делегувати дорогі обчислення ненадійному серверу та отримати криптографічний доказ, що підтверджує правильність обчислень, без витоку конфіденційної інформації. Ми також можемо використовувати zk-SNARK для вирішення проблем конфіденційності та масштабованості, від яких страждає більшість децентралізованих реєстрів. У випадку реєстру кожна нода повина виконати обчислення самостійно, щоб перевірити його достовірність. Це означає, що менш потужні пристрої в реєстрі можуть бути вузькими місцями, особливо коли обчислення дорогі, що впливає на масштабованість. Однак замість того, щоб кожна нода повторно виконувала кожне обчислення, ми могли б змусити їх перевірити короткий доказ, який показує, що обчислення правильні, тоді ми можемо зменшити навантаження на всю систему.

Однією з головних проблем з zk-SNARK є час генерації доказу. Як правило, створення доказів передбачає перетворення обчислень у деяку NP-повну задачу, де ми можемо довести правильність обчислень, наприклад, виконуваність арифметичної схеми або систему квадратичних обмежень (система обмежень рангу один, R1CS) і виконання деяких дорогих обчислень, таких як мультискалярне множення (MSM) і поєднання еліптичних кривих. Було прийнято кілька стратегій для зменшення обчислювальних витрат, таких як композиція доказів, групування, рекурсія, збільшенням кількості менших доказів і використання переваг схем поліноміальних зобов’язань.

У попередній публікації ми розглянули інкрементально перевірені обчислення (IVC) і схеми згортання, які дають нам способи реалізації IVC на практиці. Ми розповіли про основи Nova та про те, як працює схема складання. Тепер ми звернемо нашу увагу на схеми агрегації доказів: SNARKPack і aPlonK. Це дозволяє нам зменшити загальний розмір доказів і пов’язаний з ними час перевірки: для n доказів, розмір і час перевірки сукупного доказу буде O(n) , що є значним скороченням, особливо для великої кількості доказів. SNARKPack побудовано на основі Groth16 SNARK, тоді як aPlonk працює з системою перевірки Plonk. Обидва є одними з найбільш широко використовуваних SNARK і використовують надійні налаштування, які є результатом церемоній налаштування, що включають багатосторонні обчислення.

SNARPack У схемі Groth16 доказ π складається з трьох елементів групи еліптичних кривих, А, B, C. Обидва А та B належать до групи G1 і C належить до групи G1. Групи мають однаковий порядок (кількість елементів), p і належать до торсійних груп порядку p еліптичної кривої над полем розширення. Можна визначити білінійну карту (або операцію сполучення), беручи елемент із кожної групи та виводячи елемент у третю групу Gt: e:G1×G2→Gt , такий, що e(ga,hb)=e(g,h)ab, де a, b є числа і g, h є генераторами груп G1 і G2 де відповідно (елемент групи, g називається генератором, якщо будь-який елемент у групі можна отримати шляхом його багаторазового додавання). Перевірка доказів у Groth16 виконується за допомогою операції сполучення,

де D є елементом G2, а Y є елементом Gt. Основна ідея агрегації n доказів Groth16 полягають у тому, що ми можемо перевірити їх усі одночасно, використовуючи випадкову лінійну комбінацію (з точністю до дуже невеликої помилки). Таким чином, нам потрібно виконати лише одну операцію створення пари n,

де r є випадковим числом і ∏ означає, що ми беремо добуток усіх можливих пар.

Для спрощення дано визначення таких термінів:

Після перевірки того, що останнє рівняння виконується, нам залишається завдання перевірити, що для деяких початкових зафіксованих векторів: A=(A1,A2,…An), B=(B1,B2,…,Bn) і C=(C1,C2,…,Cn), ZAC,ZB відповідають цим специфікаціям. Це робиться за допомогою двох внутрішніх парних аргументів:

1. Цільовий внутрішній парний продукт (TIPP) показує це:

2. Внутрішній парний добуток з кількома ступенями (MIPP) показує :

Щоб мати можливість реалізувати ці продукти внутрішнього сполучення, нам потрібні ефективні схеми зобов’язань із властивостями homomorphic та collapsing. Ми кажемо, що зобов’язання є additively homomorphic, якщо, задано два елементи, a, b, схема зобов’язань задовольняє це cm(a+b)=cm(a)+cm(b). Таку властивість мають, наприклад, зобов’язання Pedersen та Kate-Zaverucha-Goldberg. Щоб досягти логарифмічного розміру доказу, автори SNARKPack використовують ту саму стратегію, що б бути не ураженими, яка базується на аргументі внутрішнього продукту. Ці зобов’язання також є homomorphic в ключовому просторі: дано два ключі k1, k2 і для будь-якого повідомлення m, у нас це:

Протокол використовує надійні налаштування двох великих церемоній налаштування: Filecoin і Zcash. У Groth16 структурований еталонний рядок (SRS), який є результатом церемонії, складається з випадкового елемента τ, прихованих всередині груп G1,G2. Дано генератори g, h, SRS подано як:

Це дозволить нам використовувати поліноми та перевіряти твердження щодо них.

Тепер ми можемо створювати парні групові зобов’язання за допомогою двох SRS. Для полегшення позначень назвемо

1. w1=(g,g11,h12,…) і v1=(h,h11,h12,…) це SRS для церемонії 1.
2. w2=(g,g21,h22,…) і v2=(h,h21,h22,…) це SRS для церемонії 2.

Є два варіанти цих зобов’язань: одногруповий і подвійний. Перший приймає як ключ зобов’язання key ks=(v1,v2), а останній використовує kd=(v1,w1,v2,w2).

Зобов’язання однієї групи мають вектор А і ключ ks і виводить два елементи групи:

де

Подвійне зобов’язання приймає вектори А і C утворений з елементів в G1 і G2, відповідно і kd і виводить два елементи:

з

Подвійне зобов’язання використовуватиметься разом із TIPP, щоб показати це ZAC=∏e(A,C)rk, тоді як MIPP використовуватиметься з єдиним зобов’язанням побачити це ZB=∏e(B*rk*k,D).Необхідно перевірити два співвідношення:

Простими словами, у кожному відношенні ми перевіряємо правильність значення та дійсність зобов’язань.

Щоб отримати точні відомості про алгоритми підтвердження та перевірки, ми посилаємо читача на джерело.

У показаних тематичних дослідженнях схема агрегації перевершує пакетну перевірку як за розміром, так і за часом із трохи більше ніж 100 доказами.

aPlonk aPlonk спирається на ідеї SNARKPack, використовуючи іншу систему перевірки (Plonk) і запроваджуючи багатополіноміальні зобов’язання, щоб досягти сублінійного розміру кількості поліномів. Ключова ідея полягає в тому, що ми можемо перевірити кілька доказів, виконавши випадкову лінійну комбінацію зобов’язань і перевіривши її. Нотація дещо відрізняється, оскільки автори aPlonk використовують адитивну нотацію при роботі з групами, тоді як автори SNARKPack використовують мультиплікативну нотацію. Якщо cm(pk) є прихильними до полінома pk (який, якщо ми використовуємо зобов’язання KZG, є елементом еліптичної кривої), тоді ми можемо перевірити їх усі, виконавши

і перевірити β, в точці z, відкриває (оцінює) до v=∑rkvk

де vk це значення pk(z). Якби ми використовували мультиплікативний запис, попереднє рівняння було б таким

Щоб досягти сублінійного розміру, прувер візьме на себе зобов’язання поліномів, тобто β=cm(cm(p1),cm(p2)…). Оскільки ми обчислюємо лінійну комбінацію з використанням степенів r, природно використовувати поліноміальну схему зобов’язань, таку як KZG або аргументи внутрішнього продукту (IPA).

Система обмежень Plonk виражається як:

і може бути розширена, щоб включити терміни вищого порядку. Для кожного qk ми можемо визначити одновимірний поліном, qL(x),qR(x),qO(x),qM(x),qC(x) шляхом оцінки кожного полінома відповідно до його qk i у первісних коренів ωi є примітивним коренем n-го числа з одиниці, якщо

ωn**i=1 і ωk**i≠1 якщо k<n.

Крім того, довідник повинен показати, що співвідношення між індексами ai,bi,ci пов’язані перестановками; ці перестановки також виражаються через поліноми. Це дає загалом 8 поліномів, які потрібно виконати.

Одним із ключових будівельних блоків є багатополіноміальна схема зобов’язань. Він складається з 5 ефективних алгоритмів, setup, commit−polynomial, commit−evaluation, open, check; основною відмінністю є додавання в commit−evaluation алгоритмі. Мультиполіноміальне зобов’язання побудовано на двох схемах поліноміального зобов’язання: KZG та IPA.

Одна з важливих оптимізацій полягає в тому, що всі поліноми оцінюються в одному випадковому r, що задано евристикою Fiat-Shamir. Якщо робити так, r має бути отримано з часткової розшифровки всіх доказів, вимагаючи, щоб перевірники кожного твердження працювали координовано. Навіть якщо це перешкоджає побудові інкрементально-перевірюваних обчислень (IVC), оскільки в цьому випадку докази генеруються одне за одним, конструкція добре працює для зведення валідності.

Підсумки Схема агрегації доказів є альтернативою для зменшення розміру та часу перевірки багатьох zk-SNARK. Ключовим фактом є те, що можна отримати пробні розміри та час перевірки замовлення O(log(n)) для n доказів, що перевершує методи групування для трохи більше ніж 100 доказів і має значну різницю, коли ми додаємо разом понад 1000 доказів. Основними будівельними блоками для досягнення цих властивостей є гомоморфні поліноміальні зобов’язання (такі як KZG), дві перевірені установки та той факт, що ми можемо перевірити багато доказів, взявши випадкову лінійну комбінацію, з використанням коефіцієнтів ступеня деяких чисел-r.

Дізнайтеся більше про Aleo

***Twitter | Discord | Website***