Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

Bitcoin Scaling Bitcoin Scriptless Scripts Payment Channel Lightning network ECDSA Cryptography

Scaling Bitcoin 2018のセッションの１つでもある、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. 送信者は受信者までの各ユーザーに対して３つのアイテム {(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が変更されていた場合、もう１つのsの候補を計算すればいいだけなので、問題はなかった。

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

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

Bitcoin Cryptography 秘密分散

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 + 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. 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}}
  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. 続いて各ユーザーはそれぞれ以下の２つの多項式を生成する。
    • {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}} で検証する。この１つ１つのシェアの検証に↑の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にする。

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

  • アリスの多項式
    • 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とする）、その署名は以下のように計算される。

  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人未満の場合は署名は作成できない。

手順１

まず、署名生成にあたって上記の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:シークレットを分割してできた各断片

Bitcoinのトランザクション伝播時の匿名性を強化するDandelionについて定義したBIP-156

Bitcoin BIP

Bitcoin Coreなどのノードがトランザクションをリレーする際、ノードは接続中のピアに対して一斉にトランザクションを送信する訳ではなく、接続中の各ピア毎に指数関数的な遅延時間をもって各ピアにトランザクションを送信するようになっている。これによりトランザクションを作成したノードを判定しにくくし、プライバシーを向上させるのが狙いだ。

ただBitcoinネットワークのノード数は10,000ノードくらいなので、安価に大量のスパイノードを配置して、送信されるトランザクションメッセージの対称性を観測することで、トランザクションをブロードキャストしたソースノードを推論することができるとして、もっとプライバシーを向上させようと、新しくDandelionというトランザクション伝播プロトコルがBIP-156として提案された↓

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

なお、Bitcoin CoreではDandelionの採用とは別に、各ネットワークブロック（IPブロック）毎にランダムな遅延時間を設定することで、分析コストを上げてよりプライバシーを向上させようという提案がマージされ↓、0.17.0で導入される見込みなので、CoreでDandelionが採用されるかどうかは未定。

github.com

具体的なDandelionのBIPの仕様について見てみる↓

概要

Bitcoinのトランザクション拡散プロトコルは、匿名性を奪う攻撃に対して脆弱だ。Dandelionはこれらの攻撃に対して正式な匿名性保証を提供するトランザクションルーティングメカニズムだ。Dandelionを使わずにノードがトランザクションを生成すると、ノードは接指数関数的な遅延をさせつつ接続中のピアに個別にトランザクションを送信する。Diffusionとして知られるこのアプローチは、ネットワーク内の敵対者がトランザクションをIPアドレスにリンクすることを可能にする。

Dandelionは拡散前にランダムに選択されたパスを介してトランザクションを送信することで、この種の攻撃を緩和する。トランザクションは「stemフェーズ」中にこのパスに沿って移動し、その後の「fluffフェーズ」で拡散される（stem=幹、fluff=綿毛なのでDandelion＝たんぽぽ）。このルーティング・プロトコルは追加の暗号メカニズムを導入することなく、最適な匿名性保証を提供する。

動機

Bitcoinのトランザクション拡散は、匿名性を奪う攻撃に対して脆弱だ。トランザクションはピア毎に個別に指数関数的な遅延をもって送信されるため、メッセージは統計的に対称な方法でネットワーク全体に広がる。このパターンはスパイノードと結託してトランザクションソースを推論することを可能にする。この対称性を破ることで攻撃を防ぐ。しかし、我々は対称性の破壊が適切に行われない場合、ネットワークトポロジーの知識を持つ敵がより効果的な指紋攻撃を開始できることが分かった。

P2Pグラフにアクセスできるボットネット型の敵を考えてみよう。BitcoinのP2Pネットワークに匹敵するサイズのボットネットは一般的に安価で、これらの敵はプローブメッセージでネットワーク構造を知ることができる。このような敵は、各ノード毎に10以下のトランザクションを観察した後、ネットワーク全体の完全な非匿名化を達成できることが分かった。

Dandelionは、Bitcoinネットワークの正式な匿名性の保証を提供する実用的で軽量なプライバシーソリューションだ。他のプライバシーソリューションは個々のユーザーを保護することを目的としているが、Dandelionは敵対者がネットワーク全体を非匿名化することを制限することで、匿名性を保護する。

Dandelionはどのように動作するのか？

Dandelionはトランザクションをネットワークに拡散する前に、「anonymityフェーズ」を介してトランザクションを送信することでユーザーのプライバシーを強化する。高レベルでは、

  • 拡散の対称性の破壊
  • 同じパスに沿って異なるソースからのメッセージを転送することによりトランザクションをミキシング

することで、プライバシーを強化する。

Dandelionのルーティングは３つのフェーズで概念化される。最初にプライバシーグラフが構築される。実際に、このプライバシーグラフは完全に分散された方法で構築され、既存のBitcoinのP2Pネットワークのサブグラフになる。次に、stemフェーズ中にこのプライバシーグラフに沿ってトランザクションが転送される。最後にメッセージはfluffフェーズで、拡散の典型的な方法でネットワークにブロードキャストされる。

https://github.com/bitcoin/bips/raw/master/bip-0156/1-dandelion.png

分散型でプライバシーグラフを選択するために、各ノードはそのアウトバウンドピアのサブセットをDandelionの宛先に選択する。インバウンドの接続を介してこのノードに届くDandelionトランザクション（stemフェーズ中のトランザクション）は、これらDandelionの宛先に転送される。

理想的な設定では、ハミルトン閉路がほぼ最適なプライバシー保証を提供することが分かった。しかし分散型のBitcoinのP2Pネットワークを介してトラストレスな方法でハミルトン閉路を構築するのは不可能だ。そのため、各ノードはアウトバウンドピアのリストから置換することなく、ランダムに一様に2つのDandelionの宛先を選択することを推奨する。我々のテストでは、この方法が堅牢性の向上と同等のプライバシーを提供することが分かった。

stemフェーズのルーティングの際、プライバシーを保護するためにどのようにルーティングするかという問題がある。例えば2つのDandelionトランザクションが異なるインバウンドピアからノードに届いた場合、どのDandelionの宛先にこれらのトランザクションを送信すべきだろうか？我々はいくつかの選択肢が他の選択肢よりずっと優れていることに気づいた。

各Dandelionのトランザクションが、ランダムに一様に選択されたDandelionの宛先に転送される場合を考えてみよう。このアプローチの結果、指紋攻撃が発生し、ネットワークレベルのボットネット攻撃者がノードあたり10件未満のトランザクションを観察した後、P2Pネットワークの完全な非匿名化を達成できるようになる。

https://github.com/bitcoin/bips/raw/master/bip-0156/2-attack.png

指紋攻撃の間に、グラフ構造の知識を持つボットネット形式の敵対者は最初にトランザクションの伝搬をシミュレートする。このオフラインステップにより、敵対者は各ネットワークノードの指紋を生成することができる。オンライン攻撃中、敵対者はスパイノードでトランザクションを収集し、これらの観測結果をシミュレートした指紋と一致させる。我々のシミュレーションでは、この攻撃がネットワーク全体の匿名化を壊滅させると示されている。

https://github.com/bitcoin/bips/raw/master/bip-0156/3-attack-plot.png

この問題を回避するには、インバウンドエッジ毎のルーティングを推奨する。各インバウンドピアには、特定のDandelionの宛先が割り当てられる。このピアを介して届いたDandelionトランザクションは同じDandelionの宛先に転送される。インバウンドエッジ毎のルーティングは攻撃者が有用な指紋を構築する能力をブロックすることで、攻撃を破る。指紋はルーティングの決定が各ノードでトランザクション毎に独立して行われる際に発生する。この場合、同じノードからの2つのトランザクションは通常ネットワークの異なる経路をとる。重要なのは、指紋と一致するような複数、単一のデータポイントが得られることだ。

Dandelionでは、同じノードからの２つのトランザクションは同じネットワーク経路を取るようにし、Figure 3の左端に敵対者を限定する。言い換えると、敵対者の知識は、複数のトランザクション経路の豊富なプロファイルではなく、1つの観察されたメッセージに限定される。Dandelionはまた拡散の対称性を破壊し、トランザクションソースの推測を困難にする。

https://github.com/bitcoin/bips/raw/master/bip-0156/4-dandelion-plot.png

トランザクションはDandelionのstemフェーズでランダム数ホップした後、ルーティングのfluffフェーズに移行する。トランザクションは既存の拡散プロセスを通じてネットワークに共有される。実際には、fluffの仕組みは各ノードでコインフリップの重み付けで強制される。ランダム値がある閾値を下回る場合、Dandelionトランザクションは典型的なトランザクションに変換される。我々のテストでは、あるノードを離れる際、特定のDandelionトランザクションがfluffフェーズに入る確率を10%と選択した。この値はstemの経路長とトランザクション拡散のレイテンシーとの間で良好なバランスを取る。

Dandelionの予測精度保証は集団レベルのメトリックだが、期待リコール保証は個人レベルのメトリックとして解釈できる。期待リコールは、敵対者が単一のトランザクションを所与のソースに関連付ける確率に相当する。これらの保証は確率的だ。彼らは、ノードが他のノードによって覆い隠されたシナリオ、またはISPのような敵対者によってノードが具体的にターゲットにされているシナリオに対処していない。非匿名化のターゲットとされるのを心配する個人は、Torを使用する必要がある。

高いレベルでは、DandelionはBitcoinのプライバシーの課題を意識していないようなユーザーを含む、一般の人々のための匿名性の注入のようなものだ。Torを使っていないユーザーにも、採用が増えると大きなメリットがもたらされる。Dandelionの早期採用者は、プライバシー上の利益を得ている。隣接するノード群がDandelionをサポートしない最悪の場合、トランザクションはDiffusion前に1ホップを作成する。ルーティングにのみ基づくソリューションは、オリジナルのDandelionペーパーに示されている精度とリコールに関する基本的な下限のため、完全に匿名にすることはできない。Dandelionはそのようなソリューションの中で最適な匿名性保証を提供する。

仕様

Dandelionは以下のいくつかの機能で定義される。

仕様の詳細について以下にまとめる。

Dandelionトランザクションサポート

stemフェーズ中、トランザクションはDandelionトランザクションとなる。Dandelionトランザクションがfluffフェーズに入ると、トランザクションはBitcoinの通常のトランザクションとなる。Dandelionトランザクションと通常のBitcoinトランザクションとの違いは、NetMsgTypeのみ。

stemフェーズのDandelionトランザクションは通常のBitcoinトランザクションと区別できなければならない。

Dandelionルーティングデータとロジック

stemフェーズ中のDandelionのルーティングでは、インバウンドピア、アウトバウンドピア、Dandelion宛先、Dandelionルートという4つの概念がある。インバウンドピアはピアが接続を開始してから現在接続されている全てのピアで構成される。アウトバウンドピアは、このノードによって現在接続されている全てのピアで構成される。Dandelionの宛先はアウトバウンドピアのサブセットである。Dandelion宛先の数は、DANDELION_MAX_DESTINATIONSパラメータによって制限される。参照実装ではこの値は2に設定されている。我々のテストでは、この値がプライバシーと堅牢性の両方を提供することを示している（パラメータのトレードオフに関する詳細は参考文献を参照）。Dandelionルートは、Dandelion宛先へのインバウンドピアのマップだ。各インバウンドピアはDandelion宛先にマッピングされている。

Dandelionノードは、プライバシーグラフから分割することなく異なるDANDELION_MAX_DESTINATIONSパラメータを選択できることに注意すること。Dandelionルートのインバウンド接続をアウトバウンド接続にマッピングする際は、次のルーティングロジックを実装する。最初に、アウトバウンドピアのセットからDandelionの宛先のセットを選択する。このDandelionの宛先のセットのサイズは、DANDELION_MAX_DESTINATIONS以下である。インバウンド接続毎に、最小数のルートを持つDandelion宛先のサブセットを最初に識別する。例えば、Dandelion宛先の一部がゼロルートに属し、他の全てのDandelion宛先は１以上のルートに属する。このサブセットの中から一様にランダムに１つのDandelion宛先を選択する。インバウンド接続からこのDandelion宛先へのDandelionルートを確立する。

あるDandelionルートエポックでは、２つの個別のDandelion宛先を、アウトバウンド接続のセットから一様にランダムに選択する必要がある。特定のインバウンド接続から受信した全てのDandelionトランザクションは、同じDandelion宛先に送信する必要がある。特定のインバウンド接続に対してDandelion宛先を選択する際は、最小のインバウンド接続がそれらにマップされているDandelion宛先のセットから一様にランダムに選択しなければならない。

定期的なDandelionルートシャッフル

Dandelionルートのマップは、平均10分毎にクリアされ再構築される。我々は敵がプライバシーグラフを学習するのを困難にするため、経験的に10分という時間を選択した。Dandelionノードは、プライバシーグラフを分割することなく、異なる平均シャッフル時間を選択できることを注意すること。embargoes

Dandelionルートは、ランダムな間隔でクリアし再構築しなければならない。Dandelionルートは平均１０分毎にクリアして再構築する必要がある。

メモリプールロジック

Dandelionトランザクションは、一般的なトランザクションとは区別される。ただメモリプールは変更されない。stempoolと呼ばれるCTxMemPoolの別のインスタンスが、Dandelionトランザクションに使用される。適切なトランザクション伝播を保証するため、情報がmempoolからstempoolへ流れる。Dandelionトランザクションが通常のトランザクションに流入しない限り、情報がstempoolからmempoolに流れることはない。

Dandelionトランザクションが届くと、そのトランザクションはstempoolに追加され、mempoolに追加されてはならない。一般的なトランザクションが届くと、そのトランザクションはmempoolに追加され、stempoolにも追加されなければならない。Dandelionトランザクションがfluffに入ると、そのトランザクションはmempoolに追加しなければならない。

fluffメカニズム

DandelionルートにDandelionトランザクションを中継すると、Dandelionトランザクションは10%の確率で通常のBitcoinトランザクションになり、Diffusionで中継される。我々のテストでは、この値はstemのパス長とトランザクション拡散レイテンシー間で良好なバランスを保っている。Dandelionノードは、プライバシーグラフを分割することなく異なる確率を選択できることに注意すること。

ノードがDandelionトランザクションの送信を準備する際、偏ったコインフリップをしなければならない。コインフリップの結果がDandelionトランザクションの場合、ノードはトランザクションを適切なDandelion宛先に送信する必要がある。結果がDandelionトランザクションでない場合は、Dandelionトランザクションを通常のBitcoinトランザクションに変換する必要がある。Dandelionトランザクションは10%の確率で通常のBitcoinトランザクションに変換されるはずだ。

トランザクションの停止

stemフェーズ中、トランザクションは単一のパスに沿って中継される。このパスの任意のノードがDandelionトランザクションを受信してオフラインになると、そのトランザクションの伝播は停止する。堅牢性を高めるため、Dandelionトランザクションを転送する全てのノードは受信時にタイマーを初期化する。タイマーが終了するまでにDandelionトランザクションがメモリプールに現れない場合、トランザクションはfluffフェーズに入り、Diffusionで転送される。

Dandelionトランザクションを受信すると、ノードは将来のランダムな時間を停止タイマーとしてセットしなければならない。Dandelionトランザクションが通常のBitcoinトランザクションとして届いた場合、ノードはタイマーをキャンセルする必要がある。Dandelionトランザクションがタイマーが切れる前に通常のBitcoinとして観測されたら、ノードはDandelionをfluffで処理する。

Dandelionトランザクションロジック

以下のケースは、Dandelionトランザクションを参照するネットワークパケットを受信した際のノード振る舞いを定義している。

  • Dandelion TxのINVを受信した場合
    ピアがインバウンドで、そのピアからDandelionトランザクションを受信していない場合、GETDATAで応答する。
  • Dandelion TxのGETDATAを受信した場合
    ピアがインバウンドではなく、Dandelionトランザクションがこのピアに配信されている場合、Dandelionトランザクションで応答する。
  • Dandelion Txを受信した場合
    ピアがインバウンドの場合、Dandelion Txを適切なDandelion宛先に中継する。

実装

参照実装は以下から入手可能。

github.com

全ての機能は以下のURLの単一のコミットに圧縮されている。

https://github.com/dandelion-org/bitcoin/tree/dandelion

互換性

DandelionはBitcoinの既存バージョンと競合しない。DandelionをサポートするBitcoinノードは、古いソフトウェアバージョンを実行するBitcoinノードと同様に見える。DandelionをサポートするBitcoinノードは、プローブメッセージを介して機能サポートを識別することができる。明らかに古いノードはDandelionルーティングの互換性はない。DandelionをサポートするBitcoinノードでも、接続先にDandelionをサポートするピアがない場合、Dandelionトランザクションの停止により、自然とDandelionサポートのないBitcoinノードの動作になる。

Bitcoinのプライバシーを向上する決済プロトコル Pay to EndPoint（P2EP）

Bitcoin

Blockstreamが先日公開した、Bitcoinのfungibilityの問題を改善するため、Pay to EndPoint（P2EP）という決済プロトコルを発表してたので見てみる↓

blockstream.com

Bitcoinのプライバシーの課題

Bitcoinの課題の１つとして挙げられるのがfungibility。

現金であれば、それがどのような使われ方をして自分の財布の中にあったとしても、その紙幣を使って支払いができる。偽札でも無い限り、紙幣での支払いを拒否されることはない。１万円札はどこに行っても同じ１万円の価値があり、交換可能。

たがBitcoinの場合、自分が持っているコインがどういう経路を辿ってきたか、ブロックチェーンを分析することである程度分かる可能性がある。そのコインの出処によってはそのコインの支払いを拒否するといった可能性も否定できない。本来、どいういう経路であれ自分が受け取り財布の中にあるコインは、同じコインとして使用できるべきで、コインの出処によって関係のないユーザーの価値が毀損されるという自体は避けたいが、現金と比べると、こういった代替可能性がBitcoinの場合は低い。

このfungibilityの課題について改善しようというのがPay-to-EndPoint (P2EP)のゴール。

コインの出処や所有権が追跡できるようにしようとブロックチェーンの分析がされているが、この分析は、１つのトランザクションのインプットは全て同じユーザーが所有している「common input ownership」という仮定に基づいて行われている。まぁマルチシグやCoinJoinのような取引を除いて、ほとんどの取引は事実そういうトランザクションになっている。コインの追跡はこの前提を元に行われるので、この前提を壊せばコインの追跡がしにくくなり、Bitcoinにおけるfungibilityの課題を改善できるのではないか？ということみたい。

では、「common input ownership」の前提を崩すにはどうすれば良いかというと、

普段コインを送金する際は、コインの受信者が送信者にアドレスを伝え、送信者がそのアドレス宛にコインを支払うトランザクションを作成＆署名し、ネットワークにブロードキャストする。この場合、当然送信者が作成するトランザクションのインプットのUTXOの所有権は送信者が持つものだ。

P2EPでは、この送金トランザクションのインプットに送信者のUTXOに加え、受信者のUTXOも加えることで「common input ownership」の前提を崩そうとしている。

具体的には↓

Pay to EndPointのプロトコル

Pay to EndPointでは、以下の手順で、受信者と送信者が協力して送金トランザクションを作成する。

手順１

受信者はまずBIP-21形式の送金先URIを生成し、送金先として送信者に送る。この時、URIにP2EPのエンドポイントを付与する。

bitcoin:175tWpb8K1S7NmH4Zx6rewF9WQrcZv245W?p2ep=3j4tau93wkc8mh32.onion

↑のようなURIが生成される。通常のBIP-21のURIに加えて、p2epキーでP2EPのエンドポイントのURI3j4tau93wkc8mh32.onionが付与されている。

※ BIP-21のURIの定義には未定義のkey-valueを指定可能なので、P2EPに対応していないウォレットは、従来の方法でコインを送ることになる。

手順２

送信者は受信者から送られてきたエンドポイントが有効であれば、受信者との対話を始める。

  • エンドポイントが有効でない場合
    通常の送金と同様BIP-21のURIに記載されているアドレス宛にコインを送金する。
  • エンドポイントが有効な場合
    UTXOの所有権の証明として、自分が送金する額を持つ自身のUTXOをトランザクションのインプットにセットした署名済みのトランザクションを受信者に送る。

手順３

受信者は署名のため多数のトランザクションを署名のため送信者に送る（これらのトランザクションはさっき送信者が送ってきた送信者のUTXOと、受信者のUTXOがセットされたものと思われる）。 ただこれらのトランザクションのうち、実際に受信者が所有しているUTXOがセットされたトランザクションは１つのみで、それ以外は未使用のUTXOプールから選択されたUTXOがセットされたトランザクションになる。

このトランザクションは、送信者に直列もしくは並列で送られる。

直列送信

順番に送信されるトランザクションのどれが受信者のUTXOを持つトランザクションかの確率は、受信者が選択し署名したトランザクションの数と順番がどのようにランダム化されたかによって代わる。一連のトランザクションの交換は、送信者が受信者のUTXOを使った署名済みのトランザクションを受信者に送ると終了する。

並列送信

受信者によって作成されたトランザクションは全て一度に送信者に送られる。送信者が受け取った一連のトランザクションの内、受信者が所有するのは１つのみ。送信者が正しいもの（受信者のUTXOを持つTx）を選択する確率は、受信者が選択して送信したトランザクションの数に比例する。送信者は全てのトランザクションに署名し、受信者に送付する。

上記いずれかの方法で受信者が送信するトランザクションの数は今のところ100個で、いずれかの側でプライバシーとデータ送信/処理のバランスを取る。

UTXOを交換する上記の方法は、Bulletproofsを使用する方法で置き換えられるかもしれない。

手順４

手順３のどちらのケースでも、受信者は署名済みのトランザクションを手に入れので、このトランザクションに受信者の署名を加えてブロードキャストする。このトランザクションのインプットには受信者と送信者の両方のUTXOが含まれている。

上記P2EPのプロセスが何らかの理由で失敗した場合は、従来通りの方法でコインを送金する。

P2EP送金の具体例

アリスがボブに1 BTC送金したい場合、P2EPのプロトコルを使って以下のようなトランザクションを作成する。

  • アリスはトランザクションのインプットに3 BTCをセットする。
  • ボブはトランザクションのインプットに5 BTCをセットする。
  • アリスはお釣りとして2 BTC受け取る。
  • ボブはアリスからの送金分とお釣りで6 BTC受け取る。

こうやってできたトランザクションは「common input ownership」の仮定を崩したものになる。これがどういう送金なのかはいろんな解釈ができる。例えば、アリスが3 BTCと5 BTCのUTXOを使って、ボブに6 BTC支払い、2 BTCのお釣りを受け取ったなど。

P2EPの利点と欠点

利点
  • 「common input ownership」の仮定を崩せる。最小限の採用であっても、通常の非P2EPトランザクションのプライバシーを改善できる。
  • subset sum analysisを壊す。
  • 受信者のUTXOを使用することで、UTXOの膨張を低減させるのに役立つ。
  • 受信者はP2EPを使うことでUTXOセットを統合できる。
  • 従来のCoinJoinトランザクションと異なり、見た目は通常のトランザクションと変わらないので、トランザクションタイプを特定するのが困難。
  • 送信者のウォレットは軽量ウォレットでいい。
  • 送信者と受信者にはより大きなプライバシーが与えられる。
欠点

P2EPの今後

P2EPはまだ初期段階なので、正式な提案の前に今後コミュニティからのレビューと改良が加えられる。

P2EPの考え方は、支払いの分割やコインスワップなど他の形態のトランザクションを含むよう拡張することも可能と。

所感

  • 受信者側にホットウォレットとフルノードへのアクセスが必要というのは、それなりにハードル高い。
  • ↑の手順3で受信者が多数のトランザクションを送信者に送ってるのが、UTXOのスプーフィング攻撃への対応？
  • P2EPに限らず、P2Pの参加者間で対話的に決済トランザクションを作成するネットワークの標準仕様とかあると便利かも。
  • 通常のP2PKHの送金だと一般的には１つのインプットと2つのアウトプット（送金先のアウトプットとお釣りのアウトプット）が考えられ、UTXOの数は増えていくトランザクションが多いと思うけど、インプットに受信者のUTXOが増えることでUTXOの膨張を低減させるって視点はおもしろいな。

安全性とプライバシーを強化するペイメントチャネルネットワーク「Multi-Hop Locks」

Bitcoin Lightning network Payment Channel Scaling Bitcoin

LNではHTLCを使って仲介者を経由したマルチホップ決済を可能にしている。例えばアリス→キャロルのオフチェーン決済をボブとマイクを経由して行うケースでは以下のような決済フローになる。

f:id:techmedia-think:20180704140150p:plain

  1. 最初に受信者のキャロルがランダムな値Rとそのハッシュ値H(R)を生成し、H(R)をアリスに渡す（invoice）。
  2. アリスはキャロルまでの経路を決め、H(R)とタイムロックを組み合わせたHTLCトランザクションをボブとのペイメントチャネルに投げる。
  3. 仲介者はさらに経路上の隣のユーザーにHTLCを流していく。
  4. キャロルまでHTLCが届いたら、マイクにRを明かして資金を受け取る。
  5. 今度は逆方向に終着点アリスまでRと交換に資金をセトルメントしていく。

ここでタイムロックとシークレットを組み合わせたHTLCは、以下のような条件を持つコントラクト（↑のアリスとボブで考えた場合）

  • 3日経過する前にボブがハッシュを取るとH(R)になるようなRを生成できればアリスはボブにコインを支払う。
  • 3日経過するとアリスにコインが戻ってくる。

こういったマルチホップ決済について、一般化し安全性およびプライバシー保護を強化するMulti-Hop Locksという新しい提案が発表された↓

https://eprint.iacr.org/2018/472.pdf

↑のホワイトペーパーの著者であるPedro Moreno-Sanchezのプレゼン↓

youtu.be

マルチホップ決済のモデル化

↑のホワイトペーパーではこのマルチホップ決済のようなロック機構をMulti-Hop Locksという暗号プリミティブとしてモデル化している。このモデル自体はマルチホップ環境下のロックを一般化したもので、LNはその使用形態の１つ。LNの場合はロックの解除＝コインの入手を意味するMulti-Hop Locksの一使用形態になる。

ホワイトペーパーでは、このモデルを実装するための方法として以下の３つの方法を提示している。

  • 一方向準同型関数を使った一般的なスクリプトベースの構成
  • Schnorr署名を使ったScriptless Scriptベースの構成
  • ECDSAを使ったScriptless Scriptベースの構成

一般的なスクリプトベースの構成では一方向の準同型関数を使った任意のコントラクトを作成できるブロックチェーンである必要があり、EthereumやHyperledger Fabricがターゲットとして挙げられている。BitcoinはまだSchnorrはサポートしていないので、現状のBitcoinベースでMulti-Hop Locksを実装する場合、ECDSAを使ったScriptless Scriptの構成になる。この場合、2017年にYehuda Lindellが発表した「Fast Secure Two-Party ECDSA Signing」を使って後述する鍵生成やロックが実装される。

（参考） techmedia-think.hatenablog.com

Multi-Hop Locksは以下の5つのプロトコルで構成される。

f:id:techmedia-think:20180705095024p:plain

1. 鍵生成

チャネルを構成する二者間の鍵を生成するプロトコルで、アリスとボブがいた場合アリスの鍵 {sk_1}とボブの鍵 {sk_2}、最後にアリスとボブの共通公開鍵 {pk}を返す。

基本的にはチャネルを開設した時点で、お互いの公開鍵を知り、共通公開鍵を共有している状態（チャネルを開いた時点で鍵生成プロトコルは実行済み）になると思われる。

2. セットアップ

セットアッププロトコルは、参加者の集合（＝LNで決済する際の経路）が与えられた際に、経路上の各参加者に状態 {s_i}を与えられる。また最後の参加者（＝LNでコインの最終的な受信者）にはさらにオープン鍵 {k_n}が与えられる。各状態はこの後のロックを生成するのに使われる。

3. ロック

続いて隣り合う各参加者のペアがロックプロトコルを実行する。ユーザーのペアを {U_i}と {U_{i+1}}とした場合、2人は両者の初期状態 {s_i}と {s_{i+1}}を使ってロック（ {L_i}）を作成する。このロックは、ある暗号条件が {U_{i+1}}によって解かれた場合に、 {U_{i}}がある量のコインを {U_{i+1}}に支払うというコミットメントになっている。

既存のLNではこのロックをアンロックする際に必要となるのは、受信者がコインを受け取る際に必要なプリイメージで、経路上の全ノードのコミットメントで同じ値が使用されるが、Multi-Hop Locksの場合はアンロック条件は隣り合うノード毎に異なるのが特徴だ。

↑の図のアリスとボブの場合は、初期状態 {s_0}、 {s_1}を使って、ロック {L_0}を生成し、 {s_0^{R}}をアリスに {s_1^{L}}をボブに送る。

このロックは、 {L_0}のロックを解いたらアリスがボブにコインを支払うというコミットメントを表す。

4. リリース

リリースプロトコルは↑のロックを解放するプロトコルで、オープン鍵kと {(s_i , s_i^{R}, s_{i}^{L})}が与えられた時、新しいオープン鍵k'を返す。

↑の図では、キャロルがロック {L_2}をアンロックするために、最初に受信したオープン鍵 {k_3}と {(s_3 , s_{3}^{L})}を使って新しいオープン鍵 {k_2}を入手する。キャロルは {k_2}でL2をアンロックすると、今度はマイクが {k_2}と {(s_2 , s_2^{R}, s_{2}^{L})}を使って、L1をアンロックするためのオープン鍵 {k_1}を入手できる。これを送信者のアリスに辿り着くまで続ける。

5. 検証

検証プロトコルは、↑のリリースプロトコルで生成したオープン鍵とロックから、そのロックがリリースできるか検証する。

一方向準同型関数を使った実装

モデルでなんとなーくのイメージは掴めるけど、一般化されたモデルで実際のロジックが分かりづらいため、一方向準同型関数を使った実装で理解する。

一方向準同型関数というのは、 { y = f(x)}のような関数で、yからxを計算することが困難で、かつ {f(x) \cdot f(x') = f(x \cdot x')}のような準同型性がある関数。

楕円曲線の鍵ペアを使うのが簡単で、秘密鍵をxとした場合y = xGとなり、xG + x'G = (x + x')Gとなる性質を持つ関数を採用する。

セットアップフェーズ

  1. LNで支払いを行う送信者は受信者までの数分（n）、ランダムに値をサンプリング（ {y_0, ..., y_n}）する。
  2. 送信者は受信者までの各ユーザーに対して３つのアイテム= {(\sum_{j=0}^{i-1}y_jG,\, \sum_{j=0}^{i}y_jG,\, y_i)}を送る。参加者が3人の場合、以下のデータが送られる。
    • {U_0}（送信者）には {(n/a, y_0G, y_0)}
    • {U_1}（中間者）には {(y_0G, (y_0 + y_1)G, y_1)}
    • {U_2}（受信者）には {((y_0 + y_1)G, (y_0 + y_1 + y_2)G, y_2)}
  3. 受信者にだけ、 {\sum_{i=0}^{n-1}y_i}をオープン鍵を送る（この場合オープン鍵 = {y_0 + y_1 + y_2}）。

ロックフェーズ

各ユーザーは、送信者から送られたデータを元に、ロックスクリプトを構成する。3つ受信したアイテムの内、右側のノードの2つめのアイテムと、左側のノードの1つめのアイテムは同じデータを指しているので、それを使ってロックをする。

例えばU_2とU_3の間のロックはU_2の {(y_0G, (y_0 + y_1)G, y_1)}の2つめのデータと、U_3の {((y_0 + y_1)G, (y_0 + y_1 + y_2)G, y_2)}の１つめのデータは {(y_0 + y_1)G}で同じ値になる。これを使ってロックスクリプトを構成する。この時の条件は、 {y_0 + y_1}が明らかになればU_2からU_3にコインを支払うというもの。

これがHTLCの代わりで経路上の全ノードが実行する。

リリースフェーズ

受信者がセットアップフェーズで送信者から送られた y_{n-1}とオープン鍵を使ってコインを入手する。3者の場合、受信者U_3は、y_2を知っているので、別途送信者からもらったオープン鍵 {k = y_0 + y_1 + y_2}からy_2を引いて {y_0 + y_1}の知識を得る。 {y_0 + y_1}は、 {U_2}と {U_3}間でロックされているコインのアンロックするのに有効なプリイメージなので、これを {U_2}開示するとコインを入手することができる。

続いて {U_2}は {y_0 + y_1}が分かるので、セットアップフェーズで受信したy_1を引いてy_0を計算する。y_0が分かれば {U_0}からコインを入手できるという仕組みだ。

図にまとめると↓な感じ。

f:id:techmedia-think:20180801142831p:plain

説明のためにプリイメージのみをアンロック条件として記載しているけど、実際はプリイメージを知っているアリスが不正をしないよう、各ノード間のコントラクトには別途参加者の鍵での署名も条件に加わると思われる。

こうやって準同型性のある一方向関数を使うことで、受信者側（左側）から順にコインをアンロックし、アンロックに使用した値がさらにその先のロックをアンロックするのに使われる仕組みを実現しており、これがHTLCの代替になる。HTLCと比べて各中間ノードで扱われる条件はそれぞれ異なるのでプライバシー及びセキュリティの向上になると考えられる。

※ なお、現状のBitcoinでは一方向準同型関数を使った構成はスクリプトで実装できないので、現状のBitcoinに適用する場合は別のECDSAを使ったScriptless Scriptの構成を取る必要がある。SchnorrやECDSAを利用した実装については、別途書けるといいな。

Multi-Hop Locks のメリット

従来のペイメントチャネルが、ハッシュのプリイメージとコインを交換するHTLCの連鎖であったのに対し、Multi-Hop Locksでは各ホップで両者の状態（ {s_i, s_{i+1}}）を使ってロックを構成し、そのロックは右側のロックをリリースした際のオープン鍵を使ってアンロックできるようになっている。

このモデルでは既存のペイメントチャネルに比べて以下のようなメリットがある。

  • HTLCでは経路上に同じシークレット値とそのハッシュを使用するが、Multi-Hop Locksは各ホップ毎にロック条件が異なるのでプライバシーが向上する。
  • HTLCの場合、途中のコミットメントトランザクションがブロードキャストされると、HTLCが使われていたことがチェーン上で明らかになるが、Scriptlessで構成した場合チェーン上に現れるのは（P2PKHのような）通常の決済のトランザクションと同じになるのでプライバシーが向上し、さらにトランザクションサイズも削減され、その結果、手数料、オンチェーン上のスペースの削減が見込まれる。
  • Scriptlessの構成の場合、EthereumなどのECDSA（もしくはSchnorr）をサポートするその他の暗号通貨にも同様に適用可能。
  • LNに限らずAtomic SwapもScriptlessベースで行うと、HTLCトランザクションがオンチェーン上に記録されることはなく、プライバシーの向上が見込める。