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