#何の話？
ビットコインは単位時間あたりに処理できるトランザクション数に限りがあります。
所謂スケーラビリティ問題です。これを解決するために、トランザクションの処理をブロックチェーンの外で行うマイクロペイメントチャネルというアプローチがあります。
invalidation tree とは、双方向マイクロペイメントチャネルの基本構造です。
元の論文は
A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels
#前提知識
- 単方向マイクロペイメントチャネルの知識
- トランザクションのタイムロックの知識
- マルチシグの知識
- ( segwit の知識 )
#準備
それぞれ 1BTC 保持している Alice と Bob が、双方向(Alice ⇔ Bob)で資金のやりとりをすることを考えます。双方向にやり取りを行うには、単方向のマイクロペイメントチャネルを2つ作れば良いはずです。ここで、
Cab : Alice ⇒ Bob の単方向チャネル
Cba : Bob ⇒ Alice の単方向チャネル
と定義します。各チャネルでの資金の初期状態は以下の通りです。
Cab: Alice(1BTC), Bob(0BTC)
Cba: Alice(0BTC), Bob(1BTC)
ここで、Alice ⇒ Bob へ 1BTC の支払い、Bob ⇒ Alice へ 0.5BTC 支払いを行うと、以下の様に変化します。
Cab: Alice(0BTC), Bob(1BTC)
Cba: Alice(0.5BTC), Bob(0.5BTC)
現在、Alice の保有資金は 0.5BTC、Bob は 1.5BTC ですが、Cab の Alice の資金が枯渇してしまっているため、Alice は資金を保持しているのにも関わらず、Bob へ送金することが出来ません。
#双方向マイクロペイメントチャネル
invalidation tree とは、簡単に説明すると単方向チャネルをリセットする仕組みです。
上記の Cab, Cba を以下のようにリセットします。
Cab: Alice(0.5BTC), Bob(0BTC)
Cba: Alice(0BTC), Bob(1.5BTC)
この時、以前のチャネルを invalidate ( 無効に ) する必要があります。
invalidation tree では、タイムロックを利用して invalidate しています。
A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels から
図では invalidation tree の深さは d = 3 になっています。
d は 1 でも問題ないです。d が大きいとリセット回数の上限が増えます。
●は Alice, ○ は Bob, 
←こんなやつがマルチシグです。
四角形はトランザクション、T はロックタイムです。
図右端の、micropayment channels が単方向ペイメントチャネルになります。
その結果、一番右の は、マルチシグですが仮想的に 1 つのパーティに資金が保有されている形になります。
図では 3 回リセットが起こり、計 4 回のパスが発生しています。
1 回目 : 100 - 100 - 100
2 回目 : 99 - 100 - 100
3 回目 : 99 - 99 - 100
4 回目 : 99 - 99 - 99
一番タイムロックが短い 99 - 99 - 99 のパスのみが有効になります。
例えば、100 - 100 - 99 のようなパスは組めません。T = 100 ロックタイムのトランザクションのアウトプットを T = 99 ロックタイムのトランザクションが参照する ( UTXO を利用する ) ことは出来ないからです。