Statechainsから発展したSparkではどのようにUTXOの分割を行っているのか？

Table of Contents

概要

Spark¹はStatechains²の派生プロトコルです。元のStatechainsは、オフチェーンで自分の持っているutxoを別のユーザーに渡すことができるようなプロトコルですが、そのutxoを分割することはできませんでした。つまり、1BTCを持っていたら0.5BTCだけを支払うということが、Statechainsでは不可能でした。

SparkではSparkツリーと呼ばれるオフライントランザクションのツリー構造を導入することで、utxoを分割して、金額の一部を別のユーザーに渡し、お釣りを自分が受け取ることができるようになっています。

また、プロトコルとして運営者が単一の秘密鍵を持つユーザーではなく、複数のユーザーの集合であることを明記しており、柔軟なフェデレーションが可能であることも特徴です（ただし、これはStatechainsでも簡単に取り入れられます）。

Statechainsの概要

Statechainsの概要については他の方の説明³⁴を読んでください。

Sparkの用語

ドキュメント¹に書いてあります。

Spark Entity (SE)

Statechainsの運営者として振る舞うユーザーの集合です。

Spark Operator (SO)

SEに属するユーザーを指します。このユーザーがn人いると仮定すると、n人中1人でも正直なユーザーがいれば、ユーザーの資金を盗まれることはありません。

Spark Service Provider (SSP)

アトミックスワップのサービスをSparkに提供するユーザーです。理論上は誰でもSSPになることができます。

Sparkツリー

SparkにおいてUTXOを分割するために構成されます。オフラインで作成されたビットコインのトランザクションで木構造になっています。末端のトランザクションは葉トランザクションと呼ばれ、中間のトランザクションは枝トランザクションと呼ばれます。

Sparkツリーを使ったUTXOの分割

Sparkツリーは以下の図のように、オンチェーントランザクションを消費する複数のオフチェーントランザクションのツリーでできています。

このツリーの左端が分割したいUTXO（オンチェーントランザクション）です。
このツリーの右端が葉トランザクションで、ユーザー間で移転されるものになります。葉トランザクションにはStatechainsで必要なタイムロックがついています。それ以外のトランザクションは枝トランザクションと呼ばれます。
一度作られた葉トランザクションから、さらに分割して新しく葉トランザクションを作成することはできません。
これらのトランザクションは残高の合計が親の枝のトランザクションの合計になっていれば、送金金額の分割方法に特に制限はありません。
中間の枝トランザクションの秘密鍵は子になる枝トランザクションの秘密鍵を足し合わせたものになっています。これによって、全ての葉トランザクションを消費しなくても、中間の枝トランザクションを消費すれば、下位の葉トランザクションをまとめた(aggregate)ものとして動かすことが可能になり、オンチェーン手数料を節約できます。（まとめたトランザクションをさらに葉トランザクションに分割するためには、過去の葉トランザクションがブロードキャストされる可能性を踏まえて再分割する必要があると思われます）
この木構造はユーザーとSEが協力して作成する必要があります。

仮に、枝トランザクション1-葉トランザクション1をアリスが保有し、枝トランザクション2-葉トランザクション2をボブが保有しているとします。また枝トランザクション1と枝トランザクション2の共通の親として枝トランザクション0が存在するとします。
葉トランザクション1をアリスがブロードキャストするためには、親トランザクションである枝トランザクション0,1のブロードキャストも必要です。しかし、枝トランザクション0,1がブロードキャストされても枝トランザクション2がブロードキャストされない限り、ボブの資金に影響を与えることはありません。
枝トランザクション2は、Sparkが正常に運営されている限りにおいて、葉トランザクション2の所有者であるボブ(+SE)と過去のutxo所有者のみがブロードキャスト可能です。

flowchart TD
    b0[枝トランザクション0] --> b1[枝トランザクション1]
    b0[枝トランザクション0] --> b2[枝トランザクション2]
    b1 --> l1[葉トランザクション1]
    b2 --> l2[葉トランザクション2]

Sparkツリーからの協力的出金(Atomic Swap)

通常の葉トランザクションをオンチェーンで出金しようとすると、全ての枝トランザクションもブロードキャストする必要があります。
SparkツリーからSSP（Spark Service Provider）を通じて協力的に出金を行うこともできます。この場合、SSPはツリーからの出金を先延ばしにすることができます。SSPはもし他の葉要素を持っていればそれらを統合して、手数料を節約できます。この協力的出金にはSSPに対するアトミックスワップの手数料が求められる可能性があり、やや中央集権的と言えます（誰でもSSPにはなれますが、流動性があるとは限りません）。

Sparkの問題点

以下は現状のSparkの問題点ですが、今後改善される可能性はありえます。Mercury Layerなどの既存のStatechainsも、中央集権的なサーバーが存在するという基本的な信頼の問題があり、それはSparkにも引き継がれています。

ユーザーの不正がSSPのコストを増大させる

前のutxoの所有者は葉トランザクションを(トランザクション手数料以外)ノーコストで公開できます。不正な引き出しトランザクションの親トランザクションが出た時点で、現在の正当なutxoの所有者はそれを検知し、自分の手元から正当な引き出しトランザクションを発行することができますが、その引き出し手数料はユーザー負担になります。

不正な引き出しトランザクションを実行するのにかかるコストは、Sparkツリーの深さをdとすると、攻撃者は d-1個分、正当な所有者ユーザーは1個分になります。

これだけ見ると攻撃者の方が余分にトランザクション料金を支払っているように見えますが、Sparkでは葉トランザクションの統合を行う際に、子トランザクションが不正に引き出されていないことが重要になるため、SSPの負担を加味すると不正を行われた場合のコストは高くなります。

なお、二重支払いの不正を試みたからといって、必ずしも二重支払いが成功するわけではなく、ツリーの他の部分には影響はありません。

送金回数に制限がある

こちらはMercury Layer⁵でも同じことが言えます。

utxoをSparkツリーを使って分割し、n個の葉トランザクションに対応したutxoができることになります。このutxoそれぞれで、独立な送金回数制限があります。
相対ロックによる管理であるため、特定の日時までに必ず手放さなければならない、というものではないですが、utxoごとに送金回数が決まっている点は変わりません。

最終的には送金回数の残り少ないutxoを受け取った場合自分でブロードキャストするか（手数料が高くなる）、アトミックスワップによる交換相手を探す（必ず相手が見つかる保証はない）必要が出てきます。

もしも特定のユーザーまたはSEの元に期限切れの直前の取引がすべて戻ってきたならばツリーの一部を統合することで、うまく単一のトランザクションにまとめ直す方法があります(¹のaggregationを参照)。しかし、そうでない場合、結局の所最終的には誰かが手数料を支払って葉トランザクションもオンチェーンに戻す必要があります。ユーザーが増えるほどまとめ直すのが困難になり、この問題が大きくなります。

なお⁶に書いてあるとおり、SIGHASH_NOINPUTが有効化されればeltooスタイルの送金回数制限がない形式のstatechainsを使うことができるようになり、このデメリットはなくなります。

手数料はそこまで安くならない可能性がある

Sparkツリーの葉utxoを受け取ったユーザーは、そのutxoが残り何回使えるのかを検証できます。もしも最大使用回数がM回で、現在の使用回数がM-1回だった場合、受け取ったユーザーは当然引き出しトランザクションを実行する必要があるので、オンチェーン手数料を受け取り時に要求することになります。すると、utxoの価値をv, オンチェーン手数料をfとして v -f の分の値しか残りM-1回時点では残っていないことになります。残り回数が1回など極端なケースでなくても、手数料を払わなければオンチェーンに戻せないことから、割引された額面でutxoが取引されることは避けられません。

よって、Sparkツリーをセットアップしてutxoを分割したユーザーは、その時点ではオンチェーン手数料を支払っていないにもかかわらず、割引された金額でしかutxoを使えないことになります。
送金時の手数料として、このような割引率を考慮したり、アトミックスワップの手数料などを考慮すると、必ずしもオンチェーンで直接取引を行うより安くなるとは限りません。

こちらも⁶に書いてあるとおり、SIGHASH_NOINPUTが有効化されればeltooスタイルの送金回数制限がない形式のstatechainsを使うことができるようになり、このデメリットはなくなります。

検閲の可能性がある

Mercury Layerにおいてはブラインド署名が用いられており、オペレーター側からは何に署名しているのかが分からないようになっています。これによりオペレータによる検閲が難しくなっています。

一方でSparkにおけるSOは特定のutxoに対して常に検閲、署名拒否を行うことができます。これはSOが鍵を正常に削除し、安全にプロトコルを使わせている（＝二重支払いを行わせない）仮定の下であっても発生しえます。SOがマークしたutxoに対してはそれ以上の転送を認めず、オンチェーン上での出金のみを認めるということが可能になります。
オンチェーン上で出金できるならば良さそうにも思えますが、理想的にはSOが選択的にutxoをマークして検閲を行うということができないような構成が望ましいです。例えば、ブラインド署名⁷のような仕組みをプロトコルにうまく導入できれば良いですが、現状ではそのようになっていません(⁸で提案中)。
chaumian ecash⁹についてもこれは同じことが言えます。