Minimize vfExec counting in script handling #14245

jl2012 · 2018-09-17T18:46:36Z

@SergioDemianLerner described a potential attack vector by exploiting the way how vfExec is handled in script. Since the vfExec vector is scanned once for every opcode, a specially crafted script could scan up to 979K items, and it may take a couple seconds to validate a block packed with such scripts. Read more: https://bitslog.wordpress.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/

The article suggested an O(1) algorithm to fix the problem. I'm trying to fix in a different way. Although it is not the optimal solution, the 5-line patch is very easy to review, and it can reduce the worst case from 979k to about 5k items to be scanned, a 99.49% reduction.

To make review easier, I'll make inline comments

EDIT: a regular block full of CHECKSIG might also take seconds to validate, so this consensus code fix may not be necessary. But anyway, review and comments are welcomed.

jl2012 · 2018-09-17T18:47:37Z

src/script/interpreter.cpp

    opcodetype opcode;
    valtype vchPushValue;
    std::vector<bool> vfExec;
+    bool fExec = true;


By definition, the first opcode must be executed because vfExec is empty and without any false item. So fExec must be true at the beginning

jl2012 · 2018-09-17T18:49:39Z

src/script/interpreter.cpp

    {
        while (pc < pend)
        {
-            bool fExec = !count(vfExec.begin(), vfExec.end(), false);


value of fExec may change only if an IF, NOTIF, ELSE, or ENDIF is encountered. No other opcode may flip fExec. So we don't need to redo it for every opcode, just after IF, NOTIF, ELSE, or ENDIF

jl2012 · 2018-09-17T18:54:44Z

src/script/interpreter.cpp

                        if (opcode == OP_NOTIF)
                            fValue = !fValue;
                        popstack(stack);
+                        fExec = fValue;


in OP_IF, if fExec is true, the original vfExec must be by definition all true. Since fValue is added to the end of vfExec, the new fExec value must be same as fValue

If fExec is false, a false will be added to vfExec, and by definition fExec will remain false, so we don't need to do anything

jl2012 · 2018-09-17T18:59:34Z

src/script/interpreter.cpp

                    if (vfExec.empty())
                        return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
                    vfExec.back() = !vfExec.back();
+                    fExec = fExec ? false : !count(vfExec.begin(), vfExec.end(), false);


in OP_ELSE, if fExec is true, the original vfExec must be by definition all true. Since OP_ELSE will flip the last vfExec item, the resulting vfExec must have exactly one false at the end. So we know fExec must become false.

If fExec is false, there is at least one false in vfExec but we don't know where it is, so we have to count as usual (fExec will flip if and only if the original vfExec had exactly one false at the end)

std::count?

Could improve by using std::find since the actual count is not necessary?

jl2012 · 2018-09-17T19:02:31Z

src/script/interpreter.cpp

                    if (vfExec.empty())
                        return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
                    vfExec.pop_back();
+                    fExec = fExec ? true : !count(vfExec.begin(), vfExec.end(), false);


in OP_ENDIF, if fExec is true, the original vfExec must be by definition all true. Since OP_ENDIF will simply remove the last vfExec item, the resulting vfExec must not have any false. So we know fExec must remain true.

If fExec is false, there is at least one false in vfExec but we don't know where it is, so we have to count as usual (fExec will flip if and only if the original vfExec had exactly one false at the end)

practicalswift · 2018-09-21T08:19:14Z

src/script/interpreter.cpp

    opcodetype opcode;
    valtype vchPushValue;
    std::vector<bool> vfExec;
+    bool fExec = true;


2018-09-20 01:47:27 cppcheck(pr=14245): [src/script/interpreter.cpp:297]: (style) The scope of the variable 'fExec' can be reduced.

yes, but a few variables there, like nOpCount, can be reduced as well

DrahtBot · 2018-09-28T08:11:26Z

Coverage	Change (pull 14245)	Reference (master)
Lines	+0.0056 %	87.0361 %
Functions	+0.0618 %	84.1130 %
Branches	-0.0095 %	51.5451 %

DrahtBot · 2018-11-08T21:48:20Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#16902 ([POC] O(1) OP_IF/NOTIF/ELSE/ENDIF script implementation by sipa)
#10729 (Wrap EvalScript in a ScriptExecution class by luke-jr)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot · 2019-05-07T17:06:19Z

The last travis run for this pull request was 231 days ago and is thus outdated. To trigger a fresh travis build, this pull request should be closed and re-opened.

fanquake · 2019-09-18T05:10:17Z

This has been open for a year, and received no conceptual review / interest (other than nits). Closing as "Up for grabs".

sipa · 2019-09-18T06:22:18Z

Oh, I completely forgot about this PR's existence. #16902 is a slightly more advanced version of this.

fanquake · 2019-09-18T06:28:02Z

#16902 is a slightly more advanced version of this.

Great. I'll remove "Up for Grabs", and reviewers can head to #16902 instead.

e6e622e Implement O(1) OP_IF/NOTIF/ELSE/ENDIF logic (Pieter Wuille) d0e8f4d [refactor] interpreter: define interface for vfExec (Anthony Towns) 89fb241 Benchmark script verification with 100 nested IFs (Pieter Wuille) Pull request description: While investigating what mechanisms are possible to maximize the per-opcode verification cost of scripts, I noticed that the logic for determining whether a particular opcode is to be executed is O(n) in the nesting depth. This issue was also pointed out by Sergio Demian Lerner in https://bitslog.wordpress.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/, and this PR implements a variant of the O(1) algorithm suggested there. This is not a problem currently, because even with a nesting depth of 100 (the maximum possible right now due to the 201 ops limit), the slowdown caused by this on my machine is around 70 ns per opcode (or 0.25 s per block) at worst, far lower than what is possible with other opcodes. This PR mostly serves as a proof of concept that it's possible to avoid it, which may be relevant in discussions around increasing the opcode limits in future script versions. Without it, the execution time of scripts can grow quadratically with the nesting depth, which very quickly becomes unreasonable. This improves upon #14245 by completely removing the `vfExec` vector. ACKs for top commit: jnewbery: Code review ACK e6e622e MarcoFalke: ACK e6e622e 🐴 fjahr: ACK e6e622e ajtowns: ACK e6e622e laanwj: concept and code review ACK e6e622e jonatack: ACK e6e622e code review, build, benches, fuzzing Tree-SHA512: 1dcfac3411ff04773de461959298a177f951cb5f706caa2734073bcec62224d7cd103767cfeef85cd129813e70c14c74fa8f1e38e4da70ec38a0f615aab1f7f7

e6e622e Implement O(1) OP_IF/NOTIF/ELSE/ENDIF logic (Pieter Wuille) d0e8f4d [refactor] interpreter: define interface for vfExec (Anthony Towns) 89fb241 Benchmark script verification with 100 nested IFs (Pieter Wuille) Pull request description: While investigating what mechanisms are possible to maximize the per-opcode verification cost of scripts, I noticed that the logic for determining whether a particular opcode is to be executed is O(n) in the nesting depth. This issue was also pointed out by Sergio Demian Lerner in https://bitslog.wordpress.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/, and this PR implements a variant of the O(1) algorithm suggested there. This is not a problem currently, because even with a nesting depth of 100 (the maximum possible right now due to the 201 ops limit), the slowdown caused by this on my machine is around 70 ns per opcode (or 0.25 s per block) at worst, far lower than what is possible with other opcodes. This PR mostly serves as a proof of concept that it's possible to avoid it, which may be relevant in discussions around increasing the opcode limits in future script versions. Without it, the execution time of scripts can grow quadratically with the nesting depth, which very quickly becomes unreasonable. This improves upon bitcoin#14245 by completely removing the `vfExec` vector. ACKs for top commit: jnewbery: Code review ACK e6e622e MarcoFalke: ACK e6e622e 🐴 fjahr: ACK e6e622e ajtowns: ACK e6e622e laanwj: concept and code review ACK e6e622e jonatack: ACK e6e622e code review, build, benches, fuzzing Tree-SHA512: 1dcfac3411ff04773de461959298a177f951cb5f706caa2734073bcec62224d7cd103767cfeef85cd129813e70c14c74fa8f1e38e4da70ec38a0f615aab1f7f7

Minimize vfExec counting in script handling

f3155ea

jl2012 commented Sep 17, 2018

View reviewed changes

fanquake added the Consensus label Sep 18, 2018

practicalswift reviewed Sep 21, 2018

View reviewed changes

DrahtBot closed this May 7, 2019

DrahtBot reopened this May 7, 2019

fanquake added the Needs Conceptual Review label Jun 24, 2019

fanquake added the Up for grabs label Sep 18, 2019

fanquake closed this Sep 18, 2019

sipa mentioned this pull request Sep 18, 2019

O(1) OP_IF/NOTIF/ELSE/ENDIF script implementation #16902

Merged

fanquake removed the Up for grabs label Sep 18, 2019

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

Minimize vfExec counting in script handling #14245

Minimize vfExec counting in script handling #14245

Uh oh!

Conversation

jl2012 commented Sep 17, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jl2012 Sep 17, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jl2012 Sep 17, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jl2012 Sep 17, 2018

Choose a reason for hiding this comment

Uh oh!

jl2012 Sep 17, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

promag Oct 2, 2018

Choose a reason for hiding this comment

Uh oh!

promag Oct 2, 2018

Choose a reason for hiding this comment

Uh oh!

jl2012 Sep 17, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

practicalswift Sep 21, 2018

Choose a reason for hiding this comment

Uh oh!

jl2012 Sep 22, 2018

Choose a reason for hiding this comment

Uh oh!

DrahtBot commented Sep 28, 2018

Uh oh!

DrahtBot commented Nov 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

DrahtBot commented May 7, 2019

Uh oh!

fanquake commented Sep 18, 2019

Uh oh!

sipa commented Sep 18, 2019

Uh oh!

fanquake commented Sep 18, 2019

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

jl2012 commented Sep 17, 2018 •

edited

Loading

jl2012 Sep 17, 2018 •

edited

Loading

jl2012 Sep 17, 2018 •

edited

Loading

jl2012 Sep 17, 2018 •

edited

Loading

jl2012 Sep 17, 2018 •

edited

Loading

DrahtBot commented Nov 8, 2018 •

edited

Loading