ZKP і zk-SNARKs
Коротко
- zk-SNARKs = короткі неінтерактивні аргументи знання з нульовим розголошенням
- Вони дозволяють одній стороні довести, що вона щось знає, не розкриваючи саму інформацію
- Zcash використовує zk-SNARKs, щоб довести, що транзакція є дійсною (правильні суми, невитрачені входи) без розкриття відправника, отримувача чи суми
- «Короткі» означає, що доказ є дуже малим і швидко перевіряється навіть для складних тверджень
- Пул Orchard використовує Halo 2, систему zk-SNARK, для якої не потрібне довірене налаштування
Що таке доказ?
Докази є основою всієї математики. Доказ — це твердження або теорема, яку ви намагаєтеся довести, та послідовність виведень, зроблених для того, щоб оголосити теорему доведеною. Наприклад, те, що сума всіх кутів трикутника дорівнює 180°, може бути незалежно перевірено будь-ким (verifier).
Докази
Prover ---> Робить твердження ---> Verifier обирає ---> Прийняти/Відхилити
(І prover, і verifier є алгоритмами)
У computer science термін для доказів, які можна ефективно перевіряти, — це NP proofs. Ці короткі докази можна перевірити за поліноміальний час. Загальна ідея така: "Існує розв’язок теореми, і його передають verifier для перевірки"
У NP-language мають виконуватися дві умови:
Повнота: істинні твердження будуть прийняті verifier (це дозволяє чесним prover успішно пройти перевірку)
Коректність: хибні твердження не матимуть доказів (для будь-якої стратегії нечесного prover він не зможе довести правильність хибного твердження).
Інтерактивні та ймовірнісні докази
Інтерактивність: Замість того щоб просто читати доказ, verifier взаємодіє з prover у кількох раундах обміну повідомленнями.
Випадковість: Запити verifier до prover є рандомізованими, і prover повинен уміти правильно відповісти на кожен із них.
Використовуючи разом інтерактивність і випадковість, можна довести твердження "сліпому" verifier за ймовірнісний поліноміальний час (PPT).
Чи можуть інтерактивні докази ефективно перевіряти більше, ніж NP proofs?
NP Proofs vs IP proofs:
| Твердження | NP | IP |
|---|
| NP | так | так |
| CO-NP | ні | так |
| #P | ні | так |
| PSPACE | ні | так |
NP - Існує розв’язок для твердження
CO-NP - Доведення того, що для твердження не існує розв’язків
#P - Підрахунок того, скільки розв’язків має твердження
PSPACE - Доведення чергування різних тверджень
Що таке Zero Knowledge?
Те, що verifier може обчислити після взаємодії, є ідентичним тому, що він міг би довести до неї. Взаємодія між prover і verifier у кількох раундах не збільшує обчислювальну потужність verifier.
Simulation Paradigm
Цей експеримент зустрічається в усій криптографії. Він представляє "Real View" і "Simulated View".
Real View: усі можливі історії взаємодії між Prover і Verifier (P,V)
Simulated View: verifier симулює всі можливі взаємодії між Prover і Verifier
Поліноміальний distinguisher намагається визначити, чи дивиться він на real view чи simulated view, і багаторазово запитує зразок з обох.
Кажуть, що ці два подання є "computationally indistinguishable", якщо для всіх алгоритмів/стратегій distinguisher, навіть після отримання поліноміальної кількості зразків з real або simulated view, ймовірність становить >1/2.
Zero-Knowledge Arguments of Knowledge
Інтерактивний протокол (P,V) є zero-knowledge, якщо існує simulator (алгоритм) такий, що для кожного verifier, який працює за probabilty polynomial-time (коли теорема правильна), розподіли ймовірностей, що визначають real і simulated view, є computationaly indistinguishable.
Інтерактивні протоколи корисні, коли є один verifier. Прикладом може бути податковий аудитор у застосунку zero-knowledge "proof of taxes".
Що таке SNARK?
Succinct Non-Interactive Argument of Knowledge
Широке визначення — це стислий доказ того, що твердження є істинним. Доказ має бути коротким і швидким для перевірки. У SNARKS одне повідомлення надсилається від Prover до Verifier. Після цього verifier може вирішити, прийняти його чи відхилити.
приклад твердження: "Я знаю повідомлення (m), таке що SHA256(m)=0"
У zk-SNARK доказ не розкриває нічого про повідомлення (m).
Поліноми: Суми членів, що містять константу (наприклад 1,2,3), змінні (наприклад x,y,z) та степені змінних (наприклад x², y³).
приклад: "3x² + 8x + 17"
Arithmetic Circuit: Модель для обчислення поліномів. У більш загальному сенсі її можна визначити як Directed Acyclic Graph, у кожному вузлі якого виконується арифметична операція. Circuit складається з воріт додавання, воріт множення та деяких константних воріт. Так само, як Boolean circuits передають біти по дротах, Arithmetic circuits передають цілі числа.
У цьому прикладі prover хоче переконати verifier, що він знає розв’язок для arithmetic circuit.
Commitments: Щоб зробити це, prover поміщає всі значення (приватні та публічні), пов’язані зі схемою, у commitment. Commitments приховують свої входи, використовуючи функцію, результат якої неможливо обернути.
Sha256 — один із прикладів хеш-функції, яку можна використовувати у схемі commitments.
Після того як prover фіксує значення, commitments надсилаються verifier (який упевнений, що не зможе розкрити жодне з початкових значень). Потім prover може показати verifier, що він знає кожне зі значень у вузлах графа.
Fiat-Shamir Transform
Щоб зробити протокол неінтерактивним, prover генерує випадковість (яка використовується для прихованого виклику) від імені verifier за допомогою криптографічної хеш-функції. Це відомо як random oracle. Потім prover може надіслати verifier одне повідомлення, яке той зможе перевірити на правильність.
Щоб сформувати SNARK, придатний для загальних схем, потрібні два елементи:
Функціональна схема commitments: дозволяє тому, хто комітить, зафіксувати поліном коротким рядком, який verifier може використати для підтвердження заявлених обчислень committed polynomial.
Polynomial interactive oracle: verifier просить prover (алгоритм) відкрити всі commitments у різних обраних ним точках за допомогою polynomial commitment scheme і перевіряє, чи виконується між ними тотожність.
Setup
Процедури setup допомагають verifier, підсумовуючи схему та виводячи публічні параметри.
Типи попередньої обробки setup:
Довірене налаштування для кожної схеми — виконується окремо для кожної схеми. Отриманий спільний еталонний рядок (CRS) містить публічні параметри, що використовуються довідниками та верифікаторами. Саме секретний проміжний матеріал налаштування («токсичні відходи»), а не CRS, потрібно зберігати в таємниці та знищити. ECC у своєму поясненні публічних параметрів розрізняє ці два поняття.
Якщо необхідний секретний матеріал налаштування збережено або відновлено, нечесний доказувач може бути здатний створювати докази хибних тверджень. У церемонії MPC безпека може залежати від того, чи дотримується принаймні один учасник протоколу та знищує свій секретний внесок.
Довірене, але універсальне налаштування — Одне довірене налаштування створює параметри, які можна використовувати для виведення ключів доведення та перевірки для кількох схем у межах підтримуваних обмежень розміру. Це все одно передбачає знищення секрету; універсальне не означає прозоре.
Прозоре налаштування (без довіреного налаштування) — Відкриті параметри можуть бути згенеровані без секретного лазівкового ключа налаштування, який хтось має бути зобов’язаний знищити. Це не означає, що для створення доказів не використовується випадковість або що система не має відкритих параметрів. Книга Halo 2 наводить приклад відкритих параметрів групи.
Типи конструкцій доказів SNARK:
Groth16: Потребує Trusted Setup, але має дуже короткі докази, які можна швидко перевірити.
Sonic/Marlin/PLONK: Universally Trusted Setup.
DARK/Halo/STARK: Не потребують довіреного налаштування, але створюють дещо довші докази або робота доводника може тривати довше.
SNARKS корисні, коли потрібні багато verifier, як-от у blockchain на кшталт Zcash або в zk-Rollup, такому як Aztec, щоб багатьом вузлам валідації не доводилося взаємодіяти в кількох раундах для кожного доказу.
Як zk-SNARK's реалізовані в Zcash?
Загалом zero-knowledge proofs — це інструмент для забезпечення чесної поведінки в протоколах без розкриття будь-якої інформації.
Zcash — це публічний blockchain, який забезпечує приватні транзакції. zk-SNARK's використовуються для доведення того, що приватна транзакція є дійсною відповідно до правил консенсусу мережі, не розкриваючи жодних інших деталей про транзакцію.
Відеопояснення - У цій лекції Ariel Gabizon описує дерево commitments нотаток Zcash, Blind Polynomial Evaluation та Homomorphically Hidden Challenges і те, як вони реалізовані в мережі.
Прочитайте книгу Halo2, щоб дізнатися більше.
Інші застосування Zero-Knowledge
zk-SNARKs дають кілька переваг у різноманітних застосуваннях. Розгляньмо кілька прикладів.
Масштабованість: Це досягається через "Outsourcing Computation". Немає суворої потреби в zero-knowledge, щоб L1 chain перевіряв роботу позаланцюгового сервісу. Транзакції не обов’язково є приватними у zk-EVM.
Перевага сервісу Rollup на основі доказів (zk-Rollup) полягає в обробці пакета з сотень/тисяч транзакцій, а L1 може перевірити стислий доказ того, що всі транзакції були оброблені правильно, масштабуючи пропускну здатність мережі за транзакціями у 100 або 1000 разів.
Інтероперабельність: Це досягається у zk-Bridge шляхом "блокування" активів у вихідному chain і доведення цільовому chain, що активи були заблоковані (proof of consensus).
Відповідність вимогам: Такі проєкти, як Espresso, можуть довести, що приватна транзакція відповідає місцевому банківському законодавству, не розкриваючи деталей транзакції.
Боротьба з дезінформацією: Серед кількох прикладів поза blockchain і cryptocurrency — використання генерації доказів для зображень, оброблених новинними та медіа-ресурсами, що дає змогу глядачам незалежно перевіряти джерело зображення та всі операції, виконані над ним. https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
Подальше вивчення:
Бібліографія Zero-Knowledge - a16z Crypto
zkSNARK's з Hanh Huynh Huu
Zcash: Halo 2 і SNARKs без Trusted Setups - Sean Bowe на Dystopia labs
Zero knowledge Proofs з Avi Wigderson - Numberphile
Інтерактивні Zero-Knowledge Proofs - стаття Chainlink
Лекція 1: Вступ та історія ZKP - zklearning.org
Просте пояснення Arithmetic Circuits - Medium
Scalability is Boring, Privacy is Dead: ZK-Proofs, What are They Good for?
Пов’язані сторінки