VRF(Verifiable Random Function)について

nuno 2023/10/06に更新

VRFとは検証可能な疑似乱数関数(ハッシュ関数)のこと。

疑似乱数関数 $H_s(x)$ はシード値 $s$ で指定されるハッシュ関数で、出力は一様分布と区別できない。通常の疑似乱数関数では $s$ は公開されている。つまり誰でも $y = H_s(x)$ の値を計算することができる。

ブロックチェーンなどの分散ネットワークで乱数を生成したいとき、これではどのような乱数が出てくるか予想ができてしまう。この問題を解決するのがVRFである。

nuno 2023/10/06

VRFの定義

VRFには秘密鍵 $sk$ と、公開鍵 $pk$ が存在する。秘密鍵 $sk$ を知っている人は、どんな入力 $x$ が来ても、その疑似乱数出力 $y= H_{sk}(x)$ を簡単に計算することができる。 $y$ は $x$ に対して一意的に定まり、また一様分布と区別できない。一方で秘密鍵 $sk$ を知らない人は疑似乱数出力を計算することができない。

秘密鍵 $sk$ を知っている人は、疑似乱数出力 $y= H_{sk}(x)$ の正しさを示す証明 $proof$ を生成することができる。誰でも、公開鍵 $pk$ , 入力 $x$ , 出力 $y$ , 証明 $proof$ を用いて、疑似乱数出力 $y= H_{sk}(x)$ の正しさを検証することができる。

Verify(x, y, pk, proof) \rightarrow bool

nuno 2023/10/06

VRFによる乱数生成

VRFを使うと次のように乱数を生成することができる。

いま、ここに $N$ 人の参加者がいるとする。全員はそれぞれ秘密鍵 $sk_i$ をランダムに選び、それに対応する公開鍵 $pk_i$ を全員に公開する。公開鍵の交換が終了したら、全員は、同一の $x$ (適当に選んで良い)に対して疑似乱数出力 $y_i = H_{sk_i}(x)$ を計算し、証明 $proof_i$ とともに公開する。全員の証明を検証した後に、全ての $y_i$ のXORを取ったものを乱数とする。

ポイントは、秘密鍵が分からないとVRFの出力を予測することができないということである。そのため、N人のうち1人でも正直な参加者がいれば、攻撃者は正直な参加者の出力を予測することができず、最終的な乱数も予測することができない。またVRFの証明を検証することで、攻撃者が出力値をすり替えた場合に検出できるようになる。

nuno 2023/10/06

VRFの構成

VRFの構成には様々な方法があるが、ここでは下記の記事の方法を取り上げる。

https://asecuritysite.com/zero/vrf

公開鍵

$G$ を楕円曲線の生成元とする。秘密鍵 $k$ に対して公開鍵を $P = kG$ とする。

VRF
$H_1$ を入力 $m$ から(ランダムな)楕円曲線上の点へマップする、hash-to-curve関数とする。入力 $m$ に対するVRFを $V = kH_1(m)$ によって構成する。 $H_1(m)$ は楕円曲線上の点で、 $k H_1(m)$ はその $k$ 倍の点であることに注意。

prove
$r$ をランダムに選び、次の $s$ , $t$ を計算する。
$s = H_2 (G, H_1(m), P, V, rG, rH_1(m))$
$t = r - sk$
proofは $(s, t)$

verifiy
$s \stackrel{?}{=} H_2(G, H_1(m), P, V, tG+sP, tH_1(m)+sV)$
を検証する。
proverが正直なら
$tG + sP = tG +skG = (t+sk)G = rG$
と、
$tH_1(m) + s V = (t + sk)H_1(m) = rH_1(m)$
が成り立つことに注意