Контур отложения керна

Схема основного депозита

Схема основного депозита — это то, с чем взаимодействует большинство пользователей, доказывая, что пользователь создал обязательство, представляющее депозит определенного номинала актива, что он еще не забрал этот актив и что он знает секрет, который он предоставил при создании первоначальное обязательство.

Внесение депозита

Депозит на Tornado.cash — это очень простая операция, которая фактически не требует каких-либо доказательств ZK. По крайней мере, пока. Чтобы внести депозит, вы вызываете depositметод Контракт Торнадо Например, предоставив Обязательство Педерсена вместе с номиналом актива, который вы вносите. Это обязательство вставляется в специализированное дерево Меркла, где структура дерева Меркла выравнивается по эллиптической кривой, связанной с простым числом в порядке эллиптической кривой BN128, а метки дерева вычисляются с использованием хеширования MiMC.

Схема обязательств

Когда вы берете на себя «обязательство» в контексте криптографии, вы берете секретное значение — часто большое и случайное — и пропускаете его через некоторую криптографическую функцию (например, хеш-функцию), а затем раскрываете результат. Позже, когда вам нужно будет выполнить обязательство, вы докажете, что знаете исходное секретное значение.

Педерсен Хэш

Хэш Педерсена — это чрезвычайно специализированная функция хеширования, которая особенно хорошо подходит для использования в приложениях, использующих схемы проверки с нулевым разглашением. В то время как другие функции хеширования, такие как SHA-256, предназначены для проявления таких свойств, как создание очень разных выходных данных для даже немного разных входных данных (лавинный эффект), хеширование Педерсена вместо этого отдает приоритет способности чрезвычайно эффективно вычислять хэш в схемах с нулевым разглашением.

Хеширование сообщения с помощью Педерсена сжимает биты сообщения до точки на эллиптической кривой, называемой Baby Jubjub. Baby Jubjub имеет порядок эллиптической кривой BN128, которая поддерживается предварительно скомпилированными операциями в сети Ethereum, которые были добавлены в EIP-196. Это означает, что операции, использующие кривую Baby Jubjub, такие как хэширование Педерсена, отличаются высокой эффективностью использования газа.

Когда вы вычисляете хэш Педерсена сообщения, полученную точку на его эллиптической кривой очень удобно проверить, но невозможно вернуть обратно в исходное сообщение.

Обязательства Торнадо

Чтобы сгенерировать обязательство по депозиту Tornado.cash, вы сначала генерируете два больших случайных целых числа, каждое длиной 31 байт. Первое значение — это нуллификатор, который вы позже раскроете, чтобы снять свой депозит, а второе — это секрет, который обеспечивает конфиденциальную связь между вашим депозитом и снятием средств.

Прообраз вашей депозитной банкноты представляет собой объединение этих двух значений ( nullifier+ secret), в результате чего получается сообщение длиной 62 байта. Это сообщение хешируется по Педерсену, в результате чего выходные данные представляют собой элемент эллиптической кривой Baby Jubjub, закодированный как 32-байтовое целое число с прямым порядком байтов.Если вы хотите увидеть это в форме кода, вы можете сослаться на функция депозита Tornado-Cli.

Дерево МиМК Меркла

Контракт Tornado представляет собой специализированное дерево Меркла, которое маркирует свои узлы с помощью хэшей MiMC.Для тех, кто не знаком с деревьями Меркла, это двоичные деревья, в которых каждый нелистовой узел помечен хешем меток его дочерних узлов, а листовые узлы помечены хешем их данных. Обычно деревья Меркла используют одностороннюю криптографическую функцию хеширования, например SHA-2, но в данном случае мы используем MiMC, который имеет некоторые полезные свойства.

Одним из полезных свойств MiMC является то, что он хорошо подходит для работы с простыми полями, что важно для нас, поскольку доказательства с нулевым разглашением фундаментально основаны на простых полях, а хеши Педерсена — это точки внутри простого поля, определяемого эллиптическим алгоритмом Baby Jubjub. Кривая, которая, в свою очередь, находится в пределах порядка кривой BN128, изначально поддерживаемой в Ethereum. Поскольку доказательства с нулевым разглашением являются операционно дорогостоящими, а каждая операция в транзакции Ethereum имеет соответствующую стоимость газа, конкретные типы операций, которые мы разрабатываем, должны быть максимально экономичными.

Другие особенно полезные свойства MiMC заключаются в том, что он не поддается распараллеливанию, его сложно вычислить, но легко проверить. Эти свойства повышают безопасность контракта, делая вычислительно невозможным вычисление поддельного «обязательства», которое имеет конфликтующий путь в дереве Меркла.

Нулевые узлы

Во время инициализации дерева Меркла Торнадо предварительно выделяется один путь, охватывающий высоту дерева, начиная с узла «нулевого листа» с меткой keccak256("tornado") % FIELD_SIZE.

Каждый последующий нелистовой узел по направлению к корню затем помечается так, как если бы вся нижняя часть дерева была заполнена тем же самым листовым узлом.

Цель этих «нулевых узлов» — гарантировать, что все пути в дереве Меркла недействительны до тех пор, пока они не завершатся действительным обязательством.

Вставка обязательства

Когда вы вставляете обязательство в дерево Меркла контракта Tornado, вы заменяете «нулевой лист» новым листом, метка которого представляет собой хеш MiMC вашего обязательства Педерсена, а затем перемещаетесь вверх по дереву, обновляя каждый последующий родительский узел новой меткой. на основе обновлений этикетки, представленных ниже на вашем новом листе.

Обязательства вставляются в дерево слева направо, причем каждые две вставки обязательств заполняют «поддерево». Каждая вставка увеличивает «индекс» дерева, определяя, будет ли следующее обязательство вставлено с левой или с правой стороны записи ее пути Меркла.

Как только ваш депозит обновит дерево, метка самого верхнего узла становится новым «корнем» дерева и добавляется в прокручивающуюся историю, содержащую метки последних 100 корней, для последующего использования при обработке транзакций вывода средств.Депозитные контракты Tornado.cash развертываются с 20 «уровнями», каждый из которых увеличивает количество потенциальных листьев в степени 2. Это означает, что дерево Меркла контракта поддерживает до 2 ^ 20 листьев, что позволяет разместить до 1 048 576 депозитов. должно быть включено в контракт до того, как его потребуется заменить.

Причина такого, казалось бы, небольшого количества уровней заключается в том, что каждый депозит должен выполнять столько обновлений дерева, сколько существует уровней. Дерево с большим количеством уровней потребует больше газа на депозит, а также, соответственно, больший размер доказательства при снятии банкнот.

Вывод средств

Внеся депозит, у вас теперь есть набор правдивых утверждений, на основе которых вы можете создать доказательства. Вообще говоря, доказательства с нулевым разглашением привязаны к некоторым значениям, известным как доказывающему, так и проверяющему, связь с которыми будет доказана с набором значений, известных только доказывающему.

Верификатор схемы может подтвердить, что проверяющий использовал известные значения и что вычисленное им доказательство удовлетворяет ограничениям, наложенным схемой.

Входные данные для подтверждения вывода средств

В случае депозитов Tornado.cash и проверяющий (лицо, отправляющее транзакцию вывода средств), и проверяющий (метод вывода депозитного контракта) знают недавний корень Меркла. Доказывающая также предоставляет набор других общедоступных данных, которые они использовали для создания своего доказательства.

Общий набор общедоступных данных для доказательства вывода средств:

1. Недавний корень Меркла

2. Хэш Педерсена компонента обнуления из их депозитного обязательства.

3. Адрес получателя вывода средств

4. Адрес выбранного ретранслятора (или собственный адрес)

5. Комиссия, которую они платят ретранслятору (или ноль)

6. Возврат, который они платят ретранслятору (или ноль)

Дополнительными частными входами для подтверждения вывода являются:

1. Обнуляющий компонент депозитного обязательства.

2. Секретный компонент депозитного обязательства.

3. Набор меток узлов, существующих на пути между корневыми и листовыми узлами дерева Меркла.

4. Массив 0/1значений, указывающий, находится ли каждый указанный элемент пути слева или справа от родительского узла.

Доказанные утверждения

Было бы легко упустить из виду новую умную часть знаний, которую мы создали, когда создавали и вставляли наше обязательство в дерево Меркла. Вы можете подумать, что для вывода средств нам просто нужно доказать, что мы знаем компоненты обязательства Педерсена и что дерево Меркла — это всего лишь эффективный способ хранения этих хэшей обязательств.

Особенностью этой конструкции является то, что она позволяет нам доказать не только то, что мы знаем компоненты депонированного обязательства, но, скорее, позволяет нам просто доказать, что мы знаем путь к обязательству внутри дерева и как туда добраться, начиная с с прообразом обязательства.

Если бы нам нужно было только доказать, что мы знаем прообраз депонированного хеша, мы бы рискнули раскрыть, какое обязательство принадлежит нам. Вместо этого мы не раскрываем прообраз обязательства, а просто доказываем, что у нас есть знание прообраза обязательства внутри дерева. Какое обязательство является нашим, остается совершенно неразличимым на стороне выхода из окружного протокола.

Вычисление свидетеля

Проверка хэша обнулителя

Чтобы вычислить свидетель для доказательства вывода средств, наша схема сначала принимает входные данные о фиксации частного депозита ( nullifier+ secret) и пропускает их через компонент схемы, который одновременно вычисляет хэш Педерсена полного сообщения о фиксации и хэш Педерсена обнулителя. один. Затем схема сравнивает полученный хеш-нуллификатор с тем, который вы предоставили в качестве общедоступных входных данных, и подтверждает их равенство.

Это доказывает, что хэш-нуллификатор, который вы предоставили публично, на самом деле является компонентом вашего первоначального обязательства.

Проверка дерева Меркла

Затем схема принимает вычисленный ею хэш-фиксатор, корень Меркла, который вы указали публично, а также элементы пути и селекторы влево/вправо, которые вы указали конфиденциально, в качестве входных данных для компонента, который проверяет ваше утверждение пути к дереву Меркла.

Средство проверки дерева Меркла начинается с нижней части пути, вводя хэш вашего обязательства и первый элемент предложенного вами пути в мультиплексор. Мультиплексор принимает третий вход, который является элементом предоставленных вами направлений влево/вправо. Компонент Muxer использует эти указания для информирования компонента хеширования MiMC о порядке его входных данных. Если указанное направление равно 0, то предоставленный элемент пути находится слева, а хеш вашего обязательства — справа. Если направление равно 1, то порядок обратный.

Хэшер MiMC выводит результирующий хеш, и программа проверки дерева Меркла переходит на следующий уровень. Он повторяет последний процесс, за исключением того, что на этот раз вместо использования хеша вашего обязательства он использует хэш последнего уровня. Он продолжает проходить через каждый уровень предложенного пути, пока не получит окончательный результат хеширования.

Средство проверки дерева Меркла сравнивает вычисленный им хеш с предоставленными вами общедоступными корневыми входными данными Меркла и подтверждает их равенство.

Это доказывает, что ваше обязательство существует на каком-то пути ниже указанного корня Меркла.

Дополнительная проверка параметров вывода

Прежде чем закончить, схема берет каждый из оставшихся четырех общедоступных входов и преобразует их в общедоступный выход. Хотя это не является строго необходимым, это создает набор ограничений в вашем доказательстве, которые гарантируют, что параметры вашей транзакции не могут быть подделаны до обработки транзакции вывода средств. Если какой-либо из этих параметров изменится, ваше доказательство перестанет быть действительным.

Вычисление доказательства

Теперь, когда у нас есть свидетель для нашего доказательства, мы берем эти засвидетельствованные значения состояния и вводим их в R1CS, соответствующую схеме вывода, и запускаем над ними средство доказательства. Из доказывающего появляются два артефакта-доказательства. Первый — это само доказательство в соответствии с используемым нами протоколом SNARK, а второй — набор общедоступных входных и выходных данных, соответствующих этому доказательству.

Завершение транзакции вывода средств

Теперь, когда доказательство вывода средств создано, вы передаете это доказательство вместе с его общедоступными входными данными в метод withdrawдепозитного контракта. Этот метод проверяет, что:

1. Указанная ретрансляционная комиссия не превышает номинала выводимого актива.

2. Предоставленный хеш-нуллификатор ранее не был потрачен.

3. Предоставленный корень Меркла известен с использованием 100-корневой исторической записи.

4. Предоставленное доказательство действительно.

Одним из артефактов, развернутых в качестве зависимости депозитного контракта, является контракт Solidity, который генерируется с использованием проверочного ключа схемы вывода средств в качестве входных данных. Этот контракт Verifier представляет собой оптимизированный верификатор доказательства с единственной функцией публичного просмотра, которая принимает доказательство и массив из шести общедоступных входных данных в качестве uint256значений.

Эта функция возвращает значение TRUE, если доказательство действительно в соответствии с общедоступными данными.

Если вышеуказанные предварительные условия соблюдены, предоставленный хеш-нуллификатор вставляется в набор потраченных нуллификаторов, а затем стоимость депозита распределяется между получателем и ретранслятором в соответствии с указанными параметрами комиссии.