Bitcoinのトランザクションは10分に一度作成されるブロックに取り込まれる。最近のメモリプールの状況では10分後に取り込まれればラッキーな方で、まだ時間がかかることもよくあると思う。
その一方でECサイトや実店舗でのBitcoin決済の導入は進んでいる。リアルな店舗で決済する際に10分以上待たされてはBitcoinを使って決済しようとは思えないから、こういった店舗では、決済するトランザクションがブロードキャストされれば決済されたと判断しトランザクションがブロックに取り込まれるまで待たずに決済をしている。つまに未承認のトランザクションで決済している。
この場合、もし二重使用が発生すると店舗側は決済した金額を受け取れない事態が発生する。まぁその辺のリスクを考慮してBitcoin決済ができるのはある一定額までで、そういう事態が発生した場合は決済会社が保証などしているのだと思う。
そんな未承認トランザクションの二重使用を防ぐ仕組みについてバルセロナ自治大学のホワイトペーパーが公開されていたので見てみた↓
http://eprint.iacr.org/2017/394.pdf
二重使用を防ぐ基本的な仕組み
二重使用はその資金を二重使用できないようなトランザクションに送る初期化フェーズと、そのトランザクションを使って決済を行うファストペイメントフェーズの２つのフェーズからなる。
初期化フェーズ
アリスはまず自分のUTXOをFR-P2PKの出力に送るfunding transactionを作成する。このトランザクションを作るためアリスは、ランダムな整数値kと公開鍵PKa（対応する秘密鍵はSKa）を選択し（＝決済に使用するキーペアの生成）、FR-P2PKの出力（具体的なスクリプトは後述）をセットし、そこにいくらかの資金を送金するトランザクションを構成する。アリスはfunding transactionをブロードキャストし、トランザクションがブロックに格納されたら初期化フェーズが完了する。
FR-P2PKというのはfixed-r pay-to-pubkey scriptの略で、Pay-to-Pubkeyを少し変形させたスクリプトになる。Pay-to−Pubkeyの場合、そのスクリプトを使用するには署名をscript_sigにセットすればいいけど、FR-P2PKはその署名が特定の値rを使って生成される必要がある。FR-P2PKではECDSAの脆弱性を逆に利用して二重使用から保護する。
つまり、FR-P2PKを使用するトランザクションを作り、更に同じFR-P2PKを二重使用するトランザクションがブロードキャストされた場合、ネットワーク上には
- 同じ秘密鍵
- 同じ乱数
- ２つ異なる署名対象のメッセージ
から生成された署名が２つ存在することになり、ネットワークに参加しているノードであれば誰でもそこから秘密鍵を計算することができる。そのため二重使用しようとしたユーザーは、ネットワーク上のノードに計算した秘密鍵からFR-P2PKの資金を奪われるというリスクを考慮するから、二重使用するインセンティブが働かなくなるという仕組み。
この脆弱性から秘密鍵を導出するのは簡単でRubyでecdsa gemを使って書くと↓のように書ける。
※ 署名値のSが-S mod Nの場合もあるので、ちゃんと計算する場合はそこも考慮する必要はある。
Fast paymentフェーズ
実際に決済する際は、アリスは初期化フェーズで作成したfunding transactionのFR-P2PK出力を使ってボブにBitcoinを送るfast-payment transactionを作成する。このトランザクションのscript_sigが有効であるということは、アリスが公開鍵PKaに対応する有効な秘密鍵SKaと初期化フェーズで生成したkの値を持っていることの証明になる。アリスは作成したfast-payment transactionをBitcoinネットワークにブロードキャストする。
ボブはメモリプール内にある受信したfast-payment transactionを確認すると、このトランザクションで使用されるUTXOがFR-P2PK出力であることを検証することができる。FR-P2PK出力であることが確認できれば、ボブはアリスが二重使用しようとすると彼女が自分の資金を失う可能性があることを認識する。
アリスがfunding transactionの資金を二重使用する場合、FR-P2PK出力を二重使用するトランザクションを新たに作成する必要がある。このトランザクションの署名はもちろん有効な署名でないといけないので、SKaと初期化フェーズで選択されたkを使った２つ目の署名を作ることになる。つまり二重使用のトランザクションを作るということは、同じ秘密鍵SKaと同じrをを使った異なる署名を作ることになる。署名されるメッセージ（トランザクションダイジェスト）も異なるので、この場合ECDSAの、同一の秘密鍵によって同じ値kで行われる２つの署名があれば、署名に使用された秘密鍵を導出するのに充分なヒントになるという脆弱性に該当する。
そのためアリスは二重使用トランザクションをブロードキャストすると、自分の資金を失う危険性がある。これはfunding transactionとfast-payment transactionの両方を受信するオブザーバーがアリスの秘密鍵SKaを導出できるため、結果 FR-P2PKの出力をオブザーバーに送金する第３のトランザクション（ペナルティトランザクション）を作成することができる。
抑止的な保護の仕組み
↑の仕組みには明らかな欠陥がある。アリスがボブの店で↑のファストペイメントを行い商品を購入するとする。ボブはトランザクションを受信すると商品をアリスに発送する。アリスは商品を受取ると二重使用を試みるかもしれない。オブザーバーがfast-payment transactionと二重使用トランザクションの両方を監視しているケースでは、ペナルティトランザクションを作成し、それが先にブロックチェーンに格納されるように調整する（手数料などで）。この場合ペナルティトランザクションがブロックに入れられるとアリスは資金を失うが、ボブも支払いを受け取れない。このようなケースであればボブは、商品を発送したが、それと交換にBitcoinを受け取ることができない。結果的にアリスはBitcoinをボブではなく第三者のオブザーバーに支払ったことになり、オブザーバーがトランザクションの総量を手に入れる。結果的にアリスが二重使用をするインセンティブは働かないので、この提案した方法は二重使用を防ぐかもしれない。
しかし、方法を少し変えるだけでアリスに二重使用を思いとどまらせる方法がある。それはfunditoin transactionのFR-P2PK出力に支払いに使う金額より一定の係数λだけ高い金額をセットすることを強制する方法だ。この場合、アリスが二重使用を試みると、支払金額より多いFR-P2PK出力分のコインをオブザーバーに全て持って行かれる可能性があり、商品をボブから入手したとしても、係数λの分だけアリスが損をすることになる。そのため自分が損する可能性があるのにアリスは二重使用を試みるはずはない。
FR-P2PKスクリプトの構成
Bitcoinのトランザクションの署名データは、以下のDERエンコーディング仕様で構成されている。
0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash]
techmedia-think.hatenablog.com
この署名データのフォーマットを考慮した上で、FR-P2PKの出力は以下のように定義される。
ScriptPubKey: OP_DUP <pubKey> OP_CHECKSIGVERIFY OP_SIZE <0x47> OP_EQUALVERIFY <sigmask> OP_AND <r> OP_EQUAL ScriptSig: <sig>
<pubKey>: 署名の検証に使われる公開鍵<sigmask>: 71バイトのバイト列で、DERエンコーディングされた署名データ(sig)のrの位置と最後のSIGHASH_TYPEの位置に1がセットされ、その他の部分には0がセットされたビットマスクになる。<r>: 71バイトのバイト列で、整数rのDER形式の値と、SIGHASH_TYPEには0x01が、それ以外の箇所は全て0がセットされている。
このスクリプトを実行すると、まず署名が<pubKey>に対応した有効な署名か検証が行われ、続いて署名のサイズを検証する。その後<sig>と<sigmask>のビット単位のANDを計算し、その結果が<r>と同じかチェックされる。このようにして署名データに固定値のrを強制している。
ただ、このOP_ANDというopcodeはBitcoinの標準仕様では無効化されているものなので、このスクリプトを現在使用することはできない。
所感
- ECDSAの脆弱性を利用するという逆転の発想感は面白い。
- オブザーバーの存在や、現実的に全てのノードがオブザーバーになるわけでもないのと、二重使用のトランザクションがブロードキャストされそれをオブザーバーが検知してからの対応になるという仕組みを考えると、完璧に二重使用を防げるものではないので、そういうリスクを取らせることで二重使用するインセンティブを排除していくのだろう。
- 初期化フェーズでfunding transactionをブロードキャストする必要があるので、最終的に決済するのに２つのトランザクションのブロードキャストが必要になる。この部分の手数料や手間とか考慮すると残念ながらあまりカジュアルに使える方法ではないと思う。
- 実現する場合は、現在無効化されている
OP_ANDが再び使えるようになる必要がある。
