Вступ

Короткі не інтерактивні аргументи знання (SNARK) — це потужні криптографічні примітиви, які знаходять своє застосування у децентралізованих фінансах, управлінні та обчисленнях. Існує безліч різних SNARK таких, як Marlin (на якому заснований Aleo), Plonk , STARK , Groth16 і т.д., побудованих на різних інструментах та з різними продуктивністю, розміром доказів, часом перевірки тощо. Проте всі вони ґрунтуються на загальних принципах та властивостях. Серед SNARK найважливішими для приватних програм є SNARK з нульовим розголошенням (скорочено zk-SNARK). Вони дозволяють доводити, що знаємо якісь змінні, звані свідком, w , такі, що вихідне значення функціїF , обчислене у свідку та примірнику (публічних змінних), x , дорівнює F(x, w) = y , не розкриваючи при цьому нічого про w .

Комп'ютерні програми можуть бути перетворені на функції, які приймають вхідні дані (деякі з них, можливо, захочемо приховати), і правильне виконання яких ми доводимо за допомогою SNARK. Наприклад, ми можемо перетворити програму на арифметичну схему, C , і, враховуючи публічні вхідні та вихідні дані, x , і засекречені дані, w , ми можемо довести, що програма була виконана коректно, продемонструвавши здійсненність схеми, C(x, w)= 0 . Оскільки здійснюваність арифметичних схем — це NP-повне завдання , ми можемо звести будь-яке NP-завдання до арифметичної схеми (проте це не єдина альтернатива, і кілька конструкцій спираються на інші техніки).

Перед тим, як перейти до деталей, дозвольте пояснити головні властивості SNARK та дати точні визначення кожного слова у його назві. У zk-SNARK беруть участь дві сторони, що доводить і перевіряє, де перший намагається переконати останнього в цьому твердженні, наприклад, у тому, що той, хто доводить, знає такий w , що C(x, w)=0 . SNARK має задовольняти властивостям:

1. Завершеності: якщо доказуючий знає w , він повинен бути здатний переконати чесного перевіряючого у достовірності затвердження.

2. Надійності: якщо твердження хибне, то жоден обманюючий доводить не зможе переконати перевіряючого прийняти його, за винятком випадків із дуже низькою ймовірністю.

3. Нульового розголошення: доказ не розкриває жодної інформації про свідка.

Що стосується назви:

1. Короткість: докази мають бути короткими та швидко перевіряються. Це дозволило б нам делегувати дорогі обчислення ненадійним сторонам та перевіряти їх достовірність без необхідності запускати програму самостійно.

2. Не інтерактивність: ні для генерації, ні для перевірки доказу не потрібна взаємодія між доказуючим та перевіряючим. Ми побачимо, що спочатку конструкція покладалася на інтерактивні докази, але ми зможемо перетворити їх на не інтерактивні, використовуючи трансформацію Фіата-Шаміра .

3. Аргумент знання: ми можемо довести, що ми знаємо свідка.

   Налаштування

   SNARK вимагають довірене налаштування. Серед її видів ми можемо виділити:

   — Єдиний довідковий рядок, або прозорі налаштування ( URS ).

   — Структурований рядок посилань, або приватне налаштування ( SRS ).

   У випадку SRS ми можемо натрапити на два випадки:

   • Універсальна (наприклад, MARLIN)

   • Конкретна (Groth 16)

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

   Імовірнісні докази та можливості перевіряючого

   Короткість аргументу спирається на імовірнісні докази. Щоб це було можливо, ми спочатку маємо встановити те, що відповідає “повноваженням”, чи можливостям перевіряючого. Є:

   — Інтерактивність: перевіряльнику дозволяється взаємодіяти з доказуючим, надсилаючи виклики та отримуючи відповіді.

   — Безліч доказуючих: є кілька доказувачів, але всі вони ізольовані.

   — Випадковість: перевіряючий може вибирати випадкові елементи чи запити.

   — Можливість надсилання запитів до оракулу : перевіряючий може надсилати запити на повідомлення доказуючого.

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

   • Інтерактивність + Випадковість: Інтерактивні докази (ІР).

   — Випадковість + Оракул: Докази (PCP), що ймовірно перевіряються.

   • Інтерактивність + Випадковість + Оракул: Інтерактивні докази з оракулом (IOP).

   Є й інші можливі варіанти, наприклад, MIOP, але ми зосередимося попередніх трьох. На даний момент IOP надає найбільш ефективну конструкцію для SNARK: квазілінійний час перевірки, лінійна довжина розміру доказів, лінійний час доказу та ефективні реалізації. PCP цікаві з теоретичної точки зору, але на практиці не ефективні (вони не призводять до коротких доказів, за винятком лінійних запитів). Нарешті IP надають цікаві будівельні блоки у вигляді підпрограм.

   У IOP доводить і перевіряє обмінюються повідомленнями. Той, хто доводить, надсилає довільні повідомлення (в поліноміальному IOP доказуючий відправляє зобов'язання - див. наступний розділ - поліномам), і перевіряючий відправляє випадкові виклики. Після кількох раундів перевіряючий складає запит із кількох змінних і вирішує, прийняти доказ чи ні.

   Схема зобов'язань

   Продуктивність SNARK залежить від типу використаних зобов'язань; За останні роки було зроблено багато кроків щодо їх поліпшення.

   Ми можемо подавати зобов'язання як сейф. Ми робимо якийсь вибір для ставки, кладемо його в сейф та передаємо іншому. Коли оголошено результат, ми можемо розкрити нашу ставку, відкривши сейф.

   Зобов'язання має задовольняти двом властивостям:

   — Зв'язуюче: ми не можемо зробити два вірних відкриття для того самого зобов'язання. Іншими словами, якщо зобов'язання має якесь значення a , повинно бути неможливо знайти такий b , що cm(a) = cm(b) .

   — Приховуюче: зобов'язання не розкриває нічого про зафіксовані дані.

   Один із способів зафіксувати повідомлення - використовувати стійку до колізій хеш-функцію. Якщо нам дані повідомлення m і випадкове значення r , cm(m, r) = hash(m ∣ r) Враховуючи, що вона стійка до колізій, ми отримуємо властивість зв'язування. Потім ми можемо відкрити зобов'язання та перевірити: Verify( m, r, cm ) → прийняти чи відхилити Однією з переваг зобов'язань є те, що вони схильні бути короткими. Наприклад, якщо ми будемо використовувати SHA-256 , довжина доказу дорівнюватиме 32 байтам.

   Одна важлива група зобов'язань – це поліноміальні схеми. Нижче представлені кілька конструкцій та математика, на якій вони ґрунтуються:

   • Базові еліптичні криві : bulletproofs

   • Білінійні групи: поліноміальні зобов'язання Kate-Zaverucha-Goldberg (KZG) (спарювання, довірене налаштування), DORY (без довірчого налаштування)

   • Групи невизначеного порядку: DARK

   • Тільки хеш-функції: FRI

     Анатомія СНАРК

     SNARK може бути сконструйований шляхом вибору наступних двох елементів:

     • Тип імовірнісного доказу: наприклад, доказ, що вірогідно перевіряється (PCP) або інтерактивний доказ з оракулом (IOP). Особливий вид IOP – це поліноміальний IOP (PIOP).

     • Схеми зобов'язань (криптографія). Наприклад, поліноміальні/функціональні зобов'язання, векторні зобов'язання та лінійне кодування.

       Імовірнісний доказ визначає тип обчислення. Можливі варіанти машинного обчислення (наприклад, vmTinyRam) чи схеми.

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

     • Лінійне кодування: Спарювання еліптичних кривих (ECP) + Грати

     — Векторне зобов'язання: стійкий до колізій хеш-функції (CRH) + ECP

     • Поліноміальні зобов'язання: CRH, ECP, PO групи, UO групи

     Деякі рецепти SNARK:

     Лінійне PCP + Лінійне кодування: Groth16, Groth-Maller 17 PCP/IOP + Векторне зобов'язання: STARK Поліноміальне PCP/IOP + Поліноміальне зобов'язання: MARLIN, SONIC, Plonk, Spartan. Bulletproofs використовують кілька різних комбінацій перерахованих вище елементів і засновані на криптографічних перевірках суми.

     Розмір доказу залежить від типу конструкції. Наприклад, для PIOP з поліноміальними зобов'язаннями KZG доказ займає менше ніж 1 КіБ (два елементи еліптичних кривих), тоді як IOP з FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) – близько 100 КіБ, більш ніж на два порядки більше! Це так, тому що FRI використовує дерева Меркла ; для перевірки потрібен шлях автентифікації, що вимагає кількох хешів.

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

     Тепер ми зосередимося на поліноміальних зобов'язаннях KZG, які є основою Marlin та Plonk.

     Схема поліноміальних зобов'язань KZG

     Схема поліноміальних зобов'язань має такі алгоритми:

     1. Настройка.

     2. Фіксація.

     3. Відкриття.

     Щоб зафіксувати поліном, ми оцінимо його у заданій, але невідомій точці α .

     Налаштування приймає максимальний ступінь полінома (що залежить від кількості вентилів арифметичної схеми) і виводить загальнодоступні параметри: ключ, що доводить, і перевіряючий ключ. Щоб мати можливість обчислювати багаточлени, ми будемо використовувати еліптичну криву (нам потрібно, щоб вона була зручною для парування, наприклад, BLS 12–377), щоб приховати α та його потужності ( α вибирається під час церемонії налаштування та викидається як токсичне сміття!) . Щоб зробити це, ми вибираємо генератор з групи великого простого порядку d +1, g і обчислюємо

Це дасть нам дуже велику колекцію точок еліптичної кривої (ми збережемо їх у вигляді рядка), яка буде працювати як ключ, що доводить. У разі універсального налаштування кількість елементів збігатиметься з максимальним розміром схеми. Оскільки точки еліптичної кривої займають близько 100 В, якщо ми хочемо мати справу з 10⁸ вентилів, нам потрібно більше 1 Гбайт лише для того, щоб зберігати їх. Для заданої схеми, яка може бути набагато меншою за максимальну, MARLIN обрізає ключ, так що працювати з ним набагато простіше і швидше. Налаштування також залежить від параметра безпеки λ , але в нашому аналізі ми вважатимемо його постійним. Отже, ми маємо setup( λ, N ) → pp(pk, vk).

Доказуючий генерує поліном

і фіксує його , обчислюючи в точці ? Ми не знаємо α , лише скалярні кратні елементи групи ступенів α

Це проблема мульти-скалярного множення ( MSM ). Ми, що поліноміальні зобов'язання відповідає одному груповому елементу еліптичної кривої.

Ми також могли б використовувати дерево Меркла, щоб зафіксувати багаточлен. Проблема дерева Меркла полягає в тому, що розмір дерева залежить від рівня полінома. У випадку KZG зобов'язання - це лише один елемент групи, який не залежить від розміру. Крім того, коли ми хочемо обчислити багаточлен у доказі, нам потрібно відправити всі коефіцієнти у відкритому вигляді (який показує багаточлен), при цьому перевіряльнику доводиться виконувати лінійну роботу над розміром багаточлена. З іншого боку, ми побачимо, що KZG в основному приховує багаточлен (якщо тільки запитів небагато), і перевірка залежить від ступеня многочлена. Крім того, KZG допускає пакетні докази: якщо ми маємо кілька зобов'язань cm1, cm2, …, cmk, ми можемо згенерувати лише одне доказ, показує, що це зобов'язання дійсні.

Як тільки многочлен зафіксований, перевіряючий (в інтерактивній схемі) може відправляти випадкові точки rk доказує, і останній видає многочлен, обчислений rk, P(rk) . Щоб зробити його неінтерактивним, ми використовуємо перетворення Фіата-Шаміра, де випадкові виклики генеруватимуться з криптографічної хеш-функції.

Припустимо, що доводить хоче переконати перевіряючого у цьому, що P(u) = v . Він може перетворити цю рівність на поліном, g(x) = P(x) − v , який має рішення в x = u . Це означає, що g(x) ділиться на x − u , що ми можемо записати як g(x) = P(x)−v = Q(x)(x−u ), де Q є приватним многочленом. Доказуючий може зафіксувати Q(x) , виконавши те саме, що раніше

- Ще один MSM. Доказ π містить елемент групи, який має постійний розмір! Доказ продемонструє, що P(u) = v і P — це дійсно багаточлен ступеня не більше, ніж d , і фіксація P — це cm( P ).

Перевіряючий приймає доказ, якщо (α−u)cm(Q) = cm(P) − vg . Але проблема в тому, що ми не знаємо α . Ось де спаровування приходить на допомогу, і нам знадобляться лише елементи h0 і h1 , щоб мати можливість провести обчислення. Грубо кажучи, спарювання еліптичних кривих – це функція

яка приймає два елементи, P з G1 and Q з G2 і виробляє елемент R з Gt . Всі групи мають однаковий порядок r і відповідають групам зручних для спарювання еліптичних кривих. У разі MARLIN використовується крива BLS 12-377 . Спарювання задовольняє:

де g and g2 - генератори з груп G1 і G2 (і P = pg і Q = qg2 ). Форма рівняння перевірки з точки зору спарювання:

Перевірка проводиться в Gt . Нам потрібно лише дізнатися αg2 із довіреної настройки.

Тепер, як ми можемо бути впевнені, що якщо ми оцінили багаточлени в одній точці і вони збігаються, то дуже ймовірно, що аргумент вірний? Відповідь лежить у лемі Шварца-Зіппеля (ми сформулюємо її для кінцевих полів ): для полінома P ступеня d у кінцевому полі порядку p ймовірність, що поліном дорівнює нулю в точці r , обраної випадковим чином, дорівнює

Враховуючи, що максимальний розмір схеми (який визначає максимальний порядок полінома) дорівнює приблизно 2²⁶ ≈ 10⁸, а розмір поля більше ніж 2²⁵⁶, ця ймовірність дорівнює приблизно 2^(-230) ≈ 10^(-70). Якщо P1 і P2 збігаються в одній точці r ми можемо скласти поліном P(x) = P1(x )− P2(x) (оскільки складення поліномів замкнуте) і P(r) = 0 . Враховуючи, наскільки малоймовірно випадкове потрапляння в нуль, ми можемо бути цілком впевнені, що P(x) є нульовим поліном.

Висновок

zk-SNARK почали привертати увагу завдяки їхньому використанню при розробці повністю приватних додатків. Вони надають короткі докази, що певне обчислення було виконано правильно, не розкриваючи конфіденційної інформації. Існує безліч можливих конструкцій, заснованих на імовірнісних доказах та схемі зобов'язань. Залежно від різних варіантів можливі ефективніші версії, які визначають тип обчислень (машинні чи схемні обчислення). Ми вивчили схему зобов'язань KZG, яка демонструє ідею, що лежить в основі таких систем, як MARLIN та Plonk, та обчислення, які нам необхідно виконати для генерації та перевірки доказів.

Оригінал статті: https://www.entropy1729.com/the-hunting-of-the-zk-snark/