Автор: 0xAlpha Співзасновник @DeriProtocol; Укладач: DODO Research
Вступ
zk-SNARKs, або «стислі неінтерактивні аргументи знань з нульовим розголошенням», дозволяють верифікатору підтвердити, що дослідник володіє певними специфічними знаннями, відомими як свідки, які задовольняють конкретні відносини, нічого не розкриваючи про самого свідка.
Генерація zk-SNARK для конкретної задачі складається з наступних чотирьох фаз:
- Перетворіть задачу (або функцію) в схему арифметичних вентилів.
- Потім ця схема переводиться в матричну формулу.
- Ця формула матриці далі перетворюється в многочлен, який повинен ділитися на певний мінімальний многочлен.
- Нарешті, ця подільність представлена в точках еліптичної кривої в скінченних полях, де відбувається доведення.
Перші три кроки просто перетворюють представлення вихідної інструкції. На останньому кроці використовується гомоморфне шифрування для проектування інструкції кроку 3 у криптографічний простір, що дозволяє організатору перевірити дзеркальну інструкцію в ньому. Враховуючи, що ця проекція використовує асиметричну криптографію, неможливо простежити вихідне твердження з третього кроку, що забезпечує доступ до нульового розголошення.
Математична підготовка, необхідна для прочитання цієї статті, еквівалентна першому рівню алгебри для спеціальностей STEM. Єдина концепція, яка може бути складною, це, ймовірно, шифрування з еліптичною кривою. Для тих, хто не знайомий з цим, його можна розглядати як експоненціальну функцію з особливою кардинальністю, пам’ятаючи, що її обернена залишається нерозв’язаною.
У цій статті ми будемо дотримуватися наступних правил позначення:
- Матриця: жирні великі літери, наприклад, A; Пишіть явно у формі
- Вектор: малі літери зі стрілками, написані в явній формі [ ] ; За замовчуванням всі вектори є стовпчастими векторами
- Скалярний: Звичайне представлення літер
Візьмемо на прикладі це питання:
f(x)=x^3+x^2+5 (1)
Скажімо, Аліса хоче довести, що знає одного. Ми розглянемо всю процедуру, яку Алісі потрібно пройти, щоб згенерувати zk-SNARK для своїх доказів.
Це питання може здатися занадто простим, оскільки воно не пов’язане з потоком управління (наприклад, якщо-то-інакше). Однак перетворити функцію з керуючим потоком в арифметичний вираз нескладно. Наприклад, розглянемо наступне питання (або «функція» в мові програмування):
f(x, z):
if(z==1):
повернути x*x*x+x*x+5
ще:
повернути x*x+5
Цю задачу легко переписати в наступний арифметичний вираз (припустимо, що z належить (0,1)), який не набагато складніший, ніж рівняння (1).
f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)
У цій статті ми продовжимо використовувати рівняння (1) як основу для обговорення.
Крок 1: Схема арифметичних воріт
Рівняння (1) можна розбити на такі основні арифметичні дії:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128057_watermarknone.png)
Це відповідає наступній схемі арифметичних вентилів:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7127628_watermarknone.png)
Ми також називаємо рівняння (2) набором з 4 «обмежень першого порядку», кожне з яких описує зв’язок арифметичного вентиля в ланцюзі. У загальному випадку, множина з n обмежень першого порядку може бути узагальнена як квадратична арифметична процедура (QAP), яка буде пояснена далі.
Крок 2: Матриця
Для початку визначимо вектор «свідка» наступним чином:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128058_watermarknone.png)
де y, s1, s2, s3 - ті ж, що визначені в рівнянні (2).
У загальному випадку, для задачі з m входами та n арифметичними вентилями (тобто n-1 проміжних кроків та кінцевого виходу), цей вектор свідка буде (m+n+1) вимірним. У практичній задачі число n може бути дуже великим. Наприклад, для хеш-функції n зазвичай дорівнює кільком тисячам.
Далі побудуємо три n*(m+n+*1) матриць A,B,C так, щоб можна було переписати рівняння (2) наступним чином:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128059_watermarknone.png)
Рівняння (3) є ще одним відображенням рівняння (2): кожній групі (ai, bi, ci) відповідає вентиль в ланцюзі. Нам потрібно лише однозначно розгорнути формулу матриці, щоб побачити наступне:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128060_watermarknone.png)
Таким чином, LHS=RHS точно таке ж, як і рівняння (2), і кожен рядок матричного рівняння відповідає обмеженню першого порядку (тобто арифметичному вентилю в схемі).
Ми пропустили етапи збірки (A, B, C), які є відносно простими. Нам потрібно лише перевести їх у форму матриці відповідно до відповідних обмежень першого рівня, щоб визначити вміст кожного рядка (A, B, C), ТОБТО (AI, BI, CI). Візьмемо для прикладу перший рядок: легко побачити, що для того, щоб примус першого порядку x був помножений на x, рівний s1, нам потрібно помножити [0,1,0,0,0,0,0], [0,1,0,0,0] і [0,0,0,0,0,0,0] на вектор s.
Таким чином, нам вдалося перетворити схему арифметичних воріт в матричну формулу, т. Е. Рівняння (3). У той же час ми також змінили об’єкт, який потрібно довести, щоб бути освоєним, на вектор свідка s.
Крок 3: Многочлени
Тепер побудуємо n*(*n+m+*1) матрицю PA, яка визначає множину многочленів про z:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128061_watermarknone.png)
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128062_watermarknone.png)
Це чотири набори лінійних рівнянь для шести змінних, які можна розв’язати традиційними методами. Однак більш ефективним способом розв’язання ПА в цьому випадку є інтерполяція Лагранжа, яка використовує специфіку задачі. Тут ми пропускаємо процес розв’язання для PA, який є трохи виснажливим, але простим.
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128063_watermarknone.png)
При цьому:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128064_watermarknone.png)
Крок 4: Точки кривої еліпса
Перепишіть рівняння (4) так:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128065_watermarknone.png)
де i(z)=1 є тривіальним многочленом нульового порядку для z, який використовується для уніфікації рівняння - всі доданки квадратні. Потреба в цьому скоро стане зрозумілою. Зауважимо, що це рівняння містить лише додавання та множення многочлена z.
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128066_watermarknone.png)
Далі ми пояснимо фактичні кроки більш детально.
Шифрування еліптичної кривої
Загальна теорія еліптичних кривих виходить далеко за рамки цієї статті. Для цілей цієї статті еліптичні криві визначаються як відображення від простої області Fp до функції E, де E включає точки, що задовольняють y^2=x^3+ax+b (так звані еліптичні криві точки, або скорочено ECP).
Зауважте, що якщо раніше ми говорили про звичайну арифметику, то тепер, коли ми перетворюємо на прості поля, арифметичні операції над числами виконуються модульним способом. Наприклад, a+b=a+b(mod p), де p — порядок Fp.
З іншого боку, визначення додавання двох точок еліптичної кривої показано на наступному малюнку:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128067_watermarknone.png)
Зокрема, додавання двох ECP, P і Q:
Знайти перетин прямої PQ і кривої R, визначену як -(P+Q)
Переверніть до «дзеркальної» точки R’ на кривій для R.
Отже, визначимо додавання точок еліптичної кривої P+Q=R’:
Зауважимо, що це правило поширюється і на особливі випадки, тобто коли ЕКП самоадитив, де буде використовуватися тангенс точки.
Тепер припустимо, що ми вибираємо випадкову точку G і зіставляємо з нею число 1. (Таке «початкове відображення» звучить дещо довільно.) Про це трохи пізніше). Тоді, щоб будь-яке n належало Fp, визначимо:
E(N)=G+G+G+…+G=G
Це має вираз дії. Дії, які визначають +G, є «генераторами» і позначаються як g. Тоді наведене вище визначення рівнозначне:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128068_watermarknone.png)
Для тих, хто не знайомий з еліптичними кривими, ви можете провести аналогію цього відображення з регулярною експоненціальною функцією, де кардинал g замінює дійсні числа. Аналогічно поводяться і арифметичні дії. Однак ключова відмінність полягає в тому, що обернена функція g^n не є обчислювально здійсненною. Тобто немає можливості обчислити версію еліптичної кривої! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128069_watermarknone.png)。 Це, звичайно ж, основа криптографії з еліптичною кривою. Таке відображення відоме як одностороннє шифрування.
Зауважимо, що для еліптичної кривої, оскільки вибір G (і, отже, генератора g) є довільним (за винятком точок на осі x), існує нескінченна кількість способів її відображення. Вибір (G або g) може бути аналогічним вибору кардинальності експоненціальної функції (2^x, 10^x, e^x тощо) як частини здорового глузду.
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128070_watermarknone.png)
Однак рівняння (5), яке Аліса хоче довести, є квадратичним і тому недостатньо лінійним. Для того, щоб мати справу з квадратичними членами, нам потрібно визначити множення в криптографічному просторі. Це відоме як функція сполучення, або білінійне відображення, і буде пояснено далі.
Білінійне відображення
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128071_watermarknone.png)
Загальний довідковий рядок
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128072_watermarknone.png)
Весь процес називається «ключем перевірки», або скорочено ВК. Тут задіяно лише 7 еліптичних точок кривої (ECP), які потрібно надати верифікатору. Важливо відзначити, що незалежно від того, скільки входів і обмежень першого рівня задіяно в задачі, ВК завжди складається з 7 ECP.
Крім того, варто згадати, що «довірена настройка» і процес генерації ПК і ВК можна зробити один раз для конкретної задачі.
Доказ і верифікація
Тепер, використовуючи відкритий ключ (PK), Аліса обчислить наступні еліптичні точки кривої (ECP):
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128073_watermarknone.png)
Ці 9 еліптичних точок кривої є ключем до стислих неінтерактивних доказів з нульовим розголошенням (zk-SNARKs)!
Зауважте, що Аліса насправді просто виконує деякі лінійні комбінаторні операції над точками еліптичної кривої у відкритому ключі. Це особливо важливо і буде перевірено під час валідації.
Тепер, коли Аліса передала доказ zk-SNARK, давайте нарешті перейдемо до процесу верифікації, який складається з трьох етапів.
Перш за все, важливо переконатися, що перші 8 точок еліптичної кривої дійсно є лінійною комбінацією цих точок у загальному еталонному рядку.
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128074_watermarknone.png)
Якщо всі три перевірки вірні, то рівняння (5) перевірено, тому ми вважаємо, що Аліса знає свідка.
Пояснимо обґрунтування рівняння. Візьмемо для прикладу перше рівняння в першій частині, яке справедливе через білінійну природу:
! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128075_watermarknone.png)
Однак, оскільки Аліса не знає значення символу альфа, вона не в змозі обчислити це додавання явно. Єдиний спосіб, яким вона могла придумати пару, яка задовольняє рівнянню (EA, EA’), полягав у тому, щоб використовувати один і той же набір векторів s кожен, обчислити! [Сила доказів з нульовим розголошенням: математичне розшифровування zk-SNARKs] (https://img.jinse.cn/7128076_watermarknone.png).
Список літератури
“Zk-SNARKs: Під капотом” (Віталік Бутерін)
«Огляд доказів нульового розголошення» (Томас Чен, Еббі Лу, Джерн Кунпіттайя та Алан Луо)
“Чому і як працює zk-SNARK: остаточне пояснення” (Максим Петкус)
Веб-сайт: Докази з нульовим розголошенням
Вікіпедія: Еліптична крива
Вікіпедія: Скінченне поле
Вікіпедія: Криптографія на основі сполучення
