Develop with pleasure!

福岡でCloudとかBlockchainとか。

Taroのアセットツリーの構造

Taro Bitcoin Lightning network

Lightning Labsが発表したBitcoin上の新しいアセットプロトコルTaroについて、今回はTaroのアセットツリー周りのデータ構造/表現についてみていく。

Taroのアセットツリー

Taroは、Taprootを利用したアセットのオーバーレイプロトコルになる（TaprootベースのオーバーレイプロトコルはTaroがおそらく初）。なのでTaroを理解する場合、Taprootの知識があった方がいい↓

Taprootのアウトプットは32バイトの公開鍵だが、この公開鍵は、内部公開鍵（Key-Path）とスクリプトツリー（Script-Path）で構成されている。Taroのアセットは、この内、スクリプトツリー内の構造化されたデータへのコミットメントとして表される。

Taroのアセットツリーは、Merkle-Sum Sparse Merkle Treeというデータ構造のツリーになる↓

techmedia-think.hatenablog.com

Taroのアセットツリーは、以下のような2階層のMS-SMTで構成される。

Taro Asset Tree

1階層めは、アセットIDまたはアセットキーファミリーをキーとしたMS-SMT。このツリーのリーフの値は↓

taro_version || asset_id_tree_root || asset_sum

つまり、アセットIDをキーにして、対応するアセットの合計量（asset_sum）と、asset_id_tree_rootをルートとする2階層めのツリーのルートコミットメントおよびtaro_versionから構成されるリーフノードをマッピングしている。

そして2階層めが、アセット毎に作成されるMS-SMT。キーはAsset Script Keyで、リーフは、asset_leafとリーフが保持するそのアセットの量（leaf_sum）で構成される。つまり、あるキーが保持しているアセットの残高を保持するツリーになる。

asset_leaf || leaf_sum

asset_leafは、TLV形式のデータで、以下のデータが現在定義されている。

  • taro_version：使用するTaroのバージョン
  • asset_id：アセットID
  • asset_type：アセットのタイプ（0：通常のアセット、1：収集品）
  • amt：このリーフが保持するアセットの量
  • lock_time：アセットを移動可能なタイムロック
  • prev_asset_witnesses：ネストされたTLVで、対象となるアセットリーフへのマージを検証するためのアセットwitnessを含む。
  • split_commitment：通常のアセットについて、新しいアウトプットの分割の検証を許可するために使用。
  • asset_script_version：以下のTLV値の検証を方法を管理する2バイトのアセットスクリプトバージョン。
  • asset_script_key：このアセットリーフを包含するアセットスクリプトにコミット可能なBIP341方式で導出された外部公開鍵。
  • asset_family_key：BIP340で定義された32バイトの公開鍵、で、assert_idに対する64バイトのBIP340署名が続く。
  • TODO（まだ作業中っぽい）

なお、Asset Script Keyは、BIP341形式の32バイトの公開鍵。なので、2階層めも1階層めと同様に高さ256のツリーになる。

↑のようにアセットの保持状況をネストしたMS-SMTにエンコードして、そのルートハッシュをTaprootのスクリプトツリーにコミットしてるっぽい。

アセットID

↑で既に登場してるけど、オーバーレイプロトコルとしてアセットプロトコルを定義する場合、各アセットを識別するためのIDをどう導出するかを決める必要がある。Taroでは、アセットIDは以下のように計算される32バイトのデータになる。

asset_id = sha256(genesis_outpoint || asset_tag || asset_meta || output_index || asset_type)

ここで、

  • genesis_outpoint: アセット発行トランザクションで使用されるインプットが参照するUTXOのOutPoint。
  • asset_tag: 特定のアセットを表現するランダムな32バイトの値。複数のアセットを１つのアセットファミリーとしてリンクする際に使用されるタグで、実際にはアセット名のハッシュ値が設定される。
  • asset_meta: 外部リンクやドキュメント、属性値、画像などのメタデータにコミットするために使われるメタデータのハッシュ値（32バイト）。
  • output_index: ジェネシストランザクション内で一意なTaroコミットメントを含むアウトプットのインデックス（4バイト）
  • asset_type: アセットのタイプ（1バイト）

この内、genesis_outpointによってアセットIDの一意性が担保される。

参考

次は、アセットの作成や転送の仕組みについて。

Fiat-Shamir変換の安全でない適用による脆弱性Frozen Heart

Cryptography zk Bulletproof PlonK vulnerability

最近公開された、Fiat-Shamir変換を正しく適用できていないプロトコルや実装において、証明システムの偽造が可能になる脆弱性「Frozen Heart」について↓

blog.trailofbits.com

Fiat-Shamir変換とは？

Fiat-Shamir変換は、証明システムを非対話型にするために使用される有名なスキームで、検証者がランダムに選択するチャレンジの値を（ランダムオラクルモデルとして）暗号学的ハッシュ関数を使って決定論的に導出することで、証明システムのプロトコルを非対話型にする。

シンプルな適用例としては、RFC8235として定義されているSchnorr署名を使って離散対数の知識を知っていることをゼロ知識で証明するプロトコルとか↓

techmedia-think.hatenablog.com

RFC8235の概要は↓（簡略化のため、modの計算や群内の存在確認などは省略）

アリスがP = aGとなる公開鍵Pに対する離散対数（a）の知識をボブに証明したい場合。以下のステップで非対話的に証明する：

  1. アリスはランダムな値vを選択し、V = vGを計算
  2. アリスは暗号学的ハッシュ関数（H）を使ってチャレンジ c = H(G || V || P || UserID || OtherInfo)を計算する。
  3. アリスはr = v - c * aを計算
  4. (P, V, r)をボブに送る。

これに対しボブは、渡された情報（P, V, r, UserID, OtherInfo）からcを計算してV = rG + cPが成立するか検証する。

チャレンジcの値をボブがランダムに作って渡すのではなく↑のようにルールに従って生成することで、チャレンジのやり取りの対話を省略することができる。

Fiat-Shamir変換のポイント

↑のレポートにかかれているけど、Fiat-Shamir変換を適用する際のポイントは、チャレンジのハッシュ計算の際の入力に、証明するステートメントに関するすべての公開値（ランダムなコミットメント値を含む）を含める必要があるということ（↑の例だと入力は、G、V、P、UserID、OtherInfo）。

Frozen Heart

Frozen Heartは、↑のFiat-Shamir変換のポイントを遵守していないプロトコルや実装による脆弱性。

↑のRFC8235の例で考えてみよう。例えばチャレンジの計算にVが含まれていないとどうなるか？

  1. チャレンジ c = H(G || P || UserID || OtherInfo)を計算する。
  2. rにランダムな値を設定する。
  3. V = rG + cPを計算する。

こうやって後付けで辻褄があうように算出したVを含む(P, V, r)を検証者に送ると、V = rG + cPのチェックをパスすることが分かる。この時、証明者はV = vGとなるVの離散対数vを知らず、Pの離散対数aも知ることなく、検証をパスする証明を作成できてしまう。

Vがチャレンジのハッシュ計算に含まれていれば、こういった偽造はできない。これが↑のFiat-Shamir変換をする際の重要なポイント。

Frozen Heartの影響を受けるプロトコル/実装

Frozen Heartの脆弱性があるのは、プロトコル自体やその実装が、↑Fiat-Shamir変換のポイントを正しく行っていないケース。

↑のレポートでは、Giraultの知識証明と、値の範囲証明によく使われているBulletproofs、zk-SNARKベースの証明システムPlonKにおける脆弱性が取り上げられている。中でも影響度が大きいのは、BulletproofsとPlonKだろう。

Bulletproofsは、元の論文の非対話型プロトコルに問題があり、楕円曲線の群の位数の範囲内の値に対して証明の偽造が可能で、対象としていた範囲外の値に対して有効な範囲証明が作れてしまう。対象のプロダクトとしては、 Adjoint, Inc.のbulletproofsが取り上げられている。ちなみにMoneroの実装では脆弱性は回避されてるっぽい（Grinはどうなんだろう？）。偽造方法の詳細について、後続のレポートで解説されてる。

PlonKは、論文でFiat-Shamir変換の計算方法を明示的に説明せず、transcriptをハッシュ化するよう記載しており、その内容を明示的に記載していないことから、Dusk Networkのplonk、iden3のSnarkJS、ConsensysのgnarkでFrozen Heartの脆弱性が報告されている。具体的には算術回路への入力値をFiat-Shamirの計算に含めなかったことで、証明の偽造が可能になっていた。つまり、プログラムが正しく実行されたことが保証されなくなってしまう。具体的な偽造手順は、後続のレポートで解説されてる。

PlonKに限らず他の論文でもメインの内容は証明システムの新しい発明であって、それを非対話型にするのにFiat-Shamir変換を使うことがおまけ的に書いてあることは多いので、論文だけ読んでプロダクト実装しても脆弱性が含まれるケースは十分考えられる。zkは機能面ばかりフィーチャーされる傾向にあるけど、透過的なプロトコルと比べて脆弱性やバグがあっても発見し辛いので、このあたりのトレードオフはちゃんと評価する必要がある。

Ed25519で決定論的な鍵導出をサポートするBIP32-Ed25519

Cryptography EdDSA BIP

Bitcoinのウォレットなどが、単一のマスターシードから多数の鍵ペアを決定論的に導出する仕様を定義したのがBIP-32↓

techmedia-think.hatenablog.com

これは、Bitcoinが採用している楕円曲線secp256k1とECDSAを前提に作られた仕様になる。

これに対して、EdDSA（Edwards-Curveデジタル署名アルゴリズム）の一種であるEd25519においても、BIP32と同様の決定論的な鍵導出を可能にする提案の１つがBIP32-Ed25519↓

https://raw.githubusercontent.com/LedgerHQ/orakolo/master/papers/Ed25519_BIP%20Final.pdf

Ed25519

Ed25519は鍵の導出方法がsecp256k1と異なり、これがBIP-32をそのまま利用できない原因でもある。

鍵生成

Ed25519は以下の手順で秘密鍵と公開鍵を生成する。

秘密鍵は、32バイトのランダム値で、これをxとする。公開鍵はこの秘密鍵を使って以下のように計算される。Gを曲線のベースポイント、nを曲線の位数とする。

  1. SHA-512を使って秘密鍵をハッシュし、その値を {k = H_{512}(x)}とする。
  2. kの下位32バイトを {k_L}とし、上位32バイトを {k_R}とする。公開鍵の導出に使用するのは、 {k_L}のみ。
  3. {k_L}のデータに対して以下を行う。
    • 先頭バイトの下位3 bitをクリアする。
    • 最終バイトの最上位bitをクリアする。
    • 最終バイトの最上位から２つめのbitをセットする。
  4. 3のデータをリトルエンディアンで整数として解釈してスカラー値sとする。
  5. Gに対してスカラー値sをスカラー倍算する（sG）。
  6. 公開鍵Pは点sGをエンコードしたもの。sGのy座標を32バイトのリトルエンディアンのバイト列としてエンコードする。最終バイトの最上位bitは常に0で、x座標の最下位bitを最終バイトの最上位bitにコピーする。

こうして生成されたのが公開鍵になる。

秘密鍵からSHA-512で64バイトのハッシュしたけど、半分の {k_R}使ってないじゃん？って思うけど、これは署名生成の際に使用される。

署名生成

メッセージMと公開鍵Pに対する署名は以下のように作成される。Schnorr署名の一種なので、基本的にはSchnorr署名の計算。

  1. {H_{512}(k_R || M)}を計算し、結果をリトルエンディアンの整数rとして解釈する（なお、 { r = r \mod n}）。
  2. R = rGを計算する。
  3. {h = H_{512}(R || P ||M)}を計算し、64バイトのダイジェストをリトルエンディアンの整数として解釈する。
  4. {s = (r + h \cdot k_L) \mod n}を計算する。
  5. R || sが署名データ

Schnorr署名と違うのは、Schnorrがnonceの選択に乱数を使うのに対し、Ed25519は、 {k_L}とメッセージMのハッシュからnonceを生成している。そのため署名生成に乱数を必要としない。

署名検証

R || sおよび、P、Mが与えられた検証者は、以下の検証を行うことで署名の有効性をチェックする。

  1. {h = H_{512}(R || P ||M)}を計算し、64バイトのダイジェストをリトルエンディアンの整数として解釈する。
  2. {8sG = 8R + 8h \cdot A}が成立するか検証する（Ed25519のco-factorが8であるため）。

BIP32採用の問題

secp256k1のECDSAの場合、秘密鍵xに対応する公開鍵は、単純にベースポイントに対してスカラー倍算したP = xG。公開鍵Pに対してQ = yGを加算した公開鍵Z = P + Qを導出すると、Zに対応する秘密鍵は x + yになるという特性がある。

そのため、公開鍵から新しい公開鍵を導出することができ、元の公開鍵に対応する秘密鍵を知っていれば、導出した公開鍵の秘密鍵を知ることができる。なので、オンラインのECサイトには公開鍵だけ置いといて、支払いの度に新しい支払いアドレスを導出し、秘密鍵はオフラインで管理し、必要な場合に対象の秘密鍵を計算して利用するといったユースケースが可能になる。

これに対し、Ed25519の場合、公開鍵は秘密鍵のSHA-512ハッシュ値の下位32バイトを細工して出来た値をスカラー倍算した値になるため、↑のような特性がない。これがEd25519にBIP-32をそのまま採用できない理由。

BIP32-Ed25519

ただ、Bitcoinみたいに1人のユーザーやシステムが多数の公開鍵を使用するようなケースなど、同じシードから鍵やIDを多数生成したい場合、BIP-32のような決定論的な鍵導出スキームの需要がある。Ed25519でもBIP-32を少し変更することで、これに対応したのがBIP32-Ed25519。

ルート鍵

まず、ランダムに選択した32バイトのマスターシークレットをxとする。

  1. SHA-512を使ってマスターシークレットをハッシュし、その値を {k = H_{512}(x)}とする。
  2. kの下位32バイトを {k_L}とし、上位32バイトを {k_R}とする。 {k_L}の最終バイトの最上位３つめのbitがゼロでない場合、マスターシークレットを廃棄してやり直す。
  3. {k_L}のデータに対して以下を行う。
    • 先頭バイトの下位3 bitをクリアする。
    • 最終バイトの最上位bitをクリアする。
    • 最終バイトの最上位から２つめのbitをセットする。
  4. 得られた {(k_L, k_R)}のペアを拡張ルート秘密鍵とし、 {P = k_LG}をルート公開鍵とする。

鍵の導出手順から分かるように、拡張ルート秘密鍵とルート公開鍵は、Ed25519と鍵としても使えるもの。

そしてBIP-32のルートチェーンコードを {c = H_{256}(0x01 || k)}とする。

子鍵

ルート鍵は、 {2^{32}}個の子鍵（インデックスi \in 0..{2^{32} - 1}）を持つ。

子秘密鍵の導出

親のチェーンコードを {c^{P}}、拡張秘密鍵を {k^{P} = (k^{P}_L, k^{P}_R)}、公開鍵を {P^{P}}とした場合、i番目の拡張秘密鍵は以下のように計算される。

  1. インデックスに応じて、チェーンコードをHMACの鍵として、以下の計算を行う：
    • {i \lt 2^{31}}の場合
      {Z = HMAC(0x02 || P^{P} || i, c^{P})}
    • {i \ge 2^{31}}の場合
      {Z = HMAC(0x00 || k^{P} || i, c^{P})}
  2. Zの左28バイトを {Z_L}、右32バイトを {Z_R}とする。
  3. 子の拡張秘密鍵を {k_L = 8Z_L + k^{P}_L}とし、 {k_R = (Z_R + k_R^{P}) \mod 2^{256}}とする。 {k_L}が位数nで割り切れる場合、その子は破棄する。
  4. 子のチェーンコードは、
    • {i \lt 2^{31}}の場合
      {c_i = HMAC_{512}(0x03 || P^{P} ||i, c^{P})}
    • {i \ge 2^{31}}の場合
      {c_i = HMAC(0x01 || k^{P} || i, c^{P})}

そして、対応する子どもの公開鍵は {P_i = k_LG}。

※ {Z_L}だけ28バイトにトリムしているのは、子の {k_L}の最終バイトの最上位2 bitめが常に1であることを保証するためらしい。

子公開鍵の導出
  1. ↑の子秘密鍵の場合と同じようにZを計算する。そのため、BIP32と同様、 {i \ge 2^{31}}の強化導出の場合、親の拡張秘密鍵を知らないと導出できない。
  2. {P_i = P^{P} + 8Z_LG}を計算する。
  3. ↑の子秘密鍵と同様に子のチェーンコードを算出する。

↑からBIP32-Ed25519では、本来の鍵xではなく、拡張秘密鍵 {k = (k_L, k_R)}を使って鍵導出をしている。公開鍵を親の {k_L}に対して加算処理をすることで、親密鍵→子秘密鍵（子公開鍵）、親公開鍵→子公開鍵（親の公開鍵は {k_LG}で既知であるため）の導出をできるようにしていることが分かる。

そして、すべての拡張鍵がEdDSAの仕様で定義されるように特定のビットのセット、クリアが行われるようになってるっぽい。

SLIP-0010

BIP32-Ed25519とは別に、異なる曲線で異なる秘密鍵を決定論的に導出する仕様がSLIP-0010として提案されていて、Ed25519も対象に含まれている↓

https://github.com/satoshilabs/slips/blob/master/slip-0010.md

ただ、この仕様では、Ed25519については親公開鍵→子公開鍵の導出はサポートしていない。

Merkle Sum Sparse Merkle Tree

Cryptography Bitcoin

先日、Olaoluwa Osuntokunが発表したTaprootを利用したアセットオーバーレイプロトコルTaro↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020196.html

今回はその構成要素の１つであるMerkle Sum Sparse Merkle Tree（MS-SMT）の仕様についてみてみる↓

https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-ms-smt.mediawiki

MS-SMTは、Sparse Merkle TreeとMerkle Sum Treeを組み合わせたマークルツリーの一種。これらそれぞれのツリー構造自体は、Plasmaなど既存のプロダクトで既に採用されてる仕組みでもある。

Sparse Merkle Tree

Sparse Merkle Tree（SMT）というのは、key-valueのマップをマークルツリーにエンコードしたマークルツリーの一種。

通常のマークルツリーとの違いは、

  • ツリーのリーフノードの値はkey-valueマップのエントリー値になっており、そしてキーに対応するエントリー（ツリーのリーフノード）がどこにあるかは、キーをビットに展開し、ツリーのルートを0としてその左の子ノードを0、右の子ノードを1として、ツリーを上から下にキーのビットに対してリーフノードまで降りていくことで特定することができる。
  • キーに対応するエントリーが存在しない場合は、空の値がリーフノードにセットされる。空のリーフノードにはTaroの場合H(nil || nil || 0)がセットされる。

Taroではキーの値はSHA256値なので、キーは256 bitの範囲の値になる。このキースペースを持つツリーの深さは256で、 {2^{256}}個のリーフノードを持つ。

↑の仕様から、Sparse Merkle Treeにはマークルツリーにはない以下の特性を持つ。

  • キーから、対応するエントリーがツリー内のどの位置にあるかが分かる。
  • 効率的に非包含証明を作成できる。
    エントリーの値が空であることと、その空の値までのマークルプルーフを提供することで、あるエントリーがツリー内に存在しないことを証明する非包含証明を提供できる。
    通常のマークルツリーで、ある要素が含まれていなことを証明しようとすると、ツリーの全てのリーフを公開する必要があり効率的ではない。

ビットマップを利用した最適化

非包含証明は、キーに対応した空のリーフノードが存在することを証明するため、空のリーフノードまでの兄弟ノードのリストをマークルプルーフとして提供する。しかし、空のリーフノードのハッシュ値は既知のデータであり（H(nil || nil || 0)のように）、その空ノード同士の親ノードのハッシュ値も事前に計算可能な既知の値になるため、マークルプルーフから

  • 空ノードのノード値を除外し
  • 代わりに経路のどのノードが空でないかを示すビットマップを追加する

ことで、マークルプルーフのデータスペースを節約することができる。

Merkle-Sum Tree

Merkle Sum Sparse Merkle Treeのもう１つの特性がMerkle-Sum。

通常、マークルツリーのリーフノードの値は要素のハッシュ値で、親ノードは2つの子ノードのハッシュ値を連結してそれをハッシュした値を自身のハッシュ値として、これをルートまで繰り返すことでルートハッシュを得る。

Merkle-Sum Treeというのは、この時単に要素のみにコミットするのではなく、その要素の属性の合計にもコミットするタイプのマークルツリー。Taroでは、8バイトの合計値（sum）を持つ。

例えば要素Aが100、要素Bが50の2つのリーフがあるとすると、その親ノードのハッシュ値は、

ParentAB = SHA256(H(A) || H(B) || (100 + 50))

さらにその親ノードABCDがある場合、同様の計算が行われ、以下のようなツリーになる。

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

MS-SMT

MS-SMTは、↑のSparse Merkle TreeとMerkle-Sum Treeを組み合わせたツリー。

Taproでは、↑のMS-SMTツリーを使ってアセットツリーを構成し、そのルートハッシュをコミットメントとしてTaprootのスクリプトツリーに配置するようになってる*1。

そんなアセットを保持したTaprootアウトプットを転送する際に、

  • アセットの以前の所有者がアセットツリー内でアセットにコミットしていないこと
  • 新しいアセットが作成されていないこと（アセットのインフレーションが発生していないこと）

を証明するため、非包含証明と、Merkle-Sumの特性から非インフレーションの証明にMS-SMTを利用するっぽい。

Taroのこのあたりの仕様については、また別途。

*1:そのため、オンチェーン上でアセットツリーやアセットの情報が直接的に記録されることはない。この辺りのアプローチはRGBとかも同じ

1つのUTXOの所有権を複数人でシェアするCoinPool

CoinPool Bitcoin Payment Channel

Lightning Networkなどの現在主流のペイメントチャネルプロトコルはいずれも2人で1つのUTXOの所有権を管理するプロトコルだけど、N（N > 2）人で1つのUTXOの所有権を管理できるようにするプロトコルがCoinPoolで、少し前にホワイトペーパーが公開された↓ので、内容を見ていこう。

https://coinpool.dev/v0.1.pdf

CoinPool

CoinPoolは、LNなどのプロトコルや運用から得られた教訓をもとに、UTXOの所有権を共有するこで新しいスケーラビリティ構造を提案するプロトコルになる。CoinPoolではN人のプール参加者のコインを１つのUTXO（プール）で管理する。つまりN人が１つのUTXOの所有権を共有することになる。そしてこのプールについて、以下の基本的な機能を提供する。

  • 参加者はプール内で、オフチェーンで資金の転送ができる（プール内の資金の配分を変更できる）。
  • 参加者は、他の参加者の承諾なしに、いつでもプールから抜けることができる。

そして、高度な機能として、ペイメントチャネルなどのコントラクトでの使用や、LNや他のプールのユーザーとの取引に使用することができる。

セットアップ

N人の参加者はUTXOを持ち寄って、CoinPoolをセットアップする。まずN人の参加者はキーキャンセルができない方法を使って、それぞれの公開鍵（N個の公開鍵）を加算して集約公開鍵Pを作成する。セットアップでは、以下の3種類のトランザクションを作成する。

f:id:techmedia-think:20220320160335p:plain
CoinPoolのセットアップ

Setup Tx

各メンバーのUTXOをインプットとして、単一のUTXOに参加者の資金をロックするトランザクション。このアウトプットをPre-CoinPoolアウトプットと呼ぶ。Pre-CoinPoolアウトプットは、参加者全員の鍵から計算した集約公開鍵Pにロックされる。

Update Tx

プールの状態を表すトランザクションで、Setup TxのPre-CoinPoolアウトプットをインプットとし、アウトプットは以下の支払いパスを持つTaprootアウトプット（CoinPoolアウトプット）になる。

  • Key-Path: 参加者全員の集約公開鍵P
  • Script-Path: 以下のアンロック条件を持つ。
    • 参加者全員が協力してUpdate Txを更新する際に使用する条件
    • N個の各参加者毎の引き出し条件
Withdraw Tx

これは各参加者が、他の参加者の許諾なしにプールを抜ける際に使用するトランザクションで、各参加者の人数分作られる。

Update TxのCoinPoolアウトプットをインプットとし、以下の２つのアウトプットを持つ。

  • CoinPoolから抜ける退出者の金額をロックしたアウトプット
  • 退出者を除いた残りのCoinPoolの残高をロックしたアウトプット
    • このアウトプットのscriptPubkeyは、Update TxのCoinPoolアウトプットからCoinPoolから抜ける参加者の条件を削除したもの。

途中で資金がロックされることがないように、署名はWithdraw->Update->Setupの順に行われる。

実際のTx構成の例は、以下で公開されてる

gist.github.com

プールの更新

プール内のユーザー間でコインを送金する場合は、新しいUpdate Txと送金後のバランスを反映したWithdraw Txのセットを作成することでオフチェーンで送金が完了する。

古い状態のUpdate Txがブロードキャストされるようなことがあれば、ブロードキャストしたユーザーがWithdraw Txで引き出す前に（タイムロックされてる間に）、eltooの仕組みにより最新のUpdate Txに置き換える。

プールからの引き出し

プール参加者は、他の参加者の許諾なしにいつでもプールから退出（引き出し）できる。

退出する参加者は、

  1. 最新のUpdate Txをブロードキャストする。
  2. 続いて、自身のWithdraw Txをブロードキャストする。
    • ただし、Update TxのCoinPoolのUTXOをWithdraw Txで使用する際はタイムロックが付与されているので、Update Txがブロックに格納されてから一定期間待つ必要がある。
    • タイムロックが経過したら他の参加者が署名済みの自身のWithdraw Txに自身の署名を追加してブロードキャストする。

この結果、退出する参加者のプールの残高は、Withdraw TxのUTXOとして利用可能になり、残りのプール参加者には同様にプールから退出するかプールに留まるかの選択肢がある。

  • プールから退出する場合は、このWithdraw TxのCoinPool UTXOをインプットとしてプールから抜ける。
  • 継続する場合は、Snapshot Txを作成＆ブロードキャストし、これまで事前署名したWithdraw Txの署名を無効にする。Snapshot TxはWithdraw TxのCoinPool UTXOをインプットとし、残ったプールメンバーの集約公開鍵にコインをロックするトランザクションでSetup Txと似たトランザクションになる。当然ながら、Snapshot Txに署名する前に、後続となるUpdate TxおよびWithdraw Txのセットを作成し先に署名しておく必要がある。

Bitcoinに必要な機能追加

CoinPoolプロトコルは、現在のBitcoinプロトコルでは実装ができず、Bitcoinに以下の機能を追加する必要がある。

OP_MERKLESUB

OI_MERKLESUBは、Update TxおよびWithdraw TxのCoin Poolアウトプットの各ユーザーの引き出し条件のスクリプトに使われる。これは、プールからのユーザーの退出にあたって、

  • プールから退出するユーザーの引き出しに使用する条件ブランチが新しいCoinPoolアウトプットのTapScriptのツリーから削除されている。
  • プールから退出するユーザーの公開鍵が新しいCoinPoolアウトプット集約公開鍵から削除されている。

ことを保証する必要があり、その検証をするために新たに追加されるopcodeになる。このopcodeの仕様案は↓

https://github.com/ariard/bips/blob/coinpool-bips/bip-merklesub.mediawiki

SIGHASH_GROUP

Withdraw Txの2つのアウトプットの量が、それぞれ

  • 元々プール参加者全員が合意した退出ユーザーの残高であること
  • 残りのプールのCoinPoolアウトプット量はプールの量から退出者の残高を差し引いた額と等しいこと

を保証する必要がある。これを事前署名時にコミットするために新しいSIGHASHタイプであるSIGHASH_GROUPが必要になる。この具体的な仕様は↓

https://github.com/ariard/bips/blob/coinpool-bips/bip-group.mediawiki

SIGHASH_ANYPREVOUT

Update Txの更新にeltooスタイルで行うため、SIGHASH_ANYPREVOUTが必要になる。

また、Taprootアウトプットとして構成されるCoinPoolアウトプットのTapscriptでは、ツリーのリーフブランチに各ユーザーの引き出しが可能な条件が設定されている。このリーフを2社間のペイメントチャネルで利用可能にすることで、CoinPoolのスケーラビリティは大きく向上する。ただ、CoinPoolのステート（Update Tx）は随時更新されるため、このリーフレベルのペイメントチャネルを有効にするためには、特定のステートにロックされることがないよう、SIGHASH_ANYPREVOUTによりペイメントチャネルの参照先のUpdate Txを切り替えられる必要がある。