Проблеми, які необхідно довести-Арифметичні схеми-R1CS-Поліноми
**Навіщо зрештою перетворювати на поліном? **
Завдяки характеристикам поліномів час перевірки значно скорочується та досягається простота.
**Як досягти нульових знань? **
Простіше кажучи, у процесі виведення полінома вибираються ще два випадкових числа, так що похідний поліном може перешкодити верифікатору отримати коефіцієнти вихідного полінома, тобто секретний вхід прувера, так як реалізувати ЗК.
**Як досягти відсутності взаємодії? **
Перед початком перевірки вводиться третя сторона, тобто довірений параметр, який призначає початковому верифікатору завдання вибору випадкових чисел для довіреного параметра, таким чином реалізуючи відсутність взаємодії між верифікатором і перевіряльником.
За останні два роки технологія ZK привернула велику увагу в галузі Web3. Починаючи з Rollup, все більше і більше проектів на різних напрямках намагаються використовувати технологію ZK. Серед них SNARK і STARK є двома найпоширенішими термінами. Щоб краще зрозуміти застосування технології ZK на наступному етапі, **ця стаття спростить логіку доказу SNARK з нетехнічної точки зору, а потім використає * * Scroll's zk Rollup ** використовується як приклад для ілюстрації роботи системи перевірки zk. **
Мета статті — пояснити основну логіку, яку легко читати, уникати використання термінології та не вдаватися в подробиці, такі як математичне перетворення, будь ласка, вибачте мене за будь-які пропуски.
У січні 2012 року Алессандро К'єза, професор Каліфорнійського університету в Берклі, став співавтором статті про SNARK і запропонував термін zk-SNARK.
zk-SNARK, повна назва Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, є системою доказів, що використовує технологію ZK. **Слід зазначити, що SNARK — це назва класу схем, і існує багато різних методів комбінування, які можуть реалізувати SNARK. **
Нульове знання: те, що знає лише перевіряючий, буде приховано, і ніхто інший не зможе це побачити, крім перевіряючого.
Короткий (короткий): згенерований доказ невеликий, а час перевірки швидкий.
Неінтерактивний (неінтерактивний): між прувером і верифікатором практично немає взаємодії.
Аргумент: Перевірка верифікатора дійсна лише для перевірки з обмеженою обчислювальною потужністю, оскільки перевірка з суперобчислювальною потужністю може підробити доказ, тобто система має обчислювальну надійність.
Знання: перевіряючий може обчислити доказ, лише якщо він знає певну інформацію, якої не знає перевіряючий.
Що має вирішити zk-SNARK, так це «проблему перевірки обчислень», тобто чи може верифікатор ефективно перевірити результати обчислень, не знаючи конфіденційності прувера.
Нижче буде використано спрощений процес побудови zk-SNARK, щоб проілюструвати, як система поєднує нульові знання для досягнення ефективної перевірки. **
Конструкція Zk-SNARK
Перетворіть задачу, яку потрібно довести, на поліном
Простіше кажучи, ідея SNARK полягає в тому, щоб перетворити доказ того, чи є твердження істинним чи ні, у доказ того, чи поліноміальна рівність істинна чи ні.
Весь процес перетворення: проблеми, які необхідно перевірити ➡ арифметична схема ➡ R1CS ➡ поліном ➡ перетворення між поліномами
Питання для перевірки➡Арифметична схема
Щоб довести, чи є питання істинним за допомогою обчислень, питання, яке потрібно довести, спочатку має бути перетворено в задачу обчислення, і будь-яке обчислення можна описати як арифметичну схему.
Арифметичні схеми зазвичай складаються з констант, «вентів додавання» та «вентів множення». За допомогою суперпозиції вентилів ми можемо будувати комплексні поліноми.
Поліном, побудований арифметичною схемою на малюнку вище: (Inp1+Inp2)*(-1) = Вихід
Насправді задачу надзвичайно складно перетворити на арифметичну схему. Ми можемо просто розуміти це як: ввести деякий вміст, вміст трансформується схемою, і, нарешті, вивести результат. Зараз:
На основі концепції арифметичних схем будуємо арифметичну схему для генерації доказів, а саме:
Схема містить два набори входів: публічний вхід x і секретний вхід w. Загальнодоступний вхід x означає, що вміст є фіксованим значенням проблеми, яку потрібно перевірити, яке відомо як верифікатору, так і перевіряючому, а секретний вхід w означає, що вміст відомий лише перевіряючому.
Арифметична схема, яку ми побудували, є C( x, w ) = 0, тобто введення x і w через схему, а кінцевий вихідний результат дорівнює 0. Коли перевіряльник і верифікатор знають, що вихід схеми дорівнює 0, а публічний вхід — x, перевіряльнику потрібно довести, що він знає секретний вхід w.
Арифметична схема ➡R1CS
Нарешті нам потрібен поліном, але арифметичну схему не можна безпосередньо перетворити на поліном, і R1CS потрібен як посередник між ними, тому арифметичну схему спочатку перетворюють на R1CS.
R1CS, повна назва Rank-1 Constraints (система обмежень першого порядку), — це мова для опису схем, яка, по суті, є матрично-векторним рівнянням. Зокрема, R1CS — це послідовність із трьох векторів (a,b,c), а розв’язок R1CS — вектор s, де s має задовольняти рівняння:
Серед них являє собою операцію внутрішнього продукту.
Конкретне математичне перетворення тут можна знайти у Ваталік: Програми квадратичної арифметики: від нуля до героя
Нам лише потрібно знати, що роль **R1CS полягає в тому, щоб обмежити опис кожного вентиля в арифметичній схемі, щоб вектори між кожними воротами задовольняли наведене вище співвідношення. **
R1CS➡Поліном
Отримавши середовище R1CS, ми можемо перетворити його на поліноміальний еквівалент.
Еквівалентні перетворення між матрицями та поліномами можна виконати, як показано на наступному малюнку:
поліном
перетворити на матрицю
Згідно з природою наведеного вище еквівалентного перетворення, для матриці, яка задовольняє R1CS, ми можемо використати метод інтерполяції Лагранжа для відновлення кожного коефіцієнта полінома.На основі цього співвідношення ми можемо вивести матрицю R1CS як поліноміальне співвідношення, а саме:
Примітка: A, B, C представляють поліном відповідно
Поліном відповідає обмеженню матриці R1CS, що відповідає проблемі, яку ми хочемо довести. Завдяки наведеному вище перетворенню ми можемо знати, що якщо поліноми задовольняють наведеному вище співвідношенню, це означає, що наша матриця R1CS є правильною, таким чином вказуючи, що перевірка знаходиться в арифметичній схемі. Секретний вхід для також правильний.
До цього моменту наша проблема спрощена таким чином: верифікатор випадковим чином вибирає число x і просить сертифікатора довести, що A(x) * B(x)=C(x) встановлено. Якщо це встановлено, це означає, що секретний вхід сертифікатора правильний.
Перетворення між поліномами
У складних арифметичних схемах існують десятки тисяч вентилів, і нам потрібно перевірити, чи задовольняє кожен вентиль обмеження R1CS. Іншими словами, нам потрібно кілька разів перевірити рівність A(x) * B(x)=C(x), але ефективність окремої перевірки одна за одною надто низька. Як ми можемо перевірити правильність усіх обмеження воріт за один раз? секс?
Для зручності розуміння введемо P(x), нехай P(x) = A(x) * B(x) – C(x)
Ми знаємо, що будь-який поліном можна розкласти на лінійні поліноми, якщо він має розв’язок. Отже, ми розбиваємо P(x) на F(x) і H(x), а саме:
Тоді F(x) є відкритим, що означає, що існує H(x) = P(x)/F(x), тому поліном, який ми хочемо перевірити, нарешті перетворюється на:
A(x) * B(x) – C(x): Містить коефіцієнти полінома, відомі лише перевіряльнику, тобто секретний вхід.
F(x) : загальнодоступний поліном, відомий як верифікатору, так і перевіряючому, тобто відкритий вхід.
H(x): Довідник знає це через обчислення, але верифікатор непізнаваний.
**Остання проблема, яку потрібно довести: поліноміальне рівняння A(x) * B(x) – C(x) = F(x) * H(x), виконується на всіх x. **
Тепер необхідно лише один раз перевірити поліном, щоб переконатися, що всі обмеження задовольняють матричним співвідношенням.
**Тут ми завершили перетворення проблеми, яку потрібно довести, у поліном, який потрібно перевірити лише один раз, усвідомлюючи простоту системи. **
Але простота цієї реалізації полягає в скороченні часу перевірки верифікатора, тож як щодо розміру доказу?
**Просто кажучи, у протоколі перевірки використовується деревовидна структура Merkle, яка ефективно зменшує розмір перевірки. **
Після завершення всього процесу перетворення природно виникнуть дві проблеми:
Навіщо перетворювати на поліном?
Оскільки поліноми забезпечують простоту доведення. Проблема доказу з нульовим знанням полягає в тому, щоб переконатися, що обчислення задовольняють множині обмежень, а поліноми можуть перевіряти численні обмеження в одній точці. Іншими словами, верифікатор повинен перевірити n разів, щоб підтвердити проблему, але тепер потрібно перевірити лише один раз, щоб підтвердити правильність доказу з високою ймовірністю.
Чому два поліноми A(x) * B(x) – C(x )= F(x) * H(x) можна встановити шляхом перевірки точки на поліномі?
Це визначається характеристиками поліномів, тобто результат обчислення полінома в будь-якій точці можна розглядати як представлення його унікальної ідентичності. Для двох поліномів вони перетинатимуться лише в кінцевій кількості точок.
Для двох наведених вище поліномів ступеня d: A(x) * B(x) – C(x) і F(x) * H(x), якщо вони не рівні, вони будуть лише не більше d точок Перетинаються, тобто розв’язки в d точках однакові.
Після завершення перетворення полінома ми переходимо до етапу доказу полінома.
Доведіть, що поліном виконується
Для ілюстрації ми використовуємо поліном P(x) = F(x) * H(x).
Тепер проблема, яку довідник хоче довести: на всіх x P(x) = F(x) * H(x).
Процес перевірки наведеного вище полінома перевіряючим і перевіряючим виглядає наступним чином:
Верифікатор вибирає випадкову точку виклику x, припускаючи, що x = s;
Після того, як прувер отримає s, обчисліть P(s) і H(s) і передайте ці два значення верифікатору;
Верифікатор спочатку обчислює F(s), потім обчислює F(s) * H(s) і оцінює, чи є F(s) * H(s) = P(s) істинним, і якщо це правда, перевірку пройдено.
Але якщо ми уважно подумаємо, то побачимо, що в описаному вище процесі є деякі проблеми:
Тест, який перевіряє, може знати інформацію про все рівняння. Якщо він отримує випадкову точку s, він може обчислити F(s), а потім побудувати пару фальшивих P(x) і H(x), щоб P(s ) = F(s) * H(s), щоб обдурити верифікатор.
Пристрій перевірки не використовує s, надані верифікатором, для обчислення F(s) і H(s), але обчислює інші значення, щоб ввести в оману верифікатор.
Значення, отримане верифікатором, обчислюється загальнодоступним і приватним введенням перевірки. Якщо верифікатор має велику обчислювальну потужність, він може зламати приватні дані перевірки.
Щоб вирішити вищевказані проблеми, ми проводимо такі оптимізації:
Після того, як верифікатор вибере випадкову точку s, він виконує гомоморфне шифрування на s. Гомоморфне шифрування означає розв’язок, обчислений після шифрування = розв’язок, зашифрований після обчислення; у цій формі шифрування перевіряльник може обчислити розв’язок, але не може побудувати помилкові P(x) і H(x).
Коли верифікатор вибирає точку виклику s, вибирається інший випадковий параметр λ для створення додаткового лінійного зв’язку між s та λ. Верифікатор надсилає як s, так і λ після гомоморфного шифрування до перевірювача. Довідник надсилає доказ назад, і верифікатор повинен перевірити зв’язок між випадковими параметрами λ і s на додаток до перевірки того, чи доказ є істинним.
**Націлюючись на проблему того, що верифікатор може зламати секретний вхід, ми можемо ввести ZK. ** Переглядаючи весь доказ, ми можемо виявити, що під час процесу перевірки перевіряльник надсилає лише розраховане значення полінома верифікатору, а верифікатор може вивести коефіцієнт полінома через значення, яке є секретним введенням перевірка. Щоб запобігти відштовхуванню верифікатора, ми можемо вибрати ще два випадкових числа та додати набір значень під час отримання поліномів A, B і C з R1CS, щоб відновлений поліном був на один порядок більший за початковий поліном , так що читач не може отримати інформацію про вихідний поліном із зашифрованого полінома для реалізації ZK.
Після оптимізації ми виявили, що система перевірки все ще вимагає взаємодії між верифікатором і перевіряльником. Як ми можемо досягти відсутності взаємодії?
Реалізувати неінтерактивний
**Щоб досягти відсутності взаємодії, SNARK вводить довірені налаштування (Налаштування). **
Іншими словами, перед початком перевірки право верифікатора вибирати випадкові точки виклику передається довіреній третій стороні.Після того, як третя сторона вибирає випадковий параметр λ, вона поміщає зашифрований λ у схему R1CS. Таким чином, генерується CRS (Common Reference String, рядок публічного посилання). Верифікатор може отримати свій власний Sv від CRS, а перевіряючий може отримати свій власний Sp від CRS.
Слід зазначити, що λ потрібно знищити після генерації Sv і Sp. Якщо λ витік, він може бути використаний для підробки транзакцій через помилкову перевірку.
робочий процес zk-SNARK
Після розуміння процесу побудови SNARK на основі створеної нами арифметичної схеми, яка може генерувати докази, процес перевірки zk-SNARK виглядає наступним чином:
Налаштування: (ланцюг C, λ) = (Sv, Sp)
За допомогою схеми C і випадкового параметра λ генеруються випадкові параметри Sv і Sp, які використовуються наступним првером і верифікатором.
Доведіть(Sp,x,w) = Π
Пристрій перевірки обчислює доказ Π за допомогою випадкового параметра Sp, публічного введення x і секретного введення w.
Перевірте (Sv,x,Π) == (∃ w st C(x,w))
Верифікатор перевіряє, чи існує C(x,w)=0 за допомогою випадкового параметра Sv, відкритого введення x і доказу Π. У той же час перевірте, чи обчислено доказ за схемою C чи ні.
На цьому ми завершили пояснення всього zk-SNARK. Давайте подивимося на фактичний випадок застосування.
Випадок: візьміть Scroll's zk Rollup як приклад
Роль системи доказів полягає в тому, щоб дозволити перевіряючому переконати перевіряючого вірити в одне;
Для системи zk-доказу це полягає в тому, щоб змусити верифікатора повірити, що Zero-Knowledge Proof (доказ з нульовим знанням), обчислений алгоритмом zk, є істинним.
Ми беремо Scroll's zk Rollup як приклад, щоб проілюструвати роботу системи перевірки zk.
Зведення стосується обчислень поза ланцюгом і перевірки в ланцюзі. Для zk Rollup після того, як транзакція буде виконана поза ланцюгом, перевіряльнику необхідно згенерувати сертифікат zk для нового кореня стану, згенерованого після виконання транзакції, а потім передати сертифікат контракту L1 Rollup для перевірки в ланцюжку.
Слід зазначити, що в zk Rollup є два типи блоків:
L1 Rollup block: блок, надісланий до Ethereum
Блок L2: блок, що складається з транзакцій, надісланих користувачами на L2
Нижче наведено робочий процес Scroll's zk Rollup:
Користувач ініціює транзакцію в L2, секвенсор отримує транзакцію, виконує транзакцію поза ланцюжком і генерує блок L2 і новий корінь стану; в той же час надсилає дані транзакції та новий корінь стану в контракт Rollup. на Ethereum (надсилання даних про транзакції для доступності даних);
Коли генерується блок L2, Координатор отримає трек виконання блоку від секвенсора, а потім випадковим чином призначить трек будь-якому ролику;
Roller перетворює отриману доріжку виконання в схеми та генерує сертифікат дійсності для кожної схеми, а потім надсилає сертифікат назад до координатора;
Кожного разу, коли генерується k блоків L2, Координатор надсилає завдання агрегування іншому ролику, щоб об’єднати докази k блоків у єдиний агрегований доказ;
Координатор подає єдине підтвердження агрегації до контракту зведення, а контракт під час зведення перевіряє підтвердження агрегації в поєднанні з попередньо наданими кореневими даними стану та даними транзакції. Якщо перевірка пройшла, відповідний блок вважається завершеним на Scroll.
Як видно з наведеного вище процесу, Roller є проверкою в системі, а контракт Rollup є перевіркою. Roller генерує доказ zk для транзакцій, здійснених поза ланцюгом; контракт Rollup перевіряє підтвердження, і якщо перевірку пройдено, контракт Rollup безпосередньо прийме поданий корінь стану як новий корень стану.
Переглянути оригінал
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Конструкція та корпус zk-SNARK
TL;DR
Проблеми, які необхідно довести-Арифметичні схеми-R1CS-Поліноми
Завдяки характеристикам поліномів час перевірки значно скорочується та досягається простота.
Простіше кажучи, у процесі виведення полінома вибираються ще два випадкових числа, так що похідний поліном може перешкодити верифікатору отримати коефіцієнти вихідного полінома, тобто секретний вхід прувера, так як реалізувати ЗК.
Перед початком перевірки вводиться третя сторона, тобто довірений параметр, який призначає початковому верифікатору завдання вибору випадкових чисел для довіреного параметра, таким чином реалізуючи відсутність взаємодії між верифікатором і перевіряльником.
За останні два роки технологія ZK привернула велику увагу в галузі Web3. Починаючи з Rollup, все більше і більше проектів на різних напрямках намагаються використовувати технологію ZK. Серед них SNARK і STARK є двома найпоширенішими термінами. Щоб краще зрозуміти застосування технології ZK на наступному етапі, **ця стаття спростить логіку доказу SNARK з нетехнічної точки зору, а потім використає * * Scroll's zk Rollup ** використовується як приклад для ілюстрації роботи системи перевірки zk. **
Мета статті — пояснити основну логіку, яку легко читати, уникати використання термінології та не вдаватися в подробиці, такі як математичне перетворення, будь ласка, вибачте мене за будь-які пропуски.
У січні 2012 року Алессандро К'єза, професор Каліфорнійського університету в Берклі, став співавтором статті про SNARK і запропонував термін zk-SNARK.
zk-SNARK, повна назва Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, є системою доказів, що використовує технологію ZK. **Слід зазначити, що SNARK — це назва класу схем, і існує багато різних методів комбінування, які можуть реалізувати SNARK. **
Що має вирішити zk-SNARK, так це «проблему перевірки обчислень», тобто чи може верифікатор ефективно перевірити результати обчислень, не знаючи конфіденційності прувера.
Нижче буде використано спрощений процес побудови zk-SNARK, щоб проілюструвати, як система поєднує нульові знання для досягнення ефективної перевірки. **
Конструкція Zk-SNARK
Перетворіть задачу, яку потрібно довести, на поліном
Простіше кажучи, ідея SNARK полягає в тому, щоб перетворити доказ того, чи є твердження істинним чи ні, у доказ того, чи поліноміальна рівність істинна чи ні.
Весь процес перетворення: проблеми, які необхідно перевірити ➡ арифметична схема ➡ R1CS ➡ поліном ➡ перетворення між поліномами
Питання для перевірки➡Арифметична схема
Щоб довести, чи є питання істинним за допомогою обчислень, питання, яке потрібно довести, спочатку має бути перетворено в задачу обчислення, і будь-яке обчислення можна описати як арифметичну схему.
Арифметичні схеми зазвичай складаються з констант, «вентів додавання» та «вентів множення». За допомогою суперпозиції вентилів ми можемо будувати комплексні поліноми.
Поліном, побудований арифметичною схемою на малюнку вище: (Inp1+Inp2)*(-1) = Вихід
Насправді задачу надзвичайно складно перетворити на арифметичну схему. Ми можемо просто розуміти це як: ввести деякий вміст, вміст трансформується схемою, і, нарешті, вивести результат. Зараз:
На основі концепції арифметичних схем будуємо арифметичну схему для генерації доказів, а саме:
Схема містить два набори входів: публічний вхід x і секретний вхід w. Загальнодоступний вхід x означає, що вміст є фіксованим значенням проблеми, яку потрібно перевірити, яке відомо як верифікатору, так і перевіряючому, а секретний вхід w означає, що вміст відомий лише перевіряючому.
Арифметична схема, яку ми побудували, є C( x, w ) = 0, тобто введення x і w через схему, а кінцевий вихідний результат дорівнює 0. Коли перевіряльник і верифікатор знають, що вихід схеми дорівнює 0, а публічний вхід — x, перевіряльнику потрібно довести, що він знає секретний вхід w.
Арифметична схема ➡R1CS
Нарешті нам потрібен поліном, але арифметичну схему не можна безпосередньо перетворити на поліном, і R1CS потрібен як посередник між ними, тому арифметичну схему спочатку перетворюють на R1CS.
R1CS, повна назва Rank-1 Constraints (система обмежень першого порядку), — це мова для опису схем, яка, по суті, є матрично-векторним рівнянням. Зокрема, R1CS — це послідовність із трьох векторів (a,b,c), а розв’язок R1CS — вектор s, де s має задовольняти рівняння:
Серед них являє собою операцію внутрішнього продукту.
Конкретне математичне перетворення тут можна знайти у Ваталік: Програми квадратичної арифметики: від нуля до героя
Нам лише потрібно знати, що роль **R1CS полягає в тому, щоб обмежити опис кожного вентиля в арифметичній схемі, щоб вектори між кожними воротами задовольняли наведене вище співвідношення. **
R1CS➡Поліном
Отримавши середовище R1CS, ми можемо перетворити його на поліноміальний еквівалент.
Еквівалентні перетворення між матрицями та поліномами можна виконати, як показано на наступному малюнку:
поліном
перетворити на матрицю
Згідно з природою наведеного вище еквівалентного перетворення, для матриці, яка задовольняє R1CS, ми можемо використати метод інтерполяції Лагранжа для відновлення кожного коефіцієнта полінома.На основі цього співвідношення ми можемо вивести матрицю R1CS як поліноміальне співвідношення, а саме:
Примітка: A, B, C представляють поліном відповідно
Поліном відповідає обмеженню матриці R1CS, що відповідає проблемі, яку ми хочемо довести. Завдяки наведеному вище перетворенню ми можемо знати, що якщо поліноми задовольняють наведеному вище співвідношенню, це означає, що наша матриця R1CS є правильною, таким чином вказуючи, що перевірка знаходиться в арифметичній схемі. Секретний вхід для також правильний.
До цього моменту наша проблема спрощена таким чином: верифікатор випадковим чином вибирає число x і просить сертифікатора довести, що A(x) * B(x)=C(x) встановлено. Якщо це встановлено, це означає, що секретний вхід сертифікатора правильний.
Перетворення між поліномами
У складних арифметичних схемах існують десятки тисяч вентилів, і нам потрібно перевірити, чи задовольняє кожен вентиль обмеження R1CS. Іншими словами, нам потрібно кілька разів перевірити рівність A(x) * B(x)=C(x), але ефективність окремої перевірки одна за одною надто низька. Як ми можемо перевірити правильність усіх обмеження воріт за один раз? секс?
Для зручності розуміння введемо P(x), нехай P(x) = A(x) * B(x) – C(x)
Ми знаємо, що будь-який поліном можна розкласти на лінійні поліноми, якщо він має розв’язок. Отже, ми розбиваємо P(x) на F(x) і H(x), а саме:
Тоді F(x) є відкритим, що означає, що існує H(x) = P(x)/F(x), тому поліном, який ми хочемо перевірити, нарешті перетворюється на:
A(x) * B(x) – C(x): Містить коефіцієнти полінома, відомі лише перевіряльнику, тобто секретний вхід.
F(x) : загальнодоступний поліном, відомий як верифікатору, так і перевіряючому, тобто відкритий вхід.
H(x): Довідник знає це через обчислення, але верифікатор непізнаваний.
**Остання проблема, яку потрібно довести: поліноміальне рівняння A(x) * B(x) – C(x) = F(x) * H(x), виконується на всіх x. **
Тепер необхідно лише один раз перевірити поліном, щоб переконатися, що всі обмеження задовольняють матричним співвідношенням.
**Тут ми завершили перетворення проблеми, яку потрібно довести, у поліном, який потрібно перевірити лише один раз, усвідомлюючи простоту системи. **
Але простота цієї реалізації полягає в скороченні часу перевірки верифікатора, тож як щодо розміру доказу?
**Просто кажучи, у протоколі перевірки використовується деревовидна структура Merkle, яка ефективно зменшує розмір перевірки. **
Після завершення всього процесу перетворення природно виникнуть дві проблеми:
Оскільки поліноми забезпечують простоту доведення. Проблема доказу з нульовим знанням полягає в тому, щоб переконатися, що обчислення задовольняють множині обмежень, а поліноми можуть перевіряти численні обмеження в одній точці. Іншими словами, верифікатор повинен перевірити n разів, щоб підтвердити проблему, але тепер потрібно перевірити лише один раз, щоб підтвердити правильність доказу з високою ймовірністю.
Це визначається характеристиками поліномів, тобто результат обчислення полінома в будь-якій точці можна розглядати як представлення його унікальної ідентичності. Для двох поліномів вони перетинатимуться лише в кінцевій кількості точок.
Для двох наведених вище поліномів ступеня d: A(x) * B(x) – C(x) і F(x) * H(x), якщо вони не рівні, вони будуть лише не більше d точок Перетинаються, тобто розв’язки в d точках однакові.
Після завершення перетворення полінома ми переходимо до етапу доказу полінома.
Доведіть, що поліном виконується
Для ілюстрації ми використовуємо поліном P(x) = F(x) * H(x).
Тепер проблема, яку довідник хоче довести: на всіх x P(x) = F(x) * H(x).
Процес перевірки наведеного вище полінома перевіряючим і перевіряючим виглядає наступним чином:
Але якщо ми уважно подумаємо, то побачимо, що в описаному вище процесі є деякі проблеми:
Щоб вирішити вищевказані проблеми, ми проводимо такі оптимізації:
Після оптимізації ми виявили, що система перевірки все ще вимагає взаємодії між верифікатором і перевіряльником. Як ми можемо досягти відсутності взаємодії?
Реалізувати неінтерактивний
**Щоб досягти відсутності взаємодії, SNARK вводить довірені налаштування (Налаштування). **
Іншими словами, перед початком перевірки право верифікатора вибирати випадкові точки виклику передається довіреній третій стороні.Після того, як третя сторона вибирає випадковий параметр λ, вона поміщає зашифрований λ у схему R1CS. Таким чином, генерується CRS (Common Reference String, рядок публічного посилання). Верифікатор може отримати свій власний Sv від CRS, а перевіряючий може отримати свій власний Sp від CRS.
Слід зазначити, що λ потрібно знищити після генерації Sv і Sp. Якщо λ витік, він може бути використаний для підробки транзакцій через помилкову перевірку.
робочий процес zk-SNARK
Після розуміння процесу побудови SNARK на основі створеної нами арифметичної схеми, яка може генерувати докази, процес перевірки zk-SNARK виглядає наступним чином:
За допомогою схеми C і випадкового параметра λ генеруються випадкові параметри Sv і Sp, які використовуються наступним првером і верифікатором.
Пристрій перевірки обчислює доказ Π за допомогою випадкового параметра Sp, публічного введення x і секретного введення w.
Верифікатор перевіряє, чи існує C(x,w)=0 за допомогою випадкового параметра Sv, відкритого введення x і доказу Π. У той же час перевірте, чи обчислено доказ за схемою C чи ні.
На цьому ми завершили пояснення всього zk-SNARK. Давайте подивимося на фактичний випадок застосування.
Випадок: візьміть Scroll's zk Rollup як приклад
Роль системи доказів полягає в тому, щоб дозволити перевіряючому переконати перевіряючого вірити в одне;
Для системи zk-доказу це полягає в тому, щоб змусити верифікатора повірити, що Zero-Knowledge Proof (доказ з нульовим знанням), обчислений алгоритмом zk, є істинним.
Ми беремо Scroll's zk Rollup як приклад, щоб проілюструвати роботу системи перевірки zk.
Зведення стосується обчислень поза ланцюгом і перевірки в ланцюзі. Для zk Rollup після того, як транзакція буде виконана поза ланцюгом, перевіряльнику необхідно згенерувати сертифікат zk для нового кореня стану, згенерованого після виконання транзакції, а потім передати сертифікат контракту L1 Rollup для перевірки в ланцюжку.
Слід зазначити, що в zk Rollup є два типи блоків:
Нижче наведено робочий процес Scroll's zk Rollup:
Як видно з наведеного вище процесу, Roller є проверкою в системі, а контракт Rollup є перевіркою. Roller генерує доказ zk для транзакцій, здійснених поза ланцюгом; контракт Rollup перевіряє підтвердження, і якщо перевірку пройдено, контракт Rollup безпосередньо прийме поданий корінь стану як новий корень стану.