Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

Bitcoin Scriptless Scripts Schnorr Payment Channel Lightning network Cryptography

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. 送信者は受信者までの各ユーザーに対して３つのアイテム {(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」を構成しているのが分かる。