Сила доказів із нульовим знанням: глибоке занурення в zk-SNARK

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

Укладач: DODO Research

Автор: співзасновник 0xAlpha @DeriProtocol

Вступ

Zk-SNARK, або стислий неінтерактивний аргумент знань із нульовим знанням, дає змогу верифікатору підтвердити, що перевіряючий володіє певними знаннями (званими свідками), які задовольняють певні відносини, не розкриваючи жодної інформації про самі знання.

Створення zk-SNARK для конкретної проблеми включає наступні чотири етапи:

• Перетворення задачі (або функції) в арифметичну схему.
• Потім ця схема перетворюється на матричне рівняння.
• Це матричне рівняння далі перетворюється на поліном, який має ділитися на певний мінімальний поліном.
• Нарешті, ця подільність виражається в точках еліптичної кривої над скінченним полем, де і відбувається доказ.

Перші три кроки просто перетворюють подання вихідного твердження. Останній крок проектує твердження з третього кроку в зашифрований простір за допомогою гомоморфного шифрування, дозволяючи перевіряючому перевіряти дзеркально відображені твердження в ньому. З огляду на те, що ця проекція використовує асиметричне шифрування, неможливо повернутися від твердження на кроці 3 до вихідного твердження, забезпечуючи нульовий рівень інформації.

Математичні знання, необхідні для читання цієї статті, можна порівняти з рівнем алгебри, очікуваним від студентів першого курсу коледжу STEM. Єдиною концепцією, яка може бути складною, може бути криптографія еліптичної кривої. Для тих, хто з цим не знайомий, ви можете розглядати це як експоненціальну функцію зі спеціальною основою, маючи на увазі, що її обернена функція залишається нерозв’язаною.

Ця стаття дотримуватиметься таких правил позначення:

Матриці: жирні великі літери, напр A; написані в явних формах \
Вектори: мала літера зі стрілками, написана в явних формах [ ]; всі вектори є векторами-стовпцями за замовчуванням \
Скаляри: позначаються звичайними літерами

Візьмемо для прикладу таке запитання:

f(x)=x^3+x^2+5 (1)

Припустимо, Аліса хоче довести, що вона знає правду. Ми розглянемо всю процедуру, яку має виконати Аліса, щоб створити zk-SNARK для її доказу.
Це запитання може здатися надто простим, оскільки воно не включає контрольний потік (наприклад, if-then-else). Однак перетворити функції з потоком керування в арифметичні вирази неважко. Наприклад, розглянемо таку проблему (або «функцію» мовами програмування):

f(x, z):
якщо (z==1):
повернути xxx+xx+5
ще:
повернути xx+5

Переписати цю задачу в наступний арифметичний вираз (припускаючи, що z належить до (0,1)) не складніше, ніж рівняння (1).

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

У цій статті ми продовжимо використовувати рівняння (1) як основу для нашого обговорення.

Крок 1: Арифметична схема

Рівняння (1) можна розбити на такі основні арифметичні операції:

Це відповідає такій арифметичній схемі:

Ми також називаємо рівняння (2) набором із 4 «основних обмежень», кожне обмеження описує взаємозв’язок арифметичного вентиля в схемі. Загалом, набір із n первинних обмежень можна підсумувати як програму квадратичної арифметики (QAP), яка буде пояснена далі.

Крок 2: Матриця

Спочатку давайте визначимо вектор «свідок» наступним чином:

де y, s1, s2 і s3 визначені як у рівнянні (2).
Як правило, для задачі з m входами та n арифметичними елементами (тобто n-1 проміжних кроків і кінцевий результат), цей вектор-свідок буде (m+n+1) розмірним. У реальних випадках число n може бути надзвичайно великим. Наприклад, для хеш-функцій n зазвичай дорівнює тисячам.

Далі побудуємо три n(m+n+1) матриць A,B,C, щоб можна було переписати рівняння (2) таким чином:

Рівняння (3) є лише іншим представленням рівняння (2): кожен набір (ai, bi, ci) відповідає затвору в схемі. Ми можемо побачити це, явно розширивши матричне рівняння:

Таким чином, LHS=RHS є точно таким же, як рівняння (2), і кожен рядок матричного рівняння відповідає первинному обмеженню (тобто арифметичному вентилю в схемі).

Ми пропустили кроки побудови (A, B, C), які насправді відносно прості. Нам потрібно лише перетворити їх у матрицю відповідно до відповідних первинних обмежень, щоб визначити вміст кожного рядка (A, B, C), тобто (ai, bi, ci). Візьмемо перший рядок як приклад: ми можемо легко побачити, що щоб зробити перше первинне обмеження x, помножене на x, рівним s1, нам потрібно помножити [0,1,0,0,0], [0, 1,0, 0,0] і [0,0,0,1,0,0] вектором s.

Таким чином, ми успішно перетворили арифметичну схему в матричне рівняння, а саме рівняння (3). У той же час ми також змінили об’єкт, який потрібно довести, що він освоєний, на вектор-свідок s.

Крок 3: Поліноми

Тепер давайте побудуємо n(n+m+*1) матрицю PA, яка визначає набір поліномів щодо z:

Забезпечення функціїприймає такі значення в {1, 2, 3, 4} , задовольняє умови:

Тоді ми можемо переписати A так:

Це чотири набори лінійних рівнянь із шістьма змінними, які можна розв’язати традиційними методами. Однак більш ефективним способом вирішення ПА в цьому випадку є інтерполяція Лагранжа, яка використовує особливості проблеми. Тут ми пропускаємо процес вирішення PA, який є трохи виснажливим, але простим.

Подібним чином ми будуємо PB і PC окремо для B і C. Потім ми можемо переписати матричне рівняннянаступним чином:

Розглядаючи кожен рядок окремо, стає очевидним, що ці чотири рядки відповідають одному виразу, обчисленому в чотирьох різних точках. Отже, наведене вище матричне рівняння еквівалентне:

Крок 3: точка еліптичної кривої

Перепишіть рівняння (4) у вигляді:

де i(z)=1 — просто тривіальний поліном нульового ступеня від z, який використовується для уніфікації рівнянь — усі члени є квадратичними. Необхідність цього стане зрозумілою найближчим часом. Зауважте, що це рівняння містить лише додавання та множення поліномів від z.

Зверніть увагу, що арифметичні операції, додавання (+) і множення (X), також відображаються на відповідні операції в скінченному полі точок еліптичної кривої. Символи і використовуються, щоб уникнути плутанини та вказують на те, що це перевизначені польові операції.

Далі ми детальніше пояснимо практичні дії.

Криптографія еліптичної кривої

Загальна теорія еліптичних кривих виходить далеко за рамки цієї статті. Для цілей у цьому документі еліптична крива визначається як відображення від простого поля Fp до функції E, де E включає такі точки, що y^2=x^3+ax+b (називаються точками еліптичної кривої або скорочено ECP) .

Будь ласка, зверніть увагу, що поки ми обговорювали звичайну арифметику, при переході до простого поля арифметичні операції над числами виконуються за допомогою модульної арифметики. Наприклад, a+b=a+b(mod p), де p є порядком Fp.

З іншого боку, додавання двох точок еліптичної кривої визначається, як показано нижче:

Зокрема, додавання P і Q двох ECP:

Знайдіть точку перетину прямої PQ і кривої R і визначте її як -(P+Q)
Переверніть до «дзеркальної» точки R' від R на кривій.
Тому ми визначаємо додавання точок еліптичної кривої P+Q=R':

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

Тепер припустімо, що ми навмання вибрали точку G і відобразили на неї число 1. (Це «початкове відображення» звучить дещо довільно. Ми обговоримо це пізніше). І для будь-якого n, що належить Fp, ми визначаємо:

E(N)=G+G+G+…..+G=G, помножене на n

Є вираз операції. Визначте операцію +G як «генератор», позначену як g. Тоді наведене вище визначення еквівалентне:

Після визначення додавання стає очевидною така лінійна залежність:

Таким чином, будь-який лінійний зв’язок (або обмеження) у Fp буде збережено в зашифрованому просторі B через це відображення. Наприклад, рівняння l + m = n у Fp призведе до

Однак, оскільки рівняння (5), яке хоче довести Аліса, має квадратичну форму, воно недостатньо лінійне. Щоб працювати з квадратичними членами, нам потрібно визначити множення в зашифрованому просторі. Це називається сполученням або білінійною картою, про що я поясню в наступному розділі.

Білінійна карта

Нехай G1, G2 і GT — групи простого порядку g. Парна функція, або білінійна карта, визначається таким чином:

Загальний еталонний рядок

Це ціле називається «ключ перевірки» (PK). Зверніть увагу, що представлення векторів у E() слід розуміти як вектори точок еліптичної кривої, де кожна точка відображається з відповідного векторного елемента. Таким чином, ці 11 векторів фактично містять 62 (=42+63+63+63) точки еліптичної кривої. Ці 62 ECP будуть надані Алісі, досліднику. У загальному сценарії для проблеми з m входами та n первинними обмеженнями PK міститиме 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECP.

Одночасно будуть виконані такі обчислення:

Весь процес називається «ключ перевірки» (VK). Тут задіяно лише 7 точок еліптичної кривої (ECP), які необхідно надати верифікатору. Слід зазначити, що незалежно від того, скільки входів і первинних обмежень задіяно в задачі, ВК завжди складається з 7 ECP.

Крім того, варто зазначити, що «довірене налаштування» та процес генерації PK та VK потрібно виконувати лише один раз для конкретної проблеми.

Доведення та перевірка

Тепер, маючи відкритий ключ (PK), Аліса обчислить наступні точки еліптичної кривої (ECP):

Ці 9 точок еліптичної кривої є вирішальними для стислого неінтерактивного аргументу знання з нульовим знанням (zk-SNARK)!

Зверніть увагу, що Аліса, по суті, просто виконує лінійні комбінації на точках еліптичної кривої у відкритому ключі. Це особливо критично і буде ретельно перевірятися під час перевірки.

Тепер Аліса представляє доказ zk-SNARK, нарешті переходячи до процесу перевірки, який складається з трьох кроків.

По-перше, необхідно підтвердити, що перші 8 точок еліптичної кривої дійсно є лінійними комбінаціями цих точок у спільній еталонній ланцюжку.

Відмова від відповідальності:

1. Цю статтю передруковано з[chaincatcher]. Усі авторські права належать оригінальному автору [0xAlpha Co-founder @ DeriProtocol]. Якщо є заперечення щодо цього передруку, будь ласка, зв’яжіться з командою Gate Learn , і вони негайно розглянуть це.
2. Відмова від відповідальності: погляди та думки, висловлені в цій статті, належать виключно автору та не є жодною інвестиційною порадою.
3. Переклади статті на інші мови виконує команда Gate Learn. Якщо не зазначено вище, копіювання, розповсюдження або плагіат перекладених статей заборонено.