Merge bitcoin/bitcoin#24860: Miniscript integration follow-ups

f3a50c9dfe645c548713e44e0eaf26ea9917a379 miniscript: rename IsSane and IsSaneSubexpression to prevent misuse (Antoine Poinsot)
c5fe5163dc31db939c44129f2ff8283b290a9330 miniscript: nit: don't return after assert(false) (Antoine Poinsot)
7bbaca9d8d355a17348a8d01e3e2521c5de466b0 miniscript: explicit the threshold size computation in multi() (Antoine Poinsot)
8323e4249db50d46ae4f43c1d8a50666549ae938 miniscript: add an OpCode typedef for readability (Antoine Poinsot)
7a549c6c59e6babbae76af008433426c6fa38fe2 miniscript: mark nodes with duplicate keys as insane (Antoine Poinsot)
8c0f8bf7bc3750fad648af1a548517a272114bca fuzz: add a Miniscript target for string representation roundtripping (Antoine Poinsot)
be34d5077b2fede7404de7706362f5858c443525 fuzz: rename and improve the Miniscript Script roundtrip target (Antoine Poinsot)
7eb70f0ac0a54adabc566e2b93bbf6b2beb54a79 miniscript: tiny doc fixups (Antoine Poinsot)
5cea85f12cba5dcfe3a298eddfa711f582adffac miniscript: split ValidSatisfactions from IsSane (Antoine Poinsot)
a0f064dc1474a048e236bfff12f4def3aa11daf3 miniscript: introduce a CheckTimeLocksMix helper (Antoine Poinsot)
ed45ee3882e69266d550b56ff69388e071f0ad1b miniscript: use optional instead of bool/outarg (Antoine Poinsot)
1ab8d89fd1bdb3c0f2a506b4a10df6c23ba21c48 miniscript: make equality operator non-recursive (Antoine Poinsot)
5922c662c08a061b3b3d5ac34a31f9f9d4640d47 scripted-diff: miniscript: rename 'nodetype' variables to 'fragment' (Antoine Poinsot)
c5f65db0f03b52bc4525acae944173829290ce6f miniscript: remove a workaround for a GCC 4.8 bug (Antoine Poinsot)

Pull request description:

  The Miniscript repository and the Miniscript integration PR here have been a moving target for the past months, and some final cleanups were done there that were not included here. I initially intended to add some small followup commits to #24148 but i think there are enough of them to be worth a followup PR on its own.

  Some parts of the code did not change since it was initially written in 2019, and the code could use some modernization. (Use std::optional instead of out args, remove old compiler workarounds).
  We refactored the helpers to be more meaningful, and also did some renaming. A new fuzz target was also added and both were merged in a single file. 2 more will be added in #24149 that will be contained in this file too.

  The only behaviour change in this PR is to rule out Miniscript with duplicate keys from sane Miniscripts. In a P2WSH context, signatures can be rebounded (Miniscript does not use CODESEPARATOR) and it's reasonable to assume that reusing keys across the Script drops the malleability guarantees.
  It was previously assumed such Miniscript would never exist in the first place since a compiler should never create them. We finally agreed that if one were to exist (say, written by hand or from a buggy compiler) it would be very confusing if an imported Miniscript descriptor (after #24148) with duplicate keys was deemed sane (ie, "safe to use") by Bitcoin Core. We now check for duplicate keys in the constructor.

  This is (still) joint work with Pieter Wuille. (Actually he entirely authored the cleanups and code modernization.)

ACKs for top commit:
  sipa:
    utACK f3a50c9dfe645c548713e44e0eaf26ea9917a379 (with the caveat that a lot of it is my own code)
  sanket1729:
    code review ACK f3a50c9dfe645c548713e44e0eaf26ea9917a379. Did not review the fuzz tests.

Tree-SHA512: c043325e4936fe25e8ece4266b46119e000c6745f88cea530fed1edf01c80f03ee6f9edc83b6e9d42ca01688d184bad16bfd967c5bb8037744e726993adf3deb

3 files changed, 194 insertions, 81 deletions

diff --git a/src/test/fuzz/miniscript.cpp b/src/test/fuzz/miniscript.cpp
new file mode 100644
index 0000000000..6be75322b4
--- /dev/null
+++ b/src/test/fuzz/miniscript.cpp
@@ -0,0 +1,167 @@
+// Copyright (c) 2021 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 <core_io.h>
+#include <hash.h>
+#include <key.h>
+#include <script/miniscript.h>
+#include <script/script.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+#include <util/strencodings.h>
+
+namespace {
+
+//! Some pre-computed data for more efficient string roundtrips.
+struct TestData {
+    typedef CPubKey Key;
+
+    // Precomputed public keys.
+    std::vector<Key> dummy_keys;
+    std::map<Key, int> dummy_key_idx_map;
+    std::map<CKeyID, Key> dummy_keys_map;
+
+    //! Set the precomputed data.
+    void Init() {
+        unsigned char keydata[32] = {1};
+        for (size_t i = 0; i < 256; i++) {
+            keydata[31] = i;
+            CKey privkey;
+            privkey.Set(keydata, keydata + 32, true);
+            const Key pubkey = privkey.GetPubKey();
+
+            dummy_keys.push_back(pubkey);
+            dummy_key_idx_map.emplace(pubkey, i);
+            dummy_keys_map.insert({pubkey.GetID(), pubkey});
+        }
+    }
+} TEST_DATA;
+
+/**
+ * Context to parse a Miniscript node to and from Script or text representation.
+ * Uses an integer (an index in the dummy keys array from the test data) as keys in order
+ * to focus on fuzzing the Miniscript nodes' test representation, not the key representation.
+ */
+struct ParserContext {
+    typedef CPubKey Key;
+
+    bool KeyCompare(const Key& a, const Key& b) const {
+        return a < b;
+    }
+
+    std::optional<std::string> ToString(const Key& key) const
+    {
+        auto it = TEST_DATA.dummy_key_idx_map.find(key);
+        if (it == TEST_DATA.dummy_key_idx_map.end()) return {};
+        uint8_t idx = it->second;
+        return HexStr(Span{&idx, 1});
+    }
+
+    template<typename I>
+    std::optional<Key> FromString(I first, I last) const {
+        if (last - first != 2) return {};
+        auto idx = ParseHex(std::string(first, last));
+        if (idx.size() != 1) return {};
+        return TEST_DATA.dummy_keys[idx[0]];
+    }
+
+    template<typename I>
+    std::optional<Key> FromPKBytes(I first, I last) const {
+        Key key;
+        key.Set(first, last);
+        if (!key.IsValid()) return {};
+        return key;
+    }
+
+    template<typename I>
+    std::optional<Key> FromPKHBytes(I first, I last) const {
+        assert(last - first == 20);
+        CKeyID keyid;
+        std::copy(first, last, keyid.begin());
+        const auto it = TEST_DATA.dummy_keys_map.find(keyid);
+        if (it == TEST_DATA.dummy_keys_map.end()) return {};
+        return it->second;
+    }
+} PARSER_CTX;
+
+//! Context that implements naive conversion from/to script only, for roundtrip testing.
+struct ScriptParserContext {
+    //! For Script roundtrip we never need the key from a key hash.
+    struct Key {
+        bool is_hash;
+        std::vector<unsigned char> data;
+    };
+
+    bool KeyCompare(const Key& a, const Key& b) const {
+        return a.data < b.data;
+    }
+
+    const std::vector<unsigned char>& ToPKBytes(const Key& key) const
+    {
+        assert(!key.is_hash);
+        return key.data;
+    }
+
+    const std::vector<unsigned char> ToPKHBytes(const Key& key) const
+    {
+        if (key.is_hash) return key.data;
+        const auto h = Hash160(key.data);
+        return {h.begin(), h.end()};
+    }
+
+    template<typename I>
+    std::optional<Key> FromPKBytes(I first, I last) const
+    {
+        Key key;
+        key.data.assign(first, last);
+        key.is_hash = false;
+        return key;
+    }
+
+    template<typename I>
+    std::optional<Key> FromPKHBytes(I first, I last) const
+    {
+        Key key;
+        key.data.assign(first, last);
+        key.is_hash = true;
+        return key;
+    }
+} SCRIPT_PARSER_CONTEXT;
+
+} // namespace
+
+void FuzzInit()
+{
+    ECC_Start();
+    TEST_DATA.Init();
+}
+
+/* Fuzz tests that test parsing from a string, and roundtripping via string. */
+FUZZ_TARGET_INIT(miniscript_string, FuzzInit)
+{
+    FuzzedDataProvider provider(buffer.data(), buffer.size());
+    auto str = provider.ConsumeRemainingBytesAsString();
+    auto parsed = miniscript::FromString(str, PARSER_CTX);
+    if (!parsed) return;
+
+    const auto str2 = parsed->ToString(PARSER_CTX);
+    assert(str2);
+    auto parsed2 = miniscript::FromString(*str2, PARSER_CTX);
+    assert(parsed2);
+    assert(*parsed == *parsed2);
+}
+
+/* Fuzz tests that test parsing from a script, and roundtripping via script. */
+FUZZ_TARGET(miniscript_script)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    const std::optional<CScript> script = ConsumeDeserializable<CScript>(fuzzed_data_provider);
+    if (!script) return;
+
+    const auto ms = miniscript::FromScript(*script, SCRIPT_PARSER_CONTEXT);
+    if (!ms) return;
+
+    assert(ms->ToScript(SCRIPT_PARSER_CONTEXT) == *script);
+}
diff --git a/src/test/fuzz/miniscript_decode.cpp b/src/test/fuzz/miniscript_decode.cpp
deleted file mode 100644
index 4cc0a1be8f..0000000000
--- a/src/test/fuzz/miniscript_decode.cpp
+++ /dev/null
@@ -1,72 +0,0 @@
-// Copyright (c) 2022 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 <core_io.h>
-#include <hash.h>
-#include <key.h>
-#include <script/miniscript.h>
-#include <script/script.h>
-#include <span.h>
-#include <test/fuzz/FuzzedDataProvider.h>
-#include <test/fuzz/fuzz.h>
-#include <test/fuzz/util.h>
-#include <util/strencodings.h>
-
-#include <optional>
-
-using miniscript::operator""_mst;
-
-
-struct Converter {
-    typedef CPubKey Key;
-
-    bool ToString(const Key& key, std::string& ret) const {
-        ret = HexStr(key);
-        return true;
-    }
-    const std::vector<unsigned char> ToPKBytes(const Key& key) const {
-        return {key.begin(), key.end()};
-    }
-    const std::vector<unsigned char> ToPKHBytes(const Key& key) const {
-        const auto h = Hash160(key);
-        return {h.begin(), h.end()};
-    }
-
-    template<typename I>
-    bool FromString(I first, I last, Key& key) const {
-        const auto bytes = ParseHex(std::string(first, last));
-        key.Set(bytes.begin(), bytes.end());
-        return key.IsValid();
-    }
-    template<typename I>
-    bool FromPKBytes(I first, I last, CPubKey& key) const {
-        key.Set(first, last);
-        return key.IsValid();
-    }
-    template<typename I>
-    bool FromPKHBytes(I first, I last, CPubKey& key) const {
-        assert(last - first == 20);
-        return false;
-    }
-};
-
-const Converter CONVERTER;
-
-FUZZ_TARGET(miniscript_decode)
-{
-    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
-    const std::optional<CScript> script = ConsumeDeserializable<CScript>(fuzzed_data_provider);
-    if (!script) return;
-
-    const auto ms = miniscript::FromScript(*script, CONVERTER);
-    if (!ms) return;
-
-    // We can roundtrip it to its string representation.
-    std::string ms_str;
-    assert(ms->ToString(CONVERTER, ms_str));
-    assert(*miniscript::FromString(ms_str, CONVERTER) == *ms);
-    // The Script representation must roundtrip since we parsed it this way the first time.
-    const CScript ms_script = ms->ToScript(CONVERTER);
-    assert(ms_script == *script);
-}
diff --git a/src/test/miniscript_tests.cpp b/src/test/miniscript_tests.cpp
index 930582ea24..3877fea907 100644
--- a/src/test/miniscript_tests.cpp
+++ b/src/test/miniscript_tests.cpp
@@ -71,6 +71,10 @@ std::unique_ptr<const TestData> g_testdata;
 struct KeyConverter {
     typedef CPubKey Key;
 
+    bool KeyCompare(const Key& a, const Key& b) const {
+        return a < b;
+    }
+
     //! Convert a public key to bytes.
     std::vector<unsigned char> ToPKBytes(const CPubKey& key) const { return {key.begin(), key.end()}; }
 
@@ -84,27 +88,28 @@ struct KeyConverter {
 
     //! Parse a public key from a range of hex characters.
     template<typename I>
-    bool FromString(I first, I last, CPubKey& key) const {
+    std::optional<Key> FromString(I first, I last) const {
         auto bytes = ParseHex(std::string(first, last));
-        key.Set(bytes.begin(), bytes.end());
-        return key.IsValid();
+        Key key{bytes.begin(), bytes.end()};
+        if (key.IsValid()) return key;
+        return {};
     }
 
     template<typename I>
-    bool FromPKBytes(I first, I last, CPubKey& key) const {
-        key.Set(first, last);
-        return key.IsValid();
+    std::optional<Key> FromPKBytes(I first, I last) const {
+        Key key{first, last};
+        if (key.IsValid()) return key;
+        return {};
     }
 
     template<typename I>
-    bool FromPKHBytes(I first, I last, CPubKey& key) const {
+    std::optional<Key> FromPKHBytes(I first, I last) const {
         assert(last - first == 20);
         CKeyID keyid;
         std::copy(first, last, keyid.begin());
         auto it = g_testdata->pkmap.find(keyid);
         assert(it != g_testdata->pkmap.end());
-        key = it->second;
-        return true;
+        return it->second;
     }
 };
 
@@ -272,6 +277,19 @@ BOOST_AUTO_TEST_CASE(fixed_tests)
     // its subs to all be 'u' (taken from https://github.com/rust-bitcoin/rust-miniscript/discussions/341).
     const auto ms_minimalif = miniscript::FromString("thresh(3,c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),sc:pk_k(03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556),sc:pk_k(0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798),sdv:older(32))", CONVERTER);
     BOOST_CHECK(!ms_minimalif);
+    // A Miniscript with duplicate keys is not sane
+    const auto ms_dup1 = miniscript::FromString("and_v(v:pk(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),pk(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65))", CONVERTER);
+    BOOST_CHECK(ms_dup1);
+    BOOST_CHECK(!ms_dup1->IsSane() && !ms_dup1->CheckDuplicateKey());
+    // Same with a disjunction, and different key nodes (pk and pkh)
+    const auto ms_dup2 = miniscript::FromString("or_b(c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),ac:pk_h(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65))", CONVERTER);
+    BOOST_CHECK(ms_dup2 && !ms_dup2->IsSane() && !ms_dup2->CheckDuplicateKey());
+    // Same when the duplicates are leaves or a larger tree
+    const auto ms_dup3 = miniscript::FromString("or_i(and_b(pk(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),s:pk(03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556)),and_b(older(1),s:pk(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65)))", CONVERTER);
+    BOOST_CHECK(ms_dup3 && !ms_dup3->IsSane() && !ms_dup3->CheckDuplicateKey());
+    // Same when the duplicates are on different levels in the tree
+    const auto ms_dup4 = miniscript::FromString("thresh(2,pkh(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),s:pk(03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556),a:and_b(dv:older(1),s:pk(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65)))", CONVERTER);
+    BOOST_CHECK(ms_dup4 && !ms_dup4->IsSane() && !ms_dup4->CheckDuplicateKey());
 
     // Timelock tests
     Test("after(100)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // only heightlock