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