Schnorr署名を使用した複数署名

# はじめに

[bip-schnorr](https://qiita.com/tnakagawa/items/09cb30b84e5564aaad10)を使用して複数署名（Multisignature、マルチ署名）を行う手順について書いていきます。

Schnorr署名が有効になった後のBitcoinを考えます。
例えば、3人のユーザが作成した公開鍵にBitcoinを送信します。
この公開鍵は3人のユーザが署名しなければ使用できません。
今でも、`OP_CHECKMULTISIG`や`OP_CHECKMULTISIGVERIFY`を使用すれば可能ですが、3つの署名が必要となります。
ここでの、手順では1つの署名で十分です。

以前に書いた以下を参考にしています。
https://gist.github.com/tnakagawa/0c3bc74a9a44bd26af9b9248dfbe598b

Blockstreamが新しいマルチ署名の手順を書いています。
[MuSig: A New Multisignature Standard
](https://blockstream.com/2019/02/18/musig-a-new-multisignature-standard/)

以前のQiitaに投稿した、[MuSig（解説）](https://qiita.com/tnakagawa/items/b3d70667a559016aa193)で説明しています。

## 準備

※：ここで使う変数、関数などは、付録の方法で記述しています。

- $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$」における曲線「$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](https://en.wikipedia.org/wiki/Elliptic_curve#The_group_law)
    - 整数と点の乗算は、次を利用します。[Multiplication of an integer and a point](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication)
- 関数と演算子
    - 「$||$」はバイト配列を連結したものを返します。
    - 「$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$は整数で、[ヤコビ記号](https://en.wikipedia.org/wiki/Jacobi_symbol)を返す。$x^{(p-1)/2} \pmod{p}$