Develop with pleasure!

福岡でCloudとかBlockchainとか。

Atomic Swapを拡張してオプション、証拠金、先物取引などを可能にするAtomic Swaptions

Atomic Swapプロトコルは第三者を信頼することなく、異なるブロックチェーン間で暗号通貨の交換を可能にするプロトコル。単なる暗号通貨の交換だけでなく、オプションや先物のようなデリバティブ資産の保有を希望する参加者向けにAtomic Swapプロトコルを拡張したものがAtomic Swaption↓

https://arxiv.org/pdf/1807.08644.pdf

昨年のScaling Bitcoin 2018のOlaoluwa Osuntokunのセッション「Multi-party Channels in the UTXO Model: Challenges and Opportunities」の一部でも紹介されてる↓

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

以下、Atomic Swaptionsのホワイトペーパーの意訳↓

トラストレスな取引所

Bitcoinなどの暗号通貨の安全性は暗号プロトコルに依存している。しかし、もともとそう設計されているように、異なるブロックチェーンが互いに安全に通信するための仕組みはなかった。したがって、異なる暗号通貨の取引はチェーン外で行われるか、関連するブロックチェーンの範囲外で行われてきた。取引を希望する両者は、通常は集中型の暗号通貨取引所などの信頼できる第三者に資金を預けなければならない。

集中型の取引所を信頼する必要性は、長い間暗号通貨コミュニティ内ではこまった事実であった。取引所の参加者は資金が凍結されたり、差し押さえられたり、盗まれたりすることを恐れており、それが根拠あることであることは歴史的に示されている。逆に評判の良い取引所は特定の暗号通貨の潜在的な新規ユーザー/投資家に対して独占的な力を持っているため、使用料を取り、暗号通貨の開発全般に過度の影響を与えることができる。例えば、自身の取引所でどのアルトコインをサポートするかを選ぶことができ、おそらく上場手数料を要求するだろう。新しいアルトコインの作成者はその要求を受け入れるか、評判の悪い取引所と協力してチャンスを得る必要がある。これらの摩擦は新規参加者が最初にコインを入手するのを困難にし、暗号通貨の採用に対する障害となっている。

暗号通貨のボラティリティは、暗号通貨の採用、ギャンブラーおよび投機家に対して別の障害を提供する。潜在的な利用者は金融オプションや先物市場を利用してボラティリティリスクをヘッジすることができれば、特定の暗号通貨を採用する傾向が強くなるかもしれない。例えば暗号通貨のマイナーは暗号通貨建ての収益を持っているが、一般的には既存の通貨建ての費用を持つ。しかし、デリバティブのトレードを集中型の取引所に依存すると、スポット取引業者が直面する問題と同じ問題にさらされることになる。実際、この問題は拡大するだろう。デリバティブの長期的な性質は、ユーザーが契約期間中、資産を取引所に保管しなければならないことを意味する。さらに取引所が提供するどんなレバレッジも直接的および間接的なカウンターパーティリスクを招くことになる。極端な市場変動の場合、取引所が破綻するリスクもある。

Atomic Swapにより、ユーザーは取引時に集中型の取引所に固有のリスクや不利益を回避することができる。Atomic Swapでは暗号技術を使ったエスクローの一種であるHashed Time Lock Contracts (HTLCs)を使用し、ブロックチェーン自体が信頼できる第三者として機能するようになる。別の見方をすると、Atomic Swapは暗号のシークレットを利用して、特定のイベントが別のブロックチェーンで発生したことをユーザーが1つのブロックチェーン上で証明できるようにする。

このペーパーではAtomic Swapの機能をさらに拡張してオプション契約を作成できるようにすることを示す。これをAtmic Swaptionと呼ぶ。特に当事者は元本総額の代わりに小額の証拠金のみをデポジットすることができる。これは、先物契約を可能にし、ユーザーが1つの暗号通貨でレバレッジポジションまたはショートポジションを他の通貨に対してとることができるようにする。

Atomic Swap

アリスはAコイン、ボブはBコインをそれぞれ持っているものとする。アリスとボブそれぞれが持つAコインとBコインを交換したい場合、通常はHTLCを使って各チェーンで取引を行う。手順は簡単で、

  1. アリスはシークレットxをランダムに選択し、そのハッシュ値H(x)をボブに伝える。
  2. アリスはH(x)のプリイメージxが分かればAコインをボブに支払い、有効期間T + Aを過ぎたらアリスに払い戻されるスクリプト宛にAコインを送る。
  3. ボブも同様にH(x)のプリイメージxが分かればBコインをアリスに送り、有効期間Tを過ぎたらボブに払い戻されるスクリプト宛にBコインを送る。
  4. アリスは自分だけが知っているxを使ってBコインを入手するトランザクションをブロードキャストする。
  5. ボブはアリスがブロードキャストしたトランザクションを見て、xの値を知り、それを使ってAコインを入手するトランザクションをブロードキャストする。

スワップを完了できる。

Atomic Swaption

上記のAtomic Swapでは3でボブがBコインをデポジットした後に、アリスが意図的に約束を破ることができるこのに注意する必要がある。例えばボブと合意した後に、Aコインの価格がBコインに対して上昇した場合、アリスは交換をやめるかもしれない。アリスはこの決定をタイムロックの期間Tまでに決めればいい。

※ ちなみにあくまでAtomic Swapと見た場合に、公平な交換をしようと担保型のAtomic Swapなんかの提案もある↓

techmedia-think.hatenablog.com

ただ今回はそれとは別に、それをオプション取引に利用する話。

上記のシチュエーションを言い換えるとAtomic Swapは、アリスがアリスにとって価値のある固定価格でAコインをBコインと交換することができる経済的選択肢と見なすことができる。有効期間Tが小さければ、市場価格が短期間で大きく変動する可能性は低いため、「オプション値」は一般的に小さくなる。

Tが大きければ、アリスは大きなオプション値を得る。見返りにアリスはこのスワップション契約を締結するためにボブにプレミアムを支払うことができる。問題はスワップションをプレミアムと安全に交換する方法。これはスワップションを別のAtomic Swapにネストすることで実現する。アリスはAコインでプレミアムを支払うが、Atomic Swapは任意の数のブロックチェーンを含むことができるので、任意の暗号通貨を使って支払うことも可能。

このフレームワークはいくつかのバリエーションを可能にする。例えばコンパウンド・オプションは単にオプションを原資産とするオプション取引で、HTCLsをさらにネストすることで実装できる。同様に、Collar option(カラーオプション)は複数のスワップションをトレードする代わりに、ネストすることで効率的に実装できる。discreet log contractを結ぶオプションを作成することも可能だ。ここでは、スワップションのトレーダーにとって役に立つ可能性の高い、早期キャンセルとマージンについて分析する。

早期キャンセル

アリスがスワップションを没収され、Aコインを早期に取り戻したいと思った場合、アリスとボブがスワップションをキャンセルできるよう、払い戻しトランザクションを作成することは可能だが、ボブが協力的ではなく有効期限が切れるまでアリスを待たせるケースが考えられる。代わりにアリスが別のシークレットを使ってそれを取り消すことができるようにスワップションを設定できる。アリスがスワップションの行使とキャンセルを同時に行うことができないように、資金はRevocable Sequence Maturity Contract(RSMC)に送られる。アリスの行使に対応するRSMCは、もしアリスがキャンセルトランザクションを公開したらボブがBコインを入手できるようにする。したがって、アリスがチートをしようとするとボブが罰則として全ての資金を受け取れる。

証拠金

アリスとボブは、彼らの資金の全てをコントラクトに預ける代わりに、全資金(元本)の一部(証拠金)を預けることに同意することができる。これは証拠金契約の使用で実現できる。ボブの証拠金契約はボブがスワップションコントラクトに証拠金を送ることを可能にするが、これを可能にするトランザクションはアウトプットが全元本と同額であることを求めるため、ボブは残りの資金も同様に預けるよう要求される。Bitcoinでは、SIGHASH ANYONECANPAYを使ってよく実現される。スクリプティングのルールが異なるブロックチェーンでは、ボブが最初に残りの元本をプレースホルダコントラクトに送信する必要がある。

ボブが証拠金の有効期限までにスワップションコントラクトに資金をデポジットしない場合、アリスは証拠金を受け取ることができ、シークレットを明らかにする必要もなくなる。つまり行使しないことでAコインを取り戻すことができる。アリスの証拠金契約も同様に機能するが、ボブの証拠金契約より前に有効期間切れになるはずだ。アリスが元本のデポジットに失敗した場合は、ボブはアリスの証拠金を受け取り、ボブ自身のも失う。

ブロックチェーン間の通信プロトコルとしてのHTLCの制限のためだけに、アリスの証拠金のデポジットが必要であることに注意すること。つまりボブはアリスがAコインのスワップションコントラクトに資金をデポジットしなかったことをBコインのブロックチェーン上で証明することはできない(そして、アリスは自分がAコインをデポジットしたことをBコインのブロックチェーン上で証明することはできない)。この証明が可能なら、Bコインのブロックチェーン上で行われるアリスの行使トランザクションは、アリスがAコインをAコインのスワップションコントラクトにデポジットするまで行使できないよう制限することができる。しかしAコインとBコインが同じブロックチェーン上にある場合(ERC20トークンなど)、アリスが行使を決定するまでアリスが資金をデポジットする必要が無いようコントラクトを設計することができる。

条件を交渉する際、アリスとボブはデフォルト戦略の可能性を考慮に入れるべきで、それはスワップションのペイオフ機能を変更する。アリスの証拠金と元本の比率をボブのものと同じにすることは、アリスがデフォルトに対するインセンティブを持たないことを保証するのに十分である。しかし、ボブのマージンが元本と等しくない限り、ボブのデフォルトに対するインセンティブは存在する。それを踏まえて、アリスとボブの証拠金比率を同じにして、証拠金のスワップションを設計するための2つのアプローチについて概説する。固定証拠金アプローチは本質的に「set and forget」だ。スワップションが設定されると、アリスとボブはスワップションが有効期間切れになるまで何もすることがない。変動証拠金アプローチは、コールまたはプットオプションの従来のペイオフ機能を厳密に再現しようとするが、アリスとボブの間で頻繁なやりとりが必要になる。

固定証拠金スワップション

ここでは、証拠金の有効期限Mがスワップションの有効期限(遅くともE-2)の前に設定されているので、ボブは有効期限がデフォルトになるかどうか決定する。 {m_B} {p_B}をそれぞれ証拠金と元本の量とし、 {p_A}も同様にする。スワップションの本質的な値は、証拠金のデポジット分を含まない {max(0, min(m_B, p_B −p_A))}で与えられる。これによりFigure 1に示すよじれのあるペイオフ機能が得られる。これは価格設定の目的のために2つの伝統的な選択肢に分解できる。

f:id:techmedia-think:20190407135824p:plain
Figure 1:固定証拠金スワップションのペイオフ機能。両方のグラフは同じスワップションを説明している。Aコインで示されているのはコールオプション、Bコインで示されているのはプットオプション

変動証拠金スワップション

ここでは、アリスとボブは戦略的デフォルトからの期待利益が小さいため、予め決められた閾値を下回るように必要な証拠金量を増減することで、オプションを継続的に「時価評価」することに同意できる。これは新しいスワップションを作成中に古いスワップションをアトミックキャンセルすることで行われる。証拠金の有効期限はおそらく1日から1週間の範囲の中間値Mに設定される。アリスとボブが協力すれば証拠金の有効期限が切れるまでの時間はこの値で継続的にリセットされるが、一方が協力するのを止めると、両者はデフォルトを避けるための時間が来る。Mの選択はトレードオフで、Mの値が小さいほど証拠金も小さくなり、戦略的デフォルトが発生する確率が低くなるが、非協力的なケースにおいて対応する時間は短くなる。

変動証拠金はLightning Networkのようなレイヤー2のオフチェーンスケーリングソリューションで最も効果的に実行される。不正行為の場合を除いて、ユーザーはトランザクションを公開すること無く安全なコントラクトを結ぶことができる。そうでないと、チェーン上のトランザクションを使って、スワップションコントラクトを繰り返し作成、キャンセルするのはとてもコストがかかる可能性がある。

先物

変動証拠金は、コール/プットオプションペイオフを忠実に複製するため、先物取引の作成に使用することができる。プット・コール・パリティのバージョンでは、長期の先物取引はロングコールオプションとショートプットオプション(早期行使を無視して)と同等であると述べている。言い換えると先物取引を作成するため、アリスとボブは同じ権利行使価格と満了日で同時に、アリスは1Aコインを1Bコインと交換し、ボブは1Bコインを1Aコインと交換することが可能な、2つの変動証拠金スワップションをアトミックに開始できる。アリスが両方の契約でAコインを提供しているため、この構成は重要ではない。必要な証拠金の額を最小限に抑えるため、行使価格は先物市場価格に近づけるべきだ(より正確には、満期時の予想スポット価格に)。

Lightning Networkのルーティング

この分析の多くは、1つのブロックチェーンのみを使うため処理が簡単なdiscreet log contract(DLC)のような長期契約にも適用できる。

アリスとボブが中間者を経由してスワップション契約を結ぶことも可能で、これはアリスからボブへのAコインの支払いをHashed Time Lock Contract (HTLC) で連鎖させ、Bコインの支払いをループバックさせるAtomic Swapと同じ方法で実現できる。

スワップションの各ステップはHTLCおよび/またはHTLCに送信するコントラクトで構成されているため、必要に応じてRevocable Sequence Maturity Contractsを追加することで、LNにアトミックスワップを実装するのは簡単だ。中間者の離脱は無益で、他の参加者の損失にはならない。またペイメントチャネル上でいくつかのHTLCを同時に開始できることも明らかになっている。したがって、長期のスワップションでは、スワップションコントラクトに拘束される特定の金額を超えてチャネルの運用が中断されることはない。

ペイメントチャネル内では、ユーザーはスワップションコントラクトに参加するための証拠金をまかなうのに十分な資金を持っていればいい。ただし、チャネルに十分な資金がない場合、元本を支払うためにペイメントチャネルを閉じる必要が出てくる。

三者によるデカップリングとアンワインド

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

三者のキャロルが、アリスとボブの間でAコインとBコイン両方のパスのノードとして登場する場合、キャロルは代わりにボブとの独自のシークレットを使ってスワップションをデカップルできる。この場合、キャロルはアリス、ボブ両方の取引相手として(または同様に行動する仲介者として)機能し、ネットポジションはゼロである。これによりスワップションの実行に必要な時間が短縮される(HTLC支払いのチェーンの各ステップは1タイムステップ後に期限切れになるので)。さらに、キャロルはアリスがそうするのを待たずに、一方的にボブとのロングオプションポジションを閉じることができ、それによりキャロルの資金がより早く解放される。完全に協調的な場合は、オプションのアンワインドプロセスも単純化する。

キャロルがアリスに対してロングポジションを開始するように同一の取引がアリスとキャロルを通過すると仮定する。アリスとキャロルはお互いにゼロポジションであるため、両方のスワップションがキャンセルされ、彼らの資金が不必要にロックされなようプロセスを終了するのが理想的だ。キャロルは同じシークレットを使って、アリスの(キャロルとの)スワップションの1タイムステップ後に有効期限切れになるようなアリスとのスワップションをセットすることがdけいる。その後アリスが自身のシークレットを明らかにすると、循環的なリバランスで元に戻すことができる循環的な資金の流れを引き起こす。

同様に、自己売買をすることで、2人のユーザーがコントラクトをブロックチェーンにいれずにチャネルを閉じたい時などに、既存のポジションを再ルーティングできる。これらの手法を使うことで、LN上で一連のスワップションポジションをオープニンにしたまま維持するコストを最小限に抑えることができる。

経済的考察

アリスとボブは、プロセスに内在するリスクとネットワークトランザクション手数料だけでなく、ロックされた資金の時間的価値について仲介者前任に補償しなければならないtめ、長いパスは高価になりがちである。また証拠金スワップションのデフォルトを回避するために、仲介者は十分な流動性を維持する必要があり、これを補償する必要がある。スワップション、DLCおよびその他の長期契約は全て同じネットワークの資金のキャパシティを巡って競合する。

これは、LNベースのデリバティブ取引は、密集した大規模トレーダー/取引所の少数のセットと大規模なトレーダーに直接接続した多くの小規模なトレーダーで、ほぼ集中化されることを示唆している。

同一のスワップションをアンワインドする機能は、権利行使価格や規模、有効期限などの契約条件の標準化を促進する。

実用的な考慮事項

他の長期契約と同様、ハッシュや署名アルゴリズムなど、ブロックチェーン上で緊急的なルールの変更が発生するというリスクがある。おそらく動かされないコインは燃やされる(使えなくなる)。この場合、アリスとボブにはいくつか選択肢がある。ダイナミクスは特定の契約とルール変更のタイミングに影響される。両者はおそらく、一方が他方に超過分の支払いを強要することで、新しいルールの下で協力して契約を最下位することができる。もしボブが協力しなければ、アリスは移動の期日までに行使するか取り消すかを選択しなければならず、スワップションの付帯価値を失うことになる。しかしアリスはコインが償却されるまで何もせずボブを苦しめることもでき、その後もう一方のブロックチェーンからコインを取得する。

レバレッジ取引は、オプションの価格設定式/ソフトウェアにかなり精通している必要があるため、ユーザーフレンドリーである可能性は低い。さらに、証拠金のユーザーは、証拠金が喪失されると取引相手が実質的に利益を得ることが多いので、相手が協力的であることに依存すべきではない。十分なスワップション市場を考えると、証拠金の有効期限が同時にハッセするような大きなスワップポジションを累積することで、ショートスクイズを誘導する可能性さえある。それらはLNの仲介者の長いパスを使って援助されるかもしれない。

タイムロックは意図した順序で期限切れになるよう、ブロック高ではなく経過時間を使用するように設定する必要がある。しかし、2つのブロックチェーン間で将来のブロックの相対的なタイミングを予測するのは困難である。もちろんそれが可能であれば、多くのユーザーがブロック高を使用するのを好むのは明らかではない。

法定通過にペグした暗号通貨を作成するためのさまざまな試みがある。ボラティリティを最小限に使用としているユーザーは、スワップション取引でペグされた暗号通貨の使用を好む可能性があるが、これにはもちろん基礎となるペグを信頼する必要がある。

結論

新しいブロックチェーンの設計と採用は継続的なプロセスで、その上でのアプリケーションの開発を簡単にするため、ブロックチェーンがどの操作をサポートすべきかは未解決の問題だ。アトミックスワップを実装するのに必要な機能だけで、幅広いブロックチェーン間で派生物を実装できることを実証した。このようにアトミックスワップションでは、既存の暗号通貨でのデリバティブ取引への実用的な道筋を提供し、将来のブロックチェーン設計者が特殊なデリバティブアプリケーションを作成する必要性を排除する。

A scalable drop-in replacement for merkle trees at Scaling Bitcoin 2018

Scaling Bitcoin 2018復習シリーズ。今回は、昨年もBullet Proofsなど発表したスタンフォード大学のBenedikt Bünzによる「A scalable drop-in replacement for merkle trees」の発表で、内容的にはマークルツリーの代わりにRSAアキュムレータを利用したUTXOセットの管理方法の提案↓(58分くらいから)

youtu.be

発表スライド↓

https://tokyo2018.scalingbitcoin.org/files/Day1/scalable-drop-in-replacement-for-merkle-trees.pdf

書き起こしは↓

http://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/accumulators/

UTXO

UTXOセットの成長はますます問題になってきている。現在のUTXOの数は6000万個にもおよぶ。問題は前のセッションでもあったようにUTXOのデータ構造が非効率的だということにある。古いブロックをダウンロードしたい場合、全てのブロックヘッダが必要になる。ブロックチェーンの先頭(最近のブロック)しか持っていない状況で、古いトランザクションをダウンロードし、それが使用済みかどうかチェックしたい場合、その間にあるトランザクションをすべてチェックし、そのトランザクションが使われているかどうかチェックする必要がある。

UTXO commitment

この問題を解決するために以前提案されたのがUTXO commitmentだった。全ブロックは現在のUTXOセットの状態など現在の状態へのコミットメントを取得する。このアイディアでは、実際に正しいUTXO commitmentがブロックヘッダ内に存在することをコンセンサスルールで保証する。そのため軽量クライアントはこれをチェックできる。軽量クライアントに未使用のUTXOであることを納得させたい場合は、それがUTXOセットcommitmentに含まれている証拠を提供すればよく、これをすべての軽量クライアントに対して行うことができる。

マークルツリーを使ったUTXO commitment

UTXO commitmentを実装する古典的な方法はマークルツリーを使用する方法。その時点のUTXOセットでマークルツリーを構成し、そのルートハッシュをブロックヘッダに格納する。

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

UTXOセット内に対象のUTXOが存在することを証明するinclusion proofを提供すればよく、それはlog(n)のハッシュにになる(仕組み的にはSPVクライアントで実装されている部分マークルツリーの復元と同じロジック)。UTXOセット内に対象のUTXOが存在しないことを証明するexclusion proofもlog(n)のハッシュになる(この場合UTXOセットはソートされているか、マークルツリーの幅を知っている必要がある)。

ステートレスフルノー

UTXO commitmentを利用すると完全なUTXOセットを保存する必要がないステートレスなフルノードを構築することができる。スタンドアロンで完全な検証をするがそのノードは完全なUTXOセットを持っていないという状態になる。これがどのように動作するかというと、トランザクションを送信する際に、送信者がそのトランザクションのインプットは未使用のコインであることの証明を提供する必要がある。現在はマイナーによってマイナーが管理するUTXOセットにより未使用のトランザクションであることがチェックされているが、この設計ではこれをユーザーがコインが未使用であることを証明するようになる。このアプローチの良い点は、現在UTXOセットとして4GBのストレージを必要とするマイナーも、そのUTXOセットを保持する必要なく、単にその証明を使ってトランザクションの使用コインが未使用であることを検証するだけで済むという点だ。

マークルツリーの問題点

ただ、マークルツリーを使ったこのアプローチには以下のような問題点がある。

  • トランザクション毎にinclusion proofが必要になる。
  • 主な問題としてinclusion proofをすべてのトランザクションに追加するとそれが非常に大きくなる。
    • 単純にやると600GBのサイズに
    • いろいろ最適化して160GB
  • 検証コストが大きい。

RSA アキュムレータ

そこで今回マークルツリーの代わりに提案されたのがRSAアキュムレーター。アキュムレータというのは、何らかのジェネレーターによって生成され、以下の操作、関数を持つデータ構造になる。

  • 要素の追加
    アキュムレータと要素を引数にとり、要素を追加した更新されたアキュムレータを返す。
  • 証明関数
    ある要素がアキュムレータ内に存在することを証明する証明データを生成する。
  • 検証関数
    アキュムレータと証明データを引数に取り、bool値を返す。

ブロックチェーンのUTXOの管理をアキュムレータで行う場合、さらに要素の削除をサポートする必要がある。

セットアップ

以下のようにアキュムレータをセットアップする。

  • 2つの素数の積(pqは秘密の素数N = p * qを選択する。
  • H:任意の要素を素数写像するハッシュ関数
  • アキュムレータを初期化するため群から要素を選択 {A_0 = g \in Z_n}

※ 個人的にHの素数への写像については、衝突耐性とか問題ないのか気になる。

アキュムレータへの要素の追加

アキュムレータはセット(集合)に対する小さなコミットメントとして機能する。

現在のアキュムレータ {A_i}に要素xを追加する場合、 {A_{i+1} = A_i^{H(x)}}を計算することで、要素が追加されたアキュムレータ {A_{i+1}}が得られる。

アキュムレータから要素の削除

逆にアキュムレータから要素を削除する場合、 {A_{i+1} = A_i^{1/H(x)}}を計算することで、削除後のアキュムレータ {A_{i+1}}が得られる。

ここでUTXOのセットを表現すると、アキュムレータの状態はセット内のすべての要素の積になる。セットSの全ての要素の積を {u = \Pi_{s \in S} S}とすると、そのアキュムレータは {A_t = g^{u}}となる。

このアキュムレータは良い特性の1つは要素がいつ追加されたかどうかは問題ではなく、可換である点。

inclusion proofの作成

上記以外にも良い特性がある。それがアキュムレータ内にある要素が存在するかどうかを証明するinclusion proofが非常に簡単なこと。

アキュムレータAにxが含まれていかどうかのinclusion proof πは以下になる。

 {\pi = A^{\frac{1}{x}} \in \mathbb G}

これはtraproor(落とし戸)(pとq)使って計算するか、シークレットを使って計算することができる。もしくはセットの全要素(O|S|)を知っているか。

inclusion proofの検証

inclusion proofが正しいかの検証は、アキュムレータAと要素xおよびそのinclusion proof  {\pi}が与えられ、

 {\pi^x = A}

を検証する。  {\pi}が正直に構築されているのであればxと1/xが相殺して、Aになる。

また、もしxがセット内になければ、このRSAグループにおいてこのようなオペレーションはできないという安全性上の証明がある。

exclusion proof

同様にexclusion proofも生成できるが↓、少し複雑で発表では詳細は省略されてる。

  •  {A= g^{u}}
  •  {a \cdot x + b \cdot u = gcd(x, u) = 1}

[LiLiXue07]参照となってたので、原理はそのホワイトペーパー↓読むと分かるかも。

https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf

Trusted Setupが必要

RSAアキュムレータの課題はTrusted Setupを必要とする点。Nは巨大な素数pとqの積だが、このpとqの値を知っていれば暗号スキームを破ることができる。つまり、要素がアキュムレータ内に入っていなくても、入っていると騙すことができてしまう。

また、アキュムレータから効率よくデータを削除するためにはtrapdoor(落とし戸)の情報が必要になる。古典的なスキームではこれを行うアキュムレータマネージャーの存在を前提としている。

もしくは、ロン・リベスト仮定で公開されてるNを利用するか。RSAの発明者であるロン・リベストがNを作成し、その元となったpとqを削除し誰もそれを知らない状態にする。もしロン・リベストを信頼するならそのNを使えばいい。

が、なるべくそういった信頼モデルは排除したい。

Class Group

そこで別の提案が、Class Groupという仕組みを利用するアプローチ。これはもともとGaussにより開発された数学的オブジェクト。二次体のClass Group(類群)で、位数が未知の群であり、その群に含まれるアイテムの数は分からない。RSAと同様の特性があるが、Trusted Setupを必要としない。またClass Groupの要素は、RSAの要素より少し短く約半分になるもよう。

RSAアキュムレータの現状

現状可能なこと
  • inclusion proofについては、アキュムレータ内の要素数に関係なく一定のサイズにできる(全体で3000 bitくらい)。 セットのサイズが4000を超えると、マークルツリーベースのinclusion proofより優れている。
  • 動的でステートレスな追加が可能。アキュムレータ内に何が入っているかに関係なくアキュムレータに要素の追加が行える。
  • ルノード分のストレージを必要とせず、ユーザーは自身が所有するUTXOと、そのメンバーシップ証明を保持するだけで良い。
この研究での改善および課題
inclusion proofの集約およびバッチ処理

2つのトランザクション xとyがありそれぞれinclusion proof π1とπ2を持っているとする。そして以下の式が成立するものとする。

 {\pi^x_1 = A, \pi^y_2 = A}

そしてシャミアのトリックを使いxとyのinclusion proofを {\pi_{1,2}^{x\cdot y} = A}とすることができる。

これの良いところはπ1も1.5 KB、π2も1.5 KBそして、 {\pi_{1,2}^{x\cdot y}}も1.5 KBであるという点。そして任意の数分同じことができる。そのため、1.5 KBというのはトランザクション単位のマークルパスやRSA inclusion proofではなく、ブロック内の全てのinclusion proofのサイズになる。

ステートレスなdelete処理

trapdoorを持っていれば効率的に削除が可能だが、trapdoorを持って無い場合どうなる?効率的に計算するためにモデルの変更を考える。UTXOをアキュムレータから削除するタイミングはそれが使われたタイミングなので、その際、一緒にその所有者からinclusion proofが提供されるというモデルだ。↑ではアキュムレータから要素を削除する際の計算として、 {A_{i+1} = A_i^{1/H(x)}}と定義したが、削除の際にアキュムレータと要素およびinclusion proof  {A_t, x, \pi}が提供されるのであれば、それは次のアキュムレータの値を持っていることに等しい。つまり、次のアキュムレータは {A_{t+1} = \pi}である。

ただBitcoinに適用する場合は、工夫が必要になる。ブロックには多数のトランザクションが含まれるため、同じアキュムレータに対して、複数のトランザクションおよび複数のinclusion proofが存在する。そのままでは、上記のようにinclusion proofが次のアキュムレータを指すといったことにはならない。このため、↑のようにinclusion proofの集約を行う。その結果が次のアキュムレータになる。これがBatch Deleteで、同じアキュムレータに対して多くのinclusion proofを持ち、かつそれらを一度に削除することができるようになる。

バッチ検証の高速化

よく上がる懸念はRSAはハッシュ計算なんかに比べて遅いじゃないかということ。OpenSSLで2048 bitのRSAを使用すると毎秒219回の更新になる。特にブロックチェーンの完全同期を考えた場合、ブロックチェーン全体の更新は全てのプルーフをチェックする必要があるためとても遅くなる。集約技術は証明サイズの縮小にはなるが、検証時間を短くすることにはならない。

Class Groupを使った良いベンチマークはまだ無いが、最近Verifiable Delay Function(VDF)と呼ばれるものなどに使われつつある。また最近Chia NetworkがClass Groupをスピードアップさせるか、破壊を試みる競争に10万ドルの賞金をかけたので、その結果、良い情報が得られるだろう。

他には、検証時間を短縮するのにVDFの開発で生まれたWesolowski Proofと呼ばれる技術を使うことができるという提案。そしてそれを拡張し、Proof of Exponentiationを効率的に行う仕組みを提案。

高速なブロックの検証

↑の仕組みを使って高速なブロックの検証を実現する。

マイナーが高速にブロックをコンパイルしたい場合、

  1. ブロックチェーンの現在の状態=現在のアキュムレータの状態に対して、Stateless deleteにより使用された一連のUTXOを削除する。
  2. 新しく作成されたUTXOを追加する。
  3. 以下を持つ新しいブロックをコンパイルする。
    • ブロックヘッダ
    • トランザクションのリスト
    • BLS署名
    • 前のブロックのアキュムレータ {A_t}から使用済みのUTXOを削除した {A_{t + \frac{1}{2}}}
    •  {A_{t + \frac{1}{2}}}に対して新しいUTXOを追加した {A_{t + 1}}
    • PoE(Proof of Exponentiation)

ルノードは↑の新しいブロックに対して、BLS署名の検証、以下2つのPoEの検証を行う。

 {PoE(A_{t + \frac{1}{2}}^{\Pi_{s \in S^{S}}} = A_t)}

 {PoE(A_{t + \frac{1}{2}}^{\Pi_{n \in N^{N}}} = A_{t+1})}

パフォーマンス

JavaのBigIntegerとJDKハッシュ関数を使ってmacbookで検証すると、

  • マークルツリーを使った6,400万件のinclusion proofは26個のハッシュ計算で約8.5μs。
  • マイナーがアキュムレータに要素を追加したい場合、これは少し高価になって約1.5ms。
  • Wesolowski proofを使って検証した場合、0.3μs。これはマークルツリーを使う方法よりはるかに高速。

Class Groupについては実装がなく計測できていない。

以下は、今回のRSAアキュムレータの研究の応用ネタっぽい。

Vector Commitment

Vector Commitmentはアキュムレータに似ており、マークルツリーと一緒に使うこともできる。要素 {a_1,...,a_n}vectorがあり、そのVector Commitment(VC)がある場合、ある位置でそのvector commitmentを開くことができ、vectorのこの位置にある値を伝えることができ、その証明が {\pi = Open(VC, a_i, i)}。ただこの要素の証明πを使って、要素の検証 {Verify(VC, \pi, a_i, i)}をするのが大変で、従来検証者はGB単位のメモリを必要とした。検証者がメモリを必要としない新しいVector Commitmentを構築することができる。

Short IOPs

IOP(Interactive oracle proofs)と呼ばれる高レベルなゼロ知識証明では(zk-STARKsなどもその一種)、

  1. 証明者は非常に長い証明に対する短いコミットメントを送信する。
  2. 検証者はそれに対し、いくつかのインデックスを指定する。
  3. 証明者は指定されたインデックスについて、その位置にある値を知っていることを示す証明と、マークルパスを検証者に送る。
  4. 検証者は証明を確認し、受け入れるか拒否するかを決める。

問題は3のマークルパスが非常に長いことで、これをvector commitmentに置き換える。またこの時、アキュムレータで使った技術と似た技術を使ってvector commitmentを集約することができる。これにより証明のサイズを小さくすることができる。

所感

長期的な視点で見た場合に、膨張するUTXOの管理やフルノードの負荷は課題になるので、こういったアキュムレータの取り組みは興味深い。でも↓などの気になるポイントも。

  • Trusted Setupを避けようとするとClass Groupを利用するということだけど、Class Groupの安全性やパフォーマンスについてははっきりしたデータがなく、実用可否ふくめてまだ時間かかりそう。
  • 要素の削除処理についてはバッチ処理の説明があったけど、追加についてはそういった機能は無さそうだが、実際新しいブロックができる度に多くのUTXOが新しくできる訳で、それら1つずつRSAの計算していくと結構な計算量になりそうな気がするけどパフォーマンス的に大丈夫なんだろうか?
  • 一方LNのペーパーの著者でもあるTadgeが提案しているマークルツリーベースのアキュムレータ「utreexo」のベースはツリーとハッシュ計算なので、単純な計算コストはこっちの方が速そうではある。ただ証明のサイズはRSAアキュムレータの方が固定値であり小さい。このあたりutreexoの情報が出てきたら比較してみたい。

担保付き債務を表現するHashed Time-Locked Collateral Contract(HTLCC)を定義したBIP-197

トラストレスかつ仲介機能(中抜き)を排除した方法で超過担保付き商品を作成するためにAtomic Swapを利用したAtomic Loansを提案するペーパー↓

https://arxiv.org/pdf/1901.05117.pdf

ブローカー抜きに借り手と貸し手の間でローン契約を結ぶ際に、担保を設定した債務契約を結ぶにあたって、

  • 正常に返済されれば担保は解消され
  • デフォルト or 返済されない場合に
    • 両者が合意して担保を入札にかけて精算する。
    • 両者が合意しない場合は、担保の一定割合を差し押さえ精算する。

といったコントラクトを、HTLCを拡張したHashed Time-Locked Collateral Contract(HTLCC)で実現しようというBIP提案。担保をBitcoinブロックチェーン上でBTCとして2つのHTLCCスクリプトにロックし、他のブロックチェーン上でローン資金を発行する。

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

以下BIPの内容↓

概要

Hashed Time-Locked Collateral Contract(HTLCC)は2つのスクリプトで構成される。このスクリプトは指定された参加者(借り手)が、ローンの元本が別のブロックチェーン上の通貨建てである債務契約に担保として、指定された期間、資金をBitcoinブロックチェーンにロックすることを許可する。ローン元本が発行されたブロックチェーンを元本ブロックチェーンと呼ぶ。

スクリプトの目的は、2人の参加者(借り手と貸し手)の間で債務契約を作成できるようにすることで、担保はP2SHにロックされ、借り手が元本ブロックチェーン上で元金を返済し債務契約の利息を支払った後でのみ使用可能になる。借り手が返済をしない場合、借り手または貸し手は担保の精算を選択することができ、これにはローン通貨と担保のAtomic Swapが含まれる。両者のうち、どちらか一方が精算を選択しない場合、両者は資金が最初にP2SHにロックされた際に決定された担保の一定割合を受け取る権利がある。

これらの資金は2つのスクリプトにロックされる。Refundable CollateralスクリプトとSeizable Collateralスクリプトだ。これらのスクリプトに送られた資金は、返済が失敗し参加者が精算を選択しない場合の各参加者が権利を有する担保の割合を表す。

Refundable Collateralスクリプトは以下のような形式になる:

OP_IF
  OP_SIZE <シークレットB2の長さ> OP_EQUALVERIFY [HASHOP] <シークレットB2のハッシュ> OP_EQUALVERIFY OP_DUP OP_HASH160 <借り手の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
  OP_IF
    <ローンの有効期間> [TIMEOUTOP] OP_DROP OP_SIZE OP_PUSHDATA(1) <シークレットA2の長さ> OP_EQUALVERIFY [HASHOP] <シークレットA2のハッシュ> OP_EQUALVERIFY OP_SIZE <シークレットB3の長さ> OP_EQUALVERIFY [HASHOP] <シークレットB3のハッシュ> OP_EQUALVERIFY OP_2 <借り手の公開鍵> <貸し手の公開鍵> OP_2 OP_CHECKMULTISIG
  OP_ELSE
    <精算の有効期間> [TIMEOUTOP] OP_DROP OP_DUP OP_HASH160 <借り手の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG
  OP_ENDIF
OP_ENDIF

Seizable Collateralスクリプトは以下のような形式になる:

OP_IF
  OP_SIZE <シークレットB2の長さ> OP_EQUALVERIFY [HASHOP] <シークレットB2のハッシュ> OP_EQUALVERIFY OP_DUP OP_HASH160 <借り手の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
  OP_IF
    <ローンの有効期間> [TIMEOUTOP] OP_DROP OP_SIZE <シークレットA2の長さ> OP_EQUALVERIFY [HASHOP] <シークレットA2のハッシュ> OP_EQUALVERIFY OP_SIZE <シークレットB3の長さ> OP_EQUALVERIFY [HASHOP] <シークレットB3のハッシュ> OP_EQUALVERIFY OP_2 <借り手の公開鍵> <貸し手の公開鍵> OP_2 OP_CHECKMULTISIG
  OP_ELSE
    OP_IF
      <入札の有効期間> [TIMEOUTOP] OP_DROP OP_SIZE <シークレットA1の長さ> OP_EQUALVERIFY [HASHOP] <シークレットA1のハッシュ> OP_EQUALVERIFY OP_DUP OP_HASH160 <貸し手の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG
    OP_ELSE
      <差し押さえ有効期間> [TIMEOUTOP] OP_DROP OP_DUP OP_HASH160 <借り手の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG
    OP_ENDIF
  OP_ENDIF
OP_ENDIF

[HASHOP]、OP_SHA256OP_HASH160のいずれか。

[TIMEOUTOP]は、OP_CHECKSEQUENCEVERIFYOP_CHECKLOCKTIMEVERIFYのいずれか。

対話

  • アリス(借り手)とボブ(貸し手)は、アリスが作成した2つのシークレットのハッシA1, A2、ボブが作成した3つのシークレットのハッシュB1, B2, B3を交換する。両者はその後、ローンの期間(Loan Period)、精算期間(Liquidation Period)、差し押さえ期間(Seizure Period)のタイムアウト閾値について合意する。アリスはRefundable Collateral Contract と Seizable Collateral ContractのスクリプトおよびそのP2SHアドレスを作成する。ボブはローンの元金が発行されるブロックチェーン、元本ブロックチェーンスクリプトを構成する。
  • ボブは元本ブロックチェーンのローンスクリプトに元本の資金を送金する。
  • アリスはRefundable Collateral P2SHアドレスとSeizable Collateral P2SHアドレスに資金を送る。アリスが2つのアドレスに送金する金額は事前にアリスとボブの間で決定される。
  • その後は以下のいずれかのパターンになる:
    • ボブがアリスによる担保のロックを受け入れると、ボブはB1を明らかにし、アリスが元本ブロックチェーン上のローンの元金を引き出すのを可能にする。
    • ボブがアリスによる担保のロックを受け入れない場合、承認期間後にB2を明らかにして資金を回収する。これによりアリスにRefundableとSeizableの担保を返金できる。
    • ボブがアリスによる担保のロックを受け入れたその後は、以下のいずれかのパターンになる。
      • アリスはローン期間の終わりまでにローンを返済し、ボブはローン返済受け入れトランザクションでアリスにシークレットを明らかにする。
      • アリスがローンをデフォルト(債務不履行)し、アリスとボブ両者が担保精算を選択する場合、第三者が担保に入札することができる。入札で勝利したチャーリーは、担保資金(Refundable CollateralのP2SHとSeizable CollateralのP2SHの両方にロックされたBTC)と入札資金(チャーリーが入札に拠出したローン通貨建ての資金)をAtomic Swapし、精算担保を受け取る。これはアリスとボブがマルチシグに署名し、A2とB2を公開することで行われる。
      • アリスがローンをデフォルト(債務不履行)し、アリスとボブのどちらかが担保精算に同意しない場合、アリスはRefundable Collateralの資金を回収し、ボブはSeizable Collateralの資金を使用する。
      • アリスがローンをデフォルト(債務不履行)し、アリスとボブのどちらかが担保精算に同意せず、かつボブがSeizable Collateralの資金を使用していない場合、アリスはRefundable Collateralの資金とSeizable Collateralの資金両方を回収する。

互換性

BIP 197はEthereumのERC および Atomic Loans と互換性がある。将来的には他のHTLCおよびスマートコントラクト互換チェーンと互換性を持つよう拡張することができる。

動機

多くの異なるプロトコルでは、シークレットを明らかにすることがセトルメントの仕組みとして利用されている。HTLCCトランザクションは非協力的な相手から一定の割合の担保資金を回収し、元本 + 金利 + 精算手数料を当事者と協力して支払わせるため、債務契約の状態を進めるためにシークレットを交換する安全な方法である。

定義

借り手:借り手の借入承認後に、Bitcoinチェーンに担保をロックし、貸し手から元本ブロックチェーンの貸付金額を受け取るエンティティ

貸し手:Bitcoinチェーンに担保をロックし貸し手の承認後に、借り手が借りる元本ブロックチェーン上のHashed Time-Locked Principal Contract (HTLPC)に資金を提供するエンティティ。

返済:借り手がローンの期間の前に元本+利息を返済する場合

デフォルト:借り手がローンの期間の前に元本+利息の返済に失敗した場合

シークレット:債務契約の状態を変更できるように明らかにされる、借り手もしくは貸し手によって選択された乱数

シークレットのハッシュ:HTLCCの構築に使われるシークレットのハッシュ

シークレットA1:借り手によって生成されるシークレットで、借り手がローンを引き出したことの証明に使われる

シークレットA2:借り手によって生成されるシークレットで、入札者が精算した担保資金を引き出すのに使われる

シークレットB1:貸し手によって生成されるシークレットで、借り手による担保のロックを受け入れ、借り手がローン資金を引き出すのを可能にするのに使われる

シークレットB2:貸し手によって生成されるシークレットで、借り手に寄る担保のロックに不満がある場合に、ローン資金を返金するのに使われる。借り手による元本+利息の返済を受け入れる際にも使われる。

シークレットB3:貸し手によって生成されるシークレットで、入札者が精算される担保資金を引き出すのに使われる。

シークレットC:入札者によって生成されるシークレットで、担保の精算の承認のために借り手と貸し手の署名を受け入れるのに使われる。

ローンの有効期間:借り手がローンを返済しなければならなくなるまでのタイムスタンプ、もしくは、担保の精算、差し押さえのリスク。

入札の有効期間:差し押さえ有効期間が始まる前の、入札に割り当てられる時間を決定するタイムスタンプ

差し押さえ有効期間:貸し手がSeizable Collateral P2SH内の資金を差し押さえることができる期間を決めるタイムスタンプで、この有効期間後、借り手は借り手が権利を有する対応する額の担保(Refundable Collateral P2SH内の資金、もしくは貸し手が差し押さえに失敗した場合はRefundable CollateralとSeizable Collateralの両方)を払い戻しできる。

承認期間

この間、貸し手はHTLPCを元本ブロックチェーン上にデプロイする。続いて、Bitcoinブロックチェーン上のHTLCCに担保をロックする。貸し手は担保の内容に問題がなければシークレットB1を明らかにし、借りてはシークレットA1を明らかにすることでローンを引き出すことができる。貸し手が担保の内容に不満がある場合は、シークレットB2を明らかにすることでローン資金の払い戻しを受ける。また借り手はシークレットB2が明らかになることで、デポジットした担保資金の払い戻しを受けられる。

ローンの有効期間

一旦、借り手がローン資金を引き出すと、ローン期間が始まる。ローン期間が終了すると借り手によるローンの返済が期待される。借り手からの返済があった場合、貸し手はシークレットB2を明らかにすることで返済を受け入れることができ、借り手は担保資金の払い戻しを受けられる。借り手がデフォルトしたか、元本+利息を返済しない場合、貸し手はローンの返済を受け入れないことを選択でき、両者は入札期間中に担保の精算を選択することができる。

入札の有効期間

デフォルト、もしくは貸し手が借り手の返済を受け入れない場合、両者は第三者の入札者による担保への入札プロセス通して、担保の精算を選択することができる。入札の期間は貸し手、借り手のどちらからでも開始できる。入札期間が過ぎると、借り手と貸し手はそれぞれ署名を提供しなければならず、署名が適切あることを確認したら入札の落札者によってシークレットCが明らかにされる。最後に貸し手と借り手は落札者が担保を引き出せるようにシークレットA2とシークレットB3をそれぞれ明らかにしなければならない。

差し押さえ期間

借り手もしくは貸し手のどちらかが入札に応じない場合は、貸し手は担保の一定割合を差し押さえることができる。その金額はこのBIPで説明されているように、Seizable CollateralスクリプトとRefundable Collateralスクリプトにロックされている担保の金額によって異なる。この期間中、借り手はRefundable Collateralスクリプトにロックされている資金の払い戻しを受けることもできる。

払い戻し期間

貸し手がSeizable Collateralスクリプトにロックされた担保を差し押さえない場合、借り手はRefundable Collateralスクリプトにロックされた資金の払い戻しを受けられる(Seizable Collateralスクリプトの間違いような気が)。

論拠

以下のスクリプトOP_SHA256に使われるスタックにプッシュされたシークレットの長さをチェックするのは、

OP_SIZE <secret b2 length> OP_EQUALVERIFY

シークレットのサイズが特定のバイト長であるであることを保証するためである。

sha256 opcodeが32バイトしかしめず、残りを無視するEthereumのような他のチェーンで、このスクリプトがHTLPCと一緒に使われる場合、これは特に重要になる。Bitcoin側のサイズが32バイトであることを確実にする必要がある。

後方互換

これは担保付き債務の新しい標準であるため、後方互換性は必要ない。これが標準と認められると、同じ最大ブロックサイズを持つ2つのブロックチェーンで使われている場合はハッシュのサイズを検証する必要がなくなるなど、後方互換を保ちながら変更可能なコントラクトの特定の側面がある。

実装

https://github.com/AtomicLoans/chainabstractionlayer/blob/bitcoin-collateral-provider/src/providers/bitcoin/BitcoinCollateralProvider.js

BEAMが提供する監査機能

MimblewimbleではPedersen Commitmentにより取引する量が秘匿され、さらにスクリプトがなくPedersen CommitmentのBlinding Factorがそのコインの所有権を証明するキーになる。そのため、Perdersen Commitmentを見ただけでは誰から誰へのいくらの送金なのかは分からない。

そんなMimblewimbleをサポートするブロックチェーンの1つがBEAMだが、BEAMではウォレットが当局向けの監査機能を提供する↓

https://github.com/BeamMW/beam/wiki/Wallet-audit

ウォレットが提供する監査機能

監査機能を提供するBEAMのビジネスウォレットはどのように監査機能を実現しているのか?

監査人向けの鍵ペア

ビジネスウォレットは監査用に公開鍵/秘密鍵のペアを作成する。この鍵ペアの内、公開鍵のみが監査人に渡される。監査人が複数いる場合は、その監査人の数分、鍵ペアが作成される。

監査人はこのこの公開鍵を使って、ユーザーのトランザクションをトラッキングする。

トランザクションへのタグ付け

監査人がユーザーのトランザクションをトラッキングできるようにするために、ビジネスウォレットはトランザクションにタグ付けを行う。

BEAMのMimblewimbleトランザクショントランザクションカーネルに Excess(Blinding Factorの総計)とSchnorr署名の一部であるnonceがセットされるようになっているが、同様にトランザクション毎のカーネルを利用して、そこにタグをセットするようにしている。この時、監査人が複数いる(監査用の公開鍵が複数ある)場合、その数分タグは作られる。また、取引相手にも監査人がいる場合は、その公開鍵の分のタグもセットされる。

タグの内容

この時付与するタグは以下のように、トランザクションカーネルのExcessと、監査用の公開鍵、秘密鍵を使ってビジネスウォレットにより計算される(Hはハッシュ関数、|は結合を表す)。

  1. nonce = H(カーネルのExcess | 監査用公開鍵) * 監査用秘密鍵を計算する。
  2. タグはNonce2 = nonce * G

↑のように計算されタグはトランザクションカーネルKernel.Signature.Nonceにセットされる。

監査人は、フルノードを実行し全ブロックのデータをダウンロードする必要がある。そして、各ブロックのトランザクションカーネルにセットされているタグについて、自身の監査対象かどうかを検証する。この検証は監査人が持っている監査用の公開鍵を使って以下のように検証される。

  1. Nonce = H(カーネルのExcess | 監査人が持つ監査用公開鍵) * 監査人が持つ監査用公開鍵
  2. 計算したNonceがブロック内のトランザクションカーネルにセットされているKernel.Signature.Nonceと一致すれば、それが監査対象のトランザクションと識別できる。

※ 任意のデータ(カーネルのExcess | 監査用の公開鍵)を監査用秘密鍵に乗算した生成したのたタグの秘密鍵で、タグはそれに対応する公開鍵で任意のデータを監査用の公開鍵に乗算することで得られる。

このあたりの仕組みはステルスアドレスのアプローチに似てる。

トランザクションの詳細情報へのコミットメント

上記のタグに加えて、トランザクションの詳細情報へのコミットメントもトランザクションカーネルに追加する。

トランザクション詳細のコミットメントの作成

トランザクションの詳細情報とは以下の情報を指す。

  • トランザクションのインプット/アウトプットの内、ビジネスウォレットが所有するインプット/アウトプット
  • 上記インプット/アウトプットの所有権の証明と金額
  • トランザクションに関連する任意のデータ
TxDetail = {自分のインプット+署名、自分のアウトプット+署名、その他任意のデータ}

このTxDetailをデータとし監査用秘密鍵を使ってHMACハッシュ値を計算する。

Nonce1 = HMAC(監査用秘密鍵, TxDetail)

続いて、nonce1を使って以下を計算する。

PrivateKey = Nonce1 * H(G * Nonce1 | TxDetail)

算出したPrivateKeyにGを乗算したものをKernel.Excessにセットする。

Kernel.Excess = G * PrivateKey

上記のようにトランザクションの詳細情報へのコミットメントが作成され、トランザクションカーネルに付与される。

監査人によるコミットメントの要求

監査人は以下の検証を行う。

  1. 監査人はタグによりマッチするトランザクションを確認したら、ユーザーに対してトランザクションの詳細情報と対応するG * Nonce1を要求する。
  2. 監査人がユーザーからトランザクション情報を受け取ったら、それが本当にトランザクション作成時に作られたコミットメントと一致するか検証する。
    具体的には、(G * Nonce1) * H(G * Nonce1 | TxDetails)を計算し、それがKernel.Excessか検証する。それが一致すれば提供されたトランザクション詳細はコミットメントを作成する元となった情報であることがわかる。
  3. トランザクションの詳細情報にあるインプット/アウトプットのUTXOがブロックに存在するか検証する。
  4. 使用されたインプットが、以前受け取ったトランザクション詳細のアウトプットの中に存在することをチェックする。
  5. インプットを使用済みとマーキングし、アウトプットをUTXOとして認識する。

上記のようにコミットメント方式を利用して、トランザクションの詳細情報をやりとりしている。

監査人ができること/できないこと

上記のように監査人はタグにより監査対象のユーザーのトランザクションを識別し、その取引の詳細情報を照会しコミットメント合致するか検証する。

提供されるトランザクション情報から、ユーザーが所有するインプットとアウトプットの情報が明らかになる。各UTXOの所有権は電子署名により証明されるため、自身が保有しないUTXOを自分のものであると申告することはできない。また、インプットは必ずそれより前に自分のアウトプットであると申告したものであることから、監査人はユーザーのトランザクショングラフを構築することができる。

逆にできないことは、トランザクションアウトプットが本当は自分が所有するものにも関わらず、トランザクションの詳細に含めなかった場合、そのUTXOは監査人から認識されなくなる。そのUTXOは監査外で使用することができる。ただし、その決済は監査を受けたものとは認められず、またそのUTXOを使用するトランザクションを監査対象に含めた場合、そのUTXOの出処となるアウトプットが監査人に認識されていないため、不正なアウトプットと認識される。つまり、監査を受けたUTXOは合法的に取引可能で、監査を受けていないUTXOは合法的に取引できなくなる。

所感

現状、ZcashはMoneroなど匿名通貨は日本の取引所では扱われていない。匿名通貨により通貨のトラッキングができず、ダークウェブやマネロンの温床になるという危険性は分かる。一方で、個人のプライバシーや通貨のFungibilityといった側面が犠牲になる。そういったなんとも言えない状況において、BEAMのような匿名機能を持つ通貨がこういった監査機能を提供するのは重要な要素かもしれない。BEAMが提供するのはあくまでオプトインな監査機能だが、当局にとって必要な監査のレベルとプライバシー/Fungibilityとのバランスとそれを技術的にどう担保するかについてはもっと議論が必要になってくると思う。

OP_CODESEPARATORは廃止の流れか?

Bitcoin開発者の1人であるMatt Coralloが提案するコンセンサスルールのクリーンナップ↓

https://github.com/TheBlueMatt/bips/blob/cleanup-softfork/bip-XXXX.mediawiki

まだBIPにはなってないが、このクリーンナップの内容の1つがOP_CODESEPARATORの廃止だ。

OP_CODESEPARATORとは?

OP_CODESEPARATORはあまり見かけることがないopcodeの1つだが、これはOP_CHECKSIGで署名検証する際にscriptPubKeyの一部だけをチェックするために使われる。

署名検証の手順

例えば通常OP_CHECKSIGの署名検証は以下の手順で実行される。

  1. 公開鍵と署名データがスタックからポップされる。
  2. この時署名のフォーマットはDER形式で、署名データの最後にはSIGHASH_TYPEの値が付与されている。
  3. 署名からSIGHASH_TYPEを取り除き、保持する。
  4. 現在のトランザクションをコピーしたtxCopyを作成する。
  5. コピーしたtxCopyの全インプットのscriptSigを空にする。
  6. 署名検証対象のtxCopyのインプットに、subScript(後述)をセットする。
  7. SIGHASH_TYPEの値によってtxCopyの内容を調整する。
  8. txCopyをシリアライズし、double-SHA256する。
  9. 生成したハッシュ値とスタックからポップした公開鍵を使って署名の検証を行う。

subScriptとscriptCode

OP_CODESEPARATORが関連してくるのは、↑の手順6で出てくる該当インプットにセットするsubScriptの部分。subScriptは実際に実行されたコード = scriptCodeから作成される。

scriptCodeは、

  • 非Segwitの場合
    • P2SH以外はscriptPubkeyそのもの
    • P2SHの場合はそのredeem script
  • Segwitの場合
    • P2WPKHの場合は、witness programをP2PKHスクリプトに変換した0x1976a914{20-byte-pubkey-hash}88ac
    • P2WSHのの場合は、witness script = Segwitにおけるredeem script

となる。ほとんどの場合、scriptCodeがそのままsubScriptになるわけだが、scriptCodeスクリプト内にOP_CODESEPARATORが含まれている場合だけ勝手が違ってくる。

OP_CODESEPARATORの作用

スクリプトOP_CODESEPARATORが含まれる場合、最後にパースされたOP_CODESEPARATORからスクリプトの最後までがsubScriptになる。

例えば次のようなOP_CODESEPARATORを3つ含むscriptCodeがあった場合、

[スクリプトパート1] OP_CODESEPARATOR [スクリプトパート2] OP_CODESEPARATOR OP_DUP OP_HASH160 <受信者の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG OP_CODESEPARATOR [スクリプトパート4]

スクリプトインタプリタOP_CHECKSIGを評価する際、最後にパースしたOP_CODESEPARATORは2つめのOP_CODESEPARATORになるため、それ以降のスクリプト↓がsubScriptになる。

OP_DUP OP_HASH160 <受信者の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG OP_CODESEPARATOR [スクリプトパート4]

そして、subScript内のOP_CODESEPARATORは全て除去されるため、最終的なsubScript

OP_DUP OP_HASH160 <受信者の公開鍵ハッシュ> OP_EQUALVERIFY OP_CHECKSIG [スクリプトパート4]

となり、これが署名対象のSignature Hashを生成する際のトランザクションのインプットにセットされることになる。

※ 但し、BIP-143が適用されるSegwitスクリプトでは、subScript内の全OP_CODESEPARATORの削除は行われない。

OP_CODESEPARATORの用途は?

OP_CODESEPARATORの動作は分かったとして、この複雑な機能はいったい何のためにあるのか?という疑問が湧き、2011年にbitcointalkでスレッドが立つも有用なユースケースは見つかっていない。

bitcointalk.org

コメント頂きました。

アリスが、ボブが支払い条件を満たすトランザクションを公開しBOB_HASHのプリイメージを取得したい以下のようなスクリプトを考える。

OP_DEPTH 3 EQUAL
OP_IF
    2 <ALICE_KEY_PAYMENT> <BOB_KEY_PAYMENT> MULTICHECKSIGVERIFY HASH160 <BOB_HASH> EQUAL
OP_ELSE
    <ALICE_KEY_REDEEM> CHECKSIG CLTV DROP
OP_END

ただ、<ALICE_KEY_PAYMENT>と<ALICE_KEY_REDEEM>の鍵が同じであった場合、ボブはBOB_HASHのプリイメージを公開することなくアリスの署名を使ってコインを入手できるためよろしくない。

↑のスクリプトOP_CODESEPARATORを使うことで以下のように変更することができる。

<ALICE_KEY>
OP_DEPTH 3 EQUAL
OP_IF
    OP_SWAP <BOB_KEY_PAYMENT> CHECKSIGVERIFY HASH160 <BOB_HASH> EQUAL OP_CODESEPARATOR
OP_ELSE
     CLTV DROP
OP_END
CHECKSIG

↑のスクリプトでは<ALICE_KEY_PAYMENT>と<ALICE_KEY_REDEEM>が同じ<ALICE_KEY>として扱われるが、OP_IFの分岐とOP_ELSEの分岐でアリスが提供する署名は、OP_CODESEPARATORにより署名対象のトランザクションダイジェストの値が変わるため、最初のスクリプトのようにボブが不正をできなくなる。

結果、アリスがOP_IFとOP_ELSE分岐で同じ公開鍵を使用することで公開鍵1つ分(=33バイト分)スクリプトデータを削減することができる。というのがOP_CODESEPARATORの用途として提案されている。

実際、上記の提案では、SegwitのスクリプトOP_CODESEPARATORが利用できれば問題ないということで↓の非標準化は実現された。また、このユースケース自体はスクリプト全体を公開することなく、スクリプトの実行ブランチのみを公開する)MASTが利用可能になれば代替可能になる。

Bitcoin Core 0.16.1以降は非標準に

Bitcoin Core 0.16.1では以下のプルリクにより、非Segiwtなスクリプトにおいて、スクリプト内にOP_CODESEPARATORが含まれている場合、非標準トランザクションとみなし、リレーされなくなる。

github.com

そのため、現在標準トランザクションとしてOP_CODESEPARATORが利用できるのは、SegwitのP2WSHもしくは、PS2SH-P2WSHのみ。

OP_CODESEPARATORの弊害

↑のようにOP_CODESEPARATORを使うと署名対象のSignature Hashのデータを変更することができるため、大量の署名操作と共に悪用すると署名検証にえらい時間がかかるトランザクションを作成することが出来てしまう恐れがある(最悪30分とか)。

Bitcoin Core 0.16.1によりリレーされにくくなったとは言え、有用な用途もなく悪用される可能性のあるopcodeは廃止しようという流れだ。

本当に廃止される?

Bitcoin Core 0.16.1以降では非標準トランザクションとして判定されるものの、コンセンサスルールでは許可されてるため、廃止するにはソフトフォークが必要になる。OP_CODESEPARATORに限らず、Matt Coralloのクリーンナップの提案には無効なSIGHASH_TYPEを無効判定にするなどの提案もある。これらを有効化した場合、まだブロードキャストされていないが、それらの条件を使用した署名済みのトランザクションが保持されていて、かつその署名を作成した秘密鍵にアクセスすることができなくなってしまっている場合にコインを喪失する懸念がある。このようなユーザーがいる場合、ソフトフォークがアクティベートした後はそれらのトランザクションがブロックに取り込まれなくなるため、資金は永遠に失わえる。

そういった懸念から、OP_CODESEPARATORの数をトランザクションweightに加味するようなソフトフォークにした方がいいのでは?という提案もあるが、これをどう判断しBIPとするか課題は残る。