Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f:id:techmedia-think:20191115134054p:plain
アリスとボブのノード間のエッジが存在する場合

Coinscopeで、

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

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

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

アリス ボブ
メモリプール  {tx_P},  {tx_M}  {tx_F}
オーファンプール  {tx_M}

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

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

f:id:techmedia-think:20191115135805p:plain
アリスとボブのノード間のエッジが存在しない場合

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

アリス ボブ
メモリプール  {tx_P},  {tx_M}  {tx_F}
オーファンプール

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

TxProveのトポロジー推定手法

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

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

f:id:techmedia-think:20191115185556p:plain
invBlockの動作

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

アリス キャロル ボブ
メモリプール  {tx_P},  {tx_M}  {tx_F}  {tx_F}
オーファンプール  {tx_M}

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

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

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

TxProbeのコスト

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

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

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

f:id:techmedia-think:20191115191811p:plain
testnetのノードの接続数の分布

f:id:techmedia-think:20191115191849p:plain
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の立て方など具体的に書いてて参考になるかも。)

概要

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

動機

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

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

仕様

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

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

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を使用できるという意味で後方互換性がある。

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

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

SNICKERプロトコルとは?

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

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

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

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

SNICKER Protocol version 0

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

提案者がやること

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

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

受信者がやること

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

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

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

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

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

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

SNICKER Protocol version 1

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

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

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

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

まとめ

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

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

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

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

AMPを実現する3つのプロトコル

Lightning Networkにおいて、単一の経路ではキャパシティが不足し送金額に満たないが、複数の経路を使えば送金額を満たす場合に、複数の経路を使った支払いをアトミックに行うプロトコルがAtomic Multi-Path Payments(AMP)だ。

AMPのプロトコルとしては、以下の3つのプロトコルが提案されている。

プロトコルがどのようなものかというと

OG AMP

OG AMPはとOlaoluwa Osuntokun(@roasbeef)とConner Fromknechtが発表したAMP。

通常のLNの支払いでは受信者がプリイメージを生成し、そのハッシュをInvoiceで通知するが、OG AMPの場合、送信がベースプリイメージを生成する。AMPで使用する経路の数をnとすると、送信者はn個のシェアを生成し、それらの排他的論理和を計算してベースプリイメージを生成する。

ベースプリイメージ = s1 ^ s2 ^ .... ^ sn

続いて、各 {i \in }[1..n]をシーケンス番号とし、iとベースプリイメージを連結しハッシュした部分的なプリイメージ {r_i = H(BP || i)}を計算する。そしてi番目の経路の支払いで使用するハッシュ {h_i = H(r_i)}を計算する。

送信者は {h_i = H(r_i)}を各経路の支払いに使用し、支払いをスタートするが、受信者のHop Payloadの中にのみ {(ID, n, s_i)}を暗号化しておく(IDはAMPの支払いを識別するためのランダムな値)。

受信者は、上記AMPの部分的な支払いを複数の経路で受信すると、同じIDのデータをn個集める。n個揃うとその排他的論理和は取ればベースプリイメージBPが復元できる。BPが復元できたら、各部分的な支払いを受け取るために必要な {h_i}のプリイメージ {r_i}を計算することができ、この値を使って全経路のコインを受け取る。

各経路でベースプリイメージのシェアを配布することで、全経路分のシェアが集まらないとコインが受け取れないという意味で、複数の経路を使った支払いのアトミック性を担保する。

というのがOG AMPだが、元々LNではプリイメージを受信者が生成して、支払いが完了したらそのプリイメージが送信者に分かるという仕組みになっており、送信者にとってプリイメージは送信が正常に行われたことの暗号学的な証明になっていた。ところがOG AMPの場合、送信者がプリイメージを生成するため、この証明の仕組みが機能しなくなるという欠点がある。個人間送金などであれば問題ないけど企業間決済などのエンタープライズユースケースにおいてはこの証明を必要とするパターンも考えられる。

Base AMP

OG AMPの支払いの証明を課題を解決するため、Base AMPでは各支払いの経路で全て同じpayment_hashを利用する。

受信者がbasic_mppフィールドを含むオニオンパケットを受信した場合、受信ノードはBase AMPである可能性があると認識する。受信ノードは全ての経路の支払いが揃うまでプリイメージを明らかにしない。そのために、basic_mppのオニオンパケットを受け取った場合は他の経路のHTLCを受け取るまで60秒待つ。これは、悪意ある中間ノードが複数の経路にいた場合、片方の経路で入手したプリイメージを使って、別の経路の資金を入手するような可能性を阻止するため。OG AMPでは経路毎のpayment_hashが異なるのでこれを防げる。payment_hashが同じHTLCを集め、その送金額の合計がtotal_msatで指定された額になったら、同じタイミングでコインを受領する。

Base AMPの場合、全ての経路の支払いの受領タイミングのコントロールをアトミックに制限することはできず受信ノードの振る舞いに依存するが、送信者にとってのプリイメージの証明特性(Proof-of-Payment)は維持される。

High AMP

High AMPは、OG AMPの各支払経路で異なるハッシュを使うことによる複数のHTLCの相関関係を隠す効果と、Base AMPのProof of Payment特性の両方を実現するために研究されているプロトコル

どうやって実現するかというと、既存のHTLCのハッシュのプリイメージの交換部分を、楕円曲線上の点と(その秘密鍵である)スカラーに置き換える。

受信者は、秘密鍵となるスカラー {k_{par}}をランダムに選択し、対応する公開鍵=楕円曲線上の点 {K_{par} = k_{par}G}を計算し、Invoiceに記載する。この {K_{par}}を親公開鍵、 {k_{par}}を親秘密鍵とする。

秘密鍵 {k_{par}}に対して、各iの子鍵は {k_i = H(i || k_{par}G) + k_{par}}として導出できる。そして親公開鍵 {K_{par} = k_{par}G}に対して、各iの子公開鍵は {K_i = H(i || K_{par})G + K_{par} = k_iG}として計算できる(子鍵は部分的な支払いの経路分作られる)。

送信者は支払いに使用する経路の数分、 {K_i}を導出し、導出した各 {K_i}について対応する子秘密鍵 {k_i}の開示を必要とする条件付き支払いのHTLCを構成する。この場合HTLCの非タイムロック部分はScriptless Scriptで構成される(受取人がT = t * Gを提供し、有効な署名を作るとtが明らかになるパターン)。

こうして送信者→受信者への複数の経路の支払いが作成される。受信者は部分的な支払いを受信しても、すぐにそれを受け取るインセンティブはまだない。なぜなら、部分的な支払いの内、1つでも {k_i}を明らかにしてしまうと、送信者が {k_{par} = k_i - H(i || K_{par})}を計算することで親秘密鍵を入手し、それをもってProof of Paymentとして機能してしまうからだ。

そのため受取人はすべての経路の支払いを受信してから、コインの請求を行う。それによりすべての子秘密鍵が明らかになり、それのいずれかを使って送信者は親秘密鍵 {k_{par}}を抽出できる。

送信者は親秘密鍵 {k_{par}}を使ってデジタル署名を作成することでProof of Paymentを証明でき、かつ各部分的な支払いには異なる {K_i}が使われるため、複数の経路感の相関関係を隠すことも可能になる。

ただHight AMPについてはBitcoinにSchnorr署名が実装される必要がある(まぁ最近の2P-ECDSAの研究から、ECDSAでも可能っぽいけど)。

というのが、OG AMP、Base AMP、High AMPの違い。BOLTのwikiを見る感じだとBOLT 1.1ではBaseとOGの両方が一応サポートされるっぽい。

TumbleBitに代わる新しいPayment Channel Hubプロトコル「Anonymous Atomic Locks」

Scaling Bitcoin 2019復習シリーズ第二弾は、Payment Channelの最近の研究といえばこの人、Pedro Moreno-Sanchezの「A2L: Anonymous Atomic Locks for Scalability and Interoperability in Payment Channel Hubs」

BitcoinのScalingソリューションとしてはペイメントチャネル技術にHTLCベースのマルチホップ決済を組み合わせたLightning Networkが有名だが、ベースとなるペイメントチャネル技術はLN固有の技術ではない。LNに可変サイズのマルチホップ決済はサポートしないが、誰かがハブ(タンブラー)となることでユーザー間のオフチェーン決済をサポートするPayment Channel Hubというコンセプトもある。Lightning Networkに比べてネットワーク情報を維持するコストは無いが、反面Hubという集中化モデルになる。

また、Lightning Networkはオニオンルーティングにより支払い経路の中継者は前後のノード情報しか分からないため、実際の支払い経路がA→B→Cという経路であったとしてもBからはAが実際の送信元で、Cが実際の受信者であるか知ることはない。反面Hub型のモデルはハブとなるBがAとCがそれぞれ送信元、受信者であることが分かるので、これを秘匿するための別の仕組みが必要になる。Payment Channel Hub(PCH)には以下の特性が求められる。

  • アトミック性
    A→B→Cの決済において、A→Bの支払いが行われた場合からなずB→Cの支払いも行われることが保証されること。
  • リンク不可能性
    A→B→Cの決済において、Aの送金先がCであることをBがリンクできないことが保証されること。
  • 値のプライバシー
    送金額のプライバシーが保証されること。
  • Fungibility
    各コインはそれぞれ区別されるべきではなく、PCHのタンブラーを使用したことが(スクリプトなどから)分からないことが保証されること。
  • インターオペラビリティ
    タンブラーを介して異なる暗号通貨で送金ができること。A→BはBTC、B→CはEtherのような。

PCHの提案としては、これらの要素を全て満たすような技術は現状存在しない。1番有力なPCHの実装はTumbleBitだが、コインがHTLCをサポートするコインに限定されるという意味でインターオペラビリティが限定的で、TunbleBitを利用したことがトランザクションからわかることからFungibilityにも課題が残る(Fungibilityに関してはTaprootの技術なんかと組み合わせると影響は限定できると思う)。

今回の提案では、上記の特性をできるだけカバーする新しいPCHのプロトコルAnonymous Atomic Locks(A2L)が提案されている。

Anonymous Atomic Locks(A2L)

A2LプロトコルはTumbleBitに結構似ていて、Promise(ロック)フェーズとPayment(リリース)フェーズの2つのフェーズで構成される。

Adaptor Signatureの利用

A2LではHTLCに依存しないよう、暗号チャレンジの入手とコインの引き換えはAdaptor Signature*1を使いスクリプトレスに実現するようになっている。Adaptor Signatureを利用したA→タンブラー→Bの基本的な支払いは流れは:

  1. タンブラーがまずシークレットskを生成する。
  2. アリスとタンブラー、タンブラーとボブの間でskの値が分かれば完全な署名が完成する=skを除外しないと正しい署名にならないHalf-signatureを作成する2P-Adaptorロックを完成させる。この時、2つのAdaptor Signatureには同じskの情報が使われ、これによりアトミック性が保証される。
  3. アリスとタンブラーの支払いが行われれば、その署名値からskを計算し、タンブラーからボブの署名を完成させることができる。

2つのAdaptor Signatureを利用することで、支払いのアトミック性が得られるが、課題になるのはタンブラーによるリンク不可能性だ。このリンク不可能性を保証するため、アリスとボブはそれぞれ秘匿されているskのデータをランダム値を使ってマスキングする。

プロトコルの概要

具体的にどのようにランダム性を利用しているのかプロトコルについて見てみよう。A2LプロトコルはSchnorr署名を利用する構成と、ECDSA署名を利用する2つの構成が提案されている。

Schnorr署名を利用した構成

署名データに線形特性のあるSchnorr署名の方が構成としてはシンプルになる。A→タンブラー→Bの支払いを行うステップは以下のようになる(アリスとタンブラー、ボブとタンブラーは既にそれぞれPayment Channelを開いていると仮定する)。

Promiseフェーズ

まず最初に暗号チャレンジの解(↓の手順でタンブラーが生成するランダム値α)と交換にタンブラーはボブにコインを支払う(αが分かればボブはこの送金Txの署名を完成させられる)Promiseフェーズを実行する。

  1. アリスとタンブラー、タンブラーとボブの間で共有公開鍵をそれぞれセットアップする。ボブとタンブラー間についてはボブの秘密鍵 {sk_b}、タンブラーの秘密鍵 {sk_{t1}}とすると共有公開鍵は {pk_{bt} = (sk_b + sk_{t1})G}。タンブラーとアリス間についてはタンブラーの秘密鍵 {sk_{t2}}とし、アリスの秘密鍵 {sk_a}、共有公開鍵は {pk_{at} = (sk_a + sk_{t2})G}。(このセットアップには分散鍵生成プロトコルを使用する)
  2. 続いてタンブラーは、ボブとのペイメントチャネルを新しい状態に更新する(ボブに資金を送金する)ため、新しいコミットメントトランザクションを作成し、内容についてボブと同意する。トランザクションに同意するだけで、この時点では未署名。
  3. タンブラーはランダムな値αを選択し、Paillier暗号で暗号化する(暗号化に使用するのはタンブラーのPaillier暗号用の公開鍵)cα =  {Enc(pk_T, α)}。このcαとA = αGをボブに送信する。※ 正確にはAが秘密の値αを使って生成されたことであるゼロ知識証明も一緒に送信され、ボブにより検証される。
  4. 続いてタンブラーとボブはコイントスプロトコルを実行して、 {R' = k'_1G + k'_2G + A}に同意する。R'はタンブラーが持つ秘密の値 {(α, k'_2)}とボブが持つ {k'_1}の値を使って構成されるが、それぞれ相手の秘密の値は知らない。
  5. 続いてタンブラーは、2で作成したコミットメントTxのタンブラー側の署名をR'を使って計算する。コミットメントTxから生成するSchnorr署名にしようするハッシュ値をe'とする。ただし、この時αを含めない。そのため計算した値は {k'_2 + e' \cdot x_2}となる。これをボブに送る。
  6. ボブは送られた値に対して、自身の持つ値を使って {s' = k'_1 + k'_2 + e \cdot (sk_{t1} + sk_b)}を計算する。署名値は(R', s')となるがこれはまだ不完全で、完全に有効な署名にするためには(R', s' + α)を算出する必要があるが、この段階ではボブはαを知らないので署名を完成させることはできない。
  7. 続いてボブは、ランダムな値βを選択する。3でタンブラーから受け取った暗号化されたcαおよびタンブラーの公開鍵 {pk_T}を使い、 {c'α = cα \cdot Enc(pk_T, β) = Enc(pk_T, α + β)} *2 および {A' = A + βG = (α + β)G}を計算しランダム化する。
  8. 最後にランダム化した値をアリスの送信する。

以上がPromise(ロック)フェーズで、図にまとめると↓な感じ。

f:id:techmedia-think:20191007170526j:plain
A2L-Promiseフェーズ

Paymentフェーズ

続いて、アリスとタンブラー間で、ボブから受け取ったランダム化された値を使ってアリスがタンブラーから秘密の値αの解をボブにしか分からない形で購入する。

  1. アリスはまずランダムな値τを選択し、ボブから受け取ったランダム化された値を再度ランダム化し、 {c''α = c'α \cdot Enc(pk_t, τ) = Enc(pk_t, α + β + τ)}およびA'' = A' + τG = (α + β + τ)Gを得る。
  2. アリスとタンブラーはPromiseプロトコルで行われたようにコイントスプロトコルを実行し、 {R'' = k'_3G(= R_a) + k'_4G(= R_{ta}) + A''}に同意する。R''はタンブラーが持つ秘密の値 {(α, k'_4)}とアリスが持つ {k'_3}の値を使って構成されるが、それぞれ相手の秘密の値は知らない。
  3. アリスはランダム化したc''αをタンブラーに送信する。
  4. タンブラーは自身がもつPaillier暗号の秘密鍵でc''aを解凍し、γ = (α + β + τ)を入手する。
  5. アリスはタンブラーとのチャネルを使ってタンブラーに送金する新しいCommitment Tx Aを作成し、内容についてタンブラーと同意する。
  6. タンブラーはCommitment Tx Aについてタンブラー側の署名 {k_4 + e'' \cdot sk_{t2}}を計算し、アリスに送る(e''はコミットメントTxから生成するSchnorr署名にしようするハッシュ値)。
  7. アリスはタンブラーから貰った署名値にGを乗算して、 {R_{ta} + e'' \cdot P_{t2}}と一致するか検証する。
  8. アリスはCommitment Tx Aのアリス側の署名を計算し、タンブラーから受け取った署名と合算した {s'' = k_3 + k_4 + e'' \cdot (sk_a + sk_{t2})}を計算しタンブラーに送信する。
  9. タンブラーはアリスから受け取ったs''とγを使って有効な署名データ {s = s'' + γ = k_3 + k_4 + e'' \cdot (sk_a + sk_{t2}) + γ}を完成させ、アリスに公開する。
  10. アリスはタンブラーが公開したsからs''を引いてγを入手する {s - s'' = γ = α + β + τ}
  11. アリスはγから自身が付与したランダム値τを差し引いたα' = γ - τ = α + βを計算しボブに送信する。
  12. ボブはアリスから受信したα'から自身が付与したランダム値βを差し引き、αを入手する。
  13. ボブはαが分かったので、Promiseフェーズで作成したCommitment Tx Bの有効な署名 {s = k_1 + k_2 + e' \cdot (sk_{t1} + sk_b) + α}を完成させ、タンブラーから資金を得る。

以上がPayment(リリース)フェーズで、図にまとめると↓な感じ。

f:id:techmedia-think:20191007180117j:plain
A2L-Paymentフェーズ

ECDSA署名を利用した構成

結構なボリュームになったので、詳細なプロトコルに関してはホワイトペーパー参照。

基本的なプロトコルの流れはSchnorrの構成と同じで、ただECDSA署名にはSchnorrのような署名データの線形特性が無いので、鍵生成の方式が変わっており、Lindellのプロトコル秘密鍵もPallier暗号で渡す仕組みになっている。

所感

A2Lプロトコルは、

  • 暗号チャレンジに解凍と引き換えにコインを渡すという仕組みでアトミック性を担保し
  • 暗号チャレンジをする際に、送信者と受信者で解答に対するランダム化を行うことでタンブラーに送金元と送金先のリンク不可能性を担保し
  • 暗号チャレンジの解答をAdaptor Signatureの要素として組み込みスクリプトレスにすることで、相互運用性およびFungibilityを担保する

Payment Channel Hubの提案だ。ただ値のプライバシーについては十分ではない。

基本的な構造はTumbleBitと同じだが、Adaptor Signature使ってスクリプトレスにしてる部分が追加の特性になっている。ただ、リンク不可能性やFungibilityに関しては、TumbleBitと同様利用者が少なければリンクできたり、異なる金種を用いるとリンクできたりする可能性はそのまま残るように思える。

*1:参考動画:https://goblockchain.network/2018/12/adaptor_signature/

*2:Paillier暗号の準同型特性により暗号化したままデータの計算が可能になる。