bitcoinのSegWitの仕組み #Bitcoin

この文章は、bitcoinのSegWitの仕組みについての調査まとめです。内容はbitcoin coreのソースコードに基づくものです。(blockでの扱いの話は含みません。)

基礎知識: bitcoinのtransaction

bitcoinにおいては、blockchainは知っているのに、transactionの話をいっさい知らない場合が多いので軽く言及する。blockchainは、transactionの順序付けを可能にする場をつくる仕組みであって、システムとしてその場でどういった活動をするかの意味付けはtransactionのほうにある。

bitcoinでは、walletの本質は公開鍵暗号での鍵ペアのことである。公開鍵暗号での署名検証システムとは、署名対象データに対して、非公開鍵を用いて署名データを作成し、他が公開鍵を用いて署名データを検証することで、非公開鍵を持つ当人がその署名対象データ(の意味内容)を承認している、ということを保証するものである。Aさんが、「Bへ100を送金」というデータに署名すれば、他の誰でもないAだけがAからBへの送金を行った、とみなすことができるようになる。

bitcoinの基本送金の仕組みは、「送金」情報として送金相手のwalletの公開鍵(のハッシュ値)を指定しておくことで、それを「使う」ことに対して正しい署名を行える非公開鍵を持っている相手を限定する、というものである。送金自体が値を転送するのではなく、額に対して錠前をとりつける施錠(lock)に例えられ、使うことは錠前を解錠(unlock)することに例えられる。

そして、bitcoinでの「使う」という状況は、新たな「送金のために使う」ことである。いわば錠前を付け替えているようなものである。つまり、bitcoinというのは、「前の送金を使って、新たな送金を作る」活動を皆が行いあっている世界である。

bitcoinのこの個々の「送金」にあたる情報がtransactionである。transactionは、前のtransactionを「使う」情報であるInput(txin)のリストと、「送金」を指定する情報であるOutput(txout)のリストで構成されるデータである。

txoutには金額と、送金相手の公開鍵のハッシュ値を中心とした本人証明方法が入った情報が入っており、後者をscriptPubKeyと呼ぶ。txinには前のtransaction(のtxout)の指定と、署名などその本人証明に必要な情報が入っており、後者をscriptSigと呼ぶ。

transactionの検証方法

この「送金で使う」関係に対する検証方法とは、scriptSigに指定された前のtransaction(のtxout)にあるscriptPubKeyを連結したスクリプトコードとして、FORTHに似たスタック型インタプリタで実行することで、「失敗しないで終わる」かによって検証するものである。スクリプトコードの何処かが間違っていれば実行はエラー終了するのでそのtransactionは不正なものとみなされ、blockには追加されない。

正しい署名検証関係にある txinのscriptSigとtxinで指定されたtransactionのscriptPubKeyの組は、以下の内容になっている:

(このtransactionの)scriptSig: <Aのこのtransactionへの署名> <この署名に使ったAの公開鍵>
(前のtransactionの)scriptPubkey: OP_DUP OP_HASH160 <Aの公開鍵のハッシュ値> OP_EQUALVERIFY OP_CHECKSIG

これを実行すると、

scriptSigの公開鍵から、ハッシュ値を計算する
その算出ハッシュ値が、scriptPubKeyのハッシュ値と等しいか検証する
scriptSigの公開鍵と署名で、このtransactionに対して署名検証をする

が実行される。もし当人でなかったり、transactionの内容が変更されていたりすれば、2か3で失敗して実行終了することになる。

transactionの署名とtransactionのID

まず、基本として、署名する対象のデータには、署名の結果として生成される「署名データ」を含めることはできない。

このためbitcoinではtransactionを署名する場合や署名検証する場合に、transactionから署名データ部分を空にしたデータを作って、その署名を含まないデータに対して署名したり検証したりする。

一方、txinで指定される、前のtransactionを指すためのID(txid)には、(署名データを含む)transaction全データを対象としたハッシュ値を用いている。

Transaction Malleabilityとは

transactionから署名対象のデータを作るとき、比較的複雑な処理をするのだが、そのために正しい署名のtransactionに対して、そのscriptSigの編集可能性が存在することになった。編集と言っても、署名を別人のものに入れ替えるようなことはできなくて、ただ冗長な命令を埋め込むようなことなので、伸展性(malleability)とよんでいる。

しかしこのレベルの変化でも、scriptSigが編集されうることによって、正しく検証できるtransactionのハッシュIDは変化しうることになる。これがtransaction malleability(のscriptSig Malleability)である。

実際、block内にあるトランザクションのハッシュIDではなく、自分で発行したtranscationのハッシュIDを基準に状態をチェックしていたシステムでは、これを攻撃手段として利用されたこともあった。

また、bitcoin上でマイクロペイメントなどの複雑なシステムを構成する場合、複数の関係するtransactionを(block追加前から)同時に扱う必要でてくる。こういった場合にtransaction IDがblockに乗ったときに変化してしまうと、できるシステムの可能性が制限されることになる。

SegWit化

この問題は、正しいtransactionのIDによるの関係がズレうる点に尽きる。そこで、transactionの中から署名関連データ(witness)を明示的に分離する構造に変更するのが、SegWit(Segregated Witness)という仕組みになる。

SegWitでのtransactionのハッシュIDについては、署名を含むものと含まないものの二種類が用意される。他transactionとの関係においてtxidとしてtxinなどのポインタで使われるのが署名を含まないハッシュ値で、一方block内のmerkle treeなどの検証情報で使われるのが署名を含むハッシュ値(wtxid)となるらしい。

bitcoinソースでは、

のCTransactionにはGetHash()とGetWitnessHash()とがあり、前者は署名を含まないハッシュ、後者は署名を含むハッシュ値を作るようだ。

bitcoinのインタプリタでのSegWit処理

SegWit提案のBIP141によると、witnessを使う送金スクリプトは、

witness: <signature> <pubkey>
scriptSig: (empty)
scriptPubKey: 0 <20byte-keyhash>

で命令が一切含まれない、見た目上はただスタックに積むだけでおわるコードとなっている。

これはbitcoinのインタプリタ自体が、記載されたコードだけを実行するだけのものではなく、コードやスタックの特定のパターンに反応して特別な処理を実行するようになっているせいである。つまり、bitcoinのインタプリタというのは、コードに書いて有る命令だけを実行する一般的なインタプリタとは毛色の違うものである。

詳しくは、

https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp

の1400行目あたりにあるVerifyScript()を見るとよい。

このコードパターン(scriptSigが空でscriptPubKeyの最初が0から15の間)で、VerifyWitnessProgram()が呼び出され、その中で、続くのが20バイトのデータのときは、従来の送金チェック用のscriptPubKeyのコードが組み立てられ(OP_DUPとかを書き込んでいる部分)、EvalScript()を呼ぶコードとなっている。

ここではwitnessの内容は、(コードではなく、)このEvalScript()呼び出しでの初期スタック状態として使われている。また、続くデータが32バイトハッシュの場合は、witnesswの内容をスクリプトコードとして実行するようになっている。

ちなみに、multi-sig等で展開されるredeemScriptなども同様のパターン反応での処理実行がソース内に埋め込まれているのであって、コード展開命令(eval)が入っているわけではない。(インタプリタのソース上では、スタックからとりだして展開したpubkey2でEvalScript()している)。

こういったパターンは、CScript::IsPayToScriptHash()などでのようにベタにパターンチェックされている。

https://github.com/bitcoin/bitcoin/blob/master/src/script/script.cpp

補足: Signature Malleabilityについて

正しく受け入れられる署名データ自体に複数の表現が存在しうることを、Signature Malleabilityという。bitcoinにおいては、以下の状況で存在している。

後ろで使っていたOpenSSLが仕様に正確でない署名形式もゆるめて受け入れていた
ECDSAでは、署名が(r, s)なら、(r, -s mod N)も受け入れてしまう
(そもそも)非公開鍵を持っている人には、同じ対象データへの正しい署名データをいくらでも作れてしまう

そして、暗号系やその実装において将来的なMalleabilityが発見されることがないとは言えない。とのこと。

ちなみに、二番目のECDSAで-sでもただしい署名扱いになる、というのは、以下の手順で確認できる。まず、上のリンクのWikipediaに検証方法の手順において、sを-sに入れ替えると、つづくw、u1、u2も-w、-u1、-u2になって、求めた曲線上の点もマイナスになる。そして楕円曲線暗号では、点p=(x,y)のときの点-pというのは(x,-y)のことである。しかし、署名検証の最後の手順では、このうちx側だけをrと比較するだけであるため、(r,-s)もまた正しい署名となりうることがわかる。

三番目の話は、署名データを作るときに乱数を使っているので、乱数値を変えて計算するだけで正しい署名データをたくさん生成できる。

このようにSignature Malleabilityのほうは避けられないので、ハッシュ値を参照用ID扱いするような仕組みを組み込むシステムを考えるのならば、SegWit同様に署名データはハッシュ対象に含めないほうが良いだろう。