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