最も巧妙な ZK アプリケーション：Tornado Cash の原理とビジネスロジックを振り返る

執筆：Faust，ギーク web3

導入：最近、Vitalikといくつかの学者が共同で新しい論文を発表し、その中でTornado Cashがどのように反xi資金の仕組みを実現しているか（実際には、出金者が自分の預金記録が不正資金を含まない集合に属することを証明すること）について言及しましたが、文中にはTornado Cashのビジネスロジックと原理に関する詳細な解説が欠けており、理解が難しい部分があります。

また、Tornadoを代表とするプライバシープロジェクトこそが、実際にZK-SNARKアルゴリズムのゼロ知識性を活用しており、大多数のZKを名乗るRollupは、ZK-SNARKの簡潔さを利用しているだけです。多くの場合、人々はValidity ProofとZKの違いを混同しがちですが、TornadoはZKアプリケーションを理解するための優れたケースです。

この記事の著者は、2022年にWeb3 Caff ResearchでTornadoの原理に関する記事を書いたことがあり、今日はその一部の段落を抜粋し、拡張して整理し、皆さんがTornado Cashを体系的に理解できるようにします。

「トルネード」の原理

Tornado Cashはゼロ知識証明を利用した混合通貨プロトコルで、旧バージョンは2019年に投入され、新バージョンは2021年末にベータ版が開始されました。Tornadoの旧バージョンは基本的に分散化を実現しており、オンチェーン契約はオープンソースでマルチシグ制御がなく、フロントエンドコードはオープンソースでIPFSネットワークにバックアップされています。旧版Tornadoの全体構造はよりシンプルで理解しやすいため、この記事では旧バージョンに焦点を当てて解説します。

Tornadoの主な考え方は、大量の入出金行為を混ぜ合わせ、預金者がTornadoにトークンを預けた後、ZK Proofを示して自分が預金したことを証明し、新しいアドレスで出金することで、入出金アドレス間の関連性を断ち切るというものです。

より具体的に言えば、Tornadoは多くの人が入れたコインが混ざったガラス箱のようなものです。私たちはコインを入れた人が誰であるかを見ることができますが、これらのコインは高度に同質化されているため、見知らぬ人がガラス箱からコインを1枚取った場合、そのコインが最初に誰によって入れられたのかを知ることは非常に難しいです。

（画像出典：rareskills）

このようなシーンはよく見られます：私たちがUniswapのプールから数枚のETHをスワップする際、引き出されたETHが誰によって提供されたのか全く分かりません。なぜなら、Uniswapに流動性を提供した人が非常に多いためです。しかし、異なるのは、Uniswapでトークンを引き出すたびに、他のトークンを等価のコストとして使用する必要があり、資金を「プライベート」に他者に移転することはできません。一方、混合通貨プロトコルでは、出金者が預金証明書を示すだけで済みます。

入出金の動作を同質的に見せるために、Tornadoプールの預金アドレスは毎回預け入れる資金、出金アドレスは毎回引き出す資金を一致させます。たとえば、あるプールの100人の預金者と100人の出金者は公開されているが、互いに何の関係もないように見え、各人が預け入れた金額と引き出した金額は同じです。この時、視覚的に混乱を招き、入出金額から関連性を判断することができず、資金移動の痕跡を断ち切ることができます。明らかに、これはxi資金行為に天然の便利さを提供します。

しかし、1つの重要な問題があります：出金者は出金時にどのように自分が預金したことを証明するのでしょうか？混合通貨プロトコルに出金を要求するアドレスは、すべての預金アドレスと関連していないため、どのように彼の出金資格を判断するのでしょうか？最も直接的な方法は、出金者が自分の預金記録がどの取引であるかを直接開示することですが、これは直接的に身元を漏らすことになります。この時、ゼロ知識証明が役立ちます。

出金者はZK Proofを提示し、自分がTornado契約に預金記録を持っており、その預金はまだ引き出されていないことを証明することで、スムーズに出金を開始できます。ゼロ知識証明自体がプライバシー保護を実現しており、外部は出金者が確かに資金プールに預金をしたことを知っているが、どの預金者に対応しているのかは分からないのです。

「私はTornado資金プールに預金した」ということを証明することは、「私の預金記録はTornado契約の中に見つけることができる」ということに変換できます。もしCnを預金記録と表すと、問題は次のように要約されます：

Tornadoの預金記録集合が{C1、C2、… C100…}であることが知られている場合、出金者Bobは自分が持っている秘密鍵を使って、預金記録の中のあるCnを生成したことを証明しますが、ZKを通じてCnが具体的にどれであるかは漏らしません。

ここでMerkle Proofの特性を利用します。Tornadoのすべての預金記録は、オンチェーンで構築されたMerkle Treeに保存されており、最下層の葉ノードとして存在します。葉の総数は約2の20乗>100万で、大部分は空白の状態です（初期値が与えられています）。新しい預金行為が発生するたびに、契約はその対応する特徴値Commitmentを1つの葉に書き込み、Merkle Treeのルートを更新します。

たとえば、Bobの預金操作がTornadoの歴史上第1万件目である場合、その預金に関連する特徴値CnはMerkle Treeの第1万葉ノードに書き込まれます。つまりC10000 = Cnです。その後、契約は自動的に新しいルートを計算し、更新します。（ps：計算量を節約するために、Tornado契約は以前の一連の変化のあったノードのデータをキャッシュします。たとえば、下の図のFs1、Fs2、Fs0など）

（画像出典：RareSkills）

Merkle Proof自体は非常にシンプルで軽量です。それは、ツリー状データ構造を利用して検索/追跡プロセスの簡潔さを実現しています。特定の取引TDがMerkle Treeに存在することを外部に証明したい場合、ルートに対応するMerkle Proof（下の図の右側の部分）を示すだけで済みます。それは非常に簡潔です。もしMerkle Treeが非常に大きく、底層の葉が2の20乗個、つまり100万件の預金記録を含んでいても、Merkle Proofはわずか21ノードの数値を含むだけで、非常に短いです。

特定の取引H3が確かにMerkle Treeに含まれていることを証明するためには、H3とMerkle Tree上の他の部分のデータを使ってルートを生成できることを証明する必要があります。そして、ルートを生成するために必要なデータ（Tdを含む）はMerkle Proofを構成します。

Bobは出金時に、自分が持っている証明書がMerkle Tree上のある預金ハッシュCnに対応していることを証明する必要があります。つまり、彼は2つのことを証明する必要があります：

• Cnがチェーン上のTornado契約のMerkle Treeに存在し、具体的にMerkle Proofを構築できること、Cnを含む；
• CnがBobの手元にある預金証明書と関連していること。

Tornadoのビジネスロジック詳細

Tornadoユーザーインターフェースのフロントエンドコードには、事前に多くの機能が実装されています。預金者がTornado Cashのウェブサイトを開いて預金ボタンをクリックすると、フロントエンドコードに付随するプログラムがローカルで2つのランダム数Kとrを生成し、その後Cn = Hash(K, r)の値を計算し、Cn（下の図のコミットメント）をTornado契約に渡して、後者が記録するMerkle Treeに挿入します。言い換えれば、Kとrは秘密鍵に相当します。これらは非常に重要で、システムはユーザーに適切に保存するように促します。後で出金時にもKとrを使用する必要があります。

（ここでのencryptedNoteはオプションで、ユーザーが証明書Kとrを秘密鍵で暗号化し、チェーン上に保存することを許可し、忘れないようにします）

注意すべきは、上記の作業はすべてオフチェーンで行われるため、Tornado契約と外部の観察者はKとrを知りません。もしKとrが漏洩した場合、それは財布の秘密鍵が盗まれたのと同じです。

Tornado契約はユーザーの預金を受け取り、ユーザーが提出したCn = Hash(K, r)を受け取った後、CnをMerkle Treeの最下層に挿入し、新しい葉ノードとして扱い、同時にルートの値を更新します。したがって、Cnとユーザーの預金動作は一対一で関連付けられ、外部は各Cnがどのユーザーに対応しているかを知ることができ、誰が混合通貨プロトコルにトークンを預けたのかを知り、各預金者に対応する預金記録Cnを知ることができます。

出金手続きでは、出金者がフロントエンドウェブページに証明書/秘密鍵（預金時に生成されたランダム数Kとr）を入力し、Tornado Cashのフロントエンドコード内のプログラムがKとr、Cn = Hash(K, r)、Cnに対応するMerkle Proofを入力パラメータとして使用し、ZK Proofを生成します。これにより、CnがMerkle Tree上のある預金記録として存在することを証明し、Kとrが対応するCnの証明書であることを示します。

このステップは、私はMerkle Tree上の預金記録に対応する秘密鍵を知っていることを証明することに相当します。ZK ProofがTornado契約に提出されると、上記の4つのパラメータはすべて隠され、外部（Tornado契約を含む）はそれを知ることができず、プライバシーが保護されます。

ZK Proof生成に関与する他のパラメータには、出金時のTornado契約内のMerkle Treeのルートroot、カスタムの受取アドレスA、リプレイ攻撃を防ぐ識別子nf（後で説明します）が含まれます。これら3つのパラメータは公開され、外部が知ることができますが、プライバシーには影響しません。

ここでの細部は、預金操作でCnを生成する際に、1つのランダム数ではなく2つのランダム数Kとrを使用していることです。これは、単一のランダム数では安全性が不十分で、衝突が発生する確率があるためです。たとえば、単一のランダム数を使用すると、2人の異なる預金者が偶然にも同じランダム数を使用してしまい、生成されたCnが衝突する可能性があります。

上の図のAは、出金を受け取るアドレスを示し、出金者が自分で記入します。nfはリプレイ攻撃を防ぐ識別子で、その値nf=Hash(K)であり、Kは預金生成Cnのステップで使用された2つのランダム数のうちの1つです。こうすることで、nfはCnと関連付けられ、言い換えれば、各Cnには対応するnfがあり、両者は一対一で関連しています。

なぜリプレイ攻撃を防ぐ必要があるのでしょうか？混合通貨プロトコルの設計上の特性により、出金時にユーザーが引き出した通貨がMerkle Treeのどの葉Cnに対応しているのか分からず、出金者とどの預金者が関連しているのかも分からず、出金者が何回預金したのかも分からないからです。出金者はこの特性を利用して頻繁に出金し、リプレイ攻撃を発動し、混合通貨プールからトークンを何度も引き出すことができ、資金プールを枯渇させることができます。

ここで、nf識別子の役割は、各イーサリアムアドレスに存在する取引カウンターnonceに似ています。これは、特定の取引がリプレイされるのを防ぐために設定されています。出金が発生すると、出金者はnfを提出し、このnfがすでに使用されたかどうかを確認します（記録されている）：もしそうであれば、この出金は無効です。そうでなければ、そのnfはまだ使用されていないことを示し、出金が有効であり、対応するnfが記録されます。次回、誰かがこのnfを提出すると、その出金動作は無効と見なされます。

誰かが無作為に生成した契約に記録されていないnfは有効でしょうか？もちろん無効です。なぜなら、出金者がZK Proofを生成する際、nf=Hash(K)を保証する必要があり、ランダム数Kは預金記録Cnと関連しているからです。つまり、nfは記録のある預金Cnと関連しています。無作為にnfを作成すると、このnfは預金記録のすべての預金と一致しないため、有効なZK Proofを生成することができず、その後の作業がスムーズに進まず、出金操作は成功しません。

また、nfを使用しなくてもいいのではないか？出金者が出金時にZK証明を提出し、特定のCnと関連していることを証明するのであれば、出金動作が発生するたびに、対応するZK Proofがチェーン上に提出されているかどうかを確認すればよいのではないでしょうか？

しかし、実際には、これを行うコストは非常に高いです。なぜなら、Tornado Cash契約は過去に提出されたZK Proofを永久に保存しないからです。これはストレージスペースを大幅に浪費することになります。新しくチェーンに交付されたZK Proofと既存のProofが一致するかどうかを比較するよりも、非常に小さな識別子nfを設定し、それを永久に保存する方がはるかに経済的です。

出金関数のコード例に基づくと、必要なパラメータとビジネスロジックは次のようになります：

ユーザーはZK Proof、nf（Nullifier Hash）= Hash(K)、カスタムの受取アドレスrecipientを提出し、ZK ProofはCnとK、rの値を隠し、外部がユーザーの身元を判断できないようにします。recipientは通常、クリーンな新しいアドレスを記入し、個人情報を漏らすことはありません。

しかし、ここに小さな問題があります。ユーザーが出金する際、追跡不可能にするために、新しく申請したアドレスを使用して出金取引を開始することが多いですが、この時新しいアドレスにはガス代を支払うためのETHがありません。したがって、出金アドレスが出金を開始する際には、中継者relayerを明示的に宣言する必要があります。その後、混合通貨契約はユーザーの出金から一部を引き落とし、relayerに報酬として支払います。

以上のように、Tornado Cashは出金者と預金者の関連性を隠すことができ、ユーザー数が非常に多い場合、まるで賑やかな繁華街のように、犯人が群衆に紛れ込むと警察が追跡しにくくなります。出金プロセスではZK-SNARKが必要で、隠されたwitness部分には出金者の重要な情報が含まれており、これは混合通貨プロトコルの最も重要なポイントです。現時点では、TornadoはZKに関連する最も巧妙なアプリケーションレイヤープロジェクトの1つである可能性があります。

参考資料 1.https://etherscan.io/address/0xa160cdab225685da1d56aa342ad8841c3b53f291#codeTornado 契約ソースコード 2.https://mirror.xyz/mazemax.eth/BTbTOrEKzGkc-XoDcFtLPfJPtQ1Mt96BZYsW83m33IUTornado.cash 新旧版メカニズムの比較 3.https://www.youtube.com/watch?v=Z0s4W3UBxM8AnonymousPayments 4.https://medium.com/taipei-ethereum-meetup/zkp-study-group-tornado-cash-fdbb84d44b93[ZKP 読書会]TornadoCash 5.https://medium.com/taipei-ethereum-meetup/tornado-cash-%E5%AF%A6%E4%BE%8B%E8%A7%A3%E6%9E%90-eb84db35de04TornadoCash 実例解析