はじめに
bip-schnorrを使用して複数署名（Multisignature、マルチ署名）を行う手順について書いていきます。
Schnorr署名が有効になった後のBitcoinを考えます。
例えば、3人のユーザが作成した公開鍵にBitcoinを送信します。
この公開鍵は3人のユーザが署名しなければ使用できません。
今でも、OP_CHECKMULTISIGやOP_CHECKMULTISIGVERIFYを使用すれば可能ですが、3つの署名が必要となります。
ここでの、手順では1つの署名で十分です。
以前に書いた以下を参考にしています。
https://gist.github.com/tnakagawa/0c3bc74a9a44bd26af9b9248dfbe598b
Blockstreamが新しいマルチ署名の手順を書いています。
MuSig: A New Multisignature Standard
以前のQiitaに投稿した、MuSig（解説）で説明しています。
準備
※：ここで使う変数、関数などは、付録の方法で記述しています。
- $u$人のユーザ
- 各ユーザの公開鍵$P_1,\ldots,P_u$
- $c=\text{hash}(\text{bytes}(P_1)||\cdots||\text{bytes}(P_u))$
- $\mu_1=\text{int}(\text{hash}(c||1))\mod{n},\ldots,\mu_u=\text{int}(\text{hash}(c||u))\mod{n}$
- $P=\mu_1P_1+\ldots+\mu_uP_u$
- $m$はメッセージでバイト配列です。
署名
ステップ1
各ユーザ$(i=1,\ldots,u)$は、ハッシュ値$(h_i)$と乱数点$(R_i)$を計算します。
- 秘密鍵を$d_i$とします。$(1\le d_i\le n-1)$
- $k_i=\text{int}(\text{hash}(\text{bytes}(d_i)||m))\mod{n}$
- $R_i=k_iG$
- $h_i=\text{hash}(\text{bytes}(R_i))$
ステップ2
各ユーザ$(i\in1,\ldots,u)$は、ハッシュ値$(h_i)$を他ユーザ$(j\in 1,\ldots,u\ j\ne i)$に送信します。
ステップ3
他ユーザ$(j\in 1,\ldots,u\ j\ne i)$のハッシュ値を全て受信したら、各ユーザ$(i\in1,\ldots,u)$は、乱数点のバイト配列$\text{point}(R_i)$を他ユーザ$(j\in 1,\ldots,u\ j\ne i)$に送信します。
ステップ4
各ユーザ$(i\in1,\ldots,u)$は、次を行い署名値$(s_i)$を計算します。
- 全ての他ユーザ$(j\in 1,\ldots,u\ j\ne i)$について次をチェックします。
- $h=\text{hash}(\text{bytes}(R_j))$を計算します。
- $h_j\ne h$の場合、全ての処理は失敗で終わります。
- $k_i=\text{int}(\text{hash}(\text{bytes}(d_i)||m))\mod{n}$
- $R=R_1+\ldots +R_u$
- もし$\text{jacobi}(\text{y}(R))\ne 1$ならば、$k_i=n-k_i$とします。
- $e=\text{int}(\text{hash}(\text{bytes}(\text{x}(R))||\text{bytes}(P)||m))\mod{n}$
- $s_i=\text{bytes}(k_i+e\cdot\mu_i\cdot d_i\mod{n})$
各ユーザ$(i\in1,\ldots,u)$は、署名値$(s_i)$を他ユーザ$(j\in 1,\ldots,u\ j\ne i)$に送信します。
ステップ5
各ユーザ$(i\in1,\ldots,u)$は、チェックを行う。
- $R=R_1+\ldots +R_u$
- $e=\text{int}(\text{hash}(\text{bytes}(\text{x}(R))||\text{bytes}(P)||m))\mod{n}$
- 全ての他ユーザ$(j\in 1,\ldots,u\ j\ne i)$について次をチェックします。
- $s_j\ge n$の場合、全ての処理は失敗で終わります。
- $R'=s_jG-e\cdot\mu_jP_j\ \ $
- $\text{infinite}(R')$または、$\text{x}(R')\ne\text{x}(R_j)$の場合、全ての処理は失敗で終わります。
ステップ6
いずれかのユーザが署名値を生成します。
- $R=R_1+\ldots +R_u$
- $s=s_1+\ldots +s_u\mod{n}$
- 署名値は、$\text{bytes}(\text{x}(R))||\text{bytes}(s))$となります。
さいごに
お互いの秘密鍵や乱数を知らずとも、楕円曲線(EC)の準同型性をうまく使用して、署名を作成することができます。
付録
bipshcnorr仕様
ここで使う関数の定義などを書きます。
以下のドキュメントが原文となります。
https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#Specification
- 小文字の変数は、整数またはバイト配列を表します。
- 「$p$」は有限体のサイズで固定値となり、次の整数です。
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F(Secp256k1のサイズ） - 「$n$」は曲線の位数で固定値となり、次の整数です。
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141(Secp256k1の曲線位数)
- 「$p$」は有限体のサイズで固定値となり、次の整数です。
- 大文字の変数は、剰余「$p$」における曲線「$y^2=x^3+7$」上の点を表します。
- 「$\text{infinite}(P)$」は、点$P$が無限遠点かどうかを判定します。
- 「$\text{x}(P)$」「$\text{y}(P)$」は、それぞれ点$P$の$x$座標と$y$座標を返します。（無限遠点でない場合）
- 「$G$」を生成元とし、$\text{x}(G)$は
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798、$\text{y}(G)$は0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8となります。 - 点の加算は、次を利用します。elliptic curve group operation
- 整数と点の乗算は、次を利用します。Multiplication of an integer and a point
- 関数と演算子
- 「$||$」はバイト配列を連結したものを返します。
- 「$x[i:j]$」$x$はバイト配列で$i$番目から$j$番目をコピーした$(j-i)$バイトを返す。
- 「$\text{bytes}(x)$」$x$は整数で、$x$の長さ32のバイト配列(上位側から)を返す。
- 「$\text{bytes}(P)$」$P$は点で、$\text{bytes}(\text{0x02}+(\text{y}(P)\&1)) ||\text{bytes}(\text{x}(P))$を返す。
- 「$\text{point}(x)$」$x$は長さ33のバイト配列で、点$P$を返す。$\text{x}(P)=\text{int}(x[1:33])$、$\text{y}(P)\&1=\text{int}(x[0:1])-\text{0x02})$
- 「$\text{int}(x)$」$x$はバイト配列で、整数(上位側から)を返す。
- 「$\text{hash}(x)$」は、$x$はバイト配列で、
SHA256の結果を長さ32のバイト配列で返す。 - 「$\text{jacobi}(x)$」は、$x$は整数で、ヤコビ記号を返す。$x^{(p-1)/2} \pmod{p}$