BLS署名の集約署名

こんにちは！弐号です。

ETH2.0ではバリデータの生成する署名がBLS署名を用いており、複数のバリデータが出力する署名を効率よく検証するために集約署名 (signature aggregation) 技術が利用されているようです[1]。

ここではBLS署名の集約署名アルゴリズムの一つ[3]を解説していきます。

（復習）BLS署名

Boneh、Lynn、Shachamにより発明された楕円曲線上のペアリングを用いる署名は、従来の電子署名 (DSA、Schnorrなど) とくらべ、短いバイト数で署名データが表現できることが特徴となっている、比較的新しい署名技術です[2]。

この署名方式は発明者の頭文字を取って「BLS署名」と呼ばれています。

ペアリングは楕円曲線上の二つの点を引数として取り、楕円曲線上の点の加法について双線型性を持つ写像となっています。

e(aG, bG) = e(G, G)^{ab}

なお、ここではペアリングの定義域の群については加法的に、値域の群については乗法的に書くこととし、以下同様とします。

ペアリング写像としてはWeilペアリングが古くから見つかっていましたが、他にもTateペアリングやBilinearペアリングなど、複数の実装が存在します。

BLS署名はペアリングの双線型性に着目して作られた署名方式であり、以下のようなアルゴリズムです。

  • KeyGen: p \xleftarrow{R} \mathbb{Z}、P := pG。
  • Sign: \sigma := pM。
  • Verify: e(G, \sigma) = e(P, M) なら成功。

ここで p は秘密鍵、P は公開鍵、M は署名対象のメッセージ、\sigma が電子署名です。

電子署名は楕円曲線上の点が一個のみであり、ECDSAやSchnorr署名が二個の点を必要としていたことを思い出すと、署名サイズが従来署名の半分（！）となっているため、署名長が短くなるというわけです。

また、ECDSAやSchnorr署名などのように署名時に乱数を生成する必要がないため、署名は決定的であることも特徴となっています。

古典的な署名集約

最もナイーブな署名集約アルゴリズムは以下のようなものです。

すなわち、集約したい署名の公開鍵、メッセージ、署名をそれぞれ (P_i, M_i, \sigma_i), i = 1 \cdots n とすると、集約された署名は

\sigma := \sigma_1 + \cdots + \sigma_n

であり、署名検証は

e(G, \sigma) = e(P_1, M_1) \cdots e(P_n, M_n) \quad\quad \cdots (1)

という等式が成り立つかどうかをチェックすればいいです（演習問題①）。

特に、メッセージがすべての署名間で同一であれば、

e(G, \sigma) = e(P_1 + \cdots + P_n, M)

という式になりますので、ペアリングの計算回数を大幅に削減することができます（演習問題②）。

しかし、このような単純な署名集約アルゴリズムには深刻な脆弱性が存在します。

ここで単純化のために署名にはAliceおよびBobの二名だけが参加するものとしましょう。

Aliceは秘密鍵として a を生成し、公開鍵として A := aG をBobに渡します。

Bobは正しい鍵生成アルゴリズムには従わずに

B := pG - A

を公開鍵として提出します。

すると、集約公開鍵は

P := A + B = pG

となり、この離散対数である p はBobの知るところとなりますので、Bobはこの情報を用いてAliceの協力を得ることなく「正しい」署名を作れてしまうことになります。

このような攻撃はrogue key攻撃と呼ばれており、準同型性のあるSchnorr署名などでもこのような単純な構成で署名集約を実装しようとすると同様の攻撃ができてしまいます。

集約された署名は「AliceとBobが両者とも合意した」ということを証するものですので、Bobだけで署名が作れてしまっては意味がありません。

修正されたBLS署名集約

そこで、上記の古典的な署名集約アルゴリズムを修正し、次のようにしてみましょう。

まず、ハッシュ関数Hとして、n個の楕円曲線上の点を取り、n個の巨大整数を出力するものを用意します。

そして、署名集約アルゴリズムを次のように修正します。

すなわち、まずは公開鍵たちのハッシュ値を(t_1, \cdots, t_n)とおき

(t_1, \cdots, t_n) = H(P_1, \cdots, P_n)

これらt_nで重み付けをしてから署名を足し合わせたものを集約署名とします。

\sigma := t_1 \sigma_1 + \cdots t_n \sigma_n

このとき、集約公開鍵を集約署名と同様に

P := t_1 P_1 + \cdots t_n P_n

と計算すると、署名検証は

e(G, \sigma) = e(P, M) \quad\quad \cdots (2)

という式が成り立つかどうかをチェックします（演習問題③）。

このように署名集約アルゴリズムを構成してあげると、rogue key攻撃を防ぐことができます。

なおセキュリティの証明については難しいため[3]を参照してください。

感想とか

Schnorr署名でrogue key攻撃を防ぐ署名集約アルゴリズムであるMuSig[4]やその改良版であるMuSig-DN[5]などではかなり複雑なアルゴリズムとなっていましたが、BLS署名バージョンの署名集約アルゴリズムは比較的「素直な」見た目をしていたと思います。

暗号アルゴリズムは一般に、よりシンプルな方が理論上も実装上も脆弱性が入り込む余地が少なく、またより多くのプログラマに理解してもらいやすいため、そういった点に限れば優れていると思っています。

ですので、こうしたシンプルな方法で実装される本アルゴリズムは非常に有用性が高いと思われます。

特に、署名集約技術は大量の署名を効率よく検証できるという点において、大量の電子署名の検証を行う必要があるブロックチェーンアプリケーションについては必須技術であると言えるため、今後実装やセキュリティ的な検証などが進んでいき、当たり前のように使えるようになるとスケーリングなどに対しても非常に有効性の高い対抗馬となりうるでしょう。

ただ、BLS署名は本質的にペアリングを用いるわけですが、ペアリングが高効率で計算できる楕円曲線においては、ペアリングを用いることで決定性Diffie-Hellman問題がすぐさま解けてしまう（≠計算性Diffie-Hellman問題）などの理由から、個人的には何らかの脆弱性があるような気がしており、純粋なDLP仮定を用いているSchnorr署名と比べた安全性には疑問を持っています（もっとも1%以下の確率だと思いますが……）。

一方でBLS署名は署名長が短いという性質が、データ量に対して非常にシビアであるブロックチェーンアプリケーションについては非常に相性が良く、ここらへんのもやもやがいつの日か取れてくれればいいな〜、なんて思っていたりもします（杞憂かもしれませんが……）。

ところで、上記の修正されたBLS集約署名アルゴリズムは、Schnorr署名などでも同様の修正を行うことで適用できるような気もしているのですが、原文を見る限りそういった議論はされておらず、いずれ考えてみたい個人的な課題になっています。

数学に自身のある方は、上記のアルゴリズムがSchnorr署名などにも適用できるのか、適用できないとしたらどういった問題点があるのか考えていただき、ぜひ弐号まで教えてくださいね！

それでは、長くなりましたがお付き合いいただきありがとうございました！

最後により深く理解するための演習問題をおいておきますので、ぜひお時間のある方は解いてみてください！

演習問題

①：古典的集約署名アルゴリズムの健全性

(i)：ペアリング同士の積

ペアリング同士の積が、

e(aG, X) e(bG, Y) = e(G, aX + bY)

を満たすことを示せ。

(ii)：健全性

複数の署名が正しい手続で作成されたものであれば、(1) 式が成立することを示せ。

②：同一メッセージに対する古典的集約署名アルゴリズム

e(P_1, M) \cdots e(P_n, M) = e(P_1 + \cdots + P_n, M)

を示せ。

③：修正されたBLS集約署名アルゴリズムの健全性

署名が正当な方法で生成されたものであれば、式(2)が成り立つことを示せ。

リファレンス

演習問題回答

ここから先は、会員限定のコンテンツになります。残り全てを見るには、サロン入会案内ページから会員登録をよろしくおねがいします。

関連記事