Develop with pleasure!

福岡でCloudとかBlockchainとか。

決定性辞書式順序ソートによるトランザクションの入出力のソート(BIP-69)

Lightning Networkの仕様の中でトランザクションの入出力のソートについてBIP-69が参照されていたので、どんな仕様なのか見てみる。

bips/bip-0069.mediawiki at master · bitcoin/bips · GitHub

要約

現在、トランザクションの入力と出力の順序について、Bitcoinのウォレットクライアントにおいて標準仕様はない。その結果、ウォレットクライアントはよく識別可能なブロックチェーンのフィンガープリントを保持し、それによりユーザの個人情報が漏れるリスクがある。対象的に非決定性ソートの基準では監査が困難になる場合がある。このドキュメントでは、UTXOのハッシュとインデックスを使ってトランザクションの入力をソートし、値とscriptPubkeyを使って出力をソートする決定性辞書式順序ソートを提案する。

動機

現在、ウォレットクライアントがトランザクションの入力と出力をどういう順で作るかについての明確な標準はない。ウォレットクライアントはこの順序を決めるのを自身のデバイスに委ねているため、ユーザの財務情報が漏洩することがよくある。例えばウォレットクライアントは、ユーザーがアドレスをインポートするかランダムな生成器を使用して新しいアドレスを生成するかしてアドレスをウォレットに追加したタイミングで、入力の順序付けを行うことがある。多くのウォレットではBitcoinを送る際の出力を最初の出力に配置し、おつりの出力を2番めに配置するため、送信者と受信者双方の財務情報をブロックチェーンのオブザーバーにリークすることになる。こういった情報は、消費者の利益のためだけでなく、より高水準な金融システムにおいても詐欺を防ぐために秘密にしておく必要がある。研究者は最近、Bitstampが交換トランザクションを作成する際に情報漏洩したことを発見した際にこれを実証した。

これらのプライバシーの弱点に対処する1つの方法は、入力と出力の順序をランダムにすることである。入力の出力の順序をどうするかについてはトランザクションの機能に影響がないので、ランダムソートをするのに問題はない。ただ残念ながらランダムソートは、特にクローズドソースの場合、本当にランダムにソートされているのか証明することは難しい。悪意ある開発者はサイドチャネルで入力と出力の順序を悪用する可能性がある。例えば攻撃者が被害者のHDウォレットにパッチを適用して、マスター秘密鍵のビットに基づき入力と出力の順序付けを行える場合、攻撃者はブロックチェーンを監視することで被害者の資金を全て盗むことができる。非決定性のソートは監査が困難である。

入力と出力の順序付けをする際にウォレットクライアント間で標準化が行われていないと、その特徴から特定のウォレットやサービスを特定できる可能性がある。このような特徴は、プライバシーの侵害者がブロックチェーンを観測することで利用できるフィンガープリントを作ることになる。

解決策は、入力と出力をソートする決定性のアルゴリズムを作成することである。決定性であるためあるトランザクションが与えられた際、その入力と出力の順序は明白でなくてはならない。この標準を可能な限り広く適用できるようにするためには、フルノードとSPVノード両方によってダウンロードされる情報に依存する必要がある。

仕様

適用範囲

このBIPはトランザクションの入力と出力の順序がトランザクションの機能に影響を与えないトランザクションに適用される=署名に使用するSIGHASHSIGHASH_ALLトランザクションが対象。SIGHASH_ALLの場合、その入力と出力はこのBIPの正確な順序にコミットすることになる。SIGHASH_ANYONECANPAYおよびSIGHASH_NONEを使用するトランザクションには、署名されていない入力や出力が含まれる場合があるが、本BIPに準拠するソフトウェアは(後で他のユーザによって変更される可能性はあるが)辞書式順序ソートでソートした入力と出力を持つトランザクションを構築する必要がある。

将来のプロトコルのアップデートにより新しいSIGHASHタイプが導入される場合、本BIPに準拠するソフトウェアは辞書式順序の原則を同様に適用する必要がある。

このBIPの範囲外ではあるが、(例えばSIGHASH_SINGLEのように)特定の入出力の順序を必要とするプロトコルにおいては、このBIPの目標とそのプロトコルの特定のニーズを満たすために最適な方法を考慮する必要がある。

辞書式順序ソート

辞書式順序ソートは共通の上位集合内の直積集合に基いて2つの集合をソートするために使用される比較のためのアルゴリズムである。辞書式順序はアルファベット順または辞書順としてもよく知られている。

一般的な実装には以下のようなものがある。

  • C++ではstd::lexicographical_compare
  • Python 2.7では cmp
  • Cではmemcmp
  • Node.jsではBuffer.compare

詳細についてはWikipedia参照

トランザクションの入力

トランザクションの入力は、前のトランザクションのハッシュと前のトランザクション出力のインデックス、アンロックスクリプトのサイズ、アンロックスクリプト、シーケンス番号によって定義される。入力をソートする際は、この内、前のトランザクションのハッシュと出力のインデックスを使用する。各トランザクションのハッシュはブロックチェーン内で一意である可能性が非常に高く、トランザクション内の出力のインデックスは一意である。トランザクションハッシュは異なるが出力インデックスは同じケースがよくあるため、(効率的に処理するため)最初にトランザクションハッシュを比較する。

前のトランザクションのハッシュ(バイトオーダーの逆順)は、辞書の昇順にソートする。トランザクションハッシュが同じ値の場合は、次に出力のインデックスの数値の昇順で比較する。出力のインデックスまで同じ場合は、入力は等しいとみなされる。

トランザクションのmalleabilityの問題についてはこのプロセスに影響しない。ウォレットクライアントが未承認のUTXOを入力にセットしこのプロセスに基いてソートし、その後攻撃者が前のトランザクションハッシュを変更しても、ウォレットクライアントは無効化されたUTXOのトランザクションハッシュを含めたままで、その無効化されたハッシュも本仕様として正しくソートされるだけである。

トランザクションの出力

トランザクションの出力は、scriptPubkeyamountによって定義される。標準的なP2PKHのscriptPubkey(25バイト)と比較してamountの方がバイト情報が少ない(8バイト)ため、最初にamountを比較する。

トランザクション出力のamount(64ビットの符号なし整数)は昇順でソートする。amountの値が一致する場合は、その後それぞれのscriptPubkeyを辞書の昇順にソートする。scriptPubkeyまで同じ場合は、出力は等しいとみなされる。

トランザクション0a6a357e2f7796444e02638749d9611c008b253fb55f5dc88b739b230ed0c4c3の場合

入力は以下の順になる

0: 0e53ec5dfb2cb8a71fec32dc9a634a35b7e24799295ddd5278217822e0b31f57[0]
1: 26aa6e6d8b9e49bb0630aac301db6757c02e3619feb4ee0eea81eb1672947024[1]
2: 28e0fdd185542f2c6ea19030b0796051e7772b6026dd5ddccd7a2f93b73e6fc2[0]
3: 381de9b9ae1a94d9c17f6a08ef9d341a5ce29e2e60c36a52d333ff6203e58d5d[1]
4: 3b8b2f8efceb60ba78ca8bba206a137f14cb5ea4035e761ee204302d46b98de2[0]
5: 402b2c02411720bf409eff60d05adad684f135838962823f3614cc657dd7bc0a[1]
6: 54ffff182965ed0957dba1239c27164ace5a73c9b62a660c74b7b7f15ff61e7a[1]
7: 643e5f4e66373a57251fb173151e838ccd27d279aca882997e005016bb53d5aa[0]
8: 6c1d56f31b2de4bfc6aaea28396b333102b1f600da9c6d6149e96ca43f1102b1[1]
9: 7a1de137cbafb5c70405455c49c5104ca3057a1f1243e6563bb9245c9c88c191[0]
10: 7d037ceb2ee0dc03e82f17be7935d238b35d1deabf953a892a4507bfbeeb3ba4[1]
11: a5e899dddb28776ea9ddac0a502316d53a4a3fca607c72f66c470e0412e34086[0]
12: b4112b8f900a7ca0c8b0e7c4dfad35c6be5f6be46b3458974988e1cdb2fa61b8[0]
13: bafd65e3c7f3f9fdfdc1ddb026131b278c3be1af90a4a6ffa78c4658f9ec0c85[0]
14: de0411a1e97484a2804ff1dbde260ac19de841bebad1880c782941aca883b4e9[1]
15: f0a130a84912d03c1d284974f563c5949ac13f8342b8112edff52971599e6a45[0]
16: f320832a9d2e2452af63154bc687493484a0e7745ebd3aaf9ca19eb80834ad60[0]

出力は以下の順になる

0:    400057456    76a9144a5fba237213a062f6f57978f796390bdcf8d01588ac
1:    40000000000    76a9145be32612930b8323add2212a4ec03c1562084f8488ac

トランザクション28204cad1d7fc1d199e8ef4fa22f182de6258a3eaafe1bbe56ebdcacd3069a5fの場合

入力は以下の順になる

0: 35288d269cee1941eaebb2ea85e32b42cdb2b04284a56d8b14dcc3f5c65d6055[0]
1: 35288d269cee1941eaebb2ea85e32b42cdb2b04284a56d8b14dcc3f5c65d6055[1]

出力は以下の順になる

0:    100000000    41046a0765b5865641ce08dd39690aade26dfbf5511430ca428a3089261361cef170e3929a68aee3d8d4848b0c5111b0a37b82b86ad559fd2a745b44d8e8d9dfdc0cac
1:    2400000000    41044a656f065871a353f216ca26cef8dde2f03e8c16202d2e8ad769f02032cb86a5eb5e56842e92e19141d60a01928f8dd2c875a390f67c1f6c94cfc617c0ea45afac

ディスカッション

実装

まとめ

  • トランザクションを構築する際、入力と出力をどういう順序で構成するかという標準の仕様は現在存在しない。
  • 出力の最初が送金の出力で2つめの出力がおつりというケースがよくあり、こういったところから送信者と受信者の財務情報が分かる可能性がある。
  • そのため入力と出力の順序付けから情報が得られないようにする必要がある。
  • 入力と出力の順序付けをランダム化すれば良いが、クローズドソースなウォレットでは、それが本当にランダムに順序付けされた結果なのか判断するのは不可能である。
  • そのため入力はUTXOのハッシュとインデックス、出力は値とscriptPubkeyで辞書順にソートする。
  • ただし、SIGHASH_SINGLEのように入力と出力のインデックスがトランザクションの機能に影響を与えるケースではこのBIPのルールは適用されない。
  • 入力はtxid、出力のインデックスの順番でソートする。
  • 出力はamountscriptPubkeyの順番でソートする。
  • この仕様自体は標準を決めるものなので、ソフトフォークなどのデプロイが発生するものではなさげ。