Develop with pleasure!

福岡でCloudとかBlockchainとか。

LNの支払い経路の計算をアウトソースするトランポリンペイメント

Scaling Bitcoin 2019予習シリーズ第二弾は、「Improving routing in the Lightning Network with Trampoline Payments」について。

特にホワイトペーパーが出てる訳でも無いので、確かな内容は分からないんだけど、おそらく現在BOLTにプルリクが出されている↓の内容じゃないかと思われる(提案者もACINQのBastien Teinturierだし)。

github.com

トランポリンペイメントとは?

Lightning Networkをで支払いをする場合、現在は送信者が自身のノードから受信者のノードまでの経路を計算している。この経路を計算するためには、Lightning Networkのノードネットワークの最新情報を保持しなければならない。Lightning Networkが現在の規模のままであれば問題ないかもしれないが、Lightning Networkの採用が進み、チャネル数が数百万などに拡大するとどうなるだろう?経路計算するノードは、より多くのメモリ、ネットワーク帯域および計算能力が必要になる。特にスマートフォンやIoTデバイスのようなリソースが制限されたデバイスにとっては、そのハードルは高くなる。

トランポリンペイメントというのは、そういうリソースが制限されたデバイスのために、経路計算をトラストレスにアウトソースするための提案。例えば以下のようなAからFまでのチャネルグラフがあるとする。

A → B → C → D → E → F

ノードAはFにLNで決済をしたいけど,軽量クライアントで近隣のノード情報しか保持したいため、Cがどこにあるかは知っているけど、Fがどこにあるかは知らない。でもCはネットワーク全体の最新状態を維持するトランポリンノードであった場合、AはCに支払いを送信すると、Cがそこから先のFまでの効率的な経路計算し、支払いをしてくれるという仕組み。

また、通常のLN決済で使われるオニオンルーティングの場合、中継ノードは中継する前後のノードに関する情報は知っているけど、送信者、受信者の情報は分からないというプライバシー特性があるが、このトランポリンペイメントについても同様に、トランポリンノードに送信者の情報および受信者の情報が分からないような仕組みにする必要がある。

トランポリンペイメントの仕組み

では、具体的にどのようにしてトレストレスにトランポリンペイメントがワークするのか見ていこう。

ネットワークビュー

まず、トランポリンノードと制限デバイスのネットワーク形成について。

f:id:techmedia-think:20190731104853p:plain

トランポリンノード

ネットワーク・トポロジーの全体像を把握し、トランポリンペイメントをサポートするトランポリンノードは、option_trampoline_routingのサポートを広告する必要がある。

また、トランポリンペイメントペイメントを中継する意思があるトランポリンノードとなるノードはnode_updateという新しいメッセージを送信する。このメッセージはchannel_updateメッセージと同じ方法で中継される。トランポリンペイメントを中継する意思がないノードは、このnode_updateメッセージを送信しない。

制限デバイスはこのnode_updateによってトランポリンノードを識別する。

制限デバイス

制限ノードは上記のnode_updateを監視することで、トランポリンペイメントを行う際に送信先となるトランポリンノードの情報を得ることができる。これらのノード情報を保存し、どのトランポリンノードを使用するかは自由に選択できる。

単純にnode_updateを受信するだけでは、帯域幅の削減にはならないので、ゴシップメッセージのフィルタリングをする必要がある。制限デバイスoption_gossip_filtersをサポートするリモートノードとのみ接続する。そうすると、リモートノードはフィルタにパスしたメッセージのみを制限デバイスに送るようになる。現在定義されているのは以下の2つのフィルタ。

  • channel_update_filter
    制限デバイスは、リモートノードにchannel_update_filterを送信する。するとリモートノードは制限デバイスchannel_updateを送信する前にこのフィルタにかけ、フィルタをパスしたchannel_updateメッセージのみを制限デバイスに転送する。フィルタの中身は単純に距離数で、リモートノードから指定した最大ホップ数分離れているchannel_updateメッセージのみ受け入れ、それ以上離れているノードのchannel_updateは受け取らない。こうすることで、制限デバイスは近隣のノード情報のみを保持するノードとなる。
  • node_update_filter
    制限デバイスは、リモートノードにnode_update_filterを送信する。するとリモートノードは制限デバイスnode_updateを送信する前にこのフィルタにかけ、フィルタをパスしたnode_updateメッセージのみを制限デバイスに転送する。これによりトランポリンノードのリストを定期的に更新し、その手数料率とcltvを最新の状態に保つ。node_update_filterは、node_idsha256(local_node_id || latest_block_hash)の2つの値の距離に基づいたフィルタになっている。

制限デバイスは、node_updateとフィルタを利用して、ストレージコストとネットワークの帯域幅を削減する。

トランポリンノードを利用したトランポリンペイメント

アリス→ボブのLN支払いをしたく、両者がトランポリンペイメントをサポートする場合は、以下のように決済するようになる。

① ボブはまずインボイスを作成するが、この時ボブの近隣のトランポリンノード(TB1, TB2, TB3)を3つ記載する。

② アリスは近隣のトランポリンノードTA1を選択し、もう1つ異なる(近隣でなくてもいい)TA2を選択。そして最後のインボイスの中から1つのトランポリンノードTB3を選択したとする(アリスはインボイスに掲載されていたトランポリンノードを選択してもいいし、選択しなくてもいい)。この段階でトランポリンノードの経路はアリス -> TA1 -> TA2 -> TB3 -> ボブとなる。

③ 続いてアリスは、この経路で支払いをするため、トランポリンペイメントのために新しく導入されるtrampoline_onion_packetを作成する。trampoline_onion_packetは固定サイズのTLVパケットで、以下の構造を持つ。

  1. タイプ:trampoline_onion_packet
  2. データ:
    • [1 : 0x08] (type)
    • [3 : 0xfde202] (length)
    • [1 : version]
    • [33 : public_key]
    • [672 : tranpoline_hops_data]
    • [32 : hmac]

この中のtranpoline_hops_dataフィールドが、次のトランポリンホップのアドレスや転送情報およびそれに関連するHMACの難読化データで構成されるtrampoline_hop_payloadのリストになる。そのため、ここでは、TA1、TA2、TB3、ボブの3つのtrampoline_hop_payloadをセットすることになる。ここで最後のボブはトランポリンノードではないが、TB3にボブが受信者であることを特定されないよう、TB3にとっては次のトランポリンホップであると認識させる(このあたりは従来のLNのオニオンルーティングの仕組みを踏襲している)。そのため、trampoline_onion_packetもトランポリンノードが使用されるトランポリンノードの数を推測できないように固定サイズになっている。

④ 続いてアリスは、最初のトランポリンノードTA1までの経路を計算する。この経路をアリス -> H1 -> H2 -> TA1とする。

⑤続いて、アリスは④の経路の支払いをするため、onion_packetを作成する。このonion_packethop_payloadはH1、H2、TA1用の3つのペイロードをセットする。最後のTA1用のhop_payloadには③で作成したtrampoline_onion_packetがセットされる。※ ただ、H2はその内容がtrampoline_onion_packetであることを知ること無く、他のノードと同様onion_packetとして転送する。

⑥ H1, H2を経由してTA1は受信したonion_packetからtrampoline_onion_packetを見つけ、トランポリンペイメントであることを認識する。そしてtrampoline_onion_packetから次のトランポリンホップTA2への経路を計算する。この経路をTA1 -> H3 -> H4 -> TA2とする。

⑦ TA1はTA2までの支払いを転送するonion_packetを作成する。このonion_packethop_payloadはH1、H2、TA1用の3つのペイロードをセットする。最後のTA2用のhop_payloadにはTA1が受信したtrampoline_onion_packetのTA1分を剥がしたものがセットされる。

⑧ H3, H4を経由してTA2はonion_packetからtrampoline_onion_packetを見つけ、トランポリンペイメントであることを認識する。そしてtrampoline_onion_packetから次のトランポリンホップがTB3であることを認識する。ここでTA2とTB3は直接チャネルを開いているので、T3へ支払いを転送するonion_packetを作成する。このonion_packethop_payloadには受信したtrampoline_onion_packetからTA2分の層が剥がされたものがセットされる。※ TA2→TB3間は直接チャネルを開いているのでルーティングコストはかからない。

⑨ TB3は受信したonion_packetからtrampoline_onion_packetを見つけ、トランポリンペイメントであることを認識する。そしてtrampoline_onion_packetから次のトランポリンホップボブへの経路を計算する。この経路をTB3 -> H5 -> ボブとする。最後のボブ用のhop_payloadにはTB3が受信したtrampoline_onion_packetのTB3分を剥がしたものがセットされる。 ※この時TB3はボブが受信者であることが分からないので、あくまで次のトランポリンホップであると認識している。

⑩ H5を経由してボブは、onion_packetからtrampoline_onion_packetを見つけ、トランポリンペイメントであることを認識する。但し、hmacの値が0x00...00なので自身が受信者であると認識する。また、最後の

以上のように、制限デバイスはトランポリンノードに途中の経路計算を代替させ、送信者、受信者の情報を従来のLNの支払いと変わらない匿名性を持って支払いを行う。図にまとめると↓のような感じ。

f:id:techmedia-think:20190731134818p:plain
トランポリンペイメントフロー

受信者がトランポリンペイメントをサポートしないケース

上記はアリスとボブ両者がトランポリンペイメントをサポートしているケースだったけど、ボブがトランポリンペイメントをサポートしない場合も途中までトランポリンペイメントを利用することができる。

アリスがtrampoline_hop_payloadのリストを構成する際、最後のトランポリンノード(ボブではない)のtrampoline_hop_payloadにだけ以下のrecipient_infoTLVパケットを含めるようにする。

  1. タイプ:recipient_info
  2. データ:
    • [1 : 0x0a] (type)
    • [1 : 0x01] (length)
    • [1 : 0x00] (option_trampoline_routing)

受信したパケットに↑が含まれていた場合、そのトランポリンノードは自身が最後のトランポリンノードであると認識し、最後のホップを標準のオニオン支払いに変換して送信してもらう。

こうすることでボブがトランポリンペイメントをサポートしていなくても送金できるが、この場合、最後のトランポリンノードに受信者の身元と送金額が分かってしまうというプライベー上のデメリットが発生する。プライバシーを確保したい場合は、トランポリンペイメントをサポートするか、受信者が身元を隠すために別途ランデブールーティングなど利用する他ない。

以上が、現在提案されているトランポリンペイメントの仕組み。まだ提案中の仕様なので、今後変更される可能性はある。

※ トランポリンペイメントで新しく導入されるメッセージの具体的なデータ構造についてはプルリクの提案内容を参照。↓は参考までに、プルリクを和訳したもの(こういう機能単位のドキュメントがあるのいいよね。BOLTの各章に分散して書かれると機能の全体像が掴みづらいので、こういうBIPみたいな方が機能を把握しやすい)。

トランポリンペイメントの提案の和訳 · GitHub

Tor v3 hidden service等128bitより大きなアドレスをサポートするための新しいaddrv2メッセージを定義したBIP-155

Bitcoinのノードは、接続しているリモートピアにgetaddrメッセージを送信すると、リモートピアが知っているノード情報をaddrメッセージで返してくれ、addrメッセージによって、ネットワーク上の分散ピアが発見できる。

このaddrメッセージでは、各ノードのネットワークアドレスを128 bitのIPアドレスとして表現している。ただ、最近Tor v3 hidden serviceなどのアドレスはこの範囲に収まらないアドレスも出てきており、I2Pなどより多様なネットワークの接続をサポートするため、128 bitよりも大きなアドレス表現をサポートできる新しいaddrメッセージとしてaddrv2メッセージがBIP-155として提案されている↓

https://github.com/bitcoin/bips/blob/master/bip-0155.mediawiki

以下、BIPの意訳↓

イントロダクション

概要

このドキュメントはP2Pネットワークにおいてより長いアドレスをゴシップするための新しいP2Pメッセージを提案する。これは、新世代のオニオンアドレスやI2Pおよび現在のaddrメッセージの128 bitに収まらないエンドポイントアドレスを持つ可能性がある他のネットワークをサポートするのに必要になる。

動機

TorのV3 Hidden Serviceバージョン0.3.2.9以降のTorの安定版リリースの一部だ。これは以前のHidden Serviceと比較してさまざまな利点を持っているが、その中でも暗号化とプライバシーの利点が大きい。ただ、これらは256 bitのアドレスを持っているため、OnionCatのIPv6アドレスにオニオンアドレスをカプセル化する現在のaddrメッセージには収まらない。

I2Pなどの他のトランスポート層プロトコルは、常により長いアドレスを使用してきた。このBIPの変更により、そのようなアドレスをP2Pネットワークでゴシップすることが可能になり、他のピアがそれらに接続できるようになる。

仕様

addrv2メッセージはpchCommand == "addrv2"のメッセージとして定義され、P2Pメッセージの標準エンコーディングシリアライズされる。フォーマットは現在のaddrメッセージと似ているが、16バイト固定のIPv6アドレスがネットワークIDと可変長アドレスに置き換えられ、timeservicesのフォーマットがVARINT形式に変更されている点が異なる。

これはメッセージに以下の構造のシリアライズされたstd::vectorが含まれること意味する。

タイプ 名前 定義
VARINT(unsigned) time このノードが最後にネットワークに接続していたと思われる時刻。最大64 bit幅のUNIXタイムスタンプ。
VARINT(unsigned) services 64bit幅のサービスビットフィールド
uint8_t networkID ネットワーク識別子。どのネットワークに対応するか示す8 bitの値。
std::vector<uint8_t> addr ネットワークアドレス。解釈はnetwork IDに依存する。
uint16_t port ネットワークポート。ネットワークに無関係の場合は0でなければならない。

1つのメッセージに最大1,000個のアドレスを含めることができる。クライアントはそれ以上のアドレスを含むメッセージは拒否すべきだ。

フィールドaddrは可変長で、最大32バイト(256 bit)。クライアントはそれより長いアドレスは拒否すべきだ。

予約済みのnetwork IDのリストは以下のとおり。

Network ID Enumeration アドレス長(バイト) 定義
0x01 IPV4 4 IPv4アドレス
0x02 IPV6 16 IPv6アドレス
0x03 TORV2 10 Tor v2 hidden serviceアドレス
0x04 TORV3 32 Tor v3 hidden serviceアドレス
0x05 I2P 32 I2Pオーバーレイネットワークアドレス
0x06 CJDNS 16 Cjdnsオーバーレイネットワークアドレス

将来の拡張を可能にするため、クライアントは知らないアドレスタイプを無視しなければならない。クライアントは知らないアドレスフォーマットを保存しゴシップするかもしれない。新しいnetwork IDの番号を追加する場合、新しいBIPドキュメントで予約されなければならない。

クライアントは特定のアドレスに対して、この表に記載されている長さと異なる長さのアドレスがあった場合、そのアドレスに意味がないので拒否すべきだ。

さまざなネットワークで使用されるアドレスエンコーディングについてはAppendix参照。

互換性

ピアが特定のプロトコルバージョン(もしくはそれ以降)である場合のみ、addrv2メッセージを送信する。

//! このバージョン以降、addrv2メッセージを使ったゴシップが可能
static const int GOSSIP_ADDRV2_VERSION = 70016;

旧ピアは新しく導入されたアドレスタイプを持つアドレスを無視し、従来のaddrメッセージを送り続ける。

参照実装

予定されているがまだ記載されていない。

Appendix A: Tor v2 アドレスエンコーディング

新しいメッセージはTORV2用の別のネットワークIDを導入する。

クライアントはアドレスフィールドに80 bitのhidden service IDを入れて、このネットワークIDを持つ、Tor hidden serviceアドレスを送信しなければならない。これは従来のaddrメッセージの表現と同じだが、OnionCatのラッピングの先頭6バイトが除かれている。

クライアントはもしIPV6ネットワークIDでこれらが送られてきた場合、受信時にOnionCat(fd87:d87e:eb43::/48)アドレスを無視する必要がある。

Appendix B: Tor v3アドレスエンコーディング

仕様によると、次世代の.onionアドレスは以下のようにエンコードされる。

onion_address = base32(公開鍵 | チェックサム | バージョン) + ".onion"
 CHECKSUM = H(".onion checksum" | 公開鍵 | バージョン)[:2]

 where:
   - 公開鍵はhidden serviceの32バイトのed25519マスター公開鍵
   - VERSIONは1バイトのバージョンフィールド(デフォルト値は'\x03')
   - ".onion checksum" は固定文字列
   - チェックサムはonion_addressに挿入される前に2バイトにトランケートされる

Tor v3アドレスはアドレスフィールドの32バイトの公開鍵と一緒にTORV3ネットワークIDと共に送信されなければならない。v3アドレスの場合バージョンは常に\x03になるので、これで十分オニオンアドレスを再構築できる。

Appendix C: I2Pアドレスエンコーディング

Torと同様、I2Pのネーミングはbase32エンコードされたアドレスフォーマットが使われる。

I2Pは52文字(256 bit)を使って完全なSHA-256を表現し、その後に.b32.i2pが続く。

I2Pアドレスは、アドレスフィールドとしてデコードされたSHA256ハッシュと一緒に、I2PネットワークIDと共に送信されなければならない。

Appendix D: Cjdnsアドレスエンコーディング

Cjdnsアドレスはfc00::/8範囲内のシンプルなIPv6アドレスで、CJDNSネットワークIDと共に送信されなければならない。

スマートコントラクト用の高水準言語BitMLを利用した安全なBitcoinベースのスマートコントラクト開発

Scaling Bitcoin 2019のスケジュールが公開されたので、予習シリーズを開始!

第一弾は「Developing secure Bitcoin contracts with BitML」のペーパーの内容↓

https://arxiv.org/pdf/1905.07639.pdf

スマートコントラクトの開発用ツールはEthereum方面は充実してるけど、Bitcoinに関してはほとんど無い。まぁ単純な決済をやマルチシグくらいであれば基本的に構成するコントラクトのスクリプトの型が決まっているため、一度スクリプトを構成してしまえば後はパラメータを変更するだけというのもあるかもしれないけど、もっと複雑な金融サービスなどを構成しようとするとコントラクトの開発環境および形式証明などを含むその検証環境は重要だ。特に、現在提案されているOP_SECURETHEBAGなどでCovenantsを実装できる=有限状態マシンを実装できるようになると、その必要性は一層増す。

BitcoinでもPieter WuilleがMiniscriptというBitcoin Scriptを対象にしたDSLを発表したが、まだ正式にBIP化および仕様化はされていない。

↑のホワイトペーパーでは、Bitcoinのスマートコントラクトを開発および検証するために作ったBitMLベースのツールチェーンが紹介されている。

BitML

BitML(Bitcoin Modeling Language)はBitcoinのスマートコントラクト用のDSLBitcoinトランザクションコンパイルされる(そういう意味だとMiniscriptと同じレイヤーのプロダクト)。

https://eprint.iacr.org/2018/122.pdf

このツールチェーンは以下で構成される。

セットアップ

IDEはDrRacketというSchemeから派生したプログラミング言語Racketの開発環境を使うみたいで、以下で一緒にインストールされる。

$ git clone https://github.com/bitml-lang/bitml-compiler.git
$ cd bitml-compiler
$./install.sh
...

インストールが完了すると、

$ drracket

を実行するとIDEが起動する↓ので、フィアルの先頭に#lang bitmlを宣言し、BitMLを記述する。

f:id:techmedia-think:20190723133241p:plain

コントラクトの記述

BitMLのシンタックスはホワイトペーパーに記載されている↓

https://eprint.iacr.org/2018/122.pdf

例えば参加者A,BがいてAがBに BTC送金するコントラクトは以下のように記述できる。

#lang bitml

; コントラクトの参加者を宣言
(participant "A" "029c5f6f5ef0095f547799cb7861488b9f4282140d59a6289fbc90c70209c1cced")
(participant "B" "0316589526daa876ef27937e48176da08fc95eaef7315fa20a07114d5fb8866553")

(debug-mode)

; Aが1BTCをBに送る場合、Aはまず1BTC所有するトランザクションを宣言する。
; tx:の後がシリアライズしたトランザクションで、その後の@1がアウトプットのインデックス
(define (txA) "tx:02000000000102f28b8ec15a48abd9cda80d1c770ff9770dc0c549ddb1b8013b9e50a8799614aa000000001716001412a88716720982b693ab2bd2a2fcd4d98bdd2485feffffff08d59c3aeafd6003e6e099adde64f17d6ec7950619c22b50466281afa782e9d4000000001716001433845a8590dbf145b52bdd777103d1ddfdaa9cedfeffffff022fac1f000000000017a914e9f772646a0b6174c936806dab1b882e750ac04a8740420f00000000001976a914ded135b86a7ff97aece531c8b97dc8a3cb3ddc7488ac02473044022060135384eafe9a8021e8b8c46da20e7cd5713d581c3f79b1da3d2f7860a1bfed02206ca1ac1616d7ab778bcbb235b4b24286c2181ec171b8cadeaa9ee5f4f78fd330012102d5f8f263a81427330e7f26ba5832a2cd01e960bf145be2101bc0b6bb0fde8c2d0247304402200e02da2228774b47ff03a5a7c1bf1d070d0cec6cd9a08d6862e1855ba33dfb9f0220011511f10aaefbf402b2944b6a877c1ff9890a7fc3e266bbb74318b4540c555d012103ef2a573fbd46356dcbdbedcecc9aa25dcb500512e2be394297475ed157a9cfc6bdb51600@1")

; Aが1BTC送金するコントラクト
(contract
 (pre (deposit "A" 0.001 (ref (txA))))
 (withdraw "B"))

他にも、AがBTCをデポジットし、チェーンのブロック高が500000を超えるとBが引き出せるが、510000を超えるまでにBが引き出さない場合、Aがコインを引き出すことができるというコントラクトは以下のように書ける。

...

; ブロック高の宣言
(define (t) 500000)
(define (t1) 510000)

(contract
 (pre (deposit "A" 0.001 (ref (txA))))

 (choice
        (after (ref (t)) (withdraw "B"))
        (after (ref (t1)) (withdraw "A"))))

コントラクトのコンパイル

DrRacketのエディタの右上の実行ボタンを押すと、以下のようにBalzacで表現されるコントラクトのトランザクションを含むコンパイル結果が表示される。Balzacというのは、A formal model of Bitcoin transactionsの形式モデルに基いたBitcoinトランザクションの抽象化層とのこと。

f:id:techmedia-think:20190723141139p:plain
BitMLのコンパイル結果

さらにBalzacのコードから標準的なBitcoinトランザクションに変換する必要がある。この変換は、Balzac Webエディタを使ってできる。

試しに↑のDrRacketが吐いたコードをコピペしてEvaluateすると、Tinitの署名が提供できないのでワーニングになる。これは、

const privkeyA = key:cUnBMKCcvtpuVcfWajJBEF9uQaeNJmcRM6Vasw1vj3ZkiaoAGEuH

を宣言して、以下のように署名生成に使うようにすればいい。

tx:02000000000101adbcf28818d2556fb85ce7f6068775a6a4fd4befe650d3d7d120b609e5af1e920100000017160014a5d12120913a41cdd3be9ef88b60838b8c0db3b7feffffff028ac710000000000017a914664180e7578033f9cef5bc82b3112855f775f02587a0860100000000001976a914ded135b86a7ff97aece531c8b97dc8a3cb3ddc7488ac024730440220290f9526ed5e22d4ae72c66702f5f70dff4c5ea72445cd20112782da1986332e02201d872a0a53fa13b34a9273776dfcd0ea7385e449fec1e95263bdde96fda084e10121021215eb7fabd9bb0c1f1441bf35bade28d9e64dc798a666eb4eaf47e134a7
 4b446d191700@1:sig(privkeyA)

さらに最終行に

eval Tinit

を追加してEvaluateすると、Tinitの変換結果=BitcoinトランザクションのRAWフォーマットが出力される。

Tinit
Transaction{1e5dfc19ba826704611bfa844e3fb4fbdc00f5f4ef79dc87424913197e2437f9
weight: 756 wu, 189 bytes
version 2
purpose: UNKNOWN
   in   PUSHDATA(71)[3044022017446454e5719b15716028375b83e2bd5e504b32f3196e3de18c5dc652bc2c120220558dc80643ce0c8b5d6ca80fccd771c54c9b8d3352f4ceec58e27517474a495d01] PUSHDATA(33)[0339bd7fade9167e09681d68c5fc80b72166fe55bbb84211fd12bde1d57247fbe1]
        P2PKH addr:n1q6vo5VabL1BpqVKyHjvh4vaHrAq5NcYR  outpoint:2e647d8566f00a08d276488db4f4e2d9f82dd82ef161c2078963d8deb2965e35:1
   out  HASH160 PUSHDATA(20)[0711461f84331f5de08e04f9d5e36307b52eb6c7] EQUAL  0.001 BTC
        P2SH addr:2MstbQqerozS9oHt8cpL7rZjKcnVchSxEiU
}
0200000001355e96b2ded8638907c261f12ed82df8d9e2f4b48d4876d2080af066857d642e010000006a473044022017446454e5719b15716028375b83e2bd5e504b32f3196e3de18c5dc652bc2c120220558dc80643ce0c8b5d6ca80fccd771c54c9b8d3352f4ceec58e27517474a495d01210339bd7fade9167e09681d68c5fc80b72166fe55bbb84211fd12bde1d57247fbe1ffffffff01a08601000000000017a9140711461f84331f5de08e04f9d5e36307b52eb6c78700000000

コントラクトの検証

続いて、BitMLコントラクトの検証について。現在以下の検証をサポートしている。

流動性の検証

コントラクトの実行にあたって、必ず資金がいずれかの参加者に渡ることが重要で、誰も入手できない条件があると資金が永遠に凍結されてしまう。

コントラクトの条件によらず、全てのパータンを考慮した上で、資金の流動性をチェックしたい場合、コントラクトの最後に(check-liquid)を追加する。

(contract
...
 (check-liquid))

もし、コインの流動性が損なわれる場合、出力ボックスにその旨表示される。

その他、以下のように参加者の戦略毎に流動性のチェックをすることもできる。

(contract
...
  (choice
   (reveal (a) (withdraw "A"))
   (auth "B" (after 700000  (withdraw "B"))))

  (check-liquid
    (strategy "A" (do-reveal a)))

  (check-liquid
    (strategy "B" (do-auth (auth "B" (after 700000 (withdraw "B")))))))
LTL特性の検証

BitMLでは流動性の検証以外に、(check-query "query")を使って、コントラクトに合わせてカスタマイズされたカスタムLTLプロパティを検証できる。

例えば時間制限のついたコミットメントの場合、以下のような検証ができる。

  • Aがシークレットを明らかにした場合、Aのデポジットを取り戻すというチェックは以下のように書ける。
    (check-query "[]<> (a revealed => A has-deposit>= 100000000 satoshi)")
  • Bがシークレットを知る or Bがデポジットの資金を得るという条件のチェックは、以下のように書ける。 (check-query "[]<> (a revealed \/ B has-deposit>= 100000000 satoshi)"))

課題

今までBitcoin Scriptで作るスマートコントラクト用の開発ツールや形式証明ツールなどはほとんどなかったので、このレベルのプロダクトが出てきてるのは素晴らしい。ただ、現在どんなコントラクトでも書けるという訳ではなく、以下のような制約があるようだ。

  • BitMLは完全にBitcoinに対応しているわけではなく、Bitcoin Scriptを直に書けば書けるコントラクトがBitMLでは書けないものがある。
    • サポートする署名タイプはSIGHASH_ALLのみで、その他の署名タイプはサポートできていない。
    • オフチェーンのやりとりは、シークレットの公開と承認のみを限定的にサポート。
    • 動的に定義される参加者のセット(クラウドファウンディング)や、無制限の反復(マイクロペイメントチャネル)などは現状BitMLで表現できない。
  • 実際に使ってみると、Balzacの知識も必要となるので、まだお手軽開発環境という状態ではなさげ。ある程度熟知して、使いこなす必要がある。

さらに、Covenantsなどが有効になるとトランザクションを跨いだ状態マシンの管理などが求められるようになると思うので、今後の発展に期待したいところ。

BitMLについては以下のサイトが参考になる。

BitML Toolchain — BitML 2019-07-23_054007 documentation

以下、ホワイトペーパーの意訳↓

Abstract

Bitcoinで実行できるスマートコントラクトを開発および検証するためのツールチェーンを紹介する。このツールチェーンは、計算上健全なBitcoinに組み込まれたスマートコントラクト用の最近のDSLであるBitMLをベースにしている。このツールチェーンは自動的にコントラクトの関係性を検証し、資金が永久にコントラクト内で凍結されたままになるようなことがないことを保証する。BitMLコントラクトを標準のBitcoinトランザクションに変換するためのコンパイラも提供される。コントラクトの実行はこれらのトランザクションブロックチェーンに追加することに相当する。我々は代表的なコントラクトのベンチマークを通して、このツールチェーンを評価する。

1. イントロダクション

過去5年間で、Bitcoinを悪用してスマートコントラクトを実行する方法、つまり事前に合意された複雑なルールに従って暗号通貨を交換することを可能にするコンピュータープロトコルについて多くの優れた研究が行われてきた。これらの研究によって確認された多種多様なユースケースにも関わらず、Bitcoinコントラクトの開発を容易にするためのツールサポートはまだ提供されていない。現在、このタスクでは標準的な暗号プリミティブを使用する他に、Bitcoinブロックチェーン上のトランザクションを読み取り、追加できる複雑なプロトコルを考案する必要がある。新しいプロトコルを作るにあたっては、その正当性と安全性を確立するためにかなりの努力を必要とする。これはエラーを起こしやすいタスクで、通常手動で実行され、一部のコーナーケースを見逃す可能性がある。これらのプロトコルで使われるトランザクションの作成も同様に面倒で、十分にドキュメント化されていないBitcoinの機能(スタックベースのスクリプト言語など)と戦う必要がある。

本稿では、Bitcoinへの計算的に健全な埋め込みおよび関連するトレース特性の健全で完全な検証技術を特徴とするスマートコントラクト用の最近の高水準言語であるBitMLについて考察する。BitMLはPrinciples of Security and TrustFun with Bitcoin Smart Contractsに記載されているスマートコントラクトの多くを表現し、適切なトランザクションブロックチェーンに追加することでそれらを実行する。埋め込みの計算上の健全性は、たとえ敵対者が存在したとしても、BitMLのセマンティクスのレベルでセキュリティ特性がBitcoinトランザクションレベルで維持されることを保証する。まだコントラクトを開発しBitcoinブロックチェーンにデプロイするためのツールは存在しないため、BitMLは理論上の限界にある。

貢献

この研究では、BitMLコントラクトを書き、検証し、それらをBitcoinデプロイするためのツールチェーンを開発する。より具体的には主な貢献は次のようになる:

  1. BitMLはRacketに埋め込む。Racketは、BitMLコントラクトをDrRacket IDE内でプログラミングできるようにするもの。
  2. BitMLコントラクトの任意のLTL特性をチェックできるセキュリティアナライザー。特に分析は流動性、つまりコントラクトないの資金が永久に凍結されたままではないことを要求するスマートコントラクトのランドマーク特性を決定することができる。
  3. BitMLから標準的なBitcoinトランザクションへのコンパイラ。計算上の健全性の結果は、コンパイルされたコントラクトに対する攻撃もBitMLレベルで観察可能であることを保証する。したがって、セキュリティアナライザーによって検証された特性は、コンパイルされたコントラクトにも当てはまる。
  4. ツールチェーンを評価するためのベンチマークとして使用するBitMLコントラクトのコレクション。コレクションには、Bitcoin用に開発された最も複雑なコントラクト、金融サービス、オークション、期限付きコミットメント、宝くじ、その他の様々なギャンブルゲームなどの一部が含まれている。ベンチマークを使用して、スマートコントラクトプラットフォームとしてのBitcoinの表現力と限界について説明する。

f:id:techmedia-think:20190722141607p:plain
Figure 1:ツールチェーンのアーキテクチャ

ツールチェーンのアーキテクチャをFigure 1に示す。開発のワークフローは以下の通り。

  1. BitMLコントラクトを書き、必要なプロパティを指定する。オプションで参加者の戦略にいくつかの制約をし正直な参加者の行動を部分的に定義する。
  2. セキュリティアナライザーを通して、コントラクトが要求された特性を満たすことを検証する。
  3. Bitcoinトランザクションコンパイルする。
  4. 選択された戦略に従ってトランザクションBitcoinブロックチェーンに追加することで、コントラクトを実行する。

最後のステップは、拡張やカスタマイズを必要とせずBitcoinのmainnet上で実行できることに注意すること。

ツールチェーンの全てのコンポーネントオープンソースであり、ベンチマークコントラクトもである。チュートリアルはオンラインで利用可能で、そこにはBitcoinのtestnet上の我々の実行への参照も含む。

2. Bitcoin Contractの設計

BitMLのコントラクトでは、2人以上の参加者が特定のロジックに従って彼らのBitcoin(B)を交換できる。コントラクトは

  • 参加者ががコントラクトを規定するために満たさなければならない前提条件
  • コントラクトの実行ロジックを指定するプロセス

という2つの部分で構成される。ここではBitMLの文法やセマンティクスを提供するのではなく、単純だがパラダイム的な例である相互のタイミングコミットメントコントラクトを通してそれを説明する。このコントラクトには2人の参加者(AとB)がそれぞれ1つのシークレットを選択し、一定量の暗号通貨(1Bなど)のデポジットを含む。コントラクトの目標は、各参加者は他の参加者のシークレットを知るか、そうでなければ他の三社かのデポジットを保証として受け取ることだ。コントラクトは参加者に彼らのシークレットを明らかにするための時間を与える。参加者がそれに間に合って、そのシークレットを明らかにした場合、その参加者自分のデポジットを取り戻すことができ、そうでなければ、時間切れになった後、他の参加者はそのデポジットを引き出すことができる。

我々のツールでは、このコントラクトを以下のように指定する。

f:id:techmedia-think:20190722143537p:plain

最初の2行は、参加者の公開鍵を指定して参加者名のエイリアスを作成する。コントラクトの前提条件は、前編にあり、各参加者はトランザクションアウトプットの識別子とシークレットのハッシュを指定しなければならない。トランザクションアウトプットは未使用でなければならず、必要な1Bを持ち、参加者の秘密鍵を使って償還可能でなければならない。ハッシュはコントラクトの実行中に使用される。参加者が選択したシークレットであると主張する値を提供した際、この値のハッシュは前提条件のハッシュと等しくなければならない。

コントラクトロジックは、前提条件の後に指定される。トップレベルの選択では、2つの代替ブランチを定義する。Aがシークレットを明らかにした場合のみ最初のブランチを選択することができる。これが実行される場合、コントラクトは最も内側のものが続く。2つめのブランチは、高さ100,000のブロックとして指定されたタイムアウト後のみ選択でき、その場合Bはコントラクト内の資金すべて(すなわち2B)を引き出すことができる。そのため、Aはデポジットした資金を失うのを避けるため、間に合うようにシークレットを明らかにするよう動機づけられる。同様に最も内側の選択は高さ100,050ブロックまでにBにシークレットを明らかにする動機づけをするのに使われる。Bがシークレットを明らかにした場合、分岐したサブコントラクトが実行され、これによりコントラクトの残高がそれぞれ1Bの2つに分割され、参加者は自分のデポジットを引き出すことができる。

この言語はBitML構文構造をRacketコードに書き換えるのに使用されるRacketマクロシステムを利用して定義されている。このアプローチはRacket言語のエコシステムから利益を得て、我々がDrRacket IDEでBitMLコントラクトを書けるようにする。実際我々のツールチェーンはDrRacket IDEの中に、コントラクトのエディター、セキュリティアナライザーおよびBitMLコンパイラを統合している。RacketでのBitMLの実装は言語を実際に使えるようにするため理想的なバージョンのBitMLを拡張したものだ。例えば、自動的にコンパイラによって得られた全てのトランザクションにスプレッドするタイプ手数料の特別なデポジットなどを導入している。またコントラクトの正しい執行を妨げる可能性があるいくつかのエラーに対して静的チェックも実装している。例えば、同じハッシュを持つシークレットをコミットしたり、トランザクションアウトプットの二重使用など。

BitMLコントラクトの検証

このツールは、さまざまな形態の流動性を検証し、コントラクト内で資金(もしくは一定額までの資金)が永久に凍結されることが内容にする。さらに、ツールは任意のLTL式を検証することができ、この状態述語は、例えば、参加者に寄って所有される資金、提供される認可および明らかにされたシークレットを指定することができる。デフォルトでは、ツールは書く参加者の考えられる全ての動作に対して必要なプロパティを検証する。例えば、aの公開が含まれるコントラクトの場合、検証者はシークレットが明らかになる場合と明らかにならなかった場合の両方を考慮する。どちらのケースを考慮しても、認可は同様に処理される。しかし、ほとんどの場合、参加者は参加者は自分に割り当てられた行動に関してコントラクトを検証しようとし、他の参加者の行動を仮定しない(他の参加者が信頼できるとみなされない場合、彼らにとっても行動を修正する意味がでる)。例えば、参加者Aは参加者Bがシークレットを明らかにした後でのみ与えられたブランチを実行する許可を与えたいと思う。このツールを使うと、参加者の行動を制限し、シークレットが明らかにされ承認が提供される条件を指定できる。引出しや分割のように誰もが実行できる行動を制限することはできない。

例えば、参加者が選択した戦略がどうであれ、相互時限コントラクトが流動的であることを検証できる。以下の理由からcheck-liquidクエリは正しくtrueと回答する:

  • Aがシークレットを明かさなければ、(ブロック高100000以降)誰もがコントラクトの全ての残高をBに転送する引出しを実行できる。
  • Aがシークレットを公開し、Bがシークレットを公開しなかった場合、(ブロック100050以降)誰もがコントラクト内の残高をAに転送する引出しを実行できる。
  • AとB両者がシークレットを公開した場合、誰もがコントラクトの残高を半分ずつAとBに転送する分割を実行できる。

もし、我々が16行目のafterブランチを削除すると、コントラクトの流動性は無くなる。しかし、Aの戦略がシークレットを明らかにする場合、それは流動的になる。これをcheck-liquid (strategy "A" (do-reveal a))というクエリを介して成立することを検証できる。AがBがシークレットを明らかにした後でシークレットを明らかにすることを選択した場合、つまり、Aの戦略が "A" (do-reveal a) if ("B" (do-reveal b))の場合流動性は再び失われる。

流動性に加えて、check-queryコマンドを使ってコントラクトの特定のLTL特性を確認できる。例えば、Aがシークレットを明らかにした後、Aは少なくとも自分の1Bのデポジットを取り戻すことを検証することができる。LTLではこの特性は次の式のように定式化される。

[](a revealed => <>A has-deposit>= 100000000 satoshi)

またAがシークレットを明らかにした場合、最終的にBがシークレットを明らかにするか、AがBのデポジットを入手するかも検証する。そのLTLクエリは以下の通り。

[](a revealed =>
<>(b revealed \/ A has-deposit>= 200000000 satoshi))

我々の検証技術はBitMLコントラクトの状態空間をmodel-checkingすることに基づいている。この状態空間は無限であるため、model-checkerを実行する前に抽象化を利用して有限状態のものに削減する。この抽象化は、BitMLの具体的なセマンティクスの無限性の3つのソース、時間の経過、コントラクトの宣伝/規定、コントラクト外のBitcoinの転送を解決する。有限状態のシステムを得るため抽象化は、

  1. 有限個の時間間隔で時間を商する。
  2. 新しいコントラクトの宣伝を無効にする。
  3. コントラクト外の操作を制限し、資金をコントラクトに移転し、それらを破壊する。

この抽象化は具体的なBitMLのセマンティクスと厳密に対応する。つまり、分析中のコントラクトの具体的な各ステップは抽象ステップによって模倣され、逆もまた同様。

我々のツールは、書き換えロジックに基づくmodel-checkingフレームワークであるMaudeの抽象BitMLセマンティクスを実装している。Maudeはこの目的にとって便利だ。BitML用語間の構造的等価性を表現するための等式論理と、BitMLの抽象セマンティクスをエンコードするための条件付き書き換えルールを使用する。このような方法で、BitMLの実行可能な抽象セマンティクスを得る。BitMLコントラクトがMaudeで翻訳されると、MaudeのLTL model-checkerでユーザーが指定したセンラ訳の元でセキュリティ特性を検証する。さまざまな形態の流動性もまた対応するLTLの計算式に変換される。BitMLコンパイラの計算上の健全性は、Bitcoinコントラクトを実行する際にmodel checkerによって検証された特性が確実に保持されることを保証する。

4. BitMLをBitcoinコンパイル

我々のコンパイラは2つのフェーズで動作する。最初にBitMLコントラクトをA formal model of Bitcoin transactionsの形式モデルに基づくBitcoinトランザクションの抽象化層であるBalzacに変換する。それからBalzacトランザクションを標準的なBitcoinトランザクションに変換する。

BitMLからBalzacへのコンパイラは、BitMLアルゴリズムを実装し、それをトランザクション手数料で拡張する。特に、コンパイラは各トランザクションブロックチェーンで公開できるだけの十分な手数料が含まれていることを保証する。

BalzacからBitcoinへのコンパイラは、標準的なBitcoinトランザクションを生成する。非標準トランザクションBitcoinネットワークおいて破棄されるのでこれは重要だ。この目的のためBalzacはP2PKHもしくはP2SH形式のアウトプットスクリプトを生成する。P2PKHは署名検証をエンコードするのに使われ(引出しによってデポジットを償還する)、一方P2SHは複雑な引出し条件のために使われる(公開されたシークレットがコミットされたハッシュと一致するかチェックするなど)。Bitcoinは標準スクリプトでプッシュされた全ての値が520バイト以内に収まることを要求するので、コンパイラは生成されたスクリプトに対してこれを満たしているかチェックする。BalzacシリアライズされたRAWトランザクションを出力し、これはそのままBitcoinネットワークにブロードキャストできる。

5. 評価

ツールチェーンを評価するために、金融コントラクト、オークション、宝くじ、ギャンブルゲームなど代表的なユースケースベンチマークを使用する。ベンチマークの各コントラクトについて、関係する参加者の数N、コンパイラによって取得されるトランザクションの数Tおよび流動性をチェックするための検証時間Vを表1に示す。

f:id:techmedia-think:20190722172513p:plain
表1:BitMLツールチェーンのベンチマーク

参加者の戦略は、流動性を確保するのに必要な場合のみ制約される。ほとんどの場合、まったく制約を課さない。シークレットに関する述語を含むコントラクトについては、原則として、可能性のある全てのシークレットの選択に対して、流動性をチェックする必要があるだろう。検証を実行可能にするため、各コントラクトは有限の述語セットのみをチェックするため、無限のシークレットの選択をリージョンの有限セットに分割し、各リージョンから1つの選択をサンプリングする。このように、流動性のチェックは有限回実行され、検証者がコントラクトの全ての到達可能な状態を確実に調査するようにする。例えば4人用の宝くじでは、34リージョン探索し、流動性を検証するのに67時間かかる。

我々のツールの性能を比較できる唯一の研究はModeling Bitcoin Contracts by Timed Automataで、これはBitcoinコントラクトをUppaalでモデル化し、Timed Automataに基づくモデルチェックフレームワークである。これでモデル化された最も複雑なコントラクトは、2人の参加者がいる相互時限コミットメントだ。これをUppaalで検証すると30秒要するのに対し、我々のツールは100ms未満で同じ特性を検証する。このスピードアップはより高い抽象化レベルのBitMLによるもので、より低いレベルのBitcoinトランザクションで動作する。

Bitcoinは評価スタックにプッシュされる各値のサイズに520バイトの制限があるため、コントラクトを開発する際に直面した主な困難の1つは、複雑なBitMLを仕様をBitcoinコンパイルできないことだ。場合に寄っては、そのコンパイルが520バイト制約を遵守するようにBitMLコントラクトを縮小することができた。例えば、520バイトの制約に簡単に違反する一般的なパターンは次のようなもの:

( choice ( revealif (b ) ( pred ( p0 ) ) ( C0 ) )
         ( revealif (b ) ( pred ( p1 ) ) ( C1 ) )
         ( after T ( C2 )) )

choiceは、その選択肢の3つのブランチに対応する3つの論理条件の分離をredeem scriptがエンコードするトランザクションコンパイルされる。述語p0とp1およびコントラクトの参加者数に応じて、このスクリプtおは520バイトの制約に違反する可能性がある。これを回避するには、以下のように書き換える:

( choice ( revealif (b ) ( pred ( p0 ) ) ( C0 ) )
         ( after T ( tau ( choice
                         ( revealif (b ) ( pred ( p1 ) ) ( C1 ) )
                         ( after T1 ( C2 ) )))) )

この場合、コンパイルには2つの選択肢に対応する2つのトランザクションが含まれる。これらのトランザクションスクリプトは選択肢の2つのブランチに対応する2つの論理条件の分離をエンコードする。この回避策を使用してトランザクション数を増やすという代償で4人用の宝くじを標準トランザクションにまとめることができた(587標準バージョン vs 138非標準バージョン)。同様の技術で(例えば述語の単純化など)、表1の全てのコントラクトを標準のBitcoinトランザクションにまとめることができる。

一般的に、520バイトの制約はBitcionのコントラクトの表現力を制限sるう。例えば公開鍵は33バイトなので、15個の署名を同時に検証する必要があるコントラクトは標準トランザクションとして使用できない。

6. 結論

スマートコントラクトのビジネスはEthereumやCardanoようなプラットフォームではやっているが、それらがBitcoinに追いついたことはない。主な理由の1つは、他のプラットフォームとは異なり、Bitcoinには高水準のコントラクト言語も関連する開発、検証ツールも無いということだ。表現力豊かでチューリング完全な言語でプラットフォームを使用することの欠点は、それがコントラクトをより広い攻撃面にさらす可能性があることだ。実際に、一連の言語によるEhtereumコントラクトの脆弱性は何億ドルもの損失を引き起こした。Ehtereumコントラクトの分析に関する最近の研究では、これらの脆弱性を検出するためのツールが作成されているが、それらの精度は、基底となる言語のチューリング完全性によって生じる固有の制限を受ける。対照的に本稿ではBitMLによって与えられたより単純な計算モデルを使って、健全で安全な検証技術を備えたツールチェーンを紹介した。

我々のベンチマークはBitMLで表現可能な多種多様なコントラクトを目にするが、改善の余地はある。まずBitMLは完全にBitcoinに対応していない。つまりBitcoinでは実行可能であるが、BitMLでは表現できないコントラクトが存在する。この不完全性の主な原因は次の3つだ。

  1. 関係者全員が規定する前にコンパイラによって取得された全てのトランザクションに署名する必要がある(実行時に許可用の署名のみ提供できる)。
  2. トランザクションで使われる署名タイプは全てのSIGHASH_ALLで、SIGHASH_ANYONECANPAYSIGHASH_SINGLEなどは使えない。
  3. オフチェーンのやりとりは、秘密を明らかにすることと、承認を提供することに限定される。

最初の制約は、他の人の行動に関係なく、正直な参加者が対応するBitMLコントラクトで有効になっている移動を常にBitcoinレベルで実行できるようにするために必要だ。この点に関して、BitMLは参加者が非協力的であるという標準的な仮定に従う。つまり規定後いつでも彼らは対話をやめることができる。それにも関わらず、違法行為を罰則で罰することでコントラクト内で協調を動機づけることができる。2章の期限付きコミットメントのように。上記の設計上の選択の結果として、動的に定義された参加者のセットとの契約(クラウドファウンディングなど)や、無限数の反復(マイクロペイメントチャネルなど)はBitMLでは表現できない。

BitML(およびBitcoin)の制限はさまざまな方法で克服できる。例えば、Bitcoinをそのまま使うと、上記の3の制限を緩和することが可能で、ゼロ知識オフチェーンプロトコルなどが可能になる。これは参加者がNP問題のクラスの解決策を交換するという条件付き支払いコントラクトを表現するために、プリミティブでBitMLを拡張すること可能にするだろう。同様い制限1を緩和することで、関与するすべての参加者が実行時に自分の署名を提供することを要求するサブコントラクトの動的機能を可能にするようBitMLを拡張できる。これはBitMLにおけるマイクロペイメントチャネルのモデル化を可能にするだろう。SIGHASH_ANYONECANPAYの使用と共に(2の緩和)、クラウドファウンディングコントラクトのモデリングも可能にする。以前と同様、この拡張はBitcoinを変更することなく実現できる。

BitMLの他の拡張は、Bitcoinの拡張を必要とするだろう。例えばCovenantsでは、任意の有限状態マシンを実装することが認められている。制御されたインプットmalleabilityは、宝くじなどのマルチプレイヤーギャンブルゲームにおいてトーナメントを効率的に実装するのを可能にするだろう。これは償還トランザクションが特定のセットに属しているかどうかをチェックする新しいopcodeによって達成できる。ゼロ知識証明を使った条件付き支払いは、キーペアの有効性をチェックする新しいopcodeを利用することで実現できるだろう。任意のメッセージに対して署名をチェックする新しいopcodeは、一般的で公平なマルチパーティ計算を表現することを可能にするだろう。さらに公平で堅牢なパルティパーティ計算はより複雑なトランザクションを使って実現できる。より根本的なアプローチはBitcoinスクリプト言語をより表現力豊かなものに置き換えることだ。例えば、Simplicityは有限ドメイン上で任意の関数を表現することを可能にする。

MoneroでスクリプトレスなPayment Channelを実現するためのDLSAGリング署名スキーム Part2

Part1でDLSAGの仕組みについて整理したので↓

techmedia-think.hatenablog.com

続いて、DLSAGを利用して、Payment Channel Networkを構築する際に必要な構成要素を順番に見ていく。

MoneroでPayment Channel

上記のDual-Keyアウトプットを使った払い戻しトランザクションを使ってMoneroでPayment Channelを構築する。

Dual-Keyは↑のDLSAGの提案で新しく出てきた概念で、現状のMoneroでは各アウトプットには送信先として公開鍵が1つだけ指定できるが、Dual-Keyでは2つ公開鍵が指定できるようになり、さらにタイムロックを制御するフラグtがセットされた以下のような3つの要素で構成されるようになる。

(アリスの公開鍵、ボブの公開鍵、t)

tはチェーン上のブロック高をセットでき、

  • t = 0の場合は、このアウトプットをいつでもアリスの公開鍵に対応した秘密鍵で署名すれば使用できる
  • tが0でない場合、ブロックチェーン上のブロック高がtを超えると、2つめのボブの公開鍵に対応した秘密鍵で署名して使用できるようになる

という性質を持つ。

チャネルのオープン

アリスがMoneroのDual-Key {(pk_{A,0}, pk_{A,1})}にγ XMR保持していて、ボブとの間にPayment Channelを作成したい場合、↑のDual-Keyを使ってチャネルを開く。

f:id:techmedia-think:20190716144242j:plain

アリスはγ XMRをDual-Key {(pk_{AB}, pk_{A'})}に送金するデポジットトランザクション(dtx)を作成し、ブロック高lにロックするよう設定する。

Moneroにおける2-of-2のマルチシグは、アリスとボブがそれぞれその秘密鍵のシェアを持つ公開鍵 {pk_{AB}}で実現する。この公開鍵に対応する秘密鍵 {sk_{AB}}は、アリスが持つ秘密鍵 {[sk_{AB}]_A}とボブが持つ秘密鍵 {[sk_{AB}]_B}を加算したもの {sk_{AB} = [sk_{AB}]_A + [sk_{AB}]_B}となる。つまり、コインを公開鍵 {pk_{AB}}に送金することで、両者の秘密鍵の情報がなければ署名を完成させられない=使えない2-of-2のマルチシグへのロックとなる。

こうして、ボブが {pk_{AB}}にロックされたコインの使用に協力しない場合、アリスはチェーンのブロックがlを超えると別の払い戻しトランザクションを作ること無く、自分の資金のコントロールを取り戻すことができる。一方、ボブがオフチェーンで {pk_{AB}}からコインを受け取った場合、チェーン上でブロック高lに達するまでに最も金額の高いものをオンチェーンにプットする必要がある。

このデポジットトランザクションのアウトプットを使用する方法は以下の2つ。

  • アリスとボブが協力して {pk_{AB}}に対して有効な署名を作る
  • チェーンのブロック高がlを超えたら、アリスの {pk_{A'}}に対して有効な署名を作る

このことから、このPayment Channelは以下の特性を持つ。

  • ブロック高lを超えるとアリスによる払い戻しが可能であることから、有効期間付きのPayment Channelであること。
  • 一度もオフチェーン決済をしない場合( {pk_{AB}}に対して有効なアリスの署名をボブに送っていない場合)、ブロック高lを超えるとアリスしかコインを取り扱えないので払い戻し用にトランザクションをブロードキャストする必要なく、コインはアリスの所有物となる。

オフチェーン決済

↑でセットアップしたPayment Channelを使ってオフチェーン決済をする。アリスはγ'をボブに送金するオフチェーントランザクション(otx)を作成する。このトランザクションのインプットは↑のDual-Key {(pk_{AB}, pk_{A'})}で、アウトプットはボブのDual-Keyアドレス {(pk_{B,0}, pk_{B,1})}と、お釣りγ-γ'を送るアリスのDual-Key {(pk_{A,0}, pk_{A,1})}。このトランザクションotxを有効なトランザクションにするためには、アリスとボブが協力して署名する必要がある。

が、このPayment Channelの要は、アリスだけがotxに署名し、署名のシェアとなる {[σ]_A}をボブに送る。この時点でボブはブロック高lが来る前に、署名を完成させトランザクションをブロードキャストすることでγ'を入手できる状態になる。その後は、ブロック高lが訪れるまでは、γ'より高い残高のオフチェーン決済トランザクションを受け取ることができる。

この時の署名プロセスが↓の2OF2RSSIGNプロトコル(青字の部分は除く)

f:id:techmedia-think:20190711165015p:plain
2OF2RSSIGN(pkAB, [skAB]A, [skAB]B, tx) プロトコルの定義

このプロトコルの結果、アリスとボブはそれぞれの署名 {[σ]_A} {[σ]_B}を入手するので、それを結合して最終的な署名 {σ = ([s_0]_A + [s_0]_B, s_1, ..., s_{n-1}, h_0, (J_A + J_B))}を完成させる。

署名のシェアの検証

また、署名プロトコルにおいて重要なのが、それぞれが出力する署名のシェアが正しいものかの検証だ。アリスが {[σ]_B}を受け取り、それが有効な署名σのシェアかどうか検証したい場合、 {[σ]_B}から {[s_0]_B}をピックアップし、 {([s_0] + [s_0]B)G = (R_A + R_B) - h_{n-1}pk_{AB,b}}が成立するか検証する。ここで {R_A = [s'_0]_A G} {R_B = [s'_0]_B G}である。

Channelのクローズ

Channelのクローズには2パターンある。

  • ボブが最新のotxに自分の署名 {[σ]_B}を計算し、アリスの {[σ]_A}と組み合わせて最終的な署名を完成させブロードキャストする。
  • タイムロックlを過ぎてもボブがotxをブロードキャストしない場合、アリスがdtxのDual-Keyのタイムロック側の条件を使ったトランザクションを作成、ブロードキャストし資金を取り戻す。

※ クローズ処理やオフチェーン決済を見て分かるが、どのオフチェーントランザクションをブロードキャストしたとしても、チェーン上に記録されたものが有効で、ペナルティや最新の残高の反映を強制させる仕組みがないため、これはあくまで一方向のPayment Channelっぽい。

Moneroの条件付き支払い

条件付き支払いは、ハッシュのプリイメージや離散対数問題の解を入手するなど暗号問題に対する解を提供できる場合にのみ有効になる支払いだ。この条件付き支払いはAtomic SwapやPayment Channel Networkなどで利用される。

グループ要素Y = yG、XMRの量γおよびタイムアウトtで定義される 以下のようなDiscrete-log Timelock Contract (DTLC)を考える。

  1. ボブがt日前にyG = Yとなるような値yを生成した場合、アリスはボブにγXMR支払う。
  2. tが経過するとアリスはγXMRを取り戻す。

アリスとボブの間のPayment Channelを開く際に作成したDualアドレス {(pk_AB, pk_A)}において、この条件付き支払いを行う場合、アリスとボブは条件Yで、2OF2RSSIGNCONDプロトコル(上図の青字の部分が加わる)を使ってctxに署名する。この時、 {Y = yg} {Y^* = ympk_{AB,1}}

このプロトコルの要は、アリスとボブが協力して署名を完成させるが、もう1人ボブにyを教えるユーザーがいる。これは別のコインのチェーンと交換する場合にはアリスだったり、マルチホップ決済の場合はボブより先の受領者だったりする。アリスは ([{s'_0}]_A, [sk_AB]_A)をボブは ([{s'_0}]_B, [sk_AB]_B)を、そして3人目のユーザは(y, Y)を提供する。アリスとボブがそれぞれ {[σ]_A}および {[σ]_B}を提供しても、最終的な署名を完成させるためにはtの値が必要だ。

そのため、2OF2RSSIGNCONDプロトコル実行後、ボブはアリスに自分の署名のシェア {[σ]_B}を渡し、アリスはその有効性を検証した後、自分の署名のシェア {[σ]_A}を返信する。この順の交換で、値yが明らかになっていて、ブロック高のロックlに達していない場合にのみctxが公開されることを保証する。

ボブがctxで自分のXMRを請求する場合、ボブは {[s'_0]_A + [s'_0]_B + y}を含む署名σを提供する必要がある。そのためボブはyを知っている場合のみこれを行える。この署名が公開されると、アリスは既に {[σ]_A}および {[σ]_B}を知っているのでσからtを計算できる。

重要なのはyとYがチェーン上に現れないということで、第三者がチェーンを監視しても、同じ条件を使う別のトランザクションと結びつけることはできない。このトランザクションは条件なしのMoneroトランザクションと変わらないため、暗号通貨MoneroのFungibilityに貢献する。

MoneroのPayment Channel Network

アリスが、アリス⇔ボブ⇔キャロル⇔デイブという形式の開かれたPayment Channel Networkの経路を使ってデイブへのオフチェーン支払いをする場合、支払は以下の3つのフェーズで行われる。

  1. 最初にデイブは条件 {(Y = yG, Y^{*} = ympk^{1}_{CD})}を作成する。条件 {(Y, Y^{*})}をアリスに伝える。
  2. アリスは条件 {(Y, Y^{*})}を使ってボブへの条件付き支払いを作成し、ボブは同じ条件を使ってキャロルへの条件付き支払いを作成し、キャロルも同条件を使ってデイブへの条件付き支払いを作成する。
  3. 最後にデイブはyをキャロルに公開し、キャロルからコインを受け取る。次にキャロルはボブに、ボブはアリスにyを公開してそれぞれコインを入手する。

と基本は↑のような手順を踏むが、全てのユーザーで同じ条件(Y, Y^*)は使用できない(計算に使うGは全ユーザー共通だけど各 {Y^*_i}の値などは異なる)。この問題に対応するため、各ユーザーペアは支払いの受取人を彼らの共有アドレスの払い戻しアドレスにアウトプットの識別子を掛けたもの(つまり、 {m_{AB}pk_A}で、 {pk_A}はペア {(pk_{AB}, pk_A)}の払い戻しアドレス)に転送する通信ラウンドを追加する。この値を受け取ると、受信者は各ユーザーについてペア {(Y, Y^*_i)}を両方の条件値が期待通りに功徳されている事実のゼロ知識証明と共に計算する。最後に、受信者はこれらの条件をゼロ知識証明と一緒に支払いのパスに送り返すという処理が加わる。

ここで、条件付き支払いを設定する前に、各ユーザーは入金の条件が出金の条件と同じ値yに基づいて構築されていることを検証するため、受信者が作成したゼロ知識証明を検証する必要がある。ゼロ知識スキームの健全性は、デイブがその証明をずるし、その状態で他のユーザーが正しいと検証できないようにすることが重要で、そうでなければ、デイブへの支払いは行われるが、同じyが使えず中継ユーザーがコインを失う状況ができるかもしれない。

この条件部分はMulti Hop Locks↓を利用して、最初に送金者がセットアップするようになるのかも?

techmedia-think.hatenablog.com

所感

↑がDLSAGを利用した条件付き支払いやPayment Channelの構成方法だけど、やっぱりかなり複雑ね。あと以下の制約もあるので、まだBitcoinのLNほど柔軟に決済とまではいかず、課題は残る。

  • DLSAGはまだMoneroでは利用可能ではなく、まだ具体的なデプロイ計画は無い?
  • Dual-Keyを使ってセットアップしたPayment Channelは有効期間付きである。
  • ペナルティや最新の残高を反映するような制約はついていないため、基本的に一方向の決済となるっぽい。

ただスクリプトシステムが無いかつ、リング署名スキームを採用しているプラットフォームで実現するという意味では意味のある提案だと思う。

MoneroでスクリプトレスなPayment Channelを実現するためのDLSAGリング署名スキーム Part1

ベースの考え方であるLSAGについて整理したので↓

techmedia-think.hatenablog.com

本丸のDLSAGとDLSAGを利用したPayment Channelの仕組みについて見ていく。

https://eprint.iacr.org/2019/595.pdf

Moneroの課題

  • BitcoinBitcoin ScriptをEthereumがSolidityなどで記述可能なコントラクトを記述出来るのに対し、Moneroにはそういったスクリプト機能が無く、コインをある秘密鍵宛に送信者を匿名化し、量を秘匿して送ることができるだけである。BitcoinやEthereumのようにどんな条件にコインがロックされ、ただどんな条件でアンロックされるのかという情報がオンチェーン上に記録され、これがFungibilityを損なう要因にもなりうる。これに対しホワイトペーパーでは、スクリプトを導入することなく、Fungibilityを担保し、インターオペラビリティを向上する仕組みを提案している。
  • BitcoinやEthereumなどのパブリックチェーンと同様、スケーラビリティの課題を抱えている。Moneroのブロックは2分毎に作成されるが、リング署名の仕組みによりBitcoinなどと比べてどうしてもトランザクションサイズが大きくなり、スケーラビリティの課題はBitcoinよりも深刻と言える。ホワイトペーパーでは、このスケーラビリティに課題に対して既にBitcoinでは実現されているが、Payment Channel Networkを利用したオフチェーンスケーリングを提案している。

上記のMoneroにおけるトランザクションの表現力の欠如とスケーラビリティという2つの問題を解決するために提案されているのが新しいリング署名方式=Dual Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (DLSAG)だ。

Dual-Key LSAG

現在のMoneroのトランザクションはインプットとアウトプットを持ち、その両者は {(pk, COM(γ), \Pi_{amt})}で定義される。pkは新しい公開鍵で、COM(γ)はコインの量γへの暗号学的コミットメントを示し、 {\Pi_{amt}}はγが範囲内の値であることを証明する範囲証明を表す。トランザクションインプットは、デコイを持つため1インプットあたり複数のタプルを持つ。トランザクションアウトプットは、1アウトプットあたり1つのタプルを持つ。

これに対し、Dual-Key LSAGでは、 {((pk_{A, 0}, pk_{B, 1}), COM(γ), \Pi_{amt}, t)}と定義される新しいdual-key タプルフォーマットがベースになる。このタプルには(それぞれ異なるユーザーの公開鍵である)2つの公開鍵が含まれ、フラグtに応じて使用できる。このDual-Keyタプルは現在のMoneroのタプルと比べて以下の点が異なる。

  1. このタプルのコインを使用する可能性がある2人のユーザーを識別するため1つではなく2つの公開鍵が含まれる。
  2. 公開鍵間のスイッチを示す(例えばtがMoneroのブロックチェーン内の現在のブロック高より小さい場合には {pk_{A, 0}}が使われる等)追加の要素tが含まれる。

Dual-Keyタプルフォーマットにより、払い戻し用トランザクションを作るためのロジックをエンコードできるようになる。

シグナルt {pk_{A, 0}}を使わなければならいことを示す場合、アリスは {pk_{A, 0}} {pk_{B, 1}}をそれぞれ含む2つの公開鍵のセットを選択し、公開鍵 {pk_{A, 0}}に対応する秘密鍵 {sk_{A}}リンク可能なリング署名を生成する。

逆にt {pk_{B, 1}}を使用する必要があると示す場合、ボブはこれまでと同じ方法でリングを選択し、 {sk_{B}}でリング署名を作ることでアウトプットを使用できる。

もちろん1人のユーザーが2つの公開鍵に対応する各秘密鍵を持っているのであれば、tの値に関係なくこの1人でそのDual-Keyタプルを使用できる。

Dual-Keyのリンク可能なリング署名

↑のDual-Keyのサポートにあたって必要になるのは、新しいリンク可能なリング署名の設計で、以下の課題がある。

キーイメージの仕組み

Moneroの現在のリング署名スキームでは、単一の公開鍵から構成されるキーイメージを公開することで、Linkabilityを実現している。例えばアリスは {sk_A}を使って署名する際は、合わせてキーイメージ {I = sk_Aℍ(pk_A)}を公開する(ℍは曲線上の点を出力するハッシュ関数)。アリスが二重使用しようとして再度 {sk_A}で署名しようとすると、同じキーイメージが計算され、ブロックチェーン上で既に使用済みであることを検出できる。

Dual-Keyで同様のLinkabilityをサポートする際の課題は、公開鍵のペア {(pk_0, pk_1)}を一意に識別し、署名鍵の内 {sk_b}1つだけで計算できる単一のキーイメージを定義する方法だ。

このホワイトペーパーでは、キーイメージをDual-Keyタプルの2つの公開鍵を使ってDiffie-Hellmanの鍵交換を使い、共有鍵を導出する方法提案している。つまり {J = sk_0 \cdot sk_1 \cdot G}として再定義している。これは以下の要件を満たす:

  1.  {sk_b}の知識で {J = sk_b \cdot pk_{1-b}}を計算できる。
  2.  {sk_b \cdot pk_{1-b} = sk_{1-b} \cdot pk_b}が成り立つので、 {(pk_0, pk_1)}を一意に識別できる。
キーイメージのLinkabilityの強化

↑の新しいキーイメージの定義は公開鍵のペアのリンクを可能にする。ただし、キーイメージを公開鍵のペアに一意になるだけでなく、それらを含むアウトプットも一意にするのが重要だ。そうしないと、ユーザーの1人が、同じ公開鍵のペアを使って別のDual-Keyタプルを作成し、それ(およびそのキーイメージ)を使って署名を作成すると、Moneroでは同じキーイメージは二度と使えないので、元々のタプルのコインは使用不可能になってしまう。

署名スキームの安全性とプライバシーの保証を損なうこと無く、各アウトプットに一意の識別子を追加することでこれを軽減できる。例えば、Moneroでは全てのアウトプットを、そのアウトプットが含まれるトランザクションとアウトプットのインデックスで構成する値 {m = H(txid || output_index)}で識別できる。

そのため、DLSAGで使われているリングを一意のトリプル {(pk_0, pk_1, m)_{[1,n]}}で構成されていると見なし、Dualキーイメージを {J = m_j \cdot sk_{j,0} \cdot sk_{j, 1} \cdot g}と定義する。jはリング内の本当の署名の位置を表す[1, n]の値。

以上を踏まえた、新しいDLSAG署名スキームは以下のようになる。

二者がそれぞれ保持する鍵ペアを {(sk_0, pk_0), (sk_1, pk_1)}とする。 そのDual-Keyタプルのコインがロックされたトランザクションアウトプットの識別子をmとする。

DLSAGの署名生成

Dual-Keyにロックされたコインを使用するトランザクションを作成し、そのインプットにはデコイと実際に使用するDual-Keyのタプルのリスト {( (pk_{0,1}, pk_{1,1}, m_1), ...., (pk_{n, 0}, pk_{n, 1}, m_n) )}がセットされている。

  1. n個ほどランダムな値をサンプリングする。  {s'_0, s_1, ..., s_{n-1}}
  2. 実際に使用する鍵と、その公開鍵とペアになる公会鍵を使ってキーイメージ {J = m_n \cdot sk_b \cdot pk_{n, 1-b}}を計算する。ここで {sk_b}は公開鍵 {pk_{n, b}}に対応する秘密鍵
  3.  {L_0 = s_0 \cdot G}および {R_0 = s'_0 \cdot ℍ(pk_n)} {h_0 = H(tx || L_0 || R_0)}を計算する。
  4.  {i \in {1, ..., n-1}}について以下の計算をする。
    •  {L_i = s_i \cdot G + h_{i-1} \cdot pk_{i, b}}
    •  {R_i = s_i \cdot m_i \cdot pk_{i, 1-b} + h_{i-1} /cdot J}
    •  {H(tx || L_i || R_i)}
  5.  {H(tx || s_0 \cdot G + h_{n-1} \cdot pk_{n, b} || s_0 \cdot m_n \cdot pk_{n, 1-b} + h_{n-1} \cdot J) = h_0}となるような {s_0 = s'_0 - h_{n-1} \cdot sk}を計算する。
  6. 結果、計算した {σ = (s_0, s_1, ..., s_{n-1}, h_0, J, b)}が署名となる。

ホワイトペーパーに合わせたので若干前回のブログと表記は違うが、基本的な署名の仕組みはLSAGと大きく変わっておらず、キーイメージおよび、キーイメージを計算に使っているRの計算式が異なるのと、どの公開鍵によるアンロックなのか示すbが署名に追加される。

DLSAGの署名検証

検証者は以下の手順で検証する。

  1.  {i \in {1,..., n}}について以下を計算する。
    •  {L_i = s_i \cdot G + h_{i-1} \cdot pk_{i, b}}
    •  {R_i = s_i \cdot m_i \cdot pk_{i, 1-b} + h_{i-1} /cdot J}
    •  {H(tx || L_i || R_i)}
  2. 算出した {h_n} {h_0}と一致すれば有効な署名。

これも基本的にLSAGの仕組みと大きく変わらない。

Moneroへの適用について

Dual Outputはもちろん現在のMoneroではサポートされないが、ハードフォークでMoneroに導入可能。現在の署名方式ととDLSAGを組み合わせたトランザクションを構成することが可能で、この混合トランザクションの場合、トランザクションは各インプット毎に通常にLSAGと、Dual-Key形式のDLSAGの署名が含まれる。どちらの形式でも公開鍵の数が異なり、Dual-Keyの場合追加のフィールド(フラグt)がある。このため、コミットメントおよび範囲証明に関する操作や検証についてはDLSAGとなっても互換性が残る。

Fungibility

2種類のアウトプット形式を共存させるとFungibilityが低下する可能性がある。例えばマイナーは選択したアウトプット形式によっては特定のトランザクションのマイニングを拒否するかもしれない。これを軽減するためには、シングルキーの場合も自分の鍵をもう1つ追加してDual-Key形式のトランザクションにするという方法がある。

タイムロック処理の拡張

Dual-Keyタプルにはフラグtが含まれており、このフラグはMoneroではブロック高として実装されると思われる。公開鍵のペア {(pk_0, pk_1)}が与えられた場合、 {pk_0}はブロックtがマイニングされる前に使うことができ、ブロックtがマイニングされた後は {pk_1}で使用できるようになる。

最近の論文に記載されているMoneroへの攻撃において、不明瞭だが、異なるtの値が敵対者にプライバシーを侵害する十分な情報を漏らす可能性がある(例えばtが現在に近い場合リングの1つめの鍵が使われる可能性が高いなど)。このため、この研究では、区別できないタイムアウトを持てるようにするタムロック処理スキームの拡張を提案している。このスキームは、Dual-KeyタプルフォーマットとDLSAG署名スキームの拡張として追加されたもので、MoneroのFungibilityを維持するのに役立つ。

提案されているタイムロック処理スキームは、tを平文のまま含めるのではなく、tの値へのPedersen Commitmentをその範囲証明と一緒に含めるというもの。tが有効期限切れになっていないかは以下のように証明できる。

  1. t < t' < Tとなるようなt'を選択する。Tはトランザクションをマイニングする必要があるブロックの高さ。
  2. 続いて、Pedersen Commitmentの準同型性を利用してコミットメント COM(t' - t) = COM(t') - COM(t)を計算する。
  3. t' - tが[0, 2k]の範囲あることを証明するために、範囲証明 {\Pi_{time}}を計算する。
  4. Pedersenタプル {(COM(t), t', COM(t' - t), \Pi_{time})}はタイムロックtが期限切れになっていないことを証明する。

この仕組みにより、ユーザーはtの実際の値を隠す任意の値t'を選択できる。MoneroはすでにPedersen Commitmentとその範囲証明をサポートしているので、この機能はシームレスにMoneroに追加できる。

以上がDLSAGの大枠。次回はDLSAGを利用してPayment Channel Networkを構成する方法について見ていきたい。