aboutsummaryrefslogtreecommitdiff
path: root/src/script
diff options
context:
space:
mode:
Diffstat (limited to 'src/script')
-rw-r--r--src/script/descriptor.cpp141
-rw-r--r--src/script/miniscript.cpp34
-rw-r--r--src/script/miniscript.h660
-rw-r--r--src/script/sign.cpp272
-rw-r--r--src/script/sign.h1
5 files changed, 797 insertions, 311 deletions
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index 2f3f2c7a1d..7e62d75583 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -1114,16 +1114,33 @@ public:
class ScriptMaker {
//! Keys contained in the Miniscript (the evaluation of DescriptorImpl::m_pubkey_args).
const std::vector<CPubKey>& m_keys;
+ //! The script context we're operating within (Tapscript or P2WSH).
+ const miniscript::MiniscriptContext m_script_ctx;
+
+ //! Get the ripemd160(sha256()) hash of this key.
+ //! Any key that is valid in a descriptor serializes as 32 bytes within a Tapscript context. So we
+ //! must not hash the sign-bit byte in this case.
+ uint160 GetHash160(uint32_t key) const {
+ if (miniscript::IsTapscript(m_script_ctx)) {
+ return Hash160(XOnlyPubKey{m_keys[key]});
+ }
+ return m_keys[key].GetID();
+ }
public:
- ScriptMaker(const std::vector<CPubKey>& keys LIFETIMEBOUND) : m_keys(keys) {}
+ ScriptMaker(const std::vector<CPubKey>& keys LIFETIMEBOUND, const miniscript::MiniscriptContext script_ctx) : m_keys(keys), m_script_ctx{script_ctx} {}
std::vector<unsigned char> ToPKBytes(uint32_t key) const {
- return {m_keys[key].begin(), m_keys[key].end()};
+ // In Tapscript keys always serialize as x-only, whether an x-only key was used in the descriptor or not.
+ if (!miniscript::IsTapscript(m_script_ctx)) {
+ return {m_keys[key].begin(), m_keys[key].end()};
+ }
+ const XOnlyPubKey xonly_pubkey{m_keys[key]};
+ return {xonly_pubkey.begin(), xonly_pubkey.end()};
}
std::vector<unsigned char> ToPKHBytes(uint32_t key) const {
- auto id = m_keys[key].GetID();
+ auto id = GetHash160(key);
return {id.begin(), id.end()};
}
};
@@ -1164,8 +1181,15 @@ protected:
std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts,
FlatSigningProvider& provider) const override
{
- for (const auto& key : keys) provider.pubkeys.emplace(key.GetID(), key);
- return Vector(m_node->ToScript(ScriptMaker(keys)));
+ const auto script_ctx{m_node->GetMsCtx()};
+ for (const auto& key : keys) {
+ if (miniscript::IsTapscript(script_ctx)) {
+ provider.pubkeys.emplace(Hash160(XOnlyPubKey{key}), key);
+ } else {
+ provider.pubkeys.emplace(key.GetID(), key);
+ }
+ }
+ return Vector(m_node->ToScript(ScriptMaker(keys, script_ctx)));
}
public:
@@ -1290,6 +1314,10 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S
if (IsHex(str)) {
std::vector<unsigned char> data = ParseHex(str);
CPubKey pubkey(data);
+ if (pubkey.IsValid() && !pubkey.IsValidNonHybrid()) {
+ error = "Hybrid public keys are not allowed";
+ return nullptr;
+ }
if (pubkey.IsFullyValid()) {
if (permit_uncompressed || pubkey.IsCompressed()) {
return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, false);
@@ -1385,8 +1413,16 @@ std::unique_ptr<PubkeyProvider> ParsePubkey(uint32_t key_exp_index, const Span<c
return std::make_unique<OriginPubkeyProvider>(key_exp_index, std::move(info), std::move(provider), apostrophe);
}
-std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext, const SigningProvider& provider)
+std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptContext ctx, const SigningProvider& provider)
{
+ // Key cannot be hybrid
+ if (!pubkey.IsValidNonHybrid()) {
+ return nullptr;
+ }
+ // Uncompressed is only allowed in TOP and P2SH contexts
+ if (ctx != ParseScriptContext::TOP && ctx != ParseScriptContext::P2SH && !pubkey.IsCompressed()) {
+ return nullptr;
+ }
std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, false);
KeyOriginInfo info;
if (provider.GetKeyOrigin(pubkey.GetID(), info)) {
@@ -1397,9 +1433,7 @@ std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptCo
std::unique_ptr<PubkeyProvider> InferXOnlyPubkey(const XOnlyPubKey& xkey, ParseScriptContext ctx, const SigningProvider& provider)
{
- unsigned char full_key[CPubKey::COMPRESSED_SIZE] = {0x02};
- std::copy(xkey.begin(), xkey.end(), full_key + 1);
- CPubKey pubkey(full_key);
+ CPubKey pubkey{xkey.GetEvenCorrespondingCPubKey()};
std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, true);
KeyOriginInfo info;
if (provider.GetKeyOriginByXOnly(xkey, info)) {
@@ -1422,18 +1456,32 @@ struct KeyParser {
mutable std::vector<std::unique_ptr<PubkeyProvider>> m_keys;
//! Used to detect key parsing errors within a Miniscript.
mutable std::string m_key_parsing_error;
+ //! The script context we're operating within (Tapscript or P2WSH).
+ const miniscript::MiniscriptContext m_script_ctx;
+ //! The number of keys that were parsed before starting to parse this Miniscript descriptor.
+ uint32_t m_offset;
- KeyParser(FlatSigningProvider* out LIFETIMEBOUND, const SigningProvider* in LIFETIMEBOUND) : m_out(out), m_in(in) {}
+ KeyParser(FlatSigningProvider* out LIFETIMEBOUND, const SigningProvider* in LIFETIMEBOUND,
+ miniscript::MiniscriptContext ctx, uint32_t offset = 0)
+ : m_out(out), m_in(in), m_script_ctx(ctx), m_offset(offset) {}
bool KeyCompare(const Key& a, const Key& b) const {
return *m_keys.at(a) < *m_keys.at(b);
}
+ ParseScriptContext ParseContext() const {
+ switch (m_script_ctx) {
+ case miniscript::MiniscriptContext::P2WSH: return ParseScriptContext::P2WSH;
+ case miniscript::MiniscriptContext::TAPSCRIPT: return ParseScriptContext::P2TR;
+ }
+ assert(false);
+ }
+
template<typename I> std::optional<Key> FromString(I begin, I end) const
{
assert(m_out);
Key key = m_keys.size();
- auto pk = ParsePubkey(key, {&*begin, &*end}, ParseScriptContext::P2WSH, *m_out, m_key_parsing_error);
+ auto pk = ParsePubkey(m_offset + key, {&*begin, &*end}, ParseContext(), *m_out, m_key_parsing_error);
if (!pk) return {};
m_keys.push_back(std::move(pk));
return key;
@@ -1447,11 +1495,20 @@ struct KeyParser {
template<typename I> std::optional<Key> FromPKBytes(I begin, I end) const
{
assert(m_in);
- CPubKey pubkey(begin, end);
- if (pubkey.IsValid()) {
- Key key = m_keys.size();
- m_keys.push_back(InferPubkey(pubkey, ParseScriptContext::P2WSH, *m_in));
- return key;
+ Key key = m_keys.size();
+ if (miniscript::IsTapscript(m_script_ctx) && end - begin == 32) {
+ XOnlyPubKey pubkey;
+ std::copy(begin, end, pubkey.begin());
+ if (auto pubkey_provider = InferPubkey(pubkey.GetEvenCorrespondingCPubKey(), ParseContext(), *m_in)) {
+ m_keys.push_back(std::move(pubkey_provider));
+ return key;
+ }
+ } else if (!miniscript::IsTapscript(m_script_ctx)) {
+ CPubKey pubkey(begin, end);
+ if (auto pubkey_provider = InferPubkey(pubkey, ParseContext(), *m_in)) {
+ m_keys.push_back(std::move(pubkey_provider));
+ return key;
+ }
}
return {};
}
@@ -1465,12 +1522,18 @@ struct KeyParser {
CKeyID keyid(hash);
CPubKey pubkey;
if (m_in->GetPubKey(keyid, pubkey)) {
- Key key = m_keys.size();
- m_keys.push_back(InferPubkey(pubkey, ParseScriptContext::P2WSH, *m_in));
- return key;
+ if (auto pubkey_provider = InferPubkey(pubkey, ParseContext(), *m_in)) {
+ Key key = m_keys.size();
+ m_keys.push_back(std::move(pubkey_provider));
+ return key;
+ }
}
return {};
}
+
+ miniscript::MiniscriptContext MsContext() const {
+ return m_script_ctx;
+ }
};
/** Parse a script in a particular context. */
@@ -1496,8 +1559,9 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
}
++key_exp_index;
return std::make_unique<PKHDescriptor>(std::move(pubkey));
- } else if (Func("pkh", expr)) {
- error = "Can only have pkh at top level, in sh(), or in wsh()";
+ } else if (ctx != ParseScriptContext::P2TR && Func("pkh", expr)) {
+ // Under Taproot, always the Miniscript parser deal with it.
+ error = "Can only have pkh at top level, in sh(), wsh(), or in tr()";
return nullptr;
}
if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
@@ -1710,11 +1774,12 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
}
// Process miniscript expressions.
{
- KeyParser parser(&out, nullptr);
+ const auto script_ctx{ctx == ParseScriptContext::P2WSH ? miniscript::MiniscriptContext::P2WSH : miniscript::MiniscriptContext::TAPSCRIPT};
+ KeyParser parser(/*out = */&out, /* in = */nullptr, /* ctx = */script_ctx, key_exp_index);
auto node = miniscript::FromString(std::string(expr.begin(), expr.end()), parser);
if (node) {
- if (ctx != ParseScriptContext::P2WSH) {
- error = "Miniscript expressions can only be used in wsh";
+ if (ctx != ParseScriptContext::P2WSH && ctx != ParseScriptContext::P2TR) {
+ error = "Miniscript expressions can only be used in wsh or tr.";
return nullptr;
}
if (parser.m_key_parsing_error != "") {
@@ -1749,6 +1814,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
// A signature check is required for a miniscript to be sane. Therefore no sane miniscript
// may have an empty list of public keys.
CHECK_NONFATAL(!parser.m_keys.empty());
+ key_exp_index += parser.m_keys.size();
return std::make_unique<MiniscriptDescriptor>(std::move(parser.m_keys), std::move(node));
}
}
@@ -1795,8 +1861,8 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
if (txntype == TxoutType::PUBKEY && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) {
CPubKey pubkey(data[0]);
- if (pubkey.IsValid()) {
- return std::make_unique<PKDescriptor>(InferPubkey(pubkey, ctx, provider));
+ if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) {
+ return std::make_unique<PKDescriptor>(std::move(pubkey_provider));
}
}
if (txntype == TxoutType::PUBKEYHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) {
@@ -1804,7 +1870,9 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
CKeyID keyid(hash);
CPubKey pubkey;
if (provider.GetPubKey(keyid, pubkey)) {
- return std::make_unique<PKHDescriptor>(InferPubkey(pubkey, ctx, provider));
+ if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) {
+ return std::make_unique<PKHDescriptor>(std::move(pubkey_provider));
+ }
}
}
if (txntype == TxoutType::WITNESS_V0_KEYHASH && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH)) {
@@ -1812,16 +1880,24 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
CKeyID keyid(hash);
CPubKey pubkey;
if (provider.GetPubKey(keyid, pubkey)) {
- return std::make_unique<WPKHDescriptor>(InferPubkey(pubkey, ctx, provider));
+ if (auto pubkey_provider = InferPubkey(pubkey, ParseScriptContext::P2WPKH, provider)) {
+ return std::make_unique<WPKHDescriptor>(std::move(pubkey_provider));
+ }
}
}
if (txntype == TxoutType::MULTISIG && (ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH)) {
+ bool ok = true;
std::vector<std::unique_ptr<PubkeyProvider>> providers;
for (size_t i = 1; i + 1 < data.size(); ++i) {
CPubKey pubkey(data[i]);
- providers.push_back(InferPubkey(pubkey, ctx, provider));
+ if (auto pubkey_provider = InferPubkey(pubkey, ctx, provider)) {
+ providers.push_back(std::move(pubkey_provider));
+ } else {
+ ok = false;
+ break;
+ }
}
- return std::make_unique<MultisigDescriptor>((int)data[0][0], std::move(providers));
+ if (ok) return std::make_unique<MultisigDescriptor>((int)data[0][0], std::move(providers));
}
if (txntype == TxoutType::SCRIPTHASH && ctx == ParseScriptContext::TOP) {
uint160 hash(data[0]);
@@ -1882,8 +1958,9 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
}
}
- if (ctx == ParseScriptContext::P2WSH) {
- KeyParser parser(nullptr, &provider);
+ if (ctx == ParseScriptContext::P2WSH || ctx == ParseScriptContext::P2TR) {
+ const auto script_ctx{ctx == ParseScriptContext::P2WSH ? miniscript::MiniscriptContext::P2WSH : miniscript::MiniscriptContext::TAPSCRIPT};
+ KeyParser parser(/* out = */nullptr, /* in = */&provider, /* ctx = */script_ctx);
auto node = miniscript::FromScript(script, parser);
if (node && node->IsSane()) {
return std::make_unique<MiniscriptDescriptor>(std::move(parser.m_keys), std::move(node));
diff --git a/src/script/miniscript.cpp b/src/script/miniscript.cpp
index 19556a9775..344a81bdf0 100644
--- a/src/script/miniscript.cpp
+++ b/src/script/miniscript.cpp
@@ -6,6 +6,7 @@
#include <vector>
#include <script/script.h>
#include <script/miniscript.h>
+#include <serialize.h>
#include <assert.h>
@@ -32,7 +33,8 @@ Type SanitizeType(Type e) {
return e;
}
-Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys) {
+Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k,
+ size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx) {
// Sanity check on data
if (fragment == Fragment::SHA256 || fragment == Fragment::HASH256) {
assert(data_size == 32);
@@ -44,7 +46,7 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
// Sanity check on k
if (fragment == Fragment::OLDER || fragment == Fragment::AFTER) {
assert(k >= 1 && k < 0x80000000UL);
- } else if (fragment == Fragment::MULTI) {
+ } else if (fragment == Fragment::MULTI || fragment == Fragment::MULTI_A) {
assert(k >= 1 && k <= n_keys);
} else if (fragment == Fragment::THRESH) {
assert(k >= 1 && k <= n_subs);
@@ -68,7 +70,11 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
if (fragment == Fragment::PK_K || fragment == Fragment::PK_H) {
assert(n_keys == 1);
} else if (fragment == Fragment::MULTI) {
- assert(n_keys >= 1 && n_keys <= 20);
+ assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTISIG);
+ assert(!IsTapscript(ms_ctx));
+ } else if (fragment == Fragment::MULTI_A) {
+ assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTI_A);
+ assert(IsTapscript(ms_ctx));
} else {
assert(n_keys == 0);
}
@@ -113,7 +119,8 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
"e"_mst.If(x << "f"_mst) | // e=f_x
(x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
(x & "ms"_mst) | // m=m_x, s=s_x
- // NOTE: 'd:' is not 'u' under P2WSH as MINIMALIF is only a policy rule there.
+ // NOTE: 'd:' is 'u' under Tapscript but not P2WSH as MINIMALIF is only a policy rule there.
+ "u"_mst.If(IsTapscript(ms_ctx)) |
"ndx"_mst; // n, d, x
case Fragment::WRAP_V: return
"V"_mst.If(x << "B"_mst) | // V=B_x
@@ -210,7 +217,12 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
((x << "h"_mst) && (y << "g"_mst)) ||
((x << "i"_mst) && (y << "j"_mst)) ||
((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*k_z* !(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
- case Fragment::MULTI: return "Bnudemsk"_mst;
+ case Fragment::MULTI: {
+ return "Bnudemsk"_mst;
+ }
+ case Fragment::MULTI_A: {
+ return "Budemsk"_mst;
+ }
case Fragment::THRESH: {
bool all_e = true;
bool all_m = true;
@@ -246,11 +258,12 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
assert(false);
}
-size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys) {
+size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs,
+ size_t n_keys, MiniscriptContext ms_ctx) {
switch (fragment) {
case Fragment::JUST_1:
case Fragment::JUST_0: return 1;
- case Fragment::PK_K: return 34;
+ case Fragment::PK_K: return IsTapscript(ms_ctx) ? 33 : 34;
case Fragment::PK_H: return 3 + 21;
case Fragment::OLDER:
case Fragment::AFTER: return 1 + BuildScript(k).size();
@@ -259,6 +272,7 @@ size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_
case Fragment::HASH160:
case Fragment::RIPEMD160: return 4 + 2 + 21;
case Fragment::MULTI: return 1 + BuildScript(n_keys).size() + BuildScript(k).size() + 34 * n_keys;
+ case Fragment::MULTI_A: return (1 + 32 + 1) * n_keys + BuildScript(k).size() + 1;
case Fragment::AND_V: return subsize;
case Fragment::WRAP_V: return subsize + (sub0typ << "x"_mst);
case Fragment::WRAP_S:
@@ -372,9 +386,13 @@ std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script)
// Decompose OP_EQUALVERIFY into OP_EQUAL OP_VERIFY
out.emplace_back(OP_EQUAL, std::vector<unsigned char>());
opcode = OP_VERIFY;
+ } else if (opcode == OP_NUMEQUALVERIFY) {
+ // Decompose OP_NUMEQUALVERIFY into OP_NUMEQUAL OP_VERIFY
+ out.emplace_back(OP_NUMEQUAL, std::vector<unsigned char>());
+ opcode = OP_VERIFY;
} else if (IsPushdataOp(opcode)) {
if (!CheckMinimalPush(push_data, opcode)) return {};
- } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL) && (*it == OP_VERIFY)) {
+ } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL || opcode == OP_NUMEQUAL) && (*it == OP_VERIFY)) {
// Rule out non minimal VERIFY sequences
return {};
}
diff --git a/src/script/miniscript.h b/src/script/miniscript.h
index 4c6bd0bb1d..d6bded959d 100644
--- a/src/script/miniscript.h
+++ b/src/script/miniscript.h
@@ -20,6 +20,7 @@
#include <primitives/transaction.h>
#include <script/script.h>
#include <span.h>
+#include <util/check.h>
#include <util/spanparsing.h>
#include <util/strencodings.h>
#include <util/string.h>
@@ -44,8 +45,8 @@ namespace miniscript {
* - When satisfied, pushes nothing.
* - Cannot be dissatisfied.
* - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode
- * of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY
- * and OP_EQUAL), or by combining a V fragment under some conditions.
+ * of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY,
+ * OP_NUMEQUAL and OP_EQUAL), or by combining a V fragment under some conditions.
* - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY
* - "K" Key:
* - Takes its inputs from the top of the stack.
@@ -216,7 +217,8 @@ enum class Fragment {
OR_I, //!< OP_IF [X] OP_ELSE [Y] OP_ENDIF
ANDOR, //!< [X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
THRESH, //!< [X1] ([Xn] OP_ADD)* [k] OP_EQUAL
- MULTI, //!< [k] [key_n]* [n] OP_CHECKMULTISIG
+ MULTI, //!< [k] [key_n]* [n] OP_CHECKMULTISIG (only available within P2WSH context)
+ MULTI_A, //!< [key_0] OP_CHECKSIG ([key_n] OP_CHECKSIGADD)* [k] OP_NUMEQUAL (only within Tapscript ctx)
// AND_N(X,Y) is represented as ANDOR(X,Y,0)
// WRAP_T(X) is represented as AND_V(X,1)
// WRAP_L(X) is represented as OR_I(0,X)
@@ -229,13 +231,56 @@ enum class Availability {
MAYBE,
};
+enum class MiniscriptContext {
+ P2WSH,
+ TAPSCRIPT,
+};
+
+/** Whether the context Tapscript, ensuring the only other possibility is P2WSH. */
+constexpr bool IsTapscript(MiniscriptContext ms_ctx)
+{
+ switch (ms_ctx) {
+ case MiniscriptContext::P2WSH: return false;
+ case MiniscriptContext::TAPSCRIPT: return true;
+ }
+ assert(false);
+}
+
namespace internal {
+//! The maximum size of a witness item for a Miniscript under Tapscript context. (A BIP340 signature with a sighash type byte.)
+static constexpr uint32_t MAX_TAPMINISCRIPT_STACK_ELEM_SIZE{65};
+
+//! nVersion + nLockTime
+constexpr uint32_t TX_OVERHEAD{4 + 4};
+//! prevout + nSequence + scriptSig
+constexpr uint32_t TXIN_BYTES_NO_WITNESS{36 + 4 + 1};
+//! nValue + script len + OP_0 + pushdata 32.
+constexpr uint32_t P2WSH_TXOUT_BYTES{8 + 1 + 1 + 33};
+//! Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout + segwit marker
+constexpr uint32_t TX_BODY_LEEWAY_WEIGHT{(TX_OVERHEAD + GetSizeOfCompactSize(1) + TXIN_BYTES_NO_WITNESS + GetSizeOfCompactSize(1) + P2WSH_TXOUT_BYTES) * WITNESS_SCALE_FACTOR + 2};
+//! Maximum possible stack size to spend a Taproot output (excluding the script itself).
+constexpr uint32_t MAX_TAPSCRIPT_SAT_SIZE{GetSizeOfCompactSize(MAX_STACK_SIZE) + (GetSizeOfCompactSize(MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) + MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) * MAX_STACK_SIZE + GetSizeOfCompactSize(TAPROOT_CONTROL_MAX_SIZE) + TAPROOT_CONTROL_MAX_SIZE};
+/** The maximum size of a script depending on the context. */
+constexpr uint32_t MaxScriptSize(MiniscriptContext ms_ctx)
+{
+ if (IsTapscript(ms_ctx)) {
+ // Leaf scripts under Tapscript are not explicitly limited in size. They are only implicitly
+ // bounded by the maximum standard size of a spending transaction. Let the maximum script
+ // size conservatively be small enough such that even a maximum sized witness and a reasonably
+ // sized spending transaction can spend an output paying to this script without running into
+ // the maximum standard tx size limit.
+ constexpr auto max_size{MAX_STANDARD_TX_WEIGHT - TX_BODY_LEEWAY_WEIGHT - MAX_TAPSCRIPT_SAT_SIZE};
+ return max_size - GetSizeOfCompactSize(max_size);
+ }
+ return MAX_STANDARD_P2WSH_SCRIPT_SIZE;
+}
+
//! Helper function for Node::CalcType.
-Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys);
+Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx);
//! Helper function for Node::CalcScriptLen.
-size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
+size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx);
//! A helper sanitizer/checker for the output of CalcType.
Type SanitizeType(Type x);
@@ -328,13 +373,112 @@ struct Ops {
Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
};
+/** A data structure to help the calculation of stack size limits.
+ *
+ * Conceptually, every SatInfo object corresponds to a (possibly empty) set of script execution
+ * traces (sequences of opcodes).
+ * - SatInfo{} corresponds to the empty set.
+ * - SatInfo{n, e} corresponds to a single trace whose net effect is removing n elements from the
+ * stack (may be negative for a net increase), and reaches a maximum of e stack elements more
+ * than it ends with.
+ * - operator| is the union operation: (a | b) corresponds to the union of the traces in a and the
+ * traces in b.
+ * - operator+ is the concatenation operator: (a + b) corresponds to the set of traces formed by
+ * concatenating any trace in a with any trace in b.
+ *
+ * Its fields are:
+ * - valid is true if the set is non-empty.
+ * - netdiff (if valid) is the largest difference between stack size at the beginning and at the
+ * end of the script across all traces in the set.
+ * - exec (if valid) is the largest difference between stack size anywhere during execution and at
+ * the end of the script, across all traces in the set (note that this is not necessarily due
+ * to the same trace as the one that resulted in the value for netdiff).
+ *
+ * This allows us to build up stack size limits for any script efficiently, by starting from the
+ * individual opcodes miniscripts correspond to, using concatenation to construct scripts, and
+ * using the union operation to choose between execution branches. Since any top-level script
+ * satisfaction ends with a single stack element, we know that for a full script:
+ * - netdiff+1 is the maximal initial stack size (relevant for P2WSH stack limits).
+ * - exec+1 is the maximal stack size reached during execution (relevant for P2TR stack limits).
+ *
+ * Mathematically, SatInfo forms a semiring:
+ * - operator| is the semiring addition operator, with identity SatInfo{}, and which is commutative
+ * and associative.
+ * - operator+ is the semiring multiplication operator, with identity SatInfo{0}, and which is
+ * associative.
+ * - operator+ is distributive over operator|, so (a + (b | c)) = (a+b | a+c). This means we do not
+ * need to actually materialize all possible full execution traces over the whole script (which
+ * may be exponential in the length of the script); instead we can use the union operation at the
+ * individual subexpression level, and concatenate the result with subexpressions before and
+ * after it.
+ * - It is not a commutative semiring, because a+b can differ from b+a. For example, "OP_1 OP_DROP"
+ * has exec=1, while "OP_DROP OP_1" has exec=0.
+ */
+struct SatInfo {
+ //! Whether a canonical satisfaction/dissatisfaction is possible at all.
+ const bool valid;
+ //! How much higher the stack size at start of execution can be compared to at the end.
+ const int32_t netdiff;
+ //! Mow much higher the stack size can be during execution compared to at the end.
+ const int32_t exec;
+
+ /** Empty script set. */
+ constexpr SatInfo() noexcept : valid(false), netdiff(0), exec(0) {}
+
+ /** Script set with a single script in it, with specified netdiff and exec. */
+ constexpr SatInfo(int32_t in_netdiff, int32_t in_exec) noexcept :
+ valid{true}, netdiff{in_netdiff}, exec{in_exec} {}
+
+ /** Script set union. */
+ constexpr friend SatInfo operator|(const SatInfo& a, const SatInfo& b) noexcept
+ {
+ // Union with an empty set is itself.
+ if (!a.valid) return b;
+ if (!b.valid) return a;
+ // Otherwise the netdiff and exec of the union is the maximum of the individual values.
+ return {std::max(a.netdiff, b.netdiff), std::max(a.exec, b.exec)};
+ }
+
+ /** Script set concatenation. */
+ constexpr friend SatInfo operator+(const SatInfo& a, const SatInfo& b) noexcept
+ {
+ // Concatenation with an empty set yields an empty set.
+ if (!a.valid || !b.valid) return {};
+ // Otherwise, the maximum stack size difference for the combined scripts is the sum of the
+ // netdiffs, and the maximum stack size difference anywhere is either b.exec (if the
+ // maximum occurred in b) or b.netdiff+a.exec (if the maximum occurred in a).
+ return {a.netdiff + b.netdiff, std::max(b.exec, b.netdiff + a.exec)};
+ }
+
+ /** The empty script. */
+ static constexpr SatInfo Empty() noexcept { return {0, 0}; }
+ /** A script consisting of a single push opcode. */
+ static constexpr SatInfo Push() noexcept { return {-1, 0}; }
+ /** A script consisting of a single hash opcode. */
+ static constexpr SatInfo Hash() noexcept { return {0, 0}; }
+ /** A script consisting of just a repurposed nop (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY). */
+ static constexpr SatInfo Nop() noexcept { return {0, 0}; }
+ /** A script consisting of just OP_IF or OP_NOTIF. Note that OP_ELSE and OP_ENDIF have no stack effect. */
+ static constexpr SatInfo If() noexcept { return {1, 1}; }
+ /** A script consisting of just a binary operator (OP_BOOLAND, OP_BOOLOR, OP_ADD). */
+ static constexpr SatInfo BinaryOp() noexcept { return {1, 1}; }
+
+ // Scripts for specific individual opcodes.
+ static constexpr SatInfo OP_DUP() noexcept { return {-1, 0}; }
+ static constexpr SatInfo OP_IFDUP(bool nonzero) noexcept { return {nonzero ? -1 : 0, 0}; }
+ static constexpr SatInfo OP_EQUALVERIFY() noexcept { return {2, 2}; }
+ static constexpr SatInfo OP_EQUAL() noexcept { return {1, 1}; }
+ static constexpr SatInfo OP_SIZE() noexcept { return {-1, 0}; }
+ static constexpr SatInfo OP_CHECKSIG() noexcept { return {1, 1}; }
+ static constexpr SatInfo OP_0NOTEQUAL() noexcept { return {0, 0}; }
+ static constexpr SatInfo OP_VERIFY() noexcept { return {1, 1}; }
+};
+
struct StackSize {
- //! Maximum stack size to satisfy;
- MaxInt<uint32_t> sat;
- //! Maximum stack size to dissatisfy;
- MaxInt<uint32_t> dsat;
+ const SatInfo sat, dsat;
- StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
+ constexpr StackSize(SatInfo in_sat, SatInfo in_dsat) noexcept : sat(in_sat), dsat(in_dsat) {};
+ constexpr StackSize(SatInfo in_both) noexcept : sat(in_both), dsat(in_both) {};
};
struct WitnessSize {
@@ -362,7 +506,22 @@ struct Node {
//! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
const std::vector<unsigned char> data;
//! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
- const std::vector<NodeRef<Key>> subs;
+ mutable std::vector<NodeRef<Key>> subs;
+ //! The Script context for this node. Either P2WSH or Tapscript.
+ const MiniscriptContext m_script_ctx;
+
+ /* Destroy the shared pointers iteratively to avoid a stack-overflow due to recursive calls
+ * to the subs' destructors. */
+ ~Node() {
+ while (!subs.empty()) {
+ auto node = std::move(subs.back());
+ subs.pop_back();
+ while (!node->subs.empty()) {
+ subs.push_back(std::move(node->subs.back()));
+ node->subs.pop_back();
+ }
+ }
+ }
private:
//! Cached ops counts.
@@ -390,7 +549,7 @@ private:
subsize += sub->ScriptSize();
}
Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
- return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size());
+ return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size(), m_script_ctx);
}
/* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
@@ -557,7 +716,7 @@ private:
Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
- return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
+ return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size(), m_script_ctx));
}
public:
@@ -578,7 +737,8 @@ public:
};
// The upward function computes for a node, given its followed-by-OP_VERIFY status
// and the CScripts of its child nodes, the CScript of the node.
- auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
+ const bool is_tapscript{IsTapscript(m_script_ctx)};
+ auto upfn = [&ctx, is_tapscript](bool verify, const Node& node, Span<CScript> subs) -> CScript {
switch (node.fragment) {
case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
@@ -611,12 +771,21 @@ public:
case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
case Fragment::MULTI: {
+ CHECK_NONFATAL(!is_tapscript);
CScript script = BuildScript(node.k);
for (const auto& key : node.keys) {
script = BuildScript(std::move(script), ctx.ToPKBytes(key));
}
return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
}
+ case Fragment::MULTI_A: {
+ CHECK_NONFATAL(is_tapscript);
+ CScript script = BuildScript(ctx.ToPKBytes(*node.keys.begin()), OP_CHECKSIG);
+ for (auto it = node.keys.begin() + 1; it != node.keys.end(); ++it) {
+ script = BuildScript(std::move(script), ctx.ToPKBytes(*it), OP_CHECKSIGADD);
+ }
+ return BuildScript(std::move(script), node.k, verify ? OP_NUMEQUALVERIFY : OP_NUMEQUAL);
+ }
case Fragment::THRESH: {
CScript script = std::move(subs[0]);
for (size_t i = 1; i < subs.size(); ++i) {
@@ -646,7 +815,8 @@ public:
};
// The upward function computes for a node, given whether its parent is a wrapper,
// and the string representations of its child nodes, the string representation of the node.
- auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
+ const bool is_tapscript{IsTapscript(m_script_ctx)};
+ auto upfn = [&ctx, is_tapscript](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
std::string ret = wrapped ? ":" : "";
switch (node.fragment) {
@@ -710,6 +880,7 @@ public:
if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
case Fragment::MULTI: {
+ CHECK_NONFATAL(!is_tapscript);
auto str = std::move(ret) + "multi(" + ::ToString(node.k);
for (const auto& key : node.keys) {
auto key_str = ctx.ToString(key);
@@ -718,6 +889,16 @@ public:
}
return std::move(str) + ")";
}
+ case Fragment::MULTI_A: {
+ CHECK_NONFATAL(is_tapscript);
+ auto str = std::move(ret) + "multi_a(" + ::ToString(node.k);
+ for (const auto& key : node.keys) {
+ auto key_str = ctx.ToString(key);
+ if (!key_str) return {};
+ str += "," + std::move(*key_str);
+ }
+ return std::move(str) + ")";
+ }
case Fragment::THRESH: {
auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
for (auto& sub : subs) {
@@ -783,6 +964,7 @@ private:
return {count, sat, dsat};
}
case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
+ case Fragment::MULTI_A: return {(uint32_t)keys.size() + 1, 0, 0};
case Fragment::WRAP_S:
case Fragment::WRAP_C:
case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
@@ -808,50 +990,115 @@ private:
}
internal::StackSize CalcStackSize() const {
+ using namespace internal;
switch (fragment) {
- case Fragment::JUST_0: return {{}, 0};
- case Fragment::JUST_1:
+ case Fragment::JUST_0: return {{}, SatInfo::Push()};
+ case Fragment::JUST_1: return {SatInfo::Push(), {}};
case Fragment::OLDER:
- case Fragment::AFTER: return {0, {}};
- case Fragment::PK_K: return {1, 1};
- case Fragment::PK_H: return {2, 2};
+ case Fragment::AFTER: return {SatInfo::Push() + SatInfo::Nop(), {}};
+ case Fragment::PK_K: return {SatInfo::Push()};
+ case Fragment::PK_H: return {SatInfo::OP_DUP() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY()};
case Fragment::SHA256:
case Fragment::RIPEMD160:
case Fragment::HASH256:
- case Fragment::HASH160: return {1, {}};
+ case Fragment::HASH160: return {
+ SatInfo::OP_SIZE() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUAL(),
+ {}
+ };
case Fragment::ANDOR: {
- const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
- const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
- return {sat, dsat};
+ const auto& x{subs[0]->ss};
+ const auto& y{subs[1]->ss};
+ const auto& z{subs[2]->ss};
+ return {
+ (x.sat + SatInfo::If() + y.sat) | (x.dsat + SatInfo::If() + z.sat),
+ x.dsat + SatInfo::If() + z.dsat
+ };
+ }
+ case Fragment::AND_V: {
+ const auto& x{subs[0]->ss};
+ const auto& y{subs[1]->ss};
+ return {x.sat + y.sat, {}};
+ }
+ case Fragment::AND_B: {
+ const auto& x{subs[0]->ss};
+ const auto& y{subs[1]->ss};
+ return {x.sat + y.sat + SatInfo::BinaryOp(), x.dsat + y.dsat + SatInfo::BinaryOp()};
}
- case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
- case Fragment::AND_B: return {subs[0]->ss.sat + subs[1]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.dsat};
case Fragment::OR_B: {
- const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
- const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
- return {sat, dsat};
+ const auto& x{subs[0]->ss};
+ const auto& y{subs[1]->ss};
+ return {
+ ((x.sat + y.dsat) | (x.dsat + y.sat)) + SatInfo::BinaryOp(),
+ x.dsat + y.dsat + SatInfo::BinaryOp()
+ };
}
- case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
- case Fragment::OR_D: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), subs[0]->ss.dsat + subs[1]->ss.dsat};
- case Fragment::OR_I: return {(subs[0]->ss.sat + 1) | (subs[1]->ss.sat + 1), (subs[0]->ss.dsat + 1) | (subs[1]->ss.dsat + 1)};
- case Fragment::MULTI: return {k + 1, k + 1};
+ case Fragment::OR_C: {
+ const auto& x{subs[0]->ss};
+ const auto& y{subs[1]->ss};
+ return {(x.sat + SatInfo::If()) | (x.dsat + SatInfo::If() + y.sat), {}};
+ }
+ case Fragment::OR_D: {
+ const auto& x{subs[0]->ss};
+ const auto& y{subs[1]->ss};
+ return {
+ (x.sat + SatInfo::OP_IFDUP(true) + SatInfo::If()) | (x.dsat + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.sat),
+ x.dsat + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.dsat
+ };
+ }
+ case Fragment::OR_I: {
+ const auto& x{subs[0]->ss};
+ const auto& y{subs[1]->ss};
+ return {SatInfo::If() + (x.sat | y.sat), SatInfo::If() + (x.dsat | y.dsat)};
+ }
+ // multi(k, key1, key2, ..., key_n) starts off with k+1 stack elements (a 0, plus k
+ // signatures), then reaches n+k+3 stack elements after pushing the n keys, plus k and
+ // n itself, and ends with 1 stack element (success or failure). Thus, it net removes
+ // k elements (from k+1 to 1), while reaching k+n+2 more than it ends with.
+ case Fragment::MULTI: return {SatInfo(k, k + keys.size() + 2)};
+ // multi_a(k, key1, key2, ..., key_n) starts off with n stack elements (the
+ // signatures), reaches 1 more (after the first key push), and ends with 1. Thus it net
+ // removes n-1 elements (from n to 1) while reaching n more than it ends with.
+ case Fragment::MULTI_A: return {SatInfo(keys.size() - 1, keys.size())};
case Fragment::WRAP_A:
case Fragment::WRAP_N:
- case Fragment::WRAP_S:
- case Fragment::WRAP_C: return subs[0]->ss;
- case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
- case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
- case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
+ case Fragment::WRAP_S: return subs[0]->ss;
+ case Fragment::WRAP_C: return {
+ subs[0]->ss.sat + SatInfo::OP_CHECKSIG(),
+ subs[0]->ss.dsat + SatInfo::OP_CHECKSIG()
+ };
+ case Fragment::WRAP_D: return {
+ SatInfo::OP_DUP() + SatInfo::If() + subs[0]->ss.sat,
+ SatInfo::OP_DUP() + SatInfo::If()
+ };
+ case Fragment::WRAP_V: return {subs[0]->ss.sat + SatInfo::OP_VERIFY(), {}};
+ case Fragment::WRAP_J: return {
+ SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If() + subs[0]->ss.sat,
+ SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If()
+ };
case Fragment::THRESH: {
- auto sats = Vector(internal::MaxInt<uint32_t>(0));
- for (const auto& sub : subs) {
- auto next_sats = Vector(sats[0] + sub->ss.dsat);
- for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ss.dsat) | (sats[j - 1] + sub->ss.sat));
- next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
+ // sats[j] is the SatInfo corresponding to all traces reaching j satisfactions.
+ auto sats = Vector(SatInfo::Empty());
+ for (size_t i = 0; i < subs.size(); ++i) {
+ // Loop over the subexpressions, processing them one by one. After adding
+ // element i we need to add OP_ADD (if i>0).
+ auto add = i ? SatInfo::BinaryOp() : SatInfo::Empty();
+ // Construct a variable that will become the next sats, starting with index 0.
+ auto next_sats = Vector(sats[0] + subs[i]->ss.dsat + add);
+ // Then loop to construct next_sats[1..i].
+ for (size_t j = 1; j < sats.size(); ++j) {
+ next_sats.push_back(((sats[j] + subs[i]->ss.dsat) | (sats[j - 1] + subs[i]->ss.sat)) + add);
+ }
+ // Finally construct next_sats[i+1].
+ next_sats.push_back(sats[sats.size() - 1] + subs[i]->ss.sat + add);
+ // Switch over.
sats = std::move(next_sats);
}
- assert(k <= sats.size());
- return {sats[k], sats[0]};
+ // To satisfy thresh we need k satisfactions; to dissatisfy we need 0. In both
+ // cases a push of k and an OP_EQUAL follow.
+ return {
+ sats[k] + SatInfo::Push() + SatInfo::OP_EQUAL(),
+ sats[0] + SatInfo::Push() + SatInfo::OP_EQUAL()
+ };
}
}
assert(false);
@@ -885,6 +1132,7 @@ private:
case Fragment::OR_D: return {subs[0]->ws.sat | (subs[0]->ws.dsat + subs[1]->ws.sat), subs[0]->ws.dsat + subs[1]->ws.dsat};
case Fragment::OR_I: return {(subs[0]->ws.sat + 1 + 1) | (subs[1]->ws.sat + 1), (subs[0]->ws.dsat + 1 + 1) | (subs[1]->ws.dsat + 1)};
case Fragment::MULTI: return {k * (1 + 72) + 1, k + 1};
+ case Fragment::MULTI_A: return {k * (1 + 65) + static_cast<uint32_t>(keys.size()) - k, static_cast<uint32_t>(keys.size())};
case Fragment::WRAP_A:
case Fragment::WRAP_N:
case Fragment::WRAP_S:
@@ -925,6 +1173,34 @@ private:
Availability avail = ctx.Sign(node.keys[0], sig);
return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)};
}
+ case Fragment::MULTI_A: {
+ // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
+ // In the loop below, these stacks are built up using a dynamic programming approach.
+ std::vector<InputStack> sats = Vector(EMPTY);
+ for (size_t i = 0; i < node.keys.size(); ++i) {
+ // Get the signature for the i'th key in reverse order (the signature for the first key needs to
+ // be at the top of the stack, contrary to CHECKMULTISIG's satisfaction).
+ std::vector<unsigned char> sig;
+ Availability avail = ctx.Sign(node.keys[node.keys.size() - 1 - i], sig);
+ // Compute signature stack for just this key.
+ auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
+ // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
+ // next_sats[j] are equal to either the existing sats[j] + ZERO, or sats[j-1] plus a signature
+ // for the current (i'th) key. The very last element needs all signatures filled.
+ std::vector<InputStack> next_sats;
+ next_sats.push_back(sats[0] + ZERO);
+ for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + ZERO) | (std::move(sats[j - 1]) + sat));
+ next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
+ // Switch over.
+ sats = std::move(next_sats);
+ }
+ // The dissatisfaction consists of as many empty vectors as there are keys, which is the same as
+ // satisfying 0 keys.
+ auto& nsat{sats[0]};
+ assert(node.k != 0);
+ assert(node.k <= sats.size());
+ return {std::move(nsat), std::move(sats[node.k])};
+ }
case Fragment::MULTI: {
// sats[j] represents the best stack containing j valid signatures (out of the first i keys).
// In the loop below, these stacks are built up using a dynamic programming approach.
@@ -1205,19 +1481,36 @@ public:
//! Check the ops limit of this script against the consensus limit.
bool CheckOpsLimit() const {
+ if (IsTapscript(m_script_ctx)) return true;
if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
return true;
}
- /** Return the maximum number of stack elements needed to satisfy this script non-malleably.
- * This does not account for the P2WSH script push. */
+ /** Whether this node is of type B, K or W. (That is, anything but V.) */
+ bool IsBKW() const {
+ return !((GetType() & "BKW"_mst) == ""_mst);
+ }
+
+ /** Return the maximum number of stack elements needed to satisfy this script non-malleably. */
std::optional<uint32_t> GetStackSize() const {
if (!ss.sat.valid) return {};
- return ss.sat.value;
+ return ss.sat.netdiff + static_cast<int32_t>(IsBKW());
+ }
+
+ //! Return the maximum size of the stack during execution of this script.
+ std::optional<uint32_t> GetExecStackSize() const {
+ if (!ss.sat.valid) return {};
+ return ss.sat.exec + static_cast<int32_t>(IsBKW());
}
//! Check the maximum stack size for this script against the policy limit.
bool CheckStackSize() const {
+ // Since in Tapscript there is no standardness limit on the script and witness sizes, we may run
+ // into the maximum stack size while executing the script. Make sure it doesn't happen.
+ if (IsTapscript(m_script_ctx)) {
+ if (const auto exec_ss = GetExecStackSize()) return exec_ss <= MAX_STACK_SIZE;
+ return true;
+ }
if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS;
return true;
}
@@ -1235,6 +1528,9 @@ public:
//! Return the expression type.
Type GetType() const { return typ; }
+ //! Return the script context for this node.
+ MiniscriptContext GetMsCtx() const { return m_script_ctx; }
+
//! Find an insane subnode which has no insane children. Nullptr if there is none.
const Node* FindInsaneSub() const {
return TreeEval<const Node*>([](const Node& node, Span<const Node*> subs) -> const Node* {
@@ -1259,6 +1555,7 @@ public:
case Fragment::PK_K:
case Fragment::PK_H:
case Fragment::MULTI:
+ case Fragment::MULTI_A:
case Fragment::AFTER:
case Fragment::OLDER:
case Fragment::HASH256:
@@ -1286,7 +1583,10 @@ public:
}
//! Check whether this node is valid at all.
- bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }
+ bool IsValid() const {
+ if (GetType() == ""_mst) return false;
+ return ScriptSize() <= internal::MaxScriptSize(m_script_ctx);
+ }
//! Check whether this node is valid as a script on its own.
bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
@@ -1328,20 +1628,32 @@ public:
bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; }
// Constructors with various argument combinations, which bypass the duplicate key check.
- Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
- Node(internal::NoDupCheck, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
- Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
- Node(internal::NoDupCheck, Fragment nt, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
- Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : fragment(nt), k(val), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
- Node(internal::NoDupCheck, Fragment nt, uint32_t val = 0) : fragment(nt), k(val), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0)
+ : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
+ : fragment(nt), k(val), data(std::move(arg)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0)
+ : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0)
+ : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0)
+ : fragment(nt), k(val), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, uint32_t val = 0)
+ : fragment(nt), k(val), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
// Constructors with various argument combinations, which do perform the duplicate key check.
- template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
- template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
- template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
- template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
- template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
- template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, val) { DuplicateKeyCheck(ctx); }
+ template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0)
+ : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
+ template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
+ : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
+ template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0)
+ : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
+ template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0)
+ : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
+ template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0)
+ : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
+ template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0)
+ : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, val) { DuplicateKeyCheck(ctx); }
};
namespace internal {
@@ -1429,14 +1741,14 @@ std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<co
/** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */
template<typename Key>
-void BuildBack(Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
+void BuildBack(const MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
{
NodeRef<Key> child = std::move(constructed.back());
constructed.pop_back();
if (reverse) {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(child), std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(child), std::move(constructed.back())));
} else {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(constructed.back()), std::move(child)));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(constructed.back()), std::move(child)));
}
}
@@ -1461,6 +1773,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
// (instead transforming another opcode into its VERIFY form). However, the v: wrapper has
// to be interleaved with other fragments to be valid, so this is not a concern.
size_t script_size{1};
+ size_t max_size{internal::MaxScriptSize(ctx.MsContext())};
// The two integers are used to hold state for thresh()
std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
@@ -1468,8 +1781,43 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+ // Parses a multi() or multi_a() from its string representation. Returns false on parsing error.
+ const auto parse_multi_exp = [&](Span<const char>& in, const bool is_multi_a) -> bool {
+ const auto max_keys{is_multi_a ? MAX_PUBKEYS_PER_MULTI_A : MAX_PUBKEYS_PER_MULTISIG};
+ const auto required_ctx{is_multi_a ? MiniscriptContext::TAPSCRIPT : MiniscriptContext::P2WSH};
+ if (ctx.MsContext() != required_ctx) return false;
+ // Get threshold
+ int next_comma = FindNextChar(in, ',');
+ if (next_comma < 1) return false;
+ int64_t k;
+ if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return false;
+ in = in.subspan(next_comma + 1);
+ // Get keys. It is compatible for both compressed and x-only keys.
+ std::vector<Key> keys;
+ while (next_comma != -1) {
+ next_comma = FindNextChar(in, ',');
+ int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
+ if (key_length < 1) return false;
+ auto key = ctx.FromString(in.begin(), in.begin() + key_length);
+ if (!key) return false;
+ keys.push_back(std::move(*key));
+ in = in.subspan(key_length + 1);
+ }
+ if (keys.size() < 1 || keys.size() > max_keys) return false;
+ if (k < 1 || k > (int64_t)keys.size()) return false;
+ if (is_multi_a) {
+ // (push + xonly-key + CHECKSIG[ADD]) * n + k + OP_NUMEQUAL(VERIFY), minus one.
+ script_size += (1 + 32 + 1) * keys.size() + BuildScript(k).size();
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), k));
+ } else {
+ script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), k));
+ }
+ return true;
+ };
+
while (!to_parse.empty()) {
- if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
+ if (script_size > max_size) return {};
// Get the current context we are decoding within
auto [cur_context, n, k] = to_parse.back();
@@ -1488,7 +1836,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
// If there is no colon, this loop won't execute
bool last_was_v{false};
for (size_t j = 0; colon_index && j < *colon_index; ++j) {
- if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
+ if (script_size > max_size) return {};
if (in[j] == 'a') {
script_size += 2;
to_parse.emplace_back(ParseContext::ALT, -1, -1);
@@ -1521,7 +1869,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
} else if (in[j] == 'l') {
// The l: wrapper is equivalent to or_i(0,X)
script_size += 4;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
to_parse.emplace_back(ParseContext::OR_I, -1, -1);
} else {
return {};
@@ -1534,63 +1882,63 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
}
case ParseContext::EXPR: {
if (Const("0", in)) {
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
} else if (Const("1", in)) {
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1));
} else if (Const("pk(", in)) {
auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
if (!res) return {};
auto& [key, key_size] = *res;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))))));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(key))))));
in = in.subspan(key_size + 1);
- script_size += 34;
+ script_size += IsTapscript(ctx.MsContext()) ? 33 : 34;
} else if (Const("pkh(", in)) {
auto res = ParseKeyEnd<Key>(in, ctx);
if (!res) return {};
auto& [key, key_size] = *res;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))))));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(key))))));
in = in.subspan(key_size + 1);
script_size += 24;
} else if (Const("pk_k(", in)) {
auto res = ParseKeyEnd<Key>(in, ctx);
if (!res) return {};
auto& [key, key_size] = *res;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(key))));
in = in.subspan(key_size + 1);
- script_size += 33;
+ script_size += IsTapscript(ctx.MsContext()) ? 32 : 33;
} else if (Const("pk_h(", in)) {
auto res = ParseKeyEnd<Key>(in, ctx);
if (!res) return {};
auto& [key, key_size] = *res;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(key))));
in = in.subspan(key_size + 1);
script_size += 23;
} else if (Const("sha256(", in)) {
auto res = ParseHexStrEnd(in, 32, ctx);
if (!res) return {};
auto& [hash, hash_size] = *res;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, std::move(hash)));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, std::move(hash)));
in = in.subspan(hash_size + 1);
script_size += 38;
} else if (Const("ripemd160(", in)) {
auto res = ParseHexStrEnd(in, 20, ctx);
if (!res) return {};
auto& [hash, hash_size] = *res;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, std::move(hash)));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, std::move(hash)));
in = in.subspan(hash_size + 1);
script_size += 26;
} else if (Const("hash256(", in)) {
auto res = ParseHexStrEnd(in, 32, ctx);
if (!res) return {};
auto& [hash, hash_size] = *res;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, std::move(hash)));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, std::move(hash)));
in = in.subspan(hash_size + 1);
script_size += 38;
} else if (Const("hash160(", in)) {
auto res = ParseHexStrEnd(in, 20, ctx);
if (!res) return {};
auto& [hash, hash_size] = *res;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, std::move(hash)));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, std::move(hash)));
in = in.subspan(hash_size + 1);
script_size += 26;
} else if (Const("after(", in)) {
@@ -1599,7 +1947,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
int64_t num;
if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
if (num < 1 || num >= 0x80000000L) return {};
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, num));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, num));
in = in.subspan(arg_size + 1);
script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
} else if (Const("older(", in)) {
@@ -1608,30 +1956,13 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
int64_t num;
if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
if (num < 1 || num >= 0x80000000L) return {};
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, num));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, num));
in = in.subspan(arg_size + 1);
script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
} else if (Const("multi(", in)) {
- // Get threshold
- int next_comma = FindNextChar(in, ',');
- if (next_comma < 1) return {};
- if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
- in = in.subspan(next_comma + 1);
- // Get keys
- std::vector<Key> keys;
- while (next_comma != -1) {
- next_comma = FindNextChar(in, ',');
- int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
- if (key_length < 1) return {};
- auto key = ctx.FromString(in.begin(), in.begin() + key_length);
- if (!key) return {};
- keys.push_back(std::move(*key));
- in = in.subspan(key_length + 1);
- }
- if (keys.size() < 1 || keys.size() > 20) return {};
- if (k < 1 || k > (int64_t)keys.size()) return {};
- script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), k));
+ if (!parse_multi_exp(in, /* is_multi_a = */false)) return {};
+ } else if (Const("multi_a(", in)) {
+ if (!parse_multi_exp(in, /* is_multi_a = */true)) return {};
} else if (Const("thresh(", in)) {
int next_comma = FindNextChar(in, ',');
if (next_comma < 1) return {};
@@ -1684,70 +2015,70 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
break;
}
case ParseContext::ALT: {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back())));
break;
}
case ParseContext::SWAP: {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back())));
break;
}
case ParseContext::CHECK: {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back())));
break;
}
case ParseContext::DUP_IF: {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back())));
break;
}
case ParseContext::NON_ZERO: {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back())));
break;
}
case ParseContext::ZERO_NOTEQUAL: {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back())));
break;
}
case ParseContext::VERIFY: {
script_size += (constructed.back()->GetType() << "x"_mst);
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back())));
break;
}
case ParseContext::WRAP_U: {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0)));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0)));
break;
}
case ParseContext::WRAP_T: {
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1)));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1)));
break;
}
case ParseContext::AND_B: {
- BuildBack(Fragment::AND_B, constructed);
+ BuildBack(ctx.MsContext(), Fragment::AND_B, constructed);
break;
}
case ParseContext::AND_N: {
auto mid = std::move(constructed.back());
constructed.pop_back();
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(ctx, Fragment::JUST_0)));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0)));
break;
}
case ParseContext::AND_V: {
- BuildBack(Fragment::AND_V, constructed);
+ BuildBack(ctx.MsContext(), Fragment::AND_V, constructed);
break;
}
case ParseContext::OR_B: {
- BuildBack(Fragment::OR_B, constructed);
+ BuildBack(ctx.MsContext(), Fragment::OR_B, constructed);
break;
}
case ParseContext::OR_C: {
- BuildBack(Fragment::OR_C, constructed);
+ BuildBack(ctx.MsContext(), Fragment::OR_C, constructed);
break;
}
case ParseContext::OR_D: {
- BuildBack(Fragment::OR_D, constructed);
+ BuildBack(ctx.MsContext(), Fragment::OR_D, constructed);
break;
}
case ParseContext::OR_I: {
- BuildBack(Fragment::OR_I, constructed);
+ BuildBack(ctx.MsContext(), Fragment::OR_I, constructed);
break;
}
case ParseContext::ANDOR: {
@@ -1755,7 +2086,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
constructed.pop_back();
auto mid = std::move(constructed.back());
constructed.pop_back();
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
break;
}
case ParseContext::THRESH: {
@@ -1775,7 +2106,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
constructed.pop_back();
}
std::reverse(subs.begin(), subs.end());
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k));
} else {
return {};
}
@@ -1808,8 +2139,8 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
* Construct a vector with one element per opcode in the script, in reverse order.
* Each element is a pair consisting of the opcode, as well as the data pushed by
* the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY,
- * and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, OP_EQUAL
- * respectively, plus OP_VERIFY.
+ * OP_NUMEQUALVERIFY and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG,
+ * OP_EQUAL and OP_NUMEQUAL respectively, plus OP_VERIFY.
*/
std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
@@ -1911,27 +2242,27 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
// Constants
if (in[0].first == OP_1) {
++in;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1));
break;
}
if (in[0].first == OP_0) {
++in;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
break;
}
// Public keys
- if (in[0].second.size() == 33) {
+ if (in[0].second.size() == 33 || in[0].second.size() == 32) {
auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
if (!key) return {};
++in;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(*key))));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))));
break;
}
if (last - in >= 5 && in[0].first == OP_VERIFY && in[1].first == OP_EQUAL && in[3].first == OP_HASH160 && in[4].first == OP_DUP && in[2].second.size() == 20) {
auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
if (!key) return {};
in += 5;
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(*key))));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))));
break;
}
// Time locks
@@ -1939,37 +2270,38 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
in += 2;
if (*num < 1 || *num > 0x7FFFFFFFL) return {};
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, *num));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num));
break;
}
if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
in += 2;
if (num < 1 || num > 0x7FFFFFFFL) return {};
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, *num));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num));
break;
}
// Hashes
if (last - in >= 7 && in[0].first == OP_EQUAL && in[3].first == OP_VERIFY && in[4].first == OP_EQUAL && (num = ParseScriptNumber(in[5])) && num == 32 && in[6].first == OP_SIZE) {
if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, in[1].second));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, in[1].second));
in += 7;
break;
} else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, in[1].second));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, in[1].second));
in += 7;
break;
} else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, in[1].second));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, in[1].second));
in += 7;
break;
} else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, in[1].second));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, in[1].second));
in += 7;
break;
}
}
// Multi
if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
+ if (IsTapscript(ctx.MsContext())) return {};
std::vector<Key> keys;
const auto n = ParseScriptNumber(in[1]);
if (!n || last - in < 3 + *n) return {};
@@ -1984,7 +2316,37 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
if (!k || *k < 1 || *k > *n) return {};
in += 3 + *n;
std::reverse(keys.begin(), keys.end());
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), *k));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), *k));
+ break;
+ }
+ // Tapscript's equivalent of multi
+ if (last - in >= 4 && in[0].first == OP_NUMEQUAL) {
+ if (!IsTapscript(ctx.MsContext())) return {};
+ // The necessary threshold of signatures.
+ const auto k = ParseScriptNumber(in[1]);
+ if (!k) return {};
+ if (*k < 1 || *k > MAX_PUBKEYS_PER_MULTI_A) return {};
+ if (last - in < 2 + *k * 2) return {};
+ std::vector<Key> keys;
+ keys.reserve(*k);
+ // Walk through the expected (pubkey, CHECKSIG[ADD]) pairs.
+ for (int pos = 2;; pos += 2) {
+ if (last - in < pos + 2) return {};
+ // Make sure it's indeed an x-only pubkey and a CHECKSIG[ADD], then parse the key.
+ if (in[pos].first != OP_CHECKSIGADD && in[pos].first != OP_CHECKSIG) return {};
+ if (in[pos + 1].second.size() != 32) return {};
+ auto key = ctx.FromPKBytes(in[pos + 1].second.begin(), in[pos + 1].second.end());
+ if (!key) return {};
+ keys.push_back(std::move(*key));
+ // Make sure early we don't parse an arbitrary large expression.
+ if (keys.size() > MAX_PUBKEYS_PER_MULTI_A) return {};
+ // OP_CHECKSIG means it was the last one to parse.
+ if (in[pos].first == OP_CHECKSIG) break;
+ }
+ if (keys.size() < (size_t)*k) return {};
+ in += 2 + keys.size() * 2;
+ std::reverse(keys.begin(), keys.end());
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), *k));
break;
}
/** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather
@@ -2079,63 +2441,63 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
case DecodeContext::SWAP: {
if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
++in;
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back())));
break;
}
case DecodeContext::ALT: {
if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
++in;
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back())));
break;
}
case DecodeContext::CHECK: {
if (constructed.empty()) return {};
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back())));
break;
}
case DecodeContext::DUP_IF: {
if (constructed.empty()) return {};
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back())));
break;
}
case DecodeContext::VERIFY: {
if (constructed.empty()) return {};
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back())));
break;
}
case DecodeContext::NON_ZERO: {
if (constructed.empty()) return {};
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back())));
break;
}
case DecodeContext::ZERO_NOTEQUAL: {
if (constructed.empty()) return {};
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back())));
break;
}
case DecodeContext::AND_V: {
if (constructed.size() < 2) return {};
- BuildBack(Fragment::AND_V, constructed, /*reverse=*/true);
+ BuildBack(ctx.MsContext(), Fragment::AND_V, constructed, /*reverse=*/true);
break;
}
case DecodeContext::AND_B: {
if (constructed.size() < 2) return {};
- BuildBack(Fragment::AND_B, constructed, /*reverse=*/true);
+ BuildBack(ctx.MsContext(), Fragment::AND_B, constructed, /*reverse=*/true);
break;
}
case DecodeContext::OR_B: {
if (constructed.size() < 2) return {};
- BuildBack(Fragment::OR_B, constructed, /*reverse=*/true);
+ BuildBack(ctx.MsContext(), Fragment::OR_B, constructed, /*reverse=*/true);
break;
}
case DecodeContext::OR_C: {
if (constructed.size() < 2) return {};
- BuildBack(Fragment::OR_C, constructed, /*reverse=*/true);
+ BuildBack(ctx.MsContext(), Fragment::OR_C, constructed, /*reverse=*/true);
break;
}
case DecodeContext::OR_D: {
if (constructed.size() < 2) return {};
- BuildBack(Fragment::OR_D, constructed, /*reverse=*/true);
+ BuildBack(ctx.MsContext(), Fragment::OR_D, constructed, /*reverse=*/true);
break;
}
case DecodeContext::ANDOR: {
@@ -2145,7 +2507,7 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
NodeRef<Key> right = std::move(constructed.back());
constructed.pop_back();
NodeRef<Key> mid = std::move(constructed.back());
- constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
+ constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
break;
}
case DecodeContext::THRESH_W: {
@@ -2169,7 +2531,7 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
constructed.pop_back();
subs.push_back(std::move(sub));
}
- constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
+ constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k));
break;
}
case DecodeContext::ENDIF: {
@@ -2219,7 +2581,7 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
if (in >= last) return {};
if (in[0].first == OP_IF) {
++in;
- BuildBack(Fragment::OR_I, constructed, /*reverse=*/true);
+ BuildBack(ctx.MsContext(), Fragment::OR_I, constructed, /*reverse=*/true);
} else if (in[0].first == OP_NOTIF) {
++in;
to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
@@ -2252,7 +2614,7 @@ template<typename Ctx>
inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
using namespace internal;
// A too large Script is necessarily invalid, don't bother parsing it.
- if (script.size() > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
+ if (script.size() > MaxScriptSize(ctx.MsContext())) return {};
auto decomposed = DecomposeScript(script);
if (!decomposed) return {};
auto it = decomposed->begin();
diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index 92b7ad50b5..248ad780c3 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -114,12 +114,17 @@ static bool GetPubKey(const SigningProvider& provider, const SignatureData& sigd
pubkey = it->second.first;
return true;
}
- // Look for pubkey in pubkey list
+ // Look for pubkey in pubkey lists
const auto& pk_it = sigdata.misc_pubkeys.find(address);
if (pk_it != sigdata.misc_pubkeys.end()) {
pubkey = pk_it->second.first;
return true;
}
+ const auto& tap_pk_it = sigdata.tap_pubkeys.find(address);
+ if (tap_pk_it != sigdata.tap_pubkeys.end()) {
+ pubkey = tap_pk_it->second.GetEvenCorrespondingCPubKey();
+ return true;
+ }
// Query the underlying provider
return provider.GetPubKey(address, pubkey);
}
@@ -171,49 +176,158 @@ static bool CreateTaprootScriptSig(const BaseSignatureCreator& creator, Signatur
return false;
}
-static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, Span<const unsigned char> script_bytes, std::vector<valtype>& result)
+template<typename M, typename K, typename V>
+miniscript::Availability MsLookupHelper(const M& map, const K& key, V& value)
{
- // Only BIP342 tapscript signing is supported for now.
- if (leaf_version != TAPROOT_LEAF_TAPSCRIPT) return false;
- SigVersion sigversion = SigVersion::TAPSCRIPT;
+ auto it = map.find(key);
+ if (it != map.end()) {
+ value = it->second;
+ return miniscript::Availability::YES;
+ }
+ return miniscript::Availability::NO;
+}
- uint256 leaf_hash = ComputeTapleafHash(leaf_version, script_bytes);
- CScript script = CScript(script_bytes.begin(), script_bytes.end());
+/**
+ * Context for solving a Miniscript.
+ * If enough material (access to keys, hash preimages, ..) is given, produces a valid satisfaction.
+ */
+template<typename Pk>
+struct Satisfier {
+ using Key = Pk;
- // <xonly pubkey> OP_CHECKSIG
- if (script.size() == 34 && script[33] == OP_CHECKSIG && script[0] == 0x20) {
- XOnlyPubKey pubkey{Span{script}.subspan(1, 32)};
- std::vector<unsigned char> sig;
- if (CreateTaprootScriptSig(creator, sigdata, provider, sig, pubkey, leaf_hash, sigversion)) {
- result = Vector(std::move(sig));
- return true;
- }
- return false;
+ const SigningProvider& m_provider;
+ SignatureData& m_sig_data;
+ const BaseSignatureCreator& m_creator;
+ const CScript& m_witness_script;
+ //! The context of the script we are satisfying (either P2WSH or Tapscript).
+ const miniscript::MiniscriptContext m_script_ctx;
+
+ explicit Satisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
+ const BaseSignatureCreator& creator LIFETIMEBOUND,
+ const CScript& witscript LIFETIMEBOUND,
+ miniscript::MiniscriptContext script_ctx) : m_provider(provider),
+ m_sig_data(sig_data),
+ m_creator(creator),
+ m_witness_script(witscript),
+ m_script_ctx(script_ctx) {}
+
+ static bool KeyCompare(const Key& a, const Key& b) {
+ return a < b;
}
- // multi_a scripts (<key> OP_CHECKSIG <key> OP_CHECKSIGADD <key> OP_CHECKSIGADD <k> OP_NUMEQUAL)
- if (auto match = MatchMultiA(script)) {
- std::vector<std::vector<unsigned char>> sigs;
- int good_sigs = 0;
- for (size_t i = 0; i < match->second.size(); ++i) {
- XOnlyPubKey pubkey{*(match->second.rbegin() + i)};
- std::vector<unsigned char> sig;
- bool good_sig = CreateTaprootScriptSig(creator, sigdata, provider, sig, pubkey, leaf_hash, sigversion);
- if (good_sig && good_sigs < match->first) {
- ++good_sigs;
- sigs.push_back(std::move(sig));
- } else {
- sigs.emplace_back();
- }
+ //! Get a CPubKey from a key hash. Note the key hash may be of an xonly pubkey.
+ template<typename I>
+ std::optional<CPubKey> CPubFromPKHBytes(I first, I last) const {
+ assert(last - first == 20);
+ CPubKey pubkey;
+ CKeyID key_id;
+ std::copy(first, last, key_id.begin());
+ if (GetPubKey(m_provider, m_sig_data, key_id, pubkey)) return pubkey;
+ m_sig_data.missing_pubkeys.push_back(key_id);
+ return {};
+ }
+
+ //! Conversion to raw public key.
+ std::vector<unsigned char> ToPKBytes(const Key& key) const { return {key.begin(), key.end()}; }
+
+ //! Time lock satisfactions.
+ bool CheckAfter(uint32_t value) const { return m_creator.Checker().CheckLockTime(CScriptNum(value)); }
+ bool CheckOlder(uint32_t value) const { return m_creator.Checker().CheckSequence(CScriptNum(value)); }
+
+ //! Hash preimage satisfactions.
+ miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
+ return MsLookupHelper(m_sig_data.sha256_preimages, hash, preimage);
+ }
+ miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
+ return MsLookupHelper(m_sig_data.ripemd160_preimages, hash, preimage);
+ }
+ miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
+ return MsLookupHelper(m_sig_data.hash256_preimages, hash, preimage);
+ }
+ miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
+ return MsLookupHelper(m_sig_data.hash160_preimages, hash, preimage);
+ }
+
+ miniscript::MiniscriptContext MsContext() const {
+ return m_script_ctx;
+ }
+};
+
+/** Miniscript satisfier specific to P2WSH context. */
+struct WshSatisfier: Satisfier<CPubKey> {
+ explicit WshSatisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
+ const BaseSignatureCreator& creator LIFETIMEBOUND, const CScript& witscript LIFETIMEBOUND)
+ : Satisfier(provider, sig_data, creator, witscript, miniscript::MiniscriptContext::P2WSH) {}
+
+ //! Conversion from a raw compressed public key.
+ template <typename I>
+ std::optional<CPubKey> FromPKBytes(I first, I last) const {
+ CPubKey pubkey{first, last};
+ if (pubkey.IsValid()) return pubkey;
+ return {};
+ }
+
+ //! Conversion from a raw compressed public key hash.
+ template<typename I>
+ std::optional<CPubKey> FromPKHBytes(I first, I last) const {
+ return Satisfier::CPubFromPKHBytes(first, last);
+ }
+
+ //! Satisfy an ECDSA signature check.
+ miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const {
+ if (CreateSig(m_creator, m_sig_data, m_provider, sig, key, m_witness_script, SigVersion::WITNESS_V0)) {
+ return miniscript::Availability::YES;
}
- if (good_sigs == match->first) {
- result = std::move(sigs);
- return true;
+ return miniscript::Availability::NO;
+ }
+};
+
+/** Miniscript satisfier specific to Tapscript context. */
+struct TapSatisfier: Satisfier<XOnlyPubKey> {
+ const uint256& m_leaf_hash;
+
+ explicit TapSatisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
+ const BaseSignatureCreator& creator LIFETIMEBOUND, const CScript& script LIFETIMEBOUND,
+ const uint256& leaf_hash LIFETIMEBOUND)
+ : Satisfier(provider, sig_data, creator, script, miniscript::MiniscriptContext::TAPSCRIPT),
+ m_leaf_hash(leaf_hash) {}
+
+ //! Conversion from a raw xonly public key.
+ template <typename I>
+ std::optional<XOnlyPubKey> FromPKBytes(I first, I last) const {
+ CHECK_NONFATAL(last - first == 32);
+ XOnlyPubKey pubkey;
+ std::copy(first, last, pubkey.begin());
+ return pubkey;
+ }
+
+ //! Conversion from a raw xonly public key hash.
+ template<typename I>
+ std::optional<XOnlyPubKey> FromPKHBytes(I first, I last) const {
+ if (auto pubkey = Satisfier::CPubFromPKHBytes(first, last)) return XOnlyPubKey{*pubkey};
+ return {};
+ }
+
+ //! Satisfy a BIP340 signature check.
+ miniscript::Availability Sign(const XOnlyPubKey& key, std::vector<unsigned char>& sig) const {
+ if (CreateTaprootScriptSig(m_creator, m_sig_data, m_provider, sig, key, m_leaf_hash, SigVersion::TAPSCRIPT)) {
+ return miniscript::Availability::YES;
}
- return false;
+ return miniscript::Availability::NO;
}
+};
- return false;
+static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, Span<const unsigned char> script_bytes, std::vector<valtype>& result)
+{
+ // Only BIP342 tapscript signing is supported for now.
+ if (leaf_version != TAPROOT_LEAF_TAPSCRIPT) return false;
+
+ uint256 leaf_hash = ComputeTapleafHash(leaf_version, script_bytes);
+ CScript script = CScript(script_bytes.begin(), script_bytes.end());
+
+ TapSatisfier ms_satisfier{provider, sigdata, creator, script, leaf_hash};
+ const auto ms = miniscript::FromScript(script, ms_satisfier);
+ return ms && ms->Satisfy(ms_satisfier, result) == miniscript::Availability::YES;
}
static bool SignTaproot(const SigningProvider& provider, const BaseSignatureCreator& creator, const WitnessV1Taproot& output, SignatureData& sigdata, std::vector<valtype>& result)
@@ -382,92 +496,6 @@ static CScript PushAll(const std::vector<valtype>& values)
return result;
}
-template<typename M, typename K, typename V>
-miniscript::Availability MsLookupHelper(const M& map, const K& key, V& value)
-{
- auto it = map.find(key);
- if (it != map.end()) {
- value = it->second;
- return miniscript::Availability::YES;
- }
- return miniscript::Availability::NO;
-}
-
-/**
- * Context for solving a Miniscript.
- * If enough material (access to keys, hash preimages, ..) is given, produces a valid satisfaction.
- */
-struct Satisfier {
- typedef CPubKey Key;
-
- const SigningProvider& m_provider;
- SignatureData& m_sig_data;
- const BaseSignatureCreator& m_creator;
- const CScript& m_witness_script;
-
- explicit Satisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
- const BaseSignatureCreator& creator LIFETIMEBOUND,
- const CScript& witscript LIFETIMEBOUND) : m_provider(provider),
- m_sig_data(sig_data),
- m_creator(creator),
- m_witness_script(witscript) {}
-
- static bool KeyCompare(const Key& a, const Key& b) {
- return a < b;
- }
-
- //! Conversion from a raw public key.
- template <typename I>
- std::optional<Key> FromPKBytes(I first, I last) const
- {
- Key pubkey{first, last};
- if (pubkey.IsValid()) return pubkey;
- return {};
- }
-
- //! Conversion from a raw public key hash.
- template<typename I>
- std::optional<Key> FromPKHBytes(I first, I last) const {
- assert(last - first == 20);
- Key pubkey;
- CKeyID key_id;
- std::copy(first, last, key_id.begin());
- if (GetPubKey(m_provider, m_sig_data, key_id, pubkey)) return pubkey;
- m_sig_data.missing_pubkeys.push_back(key_id);
- return {};
- }
-
- //! Conversion to raw public key.
- std::vector<unsigned char> ToPKBytes(const CPubKey& key) const { return {key.begin(), key.end()}; }
-
- //! Satisfy a signature check.
- miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const {
- if (CreateSig(m_creator, m_sig_data, m_provider, sig, key, m_witness_script, SigVersion::WITNESS_V0)) {
- return miniscript::Availability::YES;
- }
- return miniscript::Availability::NO;
- }
-
- //! Time lock satisfactions.
- bool CheckAfter(uint32_t value) const { return m_creator.Checker().CheckLockTime(CScriptNum(value)); }
- bool CheckOlder(uint32_t value) const { return m_creator.Checker().CheckSequence(CScriptNum(value)); }
-
-
- //! Hash preimage satisfactions.
- miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
- return MsLookupHelper(m_sig_data.sha256_preimages, hash, preimage);
- }
- miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
- return MsLookupHelper(m_sig_data.ripemd160_preimages, hash, preimage);
- }
- miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
- return MsLookupHelper(m_sig_data.hash256_preimages, hash, preimage);
- }
- miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
- return MsLookupHelper(m_sig_data.hash160_preimages, hash, preimage);
- }
-};
-
bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreator& creator, const CScript& fromPubKey, SignatureData& sigdata)
{
if (sigdata.complete) return true;
@@ -512,7 +540,7 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato
// isn't fully solved. For instance the CHECKMULTISIG satisfaction in SignStep() pushes partial signatures
// and the extractor relies on this behaviour to combine witnesses.
if (!solved && result.empty()) {
- Satisfier ms_satisfier{provider, sigdata, creator, witnessscript};
+ WshSatisfier ms_satisfier{provider, sigdata, creator, witnessscript};
const auto ms = miniscript::FromScript(witnessscript, ms_satisfier);
solved = ms && ms->Satisfy(ms_satisfier, result) == miniscript::Availability::YES;
}
diff --git a/src/script/sign.h b/src/script/sign.h
index 4d7dade44e..ace2ba7856 100644
--- a/src/script/sign.h
+++ b/src/script/sign.h
@@ -79,6 +79,7 @@ struct SignatureData {
std::vector<unsigned char> taproot_key_path_sig; /// Schnorr signature for key path spending
std::map<std::pair<XOnlyPubKey, uint256>, std::vector<unsigned char>> taproot_script_sigs; ///< (Partial) schnorr signatures, indexed by XOnlyPubKey and leaf_hash.
std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> taproot_misc_pubkeys; ///< Miscellaneous Taproot pubkeys involved in this input along with their leaf script hashes and key origin data. Also includes the Taproot internal key (may have no leaf script hashes).
+ std::map<CKeyID, XOnlyPubKey> tap_pubkeys; ///< Misc Taproot pubkeys involved in this input, by hash. (Equivalent of misc_pubkeys but for Taproot.)
std::vector<CKeyID> missing_pubkeys; ///< KeyIDs of pubkeys which could not be found
std::vector<CKeyID> missing_sigs; ///< KeyIDs of pubkeys for signatures which could not be found
uint160 missing_redeem_script; ///< ScriptID of the missing redeemScript (if any)
generated by cgit v1.2.3 (git 2.26.2) at 2024-10-30 05:33:52 +0000