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を送る際の出力を最初の出力に配置し、おつりの出力を２番めに配置するため、送信者と受信者双方の財務情報をブロックチェーンのオブザーバーにリークすることになる。こういった情報は、消費者の利益のためだけでなく、より高水準な金融システムにおいても詐欺を防ぐために秘密にしておく必要がある。研究者は最近、Bitstampが交換トランザクションを作成する際に情報漏洩したことを発見した際にこれを実証した。

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

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

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

仕様

適用範囲

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

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

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

辞書式順序ソート

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

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

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

詳細についてはWikipedia参照。

トランザクションの入力

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

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

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

トランザクションの出力

トランザクションの出力は、scriptPubkeyとamountによって定義される。標準的な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

ディスカッション

• [Bitcoin-development] Lexicographical Indexing of Transaction Inputs and Outputs
• [Bitcoin-development] [RFC] Canonical input and output ordering in transactions

実装

• Electrum
• BitcoinJS
• BitcoinJS Test Fixtures
• NodeJS
• Blockchain.info public beta
• Btcsuite

まとめ

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

Lightning Networkを使ったクロスチェーン取引

Bitcoin MagazineのLightning Networkを使ったクロスチェーン取引の拡張についての記事が出てた↓ので見てみる。

bitcoinmagazine.com

Atomic Swap

そもそもBitcoinとアルトコインの相互運用というのは、別に新しいことではなく、2013 年にTier Nolanが紹介している↓

Atomic cross-chain trading - Bitcoin Wiki

Atomic cross-chain trading

クロスチェーンの取引をアトミックに行う際の課題は、２人の当事者アリスとボブがいて、それぞれ別々の暗号通貨を持っている状況で、第三者を信頼することなくお互いのコインをアトミックに交換することにある。非アトミックであればアリスがボブにコインを送り、コインを受け取ったボブがアリスにコインを送ることができるが、この場合ボブがアリスにコインを送らなければ、ボブがアリスのコインを盗んで終わりになってしまう。

第三者や取引相手を信頼することなく、この交換を行う方法として↓の２つが挙げられている。

シークレットの交換とロックタイムを使った解決策

シークレットとロックタイムを利用したアトミックな取引は以下のような仕組みで行われる。

１. アリスはランダムな数値xを生成する（xはこの時点でアリスのみが知っている）
２. アリスはwコインを以下のscriptPubkeyに送るTX1を作成する

IF
    2 <アリスの公開鍵> <ボブの公開鍵> 2 CHECKMULTISIGVERIFY
ELSE
  HASH160 <H(x)> EQUAL <ボブの公開鍵> CHECKSIGVERIFY
ENDIF

３. 続いて、TX1のwコインをアリスの公開鍵に送るTX2を作成する。このTX2のnLocktimeには48時間後までロックするよう設定する。
４. アリスはTX2をボブに送ってIF分岐のマルチシグの１つであるボブの署名をしてもらう
５. ボブはTX2の署名をしたTX1をアリスに返す
６. ボブから署名済みのTX2を受け取ったアリスはTX1をBitcoinネットワークにブロードキャストする
７. 続いてボブが、vアルトコインを以下のscriptPubkeyに送るTX3を作成する

IF
    2 <アリスの公開鍵> <ボブの公開鍵> 2 CHECKMULTISIGVERIFY
ELSE
  HASH160 <H(x)> EQUAL <アリスの公開鍵> CHECKSIGVERIFY
ENDIF

８. 続いてTX3のwコインをボブの公開鍵に送るTX4を作成する。このTX4のnLocktimeには24時間後までロックするよう設定する。
９. ボブはTX4をアリスに送ってIF分岐のマルチシグの１つであるアリスの署名をしてもらう。
１０. アリスから署名済みのTX4を受け取ったボブはTX3をアルトコインのネットワークにブロードキャストする。
１１. アリスはxを使ってTX3のELSE分岐の条件の署名を行いvコインを入手する。
１２. アリスがvコインを入手するトランザクションがアルトコインのネットワークにブロードキャストされるとボブはxの値が分かるので、そのxを使ってTX1のELSE分岐の条件の署名を行いwコインを入手する。

TX1もTX2はそれぞれアリスとボブの署名があればいいだけなので、↑はSegwitを必要とせず払い戻し用トランザクションTX2とTX4が作れる。

共通のシークレットxを利用して、２つのブロックチェーン上でそれぞれのコインをロックし、xが明かされるとそれぞれのチェーンで交換したコインを入手できるようになっている。この時大事なのはxを作った側（↑ではアリス）が作成するトランザクション（↑ではTX1）のロックタイムより、相手が作成するトランザクション（↑ではTX3）のロックタイムの方を短く設定しておく必要がある。

基本的な仕組みはHTLCs↓

techmedia-think.hatenablog.com

特殊なアルトチェーンを使った解決策

↑の方法は、アルトチェーン側の特別なサポートを必要とせずBitcoinとアルトコインを交換できる。ただ欠点はnLocktimeで、相手が取引を行わない場合nLocktimeで指定した期間まで資金がロックされることである。特殊なアルトチェーンを使うことで、こういった欠点の無い形でアトミックにコインを交換する方法もある。

アリスがアルトチェーン、ボブがBitcoinでそれぞれコインを保持しているとする。

1. まずボブは普通にBitcoinを送るトランザクションを作成し、署名を行い、そのトランザクションのtxidを算出する。その後、txidとその入力のスクリプトと署名をブランクにしたトランザクションをアリスに送る。
2. アリスは、そのトランザクションのハッシュを計算する。これをblankhashと呼ぶ。続いてblankhashとtxidを引数にとるbitcointxid opcodeを使ってアルトコインを送るトランザクションを構成し、アルトチェーンのネットワークにブロードキャストする。
3. ボブはアルトチェーンでトランザクションが承認されるのを待ち、その出力が事前に合意していた内容かどうか検証する。内容が問題なければボブは元々の署名付きのトランザクションをアリスに送り、アリスはそれをBitcoinネットワークにブロードキャストしてBitcoinを入手する。

ただ、これで正常にクロスチェーンのAtomic Swapをするためには、アルトコイン側のチェーンで以下のルールが必要になる。

• bitcointxidというopcodeは、引数に与えられたtxidのトランザクションをBitcoinのブロックチェーン上で確認し、そのトランザクションの入力のスクリプトと署名をブランクにして計算したハッシュがblankhashと同じでその出力が使用可能な場合、trueを返す。（このためアルトチェーンのクライアントはBitcoinのブロックチェーンと通信する）
• アリスがブロードキャストしたアルトチェーンのトランザクションは、bitcointxidに渡したtxidのトランザクションがBitcoinのネットワーク上で確認されなくても構築することができる。
• ただし、そのトランザクションの出力はBitcoinネットワーク上で対象のトランザクションが確認できるまで、使用可能にはならない。
• アルトチェーン側のトランザクションの入力は、Bitcoinのネットワークで対象のトランザクションが確認されその出力が使用可能な状態になるまで、何回でも他のトランザクションの入力として使える。ただ、最終的に使われる入力はBitcoinのトランザクションで最初に確認されたtxidを使用しているトランザクションになり、その他の同じ入力を使っているトランザクションは無効になる。

※ 実際にこういうことしてるアルトチェーンってあるんだろうか？

Lightning Networkを利用したクロスチェーン取引

Lightning NetworkはBitcoin向けに設計されているけど、Bitcoinのコードベースからフォークしているアルトコイン（LitecoinやDogecoin、Zcashなど）であれば同様にLightning Networkをホストできる。

Lightning Networkは↑のAtomic Swapの仕組みと同様、HTLCsを利用していて、これによって、アリスとボブがそれぞれキャロルとPayment Channelをオープンしていれば、アリスとボブ間にPayment Channelが開いてなくても、キャロルを経由してコインを送付できるようになっている。この時アリスとボブは仲介者キャロルを信頼する必要はない。

その際、どういったトランザクションを構成するかは↓ techmedia-think.hatenablog.com

Lightning NetworkとクロスチェーンのAtomic Swapは、基本的な仕組みは同じで、このプロセスをマージすることでLightning Networkを利用したクロスチェーン取引が可能になるという話（記事では仕組みについては書かれていない）。Bitcoinとアルトコインの両方のブロックチェーンでチャネルをオープンしているピアは、アルトコインとBitcoinを交換するPayment Processorとして機能する。

例えばアリスがボブからPCを購入しようとしていて、ボブは１ BTCを請求するがアリスがLitecoinしか持っていない場合。幸いにもキャロルがアリスとの間にLitecoinのPayment Channelをオープンしていて、ボブとの間にはBitcoinのPayment Channelをオープンしていたとする。この時アリスはキャロルに200Litecoinを送り、キャロルはボブに1 BTC送る。この取引はHTLCsで構成されており、キャロルをトラストレスなPayment Processorとして利用できる。

またアリスとボブがそれぞれBitcoinとLitecoinのチャネルをキャロルとオープンしている場合、資金を交換することもできる。アリスがキャロルに200 Litecoinを送り、キャロルはそれをボブに送る。ボブはその後１ BTCをキャロルに送り、キャロルはそれをアリスに送る。これもまはHTLCsで構成されており、キャロルをトラストレスなアルトコインの交換所として利用できる。

クロスチェーンのLightning NetworkはBitcoinのLightning Networkを改善することにもなる。例えば、BitcoinとBitcoinの決済がLitecoinのピアを経由して行った方が安価な経路になるケースが考えられる。また複数のコインを扱っているユーザはPayment Channelを使ってそれぞれのコインのバランスを調整することができる。

課題

Lightning Netoworkを利用したクロスチェーン取引にはいくつかの課題がある。

１つはDoS攻撃からの保護。Lightning Networkの仕組み上、トラストレスな構成で仲介者が資金を盗むことができないようになっている反面、仲介者が決済プロセスを阻止or停止する可能性がある。これを解決するには、非協力的なピアのチャネルをクローズする必要がある。ただ、この攻撃を行う場合、非協力的なピアもチャネルを開く必要があるので、チャネルにコインがロックされその攻撃コストは高くなる。

しかし、チャネルを閉じ攻撃者が処罰されたか確認するためには、決済チェーンに関係した各ピアが全ての参加者を監視できる必要がある。

また当然のことながら、Lightning Networkがデプロイされる必要があり、そのためにはSegwitがアクティベートされる必要があるが、まだアクティベートされる様子はない。

所感

• ペグではなく、Atomic Swapみたいにクロスチェーン間の取引を利用した仕組みをベースにした拡張を考えるのもおもしろそう。
• Lightning NetworkとAtomic Swapをどうマージするのか仕組みが気になる。
• Lightning Networkでクロスチェーン取引をする場合、その仲介者は実質的にコインの交換業者のような役割を果たしてる。

HDウォレット（BIP-32）

長編のBIPで斜め読みしてたので、ちゃんと読んでみる。

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

概要

このBIPでは階層的決定性ウォレット（HDウォレット）について説明する。

この仕様では、異なるクライアント間で交換可能な決定性ウォレットの標準化を目的としている。ここで説明するウォレットにはたくさんの機能があるが、クライアントに全ての機能のサポートを要求するものではない。

仕様は２つのパートで構成される。最初のパートで、単一のシードからキーペアのツリーを導出するためのシステムについて説明する。続くパートで、その構造を使ってウォレットを構築する方法を説明する。

動機

Bitcoin Core（Bitcoinの参照クライアント）は、ランダム生成されたキーを使用する*1。トランザクションのブロードキャスト後に毎回鍵のバックアップをするのを避けるため、キーは都度生成されるのではなく、デフォルトで100個のキーが予約キーのプールにキャッシュされるようになっている。そのためこれらを複数のシステムで同時に共有・使用することはできない。またBitcoin Coreではウォレットの暗号化機能を利用しパスワードを共有しないことで秘密鍵を隠すことができるが、こういったウォレットでは公開鍵を生成する機能もない。

決定性ウォレットは、頻繁なバックアップを必要とせず、楕円曲線の特性を利用して秘密鍵を明かすことなく公開鍵を計算することができるスキームを可能にする。このため例えばECサイトを運用する場合、ECサイトのサーバが秘密鍵にアクセスすることなく、決済や顧客毎に新しい支払い用のアドレス（公開鍵のハッシュ）を生成することができるようになる。

ただ決定性ウォレットは、単一のキーペアのチェーンから構成される。チェーンが１つしかないということは、ウォレットを共有することがオール・オア・ナッシングになる。ユースケースによっては、一部の公開鍵だけ共有したいケースもある。ECサイトの場合、サーバはEC事業者のウォレットの全ての公開鍵にアクセスする必然性はなく、顧客の支払いを受け取るために使われるアドレスにのみ適用されればいい。階層的決定性ウォレットは、単一のルートから派生した複数のキーペアチェーンをサポートすることで、このような選択的な鍵の共有を可能にする。

鍵導出の仕様

表記

このBIPで扱うのは、Bitcoinで使われる公開鍵暗号であるsecp256k1を使った楕円曲線暗号をベースとする。またこれから扱う変数は以下のいずれかである。

• 曲線の位数（nとする）を法とする整数
• 曲線上の点の座標
• バイトシーケンス

２つの座標ペアの加算(+)は、ECグループの操作として定義される。連結(||)はバイトシーケンスを別のバイトシーケンスに追加する操作を表す。

スタンダードな変換関数を、以下のように表記する。

• point(p)
  secp256k1のベースポイントに、整数pを使ってECポイントの乗算をした結果を返す
• ser₃₂(i)
  32bitのunsigned integer iをシリアライズした先頭4バイトのシーケンス。最上位バイトが先頭（＝ビッグエンディアン）
• ser₂₅₆(p)
  整数pをシリアライズした先頭３２バイトのシーケンス。最上位バイトが先頭（＝ビッグエンディアン）
• ser_P(P)
  SEC1の圧縮形式 (0x02 or 0x03) || ser₂₅₆(x)を使って座標ペアP＝(x, y)をシリアライズしたバイトシーケンス
• parse₂₅₆(p)
  32バイトのシーケンスを256bitの数字として解釈する。最上位バイトが先頭（＝ビッグエンディアン）

拡張鍵

↓で親キーからいくつかの子キーを派生させる関数を定義する。その際、キーのみに依存することを避けるため、最初に余分な256 bitのエントロピーを追加して公開鍵と秘密鍵両方を拡張する。chain codeと呼ばれるこの拡張は、秘密鍵と公開鍵のペアに同一のものが使用され、32バイトで構成される。

ここでは拡張した秘密鍵を(k, c)と表記する。kは元の秘密鍵で、cがchain codeを表す。
拡張した公開鍵も同様に(K, c)と表記し、Kはpoint(k)でcがchain codeを表す。

各拡張鍵は、2³¹個の通常の子キーと2³¹個の強化鍵を持ち、これらの子キーにはそれぞれインデックスがある。通常の子キーはインデックスとして0〜2³¹-1を使用し、強化された子キーは2³¹〜2³²-1のインデックスを使用する。強化鍵のインデックスの表記を簡単にするため数値i_Hを使ってi+2³¹と表す。

子キー導出（CKD）関数

親の拡張鍵とインデックスiが与えられると、対応する子拡張鍵を計算することができる。この計算アルゴリズムは、子が強化鍵かどうか（iが2³¹以上かどうか）、対象が秘密鍵か公開鍵によって決まる。

親秘密鍵→子秘密鍵の計算

関数 CKDpriv( (k_par, c_par), i) → (k_i, c_i) で、親拡張秘密鍵から子拡張秘密鍵を計算する。

• i ≥ 2³¹かどうかチェックする（子が強化鍵かどうかチェックする）
  • 強化鍵の場合は、I = HMAC-SHA512(Key = c_par, Data = 0x00 || ser₂₅₆(k_par) || ser₃₂(i))を計算する。（0x00は秘密鍵を33バイトの長さにするためのパディング）
  • 通常の子の場合は、I = HMAC-SHA512(Key = c_par, Data = ser_P(point(k_par)) || ser₃₂(i))を計算する。
• 計算した I を２つの32バイトのシーケンスに分割する（分割したのをl_Lとl_Rとする）
• parse₂₅₆(I_L) + k_par (mod n)が子鍵 k_iとなる。
• chain code c_iは、l_Rとなる。
• parse₂₅₆(I_L) ≥ n もしくは k_i = 0 となる場合は、その鍵は無効で i を次の値を使って処理を進める必要がある。

HMAC-SHA512関数はRFC 4231で定義されている。

親公開鍵→子公開鍵の計算

関数 CKDpub( (K_par, c_par), i) → (K_i, c_i) で、親拡張公開鍵から子拡張公開鍵を計算する。この関数は強化されていない子キーに対してのみ有効な関数である。

• i ≥ 2³¹かどうかチェックする（子が強化鍵かどうかチェックする）
  • 強化鍵の場合はfailureを返す
  • 通常の子の場合は、I = HMAC-SHA512(Key = c_par, Data = ser_P(K_par) || ser₃₂(i)) を計算する
• 計算した I を２つの32バイトのシーケンスに分割する（分割したのをl_Lとl_Rとする）
• point(parse₂₅₆(I_L)) + K_parが子鍵K_iとなる。
• chain code c_iは、l_Rとなる。
• parse₂₅₆(I_L) ≥ n もしくはK_iが無限遠点である場合は、その鍵は無効で i を次の値を使って処理を進める必要がある。

親秘密鍵→子公開鍵の計算

関数 N( (k, c)) → (K, c)で、拡張秘密鍵に対応する拡張公開鍵を計算する。

• 返却されるKはpoint(k)
• 返却されるchain codeは渡されたchain code

親秘密鍵から子公開鍵を計算するには↓の２つの方法がある

• N(CKDpriv( (k_par, c_par), i) )
  親秘密鍵から子秘密鍵を生成し、そこから子公開鍵を生成する方法で、常に動作する。
• CKDpub( N(k_par, c_par), i )
  親秘密鍵から親公開鍵を生成し、そこから子公開鍵を生成する方法で、強化されていない子鍵の場合のみ動作する。

親公開鍵→子秘密鍵の計算

この計算は不可能。

鍵ツリー

次のステップでは、いくつかのCKD構成をカスケードしてツリーを構築する。まず１つのルートとなるマスター拡張鍵mを取る。いくつかのi の値についてCKDpriv(m,i)を計算すると、レベル１の派生ノードがいくつかできる。生成されたものは拡張鍵なので、それらについてもCKDprivを適用できる。

表記を簡略化するためCKDpriv(CKDpriv(CKDpriv(m,3H),2),5)をm/3H/2/5と表記する。公開鍵も同様にCKDpub(CKDpub(CKDpub(M,3),2),5)をM/3/2/5と表記する。結果以下は同一のものを指す。

• N(m/a/b/c) = N(m/a/b)/c = N(m/a)/b/c = N(m)/a/b/c = M/a/b/c
• N(m/aH/b/c) = N(m/aH/b)/c = N(m/aH)/b/c

ただし、N(m/aH)はN(m)/aHとは書けない。（後者は不可能なので）

ツリーの各リーフノードは、実際の鍵に対応し、内部ノードはツリーの下にある鍵の集合に対応する。リーフノードのchain codeは無視され、埋め込まれた秘密鍵と公開鍵のみが関連を持つ。この構成のため、拡張された秘密鍵を知っていれば、その全ての子・孫秘密鍵とそれに対応する公開鍵を再構成でき、拡張された公開鍵を知っていれば、その全ての強化されていない子・孫公開鍵を再構成できる。

鍵識別子

拡張鍵は、シリアライズされたECDSAの公開鍵KのHash160（SHA256してRIPEMD160した値）によって識別できる。これは従来のBitcoinアドレスで使用されているデータと全く同じである。そのためアドレスとして解釈される可能性があるので、このデータをBase58で表現することは避けた方がいい。

この識別子の最初の32 bitをkey fingerprintと呼ぶ。

シリアライゼーションフォーマット

拡張公開鍵と秘密鍵は以下のフォーマットでシリアライズされる。

バイト数	内容
4	version bytes。mainnetの場合は公開鍵が0x0488B21Eで秘密鍵が0x0488ADE4、 testnetの場合は公開鍵が0x043587CFで秘密鍵が0x04358394
1	ツリーの深さ。マスターノードが0x00で、レベル１の派生鍵は0x01
4	親鍵のfingerprint（マスター鍵の場合は0x00000000を使用）
4	子の番号で、xi = xpar/iにおけるiのser32(i)。xiはキーがシリアライズされたもの。（マスター鍵の場合は0x00000000を使用）
32	chain code
33	公開鍵または秘密鍵のデータ（公開鍵の場合はserP(K)、秘密鍵の場合は 0x00 || ser256(k)）

この78バイトの構造に32bitのチェックサムを追加し、その後Base58でエンコードされ、最大112文字のデータが生成される。選択したversion bytesによってBase58エンコードした値はmainnetの場合はxpubもしくはxprvで始まり、testnetの場合はtpubもしくはtprvで始まる。

親のfingerprintはソフトウェア内で親ノードと子ノードを高速に検出するためのものなので、衝突についてはソフトウェア側で考慮する必要がある。内部的には完全な160 bitの識別子を使用可能。

シリアライズされた公開鍵をインポートする際は、公開鍵データ内のX座標が楕円曲線上のポイントとして存在するかどうか検証する必要がある。もし楕円曲線上のポイントではない場合、その拡張公開鍵は無効である。

マスター鍵の生成

生成可能な拡張鍵ペアの総数は2⁵¹²だが、生成される鍵は256bit長で、セキュリティの観点から約半分になっている。そのためマスター鍵は直接生成されるのではなく、短いシード値から生成される。

1. (P)RNGから選択された長さ（128 bit から512 bitの間で、256 bitが推奨される）のシードのバイトシーケンスSを生成する。
2. I = HMAC-SHA512(Key = "Bitcoin seed", Data = S)を計算する。
3. 計算した I を２つの32バイトのシーケンスに分割する（分割したのをl_Lとl_Rとする）
4. parse₂₅₆(I_L)がマスター秘密鍵で、I_R がmaster chain codeとなる。

I_L=0、もしくはI_L ≥ n の場合、そのマスター鍵は無効。

ウォレットの構造の仕様

↑のセクションでは、鍵ツリーとそのノードについて定義したので、次のステップではウォレットにこのツリー構造を取り込む。このセクションで定義されているレイアウトはデフォルトであり、クライアントは互換性のためこのレイアウトを模倣することが推奨されるが、全ての機能がサポートされるわけではない。

デフォルトのウォレットレイアウト

HDW（HDウォレット）はいくつかのアカウントで編成されている。アカウントにはそれぞれ番号が付けられており、デフォルトアカウント""の番号は0になる。クライアントは必ずしも複数のアカウントをサポートする必要はなく、その場合デフォルトアカウントのみを使う。

各アカウントはinternalとexternalの２つのキーペアチェーンで構成されている。externalキーチェーンは（Bitcoinの受け取り用に）新しい公開アドレスを生成するために使われ、internalキーチェーンはその他の全ての操作（おつり用アドレスや、世代アドレスなど生成）で使われる。こういった分離されたキーチェーンをサポートしていないクライアントは、externalキーチェーンのみを使用して全ての操作をする必要がある。

• m/i_H/0/kはマスター鍵mから派生したHDWのアカウント番号 i のexternalチェーンのk番目のキーペアを表す。
• m/i_H/1/kはスター鍵mから派生したHDWのアカウント番号 i のinternalチェーンのk番目のキーペアを表す。

ユースケース

完全ウォレット共有：m

２つのシステムが単一の共有ウォレットにアクセスする必要があり、どちらのシステムもBitcoinの支払いが行える必要がある場合は、マスター拡張秘密鍵を共有する必要がある。

ノードは入金を監視するため、externalチェーン用にキャッシュされたN個のlook-ahead keysを保持することができる。このユースケースでは予想されるギャップは無いので、internalチェーンのlook-aheadは非常に小さくすることができる。新しいアカウントの作成時に、未使用のアカウントチェーンに対し確保されているlook-aheadが有効になる。なお、アカウント名はブロックチェーンを介して同期できないので、手動で入力する必要がある。

監査： N(m/*)

監査ノードが入金と出金のリストにフルアクセスする必要がある場合は、全てアカウントの拡張公開鍵を共有する。これにより監査ノードは全てのアカウントの入りと出のトランザクションを参照できる。ただし、秘密鍵は参照できない。

オフィス毎の残高：m/iH

複数の独立したオフィスがある場合は、単一のマスターから派生したウォレットを使用する。これにより本社は、全てのオフィスの全ての入りと出のトランザクションを参照でき、オフィス間の資金移動も可能なスーパーウォレットを保持することになる。

定期的なB2B取引： N(m/iH/0)

取引先間において頻繁に資金を送ることがある場合は、一方の特定のアカウント（M/i h/0）のexternalチェーンの拡張公開鍵をスーパーアドレスの一種として利用することで、支払い毎に支払先の新しいアドレスを要求することなく頻繁に取引することができる。このような仕組みは、可変支払いアドレスとしてマイニングプールのオペレータが使うこともできる。

セキュリティに依存しない資金の受け取り： N(m/iH/0)

Webサーバ上でECサイトを運営している場合、支払いを受け取るための公開アドレスを知る必要がある。（セキュリティに気をつけていても脆弱性のリスクなどはあるので）Webサーバには単一のアカウントのexternalチェーンの拡張公開鍵のみを配置する。これによりWebサーバの脆弱性をついて誰かが侵入したとしても、全ての入金を見ることはできるが資金を盗むことはできないし、サーバが複数台ある場合他のWebサーバが受け取った支払いを見ることもできない。

互換性

この標準に準拠するには、クライアントは少なくとも拡張公開鍵もしくは拡張秘密鍵をインポートできなければならない。仕様の第２部に記載しているウォレットの構造（master/account/chain/subchain）についてはアドバイザリーという位置付けではあるが、（クライアントの機能としてアカウントが分離されていなかったり、internalとexternalチェーンに区別が無かったとしても）互換性のための最小限の構成として推奨する。しかし実際の実装では特定のニーズに合わせて逸脱することがある。より複雑なアプリケーションでは、より複雑なツリー構造が必要になることもある。

セキュリティ

↓の楕円曲線の公開鍵暗号自体の特性に加え

• 公開鍵Kが与えられたとして、攻撃者は楕円曲線の離散対数問題を解く以外に効率的に対応する秘密鍵を見つけることはできない。

この規格の意図するセキュリティ特性は以下の通り

• 子の拡張秘密鍵(K_i, c_i)と整数 i が与えられたとして、攻撃者は2²⁵⁶のHMAC-SHA512のブルートフォースよりも効率的に親の秘密鍵k_parを見つけることはできない。
• インデックスと拡張秘密鍵からなるタプル(i_j,(k_ij,c_ij))の任意の数(2 ≤ N ≤ 2³²-1)が与えられたとして、ijが異なる際、それらが共通の親拡張秘密鍵から派生したものか判定するには、2²⁵⁶のHMAC-SHA512のブルートフォースより効率的な方法はない。

しかし、以下のような特性もある。

• 親の拡張公開鍵(K_par,c_par)と子の公開鍵(K_i)が与えられると、i を見つけるのは困難ではない。
• 親の拡張公開鍵(K_par,c_par)と強化されていない子の秘密鍵(k_i)が与えられると、親の秘密鍵k_parを見つけるのは困難ではない。

注意事項

秘密鍵と公開鍵は今までと同様、安全に保持する必要がある。秘密鍵の漏洩はコインへのアクセスを意味し、公開鍵の漏洩はプライバシーの喪失を意味する。

拡張鍵については、そのサブツリーの鍵に対応するためいくつか注意する必要がある。

１つの弱点は、親の拡張公開鍵と強化されていない子の秘密鍵が分かれば、親の拡張秘密鍵を知ることができるという点である（親の拡張秘密鍵が知られるということは、そのサブツリーの公開鍵及び秘密鍵が全て知られてしまうことになる）。これは拡張公開鍵は通常の公開鍵より慎重に扱わなければならないことを意味する。またこれは強化鍵が存在しツリーのアカウントレベルで使用される理由でもある。強化鍵を使うとアカウント固有の秘密鍵の漏洩が、マスターまたは他のアカウントに及ぶことはない。

Test Vectors

BIP参照

実装

Pythonの実装

• PyCoin

Javaの実装

• supernode/ExtendedKey.java at 1.1 · bitsofproof/supernode · GitHub
• bushido-java-core/src/main/java/com/bushidowallet/core/bitcoin/bip32 at master · bushidowallet/bushido-java-core · GitHub

C++の実装

• mSIGNA/hdkeys.h at master · ciphrex/mSIGNA · GitHub

Objective-Cの実装

• CoreBitcoin/BTCKeychain.h at master · oleganza/CoreBitcoin · GitHub

Rubyの実装

• GitHub - GemHQ/money-tree: A Ruby implementation of Bitcoin HD Wallets (Hierarchical Deterministic) BIP32

Goの実装

• btcutil/hdkeychain at master · btcsuite/btcutil · GitHub
• GitHub - wemeetagain/go-hdwallet: Go utilities for generating hierarchical deterministic Bitcoin wallets based on BIP 32

JavaScriptの実装

• GitHub - sarchar/brainwallet.github.com at bip32
• GitHub - bitpay/bitcore: A full stack for bitcoin and blockchain-based applications

PHPの実装

• GitHub - Bit-Wasp/bitcoin-lib-php: PHP libraries implementing bitcoin key functions, as well as BIP32 and electrum.

C#の実装

• GitHub - MetacoSA/NBitcoin: Comprehensive Bitcoin library for the .NET framework.

Haskellの実装

• GitHub - haskoin/haskoin: Haskell implementation of the Bitcoin protocol

bitcoin-rubyに実装してみた

github.com

プルリク出した後に、実は以前実装中ものがあったらしく、↑が取り込まれるかどうかは不明。

*1:Bitcoin Coreも0.13.0からHDウォレットをサポートした

Bitcoin Core 0.13.2のリリース

先日Bitcoin Core 0.13.2がリリースされた↓

bitcoincore.org

リリースノートは↓

bitcoincore.org

主な変更点

0.13系のマイナーアップデートなので、基本的にはBugfixとパフォーマンス改善のリリースになるので、新機能のリリースは無い。

古いOSをサポート対象外に

0.13.2というよりは0.13.x系だけど。

Windows

Windows XP自体が既にMicrosoftのサポートも切れ、セキュリティアップデートも提供されておらず、Bitcoin Coreも0.12.xでランダムにクラッシュする報告が挙げられているが、QtなどのライブラリがもうXPでテストされていない可能性もあり、サポートに割く時間もリソースも無いので、0.13.0以降、Windows XPはサポートしない。

Mac OS

0.13.1からOS X 10.7はサポート外に。0.13.1以降はOS X 10.8以降のみをサポート。

ウォレットのmempoolのリジェクトのハンドリング方法の変更

新しく作成したトランザクションが、制限によりmempoolに入れることが出来なかった場合、今までの仕様では、そのトランザクションをブロードキャストしようとしたRPCコールはエラーを返し、そのトランザクション自体はウォレット内に入っており、いくつかのトランザクションが承認されるとソフトウェアの再起動後にブロードキャストされる。

0.13.2では、↑のRPCコールは成功を返し、トランザクションの再ブロードキャストと同時にmempoolへの挿入を再試行するよう変更され、ソフトウェアの再起動を回避するようになった。

mempoolに格納されていないウォレット内のトランザクションは、abandontransaction RPCを使って放棄できる。