📖

BLS署名の基本

2023/09/14に公開

初めに

今回はBLS署名を紹介します。BLS署名はBoneh, Lynn, Shachamが提案した署名で、EthereumのPoSの暗号プロトコルなどで利用されています。

数学用語の復習

素数 p の有限体 𝔽_p 上で定義された楕円曲線の0でない点を P_1 を1個とり、素数 r 倍すると0になるとします。r P_1=0.
すると集合 G_1:=\Set{0, P_1, 2 P_1, \dots, (r-1)P_1} は位数 r の加法巡回群です。
同様に、別の楕円曲線の0でない点で r 倍すると0になる点 P_2 を1個とり、
G_2:=\Set{0, P_2, 2 P_2, \dots, (r-1) P_2} とします。G_2 も位数 r の加法巡回群です。

e : G_1 \times G_2 \rightarrow G_T をペアリングとします。
すなわち、G_Te(P_1, P_2) を生成元とする位数 r の乗法巡回群で、
任意の整数 a, b と点 P \in G_1, Q \in G_2 に対して e(a P, b Q) = e(ab P, Q) = e(P, ab Q)= e(P, Q)^{ab} が成り立ちます。これを双線型性というのでした。

ここで紹介した用語を初めて見る方は過去の記事を参照してください。

また任意の文字列から G_1, G_2 への暗号学的ハッシュ関数を

H_1 : \Set{文字列} \rightarrow G_1,\\ H_2 : \Set{文字列} \rightarrow G_2

とします。

BLS署名の基本形

署名の一般的な説明については署名の概要を参照ください。

鍵生成

有限体 𝔽_r := \Set{ 0, 1, 2, \dots, r-1} からランダムに要素 s を1個選び、s を署名鍵(秘密鍵)、pk:=s P_1 \in G_1 を検証鍵(公開鍵)とします。
署名鍵と検証鍵の作り方は、(楕円曲線の種類は異なりますが)ECDSAなどと同じです。

署名

文字列 m に対して署名鍵 s を使って σ:=Sign(s,m):= s H_2(m) \in G_2 とします。H_2 は楕円曲線 G_2 へのハッシュ関数なので σG_2 の要素です。

検証

検証鍵 pk を持っている人は文字列 m と署名 σ \in G_2 に対して、2個のペアリング e(pk, H_2(m))e(P_1, σ) を計算し、それらが一致していれば受理、そうでなれければ拒絶します。P_1G_1 の生成元です。

e(pk, H_2(m)) == e(P_1, σ)?

正当性の確認

正しく作った署名が検証に通ることを確認します。構成法から pk = s P_1, σ=s H_2(m) なので

e(pk, H_2(m)) = e(s P_1, H_2(m)) = e(P_1, s H_2(m)) = e(P_1, σ)

が成り立ちます。2番目の等号はペアリングの双線型性を使っています。

安全性

G_1 の離散対数問題が困難(→楕円曲線暗号の安全性 DLPとCDHとDDH)なら、検証鍵 s P_1 から署名鍵 s は求められません。
署名の偽造ができないことの説明はここでは省略しますが、楕円曲線としてBLS12-381曲線を使い、H_2 が安全なハッシュ関数なら偽造困難であることが知られています。
ここでBLS12-381曲線のBLSはBarreto, Lynn, Scottの略でBLS署名のBLSとは異なります。BLS12-381曲線の詳細はまた解説しますが、381ビットの素数上の楕円曲線です。以前はBN254というタイプの楕円曲線が使われていたのですが、離散対数問題の解読理論の向上により100ビットセキュリティレベルに落ちたため(それでも2023年のスーパーコンピュータでは解けませんが)、よりセキュリティレベルの高いBLS12-381が主流になっています。

ハッシュ関数の仕様

安全性の説明で「H_2 が安全なハッシュ関数なら」と書いている点にも注意してください。
文字列から楕円曲線 G_2 へのハッシュ関数を、たとえば

H_× : \Set{文字列} \ni m \mapsto \text{SHA256}(m) \cdot P_2 \in G_2

としてしまいたくなるかもしれません(m のハッシュをとって G_2 の生成元 P_2 に掛ける)。しかし、このようなハッシュ関数は全く安全ではありません。
なぜなら攻撃者が、あるメッセージ m_0 に対する署名

σ_0 := s H_×(m_0)=s \cdot \text{SHA256}(m_0) \cdot P_2

を得たとします。すると任意のメッセージ m に対する署名は

(\text{SHA256}(m)/\text{SHA256}(m_0)) \cdot σ_0 = s \cdot \text{SHA256}(m) \cdot P_2 = s H_×(m)=σ(m)

と、署名鍵 s を知らなくても作れてしまうからです。
最近は流石に無いと思いますが、以前はたまにこのようなハッシュ関数を使ったBLS署名の実装があったそうなので注意してください。
EthereumではRFC 9380(のドラフト段階)で定義された非常に複雑な方法が使われています。Ethereumの中の人にこのハッシュ関数の実装をたのまれたときは、ドラフトのバージョンが上がるごとに仕様が結構変わって苦労しました。いつ、fixされるのかと思ったものです。
なお、このアルゴリズムで使われるDSTというパラメータはブロックチェーンのプロジェクトや製品によって異なることがあるので注意してください(私のGitHubでもよくissueに上がる)。

G_1G_2 の取り替え

BLS署名は s P_1 \in G_1 が検証鍵で s H_2(m) \in G_2 が署名と説明しました。ここで G_1G_2 を入れ換えて pk:=s P_2 \in G_2 が検証鍵で s H_1(m) \in G_1 を署名にしても同じようにBLS署名を構成できます。
この場合、検証はメッセージ m, 検証鍵 pk \in G_2, 署名 σ \in G_1, G_2 の生成元 P_2 を使って

e(H_1(m), pk) == e(σ, P_2)?

を検証します。

二つのタイプのBLS署名

プロジェクト 署名鍵 検証鍵 署名
(A) Ethereumなど s \in 𝔽_r s P_1 \in G_1 s H_2(m) \in G_2
(B) DFINITYなど s \in 𝔽_r s P_2 \in G_2 s H_1(m) \in G_1

署名鍵のサイズは同じですが、どちらのタイプのBLS署名を選ぶかによって、検証鍵と署名の群(楕円曲線)が入れ代わっています。
実はBLS署名でよく使われるペアリングでは楕円曲線 G_2 の大きさは 楕円曲線 G_1 の2倍あり、演算コストは3倍以上重たくなります。
したがって、自分のプロジェクトでBLS署名を採用する場合、検証鍵(公開鍵)を小さくしたい場合は(A)を、署名を小さくしたい場合は(B)を選ぶことになります。
また署名生成と、検証は(B)の方が速いので速度を考慮するなら(B)となります。
私のプロジェクトherumi/blsではコンパイル時にどちらを選ぶか選択できるようになっています。

まとめ

ブロックチェーン系プロジェクトでよく見られるBLS署名を紹介しました。ペアリングの群が非対称なため、検証鍵と署名の大きさのトレードオフが存在します。また楕円曲線へのハッシュ関数を安易に作ると安全ではないことを示しました。

GitHubで編集を提案

Discussion