このセクションでは、この集団鍵ペアを使って、公開検証可能で、偏りがなく、予測できない乱数を分散的に生成する方法を説明します。
まず、広く使われるようになったペアリングベース暗号（PBC）を説明します。PBC は、zk-SNARKs などの現代のコンセンサスプロトコルやゼロ知識証明でも使われています。次に、しきい値 Boneh-Lynn-Shacham（BLS）署名による乱数ビーコン生成フェーズで、drand が PBC をどう使うかを示します。最後に、生成したしきい値 BLS 署名を乱数チェーンへつなぐ方法を説明します。
ペアリングベース暗号は双線形群 (𝔾1,𝔾2,𝔾𝑡) に基づきます。𝔾1、𝔾2、𝔾𝑡 はそれぞれ生成元 𝑔1、𝑔2、𝑔𝑡 を持つ素数位数 𝑝 の巡回群で、ペアリング演算 𝑒:𝔾1×𝔾2→𝔾𝑡 は次の性質を持ちます。
-
双線形性:
∀𝑎,𝑏∈ℤ∗𝑝,∀𝑃∈𝔾1,∀𝑄∈𝔾2,に対して𝑒(𝑎𝑃,𝑏𝑄)=𝑒(𝑃,𝑄)𝑎𝑏が成り立ちます -
非退化性:
𝑒≠1 -
計算可能性:
𝑒を計算する効率的なアルゴリズムが存在します。 drand は現在、Barreto-Lynn-Scott 曲線 BLS12-381 を使っています。
公開検証可能で偏りがなく分散された乱数を生成するため、drand はしきい値 Boneh-Lynn-Shacham（BLS）署名を使います。まず通常の BLS 署名を説明し、次にしきい値版を説明します。
BLS 署名は双線形ペアリングに基づく短い署名で、𝔾1 の要素 1 つだけで構成されます。メッセージと署名者の鍵だけに依存する決定的な署名です。ECDSA など、署名ごとに新しい乱数値が安全性に必要な方式とは異なります。言い換えると、同じ鍵で同じメッセージに対して作った BLS 署名は、どれも同一です。drand では、この性質を使って乱数生成の偏りのなさを実現します。
BLS 署名方式は、次の部分手続きで構成されます。
鍵ペアを生成するには、署名者がまず秘密鍵 𝑥∈ℤ∗𝑝 をランダムに選び、対応する公開鍵を 𝑋=𝑔𝑥2∈𝔾2 として計算します。
𝐻:{0,1}∗→𝔾1 を、任意のビット列を 𝔾1 の要素へ写す暗号学的ハッシュ関数とします。メッセージ 𝑚 に対する BLS 署名 𝜎 を計算するには、署名者は 𝜎=𝑥𝐻(𝑚)∈𝔾1 を計算します。
メッセージ 𝑚 に対する BLS 署名 𝜎 が妥当かを検証するには、検証者は署名者の公開鍵 𝑋 を使い、𝑒(𝐻(𝑚),𝑋)=𝑒(𝜎,𝑔2) が成り立つかを確認します。
妥当な署名では、𝑒(𝐻(𝑚),𝑋)=𝑒(𝐻(𝑚),𝑔𝑥2)=𝑒(𝐻(𝑚),𝑔2)𝑥=𝑒(𝑥𝐻(𝑚),𝑔2)=𝑒(𝜎,𝑔2) となるため、この等式が成り立ちます。
しきい値署名方式の目的は、参加者が独立に生成した部分署名を組み合わせて、集団で署名を計算することです。しきい値 BLS 署名方式には、次の部分手続きがあります。
𝑛 人の参加者は、上で説明したとおり 𝑡-of-𝑛 DKG を実行し、集団公開鍵 𝑆∈𝔾2 と、未知の集団秘密鍵 𝑠 の秘密鍵シェア 𝑠𝑖∈ℤ∗𝑝 をセットアップします。
メッセージ 𝑚 に署名するには、各 𝑖 が自分の秘密鍵シェア 𝑠𝑖 を使い、部分 BLS 署名 𝜎𝑖=𝑠𝑖𝐻(𝑚) を作成します。
𝑚 に対する部分署名 𝜎𝑖 の正しさを検証するには、検証者は DKG で生成された公開鍵シェア 𝑆𝑖 を使い、𝑒(𝐻(𝑚),𝑆𝑖)=𝑒(𝜎𝑖,𝑔2) が成り立つことを確認します。
𝑚 に対する集団 BLS 署名 𝜎 を再構成するには、検証者はまず 𝑚 に対する互いに異なる妥当な部分 BLS 署名 𝜎𝑖 を 𝑡 個集め、続けてラグランジュ補間を行います。
集団 BLS 署名 𝜎 を検証するには、検証者は集団公開鍵 𝑆 に対して 𝑒(𝐻(𝑚),𝑆)=𝑒(𝜎,𝑔2) が成り立つことを確認します。
ラグランジュ補間の性質により、𝜎 の値は、署名再構成時に選んだ 𝑡 個の妥当な部分署名 𝜎𝑖 の部分集合に依存しません。さらに、ラグランジュ補間は、𝑡 人未満の署名者の集合では 𝜎 を予測したり偏らせたりできないことも保証します。
まとめると、しきい値 BLS 署名 𝜎 は、公開検証可能で、偏りがなく、予測できず、分散された乱数に必要な性質をすべて備えています。
上記では 𝔾1 と 𝔾2 を入れ替えることもできます。影響は、公開鍵と署名の相対的なサイズです。最初の drand チェーンは上のとおり構成されており、署名は 𝔾2、公開鍵は 𝔾1 にあります。署名サイズは 96 バイト、公開鍵サイズは 48 バイトです。
一部のアプリケーションでは、公開鍵が大きくなっても署名を小さくしたいことがあります。そのため、一部の drand ビーコンでは署名が 𝔾1、公開鍵が 𝔾2 にあります。この変更を 𝔾1/𝔾2 swap と呼びます。
drand の乱数ビーコンは、離散的なラウンド 𝑟 で動作します。チェーン型乱数を使うように設定した drand ビーコンは、各ラウンドで、乱数チェーンにつないだしきい値 BLS 署名を使って新しい乱数値を生成します。この乱数チェーンを伸ばすため、各 drand 参加者 𝑖 はラウンド 𝑟 で、メッセージ 𝑚=𝐻(𝑟∥𝜎𝑟−1) に対する部分 BLS 署名 𝜎𝑟𝑖 を作成します。ここで 𝜎𝑟−1 はラウンド 𝑟−1 の（完全な）BLS しきい値署名、𝐻 は暗号学的ハッシュ関数です。
少なくとも 𝑡 人の参加者が 𝑚 に対する部分署名 𝜎𝑟𝑖 をブロードキャストすると、誰でもラウンド 𝑟 の乱数値に対応する完全な BLS しきい値署名 𝜎𝑟 を復元できます。その後、drand ノードはラウンド 𝑟+1 に進み、同じ処理を繰り返します。
ラウンド 𝑟=0 では、drand 参加者はセットアップ時に固定したシードに署名します。この処理により、新しい乱数値は、それまでに生成されたすべての署名に依存します。署名は決定的なので、攻撃者がチェーンを分岐させ、あるラウンド 𝑟 で異なる 2 つの署名 𝜎𝑟 と 𝜎′𝑟 を提示して、公開乱数に依存するシステムに不整合を起こすこともできません。
drand ビーコンは、非チェーン型乱数を使うように設定することもできます。この乱数チェーンを伸ばすため、各 drand 参加者 𝑖 はラウンド 𝑟 で、メッセージ 𝑚=𝐻(𝑟) に対する部分 BLS 署名 𝜎𝑟𝑖 を作成します。ここで 𝐻 は暗号学的ハッシュ関数です。
この処理により、ラウンド 𝑟=i のメッセージ 𝑚 を直接事前計算できます。