Develop with pleasure!

福岡でCloudとかBlockchainとか。

冗長的な支払経路を用いることでLN支払のスループットを向上させるBoomerang

Lightning Networkで決済可能な金額は各チャネルのキャパシティに依存する。この制限を緩和するため、支払に複数の経路を使用するAtomic Multi-Path Payments(AMP)が提案され、各ノードに実装されつつある。AMPの仕組みについては以前書いた↓参照。

techmedia-think.hatenablog.com

このAMPを利用した支払の経路に冗長性をもたせることで支払のレイテンシースループットを向上させようという提案が最近発表された↓ので、どういう内容か見てみる。

https://arxiv.org/pdf/1910.01834.pdf

AMPの課題

AMPは(OG AMPもBase AMPも)、全ての経路の支払の準備が出来るまで支払の受け取りを開始しない仕組みになっている。

例えばアリスからボブに4コインを送金するのに、1コインずつ4つの経路を使ってAMPで送金する場合。

  • 経路1: →
  • 経路2: →
  • 経路3: →→→→
  • 経路4: →

経路1,2,4は1秒でHTLCの転送が完了するのに対し、経路3は4秒かかったとする。この場合全てのHTLCの転送が完了した段階でボブはコインのクレームを実行するので、経路3の転送を受信するまで経路1,2,4はアイドル状態になる。つまりこの送金における送金完了までに時間=TTC(Time-to-completion)は4秒で、消費されるコインの流動性は、4 · 4 s = 16 · sとなる。

AMPでは複数の経路を使用した支払のアトミック性を担保するために、「最後まで全て待つ」という方針を掲げているが、遅延した経路がいるとその分レイテンシースループットが犠牲になる。

Boomerang

↑の課題に対して、AMPの複数の経路に冗長性を持たせることで、レイテンシーを削減し、スループットを向上させようというのがBoomerangプロトコル

上記の4コインの送金を1コインずつ8つの経路を使って支払をする。この場合、4つの経路が冗長であるため、8つの経路の内、4つの経路のHTLCの転送が成功すれば送金完了で、ボブは余分なコインは盗めないと仮定する。

  • 経路1: →
  • 経路2: →
  • 経路3: →→→→
  • 経路4: →
  • 経路5: →
  • 経路6: →
  • 経路7: →→→→
  • 経路8: →

6つの経路が1秒で転送完了し、2つの経路が4秒かかったとすると、送金のTTCは1秒で、消費されるコインの流動性は、4 · 1 · 1 s + 2 · 1 · 1 s + 2 · 1 · 4 s = 14 ·sとなり、冗長的な支払によりTTCが削減でき、結果的に消費される流動性が少なくなり、より高いスループットが得られるというもの。

Boomerangプロトコル

↑のような冗長経路を採用した場合に必要な仕組みが、ボブが元の送金額より余分に受け取ろうとするカウンターパーティリスクなくすこと。ここに秘密分散の仕組みを利用する。

アリスとボブは、送金する資金をv個のTxに分割して送金すること、u個の冗長性をもたせることに合意するものとする。この時トランザクションの総数はw = v + u

ボブはまず、ランダムな値 {α_0, ..., α_v}を選択する。そしてこのランダム値を係数とした次数v多項式P(x)を作成する。

 {P(x) = \sum^{j}_{j=0} α_{j} x^{j}}

続いて、ボブは多項式の各係数 {α_0, ..., α_v}を一方向関数Hにかけた値を計算し、その値 {H(α_0), ..., H(α_v)}をアリスに提供する。

ここで、Hは {g \in \mathbb G, H(α) = g^{α}}とした場合 {H(cα + dβ) = H(α)^{c} H(β)^{d}}の関係が成立する準同型性を持つ一方向関数。

アリスは受け取った {H(α_0), ..., H(α_v)}とその準同型性を利用して、多項式P(x)を評価するハッシュを計算できる↓

 {h_i = H(P(i)) = H(\sum^{v}_{j=0}α_{j}i^{j}) = \Pi^{v}_{j=0}H(α_{j})^{i^{j}}}

こうしてi個め経路でのチャンレンジとして {h_i}を使うHTLCタイプの転送コントラクトを構成する。

このような転送を受信したボブはi個めの経路のコインを受け取るために、 {h_i}のプリイメージを明らかにする。もしボブがここで、v個以上の {h_i}のプリイメージを明らかにすると、アリスはラグランジュ多項式補完を使って {α_0, ..., α_v}を計算することができる。そしてこの {α_0}は、送金額を取り戻すことができるシークレットとして機能する。ただし、ボブがv個より多くのプリイメージを明らかにしなければ、アリスは {α_0}を計算することはできない。

このように冗長性を持たせた経路を用いた支払において、相手が余分な償還を行った場合、それを取り消すことができるよう、秘密分散の仕組みを利用することでカウンターパーティリスクに対処しているのがBoomerangプロトコルの特徴だ。

Boomerangコントラクト

上記を実現するBoomerangコントラクトの結果は以下の3つのいずれかになる。

  • 転送がクレームされずタイムアウトを迎えアリスに資金が戻る。
  • 転送が条件が満たされボブによりプリイメージが公開されると、この経路がアクティベートされ資金がRetaliation Txに送られる。Retaliation Txのコインの使用方法は以下のいずれかになる。
    • アリスがボブの余分な引き出しのプルーフ(↑の {α_0})を提出した場合、資金はアリスに戻る。
    • 設定されたタイムアウトを過ぎ、それまでにアリスによるプルーフの提出がない場合、資金はボブのものになる。

なお、現状のBitcoinには↑のような準同型性を持つ一方向関数Hは存在しないため、Bitcoin Scriptを使って実現する場合は、スタックから要素xを取り出し、xGをスタックに戻す新しいopcodeECEXP<g>Bitcoin Scriptに追加する必要がある。

ペーパーではこれをeltooのペイメントチャネルに適用する方法について書いてる↓(Eltooの仕組みについては、以前解説したGBEC動画参照

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

eltooのSettlement Txに、HTLC転送のアウトプットを追加し、そのアンロック条件が↑のタイムアウトによる送信元への返金か、プリイメージ公開によるRetaliation Txへの送金。単純なeltooプロトコルではSettlement Txのみで完結したてけど、アリスがボブの超過引き出しに対応するため、Retaliation Txが作られ、ここで一定期間ボブのコインの入手がロックされ、その間超過引き出しがあれば、そのプルーフの提出により、すべての送金を取り消しできるようになっている。

Adaptor Signatureの利用

↑の場合、新しいopcodeがBitcoinに追加されなければ実現できないが、代わりにAdaptor Signatureを使うことでScriptlessに同様のことができるようになる。SchnorrベースのAdaptor Signatureでも可能だし、やろうと思えばECDSAベースのものもある。