tests: dumping and minimizing of script assets data

This adds a --dumptests flag to the feature_taproot.py test, to dump all its
generated test cases to files, in a format compatible with the
script_assets_test unit test. A fuzzer for said format is added as well, whose
primary purpose is coverage-based minimization of those dumps.

3 files changed, 210 insertions, 0 deletions

diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 06dde87ddd..28608715b4 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -129,6 +129,7 @@ FUZZ_TARGETS = \
   test/fuzz/script_deserialize \
   test/fuzz/script_flags \
   test/fuzz/script_interpreter \
+  test/fuzz/script_assets_test_minimizer \
   test/fuzz/script_ops \
   test/fuzz/script_sigcache \
   test/fuzz/script_sign \
@@ -1082,6 +1083,12 @@ test_fuzz_script_interpreter_LDADD = $(FUZZ_SUITE_LD_COMMON)
 test_fuzz_script_interpreter_LDFLAGS = $(FUZZ_SUITE_LDFLAGS_COMMON)
 test_fuzz_script_interpreter_SOURCES = test/fuzz/script_interpreter.cpp
 
+test_fuzz_script_assets_test_minimizer_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_script_assets_test_minimizer_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_script_assets_test_minimizer_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_script_assets_test_minimizer_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_script_assets_test_minimizer_SOURCES = test/fuzz/script_assets_test_minimizer.cpp
+
 test_fuzz_script_ops_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
 test_fuzz_script_ops_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 test_fuzz_script_ops_LDADD = $(FUZZ_SUITE_LD_COMMON)
diff --git a/src/test/fuzz/script_assets_test_minimizer.cpp b/src/test/fuzz/script_assets_test_minimizer.cpp
new file mode 100644
index 0000000000..d20fa43d68
--- /dev/null
+++ b/src/test/fuzz/script_assets_test_minimizer.cpp
@@ -0,0 +1,200 @@
+// Copyright (c) 2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <test/fuzz/fuzz.h>
+
+#include <primitives/transaction.h>
+#include <pubkey.h>
+#include <script/interpreter.h>
+#include <serialize.h>
+#include <streams.h>
+#include <univalue.h>
+#include <util/strencodings.h>
+
+#include <boost/algorithm/string.hpp>
+#include <cstdint>
+#include <string>
+#include <vector>
+
+// This fuzz "test" can be used to minimize test cases for script_assets_test in
+// src/test/script_tests.cpp. While it written as a fuzz test, and can be used as such,
+// fuzzing the inputs is unlikely to construct useful test cases.
+//
+// Instead, it is primarily intended to be run on a test set that was generated
+// externally, for example using test/functional/feature_taproot.py's --dumptests mode.
+// The minimized set can then be concatenated together, surrounded by '[' and ']',
+// and used as the script_assets_test.json input to the script_assets_test unit test:
+//
+// (normal build)
+// $ mkdir dump
+// $ for N in $(seq 1 10); do TEST_DUMP_DIR=dump test/functional/feature_taproot --dumptests; done
+// $ ...
+//
+// (fuzz test build)
+// $ mkdir dump-min
+// $ ./src/test/fuzz/script_assets_test_minimizer -merge=1 dump-min/ dump/
+// $ (echo -en '[\n'; cat dump-min/* | head -c -2; echo -en '\n]') >script_assets_test.json
+
+namespace {
+
+std::vector<unsigned char> CheckedParseHex(const std::string& str)
+{
+    if (str.size() && !IsHex(str)) throw std::runtime_error("Non-hex input '" + str + "'");
+    return ParseHex(str);
+}
+
+CScript ScriptFromHex(const std::string& str)
+{
+    std::vector<unsigned char> data = CheckedParseHex(str);
+    return CScript(data.begin(), data.end());
+}
+
+CMutableTransaction TxFromHex(const std::string& str)
+{
+    CMutableTransaction tx;
+    try {
+        VectorReader(SER_DISK, SERIALIZE_TRANSACTION_NO_WITNESS, CheckedParseHex(str), 0) >> tx;
+    } catch (const std::ios_base::failure&) {
+        throw std::runtime_error("Tx deserialization failure");
+    }
+    return tx;
+}
+
+std::vector<CTxOut> TxOutsFromJSON(const UniValue& univalue)
+{
+    if (!univalue.isArray()) throw std::runtime_error("Prevouts must be array");
+    std::vector<CTxOut> prevouts;
+    for (size_t i = 0; i < univalue.size(); ++i) {
+        CTxOut txout;
+        try {
+            VectorReader(SER_DISK, 0, CheckedParseHex(univalue[i].get_str()), 0) >> txout;
+        } catch (const std::ios_base::failure&) {
+            throw std::runtime_error("Prevout invalid format");
+        }
+        prevouts.push_back(std::move(txout));
+    }
+    return prevouts;
+}
+
+CScriptWitness ScriptWitnessFromJSON(const UniValue& univalue)
+{
+    if (!univalue.isArray()) throw std::runtime_error("Script witness is not array");
+    CScriptWitness scriptwitness;
+    for (size_t i = 0; i < univalue.size(); ++i) {
+        auto bytes = CheckedParseHex(univalue[i].get_str());
+        scriptwitness.stack.push_back(std::move(bytes));
+    }
+    return scriptwitness;
+}
+
+const std::map<std::string, unsigned int> FLAG_NAMES = {
+    {std::string("P2SH"), (unsigned int)SCRIPT_VERIFY_P2SH},
+    {std::string("DERSIG"), (unsigned int)SCRIPT_VERIFY_DERSIG},
+    {std::string("NULLDUMMY"), (unsigned int)SCRIPT_VERIFY_NULLDUMMY},
+    {std::string("CHECKLOCKTIMEVERIFY"), (unsigned int)SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY},
+    {std::string("CHECKSEQUENCEVERIFY"), (unsigned int)SCRIPT_VERIFY_CHECKSEQUENCEVERIFY},
+    {std::string("WITNESS"), (unsigned int)SCRIPT_VERIFY_WITNESS},
+    {std::string("TAPROOT"), (unsigned int)SCRIPT_VERIFY_TAPROOT},
+};
+
+std::vector<unsigned int> AllFlags()
+{
+    std::vector<unsigned int> ret;
+
+    for (unsigned int i = 0; i < 128; ++i) {
+        unsigned int flag = 0;
+        if (i & 1) flag |= SCRIPT_VERIFY_P2SH;
+        if (i & 2) flag |= SCRIPT_VERIFY_DERSIG;
+        if (i & 4) flag |= SCRIPT_VERIFY_NULLDUMMY;
+        if (i & 8) flag |= SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY;
+        if (i & 16) flag |= SCRIPT_VERIFY_CHECKSEQUENCEVERIFY;
+        if (i & 32) flag |= SCRIPT_VERIFY_WITNESS;
+        if (i & 64) flag |= SCRIPT_VERIFY_TAPROOT;
+
+        // SCRIPT_VERIFY_WITNESS requires SCRIPT_VERIFY_P2SH
+        if (flag & SCRIPT_VERIFY_WITNESS && !(flag & SCRIPT_VERIFY_P2SH)) continue;
+        // SCRIPT_VERIFY_TAPROOT requires SCRIPT_VERIFY_WITNESS
+        if (flag & SCRIPT_VERIFY_TAPROOT && !(flag & SCRIPT_VERIFY_WITNESS)) continue;
+
+        ret.push_back(flag);
+    }
+
+    return ret;
+}
+
+const std::vector<unsigned int> ALL_FLAGS = AllFlags();
+
+unsigned int ParseScriptFlags(const std::string& str)
+{
+    if (str.empty()) return 0;
+
+    unsigned int flags = 0;
+    std::vector<std::string> words;
+    boost::algorithm::split(words, str, boost::algorithm::is_any_of(","));
+
+    for (const std::string& word : words)
+    {
+        auto it = FLAG_NAMES.find(word);
+        if (it == FLAG_NAMES.end()) throw std::runtime_error("Unknown verification flag " + word);
+        flags |= it->second;
+    }
+
+    return flags;
+}
+
+void Test(const std::string& str)
+{
+    UniValue test;
+    if (!test.read(str) || !test.isObject()) throw std::runtime_error("Non-object test input");
+
+    CMutableTransaction tx = TxFromHex(test["tx"].get_str());
+    const std::vector<CTxOut> prevouts = TxOutsFromJSON(test["prevouts"]);
+    if (prevouts.size() != tx.vin.size()) throw std::runtime_error("Incorrect number of prevouts");
+    size_t idx = test["index"].get_int64();
+    if (idx >= tx.vin.size()) throw std::runtime_error("Invalid index");
+    unsigned int test_flags = ParseScriptFlags(test["flags"].get_str());
+    bool final = test.exists("final") && test["final"].get_bool();
+
+    if (test.exists("success")) {
+        tx.vin[idx].scriptSig = ScriptFromHex(test["success"]["scriptSig"].get_str());
+        tx.vin[idx].scriptWitness = ScriptWitnessFromJSON(test["success"]["witness"]);
+        PrecomputedTransactionData txdata;
+        txdata.Init(tx, std::vector<CTxOut>(prevouts));
+        MutableTransactionSignatureChecker txcheck(&tx, idx, prevouts[idx].nValue, txdata);
+        for (const auto flags : ALL_FLAGS) {
+            // "final": true tests are valid for all flags. Others are only valid with flags that are
+            // a subset of test_flags.
+            if (final || ((flags & test_flags) == flags)) {
+                (void)VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr);
+            }
+        }
+    }
+
+    if (test.exists("failure")) {
+        tx.vin[idx].scriptSig = ScriptFromHex(test["failure"]["scriptSig"].get_str());
+        tx.vin[idx].scriptWitness = ScriptWitnessFromJSON(test["failure"]["witness"]);
+        PrecomputedTransactionData txdata;
+        txdata.Init(tx, std::vector<CTxOut>(prevouts));
+        MutableTransactionSignatureChecker txcheck(&tx, idx, prevouts[idx].nValue, txdata);
+        for (const auto flags : ALL_FLAGS) {
+            // If a test is supposed to fail with test_flags, it should also fail with any superset thereof.
+            if ((flags & test_flags) == test_flags) {
+                (void)VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr);
+            }
+        }
+    }
+}
+
+ECCVerifyHandle handle;
+
+}
+
+void test_one_input(const std::vector<uint8_t>& buffer)
+{
+    if (buffer.size() < 2 || buffer.back() != '\n' || buffer[buffer.size() - 2] != ',') return;
+    const std::string str((const char*)buffer.data(), buffer.size() - 2);
+    try {
+        Test(str);
+    } catch (const std::runtime_error&) {}
+}
diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp
index 3132f440af..a2efd8ac07 100644
--- a/src/test/script_tests.cpp
+++ b/src/test/script_tests.cpp
@@ -1715,6 +1715,9 @@ static void AssetTest(const UniValue& test)
 
 BOOST_AUTO_TEST_CASE(script_assets_test)
 {
+    // See src/test/fuzz/script_assets_test_minimizer.cpp for information on how to generate
+    // the script_assets_test.json file used by this test.
+
     const char* dir = std::getenv("DIR_UNIT_TEST_DATA");
     BOOST_WARN_MESSAGE(dir != nullptr, "Variable DIR_UNIT_TEST_DATA unset, skipping script_assets_test");
     if (dir == nullptr) return;