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:
Trusted Setup для кожної схеми - Виконується один раз для кожної схеми. Є специфічним для схеми, а секретну випадковість (Common Reference String) потрібно зберігати в таємниці та знищити.
Скомпрометований setup у цьому методі означає, що нечесний prover може доводити хибні твердження.
Trusted but Universal Setup - Trusted setup потрібно виконати лише один раз, після чого можна детерміновано попередньо обробляти багато різних схем.
Transparent Setup (No Trusted Setup)- Алгоритм попередньої обробки взагалі не використовує жодної секретної випадковості.
Типи конструкцій доказів 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?
Пов’язані сторінки
