diff --git a/src/Makefile.test.include b/src/Makefile.test.include
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -114,6 +114,7 @@
test/sigencoding_tests.cpp \
test/sighash_tests.cpp \
test/sighashtype_tests.cpp \
+ test/sigcheckcount_tests.cpp \
test/sigopcount_tests.cpp \
test/sigutil.h \
test/skiplist_tests.cpp \
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -82,9 +82,24 @@
using MutableTransactionSignatureChecker =
GenericTransactionSignatureChecker<CMutableTransaction>;
+/**
+ * Struct for holding cumulative results from executing a script or a sequence
+ * of scripts.
+ */
+struct ScriptExecutionMetrics {
+ int nSigChecks = 0;
+};
+
bool EvalScript(std::vector<std::vector<uint8_t>> &stack, const CScript &script,
uint32_t flags, const BaseSignatureChecker &checker,
- ScriptError *error = nullptr);
+ ScriptExecutionMetrics &metrics, ScriptError *error = nullptr);
+static inline bool EvalScript(std::vector<std::vector<uint8_t>> &stack,
+ const CScript &script, uint32_t flags,
+ const BaseSignatureChecker &checker,
+ ScriptError *error = nullptr) {
+ ScriptExecutionMetrics dummymetrics;
+ return EvalScript(stack, script, flags, checker, dummymetrics, error);
+}
bool VerifyScript(const CScript &scriptSig, const CScript &scriptPubKey,
uint32_t flags, const BaseSignatureChecker &checker,
ScriptError *serror = nullptr);
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -102,7 +102,7 @@
bool EvalScript(std::vector<valtype> &stack, const CScript &script,
uint32_t flags, const BaseSignatureChecker &checker,
- ScriptError *serror) {
+ ScriptExecutionMetrics &metrics, ScriptError *serror) {
static const CScriptNum bnZero(0);
static const CScriptNum bnOne(1);
static const valtype vchFalse(0);
@@ -885,6 +885,7 @@
fSuccess = checker.CheckSig(vchSig, vchPubKey,
scriptCode, flags);
+ metrics.nSigChecks += 1;
if (!fSuccess && (flags & SCRIPT_VERIFY_NULLFAIL)) {
return set_error(serror,
@@ -932,6 +933,7 @@
.Finalize(vchHash.data());
fSuccess = checker.VerifySignature(
vchSig, CPubKey(vchPubKey), uint256(vchHash));
+ metrics.nSigChecks += 1;
if (!fSuccess && (flags & SCRIPT_VERIFY_NULLFAIL)) {
return set_error(serror,
@@ -1086,6 +1088,10 @@
return set_error(serror,
ScriptError::SIG_NULLFAIL);
}
+
+ // this is guaranteed to execute exactly
+ // nSigsCount times (if not script error)
+ metrics.nSigChecks += 1;
}
if ((checkBits >> iKey) != 0) {
@@ -1157,6 +1163,14 @@
return set_error(serror,
ScriptError::SIG_NULLFAIL);
}
+
+ if (!areAllSignaturesNull) {
+ // This is not identical to the number of actual
+ // ECDSA verifies, but, it is an upper bound
+ // that can be easily determined without doing
+ // CPU-intensive checks.
+ metrics.nSigChecks += nKeysCount;
+ }
}
// Clean up stack of all arguments
diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt
--- a/src/test/CMakeLists.txt
+++ b/src/test/CMakeLists.txt
@@ -135,6 +135,7 @@
sigencoding_tests.cpp
sighash_tests.cpp
sighashtype_tests.cpp
+ sigcheckcount_tests.cpp
sigopcount_tests.cpp
skiplist_tests.cpp
streams_tests.cpp
diff --git a/src/test/sigcheckcount_tests.cpp b/src/test/sigcheckcount_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/sigcheckcount_tests.cpp
@@ -0,0 +1,308 @@
+// Copyright (c) 2019 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <policy/policy.h>
+#include <pubkey.h>
+#include <script/interpreter.h>
+#include <script/script_error.h>
+
+#include <test/test_bitcoin.h>
+
+#include <boost/test/unit_test.hpp>
+
+typedef std::vector<uint8_t> valtype;
+typedef std::vector<valtype> stacktype;
+
+BOOST_FIXTURE_TEST_SUITE(sigcheckcount_tests, BasicTestingSetup)
+
+/**
+ * Stand-in for proper signature check, in the absence of a proper
+ * transaction context. We will use a dummy signature checker with
+ * placeholder signatures / pubkeys that are correctly encoded.
+ */
+
+// First, correctly encoded ECDSA/Schnorr signatures in data/tx form.
+static const valtype sigecdsa = {0x30, 6, 2, 1, 0, 2, 1, 0};
+static const valtype txsigecdsa = {0x30, 6, 2, 1, 0, 2, 1, 0, 0x41};
+static const valtype sigschnorr(64);
+static const valtype txsigschnorr = {
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x41};
+
+// An example message to use (9 bytes).
+static const valtype msg = {0x73, 0x69, 0x67, 0x63, 0x68,
+ 0x65, 0x63, 0x6b, 0x73};
+
+// A valid pubkey
+static const valtype pub = {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
+// A special key that causes signature checks to return false (see below).
+static const valtype badpub = {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
+
+// Some small constants with descriptive names to make the purpose clear.
+static const valtype nullsig = {};
+static const valtype vfalse = {};
+static const valtype vtrue = {1};
+
+static class : public BaseSignatureChecker {
+ /**
+ * All null sigs verify false, and all checks using the magic 'bad pubkey'
+ * value verify false as well. Otherwise, checks verify as true.
+ */
+ bool VerifySignature(const std::vector<uint8_t> &vchSig,
+ const CPubKey &vchPubKey,
+ const uint256 &sighash) const final {
+ if (vchPubKey == CPubKey(badpub)) {
+ return false;
+ }
+ return !vchSig.empty();
+ }
+
+ bool CheckSig(const std::vector<uint8_t> &vchSigIn,
+ const std::vector<uint8_t> &vchPubKey,
+ const CScript &scriptCode, uint32_t flags) const final {
+ if (vchPubKey == badpub) {
+ return false;
+ }
+ return !vchSigIn.empty();
+ }
+} dummysigchecker;
+
+// construct a 'checkbits' stack element for OP_CHECKMULTISIG (set lower m bits
+// to 1, but make sure it's at least n bits long).
+static valtype makebits(int m, int n) {
+ valtype ret(0);
+ uint64_t bits = (uint64_t(1) << m) - 1;
+ for (; n > 0; n -= 8, bits >>= 8) {
+ ret.push_back(uint8_t(bits & 0xff));
+ }
+ return ret;
+}
+
+// Two lists of flag sets to pass to CheckEvalScript. The first is a wider
+// set of flags for long-supported opcodes. The latter list is restricted to
+// the case with schnorr multisig turned on.
+static const std::vector<uint32_t> allflags{
+ 0,
+ SCRIPT_VERIFY_NULLFAIL,
+ STANDARD_SCRIPT_VERIFY_FLAGS,
+ STANDARD_SCRIPT_VERIFY_FLAGS | SCRIPT_ENABLE_SCHNORR_MULTISIG,
+};
+
+static const std::vector<uint32_t> schnorrmultisigflags{
+ SCRIPT_VERIFY_NULLFAIL | SCRIPT_ENABLE_SCHNORR_MULTISIG,
+ STANDARD_SCRIPT_VERIFY_FLAGS | SCRIPT_ENABLE_SCHNORR_MULTISIG,
+};
+
+static void CheckEvalScript(const stacktype &original_stack,
+ const CScript &script,
+ const stacktype &expected_stack,
+ const int expected_sigchecks,
+ std::vector<uint32_t> flagset = allflags) {
+ for (uint32_t flags : flagset) {
+ ScriptError err = ScriptError::UNKNOWN;
+ stacktype stack{original_stack};
+ ScriptExecutionMetrics metrics;
+
+ bool r =
+ EvalScript(stack, script, flags, dummysigchecker, metrics, &err);
+ BOOST_CHECK(r);
+ BOOST_CHECK_EQUAL(err, ScriptError::OK);
+ BOOST_CHECK(stack == expected_stack);
+ BOOST_CHECK_EQUAL(metrics.nSigChecks, expected_sigchecks);
+ }
+}
+
+BOOST_AUTO_TEST_CASE(test_evalscript) {
+ CheckEvalScript({}, CScript(), {}, 0);
+
+ CheckEvalScript({nullsig}, CScript() << pub << OP_CHECKSIG, {vfalse}, 0);
+ CheckEvalScript({txsigecdsa}, CScript() << pub << OP_CHECKSIG, {vtrue}, 1);
+ CheckEvalScript({txsigschnorr}, CScript() << pub << OP_CHECKSIG, {vtrue},
+ 1);
+
+ CheckEvalScript({nullsig}, CScript() << msg << pub << OP_CHECKDATASIG,
+ {vfalse}, 0);
+ CheckEvalScript({sigecdsa}, CScript() << msg << pub << OP_CHECKDATASIG,
+ {vtrue}, 1);
+ CheckEvalScript({sigschnorr}, CScript() << msg << pub << OP_CHECKDATASIG,
+ {vtrue}, 1);
+
+ // Check all M-of-N OP_CHECKMULTISIGs combinations in all flavours.
+ for (int n = 0; n <= MAX_PUBKEYS_PER_MULTISIG; n++) {
+ for (int m = 0; m <= n; m++) {
+ // first, generate the spending script
+ CScript script;
+ script << m;
+ for (int i = 0; i < n; i++) {
+ script << pub;
+ }
+ script << n << OP_CHECKMULTISIG;
+
+ stacktype sigs;
+
+ // The all-null-signatures case with null dummy element counts as 0
+ // sigchecks, since all signatures are null.
+ sigs.assign(m + 1, {});
+ sigs[0] = {};
+ CheckEvalScript(sigs, script, {m ? vfalse : vtrue}, 0);
+
+ // The all-ECDSA-signatures case counts as N sigchecks, except when
+ // M=0 (so that it counts as 'all-null-signatures" instead).
+ sigs.assign(m + 1, txsigecdsa);
+ sigs[0] = {};
+ CheckEvalScript(sigs, script, {vtrue}, m ? n : 0);
+
+ // The all-Schnorr-signatures case counts as M sigchecks always.
+ // (Note that for M=N=0, this actually produces a null dummy which
+ // executes in legacy mode, but the behaviour is indistinguishable
+ // from schnorr mode.)
+ sigs.assign(m + 1, txsigschnorr);
+ sigs[0] = makebits(m, n);
+ CheckEvalScript(sigs, script, {vtrue}, m, schnorrmultisigflags);
+ }
+ }
+
+ // repeated checks of the same signature count each time
+ CheckEvalScript({txsigschnorr},
+ CScript() << pub << OP_2DUP << OP_CHECKSIGVERIFY
+ << OP_CHECKSIGVERIFY,
+ {}, 2);
+ CheckEvalScript({sigschnorr},
+ CScript() << msg << pub << OP_3DUP << OP_CHECKDATASIGVERIFY
+ << OP_CHECKDATASIGVERIFY,
+ {}, 2);
+
+ // unexecuted checks (behind if-branches) don't count.
+ {
+ CScript script = CScript() << OP_IF << pub << OP_CHECKSIG << OP_ELSE
+ << OP_DROP << OP_ENDIF;
+ CheckEvalScript({txsigecdsa, {1}}, script, {vtrue}, 1);
+ CheckEvalScript({txsigecdsa, {0}}, script, {}, 0);
+ }
+
+ // Without NULLFAIL, it is possible to have checksig/checkmultisig consume
+ // CPU using non-null signatures and then return false to the stack, without
+ // failing. Make sure that this historical case adds sigchecks, so that the
+ // CPU usage of possible malicious alternate histories (branching off before
+ // NULLFAIL activated in consensus) can be limited.
+ CheckEvalScript({txsigecdsa}, CScript() << badpub << OP_CHECKSIG, {vfalse},
+ 1, {SCRIPT_VERIFY_NONE});
+ CheckEvalScript({{}, txsigecdsa},
+ CScript() << 1 << badpub << badpub << badpub << badpub << 4
+ << OP_CHECKMULTISIG,
+ {vfalse}, 4, {SCRIPT_VERIFY_NONE});
+
+ // CHECKDATASIG and Schnorr need to be checked as well, since they have been
+ // made retroactively valid since forever and thus alternate histories could
+ // include them.
+ CheckEvalScript({sigecdsa}, CScript() << msg << badpub << OP_CHECKDATASIG,
+ {vfalse}, 1, {SCRIPT_VERIFY_NONE});
+ CheckEvalScript({txsigschnorr}, CScript() << badpub << OP_CHECKSIG,
+ {vfalse}, 1, {SCRIPT_VERIFY_NONE});
+ CheckEvalScript({sigschnorr}, CScript() << msg << badpub << OP_CHECKDATASIG,
+ {vfalse}, 1, {SCRIPT_VERIFY_NONE});
+
+ // CHECKMULTISIG with schnorr cannot return false, it just fails instead
+ // (hence, the sigchecks count is unimportant)
+ {
+ stacktype stack{{1}, txsigschnorr};
+ BOOST_CHECK(!EvalScript(
+ stack, CScript() << 1 << badpub << 1 << OP_CHECKMULTISIG,
+ SCRIPT_VERIFY_NONE, dummysigchecker));
+ }
+ {
+ stacktype stack{{1}, txsigschnorr};
+ BOOST_CHECK(!EvalScript(
+ stack, CScript() << 1 << badpub << 1 << OP_CHECKMULTISIG,
+ SCRIPT_ENABLE_SCHNORR_MULTISIG, dummysigchecker));
+ }
+
+ // EvalScript cumulatively increases the sigchecks count.
+ {
+ stacktype stack{txsigschnorr};
+ ScriptExecutionMetrics metrics;
+ metrics.nSigChecks = 12345;
+ bool r = EvalScript(stack, CScript() << pub << OP_CHECKSIG,
+ SCRIPT_VERIFY_NONE, dummysigchecker, metrics);
+ BOOST_CHECK(r);
+ BOOST_CHECK_EQUAL(metrics.nSigChecks, 12346);
+ }
+
+ // Other opcodes may be cryptographic and/or CPU intensive, but they do not
+ // add any additional sigchecks.
+ static_assert(
+ (MAX_SCRIPT_SIZE <= 10000 && MAX_OPS_PER_SCRIPT <= 201 &&
+ MAX_STACK_SIZE <= 1000 && MAX_SCRIPT_ELEMENT_SIZE <= 520),
+ "These can be made far worse with higher limits. Update accordingly.");
+
+ // Hashing operations on the largest stack element.
+ {
+ valtype bigblob(MAX_SCRIPT_ELEMENT_SIZE);
+ CheckEvalScript({},
+ CScript()
+ << bigblob << OP_RIPEMD160 << bigblob << OP_SHA1
+ << bigblob << OP_SHA256 << bigblob << OP_HASH160
+ << bigblob << OP_HASH256 << OP_CAT << OP_CAT
+ << OP_CAT << OP_CAT << OP_DROP,
+ {}, 0);
+ }
+
+ // OP_ROLL grinding, see
+ // https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/
+ {
+ stacktype bigstack;
+ bigstack.assign(999, {1});
+ CScript script;
+ for (int i = 0; i < 200; i++) {
+ script << 998 << OP_ROLL;
+ }
+ CheckEvalScript(bigstack, script, bigstack, 0);
+ }
+
+ // OP_IF grinding, see
+ // https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/
+ {
+ CScript script;
+ script << 0;
+ for (int i = 0; i < 100; i++) {
+ script << OP_IF;
+ }
+ for (int i = 0; i < 9798; i++) {
+ script << 0;
+ }
+ for (int i = 0; i < 100; i++) {
+ script << OP_ENDIF;
+ }
+ script << 1;
+ CheckEvalScript({}, script, {vtrue}, 0);
+ }
+
+ // OP_CODESEPARATOR grinding, see
+ // https://gist.github.com/markblundeberg/c2c88d25d5f34213830e48d459cbfb44
+ // (this is a simplified form)
+ {
+ stacktype stack;
+ stack.assign(94, txsigecdsa);
+ CScript script;
+ for (int i = 0; i < 94; i++) {
+ script << pub << OP_CHECKSIGVERIFY << OP_CODESEPARATOR;
+ }
+ // (remove last codesep)
+ script.pop_back();
+ // Push some garbage to lengthen the script.
+ valtype bigblob(520);
+ for (int i = 0; i < 6; i++) {
+ script << bigblob << bigblob << OP_2DROP;
+ }
+ script << 1;
+ BOOST_CHECK_EQUAL(script.size(), 9666);
+ CheckEvalScript(stack, script, {vtrue}, 94);
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END()