Upgrade to Pro — share decks privately, control downloads, hide ads and more …

BLS署名の集約

 BLS署名の集約

GBECの解説動画のスライドです。
https://goblockchain.network/2022/10/agg-bls/

shigeyuki azuchi

October 13, 2022
Tweet

More Decks by shigeyuki azuchi

Other Decks in Technology

Transcript

  1. 1 署名の集約
 署名の集約=複数の署名を1つの署名に集約すること 
 
 n-of-nのようなマルチシグを単一の署名に集約でき、 
 
 • データスペースの節約


    • 検証コストの削減
 
 というメリットがある。
 
 ※ BLS署名の仕組みについては、以前の動画参照: 
 https://goblockchain.network/2022/09/bls/ 

  2. 2 BLS署名の単純な集約
 • e(G 1 , G 2 ) →

    G T のペアリングが成立し、G 1 とG 2 の生成元をそれぞれPとQとする
 • アリスとボブの鍵ペアをそれぞれ、 Y A = x A Q、Y B = x B Qとする
 • 署名対象のメッセージをmとする
 
 集約公開鍵は、Y = Y A + Y B
 部分署名は、
 • σ A = x A H 1 (m)
 • σ B = x B H 1 (m)
 集約署名は、σ = σ A + σ B
 署名の検証は、e(σ, Q) = e(H 1 (m), Y)が成立するか検証する
 e(σ, Q) = e(σ A + σ B , Q) = e((x A + x B )H 1 (m), Q) 
 = e(H 1 (m), Q)(xA + xB) = e(H 1 (m), (x A + x B )Q) = e(H 1 (m), Y)

  3. 3 BLS署名の単純な集約
 • e(G 1 , G 2 ) →

    G T のペアリングが成立し、G 1 とG 2 の生成元をそれぞれPとQとする
 • アリスとボブの鍵ペアをそれぞれ、 Y A = x A Q、Y B = x B Qとする
 • 署名対象のメッセージをmとする
 
 集約公開鍵は、Y = Y A + Y B
 部分署名は、
 • σ A = x A H 1 (m)
 • σ B = x B H 1 (m)
 集約署名は、σ = σ A + σ B
 署名の検証は、e(σ, Q) = e(H 1 (m), Y)が成立するか検証する
 e(σ, Q) = e(σ A + σ B , Q) = e((x A + x B )H 1 (m), Q) 
 = e(H 1 (m), Q)(xA + xB) = e(H 1 (m), (x A + x B )Q) = e(H 1 (m), Y)
 Rogue-Key攻撃に対して脆弱
 Y B = x B Q - Y A とした場合、
 Y = Y A + Y B = x B Qとなり、
 ボブのみでYに対して有効な署名を計算可能 

  4. 4 Rogue-Key対策
 • Knowledge of Secret Key(KOSK)
 参加者全員に秘密鍵の知識の証明(署名)を求める 
 


    • 集約されるメッセージがすべて異なるようにする 
 この場合、署名は、
 ◦ σ A = x A H 1 (m 1 )
 ◦ σ B = x B H 1 (m 2 )
 署名検証は、公開鍵とメッセージのリストを受け取り、 
 e(σ, Q) = e(H 1 (m 1 ), Y A )・e(H 1 (m 2 ), Y B )
 を検証する。
 ※ 署名の数分、ペアリングの計算が必要で、計算コストが上がる。 
 
 EthereumのBeacon chainが
 採用してるアプローチ
 集約署名 σ = σ A + σ B

  5. 5 Rogue-Key対策
 • 集約時の線形性の破壊
 公開鍵のセットに対しL = Y 1 + …

    + Y N を計算し、a i = H(Y i || L)を計算する。
 ◦ 集約公開鍵は、
 Y = a 1 Y 1 + … + a N Y N (アリスとボブの場合、Y = a 1 Y 1 + a 2 Y 2 )
 ◦ 集約署名は、
 σ = a 1 σ 1 + … a N σ N (アリスとボブの場合、σ = a 1 σ 1 + a 2 σ 2 )
 ※ 集約公開鍵の計算に、各公開鍵毎に係数を乗算しているため、 
  Rogue-Key攻撃が機能しない。
 • 検証はオリジナルのBLSの検証と変わらない 
 ※ Schnorrの集約署名方式MuSigも同様のアプローチ 
 https://goblockchain.network/2019/04/musig/ 
 
 ペアリング計算のコストも最小限に
 Schnorrと違ってPublic nonceを構成するための 
 通信ラウンド(対話)が不要