Loading...
Серия: Zcash from First Principles . Статья 5 . Доказательства с нулевым разглашением Аудитория: новички. Мы опираемся на все предыдущие статьи (конечные поля, кривые, коммитменты, деревья Меркла), но каждую идею будем напоминать по мере необходимости. Что вы поймёте после прочтения: интуитивное и корректное понимание того, что такое доказательство с нулевым разглашением, какие три гарантии оно даёт, как доказываются произвольные утверждения и что лежит в основе Sapling и Orchard в Zcash.
Именно к этой статье вела вся серия. Начиная с Статьи 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. Нулевое разглашение (ничего не раскрывает), краткость (маленькое и быстрое), неинтерактивность (одноразовое), 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 |
Если доказательство ничего не раскрывает, как его проверка вообще может что-то значить? Потому что математика устроена так, что только настоящий, корректный witness может породить проходящее проверку доказательство. Сам факт прохождения проверки и есть свидетельство, никакого раскрытия не требуется.
Можно ли подделать доказательство? Корректность делает это практически невозможным. Единственное исключение — SNARK, у которого был сохранён toxic waste из trusted setup; именно поэтому церемонии по его уничтожению так важны.
Если trusted setup скомпрометирован, утекут ли мои приватные данные? Нет. Это позволило бы злоумышленнику подделывать новые деньги, но не раскрывает суммы, адреса или notes. Приватность и корректность — это разные гарантии.
Почему Zcash со временем менял системы доказательств? Чтобы получить более маленькие и быстрые доказательства, а с Halo 2 — полностью убрать trusted setup и включить рекурсию.
Почему в истории с пещерой принципиально важно, чтобы проверяющий выбирал сторону выхода после того, как доказывающий уже вошёл внутрь, а не объявлял её заранее? (Ответ ниже.)
Если бы проверяющий сначала объявлял сторону, блефующий, который не знает секретного слова, мог бы просто сразу пойти в этот проход и спокойно выйти обратно, вообще не нуждаясь в двери. Выбор после того, как доказывающий зафиксировал свой проход, заставляет блефующего полагаться на удачу (50/50 в каждом раунде), и именно это делает повторяющиеся раунды убедительными. Такой порядок — «сначала зафиксируйся, потом получи вызов» — как раз и сохраняется в Fiat-Shamir, где вызов выводится из хеша уже зафиксированной части доказательства.
Статья 6 . Shielded-протокол от начала до конца: финал. Мы возьмём все элементы — notes, коммитменты, дерево коммитментов note, nullifiers, баланс стоимости и доказательство с нулевым разглашением — и соберём полную shielded-транзакцию Zcash, замкнув все без исключения круги, открытые ещё в Статье 0.
Часть серии Zcash from First Principles для ZecHub. Лицензия CC BY-SA 4.0.
| Одноразовая генерация параметров, при которой остаточный секрет должен быть уничтожен |