BitcoinでMuSig2＊をサポートするためのBIP-327

MuSigは、Schnorr署名でn-of-nのマルチシグを実現するにあたって、Rogue-Key攻撃に対する堅牢性を備えた署名プロトコル。MuSigは

署名に使用するPublic nonceのコミットメントの交換
Public nonceの交換
部分署名の作成、交換

という3ラウンドの通信を必要としたけど、最初のPublic nonceのコミットメントの交換を不要にして2ラウンドにしたのが2020年に提案されたMuSig2↓

techmedia-think.hatenablog.com

そして、これを実際にBitcoinに適用するための提案が最近BIP-327として登録された↓

https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki

MuSig2＊

BIP-327で採用しているのは、正確にはMuSig2＊というMuSig2を少し最適化した亜種になる。MuSig2のペーパーのAppendix Bに掲載されているけど、違いは集約公開鍵を計算する際の乗算コストを削減する点。

MuSigでは、集約公開鍵を計算する場合、Rogue-Key攻撃への対策として、単純に全公開鍵を加算するのではなく、各公開鍵に係数を乗算した上で加算するようになっている。参加者の個々の鍵ペアを ${X_i = x_iG}$ 、集約対象のすべての公開鍵のリストを ${L = (X_1, ..., X_n)}$ とすると、

最初に、集約の際に各公開鍵に乗算する係数 ${a_i = H(L, X_i)}$ として計算する。
計算した各係数を対応する公開鍵に乗算して集約公開鍵を計算する。つまり、 ${X_{agg} = \sum_{i=1}^n a_iX_i}$

MuSig2＊では、公開鍵のリストの２番めの公開鍵（ ${X_2}$ ）について、乗算する係数を↑の ${a_2}$ ではなく定数１を使用する。つまり１つの公開鍵分、 ${a_i * X_i}$ の計算コストを削減する最適化を行うのがMuSig2＊。

BIP-327の各アルゴリズム

BIP-327で定義されている各アルゴリズムは↓

鍵生成と集約系のアルゴリズム

個々の公開鍵の生成（IndividualPubkey）

各参加者の鍵生成プロセス。通常の鍵生成と同じで、秘密鍵から公開鍵を計算し、33バイトの圧縮形式の公開鍵を出力する。

鍵のソート（KeySort）

公開鍵を集約する前に公開鍵のリストをソートするアルゴリズム。ソートは必須ではなくオプション。33バイトの圧縮公開鍵のリストを入力として受け取り、辞書順にソートした公開鍵のリストを出力する。

公開鍵の集約（KeyAgg）

33バイトの圧縮公開鍵のリストを受け取り、集約公開鍵を計算するアルゴリズム。アルゴリズムは、BIP-340互換のx-only公開鍵を導出するために必要なtweak値を持つKeyAgg Contextを出力し、KeyAgg ContextはBIP-340互換のx-only公開鍵を出力する。

１． 33バイトの公開鍵のリストを連結し、タグ付きハッシュを計算

L = H('KeyAgg list', <リストの公開鍵を連結したデータ>)

２． 2番めの公開鍵以外について、係数 ${a_i}$ を計算（２番めの公開鍵の係数は1）

a_i = int(H('KeyAgg coefficient', L + <i番目の公開鍵>))

３．各公開鍵に２で計算した係数を乗算

X_i = a_i * <i番目の公開鍵>

４．３の公開鍵をすべて加算したものが集約公開鍵

集約の際は、↑の係数の計算とMuSig2＊による２つめの公開鍵への定数の適用から、公開鍵の順番が異なると異なる集約公開鍵が導出される。これについて、KeyAggアルゴリズム自体では、明示的に公開鍵のソートはせず、必要であれば別途集約前に↑のKeySortアルゴリズムでソートすることとしている。

KeyAgg Contextは、集約した結果の楕円曲線上の点と、適用された調整の累積値（後述）と符号反転を追跡する値を持つ。

集約公開鍵の微調整（ApplyTweak）

KeyAggで集約した集約公開鍵に対して、微調整を行う際のアルゴリズム。

単純にn-of-nのマルチシグを実現するだけならこの微調整は必要ないが、次のようなユースケースでは微調整が必要になる。

マルチシグ以外に、Taprootのスクリプト条件にコミットした集約公開鍵を作る場合
微調整前のKeyAgg Contextの公開鍵がTaprootの内部鍵になり、Tapscriptのルートハッシュ値から作られる公開鍵を加算する必要がある。
BIP-32を使って、集約公開鍵から子鍵を導出する場合

ApplyTweakアルゴリズムは、KeyAgg Contextと調整値（tweak）と調整モード（is_xonly）を入力として受け取り、調整を適用したKeyAgg Contextを出力する。調整モードは調整時にx-only公開鍵を使うかプレーンな33バイトの公開鍵を使うかを決めるパラメーター。↑のユースケースでは前者はx-onlyの調整が必要で、後者はプレーンな調整になる。

nonceの生成（NonceGen）

署名を作成する際に使用するnonceを生成するアルゴリズム。BIP-340の署名やRFC6979のように決定論的なnonce生成は、MuSig2ではセキュリティ上使用できない（詳細はこちら）。

基本的にnonceはランダムに生成するけど、偶然にも一様にランダムに生成されなかった場合を想定して、そのような場合が万が一あったとしても秘密鍵の漏洩を防げるように、入力（公開鍵に加えてオプションで秘密鍵、集約公開鍵、署名対象のメッセージ、補助入力）を使用してnonceの値が変わるような多層防御の仕組みを組み込んでいる。

MuSig2ではPublic nonceのコミットメントの交換ラウンドを排除するため、１つの署名ラウンドで複数個のnonceを生成するようになってる。BIP-327では2個nonceを生成するようになっており、このアルゴリズムの出力は↓

2つのnonceと公開鍵を結合したバイト列（nonce k1 || nonce k2 || 公開鍵）
2つのnonceに対応するそれぞれのPublic nonce（R1 = k1G || R2 = k2G）

署名セッションで署名参加者は、まずこのPublic nonceを他の参加者に送信する（これが署名時の最初の通信ラウンド）

nonceの集約（NonceAgg）

各参加者が別の参加者のPublic nonceのリストを受け取り、集約するアルゴリズム。

各Public nonceには、２つのPublic nonceR1、R2が含まれているので、ここでは、

すべてのPublic nonceのR1を合算
すべてのPublic nonceのR2を合算

して、2つの楕円曲線上の点が計算できるので、それぞれを33バイトの公開鍵としてエンコードし連結した値を出力する。※ ここで集約したPublic nonceがそのまま集約署名のPublic nonceになる訳ではない。

集約署名のPublic nonce

MuSig2では、集約署名のPublic nonceは

全参加者のPublic nonce R1の合算値 + 係数 * 全参加者のPublic nonce R2の合算値

として計算される。ここでR2の合算値に乗算する係数は、

NonceAggの値
集約公開鍵
署名対象のメッセージ

を連結したタグ付きハッシュ値（タグはMuSig/noncecoef）で、決定論的に導出される。

この係数をR2のPublic nonceに乗算して最終的な集約署名のPublic nonceを導出することで、MuSig2ではPublic nonceのコミットメントラウンドを省略可能にしている。

署名（Sign）

各参加者がそれぞれ個別の署名を生成する際のアルゴリズムは、自分が生成したnonce（自分のk1とk2）と秘密鍵（x_i）を使って、部分署名

s = k1 + b * k2 + e * a_i * x_i

を計算する。ここで、eは集約署名のPublic nonce || 集約公開鍵 || 署名対象のメッセージのタグ付きハッシュ（タグはBIP0340/challenge）。a_iは（Rogue-Key対策で）集約公開鍵を導出する際に乗算した係数。

部分署名を計算したら、これを他の参加者（もしくは署名の集約者）に送信する。これが2ラウンドめの通信。

部分署名の検証（PartialSigVerify）

部分署名が有効かどうか検証する際のアルゴリズム。

部分署名（s）
全参加者のPublic nonceのリスト
署名者のインデックス（i）

を入力として受け取り、Public nonceのリストからNonceAggを実行して集約したR1とR2を計算し、

sG = R1 + b * R2 + e * a_i * X_i

が成立するか、Schnorr署名の検証を行う。この検証が失敗する場合、その部分署名を提供した署名者が不正な署名を送ったことになる。すべての参加者の部分署名がこの検証をパスする場合、署名の集約で有効なSchnorr署名を完成できる。

最後の署名者のみ利用可能な決定性署名（DeterministicSign）

MuSig2では、署名にあたって最初にnonceを生成して他の署名者のPublic nonceを受け取るまでそれらのデータを保持する必要があるという意味でステートフルな構成になる。ただ、署名参加者の内、1人だけならこれをステートレスにすることができる。この署名者は、他の参加者の全Public nonceを受信するまで待機して、その後NonceGen、NonceAgg、Signの各アルゴリズムを一斉に実行し、自分のPublic nonceと部分署名を一緒に他の参加者に送信する。このオペレーションが可能なのは全参加者の中で1人のみで、ステートレス署名者とも呼ばれる。

↑で、MuSig2では決定論的にnonceを生成することはできないとしたけど、このようなステートレスなオペレーションの場合、他の参加者のすべてのPublic nonceを受信した後に実行されるので、自分のnonceは決定論的に生成することができる。

DeterministicSignアルゴリズムは、このように決定論的に導出したnonceを使って決定性署名を作成するアルゴリズム。この決定性nonceは、

自分の秘密鍵
自分以外の署名者のPublic nonceの集約値
集約公開鍵
署名対象のメッセージ
0 or 1（0 = k1, 1 = k2）

を使ったタグ付きハッシュ（タグはMuSig/deterministic/nonce）で計算される。

決定性nonceが導出されたら、それを使って（Sign アルゴリズムで）部分署名を生成して、生成したPublic nonceと部分署名を出力する。

部分署名の集約（PartialSigAgg）

各署名者が生成した部分署名を集約するアルゴリズム。集約Public nonceのx座標と部分署名の合算値を出力（R.x, s）。

以上が、BIP-327で定義されてるアルゴリズム。アルゴリズムの詳細については、BIP本体を参照。

bip-schnorr gemで実装

BIPの参照実装とTest Vectorを参考にbip-schnorr gemにもMuSig2＊を実装してみた↓

require 'schnorr'

sk1 = 1 + SecureRandom.random_number(Schnorr::GROUP.order - 1)
pk1 = (Schnorr::GROUP.generator.to_jacobian * sk1).to_affine.encode

sk2 = 1 + SecureRandom.random_number(Schnorr::GROUP.order - 1)
pk2 = (Schnorr::GROUP.generator.to_jacobian * sk2).to_affine.encode

pubkeys = [pk1, pk2]

# 公開鍵の集約
agg_ctx = Schnorr::MuSig2.aggregate(pubkeys)
# 公開鍵の集約（微調整バージョン）
agg_ctx = Schnorr::MuSig2.aggregate_with_tweaks(pubkeys, tweaks, modes)

## 集約公開鍵は
### 楕円曲線上の点は↓
agg_ctx.q
### x-only公開鍵のhex値は↓
agg_ctx.x_only_pubkey

msg = SecureRandom.bytes(32)

# nonceを生成
sec_nonce1, pub_nonce1 = Schnorr::MuSig2.gen_nonce(
        pk: pk1,
        sk: sk1,  # optional
        agg_pubkey: agg_ctx.x_only_pubkey,  # optional
        msg: msg, # optional
        extra_in: SecureRandom.bytes(4),  # optional
        rand: SecureRandom.bytes(32)  # optional
)

## ステートレス署名者の場合のnonce生成
agg_other_nonce = described_class.aggregate_nonce([pub_nonce1])
pub_nonce2, sig2 = described_class.deterministic_sign(
        sk2, agg_other_nonce, pubkeys, msg, 
        tweaks: tweaks, # optional
        modes: modes, # optional
        rand: SecureRandom.bytes(32)  # optional
)

# nonceの集約
agg_nonce = Schnorr::MuSig2.aggregate_nonce([pub_nonce1, pub_nonce2])

# 部分署名の作成
session_ctx = Schnorr::MuSig2::SessionContext.new(
        agg_nonce, pubkeys, msg, 
        tweaks, # optional
        modes # optional
)
sig1 = session_ctx.sign(sec_nonce1, sk1)

# 部分署名の検証
signer_index = 0
session_ctx.valid_partial_sig?(sig1, pub_nonce1, signer_index)

# 署名の集約
sig = session_ctx.aggregate_partial_sigs([sig1, sig2])

# 通常のSchnorr署名の検証
Schnorr.valid_sig?(msg, agg_ctx.x_only_pubkey, sig.encode)

Develop with pleasure!

福岡でCloudとかBlockchainとか。