From 89fb241c54fc85befacfa3703d8e21bf3b8a76eb Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 17 Sep 2019 19:34:51 -0700 Subject: Benchmark script verification with 100 nested IFs --- src/bench/verify_script.cpp | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'src') diff --git a/src/bench/verify_script.cpp b/src/bench/verify_script.cpp index 1c025e29d3..5894f22b5b 100644 --- a/src/bench/verify_script.cpp +++ b/src/bench/verify_script.cpp @@ -71,4 +71,27 @@ static void VerifyScriptBench(benchmark::State& state) } } +static void VerifyNestedIfScript(benchmark::State& state) { + std::vector> stack; + CScript script; + for (int i = 0; i < 100; ++i) { + script << OP_1 << OP_IF; + } + for (int i = 0; i < 1000; ++i) { + script << OP_1; + } + for (int i = 0; i < 100; ++i) { + script << OP_ENDIF; + } + while (state.KeepRunning()) { + auto stack_copy = stack; + ScriptError error; + bool ret = EvalScript(stack_copy, script, 0, BaseSignatureChecker(), SigVersion::BASE, &error); + assert(ret); + } +} + + BENCHMARK(VerifyScriptBench, 6300); + +BENCHMARK(VerifyNestedIfScript, 100); -- cgit v1.2.3 From d0e8f4d5d8ddaccb37f98b7989fb944081e41ab8 Mon Sep 17 00:00:00 2001 From: Anthony Towns Date: Wed, 18 Sep 2019 15:49:29 +1000 Subject: [refactor] interpreter: define interface for vfExec Includes comments added by Pieter Wuille. --- src/script/interpreter.cpp | 30 +++++++++++++++++++++++++++--- 1 file changed, 27 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index 20fae2eebf..7a34c9c48d 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -278,6 +278,30 @@ int FindAndDelete(CScript& script, const CScript& b) return nFound; } +namespace { +/** A data type to abstract out the condition stack during script execution. + * + * Conceptually it acts like a vector of booleans, one for each level of nested + * IF/THEN/ELSE, indicating whether we're in the active or inactive branch of + * each. + * + * The elements on the stack cannot be observed individually; we only need to + * expose whether the stack is empty and whether or not any false values are + * present at all. To implement OP_ELSE, a toggle_top modifier is added, which + * flips the last value without returning it. + */ +class ConditionStack { +private: + std::vector m_flags; +public: + bool empty() { return m_flags.empty(); } + bool all_true() { return !std::count(m_flags.begin(), m_flags.end(), false); } + void push_back(bool f) { m_flags.push_back(f); } + void pop_back() { m_flags.pop_back(); } + void toggle_top() { m_flags.back() = !m_flags.back(); } +}; +} + bool EvalScript(std::vector >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror) { static const CScriptNum bnZero(0); @@ -293,7 +317,7 @@ bool EvalScript(std::vector >& stack, const CScript& CScript::const_iterator pbegincodehash = script.begin(); opcodetype opcode; valtype vchPushValue; - std::vector vfExec; + ConditionStack vfExec; std::vector altstack; set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR); if (script.size() > MAX_SCRIPT_SIZE) @@ -305,7 +329,7 @@ bool EvalScript(std::vector >& stack, const CScript& { while (pc < pend) { - bool fExec = !count(vfExec.begin(), vfExec.end(), false); + bool fExec = vfExec.all_true(); // // Read instruction @@ -494,7 +518,7 @@ bool EvalScript(std::vector >& stack, const CScript& { if (vfExec.empty()) return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL); - vfExec.back() = !vfExec.back(); + vfExec.toggle_top(); } break; -- cgit v1.2.3 From e6e622e5a0e22c2ac1b50b96af818e412d67ac54 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 4 Nov 2019 10:54:38 -0800 Subject: Implement O(1) OP_IF/NOTIF/ELSE/ENDIF logic This optimization was first suggested by Sergio Demian Lerner in https://bitslog.wordpress.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/. The implementation follows the suggested approach there, but with a slightly simpler representation. --- src/script/interpreter.cpp | 52 ++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 46 insertions(+), 6 deletions(-) (limited to 'src') diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index 7a34c9c48d..cd6ab0ee1b 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -289,16 +289,56 @@ namespace { * expose whether the stack is empty and whether or not any false values are * present at all. To implement OP_ELSE, a toggle_top modifier is added, which * flips the last value without returning it. + * + * This uses an optimized implementation that does not materialize the + * actual stack. Instead, it just stores the size of the would-be stack, + * and the position of the first false value in it. */ class ConditionStack { private: - std::vector m_flags; + //! A constant for m_first_false_pos to indicate there are no falses. + static constexpr uint32_t NO_FALSE = std::numeric_limits::max(); + + //! The size of the implied stack. + uint32_t m_stack_size = 0; + //! The position of the first false value on the implied stack, or NO_FALSE if all true. + uint32_t m_first_false_pos = NO_FALSE; + public: - bool empty() { return m_flags.empty(); } - bool all_true() { return !std::count(m_flags.begin(), m_flags.end(), false); } - void push_back(bool f) { m_flags.push_back(f); } - void pop_back() { m_flags.pop_back(); } - void toggle_top() { m_flags.back() = !m_flags.back(); } + bool empty() { return m_stack_size == 0; } + bool all_true() { return m_first_false_pos == NO_FALSE; } + void push_back(bool f) + { + if (m_first_false_pos == NO_FALSE && !f) { + // The stack consists of all true values, and a false is added. + // The first false value will appear at the current size. + m_first_false_pos = m_stack_size; + } + ++m_stack_size; + } + void pop_back() + { + assert(m_stack_size > 0); + --m_stack_size; + if (m_first_false_pos == m_stack_size) { + // When popping off the first false value, everything becomes true. + m_first_false_pos = NO_FALSE; + } + } + void toggle_top() + { + assert(m_stack_size > 0); + if (m_first_false_pos == NO_FALSE) { + // The current stack is all true values; the first false will be the top. + m_first_false_pos = m_stack_size - 1; + } else if (m_first_false_pos == m_stack_size - 1) { + // The top is the first false value; toggling it will make everything true. + m_first_false_pos = NO_FALSE; + } else { + // There is a false value, but not on top. No action is needed as toggling + // anything but the first false value is unobservable. + } + } }; } -- cgit v1.2.3