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を使って放棄できる。

Teechanの決済プロトコル

Bitcoin-NGやCovenantsなどの提案をしているコーネル大学の先生方が先日Teechanというオフチェーン決済のプロトコルに関するブログとホワイトペーパーを公開していたので見てみる↓

hackingdistributed.com

https://www.cs.cornell.edu/People/egs/papers/teechan.pdf

TeechanはTrusted Execution Environment（TEE）を利用したPayment Channelの実装プロトコルで、TEEを備えた２つのエンドポイント間にPayment Channelを構築する。

Trusted Execution Environment（TEE）とは

TEE＝信頼できる実行環境で、ホワイトペーパーの中ではCPUの拡張命令セットの１つであるSoftware Guard Extensions(SGX)を利用している。SGXはアプリケーションがシステムメモリ上に保護された領域を作成できる仕組み（その他のプログラムはアクセスできない）で、重要なデータをマルウェアなどから守ることを目的に最近のCPUに追加された命令セットになる。

チップにはEnclaveと呼ばれる特別な構成があり、Enclave内のメモリデータは、オフチップでは必ず暗号化されており、特殊なEnclaveコードが実行されている間のみオンチップでのみアクセスできる。
さらに復号化キー特定のハッシュを持つコードのみに有効であるため、もし攻撃者がEnclaveをハックしてそのハッシュを書き換えるても、ハッキングされたコードは暗号化キーにアクセスできなくなるため攻撃は成功しない。そのためコードの内容を自由に書き換え可能なマシンの所有者であっても、Enclaveの内容を覗いたり実行コードを変更することはできない。

またSGXハードウェアは特定のEnclaveが特定のソフトウェアディストリビューションを実行していることをリモートコンピュータに証明する機能を持つ。つまり、そのチップは”特定のハッシュを持つコードを実行していることをリモートパーティに保証する”ことができ、これがPayment Channelを構築する上で重要なファクターになっている。

SGXの詳細については、IntelのSGXの説明のホワイトペーパー参照↓

https://eprint.iacr.org/2016/086.pdf

TEEを利用するTeechanはSegwitが無くても双方向のPayment Channelを構築でき、１取引で複数回のメッセージ往復が必要なLNと違い、１つの取引は片方から１つのメッセージを送るだけで完了するというシンプルさがある。

Teechanの決済プロセス

ホワイトペーパーの４章にTeechanの具体的な決済プロセスが記述されている。

Teechanチャネルプロトコルは３つのフェーズからなる。

1. チャネルの確立
2. チャネル操作
3. チャネルの決済

↓で、これらの３つフェーズのそれぞれで交換されるメッセージを詳細に示している。

チャネルの確立

最初のフェーズでは、アリスとボブの間で双方向のPayment Channelを確立する。今までのPayment Channelと同様、セットアップと払い戻し用のトランザクションを使ってPayment Channelを確立する。アリスとボブは2-of-2のマルチシグにBitcoinをデポジットするセットアップトランザクションを構築する。
続いてセットアップトランザクションを入力にし、アリスとボブの資金を返却する払い戻しトランザクションを構築する。払い戻しトランザクションにはロックタイムが設けられていて、将来のある時点になると利用可能になる。必ずこのロックタイムの時間より前にチャネルを閉じる必要がある。

A1

最初にアリスとボブはそれぞれのEnclaveをセットし、セットアップ及び払い戻しトランザクションを構築する。この時必要になるのが

• それぞれの秘密鍵（図中のkBTC,AとkBTC,B）
• セットアップトランザクションにセットする未使用のトランザクション出力（UTXOAとUTXOB）
• セットアップトランザクションでデポジットする量（BTCAとBTCB）

A2

続いて、Enclave AとEnclave Bはセキュアな通信チャネルを確立し、remote attestationを通じてお互いを認証する。この時、各Enclaveは安全な乱数生成器を使って、非対称暗号の鍵ペアとランダムな秘密鍵を生成する。
アリスのEnclaveは生成した非対称公開鍵（KA）をSGXのQUOTEにバインドし、ボブに送信する。ボブは、KAで暗号化したデータはアリスのEnclaveによってのみ復号化され、Enclaveが必要なバイナリハッシュを持つEnclaveコードを実行していることを検証する。
同じことを逆方向でも行い、アリスのEnclaveもボブの公開鍵を取得する。相互検証が成功すると、Enclave AとEnclave Bははそれぞれ、KA、KBで暗号化されたデータが相手のEnclaveでのみ復号化できる状態になり、秘匿通信チャネルを確立したことになる。

A3

ボブのEnclaveはステップA1のボブのセットアップデータ（kBTC,B、UTXOB、BTCB）と一緒にランダムな秘密鍵IDBをアリスのEnclaveに提示する。アリスのEnclaveは内部的に署名付きのセットアップ及び払い戻しトランザクションを生成し、セットアップトランザクションのハッシュ（SetupHash）と払い戻しトランザクションをアリスに明かす。この時点ではアリスのEnclaveだけがセットアップトランザクションを知っている。

続いて、アリスのEnclaveはA1のアリスのセットアップデータ（kBTC,A、UTXOA、BTCA）と一緒にランダムな秘密鍵IDAをボブのEnclaveに提示する。ボブのEnclaveは内部的にセットアップトランザクションと払い戻しトランザクションを生成し、その両方をボブに明かす。ボブはセットアップトランザクションをBitcoinネットワークにブロードキャストし、チャネルを確立する。
アリスはブロックチェーン上にSetupHashと同じTXIDのトランザクションを見つけることでチャネルの確立を検知する。

以上のステップのハンドシェイクが終わると２つのEnclave間の安全な通信チャネルが確立する。

チャネル操作

Enclave AとEnclave Bの間でチャネルが確立すると、アリスとボブは資金の交換をスタートできる。この段階ではアリスもボブもBitcoinネットワークとの接続を維持する必要は無い。

B1

ボブに資金を送るため、アリスはボブに送りたい資金の量を指定して自分のEnclaveにローカルでリクエストを送る（A1）。

B2

Enclaveはオーナー（アリス）から支払いのリクエストを受信すると、送ろうとしている量が残高内かチェックする。問題なければ残高を更新し、支払いを承認するメッセージを作成する。このメッセージには、支払いを行うEnclaveのランダムな秘密鍵IDAと、更新された支払いカウンタ（初回は１）が含まれる。メッセージは非対称公開鍵KBで暗号化され、ボブに送られる。

B3

ボブはメッセージを受信するとそれをボブのEnclaveに送る。Enclaveがメッセージを受信すると、メッセージを復号化し、正しい秘密鍵かどうかとカウンタが以前提示されたものより１つ大きいものかチェックする。問題なければ残高とカウンタを更新し、ボブに残高を通知する。

B1〜B3のステップが１つのオフチェーン決済となり、決済の都度このステップを繰り返す。

チャネルの決済

Teechanプロトコルの最終段階はチャネルの決済である。このフェーズでは、Payment Channelが閉じられ、アリスとボブ間の最終的な残高を決済するトランザクションがBitcoinネットワークにブロードキャストされる。

C1

フェーズ２のいずれかの時点で、両者のいずれかがEnclaveに対して終了リクエストを送信する。

C2

Enclaveはオーナーから終了リクエストを受信すると、セットアップトランザクションでロックされた資金を現在の残高に応じてアリス、ボブそれぞれに送る決済トランザクションを生成し、kBTC,AとkBTC,Bを使って署名する。このトランザクションはホストに返されEnclave内のメモリデータは全て破棄され、実行を停止する。

C3

Enclaveから決済トランザクションを受け取ったオーナーはそれをBitcoinネットワークにブロードキャストして決済を完了する。

まとめ＆所感

• TeechanではTEEを信頼できるサードパーティとして利用していて、両者のEnclaveが信頼できるサードパーティとして機能する前提で、お互いの秘密鍵を相手のEnclaveに送っている。
• 両者のEnclaveが相手の秘密鍵も持っているので、オフチェーンでの決済は残高が合意できれば、Enclave内に相手の鍵と自分の鍵があるので、いつでもそれでトランザクションを作って署名できる（その操作を行うのは全てTEEデバイス）。
• トラストポイントを排除してきた既存のPayment Channelと違いEnclave等のTEEをを使ったトラストポイントを利用することで、作成するトランザクションはシンプルで、二者間のメッセージ交換の手間も省いている。
• LNだと両者間でシークレットから生成したハッシュの交換や鏡像となるトランザクションの交換など１つの取引で複数のメッセージ交換を必要とするのに比べ、１つの取引が１回のメッセージで完了するというのはシンプルで良い。
• 今までのマイクロペイメントチャネルだと、トラストポイントが無い形で自分のコインを保護できるが、そのためにはBitcoinネットワークを監視し相手が不正していないか検知する必要があったが、そういった監視をする必要が無くなる。
• TEEを使ったPayment Channelを構成する上で重要なのが、SGXのremote attestation機能だけど、これ現状でどれくらい使えるものなのか気になる。
• 故障なんかでenclaveのデータが読めなくなった場合ってどうなるのかね？
• あとEnclave間のリモート通信がどういうネットワークプロトコルで行われるのか気になる。

Federated Pegのアドレス導出スキーム

Blockstreamが公開しているSidechainのホワイトペーパーのAppendixにFederated Pegを行う際のP2SHアドレスの導出スキームが定義されている。このFederated Pegの仕組みは同じくBlockstreamが公開しているサイドチェーンの実装Elements Alphaでも利用されている。

techmedia-think.hatenablog.com

楕円曲線の準同型性を利用したこのアドレス導出のスキームの実装がどうなってるのか見てみる。

Federated Pegのコンセプト

現在のBitcoinのスクリプトにはSPV proof検証が行えるような機能は無いため、Bitcoinとサイドチェーンをペグする方法としてはFederated Pegを利用する方法がとられている。OP_SIDECHAINPROOFVERIFYのようなソフトフォークも考えられているみたいだけど、最近のSegwitのデプロイ状況を見てもわかるようにソフトフォークといっても合意を取るのは難しいので、ソフトフォーク無しでペグするのが現状は妥当なアプローチだと思う。

Federated Pegでは、信頼できる連合の職員にスクリプトを評価させることで、Bitcoinのスクリプトを拡張して実現しようとしていた機能を外部的に実装している。そのため連合の職員というトラスポイントが発生する。

ホワイトペーパーに記載されている例より

連合職員5人の内3人の署名が必要なケースを考えた場合、連合はsecp256k1の楕円曲線上の点（公開鍵）P1、P2、P3、P4、P5と、redeemscriptのテンプレート3 x x x x x 5 OP_CHECKMULTISIGを持ち、それらはサイドチェーンの全参加者に知られている。ユーザはfederated pegを使ってサイドチェーン上でコインを有効にするため、以下のスキームでクロスチェーンP2SHアドレスを導出する。

この導出スキームはBIP-32で使われているのと同じ準同型の手法をベースにしていて、第三者がリンク不可能なアドレスを生成でき、pay-to-contractトランザクションと同じ構成でもある。

アドレスを生成すると、そのアドレス宛てにコインを送る。コインを送ったユーザは連合の職員にnonceとscriptPubkey、SPV proofに提供すると（職員がBitcoinのブロックチェーン上の支払いを確認するのに必要）、送ったコインと同額のコインをサイドチェーン上で入手することができる。Bitcoinとサイドチェーン間のコインの転送は、標準のP2SHアドレスへ支払い、任意のScriptPubKeyに対して支払われるので、マルチシグアドレスをサポートしているBitcoinサービスであればすぐにでもfederated pegを利用してサイドチェーンへのコインの支払い、サイドチェーンからのコインの受取ができる。

federated pegのアプローチではチェーン間の移動の際に連合の職員というトラストポイントが発生するが、Bitcoinになんら変更を加える必要がないのと、サイドチェーンの利用を限られたユーザのみにしぼりたい場合も、連合の職員によってそういった制御をすることが可能になるといったメリットもある。

実装

実はこれをRubyで実装したものがbitcoin-rubyの一部にある↓

https://github.com/lian/bitcoin-ruby/blob/master/lib/bitcoin/contracthash.rb

ので、身近なRubyの実装でみていく。

アドレスの導出

コインをBitcoinからサイドチェーンに送る際のP2SHアドレスを計算する。

bitcoin-rubyでこれを実装しているのがBitcoin::ContractHash#generateで

引数に渡すのが↓の３つ

• redeem_script_template
  redeemscriptのテンプレートで↑のホワイトペーパーでは、3 x x x x x 5 OP_CHECKMULTISIGの部分。
• payee_address
  サイドチェーン上でコインを受け取るアドレス（ホワイトペーパーではScriptPubKey）
• nonce_hex
  128bitの乱数

この実装が↑のホワイトペーパーに記載されているアドレス導出スキームの実装にあたり、以下のプロセスでP2SHアドレスを生成している。

1. nonceとpayee_addressを組み合わせてdataを生成する
2. redeem_script_template（3 x x x x x 5 OP_CHECKMULTISIG）のマルチシグの各公開鍵＝楕円曲線上の点に対して、1で生成したdataを加算して新しい点＝公開鍵を生成する。
3. redeem_script_templateの各公開鍵の部分を、2で生成した新しい公開鍵に置き換えたP2SHスクリプトを生成する。
4. 3で生成したP2SHスクリプトから生成したP2SHアドレスとそのredeem_scriptとnonceを返す。

ユーザは生成されたP2SHアドレスにコインを送付する。

連合の職員の秘密鍵

ユーザーは職員にpayee_address（ホワイトペーパーではScriptPubKey）とnonceを渡す。連合の職員は渡されたpayee_addressとnonceを使って秘密鍵を入手する。

この処理を実装しているのがBitcoin::ContractHash#claimで、

引数に渡すのが↓の３つ

• private_key
  元々公開していた公開鍵の秘密鍵
• payee_address
  ユーザから渡された支払先のアドレス（ホワイトペーパーではScriptPubKey）
• nonce
  ユーザから渡されたnonce

↑でユーザがコインを送付したアドレスのロックを解除するための秘密鍵を↑のclaimメソッドで生成している。ユーザから渡されたpayee_addressとnonceから元々の公開鍵に加算されたdataを計算し、秘密鍵にそのdataを加算した新しい秘密鍵を生成している。

ポイントとなるのは、ユーザは公開されている職員の公開鍵に対してnonceとアドレスから生成したdataを加算した公開鍵を生成しており、職員はそれに対応する秘密鍵を同じく秘密鍵にdadtaを加算して入手してる点で楕円曲線の準同型性を利用している。ユーザがコインを送付するマルチシグは連合のマルチシグの各公開鍵にデータを加算したマルチシグであるため、このアドレスへの支払いがサイドチェーンへの支払いになっていることを第三者がリンクすることはできない。