2021-08-27

異なる楕円曲線間の離散対数の等価性の証明

Bitcoin Monero Cryptography

MoneroからBitcoinとMoneroでAtomic Swapが利用可能になったというアナウンスが出ていて↓

https://www.getmonero.org/2021/08/20/atomic-swaps.html

そのプロトコルの一部で使用されているのが、異なる楕円曲線間の離散対数の等価性の証明。開発をしているのがCOMITというチームで、リポジトリは↓

https://github.com/comit-network/xmr-btc-swap

今回は、Atomic Swapプロトコル全体ではなく、異なる楕円曲線間の離散対数の等価性の証明方法についてみていく。

MoneroでAtomic Swapをする際の課題

チェーンをまたいで資金の交換を可能にするAtomic Swapは、いろんなブロックチェーンで可能になっているけど、MoneroでこのAtomic Swapを行うためには、次の課題がある。

スクリプト言語がない
MoneroにはBitcoin Scriptのようなスクリプトが存在しないので、よくAtomic Swapで使用されているHTLCなどのロジックが利用できない。
楕円曲線の違い
スクリプトを使用せずにAtomic Swapをする方法の１つとしてAdaptor Signatureを利用したスクリプトレスな方法があり、BitcoinとLitecoin間のAtomic Swapでもこの方法が利用できる。ただ、これは2つのチェーンが同じ楕円曲線を使用している必要があり、Moneroで使用している楕円曲線（ed25519）とBitcoinで使用されている楕円曲線（secp256k1）は異なるため、Adaptor Signatureを利用するのは難しい。

今回のAtomic Swapは、後者のアプローチを可能にするもの。

異なる楕円曲線間のインターオペラビリティ

Adaptor Signatureを利用したAtomic Swapは、２つのチェーンで同じ補助ポイント（公開鍵：T = tG）を使って、その補助ポイントの離散対数（秘密鍵：t）の知識が片方のチェーンのトランザクションが公開されることで判明し、その値を使ってもう一方のチェーンのコインの支払いを可能するという仕組みで機能するようになっている。詳しくは、↓のGBEC動画参照。

goblockchain.network

ただ、これは両方のチェーンが、同じ楕円曲線を使用しているから成立する。そのためBitcoinではsecp256k1、Moneroではed25519のように異なる楕円曲線を採用しているチェーン間では成立しない。これはT = tGという１つの鍵ペアが両方のチェーンにおいて同時に成立することができないため。

この問題に対して、各チェーンの公開鍵XとYがそれぞれ異なるものながら、それが実際には同じ秘密鍵xを利用してできた公開鍵であることを、秘密鍵を明かすことなく証明できればクロースチェーンAtomic Swapができるのではないか？というのが今回BitcoinとMoneroでAtomic Swapを可能にしたアイディア。

※ さすがに秘密鍵の鍵長まで違う曲線だと使えないと思うけど。

異なる楕円曲線間の離散対数の等価性の証明

キーとなるのはsecp256k1とed25519という異なる楕円曲線間で離散対数の等価性（DLEQ）を証明するスキームで、↓のペーパーで発表されている

https://web.getmonero.org/resources/research-lab/pubs/MRL-0010.pdf

表記

詳しいプロトコルの前に、表記を定義↓

${\mathbb G}$ ：secp256k1の群
${\mathbb H}$ ：curve25519の（部分）群
${G, G'}$ ：それぞれ ${\mathbb G}$ のジェネレーター
${H, H'}$ ：それぞれ ${\mathbb H}$ のジェネレーター

証明プロトコル

秘密鍵をxとした場合、xGとxHが指す点は異なるが、それらの点の離散対数（x）は同じであることを証明する。ここでxの値は、両楕円曲線で取りうる秘密鍵の数値内であること。

ビットコミットメントの作成

まず、秘密鍵xをビット列に変換する、つまり ${x = \sum_{i=0}^{n} b_i 2^{i}}$

続いて、n -1個（0〜n-2）のランダムなブラインドファクター ${r_i}$ と ${s_i}$ を生成する。そしてn個（n-1）めのブラインドファクターはそれぞれ、

${r_{n-1} = -(2^{n-1})^{-1} \sum_{i=0}^{n-2} r_i 2^{i}}$

${s_{n-1} = -(2^{n-1})^{-1} \sum_{i=0}^{n-2} s_i 2^{i}}$

とする。つまり、 ${\sum_{i=0}^{n-1} r_i2^{i} = \sum_{i=0}^{n-1}s_i2^{i} = 0}$ が成立するように、それぞれ最後のブラインドファクターを選択する。

生成したブラインドファクターと秘密鍵の各ビット値を使って以下のビットコミットメントを生成する。

${C^{G}_i = b_iG' + r_iG}$ （secp256k1用のコミットメント）

${C^{H}_i = b_iH' + s_iH}$ （ed25519用のコミットメント）

ブラインドファクターrとsについては、↑の関係があるため、各ビットコミットメントの合算値について、 ${\sum_{i=0}^{n-1}2^{i} C_i^{G} = xG'}$ および ${\sum^{n-1}_{i=0} 2^{i}C_i^{H} = xH'}$ が成立する。

リング署名の作成

続いて、ビットコミットメントの各ビット値が0か1であること、そして2つの群において同じ値であることを示すリング署名を作成する。

具体的には、各 ${i \in \lbrack 1, n - 1 \rbrack}$ について、ビット値が0か1かで以下の計算をする。

${b_i = 0}$ の場合

ランダムな値 ${j_i}$ と ${k_i}$ を選択し、以下を計算する。

${e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, j_iG, k_iH)}$

${e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, j_iG, k_iH)}$

続いて、ランダム値 ${a_{0, i}}$ と ${b_{0, i}}$ を選択し、以下を計算する。

${e^{G}_{0, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i}(C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i}(C^{H}_i - H'))}$

${e^{H}_{0, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i}(C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i}(C^{H}_i - H'))}$

そして以下を定義する。

${a_{1, i} = j_i + e^{G}_{0, i} r_i}$

${b_{1, i} = k_i + e^{H}_{0, i} s_i}$

${b_i = 1}$ の場合

ランダムな値 ${j_i}$ と ${k_i}$ を選択し、以下を計算する。

${e^{G}_{0, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, j_iG, k_iH)}$

${e^{H}_{0, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, j_iG, k_iH)}$

続いて、ランダム値 ${a_{1, i}}$ と ${b_{1, i}}$ を選択し、以下を計算する。

${e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i}C^{G}_i, b_{1, i}H - e^{H}_{0, i}C^{H}_i)}$

${e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i}C^{G}_i, b_{1, i}H - e^{H}_{0, i}C^{H}_i)}$

そして以下を定義する。

${a_{0, i} = j_i + e^{G}_{1, i} r_i}$

${b_{0, i} = k_i + e^{H}_{1, i} s_i}$

そうして計算した以下のタプルがプルーフになる。

${(xG', xH', \lbrace C^{G}_i \rbrace, \lbrace C^{H}_i \rbrace, \lbrace e^{G}_{0, i} \rbrace, \lbrace e^{H}_{0, i} \rbrace, \lbrace a_{0, i} \rbrace, \lbrace a_{1, i} \rbrace, \lbrace b_{0, i} \rbrace, \lbrace b_{1, i} \rbrace)}$

検証プロトコル

プルーフ ${(xG', xH', \lbrace C^{G}_i \rbrace, \lbrace C^{H}_i \rbrace, \lbrace e^{G}_{0, i} \rbrace, \lbrace e^{H}_{0, i} \rbrace, \lbrace a_{0, i} \rbrace, \lbrace a_{1, i} \rbrace, \lbrace b_{0, i} \rbrace, \lbrace b_{1, i} \rbrace)}$ が与えられたら、以下の検証を行う。

まず、ビットコミットメントが両曲線の離散対数へコミットしているか以下を確認する。

${\sum_{i=0}^{n-1} 2^{i} C^{G}_i = xG'}$

${\sum_{i=0}^{n-1} 2^{i} C^{H}_i = xH'}$

続いて、各 ${i \in \lbrack 1, n - 1 \rbrack}$ について、以下の計算を行う：

${e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i} C^{G}_i, b_{1, i}H - e^{H}_{0, i} C^{H}_i)}$

${e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i} C^{G}_i, b_{1, i}H - e^{H}_{0, i} C^{H}_i)}$

${(e^{G}_{0, i})' = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i} (C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i} (C^{H}_i - H'))}$

${(e^{H}_{0, i})' = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i} (C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i} (C^{H}_i - H'))}$

そして、 ${(e^{G}_{0, i})'}$ と ${(e^{H}_{0, i})' }$ が、プルーフの ${e^{G}_{0, i}}$ と ${e^{H}_{0, i} }$ それぞれ等しく、プルーフのデータが各群の要素であれば検証は成功する。

証明の仕組み

ぱっと↑の証明と検証をみても何をやってるのか分からないけど、基本的な仕組みはMoneroで最初に導入されていたリング署名スキーム（LSAG）↓を拡張した構造になってるっぽい。

techmedia-think.hatenablog.com

この場合のリングは２つで、ブラインドファクターを秘密鍵として、各ビットコミットメントが0か1へのコミットメントであることを確認するスキームになってるみたい。

COMITのスキーム

今回、Bitcoin - Monero間のAtomic Swapを行うソフトウェアを提供しているCOMITでは、↑のSarang Noetherのペーパーのプロトコルをそのまま使っているのではなく、簡略化して安全性を証明したものを使用してるっぽい。ただ、具体的なプロトコルの説明が見つけられなかった。

2021-08-23

LitecoinのMWEBで非対話型トランザクションを構築するプロトコル（LIP-0004）

Litecoin Mimblewimble

Litecoinでは、Extension Blockを利用してMimblewimbleを実装するMWEBの開発が行われているけど、その中でMimblewimbleのトランザクションを送信者のみが構築するプロトコルがLIP-0004として提案されている↓（まだ正式にLIPとしてマージされてる訳ではななくMWEBの開発者であるDavid Burkettのリポジトリ）

https://github.com/DavidBurkett/lips/blob/master/lip-0004.mediawiki

MWのトランザクション構築

Mimblewimbleでは、基本的に送信者と受信者が協力してトランザクションを作成する必要がある。これは送信者が所有するインプットのUTXOのブラインドファクターと、受信者が新たに所有するアウトプットのブラインドファクターの値をそれぞれ秘匿した状態で、インプットのコミットメントとアウトプットのコミットメントの差分値（超過値）に対して共同で署名する必要があるためだ。詳しい仕組みについてはGBECのMimblewimble動画を参照。

非対話型にするための課題

トランザクションの構築が対話型になると、送信者と受信者の通信が必要になり、両者がオンラインになっている必要がある。LNも同様だが、Bitcoinのように送信者のみでトランザクションを構築できると利便性は上がる。そのような非対話型のトランザクションの構築にあたって課題になるのがブラインドファクターの共有。

送信者のみでトランザクションを構築するということは、新たに作られる受信者のUTXOのブラインドファクターを送信者が生成することになる。この場合、

生成したブラインドファクターをどう受信者に伝えるのか？
従来MWプロトコルではこのブラインドファクターが秘密鍵の代わりをしているため、送信者がこれを知るということは、そのコインは完全に受信者だけのものではなく送信者も使えてしまうことになる。

といった課題が発生する。

初期の提案

David Burkettは、Mimblewimbleを実装しているGrinでも送信者のみでトランザクションを構築する提案をしている↓

https://gist.github.com/DavidBurkett/32e33835b03f9101666690b7d6185203

仕組みとしては、送信者と受信者の鍵でECDHを実行し共有シークレットを生成し、それでブラインドファクターとコインの量を暗号化してアウトプットにセットすることで、受信者がブラインドファクターを抽出可能にする。そして別途受信者の公開鍵もアウトプットに追加し、ブラインドファクターによる検証＋その公開鍵に対して有効な署名が提供されているか追加のチェックをコンセンサスに加えることで、送信者が受信者のブラインドファクターを知っている状態でも、受信者しかコインが使用できないようにするというもの。

プロトコルの詳細は、以前書いた↓の「非対話型トランザクション作成」参照

techmedia-think.hatenablog.com

初期提案の問題点

↑の提案に対して、3つの問題点が指摘されている↓

トランザクションがブロックに入る前に、受信者はトランザクションからブラインドファクターを抽出でき、それを変更できるため*1、資金を受け取った事実を否定することができる。
トランザクション・カットスルーにより、アウトプットがブロックに格納される前に削除された場合、支払いの証明をオンチェーンで行えない。
署名がアウトプットやカーネルをカバーしていない場合、ランダム性の欠如によりインプットの署名を再利用することができてしまう。つまり、アリスからボブに支払いをし、その後ボブがチャーリーに支払いをした場合、アリスはreorgを発生させ、ボブ→チャーリーのトランザクションの署名を使って、ボブ→アリスのように支払いを送り返すことができる*2。

LIP-0004の提案

↑の問題を解決するために、Owner Offsetという新たな要素を追加する。

もともと、Mimblewimbleプロトコルでは、コインのインフレーションが発生していないことをチェックするため、以下の検証を行っている

全アウトプットのコミットメントの合計 + 手数料*H - 全インプットのコミットメントの合計 == Kernel excess（超過値）

で、Kernel excessを公開鍵として、それに対して有効な署名を提供する（正確にはKernel excessはkernel offsetとkernel commitmentで構成される）。

↑はコインの量のインフレーションに対するチェックだが、これと似たチェックを送信者の公開鍵に対して行う。トランザクションに新たにOwner excessというフィールドを追加し（正確にはowner offsetとowner proof commitmentで構成される）

全アウトプットのsender_pubkeyの合算値 - 全インプットのreceiver_pubkeyの合算値 == Owner excess

が成立するかチェックする。Owner excessに対する有効な署名があるかチェックする。

アウトプットのsender_pubkeyというのは、受信者がECDHで共有シークレットを導出するための送信者の一時公開鍵。インプットのreceiver_pubkeyというのは、インプットが参照するUTXO（つまり、コイン送信者のUTXO）にセットされている公開鍵。なので、どちらも送信者の公開鍵である（じゃないと非対話型でトランザクション作れない）。

このチェックにより、アリス→ボブ→チャーリーの支払いにおいて、アリスがreorgを起こしてもボブ→チャーリーのトランザクションのOwner excessの署名を再利用することはできなくなる。これは、Owner excessがボブがチャーリーに送金する際の一時公開鍵も含めて計算されているため。

仕様

LIP-0004の仕様を詳細に書くと、

各アウトプットにコミットメント以外に追加のoutput_dataを追加し、それは以下の要素で構成される：

sender_pubkey：送信者の一時公開鍵
receiver_pubkey：受信者の公開鍵
encrypted_data：（送信者の鍵と受信者の鍵による）ECDHで生成された共有シークレットを使って暗号化したデータ（アウトプットの量とブラインドファクター）
sender_signature：送信者の鍵を使ったメッセージreceiver_pubkey || public_nonce || encrypted_dataへの署名

実際に拡張される項目は↓の青色の部分

コンセンサスルールで、以下のチェックを追加する。

output_dataのsender_signatureが公開鍵sender_pubkeyとメッセージreceiver_pubkey || public_nonce || encrypted_dataに対して有効な署名であること。
各インプットのinput_signatureは、それが参照するアウトプットのreceiver_pubkeyに対して有効な署名であること（メッセージはTBDみたい）
owner_proofのowner_signatureはブロック内のカーネルのハッシュに対し有効な署名であること。
各ブロックについて、sum(output.sender_pubkey) - sum(input.receiver_pubkey) == sum(owner_offset)*G + sum(owner_proof.commitment)が成立すること。

攻撃の可能性

↑のowner_offsetの検証が有効なのは、最新のブロックからhorizonブロックまでということなので、それを超えるreorgを発生させると攻撃の可能性が残っているとされている。reorgのコストと攻撃により得られる利益が釣り合うかが判断ポイントで、そのため大きめの資金を受け取った場合は、すぐに自分宛てに使用することで、攻撃を防御可能と。

このhorizonブロックの位置づけがよく分かってないので、また時間があるときにでも調べよう。

*1:Bitcoinなどではトランザクションを一部でも変更すると署名が無効になるが、現状のMWプロトコルではトランザクションアウトプットは署名に含まれないため変更ができてしまう

*2:Bitcoinと違って、トランザクションインプットやアウトプットが署名対象に含まれていない、かつ送信者が受信者のブラインドファクターを知っているため、アウトプットに受信者の公開鍵をセットしたとしても、このような攻撃が可能になる

2021-08-02

LN Offer

Lightning network Bitcoin

LN Offerは、ノードがLNを介してインボイスを要求、受信できるようにするプロトコルの拡張機能の１つで、BOLTにもBOLT 12として提案されている↓

https://github.com/rustyrussell/lightning-rfc/blob/guilt/offers/12-offer-encoding.md

http://bolt12.org/

LNの支払いは、受信者がBOLT 11で定義されているインボイスを発行し、それをQRコードコードなどで読み取って送信者がLN支払いをするというのが一般的で、実際に送信者と受信者がインタラクティブに通信することはない。

LN Offerの機能

LN Offerはインボイスの前段階の処理フェーズで、Offerに基づいてインボイスの要求や発行をするための情報を提供する。

Offerを利用したフロー

Offerを利用した支払いのフローは以下のようになる：

ユーザー→サービス提供者へ支払いをする場合

サービス提供者がWebサイトやQRコードでOfferを公開する。
ユーザーは、LNを介して一意のインボイスを要求する。
サービス提供者は2に対してインボイスを返信する。
ユーザーは送られたインボイスに従って支払いをする。

ユーザーがサービス提供者から支払いを受ける場合

ATMや払い戻しなどでサービス提供者がユーザーへ支払いするフローは：

サービス提供者がユーザー固有のOfferを、WebサイトやQRコードで金額と一緒に提供する。
ユーザーはOfferの金額のインボイスを送信する。
サービス提供者は、2のインボイスに従って支払いをする。

インボイスは１回しか使えないけど*1、Offerの場合同じものを何度でも利用可能。寄付なんかを受け付ける場合も、サイトにOfferのQRコードだけ貼っておけば、寄付したいユーザーがOfferを読んで、インボイスを要求し、発行されたインボイスに対して支払いをする。

メッセージの通信

LN Offerに対してインボイスの要求や発行する際のメッセージの送信には、既存のオニオンルーティングを使ったLNのメッセージ送信の仕組みがそのまま使われる。アプローチは、実際に支払いをしない偽の支払いを送信するLNを使ったチャットアプリとかと似てる。

bootstrap.bolt12.orgで公開されているサンプルを見ると、一番シンプルなOfferのデータは↓

{
  description: "Offer by rusty's node",
  node_id: "4b9a1fa8e006f1e3937f65f66c408e6da8e1ca728ea43222a7381df1cc449605",
  offer_id: "28522b52ac39fa518ce3a5b3e4a9a96372487e78ba5eb1540ec4d9f02ca82718",
  signature: "f4c5b54263766d8aa86dcb28b9973449cf995ef58ce8a96430bbb5b516460f465e9794b6842f1260b400966a3eb7e1557998f858aeb5bce1459ebc984fa3cabb",
  type: "bolt12 offer",
  valid: true
}

Offerを受けつけるnode_idが記載されているので、ここにインボイスの要求/発行をするメッセージをLNのネットワークを介して送信することになるっぽい。

bech32でエンコードしたデータも記載されてる↓けど、どうもQRコード自体がチェックサム機能を持っているから、bech32のチェックサムは省略されてるっぽい（bech32使う必要ないよね。。）。

lno1pg257enxv4ezqcneype82um50ynhxgrwdajx283qfwdpl28qqmc78ymlvhmxcsywdk5wrjnj36jryg488qwlrnzyjczlqs85ck65ycmkdk92smwt9zuewdzfe7v4aavvaz5kgv9mkk63v3s0ge0f099kssh3yc95qztx504hu92hnx8ctzhtt08pgk0texz0509tk

ブラインドパス

↑のOfferにはnode_idが記載されているけど、Offerとインボイス両方についてノードIDを明らかにすることなく、つまりメッセージの送信先を知ることなく、Offerへのリクエスト/レスポンスを返すことも可能。

支払いの証明

通常のLN支払いの支払いの証明は、インボイスに含まれているpayment_hashのプリイメージを示すこと。ただ、この場合、プリイメージさえ知っていれば誰でも支払いをしたと主張できてしまう。

この問題に対処するため、Offerに対してインボイスを要求する場合、送信者は公開鍵payer_keyを、リクエストのTLVフィールドに含める。そして、発行されるインボイスのTLVデータにもこのデータが含まれ、これによりインボイスの所有を証明する。※ 払い戻しの時などに、実際の支払者であることを証明するのに使われる。

また、BOLT 11インボイスの場合、署名がインボイス全体適用されるため、インボイスの全データを公開しないとインボイスを証明することはできなかった。BOLT 12では、各TLVフィールドのデータでマークルツリーを構成し、そのルートハッシュに対して署名が計算される（Taprootと同様の署名スキームを実装している）。このため、支払いに関する情報をすべて公開することなく支払いの証明が可能になる。

※ また署名アルゴリズムはSchnorr署名を採用しており、BIP340と同様、公開鍵はx座標のみをエンコードした32バイトの公開鍵が採用されている。

デプロイ状況

現在BOLT 12はまだドラフトで、c-lightningが実験的にサポートしている状況。

また↑のオニオンメッセージについても、現在まだドラフトで、現状のc-lightningは、オニオンメッセージを送信する際は、直接接続をしてるっぽいので、Torなどを使ってないとプライバシー上のリスクがある状態。

Offerが利用可能になると、OfferのQRコードを公開しておけばよく（WebサイトでもTwitterでも）、後はLNノードにインボイス要求が来たら反応するということが可能になるので、インボイス生成用にWebサーバーとかを別途用意するみたいなことしなくてもよくなる。

ただ、インボイスの要求や配信はオニオンメッセージを介して送信されるので、対象ノードまでの経路がなければ送れないだろうし、これらのメッセージを中継するノードの帯域幅やリソースは消費されることになるんじゃないかな。

*1:使用済みのインボイスは、ネットワーク上でペイメントシークレットが既知のものになっているので、同じシークレットを使用した支払いは安全ではない

2021-07-30

LNのゴシッププロトコルを使った流動性の提供

Lightning network Bitcoin CLN

最近、C-Lightningで実験的にLNのチャネルの流動性（インバウンドキャパシティの提供）をLNのゴシッププロトコルを使って配信する機能がマージされた↓

https://github.com/ElementsProject/lightning/pull/4639

LNの支払いを受ける場合、チャネルにインバウンドキャパシティが必要になる。手数料を支払うことでこのインバウンドキャパシティを提供してくれるLNBIGのようなサービスもある（LNBIGは何で小額でインバウンドキャパシティ提供してくれてるのか不思議だ）。

今回C-Lightningが実装したのは、まだマージされていないけどBOLTにも提案されている機能で↓

https://github.com/lightningnetwork/lightning-rfc/issues/878

LNのゴシッププロトコルを使って、流動性の提供をアナウンスし、リース料をもらいインバウンドキャパシティを一定期間提供するチャネル開設を可能にしようというアプローチ。これが普及すると、チャネルのリバランスも自動化できるようになるかも。

ZmnSCPxjの提案

LNで流動性マーケットを提供する仕組みについては、2018年にZmnSCPxjがLightning-Devメーリングリストで提案している↓

[Lightning-dev] Towards a Market for Liquidity Providers -- Enforcing Minimum Channel Lifetime

流動性を購入する際には、以下の2つが重要なパラメーターになる：

提供されるインバウンドキャパシティ
提供される期間

流動性の提供期間の保証

せっかく購入したキャパシティも、すぐにチャネルが閉じられてしまうと損するだけなので、購入したキャパシティは一定期間利用できる状態にする必要がある。

単純にこの期間を担保する方法として考えられるのは、コミットメントトランザクションのnLocktimeにリース期間を加味したブロック高を設定するという方法。ただ、この場合、支払いをルーティングする際のHTLCのタイムロックと競合してしまう。

そこで、コミットメントトランザクション自体にnLocktimeを設定するのではなく、コミットメントトランザクションの流動性提供側のアウトプットにCLTVを設定するアプローチが提案されている。

流動性提供者をLicky、流動性の購入者をMercyとした場合、

Licky側のコミットメントトランザクションのアウトプットは：

Mercyの残高：Mercyの鍵 && CSV
Lickyの残高： Revocation || (Lickyの鍵 && CSV && CLTV)

Mercy側のコミットメントトランザクションのアウトプットは：

Lickyの残高：Lickyの鍵 && CSV && CLTV
Mercyの残高： Revocation || (Mercyの鍵 && CSV)

という構成になる。ここでCLTVは、流動性が提供される期間＝ライフタイム。既存のコミットメントトランザクションは対称的な構成になるが、流動性のライフタイム（CLTV）が常にLicky側に付くため、トランザクションは非対称な構成になる。

この場合、コミットメントトランザクションをブロードキャストして一方的にチャネルを閉じた場合、どちらがブロードキャストしたとしてもLicky側の残高は流動性のライフタイムが過ぎるまでは動かせなくなる。この仕組みで、購入した流動性の提供期間を保証させる。

もちろん、Lickyがコミットメントトランザクションをブロードキャストするのを防止する方法は無いけど、ブロードキャストしても資金がロックされるだけで、チャネルを維持していれば得られたかもしれないルーティング手数料も手に入らないので、提供側がそのような行為をする経済的なインセンティブはない。

支払いの循環を利用した資金移動

↑の方法で、流動性提供者のインセンティブが設計されるが、例えば、

Licky → Mercy → Randy → Licky

のような経路が存在した場合、Lickyは自分の資金をRandyを経由した自分に送ることで、Licky → Mercy間の流動性を移動することができてしまう。この場合、流動性を購入したMercyにとっては、その流動性が移動してしまうという攻撃が考えられる。

ただ、Mercy → Randy間でも資金が移動していることになるので、逆側から見た場合、流動性は減っていないことになる。そのため、Mercy → Randy間のチャネルにもチャネルのライフタイムを課すことで、この攻撃は緩和できるとしている。

デュアル・ファンディング

流動性の提供者に対して、上記のコミットメントトランザクションを作成しインバウンドキャパシティを購入するが、その際に提供と支払いを同時に行うため、デュアル・ファンディングチャネルを前提としている。

つまり、チャネルを構築する際に、流動性の提供者と購入者それぞれがUTXOを持ち合い、初期残高は、

提供者の残高：拠出額＋流動性の購入費用
購入者の残高：拠出額 - 流動性の購入費用

になる。正確には、オンチェーン手数料がこれに加味される。

BOLTの提案内容

BOLTでは、さらに流動性の提供をLNのゴシッププロトコルで配信できるようにする仕組みが（まだドラフトだけど）提案されている（冒頭に書いたC-Lightningに実験的に実装された機能）↓

https://github.com/lightningnetwork/lightning-rfc/blob/04843175f05e7fdcea8fa1cd730857f3d42c4ca3/proposals/010-will-fund-for-food.md

デュアル・ファンディングを可能にするv2 channelプロトコル上に構築され、流動性を提供したいユーザーは、node_announcementに資金提供するレートをセットして配信できるようになる。

これらの配信情報を見て、インバウンドキャパシティが欲しいユーザーは、request_fundstlvを含むopen_channel2リクエストをノードに送信して、チャネル開設のネゴシエーションを始め、提供側はwill_fundを含むメッセージでこれに応答する。

現状の提案では、流動性の貸出は4032ブロック、つまり約28日間とされてる。資金を貸出用にロックする期間であって、それが経過したらチャネルを閉じなければならないというものではない。

CSVを使ったロック

↑のZmnSCPxjの提案ではCLTVを使ったロックだったが、BOLTの定義では、CSVの使用に置き換わってる。具体的には流動性提供者の残高のCSVに、貸出金のライフタイムの期間分が加算される。

CLTV→CSVにすると、絶対時間指定がコミットメントトランザクションがブロックに入ってからの相対時間指定になるから、リース期間の指定にならないんじゃ？と疑問に思ったけど、別途update_blockheightというメッセージが定義されている。

update_blockheightメッセージは、チャネルの開設者のみが相手に送信できるメッセージで、文字通りブロック高を通知するメッセージになる。このメッセージを受け取ると、チャネルにセットされている流動性を提供しているアウトプットのCSVのタイムロックがブロック数に応じてデクリメントされる。

つまり、チャネル開設当初は、流動性を提供しているコミットメントトランザクションのアウトプット（Licky側のアウトプットには）通常のCSV値に加えて、4032ブロック分のCSV値が加算された値が設定されているが、チャネル開設後、ブロックチェーン上で新しいブロックが作られると、update_blockheightメッセージでそのブロック高を通知し、コミットメントトランザクションのCSV値をデクリメントした状態で更新する。これにより、CSVによる相対時間だけど、CLTVによる絶対時間による流動性の貸出期間の制限と同様の制限を課すようにしたっぽい。なんでCLTV→CSVに変更されたのかは謎。

P2P環境で流動性を提供する試みが始まるという点で興味深い。またこういうオンチェーンに裏付け資産がある状態で、貸出をベースにした金融商品やサービスのアイディアも広がってくるかもしれない。

2021-07-22

Bitcoin Scriptを使ったランポート署名の検証と量子耐性

Cryptography Bitcoin

最近Bitcoin-Devメーリングリストに、OP_CATを使ってBitcoinに量子耐性をもたせる方法について投稿されてたのが興味深かったので見てみる↓

[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]

アイディアは量子耐性のあるランポート署名をBitcoin Scriptで検証するというもので、その仕組みはJeremy Rubinの↓のブログから来てる

https://rubin.io/blog/2021/07/02/signing-5-bytes/

ランポート署名

量子耐性のある署名アルゴリズムの１つがランポート署名で、一方向性関数（通常、暗号学的ハッシュ関数）を利用しており、アルゴリズム自体はとてもシンプル。

秘密鍵の生成

秘密鍵として、n個のランダム値のペアを生成する（nは署名対象のメッセージのビット数に依存する）。ここではn=256とし、各ランダム値のサイズも256 bitであると仮定すると、秘密鍵のサイズは、2 ✕ 256 ✕ 256 = 16 KBになる。

公開鍵の生成

公開鍵の作成は、秘密鍵のハッシュ値になる。つまり↑の2✕256 = 512個の乱数をハッシュしたもの。このハッシュ関数も256 bitとすると秘密鍵と同様サイズは16 KB。

この公開鍵のリストを公開鍵として公開する。

ハッシュ関数にもよるけど、楕円曲線暗号の秘密鍵が32 B、公開鍵が（圧縮版で）33 Bであることを考えると鍵長は大きい。

署名の生成

メッセージに署名する手順は↓

メッセージmをハッシュする→H(m)
H(m)を２進展開する。
2の各bit値に基づいて、対応する秘密鍵をピックアップする。bit = 0の場合はペアの最初の数値を、bit = 1の場合はペアの２つめの値を選択する。
3をメッセージのハッシュ値分行うと256個の数値のリストが生成され、これが署名データになる。サイズは256✕256 bit = 8 KB。

つまり、秘密鍵はn個の乱数値のペアで、署名対象のメッセージのビット値によって、そのペアのいずれかをピックアップしたものが署名データになる。

こういうアルゴリズムなので（署名を提供する＝秘密鍵の一部の提供になるので）、署名に使用した秘密鍵は2回以上再利用してはならない。

署名の検証

↑で生成した署名を検証する手順は↓

メッセージmのハッシュ値を計算する→H(m)
H(m)を２進展開する。
2の各bit値に基づいて、対応する公開鍵をピックアップする。bit = 0の場合はペアの最初の数値を、bit = 1の場合はペアの２つめの値を選択する。
署名値の256個の値のハッシュ値を計算する。
3と4のハッシュ値がすべて一致した場合、署名は正しい。一致しなければ間違った署名データになる。

Bitcoin Scriptでランポート署名を検証

Bitcoinで↑のランポート署名を検証するにはどうしたらいいか？当然、Bitcoin Scriptにはランポート署名を直接検証できるopcodeは存在しないので、↑のブログ記事では、Bitcoin Scriptを使ってランポート署名の検証をしている。ここで検証しているのはトランザクションインプットのnSequenceを署名対象のメッセージとして見立てて、それに対して有効なランポート署名が提供されているかチェックするスクリプト↓

ここでは、nSequenceの値が53593（2進展開すると1101000101011001）であることを要求している。この場合、メッセージの長さは16 bitなので、n = 16。

<pk> CHECKSIGVERIFY
 0
 SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> ADD ELSE <H(K_1_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <1<<2> ADD ELSE <H(K_2_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> ADD ELSE <H(K_3_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <1<<4> ADD ELSE <H(K_4_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <1<<5> ADD ELSE <H(K_5_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <1<<6> ADD ELSE <H(K_6_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <1<<7> ADD ELSE <H(K_7_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <1<<8> ADD ELSE <H(K_8_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <1<<9> ADD ELSE <H(K_9_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1<<10> ADD ELSE <H(K_10_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> ADD ELSE <H(K_11_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> ADD ELSE <H(K_12_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> ADD ELSE <H(K_13_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> ADD ELSE <H(K_14_0)> EQUALVERIFY ENDIF
 SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> ADD ELSE <H(K_15_0)> EQUALVERIFY ENDIF
 CHECKSEQUENCEVERIFY

先頭の<pk> CHECKSIGVERIFYは単純に既存のECDSA署名検証の仕組みで、これはランポート署名とは無関係。

H(K_0_0)やH(K_0_1)、…H(K_15_0)、H(K_15_1)の値は、ランポート署名に用いる公開鍵の値。H()はハッシュ関数で、中身のK_0_0が対応する秘密鍵の値。

このスクリプトをアンロックするために必要なscriptSigは、CHECKSIGVERIFYで評価される通常のECDSA署名と、16個のランポート署名のデータ↓

K_15_1
K_14_1
K_13_0
K_12_1
K_11_0
K_10_0
K_9_0
K_8_1
K_7_0
K_6_1
K_5_0
K_4_1
K_3_1
K_2_0
K_1_0
K_0_1
<sig>

ランポート署名の検証ロジックである↓の部分は、

SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQUALVERIFY ENDIF

（CHECKSIGVERIFYの検証が終わったとして）次のように評価される

No	実行処理	実行後のスタック
1	スタックの先頭２つの順番を入れ替える。最初に評価する時点ではスタックの先頭２つは`0 K_0_1`なのでこれが入れ替わって`K_0_1 0`になる。	`K_0_1 0...`
2	続いて先頭の要素がSHA-256される。	`H(K_0_1) 0 K_1_0 K_2_0...`
3	`DUP`を実行すると先頭の要素が複製される。	`H(K_0_1) H(K_0_1) 0 K_1_0 K_2_0...`
4	`<H(K_0_1)>`がプッシュされる。	`H(K_0_1) H(K_0_1) H(K_0_1) 0 K_1_0 K_2_0...`
5	`EQUAL`によりスタックの先頭２つが比較される。ここでは、scriptSigで提供された秘密鍵と、対応する公開鍵のペアの２つめを比較している。先頭２つは`H(K_0_1) H(K_0_1)`で等しいので`TRUE`がプッシュされる	`TRUE H(K_0_1) 0 K_1_0 K_2_0...`
6	`IF`が評価されスタックの先頭は`TRUE`であるため、IF分岐に入る。	`H(K_0_1) 0 K_1_0 K_2_0...`
7	`DROP`により、`H(K_0_1)`が削除される。	`0 K_1_0 K_2_0...`
8	<1>がスタックにプッシュされ、`ADD`によりスタックの先頭２要素が加算される。つまり1 + 0 = 1。	`1 K_1_0 K_2_0...`

5の分岐でFalseになった場合は、scriptSigの秘密鍵のハッシュともう１つの公開鍵（ペアのうちの１つめ）を比較する。この場合、メッセージの該当bitは0であるため、8の加算は発生しない。

これを繰り返すと、最終的にスタックにはメッセージ53593が残ることになり、それをCHECKSEQUENCEVERIFYで評価する。

というスクリプトにより、やろうと思えば今でもスクリプトを使ってランポート署名の検証は可能。

量子耐性

↑の仕組みを使って量子耐性を持つビットコインを作ろうというのが、続きのブログ記事↓

https://rubin.io/blog/2021/07/06/quantum-bitcoin/

量子コンピューターにより楕円曲線暗号の離散対数仮定が破られたとしても（つまりP = xGとなる公開鍵Pから秘密鍵xを逆算できるようになっても）コインを安全に保つためには、従来の署名データの検証に加えて（ここは量子コンピューターにより侵害可能）、署名データのHash160値を↑のランポート署名で検証すればいいというアイディア。

Hash160だと署名されるメッセージダイジェストの長さは20Bになるので、↑の検証を4バイトずつ実行して、その結果をOP_CATで結合する処理を5回実行した結果が、Hash160(ECDSA署名)と等しければコインを使用できるようするということみたい。ただ、これを実現するためにはOP_CATをBitcoinで再度使えるようにする必要がある。

あと前述したように、ランポート署名の鍵や署名データのデータ長は大きいので、トランザクションサイズはこれまでよりも大幅に大きくなる。