1  // Copyright (c) 2009-present The Bitcoin Core developers
   2  // Distributed under the MIT software license, see the accompanying
   3  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4  
   5  #ifndef BITCOIN_PSBT_H
   6  #define BITCOIN_PSBT_H
   7  
   8  #include <common/types.h>
   9  #include <node/transaction.h>
  10  #include <policy/feerate.h>
  11  #include <primitives/transaction.h>
  12  #include <pubkey.h>
  13  #include <script/keyorigin.h>
  14  #include <script/sign.h>
  15  #include <script/signingprovider.h>
  16  #include <span.h>
  17  #include <streams.h>
  18  
  19  #include <optional>
  20  
  21  namespace node {
  22  enum class TransactionError;
  23  } // namespace node
  24  
  25  using common::PSBTError;
  26  
  27  // Magic bytes
  28  static constexpr uint8_t PSBT_MAGIC_BYTES[5] = {'p', 's', 'b', 't', 0xff};
  29  
  30  // Global types
  31  static constexpr uint8_t PSBT_GLOBAL_UNSIGNED_TX = 0x00;
  32  static constexpr uint8_t PSBT_GLOBAL_XPUB = 0x01;
  33  static constexpr uint8_t PSBT_GLOBAL_VERSION = 0xFB;
  34  static constexpr uint8_t PSBT_GLOBAL_PROPRIETARY = 0xFC;
  35  
  36  // Input types
  37  static constexpr uint8_t PSBT_IN_NON_WITNESS_UTXO = 0x00;
  38  static constexpr uint8_t PSBT_IN_WITNESS_UTXO = 0x01;
  39  static constexpr uint8_t PSBT_IN_PARTIAL_SIG = 0x02;
  40  static constexpr uint8_t PSBT_IN_SIGHASH = 0x03;
  41  static constexpr uint8_t PSBT_IN_REDEEMSCRIPT = 0x04;
  42  static constexpr uint8_t PSBT_IN_WITNESSSCRIPT = 0x05;
  43  static constexpr uint8_t PSBT_IN_BIP32_DERIVATION = 0x06;
  44  static constexpr uint8_t PSBT_IN_SCRIPTSIG = 0x07;
  45  static constexpr uint8_t PSBT_IN_SCRIPTWITNESS = 0x08;
  46  static constexpr uint8_t PSBT_IN_RIPEMD160 = 0x0A;
  47  static constexpr uint8_t PSBT_IN_SHA256 = 0x0B;
  48  static constexpr uint8_t PSBT_IN_HASH160 = 0x0C;
  49  static constexpr uint8_t PSBT_IN_HASH256 = 0x0D;
  50  static constexpr uint8_t PSBT_IN_TAP_KEY_SIG = 0x13;
  51  static constexpr uint8_t PSBT_IN_TAP_SCRIPT_SIG = 0x14;
  52  static constexpr uint8_t PSBT_IN_TAP_LEAF_SCRIPT = 0x15;
  53  static constexpr uint8_t PSBT_IN_TAP_BIP32_DERIVATION = 0x16;
  54  static constexpr uint8_t PSBT_IN_TAP_INTERNAL_KEY = 0x17;
  55  static constexpr uint8_t PSBT_IN_TAP_MERKLE_ROOT = 0x18;
  56  static constexpr uint8_t PSBT_IN_MUSIG2_PARTICIPANT_PUBKEYS = 0x1a;
  57  static constexpr uint8_t PSBT_IN_MUSIG2_PUB_NONCE = 0x1b;
  58  static constexpr uint8_t PSBT_IN_MUSIG2_PARTIAL_SIG = 0x1c;
  59  static constexpr uint8_t PSBT_IN_PROPRIETARY = 0xFC;
  60  
  61  // Output types
  62  static constexpr uint8_t PSBT_OUT_REDEEMSCRIPT = 0x00;
  63  static constexpr uint8_t PSBT_OUT_WITNESSSCRIPT = 0x01;
  64  static constexpr uint8_t PSBT_OUT_BIP32_DERIVATION = 0x02;
  65  static constexpr uint8_t PSBT_OUT_TAP_INTERNAL_KEY = 0x05;
  66  static constexpr uint8_t PSBT_OUT_TAP_TREE = 0x06;
  67  static constexpr uint8_t PSBT_OUT_TAP_BIP32_DERIVATION = 0x07;
  68  static constexpr uint8_t PSBT_OUT_MUSIG2_PARTICIPANT_PUBKEYS = 0x08;
  69  static constexpr uint8_t PSBT_OUT_PROPRIETARY = 0xFC;
  70  
  71  // The separator is 0x00. Reading this in means that the unserializer can interpret it
  72  // as a 0 length key which indicates that this is the separator. The separator has no value.
  73  static constexpr uint8_t PSBT_SEPARATOR = 0x00;
  74  
  75  // BIP 174 does not specify a maximum file size, but we set a limit anyway
  76  // to prevent reading a stream indefinitely and running out of memory.
  77  const std::streamsize MAX_FILE_SIZE_PSBT = 100000000; // 100 MB
  78  
  79  // PSBT version number
  80  static constexpr uint32_t PSBT_HIGHEST_VERSION = 0;
  81  
  82  /** A structure for PSBT proprietary types */
  83  struct PSBTProprietary
  84  {
  85      uint64_t subtype;
  86      std::vector<unsigned char> identifier;
  87      std::vector<unsigned char> key;
  88      std::vector<unsigned char> value;
  89  
  90      bool operator<(const PSBTProprietary &b) const {
  91          return key < b.key;
  92      }
  93      bool operator==(const PSBTProprietary &b) const {
  94          return key == b.key;
  95      }
  96  };
  97  
  98  // Takes a stream and multiple arguments and serializes them as if first serialized into a vector and then into the stream
  99  // The resulting output into the stream has the total serialized length of all of the objects followed by all objects concatenated with each other.
 100  template<typename Stream, typename... X>
 101  void SerializeToVector(Stream& s, const X&... args)
 102  {
 103      SizeComputer sizecomp;
 104      SerializeMany(sizecomp, args...);
 105      WriteCompactSize(s, sizecomp.size());
 106      SerializeMany(s, args...);
 107  }
 108  
 109  // Takes a stream and multiple arguments and unserializes them first as a vector then each object individually in the order provided in the arguments
 110  template<typename Stream, typename... X>
 111  void UnserializeFromVector(Stream& s, X&&... args)
 112  {
 113      size_t expected_size = ReadCompactSize(s);
 114      size_t remaining_before = s.size();
 115      UnserializeMany(s, args...);
 116      size_t remaining_after = s.size();
 117      if (remaining_after + expected_size != remaining_before) {
 118          throw std::ios_base::failure("Size of value was not the stated size");
 119      }
 120  }
 121  
 122  // Deserialize bytes of given length from the stream as a KeyOriginInfo
 123  template<typename Stream>
 124  KeyOriginInfo DeserializeKeyOrigin(Stream& s, uint64_t length)
 125  {
 126      // Read in key path
 127      if (length % 4 || length == 0) {
 128          throw std::ios_base::failure("Invalid length for HD key path");
 129      }
 130  
 131      KeyOriginInfo hd_keypath;
 132      s >> hd_keypath.fingerprint;
 133      for (unsigned int i = 4; i < length; i += sizeof(uint32_t)) {
 134          uint32_t index;
 135          s >> index;
 136          hd_keypath.path.push_back(index);
 137      }
 138      return hd_keypath;
 139  }
 140  
 141  // Deserialize a length prefixed KeyOriginInfo from a stream
 142  template<typename Stream>
 143  void DeserializeHDKeypath(Stream& s, KeyOriginInfo& hd_keypath)
 144  {
 145      hd_keypath = DeserializeKeyOrigin(s, ReadCompactSize(s));
 146  }
 147  
 148  // Deserialize HD keypaths into a map
 149  template<typename Stream>
 150  void DeserializeHDKeypaths(Stream& s, const std::vector<unsigned char>& key, std::map<CPubKey, KeyOriginInfo>& hd_keypaths)
 151  {
 152      // Make sure that the key is the size of pubkey + 1
 153      if (key.size() != CPubKey::SIZE + 1 && key.size() != CPubKey::COMPRESSED_SIZE + 1) {
 154          throw std::ios_base::failure("Size of key was not the expected size for the type BIP32 keypath");
 155      }
 156      // Read in the pubkey from key
 157      CPubKey pubkey(key.begin() + 1, key.end());
 158      if (!pubkey.IsFullyValid()) {
 159         throw std::ios_base::failure("Invalid pubkey");
 160      }
 161      if (hd_keypaths.contains(pubkey)) {
 162          throw std::ios_base::failure("Duplicate Key, pubkey derivation path already provided");
 163      }
 164  
 165      KeyOriginInfo keypath;
 166      DeserializeHDKeypath(s, keypath);
 167  
 168      // Add to map
 169      hd_keypaths.emplace(pubkey, std::move(keypath));
 170  }
 171  
 172  // Serialize a KeyOriginInfo to a stream
 173  template<typename Stream>
 174  void SerializeKeyOrigin(Stream& s, KeyOriginInfo hd_keypath)
 175  {
 176      s << hd_keypath.fingerprint;
 177      for (const auto& path : hd_keypath.path) {
 178          s << path;
 179      }
 180  }
 181  
 182  // Serialize a length prefixed KeyOriginInfo to a stream
 183  template<typename Stream>
 184  void SerializeHDKeypath(Stream& s, KeyOriginInfo hd_keypath)
 185  {
 186      WriteCompactSize(s, (hd_keypath.path.size() + 1) * sizeof(uint32_t));
 187      SerializeKeyOrigin(s, hd_keypath);
 188  }
 189  
 190  // Serialize HD keypaths to a stream from a map
 191  template<typename Stream>
 192  void SerializeHDKeypaths(Stream& s, const std::map<CPubKey, KeyOriginInfo>& hd_keypaths, CompactSizeWriter type)
 193  {
 194      for (const auto& keypath_pair : hd_keypaths) {
 195          if (!keypath_pair.first.IsValid()) {
 196              throw std::ios_base::failure("Invalid CPubKey being serialized");
 197          }
 198          SerializeToVector(s, type, std::span{keypath_pair.first});
 199          SerializeHDKeypath(s, keypath_pair.second);
 200      }
 201  }
 202  
 203  // Deserialize a PSBT_{IN/OUT}_MUSIG2_PARTICIPANT_PUBKEYS field
 204  template<typename Stream>
 205  void DeserializeMuSig2ParticipantPubkeys(Stream& s, SpanReader& skey, std::map<CPubKey, std::vector<CPubKey>>& out, std::string context)
 206  {
 207      std::array<unsigned char, CPubKey::COMPRESSED_SIZE> agg_pubkey_bytes;
 208      skey >> std::as_writable_bytes(std::span{agg_pubkey_bytes});
 209      CPubKey agg_pubkey(agg_pubkey_bytes);
 210      if (!agg_pubkey.IsFullyValid()) {
 211          throw std::ios_base::failure(context + " musig2 aggregate pubkey is invalid");
 212      }
 213  
 214      std::vector<CPubKey> participants;
 215      std::vector<unsigned char> val;
 216      s >> val;
 217      SpanReader s_val{val};
 218      while (s_val.size() >= CPubKey::COMPRESSED_SIZE) {
 219          std::array<unsigned char, CPubKey::COMPRESSED_SIZE> part_pubkey_bytes;
 220          s_val >> std::as_writable_bytes(std::span{part_pubkey_bytes});
 221          CPubKey participant(part_pubkey_bytes);
 222          if (!participant.IsFullyValid()) {
 223              throw std::ios_base::failure(context + " musig2 participant pubkey is invalid");
 224          }
 225          participants.push_back(participant);
 226      }
 227      if (!s_val.empty()) {
 228          throw std::ios_base::failure(context + " musig2 participants pubkeys value size is not a multiple of 33");
 229      }
 230  
 231      out.emplace(agg_pubkey, participants);
 232  }
 233  
 234  // Deserialize the MuSig2 participant identifiers from PSBT_MUSIG2_{PUBNONCE/PARTIAL_SIG} fields
 235  // Both fields contain the same data after the type byte - aggregate pubkey | participant pubkey | leaf script hash
 236  template<typename Stream>
 237  void DeserializeMuSig2ParticipantDataIdentifier(Stream& skey, CPubKey& agg_pub, CPubKey& part_pub, uint256& leaf_hash)
 238  {
 239      leaf_hash.SetNull();
 240  
 241      std::array<unsigned char, CPubKey::COMPRESSED_SIZE> part_pubkey_bytes;
 242      std::array<unsigned char, CPubKey::COMPRESSED_SIZE> agg_pubkey_bytes;
 243  
 244      skey >> std::as_writable_bytes(std::span{part_pubkey_bytes}) >> std::as_writable_bytes(std::span{agg_pubkey_bytes});
 245      agg_pub.Set(agg_pubkey_bytes.begin(), agg_pubkey_bytes.end());
 246      if (!agg_pub.IsFullyValid()) {
 247          throw std::ios_base::failure("musig2 aggregate pubkey is invalid");
 248      }
 249  
 250      part_pub.Set(part_pubkey_bytes.begin(), part_pubkey_bytes.end());
 251      if (!part_pub.IsFullyValid()) {
 252          throw std::ios_base::failure("musig2 participant pubkey is invalid");
 253      }
 254  
 255      if (!skey.empty()) {
 256          skey >> leaf_hash;
 257      }
 258  }
 259  
 260  /** A structure for PSBTs which contain per-input information */
 261  struct PSBTInput
 262  {
 263      CTransactionRef non_witness_utxo;
 264      CTxOut witness_utxo;
 265      CScript redeem_script;
 266      CScript witness_script;
 267      CScript final_script_sig;
 268      CScriptWitness final_script_witness;
 269      std::map<CPubKey, KeyOriginInfo> hd_keypaths;
 270      std::map<CKeyID, SigPair> partial_sigs;
 271      std::map<uint160, std::vector<unsigned char>> ripemd160_preimages;
 272      std::map<uint256, std::vector<unsigned char>> sha256_preimages;
 273      std::map<uint160, std::vector<unsigned char>> hash160_preimages;
 274      std::map<uint256, std::vector<unsigned char>> hash256_preimages;
 275  
 276      // Taproot fields
 277      std::vector<unsigned char> m_tap_key_sig;
 278      std::map<std::pair<XOnlyPubKey, uint256>, std::vector<unsigned char>> m_tap_script_sigs;
 279      std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> m_tap_scripts;
 280      std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> m_tap_bip32_paths;
 281      XOnlyPubKey m_tap_internal_key;
 282      uint256 m_tap_merkle_root;
 283  
 284      // MuSig2 fields
 285      std::map<CPubKey, std::vector<CPubKey>> m_musig2_participants;
 286      // Key is the aggregate pubkey and the script leaf hash, value is a map of participant pubkey to pubnonce
 287      std::map<std::pair<CPubKey, uint256>, std::map<CPubKey, std::vector<uint8_t>>> m_musig2_pubnonces;
 288      // Key is the aggregate pubkey and the script leaf hash, value is a map of participant pubkey to partial_sig
 289      std::map<std::pair<CPubKey, uint256>, std::map<CPubKey, uint256>> m_musig2_partial_sigs;
 290  
 291      std::map<std::vector<unsigned char>, std::vector<unsigned char>> unknown;
 292      std::set<PSBTProprietary> m_proprietary;
 293      std::optional<int> sighash_type;
 294  
 295      bool IsNull() const;
 296      void FillSignatureData(SignatureData& sigdata) const;
 297      void FromSignatureData(const SignatureData& sigdata);
 298      void Merge(const PSBTInput& input);
 299      PSBTInput() = default;
 300  
 301      template <typename Stream>
 302      inline void Serialize(Stream& s) const {
 303          // Write the utxo
 304          if (non_witness_utxo) {
 305              SerializeToVector(s, CompactSizeWriter(PSBT_IN_NON_WITNESS_UTXO));
 306              SerializeToVector(s, TX_NO_WITNESS(non_witness_utxo));
 307          }
 308          if (!witness_utxo.IsNull()) {
 309              SerializeToVector(s, CompactSizeWriter(PSBT_IN_WITNESS_UTXO));
 310              SerializeToVector(s, witness_utxo);
 311          }
 312  
 313          if (final_script_sig.empty() && final_script_witness.IsNull()) {
 314              // Write any partial signatures
 315              for (const auto& sig_pair : partial_sigs) {
 316                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_PARTIAL_SIG), std::span{sig_pair.second.first});
 317                  s << sig_pair.second.second;
 318              }
 319  
 320              // Write the sighash type
 321              if (sighash_type != std::nullopt) {
 322                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_SIGHASH));
 323                  SerializeToVector(s, *sighash_type);
 324              }
 325  
 326              // Write the redeem script
 327              if (!redeem_script.empty()) {
 328                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_REDEEMSCRIPT));
 329                  s << redeem_script;
 330              }
 331  
 332              // Write the witness script
 333              if (!witness_script.empty()) {
 334                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_WITNESSSCRIPT));
 335                  s << witness_script;
 336              }
 337  
 338              // Write any hd keypaths
 339              SerializeHDKeypaths(s, hd_keypaths, CompactSizeWriter(PSBT_IN_BIP32_DERIVATION));
 340  
 341              // Write any ripemd160 preimage
 342              for (const auto& [hash, preimage] : ripemd160_preimages) {
 343                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_RIPEMD160), std::span{hash});
 344                  s << preimage;
 345              }
 346  
 347              // Write any sha256 preimage
 348              for (const auto& [hash, preimage] : sha256_preimages) {
 349                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_SHA256), std::span{hash});
 350                  s << preimage;
 351              }
 352  
 353              // Write any hash160 preimage
 354              for (const auto& [hash, preimage] : hash160_preimages) {
 355                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_HASH160), std::span{hash});
 356                  s << preimage;
 357              }
 358  
 359              // Write any hash256 preimage
 360              for (const auto& [hash, preimage] : hash256_preimages) {
 361                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_HASH256), std::span{hash});
 362                  s << preimage;
 363              }
 364  
 365              // Write taproot key sig
 366              if (!m_tap_key_sig.empty()) {
 367                  SerializeToVector(s, PSBT_IN_TAP_KEY_SIG);
 368                  s << m_tap_key_sig;
 369              }
 370  
 371              // Write taproot script sigs
 372              for (const auto& [pubkey_leaf, sig] : m_tap_script_sigs) {
 373                  const auto& [xonly, leaf_hash] = pubkey_leaf;
 374                  SerializeToVector(s, PSBT_IN_TAP_SCRIPT_SIG, xonly, leaf_hash);
 375                  s << sig;
 376              }
 377  
 378              // Write taproot leaf scripts
 379              for (const auto& [leaf, control_blocks] : m_tap_scripts) {
 380                  const auto& [script, leaf_ver] = leaf;
 381                  for (const auto& control_block : control_blocks) {
 382                      SerializeToVector(s, PSBT_IN_TAP_LEAF_SCRIPT, std::span{control_block});
 383                      std::vector<unsigned char> value_v(script.begin(), script.end());
 384                      value_v.push_back((uint8_t)leaf_ver);
 385                      s << value_v;
 386                  }
 387              }
 388  
 389              // Write taproot bip32 keypaths
 390              for (const auto& [xonly, leaf_origin] : m_tap_bip32_paths) {
 391                  const auto& [leaf_hashes, origin] = leaf_origin;
 392                  SerializeToVector(s, PSBT_IN_TAP_BIP32_DERIVATION, xonly);
 393                  std::vector<unsigned char> value;
 394                  VectorWriter s_value{value, 0};
 395                  s_value << leaf_hashes;
 396                  SerializeKeyOrigin(s_value, origin);
 397                  s << value;
 398              }
 399  
 400              // Write taproot internal key
 401              if (!m_tap_internal_key.IsNull()) {
 402                  SerializeToVector(s, PSBT_IN_TAP_INTERNAL_KEY);
 403                  s << ToByteVector(m_tap_internal_key);
 404              }
 405  
 406              // Write taproot merkle root
 407              if (!m_tap_merkle_root.IsNull()) {
 408                  SerializeToVector(s, PSBT_IN_TAP_MERKLE_ROOT);
 409                  SerializeToVector(s, m_tap_merkle_root);
 410              }
 411  
 412              // Write MuSig2 Participants
 413              for (const auto& [agg_pubkey, part_pubs] : m_musig2_participants) {
 414                  SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PARTICIPANT_PUBKEYS), std::span{agg_pubkey});
 415                  std::vector<unsigned char> value;
 416                  VectorWriter s_value{value, 0};
 417                  for (auto& pk : part_pubs) {
 418                      s_value << std::span{pk};
 419                  }
 420                  s << value;
 421              }
 422  
 423              // Write MuSig2 pubnonces
 424              for (const auto& [agg_pubkey_leaf_hash, pubnonces] : m_musig2_pubnonces) {
 425                  const auto& [agg_pubkey, leaf_hash] = agg_pubkey_leaf_hash;
 426                  for (const auto& [part_pubkey, pubnonce] : pubnonces) {
 427                      if (leaf_hash.IsNull()) {
 428                          SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PUB_NONCE), std::span{part_pubkey}, std::span{agg_pubkey});
 429                      } else {
 430                          SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PUB_NONCE), std::span{part_pubkey}, std::span{agg_pubkey}, leaf_hash);
 431                      }
 432                      s << pubnonce;
 433                  }
 434              }
 435  
 436              // Write MuSig2 partial signatures
 437              for (const auto& [agg_pubkey_leaf_hash, psigs] : m_musig2_partial_sigs) {
 438                  const auto& [agg_pubkey, leaf_hash] = agg_pubkey_leaf_hash;
 439                  for (const auto& [pubkey, psig] : psigs) {
 440                      if (leaf_hash.IsNull()) {
 441                          SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PARTIAL_SIG), std::span{pubkey}, std::span{agg_pubkey});
 442                      } else {
 443                          SerializeToVector(s, CompactSizeWriter(PSBT_IN_MUSIG2_PARTIAL_SIG), std::span{pubkey}, std::span{agg_pubkey}, leaf_hash);
 444                      }
 445                      SerializeToVector(s, psig);
 446                  }
 447              }
 448          }
 449  
 450          // Write script sig
 451          if (!final_script_sig.empty()) {
 452              SerializeToVector(s, CompactSizeWriter(PSBT_IN_SCRIPTSIG));
 453              s << final_script_sig;
 454          }
 455          // write script witness
 456          if (!final_script_witness.IsNull()) {
 457              SerializeToVector(s, CompactSizeWriter(PSBT_IN_SCRIPTWITNESS));
 458              SerializeToVector(s, final_script_witness.stack);
 459          }
 460  
 461          // Write proprietary things
 462          for (const auto& entry : m_proprietary) {
 463              s << entry.key;
 464              s << entry.value;
 465          }
 466  
 467          // Write unknown things
 468          for (auto& entry : unknown) {
 469              s << entry.first;
 470              s << entry.second;
 471          }
 472  
 473          s << PSBT_SEPARATOR;
 474      }
 475  
 476  
 477      template <typename Stream>
 478      inline void Unserialize(Stream& s) {
 479          // Used for duplicate key detection
 480          std::set<std::vector<unsigned char>> key_lookup;
 481  
 482          // Read loop
 483          bool found_sep = false;
 484          while(!s.empty()) {
 485              // Read the key of format "<keylen><keytype><keydata>" after which
 486              // "key" will contain "<keytype><keydata>"
 487              std::vector<unsigned char> key;
 488              s >> key;
 489  
 490              // the key is empty if that was actually a separator byte
 491              // This is a special case for key lengths 0 as those are not allowed (except for separator)
 492              if (key.empty()) {
 493                  found_sep = true;
 494                  break;
 495              }
 496  
 497              // "skey" is used so that "key" is unchanged after reading keytype below
 498              SpanReader skey{key};
 499              // keytype is of the format compact size uint at the beginning of "key"
 500              uint64_t type = ReadCompactSize(skey);
 501  
 502              // Do stuff based on keytype "type", i.e., key checks, reading values of the
 503              // format "<valuelen><valuedata>" from the stream "s", and value checks
 504              switch(type) {
 505                  case PSBT_IN_NON_WITNESS_UTXO:
 506                  {
 507                      if (!key_lookup.emplace(key).second) {
 508                          throw std::ios_base::failure("Duplicate Key, input non-witness utxo already provided");
 509                      } else if (key.size() != 1) {
 510                          throw std::ios_base::failure("Non-witness utxo key is more than one byte type");
 511                      }
 512                      // Set the stream to unserialize with witness since this is always a valid network transaction
 513                      UnserializeFromVector(s, TX_WITH_WITNESS(non_witness_utxo));
 514                      break;
 515                  }
 516                  case PSBT_IN_WITNESS_UTXO:
 517                      if (!key_lookup.emplace(key).second) {
 518                          throw std::ios_base::failure("Duplicate Key, input witness utxo already provided");
 519                      } else if (key.size() != 1) {
 520                          throw std::ios_base::failure("Witness utxo key is more than one byte type");
 521                      }
 522                      UnserializeFromVector(s, witness_utxo);
 523                      break;
 524                  case PSBT_IN_PARTIAL_SIG:
 525                  {
 526                      // Make sure that the key is the size of pubkey + 1
 527                      if (key.size() != CPubKey::SIZE + 1 && key.size() != CPubKey::COMPRESSED_SIZE + 1) {
 528                          throw std::ios_base::failure("Size of key was not the expected size for the type partial signature pubkey");
 529                      }
 530                      // Read in the pubkey from key
 531                      CPubKey pubkey(key.begin() + 1, key.end());
 532                      if (!pubkey.IsFullyValid()) {
 533                         throw std::ios_base::failure("Invalid pubkey");
 534                      }
 535                      if (partial_sigs.contains(pubkey.GetID())) {
 536                          throw std::ios_base::failure("Duplicate Key, input partial signature for pubkey already provided");
 537                      }
 538  
 539                      // Read in the signature from value
 540                      std::vector<unsigned char> sig;
 541                      s >> sig;
 542  
 543                      // Check that the signature is validly encoded
 544                      if (sig.empty() || !CheckSignatureEncoding(sig, SCRIPT_VERIFY_DERSIG | SCRIPT_VERIFY_STRICTENC, nullptr)) {
 545                          throw std::ios_base::failure("Signature is not a valid encoding");
 546                      }
 547  
 548                      // Add to list
 549                      partial_sigs.emplace(pubkey.GetID(), SigPair(pubkey, std::move(sig)));
 550                      break;
 551                  }
 552                  case PSBT_IN_SIGHASH:
 553                      if (!key_lookup.emplace(key).second) {
 554                          throw std::ios_base::failure("Duplicate Key, input sighash type already provided");
 555                      } else if (key.size() != 1) {
 556                          throw std::ios_base::failure("Sighash type key is more than one byte type");
 557                      }
 558                      int sighash;
 559                      UnserializeFromVector(s, sighash);
 560                      sighash_type = sighash;
 561                      break;
 562                  case PSBT_IN_REDEEMSCRIPT:
 563                  {
 564                      if (!key_lookup.emplace(key).second) {
 565                          throw std::ios_base::failure("Duplicate Key, input redeemScript already provided");
 566                      } else if (key.size() != 1) {
 567                          throw std::ios_base::failure("Input redeemScript key is more than one byte type");
 568                      }
 569                      s >> redeem_script;
 570                      break;
 571                  }
 572                  case PSBT_IN_WITNESSSCRIPT:
 573                  {
 574                      if (!key_lookup.emplace(key).second) {
 575                          throw std::ios_base::failure("Duplicate Key, input witnessScript already provided");
 576                      } else if (key.size() != 1) {
 577                          throw std::ios_base::failure("Input witnessScript key is more than one byte type");
 578                      }
 579                      s >> witness_script;
 580                      break;
 581                  }
 582                  case PSBT_IN_BIP32_DERIVATION:
 583                  {
 584                      DeserializeHDKeypaths(s, key, hd_keypaths);
 585                      break;
 586                  }
 587                  case PSBT_IN_SCRIPTSIG:
 588                  {
 589                      if (!key_lookup.emplace(key).second) {
 590                          throw std::ios_base::failure("Duplicate Key, input final scriptSig already provided");
 591                      } else if (key.size() != 1) {
 592                          throw std::ios_base::failure("Final scriptSig key is more than one byte type");
 593                      }
 594                      s >> final_script_sig;
 595                      break;
 596                  }
 597                  case PSBT_IN_SCRIPTWITNESS:
 598                  {
 599                      if (!key_lookup.emplace(key).second) {
 600                          throw std::ios_base::failure("Duplicate Key, input final scriptWitness already provided");
 601                      } else if (key.size() != 1) {
 602                          throw std::ios_base::failure("Final scriptWitness key is more than one byte type");
 603                      }
 604                      UnserializeFromVector(s, final_script_witness.stack);
 605                      break;
 606                  }
 607                  case PSBT_IN_RIPEMD160:
 608                  {
 609                      // Make sure that the key is the size of a ripemd160 hash + 1
 610                      if (key.size() != CRIPEMD160::OUTPUT_SIZE + 1) {
 611                          throw std::ios_base::failure("Size of key was not the expected size for the type ripemd160 preimage");
 612                      }
 613                      // Read in the hash from key
 614                      std::vector<unsigned char> hash_vec(key.begin() + 1, key.end());
 615                      uint160 hash(hash_vec);
 616                      if (ripemd160_preimages.contains(hash)) {
 617                          throw std::ios_base::failure("Duplicate Key, input ripemd160 preimage already provided");
 618                      }
 619  
 620                      // Read in the preimage from value
 621                      std::vector<unsigned char> preimage;
 622                      s >> preimage;
 623  
 624                      // Add to preimages list
 625                      ripemd160_preimages.emplace(hash, std::move(preimage));
 626                      break;
 627                  }
 628                  case PSBT_IN_SHA256:
 629                  {
 630                      // Make sure that the key is the size of a sha256 hash + 1
 631                      if (key.size() != CSHA256::OUTPUT_SIZE + 1) {
 632                          throw std::ios_base::failure("Size of key was not the expected size for the type sha256 preimage");
 633                      }
 634                      // Read in the hash from key
 635                      std::vector<unsigned char> hash_vec(key.begin() + 1, key.end());
 636                      uint256 hash(hash_vec);
 637                      if (sha256_preimages.contains(hash)) {
 638                          throw std::ios_base::failure("Duplicate Key, input sha256 preimage already provided");
 639                      }
 640  
 641                      // Read in the preimage from value
 642                      std::vector<unsigned char> preimage;
 643                      s >> preimage;
 644  
 645                      // Add to preimages list
 646                      sha256_preimages.emplace(hash, std::move(preimage));
 647                      break;
 648                  }
 649                  case PSBT_IN_HASH160:
 650                  {
 651                      // Make sure that the key is the size of a hash160 hash + 1
 652                      if (key.size() != CHash160::OUTPUT_SIZE + 1) {
 653                          throw std::ios_base::failure("Size of key was not the expected size for the type hash160 preimage");
 654                      }
 655                      // Read in the hash from key
 656                      std::vector<unsigned char> hash_vec(key.begin() + 1, key.end());
 657                      uint160 hash(hash_vec);
 658                      if (hash160_preimages.contains(hash)) {
 659                          throw std::ios_base::failure("Duplicate Key, input hash160 preimage already provided");
 660                      }
 661  
 662                      // Read in the preimage from value
 663                      std::vector<unsigned char> preimage;
 664                      s >> preimage;
 665  
 666                      // Add to preimages list
 667                      hash160_preimages.emplace(hash, std::move(preimage));
 668                      break;
 669                  }
 670                  case PSBT_IN_HASH256:
 671                  {
 672                      // Make sure that the key is the size of a hash256 hash + 1
 673                      if (key.size() != CHash256::OUTPUT_SIZE + 1) {
 674                          throw std::ios_base::failure("Size of key was not the expected size for the type hash256 preimage");
 675                      }
 676                      // Read in the hash from key
 677                      std::vector<unsigned char> hash_vec(key.begin() + 1, key.end());
 678                      uint256 hash(hash_vec);
 679                      if (hash256_preimages.contains(hash)) {
 680                          throw std::ios_base::failure("Duplicate Key, input hash256 preimage already provided");
 681                      }
 682  
 683                      // Read in the preimage from value
 684                      std::vector<unsigned char> preimage;
 685                      s >> preimage;
 686  
 687                      // Add to preimages list
 688                      hash256_preimages.emplace(hash, std::move(preimage));
 689                      break;
 690                  }
 691                  case PSBT_IN_TAP_KEY_SIG:
 692                  {
 693                      if (!key_lookup.emplace(key).second) {
 694                          throw std::ios_base::failure("Duplicate Key, input Taproot key signature already provided");
 695                      } else if (key.size() != 1) {
 696                          throw std::ios_base::failure("Input Taproot key signature key is more than one byte type");
 697                      }
 698                      s >> m_tap_key_sig;
 699                      if (m_tap_key_sig.size() < 64) {
 700                          throw std::ios_base::failure("Input Taproot key path signature is shorter than 64 bytes");
 701                      } else if (m_tap_key_sig.size() > 65) {
 702                          throw std::ios_base::failure("Input Taproot key path signature is longer than 65 bytes");
 703                      }
 704                      break;
 705                  }
 706                  case PSBT_IN_TAP_SCRIPT_SIG:
 707                  {
 708                      if (!key_lookup.emplace(key).second) {
 709                          throw std::ios_base::failure("Duplicate Key, input Taproot script signature already provided");
 710                      } else if (key.size() != 65) {
 711                          throw std::ios_base::failure("Input Taproot script signature key is not 65 bytes");
 712                      }
 713                      SpanReader s_key{std::span{key}.subspan(1)};
 714                      XOnlyPubKey xonly;
 715                      uint256 hash;
 716                      s_key >> xonly;
 717                      s_key >> hash;
 718                      std::vector<unsigned char> sig;
 719                      s >> sig;
 720                      if (sig.size() < 64) {
 721                          throw std::ios_base::failure("Input Taproot script path signature is shorter than 64 bytes");
 722                      } else if (sig.size() > 65) {
 723                          throw std::ios_base::failure("Input Taproot script path signature is longer than 65 bytes");
 724                      }
 725                      m_tap_script_sigs.emplace(std::make_pair(xonly, hash), sig);
 726                      break;
 727                  }
 728                  case PSBT_IN_TAP_LEAF_SCRIPT:
 729                  {
 730                      if (!key_lookup.emplace(key).second) {
 731                          throw std::ios_base::failure("Duplicate Key, input Taproot leaf script already provided");
 732                      } else if (key.size() < 34) {
 733                          throw std::ios_base::failure("Taproot leaf script key is not at least 34 bytes");
 734                      } else if ((key.size() - 2) % 32 != 0) {
 735                          throw std::ios_base::failure("Input Taproot leaf script key's control block size is not valid");
 736                      }
 737                      std::vector<unsigned char> script_v;
 738                      s >> script_v;
 739                      if (script_v.empty()) {
 740                          throw std::ios_base::failure("Input Taproot leaf script must be at least 1 byte");
 741                      }
 742                      uint8_t leaf_ver = script_v.back();
 743                      script_v.pop_back();
 744                      const auto leaf_script = std::make_pair(script_v, (int)leaf_ver);
 745                      m_tap_scripts[leaf_script].insert(std::vector<unsigned char>(key.begin() + 1, key.end()));
 746                      break;
 747                  }
 748                  case PSBT_IN_TAP_BIP32_DERIVATION:
 749                  {
 750                      if (!key_lookup.emplace(key).second) {
 751                          throw std::ios_base::failure("Duplicate Key, input Taproot BIP32 keypath already provided");
 752                      } else if (key.size() != 33) {
 753                          throw std::ios_base::failure("Input Taproot BIP32 keypath key is not at 33 bytes");
 754                      }
 755                      SpanReader s_key{std::span{key}.subspan(1)};
 756                      XOnlyPubKey xonly;
 757                      s_key >> xonly;
 758                      std::set<uint256> leaf_hashes;
 759                      uint64_t value_len = ReadCompactSize(s);
 760                      size_t before_hashes = s.size();
 761                      s >> leaf_hashes;
 762                      size_t after_hashes = s.size();
 763                      size_t hashes_len = before_hashes - after_hashes;
 764                      if (hashes_len > value_len) {
 765                          throw std::ios_base::failure("Input Taproot BIP32 keypath has an invalid length");
 766                      }
 767                      size_t origin_len = value_len - hashes_len;
 768                      m_tap_bip32_paths.emplace(xonly, std::make_pair(leaf_hashes, DeserializeKeyOrigin(s, origin_len)));
 769                      break;
 770                  }
 771                  case PSBT_IN_TAP_INTERNAL_KEY:
 772                  {
 773                      if (!key_lookup.emplace(key).second) {
 774                          throw std::ios_base::failure("Duplicate Key, input Taproot internal key already provided");
 775                      } else if (key.size() != 1) {
 776                          throw std::ios_base::failure("Input Taproot internal key key is more than one byte type");
 777                      }
 778                      UnserializeFromVector(s, m_tap_internal_key);
 779                      break;
 780                  }
 781                  case PSBT_IN_TAP_MERKLE_ROOT:
 782                  {
 783                      if (!key_lookup.emplace(key).second) {
 784                          throw std::ios_base::failure("Duplicate Key, input Taproot merkle root already provided");
 785                      } else if (key.size() != 1) {
 786                          throw std::ios_base::failure("Input Taproot merkle root key is more than one byte type");
 787                      }
 788                      UnserializeFromVector(s, m_tap_merkle_root);
 789                      break;
 790                  }
 791                  case PSBT_IN_MUSIG2_PARTICIPANT_PUBKEYS:
 792                  {
 793                      if (!key_lookup.emplace(key).second) {
 794                          throw std::ios_base::failure("Duplicate Key, input participant pubkeys for an aggregate key already provided");
 795                      } else if (key.size() != CPubKey::COMPRESSED_SIZE + 1) {
 796                          throw std::ios_base::failure("Input musig2 participants pubkeys aggregate key is not 34 bytes");
 797                      }
 798                      DeserializeMuSig2ParticipantPubkeys(s, skey, m_musig2_participants, std::string{"Input"});
 799                      break;
 800                  }
 801                  case PSBT_IN_MUSIG2_PUB_NONCE:
 802                  {
 803                      if (!key_lookup.emplace(key).second) {
 804                          throw std::ios_base::failure("Duplicate Key, input musig2 pubnonce already provided");
 805                      } else if (key.size() != 2 * CPubKey::COMPRESSED_SIZE + 1 && key.size() != 2 * CPubKey::COMPRESSED_SIZE + CSHA256::OUTPUT_SIZE + 1) {
 806                          throw std::ios_base::failure("Input musig2 pubnonce key is not expected size of 67 or 99 bytes");
 807                      }
 808                      CPubKey agg_pub, part_pub;
 809                      uint256 leaf_hash;
 810                      DeserializeMuSig2ParticipantDataIdentifier(skey, agg_pub, part_pub, leaf_hash);
 811  
 812                      std::vector<uint8_t> pubnonce;
 813                      s >> pubnonce;
 814                      if (pubnonce.size() != MUSIG2_PUBNONCE_SIZE) {
 815                          throw std::ios_base::failure("Input musig2 pubnonce value is not 66 bytes");
 816                      }
 817  
 818                      m_musig2_pubnonces[std::make_pair(agg_pub, leaf_hash)].emplace(part_pub, pubnonce);
 819                      break;
 820                  }
 821                  case PSBT_IN_MUSIG2_PARTIAL_SIG:
 822                  {
 823                      if (!key_lookup.emplace(key).second) {
 824                          throw std::ios_base::failure("Duplicate Key, input musig2 partial sig already provided");
 825                      } else if (key.size() != 2 * CPubKey::COMPRESSED_SIZE + 1 && key.size() != 2 * CPubKey::COMPRESSED_SIZE + CSHA256::OUTPUT_SIZE + 1) {
 826                          throw std::ios_base::failure("Input musig2 partial sig key is not expected size of 67 or 99 bytes");
 827                      }
 828                      CPubKey agg_pub, part_pub;
 829                      uint256 leaf_hash;
 830                      DeserializeMuSig2ParticipantDataIdentifier(skey, agg_pub, part_pub, leaf_hash);
 831  
 832                      uint256 partial_sig;
 833                      UnserializeFromVector(s, partial_sig);
 834  
 835                      m_musig2_partial_sigs[std::make_pair(agg_pub, leaf_hash)].emplace(part_pub, partial_sig);
 836                      break;
 837                  }
 838                  case PSBT_IN_PROPRIETARY:
 839                  {
 840                      PSBTProprietary this_prop;
 841                      skey >> this_prop.identifier;
 842                      this_prop.subtype = ReadCompactSize(skey);
 843                      this_prop.key = key;
 844  
 845                      if (m_proprietary.contains(this_prop)) {
 846                          throw std::ios_base::failure("Duplicate Key, proprietary key already found");
 847                      }
 848                      s >> this_prop.value;
 849                      m_proprietary.insert(this_prop);
 850                      break;
 851                  }
 852                  // Unknown stuff
 853                  default:
 854                      if (unknown.contains(key)) {
 855                          throw std::ios_base::failure("Duplicate Key, key for unknown value already provided");
 856                      }
 857                      // Read in the value
 858                      std::vector<unsigned char> val_bytes;
 859                      s >> val_bytes;
 860                      unknown.emplace(std::move(key), std::move(val_bytes));
 861                      break;
 862              }
 863          }
 864  
 865          if (!found_sep) {
 866              throw std::ios_base::failure("Separator is missing at the end of an input map");
 867          }
 868      }
 869  
 870      template <typename Stream>
 871      PSBTInput(deserialize_type, Stream& s) {
 872          Unserialize(s);
 873      }
 874  };
 875  
 876  /** A structure for PSBTs which contains per output information */
 877  struct PSBTOutput
 878  {
 879      CScript redeem_script;
 880      CScript witness_script;
 881      std::map<CPubKey, KeyOriginInfo> hd_keypaths;
 882      XOnlyPubKey m_tap_internal_key;
 883      std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> m_tap_tree;
 884      std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> m_tap_bip32_paths;
 885      std::map<CPubKey, std::vector<CPubKey>> m_musig2_participants;
 886      std::map<std::vector<unsigned char>, std::vector<unsigned char>> unknown;
 887      std::set<PSBTProprietary> m_proprietary;
 888  
 889      bool IsNull() const;
 890      void FillSignatureData(SignatureData& sigdata) const;
 891      void FromSignatureData(const SignatureData& sigdata);
 892      void Merge(const PSBTOutput& output);
 893      PSBTOutput() = default;
 894  
 895      template <typename Stream>
 896      inline void Serialize(Stream& s) const {
 897          // Write the redeem script
 898          if (!redeem_script.empty()) {
 899              SerializeToVector(s, CompactSizeWriter(PSBT_OUT_REDEEMSCRIPT));
 900              s << redeem_script;
 901          }
 902  
 903          // Write the witness script
 904          if (!witness_script.empty()) {
 905              SerializeToVector(s, CompactSizeWriter(PSBT_OUT_WITNESSSCRIPT));
 906              s << witness_script;
 907          }
 908  
 909          // Write any hd keypaths
 910          SerializeHDKeypaths(s, hd_keypaths, CompactSizeWriter(PSBT_OUT_BIP32_DERIVATION));
 911  
 912          // Write proprietary things
 913          for (const auto& entry : m_proprietary) {
 914              s << entry.key;
 915              s << entry.value;
 916          }
 917  
 918          // Write taproot internal key
 919          if (!m_tap_internal_key.IsNull()) {
 920              SerializeToVector(s, PSBT_OUT_TAP_INTERNAL_KEY);
 921              s << ToByteVector(m_tap_internal_key);
 922          }
 923  
 924          // Write taproot tree
 925          if (!m_tap_tree.empty()) {
 926              SerializeToVector(s, PSBT_OUT_TAP_TREE);
 927              std::vector<unsigned char> value;
 928              VectorWriter s_value{value, 0};
 929              for (const auto& [depth, leaf_ver, script] : m_tap_tree) {
 930                  s_value << depth;
 931                  s_value << leaf_ver;
 932                  s_value << script;
 933              }
 934              s << value;
 935          }
 936  
 937          // Write taproot bip32 keypaths
 938          for (const auto& [xonly, leaf] : m_tap_bip32_paths) {
 939              const auto& [leaf_hashes, origin] = leaf;
 940              SerializeToVector(s, PSBT_OUT_TAP_BIP32_DERIVATION, xonly);
 941              std::vector<unsigned char> value;
 942              VectorWriter s_value{value, 0};
 943              s_value << leaf_hashes;
 944              SerializeKeyOrigin(s_value, origin);
 945              s << value;
 946          }
 947  
 948          // Write MuSig2 Participants
 949          for (const auto& [agg_pubkey, part_pubs] : m_musig2_participants) {
 950              SerializeToVector(s, CompactSizeWriter(PSBT_OUT_MUSIG2_PARTICIPANT_PUBKEYS), std::span{agg_pubkey});
 951              std::vector<unsigned char> value;
 952              VectorWriter s_value{value, 0};
 953              for (auto& pk : part_pubs) {
 954                  s_value << std::span{pk};
 955              }
 956              s << value;
 957          }
 958  
 959          // Write unknown things
 960          for (auto& entry : unknown) {
 961              s << entry.first;
 962              s << entry.second;
 963          }
 964  
 965          s << PSBT_SEPARATOR;
 966      }
 967  
 968  
 969      template <typename Stream>
 970      inline void Unserialize(Stream& s) {
 971          // Used for duplicate key detection
 972          std::set<std::vector<unsigned char>> key_lookup;
 973  
 974          // Read loop
 975          bool found_sep = false;
 976          while(!s.empty()) {
 977              // Read the key of format "<keylen><keytype><keydata>" after which
 978              // "key" will contain "<keytype><keydata>"
 979              std::vector<unsigned char> key;
 980              s >> key;
 981  
 982              // the key is empty if that was actually a separator byte
 983              // This is a special case for key lengths 0 as those are not allowed (except for separator)
 984              if (key.empty()) {
 985                  found_sep = true;
 986                  break;
 987              }
 988  
 989              // "skey" is used so that "key" is unchanged after reading keytype below
 990              SpanReader skey{key};
 991              // keytype is of the format compact size uint at the beginning of "key"
 992              uint64_t type = ReadCompactSize(skey);
 993  
 994              // Do stuff based on keytype "type", i.e., key checks, reading values of the
 995              // format "<valuelen><valuedata>" from the stream "s", and value checks
 996              switch(type) {
 997                  case PSBT_OUT_REDEEMSCRIPT:
 998                  {
 999                      if (!key_lookup.emplace(key).second) {
1000                          throw std::ios_base::failure("Duplicate Key, output redeemScript already provided");
1001                      } else if (key.size() != 1) {
1002                          throw std::ios_base::failure("Output redeemScript key is more than one byte type");
1003                      }
1004                      s >> redeem_script;
1005                      break;
1006                  }
1007                  case PSBT_OUT_WITNESSSCRIPT:
1008                  {
1009                      if (!key_lookup.emplace(key).second) {
1010                          throw std::ios_base::failure("Duplicate Key, output witnessScript already provided");
1011                      } else if (key.size() != 1) {
1012                          throw std::ios_base::failure("Output witnessScript key is more than one byte type");
1013                      }
1014                      s >> witness_script;
1015                      break;
1016                  }
1017                  case PSBT_OUT_BIP32_DERIVATION:
1018                  {
1019                      DeserializeHDKeypaths(s, key, hd_keypaths);
1020                      break;
1021                  }
1022                  case PSBT_OUT_TAP_INTERNAL_KEY:
1023                  {
1024                      if (!key_lookup.emplace(key).second) {
1025                          throw std::ios_base::failure("Duplicate Key, output Taproot internal key already provided");
1026                      } else if (key.size() != 1) {
1027                          throw std::ios_base::failure("Output Taproot internal key key is more than one byte type");
1028                      }
1029                      UnserializeFromVector(s, m_tap_internal_key);
1030                      break;
1031                  }
1032                  case PSBT_OUT_TAP_TREE:
1033                  {
1034                      if (!key_lookup.emplace(key).second) {
1035                          throw std::ios_base::failure("Duplicate Key, output Taproot tree already provided");
1036                      } else if (key.size() != 1) {
1037                          throw std::ios_base::failure("Output Taproot tree key is more than one byte type");
1038                      }
1039                      std::vector<unsigned char> tree_v;
1040                      s >> tree_v;
1041                      SpanReader s_tree{tree_v};
1042                      if (s_tree.empty()) {
1043                          throw std::ios_base::failure("Output Taproot tree must not be empty");
1044                      }
1045                      TaprootBuilder builder;
1046                      while (!s_tree.empty()) {
1047                          uint8_t depth;
1048                          uint8_t leaf_ver;
1049                          std::vector<unsigned char> script;
1050                          s_tree >> depth;
1051                          s_tree >> leaf_ver;
1052                          s_tree >> script;
1053                          if (depth > TAPROOT_CONTROL_MAX_NODE_COUNT) {
1054                              throw std::ios_base::failure("Output Taproot tree has as leaf greater than Taproot maximum depth");
1055                          }
1056                          if ((leaf_ver & ~TAPROOT_LEAF_MASK) != 0) {
1057                              throw std::ios_base::failure("Output Taproot tree has a leaf with an invalid leaf version");
1058                          }
1059                          m_tap_tree.emplace_back(depth, leaf_ver, script);
1060                          builder.Add((int)depth, script, (int)leaf_ver, /*track=*/true);
1061                      }
1062                      if (!builder.IsComplete()) {
1063                          throw std::ios_base::failure("Output Taproot tree is malformed");
1064                      }
1065                      break;
1066                  }
1067                  case PSBT_OUT_TAP_BIP32_DERIVATION:
1068                  {
1069                      if (!key_lookup.emplace(key).second) {
1070                          throw std::ios_base::failure("Duplicate Key, output Taproot BIP32 keypath already provided");
1071                      } else if (key.size() != 33) {
1072                          throw std::ios_base::failure("Output Taproot BIP32 keypath key is not at 33 bytes");
1073                      }
1074                      XOnlyPubKey xonly(uint256(std::span<uint8_t>(key).last(32)));
1075                      std::set<uint256> leaf_hashes;
1076                      uint64_t value_len = ReadCompactSize(s);
1077                      size_t before_hashes = s.size();
1078                      s >> leaf_hashes;
1079                      size_t after_hashes = s.size();
1080                      size_t hashes_len = before_hashes - after_hashes;
1081                      if (hashes_len > value_len) {
1082                          throw std::ios_base::failure("Output Taproot BIP32 keypath has an invalid length");
1083                      }
1084                      size_t origin_len = value_len - hashes_len;
1085                      m_tap_bip32_paths.emplace(xonly, std::make_pair(leaf_hashes, DeserializeKeyOrigin(s, origin_len)));
1086                      break;
1087                  }
1088                  case PSBT_OUT_MUSIG2_PARTICIPANT_PUBKEYS:
1089                  {
1090                      if (!key_lookup.emplace(key).second) {
1091                          throw std::ios_base::failure("Duplicate Key, output participant pubkeys for an aggregate key already provided");
1092                      } else if (key.size() != CPubKey::COMPRESSED_SIZE + 1) {
1093                          throw std::ios_base::failure("Output musig2 participants pubkeys aggregate key is not 34 bytes");
1094                      }
1095                      DeserializeMuSig2ParticipantPubkeys(s, skey, m_musig2_participants, std::string{"Output"});
1096                      break;
1097                  }
1098                  case PSBT_OUT_PROPRIETARY:
1099                  {
1100                      PSBTProprietary this_prop;
1101                      skey >> this_prop.identifier;
1102                      this_prop.subtype = ReadCompactSize(skey);
1103                      this_prop.key = key;
1104  
1105                      if (m_proprietary.contains(this_prop)) {
1106                          throw std::ios_base::failure("Duplicate Key, proprietary key already found");
1107                      }
1108                      s >> this_prop.value;
1109                      m_proprietary.insert(this_prop);
1110                      break;
1111                  }
1112                  // Unknown stuff
1113                  default: {
1114                      if (unknown.contains(key)) {
1115                          throw std::ios_base::failure("Duplicate Key, key for unknown value already provided");
1116                      }
1117                      // Read in the value
1118                      std::vector<unsigned char> val_bytes;
1119                      s >> val_bytes;
1120                      unknown.emplace(std::move(key), std::move(val_bytes));
1121                      break;
1122                  }
1123              }
1124          }
1125  
1126          if (!found_sep) {
1127              throw std::ios_base::failure("Separator is missing at the end of an output map");
1128          }
1129      }
1130  
1131      template <typename Stream>
1132      PSBTOutput(deserialize_type, Stream& s) {
1133          Unserialize(s);
1134      }
1135  };
1136  
1137  /** A version of CTransaction with the PSBT format*/
1138  struct PartiallySignedTransaction
1139  {
1140      std::optional<CMutableTransaction> tx;
1141      // We use a vector of CExtPubKey in the event that there happens to be the same KeyOriginInfos for different CExtPubKeys
1142      // Note that this map swaps the key and values from the serialization
1143      std::map<KeyOriginInfo, std::set<CExtPubKey>> m_xpubs;
1144      std::vector<PSBTInput> inputs;
1145      std::vector<PSBTOutput> outputs;
1146      std::map<std::vector<unsigned char>, std::vector<unsigned char>> unknown;
1147      std::optional<uint32_t> m_version;
1148      std::set<PSBTProprietary> m_proprietary;
1149  
1150      bool IsNull() const;
1151      uint32_t GetVersion() const;
1152  
1153      /** Merge psbt into this. The two psbts must have the same underlying CTransaction (i.e. the
1154        * same actual Bitcoin transaction.) Returns true if the merge succeeded, false otherwise. */
1155      [[nodiscard]] bool Merge(const PartiallySignedTransaction& psbt);
1156      bool AddInput(const CTxIn& txin, PSBTInput& psbtin);
1157      bool AddOutput(const CTxOut& txout, const PSBTOutput& psbtout);
1158      PartiallySignedTransaction() = default;
1159      explicit PartiallySignedTransaction(const CMutableTransaction& tx);
1160      /**
1161       * Finds the UTXO for a given input index
1162       *
1163       * @param[out] utxo The UTXO of the input if found
1164       * @param[in] input_index Index of the input to retrieve the UTXO of
1165       * @return Whether the UTXO for the specified input was found
1166       */
1167      bool GetInputUTXO(CTxOut& utxo, int input_index) const;
1168  
1169      template <typename Stream>
1170      inline void Serialize(Stream& s) const {
1171  
1172          // magic bytes
1173          s << PSBT_MAGIC_BYTES;
1174  
1175          // unsigned tx flag
1176          SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_UNSIGNED_TX));
1177  
1178          // Write serialized tx to a stream
1179          SerializeToVector(s, TX_NO_WITNESS(*tx));
1180  
1181          // Write xpubs
1182          for (const auto& xpub_pair : m_xpubs) {
1183              for (const auto& xpub : xpub_pair.second) {
1184                  unsigned char ser_xpub[BIP32_EXTKEY_WITH_VERSION_SIZE];
1185                  xpub.EncodeWithVersion(ser_xpub);
1186                  // Note that the serialization swaps the key and value
1187                  // The xpub is the key (for uniqueness) while the path is the value
1188                  SerializeToVector(s, PSBT_GLOBAL_XPUB, ser_xpub);
1189                  SerializeHDKeypath(s, xpub_pair.first);
1190              }
1191          }
1192  
1193          // PSBT version
1194          if (GetVersion() > 0) {
1195              SerializeToVector(s, CompactSizeWriter(PSBT_GLOBAL_VERSION));
1196              SerializeToVector(s, *m_version);
1197          }
1198  
1199          // Write proprietary things
1200          for (const auto& entry : m_proprietary) {
1201              s << entry.key;
1202              s << entry.value;
1203          }
1204  
1205          // Write the unknown things
1206          for (auto& entry : unknown) {
1207              s << entry.first;
1208              s << entry.second;
1209          }
1210  
1211          // Separator
1212          s << PSBT_SEPARATOR;
1213  
1214          // Write inputs
1215          for (const PSBTInput& input : inputs) {
1216              s << input;
1217          }
1218          // Write outputs
1219          for (const PSBTOutput& output : outputs) {
1220              s << output;
1221          }
1222      }
1223  
1224  
1225      template <typename Stream>
1226      inline void Unserialize(Stream& s) {
1227          // Read the magic bytes
1228          uint8_t magic[5];
1229          s >> magic;
1230          if (!std::equal(magic, magic + 5, PSBT_MAGIC_BYTES)) {
1231              throw std::ios_base::failure("Invalid PSBT magic bytes");
1232          }
1233  
1234          // Used for duplicate key detection
1235          std::set<std::vector<unsigned char>> key_lookup;
1236  
1237          // Track the global xpubs we have already seen. Just for sanity checking
1238          std::set<CExtPubKey> global_xpubs;
1239  
1240          // Read global data
1241          bool found_sep = false;
1242          while(!s.empty()) {
1243              // Read the key of format "<keylen><keytype><keydata>" after which
1244              // "key" will contain "<keytype><keydata>"
1245              std::vector<unsigned char> key;
1246              s >> key;
1247  
1248              // the key is empty if that was actually a separator byte
1249              // This is a special case for key lengths 0 as those are not allowed (except for separator)
1250              if (key.empty()) {
1251                  found_sep = true;
1252                  break;
1253              }
1254  
1255              // "skey" is used so that "key" is unchanged after reading keytype below
1256              SpanReader skey{key};
1257              // keytype is of the format compact size uint at the beginning of "key"
1258              uint64_t type = ReadCompactSize(skey);
1259  
1260              // Do stuff based on keytype "type", i.e., key checks, reading values of the
1261              // format "<valuelen><valuedata>" from the stream "s", and value checks
1262              switch(type) {
1263                  case PSBT_GLOBAL_UNSIGNED_TX:
1264                  {
1265                      if (!key_lookup.emplace(key).second) {
1266                          throw std::ios_base::failure("Duplicate Key, unsigned tx already provided");
1267                      } else if (key.size() != 1) {
1268                          throw std::ios_base::failure("Global unsigned tx key is more than one byte type");
1269                      }
1270                      CMutableTransaction mtx;
1271                      // Set the stream to serialize with non-witness since this should always be non-witness
1272                      UnserializeFromVector(s, TX_NO_WITNESS(mtx));
1273                      tx = std::move(mtx);
1274                      // Make sure that all scriptSigs and scriptWitnesses are empty
1275                      for (const CTxIn& txin : tx->vin) {
1276                          if (!txin.scriptSig.empty() || !txin.scriptWitness.IsNull()) {
1277                              throw std::ios_base::failure("Unsigned tx does not have empty scriptSigs and scriptWitnesses.");
1278                          }
1279                      }
1280                      break;
1281                  }
1282                  case PSBT_GLOBAL_XPUB:
1283                  {
1284                      if (key.size() != BIP32_EXTKEY_WITH_VERSION_SIZE + 1) {
1285                          throw std::ios_base::failure("Size of key was not the expected size for the type global xpub");
1286                      }
1287                      // Read in the xpub from key
1288                      CExtPubKey xpub;
1289                      xpub.DecodeWithVersion(&key.data()[1]);
1290                      if (!xpub.pubkey.IsFullyValid()) {
1291                         throw std::ios_base::failure("Invalid pubkey");
1292                      }
1293                      if (global_xpubs.contains(xpub)) {
1294                         throw std::ios_base::failure("Duplicate key, global xpub already provided");
1295                      }
1296                      global_xpubs.insert(xpub);
1297                      // Read in the keypath from stream
1298                      KeyOriginInfo keypath;
1299                      DeserializeHDKeypath(s, keypath);
1300  
1301                      // Note that we store these swapped to make searches faster.
1302                      // Serialization uses xpub -> keypath to enqure key uniqueness
1303                      if (!m_xpubs.contains(keypath)) {
1304                          // Make a new set to put the xpub in
1305                          m_xpubs[keypath] = {xpub};
1306                      } else {
1307                          // Insert xpub into existing set
1308                          m_xpubs[keypath].insert(xpub);
1309                      }
1310                      break;
1311                  }
1312                  case PSBT_GLOBAL_VERSION:
1313                  {
1314                      if (m_version) {
1315                          throw std::ios_base::failure("Duplicate Key, version already provided");
1316                      } else if (key.size() != 1) {
1317                          throw std::ios_base::failure("Global version key is more than one byte type");
1318                      }
1319                      uint32_t v;
1320                      UnserializeFromVector(s, v);
1321                      m_version = v;
1322                      if (*m_version > PSBT_HIGHEST_VERSION) {
1323                          throw std::ios_base::failure("Unsupported version number");
1324                      }
1325                      break;
1326                  }
1327                  case PSBT_GLOBAL_PROPRIETARY:
1328                  {
1329                      PSBTProprietary this_prop;
1330                      skey >> this_prop.identifier;
1331                      this_prop.subtype = ReadCompactSize(skey);
1332                      this_prop.key = key;
1333  
1334                      if (m_proprietary.contains(this_prop)) {
1335                          throw std::ios_base::failure("Duplicate Key, proprietary key already found");
1336                      }
1337                      s >> this_prop.value;
1338                      m_proprietary.insert(this_prop);
1339                      break;
1340                  }
1341                  // Unknown stuff
1342                  default: {
1343                      if (unknown.contains(key)) {
1344                          throw std::ios_base::failure("Duplicate Key, key for unknown value already provided");
1345                      }
1346                      // Read in the value
1347                      std::vector<unsigned char> val_bytes;
1348                      s >> val_bytes;
1349                      unknown.emplace(std::move(key), std::move(val_bytes));
1350                  }
1351              }
1352          }
1353  
1354          if (!found_sep) {
1355              throw std::ios_base::failure("Separator is missing at the end of the global map");
1356          }
1357  
1358          // Make sure that we got an unsigned tx
1359          if (!tx) {
1360              throw std::ios_base::failure("No unsigned transaction was provided");
1361          }
1362  
1363          // Read input data
1364          unsigned int i = 0;
1365          while (!s.empty() && i < tx->vin.size()) {
1366              PSBTInput input;
1367              s >> input;
1368              inputs.push_back(input);
1369  
1370              // Make sure the non-witness utxo matches the outpoint
1371              if (input.non_witness_utxo) {
1372                  if (input.non_witness_utxo->GetHash() != tx->vin[i].prevout.hash) {
1373                      throw std::ios_base::failure("Non-witness UTXO does not match outpoint hash");
1374                  }
1375                  if (tx->vin[i].prevout.n >= input.non_witness_utxo->vout.size()) {
1376                      throw std::ios_base::failure("Input specifies output index that does not exist");
1377                  }
1378              }
1379              ++i;
1380          }
1381          // Make sure that the number of inputs matches the number of inputs in the transaction
1382          if (inputs.size() != tx->vin.size()) {
1383              throw std::ios_base::failure("Inputs provided does not match the number of inputs in transaction.");
1384          }
1385  
1386          // Read output data
1387          i = 0;
1388          while (!s.empty() && i < tx->vout.size()) {
1389              PSBTOutput output;
1390              s >> output;
1391              outputs.push_back(output);
1392              ++i;
1393          }
1394          // Make sure that the number of outputs matches the number of outputs in the transaction
1395          if (outputs.size() != tx->vout.size()) {
1396              throw std::ios_base::failure("Outputs provided does not match the number of outputs in transaction.");
1397          }
1398      }
1399  
1400      template <typename Stream>
1401      PartiallySignedTransaction(deserialize_type, Stream& s) {
1402          Unserialize(s);
1403      }
1404  };
1405  
1406  enum class PSBTRole {
1407      CREATOR,
1408      UPDATER,
1409      SIGNER,
1410      FINALIZER,
1411      EXTRACTOR
1412  };
1413  
1414  std::string PSBTRoleName(PSBTRole role);
1415  
1416  /** Compute a PrecomputedTransactionData object from a psbt. */
1417  PrecomputedTransactionData PrecomputePSBTData(const PartiallySignedTransaction& psbt);
1418  
1419  /** Checks whether a PSBTInput is already signed by checking for non-null finalized fields. */
1420  bool PSBTInputSigned(const PSBTInput& input);
1421  
1422  /** Checks whether a PSBTInput is already signed by doing script verification using final fields. */
1423  bool PSBTInputSignedAndVerified(const PartiallySignedTransaction& psbt, unsigned int input_index, const PrecomputedTransactionData* txdata);
1424  
1425  /** Signs a PSBTInput, verifying that all provided data matches what is being signed.
1426   *
1427   * txdata should be the output of PrecomputePSBTData (which can be shared across
1428   * multiple SignPSBTInput calls). If it is nullptr, a dummy signature will be created.
1429   **/
1430  [[nodiscard]] PSBTError SignPSBTInput(const SigningProvider& provider, PartiallySignedTransaction& psbt, int index, const PrecomputedTransactionData* txdata, const common::PSBTFillOptions& options, SignatureData* out_sigdata = nullptr);
1431  
1432  /**  Reduces the size of the PSBT by dropping unnecessary `non_witness_utxos` (i.e. complete previous transactions) from a psbt when all inputs are segwit v1. */
1433  void RemoveUnnecessaryTransactions(PartiallySignedTransaction& psbtx);
1434  
1435  /** Counts the unsigned inputs of a PSBT. */
1436  size_t CountPSBTUnsignedInputs(const PartiallySignedTransaction& psbt);
1437  
1438  /** Updates a PSBTOutput with information from provider.
1439   *
1440   * This fills in the redeem_script, witness_script, and hd_keypaths where possible.
1441   */
1442  void UpdatePSBTOutput(const SigningProvider& provider, PartiallySignedTransaction& psbt, int index);
1443  
1444  /**
1445   * Finalizes a PSBT if possible, combining partial signatures.
1446   *
1447   * @param[in,out] psbtx PartiallySignedTransaction to finalize
1448   * return True if the PSBT is now complete, false otherwise
1449   */
1450  bool FinalizePSBT(PartiallySignedTransaction& psbtx);
1451  
1452  /**
1453   * Finalizes a PSBT if possible, and extracts it to a CMutableTransaction if it could be finalized.
1454   *
1455   * @param[in]  psbtx PartiallySignedTransaction
1456   * @param[out] result CMutableTransaction representing the complete transaction, if successful
1457   * @return True if we successfully extracted the transaction, false otherwise
1458   */
1459  bool FinalizeAndExtractPSBT(PartiallySignedTransaction& psbtx, CMutableTransaction& result);
1460  
1461  /**
1462   * Combines PSBTs with the same underlying transaction, resulting in a single PSBT with all partial signatures from each input.
1463   *
1464   * @param[out] out   the combined PSBT, if successful
1465   * @param[in]  psbtxs the PSBTs to combine
1466   * @return True if we successfully combined the transactions, false if they were not compatible
1467   */
1468  [[nodiscard]] bool CombinePSBTs(PartiallySignedTransaction& out, const std::vector<PartiallySignedTransaction>& psbtxs);
1469  
1470  //! Decode a base64ed PSBT into a PartiallySignedTransaction
1471  [[nodiscard]] bool DecodeBase64PSBT(PartiallySignedTransaction& decoded_psbt, const std::string& base64_psbt, std::string& error);
1472  //! Decode a raw (binary blob) PSBT into a PartiallySignedTransaction
1473  [[nodiscard]] bool DecodeRawPSBT(PartiallySignedTransaction& decoded_psbt, std::span<const std::byte> raw_psbt, std::string& error);
1474  
1475  #endif // BITCOIN_PSBT_H