1  // Copyright (c) 2009-2010 Satoshi Nakamoto
  2  // Copyright (c) 2009-present The Bitcoin Core developers
  3  // Distributed under the MIT software license, see the accompanying
  4  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  5  
  6  #include <script/keyorigin.h>
  7  #include <script/interpreter.h>
  8  #include <script/signingprovider.h>
  9  
 10  #include <logging.h>
 11  
 12  const SigningProvider& DUMMY_SIGNING_PROVIDER = SigningProvider();
 13  
 14  template<typename M, typename K, typename V>
 15  bool LookupHelper(const M& map, const K& key, V& value)
 16  {
 17      auto it = map.find(key);
 18      if (it != map.end()) {
 19          value = it->second;
 20          return true;
 21      }
 22      return false;
 23  }
 24  
 25  bool HidingSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const
 26  {
 27      return m_provider->GetCScript(scriptid, script);
 28  }
 29  
 30  bool HidingSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const
 31  {
 32      return m_provider->GetPubKey(keyid, pubkey);
 33  }
 34  
 35  bool HidingSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const
 36  {
 37      if (m_hide_secret) return false;
 38      return m_provider->GetKey(keyid, key);
 39  }
 40  
 41  bool HidingSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const
 42  {
 43      if (m_hide_origin) return false;
 44      return m_provider->GetKeyOrigin(keyid, info);
 45  }
 46  
 47  bool HidingSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const
 48  {
 49      return m_provider->GetTaprootSpendData(output_key, spenddata);
 50  }
 51  bool HidingSigningProvider::GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const
 52  {
 53      return m_provider->GetTaprootBuilder(output_key, builder);
 54  }
 55  std::vector<CPubKey> HidingSigningProvider::GetMuSig2ParticipantPubkeys(const CPubKey& pubkey) const
 56  {
 57      if (m_hide_origin) return {};
 58      return m_provider->GetMuSig2ParticipantPubkeys(pubkey);
 59  }
 60  
 61  std::map<CPubKey, std::vector<CPubKey>> HidingSigningProvider::GetAllMuSig2ParticipantPubkeys() const
 62  {
 63      return m_provider->GetAllMuSig2ParticipantPubkeys();
 64  }
 65  
 66  void HidingSigningProvider::SetMuSig2SecNonce(const uint256& id, MuSig2SecNonce&& nonce) const
 67  {
 68      m_provider->SetMuSig2SecNonce(id, std::move(nonce));
 69  }
 70  
 71  std::optional<std::reference_wrapper<MuSig2SecNonce>> HidingSigningProvider::GetMuSig2SecNonce(const uint256& session_id) const
 72  {
 73      return m_provider->GetMuSig2SecNonce(session_id);
 74  }
 75  
 76  void HidingSigningProvider::DeleteMuSig2Session(const uint256& session_id) const
 77  {
 78      m_provider->DeleteMuSig2Session(session_id);
 79  }
 80  
 81  bool FlatSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const { return LookupHelper(scripts, scriptid, script); }
 82  bool FlatSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const { return LookupHelper(pubkeys, keyid, pubkey); }
 83  bool FlatSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const
 84  {
 85      std::pair<CPubKey, KeyOriginInfo> out;
 86      bool ret = LookupHelper(origins, keyid, out);
 87      if (ret) info = std::move(out.second);
 88      return ret;
 89  }
 90  bool FlatSigningProvider::HaveKey(const CKeyID &keyid) const
 91  {
 92      CKey key;
 93      return LookupHelper(keys, keyid, key);
 94  }
 95  bool FlatSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const { return LookupHelper(keys, keyid, key); }
 96  bool FlatSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const
 97  {
 98      TaprootBuilder builder;
 99      if (LookupHelper(tr_trees, output_key, builder)) {
100          spenddata = builder.GetSpendData();
101          return true;
102      }
103      return false;
104  }
105  bool FlatSigningProvider::GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const
106  {
107      return LookupHelper(tr_trees, output_key, builder);
108  }
109  
110  std::vector<CPubKey> FlatSigningProvider::GetMuSig2ParticipantPubkeys(const CPubKey& pubkey) const
111  {
112      std::vector<CPubKey> participant_pubkeys;
113      LookupHelper(aggregate_pubkeys, pubkey, participant_pubkeys);
114      return participant_pubkeys;
115  }
116  
117  std::map<CPubKey, std::vector<CPubKey>> FlatSigningProvider::GetAllMuSig2ParticipantPubkeys() const
118  {
119      return aggregate_pubkeys;
120  }
121  
122  void FlatSigningProvider::SetMuSig2SecNonce(const uint256& session_id, MuSig2SecNonce&& nonce) const
123  {
124      if (!Assume(musig2_secnonces)) return;
125      auto [it, inserted] = musig2_secnonces->try_emplace(session_id, std::move(nonce));
126      // No secnonce should exist for this session yet.
127      Assert(inserted);
128  }
129  
130  std::optional<std::reference_wrapper<MuSig2SecNonce>> FlatSigningProvider::GetMuSig2SecNonce(const uint256& session_id) const
131  {
132      if (!Assume(musig2_secnonces)) return std::nullopt;
133      const auto& it = musig2_secnonces->find(session_id);
134      if (it == musig2_secnonces->end()) return std::nullopt;
135      return it->second;
136  }
137  
138  void FlatSigningProvider::DeleteMuSig2Session(const uint256& session_id) const
139  {
140      if (!Assume(musig2_secnonces)) return;
141      musig2_secnonces->erase(session_id);
142  }
143  
144  FlatSigningProvider& FlatSigningProvider::Merge(FlatSigningProvider&& b)
145  {
146      scripts.merge(b.scripts);
147      pubkeys.merge(b.pubkeys);
148      keys.merge(b.keys);
149      origins.merge(b.origins);
150      tr_trees.merge(b.tr_trees);
151      aggregate_pubkeys.merge(b.aggregate_pubkeys);
152      // We shouldn't be merging 2 different sessions, just overwrite with b's sessions.
153      if (!musig2_secnonces) musig2_secnonces = b.musig2_secnonces;
154      return *this;
155  }
156  
157  void FillableSigningProvider::ImplicitlyLearnRelatedKeyScripts(const CPubKey& pubkey)
158  {
159      AssertLockHeld(cs_KeyStore);
160      CKeyID key_id = pubkey.GetID();
161      // This adds the redeemscripts necessary to detect P2WPKH and P2SH-P2WPKH
162      // outputs. Technically P2WPKH outputs don't have a redeemscript to be
163      // spent. However, our current IsMine logic requires the corresponding
164      // P2SH-P2WPKH redeemscript to be present in the wallet in order to accept
165      // payment even to P2WPKH outputs.
166      // Also note that having superfluous scripts in the keystore never hurts.
167      // They're only used to guide recursion in signing and IsMine logic - if
168      // a script is present but we can't do anything with it, it has no effect.
169      // "Implicitly" refers to fact that scripts are derived automatically from
170      // existing keys, and are present in memory, even without being explicitly
171      // loaded (e.g. from a file).
172      if (pubkey.IsCompressed()) {
173          CScript script = GetScriptForDestination(WitnessV0KeyHash(key_id));
174          // This does not use AddCScript, as it may be overridden.
175          CScriptID id(script);
176          mapScripts[id] = std::move(script);
177      }
178  }
179  
180  bool FillableSigningProvider::GetPubKey(const CKeyID &address, CPubKey &vchPubKeyOut) const
181  {
182      CKey key;
183      if (!GetKey(address, key)) {
184          return false;
185      }
186      vchPubKeyOut = key.GetPubKey();
187      return true;
188  }
189  
190  bool FillableSigningProvider::AddKeyPubKey(const CKey& key, const CPubKey &pubkey)
191  {
192      LOCK(cs_KeyStore);
193      mapKeys[pubkey.GetID()] = key;
194      ImplicitlyLearnRelatedKeyScripts(pubkey);
195      return true;
196  }
197  
198  bool FillableSigningProvider::HaveKey(const CKeyID &address) const
199  {
200      LOCK(cs_KeyStore);
201      return mapKeys.contains(address);
202  }
203  
204  std::set<CKeyID> FillableSigningProvider::GetKeys() const
205  {
206      LOCK(cs_KeyStore);
207      std::set<CKeyID> set_address;
208      for (const auto& mi : mapKeys) {
209          set_address.insert(mi.first);
210      }
211      return set_address;
212  }
213  
214  bool FillableSigningProvider::GetKey(const CKeyID &address, CKey &keyOut) const
215  {
216      LOCK(cs_KeyStore);
217      KeyMap::const_iterator mi = mapKeys.find(address);
218      if (mi != mapKeys.end()) {
219          keyOut = mi->second;
220          return true;
221      }
222      return false;
223  }
224  
225  bool FillableSigningProvider::AddCScript(const CScript& redeemScript)
226  {
227      if (redeemScript.size() > MAX_SCRIPT_ELEMENT_SIZE) {
228          LogError("FillableSigningProvider::AddCScript(): redeemScripts > %i bytes are invalid\n", MAX_SCRIPT_ELEMENT_SIZE);
229          return false;
230      }
231  
232      LOCK(cs_KeyStore);
233      mapScripts[CScriptID(redeemScript)] = redeemScript;
234      return true;
235  }
236  
237  bool FillableSigningProvider::HaveCScript(const CScriptID& hash) const
238  {
239      LOCK(cs_KeyStore);
240      return mapScripts.contains(hash);
241  }
242  
243  std::set<CScriptID> FillableSigningProvider::GetCScripts() const
244  {
245      LOCK(cs_KeyStore);
246      std::set<CScriptID> set_script;
247      for (const auto& mi : mapScripts) {
248          set_script.insert(mi.first);
249      }
250      return set_script;
251  }
252  
253  bool FillableSigningProvider::GetCScript(const CScriptID &hash, CScript& redeemScriptOut) const
254  {
255      LOCK(cs_KeyStore);
256      ScriptMap::const_iterator mi = mapScripts.find(hash);
257      if (mi != mapScripts.end())
258      {
259          redeemScriptOut = (*mi).second;
260          return true;
261      }
262      return false;
263  }
264  
265  CKeyID GetKeyForDestination(const SigningProvider& store, const CTxDestination& dest)
266  {
267      // Only supports destinations which map to single public keys:
268      // P2PKH, P2WPKH, P2SH-P2WPKH, P2TR
269      if (auto id = std::get_if<PKHash>(&dest)) {
270          return ToKeyID(*id);
271      }
272      if (auto witness_id = std::get_if<WitnessV0KeyHash>(&dest)) {
273          return ToKeyID(*witness_id);
274      }
275      if (auto script_hash = std::get_if<ScriptHash>(&dest)) {
276          CScript script;
277          CScriptID script_id = ToScriptID(*script_hash);
278          CTxDestination inner_dest;
279          if (store.GetCScript(script_id, script) && ExtractDestination(script, inner_dest)) {
280              if (auto inner_witness_id = std::get_if<WitnessV0KeyHash>(&inner_dest)) {
281                  return ToKeyID(*inner_witness_id);
282              }
283          }
284      }
285      if (auto output_key = std::get_if<WitnessV1Taproot>(&dest)) {
286          TaprootSpendData spenddata;
287          CPubKey pub;
288          if (store.GetTaprootSpendData(*output_key, spenddata)
289              && !spenddata.internal_key.IsNull()
290              && spenddata.merkle_root.IsNull()
291              && store.GetPubKeyByXOnly(spenddata.internal_key, pub)) {
292              return pub.GetID();
293          }
294      }
295      return CKeyID();
296  }
297  
298  void MultiSigningProvider::AddProvider(std::unique_ptr<SigningProvider> provider)
299  {
300      m_providers.push_back(std::move(provider));
301  }
302  
303  bool MultiSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const
304  {
305      for (const auto& provider: m_providers) {
306          if (provider->GetCScript(scriptid, script)) return true;
307      }
308      return false;
309  }
310  
311  bool MultiSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const
312  {
313      for (const auto& provider: m_providers) {
314          if (provider->GetPubKey(keyid, pubkey)) return true;
315      }
316      return false;
317  }
318  
319  
320  bool MultiSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const
321  {
322      for (const auto& provider: m_providers) {
323          if (provider->GetKeyOrigin(keyid, info)) return true;
324      }
325      return false;
326  }
327  
328  bool MultiSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const
329  {
330      for (const auto& provider: m_providers) {
331          if (provider->GetKey(keyid, key)) return true;
332      }
333      return false;
334  }
335  
336  bool MultiSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const
337  {
338      for (const auto& provider: m_providers) {
339          if (provider->GetTaprootSpendData(output_key, spenddata)) return true;
340      }
341      return false;
342  }
343  
344  bool MultiSigningProvider::GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const
345  {
346      for (const auto& provider: m_providers) {
347          if (provider->GetTaprootBuilder(output_key, builder)) return true;
348      }
349      return false;
350  }
351  
352  /*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b)
353  {
354      NodeInfo ret;
355      /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */
356      for (auto& leaf : a.leaves) {
357          leaf.merkle_branch.push_back(b.hash);
358          ret.leaves.emplace_back(std::move(leaf));
359      }
360      /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */
361      for (auto& leaf : b.leaves) {
362          leaf.merkle_branch.push_back(a.hash);
363          ret.leaves.emplace_back(std::move(leaf));
364      }
365      ret.hash = ComputeTapbranchHash(a.hash, b.hash);
366      return ret;
367  }
368  
369  void TaprootSpendData::Merge(TaprootSpendData other)
370  {
371      // TODO: figure out how to better deal with conflicting information
372      // being merged.
373      if (internal_key.IsNull() && !other.internal_key.IsNull()) {
374          internal_key = other.internal_key;
375      }
376      if (merkle_root.IsNull() && !other.merkle_root.IsNull()) {
377          merkle_root = other.merkle_root;
378      }
379      for (auto& [key, control_blocks] : other.scripts) {
380          scripts[key].merge(std::move(control_blocks));
381      }
382  }
383  
384  void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
385  {
386      assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
387      /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
388       * so would mean the Add() invocations do not correspond to a DFS traversal of a
389       * binary tree. */
390      if ((size_t)depth + 1 < m_branch.size()) {
391          m_valid = false;
392          return;
393      }
394      /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
395       * The 'node' variable is overwritten here with the newly combined node. */
396      while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
397          node = Combine(std::move(node), std::move(*m_branch[depth]));
398          m_branch.pop_back();
399          if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
400          --depth;
401      }
402      if (m_valid) {
403          /* Make sure the branch is big enough to place the new node. */
404          if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
405          assert(!m_branch[depth].has_value());
406          m_branch[depth] = std::move(node);
407      }
408  }
409  
410  /*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
411  {
412      std::vector<bool> branch;
413      for (int depth : depths) {
414          // This inner loop corresponds to effectively the same logic on branch
415          // as what Insert() performs on the m_branch variable. Instead of
416          // storing a NodeInfo object, just remember whether or not there is one
417          // at that depth.
418          if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
419          if ((size_t)depth + 1 < branch.size()) return false;
420          while (branch.size() > (size_t)depth && branch[depth]) {
421              branch.pop_back();
422              if (depth == 0) return false;
423              --depth;
424          }
425          if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
426          assert(!branch[depth]);
427          branch[depth] = true;
428      }
429      // And this check corresponds to the IsComplete() check on m_branch.
430      return branch.size() == 0 || (branch.size() == 1 && branch[0]);
431  }
432  
433  TaprootBuilder& TaprootBuilder::Add(int depth, std::span<const unsigned char> script, int leaf_version, bool track)
434  {
435      assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
436      if (!IsValid()) return *this;
437      /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
438      NodeInfo node;
439      node.hash = ComputeTapleafHash(leaf_version, script);
440      if (track) node.leaves.emplace_back(LeafInfo{std::vector<unsigned char>(script.begin(), script.end()), leaf_version, {}});
441      /* Insert into the branch. */
442      Insert(std::move(node), depth);
443      return *this;
444  }
445  
446  TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash)
447  {
448      if (!IsValid()) return *this;
449      /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
450      NodeInfo node;
451      node.hash = hash;
452      Insert(std::move(node), depth);
453      return *this;
454  }
455  
456  TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
457  {
458      /* Can only call this function when IsComplete() is true. */
459      assert(IsComplete());
460      m_internal_key = internal_key;
461      auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
462      assert(ret.has_value());
463      std::tie(m_output_key, m_parity) = *ret;
464      return *this;
465  }
466  
467  WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; }
468  
469  TaprootSpendData TaprootBuilder::GetSpendData() const
470  {
471      assert(IsComplete());
472      assert(m_output_key.IsFullyValid());
473      TaprootSpendData spd;
474      spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash;
475      spd.internal_key = m_internal_key;
476      if (m_branch.size()) {
477          // If any script paths exist, they have been combined into the root m_branch[0]
478          // by now. Compute the control block for each of its tracked leaves, and put them in
479          // spd.scripts.
480          for (const auto& leaf : m_branch[0]->leaves) {
481              std::vector<unsigned char> control_block;
482              control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size());
483              control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0);
484              std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1);
485              if (leaf.merkle_branch.size()) {
486                  std::copy(leaf.merkle_branch[0].begin(),
487                            leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(),
488                            control_block.begin() + TAPROOT_CONTROL_BASE_SIZE);
489              }
490              spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
491          }
492      }
493      return spd;
494  }
495  
496  std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
497  {
498      // Verify that the output matches the assumed Merkle root and internal key.
499      auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root);
500      if (!tweak || tweak->first != output) return std::nullopt;
501      // If the Merkle root is 0, the tree is empty, and we're done.
502      std::vector<std::tuple<int, std::vector<unsigned char>, int>> ret;
503      if (spenddata.merkle_root.IsNull()) return ret;
504  
505      /** Data structure to represent the nodes of the tree we're going to build. */
506      struct TreeNode {
507          /** Hash of this node, if known; 0 otherwise. */
508          uint256 hash;
509          /** The left and right subtrees (note that their order is irrelevant). */
510          std::unique_ptr<TreeNode> sub[2];
511          /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair.
512           *  nullptr otherwise. */
513          const std::pair<std::vector<unsigned char>, int>* leaf = nullptr;
514          /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */
515          bool explored = false;
516          /** Whether or not this node is an inner node (unknown until explored = true). */
517          bool inner;
518          /** Whether or not we have produced output for this subtree. */
519          bool done = false;
520      };
521  
522      // Build tree from the provided branches.
523      TreeNode root;
524      root.hash = spenddata.merkle_root;
525      for (const auto& [key, control_blocks] : spenddata.scripts) {
526          const auto& [script, leaf_ver] = key;
527          for (const auto& control : control_blocks) {
528              // Skip script records with nonsensical leaf version.
529              if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue;
530              // Skip script records with invalid control block sizes.
531              if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE ||
532                  ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue;
533              // Skip script records that don't match the control block.
534              if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue;
535              // Skip script records that don't match the provided Merkle root.
536              const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script);
537              const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash);
538              if (merkle_root != spenddata.merkle_root) continue;
539  
540              TreeNode* node = &root;
541              size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
542              for (size_t depth = 0; depth < levels; ++depth) {
543                  // Can't descend into a node which we already know is a leaf.
544                  if (node->explored && !node->inner) return std::nullopt;
545  
546                  // Extract partner hash from Merkle branch in control block.
547                  uint256 hash;
548                  std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE,
549                            control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE,
550                            hash.begin());
551  
552                  if (node->sub[0]) {
553                      // Descend into the existing left or right branch.
554                      bool desc = false;
555                      for (int i = 0; i < 2; ++i) {
556                          if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) {
557                              node->sub[i]->hash = hash;
558                              node = &*node->sub[1-i];
559                              desc = true;
560                              break;
561                          }
562                      }
563                      if (!desc) return std::nullopt; // This probably requires a hash collision to hit.
564                  } else {
565                      // We're in an unexplored node. Create subtrees and descend.
566                      node->explored = true;
567                      node->inner = true;
568                      node->sub[0] = std::make_unique<TreeNode>();
569                      node->sub[1] = std::make_unique<TreeNode>();
570                      node->sub[1]->hash = hash;
571                      node = &*node->sub[0];
572                  }
573              }
574              // Cannot turn a known inner node into a leaf.
575              if (node->sub[0]) return std::nullopt;
576              node->explored = true;
577              node->inner = false;
578              node->leaf = &key;
579              node->hash = leaf_hash;
580          }
581      }
582  
583      // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid
584      // overflowing the call stack (the tree may be 128 levels deep).
585      std::vector<TreeNode*> stack{&root};
586      while (!stack.empty()) {
587          TreeNode& node = *stack.back();
588          if (!node.explored) {
589              // Unexplored node, which means the tree is incomplete.
590              return std::nullopt;
591          } else if (!node.inner) {
592              // Leaf node; produce output.
593              ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second);
594              node.done = true;
595              stack.pop_back();
596          } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() &&
597                     ComputeTapbranchHash(node.sub[1]->hash, node.sub[1]->hash) == node.hash) {
598              // Whenever there are nodes with two identical subtrees under it, we run into a problem:
599              // the control blocks for the leaves underneath those will be identical as well, and thus
600              // they will all be matched to the same path in the tree. The result is that at the location
601              // where the duplicate occurred, the left child will contain a normal tree that can be explored
602              // and processed, but the right one will remain unexplored.
603              //
604              // This situation can be detected, by encountering an inner node with unexplored right subtree
605              // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash.
606              //
607              // To deal with this, simply process the left tree a second time (set its done flag to false;
608              // noting that the done flag of its children have already been set to false after processing
609              // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored)
610              // subtree to true.
611              node.sub[0]->done = false;
612              node.sub[1]->done = true;
613          } else if (node.sub[0]->done && node.sub[1]->done) {
614              // An internal node which we're finished with.
615              node.sub[0]->done = false;
616              node.sub[1]->done = false;
617              node.done = true;
618              stack.pop_back();
619          } else if (!node.sub[0]->done) {
620              // An internal node whose left branch hasn't been processed yet. Do so first.
621              stack.push_back(&*node.sub[0]);
622          } else if (!node.sub[1]->done) {
623              // An internal node whose right branch hasn't been processed yet. Do so first.
624              stack.push_back(&*node.sub[1]);
625          }
626      }
627  
628      return ret;
629  }
630  
631  std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> TaprootBuilder::GetTreeTuples() const
632  {
633      assert(IsComplete());
634      std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> tuples;
635      if (m_branch.size()) {
636          const auto& leaves = m_branch[0]->leaves;
637          for (const auto& leaf : leaves) {
638              assert(leaf.merkle_branch.size() <= TAPROOT_CONTROL_MAX_NODE_COUNT);
639              uint8_t depth = (uint8_t)leaf.merkle_branch.size();
640              uint8_t leaf_ver = (uint8_t)leaf.leaf_version;
641              tuples.emplace_back(depth, leaf_ver, leaf.script);
642          }
643      }
644      return tuples;
645  }