message: Implement O(1) OP_IF/NOTIF/ELSE/ENDIF logic
  This optimization was first suggested by Sergio Demian Lerner in
  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.
  Committer's note: EvalScript call adapted to work with BCHU
  refactoring of the Script interpreter as a "virtual machine"
  encapsulated by a class
diff: @@ -271,18 +271,64 @@ 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<bool> m_flags;
  + //! A constant for m_first_false_pos to indicate there are no falses.
  + static constexpr uint32_t NO_FALSE = std::numeric_limits<uint32_t>::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.
  + }
  + }
  };
  }
  