Schnorr署名と検証可能な秘密分散法を利用したm-of-nのマルチシグスキーム

SchnorrのBIPドラフト↓

https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

に応用例の１つとして記載されているのが、Scnorr署名とペダーセンの検証可能な秘密分散法を利用してm-of-nのマルチシグを構成するというもので、参照論文↓

https://t.co/jMhQnovLcb

をざっと読んで、どう構成なのか見てみる。

前提技術

まず、前提となる暗号技術として、以下のシャミアの閾値法、ペダーセンの検証可能な秘密分散法などについておさえとく。

以下、楕円曲線の離散対数問題を利用するため、qを巨大な素数とし、GとHを楕円曲線Eの位数qのサブグループのジェネレータ、h()を一方向ハッシュ関数とする。

シャミアの(t, n)閾値法

ベースとなるプリミティブの１つが(t, n)閾値法。これはディーラーがある秘密のシークレットをn個のシェア*1に分割し、このシェアをt個集めるともとのシークレットを復元することができるというシャミアの秘密分散法で実現できる。

秘密分散のシェアの作成

秘密のシークレットをs、閾値をtとした場合、ディーラーがn人のパーティに配布する各シェアは、f(0) = s を満たすt-1の次数を持つランダムな多項式

${f(x) = s + a_1x + a_2x^2 + ... + a_{t-1}x^{t-1} \mod p}$

から作られる。

例えば閾値t = 3、シークレットs = 5とした場合の多項式は

f(x) = 5 + ax + bx²

のような式になる。aとbの係数は何でもいいので

f(x) = 5 + 3x + 5x²

とかでも良い、重要なのはf(0) = シークレット値となるt-1次の多項式を決めること。

多項式が決まったら、n人のパーティに配布するシェアをその多項式から生成する。

例えば5人のパーティなら

${x_1 = f(1) = 13 = (1, 13)}$
${x_2 = f(2) = 31 = (2. 31)}$
${x_3 = f(3) = 59 = (3, 59)}$
${x_4 = f(4) = 97 = (4, 97)}$
${x_5 = f(5) = 145 = (5, 145)}$

が各ユーザーに配布するシェアのペアになる。

シェアからシークレットを復元

↑のように分割したシェアの内、t個が揃うとラグランジュの補間公式 ${f(x) = \sum_{i=1}^{t}y_i \frac{f_i(x)}{f_i(x_i)}}$ を使って多項式を復元できる。

上記ではt = 3なのでラグランジュの補間公式は、

${f(x) = y_1\frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)} + y_2 \frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)} + y_3 \frac{(x-x_1)(x-x_2)}{(x_3 - x_1)(x_3 - x_2)}}$

を使って計算すればいい。例えば、(1, 13)、（3, 59）、(4, 97)をそれぞれ↑の式に当てはめると

f(x) = 5 + 3x + 5x²

が算出できる。こうやって復元した多項式からシークレットsの値が何か分かる。

ペダーセンの検証可能な秘密分散法

シャミアの秘密分散法によりシークレットを各ユーザーに分割して渡すことができるが、この場合、各ユーザーに配布されるシェアは本当にシークレットから生成されたものかどうかは、シェアを生成したディーラーを信頼する必要がある。もしディーラーが不正をして誤った値のシェアを配布した場合、t個のシェアを集めても本当のシークレットを復元することはできない。

この問題を解消するのがペダーセンの検証可能な秘密分散法（Verifiable Secret Sharing Scheme＝VSS）。

VSSは以下のように動作する。

ディーラーによるシェアの作成

ディーラーはシークレットsとは別にランダムな整数s'を選択する。
sとs'について、それぞれ別の多項式をランダムに選択する。
${f(x) = s + a_{1}x' + a_{2}x^{2} + ... + a_{t-1}x^{t-1}}$
${f'(x) = s' + b_1x' + b_2x'^2 + ... + b_{t-1}x'^{t-1}}$
多項式f(x)とf(x')を使ってn個のシェアを計算し、シェアのペア ${(s_i, s'_i)}$ を安全な経路で各パーティに送る。
シェアとは別にコミットメント ${C_j = a_jG + b_jH}$ を計算し、ブロードキャストする（jは0≦ j ≦ t-1）。

例えば選択した多項式が以下の場合

f(x) = 5 + 3x + 5x²
f'(x) = 3 + 2x + 7x²

上記手順3でディーラーが各パーティ（n=4）に作成するシェアのペアは↓

(f(1), f'(1)) = (13, 12)
(f(2), f'(2)) = (31, 35)
(f(3), f'(3)) = (59, 72)
(f(4), f'(4)) = (97, 123)

手順4で作成するコミットメントは↓

${C_0 = 5G + 3H}$
${C_1 = 3G + 2H}$
${C_2 = 5G + 7H}$

になる。

各ユーザーの検証

各ユーザーは、個別に受信したペア ${(s_i, s'_i)}$ とブロードキャストされたコミットメントを使って、

${s_iG + s'_iH = \sum_{j=0}^{t-1} \, i^j \, C_j}$

が成立するか検証して、成立すれば自身のシェアは正しいシェアであることが分かる。

例えば、(f(1), f'(1)) = (13, 12)を受け取ったユーザーは、

${13G + 12H = C_0 + C_1 + C_2 = 5G + 3H + 3G + 2H + 5G + 7H}$

が成立するか検証し、(f(2), f'(2)) = (31, 35)を受け取ったユーザーは、

${31G + 35H = C_0 + 2C_1 + 4C_2 = 5G + 3H + 6G + 4H + 20G + 28H}$

が成立するか検証する。

シークレットを含む ${C_0 = 5G + 3H}$ が公開されるが、シークレットの値は ${C_0}$ からは分からない。

これが成立しない場合、受け取ったシェアは不正なシェアになる。

このように公開されたコミットメントと自身が受け取ったシェアを使って、そのシェアが確かにシークレットから生成されたものであるか検証できるようにするのがVSS。

ランダムシークレットの生成

上記の秘密分散法ではいずれも信頼できるディーラーがシークレットを生成し、シェアを作成、配布していたが、これをディーラー抜きで行う。要は、各ユーザーから集めた情報を元にシークレットを生成する。

各ユーザーは以下の手順を実行する。

各ユーザー ${U_i}$ はランダムに値 ${r_i, r'_i}$ を選択する。
※ 参加者数がnの場合、各ユーザーの ${r_i}$ を合算した ${\sum_{i=1}^{n}r_i}$ がシークレットになり、このシークレットを復元する際に使う多項式は、以下の2で各ユーザーが作成した多項式の和で構成される。
続いて各ユーザーはそれぞれ以下の２つの多項式を生成する。
- ${f_i(x) = a_{i0} + a_{i1}x + a_{i2}x^{2} + ... + a_{i t-1}x^{t-1}}$
- ${f'_i(x) = b_{i0} + b_{i1}x + b_{i2}x^{2} + ... + b_{i t-1}x^{t-1}}$
  この時、多項式のシークレット値はそれぞれ ${a_0 = r_i}$ 、 ${b_0 = r'_i}$ とする。
続いて各ユーザーは、 ${0 ≦ m ≦ t-1}$ のコミットメント ${C_{im} = a_{im}G + b_{im}H}$ を計算し公開する。
続いて各ユーザーは、 ${1 ≦ j ≦ n}$ で ${s_{ij} = f_i(j)}$ と、 ${s'_{ij} = f'_i(j)}$ を計算し、計算した値をユーザー ${U_j}$ に送る。
${(s_{ij}, s'_{ij})}$ を受け取ったユーザー ${U_j}$ はそのシェアが正しいか、送信者が公開しているコミットメントを使い ${s_{ij}G + s'_{ij}H = \sum_{m=0}^{t-1} \, j^{m} \, C_{im}}$ で検証する。この１つ１つのシェアの検証に↑のVSSが使われる。
続いて各ユーザーは ${A_{ik} = a_{ik}G}$ を算出し、ブロードキャストする（kは、 ${0 ≦ k ≦ t-1}$ ）。
各ユーザーは、他のユーザーによってブロードキャストされた値が正しい値か、 ${s_{ij}G = \sum_{k=0}^{t-1} \, j^{k} \, A_{ik}}$ が成立するか検証する。

各ユーザーがランラムに選択したシークレットに対する公開鍵は、最後に各ユーザーが公開した ${a_{ik}G}$ のリストの内、全ユーザーの ${a_{i0}G}$ を合算した ${Pub = \sum_{i=1}^{n}a_{i0}G}$ になる。

このプロトコルを実行することで、各ユーザーが生成したランダム値 ${r_i}$ を合算した値を秘密鍵とした際に、それに対応する公開鍵を共有することができる。このプロトコルでは各ユーザーは ${r_i}$ を直接公開しないし、シェアを集めて復元もしていないので実際の秘密鍵rは知られていない。

計算例

実際に↑のプロトコルに沿って計算してみよう。数が多いと大変なので、今回は2-of-3にする。

まず、各ユーザーはそれぞれシークレットを選択し（アリス：３、ボブ：７、キャロル：２）、そのシークレットを使った多項式を以下のように決める。

アリスの多項式
- fa(x) = 3 + 4x
- fa'(x) = 5 + 2x
ボブの多項式
- fb(x) = 7 + x
- fb'(x) = 3 + 5x
キャロルの多項式
- fc(x) = 2 + 7x
- fc'(x) = 8 + 9x

続いて、各ユーザーは多項式の定数項を使ってコミットメントを計算し公開する。

アリスが公開するコミットメント
- Ca0 = 3G + 5H
- Ca1 = 4G + 2H
ボブが公開するコミットメント
- Cb0 = 7G + 3H
- Cb1 = G + 5H
キャロルが公開するコミットメント
- Cc0 = 2G + 8H
- Cc1 = 7G + 9H

続いて、各ユーザーはそれぞれの多項式を利用してf(x)とf'(x)のシェアを計算して、別のユーザーに送る。

アリスが提供するシェア
- (s11, s'11) = (7, 7)
- (s12, s'12) = (11, 9)
ボブが提供するシェア
- (s21, s'21) = (8, 8)
- (s22, s'22) = (9, 13)
キャロルが提供するシェア
- (s31, s'31) = (9, 17)
- (s32, s'32) = (16, 26)

シェアを送られたユーザーはそのシェアが正しい値か送信元が公開したコミットメントを使って ${s_{ij}G + s'_{ij}H = \sum_{m=0}^{t-1} \, j^{m} \, C_{im}}$ を検証する。例えば、アリスが(s12, s'12)=（11, 9）をキャロルに送った場合、キャロルは以下を検証する。

11G + 9H = Ca0 + 2Ca1 = （3G + 5H） + 2(4G + 2H) = 3G + 5H + 8G + 4H = 11G + 9H

続いて、各ユーザーの多項式f(x)の定数項を楕円曲線のベースポイントに乗算して公開鍵を計算し、ブロードキャストする。

アリスが公開する公開鍵
- A10 = 3G
- A11 = 4G
ボブが公開する公開鍵
- A20 = 7G
- A21 = G
キャロルが公開する公開鍵
- A30 = 2G
- A31 = 7G

他のユーザーがブロードキャストした公開鍵が正しいか、送信元から受け取ったシェアを使って ${s_{ij}G = \sum_{k=0}^{t-1} \, j^{k} \, A_{ik}}$ を検証する。例えばキャロルがブロードキャストした公開鍵が正しいかボブが検証する場合は以下を検証する（ボブはキャロルからシェア（16, 26）を受け取っている）。

16G = 2G + 2(7G) = 2G + 14G

各ユーザーがブロードキャストした全ての公開鍵の検証が成功すると、各ユーザーが公開したAi0の公開鍵を加算した点がマルチシグの公開鍵になる。

A10 + A20 + A30 = 3G + 7G + 2G = 12G

これは各ユーザーがランダムに生成したシークレット（アリス：３、ボブ：７、キャロル：２）の共有シークレットに対応した公開鍵となる。

Schnorr署名

残りはSchnorr署名。これはシンプルで、楕円曲線を使う場合（ジェネレータをG、秘密鍵をx、公開鍵をP=xG、署名対象のメッセージをmとする）、その署名は以下のように計算される。

ランダム値kを選択。
R = kGを計算。
s = k + h(P, R, m)x を計算する。
(R, s)がmに対する署名

署名の検証は、sG = R + h(P, R, m)Pが成立するか検証する。

(t, n)閾値署名方式

前提が長かったけど、本題に入る。Schnorr署名を利用したm-of-nのマルチシグスキーム。

実際のSchnorrベースの（t, n）閾値署名は以下の鍵生成プロトコルと署名発行プロトコルで構成される。

鍵生成プロトコル

鍵生成プロトコルでは、↑のランダムシークレット生成のプロトコルを利用して、マルチシグの参加者は、協力して公開鍵と秘密鍵のシェアを生成する。これによりランダムな共有シークレットができる。

このプロトコルの結果、

共有される秘密鍵をx
各ユーザーが持つ秘密鍵 ${r_i}$ のシェアを ${α_i}$
各ユーザーが公開する自身の多項式の定数を使って計算した各点を ${a_{im}G}$ （0 ≦ m ≦ t-1）
公開鍵を ${P = \sum_{i=1}^{n}a_{i0}G}$

とする。

ここで生成した公開鍵宛にコインを送ること＝t-of-nのマルチシグへコインを送ることになる。

署名発行プロトコル

署名対象のメッセージmに対して、鍵生成プロトコルで生成したt-of-nのマルチシグの公開鍵Pに対して有効なSchnorr署名を生成する。この時、協力するユーザーがt人未満の場合は署名は作成できない。

手順１

まず、署名生成にあたって上記のSchnorr署名のプロトコルにあるように、ランダムな値eとその点R = eGが必要となるが、これも鍵生成プロトコルで使用したのと同じランダムシークレット生成のプロトコルを利用して生成することになる。

ランダムシークレット生成のプロトコルを実行した結果を

共有される秘密鍵をe
各ユーザーが持つ秘密鍵eのシェアを ${β_i}$
各ユーザーが公開する自身の多項式の定数を使って計算した各点を ${b_{im}G}$ （0 ≦ m ≦ t-1）
公開鍵を ${R = \sum_{i=1}^{n}b_{i0}G}$

とする。

これで署名に使用するランダムな点R = eGが共有される。

手順２

続いて各ユーザーは、eの計算に使用したシークレットの各シェア ${β_{i}}$ と、共有シークレットを構成するシークレットの各シェア ${α_{i}}$ を使って以下を計算し、公開する。

${\gamma_i = β_i + h(P, R, m)α_i}$

手順3

続いて以下が成立するか検証する。

${\gamma_k G = R + \sum_{j=1}^{t-1} c_{j}k^{j} G + h(P, R, m) \bigl( P + \sum_{j=1}^{t-1} b_jk^{j} G \bigr)}$

※ cは署名に使うランダムな点Rを導出する際の多項式の定数項、bは共有シークレットを導出する際の多項式の定数項で、これらはランダムシークレットの生成プロトコル手順６で公開している。

手順４

手順３が問題なければ、検証が成功したユーザーが提供したデータのうち任意のt個の値を使って、Schnorr署名のsを計算する。

算出するSchnorr署名 s = e + h(P, R, m)xは、共有シークレットの多項式f(x)と、署名用のランダムなシークレットの多項式f'(x)が求まれば、

s = f'(0) + h(P, R, m) f(0) = e + (P, R, m)x

が求まるので、t個の ${γ_k}$ を集めて、ラグランジュの補間公式を使えば、Schnorrの署名値sに必要なデータを復元できる。

計算例

実際に計算してみる。↑のランダムシークレット生成の計算例で使った各ユーザーの２つの多項式を、シークレットの多項式と署名に使うランダムなシークレットの多項式とする。

まず各ユーザーはシークレットと署名用のシークレットを使って以下のγを計算し、公開する。

アリスが公開する
- γ11 = 7 + h(P, R, m)7
- γ12 = 9 + h(P, R, m)11
ボブが公開する
- γ21 = 8 + h(P, R, m)8
- γ22 = 13+ h(P, R, m)9
キャロルが公開する
- γ31 = 17 + h(P, R, m)9
- γ32 = 26 + h(P, R, m)16

公開された値が正しいか手順３の検証を行う。

例えばγ2Gを計算する場合、γ2Gは各ユーザーが公開したγ2を集約して

γ２ = 9 + h(P, R, m)11 + 13+ h(P, R, m)9 + 26 + h(P, R, m)16 = 48 + h(P, R, m)36
γ2G = （48 + h(P, R, m)36）G

となる。これに対して、

${R + \sum_{j=1}^{2-1} c_{j}2^{j} G + h(P, R, m) \bigl( P + \sum_{j=1}^{2-1} b_j2^{j} G \bigr)}$

を計算すると

16G + 2(2 + 5 + 9)G + h(P, R, m)(12G + 2(4 + 1 + 7)G) = 16G + 32G + h(P, R, m)(12G + 24G)
= （48 + h(P, R, m)36）G

となり、γ2Gと一致することが分かる。

最後に署名の作成。手順2で各ユーザーが公開したγの値を使って署名に必要なデータを計算する。γ1とγ2はそれぞれ

γ1 = 7 + h(P, R, m)7 + 8 + h(P, R, m)8 + 17 + h(P, R, m)9
= 32 + h(P, R, m) 24

γ2 = 9 + h(P, R, m)11 + 13+ h(P, R, m)9 + 26 + h(P, R, m)16
= 48 + h(P, R, m) 36

となるので、これをラグランジュの補間公式に当てはめる。今回は閾値は2なので

${f(x) = y_1 \frac{x - x_2}{x_1 - x_2} + y_2 \frac{x - x_1}{x_2 - x_1}}$

を適用すればいいので、(1, γ1)、（2, γ2）を適用すると

${f(x) = (32 + h(P, R, m) 24) \frac{x - 2}{1-2} + (48 + h(P, R, m) 36) \frac{x - 1}{2 - 1}}$ ${f(x) = (16 + 12 h(P, R, m))x + 16 + 12 h(P, R, m)}$

となり、f(0) = 16 + 12 h(P, R, m)。

共有シークレットxは12、署名に使用するeは16であることから、これがそのままSchnorrの署名値sとなる。

というのが論文で紹介されてたm-of-nのマルチシグスキーム。長かった。。

という風に、Schnorr署名単体では閾値署名を生成する特性はないが、秘密分散と組み合わせてm-of-nの閾値署名を生成することができる。ただ、参加者同士での対話や検証が多いので、実装しようとすると結構面倒ではある。。

Bitcoin向けのSchnorrのm-of-nのマルチシグの実現方法としては、こういった暗号技術のみを使用する方法以外にも、↓みたいに公開鍵の組み合わせでマークルツリーを構成してn-of-mのマルチシグを評価するアイディアなんかも紹介されている。

medium.com

*1:シークレットを分割してできた各断片

Develop with pleasure!

福岡でCloudとかBlockchainとか。