bitcoinのSegWitの仕組み

この文章は、bitcoinのSegWitの仕組みについての調査まとめです。内容は[bitcoin coreのソースコード](https://github.com/bitcoin/bitcoin)に基づくものです。(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**](https://en.bitcoin.it/wiki/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`

これを実行すると、

1. scriptSigの公開鍵から、ハッシュ値を計算する
2. その算出ハッシュ値が、scriptPubKeyのハッシュ値と等しいか検証する
3. 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](https://en.bitcoin.it/wiki/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ソースでは、

- https://github.com/bitcoin/bitcoin/blob/master/src/primitives/transaction.h
- https://github.com/bitcoin/bitcoin/blob/master/src/primitives/transaction.cpp

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

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

SegWit提案の[BIP141](https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki)によると、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](https://en.bitcoin.it/wiki/Transaction_Malleabilit)という。bitcoinにおいては、以下の状況で存在している。

- 後ろで使っていたOpenSSLが仕様に正確でない署名形式もゆるめて受け入れていた
- [ECDSA](https://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9ADSA)では、署名が(r, s)なら、(r, -s mod N)も受け入れてしまう
- (そもそも)非公開鍵を持っている人には、同じ対象データへの正しい署名データをいくらでも作れてしまう

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

ちなみに、二番目のECDSAで-sでもただしい署名扱いになる、というのは、以下の手順で確認できる。まず、上のリンクのWikipediaに検証方法の手順において、sを-sに入れ替えると、つづくw、u1、u2も-w、-u1、-u2になって、求めた曲線上の点もマイナスになる。そして[楕円曲線暗号](https://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9A%E6%9A%97%E5%8F%B7)では、点p=(x,y)のときの点-pというのは(x,-y)のことである。しかし、署名検証の最後の手順では、このうちx側だけをrと比較するだけであるため、(r,-s)もまた正しい署名となりうることがわかる。

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

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