diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/script/miniscript.cpp | 70 | ||||
| -rw-r--r-- | src/script/miniscript.h | 298 | ||||
| -rw-r--r-- | src/test/miniscript_tests.cpp | 232 |
3 files changed, 598 insertions, 2 deletions
diff --git a/src/script/miniscript.cpp b/src/script/miniscript.cpp index cb4d4cb783..45aebe909a 100644 --- a/src/script/miniscript.cpp +++ b/src/script/miniscript.cpp @@ -279,6 +279,76 @@ size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_ assert(false); } +InputStack& InputStack::SetAvailable(Availability avail) { + available = avail; + if (avail == Availability::NO) { + stack.clear(); + size = std::numeric_limits<size_t>::max(); + has_sig = false; + malleable = false; + non_canon = false; + } + return *this; +} + +InputStack& InputStack::SetWithSig() { + has_sig = true; + return *this; +} + +InputStack& InputStack::SetNonCanon() { + non_canon = true; + return *this; +} + +InputStack& InputStack::SetMalleable(bool x) { + malleable = x; + return *this; +} + +InputStack operator+(InputStack a, InputStack b) { + a.stack = Cat(std::move(a.stack), std::move(b.stack)); + if (a.available != Availability::NO && b.available != Availability::NO) a.size += b.size; + a.has_sig |= b.has_sig; + a.malleable |= b.malleable; + a.non_canon |= b.non_canon; + if (a.available == Availability::NO || b.available == Availability::NO) { + a.SetAvailable(Availability::NO); + } else if (a.available == Availability::MAYBE || b.available == Availability::MAYBE) { + a.SetAvailable(Availability::MAYBE); + } + return a; +} + +InputStack operator|(InputStack a, InputStack b) { + // If only one is invalid, pick the other one. If both are invalid, pick an arbitrary one. + if (a.available == Availability::NO) return b; + if (b.available == Availability::NO) return a; + // If only one of the solutions has a signature, we must pick the other one. + if (!a.has_sig && b.has_sig) return a; + if (!b.has_sig && a.has_sig) return b; + if (!a.has_sig && !b.has_sig) { + // If neither solution requires a signature, the result is inevitably malleable. + a.malleable = true; + b.malleable = true; + } else { + // If both options require a signature, prefer the non-malleable one. + if (b.malleable && !a.malleable) return a; + if (a.malleable && !b.malleable) return b; + } + // Between two malleable or two non-malleable solutions, pick the smaller one between + // YESes, and the bigger ones between MAYBEs. Prefer YES over MAYBE. + if (a.available == Availability::YES && b.available == Availability::YES) { + return std::move(a.size <= b.size ? a : b); + } else if (a.available == Availability::MAYBE && b.available == Availability::MAYBE) { + return std::move(a.size >= b.size ? a : b); + } else if (a.available == Availability::YES) { + return a; + } else { + return b; + } +} + std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script) { std::vector<Opcode> out; diff --git a/src/script/miniscript.h b/src/script/miniscript.h index 6faf2624fd..22434a4809 100644 --- a/src/script/miniscript.h +++ b/src/script/miniscript.h @@ -223,6 +223,11 @@ enum class Fragment { // WRAP_U(X) is represented as OR_I(X,0) }; +enum class Availability { + NO, + YES, + MAYBE, +}; namespace internal { @@ -235,6 +240,62 @@ size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_ //! A helper sanitizer/checker for the output of CalcType. Type SanitizeType(Type x); +//! An object representing a sequence of witness stack elements. +struct InputStack { + /** Whether this stack is valid for its intended purpose (satisfaction or dissatisfaction of a Node). + * The MAYBE value is used for size estimation, when keys/preimages may actually be unavailable, + * but may be available at signing time. This makes the InputStack structure and signing logic, + * filled with dummy signatures/preimages usable for witness size estimation. + */ + Availability available = Availability::YES; + //! Whether this stack contains a digital signature. + bool has_sig = false; + //! Whether this stack is malleable (can be turned into an equally valid other stack by a third party). + bool malleable = false; + //! Whether this stack is non-canonical (using a construction known to be unnecessary for satisfaction). + //! Note that this flag does not affect the satisfaction algorithm; it is only used for sanity checking. + bool non_canon = false; + //! Serialized witness size. + size_t size = 0; + //! Data elements. + std::vector<std::vector<unsigned char>> stack; + //! Construct an empty stack (valid). + InputStack() {} + //! Construct a valid single-element stack (with an element up to 75 bytes). + InputStack(std::vector<unsigned char> in) : size(in.size() + 1), stack(Vector(std::move(in))) {} + //! Change availability + InputStack& SetAvailable(Availability avail); + //! Mark this input stack as having a signature. + InputStack& SetWithSig(); + //! Mark this input stack as non-canonical (known to not be necessary in non-malleable satisfactions). + InputStack& SetNonCanon(); + //! Mark this input stack as malleable. + InputStack& SetMalleable(bool x = true); + //! Concatenate two input stacks. + friend InputStack operator+(InputStack a, InputStack b); + //! Choose between two potential input stacks. + friend InputStack operator|(InputStack a, InputStack b); +}; + +/** A stack consisting of a single zero-length element (interpreted as 0 by the script interpreter in numeric context). */ +static const auto ZERO = InputStack(std::vector<unsigned char>()); +/** A stack consisting of a single malleable 32-byte 0x0000...0000 element (for dissatisfying hash challenges). */ +static const auto ZERO32 = InputStack(std::vector<unsigned char>(32, 0)).SetMalleable(); +/** A stack consisting of a single 0x01 element (interpreted as 1 by the script interpreted in numeric context). */ +static const auto ONE = InputStack(Vector((unsigned char)1)); +/** The empty stack. */ +static const auto EMPTY = InputStack(); +/** A stack representing the lack of any (dis)satisfactions. */ +static const auto INVALID = InputStack().SetAvailable(Availability::NO); + +//! A pair of a satisfaction and a dissatisfaction InputStack. +struct InputResult { + InputStack nsat, sat; + + template<typename A, typename B> + InputResult(A&& in_nsat, B&& in_sat) : nsat(std::forward<A>(in_nsat)), sat(std::forward<B>(in_sat)) {} +}; + //! Class whose objects represent the maximum of a list of integers. template<typename I> struct MaxInt { @@ -785,6 +846,190 @@ private: assert(false); } + template<typename Ctx> + internal::InputResult ProduceInput(const Ctx& ctx) const { + using namespace internal; + + // Internal function which is invoked for every tree node, constructing satisfaction/dissatisfactions + // given those of its subnodes. + auto helper = [&ctx](const Node& node, Span<InputResult> subres) -> InputResult { + switch (node.fragment) { + case Fragment::PK_K: { + std::vector<unsigned char> sig; + Availability avail = ctx.Sign(node.keys[0], sig); + return {ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)}; + } + case Fragment::PK_H: { + std::vector<unsigned char> key = ctx.ToPKBytes(node.keys[0]), sig; + Availability avail = ctx.Sign(node.keys[0], sig); + return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)}; + } + case Fragment::MULTI: { + std::vector<InputStack> sats = Vector(ZERO); + for (size_t i = 0; i < node.keys.size(); ++i) { + std::vector<unsigned char> sig; + Availability avail = ctx.Sign(node.keys[i], sig); + auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail); + std::vector<InputStack> next_sats; + next_sats.push_back(sats[0]); + for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat)); + next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat)); + sats = std::move(next_sats); + } + InputStack nsat = ZERO; + for (size_t i = 0; i < node.k; ++i) nsat = std::move(nsat) + ZERO; + assert(node.k <= sats.size()); + return {std::move(nsat), std::move(sats[node.k])}; + } + case Fragment::THRESH: { + std::vector<InputStack> sats = Vector(EMPTY); + for (size_t i = 0; i < subres.size(); ++i) { + auto& res = subres[subres.size() - i - 1]; + std::vector<InputStack> next_sats; + next_sats.push_back(sats[0] + res.nsat); + for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + res.nsat) | (std::move(sats[j - 1]) + res.sat)); + next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat)); + sats = std::move(next_sats); + } + InputStack nsat = INVALID; + for (size_t i = 0; i < sats.size(); ++i) { + // i==k is the satisfaction; i==0 is the canonical dissatisfaction; the rest are non-canonical. + if (i != 0 && i != node.k) sats[i].SetNonCanon(); + if (i != node.k) nsat = std::move(nsat) | std::move(sats[i]); + } + assert(node.k <= sats.size()); + return {std::move(nsat), std::move(sats[node.k])}; + } + case Fragment::OLDER: { + return {INVALID, ctx.CheckOlder(node.k) ? EMPTY : INVALID}; + } + case Fragment::AFTER: { + return {INVALID, ctx.CheckAfter(node.k) ? EMPTY : INVALID}; + } + case Fragment::SHA256: { + std::vector<unsigned char> preimage; + Availability avail = ctx.SatSHA256(node.data, preimage); + return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; + } + case Fragment::RIPEMD160: { + std::vector<unsigned char> preimage; + Availability avail = ctx.SatRIPEMD160(node.data, preimage); + return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; + } + case Fragment::HASH256: { + std::vector<unsigned char> preimage; + Availability avail = ctx.SatHASH256(node.data, preimage); + return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; + } + case Fragment::HASH160: { + std::vector<unsigned char> preimage; + Availability avail = ctx.SatHASH160(node.data, preimage); + return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; + } + case Fragment::AND_V: { + auto& x = subres[0], &y = subres[1]; + return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat}; + } + case Fragment::AND_B: { + auto& x = subres[0], &y = subres[1]; + return {(y.nsat + x.nsat) | (y.sat + x.nsat).SetMalleable().SetNonCanon() | (y.nsat + x.sat).SetMalleable().SetNonCanon(), y.sat + x.sat}; + } + case Fragment::OR_B: { + auto& x = subres[0], &z = subres[1]; + // The (sat(Z) sat(X)) solution is overcomplete (attacker can change either into dsat). + return {z.nsat + x.nsat, (z.nsat + x.sat) | (z.sat + x.nsat) | (z.sat + x.sat).SetMalleable().SetNonCanon()}; + } + case Fragment::OR_C: { + auto& x = subres[0], &z = subres[1]; + return {INVALID, std::move(x.sat) | (z.sat + x.nsat)}; + } + case Fragment::OR_D: { + auto& x = subres[0], &z = subres[1]; + return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)}; + } + case Fragment::OR_I: { + auto& x = subres[0], &z = subres[1]; + return {(x.nsat + ONE) | (z.nsat + ZERO), (x.sat + ONE) | (z.sat + ZERO)}; + } + case Fragment::ANDOR: { + auto& x = subres[0], &y = subres[1], &z = subres[2]; + return {(y.nsat + x.sat).SetNonCanon() | (z.nsat + x.nsat), (y.sat + x.sat) | (z.sat + x.nsat)}; + } + case Fragment::WRAP_A: + case Fragment::WRAP_S: + case Fragment::WRAP_C: + case Fragment::WRAP_N: + return std::move(subres[0]); + case Fragment::WRAP_D: { + auto &x = subres[0]; + return {ZERO, x.sat + ONE}; + } + case Fragment::WRAP_J: { + auto &x = subres[0]; + // If a dissatisfaction with a nonzero top stack element exists, an alternative dissatisfaction exists. + // As the dissatisfaction logic currently doesn't keep track of this nonzeroness property, and thus even + // if a dissatisfaction with a top zero element is found, we don't know whether another one with a + // nonzero top stack element exists. Make the conservative assumption that whenever the subexpression is weakly + // dissatisfiable, this alternative dissatisfaction exists and leads to malleability. + return {InputStack(ZERO).SetMalleable(x.nsat.available != Availability::NO && !x.nsat.has_sig), std::move(x.sat)}; + } + case Fragment::WRAP_V: { + auto &x = subres[0]; + return {INVALID, std::move(x.sat)}; + } + case Fragment::JUST_0: return {EMPTY, INVALID}; + case Fragment::JUST_1: return {INVALID, EMPTY}; + } + assert(false); + return {INVALID, INVALID}; + }; + + auto tester = [&helper](const Node& node, Span<InputResult> subres) -> InputResult { + auto ret = helper(node, subres); + + // Do a consistency check between the satisfaction code and the type checker + // (the actual satisfaction code in ProduceInputHelper does not use GetType) + + // For 'z' nodes, available satisfactions/dissatisfactions must have stack size 0. + if (node.GetType() << "z"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 0); + if (node.GetType() << "z"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() == 0); + + // For 'o' nodes, available satisfactions/dissatisfactions must have stack size 1. + if (node.GetType() << "o"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 1); + if (node.GetType() << "o"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() == 1); + + // For 'n' nodes, available satisfactions/dissatisfactions must have stack size 1 or larger. For satisfactions, + // the top element cannot be 0. + if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() >= 1); + if (node.GetType() << "n"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() >= 1); + if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(!ret.sat.stack.back().empty()); + + // For 'd' nodes, a dissatisfaction must exist, and they must not need a signature. If it is non-malleable, + // it must be canonical. + if (node.GetType() << "d"_mst) assert(ret.nsat.available != Availability::NO); + if (node.GetType() << "d"_mst) assert(!ret.nsat.has_sig); + if (node.GetType() << "d"_mst && !ret.nsat.malleable) assert(!ret.nsat.non_canon); + + // For 'f'/'s' nodes, dissatisfactions/satisfactions must have a signature. + if (node.GetType() << "f"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.has_sig); + if (node.GetType() << "s"_mst && ret.sat.available != Availability::NO) assert(ret.sat.has_sig); + + // For 'e' nodes, a non-malleable dissatisfaction must exist. + if (node.GetType() << "e"_mst) assert(ret.nsat.available != Availability::NO); + if (node.GetType() << "e"_mst) assert(!ret.nsat.malleable); + + // For 'm' nodes, if a satisfaction exists, it must be non-malleable. + if (node.GetType() << "m"_mst && ret.sat.available != Availability::NO) assert(!ret.sat.malleable); + + // If a non-malleable satisfaction exists, it must be canonical. + if (ret.sat.available != Availability::NO && !ret.sat.malleable) assert(!ret.sat.non_canon); + + return ret; + }; + + return TreeEval<InputResult>(tester); + } + public: /** Update duplicate key information in this Node. * @@ -877,6 +1122,47 @@ public: }); } + //! Determine whether a Miniscript node is satisfiable. fn(node) will be invoked for all + //! key, time, and hashing nodes, and should return their satisfiability. + template<typename F> + bool IsSatisfiable(F fn) const + { + // TreeEval() doesn't support bool as NodeType, so use int instead. + return TreeEval<int>([&fn](const Node& node, Span<int> subs) -> bool { + switch (node.fragment) { + case Fragment::JUST_0: + return false; + case Fragment::JUST_1: + return true; + case Fragment::PK_K: + case Fragment::PK_H: + case Fragment::MULTI: + case Fragment::AFTER: + case Fragment::OLDER: + case Fragment::HASH256: + case Fragment::HASH160: + case Fragment::SHA256: + case Fragment::RIPEMD160: + return bool{fn(node)}; + case Fragment::ANDOR: + return (subs[0] && subs[1]) || subs[2]; + case Fragment::AND_V: + case Fragment::AND_B: + return subs[0] && subs[1]; + case Fragment::OR_B: + case Fragment::OR_C: + case Fragment::OR_D: + case Fragment::OR_I: + return subs[0] || subs[1]; + case Fragment::THRESH: + return std::count(subs.begin(), subs.end(), true) >= node.k; + default: // wrappers + assert(subs.size() == 1); + return subs[0]; + } + }); + } + //! Check whether this node is valid at all. bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; } @@ -904,6 +1190,18 @@ public: //! Check whether this node is safe as a script on its own. bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); } + //! Produce a witness for this script, if possible and given the information available in the context. + //! The non-malleable satisfaction is guaranteed to be valid if it exists, and ValidSatisfaction() + //! is true. If IsSane() holds, this satisfaction is guaranteed to succeed in case the node's + //! conditions are satisfied (private keys and hash preimages available, locktimes satsified). + template<typename Ctx> + Availability Satisfy(const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack, bool nonmalleable = true) const { + auto ret = ProduceInput(ctx); + if (nonmalleable && (ret.sat.malleable || !ret.sat.has_sig)) return Availability::NO; + stack = std::move(ret.sat.stack); + return ret.sat.available; + } + //! Equality testing. bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; } diff --git a/src/test/miniscript_tests.cpp b/src/test/miniscript_tests.cpp index 9387c01e73..99893cc7d1 100644 --- a/src/test/miniscript_tests.cpp +++ b/src/test/miniscript_tests.cpp @@ -2,18 +2,23 @@ // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. - +#include <stdint.h> #include <string> +#include <vector> #include <test/util/setup_common.h> #include <boost/test/unit_test.hpp> +#include <core_io.h> #include <hash.h> #include <pubkey.h> #include <uint256.h> #include <crypto/ripemd160.h> #include <crypto/sha256.h> +#include <script/interpreter.h> #include <script/miniscript.h> +#include <script/standard.h> +#include <script/script_error.h> namespace { @@ -24,15 +29,22 @@ struct TestData { //! A map from the public keys to their CKeyIDs (faster than hashing every time). std::map<CPubKey, CKeyID> pkhashes; std::map<CKeyID, CPubKey> pkmap; + std::map<CPubKey, std::vector<unsigned char>> signatures; // Various precomputed hashes std::vector<std::vector<unsigned char>> sha256; std::vector<std::vector<unsigned char>> ripemd160; std::vector<std::vector<unsigned char>> hash256; std::vector<std::vector<unsigned char>> hash160; + std::map<std::vector<unsigned char>, std::vector<unsigned char>> sha256_preimages; + std::map<std::vector<unsigned char>, std::vector<unsigned char>> ripemd160_preimages; + std::map<std::vector<unsigned char>, std::vector<unsigned char>> hash256_preimages; + std::map<std::vector<unsigned char>, std::vector<unsigned char>> hash160_preimages; TestData() { + // All our signatures sign (and are required to sign) this constant message. + auto const MESSAGE_HASH = uint256S("f5cd94e18b6fe77dd7aca9e35c2b0c9cbd86356c80a71065"); // We generate 255 public keys and 255 hashes of each type. for (int i = 1; i <= 255; ++i) { // This 32-byte array functions as both private key data and hash preimage (31 zero bytes plus any nonzero byte). @@ -48,18 +60,28 @@ struct TestData { pkhashes.emplace(pubkey, keyid); pkmap.emplace(keyid, pubkey); + // Compute ECDSA signatures on MESSAGE_HASH with the private keys. + std::vector<unsigned char> sig; + BOOST_CHECK(key.Sign(MESSAGE_HASH, sig)); + sig.push_back(1); // sighash byte + signatures.emplace(pubkey, sig); + // Compute various hashes std::vector<unsigned char> hash; hash.resize(32); CSHA256().Write(keydata, 32).Finalize(hash.data()); sha256.push_back(hash); + sha256_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32); CHash256().Write(keydata).Finalize(hash); hash256.push_back(hash); + hash256_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32); hash.resize(20); CRIPEMD160().Write(keydata, 32).Finalize(hash.data()); ripemd160.push_back(hash); + ripemd160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32); CHash160().Write(keydata).Finalize(hash); hash160.push_back(hash); + hash160_preimages[hash] = std::vector<unsigned char>(keydata, keydata + 32); } } }; @@ -67,7 +89,27 @@ struct TestData { //! Global TestData object std::unique_ptr<const TestData> g_testdata; -/** A class encapsulating conversion routing for CPubKey. */ +//! A classification of leaf conditions in miniscripts (excluding true/false). +enum class ChallengeType { + SHA256, + RIPEMD160, + HASH256, + HASH160, + OLDER, + AFTER, + PK +}; + +/* With each leaf condition we associate a challenge number. + * For hashes it's just the first 4 bytes of the hash. For pubkeys, it's the last 4 bytes. + */ +uint32_t ChallengeNumber(const CPubKey& pubkey) { return ReadLE32(pubkey.data() + 29); } +uint32_t ChallengeNumber(const std::vector<unsigned char>& hash) { return ReadLE32(hash.data()); } + +//! A Challenge is a combination of type of leaf condition and its challenge number. +typedef std::pair<ChallengeType, uint32_t> Challenge; + +/** A class encapulating conversion routing for CPubKey. */ struct KeyConverter { typedef CPubKey Key; @@ -117,12 +159,197 @@ struct KeyConverter { } }; +/** A class that encapsulates all signing/hash revealing operations. */ +struct Satisfier : public KeyConverter { + //! Which keys/timelocks/hash preimages are available. + std::set<Challenge> supported; + + //! Implement simplified CLTV logic: stack value must exactly match an entry in `supported`. + bool CheckAfter(uint32_t value) const { + return supported.count(Challenge(ChallengeType::AFTER, value)); + } + + //! Implement simplified CSV logic: stack value must exactly match an entry in `supported`. + bool CheckOlder(uint32_t value) const { + return supported.count(Challenge(ChallengeType::OLDER, value)); + } + + //! Produce a signature for the given key. + miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const { + if (supported.count(Challenge(ChallengeType::PK, ChallengeNumber(key)))) { + auto it = g_testdata->signatures.find(key); + if (it == g_testdata->signatures.end()) return miniscript::Availability::NO; + sig = it->second; + return miniscript::Availability::YES; + } + return miniscript::Availability::NO; + } + + //! Helper function for the various hash based satisfactions. + miniscript::Availability SatHash(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage, ChallengeType chtype) const { + if (!supported.count(Challenge(chtype, ChallengeNumber(hash)))) return miniscript::Availability::NO; + const auto& m = + chtype == ChallengeType::SHA256 ? g_testdata->sha256_preimages : + chtype == ChallengeType::HASH256 ? g_testdata->hash256_preimages : + chtype == ChallengeType::RIPEMD160 ? g_testdata->ripemd160_preimages : + g_testdata->hash160_preimages; + auto it = m.find(hash); + if (it == m.end()) return miniscript::Availability::NO; + preimage = it->second; + return miniscript::Availability::YES; + } + + // Functions that produce the preimage for hashes of various types. + miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const { return SatHash(hash, preimage, ChallengeType::SHA256); } + miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const { return SatHash(hash, preimage, ChallengeType::RIPEMD160); } + miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const { return SatHash(hash, preimage, ChallengeType::HASH256); } + miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const { return SatHash(hash, preimage, ChallengeType::HASH160); } +}; + +/** Mocking signature/timelock checker. + * + * It holds a pointer to a Satisfier object, to determine which timelocks are supposed to be available. + */ +class TestSignatureChecker : public BaseSignatureChecker { + const Satisfier& ctx; + +public: + TestSignatureChecker(const Satisfier& in_ctx LIFETIMEBOUND) : ctx(in_ctx) {} + + bool CheckECDSASignature(const std::vector<unsigned char>& sig, const std::vector<unsigned char>& pubkey, const CScript& scriptcode, SigVersion sigversion) const override { + CPubKey pk(pubkey); + if (!pk.IsValid()) return false; + // Instead of actually running signature validation, check if the signature matches the precomputed one for this key. + auto it = g_testdata->signatures.find(pk); + if (it == g_testdata->signatures.end()) return false; + return sig == it->second; + } + + bool CheckLockTime(const CScriptNum& locktime) const override { + // Delegate to Satisfier. + return ctx.CheckAfter(locktime.GetInt64()); + } + + bool CheckSequence(const CScriptNum& sequence) const override { + // Delegate to Satisfier. + return ctx.CheckOlder(sequence.GetInt64()); + } +}; + //! Singleton instance of KeyConverter. const KeyConverter CONVERTER{}; +using Fragment = miniscript::Fragment; +using NodeRef = miniscript::NodeRef<CPubKey>; // https://github.com/llvm/llvm-project/issues/53444 // NOLINTNEXTLINE(misc-unused-using-decls) using miniscript::operator"" _mst; +using Node = miniscript::Node<CPubKey>; + +/** Compute all challenges (pubkeys, hashes, timelocks) that occur in a given Miniscript. */ +std::set<Challenge> FindChallenges(const NodeRef& ref) { + std::set<Challenge> chal; + for (const auto& key : ref->keys) { + chal.emplace(ChallengeType::PK, ChallengeNumber(key)); + } + if (ref->fragment == miniscript::Fragment::OLDER) { + chal.emplace(ChallengeType::OLDER, ref->k); + } else if (ref->fragment == miniscript::Fragment::AFTER) { + chal.emplace(ChallengeType::AFTER, ref->k); + } else if (ref->fragment == miniscript::Fragment::SHA256) { + chal.emplace(ChallengeType::SHA256, ChallengeNumber(ref->data)); + } else if (ref->fragment == miniscript::Fragment::RIPEMD160) { + chal.emplace(ChallengeType::RIPEMD160, ChallengeNumber(ref->data)); + } else if (ref->fragment == miniscript::Fragment::HASH256) { + chal.emplace(ChallengeType::HASH256, ChallengeNumber(ref->data)); + } else if (ref->fragment == miniscript::Fragment::HASH160) { + chal.emplace(ChallengeType::HASH160, ChallengeNumber(ref->data)); + } + for (const auto& sub : ref->subs) { + auto sub_chal = FindChallenges(sub); + chal.insert(sub_chal.begin(), sub_chal.end()); + } + return chal; +} + +/** Run random satisfaction tests. */ +void TestSatisfy(const std::string& testcase, const NodeRef& node) { + auto script = node->ToScript(CONVERTER); + auto challenges = FindChallenges(node); // Find all challenges in the generated miniscript. + std::vector<Challenge> challist(challenges.begin(), challenges.end()); + for (int iter = 0; iter < 3; ++iter) { + Shuffle(challist.begin(), challist.end(), g_insecure_rand_ctx); + Satisfier satisfier; + TestSignatureChecker checker(satisfier); + bool prev_mal_success = false, prev_nonmal_success = false; + // Go over all challenges involved in this miniscript in random order. + for (int add = -1; add < (int)challist.size(); ++add) { + if (add >= 0) satisfier.supported.insert(challist[add]); // The first iteration does not add anything + + // Run malleable satisfaction algorithm. + const CScript script_pubkey = CScript() << OP_0 << WitnessV0ScriptHash(script); + CScriptWitness witness_mal; + const bool mal_success = node->Satisfy(satisfier, witness_mal.stack, false) == miniscript::Availability::YES; + witness_mal.stack.push_back(std::vector<unsigned char>(script.begin(), script.end())); + + // Run non-malleable satisfaction algorithm. + CScriptWitness witness_nonmal; + const bool nonmal_success = node->Satisfy(satisfier, witness_nonmal.stack, true) == miniscript::Availability::YES; + witness_nonmal.stack.push_back(std::vector<unsigned char>(script.begin(), script.end())); + + if (nonmal_success) { + // Non-malleable satisfactions are bounded by GetStackSize(). + BOOST_CHECK(witness_nonmal.stack.size() <= node->GetStackSize()); + // If a non-malleable satisfaction exists, the malleable one must also exist, and be identical to it. + BOOST_CHECK(mal_success); + BOOST_CHECK(witness_nonmal.stack == witness_mal.stack); + + // Test non-malleable satisfaction. + ScriptError serror; + bool res = VerifyScript(CScript(), script_pubkey, &witness_nonmal, STANDARD_SCRIPT_VERIFY_FLAGS, checker, &serror); + // Non-malleable satisfactions are guaranteed to be valid if ValidSatisfactions(). + if (node->ValidSatisfactions()) BOOST_CHECK(res); + // More detailed: non-malleable satisfactions must be valid, or could fail with ops count error (if CheckOpsLimit failed), + // or with a stack size error (if CheckStackSize check fails). + BOOST_CHECK(res || + (!node->CheckOpsLimit() && serror == ScriptError::SCRIPT_ERR_OP_COUNT) || + (!node->CheckStackSize() && serror == ScriptError::SCRIPT_ERR_STACK_SIZE)); + } + + if (mal_success && (!nonmal_success || witness_mal.stack != witness_nonmal.stack)) { + // Test malleable satisfaction only if it's different from the non-malleable one. + ScriptError serror; + bool res = VerifyScript(CScript(), script_pubkey, &witness_mal, STANDARD_SCRIPT_VERIFY_FLAGS, checker, &serror); + // Malleable satisfactions are not guaranteed to be valid under any conditions, but they can only + // fail due to stack or ops limits. + BOOST_CHECK(res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE); + } + + if (node->IsSane()) { + // For sane nodes, the two algorithms behave identically. + BOOST_CHECK_EQUAL(mal_success, nonmal_success); + } + + // Adding more satisfied conditions can never remove our ability to produce a satisfaction. + BOOST_CHECK(mal_success >= prev_mal_success); + // For nonmalleable solutions this is only true if the added condition is PK; + // for other conditions, adding one may make an valid satisfaction become malleable. If the script + // is sane, this cannot happen however. + if (node->IsSane() || add < 0 || challist[add].first == ChallengeType::PK) { + BOOST_CHECK(nonmal_success >= prev_nonmal_success); + } + // Remember results for the next added challenge. + prev_mal_success = mal_success; + prev_nonmal_success = nonmal_success; + } + + bool satisfiable = node->IsSatisfiable([](const Node&) { return true; }); + // If the miniscript was satisfiable at all, a satisfaction must be found after all conditions are added. + BOOST_CHECK_EQUAL(prev_mal_success, satisfiable); + // If the miniscript is sane and satisfiable, a nonmalleable satisfaction must eventually be found. + if (node->IsSane()) BOOST_CHECK_EQUAL(prev_nonmal_success, satisfiable); + } +} enum TestMode : int { TESTMODE_INVALID = 0, @@ -152,6 +379,7 @@ void Test(const std::string& ms, const std::string& hexscript, int mode, int ops BOOST_CHECK_MESSAGE(inferred_miniscript->ToScript(CONVERTER) == computed_script, "Roundtrip failure: miniscript->script != miniscript->script->miniscript->script: " + ms); if (opslimit != -1) BOOST_CHECK_MESSAGE((int)node->GetOps() == opslimit, "Ops limit mismatch: " << ms << " (" << node->GetOps() << " vs " << opslimit << ")"); if (stacklimit != -1) BOOST_CHECK_MESSAGE((int)node->GetStackSize() == stacklimit, "Stack limit mismatch: " << ms << " (" << node->GetStackSize() << " vs " << stacklimit << ")"); + TestSatisfy(ms, node); } } } // namespace |