チェーン上で異なるコンセンサスの実行を可能にする拡張方法「Extension Block」

最近、LitecoinがMimblewimbleを導入するLIP（Litecoin版BIP）が提案された↓

• https://github.com/litecoin-project/lips/blob/master/lip-0002.mediawiki
• https://github.com/litecoin-project/lips/blob/master/lip-0003.mediawiki

Litecoinは元々Bitcoinのアルトコインであるため、根本的にブロックチェーンの構造が異なるMimblewimbleを導入するのはBitcoin同様難しい。そこでLitecoinがMimblewimbleを導入するために採った方法がExtension Blockという拡張方法だ。

Auxiliary Block

Extension Blockのアイディアはもともと、2013年にJohnson Lauがハードフォークを必要とせずブロックサイズを増やす方法として提案したものだ↓

https://bitcointalk.org/index.php?topic=283746.0

提案された1MBのブロックサイズを増やすAuxiliary Blockの仕組みは、

1. 各ブロック毎にメインのブロックとは別にAuxiliary Blockが作成される。Auxiliary Blockヘッダーを持たないブロック。
2. OP_NOP1をOP_AUXとして再定義する。
3. 誰かがBitcoinを<serialized script> OP_AUXというscriptPubkey宛に送金するまでAuxiliary Blockは空のまま。この形式のscriptPubkeyが現れると、Auxiliary Blockにコインベースのようなトランザクションが作成され、ロックされたBitcoinが送られる。Auxiliary Blockのマークルルートはメインブロックのコインベースに含まれる。アップグレードされたノードはBitcoinがメインチェーンから補助チェーンに正しく転送されているかどうか確認する。（なお、OP_AUXのトランザクションを含まないブロックではAuxiliary Blockは作られない。つまりAuxiliary Blockのチェーンは形成されない）
4. 補助チェーンでもメインチェーンと同様Bitcoinの送金ができ、マイナーもメインチェーンと同じ仕組みを使って手数料を徴収することもできる。唯一の違いは、補助チェーンにはコイン生成の報酬が無いということ。メインチェーン側で<serialized script> OP_AUXにコインを送金した場合のみ、補助チェーン上でコインが生成される。
5. 補助チェーンからメインチェーンにコインを戻す場合は、補助チェーンのコインを<serialized script y> OP_AUX OP_RETURN形式のscriptPubkeyに送金する。マイナーはこの送金を検知し、メインチェーン上でOP_AUXのUTXOをランダムに選択し、同じコインの量だけメインチェーン内の<deserialized script>宛に送金する。

というもの。この仕組みでは以下の後方互換性が担保される：

• 旧ノードには補助ブロックのデータが表示されないので、補助ブロックのサイズは自由に決められる。
• OP_AUXのアウトプットは旧ノードにとって誰もが使用可能なanyone can spendなUTXOとしてみられるので、旧ノードはそのまま動作可能。
• 上記のルールに従わずOP_AUX UTXOのコインを盗もうとしても大多数のマイナーにより上記がアクティベートされていれば、その行為は拒否される。
• 旧ノードは作成するブロックにOP_AUXトランザクションを含めたり引き換えたりしない限り、引き続き有効なブロックをマイニングできる。

この仕組みを利用すると、ブロックサイズに限らず本来ハードフォークを必要とする変更も、ソフトフォークで実現することができる。

そしてExtension Blockとして2017年1月に実際にBitcoinへのソフトフォークとして提案されたのが↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013490.html

LitecoinのExtension Block

Litecoinでは、LIP-0002としてMimblewimbleをLitecoinに導入するためにExtension Blockを導入する提案が出ている。この提案は、OP_AUXのようなopcodeを追加するのではなく、2017年にBitcoinで提案された内容の用に、新しいwitness versionを使った導入になる。

Peg-in

標準チェーンのコインをExtention Blockのチェーンに移動する場合、ユーザーはPeg-inトランザクションを作成する。Peg-inトランザクションは、EB側のブロックチェーンに送金したいコインを新しいwitness program宛に送金するトランザクション。

新しいwitness programにコインを送金するPeg-inトランザクションが作られると、そのPeg-inトランザクションが含まれるブロックに対応するEB側のブロックにおいて、同量のコインを持つコインベーストランザクションが作られる。witness programの値はEB側のコインベーストランザクションの送金先へのコミットメントになる（Mimblewimbleの場合、witness programはEB側のコインベーストランザクションにセットされるカーネルコミットメントを指定するっぽい）。なお、対応するEBのブロックに対応すコインベーストランザクションが存在しない場合、標準チェーン上のPeg-inトランザクションは無効とみなされる。

Peg-inトランザクションにより標準チェーンからEB側のチェーンにコインが移動するので、標準チェーンでは当然移動したコインはEB側から戻ってくるまでロックされなければならない。そのため、Peg-inトランザクションで作成されたUTXOは、マイナーにより収集され、同一ブロック内に作成されるインフレーショントランザクション（後述）で使用される。

Peg-out

Peg-inとは逆にEBのチェーンから標準チェーンにコインを移動する際にはEBチェーン上でPeg-outトランザクションを作成する。Peg-outトランザクションは標準チェーン上で同量のコインの送金先であるLitecoinアドレスへコミットする。

Peg-outにより標準チェーン上で利用可能になったコインは、標準トランザクションのコインベーストランザクションのコインと同様、使用できるまで一定期間ロックされる。これはチェーンの再編成に対応するため。

インテグレーショントランザクション

標準チェーン上でEBへのPeg-in、EBからのPeg-outを処理するために作られるのがインテグレーショントランザクション。インテグレーショントランザクションはマイナーによってブロック毎に１つ作成されるトランザクションで、ブロック内の最後のトランザクションとして配置される。

インテグレーショントランザクションは、X+1個のインプットとY+1個のアウトプットを持つ。Xはブロック内のPeg-inトランザクションの数で、Yはブロック内のPeg-outトランザクションの数。

• インプット
  • 最初のインプットは前のブロックExtAddr UTXO（後述）。
  • X個のインプットはブロック内のPeg-inトランザクションのUTXOを集めたもの。基本的に対応するEB内に同じ数のコインベーストランザクションが作られる。これらのコインは新しくEB側のチェーンに移動するコインであるため、標準チェーン上では他で使用されないようこのトランザクションでインプットとして使用される。
• アウトプット
  • 最初のアウトプットは、このブロックにおけるEB側のコインの合計量を持つExtAddrアウトプット。インプットには前のブロックのExtAddrとこのブロックでEB側に移動したコインの合計があるので、そこからこのブロックでEB側から標準チェーンに戻ってきたコイン（このアウトプットの後に続くPeg-out分のコイン）を差し引いた量がこのブロック時点でのEB側のコインの総量になり、その総量を全てこのExtAddrにロックすることになる。
  • Y個のアウトプットは、EB側のチェーンから標準チェーンに移動してくるコインのアウトプット。このアウトプットはEB側のPeg-outトランザクションでコミットされたLitecoinアドレス宛のアウトプットになり、対応するEB側のブロック内のPeg-outトランザクションの数と同じだけのアウトプットが作成される。

ExtAddr

ExtAddrは、EB側のチェーンに移動したコインを標準チェーン側でロックしておくためのアドレスで、以下のフォーマットのscriptPubkeyになる。

ExtVer <eb_commitment>

ExtVerの値はおそらくEB毎に異なるものと思われる（例えば今回一緒に提案されているLIP-0003のMimblewimbleのEBでは「ExtVer」の値は0x09とされている）。

witness programの部分は2〜40バイトのeb_commitment。このデータは対応するEBのブロックへのコミットメントになる。LIP-0003だと、EBのブロック内のトランザクションカーネルとそのブロック時点のUTXOセットのデータから作られるコミットメントになる。

基本的に１ブロックあたりそのインテグレーショントランザクション内で１つのExtAddrが作られ、そこにEBに移動したコインの総量がロックされることになる。

EBに対応してしない旧ノードから見ると↑のscriptPubkeyは誰もが使用可能なアウトプットと認識される。

手数料

EB側の手数料は基本的にインテグレーショントランザクションの手数料として標準チェーン側で徴収される。

所感

以上が、Extension Blockを利用した拡張方法。

• Extension Block側のチェーンの仕様は自由に決められるので（EBのブロックサイズも自由に決められるし、トランザクション構造もまったく異なる仕組みが利用できる）、既存のコンセンサスにとらわれない拡張が可能なのは大きい。
• サイドチェーンライクでもあるけど、サイドチェーンと違って
  • Peg-in/outが単一のチェーンのコンセンサスとして担保されており、この点は重要。
  • EB側のブロック生成の手数料報酬も標準チェーンのコインとして入手できる。
• 一方、サイドチェーンと違って単一チェーンのフルノードとしての検証コストは増える。これはフルノードの分散化への影響があるのと、経済的な観点からマイナーによる導入の支持がどうなるか？という別の課題が生まれる。EB側のチェーンの報酬は手数料収入だけなので、標準チェーンとEB側のチェーンで手数料レートが変わる可能性も考えられる。

ちなみに、↑のExtAddrを利用してブロック単位で別のコインを管理する手法は、似たようなアプローチが以前、Confidential TransactionをBitcoinにソフトフォークで導入する際にも使われており↓、設計方法の１つとして他にも利用できそう。

techmedia-think.hatenablog.com

Bitcoinにアカウント機能を導入するLayer 2プロトコル「easypaysy」

BitcoinはUTXOモデルのブロックチェーンで、コインはアカウント単位ではなくUTXO単位（アドレス単位）に管理される。また、プライバシーの観点から支払い毎に異なるアドレスを使用することを推奨している。このような支払いは、コインの送金先のリンク性のハードルを上げることになるが、そのような知識を必要とする支払いはユーザーに複雑なUXを強いることになる。

これに対し、Bitcoinの支払いにおいても、各ユーザーが一意のアカウントを作成でき、各支払いもそのアカウントに対して行えるようにしようというのがLayer 2プロトコルとして提案されたeasypaysyプロトコルだ。ホワイトペーパーは↓

https://www.easypaysy.org/assets/easypaysy_white_paper.pdf

easypaysy プロトコル

easypaysyはBitcoinにアカウントベースの支払いを可能にするLayer 2プロトコルだ。実際の支払いは今まで通り支払い毎に新しいアドレス宛に送金するトランザクションが作られる訳だが、ユーザーはそのような事を意識することなく、ウォレットで毎回相手のアカウントを指定することでそのようなトランザクションを作成し、送金の受取側もそのような送金を検知するための仕組みをサポートするようになっている。

アカウントの作成

easypaysyを使った支払いをするためには、まずeasypaysyのアカウントIDを作成する必要がある。このアカウントはメールアドレスや銀行口座のようにユーザーを識別するためのIDで、アカウントベースの支払いをする際のIDとなる。このアカウントは以下の３つの情報を持つ。

• Identity key
  メッセージへの署名や、送金者と受取人の間で暗号化されたメッセージを交換するのに使われる公開鍵。
• Value key
  非対話型の支払いをする際に送金先の鍵の導出に使われる公開鍵。
• ランデブー記述子
  アカウントの所有者が受け入れる支払いのタイプと、送金者がアカウントと通信する際に使用することができるプロトコルとその方法を定義したJSONドキュメント。

easypaysyアカウントを作成するには、上記３つの情報を持つトランザクションを作成し、ブロックチェーンに記録する。具体的にどういうトランザクションを作成するかというと、

① まずIdentity keyとValue keyの２つの公開鍵を使って2-of-2のマルチシグを構成する。

2 <Identity key> <Value key> 2 OP_CHECKMULTISIG

これをP2SHアドレスに変換し、そのP2SHアドレス宛にコインを送金する。

② ↑のトランザクションがブロックに格納されたら、続いて、そのUTXOをインプットにした以下のトランザクションを作成する。

• Input
  1. Identity keyとValu keyのマルチシグのUTXO
• Output
  1. Identity keyとValu keyのマルチシグのUTXO（つまりインプットと同じP2SHアドレス）
  2. OP_RETURN <ランデブー記述子>

①で作成したP2SHがインプットにあるため、そのscriptSigを確認するとIdentity keyとValue keyの値が分かる。また、OP_RETURNを使ってランデブー記述子のデータを格納する。

このトランザクションがブロックチェーンに記録されると、アカウントに必要な３つの情報がブロックチェーンに記録されることになる。

②のトランザクションがブロックチェーンに格納され100承認されるとeasypaysyアカウントがアクティベートされる。

アカウントID

↑のようにeasypaysyアカウントがアクティベートされるとアカウントIDができる。easypaysyアカウントのIDはブロックチェーンに記録された②のトランザクションのデータから以下の形式で表現される。

btc@<ブロック高>.<ブロック内のトランザクションのindex>/checksum

ブロック高は②のトランザクションが格納されたブロックのブロック高で、.の後にそのブロック内に②のトランザクションが入っている位置が続く。

チェックサムの計算

チェックサムは以下のアルゴリズムで計算される。

1. ②のトランザクションが格納されたブロックのハッシュとマークルルートおよび②のWTXIDを結合し、そのハッシュ値を計算する。tx_digest = sha256(block chash || merkle root || wtxid)
2. 32バイトのtx_digestを8バイトずつの4つのデータに分割する。
   • tx_digest_0 = tx_digest[0..7]
   • tx_digest_1 = tx_digest[8..15]
   • tx_digest_2 = tx_digest[16..23]
   • tx_digest_3 = tx_digest[24..31]
3. 各tx_digest_xを1000で割ったあまりを計算する。
   • checksum_chunk_0 = tx_digest_0 % 1000
   • checksum_chunk_1 = tx_digest_1 % 1000
   • checksum_chunk_2 = tx_digest_2 % 1000
   • checksum_chunk_3 = tx_digest_3 % 1000

こうして計算した4つのチャンクがチェックサムデータになる。つまりチェックサムの値は、000-000-000-000から999-999-999-999の乱数とみなすことができる。

アカウントIDの表現方法

アカウントIDを表現する方法は３つある。

Canonical ID

Canonical IDは↑のアカウントIDの各データをそのまま10進数で表現する方法。

例えばブロック高が#543847のブロックの636番目トランザクションの場合のCanonical IDは、btc@543847.636/577-218-376-867。

尚チェックサムは必ずしも4つすべて表記する必要はなく、btc@543847.636/577と省略してもいい。

Mnemonic ID

Mnemonic IDは↑のアカウントIDの各データをBIP-39のニーモニックワードを使って表現する方法。

↑のCanonical IDをMnemonic IDで表現するとbtc@cancel-mind.exhibit/motion-custom-fun-sugarとなる。

Domain ID

３つめのDomain IDは、DNSを利用した表現方法で、チェックサムが付いたアカウントIDを自身のドメインのTXTレコードに挿入するというもの。DNSに対してクエリするとそのドメインに対応するアカウントIDを返すという仕組み。

ランデブー記述子

アカウント情報の１つであるランデブー記述子は、アカウントの所有者が受け入れる支払いのタイプと、送金者がアカウントと通信する際に使用することができるプロトコルとその方法を定義するもので、②のトランザクションアウトプットでOP_RETURNを利用して記録される。

実際に定義されるのは以下のようなJSONデータになる。

{
 "Document_name": "EASYPAYSY_RENDEZVOUS_DESCRIPTOR",
 "Version": "0",
 "Accepted_payments": [
   "TYPE_1_RENDEZVOUS",
   "TYPE_2_IOC_OVERT"
 ],
 "Mail": "fiber.burden.erupt@gmail.com",
 "Bitmessage": "BM-2cTZhb···NnZTjC69ke9BieU"
}

• Document_name: easypaysyドキュメントを識別する文字列の固定のリテラル
• Version: ランデブー記述子のバージョン
• Accepted_payments: アカウント所有者受け入れる支払いのリスト。現在可能なのは以下の４種類で、アカウントは少なくともこのペイメントタイプの１つを受け入れる必要がある。
  • TYPE_0_UNSAFE_FIXED
  • TYPE_1_RENDEZVOUS
  • TYPE_2_IOC_OVERT
  • TYPE_3_IOC_COVERT

※ Bitcoinの標準トランザクションのルールとして、OP_RETURNで登録可能なデータは80バイト以内であることという制限があるため、↑のJSONをそのまま記録しようとするとサイズオーバーになる。そこでeasypaysyでは、最適化された辞書ベースの圧縮アルゴリズムを使ってJSON形式のランデブー記述子をシリアライズして記録する。この圧縮アルゴリズムを使用すると↑のサンプルは7バイトになると。

支払いタイプ

easypaysyでは以下の4種類の支払いタイプをサポートしている。

TYPE_0_UNSAFE_FIXED

TYPE_0の支払いタイプは、各支払いにおいて常に同じアドレス、具体的にはValue keyに関連付けられたアドレスを使用する必要がある。これはプライバシーの欠如にもなるため基本的に推奨されていない。

TYPE_1_RENDEZVOUS

TYPE_1は、対話型の支払いで、支払いの都度、受取人と対話して支払先のアドレスを導出する。この支払いタイプを使用する場合、ランデブー記述子に定義された連絡プロトコル（https, メール、Bitmessage、MQTT）とそのエンドポイントに従って、支払人が受取人に連絡し、支払先のアドレスを受け取る。この時、受取人は支払先のアドレスと一緒に受取人のeasypaysyアカウントのIdentity keyでアドレスに署名した署名データも一緒に返す。この署名データから、そのアドレスが確かに受取人によって承認されたアドレスであることを証明できるため、受取人による送金の否認防止につながる。

TYPE_2_IOC_OVERT, TYPE_3_IOC_COVERT

TYPE_2とTYPE_3は両方とも非対話型の支払い。IOCはInversion Of Controlの略で制御の反転、つまり支払いプロセスの制御を反転させ、各支払の宛先アドレスを選択するのは受取人ではなく支払人であるということを意味する。このためTYPE_1と違って、支払いの都度、受取人と対話する必要はなく、ランデブー記述子にも連絡プロトコルを定義する必要はない。

ボブからアリス（Value key = A = a * G）へeasypaysyアカウントを使った非対話型の支払いをする手順は以下の通り。※ アリスのeasypaysyアカウントはすでにチェーン上に公開されているとする。

1. ボブは支払いに使用するキーペア：B = b * Gを作成する。
2. ボブは以下の方法でnを計算し、それを秘密鍵とした公開鍵Nを計算する。
   • n = sha256(b * A) = sha256(b * a * G)
   • N = n * G
3. ボブは別の公開鍵Cを以下の方法で計算する。
   • C = A + N （ボブはアリスのeasysypaysyアカウントからアリスのValue key = Aを知っている）
   • C = c * G = (a + n) * G （この時点でボブはaを知らないのでcを計算できず、アリスもnを知らないのでcを計算できない）
4. ボブはCから送金先アドレスを導出し、最低２つのアウトプットを持つ支払いトランザクションを作成する。このアウトプットの１つはC宛の支払いで、もう１つはOP_RETURNアウトプットでBのデータが含まれる。このトランザクションをブロードキャストし、アリスにWTXIDを通知する（TXIDでもいいような？）。
5. アリスはボブから通知を受け取るか、トランザクションを監視し、4のトランザクションについて以下を行う。
   1. OP_RETURN からBを取得する。
   2. nおよびc, Cを計算する。
      • n = sha256(a * B)
      • c = a + n
      • C = c * G
6. アリスは4のトランザクションアウトプットにC宛の送金があるか確認する。アリスはそのコインを使用するために必要な秘密鍵cをこの時点知っているので、このコインはアリスのものになる。（ボブはaを知らないのでCのコインは使えない）

また、一度支払いをしてしまえば、その後の支払いではOP_RETURNに含めるBのデータを（支払い回数をiとした場合 i || bなどで）決定論的に導出すれば、OP_RETURNアウトプットを含める必要はなくなる。

なお、OVERTとCOVERTの違いは、OP_RETURNで公開鍵を伝える際にそのプレフィックスにEP(hexだと4550)を付与するかどうかという点だけ。OVERTの場合、EPが付くのでそのトランザクションがIOC支払いであることが明確になり、スキャンする側の負荷が軽減する。一方COVERTの場合プレフィックスが付かないため第三者のオブザーバーがいたとしてもIOC支払いであることを確実に判断するのが困難になる。

IOC支払いの否認防止性

IOC支払いの場合、非対話型のため実際にCのコインをアリスがアンロックできることを明示的に証明することができない。対話型の場合、受信側のアドレスへの署名データがあるため、その署名データによって否認防止性が担保できる。そのため、IOC支払いの場合、公平な第三者に支払いに使ったbの値を開示することで、それがアリスの鍵から導出可能であることを証明することができる。

通信の暗号化

支払人と受取人の間の全ての通信はECIESプロトコルを使って暗号化される。このセキュリティプロトコルはアカウントのIdentity keyを使ったECDH鍵交換を利用した共有AES鍵を使って行われる。

※ 実際にIdentity keyが使わるのは最初の通信のみで、後はメッセージ内のEncrypt_answer_with_public_keyで指定した一時鍵が使われる。

アカウントの更新

アクティベートされたアカウント情報（ランデブー記述子）はいつでも更新することができる。②のマルチシグのUTXOを使用するトランザクションを作成し、そのトランザクションアウトプットに更新したランデブー記述子を定義する（もう１つのトランザクションアウトプットは同じマルチシグのP2SH）。

アカウントの削除

アカウントを削除する場合は、アカウントのマルチシグのUTXOを、全く異なるアドレス宛に送金するだけ。

所感

• 非対話で支払先のアドレスを導出するプロトコルは今までもステルスアドレスや、BIP-47のペイメントコードなどで提案されてきたけど、これらと違って基点となるアカウント情報もブロックチェーンで管理するというのが新しい試み。
• Layer 2プロトコルを設計する際にランデブー記述子のようなメタデータをOP_RETURNに登録することはよくあるが、80バイト制限もあるので、OP_RETURNにはエンドポイントのみ記録して、実際の定義値はそのエンドポイントで公開するというアプローチが多い。ただその場合、エンドポイントが公開しているデータが不変であるという確証はないので、不変性を担保するのであればデータはブロックチェーン上に記録された方がいい。そういう意味で、easypaysyは専用の圧縮アルゴリズムを使って直接メタデータを記録するアプローチを取ってる。JSONである必要があるかは疑問だけど。
• BitcoinのUXを改善するためにUTXOやそれに付随するアドレスの仕組みをできるだけエンドユーザーに意識させない方が望ましい。そういった意味ではアカウントベースの見せ方の方が向いてそう。
• ↑の解説以外にもプル型の定期支払いの仕組みやスケーリングのための仕組みがホワイトペーパーには定義されている。

Bitcoinネットワークのトポロジーを推定するTxProbe

Scaling Bitcoin 2019復習シリーズ第三弾は、「TxProbe: Discovering Bitcoin's Network Topology Using Orphan Transactions」

• 動画：https://youtu.be/-gdfxNalDIc?t=11751
• 書き起こし： http://diyhpl.us/wiki/transcripts/scalingbitcoin/tel-aviv-2019/txprobe/
• ホワイトペーパー： https://arxiv.org/pdf/1812.00942.pdf

TxProbeは、Bitcoinネットワークのネットワークトポロジーを推定するための方法。ここで推定するBitcoinネットワークは基本的にパブリックに到達可能なノードで構成されるネットワークで、NATやファイアウォールの背後にあり到達不可能のノードや、インバウンド接続を受け入れないノード（軽量ノードなど）は対象外となる。

※ Bitcoin Coreはデフォルトで８つのアウトバウンド接続を作成する。この時選択される接続先のピアはランダムに選択されるが、/16 (ipv4)ネットワークセグメントが重複しない形で選ばれる。またこの他にインバウンド接続を受け入れる。

到達可能なノードについては、Bitnodesなどのサイトで確認できる。Bitnodesでは、getaddr/addrメッセージを利用して入手したノードに実際にアクセスするクローラーを利用して到達可能なノードを検出している。ただし、こうやって得られるのは到達可能なノードの情報のみと、それらのノードがどのようなネットワークトポロジーを形成しているかは分からない。

このノード間のエッジを推定しネットワークトポロジーを推定するための手法がTxProbeだ。

オーファントランザクションと二重使用トランザクションの扱い

TxProbeの調査方法は、Bitcoin Coreのオーファントランザクションと二重使用トランザクションのハンドリング方法に依存している。

トランザクションのハンドリング

ノードがトランザクションを受信し、検証するとそのトランザクションはメモリプールに格納され、接続中のピアに伝播される。ノードは直ぐに接続中のピアにトランザクションを送るのではなく、まずinvメッセージを使ってトランザクションの存在を通知する。そして、送信先のピアが該当トランザクションを持っていない場合getdataメッセージでトランザクションデータ自体を要求する。既に該当トランザクションを持っている場合はgetdataメッセージは送られない。

オーファントランザクションのハンドリング

オーファントランザクションのハンドリングは通常のトランザクションのハンドリングとは異なる。オーファントランザクションはそのインプットが参照するUTXOのトランザクションがまだそのノードに届いていないので、オーファントランザクションを受信してもそのトランザクションが有効なトランザクションかどうか検証することができない。そのためノードはMapOrphanTransactionsとして知られるメモリプールとは別のオーファンプールに格納される。またトランザクションの検証が出来ていないためこのオーファントランザクションが接続中のピアにリレーされることもない。

二重使用トランザクションのハンドリング

二重使用トランザクションは単純に同じコイン（UTXO）を使用する２つめのトランザクションで、このトランザクションを受信したノードは、最初のトランザクションのみを受け入れ、２つめの二重使用トランザクションは受け入れない。

基本的なネットワーク・トポロジーの推定手法

上記のトランザクションのハンドリング方法を利用すると、次のようにしてネットワーク・トポロジーの推定ができる。

まず以下の３つのトランザクションを作成する。

• 親トランザクション（）
• マーカートランザクション（）
  親トランザクションのコインを使用する子トランザクション
• フラッドトランザクション（）
  親トランザクションと同じコインを使用する二重使用トランザクション

BitcoinやBitcoinベースのアルトコインのネットワークのテストや監視、測定を行えるツールであるCoinscope*1を使用し、アリスとボブ２つのノードと接続するネットワークを仮定する。

アリスとボブのノード間のエッジが存在する場合

Coinscopeで、

• アリスのノードにはを送信する。
• ボブのノードにはを送信する。

これが同時に到着すると仮定した場合、アリスはボブにをボブはアリスにをリレーしようとするが、お互いにとって通知されたトランザクションは二重使用トランザクションであるため、両者とも受けとったトランザクションを拒否する。

その後アリスにを送信する。を受け取ったアリスは、それをボブにリレーする。この時点でアリスとボブのメモリプールとオーファンプールの状態は以下のようになる。

	アリス	ボブ
メモリプール	,
オーファンプール

アリスとボブのノード間にエッジが存在する場合、上記のようにボブのノードのオーファンプールにはが存在している状態になる。このエッジが存在するかどうかの確認はCoinscopeが、ボブのノードに対してを通知するinvメッセージを送信した際のボブのノードの反応で判断できる。ボブとアリスの間にエッジが存在すれば、ボブはをオーファンプールに持っているので、invに対してgetdataを要求することはない。逆にアリスとボブのノード間にエッジが無ければ、ボブはについて知らないので、Coinscopeのinvに対してgetdataを要求する。

以下はアリスとボブの間にエッジが存在しないパターンの構成：

アリスとボブのノード間のエッジが存在しない場合

で、アリスとボブのメモリプールとオーファンプールの状態は↓

	アリス	ボブ
メモリプール	,
オーファンプール

と簡単にエッジ検出できそうに思えるが、これはあくまでノード数が２つの場合に機能するが、ノード数が増えると破綻する。例えばアリスとボブの間にキャロルのノードが加わった場合に、Coinscopeがアリスにを送った際、をアリスがキャロルにリレーするのを止められないので、ノードが増えると上記の手法はワークしない。

TxProveのトポロジー推定手法

上記の基本的な推定手法を、多くのノードが存在する状況で行えるようにするためには、TxProveでは、invBlockと呼ばれる手法を利用する。invBlockというのは、トランザクションを通知する際にinvで通知し、その要求がgetdataで来た際にトランザクションの送信を2分間ほど保留することでトランザクションの伝播を防ぐ手法（2分以上経過すると別のノードに問い合わせる）。

例えば、アリス、キャロル、ボブのネットワークを考える。

invBlockの動作

まず、Coinscopeが全ノードに対して、のinvを送信する。すると３ノードともそのトランザクションを要求するgetdataで返信するが、このうちアリスの要求に対してのみtxメッセージでを送る。するとを受信したアリスがキャロルに対してのinvを送信してもキャロルはすでにCoinscopeから最初にのinvを受け取っているので、アリスのinvには応答せず２分間待機している。続いてをボブに送信すると、ボブはそれをキャロルにリレーする。またをアリスに送信すると、それはキャロルにリレーされるが、キャロルはを持っていないのでをオーファンとして扱い、各ノードの状態は以下のようになる。

	アリス	キャロル	ボブ
メモリプール	,
オーファンプール

上記のようにinvBlockの仕組みを利用することで、対象トランザクションを特定のノードに固定することができるので、この仕組みを利用して以下の手順でトポロジーを計測する。

1. ターゲットノードを選択
2. ターゲットノード用に親、マーカー、フラッドトランザクションを作成する。
3. invBLockを実行する。
4. ターゲットノード以外の全ての接続ノードにフラッドを送信し、フラッドを伝播させる。
5. 親をターゲットに送信する。
6. マーカーをターゲットに送信する。
7. マーカーが伝播する。
8. ターゲットを除くすべてのノードにマーカーを要求する。

ネットワーク内の全てのノードに対して↑を実行する。

TxProbeのコスト

mainnet（約１万のノード）でTxProbeを実行するコスト見積もりは以下のようになっている。

• 時間： 8.25時間
• 手数料 = (5 sat/byteとした場合) 573210〜764280 satoshi（$20〜$30）

実際にmainnetでは検証されておらず、testnetで40回ほど検証が施行され、グラフ分析した結果が↓のような結果だったみたい。観測されたネットワークにはノードが733個で、6090個のエッジがあり、平均して16.6の接続数となっている。

testnetのノードの接続数の分布

testnetのノードグラフ

サークルの大きさは接続数の多さを表現しており、色がコミュニティを表している。ランダムグラフよりも高いコミュニティ構造を持ったグラフになっている。testnetとmainnetではインセンティブも違うのでこの傾向がmainnetにもそのまま当てはまるということはないだろうが、実際にmainnetでどのようなネットワークトポロジーが形成されているかは観測してみないと分からない。この辺、誰かmainnetで計測したりしないかなー。

なお、TxProbeは↑のようなBitcoin Coreのトランザクションのハンドリング方法に依存した仕組みなので、トランザクションの伝播方法が変わるといずれそのままでは使えなくなってしまうだろう。

*1:他のノードに接続し、接続を維持するBitcoinのネットワークプロトコルをしゃべるConnectorと、Connectorに対して要求を送る（あるノードに接続したり、メッセージを送信したりなど）Clientで構成される。

Bitcoinの新しいテストネットワーク「Signet」の仕様を定義したBIP-325

Bitcoin関連のテストを行うのに便利なtestnetだが、ブロックの生成間隔がまばら（30分くらい生成されなかったり、数秒で連続してブロックが生成されたり）だったり、巨大な再編成が起こったりとあまり安定していない。そのためテストになかなか使いづらくなっていた。このような問題を解消するため新しいタイプのテストネットワークがBIP-325として提案された↓

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

Signetでは既存のProof of Workの検証に加えて、ネットワーク起動時に予め設定するチャレンジと呼ばれるscriptPubkeyに対する有効な解答（scriptSig）が提供されるか検証するようになっている。ざっくり言うとPoAタイプのテストネット。

具体的には、ノード起動時に

$ ./bitcoind -signet_blockscript=<scriptPubkey(hexフォーマット)>

のように-signet_blockscriptオプションを使ってチャレンジのscriptPubkeyを指定する。これはP2PKHであってもいいし、k-of-nのマルチシグなどであってもいい。またこのブロックスクリプトによってSignetのジェネシスブロックのデータも異なる。詳細はこちら。

-signet_blockscriptオプションで起動されたチェーンは、ブロックをマイニングする際に有効なPoWの他、そのブロックのコインベーストランザクションのwitness commitment内にscriptPubkeyに対して有効な解答（scriptSig）を含める必要がある。有効なscriptSigが無い場合無効なブロックと判定される。この時、scriptSig内の署名および署名検証の際に使われるメッセージダイジェストは、ブロックから生成される（詳細は以下BIP参照）。

そのため、-signet_blockscriptに対応する有効な解答が作れるメンバー＝対応する秘密鍵を保持し署名を付与できるメンバーしかブロックが作れなくなる。つまり予め決められたこれらのメンバーによりそのsignetのブロックは作られていくことになる。

以下、BIPの内容↓（仕組みの概要は書かれてるけど、Bitcoin Wikiの方がカスタムSignetの立て方など具体的に書いてて参考になるかも。）

2020/05/08時点の内容で更新

概要

複数の独立した参加者が関与する長期的なテストシナリオのため、ブロックの進行に対してProof of Workに加えて署名が使用される新しいタイプのテストネットワークにより、優れた調整と堅牢性を実現する。

動機

Testnetは実際のお金を危険に晒すこと無く新しいことを試すのに最適な場所だが、信頼性が低いことで有名だ。巨大なブロックの再編成や、マイニング中のブロック間に長いギャップが生じたり、また急に連続してブロックが作成されるバーストは、特に長期間に渡ってソフトウェアを実行する複数の独立した参加者が関与するソフトウェアの現実的なテストが実際に実行不可能となることを意味する。

新しいタイプのテストネットワークは、取引所などの組織による結合テストや、eltooやサイドチェーンペグなど次世代のLayer2プロトコルのテストにより適しいてる。目標は完全に信頼できることではなく、むしろ予測可能な非信頼性の量を持つことである。テストネットワークがmainnetと同じように動作する（つまり数千のブロックの再編成などはない）のと同時に、６ブロックの再編成などの予想される稀なイベントをトリガーしやすくする必要がある。Regtestはブロックの作成にコストがかからないため、複数の独立した参加者が関係する長期的シナリオには適していないため、どの参加者もテストネットワークを完全に制御できる。

仕様

新しいタイプのネットワーク「Signet」はチャレンジ（scriptPubkey）と呼ばれる追加のコンセンサスパラメータを受け取る。このチャレンジは単純なpubkey（P2PKHスタイル）、k-of-nのマルチシグもしくはその他の必要なスクリプトにすることができる。

コインベーストランザクションのwitness commitmentは、２つ目のコミットメント（署名/解答）を含むよう拡張される：

1-4 bytes - 以下の (x + 4) byteをプッシュする
4 bytes - Signetヘッダー (0xecc7daa2)
x bytes - 解答 (sigScript)

4バイトのSignetヘッダーで始まらないプッシュ操作は無視される。4バイトのSignetヘッダーを持つ複数のプッシュ操作は、最初のエントリーを除いて無視される。

チャレンジ内に含まれる全ての署名操作はSHA256d(modifiedBlockHash)、つまり以下のデータのダブルSHA256ダイジェストをsighashとして使用する：

型	サイズ	名前
Int32	4	nVersion
Uint256	32	hashPrevBlock
Uint256	32	modifiedMerkleRoot
Uint32	4	nTime
Uint32	4	nBits

modifiedMerkleRootハッシュは、コインベースのwitness commitmentに上記Signetの拡張が含まれない状態のブロックトランザクションのマークルルートを生成することで取得できる。これは、ブロックのマークルルートがSignet commitment内のマークルルートと異なることを意味する。これは署名されるメッセージ（この場合ブロック）に署名を含めることはできないためだ。署名とは別にブロック生成（マイニング）を簡単にするために、ブロックのnonce値はSignetの署名がコミットしないブロックの他の唯一のコンポーネントだ。Proof of Workを回していくのに、拡張用nonceは使用できない。これはそれを行うと署名が無効になるためだ。代わりに同じ（もしくは更新された）ブロックに再署名することで、Proof of Workの新しい計算スペースが得られる。

上記のコミットメントが見つかった場合、その解答が有効であれば、ブロックは完全に検証されたとみなされる。この検証はwitness commitmentの検証の前後に直接行うのを推奨する（両者の検証で必要なデータはほぼ同じであるため）。

ジェネシスブロックとメッセージスタート

全てのsignetネットワークにおいてジェネシスブロックは同じだが、メッセージスタートはシングルプッシュで定義されるチャレンジスクリプトのDouble-SHA256の先頭４バイト（以下参照）。

ジェネシスブロック

• Time stamp: 1534313275
• Nonce: 100123
• Difficulty: 1e2adc28

この結果、ジェネシスブロックのハッシュは0000032d7f67af9ec7b7152aea0fe7c95b9804ff973265e252f245e0ae61799dで、ブロックのHex値は、

0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a3bc3735b28dc2a1e1b8701000101000000010000000000000000000000000000000000000000000000000000000000000000ffffffff4d04ffff001d0104455468652054696d65732030332f4a616e2f32303039204368616e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f722062616e6b73ffffffff0100f2052a01000000434104678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5fac00000000

メッセージスタート

メッセージスタートはシングルプッシュで定義されるチャレンジスクリプトのDouble-SHA256の先頭４バイトとして定義される（つまりチャレンジスクリプトの長さがプレフィックスになる）。

• チャレンジスクリプト = 512103ad5e0edad18cb1f0fc0d28a3d4f1f3e445640337489abb10404f2d1e086be43051ae
• Sha256d(長さ || チャレンジスクリプト) = sha256d(25512103ad...51ae) = 7ec653a59b1912f9db10da2c461ed827d48f9404d5ef0346a6c94aadd4203646
• 先頭４バイト = the message start = 7ec653a5

互換性

この仕様は、既存のソフトウェアがすぐにSignetを使用できるという意味で後方互換性がある。

Signet用のネットワークパラメータ（マジックナンバーなど）を追加するだけで、クライアントは変更を加えることなく任意のsignetネットワークに接続して使用できる。ブロックヘッダーには有効なproof of workがあるため、クライアンはブロックが「おそらく」有効であることを簡単に確認できる。

ただし、特定のsignetネットワークでクライアントが受け入れたブロックは誰でもマイニングができる。ただし、これらのブロックには必要な署名が含まれていないため、完全な検証を行うノードはすぐにそのブロックを拒否する。そのため、クライアントはコインベーストランザクション内のブロックの署名を検証するか、信頼できるピアに接続する必要がある。

他のソフトウェアは本番環境で使用しないブロックの署名検証コードを追加する必要はない。これはネットワークが可能な限りmainnetのように動作することが目標である非実稼働のテスト目的に適している。

参照実装

https://github.com/bitcoin/bitcoin/pull/16411

2者間の非対話型CoinJoinプロトコルSNICKER

2者間で、同期や対話なくCoinJoinを作成する新しいプロトコルSNICKER(Simple Non-Interactive Coinjoin with Keys for Encryption Reused)が提案されている↓

https://gist.github.com/AdamISZ/2c13fb5819bd469ca318156e2cf25d79

提案者のブログポストは↓

joinmarket.me

CoinJoinとは？

CoinJoinプロトコルはUTXOセットを難読化/ミキシングするのに有名な手法で、古くはShared CoinやDarkWallet、最近だとJoinMarketやWasabi Wallet、Samouraiなどで利用されている。

もともと2013年にGregory Maxwellによって提案されたプロトコルで管理者などの中間者無しでミキシングを行うためのプロトコル。ミキシングの参加者は送金額を満たすインプットとアウトプット（必要に応じてお釣り用のアウトプット）を提供する。この時アウトプットのコインの量は（お釣りを除いて）全て同じ額になる。各自が持ち寄った情報からミキシングトランザクションを作成する。各参加者が所有するインプットへの署名は、このトランザクションに対して行われるので、自身のコインが第三者に盗まれるということはない。理想的なCoinJoinのトランザクションはインプットとアウトプットの金種（コインの量）が全て等しいトランザクションになる。

CoinJoinの課題

↑に理想的なトランザクションと書いたけど、CoinJoinの難点は、参加者間の調整が必要だという点で、参加者が強力な匿名性を確保したい場合は特に難しくなる。この課題のソリューションの１つとして、CoinJoinトランザクションを作成する調整用のサーバーを使用する方法もあるが、ユーザーのプライバシーを低下させるトレードオフになり、攻撃に対して障害点となりやすい。

またそんなサーバがいない場合、シビル攻撃によりプロトコルの妨害をしたり、参加者のプライバシーを損なうような攻撃を効果的に実行できる。

SNICKERプロトコルとは？

SNICKERは、上記の参加者間の調整や同期を不要にすることで、この調整のトレードオフを解消するCoinJoinプロトコル。必要なのは片方のユーザーが暗号化されたデータをブロードキャストし、それをもう1方が受信するだけ。この受信はラジオや衛星を介して行われる可能性もあるため、何が起きたかを全て知ることは物理的に不可能となると（カジュアルにそこまでやることができればだと思うが）。

具体的には、提案者がブロックチェーンの情報のみを使って、別の参加者のアウトプットを推定し、部分的に署名されたCoinJoinトランザクションを作成する。そしてそのトランザクションを受信者が複合できる形で暗号化して何らかの方法でブロードキャスト（公開）する。作成するCoinJoinトランザクションは、ブロックチェーン上で確認できる公開鍵から（アドレスの再利用かもしくはトランザクションインプットの中にある公開鍵から抽出して）作られる。

※ ただし、SNICKERのCoinJoinモデルは2者間のみのCoinJoinであるという意味で非常に制限されたものになる。

現在SNICKERプロトコルにはバージョン0とバージョン1の２つのプロトコルが提案されている。

SNICKER Protocol version 0

バージョン0はアドレスの再利用が前提のプロトコルになる。

提案者がやること

提案者は、再利用されるアドレスのセットを特定する。具体的には、現在未使用のUTXOがあり、それと同じアドレスが以前に少なくとも1回使用済みであるアドレス。このアドレスA毎に、以前そのアドレスのコインが使用されたトランザクションを見つけて、そのアドレスの公開鍵を見つける。続いて、以下の手順を実行する。

1. 提案者自身のUTXOを１つ見つける。このUTXOのコインの量は↑ののUTXOのコインの量と2-of-3のトランザクションの手数料を加えた額以上のコインの量を持っている必要がある。
2. 1で見つけた提案者のUTXOの公開鍵をQとするとQとでECDHしたtweek を計算する。
3. Aの新しいアドレスを公開鍵を使って計算する。
4. 以下のCoinJoinトランザクションを構築する。
   • Input：のUTXOと提案者自身のQのUTXOの２つ。
   • Output：から導出した新しい公開鍵から生成したアウトプットと、提案者の新しいアウトプットアドレス２つ（O1、O2）。O1はが受け取るのと同額を受け取り、O2はお釣り用のアウトプット。
5. 提案者は自身のインプットに署名をする。
6. 提案者は自身の署名を加えたトランザクションとtweakの値cをシリアライズし、それをメッセージMとし、を使ってECIESの暗号化スキームで暗号化したProposalを作成する。
7. 作成したProposalを掲示板に公開する。

受信者がやること

受信者は再利用したアドレスを記録しておく必要がある。このアドレスを上記と同じようにAと呼ぶ。

受信者は定期的に掲示板をチェックし、暗号化されたBlobを全てダウンロードする。各Blobについて（このバイナリBlobをoとする）、ECIESの復号スキームを実行し、復号を試みる（ここではアドレスAの秘密鍵）。復号化したデータについて以下をチェックする。

• 先頭7バイトがSNICKERマジックバイト0x534e49434b4552かどうか。
• versionが0x00かどうか

チェックをパスするとシリアライズされた値cと部分的に署名されたトランザクションが復号されているので、続いて以下の処理を行う。

1. トランザクションアウトプットの１つが自身のアドレスAから導出したから作られたアドレスであること。
2. 1の秘密鍵鍵をウォレットにインポートする。
3. BIP-174ベースの部分的に署名されたトランザクションについて悪意ある脆弱性が無いかチェックする。具体的には、
   • トランザクションのバージョンが02で、ロックタイムは0、インプットのsequenceが0xffffffffであるかチェックする。
   • 署名が１つのインプットに対して有効なものであるか検証する。このインプットと署名は提案者のもので受信者のものではない。
   • 署名されていないインプットの所有権を自身が持っているか確認する。
   • を再構築できるか検証する。
   • 自身の使用する金額と新たに受信する金額を確認する。
   • 手数料が現在のネットワークで適切な額が確認する。ブロードキャスト後手数料を上げる場合、RBFは使えないので、CPFPを使うことになる。
4. 全てのチェックが問題なければ、受信者はPSBTフォーマットのトランザクションに自身の署名を追加し、有効なBitcoinトランザクションを完成させ、Bitcoinネットワークにブロードキャストする。

なお、受信者が↑のトランザクションを受け取った時点で、別の参加者によってConJoinが行われるなどで既に提案者のUTXOが使用済みである可能性はある。そのようなケースがあったとしても受信者が資金を失うようなことは無い。

SNICKER Protocol version 1

バージョン1がほとんどバージョン0と同じプロセスだが、アドレスを再利用しないという点が異なる。

バージョン0では提案者はブロックチェーンをスキャンしてアドレスの再利用を検知して、そこから未使用のUTXOの公開鍵を検知してるため、アドレスの再利用が前提だった（ほとんどのトランザクションは公開鍵のハッシュのコインをロックしてるので、公開鍵が分かるのはそれを使用する時）。しかしBitcoinトランザクションのscriptSigには他にも公開鍵として利用可能なデータがある。

その１つがECDSA署名の署名データだ。ECDSAの署名値(r, s)においてrは署名用に選択したnonce kから導出した点R = kGのx座標だ。このRを↑のの代わりに使うことでアドレスの再利用を必要としないSNICKERプロトコルが可能になる。（ただし、そのTxの署名者であることの推定が必要になるが）

基本的にBitcoinの代表的なウォレットであれば、署名生成の際にランダムに選択するnonce kの値はRFC6979に従って署名対象のトランザクションデータから決定論的に導出される*1。つまり、署名をしたウォレットであればkの復元が可能である。

まとめ

CoinJoinを行う際はどうしても対話型になるが、SNICKERは参加者の対話なく2者間のCoinJoinを行う新しいプロトコルの提案だ。

基本的にはCoinJoinを行いたい提案者が適当なUTXO（基本的にはアドレスが再利用されているUTXO）を見つけ、自身のUTXOを加え2者間のCoinJoinトランザクションを構築する。その際、相手のアドレスは、相手の公開鍵と自身の秘密鍵を使ってECDHを実行し共有シークレットを生成し、そのシークレットから生成した点を相手の公開鍵に加算して新たな公開鍵＝アドレスとする。自身の署名を加えたら相手の公開鍵を利用してトランザクションデータと共有シークレットをECIESで暗号化して、そのデータを公開する。

公開したデータを発見した受信者は、内容を確認して問題なければ自身の署名を付与してブロードキャストする。

提案者と受信者の間には直接的な通信は発生しない。ブロックチェーンからスキャンしたUTXOに対応する受信者がSNICKER利用者でマッチするかという課題や受信者にインポートが必要な鍵の管理についての課題はある。

*1:https://techmedia-think.hatenablog.com/entry/2017/02/08/205627