BLS署名の基本

初めに

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

数学用語の復習

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

$e:G1×G2→GTe : G_1 \times G_2 \rightarrow G_T$ をペアリングとします。
すなわち、$GTG_T$ は $e(P1,P2)e(P_1, P_2)$ を生成元とする位数 $rr$ の乗法巡回群で、
任意の整数 $aa$, $bb$ と点 $P∈G1P \in G_1$, $Q∈G2Q \in G_2$ に対して $e(aP,bQ)=e(abP,Q)=e(P,abQ)=e(P,Q)abe(a P, b Q) = e(ab P, Q) = e(P, ab Q)= e(P, Q)^{ab}$ が成り立ちます。これを双線型性というのでした。

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

• 群, 加法群, 楕円曲線 : 群と楕円曲線とECDH鍵共有
• 巡回群 : 楕円ElGamal暗号
• ペアリング : ペアリングと内積計算可能なL2準同型暗号

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

$$H1:{ 文字列 }→G1,H2:{ 文字列 }→G2 H_1 : \Set{文字列} \rightarrow G_1,\\ H_2 : \Set{文字列} \rightarrow G_2$$

とします。

BLS署名の基本形

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

鍵生成

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

署名

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

検証

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

$$e(pk,H2(m))==e(P1,σ)? e(pk, H_2(m)) == e(P_1, σ)?$$

正当性の確認

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

$$e(pk,H2(m))=e(sP1,H2(m))=e(P1,sH2(m))=e(P1,σ) e(pk, H_2(m)) = e(s P_1, H_2(m)) = e(P_1, s H_2(m)) = e(P_1, σ)$$

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

安全性

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

ハッシュ関数の仕様

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

$$H×:{ 文字列 }∋m↦SHA256(m)⋅P2∈G2 H_× : \Set{文字列} \ni m \mapsto \text{SHA256}(m) \cdot P_2 \in G_2$$

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

$$σ0:=sH×(m0)=s⋅SHA256(m0)⋅P2 σ_0 := s H_×(m_0)=s \cdot \text{SHA256}(m_0) \cdot P_2$$

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

$$(SHA256(m)/SHA256(m0))⋅σ0=s⋅SHA256(m)⋅P2=sH×(m)=σ(m) (\text{SHA256}(m)/\text{SHA256}(m_0)) \cdot σ_0 = s \cdot \text{SHA256}(m) \cdot P_2 = s H_×(m)=σ(m)$$

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

$G1G_1$ と $G2G_2$ の取り替え

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

$$e(H1(m),pk)==e(σ,P2)? e(H_1(m), pk) == e(σ, P_2)?$$

を検証します。

二つのタイプのBLS署名

プロジェクト	署名鍵	検証鍵	署名
(A) Ethereumなど	$s∈𝔽rs \in 𝔽_r$	$sP1∈G1s P_1 \in G_1$	$sH2(m)∈G2s H_2(m) \in G_2$
(B) DFINITYなど	$s∈𝔽rs \in 𝔽_r$	$sP2∈G2s P_2 \in G_2$	$sH1(m)∈G1s H_1(m) \in G_1$

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

まとめ

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