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