Develop with pleasure!

福岡でCloudとかBlockchainとか。

2P-ECDSAを必要とせずHTLCを代替する半Scriptlessプロトコル

Bitcoin Scriptless Scripts Lightning network ECDSA

LNのマルチホップ決済で使われるHTLCの仕組みを代替する仕組みとしてPoint Time Locked Contracts (PTLCs)が提案されている。

既存のHTLCを使ったマルチホップ決済は、支払い経路で同じハッシュのプリイメージが使われるため、プライバシーの懸念や中間者のルーティング手数料を没収するワームホール攻撃などの可能性が考えられる。

離散対数ベースのロック

HTLCを代替するアプローチは、ハッシュのプリイメージの公開によりコインをアンロックする仕組みを、ある公開鍵の離散対数を公開することでコインをアンロックする仕組みに切り替えるというもの。これをAdaptor Signatureを使ってSchnorrやECDSAのデジタル署名技術にエンコードして実現するのがScriptlessでHTLCを実現する仕組みだ。

この仕組みを利用すると、経路内の各ホップで異なる識別子を使ってHTLCのハッシュのプリイメージの提供によるコインの交換の部分を代替できる。プロトコル自体は以前から提案されていて↓

techmedia-think.hatenablog.com

ECDSAベースの実装方法が↓

techmedia-think.hatenablog.com

ただし、このECDSAの実装には二者間で協力してECDSA署名を行う2PECDSAを必要とする。Lindelが発表した初期の2PECDSAは、準同型性のあるPaillier暗号という追加の暗号仮定を導入して二者間で協力して署名を作成する必要があり、Schnorrをを使用する場合と比べてプロトコルが複雑になる。詳しくは↓

goblockchain.network

半Scriptlessなプロトコル

これに対して最近発表されたのが、既存の2-of-2のOP_CHECKMULTISIGを利用してAdaptor Signatureを実現する方法↓

https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-November/002316.html

完全なScriptlessでやる場合は、１つのマルチシグ署名に対してAdaptor Signatureを構成する必要があるため、両者の秘密鍵を秘匿したまま署名を計算するのにPaillier暗号などを導入してプロトコルが複雑になるが、OP_CHECKMULTISIGを使う2-of-2のマルチシグのでは、マルチシグの署名はそれぞれ別に構成され、その内のいずれかでAdaptor Signatureを構成すれば良いので、完全なScriptlessのプロトコルに比べてシンプルなプロトコルになる。

Payment Pointプロトコルの構成

ボブがYの離散対数y（Y = yG）を明らかにしたらアリスからボブに1 BTC送金すると仮定すると、

  1. アリスはボブに自分の公開鍵A、１BTCのインプット、払い戻しアドレスを伝える。
  2. ボブはアリスに自分の公開鍵Bと送金先アドレスを伝える。
  3. 両者はアリスのUTXOをインプットとして、公開鍵AとBを使用したOP_CHECKMULTISIGを使って2-of-2のマルチシグに送金するトランザクションを作成し、TXIDを計算する。
  4. ボブは3のアウトプットをアリスに払い戻すトランザクションを作成し、Bに対応する署名を作成し、アリスに送る。（ボブがYの離散対数を明らかにしなかった場合にアリスが資金を取り戻すため）
  5. アリスは3のアウトプットをボブの送金先アドレスに送るトランザクションを作成しAと補助ポイントYに対して有効な署名を作成し、ボブに送る。
  6. 5のトランザクションについてボブはyを使ってAdaptor Signatureを完成させ、Bに対応する署名を作成し、ブロードキャストする。
  7. アリスは6のトランザクションからyの値を抽出する。

OP_CHECKMULTISIGを使用するので、Adaptor Signatureの補助ポイントは手順5のようにアリスの署名にだけ考慮されていればよく、手順6ではボブはアリスの署名を完成させるためにyを明らかにするが、OP_CHECKMULTISIGで必要とされるもう１つのBの署名は自分で通常のマルチシグと同じように計算すれば良い。

また最終的に完成するトランザクションは通常の2-of-2のマルチシグにロックされたコインを使用するだけのトランザクションなので、上記のような離散対数との交換（つまりAtomic SwapやLNのマルチホップ決済など）が行われたことは当事者以外知る術はない。

Adaptor Signatureの構成

↑のプロトコルの重要な部分は手順5の補助ポイントを使ったAdaptor Signatureの仕組みと、手順６でそれを完成させる仕組みなので、その部分についてもう少し詳しく解説する。

アリスの公開鍵A = aGとすると、アリスはAdaptor Signatureに必要な署名データを以下のように計算する。

  1. ランダムなnonceの値kを選択しR' = kGとする。
  2. 同じnonce kを使ってR = kY（= kyG）を計算する。
  3. Rのx座標をrとする。
  4. RとR'が同じ離散対数を元に計算されていることの証明 {π = DLEQ_prove((G,R'),(Y, R), k)}を計算する。
  5. {\displaystyle s' = \frac{H(m) + r \cdot a}{k}}を計算する。
  6. Adaptor Signatureを(R, R', s', π)とし、ボブに送る。

ここでポイントは

  • nonceの計算でR'とRの計算に同じnonce値kを使用し、Rの計算にGではなくYを使用している
  • s'の計算ではRのx座標であるrを使っている。つまりnonceとしてR = kY（= kyG）を使用している

という点。本来マルチシグで求められるアリスの署名値ｓは、

{\displaystyle s = \frac{H(m) + r \cdot a}{k \cdot y}}

でなければならない。このため署名を完成させるためにはs'に {y^{-1}}を掛けなければならない。つまりyが提供されればボブに1BTC送金するトランザクションのアリス分の署名が手に入る。

続いてボブはAdaptor Signatureが正しいか以下の検証をする。

  1. （G, R', Y, R）が同じ離散対数によって計算されたものか検証。
  2. {\displaystyle R' = \frac{H(m)G + rA}{s'}}が成立するか検証。
  3. ２が正しければ、ボブは {s = s' \cdot y^{-1}}で署名（R.x, s）を完成させる。

アリスは３の署名がセットされたトランザクションがブロードキャストされると署名データから {y = s' \cdot s^{-1}}を計算することでyが得られる。

離散対数の等価性の証明

↑の（G, R', Y, R'）のR', Rが同じ離散対数を元に計算されていることの証明とボブのその検証はこのペーパーより以下のようにして行える。

  1. 証明者はランダムな値ｒを選択し、A1 = rG、A2 = rYを計算し、A1、A2を検証者に送る。
  2. 検証者はランダムチャレンジcを選択し証明者に送る。
  3. 証明者はz = r + kcを計算し、検証者に送信。
  4. 検証者はzを使って、zG = rG + kcG = A1 + cR'およびzY = rY + kcY = A2 + cRが成立するか検証する。

4が成立するとR', Rは同じ離散対数kを元に作成されていることが証明される。↑は対話型で記述しているがFiat-Schamir変換により非対話型に変換することも可能。

尚、↑の方法とは別にPoDLEのプロトコルでも離散対数の等価性を証明できる↓

techmedia-think.hatenablog.com

※ ただ、今回みたいなケースなら離散対数の等価性の証明までしなくても、単純に {s = s' \cdot y^{-1}}計算して、あとはマルチシグのアリスの署名検証通れば良いような気がする。

以上が、OP_CHECKMULTISGを使った半Scriptlessな離散対数ベースのロックの仕組み。

既存の2PECDSAのような複雑さもなくなるので、ECDSAで行う場合には現実的な選択肢と言える。