Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bitcoin Scriptの分岐処理の実装とオーバーヘッド

最近Bitcoin Coreにマージされた↓の改善について

github.com

Bitcoin Core PR Review Clubで取り上げられていたので↓、内容について見ておく。

bitcoincore.reviews

Bitcoin Scriptの分岐処理

Bitcoinはスタック型のスクリプト言語を使ってコントラクトを実行できるようになっている。スクリプトはスタックにプッシュされたデータ要素と、スタック要素を操作するためのopcodeで構成される。このopcodeの内、以下のopcodeを使用するとif文を使ってスクリプトの制御フローを分岐することができる。

  • OP_IF
  • OP_NOTIF
  • OP_ELSE
  • OP_ENDIF

例えばスクリプト実行中にOP_IFが現れると、その時のスタックの1番上の要素を評価して、OP_IF分岐を実行するかどうかが決まる。もし要素がtrueを表すものであればOP_IF分岐は実行されるが、falseを表す場合、OP_IF分岐は実行されず、その後出てくるOP_ELSE分岐の方が実行される。尚、これらの分岐は複数の階層にネスト可能だ。

インタプリタの実装

スクリプトの評価は、スタック上の要素を切り替えながらループ処理される。↑の分岐処理がBitcoin Coreでどのように実装されているかだが、これまでの実装では、bool値のvectorであるvfExecという変数で制御されてきた。

  • 実行中にOP_IFもしくはOP_NOTIFが検出されると、bool値がvector vfExecにプッシュされる。
  • OP_ELSEが検出されると、vectorの最上位bool値が反転する。
  • OP_ENDIFが検出されるとvectorの最上位bool値がポップされる。
  • ループ処理ではbool値が全てtrueの場合のみ(bool fExec = !count(vfExec.begin(), vfExec.end(), false);)、実行すべきブランチと判断して処理が継続する。

そのため、例えばOP_IFを検出して、結果がfalseの場合では、スクリプトは次のOP_ELSEまでジャンプするようなことはなく(Bitcoin Scriptにジャンプ処理はない)、OP_IF分岐の中に入って現在のvfExecの値を確認して処理をするかどうか判断し、falseであれば次のループ処理を継続する。OP_IFが実行されない分岐であって、その中にOP_CATなどの無効なopcodeが含まれていた場合、実行されないのに無効なopcodeがあるとSCRIPT_ERR_DISABLED_OPCODEエラーが出るはそのためだ。

問題点

↑の処理方法の問題点を指摘しているのがSergio Demian Lernerのブログ↓

bitslog.com

これまでの実装を悪用する以下のようなスクリプトを用意した場合、

0
OP_IF { 100 times }

0 { 9798 times }

OP_ENDIF { 100 times }
1

vector vfExecに100個の要素がプッシュされ、各要素が9799回スキャン(カウント)される。つまり合計979900回スキャンされる。ブロックを全てこのスクリプトで埋めた場合ブロックの評価に2.5秒かかるようになると。

最悪のケースではチェック処理の時間が二次的に増加していくことが懸念されるが、現状スクリプト内のopcodeの最大数は201という制限があるため、大きな問題はない。

Taproot導入による問題

ただ、今後Taprootの導入(正確にはTapscript)により問題が顕在化する可能性がある。

techmedia-think.hatenablog.com

Taprootで実行可能なTapscriptではopcodeの最大数201という制限が外れる。このため検証に時間がかかるブロックを作成するのに↑が悪用される可能性がある。

修正内容

↑のPRでは、vfExecをbool値のvectorではなく、整数のペアにすることでO(n)だったチェックをO(1)で出来るように修正している。

具体的には以下の2つのプロパティを持つConditionStackというクラスに置き換わる。

  • m_stack_size: 分岐スタックのレベル
  • m_first_false_pos: ↑のスタック中に最初にfalseが出る位置

これまではvector内にfalseが無いか全要素のチェックが必要だったのに対して、↑では、m_first_false_posの値をチェックするだけ(O(1))で済むようにしたと。具体的なコードは↓

https://github.com/bitcoin/bitcoin/blob/67dfd18f4401986063e22c79d4d7da61f15b5cd4/src/script/interpreter.cpp#L281-L343

TaprootやTapscriptでは細かい適用ルールが変わってるので、その影響を調査するのも結構大変だと思う。