Loading...
Серія: Zcash from First Principles . Стаття 5 . Докази з нульовим розголошенням Аудиторія: новачки. Ми спираємося на кожну попередню статтю (скінченні поля, криві, комітменти, дерева Меркла), але кожну ідею згадуємо знову там, де вона потрібна. Що ви зрозумієте після прочитання: інтуїтивне й коректне розуміння того, що таке доказ з нульовим розголошенням, які три гарантії він надає, як доводяться довільні твердження та що лежить в основі Zcash Sapling і Orchard.
Саме до цієї статті й вела вся серія. Починаючи зі Статті 0, ми постійно казали, що платіж перевіряється «за завісою», доводиться правильним, нічого не розкриваючи. Доказ з нульовим розголошенням і є цією завісою. Саме він нарешті розв’язує парадокс, з якого ми почали: як публіка може перевірити транзакцію, яку їй не дозволено бачити?
Згадайте суперечність у самій основі Zcash:
На перший погляд це взаємовиключні речі. Перевірка, здається, вимагає побачити. Приватність забороняє побачити. Якщо неможливо примирити ці дві вимоги, то неможливо мати приватні гроші, яким усі довіряють.
Доказ з нульовим розголошенням (ZKP) і є цим примиренням. Він дозволяє доводителю переконати перевіряльника, що твердження істинне, не розкриваючи нічого, окрім самого факту його істинності. Жодних сум. Жодних особистостей. Жодної note. Лише: «усе тут відповідає правилам». Спершу сформуємо інтуїцію, ще до будь-якого технічного механізму.
Довести, що ви знаєте пароль, не називаючи його. Сайт міг би перевірити, що ви знаєте свій пароль, спостерігаючи, як ви відкриваєте щось, що можна відкрити лише цим паролем, і ніколи не бачачи сам пароль. Ви доводите знання без розкриття.
Друг із дальтонізмом і дві кульки. У вас є червона й зелена кулька, які для вашого друга-дальтоніка виглядають однаково. Ви хочете переконати його, що вони різних кольорів, не кажучи, яка з них яка. Він ховає обидві за спину, може поміняти їх місцями, а потім показує одну. Ви кажете, чи він їх поміняв. Якщо кульки справді різні, ви завжди матимете рацію. Якщо вони однакові, ви просто вгадуватимете й матимете рацію лише в половині випадків. Після 20 раундів ваша безпомилкова серія переконає його, що вони різні, хоча він так і не дізнається, яка кулька червона. Він переконується у факті, не дізнаючись нічого більше. Це і є нульове розголошення в мініатюрі.
Печера. Кільцеподібна печера має ззаду чарівні двері, які відкриваються лише секретним словом. Ви стверджуєте, що знаєте це слово. Щоб довести це, не розкриваючи його, перевіряльник чекає зовні, поки ви заходите всередину й випадково обираєте лівий або правий прохід. Потім перевіряльник кричить, з якого боку хоче, щоб ви вийшли. Якщо ви справді знаєте слово, то завжди можете це зробити (за потреби ви відкриєте двері, щоб перейти на інший бік). Якщо ви блефуєте, то можете вийти з правильного боку лише випадково, 50/50 у кожному раунді. Повторіть це 20 разів — і шанси блефуна протриматися будуть меншими ніж один на мільйон.
Ця історія з печерою непомітно демонструє три гарантії, яким має відповідати кожен доказ з нульовим розголошенням.
| Гарантія | У історії з печерою | У Zcash |
|---|---|---|
| Повнота | Якщо ви знаєте слово, ви завжди виходите з правильного боку | Валідна транзакція завжди створює доказ, який буде прийнято |
| Надійність | Блефуна викриють із переважною ймовірністю | Шахрайська транзакція (підроблені гроші, подвійне витрачання) не може створити доказ, який буде прийнято |
| Нульове розголошення | Перевіряльник ніколи не чує секретного слова | Мережа ніколи не дізнається сум, адрес або того, яка саме note використовується |
Якщо хоча б одна з них не виконується, система руйнується: без повноти чесних користувачів відхилятимуть; без надійності підробники друкуватимуть гроші; без нульового розголошення приватність зникне.
Печера доводить один симпатичний факт. Але Zcash потрібно довести складне твердження: «Я знаю невитрачену note в дереві, я маю право її витратити, її nullifier обчислено правильно, а мої входи дорівнюють моїм виходам». Як перейти від кульок і печер до цього?
Містком служить ідея, яка поєднує всю цю серію:
Будь-яке твердження, яке можна перевірити за допомогою обчислення, можна переписати як арифметичну схему: мережу додавань і множень над скінченним полем (Стаття 1).
Думайте про схему як про список арифметичних обмежень, які усі виконуються лише тоді, коли твердження істинне. Приватні входи, що роблять перевірку успішною — ваша note, ваш ключ, шлях Меркла — називаються witness.
Ось чому ми присвятили Статтю 1 скінченним полям, а Статтю 3 — дружнім до ZK хешам: схема «розмовляє» арифметикою поля, тож кожну операцію всередині твердження (включно з хешуванням і підйомом деревом Меркла зі Статті 4) треба виразити саме так. Чим дешевше виражається кожна операція, тим меншим і швидшим є доказ.
Печера вимагала багато раундів обміну. Для блокчейна це непрактично: доказ потрібно опублікувати один раз, а перевіряти його має кожен і назавжди. Дві модифікації це виправляють.
Неінтерактивність (ідея Fiat-Shamir). Замість живого перевіряльника, який вигукує випадкові виклики, доводитель сам генерує ці «випадкові виклики», хешуючи вже побудовану частину свого доказу. Оскільки хороший хеш непередбачуваний (Стаття 3), доводитель не може підігнати виклики собі на користь. Балакуча розмова стискається до одного самодостатнього доказу, який будь-хто може перевірити пізніше без жодної взаємодії.
Стислість. Найкращі системи роблять доказ крихітним і швидким для перевірки, незалежно від того, наскільки велике саме твердження. Ось це і є по-справжньому вражаючою частиною.
Доказ Groth16 (система, яку використовує Sapling) має розмір приблизно 192 байти й перевіряється за мілісекунди, незалежно від того, мале чи величезне твердження він доводить. Кілька сотень байтів можуть засвідчити обчислення, що включає багато тисяч обмежень.
Об’єднавши це, ви отримаєте акронім, який бачитимете всюди:
zk-SNARK = zero-knowledge Succinct Non-interactive ARgument of Knowledge. Нульове розголошення (нічого не відкриває), стислість (малий і швидкий), неінтерактивність (одноразовий), аргумент знання (доводитель справді знає валідний witness).
Безкоштовних обідів не буває. Багатьом SNARK потрібне одноразове setup, яке створює публічні параметри для схеми. Під час цього setup як побічний продукт утворюється секретна випадковість, і цей секрет треба знищити. Якщо хтось його збереже, він зможе підробляти докази, тобто підробляти гроші (хоча, що важливо, він усе одно не зможе зламати приватність).
Цей залишковий секрет називають toxic waste. Щоб безпечно його знищити, Zcash проводив складні багатосторонні церемонії, у яких багато незалежних учасників додавали власну випадковість; якщо хоча б один із них чесно знищив свою частину, toxic waste уже неможливо відновити.
Новіші системи взагалі усувають цю вимогу, і це одна з головних причин, чому Zcash з часом еволюціонував у своїй системі доказів.
| Дизайн | Система доказів | Trusted setup? | Побудовано на |
|---|---|---|---|
| Sprout (найперший) | ранній zk-SNARK | Так | оригінальна церемонія |
| Sapling | Groth16 | Так (багатостороння церемонія "Powers of Tau" + церемонія Sapling) | BLS12-381 (Стаття 2) |
| Orchard (поточний) | Halo 2 | Без trusted setup | Pallas / Vesta (Стаття 2) |
Шлях від Sprout до Sapling, а потім до Orchard — це значною мірою історія про те, як докази ставали меншими, швидшими й позбавлялися trusted setup. Halo 2, який використовує Orchard, узагалі не потребує церемонії та побудований для підтримки рекурсії (доказів, які перевіряють інші докази), тому Orchard використовує цикл кривих Pallas/Vesta зі Статті 2: кожна крива налаштована на перевірку доказів, записаних над іншою.
Це замикає найбільшу петлю зі Статті 0. Магія «за завісою» — це zk-SNARK: він доводить, що ваша транзакція задовольняє арифметичну схему, яка кодує всі правила, не розкриваючи нічого, окрім одного біта: «валідно».
Докази з нульовим розголошенням — це глибока галузь, і ми навмисно залишилися на рівні інтуїції. Ми не визначали точні ймовірнісні межі надійності, точну форму арифметичної схеми (R1CS, PLONKish тощо), не розглядали, як поліноми й комітменти перетворюють схему на короткий доказ, а також реальні внутрішні механізми Groth16 і Halo 2. Печера — це інтерактивний доказ; виробничі системи є неінтерактивними й набагато складнішими. Але все це не змінює суті: довести, що схему задовольняє секретний witness — повністю, надійно й нічого не розкриваючи. Увесь цей механізм заслуговує на окрему серію.
| Термін | Просте значення |
|---|---|
| Zero-knowledge proof | Переконати когось, що твердження істинне, не розкриваючи нічого більше |
| Prover / Verifier | Той, хто створює доказ / той, хто його перевіряє |
| Completeness | Істинні твердження завжди приймаються (від чесного доводителя) |
| Soundness | Хибні твердження відхиляються (шахраї не можуть виграти, хіба що випадково) |
| Witness | Секретні входи, які роблять твердження істинним |
| Arithmetic circuit | Твердження, переписане як додавання й множення над скінченним полем |
| Non-interactive (Fiat-Shamir) | Одноразовий доказ, який не потребує живого обміну репліками |
| Succinct | Доказ малий і швидкий для перевірки незалежно від розміру твердження |
| zk-SNARK | Zero-knowledge Succinct Non-interactive ARgument of Knowledge |
| Trusted setup / toxic waste |
Якщо доказ нічого не розкриває, то як його перевірка взагалі щось означає? Тому що математика влаштована так, що прохідний доказ може створити лише справжній, валідний witness. Сам факт успішної перевірки і є доказом — без жодного розкриття.
Чи може хтось підробити доказ? Надійність робить це практично неможливим. Єдиний виняток — SNARK, у якого зберегли toxic waste від trusted setup; саме тому церемонії його знищення такі важливі.
Чи витече мої приватні дані, якщо trusted setup буде зламано? Ні. Це дозволило б зловмиснику підробляти нові гроші, але не розкрило б суми, адреси чи notes. Приватність і надійність — це окремі гарантії.
Чому Zcash з часом змінював системи доказів? Щоб отримати менші й швидші докази, а з Halo 2 — повністю прибрати trusted setup і додати рекурсію.
У печері чому так важливо, щоб перевіряльник обирав бік виходу після того, як доводитель уже зайшов усередину, а не оголошував його наперед? (Відповідь нижче.)
Якби перевіряльник спершу оголошував бік, блефун, який не знає слова, міг би просто одразу зайти з цього боку й спокійно вийти назад, так і не потребуючи дверей. Вибір після того, як доводитель уже зафіксувався на проході, змушує блефуна покладатися на удачу (50/50 у кожному раунді), і саме це робить багаторазові раунди переконливими. Такий порядок — «спершу зафіксуватися, потім отримати виклик» — це саме те, що зберігає Fiat-Shamir, виводячи виклик із хешу вже зафіксованого доказу доводителя.
Стаття 6 . Shielded protocol від початку до кінця: фінал. Ми візьмемо кожен елемент — notes, commitments, дерево комітментів note, nullifiers, баланс вартості та доказ з нульовим розголошенням — і зберемо повну shielded-транзакцію Zcash, замикаючи абсолютно всі петлі, відкриті ще в Статті 0.
Частина серії Zcash from First Principles для ZecHub. Ліцензія CC BY-SA 4.0.
| Одноразове генерування параметрів, чий залишковий секрет має бути знищений |