LayerXでイーサリアムのプロトコル開発やコントラクトのコード監査事業をメインに行なっているOsuke(@zoom_zoomzo)です。今回は、ブロックチェーンベースのプロトコルであるDfinityで用いられているBLS署名について解説していきます。
今回の主眼はDfinityプロトコルの仕組みについてではなく、あくまでもBLS署名に関してです。BLS署名をどのようにブロックチェーンネットワークに応用しているのか、具体的な活用事例としてDfinityを例に紹介していきます。
Dfinityコンセンサスの概要
BLS署名について解説する前にまずはDfinityとは一体なんなのか、どのようなコンセンサスアルゴリズムから成っているのかということを見ていきます。
そもそもDfinityとは、イーサリアムのようにブロックチェーンベースのプラットフォームであり、スマートコントラクトを動作させる分散的なネットワークを構築を目指すプロジェクトです。2018年9月現在ではメインネットにはリリースしていなく、明確なリリース時期は定かではありませんが2018年末〜2019年始めに予定されています。
Dfinityのパフォーマンス的な特徴でいうと、ブロック生成時間が約5秒、ファイナリティが約7.5秒、分散ネットワークのクライアント数が数百万オーダーが実現できることが想定されています。
このように現状のイーサリアムと比べるとはるかに良いパフォーマンスをどのように実現しようとしているのでしょうか。ここでは、そのハイパフォーマンスの根源となるコンセンサスアルゴリズムの仕組みの概略について見ていきます。
まず、DfinityコンセンサスではPoWに基づくマイニングは行なっておらず、PoSに基づくステーキングベースのコンセンサスアルゴリズムです。つまり、コンセンサスアルゴリズムに参加するためにはある一定のトークンをステーキングする必要があります。ここでステークするトークンはDfinityのネイティブトークンであり、dfinitiesやDFNなどと表記されます。
また、一般的なPoSでは、「ステークするトークン量に応じてバリデーターになれる確率が多くなる」といったアルゴリズムが適用されることが多いですが、Dfinityの場合は全てのクライアントで固定のステーク額となっています。
それでは、どのようにしてPoSにおけるバリデーターを選出しているのでしょうか。全てのクライアントのステーク額が同じであったら、そもそものPoSのロジックである、「不正リスクに応じた報酬」を与えることができません。つまり、どのバリデーターも負っているリスクは同じということになるので、バリデーターが不正する余地を与えないことが必要になってしまいます。（あくまでもステーキングはシビルアタック対策として使われることになるため）
コントリビューション度合いが平等なバリデーター候補群からバリデーターを選出するためには、少なくともバリデーターは完全にランダムに選出する必要があることが分かります。しかし、ブロックチェーンのような分散ネットワークで参加者の誰からも予測したり、バイアスのかからないランダム値を生成することは簡単ではありません。そして実は、まさにこのランダム値の生成に当記事の主題であるBLS署名が用いられているのです。
詳しく見ていきましょう。
この図におけるRandom ValueがBLS署名です。まず、何らかの方法（後述）で生成したBLS署名をランダム値として活用して、ネットワークに参加しているクライアントの中からBlock MakersやNotaryをランダムに選出します。Block Makersの役割はユーザーから受け取ったトランザクションを元にブロックを生成することです。Notaryの役割は、Block Makersから送られてきたブロックが正当かどうか検証し、署名をすることです。この署名がまさにBLS署名であり、このBLS署名自体が次のブロック高のランダム値として利用されるのです。
つまり、ブロック高Hのブロックに対するNotaryによる署名がブロック高H+1のBlock MakersとNotaryのランダム選出に用いられ、これがリレー式に繰り返されていくのです。また、Notaryは約400人程度のグループであり、そのグループのうちの201人以上が署名をするとBLS署名が生成し、ランダム値として利用されることになります。
また、Block Makersの選出に用いられるランダム値は具体的にはBlock Makers候補となる優先順位付けされたリストの生成のために用いられます。これは、Probabilistic Slot Protocol(PSP, 確率的スロットプロトコル）と呼ばれ、優先順位順にブロックの生成許可時間やブロックweightが設定され、selfish miningやNothing at Stake問題の対策などにも活用されるfork-choice ruleを定めています。Probabilistic Slot Protocol自体もかなり面白いトピックになりますが話が脱線してしまうのでここでは省略します。
ちなみにこのPSP自体もBLS署名のランダム値に大きく依存しています。
つまり、BLS署名によるランダム値がコンセンサスアルゴリズムの根幹となっていることが分かります。それでは、この閾値を設定した署名生成がどのような仕組みで行われているのか見ていきましょう。
前提知識
ここでは、まずBLS署名やJoint-feldman DKGを理解するための前提知識について触れていきます。
楕円曲線暗号
楕円曲線暗号とは、さまざまな場面で一般的に用いられている暗号技術でRSA暗号などの有限体上の暗号技術と比較して鍵長が短いとことが特徴です。ビットコインやイーサリアムなどはECDSA（楕円曲線DSA）をデジタル署名として活用しています。ECDSAについてはこちらの記事で詳しく解説しています。
一般的に、楕円曲線上の演算において「楕円曲線上の点Pとn倍したnPが与えられた時にnを求めることが非常に難しい」という離散対数問題(DLP)が知られており、楕円曲線暗号ではこのDLPを元に適用されることになります。
ペアリング
ペアリングとは、上述の楕円曲線の世界から有限体の世界へつなぐ架け橋です。ちなみに、有限体とは四則演算に対して閉じている有限の集合のことを言い、群は加法と乗法が閉じているより抽象的な集合のことを言います。
楕円曲線と有限体は巡回群（数字が繰り返される群）として抽象化し、同一的に理論化されることが多いものの、それぞれは異なる集合になります。ところが、ペアリングは以下のように楕円曲線G上の２個の点の組みからある有限体Gtへの写像（関数）eとして作用します。
e: G × G → Gt
また、楕円曲線G上の点をそれぞれP, Qとし、2倍、3倍すると写像の値が2乗、3乗される性質があり、これをペアリングの双線形性と言います。このペアリングの双線形性がBLS署名の検証に用いられます。
e(2P, Q) = e(P, Q)²
e(3P, 2Q) = e(P, Q)⁶
Shamir’s Secret Sharing Scheme （SSSS, シャミアの秘密分散法）
シャミアの秘密分散法とは、ある秘密にしたいデータを分割しそれらをユーザーに配布し、その後特定の数の分割データが再び集まれば元の秘密データを復元できるという手法です。
この秘密分散は、(k-1)次多項式においてk個以上の点が集まればその多項式が一意に定まる性質を用いて行われます。つまり、定数項を秘密データにしておくことでその多項式が復元し、秘密データも復元できるということです。
例えば、秘密データが3の時、f(x) = 3 + 5x + 6x²という2次式を用意します。（xの係数は適当です）そして、例えば4人のユーザーにf(x)曲線上の点f(1),f(2),f(3),f(4)を配布します。
f(x)は2次式なので3つ以上の分割データが集まれば、f(x)を復元することができ結果的にf(0)定数項が分かり、秘密データ3が復元できます。
ちなみに、この復元にはラグランジュの補間公式が用いられています。
k=3として、(1, f(1)), (2, f(2)), (3, f(3))を代入すると、
となり、オリジナルの多項式はそれぞれの秘密鍵の線形和で復元できることが分かります。
つまり、分割する個数nと多項式の次数kを任意の値に設定することで「秘密データを400個に分割して201個のデータが集まれば復元」といったことができるということです。
BLS署名
それではBLS署名について見ていきましょう。とは言っても、上述のECDSAを理解していればかなりシンプルな署名方法であると感じるはずです。BLS署名にも楕円曲線が使われますが、イーサリアムなどで利用されているsecp256k1はペアリングの計算に適していません。なので、BLS署名ではペアリングの計算効率性とDLPのトレードオフを考慮して考えられたBLS12–381曲線が利用するのが適しています。
ここでは、それぞれの巡回群に対してe: G0 ×G1 → Gt というペアリングを考えていきます。また、G0, G1のGenerator pointをそれぞれ g0, g1とします。
鍵生成
まず、ユーザーは巡回群の位数未満の整数乱数pkを秘密鍵として生成します。公開鍵は、g1をpk倍したpkg1です。楕円曲線上のDLPから公開鍵pkg1から秘密鍵pkを求めることはできません。
署名
次に、あるメッセージmに対して生成した秘密鍵pkを使って署名する手順を考えます。実際には、メッセージmをG0の元になるようにハッシュ値H(m)を生成します。
そして、署名SはこのH(m)を秘密鍵pk倍したS=pkH(m)になります。公開鍵と同様、H(m)は楕円曲線上の演算が適用されるため、DLPからpkH(m)からpkを求めることはできません。
つまり、BLS署名は単にメッセージのハッシュ値を秘密鍵倍（整数倍）しただけでかなりシンプルであることが分かります。
検証
それでは、メッセージmと署名Sを受け取ったユーザーが確かに相手の秘密鍵によって署名されたことを検証できるのか見ていきます。
BLS署名Sの検証では、ハッシュ値H(m)と署名者の公開鍵P=pkg1を用いて以下の等式が成り立つか確認していきます。
e(P, H(m)) = e(g1, S)
この署名検証に前述したペアリングの双線形性が用いられるのです。
e(P, H(m)) = e(pkg1, H(m)) = e(g1, pkH(m)) = e(g1, S)
となり、公開鍵が正しければ署名Sをペアリングにより算出することができ、上記の等式が成り立つことが分かります。
つまり、これは楕円曲線上の2点P, H(m)のペアリング写像の値とg1, Sのペアリング写像の値が一致していることを確認していることになります。
BLS署名はマルチシグとしてシュノア署名と比較されることが多いですが、シュノア署名と比べて署名サイズが小さく、シュノアでは必要なマルチシグスキームで複数回のコミュニケーションが必要ないこと（当記事では省略）がメリットとしてあげられる一方、署名検証時にペアリングの計算コストが高く時間がかかってしまうことがあげられます。また、このペアリング計算コストの最適化施策も多く提案されています。（ここでの「マルチシグ」はSSSSを適用した閾値署名とは異なるスキームであることに注意してください）
ここで、BLS署名のパラメタについてまとめると以下のようになります。
秘密鍵：pk
公開鍵：pkg1
署名：pkH(m)
つまり、BLS署名では公開鍵も署名もpk整数倍しているだけであることが分かります。これは、上述の秘密分散と相性がよく、BLS署名にSSSSを適用することでBLS閾値署名を扱うことができます。
(t, n)BLS閾値署名
(t, n)BLS閾値署名とは、あるメッセージmに対する署名において、n人のユーザーのうちt人のユーザーによる署名がそれぞれ集まればマスターBLS署名を生成できる閾値署名になります。
マスター秘密鍵pkをSSSSの秘密データf(0)として、例えばf(x) = pk+ 5x + 6x²を考えます。例えば、4人のユーザーに対して以下のようにsecret shareを配布します。
pk1 = f(1)
pk2 = f(2)
pk3 = f(3)
pk4 = f(4)
これらのうち3つ以上が集まればpkが復元できることになります。
1番目のユーザーを見れば、秘密鍵はf(1), 公開鍵はf(1)G, 署名はf(1)H(m)ということになります。3人のユーザーが署名f(1)H(m), f(2)H(m), f(3)H(m)を提示したとすると、前述のSSSSの復元で用いたラグランジュの補間公式に基づいた係数をL1, L2, L3として、(L1f(1)+L2f(2)+L3f(3))H(m)を生成することができます。（Lに関しては重要ではなく、秘密鍵の線形和で復元できることが重要です。）
そして、この署名に対応する公開鍵は(L1f(1)+L2f(2)+L3f(3))Gで、秘密鍵L1f(1)+L2f(2)+L3f(3)に対応することになります。SSSSはこの線形和で復元することができるので、マスター秘密鍵を復元することなくマスター署名を生成することができているのです。（DLPより署名から秘密鍵を求めることはできません
(t, n)BLS閾値署名の問題点
しかし、上記の(t, n)BLS閾値署名ではブロックチェーンネットワークで活用することはできません。なぜなら、最初のマスター秘密鍵を生成する中央集権的な主体の存在が前提となってしまうからです。そもそも、DfinityではBLS署名をランダム値の源泉として活用しているので、誰からも予測することができない値である必要があり、これはマスター秘密鍵を生成する主体の存在と矛盾してしまいます。
さらに、それぞれのsecret shareが本当に元の多項式から生成されたか検証する術がユーザー側にはありません。もしかしたら、ディーラーは適当な値をsecret shareとしてユーザーに配布しているかもしれません。
この問題を解決する方法はいくつかあげられますが、Dfinityでは後述するJoint-feldman DKGを用いて解決しています。この方法のメリットは以下のことがあげられます。
- 署名時には非対話的（最初の鍵生成の時のみ対話的セットアップが必要）
- Uniqueな閾値署名スキーム（グループの誰が署名しても生成するグループ署名は同じ）
- グループ秘密鍵を復元することなく、グループのsecret shareを使い繰り返しグループ署名を生成することができる
Joint-feldman DKG
Joint-feldman DKGとは、FeldmanのVSSをDKGに組み込んだDKGのことを言います。DKG(Distributed key generation)とは、ある一定数のグループメンバーの公開鍵をDKGプロトコルに提示することでそのグループ全体の公開鍵を生成することができるプロトコルです。
Joint-feldman DKGを理解するために、まずFeldmanのVSSについて解説していきます。
Feldman’s Verifiable Secret Sharing Scheme(Feldman’s VSS, Feldmanの検証可能な秘密分散法)
VSSとは、SSSSにおいてディーラー（マスター秘密鍵生成者）から受け取ったsecret share（秘密鍵相当）が本当にSSSSの曲線上の点であるか検証できるようにする手法です。
SSSSの章で用いたf(x) = 3 + 5x + 6x²で考えていきしょう。ディーラーはf(1)などのsecret shareをユーザーに送るだけでなく、以下のコミットメントCを全てのユーザーにブロードキャストします。
C = (C0, C1, C2) = (3G, 5G, 6G)
コミットメントのそれぞれの数字はf(x)の係数が使われています。DLPによりコミットメントC0がブロードキャストされてもマスター秘密鍵は知られることはありません。
そして、f(1)のsecret shareとコミットメントCを受け取ったユーザーは以下の式が成立するか検証することで、受け取ったsecret shareが正しい多項式から得られていることを検証することができます。（下の式は乗法表記で、Iがsecret share、iが係数に相当しています）
例えば、f(1)の場合は、f(1)=14なので、
左辺：f(1)G = 14G
右辺：C0 + C1 + C2 = 14G
で、確かに成立することが分かります。
また現在では、より安全なPedersenのVSSを利用するのが一般的ですが、FeldmanのVSSでも生成される公開鍵のDLPが弱まるわけではないので、Dfinityではプロトコルのシンプルさを優先してFeldmanのVSSを活用しています。（こちらの論文が詳しいです。Secure Distributed Key Generation for Discrete-Log Based Cryptosystems）
ちなみに、PedersenのVSSではコミットメント生成のために２つのGenerator point (G, H)を用います。
以上のように、FeldmanのVSSを用いることでsecret shareの正当性問題は解決することができましたが、まだマスター秘密鍵を生成する中央集権的主体の存在問題が残っています。
Joint-feldman DKG
このFeldmanのVSSをDKGに組み込むことで、正当なsecret shareを持つユーザーのみが参加するグループのDKGプロトコルを活用することができます。つまり、Joint-feldman DKGではグループに参加する正当な公開鍵に関してグループ内で合意を取るためのプロトコルです。
それぞれのユーザーはランダムな多項式上の点を選択し、secret shareを生成します。従来であれば、secret shareはディーラーが配布していたのに対し、ここではそれぞれのユーザーが自身でランダムなsecret shareを生成していることになります。
そして、それぞれのユーザーはsecret shareに対応する公開鍵とFeldman VSSのコミットメントをブロードキャストします。上述のFeldman VSSのプロセスによりコミットメントを用いて、それぞれのユーザーがグループの全てのユーザーのコミットメントによる検証を行います。
もし、不正なshare secretを使ってDKGグループに参加しようとした場合は、他ユーザーがそれをcomplainし検知します。もし、正当なユーザーのsecret shareが不正なユーザーにcomplainされた場合は、実際にsecret shareを送信することで正当性の証明を行うことができます。そして、不正なcomplainをしたユーザーはデポジット没収などの罰を受けることになります。また、complainを受けたユーザーは簡単にsecret shareを再構築することができ、次のフェーズで参加することができます。
このような検証フェーズを経て、DKGには正当なsecret shareに対応する公開鍵のみが登録されるとこになります。そして、十分な数の公開鍵が登録されるとDKGグループの公開鍵が生成されるのです。正常に動作されている限りグループ秘密鍵が生成することはありません。
具体的なセットアッププロセス
Joint-feldman DKGの具体的なセットアッププロセスを見ていきましょう。
実際のDfinityのJoint-feldman DKGでは、大きく4つのフェーズに分かれてグループの登録が行われます。暗号学的に計算コストの高い部分はクライアント側で計算を行い、実際のagreementに関する部分だけオンチェーンのDKGコントラクトで行なっていきます。
- Dealing Phase：secret shareとコミットメントの生成とブロードキャスト
- Complain Phase：不正な公開鍵に対するチャレンジ
- Justification Phase：チャレンジに対するレスポンス
- Registration Phase：不正のないグループ登録とDKGグループ公開鍵の生成
まず、最初のDealing Phaseでそれぞれのクライアントはオフチェーンでsecret shareの生成とそれに対応する公開鍵への暗号化、コミットメントの生成を行い、公開鍵とコミットメントのデータをオンチェーンにトランザクション送信します。
続いてComplain Phaseでは、他のグループメンバーの公開鍵、コミットメントをevent駆動的に情報を受け取り不正はないか各自検証を行なっておきます。もし不正を見つけたら報告のためのトランザクションをDKGコントラクトに送信します。
そして、Justification Phaseにおいてチャレンジを受けたユーザーは上述のようにsecret shareをブロードキャストするなどしてレスポンストランザクションを送信します。
このようなPhaseを経て、不正のない十分な数（約400個を想定）の公開鍵が集まったら、グループ公開鍵が生成し、オンチェーンにグループ登録のためのトランザクションが送信されます。また、アウトプットとして検証ベクトルVgがブロックチェーンに記録されます。VgはFeldmanのVSSにおけるコミットメントととても似ていて、Vg = (v0, v1, …., v(t-1))と表されます。コミットメントと違う点は、最初のvoがDKGグループ公開鍵を表していることです。
この検証ベクトルはグループに参加しているそれぞれのユーザーの公開鍵を復元し、それぞれの署名shareが正しく生成されているのか検証をするために使われます。
例えば、f(x) = 3 + 5x + 6x²において、f(1)のコミットメントが14Gであり、公開鍵はf(1)Gであるので、同じ要領でブロックチェーンに記録された検証ベクトルからグループのそれぞれのユーザーの公開鍵を復元することができます。
一般的に、グループGのユーザーIDがiの公開鍵pkは以下のように復元することが可能です。
また、グループ公開鍵は後述するRecover関数のアウトプットとなるグループ署名の検証のために利用されます。この辺りのセットアッププロセスは実際の実装例を見ると分かりやすいです。（https://github.com/dfinity/dkg/blob/master/example.js）
具体的な署名プロセス
冒頭で説明したように、Dfinityプロトコルではそれぞれのブロック高においてNotaryグループはランダムに選出されます。ブロック高rのNotaryに選出されたグループは、以下のようにブロック高rとブロック高r-1のBLS署名（ランダム値）を結合させたデータに対して、自身のsecret shareで署名を行います。
前回の署名に対して署名を行う理由は、ブロックのwithholdだけでなくnotarizationのwithholdを防ぐためです。セットアップ時に記録しておいた検証ベクトルを使ってそれぞれが提示する署名を検証することができます。閾値署名のために必要な署名が提示されたら、それらの署名をインプットとしてRecover()関数を実行することでグループ署名を生成することができブロック高rにおけるランダム値として利用されることになります。
以上のように、BLS署名とJoint-feldman DKGを用いることでクライアントがグループごとに分かれて、ブロック高毎に一定の閾値のユーザーが署名を送信した場合のみグループ署名が生成され、さらにそれらの署名検証も誰もが行うことができるようになっています。
ただし、以下のような制限・課題点も存在することが分かります。
- コンセンサスネットワークに参加するクライアントは常にオンラインであることが前提（BLS署名生成リレーがストップしてしまう）
- DKGのために複雑なセットアッププロセスが必要であること
- 署名検証時に計算コストがかかりやすい
- （ファイナリティが早く、gasコストが安くなるのは分かるがTPSベースで実際にどれだけの数値が得られるのか）
BLS署名はDfinityをはじめ、OrbsやEthereumのbeacon chainへの導入も検討されています（BLSだとstoppableな性質を持ってしまうのでRNGに利用するのは劣勢ですが、署名のデータサイズを集約するmessege aggregationへの活用は有力です）。ブロックチェーンと相性がよく、さまざまなプロトコルへのさらなる応用も今後考えていきたいです。
最後に
LayerXではブロックチェーン領域の開発に一緒に取り組んでいける仲間を募集しています。今回解説したようなプロトコルレイヤーの研究・開発やSolidity・Vyperを用いたスマートコントラクト領域の開発、トークン設計ベースのプロダクト開発などがメインになります。このような分野に興味のある方はぜひ一緒にやっていきましょう！
