VDF(Verifiable Delay Functions)について
逆方向の計算は可能なのでハッシュ関数とは違う
背景
分散プロトコルでは、システムの参加者がある程度の時間やエネルギーを消費することを保証するために、計算を意図的に難しくしたり、時間をかけたりする
並列計算
例えば、PoWは、ブロックごとに大量の計算を行い、台帳の履歴を書き換えることを困難にしている
しかし、この計算は分散計算であり、ネットワーク内で計算が追加・削除されると、ネットワークが定期的に作業の難易度を調整する。そうしなければ、ネットワークはブロックの生成速度を制御できなくなる。
しかし、アプリケーションによっては、大量の（分散）計算能力を利用しても、同じように時間のかかる計算が必要になる
直列計算
PoWとは異なり、直列処理でしか効率的に計算できないようにする
効率的なコンピュータや専用ハードウェアが、スパコンに劣らない計算能力を持つことを保証することができる
同時に、そもそも実際に実行するのが難しい演算であっても、計算結果を効率的に確認できる必要がある
VDFの概要
VDFは上記の目標をすべて満たすもので、並列計算で高速化できない遅延を発生させながら効率的に検証可能な関数
VDFは、暗号学的に安全なランダム性の生成などに使える
Ethereum、Filecoin、Tezos、Zcashなどで評価されている
例えば、VDFを使ったランダム値は以下のようにして計算される
https://scrapbox.io/files/628b6052cfe2730023fa7bd5.png
ランダム性に関してはVDF≠VRF
課題
そこで、（VDFのためというより、zkのために)ソフト・ハード両面での研究が行われている。
Plonky2に代表されるように新たなSNARKのスキームとして研究がされている。 Halo 2とNovaを用いて実現したPCD（Proof-Carrying Data）とIncrementally Verifiable Computation を用いた、証明の構築作業を異なるプラットフォームに分散させるなど、他の組織との共同研究が盛ん
ASICベースのシステム
2022/5月にApliedzkpが発表したzkPalingの実装により、circomで実装されているgroth16などスキーム(PLONKは不明)でも再帰zkpできるようになった。しかし、これはまだ研究開発段階
https://www.youtube.com/watch?v=dN-1q8c50q0&t=965s
基本的なアルゴリズム
パラメータ生成
pp=(Public Parameters for SNARK)
$ H^{(T)}(x)=H(H(H(...(H(H(x)))...)))
Hash function sequentially works$ T times
$ H: { 0 , 1} $ ^{256}-> { 0 , 1} $ ^{256} (e.g. MiMC)
評価アルゴリズム
Eval(pp , x): output $ y=H^{(T)}(x), proof $ π=(recursive SNARK)
検証アルゴリズム
Verify(pp, x, y, π): accept if SNARK proof is valid,
https://scrapbox.io/files/62878ab8194363001d38d99f.png
この一連の過程がrecrucive SNARKであり、VDFの検証動作が正しく行われたことを示す証明を再帰的に行っている
VRF(Verifiable random function)との違い
ランダムな値を生成する点で、PoSでバリデータを選出するVRFも提案されているがこれとVDFは別物。
VRFには遅延も共同作業者もいない。これはBlock Producerという一人の関係者だけで計算することが可能
VDFでいうところのMPCベースのランダム性とは、複数の当事者がランダムシードの一部を提供し、不正行為を防止するためにVDFを順番に使用することを指している点がミソ
VRFに関しては今後調べる
参考文献