Как концептуально работает Tornado Cash, который "забанили" власти США
8 августа 2022 года Управление по контролю за иностранными активами Министерства финансов США (OFAC) наложило санкции на Tornado Cash, миксер криптовалюты, что вызвало шквал обсуждений в криптосреде. В этой статье разберем как концептуально работает криптомиксер Tornado Cash, что было понять, что есть в этой технологии, что против нее вводят санкции.
Одной из особенностей блокчейна является то, что ее реестр, содержащий все когда-либо имевшие место транзакции, виден глобально, то есть можно отслеживать средства по мере их перехода из рук в руки, а в некоторых случаях полностью деанонимизировать пользователей.
Tornado Cash — это сервис, который смешивает разные потоки потенциально идентифицируемой криптовалюты и таким образом не дает отследить переход криптовалюты с одного адреса на другой.
Tornado Cash — является децентрализованным криптомиксером, это значит, что он использует смарт-контракты, которые принимают криптовалюту, а затем позволяют выводить их на другие адреса. Поскольку вывод средств производится из пулов ликвидности смарт-контрактов проекта, невозможно узнать, кто является первоначальным отправителем. Это скрывает поток средств и затрудняет их отслеживание.
Пул ликвидности – это совокупность криптовалюты или токенов, заблокированных в смарт-контракте. Заблокированные средства используется для обеспечения тех или иных финансовых операций.
Анонимная связка адреса отправителя и адреса получателя возможна благодаря технологии доказательства с нулевым разглашением (Zero-knowledge proof). Доказательство с нулевым разглашением позволяет вам доказать истинность утверждения, не раскрывая содержание утверждения и не раскрывая, как вы обнаружили истину. Конкретно Tornado Cash использует протокол **zk-SNARK**.
Ниже мы разберем как это работает, а также будут ссылки на более детальные разборы.
Важно отметить, что, используя zk-SNARK, Tornado Cash позволяет вам вносить в контракт фиксированные суммы ETH, DAI, USDC или USDT. Когда вы вносите деньги(Deposit), вы получите резервный код, который вам понадобится для вывода(Withdrawal) средств позже.
Почему фиксированные суммы? Например, вы внесли 0,1 ETH(криптовалюта Эфереум), а также помимо вас это сделали еще 303 человека. А поскольку процес передачи средств в смарт-контракт являтся общедоступной информацией, когда вы вносите 0,1 ETH, эти 0,1 ETH позже можно будет отследить до этой группы из 303 человек, но не до вас напрямую.
Далее мы общо разберем технологии, которые используются в смарт-контрактах Tornado Cash.
Прежде чем Алиса вложит деньги в Tornado Cash, ей нужно будет выбрать два случайных числа: `secret` и `nulifier`, а затем она вычислить хэш этих двух случайных чисел.
Чтобы внести(разместить) депозит в Tornado Cash, Алиса отправит 1 ETH и хэш чисел `secret` и `nulifier`. Пускай в нашем примере это будет 0x404.
Отправленный эфериум хранится в смарт-контракте, как и хэши, которые необходимы для определения обязательств, хэш позже будет использоваться для вывода этого 1 ETH из Tornado Cash.
Прежде чем разобрать вывод средств, рассмотрим, как бы это могло бы быть сделано неправильно, то есть компрометируя выводящего средства, а потом посмотрим, как это сделать правильно.
Итак, неправильный путь это когда выводящий средства, передаст в смарт контракт числа `secret` и `nulifier`, а смарт-контракт проверит, что хэш есть в хранилище смарт-контракта и отдаст нужное кол-во ETH. Подобный процесс раскрывает личность выводящего деньги из смарт-контракта. Например, мы знаем, что Алиса разместила в смарт-контракте хэш 0x404,а позже появляется анонимный пользователь передающий `secret` и `nulifier`, так что хеш `secret` и `nulifier` равен 0x404, но поскольку хеш-функция является односторонней функцией, это означает, что единственный человек, который знает `secret` и `nulifier`, который хэширует в 0x404 — это Алиса. Именно так личность пользователя раскрывается при снятии средств. Итак, как мы можем решить эту проблему.
Если каким-то образом есть возможность доказать, что я знаю `secret` и `nulifier`, так что `hash(secret,nulifier)` есть в смарт-контракте, но без раскрытия `secret` и `nulifier`. Тогда анонимный пользователь мог бы отсылать в смарт-контракт некое доказательство что он знает `secret` и `nulifier` без фактической отправки этих чисел или хэша, а смарт-контракт проверял бы, действительно ли доказательство, при этом смарт-контракт не знал бы, предназначено ли доказательство для 0x404 или для 0x403 или 0x505, которые также записаны в смарт-контракт, другими словами, доказательство не раскрывало бы личность анонимного пользователя.
Подобный механизм называется доказательством с нулевым разглашением, то есть, когда вы можете доказать, что вам известна какая-то информация, не раскрывая ничего о фактической информации. Конкретно Tornado Cash использует криптографический протокол zk-SNARK.
Узнав, что смарт-контракт проверят действительно ли доказательство, но не знает для какого конкретно хэша, какой-нибудь хакер захотел бы много раз отправить одно и тоже доказательство, чтобы получить много ETH. Поэтому, чтобы предотвратить подобное двойное использование, когда вы отправляете доказательство для вывода, вам также нужно будет отправить хэш `nulifier` внутри доказательства.
И тогда «внутри» zk-SNARK будет проверятся: — что `hash(secret,nulifier)` есть в смарт-контракте — корректность, что хэш от `nulifier` == `hash(nulifier)`
После этих проверок, смарт-контракт отдаст ETH и «запишет», что вывод средств был произведен.
Поэтому `nulifier` грубо говоря нужен для предотвращения проблемы double spending
Для того, чтобы осуществлять большое количество проверок хэшей в Tornado Cash данные хранится в Merkle tree.
Использование хеш-деревьев позволяет «малыми» затратами проверять принадлежности определённого блока данных к множеству.
Поскольку различными блоками часто являются независимые данные, в нашем случае хэши вложенных средств, то нас интересует возможность проверить только один блок, не пересчитывая хеши для остальных узлов дерева. Пусть интересующий нас блок — это синий блок на картинке. Тогда доказательством его существования и валидности будут корневой хеш, а также верхние хеши других веток.
Зеленым отмечены хэши которые понадобятся нам для проверки, что синий элемент принадлежит к множеству средств внутри Tornado Cash
Как подробно работают **ZKPs**, и конкретно **zk-SNARK** можно найти здесь.
Верхнеуровнево при создании ZKP проверяющий просит доказывающего выполнить ряд действий, которые могут быть выполнены точно только в том случае, если доказывающий знает основную информацию. Если доказывающий только догадывается о результате этих действий, то в конечном итоге тест верификатора с высокой степенью вероятности докажет, что они ошибочны.
Концептуальный пример для интуитивного понимания данных доказательства в условиях нулевого разглашения это представить себе пещеру с одним входом, но двумя путями (путь A и B), которые соединяются через общую дверь, запертую кодовой фразой. Алиса хочет доказать Бобу, что она знает код доступа к двери, но не раскрывая код Бобу. Для этого Боб стоит снаружи пещеры, а Алиса идет внутрь пещеры, выбирая один из двух путей (при этом Боб не знает, какой путь был выбран). Затем Боб просит Алису вернуться к входу в пещеру по одному из двух путей (выбранных случайным образом). Если Алиса изначально выбрала путь А к двери, но затем Боб просит ее вернуться по пути Б, единственный способ решить головоломку для Алисы — это знать код доступа к запертой двери. Этот процесс может быть повторен несколько раз, чтобы доказать, что Алиса знает код доступа к двери и не выбрала правильный путь изначально с высокой степенью вероятности.
После завершения этого процесса Боб имеет высокую степень уверенности в том, что Алиса знает код доступа к двери, не раскрывая код доступа Бобу. Хотя это всего лишь концептуальный пример, ZKP используют ту же стратегию, но используют криптографию для подтверждения знаний о точке данных, не раскрывая сами данные.
Теперь у нас есть все, чтобы понять, как работает Tornado Cash (TC). Когда вы вносите 1 ETH по контракту Tornado Cash , вы представляете хэш доказательство. Этот хэш будет храниться в Merkle. Когда вы снимаете этот 1 ETH с другой учетной записи, вы должны предоставить 2 доказательства с нулевым разглашением. Первый доказывает, что дерево Меркель содержит ваши хэши. Это доказательство является доказательством с нулевым разглашением. Но этого недостаточно, потому что вам должно быть разрешено снять этот 1 ETH только один раз. Из-за этого вы должны предоставить `nulifier`, уникальный для доказательства. Контракт хранит этот `nulifier`,и это гарантирует, что вы не сможете снять внесенные деньги более одного раза.
Санкции на смарт-контракт являются интересным прецедентом, так как смарт-контракт сам по себе автономен, и пока не ясно к каким образом должна выглядеть, например, полная блокировка сервиса на уровне сети Ethereum.
Как концептуально работает Tornado Cash, который «забанили» власти США
8 августа 2022 года Управление по контролю за иностранными активами Министерства финансов США (OFAC) наложило санкции на Tornado Cash, миксер криптовалюты, что вызвало шквал обсуждений в криптосреде. В этой статье разберем как концептуально работает криптомиксер Tornado Cash, что было понять, что есть в этой технологии, что против нее вводят санкции.
Что такое Tornado Cash?
Одной из особенностей блокчейна является то, что ее реестр, содержащий все когда-либо имевшие место транзакции, виден глобально, то есть можно отслеживать средства по мере их перехода из рук в руки, а в некоторых случаях полностью деанонимизировать пользователей.
Tornado Cash — это сервис, который смешивает разные потоки потенциально идентифицируемой криптовалюты и таким образом не дает отследить переход криптовалюты с одного адреса на другой.
Tornado Cash — является децентрализованным криптомиксером, это значит, что он использует смарт-контракты, которые принимают криптовалюту, а затем позволяют выводить их на другие адреса. Поскольку вывод средств производится из пулов ликвидности смарт-контрактов проекта, невозможно узнать, кто является первоначальным отправителем. Это скрывает поток средств и затрудняет их отслеживание.
Пул ликвидности – это совокупность криптовалюты или токенов, заблокированных в смарт-контракте. Заблокированные средства используется для обеспечения тех или иных финансовых операций.
Анонимная связка адреса отправителя и адреса получателя возможна благодаря технологии доказательства с нулевым разглашением (Zero-knowledge proof). Доказательство с нулевым разглашением позволяет вам доказать истинность утверждения, не раскрывая содержание утверждения и не раскрывая, как вы обнаружили истину. Конкретно Tornado Cash использует протокол zk-SNARK.
Ниже мы разберем как это работает, а также будут ссылки на более детальные разборы.
Важно отметить, что, используя zk-SNARK, Tornado Cash позволяет вам вносить в контракт фиксированные суммы ETH, DAI, USDC или USDT. Когда вы вносите деньги(Deposit), вы получите резервный код, который вам понадобится для вывода(Withdrawal) средств позже.
Почему фиксированные суммы? Например, вы внесли 0,1 ETH(криптовалюта Эфереум), а также помимо вас это сделали еще 303 человека. А поскольку процес передачи средств в смарт-контракт являтся общедоступной информацией, когда вы вносите 0,1 ETH, эти 0,1 ETH позже можно будет отследить до этой группы из 303 человек, но не до вас напрямую.
Далее мы общо разберем технологии, которые используются в смарт-контрактах Tornado Cash.
Алгоритм работы
Размещение(Deposit)
Прежде чем Алиса вложит деньги в Tornado Cash, ей нужно будет выбрать два случайных числа: secret и nulifier , а затем она вычислить хэш этих двух случайных чисел.
Чтобы внести(разместить) депозит в Tornado Cash, Алиса отправит 1 ETH и хэш чисел secret и nulifier . Пускай в нашем примере это будет 0x404.
Отправленный эфериум хранится в смарт-контракте, как и хэши, которые необходимы для определения обязательств, хэш позже будет использоваться для вывода этого 1 ETH из Tornado Cash.
Вывод средств
Прежде чем разобрать вывод средств, рассмотрим, как бы это могло бы быть сделано неправильно, то есть компрометируя выводящего средства, а потом посмотрим, как это сделать правильно.
Итак, неправильный путь это когда выводящий средства, передаст в смарт контракт числа secret и nulifier , а смарт-контракт проверит, что хэш есть в хранилище смарт-контракта и отдаст нужное кол-во ETH. Подобный процесс раскрывает личность выводящего деньги из смарт-контракта. Например, мы знаем, что Алиса разместила в смарт-контракте хэш 0x404,а позже появляется анонимный пользователь передающий secret и nulifier , так что хеш secret и nulifier равен 0x404, но поскольку хеш-функция является односторонней функцией, это означает, что единственный человек, который знает secret и nulifier , который хэширует в 0x404 — это Алиса. Именно так личность пользователя раскрывается при снятии средств. Итак, как мы можем решить эту проблему.
Если каким-то образом есть возможность доказать, что я знаю secret и nulifier , так что hash(secret,nulifier) есть в смарт-контракте, но без раскрытия secret и nulifier . Тогда анонимный пользователь мог бы отсылать в смарт-контракт некое доказательство что он знает secret и nulifier без фактической отправки этих чисел или хэша, а смарт-контракт проверял бы, действительно ли доказательство, при этом смарт-контракт не знал бы, предназначено ли доказательство для 0x404 или для 0x403 или 0x505, которые также записаны в смарт-контракт, другими словами, доказательство не раскрывало бы личность анонимного пользователя.
Подобный механизм называется доказательством с нулевым разглашением, то есть, когда вы можете доказать, что вам известна какая-то информация, не раскрывая ничего о фактической информации. Конкретно Tornado Cash использует криптографический протокол zk-SNARK.
Что за nulifier?
Узнав, что смарт-контракт проверят действительно ли доказательство, но не знает для какого конкретно хэша, какой-нибудь хакер захотел бы много раз отправить одно и тоже доказательство, чтобы получить много ETH. Поэтому, чтобы предотвратить подобное двойное использование, когда вы отправляете доказательство для вывода, вам также нужно будет отправить хэш nulifier внутри доказательства.
И тогда «внутри» zk-SNARK будет проверятся:
что hash(secret,nulifier) есть в смарт-контракте;
корректность, что хэш от nulifier == hash(nulifier) .
После этих проверок, смарт-контракт отдаст ETH и «запишет», что вывод средств был произведен.
Поэтому грубо говоря нужен для предотвращения проблемы double spending
Хранение данных
Для того, чтобы осуществлять большое количество проверок хэшей в Tornado Cash данные хранится в Merkle tree.
Использование хеш-деревьев позволяет «малыми» затратами проверять принадлежности определённого блока данных к множеству.
Поскольку различными блоками часто являются независимые данные, в нашем случае хэши вложенных средств, то нас интересует возможность проверить только один блок, не пересчитывая хеши для остальных узлов дерева. Пусть интересующий нас блок — это синий блок на картинке. Тогда доказательством его существования и валидности будут корневой хеш, а также верхние хеши других веток.
Зеленым отмечены хэши которые понадобятся нам для проверки, что синий элемент принадлежит к множеству средств внутри Tornado Cash
Доказательства с нулевым разглашением ZKPs
Как подробно работают ZKPs, и конкретно zk-SNARK можно найти здесь.
Верхнеуровнево при создании ZKP проверяющий просит доказывающего выполнить ряд действий, которые могут быть выполнены точно только в том случае, если доказывающий знает основную информацию. Если доказывающий только догадывается о результате этих действий, то в конечном итоге тест верификатора с высокой степенью вероятности докажет, что они ошибочны.
Концептуальный пример для интуитивного понимания данных доказательства в условиях нулевого разглашения это представить себе пещеру с одним входом, но двумя путями (путь A и B), которые соединяются через общую дверь, запертую кодовой фразой. Алиса хочет доказать Бобу, что она знает код доступа к двери, но не раскрывая код Бобу. Для этого Боб стоит снаружи пещеры, а Алиса идет внутрь пещеры, выбирая один из двух путей (при этом Боб не знает, какой путь был выбран). Затем Боб просит Алису вернуться к входу в пещеру по одному из двух путей (выбранных случайным образом). Если Алиса изначально выбрала путь А к двери, но затем Боб просит ее вернуться по пути Б, единственный способ решить головоломку для Алисы — это знать код доступа к запертой двери. Этот процесс может быть повторен несколько раз, чтобы доказать, что Алиса знает код доступа к двери и не выбрала правильный путь изначально с высокой степенью вероятности.
После завершения этого процесса Боб имеет высокую степень уверенности в том, что Алиса знает код доступа к двери, не раскрывая код доступа Бобу. Хотя это всего лишь концептуальный пример, ZKP используют ту же стратегию, но используют криптографию для подтверждения знаний о точке данных, не раскрывая сами данные.
Теперь у нас есть все, чтобы понять, как работает Tornado Cash (TC). Когда вы вносите 1 ETH по контракту Tornado Cash , вы представляете хэш доказательство. Этот хэш будет храниться в Merkle. Когда вы снимаете этот 1 ETH с другой учетной записи, вы должны предоставить 2 доказательства с нулевым разглашением. Первый доказывает, что дерево Меркель содержит ваши хэши. Это доказательство является доказательством с нулевым разглашением. Но этого недостаточно, потому что вам должно быть разрешено снять этот 1 ETH только один раз. Из-за этого вы должны предоставить nulifier , уникальный для доказательства. Контракт хранит этот nulifier ,и это гарантирует, что вы не сможете снять внесенные деньги более одного раза.
Заключение
Санкции на смарт-контракт являются интересным прецедентом, так как смарт-контракт сам по себе автономен, и пока не ясно к каким образом должна выглядеть, например, полная блокировка сервиса на уровне сети Ethereum.
How Does Tornado Cash Work?
Tornado Cash is an open-source decentralized coin mixer on the Ethereum network, developed by Roman Semenov, Alexey Pertsev, and Roman Storm. It was launched in December 2019, and as of March 2023, 3.66M ETH are deposited with 112K ETH in the pool (Tornado Cash Analysis). The feature provided by Tornado Cash is a kind of double-edged sword: it provides strong anonymity so Ethereum co-founder Vitalik Buterin could send anonymous funds to aid Ukraine, but it allows coins earned from criminal activity to be laundered. For example, both North Korean government hacking group Lazarus and the Euler finance hacker mixed their coins using Tornado Cash.
In this post, we will talk about the mathematical principles behind Tornado Cash. Let’s deep dive into Tornado Cash!
Background
Hash Function
A hash function is a mathematical function that takes in input messages of arbitrary size and returns a fixed-size string of characters called a hash value. For example, $f(x) = x % 97$ (remainder of dividing $x$ by $97$) is a hash function for integer input. The purpose of a hash function is to generate a unique digital fingerprint of the input data, which can be used for various purposes, such as data storage, data retrieval, data integrity checking, digital signatures, and password verification.
We may define a special type of hash function named cryptographic hash function. A hash function $f$ is called a cryptographic hash function if it satisfies the below three secure properties:
- Pre-image resistance: Given hash value $h$, it is hard to find any input message $m$ that $f(m) = h$.
- Second-preimage resistance: Given input message $m$, it is hard to find message $m'( \neq m)$ that $f(m’) = f(m)$.
- Collision resistance: It is hard to find any two different input messages $m_1, m_2(\neq m_1)$ that $f(m_1) = f(m_2)$.
There are many different hash functions available, each hashes with its own characteristics, strengths, and weaknesses. Common examples of hash functions include MD5, SHA-1, SHA-2, and SHA-3. (Note: MD5 and SHA-1 are now deprecated and generally should not be used for cryptographic purposes.)
Merkle Tree
A Merkle tree is a tree data structure used in cryptography and computer science to efficiently verify the integrity and authenticity of large sets of data. The tree structure is based on cryptographic hash functions. To construct a Merkle tree, the elements to be stored are first hashed and the resulting hash values are arranged as the leaf nodes of the tree. Then, pairs of adjacent leaf nodes are hashed together to create a new set of hash values, which are used as the parents of the previous leaf nodes. This process is repeated recursively until a single hash value, known as the root hash, is generated. Here is an example of storing elements “Alice”, “Bob”, “Charles”, “Daniel”, “Emma”, “Fiona”, “Grace”, and “Henry” in a Merkle tree.
Example of storing elements “Alice”, “Bob”, “Charles”, “Daniel”, “Emma”, “Fiona”, “Grace”, and “Henry” in a Merkle tree; $f$ is a cryptographic hash function.
After storing elements in this Merkle tree, the root $h_<15>$ is opened. To prove “Alice” is in the Merkle tree, it is enough to provide $h_2, h_<10>, h_<14>$. Then verifier can recompute $h_<15>$ by $h_ <15>= f(f(f(f(\text<"Alice">),h_2),h_<10>),h_<14>)$. This additional value required to recompute Merkle root is called Merkle proof (also known as Merkle path).
Example of proving the existence of element “Alice” in a Merkle tree. Green-colored boxes denote the Merkle proof.
Due to the preimage resistance of $f$, Merkle proof does not reveal the other stored elements and the total number of elements in Merkle proof is log scale of the total number of elements stored in Merkle tree.
Commitment Scheme
A commitment scheme is a cryptographic protocol that allows a party to commit to a message or a value, without revealing the value itself, and later reveal it in a verifiable manner. This is useful in scenarios where a party needs to prove that they made a commitment to a particular message at an earlier time without revealing the message until a later time. Check out this scenario:
Alice has the foreknowledge of tomorrow’s Nasdaq closing price $p$. Alice wants to convince her foreknowledge without revealing the value itself. Then Alice can commit price $p$ by choosing sufficiently long random string $\text
$ and going public with $\text = f(\text ||p)$ where $f$ is a cryptographic hash function and $||$ is a concatenation operation. Due to preimage resistance property, it is impossible to recover $p$ from $\text $. After tomorrow, $p$ is known to everyone. Then Alice opens $\text $. Now Alice’s foreknowledge is verified by checking $\text \stackrel <=>f(\text ||p)$.
Answer: $p$ can be revealed by checking $f(1), f(2), \dots$ until hash value is the same as $\text
(Non-interactive) Zero-Knowledge Proof
A zero-knowledge proof is a cryptographic protocol that allows a prover to demonstrate to the verifier that a given statement is true without revealing any additional information beyond the truth of the statement itself. In other words, it allows a prover to convince a verifier that they know a secret value without revealing that value or any other information about it. Zero-knowledge proof must satisfy the below three properties:
- Completeness: If the statement is true, then an honest prover should be able to convince the verifier of its truth.
- Soundness: If the statement is false, then no cheating prover should be able to convince the verifier of its truth.
- Zero-knowledgeness: The proof should not reveal any additional information beyond the truth of the statement.
Zero-knowledge proofs are classified into two types, interactive or non-interactive, depending on the communications between the prover and verifier. If the prover and verifier interact by exchanging messages, similar to an oral test, the protocol is called interactive. On the other hand, if the prover creates a proof that cann be verified without requiring any further interaction between the prover and verifier, the protocol is called non-interactive.
There are several examples of zero-knowledge proof protocols such as zk-SNARK, zk-STARK, Bulletproofs, and Ligero. While we will only cover details of the zk-SNARK, which is used in Tornado Cash later, the most important thing to note is that for any function $f$ and given output $y$, it is possible to prove the knowledge of an input $x$ satisfies $f(x)=y$ without revealing $x$. Moreover, any interactive zero-knowledge proof can be transformed into non-interactive zero-knowledge proof. Finally, for any function $f$ and given output $y$, a prover can prove their knowledge of an input $x$ satisfies $f(x)=y$ without revealing $x$ by sending only proof $\pi$ to a prover with no interaction.
Protocol Overview
Tornado Cash aims to provide users with complete anonymity while using Ethereum by allowing them to make private transactions. So the main features of Tornado Cash are simply deposits and withdrawals. This can be done in a single transaction with a predetermined amount of Ether. The amount is not specified in the white paper, but it is either 0.1 or 1 or 10 or 100 ETH in the current implementations. The reason for fixing the amount is to prevent tracking the transaction based on its value. For example, there are 10 deposits from $\text
Setup
First, a Pedersen hash function and MiMC hash function are used in Tornado Cash. We denote each function as $H_1$ and $H_2$, respectively. The contract has a Merkle tree of height $20$, where each non-leaf node is the hash of its two children with $H_2$. Since the height is $20$, there are $2^<20>$ leaves. The leaves are initialized as $0$ and will be replaced by some value from left to right when a deposit is made. Since each leaf corresponds to a single deposit, the contract supports for only $2^<20>$ deposits. After $2^<20>$ deposits, no more deposits are allowed.
Although not necessary, the contract stores the most recent $n = 100$ (as mentioned in the white paper) or $30$ (in the implementation) root values for user convenience, not just the most recent one. Finally, the contract also has a list of nullifier hashes to prevent double spending, which we will introduce later.
Deposit
The process for a deposit is as follows:
- A user generates two random numbers $k$(nullifier), $r$(secret) and computes commitment $C = H_1(k||r)$. This two numbers must be memorized. This is a commitment scheme that we introduced earlier in this blog post.
- Send ETH transaction to contract with data $C$. If the tree is not full, the contract accepts the transaction and replaces the leftmost zero leaf to $C$. This changes the $20$ elements in the tree, including the root.
Note that $k, r$ are hidden but commitment $C$ is opened to everyone, and the order is also preserved. For example, from the beginning, if addresses $\text<0x111>, \text<0x222>,$ and $\text<0x333>$ make deposits, then it is publicly known that the first leaf belongs to $\text<0x111>$, the second leaf belongs to $\text<0x222>$, and the third leaf belongs to $\text<0x333>$. However, this means almost nothing because, during withdrawal, the leaf index is not revealed.
Withdrawal
The process for withdrawing the $l$-th leaf $C = H_1(k||r)$ is as follows:
- Compute the Merkle proof $O$, which proves an existence of $C$ in Merkle tree with root $R$. Root $R$ must be one of the recent $n$ root values.
- Compute the nullifier hash $h = H_1(k)$.
- Compute the proof $\pi$, which proves the knowledge of $l, k, r$ such that $h = H_1(k)$ and $O$ is a valid Merkle proof for $l$-th leaf $C=H_1(k||r)$.
- Send ETH transaction to contract with $R, h, \pi$. The contract accepts the request if proof $\pi$ is valid and $h$ is not in the list of nullifier hashes.
- The contract adds $h$ to the list of nullifier hashes.
To understand this withdrawal procedure, we recall non-interactive zero-knowledge proof (NIZK). In NIZK, a prover can prove their knowledge of an input $x$ satisfies $f(x)=y$ without revealing $x$ by sending only proof $\pi$ to prover with no interaction. Once we define $f$ as
and the target output $y = 1$, then proof $\pi$ represents that prover is a legitimate withdrawer without revealing $l, k,r,O$, so the anonymity is guaranteed. We discuss proof more in the Zero-Knowledge Proof in Tornado Cash section.
The withdrawal procedure seems sound. But what about the fee? If a user wants to withdraw a coin to a fresh wallet, the wallet cannot pay a fee because it has no balance. It is also impossible to pay from the original wallet because it allows linking the fresh wallet and original wallet, which violates anonymity. To resolve this issue, users can optionally use a relay. The user chooses coin recipient address $A$ and fee $f$ and includes them into the proof $\pi$. Then a user sends the proof to relay and relay transmits it into the contract. A relayer takes a fee as compensation, but they cannot change any withdrawal data, including recipient address.
Zero-Knowledge Proofs in Tornado Cash
Now we have a bird’s-eye view of Tornado Cash. We will take a more in-depth look at the zero-knowledge proofs used in Tornado Cash in this section.
zk-SNARKs
zk-SNARK is an acronym that stands for Zero-Knowledge Succinct Non-interactive Argument of Knowledge.
- Zero-Knowledge: Verifier learns nothing other than the statement is true.
- Succinct: Proof size and verifier time is sublinear.
- Non-interactive: Need no interaction.
- Argument of Knowledge: Not only for existence of input $x$ but also prover’s knowledge of $x$.
Not only zero-knowledge but succinct is also mysterious. For example, if a prover wants to prove their knowledge of input $x$ such that $\text
There are two $n$ by $n$ matrices $A, B,$ and $C$. The prover wants to prove that $C = AB$. If the verifier directly calculates $AB$ and compares it with $C$, the time complexity is $O(n^3)$ — or $O(n^<2.373>)$ by using a state-of-the-art algorithm. However, if the verifier selects random vector $v$ size of $n$ and checks whether $A\cdot(Bv) \stackrel <=>Cv$, its time complexity is reduced to $O(n^2)$. It is possible such that $AB \neq C$ but $A\cdot(Bv) \stackrel <=>Cv$ so the verifier might accept wrong $C$, but the probability of this occurring is dramatically reduced when the verifier repeats this verification for different values of $v$.
Groth16
Let’s move on to the zero-knowledge proof system actually used in Tornado Cash. Tornado Cash uses Groth16, which is an improved version of Pinocchio. In Groth16, a prover transforms their statement into a QAP (quadratic arithmetic program) form. We will show a transformation step by step using a simple example:
Flattening
Prover wants to prove their knowledge of $x, y$ satisfy $f(x,y) = 17$. To do this, the prover first converts the given statement into a sequence of special forms where x = y and x = y (op) z , where y, z can be variables or numbers, and op can be + or *. This is similar to the concept of three address code from compilers. The transformation of the equation $f(x, y)$ is as follows:
Continuing with our example, y2 = y * y is transformed into
t1 = 3 * y2 is transformed into
and t2 = x2 + t1, out = t2 + 10 is transformed into
After representing all the flattened equations in this format, the only prover who knows the correct $x, y$ can find solution vector $\vec$ of given constraint system. So the prover’s ultimate goal now is to prove their knowledge of $\vec$.
The purpose of QAP is to prove same system but decrease communication cost using polynomials instead of vector dot products. From the vectors in R1CS, we can derive polynomials. For example, polynomial $a_1$ (note: this is NOT $\vec
From this long journey, we transformed the statement into multiplications of polynomials. If a prover can convince that
- $A(x), B(x),$ and $C(x)$ are derived from same $\vec
$, and - exists $H(x)$ such that $A(x)\cdot B(x) — C(x) = H(x) \cdot Z(x)$ where $Z(x) = (x-1)(x-2)(x-3)(x-4)$,
then the verifier accepts the prover’s knowledge. To guarantee succinctness, rather than directly handling polynomials, $A(t)\cdot B(t) — C(t) = H(t) \cdot Z(t)$ for some random point $t$ is checked.
Homomorphic Hiding & Pairing
The equation $A(t)\cdot B(t) — C(t) = H(t) \cdot Z(t)$ can hold for some $t$ when $A(x)\cdot B(x) — C(x) \neq H(x) \cdot Z(x)$. This probability is negligible, but if $t$ is known, then an attacker can easily construct $A(x), B(x), C(x), H(x)$ satisfying $A(t)\cdot B(t) — C(t) = H(t) \cdot Z(t)$. Therefore $t$ should be hidden but allowing the prover to calculate $A(t), B(t), C(t), H(t)$. It seems contradictory, but homomorphic hiding allows this. From the hardness of elliptic curve discrete logarithm problem, we define an encryption function $E(x) = xg$ for a generator $g$. Then $E$ satisfies the following:
- It is hard to find $x$ from $E(x)$.
- $x \neq y$ then $E(x) \neq E(y)$.
- $E(x + y) = E(x)+E(y)$.
- $a \cdot E(x) = E(ax)$.
Rather than directly giving $t$ to the prover, the prover is given $E(t^0), E(t^1), \dots$. Then, since $A(t), B(t), C(t),$ and $H(t)$ are linear combinations of $t^0, t^1, \dots$, the prover can calculate $E(A(t)), E(B(t)), E(C(t)), E(H(t))$ . Moreover, the fact that $E(A(t)), E(B(t)), E(C(t)), E(H(t))$ is really derived form $E(t^0), E(t^1), \dots$ can be proven by the knowledge of coefficient assumption test. We omit information of the coefficient assumption test in this article.
Now the prover generates $E(A(t)), E(B(t)), E(C(t)), E(H(t))$ , which will be given to the verifier, and the verifier can generate $E(Z(t))$ since $Z(x)$ is known. However, the verifier cannot check $A(t)\cdot B(t) — C(t) = H(t) \cdot Z(t)$ because $E$ is not homomorphic in multiplication. We need another mapping called pairings. A pairing is a map $e : G_1 \times G_2 \rightarrow G_T$ that satisfies $e(aP,bQ)=ab \cdot e(P,Q)$ where $G_1, G_2$ are elliptic curves with the same equation but different generators $g_1, g_2$ having order $q$ and $G_T$ is a cyclic group of order $q$. We slightly extend $E$ to $E_1$ and $E_2$, where $E_1(x) = xg_1, E_2(x) = xg_2$.
From now on, we can multiply hiding values. Finally, $A(t)\cdot B(t) — C(t) = H(t) \cdot Z(t)$ is checked from $e(E_1(A(t)), E_2(B(t)) / e(E_1(C(t)), E_2(1)) \stackrel <=>e(E_1(H(t)) \cdot E_2(Z(t))).$ Since only $E_1(A(t)), E_2(B(t)), E_1(C(t))$ are required to verify, the proof size is fixed to $2$ elements of $G_1$ and $1$ element of $G_2$.
Trusted Setup
In this procedure, the prover needs $E_1(t^0),E_1(t^1),\dots,E_2(t^0),E_2(t^1),\dots$ generated from a random $t$. One possible scenario is that the verifier chooses random $t$, generates $E_1(t^0),E_1(t^1),\dots,E_2(t^0),E_2(t^1),\dots$ and sends these values to the prover. However, this method is very costly for prover and only enables an interactive model. In the non-interactive model, the verifier cannot send something to the prover. Therefore, instead of verifier, a third party generates common reference string (CRS) ****$E_1(t^0),E_1(t^1),\dots,E_2(t^0),E_2(t^1),\dots$ and opens it to everyone. This is called a trusted setup. The requirement of trusted setup is a significant weakness of zk-SNARK.
Powers-of-Tau
In Tornado Cash, the users act as provers while the contract serves as the verifier. In the beta version of Tornado Cash, the Tornado Cash team generated CRS and made it public (see here, proving key and verification key are derived from CRS). If all users trust the Tornado Cash team, they can generate proof using CRS provided by the team. However, if the Tornado Cash team become malicious, they can generate forged proof and potentially steal all the coins. To resolve this issue, the Tornado Cash team replaced CRS generated from the crypto community, called power-of-tau. User $1$ to $k$ first hold their own random $t_1, t_2, \dots, t_k$. User $1$ generates $E_1(t_1^0),E_1(t_1^1),\dots,E_2(t_1^0),E_2(t_1^1),\dots$. Note that $E_1(t_1^i) = t_1^i \cdot g_1, E_2(t_1^i) = t_1^i \cdot g_2.$ Then user $2$ generates $E_1((t_1t_2)^0),E_1((t_1t_2)^1),\dots,E_2((t_1t_2)^0),E_2((t_1t_2)^1),\dots$ from $E_1((t_1t_2)^i) = t_2^i \cdot E_1(t_1^i), E_2((t_1t_2)^i) = t_2^i \cdot E_2(t_1^i)$, without knowing $t_1$. After user $k$ generates the list, the CRS from secret $t = t_1t_2 \dots t_k$ is generated. In the case of Tornado Cash, 1,114 users participated and CRS is successfully replaced.
Implementations in Tornado Cash
Now we get back to statements in Tornado Cash. Our goal is to prove and verify the knowledge of $l,k,r,O$ such that for a $f(l,k,r,O)=1$ for
This $f$ needs to be transformed into a QAP. Tornado Cash uses circuit compilers Circom and snarkjs. Circuit compiler Circom has their own language called circom language. After coding $f$ in a circom language, the code is transformed into the R1CS using circom compiler. After that, snarkjs takes care of almost everything, such as generating CRS (via the trusted setup ceremony in case of Tornado Cash), proof, and a smart contract for the verification.
Security Concerns
In this section, we will discuss several security concerns for protocol and user levels. It is important to note that addressing these issues does not necessarily mean that Tornado Cash is vulnerable.
Hash Functions
Using different hash functions $H_1$ and $H_2$ seems unnecessary, and the reasons for this choice were not given by the authors. ABDK Consulting, who audited Tornado Cash, also pointed this out (see here, section 5.1). Moreover, the Pedersen hash function has a homomorphic property, so it is not a cryptographic hash function. Instead, defining both $H_1$ and $H_2$ as MiMC (or any other SNARK-friendly hash function) and applying domain separation might be better.
Dependencies
The contract source code is not very long and well-analyzed. However, as is often the case, small flaws can cause an apocalypse in this field. In fact, in October 2019, the Tornado Cash team discovered a vulnerability where an attacker could make arbitrary deposits due to issues with the external dependency of the zk-SNARK implementation of the MiMC (see here). Therefore, all the dependencies must be also carefully audited.
User Mistakes
The user must choose a high entropy $k$ and $r$. There are also possibilities of losing anonymity from user mistakes. We recommend reading this article.
Conclusion
Tornado Cash is a popular, decentralized coin mixer on the Ethereum network that offers strong anonymity to its users through the use of cryptographic techniques. As a main feature of Tornado Cash is anonymity in making private transactions, we looked at the math behind their deposits and withdrawals. Taking a deeper dive into their zero-knowledge proof system, Groth16, we exemplified how a transformation of a prover’s statement into quadratic arithmetic program form may occur with reference to flattening, homomorphic hiding and pairing, and the R1CS – and followed with a discussion of procedures such as trusted setup and powers-of-tau. There were also several security concerns to note (including using different hash functions, dependencies needing auditing, and user mistakes). Since the anonymity and privacy in Tornado Cash is one of its strongest features, it is interesting to take a look behind the curtain and see the math behind it.
Что такое Tornado Cash,что случилось?
Tornado Cash или TC — это так называемый «миксер», который позволяет скрыть происхождение криптовалюты. Миксеры используются, чтобы разорвать цепочку между отправителем и получателем средств.
Схема из статьи Coin Center. Главное отличие Tornado Cash в том, что это был децентрализованный миксер, то есть не было одного лица, которое бы контролировало сервис и хранило данные об операциях.
Это делает миксеры привлекательными как для злоумышленников, которые хотят «отмыть» полученные незаконным путем средства, так и для людей, которые заботятся о неприкосновенности своих личных данных.
TC считался или считается самым безопасным миксером на блокчейне Ethereum, чем завоевал свою популярность среди криптанов. Им пользовались как хакеры из Сереной Кореи, так и весьма уважаемые и публичные личности.
Миксер использовал Виталик Бутерин, когда отправлял пожертвования. Это позволило ему не светить свои другие кошельки.
Чтобы оценить масштаб использования TC, можно обратиться к их публичному дэшборду, который построен на основании открытых данных о транзакциях на блокчейне.
Около $7 млрд депозитов за все время существования, судя по этим данным. Сумма будет меньше, если пересчитывать по ценам на дату депозита.
В отличие от многих других миксеров, с точки зрения коммуникации с внешним миром, Tornado Cash был достаточно открытым и публичным протоколом, который позиционировал себя как инструмент обеспечения финансовой приватности. Основатели и разработчики TC также были хорошо известны в крипто-комьюнити.
А это вообще законно?
Разумеется, никакого специального законодательства про крипто-миксеры не существует ни в одной стране в мире. Это не означает, что миксеры имеют какой-то иммунитет и могут существовать без оглядки на регуляторов.
По мнению Агентства по борьбе с финансовыми преступлениями США (FinCEN), миксеры являются операторами денежных переводов («money transmitters») по американскому законодательству и несут ряд обязанностей, в том числе в сфере AML/KYC.
Более того, существует ряд прецедентов:
- Октябрь 2020: FinCEN наложил штраф в $60 млн на основателя и оператора миксеров Helix и Coin Ninja.
- Апрель 2021: Минюст США арестовал 32-летнего гражданина России и Швеции, который был создателем одного из первых миксером для биткоина.
- Май 2022: OFAC наложил санкции на Blender.io — похожий на TC миксер для биткоина.
С учетом этого сложно назвать очень неожиданным наложение санкций на Tornado Cash.
В санкционный список были также добавлены 45 адресов Ethereum.
Чем тогда примечателен этот кейс
В первую очередь тем, что это первый случай, когда в санкционный список США был добавлен автономный смарт-контракт.
Смарт-контракт представляет собой бинарный код, который хранится на блокчейне Ethereum. Любое лицо, которое знает адрес смарт-контракта, может взаимодействовать с его функциями путем инициирования транзакций.
Смарт-контракт Tornado Cash был полностью автономным. Не было ни одного лица, которое могло остановить или прервать его работу.
В свою очередь санкции обычно накладываются на уголовных преступников или политических врагов США. В этот раз санкции были наложены на нейтральную технологию или инструмент. Если следовать такой логике, то санкции должны быть также наложены на наличные денежные средства, потому что они позволяют проводить анонимные транзакции и широко распространены среди преступников.
Юридические основания для введения санкций
Давайте кратко разберемся с правовой стороной вопроса.
Tornado Cash и сопутствующие адреса были внесены в так называемый Specially Designated Nationals List или список SDN на основании исполнительных указов 13694 и 13757 в рамках санкционной программы с кодовым названием [CYBER2].
Эти указы запрещают американским лицам совершать любые операции с субъектами из списка SDN и обязывают их блокировать любую собственность таких лиц. Конкретные положения санкционной программы против киберпреступлений уточняются в специальном разделе Свода нормативных актов федеральных органов исполнительной власти США, а также в тематическом разделе FAQ на сайте OFAC.
В соответствии с указом 13694 в SDN могут быть добавлены лица, которые определены следующим образом:
Кем именно являются смарт-контракты Tornado Cash из этого списка — остается открытым. Например, являются ли держатели токена $TORN, который дает определенные права для управления протоколом, лицами, на которых распространяются санкции? Распространяются ли санкции на тех, кто взаимодействовал до или после введения санкций со смарт-контрактами TC?
Что случилось после анонса санкций
Сразу после публикации на сайте OFAC пресс-релиза о санкциях последовал каскад событий и вспышек от туда, где не ждали.
Сначала был заблокирован сайт tornado.cash. Дальше был удален открый репозиторий TC на GitHub. Эта же судьба ждала разработчиков TC: GitHub заблокировал их аккаунты. Затем упал Discord сервер и форум на Discourse. По большому счету, в момент были стерты все следы Tornado Cash в интернете.
P.S. Интерфейс TC доступен на IPFS, но транзакции не работают, потому что ноды не обрабатывают транзакции.
Если такие действия со стороны классических интернет-платформ мало кого удивили (привет, Дональд), то реакция отдельных крипто-протоколов напомнила, что децентрализованный интернет и суверенные деньги не такие уж децентрализованные и суверенные.
Первым подлил масла в огонь Circle, оператор самого популярного стейблкоина USDC, заморозив $75 тыс. в стейблах. То же самое сделала крипто-биржа dYdX, что особенно примечательно, ведь компания всегда сторонилась американской юрисдикции и позиционировала себя, как вне ее периметра.
��️ Tornado.cash ��️ @TornadoCash 9 авг в 19:57
Here’s the list of Tornado Cash resources that were banned
— Tornado Cash @GitHub organization
— personal @GitHub accounts of TC contributors
— all $USDC on Tornado Cash contracts @circlepay
— @infura_io RPC
— @AlchemyPlatform RPC
— http://tornadocash.eth.limo domain @eth_limo
К слову, Twitter не удалил аккаунт TC. Кажется, что Илон Маск все-таки смог повлиять на политику компании в сфере свободы слова.
Тут ребята в MakerDAO неожиданно для себя вспомнили, что 50% их резервов состоит из USDC. То есть при большом желании через давление на Circle американские спецслужбы могут умножить на ноль половину подушки безопасности самого популярного децентрализованного стейблкоина DAI.
Rune, один из основателей MakerDAO, говорит, что надо готовиться к отвязке от доллара. Если так, то ребятам придется конвертировать $3,5 млрд USDC в ETH. Возможно, именно эта новость так подбодрила курс ETH на этой неделе.
Примеры Circle и dYdX последовали другие DeFi-платформы, начав добавлять заблокированные адреса в свои блэклисты.
Голландцы-то тут причем?!
Все бы ничего, но в пятницу 12 августа ровно в 10:00 утра голландские власти объявляют об аресте одного из разработчиков Tornado Cash. В разных чатах появляются слухи о том, кто это может быть.
Новость производит эффект разорвавшейся бомбы в крипто-твиттере. Одно дело наложить санкции на протокол, который, что уж лукавить, действительно использовали северокорейские хакеры, но другое дело — арестовывать разработчика, который создал этот протокол без какого-то преступного умысла.
К слову, вопрос об умысле будет одним из краеугольных в этом деле. Как известно, вина — это один элементов состава преступления, который обязательно должен быть доказан.
Первое, что приходит в голову — это все звенья одной цепи, скоординированные действия правоохранительных органов США и Нидерландов. Ведь вряд ли бы голландцы успели начать расследование в понедельник сразу после объявления санкций и обнаружить подозреваемого уже к пятнице.
Если так, то почему не последовали аресты других ключевых разработчиков Tornado Cash?
Это не призыв к их аресту, разумеется. Просто сложно понять тактику следователей в данном случае.
Один из следующих сценариев должен иметь право на существование в отсутствие другой информации:
- Спецслужбы не знают, где находятся другие разработчики TC, поэтому арестовывают только одного из них. Или знают, но не могут их арестовать в той юрисдикции.
- В силу особенностей европейского уголовного права, правоохранительные органы решают, что лучше довести это дело до правосудия в Нидерландах. Почему? Например, потому что в США у них было бы намного меньше шансов. Это не утверждение, просто в важных судебных спорах, которые планируются заранее, инициатор всегда внимательно относится к выбору юрисдикции или конкретного суда, где будет рассматриваться спор.
- Роль арестованного разработчика TC существенно отличалась от ролей других разработчиков протокола. Например, он был намного больше вовлечен.
- Введение санкций в понедельник и арест в пятницу — случайность. Просто американцы и голландцы вели расследования параллельно и забыли засинхриться.
Наверное, есть и другие сценарии, но вы тут решайте сами, какой из них более вероятен. В любом случае мы вряд ли узнаем что-то достоверное в ближайшем будущем, хоть я и надеюсь, что этот арест является ошибкой.
Многие комментаторы сравнивают эти события с преследованием американскими спецслужбами разработчиков протокола шифрования PGP в 90-ых годах, в частности Филиппа Циммерман. Эти события привели тогда к тому, что код (программное обеспечение) стали охраняться как выражение свободы слова.
Судя по реакции многих лидеров в крипте, история на этом не закончится. Мне лично это напоминает ситуацию с Pool Together, только в 20 раз масштабнее, потому что на кону стоят те фундаментальные ценности крипты, которые всем обещали.
Основатель MakerDAO говорит, что вся серьезная крипто-братва готова вписаться.