Develop with pleasure!

福岡でCloudとかBlockchainとか。

Verifiable Delay Function

最近ブロックチェーン関連のペーパーでよく話題に上がる新しい暗号プリミティブVerifiable Delay Function(VDF)について調べてみた。

VDFに関する研究は、以下のサイトでまとめられている。

https://vdfresearch.org/

今回はVDF Day 2019のDan Bonehのセッションを見てみる↓

http://diyhpl.us/wiki/transcripts/verifiable-delay-functions/vdf-day-2019/dan-boneh/

VDFとは?

VDFは参加者が並行多項性を持っている場合でも、評価にTステップかかることになっている関数(並列処理してもスピードアップしない)で、分散環境において難しいとされる偏りの無いランダム性や時間経過のプロキシなどの機能を提供する。

VDFには

  • セットアップ
    セキュリティパラメータλと時間制限Tを入力にとり、公開パラメータpを生成する。
  • 評価
    評価関数は(p, x)を入力として、出力yとプルーフを生成する。並列コンピュータを使用したとしてもこれにはTステップかかり、並列処理によって計算が高速化することはない。
  • 検証
    検証アルゴリズムは(p, x, y, proof)を入力として、yがVDFの正しい評価かどうか迅速に示す。

の3つのアルゴリズムがある。

安全性

VDFには2つの安全性要件がある。

  • 一意性
    任意の値xが与えられた場合、検証者を納得させる値yは1つだけ存在する。同じyに対して異なるプルーフを持つことができるが、yは1つだけ。
  • シーケンシャル性
    敵対者が並列マシン、特に多項式個数のプロセッサを使っている場合でも、時間Tを費やさない限り、VDFの出力が完全にランダムに見える。

分散環境においてランダム値を生成しようとした場合、参加者はそれぞれランダム値を計算し、それを掲示板に貼り、ランダム値はその全てのXORで生成される。この場合、最後の参加者が最終的な生成値を制御できてしまう。これを防ぐために事前にランダム値のハッシュ値をコミットメントとして提出させる方法が考えられるが、コミットメントが提供された後ランダム値が提供されなかった場合、プロトコルは停止する。公開されなかったコミットメントは無視するというのは安全ではないからだ。

そこで分散環境におけるランダム値の生成にVDFを導入し、VDFの出力値をランダム値とする。なぜこれが可能で偏りのないランダム性になるのか?というと

全員が正午までにランダム値を送信し、特定の時間になるとそれがプロトコルの参加者になる。VDFは送信時間帯よりも長くなる。VDFのシーケンシャル特性は、VDFを計算するためには送信時間よりも時間がかかるため、最後の送信者がプロトコルへ多くの入力と試行できないこと保証する。 gallium-arcinide ASICなどの最新技術を持っていたとしても、時間がかかることを確実にする必要がある。

シーケンシャル特性により最後の参加者は出力にバイアスをかけられなくなる。バイアスをかけるためには多くの時間を必要とするため。また、一意性により出力に曖昧さがないことが保証される。シーケンシャル特性と一意性によってVDFは困難になる。

VDFの構築方法

VDFを構築するにあたっては以下のような構築方法がいくつか挙げられている。

ハードウェアEnclave

VDFを構築するのにとても簡単なのはハードウェアEnclaveを使う方法。Enclave内に暗号鍵を保存し、その鍵を使ってVDFを生成する。この場合、公開パラメータは公開鍵暗号の署名、つまり公開鍵は公開される。入力が入るとEnclaveは時間遅延を強制し、入力XのHMACもしくはPRFを生成し、出力に署名してVDFがハードウェアによって正しく計算されたことを証明する。ハードウェアEnclaveがあればVDFの構築は非常に簡単になる。しかしHMACを生成する際の秘密鍵が盗まれると、VDFの時間外で誰もが即座に結果を計算することができてしまう。

そのため、Enclaveの保護が重要だが、十分な資金があればこのハードウェアEnclaveを破ることは可能と思われ、プライバシーやデータ保護には問題がないが、コンセンサスを破ることが資金の損失に繋がるコンセンサスに採用するのは危険になる。

ハッシュ関数

ハッシュ関数を利用してもVDFを構築することはできる。この場合、公開パラメータはSNARKのパラメータで、VDFはSHA256を繰り返し評価するのに時間Tかかるハッシュチェーンとして定義される。しかし、出力が正しく計算されたかどうか検証するためにSNARKが登場する。しかしこれを正しく動作させることは難しい。プルーフはハッシュチェーンが正しく計算されたことのSNARKだが、SNAKRの計算にはチェーンの計算よりも時間がかかるため、それに対処する必要がある。

その対処として考えられているのが検証をSNARKのプルーフの検証にするというもので、最近、Recursive SNARKs(= SNARK内でSNARKのプルーフの検証を行う仕組み)として研究が行われている。SBC20の「Fractal: Post-Quantum and Transparent Recursive Proofs from Holography」のセッションでは、Recursive SNARKsを効率的に実現するための量子耐性を持つ新しい方法としてFractalというプロトコルが提案されている。

置換多項式

置換多項式からVDFを構築するというアイディアもあるっぽい。置換多項式は、有限体の元との置換多項式で、有限体内の2点x, yについて多項式f(x)がf(y)と等しくならないもの。この構造で使用する特性は、多項式の根*1を見つけること。VDFの入力は値xで、xと等しくなるようなf(y)の値yを求める。そのようなf(y)を見つけたい場合、多項式f - xの根を見つけることになる。この根を見つけるための実用的な方法は、シーケンシャルに行われるGCP(Generalized Characteristic Polynomial)計算となり、VDFに使えるのでは?とされている。

課題はショートカットがなくGCP計算が最良の計算方法である置換多項式があるかどうで、まだ研究がされてないっぽい?

代数的構成

代数的な構成では、有限巡回群Gから始まり、群Gの位数は不明、つまり群に含まれる要素の数を誰も知らないという仮定を持つ。公開パラメータは群へのハッシュ関数。VDFはxを入力として受け取り、群にハッシュし、出力yを以下のようにT回の平方演算を求める。

 {y = H(x)^{2^{T}}}

これは時間の証明やtimelock puzzlesなどで使われており、この種の関数はよく使われる。

こうやって生成された出力が正しいかどうかの検証proofs of exponentiationを行う必要がある。これについてはサーベイ論文で解説されてるっぽい。

↑で群の位数が不明と書いたが、群の位数がもし分かっていると、例えばDとすると、 {2^{T} \mod D}を計算でき小さな冪乗になり評価は簡単になる。VDFとしては、群の位数が分かればTは対数時間まで加速するため、群の位数は不明でなければならない。

未知の位数の群をどうやって生成するか?

既知の位数の群でVDFを構成した場合、安全はなくなるため、未知の位数を持つ群を生成する必要があるが、まずこれをどうやって生成するのか?

1番最初に思いつくのがRSA。2つの整数pとqを選択し、それらを乗算する(n = p * q)と因数分解出来ない限り群の位数は不明になる。この因数分解を知っていれば群の位数を知っていることになるので、誰も因数分解を知らない方法でこれを構築する必要があり、そのためにTrusted Setupが必要になる。また十分大きなnにする必要があり、30,000-40,000ビットほどの大きさである必要がある。

RSAの問題はこのTrusted Setupが必要なことで、RSAモジュラスが2つの巨大な素数の因子からなり、その因数分解を誰も知らないことを誰もが確信するように生成するプロトコルが必要になる。

この辺りの研究は、SBC20でも「Scalable RSA Modulus Generation with Dishonest Majority」として取り上げられている。

Class Group

未知の位数を持つ群のもう1つの候補で注目されているClass Groupだ。Class Groupというのは1990年代に提案された暗号プリミティブだが、まだ実際に展開されたことは無い。Class Groupは素数で指定された群を持ち、その素数が1000ビットのように大きな値の場合、その群の位数を計算する方法を誰も知らないという特徴がある(なぜそうなるのか、どういうものなのか詳しくは知らない)。

これにより素数を選択することで未知の位数の群を入手し、VDFに使用できるということらしい。利点としてRSAで必要だったTrusted Setupを必要としない。ネックになるのはRSAよりClass Groupの演算の方が遅いのと、Class Groupの演算がどれくらい並列化できるものなのかがはっきり分かっていない点にある。

尚、現状代数学的なアプローチは量子耐性はなく、量子耐性を持つのはハッシュベースの構成だが、これはRecursive SNARKsを必要とする。

といずれも現在進行系でそれぞれに一長一短があり、さまざまな研究が進んでいる。

*1:p(x) = 0となるようなx