Geekly Articles each Day

例付きzk-SNARKの概要（翻訳）

こんにちは、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を使用する方法の実用的な例を示しています。 これに基づいて信頼性の高いシークレットトランザクションスキームを作成するには、いくつかの問題を解決する必要があります。




Source: https://habr.com/ru/post/J342262/

More articles:


All Articles