Share
Embed
Schnorr署名のハーフアグリゲーション
GBECの解説動画のスライドです。
https://goblockchain.network/2022/11/half-aggregation/
shigeyuki azuchi
November 07, 2022
Transcript
7 slides
-
1 Schnorr署名のハーフアグリゲーション • Schnorr署名の集約 複数の証明者が署名を単一の署名に集約するプロトコル ◦ Schnorrベースの新しいマルチシグ方式 MuSig https://goblockchain.network/2019/04/musig/
◦ MuSig2 https://goblockchain.network/2021/02/musig2/ • ハーフアグリゲーションとは? ◦ 非対話型で、複数のSchnorr署名を 約半分のサイズに集約するプロトコル ◦ 署名者でなくても、誰でも集約が可能 Sig Sig Sig Sig 64 byte ✕ 3 = 192 byteが 64 byteの単一の署名に Sig Sig Sig Sig 32 byte ✕3 + 32byte = 128 byteに (半分+32 byte) -
2 ハーフアグリゲーションの用途 • トランザクション/ブロックの署名の集約
• Lightning Networkのメッセージの署名の集約 Tx In Out UTXO B UTXO A … Sig Sig Sig Block Tx Sig Sig Tx Sig Tx Sig Sig ︙ Sig … Sig Node Node Node Node ノード通知 チャネル通知 Sig Sig Sig Sig 各メッセージの署名を集約することで 通信の帯域幅を削減 (※ 要Schnorr署名への変更) -
3 ハーフアグリゲーション方式 https://eprint.iacr.org/2022/222.pdf • ASchnorr 個々の署名がすべて集まってから集約 • IASchnorr 個々の署名をインクリメンタルに集約
• SASchnorr 順番に集約した署名を復元可能な集約 Half-Aggregation of BIP 340 signatures https://github.com/ElementsProject/cross-input-aggregation/blob/master/ half-aggregation.mediawiki -
4 Schnorr署名 前提: 公開鍵P = xG、署名対象のメッセージをメッセージ mとした場合 Schnorr署名: 1.
nonce kをランダムに選択 2. R = kGを計算 3. s = k + H(P, R, m)xを計算 4. (R.x, s)が署名データ 署名の検証は、sG = R + H(P, R, m)Pを確認 R.x, s共に32バイトのデータであるため、合計64バイト -
5 ASchnorr 前提: 公開鍵P 1 = x 1 G、P 2
= x 2 Gとして、それぞれのメッセージm 1 、m 2 に対する Schnorr署名をσ1 = (R 1 , s 1 )、σ2 = (R 2 , s 2 )とする。 集約手順: 1. L = {(R 1 , P 1 , m 1 ), (R 2 , P 2 , m 2 )}とする 2. 係数 α 1 = H 2 (L, 1)、α 2 = H 2 (L, 2)を計算する 3. s = α 1 s 1 + α 2 s 2 を計算する 4. ({R 1 , R 2 }, s)が集約署名 署名の検証は、sG = α 1 (R 1 + H(P 1 , R 1 , m 1 )P 1 ) + α 2 (R 2 + H(P 2 , R 2 , m 2 )P 2 )を確認 署名者の数分のRと、1つのsの値から、 署名データのサイズは署名者の各Schnorr署名の約半分のサイズに 【係数が必要な理由】 単純にs 1 + s 2 を加算して、s = s 1 + s 2 sG = R 1 + H(P 1 , R 1 , m 1 )P 1 + R 2 + H(P 2 , R 2 , m 2 )P 2 を検証する方式の場合、 R 2 = k 2 - (R 1 + H(P 1 , R 1 , m 1 )P 1 ) と細工することで、x 1 を知らなくても 集約署名の偽造が可能になる。 -
6 IASchnorr ASchnorrの課題 1. L = {(R 1 , P
1 , m 1 ), (R 2 , P 2 , m 2 )}とする 2. 係数 α 1 = H 2 (L, 1)、α 2 = H 2 (L, 2)を計算する IASchnorr 1. L i = {(R 1 , P 1 , m 1 ), …(R i , P i , m i )}とする 2. 係数α i = H 2 (L i )とする 3. s = α 1 s 2 + … + α i s i を計算する 4. ({R 1 , …, R i }, s)が集約署名 https://techmedia-think.hatenablog.com/entry/2022/07/11/200632 各Schnorr署名に適用する係数の計算に 全参加者の以下のデータがすべて必要なため • 公開鍵(P) • Public nonce(R) • メッセージ(m) すべてが揃わないと集約不可能 係数をすべての署名に対してではなく、 順次コミットする署名を追加していく。 L 1 = {(R 1 , P 1 , m 1 )} L 2 = {(R 1 , P 1 , m 1 ), (R 2 , P 2 , m 2 )} L 3 = {(R 1 , P 1 , m 1 ), (R 2 , P 2 , m 2 ), (R 3 , P 3 , m 3 )} ※ インクリメンタルな集約が可能に P 1 , m 1 , s 1, R 1 P 2 , m 2 , s 2, R 2 P 3 , m 3 , s 3, R 3