Develop with pleasure!

福岡でCloudとかBlockchainとか。

Succinct Atomic Swap

Statechainなどを発表したRuben Somsenがシンプルな新しいAtomic Swapプロトコルを公開したので見てみる↓

https://gist.github.com/RubenSomsen/8853a66a64825716f51b409be528355f

プロトコル自体はECDSAおよびSchnorrとAdaptor Signatureを利用したScriptlessなAtomic Swapプロトコルになっており、最初にAdaptor Signatureについて理解しておくのがお勧め↓

goblockchain.network

goblockchain.network

Succinct Atomic Swapプロトコル

アリスからボブへ1BTC、ボブからアリスへ200LTCを交換するAtomic Swapの手順は以下のとおり:

  1. アリスはまず、自身の1BTCをアリスとボブの公開鍵にロックするトランザクションを作成する。
  2. 続いて、1のUTXOをインプットとした以下のトランザクションを作成する。
  3. アリスが1のトランザクションに署名して公開する前に、両者はrevoke_txrefund_txtimeout_txについて以下の署名を作成する。
    • revoke_tx:両者がそれぞれsigRevokeAlice、sigRevokeBobを作成し共有。
    • refund_tx:ボブはAdaptor Signature{sigRefundBob}を作成し共有(アリスはブロードキャスト時に自身分の署名を作ればいいのでこの時点では不要)。Adaptor Signature{sigRefundBob}は署名を完成させるためにはsecretAliceの開示を必要とする。つまりアリスがrefund_txをブロードキャストすると、ボブはsecretAliceの情報を知ることができる。
    • timeout_tx:アリスがsigTimeoutAliceを作成し共有(ボブはブロードキャスト時に自身分の署名を作ればいいのでこの時点では不要)。
  4. 署名が入手できたらアリスは1のトランザクションに署名してブロードキャストする。
  5. 一方ボブはLitecoinのチェーン上で交換する200LTCをセットアップする。ボブの持つ200LTCをsecretAliceとsecretBobから生成した公開鍵宛にロックするトランザクションを作成しブロードキャストする。
  6. アリスはsuccess_txを完成させるために必要なアリスの署名のAdaptor Signature{sigSuccessAlice}を作り、ボブに送る。sigSuccessAliceは署名を完成させるのにsecretBobの開示を必要とするAdaptor Signature。
  7. ボブはsigSuccessBobと一緒に、secretBobを使ってsigSuccessAliceを計算しsuccess_txを完成させることで1 BTC入手できる。これによりアリスはsecretBobを知るので、5の200LTCを入手するトランザクションを作成することができる。

以上がプロトコルの手順。

  • 4の時点でプロトコルが停止した場合:
    アリスはrevoke_txを公開し、その後refund_txを使って資金を回収する。アリスが期間内にrefund_txをブロードキャストしない場合、ボブはtimeout_txをブロードキャストすることで資金を入手できる。
  • 5の時点でプロトコルが停止した場合:
    アリスはrevoke_txを公開し、その後refund_txを使って資金を回収する。refund_txがブロードキャストされるとボブはsecretAliceが分かるので、5でロックしたLTCを取り戻すことができる。

Succinct Atomic Swapの特徴としては、↑のプロトコルから分かるように、タイムロックを必要とするのはBTC側のみで、LTC側ではなんらタイムロックを必要としない。このためLTC側のトランザクション構成はとてもシンプルだ。これはAdaptor Signatureの組み合わせにより、片方のコインの入手/払い戻しが一方のコインを償還/払い戻しする際のシークレットの開示とセットになっているため。

クロスチェーンでタイムロックの仕組みを動作させる際には、双方のチェーンのタイムロックの仕様やブロックのマイニング状況に左右されることもあるので、そういった要素を1つのチェーンのみに集約できるのはメリットとして大きいと思う。

LNの新しいチャネルタイプAnchor Output

LNでは送金の度に残高を更新したコミットメントトランザクションを新しく作り署名する。チャネルを閉じる際には、

  • 両者が協力してClosingトランザクションを作成し閉じるパターン
  • (相手と通信できないなどで)片方の参加者が最新のコミットメントトランザクションをブロードキャストし一方的に閉じるパターン

の2パターンがある。前者であれば両者が新しくトランザクションを作成するのでその時点の手数料市場を参考に手数料を再設定する余地があるが、後者の場合、手数料面で問題が発生する。コミットメントトランザクションを作成し署名した時点から、チャネルをクローズするためにコミットメントトランザクションをブロードキャストするタイミングまでかなり時間が経過しているケースの場合、トランザクション作成時に設定した手数料と比べて、ブロードキャスト時の手数料はその時点の手数料市場からみて低すぎたり、高すぎたりする場合が考えられる。

高めの手数料の場合は単純に手数料を損するだけだが、手数料が低い場合は以下のような問題が発生する。

  • 相手がオフラインで自分がコミットメントトランザクションをブロードキャストした場合、自分の残高のアウトプットはOP_CSVにより相対的なタイムロックされているが、そのタイマーが稼働開始するのはコミットメントトランザクションがブロックに格納されてからであるため、コミットメントトランザクションがブロックに格納されるまで時間がかかるとタイマーの開始も遅くなり、長時間自分の資金がスタックされる。
  • マルチホップ支払いのためのHTLCアウトプットがタイムアウトする。単純にチャネル参加者2者の残高を管理しているアウトプットは一方にOP_CSVを使ったタイムロックが設定されているが、これは相対的なロックタイムなので問題にならない。しかし、マルチホップのHTLCアウトプットに設定されているタイムロックはOP_CLTVを使った絶対時間によるタイムロックなので、この部分とトランザクション承認の遅延が問題になる。もしコミットメントトランザクションがHTLCの絶対時刻までにブロックに含まれない場合、タイムアウトによる払い戻しが可能になり、HTLCの資金を失う可能性がある。また先日書いた以下のような攻撃手法も考えられる↓

techmedia-think.hatenablog.com

こういった問題に対応するために、現在提案されているのがAnchor Outputと呼ばれる新しいチャネルタイプ↓

github.com

Anchor Output

コミットメントトランザクションの手数料自体はトランザクション作成時に決まってしまうので、その際の手数料は最小限に設定しつつ、CPFP(Child Pay For Parent)*1を使って手数料をバンプできるようにするために追加されるのがAnchor Output。

CPFP carve-out

なお、この仕組みをワークさせるために事前にBitcoin Core 0.19.0でCPFP carve-outというトランザクションリレーポリシーが追加された。もともと親子関係のあるトランザクションについてBitcoin Coreでは、メモリプールのトランザクションに25の子孫があった場合、 もしくはトランザクションとその全ての子孫が101,000vbyteを超えていた場合、 新しく受信したトランザクションもその子孫であれば無視するという制限がある。マルチパーティのトランザクションにおいてこれを悪用し、攻撃者が予めメモリプールに自身の作った子孫Txを大量に作ることで、相手にCPFPを使わせないといった攻撃が可能になる。そのためこの条件を緩和し、子孫がトランザクションの直接の子であり、子のサイズが 101,000 vbyte以下の場合、もう1つの子トランザクションの受け入れを許可するというもの。つまり、パッケージ制限を突破できる子トランザクションの条件は

これによりペイメントチャネルのようなマルチパーティコントラクトのアウトプットに対して、CPFPによる手数料のバンプを両者が確実に実行できることが保証される。

Anchor Outputの仕組み

通常コミットメントトランザクションは自分と相手の残高をセットした2つのアウトプットを持つ(マルチホップの場合HTLCアウトプットが追加される)。

Anchor Outputの追加

この従来のコミットメントトランザクションについて、チャネル参加者につき1つ、(現状ペイメントチャネルの参加者は2名なので)合計2つのAnchor Output(to_local_anchorto_remote_anchor)を新たに追加する。このアウトプットにロックされる資金は1アウトプット辺り330satoshi(P2WSHのdust limit)と少額なもので、チャネル開設者が資金をセットする。

Anchor Outputのスクリプトは以下の構成になっている↓

<local_funding_pubkey/remote_funding_pubkey> OP_CHECKSIG OP_IFDUP
OP_NOTIF
    OP_16 OP_CHECKSEQUENCEVERIFY
OP_ENDIF

チャネル参加者であればすぐに使用可能で、コミットメントトランザクションがブロックに格納されて16ブロック経過したら誰でも利用可能になる。これはこの少額のUTXOによるUTXOセットの汚染を防ぐため。Anchor Outputの署名鍵がlocal_funding_pubkey/remote_funding_pubkeyになっているのも、第三者がこのUTXOを回収できるようにする(redeem scriptを計算できるようにする)ため。

他のアウトプットに1 OP_CSVの条件を追加

コミットメントトランザクションに2つのAnchor Outputを追加したので、チャネル参加者の両者がすぐに子トランザクションを作成できるようになる訳だが、CPFP carve-outにより許可されるのは2つまでだと思われるので、このAnchro Output以外にすぐ使用可能なアウトプットがあるとまずい。そのため、コミットメントトランザクション内の非Anchro Outputのアウトプットのスクリプトには1 OP_CSVの条件が付与される。つまり既存のコミットメントトランザクションのアウトプットには1ブロックの相対タイムロックが付与される。

その他

Anchor Outputはコミットメントトランザクションをブロードキャストした際、どちらの参加者が手数料を支払うかについて選択肢を与えることにもなる。両者それぞれが使用可能なAnchor Outputを1つずつ持つので、素早くブロックに含めたい方がCPFPで手数料を付与できる。

というのが現状のAnchor Outputの仕組み。仕様はまだ正式にBOLTにマージされてるわけではないので、今後変更が入る可能性もある。ちなみに先日リリースされたlnd v0.10.0-betaにはすでにAnchor Commitmentの機能が実験的に導入されている↓

Release lnd v0.10.0-beta · lightningnetwork/lnd · GitHub

*1:手数料が低くブロックに取り込まれないトランザクションのアウトプットをインプットとした子トランザクションを作成し、その子トランザクションの手数料を高めに設定することで親子一緒にブロックに入れてもらうアプローチ

LNの中継者の資金を奪う攻撃手法

Bitcoin Optech Newsletterで取り上げられていた、LNのマルチホップ決済で中間者の資金を奪う攻撃方法について↓

bitcoinops.org

もともとはLigning-DevやBitcoin-Dev MLでMatto Coralloによって議論されていた内容。

HTLCの構成

LNにおいてアリス→ボブ→マロリーの経路の送金をする場合(HTLCを使ったマルチホップ支払)

アリスとボブ間の送金の挙動は以下のいずれか(分かりやすくするため旧ステートのペナルティ条件は除外)

  • ボブがハッシュのプリイメージを公開すればアリスからの送金を受け取ることができる。
  • ボブがプリイメージを公開しない場合、80ブロック待ったらアリスは送金の払い戻しを受けられる。

ボブとマロリー間の送金の挙動は

  • マロリーがハッシュのプリイメージを公開すればボブからの送金を受け取ることができる。
  • マロリーがプリイメージを公開しない場合、40ブロック待ったらボブは送金の払い戻しを受けられる。

通常このコントラクトを含むコミットメントトランザクションが作成され、プリイメージを使った決済もオフチェーンで行われるが、プロトコル的にはコミットメントトランザクションをブロードキャストすることで、オンチェーン上で決済をすることも可能。

↑のHTLCはオンチェーン上では以下のように動作する。

  1. マロリーがコミットメントトランザクションをオンチェーン上に公開し、プリイメージを提供しボブからの送金を受け取る決済トランザクションを作成する。
  2. ボブがとる行動:
    • ボブがアリス−ボブ間の80ブロックのタイムアウトの前にマロリーの決済トランザクションを確認した場合、ボブはその決済トランザクションを見てプリイメージを知り、そのプリイメージを使ってアリスからの送金をオンチェーンもしくはオフチェーンで受け取る。
    • マロリーの決済トランザクションが確認できない場合、ボブは40ブロック待って、払い戻し用のトランザクションをブロードキャストし、アリスのコインも払い戻しの処理をオンチェーンもしくはオフチェーンで行う。

攻撃方法

↑のオンチェーンHTLCプロセスに対する攻撃は、ボブのプリイメージの学習を妨げると同時に、ボブによる払い戻し用トランザクションの作成を防ぐことで、中継者であるボブから資金を盗むというもの。

プリイメージの拒否

マロリーは自身の決済トランザクションの手数料をすぐにはブロックに取り込まれないよう低く設定する。この場合、ボブがメモリプールを監視しておらず、ブロックチェーン上のトランザクションのみを監視している場合、マロリーの決済トランザクションがブロックに含まれるまで、その存在に気付かず、プリイメーが分からない。

払い戻しの拒否

ボブは80ブロック過ぎればブロードキャストされたコミットメントトランザクションのHTLCアウトプットをインプットとした払い戻し用のトランザクションを作成することで取り戻せるが、それより前にマロリーが↑のように決済トランザクションを事前にブロードキャストすることで、マイナーや他のBitcoinノードが後からブロードキャストされるボブの払い戻しトランザクションの受け入れを拒否する可能性がある。ブロックに含まれてはいないとは言え、決済トランザクションは各ノードにリレーされており、そのインプットであるコミットメントトランザクションのHTLCアウトプットは使用済みであるとされるから、ボブの払い戻しトランザクションはリジェクトされる。

ボブの払い戻しトランザクションはRBF(Replacement by Fee)を使ってより高い手数料を支払うことで、マロリーの決済トランザクションに取って代わる可能性はあるが、実際にはマロリーはさまざまなトランザクション固定技術(RBFを使えないようにするなど)を使ってその交換を防ぐことができる。

↑の攻撃により、ボブは決済トランザクションのプリイメージを知ることも、払い戻しトランザクションが承認されることも防がれるので、80ブロックが過ぎるとアリスはアリス−ボブ間のHTLCコントラクトにより払い戻しを受けられる。マロリーの決済トランザクションが最終的に承認されると、ボブだけが資金を失うことになる。

ただ、オンチェーントランザクションを使った攻撃になるので、トランザクション手数料とか考えると少額決済とかであれば攻撃は割に合わない場合もあるのと、決済トランザクションがブロックに入るタイミングを正確に制御することはできない。

解決策

解決策として挙げられているのは以下の3つ。

メモリプールもチェック

ボブがフルノードを使ってBitcoinのリレーネットワークを監視しメモリプールのトランザクションまで監視することで、マロリーの決済トランザクションについて知ることができるという解決策。ネックはフルノードを稼働させる必要があるというのと、これで完全解決できるわけでも無いということ。全てのフルノードが他のノートと全く同じトランザクションを受信するという保証はなく、マロリーのような攻撃者が、異なるピアに異なる競合トランザクションを送信するケースが考えられる(簡単に攻撃できるわけでもないけど)。

プリイメージの開示を頼むか支払いをするか

既にマロリーによりブロードキャストされた決済トランザクションを各ノードは持っており、それによりボブは払い戻しトランザクションをブロードキャストできない訳だが、接続先のノードがrejectメッセージでrejected: code 123: conflicts with txid 0123...cdefのようにメモリプール内の決済トランザクションのtxidを受け取ることができれば、getdataメッセージを利用して対象のトランザクションを受け取りプリイメージを学習するという方法も考えられる。ただ残念ながらrejectメッセージはBitcoin Coreでは既に無効化されているので使えない(もともと信頼性が低かったので無効化されたっぽいけど)。もしくは、マイナーや他のサードパーティにプリイメージと引き換えに支払いをするというのも考えられるが、こういったことをするためには、別のソフトウェアが必要になる。

Anchor Outputを持つ決済トランザクション

現在LNで新しく提案されている手数料を引き上げられるように設計されたLNのコミットメントトランザクションの特別なアウトプットAnchor Outputを利用して決済トランザクションを再設計する方法。ただし、この場合トランザクションサイズの増加により手数料が増え、事前署名が必要となる。

3つの解決策の中では好ましい解決策とされているみたいだけど、まだ利用できる状態ではないので、実装を待つ必要がある。

またこの攻撃とは別に、オンチェーンLNトランザクションの手数料管理に関連する別の課題もある。コミットメントトランザクションの手数料が署名時に設定されているので、署名後、実際にトランザクションがブロードキャストするまで数日、数週間かかる可能性があり、この場合迅速にブロックに入れるためには手数料が署名時の額では足りないケースが考えられるというもの。攻撃にもなるが、事前設定されたコミットメントトランザクションの手数料をバンプする仕組みはいずれの課題でも必要になる。

LNの経路情報を秘匿するRoute Blinding

送信者が受信者の完全な経路を知らなくても支払いやメッセージのルーティングを可能にするRoute Blindingの仕様のドラフトが提案されてるので見てみる↓

https://github.com/lightningnetwork/lightning-rfc/blob/route-blinding/proposals/route-blinding.md

Lightning Networkでは通常、送信者が支払いに使用するInvoiceに記載された受信者までの経路を計算する。

↑のRoute blindingは、経路の最後にある任意のホップ数をブラインドすることで、受信者のノードやチャネル情報を明かすことなく支払いを受けられるようにする、受信者に匿名性を提供するための仕組み。

経路のブラインド

ノード情報(node_id)とチャネル情報(scid(short channel id))は受信者と各中間ノードとのECDHを利用してブラインドされる。

ブラインドする受信者のノードをN(r)とすると、受信者N(r)は以下の手順でルートをブラインドする。

  1. 支払いを受信する自身のノードのチャネルまで、ブラインドするホップを選択する(N(0) <- N(1) ... <- N(r)とする)。この時、経路内の各ホップのノード/チャネルはアナウンスされたものでもいいし、アナウンスされていないものでもいい。
  2. ブラインドに使用する一時鍵E0 = e0 * Gを生成する。
  3. ブラインドホップの数分=i = 0..(r - 1)回、以下の手順で中間ノードのnode_idのブラインド化とscidを暗号化するための共有鍵を導出する。
    1. 受信者が生成した一時鍵と中間ノードN(i)鍵ペアP(i) = ki * Gを使って共有シークレットss(i) = H(e(i) * P(i)) = H(E(i) * ki)を計算する。
    2. 中間ノードの本来のnode_id(P(i))を共有シークレットを使ってB(i) = HMAC256("blinded_node_id", ss(i)) * P(i)を計算することで導出する。導出したB(i)がブラインドされたnode_idとなる。このB(i)秘密鍵を知るのは中間ノードのみ。
    3. 続いてscidの暗号化に使用する鍵をrho(i) = HMAC256("rho", ss(i))を計算することで導出する。
    4. 次のホップの計算に使用する一時鍵を導出する。
      • 秘密鍵e(i+1) = H(E(i) || ss(i)) * e(i)
      • 公開鍵はE(i+1) = H(E(i) || ss(i)) * E(i)

通常hop_dadtaに含まれるscidを暗号化してペイロードにセットするため、tlv_payloadに新しいTLVフィールドencrypted_blobtype10でデータは暗号化されたtlvデータ)を定義する。scidは↑で算出した暗号化鍵rho(i)を使ってChaCha20-Poly1305で暗号化されencrypted_blobにセットされる。(このためhop_payloadtlv_payloadフォーマットを使用する)

上記のように、ノード情報とチャネル情報は

  • 中間ノードのnode_idである公開鍵に共有シークレットを乗算することでnode_idをブラインド
  • 共有シークレットからscidを暗号化する鍵を導出し、暗号化しtlv_payloadencrypted_blobにセット

することでブラインドされる。

受信者は、各ブラインホップの

  • ブラインドされたnode_id
  • 手数料
  • cltv
  • encrypted_blob

データから経路情報を構成し、ブラインドルートとする。尚、ブラインドルートの最初のノードN(0)node_idはブラインドされず、P(0)のまま。

このブラインドルートの情報と最初の一時鍵の公開鍵E(0)インボイスで送信者に伝える。

ブラインドノードへの送信

ブラインドルートを受け取った送信者はブラインドルートの先頭N(0)までの経路を算出する。N(0)node_idはブラインドされていない(P(0)のまま)ので、通常通り算出できる。算出した経路のオニオンペイロードを作成しブラインドルートで拡張する。この時、N(0)のオニオンペイロードE(0)encrypted_blob(0)の値をセットする。

N(0)ペイロードを復号しE(0)encrypted_blob(0)を入手する。続いて、E(0)を使って共有シークレットss(0)を導出し、それを使ってrho(0)を導出し、encrypted_blob(0)を復号し、scidを入手する。転送先が分かったらオニオンメッセージのextensionのTLVフィールドにE(1) = H(E(0) || ss(0)) * E(0)をセットして転送する。

ブラインドルの中間ノードの処理

ブラインドルートの各中間ノードN(1) <- ... <- N(r-1)は、次の転送先ノードについて知るため、次のノードのnode_idをアンブラインドし、encrypted_blob内のscidを復号し次のノードに転送するため以下の処理を行う。

  1. メッセージ extensionのTLVフィールドから一時鍵E(i)を抽出。
  2. 共有シークレットss(i) = H(k(i) * E(i))を計算
  3. encrypted_blobの復号鍵rho(i) = HMAC256("rho", ss(i))を導出
  4. encrypted_blobを復号し、転送先のscidを入手する。
  5. 転送先のノードに必要な次の一時鍵E(i+1) = H(E(i) || ss(i)) * E(i)を導出
  6. 次のノードに送信するオニオンメッセージのextensionのTLVフィールドに導出したE(i+1)をセット

受信ノードN(r)もアンブラインド処理は上記と同様。

以上が匿名化の仕組み。

攻撃手法

受信者によるECDHによる上記のように途中の経路情報をブラインドすることで、受信者に匿名性を提供するのがルートブラインドの機能だが、送信者が手数料とcltvの設定値を調整することで、ブラインドされたノード、チャネル情報をアンブラインドできる可能性についても言及されている。

送信者がルート上のノードに対して少額の手数料を設定して送金を試行することで、ノードの手数料/cltv値を検出し、それをネットワークグラフ内のチャネル情報と比較することで、ブランドされたノード情報をアンブラインドしようとする攻撃手法が挙げられている。こういった攻撃への対応として、無効なHTLCがオファーされた場合に、

  • 使い捨ての鍵を生成し、その鍵を使ってダミーのエラーを返す。この場合送信者はこのエラーの内容を復号できず、ルート内のどのノードが起こしたエラーか分からなくなる。
  • タイミング攻撃を利用したアンブラインドに対応するため、エラーを返す際にランダムな遅延時間を発生させる。

などの対応が挙げられている。ただし、攻撃手法を完全に無効化するものではない。

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

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

Payment Pointプロトコルの構成

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

  1. アリスはボブに自分の公開鍵A、1BTCのインプット、払い戻しアドレスを伝える。
  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で必要とされるもう1つのBの署名は自分で通常のマルチシグと同じように計算すれば良い。

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

Adaptor Signatureの構成

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

アリスの公開鍵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)を使用している

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

 {\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. 2が正しければ、ボブは {s = s' \cdot y^{-1}}で署名(R.x, s)を完成させる。

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

離散対数の等価性の証明

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

  1. 証明者はランダムな値rを選択し、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で行う場合には現実的な選択肢と言える。