Контур отложения керна
Основная схема депозита — это то, с чем взаимодействует большинство пользователей, доказывая, что пользователь создал обязательство, представляющее депозит некоторой соответствующей деноминации актива, что он еще не снял этот актив и что он знает секрет, который он предоставил при создании первоначального обязательства.
Внесение депозита
Внесение депозита в Tornado.cash — очень простая операция, которая на самом деле не требует никаких доказательств ZK. По крайней мере, пока. Чтобы внести депозит, вы вызываете метод deposit экземпляра контракта Tornado, предоставляя обязательство Педерсена вместе с деноминацией актива, который вы вносите. Это обязательство вставляется в специализированное дерево Меркла, где структура дерева Меркла выровнена с эллиптической кривой, связанной с простым числом в порядке эллиптической кривой BN128, а метки дерева вычисляются с использованием хеширования MiMC.
Схема обязательств
Когда вы принимаете «обязательство» в контексте криптографии, вы берете секретное значение — часто большое и случайное — и пропускаете его через некоторую криптографическую функцию (например, хеш-функцию), а затем раскрываете результат. Позже, когда вам нужно будет выполнить обязательство, вы доказываете, что знаете исходное секретное значение.
Хеш Педерсена
Хеш Педерсена — это чрезвычайно специализированная функция хеширования, которая особенно хорошо подходит для использования в приложениях, использующих схемы доказательства с нулевым разглашением. В то время как другие функции хеширования, такие как SHA-256, разработаны для демонстрации таких свойств, как создание очень разных выходов даже для немного разных входов (эффект лавины), хеширование Педерсена вместо этого отдает приоритет возможности вычислять хеш чрезвычайно эффективно в схемах с нулевым разглашением.
Хеширование сообщения с помощью Педерсена сжимает биты сообщения до точки вдоль эллиптической кривой, называемой Baby Jubjub. Baby Jubjub находится в порядке эллиптической кривой BN128, которая поддерживается предварительно скомпилированными операциями в сети Ethereum, которые были добавлены в EIP-196. Это означает, что операции, использующие кривую Baby Jubjub, такие как хеширование Педерсена, являются высокоэффективными с точки зрения расхода газа.
Когда вы вычисляете хэш Педерсена сообщения, результирующая точка вдоль его эллиптической кривой очень эффективна для проверки, но невозможна для возврата обратно в исходное сообщение.
Tornado Commitment
Чтобы сгенерировать обязательство для депозита Tornado.cash, вы сначала генерируете два больших случайных целых числа, каждое длиной 31 байт. Первое значение является аннулирующим, которое вы позже раскроете, чтобы снять свой депозит, а второе — секрет, который обеспечивает конфиденциальную связь между вашим депозитом и снятием.
Прообраз вашего депозитного примечания — это конкатенация этих двух значений (nullifier + secret), в результате чего получается сообщение длиной 62 байта. Это сообщение хэшируется Педерсеном, в результате чего получается выход, представляющий элемент эллиптической кривой Baby Jubjub, закодированный как 32-байтовое целое число с обратным порядком байтов.
Если вы хотите увидеть это в виде кода, вы можете сослаться на функцию депозита tornado-cli.
MiMC Merkle Tree
Контракт Tornado — это специализированное Merkle Tree, которое маркирует свои узлы с помощью хешей MiMC.
Для тех, кто не знаком с Merkle Tree, это бинарные деревья, в которых каждый нелистовой узел маркируется хешем меток своих дочерних узлов, а листовые узлы маркируются хешем своих данных. Обычно деревья Меркла используют одностороннюю криптографическую хеш-функцию, такую как SHA-2, но в этом случае мы используем MiMC, которая имеет некоторые полезные свойства.
Одним из полезных свойств MiMC является то, что он хорошо подходит для работы с простыми полями, что важно для нас, поскольку доказательства с нулевым разглашением в основе своей основаны на простых полях, а хэши Педерсена являются точками внутри простого поля, определяемого эллиптической кривой Baby Jubjub, которая, в свою очередь, находится в порядке кривой BN128, поддерживаемой изначально в Ethereum. Поскольку доказательства с нулевым разглашением являются операционно дорогими, а каждая операция в транзакции Ethereum имеет соответствующую стоимость газа, конкретные типы операций, которые мы проектируем, должны быть максимально эффективными с точки зрения газа.
Другие особенно полезные свойства MiMC заключаются в том, что он непараллелизуем и сложен в вычислениях, но прост в проверке. Эти свойства повышают безопасность контракта, делая вычислительно невозможным вычисление поддельного «обязательства», имеющего конфликтующий путь в дереве Меркла.
Нулевые узлы
Во время инициализации дерева Меркла Tornado один путь, охватывающий высоту дерева, предварительно выделяется, начиная с узла "нулевой лист" с меткой keccak256("tornado") % FIELD_SIZE. Каждый последующий не листовой узел по направлению к корню затем помечается так, как если бы вся нижняя часть дерева была заполнена тем же самым листовым узлом.
Цель этих "нулевых узлов" — гарантировать, что все пути в дереве Меркла недействительны, пока они не завершатся действительным обязательством.
Вставка обязательства
Когда вы вставляете обязательство в дерево Меркла контракта Tornado, вы заменяете "нулевой лист" новым листом, метка которого является хешем MiMC вашего обязательства Педерсена, а затем проходите вверх по дереву, обновляя каждый последующий родительский узел новой меткой на основе обновлений меток, которые ваш новый лист вводит ниже.
Обязательства вставляются слева направо в дереве, причем каждые две вставки обязательств заполняют "поддерево". Каждая вставка увеличивает "индекс" дерева, определяя, будет ли следующее обязательство вставлено слева или справа от записи в его путь Меркла.
После того, как ваш депозит обновит дерево, метка самого верхнего узла становится новым "корнем" дерева и добавляется в скользящую историю, содержащую метки последних 100 корней, для последующего использования при обработке транзакций вывода.
Контракты на депозит Tornado.cash развернуты с 20 «уровнями», каждый из которых увеличивает количество потенциальных листьев на степень 2. Это означает, что дерево Меркла контракта поддерживает до 2^20 листьев, что позволяет внести до 1 048 576 депозитов в контракт, прежде чем его потребуется заменить.
Причина этого, казалось бы, небольшого количества уровней заключается в том, что каждый депозит должен выполнить столько обновлений дерева, сколько есть уровней. Дерево с большим количеством уровней потребует больше газа на депозит, а также, соответственно, большие размеры доказательств при снятии банкнот.
Вывод средств
Сделав депозит, вы теперь имеете набор утверждений об истинности, на основе которых вы можете сгенерировать доказательство. В общем, доказательства с нулевым разглашением привязаны к некоторым значениям, известным как доказывающему, так и проверяющему, для которых будет доказана связь с набором значений, известным только доказывающему. Проверяющий схему может подтвердить, что доказывающий использовал известные значения, и что вычисленное им доказательство удовлетворяет ограничениям, налагаемым схемой.
Входы для доказательства снятия
В случае депозитов Tornado.cash доказывающий (лицо, отправляющее транзакцию снятия), и проверяющий (метод снятия депозитного контракта) оба знают недавний корень Меркла. Доказывающий также предоставляет набор других публичных входов, которые они использовали для генерации своего доказательства.
Общий набор публичных входов для доказательства снятия:
Недавний корень Меркла
Хеш Педерсена компонента аннулирования из их депозитного обязательства
Адрес получателя их вывода
Адрес ретранслятора, которого они выбрали (или их собственный адрес)
Плата, которую они платят ретранслятору (или ноль)
Возврат, который они платят ретранслятору (или ноль)
Дополнительные частные входы для доказательства вывода:
Компонент аннулирования из их депозитного обязательства
Секретный компонент из их депозитного обязательства
Набор меток узлов, которые существуют в пути между корневым и конечными узлами дерева Меркла
Массив значений
0/1, указывающий, находится ли каждый указанный элемент пути слева или справа от своего родительского узла
Доказанные утверждения
Было бы легко упустить из виду новое умное знание, которое мы создали, когда построили и вставили наше обязательство в дерево Меркла. Вы можете подумать, что для вывода средств мы просто докажем, что знаем компоненты обязательства Педерсена, и что дерево Меркла — это просто эффективный способ хранения этих хешей обязательств.
Особенность этой конструкции в том, что она позволяет нам доказать не только то, что мы знаем компоненты депонированного обязательства, но и то, что мы просто знаем путь к обязательству в дереве и как туда попасть, начиная с прообраза обязательства.
Если бы мы только доказали, что знаем прообраз депонированного хеша, мы бы рискнули раскрыть, какое обязательство наше. Вместо этого мы не раскрываем прообраз обязательства, а просто доказываем, что у нас есть знание прообраза обязательства в дереве. Какое обязательство наше, остается совершенно неразличимым на стороне снятия протокола цепи.
Вычисление свидетеля
Проверка хэша нулевого устройства
Чтобы вычислить свидетеля для доказательства снятия, наша цепь сначала берет входные данные частного депозитного обязательства (nullifier + secret) и пропускает их через компонент цепи, который одновременно вычисляет хэш Педерсена полного сообщения о обязательстве и хэш Педерсена только нулевого устройства. Затем цепь сравнивает полученный хэш нулевого устройства с тем, который вы предоставили в качестве открытого входа, и подтверждает их равенство.
Это доказывает, что хэш обнулителя, который вы предоставили публично, на самом деле является компонентом вашего исходного обязательства.
Проверка дерева Меркла
Далее схема принимает вычисленный ею хэш обязательства, корень Меркла, который вы указали публично, а также элементы пути и селекторы левого/правого, которые вы указали конфиденциально, в качестве входных данных для компонента, который проверяет ваше утверждение пути дерева Меркла.
Проверка дерева Меркла начинается с нижней части пути, вводя ваш хэш обязательства и первый элемент вашего предлагаемого пути в Muxer. Muxer принимает третий входной сигнал, который является элементом из предоставленных вами направлений левого/правого направления. Компонент Muxer использует эти направления для информирования компонента хеширования MiMC о порядке его входных данных. Если предоставленное направление равно 0, то предоставленный элемент пути находится слева, а ваш хэш обязательства находится справа. Если направление равно 1, то порядок меняется на обратный.
MiMC hasher выводит полученный хэш, а Merkle Tree Checker переходит на следующий уровень. Он повторяет последний процесс, но на этот раз вместо использования вашего хэша обязательства он использует хэш последнего уровня. Он продолжает проходить через каждый уровень предлагаемого пути, пока не получит окончательный выходной хэш.
Merkle Tree Checker сравнивает вычисленный им хэш с предоставленным вами публичным корнем merkle и подтверждает их равенство.
Это доказывает, что ваше обязательство существует в некотором пути ниже указанного корня merkle.
Дополнительная проверка параметров снятия
Перед завершением схема берет каждый из оставшихся четырех публичных входов и преобразует их в публичный выход. Хотя это не является строго необходимым, она создает набор ограничений в вашем доказательстве, которые гарантируют, что параметры вашей транзакции не могут быть изменены до обработки вашей транзакции снятия. Если какой-либо из этих параметров изменится, ваше доказательство больше не будет действительным.
Вычисление доказательства
Теперь, когда у нас есть свидетель для нашего доказательства, мы берем эти засвидетельствованные значения состояния и вводим их в R1CS, соответствующий схеме снятия, и запускаем над ним доказывающий. Доказывающий выдает два артефакта доказательства. Первый — это само доказательство, согласно протоколу SNARK, который мы используем, а второй — набор публичных входов и выходов, соответствующих этому доказательству.
Завершение транзакции вывода
Теперь, когда доказательство вывода сгенерировано, вы предоставляете это доказательство вместе с его публичными входами методу withdraw депозитного контракта. Этот метод проверяет, что:
Указанная комиссия ретранслятора не превышает номинала актива, который снимается
Предоставленный хэш обнулителя не был потрачен ранее
Предоставленный корень Меркла известен с использованием исторической записи 100-корня
Предоставленное доказательство является действительным
Одним из артефактов, развернутых в качестве зависимости депозитного контракта, является контракт Solidity, который создается с использованием ключа доказательства схемы вывода в качестве входных данных. Этот контракт верификатора представляет собой оптимизированный верификатор доказательств с одной публичной функцией просмотра, которая принимает доказательство и массив из шести публичных входов как значения uint256.
Эта функция возвращает TRUE, если доказательство является действительным согласно публичным входам.
Если вышеуказанные предварительные условия выполнены, предоставленный хэш обнулителя вставляется в набор потраченных обнулителей, а затем стоимость депозита распределяется между получателем и ретранслятором в соответствии с указанными параметрами комиссии.
Last updated