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

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}$ は相手によって違う鍵になると思われる。

セットアップフェーズ

LNで支払いを行う送信者は受信者までの数分（n）、ランダムに値をサンプリング（ ${y_0, ...., y_n}$ ）する。
続いて1〜nについて ${Y_i = Y_{i-1} + y_iG}$ を計算する。なお、 ${Y_0} = y_0G$ 。
送信者は受信者までの各ユーザーに対して３つのアイテムを送信する。送信者から中間者、受信者の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)}$
最後に受信者にのみ追加で、全てのサンプリング値を加算した（ ${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}$ を無視したその署名データは

$\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}}$ を計算すると、

$\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}$ $\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}$ $\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を利用するのね。

Develop with pleasure!

福岡でCloudとかBlockchainとか。