ヴィタリック・ブテリン：どのようにして zk-SNARKs 技術を使ってプライバシーを保護するのか？

著者：Vitalik Buterin

原文タイトル：《プライバシーのためのZK-SNARKのいくつかの使用方法》

編纂：分散型金融コミュニティ

ZK-SNARKは強力な暗号ツールであり、ブロックチェーンおよびブロックチェーン外で構築されたアプリケーションにおいてますます重要な部分となっています。しかし、それらは複雑であり、動作の仕組みや私たちがどのように使用するかの観点からも複雑です。

この記事では、ZK-SNARKが既存のアプリケーションにどのように適応するか、何ができるか、何ができないかの例、および特定のアプリケーションにZK-SNARKが適しているかを判断するための一般的なガイドラインに焦点を当てます。

この記事は特に、プライバシー保護におけるZK-SNARKの応用に焦点を当てています。

ZK-SNARKは何をするのか？

公共入力x、プライベート入力w、および(公共)関数f(x,w)→{True,False}があると仮定します。これは入力に対して何らかの検証を実行します。ZK-SNARKを使用すると、特定のfとxに対してf(x,w)=Trueであることを示すためにwを知っていることを証明できますが、wが何であるかを明らかにすることなく行えます。さらに、検証者は証明をより迅速に検証でき、彼ら自身がf(x,w)を計算するよりもはるかに速く行えます。

これにより、ZK-SNARKにはプライバシーとスケーラビリティの2つの特性が与えられます。この記事では、プライバシーに焦点を当てた例を取り上げます。

メンバーシップの証明

あなたがEthereumウォレットを持っていて、そのウォレットが人間証明（proof-of-humanity）に登録されていることを証明したいとしますが、どの人が登録されているかは明らかにしたくありません。この関数を数学的に表現できます：

• プライベート入力(w)：あなたのアドレスA、あなたのアドレスの秘密鍵k
• 公共入力(x)：すべての検証済み人間証明プロファイル{H1…Hn}のアドレスの集合
• 検証関数f(x,w)
• wを(A,σ)のペアとして解釈し、xを有効なプロファイルリスト{H1…Hn}とする
• Aが{H1…Hn}のアドレスの1つであることを検証
• privtoaddr(k) = Aを検証
• 両方の検証が通ればTrueを返し、いずれかの検証が失敗すればFalseを返す

証明者は自分のアドレスAと関連する鍵kを生成し、w=(A,k)をfのプライベート入力として提供します。彼らはチェーンから公共入力を取得し、現在の検証済み人間証明プロファイルのセット{H1…Hn}を取得します。彼らはZK-SNARK証明アルゴリズムを実行し、このアルゴリズムは（入力が正しいと仮定して）証明を生成します。証明者は証明を検証者に送信し、彼らが検証プロファイルリストを取得したブロックの高さを提供します。

検証者はチェーンを読み取り、証明者が指定した高さのリスト{H1…Hn}を取得し、証明を確認します。確認が通れば、検証者は証明者がいくつかの検証済み人間証明書を持っていると信じます。

より複雑な例について議論を続ける前に、上記の例を完全に理解するまで確認することを強くお勧めします。

メンバーシップ証明をより効率的にする

上記の証明システムの欠点は、検証者が全体のプロファイルセット{H1…Hn}を知っている必要があり、彼らはこのプロファイルセットをZK-SNARKメカニズムに「入力」するのにO(n)の時間を費やす必要があることです。

この問題を解決するために、すべてのプロファイルを含むチェーン上のMerkleルートを公共入力として使用します（これは単に状態ルートである可能性があります）。もう1つのプライベート入力、Merkle証明Mを追加し、証明者のアカウントAがツリーの関連部分に存在することを証明します。

ZKによるメンバーシップ証明の非常に新しく、より効率的な代替案はCaulkです。将来的には、これらのユースケースのいくつかがCaulkのようなスキームに移行する可能性があります。

ZK-SNARKと通貨

ZcashやTornado.cashなどのプロジェクトは、プライバシーを保護する通貨を持つことを可能にします。今、あなたは上記の「ZK人間証明」を使用できると思うかもしれませんが、それは人間証明プロファイルへのアクセスを証明するのではなく、通貨へのアクセスを証明するために使用されます。今、私たちはプライバシーと二重支払いの問題を同時に解決しなければなりません。つまり、私たちは通貨を二度使うべきではありません。

私たちは次のように解決します。通貨を持つすべての人にはプライベートな秘密「s」があります。彼らはローカルで「leaf」L=hash(s,1)を計算し、それがチェーン上に公開され、状態の一部となります。N=hash(s,2)を「nullifier」と呼びます。状態はMerkleツリーに保存されます。

通貨を使うために、送信者はZK-SNARKを作成しなければなりません。その中で：

• 公共入力にはnullifier N、現在または最近のMerkleルートR、新しい葉L'が含まれます（受取人が秘密s'を持ち、送信者にL' =hash(s',1)を渡すことを目的としています）
• プライベート入力には秘密s、葉L、およびMerkleブランチMが含まれます
• 検証機能は次のことをチェックします：
• Mが有効なMerkleブランチであり、LがルートRのツリーの葉であることを証明します。ここでRは現在の状態のMerkleルートです
• hash(s,1)=L
• hash(s,2)=N

トランザクションにはnullifier Nと新しい葉L'が含まれます。実際にはL'に関して何も証明しませんが、トランザクションが進行中に第三者によって変更されるのを防ぐためにそれを「混合」します。

トランザクションを検証するために、チェーンはZK-SNARKをチェックし、さらにNが以前の支出トランザクションで使用されていないかを確認します。トランザクションが成功すれば、Nは使用済みのnullifierセットに追加され、再利用できなくなります。L'はMerkleツリーに追加されます。

ここで、私たちはzk-SNARKを使用して2つの値を関連付けます。L（通貨が作成されたときにチェーン上に現れる）とN（通貨が消費されたときにチェーン上に現れる）であり、どのLがどのNに接続されているかを明らかにすることはありません。これら2つの値を生成する秘密sを知っている場合にのみ、LとNの間の関連性を発見できます。生成された各通貨は一度だけ使用できます（各Lに対して有効なNは1つだけであるため）が、特定の時間に使用される通貨は隠されています。

これは理解する必要がある重要な原語でもあります。以下で説明する多くのメカニズムは、目的は異なりますが、これに基づいています。

任意の残高の通貨

上記の状況は、任意の残高の通貨に簡単に拡張できます。「通貨」の概念を保持しつつ、各通貨には(プライベートな)残高が付随します。これを実現する簡単な方法は、各通貨がチェーンに保存されるようにし、葉Lだけでなく暗号化された残高も持つことです。

各トランザクションは2つの通貨を消費し、2つの新しい通貨を作成し、2つの対(葉、暗号化された残高)を状態に追加します。ZK-SNARKは、入力の残高の合計が出力の残高の合計と等しく、2つの出力の残高が非負であることも確認します。

ZK拒否サービス対策

興味深い拒否サービス対策の小道具です。あなたがいくつかのチェーン上のアイデンティティを持っていると仮定します。これは簡単に作成できるものではありません。人間証明プロファイルであったり、32のETHバリデーターであったり、単に非ゼロのETH残高を持つアカウントであったりします。私たちは、メッセージ送信者がプロファイルを持っていることを証明するメッセージのみを受け入れる方法を通じて、よりDoSに強いピアツーピアネットワークを作成できます。各プロファイルは、1時間あたり最大1000件のメッセージを送信することが許可され、送信者が不正を行った場合、送信者のプロファイルはリストから削除されます。しかし、私たちはどのようにプライバシーを保護するのでしょうか？

まず、設定です。kをユーザーの秘密鍵とし、A=privtoaddr(k)は対応するアドレスです。有効なアドレスのリストは公開されています（例えば、チェーン上の登録簿です）。ここまでのところ、これは人間証明の例に似ています：あなたはアドレスの秘密鍵を持っていることを証明しなければなりませんが、どのアドレスであるかは明らかにしてはいけません。しかし、ここでは、単にリストにいることを証明したいだけではありません。私たちは、あなたがリストにいることを証明できるプロトコルが必要ですが、あなたがあまりにも多くの証明を行うのを防ぎます。

私たちは時間をいくつかの期間に分けます：各期間は3.6秒続きます（したがって、1時間に1000の期間があります）。私たちの目標は、各ユーザーが各期間に1件のメッセージのみを送信できるようにすることです。ユーザーが同じ期間に2件のメッセージを送信した場合、彼らは捕まります。ユーザーが時折バーストメッセージを送信できるようにするために、彼らは最近の期間を使用できます。したがって、あるユーザーが500の未使用の期間を持っている場合、彼らはそれらの期間を使用して一度に500件のメッセージを送信できます。

プロトコル

私たちは、nullifierを使用した簡単なバージョンから始めます。ユーザーはN=hash(k,e)を持つnullifierを生成し、ここでkは彼らの鍵、eは期間番号です。そしてそれをメッセージmと一緒に公開します。ZK-SNARKは再びhash(m)を混合し、この過程でmに関する検証は行わないため、証明は単一のメッセージにバインドされます。ユーザーが同じnullifierを使用して2つの証明を2つの異なるメッセージにバインドした場合、彼らは捕まる可能性があります。

さて、私たちはより複雑なバージョンに移ります。この場合、次のプロトコルは彼らの秘密鍵を暴露します。単に誰かが同じ期間を2回使用したかどうかを証明するのではなく、私たちのコア技術は「2点が1本の線を構成する」というテクニックに依存します：あなたが1本の線上に1点を示すと、あなたは非常に少ない情報を示しますが、あなたが1本の線上に2点を示すと、あなたはその線全体を示します。

各期間eについて、私たちは直線Le(x)=hash(k,e)∗x+kを取ります。直線の傾きはhash(k,e)、y切片はkです；どちらも公には知られていません。メッセージmのために証明書を作成するために、送信者はy=Le(hash(m))=hash(k,e)∗hash(m)+kを提供し、yの計算が正しいことを証明するZK-SNARKを提供します。

要約すると、ZK-SNARKは次のようになります：

公共入力:

• {A1…An}、有効なアカウントのリスト
• M、証明書が検証されているメッセージ
• E、証明書の期間番号
• Y、線関数の評価

プライベート入力:

• K、あなたの秘密鍵

検証機能:

• privtoaddr(k)が{A1…An}にあるかどうかをチェック
• y=hash(k,e)∗hash(m)+kをチェック

しかし、誰かが1つの期間を2回使用した場合はどうでしょうか？これは、彼らが2つの値m1とm2および対応する証明値y1=hash(k,e)∗hash(m1)+kとy2=hash(k,e)∗hash(m2)+kを公開したことを意味します。私たちはこれらの2点を使用して直線を復元できるため、y軸切片（これは秘密鍵です）を得ることができます：

したがって、誰かが1つの期間を再利用すると、彼らは秘密鍵を漏らし、誰もがそれを見ることができます。状況によっては、これは資金が盗まれることを意味するかもしれませんし、単に秘密鍵が放送され、スマートコントラクトに含まれることを意味するかもしれません。この場合、対応するアドレスは集合から削除されます。

ブロックチェーンのピアツーピアネットワーク、チャットアプリケーションなどのシステムに適した実行可能なオフチェーン匿名拒否サービスシステムは、作業証明を必要としません。RLNプロジェクトは、基本的にこのアイデアを構築していますが、少しの修正が加えられています（つまり、彼らは同時にnullifierと2点線技術を使用しており、nullifierを使用する方が期間の二重使用の問題を捕まえるのが容易です）。

ZKの悪評

私たちが完全に匿名のネットワークフォーラムを提供する0chanを構築したいと仮定します（あなたは永続的な名前すら持たない）、しかし、より高品質のコンテンツを奨励するための評判システムがあります。これは、いくつかの監査DAOがシステムのルールに違反する投稿をマークし、三振ルールを確立するシステムかもしれません。

評判システムは正の評判または負の評判をサポートできます。しかし、負の評判をサポートするには追加のインフラが必要で、ユーザーが証明の中ですべての評判情報を考慮することを要求します。たとえそれが負のものであっても。私たちは、このより難しいユースケースに焦点を当てます。これは、Unirep Socialが実現しようとしているユースケースに似ています。

リンク投稿：基礎知識

誰でも、メッセージとZK-SNARKを含む投稿をチェーン上に公開することで投稿を行うことができ、(i) あなたがアカウントを作成する権限を与えるいくつかの希少な外部アイデンティティを持っていること、または (ii) あなたが特定の投稿を行ったことを証明します。具体的には、ZK-SNARKは次のようになります：

• 公共投入
• nullifier N
• 最近のブロックチェーン状態ルートR
• 投稿内容（「混合」して証明にバインドしますが、計算は行いません）

プライベート入力:

• あなたの秘密鍵k
• 外部アイデンティティ（アドレスA）、または前の投稿で使用されたnullifier Nprev
• Merkle証明MがAまたはNprevがチェーン上に含まれていることを証明します
• あなたがこのアカウントを使用して以前に投稿したi番目の投稿

検証機能:

• Mが有効なMerkleブランチであることを確認し、（AまたはNprev、提供者に応じて）Rの根を持つツリーの葉であることを証明します
• N=enc(i,k)を確認します。ここでencは暗号化関数です（例：AES）
• i=0の場合、A=privtoaddr(k)を確認し、そうでない場合はNprev=enc(i−1,k)を確認します

証明を検証するだけでなく、チェーンは2つの側面も確認します：(i) Rが実際に最近の状態ルートであること、(ii) nullifier Nがまだ使用されていないこと。ここまでのところ、これは前述のプライバシーを保護する通貨と同じですが、私たちは新しいアカウントを「鋳造」するプロセスを追加し、あなたのアカウントを異なる鍵に「送信」する能力を削除しました。------ 代わりに、すべてのnullifierは元の鍵を使用して生成されます。

私たちはここでencを使用してnullifierを可逆にし、hashではなくします：もしあなたがkを持っていれば、チェーン上の特定のnullifierを解読でき、その結果がランダムなゴミではなく有効なインデックスである場合（例えば、dec(N)<264を確認できます）、あなたはnullifierがkを使用して生成されたことを知ることができます。

評判を追加する

このスキームでは、評判はチェーン上にあり、明示的です：いくつかのスマートコントラクトには、投稿とともにnullifierを持ち、加減する評判単位の数を入力として受け取るaddReputationメソッドがあります。

私たちは、各投稿に保存されるチェーン上のデータを拡張しました：私たちは{N,h¯,u¯}を保存します。nullifier Nだけでなく、次のようにします：

• h¯=hash(h,r) ここでhは証明で参照される状態ルートのブロック高さです
• u¯=hash(u,r) ここでuはアカウントの評判スコア（新しいアカウントは0です）

ここでのRは単なるランダム値であり、追加することでhとuが強制的に検索されるのを防ぎます（暗号学的用語で、Rを追加することでハッシュが隠れたコミットメントになります）。

投稿がルートRを使用し、{N,h¯,u¯}を保存すると仮定します。証明の中で、以前の投稿にリンクし、データ{Nprev,h¯prev,u¯prev}を保存します。投稿の証明は、hprevとhの間に投稿されたすべての評判エントリを横断する必要があります。各nullifier Nについて、検証機能はユーザーの鍵kを使用してNを解読し、解読結果が有効なインデックスであれば、評判の更新を適用します。すべての評判更新の合計がδであれば、最終的な証明はu=uprev+δとなります。

もし私たちが「三振ルール」を望むなら、ZK-SNARKはu>−3も確認します。もし私たちが「投稿のrep≥100」の場合、その投稿が特別な「高評判投稿」ラベルを取得できるというルールを望むなら。

スキームのスケーラビリティを向上させるために、私たちはそれを2つのメッセージのカテゴリに分けることができます：投稿とRCA。投稿はオフチェーンになりますが、過去1週間に作成されたRCAを指す必要があります。RCAはチェーン上にあり、RCAはその投稿者の以前のRCA以来のすべての評判更新を横断します。この方法で、チェーン上の負荷は、各投稿ごとに週に1回のトランザクションと各評判メッセージごとのトランザクションに減少します。

中央集権的な当事者に責任を持たせる

時には、何らかの中央集権的「オペレーター」を持つスキームを構築する必要があります。その背後には多くの理由があります：時にはスケーラビリティのため、時にはプライバシーのため（具体的には、オペレーターが保持するデータのプライバシーのため）です。

例えば、MACIは投票者がチェーン上で投票を提出し、中央集権的オペレーターが保持する鍵に暗号化することを要求する投票システムに対抗します。オペレーターはチェーン上のすべての投票を解読し、カウントし、最終結果を表示し、同時にZK-SNARKを使用して彼らが行ったすべてが正しいことを証明します。この追加の複雑さは、強力なプライバシー（強制抵抗と呼ばれる）を確保するために非常に必要です：ユーザーは他の人に自分がどのように投票したかを証明できません。たとえ彼らがそうしたいと思っても。

ブロックチェーンとZK-SNARKのおかげで、私たちはオペレーターに対する信頼度を非常に低いレベルに保つことができます。悪意のあるオペレーターは依然として強制抵抗を破ることができますが、投票がブロックチェーン上に公開されているため、オペレーターは投票を検閲することで不正を行うことができず、オペレーターはZK-SNARKを提供しなければならないため、結果を誤って計算することで不正を行うこともできません。

ZK-SNARKとMPCを組み合わせる

ZK-SNARKのより高度な使用は、計算において証明を行うことに関係しています。ここでの入力は2者または多者間で分配され、私たちはどの当事者も他の当事者の入力を学ぶことを望んでいません。2者の場合、あなたは暗号化回路を使用してプライバシー要件を満たすことができますが、N者の場合は、より複雑な多者計算プロトコルを使用してプライバシー要件を満たすことができます。ZK-SNARKはこれらのプロトコルと組み合わせて検証可能な多者計算を行うことができます。

これにより、複数の参加者が彼らのプライベート入力に基づいて共同計算を実行できるより高度な評判システムが可能になります。現在、これを効果的に実現するための数学的計算はまだ比較的初期段階にあります。

私たちは何をプライベートにすることができないのか？

ZK-SNARKは、ユーザーがプライベートな状態を持つシステムを作成するのに非常に効果的です。しかし、ZK-SNARKは誰も知らないプライベートな状態を保持することはできません。情報の一部を証明するには、証明者がその情報を平文で知っている必要があります。

Uniswapは、プライベート化が難しい例の1つです。Uniswapには、ロジカルに中心的な「もの」があります。それはマーケットメイカーアカウントであり、誰のものでもありません。Uniswap上のすべての取引はマーケットメイカーアカウントとの取引です。あなたはマーケットメイカーアカウントの状態を隠すことはできません。なぜなら、その場合、誰かがその状態を平文で保持して証明する必要があり、各取引には彼らの積極的な参加が必要だからです。

あなたはZK-SNARKの暗号化回路を使用して、中央集権的な操作の安全でプライベートなUniswapを作成することができますが、誰もがその利点がそれを実行するために必要なコストを相殺できるかどうかは不明です。これは実際には何の実質的な利益ももたらさないかもしれません：契約はユーザーに資産の価格が何であるかを伝える必要があり、ブロックごとの価格変動はユーザーに取引活動が何であるかを伝えることができます。

ブロックチェーンは状態情報をグローバル化し、ZK-SNARKは状態情報をプライベート化しますが、私たちは本当に状態情報をグローバル化しながらプライベート化するための良い方法を持っていません。

原語をまとめる

上記の小節では、強力で有用なツールのいくつかの例を見ましたが、それらは他のアプリケーションの構築ブロックとしても機能します。たとえば、nullifierは通貨にとって重要であり、現在では他のユースケースでも繰り返し現れています。

負の評判部分で使用される「強制リンク」技術は非常に広範囲に適用可能です。これは、ユーザーの「プロファイル」が時間とともに複雑に変化する多くのアプリケーションに非常に効果的であり、ユーザーがシステムのルールを遵守することを強制しつつプライバシーを保護したい場合に役立ちます。ユーザーは、彼らの内部「状態」を完全なプライベートMerkleツリーで表現することを要求されることさえあります。この記事で提案された「コミットメントプール」小道具は、ZK-SNARKを使用して構築できます。特定のアプリケーションが完全にオンチェーンで実行できず、中央集権的なオペレーターを持つ必要がある場合、全く同じ技術を使用してオペレーターの誠実さを維持することもできます。

ZK-SNARKは非常に強力なツールであり、責任とプライバシーの利点を結びつけています。同時に、それらには限界もありますが、特定の状況では巧妙なアプリケーション設計がこれらの制限を回避できることがあります。私は、より多くのアプリケーションがZK-SNARKを使用し、最終的には今後数年内にZK-SNARKと他の形式の暗号を組み合わせたアプリケーションが構築されることを期待しています。