Develop with pleasure!

福岡でCloudとかBlockchainとか。

Lightning Networkで古いCommitment Txを取り消すRevocation Key

以前、Lightning Networkを構築する際のPayment Channelの仕組みについて書いた↓

techmedia-think.hatenablog.com

プリイメージを使ったコミットメントトランザクションの取消

このPayment Chanelを使ったオフチェーンの決済には、悪意あるユーザによって最新の残高ではなく自分の残高が多い古いコミットメントトランザクションをブロードキャストする不正が行われた際に、チャネルにデポジットされている全資金を取り戻す仕組みが存在する。

この仕組みはHTLCsで使われている仕組みと似ていて、新しいコミットメントトランザクションに両者が合意した際、古いコミットメントトランザクションに含まれているハッシュの元となったプリイメージを交換する。そのプリイメージがあれば、相手によって古いコミットメントトランザクションがブロードキャストされても、自分の署名とそのプリイメージで全資金を自分のものにできるというもの。

具体的には、アリスとボブがいてアリスは以下のようなコミットメントトランザクション作成してボブに送る(事前にボブからボブが生成したrevokehashを受け取っておく)。

# 入力
アリスとボブのマルチシグにデポジットされたコイン

# 出力1(アリスの残高をアリスに送る出力)
OP_DUP OP_HASH160 <アリスの公開鍵のハッシュ> OP_EQUALVERIFY OP_CHECKSIG

# 出力2(ボブの残高で、24時間経てばボブの公開鍵でコインが入手可能、もしくはrevokehashのプリイメージが分かればアリスの公開鍵でコインが入手可能)
OP_HASH160 <ボブが生成したrevokehash> OP_EQUAL
OP_IF
    <アリスの公開鍵>
OP_ELSE
    "24h" OP_CSV OP_DROP
    <ボブの公開鍵>
OP_ENDIF
OP_CHECKSIG

新しいコミットメントトランザクションを作成したら、アリスとボブがお互いに古くなったコミットメントトランザクションに使ったrevokehashのプリイメージを相手に公開する。もしボブが裏切って↑の古いコミットメントトランザクションに署名してブロードキャストしてもアリスはボブが明かしたプリイメージを使って、出力1と出力2のコイン全てを入手することができる。

プリイメージを使わずRevocation Keyを利用

ただ、最近のLNの実装ではこのプリイメージを使った仕組みは使われておらず、代わりにRevocation Keyが使われている。

↑の出力2のスクリプトが↓のスクリプトになる。

OP_IF
    <revocation-pubkey>
OP_ELSE
    "24h" OP_CSV OP_DROP
    <ボブの公開鍵>
OP_ENDIF
OP_CHECKSIG

見ての通り、ハッシュとそのプリイメージを使う形から、ある公開鍵<revocation-pubkey>による署名があればコインを取り戻せるようになっている。

この<revocation-pubkey>を導出する方法だが、まずLNのチャネルをオープンする際にそれぞれ自分のベースポイントを相手に伝える。ここでいうベースポイントは楕円曲線上のポイントなので言ってしまえば公開鍵。ただこのポイント自体はチャネルのセットアップに使うだけで決済に使う公開鍵ではない。

このベースポイントを使って<revocation-pubkey>を導出する。
コミットメントトランザクションを新しく生成する際、ボブがプリイメージを新しく生成しそのハッシュをアリスに伝える代わりに、ボブは新しく生成したハッシュに楕円曲線のGを乗算し新しいポイントを作成しそのポイントをアリスに伝える。アリスはそのポイントをアリスのベースポイントに加算し<revocation-pubkey>を生成する。ちなみに(正確には元のハッシュが異なるが)アリスがボブから受け取ったポイントをボブのベースポイントに加算したのがタイムロックされたブランチのボブの公開鍵になる。
新しいコミットメントトランザクションを作成する際は、このコミットメントトランザクションの<revocation-pubkey>を作るのに使ったポイントの元のハッシュを交換する。(Payment Channelは鏡像となるトランザクションをお互いに作るのでアリスはその逆を行う)

※ LNの仕様は現在標準化されていないので、この <revocation-pubkey>の計算方法はLNの実装によって異なる。lndとかはもう少し算出方法が複雑。

プリイメージを使うパターンでなくRevocation Keyを使うメリットとしては、redeem scriptのデータ量ががOP_HASH160 <revokehash> OP_EQUALの分だけ少なくてすむ。

P2WSHを使うトランザクションの作成と署名

P2WPKHの署名方法について書いた↓ので

techmedia-think.hatenablog.com

今回はP2WSHの署名について。

単純なマルチシグでもつまならいのでOP_CSVのBIPに出てくるLNのトランザクションサンプルのP2WSHにしてみる↓

https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki#Lightning_Network

※ LNのホワイトペーパーでは古いコミットメントトランザクションの取消に↑のようなシークレットのプリイメージを使う方法が書かれてるけど、現在の実装ではプリイメージのハッシュにロックする方法は使われておらず、チャネル設立時のベースポイントに対してシークレットを加算して生成した鍵でロックする形に変わっている。

P2WSHにBitcoinを送付する

今回は↑の例に出てくる以下のスクリプトBitcoinを送る。

HASH160 <revokehash> EQUAL
IF
    <Bob's pubkey>
ELSE
    "24h" CHECKSEQUENCEVERIFY DROP
    <Alice's pubkey>
ENDIF
CHECKSIG

このスクリプトは、revokehashの元のプリイメージを知っていればボブの秘密鍵による署名でコインが入手でき、それ以外のケースではこのUTXOがブロックに入れられて24時間経過したらアリスの秘密鍵による署名でコインが入手できるというものになる。

このスクリプトをベースにしたP2WSHのscriptPubkeyを作る。P2WSHのwitness programは以下の形式になる。

0 <↑のスクリプトの32バイトハッシュ>

実際にbitcoin-rubyで↑のP2WSHに支払う処理は以下のように書ける。

require 'bitcoin'

Bitcoin.network = :testnet3

alice_key = Bitcoin::Key.from_base58('アリスの秘密鍵')
bob_key = Bitcoin::Key.from_base58('ボブの秘密鍵')

# シークレットの値
preimage = "apple"

# シークレットのハッシュ値
hash = Bitcoin.hash160(preimage)

# 24時間 = 10分ブロック計算で 24 * 6 ブロック
block_count = 24 * 6

# ロックスクリプト
redeem_script = Bitcoin::Script.from_string("OP_HASH160 #{hash} OP_EQUAL OP_IF #{bob_key.pub} OP_ELSE #{block_count} OP_NOP3 OP_DROP #{alice_key.pub} OP_ENDIF OP_CHECKSIG")

# P2WSHのscriptPubkey
script_pubkey = Bitcoin::Script.from_string("0 #{Bitcoin.sha256(redeem_script.to_payload.bth)}")

# 適当なUTXOを入力にしてP2WSH宛に送る。
tx = Bitcoin::Protocol::Tx.new
tx.add_in(Bitcoin::Protocol::TxIn.from_hex_hash('07b09f22abd2d78c41b2984f05d3dd83a3c5905771f0ee290b04f933e0c13d59', 0))
# P2WSHの出力
tx.add_out(Bitcoin::Protocol::TxOut.new(100000, script_pubkey.to_payload))
# おつり
tx.add_out(Bitcoin::Protocol::TxOut.value_to_address(760000, 'mt1hZLajqyc63NkWy7qvgiuum5nuTBdVZ6'))

# (これは非segwitなTxなので)to_payloadしたデータをsignrawtransactionなどで署名してブロードキャストする
tx.to_payload.bth

実際にtestnetにブロードキャストしたデータ
(txid = 4e70cfb5ca582aeb88924fe74dbcb49503699f0f09adb2493c7439d051668af7)↓

{
  "hex": "0100000001593dc1e033f9040b29eef0715790c5a383ddd3054f98b2418cd7d2ab229fb007000000006a47304402202ecef6c319d65d408d953d9f4dc6c8882e638d6493751c6728448fc14c8d98920220684a2c222c7b5529e6f290ae08ebe07b893de69c3f92b68fc9a9b7f804e027c9012102effb2edfcf826d43027feae226143bdac058ad2e87b7cec26f97af2d357ddefaffffffff02a086010000000000220020ee6e25ff1fcf33396396cc82bb3702533fb1ad5289711262ed75e0dea34d84e4c0980b00000000001976a9148911455a265235b2d356a1324af000d4dae0326288ac00000000",
  "txid": "4e70cfb5ca582aeb88924fe74dbcb49503699f0f09adb2493c7439d051668af7",
  "hash": "4e70cfb5ca582aeb88924fe74dbcb49503699f0f09adb2493c7439d051668af7",
  "size": 234,
  "vsize": 234,
  "version": 1,
  "locktime": 0,
  "vin": [
    {
      "txid": "07b09f22abd2d78c41b2984f05d3dd83a3c5905771f0ee290b04f933e0c13d59",
      "vout": 0,
      "scriptSig": {
        "asm": "304402202ecef6c319d65d408d953d9f4dc6c8882e638d6493751c6728448fc14c8d98920220684a2c222c7b5529e6f290ae08ebe07b893de69c3f92b68fc9a9b7f804e027c9[ALL] 02effb2edfcf826d43027feae226143bdac058ad2e87b7cec26f97af2d357ddefa",
        "hex": "47304402202ecef6c319d65d408d953d9f4dc6c8882e638d6493751c6728448fc14c8d98920220684a2c222c7b5529e6f290ae08ebe07b893de69c3f92b68fc9a9b7f804e027c9012102effb2edfcf826d43027feae226143bdac058ad2e87b7cec26f97af2d357ddefa"
      },
      "sequence": 4294967295
    }
  ],
  "vout": [
    {
      "value": 0.00100000,
      "n": 0,
      "scriptPubKey": {
        "asm": "0 ee6e25ff1fcf33396396cc82bb3702533fb1ad5289711262ed75e0dea34d84e4",
        "hex": "0020ee6e25ff1fcf33396396cc82bb3702533fb1ad5289711262ed75e0dea34d84e4",
        "type": "witness_v0_scripthash"
      }
    }, 
    {
      "value": 0.00760000,
      "n": 1,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 8911455a265235b2d356a1324af000d4dae03262 OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a9148911455a265235b2d356a1324af000d4dae0326288ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "mt1hZLajqyc63NkWy7qvgiuum5nuTBdVZ6"
        ]
      }
    }
  ]
}

0番めの出力がP2WSHの出力で、typewitness_v0_scripthashになっており、アドレスも表示されていないことが分かる。

witnessなトランザクションの作成と署名

↑でP2WSH宛に送ったBitcoinを入力にしたトランザクションの作成と署名を行う。

↑のスクリプトはアンロック条件が2つあるが、今回はシークレットを知ったボブがボブの秘密鍵を使った署名でコインをアンロックするパターンで実装する。 この条件でアンロックする際のwitnessのスタックは

<ボブの秘密鍵を使った署名> <revokehashのプリイメージ> <witness script>

になる。

version 0のwitness programで0の後に32バイトのデータがプッシュされているスクリプトをP2WSHのwitness programと認識し、以下のようなプロセスが実行される。

  1. witnessスタックの先頭から最後から1つ前までのスタックのアイテムをピックアップしてスタックを生成する。
  2. witnessスタックの最後のアイテムをredeem scriptとしてピックアップする。
  3. 1のスタックに対して2のredeem scriptを実行してスクリプトを評価する。

※ なおwitnessスタックにセットされたwitness scriptから計算したハッシュが元のscriptPubkeyの32バイトのハッシュ値と異なる場合はエラー。

この辺の処理は↓あたりで実装されている。

https://github.com/bitcoin/bitcoin/blob/v0.13.2/src/script/interpreter.cpp#L1356-L1407

実際にbitcoin-rubyで実装してみる。

P2WSHの場合も署名は、BIP-143↓で定義された新しいSIGHASHの生成方法に従う。
P2WPKHと異なるのは、scriptCodeの生成方法くらいかな。

techmedia-think.hatenablog.com

alice_key = Bitcoin::Key.from_base58('アリスの秘密鍵')
bob_key = Bitcoin::Key.from_base58('ボブの秘密鍵')

# シークレットの値
preimage = "apple"

# シークレットのハッシュ値
hash = Bitcoin.hash160(preimage)

# 24時間 = 10分ブロック計算で 24 * 6 ブロック
block_count = 24 * 6
# ロックスクリプト
redeem_script = Bitcoin::Script.from_string("OP_HASH160 #{hash} OP_EQUAL OP_IF #{bob_key.pub} OP_ELSE #{block_count} OP_NOP3 OP_DROP #{alice_key.pub} OP_ENDIF OP_CHECKSIG")

prev_tx = Bitcoin::Protocol::Tx.new('↑でブロードキャストしたトランザクションデータ'.htb)

tx = Bitcoin::Protocol::Tx.new

tx.add_in(Bitcoin::Protocol::TxIn.from_hex_hash('4e70cfb5ca582aeb88924fe74dbcb49503699f0f09adb2493c7439d051668af7', 0))
tx.add_out(Bitcoin::Protocol::TxOut.value_to_address(90000, bob_key.addr))

# BIP-143の仕様でSIGHASHを生成
sig_hash = tx.signature_hash_for_witness_input(0, prev_tx.out[0].script, 100000, redeem_script.to_payload)

# ボブの秘密鍵で署名
sig = bob_key.sign(sig_hash)+ [Bitcoin::Script::SIGHASH_TYPE[:all]].pack("C")

tx.in[0].script_witness.stack << sig # ボブの署名
tx.in[0].script_witness.stack << preimage.htb # revokehashのプリイメージ
tx.in[0].script_witness.stack << redeem_script.to_payload # redeem scrpt(witness script)

# トランザクションのrawデータが出力されるので、これをsendrawtransactionする。
tx.to_witness_payload.bth

実際にtestnetにブロードキャストしたデータ
(txid = fc45cf999310987860cf7d287d1f0118322ac31212aef1b279c7a3f8b55c83e0)が↓

{
  "hex": "01000000000101f78a6651d039743c49b2ad090f9f690395b4bc4de74f9288eb2a58cab5cf704e0000000000ffffffff01905f0100000000001976a914f8ae1df3f73d7d2e197b467b509dfedbf1b4cdc288ac0347304402203fd393fb54584fbcd89e24aff756696edd8d1889307030a6e97c7fcc7dcb4cee02207e484fca226d4d752ee69c0a9e972f58ff0f7debd8c1209911403837847c5efb0103a995e064a9146a25f59f6c9ebe7415c640c915bd48c4b7138a62876321038c811a50fa3d7a68426fef93d92c6897d7f0a1c16c6fb17e9b183ef868d8d16f67021440b2752103f50e3fdd76870c21581af66af261ffed186b780c024f8f2fc9daeac58bf8356368ac00000000",
  "txid": "fc45cf999310987860cf7d287d1f0118322ac31212aef1b279c7a3f8b55c83e0",
  "hash": "6dcce7541bf1e89698d7f616e09b5510fe75464947cab5fb3388cf0be96aaf76",
  "size": 265,
  "vsize": 130,
  "version": 1,
  "locktime": 0,
  "vin": [
    {
      "txid": "4e70cfb5ca582aeb88924fe74dbcb49503699f0f09adb2493c7439d051668af7",
      "vout": 0,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "txinwitness": [
        "304402203fd393fb54584fbcd89e24aff756696edd8d1889307030a6e97c7fcc7dcb4cee02207e484fca226d4d752ee69c0a9e972f58ff0f7debd8c1209911403837847c5efb01", 
        "a995e0", 
        "a9146a25f59f6c9ebe7415c640c915bd48c4b7138a62876321038c811a50fa3d7a68426fef93d92c6897d7f0a1c16c6fb17e9b183ef868d8d16f67021440b2752103f50e3fdd76870c21581af66af261ffed186b780c024f8f2fc9daeac58bf8356368ac"
      ],
      "sequence": 4294967295
    }
  ],
  "vout": [
    {
      "value": 0.00090000,
      "n": 0,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 f8ae1df3f73d7d2e197b467b509dfedbf1b4cdc2 OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a914f8ae1df3f73d7d2e197b467b509dfedbf1b4cdc288ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "n4BrTVLsr1PUfqAneRpVqZt3kAYJRQY6Zf"
        ]
      }
    }
  ]
}

と正常にブロードキャストできた。

前回のP2WPKHとP2WSHのトランザクションが作れればLNのペイメントチャネルを実装をする上で必要なものは揃う。

P2SHでネストしたP2WPKHや、P2SHでネストしたP2WSHなんかもあるけど、基本的にSegwit非対応なウォレットとの互換のためだけの仕様なので、普通にペイメントチャネル実装する際に使うことはないだろう。

P2WPKHを使うトランザクションの作成と署名

だいぶ前に書き始めて放置してたのでちゃんと実装してみた。

以前↓のようにwitnessなトランザクションのパース方法について書いたので、

techmedia-think.hatenablog.com

続いてwitnessなトランザクションを作ってみる。

P2WPKHにBitcoinを送付

まず最初にP2WPKH(Pay-to-Witness-Public-Key-Hash)のscriptPubkeyに対してBitcoinの支払いをするトランザクションを作成する。

P2WPKHのscriptPubkeyは以下のフォーマットの22バイトのデータになる。

0 < 20-byte-pubkey-hash >

実際にtestnetでP2WPKHの支払いをしたトランザクションが↓

{
  "hex": "0100000001f55cb86d8d04d4759fb8b05a198cf4d48d790e6c64d00e072aed98281d0ebff1010000006b483045022100fe718c5f0bb58d86225e1d9370f858b8c864f00112c6a33f9910fa7ea8e9c34b02203cef1a73a0a8e210c6a264446bbb90c86b7b6f6e6f411aa505f0a835ff147204012102effb2edfcf826d43027feae226143bdac058ad2e87b7cec26f97af2d357ddefaffffffff02806d0d00000000001600148911455a265235b2d356a1324af000d4dae0326250a1c917000000001976a9142c159d64daa0de5ae6abac61a9416c8a54e834bd88ac00000000",
  "txid": "fdb55428ed5a1949cad4732fcb1be031a9790e7e0f651fd33129909065511580",
  "hash": "fdb55428ed5a1949cad4732fcb1be031a9790e7e0f651fd33129909065511580",
  "size": 223,
  "vsize": 223,
  "version": 1,
  "locktime": 0,
  "vin": [
    {
      "txid": "f1bf0e1d2898ed2a070ed0646c0e798dd4f48c195ab0b89f75d4048d6db85cf5",
      "vout": 1,
      "scriptSig": {
        "asm": "3045022100fe718c5f0bb58d86225e1d9370f858b8c864f00112c6a33f9910fa7ea8e9c34b02203cef1a73a0a8e210c6a264446bbb90c86b7b6f6e6f411aa505f0a835ff147204[ALL] 02effb2edfcf826d43027feae226143bdac058ad2e87b7cec26f97af2d357ddefa",
        "hex": "483045022100fe718c5f0bb58d86225e1d9370f858b8c864f00112c6a33f9910fa7ea8e9c34b02203cef1a73a0a8e210c6a264446bbb90c86b7b6f6e6f411aa505f0a835ff147204012102effb2edfcf826d43027feae226143bdac058ad2e87b7cec26f97af2d357ddefa"
      },
      "sequence": 4294967295
    }
  ],
  "vout": [
    {
      "value": 0.00880000,
      "n": 0,
      "scriptPubKey": {
        "asm": "0 8911455a265235b2d356a1324af000d4dae03262",
        "hex": "00148911455a265235b2d356a1324af000d4dae03262",
        "type": "witness_v0_keyhash"
      }
    }, 
    {
      "value": 3.99090000,
      "n": 1,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 2c159d64daa0de5ae6abac61a9416c8a54e834bd OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a9142c159d64daa0de5ae6abac61a9416c8a54e834bd88ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "mjY3vKRzyHkpB5kbEwCxFNmkFb4wKVDVab"
        ]
      }
    }
  ]
}

0番目の出力がP2WPKHへの支払いで、scriptPubKeyのtypewitness_v0_keyhashになっているのがわかる。

witnessなトランザクションの作成と署名

↑でP2WPKH宛に送ったBitcoinを入力にしたトランザクションの作成と署名をする。

ここで注意するのが、署名の方法も従来とは変わっているということ。
署名時に計算するトランザクションのSIG_HASHの新しい計算方法がBIP-143で定義されている↓

techmedia-think.hatenablog.com

BIP-143の仕様をbitcoin-rubyで実装してみたのが↓

まだプルリクは出してないけど、bitcoin-rubyにsegwit対応のコードを実装してるのが↓

作成したプルリクがbitcoin-rubyの0.0.11で取り込まれたのでそのバージョンからは以下のコードで署名可能

(仕様が変わる可能性はあるけど)現状の↑を使ってP2WPKHのUTXOを使用するコードは以下のように書ける↓ P2WPKHのwitness<signature> <pubkey>の構成になる。

from_key = Bitcoin::Key.from_base58('P2WPKHのUTXOの秘密鍵')
prev_tx = Bitcoin::Protocol::Tx.new('P2WPKHのUTXOを持つトランザクションのrawデータ')

tx = Bitcoin::Protocol::Tx.new
tx.add_in(Bitcoin::Protocol::TxIn.from_hex_hash(prev_tx.hash, 0))
tx.add_out(Bitcoin::Protocol::TxOut.value_to_address(880000 - 10000, from_key.addr))

# BIP-143の仕様でSIGHASHを生成
sig_hash = tx.signature_hash_for_witness_input(0, prev_tx.out[0].script, 880000)

sig = from_key.sign(sig_hash) + [Bitcoin::Script::SIGHASH_TYPE[:all]].pack("C")

# witnessを構成(P2WPKHなのでwitnessは、 "<署名> <公開鍵>" の構成)
tx.in[0].script_witness.stack << sig
tx.in[0].script_witness.stack << from_key.pub.htb

# witnessなペイロード
puts tx.to_witness_payload.bth

生成したwitnessペイロードを実際にtestnetでブロードキャストしたトランザクションが↓

{
  "hex": "010000000001018015516590902931d31f650f7e0e79a931e01bcb2f73d4ca49195aed2854b5fd0000000000ffffffff0170460d00000000001976a9148911455a265235b2d356a1324af000d4dae0326288ac02473044022009ea34cf915708efa8d0fb8a784d4d9e3108ca8da4b017261dd029246c857ebc02201ae570e2d8a262bd9a2a157f473f4089f7eae5a8f54ff9f114f624557eda7420012102effb2edfcf826d43027feae226143bdac058ad2e87b7cec26f97af2d357ddefa00000000",
  "txid": "07b09f22abd2d78c41b2984f05d3dd83a3c5905771f0ee290b04f933e0c13d59",
  "hash": "ac6506dab409881178f4d1b416188f903e85a5d588f175d930911532cb53ac58",
  "size": 194,
  "vsize": 113,
  "version": 1,
  "locktime": 0,
  "vin": [
    {
      "txid": "fdb55428ed5a1949cad4732fcb1be031a9790e7e0f651fd33129909065511580",
      "vout": 0,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "txinwitness": [
        "3044022009ea34cf915708efa8d0fb8a784d4d9e3108ca8da4b017261dd029246c857ebc02201ae570e2d8a262bd9a2a157f473f4089f7eae5a8f54ff9f114f624557eda742001", 
        "02effb2edfcf826d43027feae226143bdac058ad2e87b7cec26f97af2d357ddefa"
      ],
      "sequence": 4294967295
    }
  ],
  "vout": [
    {
      "value": 0.00870000,
      "n": 0,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 8911455a265235b2d356a1324af000d4dae03262 OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a9148911455a265235b2d356a1324af000d4dae0326288ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "mt1hZLajqyc63NkWy7qvgiuum5nuTBdVZ6"
        ]
      }
    }
  ]
}

次はP2WSHの署名を。

bitcoin-rubyで決定性署名を生成する

bitcoin-rubyのP2PKHの署名のデフォルト実装

bitcoin-rubyを使ってP2PKHのUTXOを入力にしたトランザクションの署名は↓のように書ける。

require 'bitcoin'

Bitcoin.network = :testnet

prev_key = Bitcoin::Key.from_base58('秘密鍵')
prev_tx = Bitcoin::Protocol::Tx.new('入力のOutPointのTxのrawデータ'.htb)

tx = Bitcoin::Protocol::Tx.new
tx.add_in(Bitcoin::Protocol::TxIn.from_hex_hash(prev_tx.hash, 1))
tx.add_out(Bitcoin::Protocol::TxOut.value_to_address(bitcoinの量, '送り先のアドレス'))

# 署名対象のsighash
sig_hash = tx.signature_hash_for_input(0, prev_tx)
# 署名の生成
sig = prev_key.sign(sig_hash) + [Bitcoin::Script::SIGHASH_TYPE[:all]].pack("C")

tx.in[0].script_sig = Bitcoin::Script.new(Bitcoin::Script.pack_pushdata(sig) + Bitcoin::Script.pack_pushdata(prev_key.pub.htb)).to_payload

# 署名済みのトランザクションのペイロード
puts tx.to_payload.bth

署名処理の中身はBitcoin::Key#signで、実態はBitcoin#sign_dataの↓のコード

def sign_data(key, data)
  sig = nil
  loop {
    sig = key.dsa_sign_asn1(data)
    sig = if Script.is_low_der_signature?(sig)
            sig
          else
            Bitcoin::OpenSSL_EC.signature_to_low_s(sig)
          end
    buf = sig + [Script::SIGHASH_TYPE[:all]].pack("C") # is_der_signature expects sig + sighash_type format
    if Script.is_der_signature?(buf)
      break
    else
      p ["Bitcoin#sign_data: invalid der signature generated, trying again.", data.unpack("H*")[0], sig.unpack("H*")[0]]
    end
  }
  return sig
end

ECDSAの署名自体はffiを使ってOpenSSLに委譲しており、この時生成される署名データは生成の都度、別の値になる。(なので非witnessな場合、txidも毎回変わる)

ECDSAの署名は、署名対象のデータと秘密鍵とランダムに生成されたnonceを使って生成される。OpenSSLでは署名の都度このnonceをランダムに生成しているため、↑のコードで同じトランザクションに署名をした際に、毎回異なる署名が生成される。

この時大事なのがランダムなnonce生成器の精度。nonce生成の実装アルゴリズムに偏りがあるとnonceが重複しやすく、同じnonceを使っている署名データから容易に秘密鍵を計算することができてしまうというリスクがある。
(そもそも真の乱数を生成するのは難しいし、偏りのない乱数かテストするのも難しい。)

RFC 6979とBitcoin CoreのSecp256k1

実装のミスなどによって偏りのあるnonceが生成されるような事を防ぐために、このnonceの生成処理を決定論的に行おうというのがRFC 6979↓

RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)

RFC 6979の3.2章にnonceの生成プロセスが記載されている↓

  1. 署名対象のデータmハッシュ値 h1 = H(m)を生成する(h1はhlenビットのシーケンス)
  2. 32バイト分0x01をセットしたバイトシーケンスVを作成
  3. 32バイト分0x00をセットしたバイトシーケンスKを作成
  4. K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1)) を計算
    ||は連結、x秘密鍵
  5. V = HMAC_K(V)を計算
  6. K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))を計算
  7. V = HMAC_K(V)を計算
  8. 空のシーケンスTし、その長さをtlenとする。tlen < qlenの間以下を繰り返す。
    V = HMAC_K(V)
    T= T || V
    qlenはカーブオーダーの除数である十分に大きな素数qの長さ)

Bitcoin Coreはsecp256k1を独自に実装してこの仕様を導入しているため、同じトランザクションデータと秘密鍵からは同じnonceが生成される。そのため同じトランザクションデータに対してsignrawtransactionを何回実行しても、生成される署名データは同じものになる。

Bitcoin CoreでRFC 6979に基づいてnonceを生成して署名しているのが

https://github.com/bitcoin/bitcoin/blob/v0.13.2/src/secp256k1/src/secp256k1.c#L310-L389

https://github.com/bitcoin/bitcoin/blob/v0.13.2/src/secp256k1/src/hash_impl.h#L205-L270

あたり。

引数で与えられた秘密鍵と署名対象のデータが異なる場合、生成されるnonceは必ず別の値になる。

bitcoin-rubyで決定性署名の生成

bitcoin-rubyにもffiでsecp256k1を使用するインターフェースがあるので、署名の生成にsecp256k1を使うようにすれば決定性署名の生成が行える。
(secp256k1の関数を利用するには、環境変数にlibsecp256k1.soのパスをセットする必要がある。)

require 'bitcoin'

Bitcoin.network = :testnet

 # libsecp256k1.soのパスを環境変数にセット
ENV['SECP256K1_LIB_PATH'] = '/usr/local/lib/libsecp256k1.so'

prev_key = Bitcoin::Key.from_base58('秘密鍵')
prev_tx = Bitcoin::Protocol::Tx.new('入力のOutPointのTxのrawデータ'.htb)

tx = Bitcoin::Protocol::Tx.new
tx.add_in(Bitcoin::Protocol::TxIn.from_hex_hash(prev_tx.hash, 1))
tx.add_out(Bitcoin::Protocol::TxOut.value_to_address(bitcoinの量, '送り先のアドレス'))

# 署名対象のsighash
sig_hash = tx.signature_hash_for_input(0, prev_tx)

# secp256k1を使った署名の生成
sig = Bitcoin::Secp256k1.sign(sig_hash, prev_key.priv.htb) + [Bitcoin::Script::SIGHASH_TYPE[:all]].pack("C")

tx.in[0].script_sig = Bitcoin::Script.new(Bitcoin::Script.pack_pushdata(sig) + Bitcoin::Script.pack_pushdata(prev_key.pub.htb)).to_payload

# 署名済みのトランザクションのペイロード
puts tx.to_payload.bth

同じsecp256k1を使って決定性署名を生成しているため、↑で生成した署名済みトランザクションペイロードと、署名前のトランザクションペイロードBitcoin Coreのsignrawtransactionに投げて生成されるトランザクションペイロードは同じ値になる。

※ 現在のbitcoin-rubyのバージョンは0.0.10で、それに対応したsecp256k1ライブラリはBitcoin Core v 0.13.1以上。またsecp256k1をビルドする際は、configureのオプションに--enable-module-recoveryを指定する必要がある。

OpenSSLではまだRFC 6979は実装されてないみたいなので、署名をする際はsecp256k1を使った方が安全かもしれない。

決定性辞書式順序ソートによるトランザクションの入出力のソート(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の順番でソートする。
  • この仕様自体は標準を決めるものなので、ソフトフォークなどのデプロイが発生するものではなさげ。