2019-05-11

BitcoinにTaprootを導入するBIPドラフトbip-taproot（BIP-341）

先日、Bitcoinの開発者MLでPieter WuilleがTaproot、Schnorr署名およびマークルブランチをベースとしたコインの使用ルールである新しいSegwitバージョン1のアウトプットタイプを提案した↓

https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki

Taprootの概要については以前書いた↓参照。

techmedia-think.hatenablog.com

これを具体的にBitcoinに取り込むための仕様を定義したのが今回のbip-taprootで、Taprootアウトプットの構成方法や使用時のルール（BIP 143とは異なる新しいトランザクションダイジェストアルゴリズムも導入）などを定義している。尚、このドラフトではTaprootの構造的な仕様を定義しており、Taprootのアウトプット内のスクリプトがどのように動作するかのルールについては別のドラフト（bip-tapscript）に定義されている。

以下、BIP-341訳。追記：2020/08/04 時点の内容で以下の内容を更新

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

概要

このドキュメントではTaproot、Schnorr署名やマークルブランチに基づく使用ルールを使った新しいSegwit version 1のアウトプットタイプを提案する。

動機

この提案は新しいセキュリティ仮定を追加することなく¹、Bitcoinのスクリプト機能のプライバシーや効率性および柔軟性を改善することを目的としている。具体的には、アウトプットの作成時もしくは使用時にオンチェーンで明らかになるトランザクションアウトプットの使用可能条件に関する情報を最小限に抑え、マイナーではあるが長年の課題を修正する多くのアップグレーの仕組みを追加しようとしている。

設計

Bitcoinのスクリプト機能を改善するための多くのアイディアがこれまで提案されてきた。Schnorr署名（BIP340）やマークルブランチ（MAST, BIP114, BIP117）、新しいsighashモード（BIP118）、CHECKSIGFROMSTACKのような新しいopcode、Taproot、Graftroot、G'rootやインプットを跨いだ署名の集約など。

これらすべてのアイディアを単一の提案にまとめるのは大きな変更であり、レビューをするのが難しく、そうでなければ途中で実現されていたかもしれない新しい発見を見逃す可能性がある。またすべてが同様に成熟しているわけではない。例えば、インプットを跨いだ署名の集約は、アップグレードの仕組みと複雑な方法で相互作用し、その解決策はまだ流動的だ。一方、すべての個々の独立した提案に分割すると、効率とプライバシーの利点が減少し、ウォレットやサービスプロバイダーが多くのインクリメンタルな更新をしない傾向がある。したがって機能とスコープクリープのトレードオフに直面している。この設計では、Taprootとマークルブランチによって提供される構造スクリプトの改善と、それらを使用可能かつ効率的にするために必要な変更にフォーカスすることでバランスをとる。sighashやopcodeのようなもにに対しては、既知の問題に対する修正を含めるが、欠点がなく独立して追加できる新しい機能については除外する。

結果として、以下の技術の組み合わせを選択する。

スクリプトを実行することができるすべての方法を開示するのとは対照的に、マークルブランチではスクリプトの実際に実行された部分のみをブロックチェーンに公開することができる。これを実装するのにさまざまな既知の仕組みがある中で、マークルツリーをスクリプトの構造の一部にする方法が、1番直接スペースを節約することができるので、そのアプローチが選択される。
その上にTaprootを使うと、従来別々だったpay-to-pubkeyポリシーとpay-to-scripthashポリシーをマージし、全てのアウトプットは鍵もしくは（オプションで）スクリプトのいずれかで使用でき、互いに区別できなくすることができる。鍵ベースの使用パスが使われている限り、同様にスクリプトパスも許可されているかどうかが明らかにされることはなく、その結果、スペースの節約と使用時のスクリプトのプライバシーの向上がもたらされる。
Taprootの利点は、ほとんどのアプリケーションがすべての参加者が同意することで使用可能になるアウトプットを必要とするという仮定の下で明らかになる。Schnorr署名が入ってくると、鍵の集約が可能になるため、公開鍵は複数の参加者の公開鍵から構成することができ、それに署名するには全ての参加者の協力が必要になる。このようなマルチパーティの公開鍵や署名は、シングルパーティのものと区別がつかない。これは、taprootを使用するとほとんどのアプリケーションが効率的でプライベートな鍵ベースの使用パスを使用できることを意味する。Schnorr署名は閾値署名をサポートしているため、より複雑なセットアッププロトコルが必要になるが、任意のM-of-Nポリシーに一般化できる。
Schnorr署名はバッチ検証を可能にし、複数の署名を個別に検証するよりも効率的に複数の署名をまとめて検証できる。設計の全ての部分がこれと互換性があることを確認している。
上記の変更の結果、未使用のビットが現れた場合、それらは将来の拡張のための仕組みで予約されている。その結果、マークルツリー内の各スクリプトは関連するバージョンを持ち、このバージョンによりBIP 341との互換性を維持しながら、ソフトフォークで新しいスクリプトバージョンを導入できるようになる。さらに、将来のソフトフォークでは、witness内で現在未使用のannexを利用することができる（BIP-341参照）。
この提案では、署名ハッシュアルゴリズムのコアセマンティクスは変更されていないが、いくつかの改善点が含まれている。新しい署名ハッシュアルゴリズムは、署名メッセージににamountとscriiptPubkeyを含めることで、オフライン署名デバイスの検証機能を改善し、不要なハッシュを回避し、タグ付きハッシュを導入し、デフォルトのSIGHASHバイトを定義する。
公開鍵のハッシュやスクリプトのハッシュをアウトプット内に格納する典型的な以前の構成とは対照的に、公開鍵はアウトプットに直接含まれる。これは送信者にとって同じコストであり、鍵ベースのパスが使用される場合、全体的にスペース効率が高くなる²。

略式に、結果の設計は次のとおり。新しいwitness versionが追加され（version 1）、そのwitness programあ点Qの32バイトエンコーディングで構成される。Qは公開鍵PについてQ = P + hash(P || m)Gとして計算され、mはリーフがバージョン番号とスクリプトで構成されるマークルツリーのルート。このようなアウトプットは、Qに対して有効な署名を提供することで直接使用するか、間接的にP、スクリプトとリーフバージョン、スクリプトを満たす入力とQがそのリーフにコミットしたことを証明するマークルパスを明らかにすることを使用できる。この構造のすべてのハッシュ（PからQを計算する際のハッシュ、マークルツリーの内部ノードのハッシュ、使用されるsignature hash）は、ドメインの分離を保証するためタグ付けされる。

仕様

このセクションではTaprootのコンセンサスルールを指定する。有効性は除外によって定義される：ブロックまたはトランザクションは、失敗を示す条件が存在しない場合、有効である。

以下の表記はBIP-340の表記に従う。これには、SHA256(SHA256(tag) || SHA256(tag) || x)を指すhashtag(x)表記が含まれる。著者の知る限り、Bitcoinにおいて２つの単一のSHA256出力で始まるメッセージが投入されるSHA256の使用はこれまでないため、ハッシュタグと他のハッシュとの衝突はほぼ起こらない。

Scriptの検証ルール

Taprootのアウトプットはバージョン番号1、32バイトのwitness programを持つネイティブSegwitアウトプットである。以下のルールは、そのようなアウトプットが使用される場合にのみ適用される。32バイト以外の長さを持つバージョン1のアウトプットや、P2SHでラップされたバージョン1アウトプットの場合³、関係ないままだ。

qをBIP340における公開鍵を表すwitness program（scriptPubkey内の２つめのプッシュ）を含む32バイトの配列とする。
witness stackが0の場合失敗する。
少なくとも２つのwitness要素があり、最後の要素の先頭バイトが0x50の場合⁴、この最後の要素はannex a ⁵と呼ばれwitness stackから削除される。annex（およびその欠如）は、常に署名によってカバーされ、トランザクションのweightに寄与するが、それ以外はtaprootの検証中無視される。
witnessスタックに正確に１つだけ要素が残っている場合、コインを使用するのに鍵パスが使用される：
- 単一のwitnessスタック要素は署名として解釈され、公開鍵q（次のサブセクション参照）とメッセージとしてTaprootのトランザクションダイジェスト（後述）に対して有効でなければならない。
witnessスタックに少なくとも2つの要素が残っている場合、コインを使用するのにスクリプトパスが使用される：
- 最後から２つめのスタック要素sがスクリプトである。
- 最後のスタック要素をコントロールブロックcと呼び、33 + 32mの長さでなければならない。mの値は0〜128 ⁶までの整数。そのような長さでない場合、スクリプトの評価は失敗する。
- p = c[1:33]、P = point(p)としBIP340における点とされる。もしこれが曲線上の有効な点でない場合、スクリプトの評価は失敗する。
- v = c[0] & 0xfeとし、リーフバージョン⁷と呼ぶ。
- ${k_0 = hash_{TapLeaf}(v || compact_size(size of s) || s)}$ とし、これをtapleaf hashと呼ぶ。
- For j in [0,1,...,m-1]の各jについて
  - ${e_j = c［33+32j:65+32j］}$ とする。
  - は、（辞書順で⁸）かどうかで算出方法が変わる：
    - ${k_j ＜ e_j}$ の場合、 ${k_{j+1} = hash_{TapBranch}(k_j || e_j)}$ となる⁹。
    - ${k_j ≧ e_j}$ の場合、 ${k_{j+1} = hash_{TapBranch}(e_j || k_j)}$ となる。
- ${ t = hash_{TapTweak}(p || k_{m})}$ とする。
- t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141（secp256k1の位数）の場合、スクリプトの評価は失敗する。
- Q = P + int(t)Gとする。
- q != x(Q)もしくはc[0] & 1 ≠ y(Q) mod 2の場合、失敗する。
- 適用可能なスクリプトルールに従い¹⁰、スクリプトs、control block c、ある場合はannex aを除外したwitnessスタック要素を初期スタックとしてスクリプトを実行する。

qはTaprootアウトプットキーと呼ばれ、pはTaproot内部キーと呼ばれる。

署名検証ルール

最初に再利用可能な共通の署名メッセージ計算関数を定義し、次に鍵パスの使用で使用される実際の署名検証を定義する。

共通の署名メッセージ

SigMsg(hash_type, ext_flag)関数は署名されるメッセージをバイト列として計算する。この関数は暗黙的に支出トランザクションと支出アウトプットの関数でもあるが、表記を簡単にするために、これらはリストアップされていない。

hash_typeパラメータは8bitの符号なしの値。SIGHASH_ALL, SIGHASH_NONE, SIGHASH_SINGLE, SIGHASH_ANYONECANPAYを含む従来のスクリプトシステムのSIGHASHエンコーディングが再利用される。さらに、SIGHASH_ALLと同様にトランザクション全体が署名されるhash_type値0x00がデフォルトとして追加される。以下の制限に違反すると検証エラーになる：

（0x00, 0x01, 0x02, 0x03, 0x81, 0x82, 0x83以外の）未定義のhash_typeを使ってはならない¹¹。
対応するアウトプット（検証されるインプットと同じインデックスを持つアウトプット）が無いのに、SIGHASH_SINGLEを使用してはならない。

ext_flagパラメータは0-127の範囲の整数で、メッセージの最後¹²に拡張が追加されていることを示すのに使われる。

パラメータが許容値の場合、メッセージは以下のデータを順番に連結したものになる。2,4また8バイトの数値はリトルエンディアンでエンコードされる（カッコ内の数値は要素のバイトサイズを表す）。

Control:
- hash_type(1)
トランザクションデータ:
- nVersion(4): トランザクションのnVersion
- nLockTime(4): トランザクションのnLockTime
- hash_type & 0x80がSIGHASH_ANYONECANPAYと等しくない場合、
  - sha_prevouts (32): 全てのインプットのOutPointをシリアライゼーションした値のSHA256値
  - sha_amounts (32): 全てのインプットの量をシリアライゼーションした値のSHA256値
  - sha_scriptpubkeys (32): 使用する全てのアウトプットのscriptPubKeyをシリアライゼーションした値のSHA256値
  - sha_sequences (32): 全てのインプットのnSequenceをシリアライゼーションした値のSHA256値
- hash_type & 3がSIGHASH_NONE、SIGHASH_SINGLEと等しくない場合、
  - sha_outputs (32): 全てのアウトプットのCTxOutフォーマットの値をシリアライゼーションした値のSHA256値
インプットに関するデータ:
- spend_type (1): (ext_flag * 2) + annex_presentと等しい。annexが存在しない場合はannex_presentは0、存在する場合（元のwitnessスタックには２つ以上のwitness要素があり、最後の要素の先頭バイトが0x50）は1。
- hash_type & 0x80がSIGHASH_ANYONECANPAYと等しい場合：
  - outpoint (36): このインプットのCOutPoint（32バイトのハッシュ＋4バイトのリトルエンディアン）。
  - amount (8): このインプットが使用する前のアウトプットのvalue（コインの量）。
  - scriptPubKey (35): このインプットによって使用される前のアウトプットのscriptPubkey。CTxOut内のスクリプトとしてシリアライズされ、そのサイズは常に35バイト。
  - nSequence (4): このインプットのnSequence。
- hash_type & 0x80がSIGHASH_ANYONECANPAYと等しくない場合
  - input_index (4): トランザクションインプット内のこのインプットのインデックス。最初のインプットのインデックスは0。
- annexがある場合（spend_typeの最下位ビットがセットされている場合）:
  - sha_annex (32): (compact_size(size of annex) || annex)のSHA256値。annexは必須の0x50プレフィックスを含む。
アウトプットに関するデータ:
- hash_type & 3がSIGHASH_SINGLEと等しい場合:
  - sha_single_output (32): インプットに対応するアウトプットのCTxOut形式のSHA2256値。

SigMsg()の最大長は206バイト¹³。これには同じトランザクションの署名に間でキャッシュされる可能性があるsha_prevoutsなどのサブハッシュのサイズは含まれないことに注意すること。

まとめると、BIP143のshghash typeのセマンティクスからの変更点は以下のみ。

シリアライゼーションの方法と順序の変更¹⁴。
署名メッセージは使用されたアウトプットのscriptPubkeyにコミットし、SIGHASH_ANYONECANPAYフラグがセットされていない場合、メッセージはトランザクションで使用された全てのアウトプットのscriptPubkeyにコミットする¹⁵。
SIGHASH_ANYONECANPAYフラグがセットされていない場合、メッセージは全てのトランザクションインプットの量にコミットする¹⁶。
SIGHASH_NONEもしくはSIGHASH_SINGLEがセットされている場合（SIGHASH_ANYONECANPAYがセットされていない限り）、署名メッセージは全てのインプットのnSequenceにコミットする¹⁷。
署名メッセージにはtaroot固有のデータ、spend_typeおよび（あれば）annexへのコミットメントが含まれる。

Taprootの鍵パスを使った署名検証

公開鍵qで署名sigを検証するには：

sigが64バイトの場合、Verify(q, hashTapSighash(0x00 || SigMsg(0x00, 0)), sig)¹⁸の結果を返す。VerifyはBIP340で定義されている。
sigが65バイトの場合、sig[64] ≠ 0x00¹⁹および、Verify(q, hashTapSighash(0x00 || SigMsg(sig[64], 0)), sig[0:64])の結果を返す。
それ以外の場合は失敗²⁰。

Taprootアウトプットの構築と使用

このセクションでは、Taprootアウトプットの構成方法および使用方法について説明する。これは受信と送金を実装することを選択したウォレットのみに影響し、コンセンサスクリティカルではない。

概念的に、各Taprootアウトプットは、単一の公開鍵条件（内部キー）とツリーに編成されたスクリプト内にエンコードされた0個以上の条件の組み合わせに対応している。これらの条件のいずれかを満たすとアウトプットを使用できる。

初期ステップ

最初のステップは、内部キーと残りのスクリプトの構成を決めることだ。詳細はおそらくアプリケーション依存になるが、ここではいくつかの一般的なガイドラインを示す。

(OP_IFなどの)条件付きのスクリプトを決定し、それらを複数のスクリプトに分割する（１つ１つが元のスクリプトの実行パスに対応する）際は、通常後半の選択を推奨する。
単一の条件が複数の鍵の署名を要求する場合は、MuSigのような鍵集約技術を使ってそれらを単一の鍵に集約することができる。詳細はこのドキュメントの範囲外だが、この方法は署名手順を複雑にする可能性があることに注意すること。
１つ以上の使用条件が（集約後の）単一の鍵のみで構成されている場合、最も使用する可能性が高いものを内部キーにする必要がある。そのような条件がない場合は、全てのスクリプトに参加している全ての鍵を集約したもので構成される鍵を追加するのを推奨する。これにより全員が同意するというブランチを効果的に追加する。それが許容できない場合は未知の離散対数を持つ点を内部キーとする。そのような点の例の１つは、 H = point(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) で、これはsecp256k1ジェネレータGの標準的な非圧縮エンコードのハッシュをx座標として取得することで構築できる。キーパスの使用が不可能であるという情報の漏洩を防ぐため、0..n-1の範囲内の整数rをランダムに選択し、内部キーとしてH+rGを使用することを推奨する。rを検証者に明らかにすることで、この内部キーがGに関して既知の離散対数を持たないことを証明し、検証者は内部キーの作成方法を再構築できる。
使用条件がスクリプトパスを必要としない場合、アウトプットキーはスクリプトパスを持たないのではなく、使用できないスクリプトパスにコミットする必要がある。これは、アウトプットのキーポイントを ${Q = P + int(hash_{TapTweak}(bytes(P)))G}$ と計算することで実現できる²¹。
残りのスクリプトは、二分木のリーフに編成する必要がある。スクリプトの各条件が同じようにリーフに対応する場合、ツリーはバランスがとれたツリーになる。各条件の確率が分かっている場合は、ツリーをハフマン木として構築することを検討してほしい。

アウトプットスクリプトの計算

使用条件が内部キーinternal_pubkeyとリーフが（leaf_version、スクリプト）のタプルである二分木に分割されると、以下のPython3 アルゴリズムを使ってアウトプットスクリプトを計算できる。このアルゴリズムは整数変換や点の乗算、タグ付きハッシュを利用するためBIP340のreference.pyのヘルパー関数を使用する。

最初に32バイトのBIP340の公開鍵のバイト列に対して、taproot_tweak_pubkeyを定義する。この関数は公開鍵のバイト列に加えて、調整された公開鍵のY座標を示すビットを返す。このパリティビットはアウトプットをスクリプトパスを使って使用する場合に必要になる。鍵パスで使用できるようにするため、taproot_tweak_seckeyを定義し、調整された公開鍵に対応する秘密鍵を計算する。任意のバイト文字列hに対してtaproot_tweak_pubkey(pubkey_gen(seckey), h)[0] == pubkey_gen(taproot_tweak_seckey(seckey, h))が成立する。

def taproot_tweak_pubkey(pubkey, h):
    t = int_from_bytes(tagged_hash("TapTweak", pubkey + h))
    if t >= SECP256K1_ORDER:
        raise ValueError
    Q = point_add(point(pubkey), point_mul(G, t))
    return 0 if has_even_y(Q) else 1, bytes_from_int(x(Q))

def taproot_tweak_seckey(seckey0, h):
    P = point_mul(G, int_from_bytes(seckey0))
    seckey = SECP256K1_ORDER - seckey0 if not has_square_y(P) else seckey
    t = int_from_bytes(tagged_hash("TapTweak", bytes_from_int(x(P)) + h))
    if t >= SECP256K1_ORDER:
        raise ValueError
    return (seckey + t) % SECP256K1_ORDER

次の関数taproot_output_scriptはscriptPubkeyのバイト配列を返す（BIP141参照）。ser_scriptは先頭CCompactSizeでエンコードされた長さを付与する関数を指す。

def taproot_tree_helper(script_tree):
    if isinstance(script_tree, tuple):
        leaf_version, script = script_tree
        h = tagged_hash("TapLeaf", bytes([leaf_version]) + ser_script(script))
        return ([((leaf_version, script), bytes())], h)
    left, left_h = taproot_tree_helper(script_tree[0])
    right, right_h = taproot_tree_helper(script_tree[1])
    ret = [(l, c + right_h) for l, c in left] + [(l, c + left_h) for l, c in right]
    if right_h < left_h:
        left_h, right_h = right_h, left_h
    return (ret, tagged_hash("TapBranch", left_h + right_h))

def taproot_output_script(internal_pubkey, script_tree):
    """Given a internal public key and a tree of scripts, compute the output script.
    script_tree is either:
     - a (leaf_version, script) tuple (leaf_version is 0xc0 for [[bip-0342.mediawiki|BIP342]] scripts)
     - a list of two elements, each with the same structure as script_tree itself
     - None
    """
    if script_tree is None:
        h = bytes()
    else:
        _, h = taproot_tree_helper(script_tree)
    output_pubkey, _ = taproot_tweak_pubkey(internal_pubkey, h)
    return bytes([0x51, 0x20]) + output_pubkey

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

この図は内部キーPと５つのスクリプトリーフで構成されるマークルツリーからtweakを入手するハッシュ構造を示している。A,B,CおよびEはDと同様のTapLeafハッシュで、ABはTapBranchハッシュ。EはCDより小さいのでCDEを計算刷る際最初にEがハッシュされることに注意すること。

スクリプトDを使ってこのアウトプットを使用する場合、Control Blockに以下のデータがこの順番で含まれる。

<control byte with leaf version and parity bit> <internal key p> <C> <E> <AB>

次にTapTweakは以下のように計算される。

D = tagged_hash("TapLeaf", bytes([leaf_version]) + ser_script(script))
CD = tagged_hash("TapBranch", C + D)
CDE = tagged_hash("TapBranch", E + CD)
ABCDE = tagged_hash("TapBranch", AB + CDE)
TapTweak = tagged_hash("TapTweak", p + ABCDE)

鍵パスを使ったコインの使用

Taprootアウトプットは、internal_pubkeyに対応する秘密鍵を使って使用することができる。そのためには、witnessスタックは上記で定義されたsignature hashに対し、上記スニペット内と同じhを使って調整された秘密鍵で作成したBIP340署名という単一の要素で構成する。以下のコードを参照：

def taproot_sign_key(script_tree, internal_seckey, hash_type):
    _, h = taproot_tree_helper(script_tree)
    output_seckey = taproot_tweak_seckey(internal_seckey, h)
    sig = schnorr_sign(sighash(hash_type), output_seckey)
    if hash_type != 0:
        sig += bytes([hash_type])
    return [sig]

この関数は、必要なwitnessスタックと、上記で定義したsignature hashを計算するためのsighash関数を返す（簡単にするため、上記のスニペットはトランザクション、インプットの位置などの情報をsighashのコードに渡していない）。

スクリプトの１つを使ったコインの使用

Taprootアウトプットは、その構築に使用されたスクリプトのいずれかを満たすことで使用できる。そのためには、スクリプトへの入力に加えて、スクリプト自体とControl Blockで構成されるwitnessスタックが必要になる。以下のコードを参照：

def taproot_sign_script(internal_pubkey, script_tree, script_num, inputs):
    info, h = taproot_tree_helper(script_tree)
    (leaf_version, script), path = info[script_num]
    output_pubkey_y_parity, _ = taproot_tweak_pubkey(internal_pubkey, h)
    pubkey_data = bytes([output_pubkey_y_parity + leaf_version]) + internal_pubkey
    return inputs + [script, pubkey_data + path]

安全性

Taprootは、アウトプットを使用する際に全ての条件を明らかにするのではなく、満たされた使用条件のみを公開すれば良いので、Bitcoinのプライバシーを向上させる。理想的には、アウトプットは観察者がコインの使用条件を知ることがないキーパスを使ったコインの使用である。キーパスを使ったコインの使用は、単一もしくは複数の署名のウォレットからの通常の支払いか、隠れたマルチパーティコントラクトの共同決済のいずれかである。

スクリプトパスを使ったコインの使用は、スクリプトパスが存在すること、（例えば関係者が合意に達しなかったなどで）キーパスが使われなかったことをリークすることになる。さらに、マークルルートのスクリプトの深さは、ツリーの最小の深さを含む情報をリークする。これはアウトプットを作成したウォレットソフトウェアを示唆し、クラスタリングを助けることになる。したがって、したがってスクリプトを使用する際のプライバシーは、リーフに対する確率分布により最適なツリー構造から逸脱することでプライバシーを改善する。

他の既存のアウトプットタイプと同様に、プライバシー上の理由からTaprootアウトプットはキーを再利用すべきではない。これはアウトプットを使用する際に使われた特定のリーフだけでなく、アウトプットにコミットされたすべてのリーフにも適用される。リーフが再利用されると、別のアウトプットを使用する際にマークルプルーフで同じマークルブランチが再利用されるといったことが起きる可能性がある。新しいキーを使用することで、Taprootで使われているブランチソートのマークルツリー構造によってすでにランダム化されているため、Taprootのアウトプットの構築においてリーフ位置のランダム化に特別な対策を講じる必要が無い。これはリーフの深さを通して情報が漏れるのを避けるものではないため、バランスの取れた（サブ）ツリーにのみ適用される。さらに、すべてのリーフは、他のリーフとは異なるキーのセットを持つ必要がある。この理由は、リーフのエントロピーを増加させ、ブルートフォース検索を使って観察者が未知のスクリプトを学習するのを防ぐためだ。

Test Vector

作成トランザクションと使用トランザクションの有効、無効のペアの例。

sighashモード毎のsighashのプリイメージの例。

まだないっぽい。

展開

まだ展開方法は未定義。

後方互換正

ソフトフォークとして、古いソフトウェアは変更なく動作し続ける。ただし、アップグレードしていないノードではSegwitのバージョン1のwitness programを誰でも使用可能なスクリプトとみなす。新しいprogramを完全に検証するためにアップグレードすることを推奨する。

アップグレードされていないウォレットは、Segwitのバージョン0のprogramおよび従来のpay-to-pubkey-hashなどを使って、アップグレードしたウォレットおよびアップグレードしていないウォレットからBitcoinの受信、送金ができる。実装によっては、BIP 173のBech32アドレスへの送金をサポートしている場合、アップグレードされていないウォレットがSegwit version 1のprogramに送金できる場合がある。

論拠

セキュリティの仮定を追加しないというのはどういう意味か？署名が偽造不可能であることは、盗難を防ぐための必須要件だ。少なくともスクリプトの実行をデジタル署名スキーム自体として扱う場合、離散対数問題の困難性を仮定とするランダムオラクルモデルで偽造不可能性が証明できる。現在のスクリプトシステムにおけるECDSAの偽造不可能性の証明には、さらにその上に非標準の仮定が必要だ。ウォレットソフトウェアで使用されるポリシーとプロトコルに依存するため、スクリプトのセキュリティが意味するものを正確にモデル化することは一般的に難しいことに注意してほしい。↩
公開鍵がアウトプットに直接含まれるのはなぜか？ 初期の典型的な構造ではスクリプトや公開鍵のハッシュをアウトプットに格納するが、公開鍵が常に含まれている場合これはかなり無駄になる。バッチ検証が可能であることを保証するために、公開鍵は全ての検証者に知られている必要があり、したがって出力としてそのハッシュを明らかにすることだけが、witnessに追加の32バイトを追加することを意味する。さらに、アウトプットに対して128ビットの衝突の安全性を維持するためには、とくかく256ビットのハッシュが必要になる。これはサイズが（送信者にとってはコストが）、直接公開鍵を明らかにするのに匹敵する。公開鍵ハッシュの使用は、ECDLPの破壊や量子コンピューターへの保護になるとよく言われるが、その保護は非常に弱い。トランザクションは承認される間保護されず、通貨の供給の大部分はそのような保護の対象にならない。そのようなシステムへの実際の抵抗は、異なる暗号仮定に依存することで実現できる。しかしこの提案は、セキュリティモデルを変更しない改善にフォーカスしている。↩
なぜP2SHによるラップをサポートしないのか？ P2SHでラップしたアウトプットの使用は、160ビットのハッシュが使用されるため80ビットの衝突の安全性のみを提供する。この数値は低いとみなされアウトプットに複数のパーティのデータが含まれる場合、常にセキュリティリスクになる。↩
annexの先頭バイトが0x50なのはなぜか？ 有効なP2WPKHもしくはP2WSHのアウトプットと混同しないように0x50が選択されている。Control Blockの先頭バイトの最下位ビットが公開鍵のYのパリティを示すのに使われるため、各リーフバージョンには偶数バイト値とP2WPKHおよびP2WSHの使用時にまだ使われていない奇数バイト値を必要とする。annexを示すには、0x50のようにペアでない利用可能なバイトのみが必要だ。この選択は将来のスクリプトバージョンのために利用可能なオプションを最大にする。↩
annexの目的は何か？ annexは、使用されるアウトプットについて知らなくても認識できるような方法で、計算的に高価な新しいopcodeの検証コストを示すなど、将来の拡張のために予約されたスペースだ。このフィールドの意味が他のソフトフォークによって定義されるまでは、ユーザーはトランザクションにannexを含めるべきではなく、或いは永久的な資金の喪失に繋がるかもしれない。↩
マークルパスの長さが128までに制限されている理由は？ ハフマンアルゴリズムを使用して、リーフのスクリプトの確立に基づき最適な空間効率のマークルツリーを構築できるため。このアルゴリズムはlog2(1/probability)にほぼ等しい長さのブランチを構築するが、128を超えるブランチを作成するには、1/2^{128}未満の実行チャンスを持つスクリプトが必要になり、このような低い可能性はおそらく完全に削除できる。↩
リーフバージョンにはどのような制約がある？ まずc[0] & 0xfeは常に偶数であるため、リーフバージョンを奇数にすることはできず、また0x50にすることもできない（0x50にした場合annexとの曖昧さが生じるため）。さらに、使用されるアウトプットにアクセスすることなくスクリプトの使用を特定できることに依存する静的分析のいくつかの形式をサポートするために、有効なP2WPKH公開鍵や有効なP2WSHスクリプトのいずれかの有効な先頭バイトと競合するリーフバージョンの使用を避けることを推奨する（つまり、vとv|1の両方とも未定義、無効、無効なopcodeもしくは最初のopcodeとして無効なものでなければならない）。このルールに準拠する値は、0xc0から0xfeまでの偶数値、0x66, 0x7e, 0x80, 0x84, 0x96, 0x98, 0xba, 0xbc 0xbeだ。またこの制約はリーフバージョンを異なるwitness version間で共有する必要があることを意味するこｔに注意すること。witness versionを知るには使用されるアウトプットにアクセスする必要がある。↩
マークルツリー内でハッシュされる前に子要素がソートされるのはなぜ？ そうすることでマークルブランチのハッシュを明らかにする際に一緒に左右の方向を明らかにする必要がなくなるため。これが可能なのは、ツリー内の特定のスクリプトの位置を実際には気にしておらず、それらが実際にコミットされているということだけを気にしているためだ。↩
内部のマークルノードにとってもっと効率的なハッシュ構造を使わないのはなぜ？ 選択された構造は、SHA256圧縮関数を2回呼び出す必要があり、2回のうち1回は理論的に避けることができる（BIP-98参照）。しかし、実装の単純さと分析可能性のため、標準の暗号プリミティブを使って実装できる構造に固執するのが好ましいように思われる。必要なら、64バイトの入力用に特化することで2つ目の圧縮関数の大部分を最適化できる。↩
使用するスクリプトパスに適用できるスクリプトルールは何？ BIP342はリーフバージョンが0xc0の場合に適用される有効性ルールを指定するが、将来の提案では他のリーフバージョンに対してルールを導入できる。↩
なぜ未知のhash_typeを拒否するのか？ そうすることで、十分なキャッシングを持つ実装が実行しなければならない署名ハッシュのワーストケースを推論するのが簡単になる。↩
どの拡張機能がext_flagの仕組みを利用するのか？ BIP342は同じ共通の署名メッセージアルゴリズムを再利用するが、BIP342固有のデータを最後に追加する。これをext_flag = 1を使って明示する。↩
SigMsg()の出力長は？ SigMsg（）の長さは次の式を使って計算できる。174 - is_anyonecanpay * 49 - is_none * 32 + has_annex * 32。↩
署名メッセージのシリアライゼーションが変更されたのはなぜ？ 署名メッセージとメッセージ自体に送られるハッシュががdouble SHA256ではなく単一のSHA256で計算されるようになった。SHA256を二回しても安全性の向上は期待できない。double SHA256は伸長攻撃への保護になるのみで、署名メッセージには秘密のデータは無いので意味がない。したがって、SHA256を2回するのはリソースの無駄である。メッセージの計算は、最初にトランザクションレベルのデータ、次にインプットのデータ、アウトプットのデータと論理的な順に行われる。これによりSHA256のmidstateを使って、異なるインプットに渡るメッセージのトランザクション部分を効率的にキャッシュできる。さらにメッセージの計算で、ハッシュの前に一部にゼロをセットするBIP 143ダイジェストとは対照的にサブハッシュをスキップできる。そのようにしても、可変長データの前に（hash_typeとspend_typeに暗黙的に含まれる）データの長さにコミットすることで衝突は不可能になる。↩
署名メッセージがscriptPubKeyにコミットするのはなぜ？ これにより、実際に実行されたスクリプトが正しい場合でも（BIP 143のscriptCode）、使用されるアウトプットのタイプについてオフライン署名デバイスに嘘を付くのを防ぐ。つまり、ハードウェアウォレットに対して、どの（未使用の）実行パスが存在したかをコンパクトに証明することが可能だ。さらに使用済みの全てのscriptPubkeyにコミットすることで、オフライン署名デバイスが自身のウォレットに属するサブセットを決めるのに役立つ。これは自動化されたCoinJoinにとっても役立つ。↩
署名メッセージがすべてのインプットの量にコミットするのはなぜ？ これにより取引の手数料についてオフラインの署名デバイスに嘘を付く可能性がなくなる。↩
SIGHASH_SINGLEまたはSIGHASH_NONEがセットされている場合、署名メッセージがすべてのインプットのnSequenceにコミットするのはなぜ？ これらをセットすると、すでにすべてのトランザクションインプットのprevoutにメッセージがコミットするため、nSequenceを別の値にすると役に立たなくなる。さらにこの変更により、nSequenceはSIGHASH_SINGLEとSIGHASH_NONEがトランザクションアウトプットに対してのみ署名メッセージの変更を許可し、インプットに関しては署名メッセージを変更できないという観点と一致する。↩
${hash_{TapSighash}}$ への入力の先頭に0x00が付いているのはなぜ？ このプレフィックスはsighash epochと呼ばれ、ハッシュの実行方法に外来性の変更を加える将来の署名アルゴリズムで ${hash_{TapSighash}}$ タグ付きハッシュを再利用できる（インクリメンタル拡張に使われているext_flagとは対照的）。別の方法として異なるタグを使用することもできるが、サポートするタグの数が増えると望ましくない場合がある。↩
65バイトの署名でhash_typeを0x00できないのはなぜ？ これを許可すると64バイトの署名を65バイトに変更することができ、作者が意図したものとは異なるwtxidと手数料が発生する。↩
2つの署名の長さを許可するのはなぜ？ 最も一般的なタイプのhash_typeを暗黙的にすることで、多くの場合1バイト節約できる。↩
スクリプトパスが無い場合でも、アウトプットキーが常にtaprootコミットメントを持つのはなぜ？ taprootが鍵の集約である場合、悪意ある参加者が他の参加者に気付かれずにスクリプトパスを追加する可能性がある。これによりマルチパーティポリシーを迂回してコインを盗むことができる。MuSigの鍵集約には、内部キーが既にランダム化されているため、この問題はない。攻撃は次のように機能する。アリスとマロリーはスクリプトパスを使用せずに鍵をtaprootアウトプットキーに集約すると仮定する。鍵のキャンセルと関連する攻撃を防ぐのにMuSigの代わりにMSDL-popを使用する。MSDL-popプロトコルでは、全ての関係者が、対応する秘密鍵の所有の証明を提供する必要があり、集約鍵は各鍵の合計に過ぎない。マロリーがアリスの鍵Aを受け取った後、 ${M = M_0 + int(t)G}$ を作成する。ここで ${M_0}$ はマロリーの元々の鍵で、tは内部キー ${P = A + M_0}$ のスクリプトパスで、スクリプトはマロリーの鍵のみを含む。マロリーはMの所有の証明をアリスに送信し、両者はアウトプットキーQ = A + M = P + int(t)Gを計算する。アリスはスクリプトパスを認識できないが、マロリーはアウトプットキーQを持つコインを一方的に使用できる。↩

2019-04-24

LNDに実装されたStatic Channel Backup

Bitcoin Lightning network LND

先日リリースされたLND 0.6-beta↓

Release lnd v0.6-beta · lightningnetwork/lnd · GitHub

で新しくStatic Channel Backup機能が導入された。

通常のオンチェーンの場合であれば、全てのトランザクションはチェーン上に記録されているためバックアップは簡単で、BIP-32ベースのマスターシードさえ管理できていれば、自身の資金を失うことはない。

techmedia-think.hatenablog.com

ただ、Lightning Networkのようなペイメントチャネルを利用したオフチェーン決済の場合、これが難しくなる。オフチェーンの決済情報は二者間でしか管理していない。

オフチェーン決済は、二者間のマルチシグにロックされた資金をインプットとし、決済の度にアウトプットの両者の残高を更新していく。つまり、決済が行われる度に、このチャネルの状態が変化していく。古い状態がブロードキャストされるのを防ぐため、両者は古い状態のトランザクションを無効にするためのシークレットを交換する。もし古いチャネル状態のトランザクションがブロードキャストされると、その取引相手は交換したシークレットを使ってチャネルの資金を全て総取りすることができる。このペナルティが不正の防止策として機能する。

このため、両者は各チャネルの状態で使用している鍵や相手の署名、旧状態を無効化するためのシークレットを管理しなければならない。これらのデータを失うと、自分の資金が取り戻せなくなったり、バックアップが古かった場合、不正をする意図はなくても最新の状態と勘違いをして古いチャネル状態のトランザクションをブロードキャストしてしまうかもしれない。このようにチャネルのバックアップには課題がある。

Static Channel Backupの仕組み

Static Channel Backup（SCB）の仕組みはシンプルで、最新のチャネル状態を維持するための仕組みではなく、チャネルのオープン時にバックアップを作成しておき実際のリカバリーはData Loss Protection (DLP)プロトコルを使用する。

いくらバックアップをしていたとしても、データを失ったらそのバックアップがチャネルの最新状態を保管したものであるかの保証はなく、古いコミットメントをブロードキャストしてしまうとチャネルの資金を失ってしまうので、そういうリスクを冒さないようDLP プロトコルを使って資金をリカバリーする。DLP プロトコルは、チャネルを接続していたリモートピアに再接続し、リモートピアにチャネルを強制的にクローズするよう通知する仕組み。そうすることで、自分が誤って古い状態のトランザクションをブロードキャストするのを防ぐ。

このため、SCBを使ったバックアップは特定のチャネルについて１回のみ取得すればよく、チャネルが閉じられるまで有効である。完全にデータをロスした場合、このバックアップが最終的なリカバリー方法となる。資金を完全に回収するには、チャネルを閉じる必要があることに注意すること。

バックアップ/リカバリー方法

SCB機能では、チャネルをバックアップおよびリカバリーするための複数の安全な方法を公開している。

ファイルを使ったバックアップ

最も簡単なバックアップ＋リカバリーの方法。

lndは現在、その他のすべてのファイルを格納している場所と同じ場所（.lnd/data/chain/bitcoin/mainnet/channel.backup）でchannels.backupファイルを管理している。ユーザーはいつでもこのファイルを安全にコピーおよびバックアップできる。

チャネルがオープンまたはクローズする度に、lndはこのファイルを最新のチャネル状態で更新するので、ユーザーはファイルへの変更を検知し、それらを自分にバックアップ場所にアップロードするスクリプトを作っておくだけで良い。ファイルの変更検知については、fsnotifyなどを利用すればいい。

また、ファイルはユーザーのシードから導出した鍵を使ってAEAD方式で暗号化されているため、クラウドストレージやSDカードなどにそのまま安全に保存できる。

リカバリーする際は、restorechanbackupコマンドを使う。

$ lncli restorechanbackup --multi_file /path/to/copied/channel.backup

上記コマンドにより、リモートピアに強制的にチャネルをクローズするよう通知がいく。リモートピアがチャネルをクローズすると、資金がオンチェーンウォレットに戻ってくる。

gRPCを使ったバックアップ

２つめの仕組みは、新しく追加されたSubscribeChanBackups ストリーミングgRPCを使う、より上級者向けの方法。このgRPCを使うと、ベースとなるSCBの状態が変わる度に、新しい通知を受け取ることができる。上記のようなフィルシステムの通知よりも、より複雑なバックアップの仕組みを構築することができる。

cliやRPCを使ってバックアップを要求

最後の方法は、単一のチャネルまたは全てのチャネルのバックアップをcliやRPCで要求する方法。以下のようにcliで要求できる。

$ lncli --network=simnet exportchanbackup --chan_point=29be6d259dc71ebdf0a3a0e83b240eda78f9023d8aeaae13c89250c7e59467d5:0
{
    "chan_point": "29be6d259dc71ebdf0a3a0e83b240eda78f9023d8aeaae13c89250c7e59467d5:0",
    "chan_backup": "02e7b423c8cf11038354732e9696caff9d5ac9720440f70a50ca2b9fcef5d873c8e64d53bdadfe208a86c96c7f31dc4eb370a02631bb02dce6611c435753a0c1f86c9f5b99006457f0dc7ee4a1c19e0d31a1036941d65717a50136c877d66ec80bb8f3e67cee8d9a5cb3f4081c3817cd830a8d0cf851c1f1e03fee35d790e42d98df5b24e07e6d9d9a46a16352e9b44ad412571c903a532017a5bc1ffe1369c123e1e17e1e4d52cc32329aa205d73d57f846389a6e446f612eeb2dcc346e4590f59a4c533f216ee44f09c1d2298b7d6c"
}

$ lncli --network=simnet exportchanbackup --all
{
    "chan_points": [
        "29be6d259dc71ebdf0a3a0e83b240eda78f9023d8aeaae13c89250c7e59467d5:0"
    ],
    "multi_chan_backup": "fd73e992e5133aa085c8e45548e0189c411c8cfe42e902b0ee2dec528a18fb472c3375447868ffced0d4812125e4361d667b7e6a18b2357643e09bbe7e9110c6b28d74f4f55e7c29e92419b52509e5c367cf2d977b670a2ff7560f5fe24021d246abe30542e6c6e3aa52f903453c3a2389af918249dbdb5f1199aaecf4931c0366592165b10bdd58eaf706d6df02a39d9323a0c65260ffcc84776f2705e4942d89e4dbefa11c693027002c35582d56e295dcf74d27e90873699657337696b32c05c8014911a7ec8eb03bdbe526fe658be8abdf50ab12c4fec9ddeefc489cf817721c8e541d28fbe71e32137b5ea066a9f4e19814deedeb360def90eff2965570aab5fedd0ebfcd783ce3289360953680ac084b2e988c9cbd0912da400861467d7bb5ad4b42a95c2d541653e805cbfc84da401baf096fba43300358421ae1b43fd25f3289c8c73489977592f75bc9f73781f41718a752ab325b70c8eb2011c5d979f6efc7a76e16492566e43d94dbd42698eb06ff8ad4fd3f2baabafded"
}

$ lncli --network=simnet exportchanbackup --all --output_file=channels.backup

リカバリープロセス

リカバリープロセスが開始されるとlndは以下のプロセスを実行する。

リカバリーするチャネルのセットが与えられると、データベースにchannel shellを挿入する。これにはDLP プロトコルを開始するのに必要な情報だけが含まれる。結果、これらのチャネルはデータベース内で「recovered」とマークされ、他のプロセスがそのチャネルを使用するのを防ぐ。
channel shellが「recovered」になると、chanbackupパッケージは、ピアに到達できた以前の全てのアドレスを含むLinkNodeを挿入しようとする。その過程でそのチャネルのエッジ（送信方向にのみ）もデータベースに挿入される。
続いてlndが起動し、いつもどおりチャネルを開いている全てのピアとの接続を確立しようとする。lndがすでに実行されている場合は、新しい接続の試行が開始される。
ピアと繋がったら、次にDLP プロトコルを開始する。リモートピアはデータが失われたことを知り、すぐに強制的にチャネルを閉じる。チャネルを閉じる前に、こちら側が資金を回収するのに必要な鍵を導出するために必要な、最新のコミットメントポイントを含むチャネル再確立ハンドシェイクメッセージを送り返す。
リモートピアがブロードキャストしたコミットメントトランザクションがチェーン上で確認されたら、SCBの情報から資金を回収するのに必要な鍵を再導出し、資金を回収する。

バックアップ/リカバリ−される資金

１点、注意が必要なのは、SCBにより回収可能な資金はベースコミットメントのアウトプットにある資金のみであるということ。つまりHTLCの資金は含まれない。このバックアップファイルはチャネル作成時に作られるが、将来作られるであろうHTLCの情報は当然含まれないので、HTLCの情報は欠落しており、未処理のHTLCがあれば、その資金は回収できない。

2019-04-11

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

Bitcoin Lightning network

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は暗号のシークレットを利用して、特定のイベントが別のブロックチェーンで発生したことをユーザーが１つのブロックチェーン上で証明できるようにする。

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

Atomic Swap

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

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

とスワップを完了できる。

Atomic Swaption

上記のAtomic Swapでは３でボブが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トークンなど）、アリスが行使を決定するまでアリスが資金をデポジットする必要が無いようコントラクトを設計することができる。

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

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

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

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

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

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

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

先物

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

Lightning Networkのルーティング

この分析の多くは、１つのブロックチェーンのみを使うため処理が簡単な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支払いのチェーンの各ステップは１タイムステップ後に期限切れになるので）。さらに、キャロルはアリスがそうするのを待たずに、一方的にボブとのロングオプションポジションを閉じることができ、それによりキャロルの資金がより早く解放される。完全に協調的な場合は、オプションのアンワインドプロセスも単純化する。

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

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

経済的考察

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

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

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

実用的な考慮事項

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

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

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

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

結論

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

2019-04-06

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

Bitcoin Scaling Bitcoin Cryptography

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の管理をアキュムレータで行う場合、さらに要素の削除をサポートする必要がある。

セットアップ

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

２つの素数の積（pとqは秘密の素数）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}}$ となる。

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

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と要素ｘおよびその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を効率的に行う仕組みを提案。

高速なブロックの検証

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

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

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

フルノードは↑の新しいブロックに対して、BLS署名の検証、以下２つの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などもその一種）、

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

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

所感

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

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

2019-03-31

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

BIP Bitcoin

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

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

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

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

といったコントラクトを、HTLCを拡張したHashed Time-Locked Collateral Contract（HTLCC）で実現しようというBIP提案。担保をBitcoinのブロックチェーン上でBTCとして２つの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にロックされた際に決定された担保の一定割合を受け取る権利がある。

これらの資金は２つのスクリプトにロックされる。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_SHA256かOP_HASH160のいずれか。

[TIMEOUTOP]は、OP_CHECKSEQUENCEVERIFYかOP_CHECKLOCKTIMEVERIFYのいずれか。

対話

アリス（借り手）とボブ（貸し手）は、アリスが作成した２つのシークレットのハッシA1, A2、ボブが作成した３つのシークレットのハッシュB1, B2, B3を交換する。両者はその後、ローンの期間（Loan Period）、精算期間（Liquidation Period）、差し押さえ期間（Seizure Period）のタイムアウト閾値について合意する。アリスはRefundable Collateral Contract と Seizable Collateral ContractのスクリプトおよびそのP2SHアドレスを作成する。ボブはローンの元金が発行されるブロックチェーン、元本ブロックチェーンのスクリプトを構成する。
ボブは元本ブロックチェーンのローンスクリプトに元本の資金を送金する。
アリスはRefundable Collateral P2SHアドレスとSeizable Collateral P2SHアドレスに資金を送る。アリスが２つのアドレスに送金する金額は事前にアリスとボブの間で決定される。
その後は以下のいずれかのパターンになる：
- ボブがアリスによる担保のロックを受け入れると、ボブは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：借り手によって生成されるシークレットで、入札者が精算した担保資金を引き出すのに使われる

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

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

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

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

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

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

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

承認期間

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

ローンの有効期間

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

入札の有効期間

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

差し押さえ期間

借り手もしくは貸し手のどちらかが入札に応じない場合は、貸し手は担保の一定割合を差し押さえることができる。その金額はこの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バイトであることを確実にする必要がある。

後方互換性

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

実装

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