コンセンサスにおける検証可能なランダム関数

コンセンサスプロトコルでは、リーダー選出、委員会選択、シャード割り当てのためにランダム性が必要です。ランダム性には、3つの性質が求められます。予測不能性（出力が明らかになる前に誰も予測できないこと）、非バイアス性（参加者が自分に有利になるよう出力を操作できないこと）、公開検証可能性（生成元を信頼しなくても、誰でも出力が正しいことを検証できること）です。単純な方法ではうまくいきません。単一ノードの乱数は操作可能であり、commit-reveal方式では最後に明らかにする参加者によるバイアスが生じる可能性があります。Verifiable Random Functions（VRF）は、この3つの要件をすべて満たします。

Verifiable Random Function（VRF）は、Micali、Rabin、Vadhanによって1999年に導入された、正しさの証明を提供する擬似ランダム関数です。VRFには3つのアルゴリズムがあります。KeyGenはキーペア（SK、PK）を生成し、Prove（SK、alpha）は（beta、pi）を生成します。ここでbetaは出力、piは証明です。Verify（PK、alpha、beta、pi）はvalidまたはinvalidを返します。SKを知らない人にとって、出力betaはランダムな値と見分けがつかず（VRFの擬似ランダム性）、証明piは偽造できません（VRFの一意性）。証明のサイズはO(1)であり、入力にかかわらず一定です。

最も広く展開されているVRF構成は、楕円曲線離散対数問題の困難性に基づくECVRF（IETF RFC 9381）です。秘密キーxと入力alphaが与えられると、証明者はH = hash-to-curve（PK、alpha）（alphaを曲線上の点に写像）を計算し、続いてgamma = x * H（スカラー倍算）を計算します。VRF出力はbeta = keccak（gamma）です。証明piはSchnorrに似たゼロ知識証明を使用します。証明者はランダムなkに対するコミットメントを作成し、チャレンジc = hash（H、gamma、k*G、k*H）を計算し、レスポンスs = k - c*xを計算して、pi =（gamma、c、s）を出力します。検証ではSchnorrの等式を確認し、betaを再計算します。

Algorand（Silvio Micaliら、2017年）は、ブロックチェーンのコンセンサスにおけるVRFの利用を先駆けました。各ラウンドで、すべてのバリデーターがVRF(SK, round || seed)を非公開で評価し、ランダムな出力を取得します。その出力がしきい値と比較され、VRF_output < stake_fraction * threshold であれば、そのバリデーターは委員会メンバーまたはブロック提案者として選出されます。選出されたことを知っているのはそのバリデーターだけであり、VRF証明とともにブロックまたは投票をブロードキャストするまで、他の参加者には分かりません。この暗号学的な自己選出により、公開リーダー選出の必要がなくなるため、Algorandは、次にリーダーになることが分かっている参加者を狙ったサービス拒否攻撃に対して耐性を持ちます。

CardanoのOuroboros Praos（現在デプロイされているバージョン）は、スロットのリーダー選出にVRFを使用します。各エポックの開始時に、ブロックチェーンから新しいランダムシードが導出されます。各ステークプール運用者（SPO）は、エポック内の各スロットについてVRF(SK, slot || epoch_seed)を評価します。出力がそのステーク量に比例したしきい値を下回ると、その運用者がスロットリーダーとなり、ブロックを生成できます。VRF証明はブロックヘッダーに含まれるため、誰でもそのSPOが正当に選出されたことを検証できます。これにより、Cardanoは、エポックの途中でリーダースケジュールを知る適応型攻撃者に対して、証明可能な安全性を実現します。

Ethereumは、乱数ビーコンにVRFではなくRANDAO（蓄積されたBLS署名）を使用します。RANDAOは、BLS以外の追加の暗号プリミティブを必要としないため、より単純です。一方で、最後の公開者バイアスの影響を受けます。RANDAOへの自分の貢献によって不都合な結果になると予測できるブロック提案者は、ブロックを公開せずに済むためです（その代わりにブロック報酬を失います）。VRFベースの選出では、選出された参加者が自らを明らかにするまで、誰が選出されたかが隠されるため、この攻撃経路を完全に排除できます。トレードオフとして、VRFは暗号学的な複雑性（hash-to-curveや証明生成）を追加しますが、RANDAOは既存のBLS基盤を再利用できます。

Chainlink VRFは、スマートコントラクト向けに検証可能な乱数をサービスとして提供します。利用者のコントラクトは、LINKトークンを支払って乱数を要求します。ChainlinkのオラクルノードはVRF鍵ペアを保持しています。このノードは、ブロックハッシュとユーザーが指定したnonceから導出されたseedを使ってECVRF(SK, seed)を評価し、(beta, pi)をオンチェーンに送信します。VRFコーディネーターコントラクトは、ランダムな出力を利用者に転送する前に証明を検証します。これにより、チェーン自体にネイティブのVRFビーコンを実装しなくても、スマートコントラクトは操作耐性のある乱数を利用できます。これは、NFTのミント、くじ、ゲームなどに役立ちます。

Signal Protocolは、Curve25519上のVRF構成であるVXEdDSA（Verifiable X25519 EdDSA）を使用します。送信者がワンタイムプレキー署名を生成するとき、VRFを使ってメッセージと送信者の鍵から決定的でありながら予測不能なnonceを生成します。これにより、署名を検証可能なままnonceの再利用を防ぎます。nonceを再利用すると、EdDSAの安全性が損なわれるためです。VRF証明により、受信者はnonceが正しく導出されたことを検証でき、鍵復元攻撃につながる悪意のあるnonceを送信者が選ぶことを防げます。VXEdDSAは、VRFがコンセンサス以外にも利用できる汎用的な暗号ツールであることを示しています。

検証可能遅延関数（VDF）は、VRFと混同されることがあります。VDFでは、少なくともTステップの逐次計算が必要となるため、タイムロック特性が得られ、正しさを示す短い証明を伴う出力が生成されます。VDFは、RANDAOにおける最後の公開者バイアスの緩和策として使用されます。Ethereumで計画されているVDFレイヤーでは、操作を試みるには事前にVDFを実行する必要があり、その計算には攻撃可能な時間枠より長い時間がかかるためです。VRFは即時の非公開評価を提供し、VDFは公開された低速の評価を提供します。両者は補完関係にあり、VDFは最後の公開者バイアスを防ぎ、VRFはリーダーの予測を防ぎます。

VRFによる選出は、適応型攻撃者に対する重要なセキュリティ向上をもたらします。PBFTやTendermintでは、リーダーの身元が事前に分かっており、ラウンドロビン方式のスケジュールで決められています。そのため攻撃者は、次に提案するリーダーを事前にDDoS攻撃できます。VRFベースの選出（Algorand、Cardano）では、ブロックがブロードキャストされるまでリーダーの身元が秘密にされます。その時点ではブロックはすでに提案されているため、DDoS攻撃が届いても手遅れです。これは適応型セキュリティ、または予測不能なリーダー選出と呼ばれます。これを可能にする暗号学的性質は、秘密鍵を持たない者にとってVRF出力が擬似乱数となることです。

VRFを正しく実装するには、いくつかの点に注意する必要があります。hash-to-curveには、定時間かつ一様なアルゴリズムを使用しなければなりません（IETF RFC 9380では、タイミング情報の漏えいを防ぐ標準化手法が定義されています）。証明内のVRF nonce kは、RFC 6979を使用して(SK, alpha)から決定的に導出する必要があります。kを再利用したり、弱い乱数のkを使用したりすると、秘密鍵が漏えいします。これはECDSAでnonceを再利用した場合と同じ脆弱性です。ECVRF-P256-SHA256-TAIの証明サイズは80バイト、ECVRF-ED25519-SHA512-ELL2の証明サイズも80バイトであり、どちらもオンチェーンへの格納に適しています。VRFの一意性により、同じ(SK, alpha)の組に対して2つの有効な証明が存在しないことが保証されます。

VRFは、正しさを示す暗号学的な証明を伴う擬似乱数出力を生成し、予測不能性、非偏り性、公開検証可能性を満たします。ECVRF（RFC 9381）は、楕円曲線上の標準的な構成です。Algorandは、適応型攻撃者への耐性を得るために、VRFによる暗号学的な自己選出を使用します。CardanoのOuroboros Praosは、スロットごとのリーダー選出にVRFを使用します。Chainlink VRFは、スマートコントラクトに検証可能な乱数を提供します。VRFは、最後の公開者バイアスに対処するVDFを補完します。また、蓄積されたBLS署名を使用し、最後の公開者に関する既知の弱点を持つRANDAOとは対照的です。