こんにちは、Habr！ クリスチャン・ルンドクヴィストの例を含む記事「 zk-SNARKの紹介 」の翻訳を紹介します。
この記事では、実用的な観点からzk-SNARKの概要を説明します。 ブラックボックスとして使用される数学を検討しますが、このテクノロジーの使用方法を理解するために少し直感を示し、 Ethereumでのzk-SNARKの最近の統合に基づいた簡単なアプリケーションを示します。
ゼロ開示証拠
ゼロ開示証拠の目的は、審査官が他の誰にも証拠を開示することなく、審査官が何らかの関係を満たす証拠と呼ばれる秘密パラメータの知識を持っていることを検証できるようにすることです。
詳細に移ると、 C(x, w)
2つのパラメーターを取るC
で示されるプログラムがあると想像してください。 パラメータx
は公開値で、 w
は証拠の秘密値です。 プログラムはブール値、つまりtrue
またはfalse
返します。 目標は、 C(x,w) == true
ように、受験者がw
の秘密の値を知っていることを確認できるように、 x
そのような公開値を取得することC(x,w) == true
。
具体的には、非開示の非対話型エビデンスについて説明します。これは、エビデンス自体が検証可能なデータとの対話なしに検証可能なデータのブロックであることを意味します。
プログラム例
ボブが何らかの値のハッシュH
を取得し、アリスがハッシュがH
等しいs
の値を知っていることの証明を得たいとしますH
通常、アリスはs
ボブに与えることでこれを証明します。その後、ボブはハッシュを計算し、 H
と等しいことを確認しますH
ただし、アリスがボブの価値のあるs
値を明らかにしたくない場合、代わりに、彼女は単にその値を知っていることを証明したいだけです。 このために、彼女はzk-SNARKを使用できます。
Javascript関数として以下に説明する次のプログラムを使用して、このシナリオを説明できます。
function C(x, w) { return ( sha256(w) == x ); }
つまり、プログラムは公開ハッシュx
と秘密値w
を取得し、SHA-256ハッシュw
がx
と等しい場合にtrue
を返しtrue
。
関数C(x,w)
を使用してアリスの問題を説明すると、アリスはs
の値を明らかにせずにC(H, s) == true
であるという証明を作成する必要があることがわかります。 これは、zk-SNARKが解決する一般的な問題です。
zk-SNARKの定義
ジェネレーター（C回路、λは️）：
（pk、vk）= G（λ、C）
証明者（x pub inp、w sec inp）：
π= P（pk、x、w）
検証者：
V（vk、x、π）==（∃w st C（x、w））
ツイートで与えられた定義:)
Zk-SNARKは、次のように定義された3つのアルゴリズムG, P, V
されています。
鍵生成プログラムG
は、秘密パラメーターlambda
およびプログラムC
受け入れ、2つの公開鍵（証明鍵pk
および検証鍵vk
ます。 これらのキーは、特定のC
プログラムに対して1回だけ作成する必要がある公開パラメーターです。
証明アルゴリズムP
は、キーpk
、公開値x
および秘密値w
を入力として受け取ります。 アルゴリズムは、証明prf = P(pk, x, w)
がw
の秘密値を知っており、秘密値がプログラムC
満たすという証明prf = P(pk, x, w)
を生成しますC
テストアルゴリズムV
V(vk, x, prf)
を計算しtrue
これは、証明が真の場合に真になり、そうでない場合にfalse
ます。 したがって、 w
の秘密値がC(x,w) == true
満たしていることを検証者が知っている場合、この関数はtrue
返しC(x,w) == true
。
ジェネレーターで使用される秘密パラメーターlambda
注意してください。 このオプションにより、実際のアプリケーションでzk-SNARKを使用することが困難になる場合があります。 この理由は、このパラメーターを知っている人はだれでも偽の証拠を生成できるからです。 特に、任意のC
プログラムとパブリック値x
lambda
は知っているが秘密w
は知らない人は、アルゴリズムV(vk, x, fake_prf)
がtrue
を返す証明fake_prf
作成できます。
したがって、ジェネレーターの起動は、誰かがlambda
パラメーターを認識または盗む可能性から保護された安全なプロセスでなければなりません。 これが、Zcashチームがエビデンスキーと検証キーを作成する非常に複雑なセレモニーの理由であり、 lambda
すべての「有害廃棄物」が破壊されました。
サンプルプログラム用のZk-SNARK
アリスとボブは実際にzk-SNARKをどのように使用して、アリスが上記の例で秘密の意味を知っていることを証明するでしょうか？
まず、上で説明したように、次の関数で定義されたプログラムを使用します。
function C(x, w) { return ( sha256(w) == x ); }
最初のステップとして、ボブはジェネレータGを実行して、証明キーpk
および検証キーvk
を作成します。 これは、 lambda
をランダムに生成し、この値を入力として使用して行われます。
(pk, vk) = G(C, lambda)
上記で説明したように、Aliceがlambda
認識すると、偽の証拠を作成できるため、 lambda
パラメーターは細心の注意を払って処理する必要があります。 次に、ボブはpk
とvk
をアリスと共有します。
これで、アリスが証明者の役割を果たします。 彼女は、ハッシュがH
であるs
秘密値を知っていることを証明する必要がありますH
彼女は入力pk, H s
を使用して校正アルゴリズムP
を実行し、prfの証明を生成します。
prf = P(pk, H, s)
次に、アリスはprf
の証明prf
ボブに提示し、彼は検証関数V(vk, H, prf)
を実行します。アリスはs
秘密の値を本当に知っているため、この場合true
を返しtrue
。 これで、ボブはアリスが秘密の値を知っていることを確信できますが、アリスはボブに秘密を明かす必要はありませんでした。
再利用可能なチェックと証拠キー
上記の例では、ボブが秘密の値を知っていることをアリスに証明したい場合、zk-SNARKは使用できません。 これは、AliceがBobがlambda
パラメーターを保存しなかったことを確認できないため、Bobが証拠を偽造できるためです。
プログラムが多くの人（Zcashなど）で使用されている場合、AliceとBobとは別に、信頼できる独立したグループがジェネレーターを起動し、証明キーpk
および検証キーvk
を作成して、だれもlambda
パラメーターを知らないようにすることができます。
このグループを信頼する人は誰でも、これらのキーを将来の対話に使用できます。
イーサリアムのzk-SNARK
開発者はすでにzk-SNARKをイーサリアムに統合し始めています 。 どのように見えますか？ 検証アルゴリズムブロックは、プリコンパイルされたコントラクトとしてイーサリアムに追加されます。 以下が使用されます：ジェネレーターはブロックチェーンの外側で実行され、証拠キーと検証キーを作成します。 その後、証明者は誰でも、ネットワーク外でも証拠キーを使用して証拠を作成できます。 次に、一般的な検証アルゴリズムは、入力パラメーターとして証明、検証キー、および公開値を使用して、スマートコントラクト内で実行できます。 検証アルゴリズムの結果を使用して、ブロックチェーン上の他のアクションを開始できます。
例：機密取引
以下は、zk-SNARKがイーサリアムのプライバシーにどのように役立つかを示す簡単な例です。 単純なトークンコントラクトがあるとします。 通常、トークンコントラクトには、住所と残高のマッピングが含まれます。
mapping (address => uint256) balances;
基本コアを保持しますが、残高を残高のハッシュに置き換えます。
mapping (address => bytes32) balanceHashes;
トランザクションの送信者または受信者を非表示にするつもりはありませんが、残高と送信金額を非表示にすることができます。 これは、機密取引と呼ばれることもあります。
1つのアカウントから別のアカウントにトークンを送信するために2つのzk-SNARKが使用され、1つの証明が送信者によって作成され、1つの証明が受信者によって作成されます。
通常、サイズがvalue
であるトランザクションのトークンコントラクトでは、次の条件を確認する必要があります。
balances[fromAddress] >= value
したがって、zk-SNARKが条件が満たされていることを証明し、更新されたハッシュが更新された残高に対応することを確認する必要があります。
主なアイデアは、送信者が自分の初期残高と取引値を秘密の値として使用し、初期、最終残高と取引値のハッシュを公開値として使用することです。 同様に、受信者は初期残高とトランザクションコストを秘密の値として使用し、初期、最終残高とトランザクション値のハッシュを公開値として使用します。
以下は、送信者zk-SNARKに使用するプログラムです。以前のように、 x
はパブリック値を表し、 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 ) }
受信者が使用するプログラムは次のとおりです。
function receiverFunction(x, w) { return ( sha256(w.value) == x.hashValue && sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore && sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter ) }
プログラムは、送信者の残高が送信される値よりも大きいことを確認し、すべてのハッシュが一致することも確認します。 信頼できる人々のコミュニティが、ZK-SNARKの証明キーと検証キーを生成します。それらを示しましょう： confTxSenderPk, confTxSenderVk, confTxReceiverPk confTxReceiverVk
。
トークンコントラクトでzk-SNARKを使用すると、次のようになります。
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-SNARKを使用する方法の実用的な例を示しています。 これに基づいて信頼性の高いシークレットトランザクションスキームを作成するには、いくつかの問題を解決する必要があります。
- ユーザーはクライアント側で残高を追跡する必要があります。残高を失うと、これらのトークンを復元できなくなります。 おそらく、残高は、署名キーを使用して取得したキーを使用して、暗号化された形式でブロックチェーンに保存できます。
- バランスは、32バイトのデータを使用し、バランス部分でエントロピーをエンコードして、バランス値の計算にハッシュが選択されないようにする必要があります。
- 未使用のアドレスに送信された場合の対処方法を決定する必要があります。
- 送信するには、送信者は受信者と対話する必要があります。 送信者が証拠を使用してトランザクションを開始し、受信者がブロックチェーン上で「保留中の着信トランザクション」があることを確認して完了するシステムを作成できます。