最近Bitcoin Coreにマージされた↓の改善について
Bitcoin Core PR Review Clubで取り上げられていたので↓、内容について見ておく。
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値がvectorvfExec
にプッシュされる。 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のブログ↓
これまでの実装を悪用する以下のようなスクリプトを用意した場合、
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))で済むようにしたと。具体的なコードは↓
TaprootやTapscriptでは細かい適用ルールが変わってるので、その影響を調査するのも結構大変だと思う。