ブロックチェーンにおける VRF の応用と原理分析
黄琦
Tarax Network の共同創設者兼 CTO
コンピューター サイエンスの修士号を取得したシニア フルスタック エンジニアで、主な研究方向は分散システムと P2P 自己組織化ネットワークです。
画像の説明
中国科学院計算技術研究所知能科学グループ、ソニー中国研究所、百度、頭条などで分散データ共有に関する技術研究に従事。
今日私が皆さんにお届けする共有は、「ブロックチェーンにおける VRF のアプリケーションと原理分析」と呼ばれるもので、これは私たちのチームが取り組んでいる Tarax Network と呼ばれるパブリック チェーンから生まれました。シーンの位置決めのために、低消費電力で合意を達成する方法を見つけたいと考えています。そうするとPOWは考えなくていいし、POSを考えるのは簡単です。次に、POW であれ POS であれ、ブロックをパッケージ化することが予測できないノードをランダムに見つけて、このブロックをネットワーク全体で認識させたいと考えます。
次に、ランダム選択に関して言えば、VRF は検証可能なランダム選択に基づいて抽選を行う最も直接的な方法です。
もちろん、POWには包装用のポイントをランダムに選択する機能があるだけでなく、ゲーム性や人間性も考慮されています。現在のPOSスキームでは、ポイントをランダムに選択した後はOKではなく、ランダムなポイント選択スキームの代わりに, 当然、ゲームや人間性の問題も他の側面から再設計されます。
でもまずは問題を一つずつ解決して、ゲームの内容はさておき、まずはVRFの勉強をしましょう。
これを 2 つの質問から見ていきます。
1. 検証可能なランダム関数とは何ですか?
2. 現在の一部のチェーン スキームは検証可能なランダム関数をどのように使用していますか?
検証可能なランダム関数とは検証可能なランダム関数は次のように考えることができます。ランダムオラクル
これは、任意の入力を通じて乱数出力を取得できることを意味します。
1. 異なる入力の場合、出力値はランダムであり、値の範囲内で均等に分布します。
2. 同じ入力の場合、取得する出力も同じでなければなりません。
ただし、検証可能なランダム関数には、ランダム オラクルよりも非対話型のゼロ知識証明が 1 つあり、乱数出力の正確性を検証するために使用でき、乱数が実際に誰かによって生成されたことを示します。
検証可能なランダム関数 4 つの関数が含まれています。
1. キーを生成し、公開キーと秘密キーのペアを生成します。これについては後で詳しく説明しません。
2. 乱数出力を生成する
3. 計算によるゼロ知識証明
4. 乱数出力を検証する
乱数の生成とその証明のプロセスはローカルで実行され、入力は秘密キーと値です。出力は乱数とそのゼロ知識証明です。
では、これら 4 つの関数とその出力を通じて、点をランダムに選択するにはどうすればよいでしょうか?
文章
検証可能なランダム関数の描画
最も単純な方法は、上記の VRF を通じて乱数値を生成した後、ネットワーク全体で認識されるしきい値を設定して、それが選択されるかどうかを決定できます。たとえば、値 100 がしきい値であることに全員が同意するとします。あるラウンドで101を獲得すると、次のステップに進むことができました。
ただし、この最も単純な解決策には Sybil 攻撃を防ぐ方法はありません。したがって、現在の VRF 宝くじスキームのほとんどは、権利と利益に基づいて投票を割り当て、その後、宝くじアルゴリズムを設計します。
ここで、最も一般的な解決策を見てみましょう。それは、二項分布を通じて宝くじの結果を計算することです。まず、秘密鍵を介して値を生成しましたが、この値は実際には大きな正の整数とみなすことができ、256 ビットと仮定すると、その値の範囲は 0 から 2 の 256 乗の間になります。それに対応する
2 の 256 乗で割ると、0 ～ 1 の値が得られます。
この値を二項分布の累積分布に入れて比較すると、対応する値が得られます (詳細については PPT を参照)。
この値が 0 より大きい場合、次のステップに進むことができる宝くじを引いたのと同じになります。
この値を、以前の VRF によって生成された合計とともに他のユーザーにブロードキャストすると、受信した他のユーザーは、次の 2 つの条件が真であるかどうかを確認できます。
1. 検証が正しいかどうか
1. 抽選にはVRFを使用する必要がありますか?
ランダムオラクルと比べてどうですか？
2. 他の応用シナリオはありますか?
皆さん、ありがとうございました。
Verifiable Random Functions [1999]
Ouroboros: A provably secure proof-of-stake blockchain protocol [2017] Algorand:
Scaling Byzantine Agreements for Cryptocurrencies [2017]
Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of- stake blockchain [2018]
https://github.com/iost-official/Documents/blob/master/ Technical_White_Paper/EN/Tech_white_paper_EN.md
https://tools.ietf.org/html/draft-irtf-cfrg-vrf-02
https://github.com/Realiserad/fts-tree
https://www.cs.bu.edu/~goldbe/projects/vrf
2. 二項分布関数を使用して、j' が j に等しいかどうかを取得します。
両方の条件が真であると仮定すると、宝くじの結果が正しく、信頼できることが証明されます。
ここまでで、宝くじの生成から検証までのプロセスが完了しました。
上記のプロセスの説明を通じて、VRF ベースの抽選メカニズムにはいくつかの利点があることがわかります。
1. まず、その抽選プロセスは他者と通信する必要がなく、抽選結果はマシン上で直接取得でき、x の入力は誰もが認識し、同じ x に対する出力値は固定されているため、複数回通過することはできません 抽選結果を変更してみてください
2. ノードは他のノードから宝くじ情報を受信した後、添付された証明書を使用して乱数の正しさを証明し、乱数が確かに秘密鍵の所有者によって計算されたものであることを確認できます。したがって、抽選結果を偽造することはできません。
3. VRF は主に擬似乱数を取得するために使用されます. 抽選部分は主に二項分布関数を担当します. 二項分布のパラメーターを構築することで, 取得する必要がある当選権利を簡単に制御できます.抽選が必要なさまざまなシナリオに適応します。
VRF に基づく宝くじアルゴリズムについて説明した後、この宝くじアルゴリズムがブロックチェーンのコンセンサスに何をもたらすかを見てみましょう。
VRF 宝くじがコンセンサスにもたらした変化
具体的な例から始めましょう。
Ouroboros は Cardano のコンセンサス アルゴリズムです。非常に興味深いものです。当初はコンセンサス プロセス スキームを提案していましたが、このスキームは安全であることが証明されており、すべての部分の実装が含まれるわけではありません。その後、紙版の更新や具体的な実施計画に実装の詳細を徐々に追加していきます。
これまでのところ、彼の理論バージョンはウロボロス、プラオス、ジェネシスの 3 つのバージョンを繰り返しています。 Praos の 2 番目のバージョンでは、VRF の部分がブロック提案ノードの抽出として導入されています。
まず、ウロボロスの合意プロセスについて簡単に説明します。
各エポックの開始前に、エポックの最後のラウンドで、ランダム シードとステーク ホルダーの数が、このエポック ラウンドの参加ノードとして決定されます。ランダム シードに従って、このエポックのすべてのスロットのスロット リーダーが決定されます。ラウンドが取得され、順次パッケージ化されます。
前回のラウンドでは、ランダム シードの送信はインタラクティブな PVSS スキームによって生成されました。簡単な例で説明すると、リアルタイム通信ではパンチを当てることができない二人がいるのと同じで、一方がもう一方のパンチ結果を受け取れば、必勝パンチを出して勝つことができるので、勝ち負けではありません。公平です。そこで、まずカードを使ってパンチを置き換え、次にそれをカバーします。パンチが何であるかは誰も知りませんが、誰もがパンチアップを選択したことは保証できます。結果は後日発表される。
ランダム シードが生成された後、フォロー ザ サトシ アルゴリズムを使用して各スロットのスロット リーダーを取得します。フォロー ザ サトシは、ランダム シードと各ステークホルダーの株式価値を使用して与えることができるランダム オラクル マシンとみなすことができます。各スロットは、ステーク ホルダーをスロット リーダーとしてランダムに割り当てます。この結果は、このエポックの開始前に各ノードに知られており、各ノードはそれを自分で計算できます。その場合、次の問題が発生します。
あるブロックのパッケージングノードを事前に知ることができるため、攻撃者はそのパッケージングノードを事前に攻撃して攻撃目的を達成することができます。
その後、プラオス、つまりウロボロスの第 2 バージョンでは、「サトシを追え」スキームに代わる VRF が導入されました。VRF 宝くじのプロセスと特徴について学んだ後、VRF の導入後、すべてのスロットのラウンドのスロット リーダーはノード自体にのみ知られており、彼が公開した後、他のノードは彼が本当にその役割を持っているかどうかを確認できるため、上記の攻撃を回避できます。
しかし、これは新たな問題も生み、前述の通り、フォロー・ザ・サトシでは各スロットにランダムでスロットリーダーを割り当てることができるが、確率ベースの抽選方式であるVRFではこの点が確実ではない。また、スロットの特定のラウンドでスロット リーダーが描画されない、または複数のスロット リーダーが描画される場合もあります。したがって、Praos では、この状況に対処するための追加のソリューションが追加されました。
2 つのソリューションを比較すると、VRF では、スロット リーダーの予測できないセキュリティ アップグレードに加えて、2 つの異常な状況が発生します。しかし、これら 2 つの異常は VRF によってもたらされた新しい問題なのでしょうか?考えてみましょう。
実際、Follow the SATO ソリューションでも VRF ソリューションでも、この問題は解決する必要があります。各スロットにスロット リーダーがあることは保証できても、スロット リーダーがこのスロットでパケットを印刷できるかどうかは保証できないからです。フォークを検証する解決策は、チェーンである限り考慮しなければならない問題ですが、スロット リーダーが攻撃され、そのスロットに多数の繰り返しパッケージングが行われた場合、フォークの問題も発生します。
したがって、新たな問題がなければ、パッケージ化ノードの匿名性を高めることは、実際にはシステムのセキュリティをアップグレードすることになります。
次に、VRF を使用する、または VRF に大きく依存する他のコンセンサス アルゴリズムをいくつか見てみましょう。
一般に、検証可能なランダム関数を使用してくじを引き、参加するコンセンサス ノードまたは特定の役割の数を減らすという考え方です。
1. アルゴランドが最初にパッカーを選択し、パッカーが選択された後に委員会が選択され、委員会は BA* を使用してブロックを選択します。
2. Dfinityでは、デポジットにより閾値を上げ、参加ノード数を減らしてからパッケージャを選択し、パッケージャを選択した後、公証人を選択し、ブロックの重みをソートしてブロックを選択します。
文章
文章
いくつかの問題
VRF とその現在のアプリケーションの一部を共有した後、一緒に考える必要があるいくつかの質問があります。
プロセスが似ている非対称暗号化スキームと比較するとどうなるでしょうか?
皆さん、ありがとうございました。
画像の説明
https://github.com/pinqy520/vrf.js
現在、Tarax コンセンサス アルゴリズムの実装で使用されています
参考文献—————————————————————————————————————————————————————
画像の説明
https://v.qq.com/x/page/e0735yg5l7t.html
Blockchain Funds-Technology Federation
BFTF共催者：
画像の説明
