psbt.h

Go to the documentation of this file.

// Copyright (c) 2009-present The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
#ifndef BITCOIN_PSBT_H
#define BITCOIN_PSBT_H
 
#include <common/types.h>
#include <musig.h>
#include <node/transaction.h>
#include <policy/feerate.h>
#include <primitives/transaction.h>
#include <pubkey.h>
#include <script/keyorigin.h>
#include <script/sign.h>
#include <script/signingprovider.h>
#include <span.h>
#include <streams.h>
#include <uint256.h>
#include <util/result.h>
#include <util/expected.h>
 
#include <optional>
#include <bitset>
 
namespace node {
enum class TransactionError;
} // namespace node
 
using common::PSBTError;
 
// Magic bytes
inline constexpr uint8_t PSBT_MAGIC_BYTES[5] = {'p', 's', 'b', 't', 0xff};
 
// Global types
inline constexpr uint8_t PSBT_GLOBAL_UNSIGNED_TX = 0x00;
inline constexpr uint8_t PSBT_GLOBAL_XPUB = 0x01;
inline constexpr uint8_t PSBT_GLOBAL_TX_VERSION = 0x02;
inline constexpr uint8_t PSBT_GLOBAL_FALLBACK_LOCKTIME = 0x03;
inline constexpr uint8_t PSBT_GLOBAL_INPUT_COUNT = 0x04;
inline constexpr uint8_t PSBT_GLOBAL_OUTPUT_COUNT = 0x05;
inline constexpr uint8_t PSBT_GLOBAL_TX_MODIFIABLE = 0x06;
inline constexpr uint8_t PSBT_GLOBAL_VERSION = 0xFB;
inline constexpr uint8_t PSBT_GLOBAL_PROPRIETARY = 0xFC;
 
// Input types
inline constexpr uint8_t PSBT_IN_NON_WITNESS_UTXO = 0x00;
inline constexpr uint8_t PSBT_IN_WITNESS_UTXO = 0x01;
inline constexpr uint8_t PSBT_IN_PARTIAL_SIG = 0x02;
inline constexpr uint8_t PSBT_IN_SIGHASH = 0x03;
inline constexpr uint8_t PSBT_IN_REDEEMSCRIPT = 0x04;
inline constexpr uint8_t PSBT_IN_WITNESSSCRIPT = 0x05;
inline constexpr uint8_t PSBT_IN_BIP32_DERIVATION = 0x06;
inline constexpr uint8_t PSBT_IN_SCRIPTSIG = 0x07;
inline constexpr uint8_t PSBT_IN_SCRIPTWITNESS = 0x08;
inline constexpr uint8_t PSBT_IN_RIPEMD160 = 0x0A;
inline constexpr uint8_t PSBT_IN_SHA256 = 0x0B;
inline constexpr uint8_t PSBT_IN_HASH160 = 0x0C;
inline constexpr uint8_t PSBT_IN_HASH256 = 0x0D;
inline constexpr uint8_t PSBT_IN_PREVIOUS_TXID = 0x0e;
inline constexpr uint8_t PSBT_IN_OUTPUT_INDEX = 0x0f;
inline constexpr uint8_t PSBT_IN_SEQUENCE = 0x10;
inline constexpr uint8_t PSBT_IN_REQUIRED_TIME_LOCKTIME = 0x11;
inline constexpr uint8_t PSBT_IN_REQUIRED_HEIGHT_LOCKTIME = 0x12;
inline constexpr uint8_t PSBT_IN_TAP_KEY_SIG = 0x13;
inline constexpr uint8_t PSBT_IN_TAP_SCRIPT_SIG = 0x14;
inline constexpr uint8_t PSBT_IN_TAP_LEAF_SCRIPT = 0x15;
inline constexpr uint8_t PSBT_IN_TAP_BIP32_DERIVATION = 0x16;
inline constexpr uint8_t PSBT_IN_TAP_INTERNAL_KEY = 0x17;
inline constexpr uint8_t PSBT_IN_TAP_MERKLE_ROOT = 0x18;
inline constexpr uint8_t PSBT_IN_MUSIG2_PARTICIPANT_PUBKEYS = 0x1a;
inline constexpr uint8_t PSBT_IN_MUSIG2_PUB_NONCE = 0x1b;
inline constexpr uint8_t PSBT_IN_MUSIG2_PARTIAL_SIG = 0x1c;
inline constexpr uint8_t PSBT_IN_PROPRIETARY = 0xFC;
 
// Output types
inline constexpr uint8_t PSBT_OUT_REDEEMSCRIPT = 0x00;
inline constexpr uint8_t PSBT_OUT_WITNESSSCRIPT = 0x01;
inline constexpr uint8_t PSBT_OUT_BIP32_DERIVATION = 0x02;
inline constexpr uint8_t PSBT_OUT_AMOUNT = 0x03;
inline constexpr uint8_t PSBT_OUT_SCRIPT = 0x04;
inline constexpr uint8_t PSBT_OUT_TAP_INTERNAL_KEY = 0x05;
inline constexpr uint8_t PSBT_OUT_TAP_TREE = 0x06;
inline constexpr uint8_t PSBT_OUT_TAP_BIP32_DERIVATION = 0x07;
inline constexpr uint8_t PSBT_OUT_MUSIG2_PARTICIPANT_PUBKEYS = 0x08;
inline constexpr uint8_t PSBT_OUT_PROPRIETARY = 0xFC;
 
// The separator is 0x00. Reading this in means that the unserializer can interpret it
// as a 0 length key which indicates that this is the separator. The separator has no value.
inline constexpr uint8_t PSBT_SEPARATOR = 0x00;
 
// BIP 174 does not specify a maximum file size, but we set a limit anyway
// to prevent reading a stream indefinitely and running out of memory.
inline constexpr std::streamsize MAX_FILE_SIZE_PSBT{100'000'000}; // 100 MB
 
// PSBT version number
inline constexpr uint32_t PSBT_HIGHEST_VERSION = 2;
 
struct PSBTProprietary
{
    uint64_t subtype;
    std::vector<unsigned char> identifier;
    std::vector<unsigned char> key;
    std::vector<unsigned char> value;
 
    bool operator<(const PSBTProprietary &b) const {
        return key < b.key;
    }
    bool operator==(const PSBTProprietary &b) const {
        return key == b.key;
    }
};
 
// Takes a stream and multiple arguments and serializes them as if first serialized into a vector and then into the stream
// The resulting output into the stream has the total serialized length of all of the objects followed by all objects concatenated with each other.
template<typename Stream, typename... X>
void SerializeToVector(Stream& s, const X&... args)
{
    SizeComputer sizecomp;
    SerializeMany(sizecomp, args...);
    WriteCompactSize(s, sizecomp.size());
    SerializeMany(s, args...);
}
 
// Takes a stream and multiple arguments and unserializes them first as a vector then each object individually in the order provided in the arguments
template<typename Stream, typename... X>
void UnserializeFromVector(Stream& s, X&&... args)
{
    size_t expected_size = ReadCompactSize(s);
    size_t remaining_before = s.size();
    UnserializeMany(s, args...);
    size_t remaining_after = s.size();
    if (remaining_after + expected_size != remaining_before) {
        throw std::ios_base::failure("Size of value was not the stated size");
    }
}
 
// Deserialize bytes of given length from the stream as a KeyOriginInfo
template<typename Stream>
KeyOriginInfo DeserializeKeyOrigin(Stream& s, uint64_t length)
{
    // Read in key path
    if (length % 4 || length == 0) {
        throw std::ios_base::failure("Invalid length for HD key path");
    }
 
    KeyOriginInfo hd_keypath;
    s >> hd_keypath.fingerprint;
    for (unsigned int i = 4; i < length; i += sizeof(uint32_t)) {
        uint32_t index;
        s >> index;
        hd_keypath.path.push_back(index);
    }
    return hd_keypath;
}
 
// Deserialize a length prefixed KeyOriginInfo from a stream
template<typename Stream>
void DeserializeHDKeypath(Stream& s, KeyOriginInfo& hd_keypath)
{
    hd_keypath = DeserializeKeyOrigin(s, ReadCompactSize(s));
}
 
// Deserialize HD keypaths into a map
template<typename Stream>
void DeserializeHDKeypaths(Stream& s, const std::vector<unsigned char>& key, std::map<CPubKey, KeyOriginInfo>& hd_keypaths)
{
    // Make sure that the key is the size of pubkey + 1
    if (key.size() != CPubKey::SIZE + 1 && key.size() != CPubKey::COMPRESSED_SIZE + 1) {
        throw std::ios_base::failure("Size of key was not the expected size for the type BIP32 keypath");
    }
    // Read in the pubkey from key
    CPubKey pubkey(key.begin() + 1, key.end());
    if (!pubkey.IsFullyValid()) {
       throw std::ios_base::failure("Invalid pubkey");
    }
 
    KeyOriginInfo keypath;
    DeserializeHDKeypath(s, keypath);
 
    // Add to map
    hd_keypaths.emplace(pubkey, std::move(keypath));
}
 
// Serialize a KeyOriginInfo to a stream
template<typename Stream>
void SerializeKeyOrigin(Stream& s, KeyOriginInfo hd_keypath)
{
    s << hd_keypath.fingerprint;
    for (const auto& path : hd_keypath.path) {
        s << path;
    }
}
 
// Serialize a length prefixed KeyOriginInfo to a stream
template<typename Stream>
void SerializeHDKeypath(Stream& s, KeyOriginInfo hd_keypath)
{
    WriteCompactSize(s, (hd_keypath.path.size() + 1) * sizeof(uint32_t));
    SerializeKeyOrigin(s, hd_keypath);
}
 
// Serialize HD keypaths to a stream from a map
template<typename Stream>
void SerializeHDKeypaths(Stream& s, const std::map<CPubKey, KeyOriginInfo>& hd_keypaths, CompactSizeWriter type)
{
    for (const auto& keypath_pair : hd_keypaths) {
        if (!keypath_pair.first.IsValid()) {
            throw std::ios_base::failure("Invalid CPubKey being serialized");
        }
        SerializeToVector(s, type, std::span{keypath_pair.first});
        SerializeHDKeypath(s, keypath_pair.second);
    }
}
 
// Deserialize a PSBT_{IN/OUT}_MUSIG2_PARTICIPANT_PUBKEYS field
template<typename Stream>
void DeserializeMuSig2ParticipantPubkeys(Stream& s, SpanReader& skey, std::map<CPubKey, std::vector<CPubKey>>& out, std::string context)
{
    std::array<unsigned char, CPubKey::COMPRESSED_SIZE> agg_pubkey_bytes;
    skey >> std::as_writable_bytes(std::span{agg_pubkey_bytes});
    CPubKey agg_pubkey(agg_pubkey_bytes);
    if (!agg_pubkey.IsFullyValid()) {
        throw std::ios_base::failure(context + " musig2 aggregate pubkey is invalid");
    }
 
    std::vector<CPubKey> participants;
    std::vector<unsigned char> val;
    s >> val;
    SpanReader s_val{val};
    while (s_val.size() >= CPubKey::COMPRESSED_SIZE) {
        std::array<unsigned char, CPubKey::COMPRESSED_SIZE> part_pubkey_bytes;
        s_val >> std::as_writable_bytes(std::span{part_pubkey_bytes});
        CPubKey participant(part_pubkey_bytes);
        if (!participant.IsFullyValid()) {
            throw std::ios_base::failure(context + " musig2 participant pubkey is invalid");
        }
        participants.push_back(participant);
    }
    if (!s_val.empty()) {
        throw std::ios_base::failure(context + " musig2 participants pubkeys value size is not a multiple of 33");
    }
 
    out.emplace(agg_pubkey, participants);
}
 
// Deserialize the MuSig2 participant identifiers from PSBT_MUSIG2_{PUBNONCE/PARTIAL_SIG} fields
// Both fields contain the same data after the type byte - aggregate pubkey | participant pubkey | leaf script hash
template<typename Stream>
void DeserializeMuSig2ParticipantDataIdentifier(Stream& skey, CPubKey& agg_pub, CPubKey& part_pub, uint256& leaf_hash)
{
    leaf_hash.SetNull();
 
    std::array<unsigned char, CPubKey::COMPRESSED_SIZE> part_pubkey_bytes;
    std::array<unsigned char, CPubKey::COMPRESSED_SIZE> agg_pubkey_bytes;
 
    skey >> std::as_writable_bytes(std::span{part_pubkey_bytes}) >> std::as_writable_bytes(std::span{agg_pubkey_bytes});
    agg_pub.Set(agg_pubkey_bytes.begin(), agg_pubkey_bytes.end());
    if (!agg_pub.IsFullyValid()) {
        throw std::ios_base::failure("musig2 aggregate pubkey is invalid");
    }
 
    part_pub.Set(part_pubkey_bytes.begin(), part_pubkey_bytes.end());
    if (!part_pub.IsFullyValid()) {
        throw std::ios_base::failure("musig2 participant pubkey is invalid");
    }
 
    if (!skey.empty()) {
        skey >> leaf_hash;
    }
}
 
static inline void ExpectedKeySize(const std::string& key_name, const std::vector<unsigned char>& key, uint64_t expected_size) {
    if (key.size() != expected_size) {
        throw std::ios_base::failure(tfm::format("Size of key was not %d for the type %s", expected_size, key_name));
    }
}
 
class PSBTInput
{
private:
    uint32_t m_psbt_version;
 
public:
    CTransactionRef non_witness_utxo;
    CTxOut witness_utxo;
    CScript redeem_script;
    CScript witness_script;
    CScript final_script_sig;
    CScriptWitness final_script_witness;
    std::map<CPubKey, KeyOriginInfo> hd_keypaths;
    std::map<CKeyID, SigPair> partial_sigs;
    std::map<uint160, std::vector<unsigned char>> ripemd160_preimages;
    std::map<uint256, std::vector<unsigned char>> sha256_preimages;
    std::map<uint160, std::vector<unsigned char>> hash160_preimages;
    std::map<uint256, std::vector<unsigned char>> hash256_preimages;
 
    Txid prev_txid;
    uint32_t prev_out;
    std::optional<uint32_t> sequence;
    std::optional<uint32_t> time_locktime;
    std::optional<uint32_t> height_locktime;
 
    // Taproot fields
    std::vector<unsigned char> m_tap_key_sig;
    std::map<std::pair<XOnlyPubKey, uint256>, std::vector<unsigned char>> m_tap_script_sigs;
    std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> m_tap_scripts;
    std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> m_tap_bip32_paths;
    XOnlyPubKey m_tap_internal_key;
    uint256 m_tap_merkle_root;
 
    // MuSig2 fields
    std::map<CPubKey, std::vector<CPubKey>> m_musig2_participants;
    // Key is the aggregate pubkey and the script leaf hash, value is a map of participant pubkey to pubnonce
    std::map<std::pair<CPubKey, uint256>, std::map<CPubKey, std::vector<uint8_t>>> m_musig2_pubnonces;
    // Key is the aggregate pubkey and the script leaf hash, value is a map of participant pubkey to partial_sig
    std::map<std::pair<CPubKey, uint256>, std::map<CPubKey, uint256>> m_musig2_partial_sigs;
 
    std::map<std::vector<unsigned char>, std::vector<unsigned char>> unknown;
    std::set<PSBTProprietary> m_proprietary;
    std::optional<int> sighash_type;
 
    void FillSignatureData(SignatureData& sigdata) const;
    void FromSignatureData(const SignatureData& sigdata);
    [[nodiscard]] bool Merge(const PSBTInput& input);
    uint32_t GetVersion() const { return m_psbt_version; }
    COutPoint GetOutPoint() const;
    bool GetUTXO(CTxOut& utxo) const;
    bool HasSignatures() const;
 
    explicit PSBTInput(uint32_t psbt_version, const Txid& prev_txid, uint32_t prev_out, std::optional<uint32_t> sequence = std::nullopt)
        : m_psbt_version(psbt_version),
        prev_txid(prev_txid),
        prev_out(prev_out),
        sequence(sequence)
    {
        assert(m_psbt_version == 0 || m_psbt_version == 2);
    }
 
    // Construct a PSBTInput when the previous txid and output index are expected to be serialized
    template <typename Stream>
    explicit PSBTInput(deserialize_type, Stream& s, uint32_t psbt_version)
        : m_psbt_version(psbt_version)
    {
        assert(m_psbt_version == 2);
        Unserialize(s);
    }
 
    bool operator==(const PSBTInput&) const = default;
 
    template <typename Stream>
    inline void Serialize(Stream& s) const {
        // Write the utxo
        if (non_witness_utxo) {
            SerializeToVector(s, CompactSizeWriter(PSBT_IN_NON_WITNESS_UTXO));
            SerializeToVector(s, TX_NO_WITNESS(non_witness_utxo));
        }
        if (!witness_utxo.IsNull()) {
            SerializeToVector(s, CompactSizeWriter(PSBT_IN_WITNESS_UTXO));
            SerializeToVector(s, witness_utxo);
        }
 
        if (final_script_sig.empty() && final_script_witness.IsNull()) {
            // Write any partial signatures
            for (const auto& sig_pair : partial_sigs) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_PARTIAL_SIG), std::span{sig_pair.second.first});
                s << sig_pair.second.second;
            }
 
            // Write the sighash type
            if (sighash_type != std::nullopt) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_SIGHASH));
                SerializeToVector(s, *sighash_type);
            }
 
            // Write the redeem script
            if (!redeem_script.empty()) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_REDEEMSCRIPT));
                s << redeem_script;
            }
 
            // Write the witness script
            if (!witness_script.empty()) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_WITNESSSCRIPT));
                s << witness_script;
            }
 
            // Write any hd keypaths
            SerializeHDKeypaths(s, hd_keypaths, CompactSizeWriter(PSBT_IN_BIP32_DERIVATION));
 
            // Write any ripemd160 preimage
            for (const auto& [hash, preimage] : ripemd160_preimages) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_RIPEMD160), std::span{hash});
                s << preimage;
            }
 
            // Write any sha256 preimage
            for (const auto& [hash, preimage] : sha256_preimages) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_SHA256), std::span{hash});
                s << preimage;
            }
 
            // Write any hash160 preimage
            for (const auto& [hash, preimage] : hash160_preimages) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_HASH160), std::span{hash});
                s << preimage;
            }
 
            // Write any hash256 preimage
            for (const auto& [hash, preimage] : hash256_preimages) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_HASH256), std::span{hash});
                s << preimage;
            }
 
            // Write taproot key sig
            if (!m_tap_key_sig.empty()) {
                SerializeToVector(s, PSBT_IN_TAP_KEY_SIG);
                s << m_tap_key_sig;
            }
 
            // Write taproot script sigs
            for (const auto& [pubkey_leaf, sig] : m_tap_script_sigs) {
                const auto& [xonly, leaf_hash] = pubkey_leaf;
                SerializeToVector(s, PSBT_IN_TAP_SCRIPT_SIG, xonly, leaf_hash);
                s << sig;
            }
 
            // Write taproot leaf scripts
            for (const auto& [leaf, control_blocks] : m_tap_scripts) {
                const auto& [script, leaf_ver] = leaf;
                for (const auto& control_block : control_blocks) {
                    SerializeToVector(s, PSBT_IN_TAP_LEAF_SCRIPT, std::span{control_block});
                    std::vector<unsigned char> value_v(script.begin(), script.end());
                    value_v.push_back((uint8_t)leaf_ver);
                    s << value_v;
                }
            }
 
            // Write taproot bip32 keypaths
            for (const auto& [xonly, leaf_origin] : m_tap_bip32_paths) {
                const auto& [leaf_hashes, origin] = leaf_origin;
                SerializeToVector(s, PSBT_IN_TAP_BIP32_DERIVATION, xonly);
                std::vector<unsigned char> value;
                VectorWriter s_value{value, 0};
                s_value << leaf_hashes;
                SerializeKeyOrigin(s_value, origin);
                s << value;
            }
 
            // Write taproot internal key
            if (!m_tap_internal_key.IsNull()) {
                SerializeToVector(s, PSBT_IN_TAP_INTERNAL_KEY);
                s << ToByteVector(m_tap_internal_key);
            }
 
            // Write taproot merkle root
            if (!m_tap_merkle_root.IsNull()) {
                SerializeToVector(s, PSBT_IN_TAP_MERKLE_ROOT);
                SerializeToVector(s, m_tap_merkle_root);
            }
 
            // Write MuSig2 Participants
            for (const auto& [agg_pubkey, part_pubs] : m_musig2_participants) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PARTICIPANT_PUBKEYS), std::span{agg_pubkey});
                std::vector<unsigned char> value;
                VectorWriter s_value{value, 0};
                for (auto& pk : part_pubs) {
                    s_value << std::span{pk};
                }
                s << value;
            }
 
            // Write MuSig2 pubnonces
            for (const auto& [agg_pubkey_leaf_hash, pubnonces] : m_musig2_pubnonces) {
                const auto& [agg_pubkey, leaf_hash] = agg_pubkey_leaf_hash;
                for (const auto& [part_pubkey, pubnonce] : pubnonces) {
                    if (leaf_hash.IsNull()) {
                        SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PUB_NONCE), std::span{part_pubkey}, std::span{agg_pubkey});
                    } else {
                        SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PUB_NONCE), std::span{part_pubkey}, std::span{agg_pubkey}, leaf_hash);
                    }
                    s << pubnonce;
                }
            }
 
            // Write MuSig2 partial signatures
            for (const auto& [agg_pubkey_leaf_hash, psigs] : m_musig2_partial_sigs) {
                const auto& [agg_pubkey, leaf_hash] = agg_pubkey_leaf_hash;
                for (const auto& [pubkey, psig] : psigs) {
                    if (leaf_hash.IsNull()) {
                        SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PARTIAL_SIG), std::span{pubkey}, std::span{agg_pubkey});
                    } else {
                        SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PARTIAL_SIG), std::span{pubkey}, std::span{agg_pubkey}, leaf_hash);
                    }
                    SerializeToVector(s, psig);
                }
            }
        }
 
        // Write script sig
        if (!final_script_sig.empty()) {
            SerializeToVector(s, CompactSizeWriter(PSBT_IN_SCRIPTSIG));
            s << final_script_sig;
        }
        // write script witness
        if (!final_script_witness.IsNull()) {
            SerializeToVector(s, CompactSizeWriter(PSBT_IN_SCRIPTWITNESS));
            SerializeToVector(s, final_script_witness.stack);
        }
 
        // Write PSBTv2 fields
        if (m_psbt_version >= 2) {
            // Write prev txid, vout, sequence, and lock times
            SerializeToVector(s, CompactSizeWriter(PSBT_IN_PREVIOUS_TXID));
            SerializeToVector(s, prev_txid);
 
            SerializeToVector(s, CompactSizeWriter(PSBT_IN_OUTPUT_INDEX));
            SerializeToVector(s, prev_out);
 
            if (sequence != std::nullopt) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_SEQUENCE));
                SerializeToVector(s, *sequence);
            }
            if (time_locktime != std::nullopt) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_REQUIRED_TIME_LOCKTIME));
                SerializeToVector(s, *time_locktime);
            }
            if (height_locktime != std::nullopt) {
                SerializeToVector(s, CompactSizeWriter(PSBT_IN_REQUIRED_HEIGHT_LOCKTIME));
                SerializeToVector(s, *height_locktime);
            }
        }
 
        // Write proprietary things
        for (const auto& entry : m_proprietary) {
            s << entry.key;
            s << entry.value;
        }
 
        // Write unknown things
        for (auto& entry : unknown) {
            s << entry.first;
            s << entry.second;
        }
 
        s << PSBT_SEPARATOR;
    }
 
 
    template <typename Stream>
    inline void Unserialize(Stream& s) {
        // Used for duplicate key detection
        std::set<std::vector<unsigned char>> key_lookup;
        // Cache whether PSBTv2 required fields were seen
        bool found_prev_txid = false;
        bool found_prev_out = false;
 
        // Read loop
        bool found_sep = false;
        while(!s.empty()) {
            // Read the key of format "<keylen><keytype><keydata>" after which
            // "key" will contain "<keytype><keydata>"
            std::vector<unsigned char> key;
            s >> key;
 
            // the key is empty if that was actually a separator byte
            // This is a special case for key lengths 0 as those are not allowed (except for separator)
            if (key.empty()) {
                found_sep = true;
                break;
            }
 
            // Duplicate keys are not permitted
            if (!key_lookup.emplace(key).second) {
                throw std::ios_base::failure(tfm::format("Duplicate Key, input key \"%s\" already provided", HexStr(key)));
            }
 
            // "skey" is used so that "key" is unchanged after reading keytype below
            SpanReader skey{key};
            // keytype is of the format compact size uint at the beginning of "key"
            uint64_t type = ReadCompactSize(skey);
 
            // Do stuff based on keytype "type", i.e., key checks, reading values of the
            // format "<valuelen><valuedata>" from the stream "s", and value checks
            switch(type) {
                case PSBT_IN_NON_WITNESS_UTXO:
                {
                    ExpectedKeySize("Input Non-witness UTXO", key, 1);
                    // Set the stream to unserialize with witness since this is always a valid network transaction
                    UnserializeFromVector(s, TX_WITH_WITNESS(non_witness_utxo));
                    break;
                }
                case PSBT_IN_WITNESS_UTXO:
                    ExpectedKeySize("Input Witness UTXO", key, 1);
                    UnserializeFromVector(s, witness_utxo);
                    break;
                case PSBT_IN_PARTIAL_SIG:
                {
                    // Make sure that the key is the size of pubkey + 1
                    if (key.size() != CPubKey::SIZE + 1 && key.size() != CPubKey::COMPRESSED_SIZE + 1) {
                        throw std::ios_base::failure("Size of key was not the expected size for the type partial signature pubkey");
                    }
                    // Read in the pubkey from key
                    CPubKey pubkey(key.begin() + 1, key.end());
                    if (!pubkey.IsFullyValid()) {
                       throw std::ios_base::failure("Invalid pubkey");
                    }
 
                    // Read in the signature from value
                    std::vector<unsigned char> sig;
                    s >> sig;
 
                    // Check that the signature is validly encoded
                    if (sig.empty() || !CheckSignatureEncoding(sig, SCRIPT_VERIFY_DERSIG | SCRIPT_VERIFY_STRICTENC, nullptr)) {
                        throw std::ios_base::failure("Signature is not a valid encoding");
                    }
 
                    // Add to list
                    partial_sigs.emplace(pubkey.GetID(), SigPair(pubkey, std::move(sig)));
                    break;
                }
                case PSBT_IN_SIGHASH:
                    ExpectedKeySize("Input Sighash Type", key, 1);
                    int sighash;
                    UnserializeFromVector(s, sighash);
                    sighash_type = sighash;
                    break;
                case PSBT_IN_REDEEMSCRIPT:
                {
                    ExpectedKeySize("Input redeemScript", key, 1);
                    s >> redeem_script;
                    break;
                }
                case PSBT_IN_WITNESSSCRIPT:
                {
                    ExpectedKeySize("Input witnessScript", key, 1);
                    s >> witness_script;
                    break;
                }
                case PSBT_IN_BIP32_DERIVATION:
                {
                    DeserializeHDKeypaths(s, key, hd_keypaths);
                    break;
                }
                case PSBT_IN_SCRIPTSIG:
                {
                    ExpectedKeySize("Input Final scriptSig", key, 1);
                    s >> final_script_sig;
                    break;
                }
                case PSBT_IN_SCRIPTWITNESS:
                {
                    ExpectedKeySize("Input Final scriptWitness", key, 1);
                    UnserializeFromVector(s, final_script_witness.stack);
                    break;
                }
                case PSBT_IN_RIPEMD160:
                {
                    ExpectedKeySize("Input RIPEMD160 Preimage", key, CRIPEMD160::OUTPUT_SIZE + 1);
                    // Read in the hash from key
                    std::vector<unsigned char> hash_vec(key.begin() + 1, key.end());
                    uint160 hash(hash_vec);
 
                    // Read in the preimage from value
                    std::vector<unsigned char> preimage;
                    s >> preimage;
 
                    // Add to preimages list
                    ripemd160_preimages.emplace(hash, std::move(preimage));
                    break;
                }
                case PSBT_IN_SHA256:
                {
                    ExpectedKeySize("Input SHA256 Preimage", key, CSHA256::OUTPUT_SIZE + 1);
                    // Read in the hash from key
                    std::vector<unsigned char> hash_vec(key.begin() + 1, key.end());
                    uint256 hash(hash_vec);
 
                    // Read in the preimage from value
                    std::vector<unsigned char> preimage;
                    s >> preimage;
 
                    // Add to preimages list
                    sha256_preimages.emplace(hash, std::move(preimage));
                    break;
                }
                case PSBT_IN_HASH160:
                {
                    ExpectedKeySize("Input Hash160 Preimage", key, CHash160::OUTPUT_SIZE + 1);
                    // Read in the hash from key
                    std::vector<unsigned char> hash_vec(key.begin() + 1, key.end());
                    uint160 hash(hash_vec);
 
                    // Read in the preimage from value
                    std::vector<unsigned char> preimage;
                    s >> preimage;
 
                    // Add to preimages list
                    hash160_preimages.emplace(hash, std::move(preimage));
                    break;
                }
                case PSBT_IN_HASH256:
                {
                    ExpectedKeySize("Input Hash256 Preimage", key, CHash256::OUTPUT_SIZE + 1);
                    // Read in the hash from key
                    std::vector<unsigned char> hash_vec(key.begin() + 1, key.end());
                    uint256 hash(hash_vec);
 
                    // Read in the preimage from value
                    std::vector<unsigned char> preimage;
                    s >> preimage;
 
                    // Add to preimages list
                    hash256_preimages.emplace(hash, std::move(preimage));
                    break;
                }
                case PSBT_IN_PREVIOUS_TXID:
                {
                    ExpectedKeySize("Input Previous TXID", key, 1);
                    if (m_psbt_version < 2) {
                        throw std::ios_base::failure("Previous txid is not allowed in PSBTv0");
                    }
                    UnserializeFromVector(s, prev_txid);
                    found_prev_txid = true;
                    break;
                }
                case PSBT_IN_OUTPUT_INDEX:
                {
                    ExpectedKeySize("Input Previous Output's Index", key, 1);
                    if (m_psbt_version < 2) {
                        throw std::ios_base::failure("Previous output's index is not allowed in PSBTv0");
                    }
                    UnserializeFromVector(s, prev_out);
                    found_prev_out = true;
                    break;
                }
                case PSBT_IN_SEQUENCE:
                {
                    ExpectedKeySize("Input Sequence", key, 1);
                    if (m_psbt_version < 2) {
                        throw std::ios_base::failure("Sequence is not allowed in PSBTv0");
                    }
                    sequence.emplace();
                    UnserializeFromVector(s, *sequence);
                    break;
                }
                case PSBT_IN_REQUIRED_TIME_LOCKTIME:
                {
                    ExpectedKeySize("Input Required Time Based Locktime", key, 1);
                    if (m_psbt_version < 2) {
                        throw std::ios_base::failure("Required time based locktime is not allowed in PSBTv0");
                    }
                    time_locktime.emplace();
                    UnserializeFromVector(s, *time_locktime);
                    if (*time_locktime < LOCKTIME_THRESHOLD) {
                        throw std::ios_base::failure("Required time based locktime is invalid (less than 500000000)");
                    }
                    break;
                }
                case PSBT_IN_REQUIRED_HEIGHT_LOCKTIME:
                {
                    ExpectedKeySize("Input Required Height Based Locktime", key, 1);
                    if (m_psbt_version < 2) {
                        throw std::ios_base::failure("Required height based locktime is not allowed in PSBTv0");
                    }
                    height_locktime.emplace();
                    UnserializeFromVector(s, *height_locktime);
                    if (*height_locktime >= LOCKTIME_THRESHOLD) {
                        throw std::ios_base::failure("Required height based locktime is invalid (greater than or equal to 500000000)");
                    } else if (*height_locktime == 0) {
                        throw std::ios_base::failure("Required height based locktime is invalid (0)");
                    }
                    break;
                }
                case PSBT_IN_TAP_KEY_SIG:
                {
                    ExpectedKeySize("Input Taproot Key Path Signature", key, 1);
                    s >> m_tap_key_sig;
                    if (m_tap_key_sig.size() < 64) {
                        throw std::ios_base::failure("Input Taproot key path signature is shorter than 64 bytes");
                    } else if (m_tap_key_sig.size() > 65) {
                        throw std::ios_base::failure("Input Taproot key path signature is longer than 65 bytes");
                    }
                    break;
                }
                case PSBT_IN_TAP_SCRIPT_SIG:
                {
                    ExpectedKeySize("Input Taproot Script Path Signature", key, 65);
                    SpanReader s_key{std::span{key}.subspan(1)};
                    XOnlyPubKey xonly;
                    uint256 hash;
                    s_key >> xonly;
                    s_key >> hash;
                    std::vector<unsigned char> sig;
                    s >> sig;
                    if (sig.size() < 64) {
                        throw std::ios_base::failure("Input Taproot script path signature is shorter than 64 bytes");
                    } else if (sig.size() > 65) {
                        throw std::ios_base::failure("Input Taproot script path signature is longer than 65 bytes");
                    }
                    m_tap_script_sigs.emplace(std::make_pair(xonly, hash), sig);
                    break;
                }
                case PSBT_IN_TAP_LEAF_SCRIPT:
                {
                    if (key.size() < 34) {
                        throw std::ios_base::failure("Input Taproot leaf script key is not at least 34 bytes");
                    } else if ((key.size() - 2) % 32 != 0) {
                        throw std::ios_base::failure("Input Taproot leaf script key's control block size is not valid");
                    }
                    std::vector<unsigned char> script_v;
                    s >> script_v;
                    if (script_v.empty()) {
                        throw std::ios_base::failure("Input Taproot leaf script must be at least 1 byte");
                    }
                    uint8_t leaf_ver = script_v.back();
                    script_v.pop_back();
                    const auto leaf_script = std::make_pair(script_v, (int)leaf_ver);
                    m_tap_scripts[leaf_script].insert(std::vector<unsigned char>(key.begin() + 1, key.end()));
                    break;
                }
                case PSBT_IN_TAP_BIP32_DERIVATION:
                {
                    ExpectedKeySize("Input Taproot BIP32 Keypath", key, 33);
                    SpanReader s_key{std::span{key}.subspan(1)};
                    XOnlyPubKey xonly;
                    s_key >> xonly;
                    std::set<uint256> leaf_hashes;
                    uint64_t value_len = ReadCompactSize(s);
                    size_t before_hashes = s.size();
                    s >> leaf_hashes;
                    size_t after_hashes = s.size();
                    size_t hashes_len = before_hashes - after_hashes;
                    if (hashes_len > value_len) {
                        throw std::ios_base::failure("Input Taproot BIP32 keypath has an invalid length");
                    }
                    size_t origin_len = value_len - hashes_len;
                    m_tap_bip32_paths.emplace(xonly, std::make_pair(leaf_hashes, DeserializeKeyOrigin(s, origin_len)));
                    break;
                }
                case PSBT_IN_TAP_INTERNAL_KEY:
                {
                    ExpectedKeySize("Input Taproot Internal Key", key, 1);
                    UnserializeFromVector(s, m_tap_internal_key);
                    break;
                }
                case PSBT_IN_TAP_MERKLE_ROOT:
                {
                    ExpectedKeySize("Input Taproot Merkle Root", key, 1);
                    UnserializeFromVector(s, m_tap_merkle_root);
                    break;
                }
                case PSBT_IN_MUSIG2_PARTICIPANT_PUBKEYS:
                {
                    ExpectedKeySize("Input MuSig2 Participants Pubkeys", key, CPubKey::COMPRESSED_SIZE + 1);
                    DeserializeMuSig2ParticipantPubkeys(s, skey, m_musig2_participants, std::string{"Input"});
                    break;
                }
                case PSBT_IN_MUSIG2_PUB_NONCE:
                {
                    if (key.size() != 2 * CPubKey::COMPRESSED_SIZE + 1 && key.size() != 2 * CPubKey::COMPRESSED_SIZE + CSHA256::OUTPUT_SIZE + 1) {
                        throw std::ios_base::failure("Input musig2 pubnonce key is not expected size of 67 or 99 bytes");
                    }
                    CPubKey agg_pub, part_pub;
                    uint256 leaf_hash;
                    DeserializeMuSig2ParticipantDataIdentifier(skey, agg_pub, part_pub, leaf_hash);
 
                    std::vector<uint8_t> pubnonce;
                    s >> pubnonce;
                    if (pubnonce.size() != MUSIG2_PUBNONCE_SIZE) {
                        throw std::ios_base::failure("Input musig2 pubnonce value is not 66 bytes");
                    }
 
                    m_musig2_pubnonces[std::make_pair(agg_pub, leaf_hash)].emplace(part_pub, pubnonce);
                    break;
                }
                case PSBT_IN_MUSIG2_PARTIAL_SIG:
                {
                    if (key.size() != 2 * CPubKey::COMPRESSED_SIZE + 1 && key.size() != 2 * CPubKey::COMPRESSED_SIZE + CSHA256::OUTPUT_SIZE + 1) {
                        throw std::ios_base::failure("Input musig2 partial sig key is not expected size of 67 or 99 bytes");
                    }
                    CPubKey agg_pub, part_pub;
                    uint256 leaf_hash;
                    DeserializeMuSig2ParticipantDataIdentifier(skey, agg_pub, part_pub, leaf_hash);
 
                    uint256 partial_sig;
                    UnserializeFromVector(s, partial_sig);
 
                    m_musig2_partial_sigs[std::make_pair(agg_pub, leaf_hash)].emplace(part_pub, partial_sig);
                    break;
                }
                case PSBT_IN_PROPRIETARY:
                {
                    PSBTProprietary this_prop;
                    skey >> this_prop.identifier;
                    this_prop.subtype = ReadCompactSize(skey);
                    this_prop.key = key;
 
                    s >> this_prop.value;
                    m_proprietary.insert(this_prop);
                    break;
                }
                // Unknown stuff
                default:
                    // Read in the value
                    std::vector<unsigned char> val_bytes;
                    s >> val_bytes;
                    unknown.emplace(std::move(key), std::move(val_bytes));
                    break;
            }
        }
 
        if (!found_sep) {
            throw std::ios_base::failure("Separator is missing at the end of an input map");
        }
 
        // Make sure required PSBTv2 fields are present
        if (m_psbt_version >= 2) {
            if (!found_prev_txid) {
                throw std::ios_base::failure("Previous TXID is required in PSBTv2");
            }
            if (!found_prev_out) {
                throw std::ios_base::failure("Previous output's index is required in PSBTv2");
            }
        }
    }
};
 
class PSBTOutput
{
private:
    uint32_t m_psbt_version;
 
public:
    CScript redeem_script;
    CScript witness_script;
    std::map<CPubKey, KeyOriginInfo> hd_keypaths;
 
    XOnlyPubKey m_tap_internal_key;
    std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> m_tap_tree;
    std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> m_tap_bip32_paths;
    std::map<CPubKey, std::vector<CPubKey>> m_musig2_participants;
 
    std::map<std::vector<unsigned char>, std::vector<unsigned char>> unknown;
    std::set<PSBTProprietary> m_proprietary;
 
    CAmount amount;
    CScript script;
 
    void FillSignatureData(SignatureData& sigdata) const;
    void FromSignatureData(const SignatureData& sigdata);
    [[nodiscard]] bool Merge(const PSBTOutput& output);
    uint32_t GetVersion() const { return m_psbt_version; }
 
    explicit PSBTOutput(uint32_t psbt_version, CAmount amount, const CScript& script)
        : m_psbt_version(psbt_version),
        amount(amount),
        script(script)
    {
        assert(m_psbt_version == 0 || m_psbt_version == 2);
    }
 
    // Construct a PSBTOutput when the amount and script are expected to be serialized
    template <typename Stream>
    explicit PSBTOutput(deserialize_type, Stream& s, uint32_t psbt_version)
        : m_psbt_version(psbt_version)
    {
        assert(m_psbt_version == 2);
        Unserialize(s);
    }
 
    bool operator==(const PSBTOutput&) const = default;
 
    template <typename Stream>
    inline void Serialize(Stream& s) const {
        // Write the redeem script
        if (!redeem_script.empty()) {
            SerializeToVector(s, CompactSizeWriter(PSBT_OUT_REDEEMSCRIPT));
            s << redeem_script;
        }
 
        // Write the witness script
        if (!witness_script.empty()) {
            SerializeToVector(s, CompactSizeWriter(PSBT_OUT_WITNESSSCRIPT));
            s << witness_script;
        }
 
        // Write any hd keypaths
        SerializeHDKeypaths(s, hd_keypaths, CompactSizeWriter(PSBT_OUT_BIP32_DERIVATION));
 
        if (m_psbt_version >= 2) {
            // Write amount and spk
            SerializeToVector(s, CompactSizeWriter(PSBT_OUT_AMOUNT));
            SerializeToVector(s, amount);
 
            SerializeToVector(s, CompactSizeWriter(PSBT_OUT_SCRIPT));
            s << script;
        }
 
        // Write proprietary things
        for (const auto& entry : m_proprietary) {
            s << entry.key;
            s << entry.value;
        }
 
        // Write taproot internal key
        if (!m_tap_internal_key.IsNull()) {
            SerializeToVector(s, PSBT_OUT_TAP_INTERNAL_KEY);
            s << ToByteVector(m_tap_internal_key);
        }
 
        // Write taproot tree
        if (!m_tap_tree.empty()) {
            SerializeToVector(s, PSBT_OUT_TAP_TREE);
            std::vector<unsigned char> value;
            VectorWriter s_value{value, 0};
            for (const auto& [depth, leaf_ver, script] : m_tap_tree) {
                s_value << depth;
                s_value << leaf_ver;
                s_value << script;
            }
            s << value;
        }
 
        // Write taproot bip32 keypaths
        for (const auto& [xonly, leaf] : m_tap_bip32_paths) {
            const auto& [leaf_hashes, origin] = leaf;
            SerializeToVector(s, PSBT_OUT_TAP_BIP32_DERIVATION, xonly);
            std::vector<unsigned char> value;
            VectorWriter s_value{value, 0};
            s_value << leaf_hashes;
            SerializeKeyOrigin(s_value, origin);
            s << value;
        }
 
        // Write MuSig2 Participants
        for (const auto& [agg_pubkey, part_pubs] : m_musig2_participants) {
            SerializeToVector(s, CompactSizeWriter(PSBT_OUT_MUSIG2_PARTICIPANT_PUBKEYS), std::span{agg_pubkey});
            std::vector<unsigned char> value;
            VectorWriter s_value{value, 0};
            for (auto& pk : part_pubs) {
                s_value << std::span{pk};
            }
            s << value;
        }
 
        // Write unknown things
        for (auto& entry : unknown) {
            s << entry.first;
            s << entry.second;
        }
 
        s << PSBT_SEPARATOR;
    }
 
 
    template <typename Stream>
    inline void Unserialize(Stream& s) {
        // Used for duplicate key detection
        std::set<std::vector<unsigned char>> key_lookup;
        // Cache whether PSBTv2 required fields are found
        bool found_amount = false;
        bool found_script = false;
 
        // Read loop
        bool found_sep = false;
        while(!s.empty()) {
            // Read the key of format "<keylen><keytype><keydata>" after which
            // "key" will contain "<keytype><keydata>"
            std::vector<unsigned char> key;
            s >> key;
 
            // the key is empty if that was actually a separator byte
            // This is a special case for key lengths 0 as those are not allowed (except for separator)
            if (key.empty()) {
                found_sep = true;
                break;
            }
 
            // Duplicate keys are not permitted
            if (!key_lookup.emplace(key).second) {
                throw std::ios_base::failure(tfm::format("Duplicate Key, output key \"%s\" already provided", HexStr(key)));
            }
 
            // "skey" is used so that "key" is unchanged after reading keytype below
            SpanReader skey{key};
            // keytype is of the format compact size uint at the beginning of "key"
            uint64_t type = ReadCompactSize(skey);
 
            // Do stuff based on keytype "type", i.e., key checks, reading values of the
            // format "<valuelen><valuedata>" from the stream "s", and value checks
            switch(type) {
                case PSBT_OUT_REDEEMSCRIPT:
                {
                    ExpectedKeySize("Output redeemScript", key, 1);
                    s >> redeem_script;
                    break;
                }
                case PSBT_OUT_WITNESSSCRIPT:
                {
                    ExpectedKeySize("Output witnessScript", key, 1);
                    s >> witness_script;
                    break;
                }
                case PSBT_OUT_BIP32_DERIVATION:
                {
                    DeserializeHDKeypaths(s, key, hd_keypaths);
                    break;
                }
                case PSBT_OUT_AMOUNT:
                {
                    ExpectedKeySize("Output Amount", key, 1);
                    if (m_psbt_version < 2) {
                        throw std::ios_base::failure("Output amount is not allowed in PSBTv0");
                    }
                    UnserializeFromVector(s, amount);
                    found_amount = true;
                    break;
                }
                case PSBT_OUT_SCRIPT:
                {
                    ExpectedKeySize("Output Script", key, 1);
                    if (m_psbt_version < 2) {
                        throw std::ios_base::failure("Output script is not allowed in PSBTv0");
                    }
                    s >> script;
                    found_script = true;
                    break;
                }
                case PSBT_OUT_TAP_INTERNAL_KEY:
                {
                    ExpectedKeySize("Output Taproot Internal Key", key, 1);
                    UnserializeFromVector(s, m_tap_internal_key);
                    break;
                }
                case PSBT_OUT_TAP_TREE:
                {
                    ExpectedKeySize("Output Taproot Tree Key", key, 1);
                    std::vector<unsigned char> tree_v;
                    s >> tree_v;
                    SpanReader s_tree{tree_v};
                    if (s_tree.empty()) {
                        throw std::ios_base::failure("Output Taproot tree must not be empty");
                    }
                    TaprootBuilder builder;
                    while (!s_tree.empty()) {
                        uint8_t depth;
                        uint8_t leaf_ver;
                        std::vector<unsigned char> script;
                        s_tree >> depth;
                        s_tree >> leaf_ver;
                        s_tree >> script;
                        if (depth > TAPROOT_CONTROL_MAX_NODE_COUNT) {
                            throw std::ios_base::failure("Output Taproot tree has as leaf greater than Taproot maximum depth");
                        }
                        if ((leaf_ver & ~TAPROOT_LEAF_MASK) != 0) {
                            throw std::ios_base::failure("Output Taproot tree has a leaf with an invalid leaf version");
                        }
                        m_tap_tree.emplace_back(depth, leaf_ver, script);
                        builder.Add((int)depth, script, (int)leaf_ver, /*track=*/true);
                    }
                    if (!builder.IsComplete()) {
                        throw std::ios_base::failure("Output Taproot tree is malformed");
                    }
                    break;
                }
                case PSBT_OUT_TAP_BIP32_DERIVATION:
                {
                    ExpectedKeySize("Output Taproot BIP32 Keypath", key, 33);
                    XOnlyPubKey xonly(uint256(std::span<uint8_t>(key).last(32)));
                    std::set<uint256> leaf_hashes;
                    uint64_t value_len = ReadCompactSize(s);
                    size_t before_hashes = s.size();
                    s >> leaf_hashes;
                    size_t after_hashes = s.size();
                    size_t hashes_len = before_hashes - after_hashes;
                    if (hashes_len > value_len) {
                        throw std::ios_base::failure("Output Taproot BIP32 keypath has an invalid length");
                    }
                    size_t origin_len = value_len - hashes_len;
                    m_tap_bip32_paths.emplace(xonly, std::make_pair(leaf_hashes, DeserializeKeyOrigin(s, origin_len)));
                    break;
                }
                case PSBT_OUT_MUSIG2_PARTICIPANT_PUBKEYS:
                {
                    ExpectedKeySize("Output MuSig2 Participants Pubkeys", key, CPubKey::COMPRESSED_SIZE + 1);
                    DeserializeMuSig2ParticipantPubkeys(s, skey, m_musig2_participants, std::string{"Output"});
                    break;
                }
                case PSBT_OUT_PROPRIETARY:
                {
                    PSBTProprietary this_prop;
                    skey >> this_prop.identifier;
                    this_prop.subtype = ReadCompactSize(skey);
                    this_prop.key = key;
 
                    s >> this_prop.value;
                    m_proprietary.insert(this_prop);
                    break;
                }
                // Unknown stuff
                default: {
                    // Read in the value
                    std::vector<unsigned char> val_bytes;
                    s >> val_bytes;
                    unknown.emplace(std::move(key), std::move(val_bytes));
                    break;
                }
            }
        }
 
        if (!found_sep) {
            throw std::ios_base::failure("Separator is missing at the end of an output map");
        }
 
        // Make sure required PSBTv2 fields are present
        if (m_psbt_version >= 2) {
            if (!found_amount) {
                throw std::ios_base::failure("Output amount is required in PSBTv2");
            }
            if (!found_script) {
                throw std::ios_base::failure("Output script is required in PSBTv2");
            }
        }
    }
};
 
class PartiallySignedTransaction
{
private:
    std::optional<uint32_t> m_version;
 
public:
    // We use a vector of CExtPubKey in the event that there happens to be the same KeyOriginInfos for different CExtPubKeys
    // Note that this map swaps the key and values from the serialization
    std::map<KeyOriginInfo, std::set<CExtPubKey>> m_xpubs;
    std::optional<std::bitset<8>> m_tx_modifiable;
    std::vector<PSBTInput> inputs;
    std::vector<PSBTOutput> outputs;
    std::map<std::vector<unsigned char>, std::vector<unsigned char>> unknown;
    std::set<PSBTProprietary> m_proprietary;
 
    uint32_t tx_version;
    std::optional<uint32_t> fallback_locktime;
 
    uint32_t GetVersion() const;
 
    [[nodiscard]] bool Merge(const PartiallySignedTransaction& psbt);
    void MergeGlobalXPubs(const PartiallySignedTransaction& psbt);
    bool AddInput(const PSBTInput& psbtin);
    bool AddOutput(const PSBTOutput& psbtout);
    std::optional<uint32_t> ComputeTimeLock() const;
    std::optional<CMutableTransaction> GetUnsignedTx() const;
    std::optional<Txid> GetUniqueID() const;
    explicit PartiallySignedTransaction(const CMutableTransaction& tx, uint32_t version = 2);
 
    template <typename Stream>
    inline void Serialize(Stream& s) const {
 
        // magic bytes
        s << PSBT_MAGIC_BYTES;
 
        if (GetVersion() < 2) {
            // unsigned tx flag
            SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_UNSIGNED_TX));
 
            // Write serialized tx to a stream
            SerializeToVector(s, TX_NO_WITNESS(*GetUnsignedTx()));
        }
 
        // Write xpubs
        for (const auto& xpub_pair : m_xpubs) {
            for (const auto& xpub : xpub_pair.second) {
                unsigned char ser_xpub[BIP32_EXTKEY_WITH_VERSION_SIZE];
                xpub.EncodeWithVersion(ser_xpub);
                // Note that the serialization swaps the key and value
                // The xpub is the key (for uniqueness) while the path is the value
                SerializeToVector(s, PSBT_GLOBAL_XPUB, ser_xpub);
                SerializeHDKeypath(s, xpub_pair.first);
            }
        }
 
        if (GetVersion() >= 2) {
            // Write PSBTv2 tx version, locktime, counts, etc.
            SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_TX_VERSION));
            SerializeToVector(s, tx_version);
            if (fallback_locktime != std::nullopt) {
                SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_FALLBACK_LOCKTIME));
                SerializeToVector(s, *fallback_locktime);
            }
 
            SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_INPUT_COUNT));
            SerializeToVector(s, CompactSizeWriter(inputs.size()));
            SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_OUTPUT_COUNT));
            SerializeToVector(s, CompactSizeWriter(outputs.size()));
 
            if (m_tx_modifiable != std::nullopt) {
                SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_TX_MODIFIABLE));
                SerializeToVector(s, static_cast<uint8_t>(m_tx_modifiable->to_ulong()));
            }
        }
 
        // PSBT version
        if (GetVersion() > 0) {
            SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_VERSION));
            SerializeToVector(s, *m_version);
        }
 
        // Write proprietary things
        for (const auto& entry : m_proprietary) {
            s << entry.key;
            s << entry.value;
        }
 
        // Write the unknown things
        for (auto& entry : unknown) {
            s << entry.first;
            s << entry.second;
        }
 
        // Separator
        s << PSBT_SEPARATOR;
 
        // Write inputs
        for (const PSBTInput& input : inputs) {
            s << input;
        }
        // Write outputs
        for (const PSBTOutput& output : outputs) {
            s << output;
        }
    }
 
 
    template <typename Stream>
    inline void Unserialize(Stream& s) {
        // Read the magic bytes
        uint8_t magic[5];
        s >> magic;
        if (!std::equal(magic, magic + 5, PSBT_MAGIC_BYTES)) {
            throw std::ios_base::failure("Invalid PSBT magic bytes");
        }
 
        // Used for duplicate key detection
        std::set<std::vector<unsigned char>> key_lookup;
 
        // Read global data
        bool found_sep = false;
        std::optional<CMutableTransaction> tx;
        uint64_t input_count = 0;
        uint64_t output_count = 0;
        bool found_input_count = false;
        bool found_output_count = false;
        bool found_tx_version = false;
        bool found_fallback_locktime = false;
        while(!s.empty()) {
            // Read the key of format "<keylen><keytype><keydata>" after which
            // "key" will contain "<keytype><keydata>"
            std::vector<unsigned char> key;
            s >> key;
 
            // the key is empty if that was actually a separator byte
            // This is a special case for key lengths 0 as those are not allowed (except for separator)
            if (key.empty()) {
                found_sep = true;
                break;
            }
 
            // Duplicate keys are not permitted
            if (!key_lookup.emplace(key).second) {
                throw std::ios_base::failure(tfm::format("Duplicate Key, global key \"%s\" already provided", HexStr(key)));
            }
 
            // "skey" is used so that "key" is unchanged after reading keytype below
            SpanReader skey{key};
            // keytype is of the format compact size uint at the beginning of "key"
            uint64_t type = ReadCompactSize(skey);
 
            // Do stuff based on keytype "type", i.e., key checks, reading values of the
            // format "<valuelen><valuedata>" from the stream "s", and value checks
            switch(type) {
                case PSBT_GLOBAL_UNSIGNED_TX:
                {
                    ExpectedKeySize("Global Unsigned TX", key, 1);
                    // Set the stream to serialize with non-witness since this should always be non-witness
                    tx.emplace();
                    UnserializeFromVector(s, TX_NO_WITNESS(*tx));
                    // Make sure that all scriptSigs and scriptWitnesses are empty
                    for (const CTxIn& txin : tx->vin) {
                        if (!txin.scriptSig.empty() || !txin.scriptWitness.IsNull()) {
                            throw std::ios_base::failure("Unsigned tx does not have empty scriptSigs and scriptWitnesses.");
                        }
                    }
                    tx_version = tx->version;
                    fallback_locktime = tx->nLockTime;
                    // Set the input and output counts
                    input_count = tx->vin.size();
                    output_count = tx->vout.size();
                    break;
                }
                case PSBT_GLOBAL_TX_VERSION:
                {
                    ExpectedKeySize("Global Transaction Version", key, 1);
                    UnserializeFromVector(s, tx_version);
                    found_tx_version = true;
                    break;
                }
                case PSBT_GLOBAL_FALLBACK_LOCKTIME:
                {
                    ExpectedKeySize("Global Fallback Locktime", key, 1);
                    fallback_locktime.emplace();
                    UnserializeFromVector(s, *fallback_locktime);
                    found_fallback_locktime = true;
                    break;
                }
                case PSBT_GLOBAL_INPUT_COUNT:
                {
                    ExpectedKeySize("Global Input Count", key, 1);
                    CompactSizeReader reader(input_count);
                    UnserializeFromVector(s, reader);
                    found_input_count = true;
                    break;
                }
                case PSBT_GLOBAL_OUTPUT_COUNT:
                {
                    ExpectedKeySize("Global Output Count", key, 1);
                    CompactSizeReader reader(output_count);
                    UnserializeFromVector(s, reader);
                    found_output_count = true;
                    break;
                }
                case PSBT_GLOBAL_TX_MODIFIABLE:
                {
                    ExpectedKeySize("Global TX Modifiable Flags", key, 1);
                    uint8_t tx_mod;
                    UnserializeFromVector(s, tx_mod);
                    m_tx_modifiable.emplace(tx_mod);
                    break;
                }
                case PSBT_GLOBAL_XPUB:
                {
                    ExpectedKeySize("Global XPUB", key, BIP32_EXTKEY_WITH_VERSION_SIZE + 1);
                    // Read in the xpub from key
                    CExtPubKey xpub;
                    xpub.DecodeWithVersion(&key.data()[1]);
                    if (!xpub.pubkey.IsFullyValid()) {
                       throw std::ios_base::failure("Invalid pubkey");
                    }
                    // Read in the keypath from stream
                    KeyOriginInfo keypath;
                    DeserializeHDKeypath(s, keypath);
 
                    // Note that we store these swapped to make searches faster.
                    // Serialization uses xpub -> keypath to enqure key uniqueness
                    if (!m_xpubs.contains(keypath)) {
                        // Make a new set to put the xpub in
                        m_xpubs[keypath] = {xpub};
                    } else {
                        // Insert xpub into existing set
                        m_xpubs[keypath].insert(xpub);
                    }
                    break;
                }
                case PSBT_GLOBAL_VERSION:
                {
                    ExpectedKeySize("Global PSBT Version", key, 1);
                    uint32_t v;
                    UnserializeFromVector(s, v);
                    m_version = v;
                    if (*m_version > PSBT_HIGHEST_VERSION) {
                        throw std::ios_base::failure("Unsupported version number");
                    }
                    break;
                }
                case PSBT_GLOBAL_PROPRIETARY:
                {
                    PSBTProprietary this_prop;
                    skey >> this_prop.identifier;
                    this_prop.subtype = ReadCompactSize(skey);
                    this_prop.key = key;
 
                    s >> this_prop.value;
                    m_proprietary.insert(this_prop);
                    break;
                }
                // Unknown stuff
                default: {
                    // Read in the value
                    std::vector<unsigned char> val_bytes;
                    s >> val_bytes;
                    unknown.emplace(std::move(key), std::move(val_bytes));
                }
            }
        }
 
        if (!found_sep) {
            throw std::ios_base::failure("Separator is missing at the end of the global map");
        }
 
        const uint32_t psbt_ver = GetVersion();
 
        // Check PSBT version constraints
        if (psbt_ver == 0) {
            // Make sure that we got an unsigned tx for PSBTv0
            if (!tx) {
                throw std::ios_base::failure("No unsigned transaction was provided");
            }
            // Make sure no PSBTv2 fields are present
            if (found_tx_version) {
                throw std::ios_base::failure("PSBT_GLOBAL_TX_VERSION is not allowed in PSBTv0");
            }
            if (found_fallback_locktime) {
                throw std::ios_base::failure("PSBT_GLOBAL_FALLBACK_LOCKTIME is not allowed in PSBTv0");
            }
            if (found_input_count) {
                throw std::ios_base::failure("PSBT_GLOBAL_INPUT_COUNT is not allowed in PSBTv0");
            }
            if (found_output_count) {
                throw std::ios_base::failure("PSBT_GLOBAL_OUTPUT_COUNT is not allowed in PSBTv0");
            }
            if (m_tx_modifiable != std::nullopt) {
                throw std::ios_base::failure("PSBT_GLOBAL_TX_MODIFIABLE is not allowed in PSBTv0");
            }
        }
        // Disallow v1
        if (psbt_ver == 1) {
            throw std::ios_base::failure("There is no PSBT version 1");
        }
        if (psbt_ver == 2) {
            // Tx version, input, and output counts are required
            if (!found_tx_version) {
                throw std::ios_base::failure("PSBT_GLOBAL_TX_VERSION is required in PSBTv2");
            }
            if (!found_input_count) {
                throw std::ios_base::failure("PSBT_GLOBAL_INPUT_COUNT is required in PSBTv2");
            }
            if (!found_output_count) {
                throw std::ios_base::failure("PSBT_GLOBAL_OUTPUT_COUNT is required in PSBTv2");
            }
            // Unsigned tx is disallowed
            if (tx) {
                throw std::ios_base::failure("PSBT_GLOBAL_UNSIGNED_TX is not allowed in PSBTv2");
            }
        }
        if (psbt_ver > 2) {
            throw std::ios_base::failure("Unknown PSBT version");
        }
 
        // Read input data
        unsigned int i = 0;
        while (!s.empty() && i < input_count) {
            if (psbt_ver < 2) {
                inputs.emplace_back(psbt_ver, tx->vin[i].prevout.hash, tx->vin[i].prevout.n, tx->vin[i].nSequence);
                s >> inputs.back();
            } else {
                inputs.emplace_back(deserialize, s, psbt_ver);
            }
 
            // Make sure the non-witness utxo matches the outpoint
            const PSBTInput& input = inputs.back();
            if (input.non_witness_utxo) {
                if (psbt_ver < 2) {
                    if (input.non_witness_utxo->GetHash() != tx->vin[i].prevout.hash) {
                        throw std::ios_base::failure("Non-witness UTXO does not match outpoint hash");
                    }
                    if (tx->vin[i].prevout.n >= input.non_witness_utxo->vout.size()) {
                        throw std::ios_base::failure("Input specifies output index that does not exist");
                    }
                } else {
                    if (input.non_witness_utxo->GetHash() != input.prev_txid) {
                        throw std::ios_base::failure("Non-witness UTXO does not match outpoint hash");
                    }
                    if (input.prev_out >= input.non_witness_utxo->vout.size()) {
                        throw std::ios_base::failure("Input specifies output index that does not exist");
                    }
                }
            }
            ++i;
        }
        // Make sure that the number of inputs matches the number of inputs in the transaction
        if (inputs.size() != input_count) {
            throw std::ios_base::failure("Inputs provided does not match the number of inputs in transaction.");
        }
 
        // Read output data
        i = 0;
        while (!s.empty() && i < output_count) {
            if (psbt_ver < 2) {
                outputs.emplace_back(psbt_ver, tx->vout[i].nValue, tx->vout[i].scriptPubKey);
                s >> outputs.back();
            } else {
                outputs.emplace_back(deserialize, s, psbt_ver);
            }
            ++i;
        }
        // Make sure that the number of outputs matches the number of outputs in the transaction
        if (outputs.size() != output_count) {
            throw std::ios_base::failure("Outputs provided does not match the number of outputs in transaction.");
        }
    }
 
    template <typename Stream>
    PartiallySignedTransaction(deserialize_type, Stream& s) {
        Unserialize(s);
    }
};
 
enum class PSBTRole {
    CREATOR,
    UPDATER,
    SIGNER,
    FINALIZER,
    EXTRACTOR
};
 
std::string PSBTRoleName(PSBTRole role);
 
std::optional<PrecomputedTransactionData> PrecomputePSBTData(const PartiallySignedTransaction& psbt);
 
bool PSBTInputSigned(const PSBTInput& input);
 
bool PSBTInputSignedAndVerified(const PartiallySignedTransaction& psbt, unsigned int input_index, const PrecomputedTransactionData* txdata);
 
[[nodiscard]] util::Expected<void, PSBTError> SignPSBTInput(const SigningProvider& provider, PartiallySignedTransaction& psbt, int index, const PrecomputedTransactionData* txdata, const common::PSBTFillOptions& options, SignatureData* out_sigdata = nullptr);
 
void RemoveUnnecessaryTransactions(PartiallySignedTransaction& psbtx);
 
size_t CountPSBTUnsignedInputs(const PartiallySignedTransaction& psbt);
 
void UpdatePSBTOutput(const SigningProvider& provider, PartiallySignedTransaction& psbt, int index);
 
bool FinalizePSBT(PartiallySignedTransaction& psbtx);
 
bool FinalizeAndExtractPSBT(PartiallySignedTransaction& psbtx, CMutableTransaction& result);
 
[[nodiscard]] std::optional<PartiallySignedTransaction> CombinePSBTs(const std::vector<PartiallySignedTransaction>& psbtxs);
 
[[nodiscard]] util::Result<PartiallySignedTransaction> DecodeBase64PSBT(const std::string& base64_tx);
[[nodiscard]] util::Result<PartiallySignedTransaction> DecodeRawPSBT(std::span<const std::byte> tx_data);
 
#endif // BITCOIN_PSBT_H