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