チェーン上のトランザクションの新たな参照方法の標準TxRefを定義したBIP-136

提案は結構前からあったみたいだけど先月マージされたBIP-136↓

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

Bitcoinでトランザクションを識別する際は、基本的にトランザクションのハッシュのエンディアンを逆にしたTXIDを使用する。フルノードでこのTXIDをキーにしてトランザクションを取得したい場合は予め-txindexオプションを有効にしてTXIDによるインデックスを作成しなければならない。このインデックスの作成が高価なのと、TXID自体32バイトと長い。そのため↑のBIP-136では、TXIDに変わってブロックチェーン上のトランザクションを参照する新しい識別子TxRefを提案している。

TxRefは何番目のブロックの何番目のトランザクションという、ブロック高とトランザクションの位置をエンコードしたデータになる。そのため、reorgなんかが起こると参照先のトランザクションが別のものに変わったり、なくなっている可能性があるという制約が付く。

具体的なユースケースがあるのか？と思って調べたら、どうも分散IDの文脈で、Bitcoinのブロックチェーンを利用したDID methodの１つであるBTCR DID methodでチェーン上のトランザクションの位置を指すのにTxRefエンコーディングを使ってるっぽい↓

https://w3c-ccg.github.io/didm-btcr/#txref

注意点としては、やっぱりreorgの影響かな。BIPにも100承認以上とあるけど、TXIDと違って別のTxを参照する可能性があるので承認がある程度ないと使いづらい。

以下、BIPの内容↓

イントロダクション

概要

この文書は、Bitcoinのブロックチェーン内のトランザクションの位置および参照トランザクション内の特定のOutPointインデックスを参照するための標準的な方法として、人が便利に使用できるフォーマット「TxRef」を提案する。このフォーマットの主な目的は、承認されたトランザクションを参照する際の標準的で信頼性のある簡潔な方法を提供することだ。

注意：IDと実際のトランザクションとの間に強力な暗号学的リンクがあるTxIDとは違い、TxRefは特定のトランザクションへの弱いリンクを提供するだけだ。TexRefはトランザクションのブロックチェーン内でのオフセットを指すが、これは実際のトランザクションを指している場合と指していない場合がある（実際のトランザクションは再編成によって変わることがある）。TxRefは、成熟度が100ブロック未満のブロックチェーン内の位置には使用しないことを推奨する。

動機

Bitcoinの初期バージョン以降、TxID（トランザクション識別子）はコンセンサスプロトコルのコア部分であり、ユーザー間で個々のトランザクションを識別するために日常的に使われてきた。

しかし、多くのユースケースにおいて、実用上の制限がある。

• TxIDは、フルノードが検索するのには高価である（ブロックチェーンのリニアなスキャンか、高価なTxIDのインデックスを必要とする）。
• TxIDは、SPVウォレットが検索するにはサードパーティのサービスを必要とする。
• TxIDは非常に長いHEXエンコード値（64文字）である。

ブロックチェーンに埋め込まれているトランザクションの場合、そのTxIDではなく、ブロックチェーン自体の中のそのトランザクションの位置により参照することが可能だ。また人が転記しやすいようにエンコードできる。この文書ではこのための標準を提案する。

サンプル

以下はBitcoinトランザクションのサンプル。

• ジェネシスコインベーストランザクション (０番目のブロックの０番目のトランザクション): tx1:rqqq-qqqq-qmhu-qhp
• 466793番目のブロックの2205番目のトランザクション： tx1:rjk0-uqay-zsrw-hqe

仕様

承認済みトランザクションの位置参照、つまりTxRefはブロックの高さとブロック内のトランザクションのインデックスおよびオプションでトランザクション内のOutPointのインデックスによって指定される、ブロックチェーン内の特定の場所への参照だ。

注意：この仕様の全ての値はリトルエンディアン形式でエンコードされている。

TxRef

以下の理由によりTxRefは存在しない場所を参照している可能性がある：

• 指定されたブロックがまだマイニングされていない。
• トランザクションインデックスが、指定されたブロックに含まれているトランザクションの総数を超えている。
• オプションのOutPointのインデックスがトランザクションに含まれているOutPointの総数を超えている。

したがって、実装者はTxRefを早い段階でユーザーに表示しないよう注意する必要がある：

• アプリケーションは、６承認未満のトランザクションのTexRefを表示してはならない。
• アプリケーションは１００承認未満のトランザクションのTxRefを表示する場合は警告を表示する。
  • この警告は、大規模な再編成が起こった場合、表示されているTxRefが別のトランザクションを指すか、トランザクションを指していない可能性があることを示す。

エンコーディング

TxRefはBIP-173で定義されている標準のBech32エンコーディングを使用しているため、以下で構成される。

• Human-readable、つまりHRPの部分は、namespaceを提供する。MainnetとTestnetを区別するための以下のように定義する。
  • Mainnetの場合は：tx
  • Testnetの場合は：txtest
  • これら２つと他のプロジェクトに関連するものを含む完全なHRPのリストについては、SLIP-0173を参照。
• セパレータ： 1
• データパート

注意：分散IDの仕様など他の仕様では、HRP内の他の場所に含まれる情報が暗黙的にエンコードされている。この場合、ここで指定されているようなHRPを含まないことを選択するかもしれない。

移植性と可読性を高めるため、セパレータを追加する必要がある。

• 1の後にコロンを追加する。
• コロンの後、４文字毎にハイフン（-）を追加する。

bech32のコードセパレータの後にある非bech32アルファベット文字は、パースの際に無視/削除しなければない（終端文字を除く）。

TxRefのテキストエンコーディングは、

	Bit	Character	Characters	Value
Human-readable部分		1-2	2	BitcoinのMainnetはtx、Testnetはtxtest
セパレータ		3	1	1
コロン		4	1	:
データ	0-19	5-8	4
ハイフン		9	1	-

データ - ハイフンパターンは、データ全体の長さに渡って繰り返される（ハイフンがエンコードされた20bitまたは４データ文字毎に挿入される）。

データ

オプションのトランザクションのOutPointが含まれるかどうかで、上記文字列にエンコードされた75ビットもしくは90ビットのデータになる。これらのbitは次のように定義されている。

Bitcoin MainnetとTestnetのTxRefバイナリフォーマット

	Bit	Bit(s)	Type	values	Notes
マジックコード	0-4	5	チェーンのネームスペースコード	Bitcoinの場合は0x03、OutPointを含むMainnetの場合は0x04。Testnetが0x06でOutPointを含むTestnetが0x07
バージョン	5	1	将来のための確保	必ず0x0
ブロック高	6-29	24	Txのブロック高	ブロック０（ジェネシス）〜ブロック16777215	2328年まで
トランザクションインデックス	30-44	15	ブロック内のTxインデックス	Tx0（コインベース）〜32767番目のTxまで	ブロック内の最大Txが16665個

マジックコードが0x04、0x07の場合、オプションのOutPointがエンコーディングに含まれる。

	Bit	Bit(s)	Type	values	Notes
OutPoint インデックス	45-59	15	Tx内のOutPointのインデックス	OutPoint 0〜32767番目のOutPointまで

最後に30bitのチェックサムを含める。

	Bit	Bit(s)	Type	values	Notes
チェックサム	45-74 or 60 - 89	30	Bech32チェックサム

マジックに関して

マジックコードはチェーン間のnamespaceを提供する。BitcoinのMainnetとTestnetには5bitのマジックコードが使われている（他のプロジェクトやチェーンではかなり長くなるかもしれない）：

• Bitcoin Mainnetの場合、マジックコードは0x3で、エンコードすると文字rになる。
• OutPointを含むBitcoin Mainnetの場合マジックコードは0x4で、エンコードすると文字yになる。
• Bitcoin Testnetの場合、マジックコードは0x6で、エンコードすると文字xになる。
• OutPointを含むBitcoin Testnetの場合マジックコードは0x7で、エンコードすると文字8になる。

コード0x0、0x1、0x2、0x5はBitcoinの将来のプロジェクト用に予約されている。

他のチェーンは0x0から0x7までで始まるマジックコードとして使ってはならない。

他のチェーンのマジックコードはSLIP-XXXX "TxRef for Non-Bitcoin Chains and Networks"で指定される。

互換性

互換性に関する既知の課題はない。

論拠

1. 承認済みトランザクションの参照になぜBech32エンコーディングを使用するのか？
   Bech32エンコーディングフォーマットの誤り検出および訂正特性は魅力的だ。ソフトウェアが最大２文字の修正するのが妥当だと期待しているが、まだこれを指定していない。
2. どうしてコロンを追加したのか？
   これによりW3CのURN/URL標準への準拠性が向上する。
3. TxRef内にハイフンがあるのはなぜ？
   TxRefは短いので、音声で引用するか手で書くことを予想している。4文字毎にハイフンを入れると文字列が分割され、人が場所を簡単に見失わないようになる。
4. 非bech32アルファベット文字列を削除するのはなぜ？
   ユーザーは自分のTxRefを良いUnicode形式にしておきたいと望むことはないと思っている。コピーやペースト、手書きを組み合わせて書くと予想する。パーサーはこれらによる一般的なエラーを全て自動的に修正すべきだ。

参照実装

• Cの参照実装（マジックコード0x3と0x6をサポート）： https://github.com/jonasschnelli/bitcoin_txref_code
• Goの参照実装（マジックコード0x3と0x6をサポート）： https://github.com/kulpreet/txref
• C++の参照実装（マジックコード0x3と0x4、0x6, 0x7をサポート）： https://github.com/dcdpr/btcr-DID-method/

Appendix

Test Vector

以下を含む2つのTest Vectorをセットがある。

• Bech32エンコードされたTest Vector。実装が正しいHuman-readableパートとセパレーターを含む円k−土を受け入れるかどうかテストするのに使用する。
• Bitcoin TxRef Test Vector。完全な仕様、特にブロック高およびトランザクションインデックスの正しい値かどうかテストするのに使用する。

TxRef用のBech32エンコーディング

注意：すべてのTest Vectorは文字列が準拠しているかどうかをテストするのに役立つ。すべての実際のアプリケーション（Bitcoin向けの）は、書きのBitcoinのTest Vectorに準拠している必要がある。

以下の文字列は有効なHuman Readable PartとBech32チェックサムを持つ。

• TX1A12UEL5L
• tx1an83characterlonghumanreadablepartthatcontainsthenumber1andtheexcludedcharactersbio1tt5tgs
• tx1abcdef1qpzry9x8gf2tvdw0s3jn54khce6mua7lmqqqxw
• tx11qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqc8247j

以下のリストは無効なTxRefとその理由を示している。

• bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kg3g4ty： Human-Readable Partが無効
• tx1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t5： チェックサムが無効

Bitcoin TxRef（mainnetおよびtestnet）

以下のリストは正しくエンコードされたBitcoin mainnetのTxRefとhex値（ブロック高およびトランザクションインデックス）。

• tx1:rqqq-qqqq-qmhu-qhp: (0x0, 0x0)
• tx1:rqqq-qqll-l8xh-jkg: (0x0, 0x7FFF)
• tx1:r7ll-llqq-qghq-qr8: (0xFFFFFF, 0x0)
• tx1:r7ll-llll-l5xt-jzw: (0xFFFFFF, 0x7FFF)

以下のリストは正しくエンコードされたBitcoin testnetのTxRefとhex値（ブロック高およびトランザクションインデックス）。

• txtest1:xqqq-qqqq-qkla-64l: (0x0, 0x0)
• txtest1:xqqq-qqll-l2wk-g5k: (0x0, 0x7FFF)
• txtest1:x7ll-llqq-q9lp-6pe: (0xFFFFFF, 0x0)
• txtest1:x7ll-llll-lew2-gqs: (0xFFFFFF, 0x7FFF)

以下のリストは（奇妙フォーマットされているが）有効なBitcoin TxRefとhex値（ブロック高およびトランザクションインデックス）。

• tx1:rjk0-uqay-zsrw-hqe: (0x71F69, 0x89D)
• TX1RJK0UQAYZSRWHQE: (0x71F69, 0x89D)
• TX1RJK0--UQaYZSRw----HQE: (0x71F69, 0x89D)
• tx1 rjk0 uqay zsrw hqe: (0x71F69, 0x89D)
• tx1!rjk0\uqay*zsrw^^hqe: (0x71F69, 0x89D)

以下のリストは無効なTxRefとその理由。

• tx1:t7ll-llll-ldup-3hh: 0x3の代わりにマジックが0xBになっている。(0xFFFFFF, 0x7FFF)
• tx1:rlll-llll-lfet-r2y: バージョンが0でなく1になっている。(0xFFFFFF, 0x7FFF)
• tx1:rjk0-u5ng-gghq-fkg7: 有効なBech32だが、8ではなく10x5 bitのパッケージになっている。
• tx1:rjk0-u5qd-s43z: 有効なBech32だが、8ではなく6x5bitのパッケージになっている。

OutPointを含むBitcoin TxRef（mainnetおよびtestnet）

以下のリストは正しくエンコードされたOutPointを含むBitcoin mainnetのTxRefとhex値（ブロック高およびトランザクションインデックス、TXOインデックス）。

• tx1:yqqq-qqqq-qqqq-ksvh-26: (0x0, 0x0, 0x0)
• tx1:yqqq-qqll-lqqq-v0h2-2k: (0x0, 0x7FFF, 0x0)
• tx1:y7ll-llqq-qqqq-a5zy-tc: (0xFFFFFF, 0x0, 0x0)
• tx1:y7ll-llll-lqqq-8tee-t5: (0xFFFFFF, 0x7FFF, 0x0)
• tx1:yqqq-qqqq-qpqq-5j9q-nz: (0x0, 0x0, 0x1)
• tx1:yqqq-qqll-lpqq-wd7a-nw: (0x0, 0x7FFF, 0x1)
• tx1:y7ll-llqq-qpqq-lktn-jq: (0xFFFFFF, 0x0, 0x1)
• tx1:y7ll-llll-lpqq-9fsw-jv: (0xFFFFFF, 0x7FFF, 0x1)
• tx1:yjk0-uqay-zrfq-g2cg-t8: (0x71F69, 0x89D, 0x123)
• tx1:yjk0-uqay-zu4x-nk6u-pc: (0x71F69, 0x89D, 0x1ABC)

以下のリストは正しくエンコードされたOutPointを含むBitcoin testnetのTxRefとhex値（ブロック高およびトランザクションインデックス、TXOインデックス）。

• txtest1:8qqq-qqqq-qqqq-cgru-fa: (0x0, 0x0, 0x0)
• txtest1:8qqq-qqll-lqqq-zhcp-f3: (0x0, 0x7FFF, 0x0)
• txtest1:87ll-llqq-qqqq-nvd0-gl: (0xFFFFFF, 0x0, 0x0)
• txtest1:87ll-llll-lqqq-fnkj-gn: (0xFFFFFF, 0x7FFF, 0x0)
• txtest1:8qqq-qqqq-qpqq-622t-s9: (0x0, 0x0, 0x1)
• txtest1:8qqq-qqll-lpqq-q43k-sf: (0x0, 0x7FFF, 0x1)
• txtest1:87ll-llqq-qpqq-3wyc-38: (0xFFFFFF, 0x0, 0x1)
• txtest1:87ll-llll-lpqq-t3l9-3t: (0xFFFFFF, 0x7FFF, 0x1)
• txtest1:8jk0-uqay-zrfq-xjhr-gq: (0x71F69, 0x89D, 0x123)
• txtest1:8jk0-uqay-zu4x-aw4h-zl: (0x71F69, 0x89D, 0x1ABC)

Bitcoin TxRef ペイロード値の選択

ブロック高とトランザクションインデックスの特定のビット長を選択した理由を示すいくつかの計算結果がある。

ブロック高の値：

0〜0xFFFFFF（16,777,216ブロック）の間の24 bit。

• 毎年52500ブロック増え、アドレス可能なブロックは319年分である。
• しｔがって、2328年より前にこの仕様は拡張されるべきだ（我々には十分な時間がある）。

トランザクションの位置の値：

0x0から0x7FFF（32,768トランザクション）の15 bit。

• 現実的な最小のトランザクションは83バイトで、1ブロック内で最大トランザクション数は12047。
  • 4B version + 1B tx_in count + 36B previous_output + 1B script length + 0B signature script + 4B sequence + 1B tx_out count + 8B amount + 1B script length + 23B pubkey script + 4B lock_time = 83B
• 極端に最小のトランザクションは60バイトで、1ブロック内の最大トランザクション数は16665。
  • 4B version + 1B tx_in count + 36B previous_output + 1B script length + 0B signature script + 4B sequence + 1B tx_out count + 8B amount + 1B script length + 0B pubkey script + 4B lock_time = 60B

LNでインボイスを必要としないSpontaneous Paymentの2つの実装方法

通常Lightning Networkの決済では、支払先が予めインボイスを作成し、それを支払元に送ることで支払いがスタートする。このインボイスにはLNでマルチホップ決済をするにあたって、支払先のノードIDやコントラクトを構成する際に必要な情報（プリイメージのハッシュ、HTLCの有効期間など）が含まれる。これらの情報の伝達のため、基本的にLNではインボイスを使った支払いフローがデフォルトになっている。

ただ、Bitcoinのオンチェーントランザクションのように、相手のアドレスさえわかっていれば、相手と対話することなく支払元か直接支払するというユースケースも十分考えられる。

AMPを利用する方法

インボイスを必要としないSpontaneous Paymentについては、既にAMP（Atomic Multi Path Payments）をベースにしたアイディアがある。

従来のLNでは決済に使用するプリイメージは支払先が作成し、そのハッシュをインボイスに載せて支払元に伝達するが、Spontaneous Paymentでは、支払元がプリイメージを作成し、ルーティング含めた決済ではそのプリイメージのハッシュを使用する。そしてLNのオニオンルーティングを仕組みを利用して、プリイメージは支払先のみが復号できるように暗号化され、LNのルーティングパケットの最後のオニオンパケットにセットされ、支払先まで送信される。データを受信した支払先のノードは、プリイメージを復号し、そのプリイメージを利用して支払を受け取る。

この機能の自体は支払元と支払先のノードだけ、この仕組みに対応していればよく、中間ノードは通常のLN決済として認識する。

ECDHを利用する方法

このSpontaneous Paymentについて、ECDHを利用する方法が先日LNの開発者MLに新しいアイディアがポストされた↓

[Lightning-dev] ECDH for spontaneous payments and offline vending machines

このアイディアは、↑で発生する暗号化したプリイメージのルーティングをECDHを使うことで不要にしようというもの。

支払元から支払先へのLNのルーティングができるのであれば、両者がECDH（楕円曲線 Diffie-Hellman）によって導出できる共有シークレットを持つことを意味するため、それをプリイメージとして使えば、暗号化したプリイメージ自体をルーティングする必要はないというもの。

ECDHは楕円曲線を使って共通鍵を導出する仕組みで、アリスとボブがそれぞれ秘密鍵a、bと対応する公開鍵A = aG、B = bGを持ち、それぞれ相手の公開鍵を知っている場合、相手の公開鍵に自分の秘密鍵を乗算して出来た点は同じ点を指すという特性ががある。

共通鍵 = a * B = b * A

具体的には、支払先のノードのノードIDをN（ノードID = 公開鍵）、支払元が支払の際に生成する一時鍵（ephemeral key）をkとするとk * Nで新しい点が算出され、その点のx座標のハッシュをプリイメージとし、x座標のdoubleハッシュをペイメントハッシュとするというもの。

この場合、支払先のノードは自分がインボイスとして発行したものではないペイメントハッシュの支払を受け取ったら、自身のノードIDNの秘密鍵nとオニオンパケットにセットされている一時鍵kの公開鍵（K = kGとする）を使って共通鍵n + Kを計算し、そのx座標のdoubleハッシュと比較する。合致すれば対応する共有シークレットがその支払のプリイメージとなる。

既にChristian Deckerによるc-lightningで動作するPoCコードもある↓

GitHub - cdecker/lightning at stepan-pay

プリイメージ用に余計なオニオンパケットのデータを作らなくて良い分、ECDHの方がデータ量が少し少なくて済むのでシンプルで良いかもね。

マークルツリーを利用したハッシュベースのアキュムレータ「Utreexo」

BitcoinのUTXOセットを管理するにあたって、そのストレージ要件を大幅に削減すると期待されているアキュムレータ。昨年のScaling Bitcoinでは、スタンフォード大学のBenedikt BünzがRSAを利用したアキュムレータを紹介した↓

techmedia-think.hatenablog.com

↑はその性質上Trusted Setupを必要とするという課題があり、Trusted Setupを回避するためにClass Groupを使用するという提案もあるがまだ新しい暗号プリミティブであるという課題はある。

そんな中、今回Lightning Networkのホワイトペーパーの共著者でもあるThaddeus Dryjaがマークルツリーを利用したハッシュベースのアキュムレータ「Utreexo」を発表した↓

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

アキュムレータの構造

Utreexoは、要素のセットを完全二分木のフォレスト（森＝複数の完全二分木が存在する）で管理する。

例えば要素の数が3つある場合、以下の2つのツリーが構成される。

Aは1,2の要素から生成された親ノードのハッシュ値。この場合、アキュムレータは各ツリーのルートであるAと3の値を管理できれば良い。

要素の追加

さらに要素4を追加すると、フォレストは以下のような１つのツリーになる。

この場合、アキュムレータはルートCの値だけ管理すれば良い。

さらに要素５を追加すると、２つのツリーになり、アキュムレータはCと５を管理する。

このような形で、アキュムレータは要素を完全二分木になるよう追加していく。新しく要素を追加する際も、各ツリーのルートハッシュだけ知っていれば新しいフォレストを構成できる。

この完全２分木の構造には効率的な特性がある。要素の数＝リーフの数さえ分かれば、どのようなフォレストが構成されるかはリーフの数をバイナリ表現にすると明白になる例えば上記の要素の数５を例にすると、そのバイナリ表現は101となる。フォレースと内のツリーの数はこのバイナリ表現の１が立っているビットの数と等しく、それらの木の高さはbit 1が立っている位置から分かる。例えば、101であれば、そこから高さ１と高さ３のツリーが２つあることが分かる。

要素の包含証明

要素の追加については↑のようにフォレストの各ツリーのルートハッシュを管理すればいいことが分かったので、続いて要素の証明について。

要素がアキュムレータ内に存在するかどうかは包含証明（inclusion proof）を提供することで証明する。

この包含証明は

• リーフの位置
• ハッシュのリスト

で構成される。ハッシュのリストには、その要素が存在するツリーにおいて、その要素の兄弟のハッシュと、さらにそこからルートのハッシュを計算するのに必要な中間ノードのハッシュが含まれる。

アキュムレータと包含証明が与えられると、アキュムレータは要素の総数からフォレストの構成を知っているので、包含証明内のリーフの位置から、対象の要素がフォレスト内のどのツリーに属するものか判断する。ツリーが特定できると後は、包含証明のハッシュのリストと、アキュムレータが管理しているそのツリーのルートハッシュを使って、要素がアキュムレータ内に存在するか検証する。

例えば↑の５の要素があるツリーにおいて、要素３の包含証明は、

３の位置と、要素３と、その兄弟である4のハッシュと、さらにルートを計算するのに必要なAのハッシュとなる。これらの包含証明からルートハッシュを計算し、それがアキュムレータの管理するハッシュと等しければ要素がアキュムレータ内に存在することが分かるという仕組みだ。この辺のマークルツリーの復元とルートハッシュの計算は、現在のBloom Filterを利用したSPVクライアントがブロック内のトランザクションの有無を検証する手法と基本的に同じだ。

要素の削除

削除する際は、アキュムレータにその要素の包含証明（inclusion proof）が与えられ、該当する要素がアキュムレータ内に存在するか検証し、存在する場合要素を削除する。Bitcoinでは、あるトランザクションでUTXOが消費された場合にそのUTXOの包含証明が添付され、アキュムレータに対して要素の存在検証が終わったのち、アキュムレータから要素を削除する。このようなケースは基本的に新しいブロックを受信した際に行われ、その際には大量の新規UTXOの追加と大量の既存UTXOの削除が行われる。このため１つ１つの要素をアキュムレータから削除し都度アキュムレータを更新するよりも、削除対象の要素のセットを一括で処理してしまう方が必要なハッシュ計算の回数が少なくて済む。

削除では以下のTwin、Swap、Root、Climbという４つのステップ順番に繰り返す。

Twin

まず最初に処理されるのがTwinで、左右の兄弟両方が削除される場合の削除を指す。

例えば↑の場合、0と1が削除対象のリストに入っている要素。Twinで削除されると更にその親の要素４が削除リストに加えられる。

Swap

↑のように要素1, 2が削除対象な場合、要素３の要素１があった場所に移動する。そして親の５は次の行を処理する際の削除リストに追加される。

この時ノードは要素３のハッシュ値について知っている必要があるが、ツリーのルート値しか知らないアキュムレータにはそれが分かるのか？と疑問に思うかもしれないが、要素３のハッシュ値は要素２を削除する際の包含証明で与えられているのでそれを利用する。

Root

TwinやSwapが起きるのはその行に対して偶数数の削除が発生する場合だ。削除の要素数が偶数の場合Rootステップはスキップされる。逆に要素の削除数が奇数の場合、Twin、Swapフェーズ終了後１つの削除要素が残った状態になり、この削除要素はRootステップで処理される。

Rootステップでは、処理する行にルートが存在する場合、ルートを削除の位置に移動する。

↑の場合、要素３が削除されているが同じ行にルート要素４があるので要素４を３の位置に移動して終了。

その行にルートが存在しない場合は、削除対象の兄弟をその高さのルート位置に移動し、フォレスト内に新しいツリーを作成する。

↑の場合、要素２は高さ１のツリーのルートに昇格する。2があった位置は削除対象になる。そのため2,3の削除がTwinに該当するので、その親の9も次の行での削除対象としてマークされる。

Climb

Rootステップが終了すると、Climbステップではフォレストのレベル間を移行する。各ステップを適用し移動後の親の再計算や削除が終了すると、ツリーの１つ上のレベルに上がってまたTwinから始める。これをフォレストの頂点に達するまで続ける。

Bitcoinへの適用

UTXOモデルを採用しているBitcoinでは、トランザクションには、インプットとアウトプットがあり、インプットは以前に作られたアウトプットを参照し使用する。この設計では、データ・セットに対する唯一の操作は作成、読み取り、削除で、記録後の要素のセットには削除以外に変更を加えることはできない。新しいトランザクションによって既存のUTXOが消費され新しいUTXOが誕生する。Bitcoinのフルノードはこの状態変化をすべて検証している。IBDと呼ばれる初期同期プロセスでは、ユーザーは200GBを超える履歴をダウンロードし、何億ものデジタル署名を検証する必要がある。そして最終状態においてそのUTXOセットは4GB近くになる。

現在のBitcoinのフルノードはUTXOセットをディスク上のデータベースに保存している（levelDB）。このUTXOは作成されてから使用される直前までの期間、システムに影響を与えずデータベースエントリーにアクセスされることもなく、それが使用される場合のみディスクから読み取られる。

そのため、消費されるまでアクセスされないUTXOを保存しなくて済む設計でにできると、フルノードを運用するハードウェア要件が緩くなる。現在でもRaspberry Piなんかの小型デバイスでフルノードを動かすことはできるが、基本的にUTXOセットにはサイズ制限が無いので、将来的に利用者の増加に伴いUTXOセットの膨張が進むかもしれない。このためUTXOの管理をアキュムレータ化すると、長期的なスケーラビリティに貢献することになり、またディスクの読み書きが最小限に抑えられることでIBDの同期時間の向上にもなる。

ブリッジノード

ただ、Bitcoinはもともとアキュムレータネイティブな設計ではなく、既に稼働中のBitcoinノードが多数ある状況で、当然そのノードもこのアキュムレータを実装している訳ではない。アキュムレータに対応したノードは、トランザクションを検証する際に別途UTXOの包含証明を添付する必要がある。アキュムレータに対象したノードであれば自身が所有するUTXOの包含証明を提供することができるが、他のノードはそれを要求しないだろうし、他のノードが伝播したトランザクションには包含証明が含まれていないのでアキュムレータ対応ノードはそれを検証できないといったことになる。

このため、現在稼働中のフルノードとアキュムレータに対応したノードが同時に稼働するためにはネットワークにブリッジノードが必要になる。ブリッジノードというのはアキュムレータ内の全てのUTXOに対するプルーフを持っているノードだ（Utreexoの場合マークルフォレスト全体を常に持っているノード）。

ブリッジノードは上記のように現状のフルノードとアキュムレータに対応したCompact State Nodeとのブリッジとして機能する。フルノードは以前と同様に動作し、トランザクションとブロックをお互いに伝播する。ブリッジノードはフルノードで、マークルフォレスト全体も格納し、Compact State Nodeに包含証明を提供する。Compact State Nodeは包含証明を省略することでトランザクションメッセージをフルノードに送信できるが、証明を提供できないフルノードから直接トランザクションを受け取ることはできない。

RSAアキュムレータと違ってTrusted Setupは必要ない。ただ、アキュムレータがフォレストのツリーのルートハッシュで構成されるので、ツリーの数の増減に伴いアキュムレーターのサイズも増減するので固定サイズにはならない。

Bitcoinネットワークの安全性を向上させるための新しいトランザクションリレープロトコル「Erlay」

先日、Gleb Naumenko, Pieter Wuille, Gregory Maxwell, Sasha Fedorova, Ivan Beschastnikhらが発表したBitcoinの新しいトランザクションリレープロトコル「Erlay」について論文読んでみた↓

https://arxiv.org/pdf/1905.10518.pdf

現在のトランザクションリレープロトコル

現在、Bitcoinのトランザクションリレーは以下のプロセスで行われている。

現在のBitcoinのトランザクションリレーフロー

1. ノード（Peer 1）が接続中のピアからトランザクションを受信する。
2. Peer 1はそのトランザクションについて、そのトランザクションのハッシュをINVメッセージを使って、接続中の（まだそのトランザクションのハッシュをINVで送っていない）他のピアにトランザクションをアナウンスする。
3. INVメッセージを受け取ったノード（Peer 2）は、そのハッシュのトランザクションについて自身が知らない場合、送信元のPeer 1にGETDATAメッセージを送信しそのトランザクションを要求する。
4. GETDATAメッセージを受信したノードは（Peer 1）は、該当するトランザクション情報をGETDATAの送信元（Peer 2）にTXメッセージで送信する。

新しいトランザクションを受信したピアが、そのトランザクション情報を自身が接続している全てのピアに一斉に送信する（正確にはピア毎にランダムな遅延時間がある）このような方式をフラッディング方式と呼ぶ。なお、Bitcoinネットワークには、以下の2種類のノードが存在する。

• パブリックノード
  8つのアウトバウンド接続とデフォルトで最大125のインバウンド接続（インバウンド接続の最大値は1000まで設定可能）を持つノード（一般的なフルノード）
• プライベートノード
  8つのアウトバウンド接続を持つが、インバウンド接続は持たないノード（トランザクションを検証できいない軽量ノードとかはこっち）

このフラッディング方式は非常に単純でトランザクションの存在をBitcoinネットワーク全体に素早く伝播するという点では効果的だ。だが、効率的ではない。ノードが接続中のインバウンド、アウトバウンドピア全てに配信するため、各ピアが既に自身が知っているトランザクションのハッシュ値をINVメッセージで受け取ることが多い。Bitcoinの場合トランザクションのハッシュ値は32バイトなので、１つのトランザクションのリレーについて、32バイト×冗長なメッセージの個数分、ネットワークの帯域幅を無駄に使用していることになる。

論文で言及されている分析結果では、トランザクションのアナウンスに使われている帯域幅の88%が冗長で、それは使用される全帯域幅の44%を占めるとされている。

一方、Bitcoinのネットワークを堅牢にするためには、各ノードが繋がるノードの数を増やす必要がある。ネットワークの接続性が高いほどネットワーク・セキュリティも向上する。しかし、現状のリレープロトコルのままアウトバウンドの接続数を増やすと、帯域幅の使用量もリニアに増えてしまう。

Erlayプロトコル

↑のようなリレープロトコルの冗長性を軽減し、接続数に対してスケール可能な新しいリレープロトコルがErlayだ。Erlayではトランザクションのリレーを以下の2段階（ファンアウト、reconciliation）で行う。

ファンアウトフェーズ

フラッディング方式は、情報素早くネットワーク全体に伝播するという意味では効果的なので、これを限定的に利用する＝ファンアウトフラッディング。このフェーズでは、パブリックノードがアウトバウンド接続のみを使って*18つのピアに対し新しいトランザクションの存在をフラッディングする。パブリックノードのアウトバウンド接続のリンクを使ってトランザクションを受け取るのはインバウンド接続を許可している同じくパブリックノードであるため、このフラッディングではパブリックノード間にトランザクションを迅速に伝播していくことになる。

この時、現状8つであるアウトバウンド接続のピアの数を将来的に増やしたとしても、ファンアウトフェーズでフラッディングするピアの数は8つのままとする。そうすることで8つ以上アウトバウンド接続を増やしてもトランザクションの伝播コストはそれに比例して増えることはない。

set reconciliationフェーズ

↑のファンアウトフェーズだけではトランザクションはネットワークの全体には行き渡らない。特にプライベートには行き渡らない。そこで続けてset reconciliationフェーズを実行する。

set reconciliationフェーズでは、P2Pネットワーク内のノードはローカルの状態と接続しているピアの状態を定期的に比較し、必要な情報（状態の差分）のみを送信/要求する。つまり各ノードは自分が知っているトランザクションセット（状態）を累積し、あるタイミングで接続先のピアとトランザクションセット（状態）の差を計算し、自身に不足しているトランザクションのみを要求する。

この二者間の状態セットの差分の計算と不足データの復元を効率的に行うためのライブラリが以前公開された、エラー訂正符号に基づいた帯域幅効率の高いMinisketchだ↓

GitHub - sipa/minisketch: Minisketch: an optimized library for BCH-based set reconciliation

Erlayを実装したピアは、Minisketchを利用してローカルの状態セットのSketchを計算し、set reconciliationを実行する。ここで計算するSketchは以下の２つの特性を持つ。

• Sketcheは事前定義された容量を持ち、セット内の要素数がその容量を超えなければ、sketchをデコードすることでsketchからセット全体を復元することが常に可能である。容量cで、bビットの要素のsketchはbcビットで保存できる。
• 2つのセットの対称差のsketchは、2つのセットのsketchのビット表現をXORすることで得られる。

具体的には、次のプロセスで二者間のトランザクションセットを同期する。アリスとボブがそれぞれ要素のセットを持っているとする。両者のセットは大部分が同じであるが、完全に同じではない。この場合両者は自分に不足している要素を学習するために以下のプロセスを実行する。なお、実際に両者が持つセットの要素というのはトランザクションの短い識別子（短縮txid）で構成される。

1. アリスとボブは共にローカルでそれぞれのセットのsketchを計算する。
2. アリスは自分のsketchをボブに送る。
3. ボブは2つのsketchを結合し、対称差のsketchを入手する。
4. ボブは対称差のsketchから要素の復元を試みる。
5. ボブはアリスにアリスが持っていない要素を送り、ボブが持っていない要素をアリスに要求する。

このプロセスはセットの差のサイズ（アリスが持っているがボブは持っていない要素+ボブが持っているがアリスは持っていない要素）がアリスが送ったsketchのサイズを超えない場合は常に成功する。そうでない場合、手順は失敗する可能性がかなり高い。

この手順の重要な特性は、実際のセットサイズに関係なく機能することで、セットの差のサイズだけが重要になる。

上記のようにファンアウトフェーズで伝播されなかったトランザクションは、その後のset reconciliationフェーズでノード間のトランザクションのセットの差異を効率的に解消することでネットワーク全般にトランザクションがいきわたること保証する。プライベートノードは基本的にそのアウトバウンド接続先であるパブリックノードとset reconciliationを実行することでトランザクションを同期する。

フラッディングとset reconciliationを組み合わせたトランザクションリレーフロー

Sketchのデコードに失敗した場合

set reconciliationは二者間のセットの差分の上限が予測可能であるという仮定に依存している。つまり、実際の差分が見積もりよりも大きい場合、Sketchのデコードに失敗する。この場合ノードは二分法を使って再度set reconciliationを試みる。これでも失敗する場合、従来のフラッディングによりトランザクションを通知する。

set reconciliationの実行スケジュール

各ノードは1秒ごとに１つのアウトバウンドピアとreconciliationを開始する。この設定で現在のプライベートノードとパブリックノードの比率では、各パブリックノードが１秒間に約8回のreconciliationを実行する。現在の最大Bitcoinネットワークトランザクションレートが7トランザクション/秒であると仮定すると、このプロトコルの平均差分セットのサイズは7要素。毎秒１回新しいピアに対して繰り返され、ファンアウトアナウンスを介して受信しなかったトランザクションを迅速に受信できる。

拡散遅延

従来のBitcoinのフラッディング方式ではトランザクションのアナウンスにランダムな遅延を入れることで、タイミング攻撃および飛行中の衝突*2を軽減している。Erlayにおいては、各フェーズの拡散遅延は以下のようになる。

ファンアウトの拡散遅延

ファンアウトフラッディングはアウトバウンド接続のピアに対してのみ行われるため、タイミング攻撃および飛行中の衝突の心配がないため、レイテンシーを減らすこともあり、より小さな拡散インターバルは1秒。

set reconciliationの拡散遅延

set reconciliationフェーズではタイミング攻撃の可能性が考えられることから、それをコスト高にするため、各ピアにreconciliation要求に応える前に小さなランダムな遅延（平均1秒であるポイズン分布の確率変数）を設けるのを強制する。

Erlay導入の効果予測

限定されたフラッディング方式の利用と断続的なreconciliationを組み合わせた代替プロトコルであるErlayの論文で紹介されているシミュレーション結果（60000ノードのシミュレーションネットワークと、複数のデータセンターにまたがって国際的に広がる100ノードのライブセットの両方を使ってパフォーマンスを分析している）では、Erlayが新しいトランザクションの存在をアナウンスするのに使われる帯域幅の84%を削減するという結果が出ている。この帯域幅の削減効果は大きく、将来的にBitcoinネットワークの接続性を向上させ、ネットワーク・セキュリティを向上させるために重要な改善と言える。

ただ、トランザクションがネットワーク全体に伝播するまでにかかる時間は約2.6秒長くなるとされている。この点については、トランザクションの承認は10分に１回であるという側面もあることからトレードオフとしては問題の無い範囲のように思える。

特に異議がなければ今後Bitcoin Coreに実装されていくことになるだろう。P2Pネットワークのような分散環境を堅牢にしていくための地道な取り組みを行っていくのがBitcoinらしくて良い！

*1:インバウンド接続ではなくアウトバウンド接続を利用するのは、タイミング攻撃を防ぐためでもある。

*2:同じタイミングで接続中のノードがそれぞれ同じトランザクションを相手に送り合う

Grinでオフチェーン決済するためのPayment Channelプロトコル「Elder Channel」

Mimblewimbleを実装したGrinにはBitcoinのようなスクリプト機能は存在しない。コインの所有権は、秘密鍵の役割をするPedersen CommitmentのBlinding Factorの値を知っているかどうかで、UTXOを使用する際はその値を使った電子署名が求められる。Mimblewimble/Grinにおけるコインとその使用方法については、以前GBECで解説動画を作ったので↓参照。

goblockchain.network

そんなスクリプト機能の無いGrinでオフチェーン決済をするためのPayment Channelプロトコルが今回提案されているElder Channel↓

https://gist.github.com/antiochp/e54fece52dc408d738bf434a14680988

Payment Channelを構成するのに必要な要素は、主に２つ↓

• マルチシグ
• チャネルの旧状態のトランザクションがブロードキャストされた際の対処方法

Grinの場合これをスクリプトレスで実現する必要がある。この内、マルチシグについては、Schnorr署名の公開鍵の集約特性を利用して実現できる。詳細は↓

techmedia-think.hatenablog.com

そして、旧状態のトランザクションがブロードキャストへの対処は相対的なタイムロックの仕組み（↑で解説）と、MimblewimbleならではのPedersen Commitmentの特性を利用する。現在のLightning Network（Joseph Poon & Tadge Dryjaモデル）は、旧状態をブロードキャストした場合、不正をしたユーザーが資金を全て没収されるペナルティモデルを採用しているが、Elder Channelは最新の状態を適用させるeltooモデルに近い。

Elder Channelのプロトコルは以下のようになる。

チャネルのセットアップ

アリスとボブはそれぞれ自身が所有するコミットメントを持ち寄り、それをマルチシグのコミットメントにロックするFunding Txを作成する。

この時、相手が応答不能になって資金を取り戻せないといった状況が起きないように、Close TxとSettle Txをそれぞれ作成する。

• Close TxのインプットはFunding Txのマルチシグアウトプットで、アウトプットは、同額をそのまま持つマルチシグのコミットメント。
• Settle TxのインプットはClose Txのマルチシグアウトプットで、アウトプットはその時のアリスとボブの残高を表す２つのコミットメント。

そして、Settle Txのカーネルにだけ、相対的なタイムロックが設定される。これはSettle TxのインプットであるClose Txがブロックに承認されて1440ブロック経過するまでSettle Txをブロードキャストできないという相対的なものだ。

それぞれ作成したClose TxとSettle Txに署名したら、Funding Txに署名しブロードキャストする。Funding Txが承認されるとチャネルがオープンする。

この時、Close Txのみがブロードキャストされた状態のまま資金がロックされることが内容、お互い相手のSettle Txを持つ。

チャネルの更新

オフチェーンで決済する際はチャネルを更新する。チャネルの更新は新しいClose TxとSettle Txを作成することを意味し、送金額に応じて新しいSettle Txの各自の残高を調整する。

そして、ここで不正対策を行う。古い状態のCloset TxやSettle Txがブロードキャストされるとコインが盗まれてはまずいので、お互いにRevoke Txというのを作る。このRevoke Txは前の状態のClose Txのアウトプットをインプットとし、そのアウトプットはチャネルの実体であるFunding Txのコミットメントと同じ値を再利用する。

こうすることで、古い状態のClose Txがブロードキャストされると、Settle Txのタイムアウトの期間内に、Revoke Txをブロードキャストすることで、古いClose Txの効果を取り消す。そして、最新のClose Txをブロードキャストし、その後タイムロックの期間を待って、Settle Txでチャネルをクローズする。最新の状態にはRevoke Txは存在しないので、最新のClose Txが取り消されることはない。

この仕組みにより、不正が行われた場合にそれを取り消しチャネルの最新残高の反映を可能にする。

チャネルのクローズ

最新のClose Tx、Settle Txをブロードキャストする以外に、両者が協力してチャネルを閉じるMut Txを作成する。このトランザクションのインプットはFunding Txのアウトプットで、アウトプットはそれぞれの最新のチャネル残高を反映したコミットメントになる。

大まかに↑のフローを図にすると以下のようになる。

Elder Channelの構築フロー

注意点

トランザクションカットスルー

個々のRevoke Txが分かると、永遠にClose & Revokeを繰り返し資金をロックする攻撃が可能になるので、Revoke Txとその後の最新のClose Txは個別にブロードキャストするのではなく、トランザクションカットスルーをして１つのトランザクションにしてブロードキャストする必要がある。カットスルーする分、承認時間も短縮され手数料も安くなる。

手数料

手数料について↑では触れてないが、それぞれトランザクションをブロードキャストする際に、手数料用のトランザクションと集約してブロードキャストする必要がある。

コミットメントの重複

あと１番大事なのが、一見これで正常に動作するように思えるが、Elder Chanelは各UTXO＝コミットメントの重複（同じコミットメントの値の再利用）を許可することが前提となっている。これは現在のGrin/Mimblewimbleの設計には当てはまらないので、改修が必要になる。

所感

Mimblewimbleプロトコルを採用したペイメントチャネルのプロトコルということで結構面白い。キーになってるのはRevoke Txでコインをチャネルに送り返せば元々作ってたClose Txが再利用できるという点。これはUTXOが単純なPedersen Commitmentでその特徴を上手く利用してると思う（よく思いつくなー）。

後は、LNにするにあたってHTLCとかルーティングとかの課題が残る。特に金額がコミットメントによって秘匿されている状態でルーティングどうするのか気になるところ。