Compact Multi-Signatures for Smaller Blockchains

概要

前提

BLS署名

Signature Aggregation

$ \sigma = \prod_i \sigma_i

$ \prod_i e(H(M_i), pk_i) \overset{?}{=} e(\sigma, g_2)

Rogue key攻撃

Proof of Possesion

Proof of Possesionは、登録時に一度だけ行い、以降は署名集約のたびに「登録」されていること(=PoPしたこと)を検証すれば良い。EthereumのBeacon chainはこの方式でRogue key攻撃を防いでいる。

しかしながら、登録フェーズが必要なのは手間であるし、集約のたびに登録を確認するのもコストが掛かる。Rogue key攻撃が存在しない集約プロトコルが望ましい。

Rogue key攻撃が存在しないmulti-signature

同一のメッセージに対するsignature aggregationをmulti-signatureと呼ぶ。次のような工夫によってPoP無しだがRogue key攻撃が存在ないmulti-signatureを構成できる。

各署名は

$ e(H(M), pk_i) = e(\sigma_i, g_2)

$ e(H(M), pk_i^{a_i}) = e(\sigma_i^{a_i}, g_2)

ペアリングの双線形性より、上の式が成り立てば下の式も成り立つ。この状態で集約すると、

$ \sigma = \prod_i \sigma_i^{a_i}

$ pk = \prod_i pk_i^{a_i}

$ e(H(M), pk) \overset{?}{=} e(\sigma, g_2)

ように

$ a_i = \mathrm{hash}(pk_i, PK)

と選ぶ。

先ほどと同じように、

$ pk_a^{a_a} = g_2 (pk_b)^{-a_b}

コスト