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