zk-SNARKs の紹介

本文オープンソースリポジトリのアドレス

本文は Consensys から翻訳されました。

翻訳者：@BoxMrChen

この記事では、実用的な観点から zk-SNARKs の概要を説明することを目的としています。私たちは、実際の数学的問題をブラックボックスとして扱い、それをどのように利用して直感を発展させるかを考えます。また、イーサリアムに zk-SNARKs を統合する最近の作業に関する簡単なアプリケーションを示します。

ゼロ知識証明#

ゼロ知識証明の目的は、検証者が証明者がある関係を満たす秘密のパラメータ、すなわち「証人」を把握していると確信できるようにすることです。これを検証者や他の誰にも明らかにすることなく行います。

これをより具体的に考えると、プログラム C が二つの入力を受け取ります： C(x, w)。入力 x は公開入力であり、w は秘密の証人入力です。プログラムの出力は真偽値、つまり true または false です。したがって、特定の公開入力 x が与えられたとき、証明者が秘密入力 w を知っていることを証明することが目標です。すなわち、 C(x,w) == true となるような w を証明します。

私たちは非対話型ゼロ知識証明について特に議論します。これは、証明自体が証明者との相互作用なしに検証できるデータの塊であることを意味します。

サンプルプログラム#

ボブがある値のハッシュ H を取得し、アリスがハッシュが H である値 s を知っていることを証明する証拠が欲しいとします。通常、アリスはボブに s を提供することでこれを証明し、ボブはハッシュを計算してそれが H と等しいかどうかを確認します。

しかし、アリスが s の値をボブに明かしたくない場合、彼女はその値を知っていることを証明したいだけです。彼女は zk-SNARK を使用してこれを実現できます。

以下のプログラムを使用してアリスの状況を説明できます。ここでは JavaScript 関数の形式で記述します：

function C(x, w) {  return ( sha256(w) == x );}

このプログラムは ZK の内容には関与しておらず、私たちが達成したい効果がどのようなものであるかを示すためのものです。私たちはこれをブラックボックスとして扱い、次のセクションで zk-SNARKs を使用してこのようなプログラムを構築する方法を議論します。

言い換えれば、このプログラムは公開ハッシュ x と秘密値 w を受け取り、w の SHA-256 ハッシュが x と等しい場合に true を返します。

アリスの問題を関数 C(x,w) を通じて翻訳すると、アリスは s を持っていることを証明するための証明を作成する必要があることがわかります。すなわち、 C(H, s) == true であることを証明し、s を明らかにすることなく行います。これが zk-SNARKs が解決する一般的な問題です。

zk-SNARK の定義#

zk-SNARK は、次のように定義される三つのアルゴリズム G, P, V から構成されます：

鍵生成器 G は、秘密パラメータ lambda とプログラム C から構成され、二つの公開可能な鍵を生成します。一つは proving key pk（証明鍵）、もう一つは verification key vk（検証鍵）です。これらの鍵は公開パラメータであり、プログラム C を使用して一度生成するだけで済みます。

証明者 P は、証明鍵 pk、公開入力 x、および証人 w を入力として受け取ります。このアルゴリズムは、証明者が証人 w を知っており、その証人がプログラムの要件を満たしていることを証明するための証明 prf = P(pk, x, w) を生成します。

検証者 V は V(vk, x, prf) を計算し、証明が正しい場合は true を返し、そうでない場合は false を返します。したがって、証明者が C (x,w) == true を満たす証人 w を知っている場合、この関数は真を返します。

生成器で使用される秘密パラメータ lambda に注意してください。このパラメータは、現実世界のアプリケーションで zk-SNARKs を使用する際に厄介になることがあります。理由は、このパラメータを知っている人は誰でも偽の証明を生成できるからです。具体的には、任意のプログラム C と公開入力 x が与えられた場合、lambda を知っている人は、秘密 w を知らなくても V(vk, x, fake_prf) が true になるような証明 fake_prf を生成できます。

したがって、生成器を実行するには、誰もパラメータを知って保存しないようにする非常に安全なプロセスが必要です。これが、Zcash チームが証明鍵と検証鍵を生成するために非常に複雑な儀式を行い、「有毒廃棄物」lambda がその過程で破棄されることを保証する理由です。

サンプルプログラムに対する zk-SNARK#

実際の操作において、アリスとボブはどのように zk-SNARK を使用してアリスが上記の例の秘密値を知っていることを証明するのでしょうか？まず、前述のように、次の関数で定義されたプログラムを使用します：

function C(x, w) {
  return sha256(w) == x;
}

まず、ボブは生成器 G を実行して証明鍵 pk と検証鍵 vk を作成する必要があります。最初に、lambda をランダムに生成し、それを入力として使用します：

(pk, vk) = G(C, lambda)

lambda パラメータを慎重に扱ってください。アリスが lambda の値を知っている場合、彼女は偽の証明を作成できるようになります。ボブはアリスと pk および vk を共有します。

アリスは今、証明者の役割を果たします。彼女は、ハッシュ値が既知のハッシュ H である値 s を知っていることを証明する必要があります。彼女は証明アルゴリズム P を実行し、入力 pk、H、および s を使用して証明 prf を生成します：

prf = P(pk, H, s)

次に、アリスは証明 prf をボブに提示し、ボブは検証関数 V(vk, H, prf) を実行します。この場合、アリスが秘密 s を正しく知っているため、真を返します。ボブはアリスがこの秘密を知っていることを確信できますが、アリスはボブにこの秘密を明かす必要はありません。

再利用可能な証明と検証鍵#

上記の例では、ボブがアリスに秘密を知っていることを証明したい場合、彼は zk-SNARK を使用できません。なぜなら、アリスはボブが lambda パラメータを保持しているかどうかを知ることができないからです。ボブは証拠を偽造する可能性があります。

あるプログラムが多くの人にとって有用である場合（例えば Zcash の例）、アリスとボブとは独立した信頼できる独立チームが生成器を実行し、証明鍵 pk と検証鍵 vk を作成できます。このようにして、誰も lambda を知ることはありません。

そのチームが不正を行っていないと信じる人は、将来の相互作用でこれらの鍵を使用できます。

イーサリアムにおける zk-SNARKs#

開発者たちは、zk-SNARKs をイーサリアムに統合し始めています。これはどのようなものになるのでしょうか？具体的には、検証アルゴリズムの構成モジュールをプリコンパイルされたコントラクトの形式でイーサリアムに追加できます。具体的な手順は次のとおりです：オフチェーンで生成器を実行し、証明鍵と検証鍵を生成します。次に、任意の証明者は証明鍵を使用して証明を作成し、これもオフチェーンで行います。その後、スマートコントラクト内部で一般的な検証アルゴリズムを実行し、証明、検証鍵、および公開入力を入力パラメータとして使用します。次に、検証アルゴリズムの結果を使用して、他のオンチェーン活動をトリガーできます。

例：秘密取引#

以下は、zk-SNARKs がイーサリアムのプライバシーを向上させる方法を示す簡単な例です。単純なトークンコントラクトがあると仮定します。通常、トークンコントラクトのコアはアドレスを残高にマッピングすることです：

mapping (address => uint256) balances;

私たちは同じ基本コアを保持しますが、残高を残高のハッシュ値に置き換えます：

mapping (address => bytes32) balanceHashes;

取引の送信者や受信者は隠しませんが、残高や送信された金額は隠します。この特性は時折秘密取引と呼ばれます。

私たちは、トークンをあるアカウントから別のアカウントに送信するために二つの zk-SNARKs を使用します。送信者と受信者はそれぞれ証明を作成します。

通常、トークンコントラクトでは、サイズ値の取引を有効にするために、次の内容を検証する必要があります：

balances[fromAddress] >= value

私たちの zk-SNARKs は、これが成り立つことを証明し、更新されたハッシュ値が更新された残高と一致することを証明する必要があります。

主な考え方は、送信者が 初期残高 と値をプライベートデータとして使用することです。初期残高、終了残高、および 値のハッシュ を公開データとして使用します。同様に、受信者は 初期残高 と値をプライベートデータとして使用し、初期残高、終了残高、および 値のハッシュ を公開データとして使用します。

以下は送信者の zk-SNARK プログラムで、ここで x は公開データ、w はプライベートデータを表します。

/**
 * @param x 公開データ
 * @param w プライベートデータ
 */
function senderFunction(x, w) {
  return (
    w.senderBalanceBefore > w.value && // 送信者が十分な残高を持っていることを確認
    sha256(w.value) == x.hashValue && // 送信された値が公開のハッシュ値と一致することを確認
    sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore && // 送信者の初期残高が公開のハッシュ値と一致することを確認
    sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter // 送信者の終了残高が公開のハッシュ値と一致することを確認
  );
}

受信者の zk-SNARK プログラムは次のとおりです：

/**
 * @param x 公開データ
 * @param w プライベートデータ
 */
function receiverFunction(x, w) {
  return (
    sha256(w.value) == x.hashValue &&
    sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
    sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
  );
}

これらのプログラムは、送信残高が送信される値より大きいことを確認し、すべてのハッシュが一致することを確認します。一組の信頼できる人々が私たちの zk-SNARKs のために証明と検証鍵を生成します。これらを confTxSenderPk、confTxSenderVk、confTxReceiverPk、および confTxReceiverVk と呼びます。 confTxSenderPk と confTxReceiverPk は証明を生成するために使用され、 confTxSenderVk と confTxReceiverVk は証明を検証するために使用されます。

トークンコントラクトで zk-SNARKs を使用する場合は次のようになります：

function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
  bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
  bytes32 hashReceiverBalanceBefore = balanceHashes[_to];

  bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);

bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);

  if(senderProofIsCorrect && receiverProofIsCorrect) {
    balanceHashes[msg.sender] = hashSenderBalanceAfter;
    balanceHashes[_to] = hashReceiverBalanceAfter;
  }
}

したがって、ブロックチェーン上で唯一更新されるのは残高のハッシュ値であり、残高そのものではありません。しかし、すべての残高が正しく更新されたことを確認できます。なぜなら、私たちは証明が検証されたことを自分で確認できるからです。

上記の例からもわかるように、ブロックチェーン上では残高のハッシュのみを保存し、実際の残高を公開しないことでデータの秘密性を保ちます。私たちは二者間で取引が行われたことは知っていますが、具体的な取引金額はわからないため、取引のプライバシーが保証されます。

詳細情報#

上記の秘密取引のスキームは、イーサリアム上で zk-SNARKs を使用する方法を示す実際の例を提供することを目的としています。健全な秘密取引スキームを作成するには、いくつかの問題を解決する必要があります：

ユーザーはクライアントで残高を追跡する必要があります。残高データを失うと、そのアカウントの制御を失います。残高は自己署名鍵の鍵で暗号化し、チェーン上に保存できるかもしれません。
残高は 32 バイトのデータを使用し、エントロピーをエンコードして、ハッシュを逆解析して残高を計算するのを防ぐ必要があります。
未使用アドレスへの送信に関するエッジケースを処理する必要があります。
送信者は受信者と対話して送信する必要があります。送信者が証明を使用して取引を開始できるシステムがあるかもしれません。その後、受信者はブロックチェーン上で「保留中の入金取引」があることを確認し、それを完了できます。