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