Develop with pleasure!

福岡でCloudとかBlockchainとか。

Stratum protocol extensionsについて定義したBIP-310

Stratumはプールマイニングをサポートするマイニングプロトコルだが、その拡張の利用については長らく正式な規格を記述するBIPが無かったが、それをBIPとして定義したのがBIP-310↓

github.com

基本的には、Stratumサーバーとマイニングソフトウェアが接続された直後に、mining.configureメッセージを送信してサーバ/クライアント間でサポートしている拡張について認識し、利用する拡張について調整する仕組み。

BIP-310で定義されている拡張は以下の4つ。

  • version-rolling
  • minimum-difficulty
  • subscribe-extranonce
  • info

1つめのバージョンローリングは、こないだ書いたBIP-320の利用を前提としている(まぁ前提というか実際はもうそういう使い方されてる)。

techmedia-think.hatenablog.com

以下BIPに定義されているプロトコルの詳細↓

動機

Stratumプロトコルの拡張のサポートを指定する最初の動機は、マイナーにBitcoinのブロックヘッダの最初のフィールドの値を変更する「バージョンローリング」と呼ばれるものを許可することだった。

オリジナルのStratumプロトコルのバージョンではサーバーに異なるブロックバージョンの値を伝えることができなかったため、バージョンローリングはStratumプロトコル後方互換性がない。同様に、サーバーは安全なbitを使ってマイナーにローリングすることができなかった。したがってマイナーとプールの両方は、バージョンローリングをサポートするためにいつくかのプロトコル拡張を実装する必要がある。

通常、マイナーが未知のメッセージをサーバーに送信すると、サーバーは接続を閉じる(全てのサーバーが閉じるわけではないが、いくつかのサーバー実装ではそうなっている。)。そのため未知のメッセージをサーバーに送信することは安全ではない。

我々はこの機会を利用して、将来複数の拡張をサポートするためにプロトコルに対して後方互換性のない変更を行うことができる。マイナーがその能力を広告すると同時にサーバからいくつかの必要な機能を要求することができる。

機能のネゴシエーションのため同じ仕組みがまだ知られていない機能に対しても使用されることが望ましい。マイニングソフトウェアにも簡単に実装されるべきだ。

標準的な方法で機能の初期設定/ネゴシエーションを処理するstratumプロトコル(mining.configure)への新しいメッセージを1つ導入する。これにより将来、stratumプロトコルに新しいメッセージを追加することなく機能を追加することができる。

各拡張にはextension codeと呼ばれる一意の文字列名がある。

仕様

現在、以下の拡張が定義されている。

  • version-rolling
  • minimum-difficulty
  • subscribe-extranonce

追加のデータタイプ

以下の名称はタイプエイリアスとして使われ、メッセージの定義を簡単にする。

  • TMask
    32bitの符号なし整数([0-9a-fA-F]{8})をエンコードする長さ8の大文字小文字を区別しない16進文字列
  • TExtensionCode
    プロトコル拡張の名前と同じ値の空でない文字列
  • TExtensionResult
    true / false / String
    • true 要求された機能がサポートされ、その設定が理解でき適用される。
    • false この機能はサポートしていないか未知のもの
    • String 何がうまく行かなかったかに関する情報を含む文字列

mining.configure リクエス

このメッセージ(JSON RPCリクエスト)は、サーバーとの接続が確立された後にマイナーが送信する最初のメッセージである必要がある。クライアントはこのメッセージを使って自身がサポートする機能を宣伝し、いくつかのプロトコル拡張を要求/許可する。

最初の理由は、実装と可能な限りやりとりを簡単、シンプルにしたいからだ。拡張は、拡張の繰り返し設定が何を意味するか明示的に定義することができる。

各拡張コードは、その拡張パラメータや拡張の戻り値に対してネームスペースを提供する。慣例により、名称は拡張コードに”.”とパラメータ名を追加することで形成される。同様のことが戻り値にも適用され、result mapにも転送される。例えば「version-rolling.mask」は拡張「version-rolling」の「mask」というパラメータ名だ。

パラメータ
  • extensions(必須。TExtensionCodeのリスト)
    • リスト内の各文字列は有効な拡張コードでなければならない。各コードの意味は、拡張定義の一部として独立して記述される。マイナーは利用可能な全ての機能を広告しなければならない。
  • extension-parameters(必須。String -> 任意のデータのMap)
    • 最初のパラメータから要求/許可された拡張のパラメータ
戻り値
  • String -> 任意のデータのMap
    • 拡張リストの各コードは、定義された戻り値(TExtensionCode -> TExtensionResult)を持たなければならない。こうすることでマイナーは拡張が有効になっているかどうか確認することができる。例えばバージョンローリングをサポートしていない場合は{"version-rolling":false}
    • いくつかの拡張では、追加情報をマイナーに提供する必要がある。戻り値のMapはこのために使われる。

リクエストの例

{"method": "mining.configure",
  "id": 1,
  "params": [["minimum-difficulty", "version-rolling"],
         {"minimum-difficulty.value": 2048,
          "version-rolling.mask": "1fffe000", "version-rolling.min-bit-count": 2}]}

(マイナーは「version-rolling」と「minimum-difficulty」という拡張を要求する。この際、拡張の定義に従ってパラメータをセットする)

結果の例

{"error": null,
  "id": 1,
  "result": {"version-rolling": true,
         "version-rolling.mask": "18000000",
         "minimum-difficulty": true}}

定義された拡張

拡張「version-rolling」

この拡張によりマイナーはブロックヘッダのバージョンフィールドの一部のbitの値を変更できます。現在バージョンローリングに使用される標準bitは存在しないため、マイナーとサーバー間で調整する必要がある。

マイナーはマイナーが変更可能なbitを記述マスクをサーバーに送信する。1 = 変更可能なbit、0 = 変更不可能なbit (miner_mask)とバージョンローリングに必要な最小bit数。

サーバーは通常、version bits(server_mask)の一部のみを変更することができ、残りのversion bitsは固定されている。これは例えばブロックを有効なブロックにするためであったり、何らかのシグナリングに使われている場合があるためだ。

サーバーはコンフィギュレーションメッセージに応答し、マイナーのマスクとサーバーのマスクの共通bit交差を持つマスクを送信する(response = server_mask & miner_mask)。

リクエスト例(16bitのマスクから任意の2 bitを変更できるマイナー)

{"method": "mining.configure", "id": 1, "params": [["version-rolling"], {"version-rolling.mask": "1fffe000", "version-rolling.min-bit-count": 2}]}

結果の例(成功の場合)

{"error": null, "id": 1, "result": {"version-rolling": true, "version-rolling.mask": "18000000"}}

結果の例(未知の拡張の場合)

{"error": null, "id": 1, "result": {"version-rolling": false}}
拡張パラメータ
  • version-rolling.mask (オプション、TMask、デフォルト値は"ffffffff"
    • 1をセットされたbitは、マイナーによって変更することができる。この値はマイニングセッション全体で安定していることが期待される。マイナーはマスクを送信する必要はなく、この場合デフォルトのフルマスクが使用される。
拡張の戻り値
  • version-rolling(必須、TExtensionResult)
    • trueの場合サーバーは新しいパラメータmining.submitを受け取る(後述)。
  • version-rolling.mask(必須、TMask)
    • 1をセットされたbitは、マイナーによって変更することができる。マイナーがマスク値0のbitを変更した場合、サーバーは送信を拒否する。
    • サーバーは可能な限り最大のマスクを返すべきだ(可能な限り多くのbitが1に設定された)。これはプロキシが将来のクライアントに最適なマスクを調整する必要がある場合に、マイニングプロキシの設定に役立つ。利用可能なnVersion bitsについて記述したドラフトがある。サーバーはBIPで指定されたすべてのbitをカバーするマスクを作成するべきだ。
  • version-rolling.min-bit-count(必須、TMask)
    • マイナーはまたハードウェアでの効率的なバージョンローリングに必要な最小bit数も提供する。このパラメータはプールサーバに重要な診断情報を提供することに注意すること。要求されたbit数がプールサーバーの制限を超えた場合、ハッシュパワーを完全に使用することがない、常に劣化モードで動作する可能性がある。この稀なミスマッチが発生した場合、マイナーとの接続を終了してはならない。
「mining.set_version_mask」の通知

サーバーは接続に有効な新しいマスクについてマイナーに通知する。このメッセージは、mining.configureメッセージによりバージョンローリングの拡張が正常にセットアップされた後、いつでも送信できる。新しいマスクはすぐに有効になり、サーバーは次のジョブを待機しない。

パラメータ
  • mask(必須、TMask)
    意味はversion-rolling.mask 戻りパラメータと同じ。

サンプル

{"params":["00003000"], "id":null, "method": "mining.set_version_mask"}
mining.submit 要求の変更

バージョンローリング拡張が正常にアクティベートされた直後に(サーバーによって送信されたmining.configureの結果)、サーバーはメッセージmining.submitの追加パラメータを受け取らなければならない。クライアントは追加のパラメータversion_bitsを1つ送らなければならない(worker_name, job_id, extranonce2, ntime, nonceに続く6つめのパラメータとして)。

追加のパラメータ
  • version_bits(必須、TMask)
    マイナーによってセットされるversion bits。
    • マイナーはmining.configureもしくはmining.set_version_mask通知(last_mask)の応答として、サーバーから最後に受信したマスクの設定bitに対応するbitのみを設定できる。このためversion_bits & ~last_mask == 0となる
    • サーバーは次のように送信するnVersionを計算する。nVersion = (job_version & ~last_mask) | (version_bits & last_mask)job_versionjob_idと共にジョブの一部としてマイナーに送信されたブロックバージョン。

拡張「minimum-difficulty」

この拡張により、マイナーは接続されたマシンに最小難易度の要求をすることができる。これにより、接続されたデバイスのハードリミットを伝える方法がないオリジナルのStratumプロトコルの問題を解決する。

拡張パラメータ
  • minimum-difficulty.value(必須、Integer/Float, >= 0)
    マイナー/接続に許容される最小難易度の値。機能を無効にするには0をセットする。
拡張戻り値
  • minimum-difficulty(必須、TExtensionResult)
    • 最小難易度が受け入れられたかどうか
    • この拡張はminimum-difficultyコードを持つmining.configureを再度呼び出して複数回設定することができる。

拡張「subscribe-extranonce」

パラメータの無い拡張。マイナーはmining.set_extranonceメッセージを受信することができることを広告する(ハッシュレートルーティングシナリオに役立つ)。

拡張「info」

マイナーはテキストベースの追加情報を提供する。

拡張パラメータ
  • info.connection-url(オプション、文字列)
    マイニングソフトウェアがstratumサーバに接続するために使用する正確なURL。
  • info.hw-version(オプション、文字列)
    製造元固有のハードウェアバージョン文字列
  • info.sw-version(オプション、文字列)
    製造元固有のソフトウェアバージョン文字列
  • info.hw-id(オプション、文字列)
    マイニングデバイスの一意の識別子

互換性

現在、さまざまなプロトコル拡張を目的とした同様のプロトコル機能mining.capabilitiesが存在する。しかし、mining.configureは、全ての受け入れらた/調整中の拡張を確認するサーバーの応答を必要とするため、この機能と互換性がない。我々がこれを非互換にしたのは、mining.capabilitiesの要求には関連する応答がないためだ。

ブロックヘッダのバージョンについてソフトフォークのデプロイ以外の汎用利用を提案するBIP-320

Bitcoinのブロックヘッダにはバージョンを表すnVersionフィールドが存在する。現在このnVersionフィールドは、コンセンサスに影響するような新しい機能をソフトフォークで導入する際に、ソフトフォークの準備ができたことを各マイナーがシグナリングするのに使われている。(と言っても、Segwit以降新たなソフトフォークの計画はまだ発表されてないけど)

BIP-9で定義されたこの仕様は、nVersionフィールドをビット列として解釈し、ソフトフォークの対応状況をその各bitを使ってシグナリングしている。詳細な仕様ついては↓参照。

techmedia-think.hatenablog.com

BIP-9のversion bitsによるシグナリングにより、異なるソフトフォークを29個同時にデプロイできるようになっているが、実際にそんな数のソフトフォークを並行デプロイするようなことはこれまで無かったし、今後も考えにくい。

そこで、このブロックヘッダのnVersionフィールドをソフトフォークのデプロイ以外にも使用できるようにしようというのがBtcDrakによって提案されたBIP-320↓

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

簡単に説明すると、ブロックヘッダのnVersionフィールドは4バイト(32 bit)あるが、そのうち16 bitを汎用的な目的のために確保し、BIP-9のversion bitsの解釈から取り除こうという提案。16 bitを任意に利用できるようにすることで、マイニング効率の向上などに繋げようと。

一時期話題にあがったAsicBoostだが、covert型とovert型の内、Segwitのデプロイによりcovert型は実質不可能になったが(Bitcoin Cashでは可能)、overt型の方はバージョンローリングをする方式なので、ちょうどこのBIPの内容に当てはまる。AsicBoostの特許は、その所有者がブロックチェーンの防衛特許ライセンス↓

bitcoinmagazine.com

に加入したことで、BDPLに参加するメンバーはその特許が利用可能になっていることから、そのあたりの絡みもあっての提案なのかもね。まぁ実際に現段階でそういう使い方をされていることもあるので、適用には問題ないと思う(あと、そもそも29個並行デプロイとかないし)。

以下、BIP-320の定義内容。

動機

マイナーはnVersionフィールドのいくつかのbitを、様々な用途に使用したいと考えている。しかし現在は、マイナーによってアクティベートされるソフトフォークの調整に使用しているため、これらのbitをソフトフォーク以外のシグナリング目的で使用すると、フルノードが未知のソフトフォークだと認識して誤った警告を生成する。nVersionフィールドのbitを汎用的な使用のために確保することで、ノードソフトウェアがそれらのbitを無視するようにアップグレードすることができ、誤った警告を生成することもなくなる。汎用的な使用のために16 bitを確保しても、まだ13個のソフトフォークの並行デプロイが可能であり十分だ。

使用例

以下はnVersionフィールドの一部のbitを使用できるようにすることで得られる利益の一例だ。このリストは網羅的ではない。

Bitcoinのマイニングハードウェアは現在200ms未満で32 bitのnonceフィールドを使い切る。このためコントローラは多くの帯域幅とCPU時間を消費して新しいジョブを非常に頻繁に各マイニングチップに配布する必要がある。これはより多くのbitをローリングすることで大幅に削減できる。同じくブロックヘッダにあるnTimeの多くのbitをローリングするという方法もあるが、タイムスタンプをより長い時間に渡って歪める可能性があるので理想的ではない。

バージョンローリングをするAsicBoostでは、4方向の衝突を計算するのにnVersionフィールドから2 bit必要だ。任意の2 bitが使用できると、マイニング装置はStratumの「version-rolling」拡張を使ってどのbitがマイニングプールで使用されるか交渉することができる。

仕様

13から始まり28(0x1fffe000を含む)で終わるブロックヘッダのnVersionフィールドの16 bitを汎用的な使用のために確保され、BIP-8およびBIP-9の仕様からは削除される。nVersion bitに0xe0001fffのマスクを適用し、ソフトフォークのシグナリングおよびソフトフォークの警告に対してbit 13〜28を無視する。

参照実装

github.com

後方互換

アップグレードされていないノードは、この提案で確保されるbitをソフトフォークのシグナリングとして解釈し、さらに未知のソフトフォークの警告システムをアクティブにすることがある。

この提案を実装するのにソフトフォークは必要としない。

これが記載されている時点で、このBIPで確保しようとしている16 bitのいずれも既知のソフトフォークで確保されてはおらず、ハッシュレートの少なくない割合がすでにそれらのbitを使用していることを考慮すると、将来のソフトフォークでアクティベーションシグナリングにこれらのbitを使用すべきではない。

SchnorrベースのScriptlessな「Multi-Hop Locks」の実現方法

techmedia-think.hatenablog.com

techmedia-think.hatenablog.com

と書いたので、残ったSchnorrベースのMulti-Hop Locksについても書いておく。
(Multi-Hop Locksのコンセプトについては最初の記事参照)

SchnorrベースのMulti-Hop Locksは署名アルゴリズム自体がSchnorrとECDSAで違うだけで、基本的な構成はECDSAの時と同じだ。

鍵生成フェーズ

各ユーザー {U_i}が持つ秘密鍵 {x_i}とし、対応する公開鍵を {P_i = x_iG}とする。

決済の経路間のユーザー=ペイメントチャネルを直接開いているユーザーは、相手と鍵生成プロトコルを使用して二者間の公開鍵を計算する。例えば {Ui, U_{i+1}}は、それぞれ公開鍵 {P_i, P_{i+1}}を持っているが、Schnorrの公開鍵の集約特性を利用し、両者の公開鍵を加算した共有鍵 {P = P_i + P_{i+1}}を算出する。

通常、Schnorr署名では上記の共有鍵Pにロックされたコインは、

  •  {U_i} {s_i = k_i + H(P, R, m)x_i}
  •  {U_{i+1}} {s_{i+1} = k_{i+1} + H(P, R, m)x_{i+1}}

をそれぞれ計算し、 {s_i + s_{i+1}}を計算した {(R, s)}がPに対する有効な署名となる。

送信者から中間者、受信者の3人の場合、それぞれ {x_0, x_1, x_2}秘密鍵を持っている場合、

  •  {U_0}(送信者)と {U_1}(中間者)の共有鍵は {P_0 = x_0G + x_1G}
  •  {U_1}(中間者)と {U_2}(受信者)の共有鍵は {P_1 = x_1G + x_2G}

となる。

セットアップフェーズ

  1. LNで支払いを行う送信者は受信者までの数分(n)、ランダムに値をサンプリング( {y_0, ...., y_n})する。
  2. 続いて1〜nについて {Y_i = Y_{i-1} + y_iG}を計算する。なお、 {Y_0} = y_0G
  3. 送信者は受信者までの各ユーザーに対して3つのアイテム {(Y_{i-1}, Y_i, y_i)}を送信する。送信者から中間者、受信者の3人の場合、それぞれに送られるデータは
    •  {U_0}(送信者)には {(n/a, Y_0, y_0)}
    •  {U_1}(中間者)には {(Y_0, Y_1, y_1)}
    •  {U_2}(受信者)には {(Y_1, Y_2, y_2)}
  4. 最後に受信者にのみ追加で、全てのサンプリング値を加算した( {y_0 + y_1 + y_2})オープン鍵を送る。

この部分は、ECDSAと全く同じ。

ロックフェーズ

ECDSAとは署名アルゴリズムが異なるので署名の構成方法は異なるが、基本的には {Y_i}をRに含めることで、Rの構成にシークレットを含めるという仕掛けは変わらない。

ロックフェーズは {U_i, U_{i+1}}間で始まる。まず両者はECDSA署名に必要なランダムなnonceについて合意する。それぞれランダムに {r_i, r_{i+1}}を選択し、それぞれ {r_i G} {r_{i+1}G}を計算する。それぞれ計算した点を明らかにし、自分のnonceと組み合わせて共通の {R_{i} = r_iG + r_{i+1}G + Y_i}を計算する。

ここで {Y_i}を加算しているのがポイントだ。

ECDSAと違ってSchnorr署名は署名アルゴリズム自体が署名の集約をサポートしているため、まず以下のように {Y_i}がなかった場合に有効な署名を計算する。

  •  {U_i} {s_i = r_i + H(P, R, m)x_i}を計算
  •  {U_{i+1}} {s_{i+1} = r_{i+1} + H(P, R, m)x_{i+1}}を計算

 {s_i + s_{i+1}}を計算すると、

 {s' = r_i + r_{i+1} + H(P, R, m)(x_i + x_{i+1})}

になるが、このままでは {Y_i}の離散対数の情報がないので、 {R_i}に対応した署名としては無効だ。

これを有効な {R_i}に対応した有効な署名にするためには、s'に対して {Y_i}の離散対数 {y_i}を加算する必要がある。

ECDSAの場合と同様各 {Y_i}の離散対数が、受信者→送信者の経路で順にアンロックするトリガーとなる。

送信者から中間者、受信者の3人の場合、送信者から中間者、受信者の3人の場合、それぞれ {r_0,r_1,r_2}のnonceを選択した状態で、それぞれの間で作成されるRと署名データは以下のようになる。

 {U_0}(送信者)と {U_1}(中間者)
 {R_0 = r_0G + r_1G + Y_0}
 {\displaystyle \biggl( R_0, s' = r_0 + r_1 + H(P, R, m)(x_0 + x_1)\biggr)}

 {Y_0 = y_0G}であることから、この署名に対して必要な {Y_0}の離散対数は {y_0}

 {U_1}(中間者)と {U_2}(受信者)
 {R_1 = r_1G + r_2G + Y_1}
 {\displaystyle \biggl( R_1, s' = r_1 + r_2 + H(P, R, m)(x_1 + x_2)\biggl)}

 {Y_1 = Y_0 + y_1G}であることから、この署名に対して必要な {Y_1}の離散対数は {y_0 + y_1}

リリースフェーズ

リリースフェーズでは、ロックフェーズでロックされたコインを入手するのに各チャネルでアンロック条件となっている離散対数を明らかにする。

送信者から中間者、受信者の3人の場合、受信者はオープン鍵 {y_0 + y_1 + y_2} {y_2}を持っているため、中間者からコインを貰う際の署名に使った {Y_1}の離散対数をオープン鍵から {y_2}を引くことで算出できる。この離散対数を中間者に対し明らかにすることで、コインを入手する。

中間者は {y_0 + y_1}の離散対数を知ったので、そこから予め知っている {y_1}の値を引けば、 {Y_0}の離散対数 {y_0}を算出でき、これを使って送信者から資金を入手する署名を完成させることができる。

途中の参加者が離散対数を相手に伝えることがなく、トランザクションをブロードキャストした場合も、ブロードキャストされたトランザクションで使われている署名値sを使ってs - s'を計算することで、自身がコインの入手に必要な離散対数を手に入れることができる。

といった形で、Schnorrの場合もECDSAと同様、署名のR値に受信者→送信者の順にアンロック要素が明らかになる離散対数のロック条件をしのばせることで、Scriptlessな「Multi-Hop Locks」を構成しているのが分かる。

ECDSAベースのScriptlessな「Multi-Hop Locks」の実現方法

Scaling Bitcoin 2018のセッションの1つでもある、LNなどで利用されているペイメントチャネルネットワークの新しいプリミティブである「Multi-Hop Locks」について、以前一方向準同型関数を使った実装方法について書いたが↓

techmedia-think.hatenablog.com

Multi-Hop Locksには、一方向準同型関数を使用する方法以外に、

  • SchnorrベースのScriptless Scripts
  • ECDSAベースのScriptless Scripts

で実現する方法が定義されている。

今回は、現在のBitcoinでも利用可能なECDSAを使ったScriptless Scriptベースの実現方法についてみてみる。(ホワイトペーパーの内容を適当に脳内補間してるので誤解している可能性あり)

鍵生成フェーズ

各ユーザー {U_i}が持つ秘密鍵 {x_i}とし、対応する公開鍵を {P_i = x_iG}とする。

決済の経路間のユーザー=ペイメントチャネルを直接開いているユーザーは、相手と鍵生成プロトコルを使用して二者間の公開鍵を計算する。例えば {Ui, U_{i+1}}は、 {U_i} {x_i P_{i+1}}を計算し、 {U_{i+1}}{x_{i+1} P_i}を計算することで共通の公開鍵 {P_{(i, i+1)}}を計算することができる。この公開鍵に対応する秘密鍵は、2人の秘密鍵を乗算した {x_i \cdot x_{i+1}}である。

ここで導出した共有鍵にコインをロックすることは、アンロックに2人の秘密の情報を必要とするという意味で、2-of-2のマルチシグへのコインのロックと同等のこととなる。

送信者から中間者、受信者の3人の場合、それぞれ {x_0, x_1, x_2}秘密鍵を持っている場合、

  •  {U_0}(送信者)と {U_1}(中間者)の共有鍵は {P_0 = (x_0 \cdot x_1)G}
  •  {U_1}(中間者)と {U_2}(受信者)の共有鍵は {P_1 = (x_1 \cdot x_2)G}

※ 簡易的に同じ記載にしてるけど、中間者の {x_1}は相手によって違う鍵になると思われる。

セットアップフェーズ

  1. LNで支払いを行う送信者は受信者までの数分(n)、ランダムに値をサンプリング( {y_0, ...., y_n})する。
  2. 続いて1〜nについて {Y_i = Y_{i-1} + y_iG}を計算する。なお、 {Y_0} = y_0G
  3. 送信者は受信者までの各ユーザーに対して3つのアイテム {(Y_{i-1}, Y_i, y_i)}を送信する。送信者から中間者、受信者の3人の場合、それぞれに送られるデータは
    •  {U_0}(送信者)には {(n/a, Y_0, y_0)}
    •  {U_1}(中間者)には {(Y_0, Y_1, y_1)}
    •  {U_2}(受信者)には {(Y_1, Y_2, y_2)}
  4. 最後に受信者にのみ追加で、全てのサンプリング値を加算した( {y_0 + y_1 + y_2})オープン鍵を送る。

ロックフェーズ

ロックフェーズは {U_i, U_{i+1}}間で始まる。まず両者はECDSA署名に必要なランダムなnonceについて合意する。それぞれランダムに {r_i, r_{i+1}}を選択し、それぞれ {r_i Y_i} {r_{i+1} Y_i}を計算する。それぞれ計算した点を明らかにし、自分のnonceと組み合わせて共通の {R_{i} = (r_i \cdot r_{i+1})Y_i}を計算する。

ここでRの計算に両者のnonceをGではなく、Yに乗算しているのがポイントになる。

まずは {Y_i}を無視して、二者の共有鍵に対する署名をLindellのプロトコルを使って計算する↓

techmedia-think.hatenablog.com

 {Y_i}を無視したその署名データは

 {\displaystyle \biggl( r_x, s' = \frac{r_x(x_{i-1} \cdot x_i) + H(m)}{r_{i-1} \cdot r_i} \biggr) }

となる。当然この署名データには {Y_i}が考慮されていないので、有効な署名ではない。有効な署名にするためには {Y_i}の離散対数 {y_i}を使って、 {s' \cdot y_i^{-1}}を計算すると、

 {\displaystyle \biggl( r_x, s = \frac{r_x(x_{i-1} \cdot x_i) + H(m)}{r_{i-1} \cdot r_i \cdot y_i} \biggr) }

と有効な署名が作成できる。

この {Y_i}の離散対数の知識が、受信者→送信者への経路でコインの入手と共に明らかになるデータになる。

つまり、2者間の共有鍵にロックされた資金の内、ペイメントチャネルのマルチホップ決済の送金分のコインを相手に送金するトランザクションを作成するが、そのトランザクションの署名で使用するRには、セットアップフェーズで送信者から配布された {Y_i}が含まれ、この署名を有効なものにするためには、 {Y_i}の離散対数の知識が必要になる。この離散対数が従来のLNのHTLCで扱われるシークレットの代替となる。

送信者から中間者、受信者の3人の場合、送信者から中間者、受信者の3人の場合、それぞれ {r_0, r_1, r_2}のnonceを選択した状態で、それぞれの間で作成されるRと署名データは以下のようになる。

 {U_0}(送信者)と {U_1}(中間者)
 {R_0 = (r_0 \cdot r_1)Y_0}
 {\displaystyle \biggl( r_x, s' = \frac{r_x(x_{0} \cdot x_1) + H(m)}{r_{0} \cdot r_1} \biggr) }

 {Y_0 = y_0G}であることから、この署名に対して必要な {Y_0}の離散対数は {y_0}

 {U_1}(中間者)と {U_2}(受信者)
 {R_1 = (r_1 \cdot r_2)Y_1}
 {\displaystyle \biggl( r_x, s' = \frac{r_x(x_{1} \cdot x_2) + H(m)}{r_{1} \cdot r_2} \biggr) }

 {Y_1 = Y_0 + y_1G}であることから、この署名に対して必要な {Y_1}の離散対数は {y_0 + y_1}

リリースフェーズ

リリースフェーズでは、ロックフェーズでロックされたコインを入手するのに各チャネルでアンロック条件となっている離散対数を明らかにする。

送信者から中間者、受信者の3人の場合、受信者はオープン鍵 {y_0 + y_1 + y_2} {y_2}を持っているため、中間者からコインを貰う際の署名に使った {Y_1}の離散対数をオープン鍵から {y_2}を引くことで算出できる。この離散対数を中間者に対し明らかにすることで、コインを入手する。

中間者は {y_0 + y_1}の離散対数を知ったので、そこから予め知っている {y_1}の値を引けば、 {Y_0}の離散対数 {y_0}を算出でき、これを使って送信者から資金を入手する署名を完成させることができる。

途中の参加者が離散対数を相手に伝えることがなく、トランザクションをブロードキャストした場合も、ブロードキャストされたトランザクションで使われている署名値sを使ってs'・s-1を計算することで、自身がコインの入手に必要な離散対数を手に入れることができる。

注意点としては、ECDSAの署名(r, s)のsは-s mod q した場合でも有効で、これを許可すると成立しなくなるので、sは {\frac{q-1}{2}}以下であるというLOW_Sルールが前提となる。 よく考えたら、sが変更されていた場合、もう1つのsの候補を計算すればいいだけなので、問題はなかった。

上記の方法を使えば、既存のBitcoinですぐにScriptlessなMulti-Hop LocksのLNコントラクトを実装することができるっぽい。ECDSA + Scriptlessということだったので、楕円曲線の操作がベースになるとは思ったけど、nonceのRを利用するのね。

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

SchnorrのBIPドラフト↓

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

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

https://t.co/jMhQnovLcb

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

前提技術

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

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

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

ベースとなるプリミティブの1つが(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 + bx2

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

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

とかでも良い、重要なのは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 + 5x2

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

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

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

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

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

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

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

  • f(x) = 5 + 3x + 5x2
  • f'(x) = 3 + 2x + 7x2

上記手順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。

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

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

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

  1. 各ユーザー {U_i}はランダムに値 {r_i, r'_i}を選択する。
    ※ 参加者数がnの場合、各ユーザーの {r_i}を合算した {\sum_{i=1}^{n}r_i}がシークレットになり、このシークレットを復元する際に使う多項式は、以下の2で各ユーザーが作成した多項式の和で構成される。
  2. 続いて各ユーザーはそれぞれ以下の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}とする。
  3. 続いて各ユーザーは、 {0 ≦ m ≦ t-1}のコミットメント {C_{im} = a_{im}G + b_{im}H}を計算し公開する。
  4. 続いて各ユーザーは、 {1 ≦ j ≦ n} {s_{ij} = f_i(j)}と、 {s'_{ij} = f'_i(j)}を計算し、計算した値をユーザー {U_j}に送る。
  5.  {(s_{ij}, s'_{ij})}を受け取ったユーザー {U_j}はそのシェアが正しいか、送信者が公開しているコミットメントを使い {s_{ij}G + s'_{ij}H = \sum_{m=0}^{t-1} \, j^{m} \, C_{im}} で検証する。この1つ1つのシェアの検証に↑のVSSが使われる。
  6. 続いて各ユーザーは {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にする。

まず、各ユーザーはそれぞれシークレットを選択し(アリス:3、ボブ:7、キャロル:2)、そのシークレットを使った多項式を以下のように決める。

  • アリスの多項式
    • 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

これは各ユーザーがランダムに生成したシークレット(アリス:3、ボブ:7、キャロル:2)の共有シークレットに対応した公開鍵となる。

Schnorr署名

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

  1. ランダム値kを選択。
  2. R = kGを計算。
  3. s = k + h(P, R, m)x を計算する。
  4. (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人未満の場合は署名は作成できない。

手順1

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

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

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

とする。

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

手順2

続いて各ユーザーは、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は共有シークレットを導出する際の多項式の定数項で、これらはランダムシークレットの生成プロトコル手順6で公開している。

手順4

手順3が問題なければ、検証が成功したユーザーが提供したデータのうち任意の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に必要なデータを復元できる。

計算例

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

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

  • アリスが公開する
    • γ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

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

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

γ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:シークレットを分割してできた各断片