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