Minimize vfExec counting in script handling #14245

1. 
   jl2012 commented at 6:46 pm on September 17, 2018: contributor

   @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.

2. Minimize vfExec counting in script handling f3155ea50c
3. in src/script/interpreter.cpp:297 in f3155ea50c

   293@@ -294,6 +294,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
   294     opcodetype opcode;
   295     valtype vchPushValue;
   296     std::vector<bool> vfExec;
   297+    bool fExec = true;
   

   ---

   ---

   

   jl2012 commented at 6:47 pm on September 17, 2018:

   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

   ---

   

   practicalswift commented at 8:19 am on September 21, 2018:

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

   ---

   

   jl2012 commented at 9:19 am on September 22, 2018:

   yes, but a few variables there, like nOpCount, can be reduced as well
4. in src/script/interpreter.cpp:308 in f3155ea50c

   305@@ -305,8 +306,6 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
   306     {
   307         while (pc < pend)
   308         {
   309-            bool fExec = !count(vfExec.begin(), vfExec.end(), false);
   

   ---

   ---

   

   jl2012 commented at 6:49 pm on September 17, 2018:

   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
5. in src/script/interpreter.cpp:487 in f3155ea50c

   483@@ -485,6 +484,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
   484                         if (opcode == OP_NOTIF)
   485                             fValue = !fValue;
   486                         popstack(stack);
   487+                        fExec = fValue;
   

   ---

   ---

   

   jl2012 commented at 6:54 pm on September 17, 2018:

   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

6. in src/script/interpreter.cpp:498 in f3155ea50c

   494@@ -495,6 +495,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
   495                     if (vfExec.empty())
   496                         return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
   497                     vfExec.back() = !vfExec.back();
   498+                    fExec = fExec ? false : !count(vfExec.begin(), vfExec.end(), false);
   

   ---

   ---

   

   jl2012 commented at 6:59 pm on September 17, 2018:

   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)

   ---

   

   promag commented at 10:35 am on October 2, 2018:

   std::count?

   ---

   

   promag commented at 10:39 am on October 2, 2018:

   Could improve by using std::find since the actual count is not necessary?
7. in src/script/interpreter.cpp:507 in f3155ea50c

   503@@ -503,6 +504,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
   504                     if (vfExec.empty())
   505                         return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
   506                     vfExec.pop_back();
   507+                    fExec = fExec ? true : !count(vfExec.begin(), vfExec.end(), false);
   

   ---

   ---

   

   jl2012 commented at 7:02 pm on September 17, 2018:

   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)

8. fanquake added the label Consensus on Sep 18, 2018
9. 
   DrahtBot commented at 8:11 am on September 28, 2018: member

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

10. 
    DrahtBot commented at 9:48 pm on November 8, 2018: member

    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.

11. DrahtBot closed this on May 7, 2019

    ---

12. 
    DrahtBot commented at 5:06 pm on May 7, 2019: member
13. DrahtBot reopened this on May 7, 2019

    ---

14. fanquake added the label Needs Conceptual Review on Jun 24, 2019
15. fanquake added the label Up for grabs on Sep 18, 2019
16. 
    fanquake commented at 5:10 am on September 18, 2019: member

    This has been open for a year, and received no conceptual review / interest (other than nits). Closing as “Up for grabs”.
17. fanquake closed this on Sep 18, 2019

    ---

18. 
    sipa commented at 6:22 am on September 18, 2019: member

    Oh, I completely forgot about this PR’s existence. #16902 is a slightly more advanced version of this.
19. fanquake removed the label Up for grabs on Sep 18, 2019
20. 
    fanquake commented at 6:28 am on September 18, 2019: member

    #16902 is a slightly more advanced version of this.

    Great. I’ll remove “Up for Grabs”, and reviewers can head to #16902 instead.

21. laanwj referenced this in commit 67dfd18f44 on Mar 14, 2020
22. sidhujag referenced this in commit 36b125ba68 on Mar 15, 2020
23. sidhujag referenced this in commit afa5aedab6 on Nov 10, 2020
24. DrahtBot locked this on Feb 15, 2022

Contributors
jl2012 practicalswift promag DrahtBot fanquake sipa

Labels
Consensus Needs Conceptual Review