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 : 1255465 : bool LookupHelper(const M& map, const K& key, V& value)
22 : : {
23 [ + + ]: 1255465 : auto it = map.find(key);
24 [ + + ]: 1255465 : if (it != map.end()) {
25 : 828011 : value = it->second;
26 : 828011 : return true;
27 : : }
28 : : return false;
29 : : }
30 : :
31 : 6160 : bool HidingSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const
32 : : {
33 : 6160 : return m_provider->GetCScript(scriptid, script);
34 : : }
35 : :
36 : 6464 : bool HidingSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const
37 : : {
38 : 6464 : return m_provider->GetPubKey(keyid, pubkey);
39 : : }
40 : :
41 : 204716 : bool HidingSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const
42 : : {
43 [ + + ]: 204716 : if (m_hide_secret) return false;
44 : 126855 : return m_provider->GetKey(keyid, key);
45 : : }
46 : :
47 : 181844 : bool HidingSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const
48 : : {
49 [ + + ]: 181844 : if (m_hide_origin) return false;
50 : 158225 : return m_provider->GetKeyOrigin(keyid, info);
51 : : }
52 : :
53 : 4947 : bool HidingSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const
54 : : {
55 : 4947 : return m_provider->GetTaprootSpendData(output_key, spenddata);
56 : : }
57 : 4947 : bool HidingSigningProvider::GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const
58 : : {
59 : 4947 : 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 : 4947 : std::map<CPubKey, std::vector<CPubKey>> HidingSigningProvider::GetAllMuSig2ParticipantPubkeys() const
68 : : {
69 : 4947 : 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 : 29885 : bool FlatSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const { return LookupHelper(scripts, scriptid, script); }
88 : 287196 : bool FlatSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const { return LookupHelper(pubkeys, keyid, pubkey); }
89 : 586575 : bool FlatSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const
90 : : {
91 [ + - ]: 586575 : std::pair<CPubKey, KeyOriginInfo> out;
92 [ + - ]: 586575 : bool ret = LookupHelper(origins, keyid, out);
93 [ + + ]: 586575 : if (ret) info = std::move(out.second);
94 : 586575 : return ret;
95 : 586575 : }
96 : 1341 : bool FlatSigningProvider::HaveKey(const CKeyID &keyid) const
97 : : {
98 : 1341 : CKey key;
99 [ + - ]: 1341 : return LookupHelper(keys, keyid, key);
100 : 1341 : }
101 : 327918 : bool FlatSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const { return LookupHelper(keys, keyid, key); }
102 : 14532 : bool FlatSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const
103 : : {
104 [ + - ]: 14532 : TaprootBuilder builder;
105 [ + - + + ]: 14532 : if (LookupHelper(tr_trees, output_key, builder)) {
106 [ + - ]: 6524 : spenddata = builder.GetSpendData();
107 : 6524 : return true;
108 : : }
109 : : return false;
110 : 14532 : }
111 : 8018 : bool FlatSigningProvider::GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const
112 : : {
113 : 8018 : 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 : 8018 : std::map<CPubKey, std::vector<CPubKey>> FlatSigningProvider::GetAllMuSig2ParticipantPubkeys() const
124 : : {
125 : 8018 : 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 : 1034546 : FlatSigningProvider& FlatSigningProvider::Merge(FlatSigningProvider&& b)
151 : : {
152 : 1034546 : scripts.merge(b.scripts);
153 : 1034546 : pubkeys.merge(b.pubkeys);
154 : 1034546 : keys.merge(b.keys);
155 : 1034546 : origins.merge(b.origins);
156 : 1034546 : tr_trees.merge(b.tr_trees);
157 : 1034546 : aggregate_pubkeys.merge(b.aggregate_pubkeys);
158 : : // We shouldn't be merging 2 different sessions, just overwrite with b's sessions.
159 [ + + ]: 1034546 : if (!musig2_secnonces) musig2_secnonces = b.musig2_secnonces;
160 : 1034546 : return *this;
161 : : }
162 : :
163 : 514 : void FillableSigningProvider::ImplicitlyLearnRelatedKeyScripts(const CPubKey& pubkey)
164 : : {
165 : 514 : AssertLockHeld(cs_KeyStore);
166 : 514 : 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 [ + + ]: 514 : if (pubkey.IsCompressed()) {
179 [ + - ]: 497 : CScript script = GetScriptForDestination(WitnessV0KeyHash(key_id));
180 : : // This does not use AddCScript, as it may be overridden.
181 [ + - ]: 497 : CScriptID id(script);
182 [ + - ]: 497 : mapScripts[id] = std::move(script);
183 : 497 : }
184 : 514 : }
185 : :
186 : 5942 : bool FillableSigningProvider::GetPubKey(const CKeyID &address, CPubKey &vchPubKeyOut) const
187 : : {
188 : 5942 : CKey key;
189 [ + - + + ]: 5942 : if (!GetKey(address, key)) {
190 : : return false;
191 : : }
192 [ + - ]: 5865 : vchPubKeyOut = key.GetPubKey();
193 : : return true;
194 : 5942 : }
195 : :
196 : 421 : bool FillableSigningProvider::AddKeyPubKey(const CKey& key, const CPubKey &pubkey)
197 : : {
198 : 421 : LOCK(cs_KeyStore);
199 [ + - + - : 421 : mapKeys[pubkey.GetID()] = key;
+ - ]
200 [ + - ]: 421 : ImplicitlyLearnRelatedKeyScripts(pubkey);
201 [ + - ]: 421 : return true;
202 : 421 : }
203 : :
204 : 2375 : bool FillableSigningProvider::HaveKey(const CKeyID &address) const
205 : : {
206 : 2375 : LOCK(cs_KeyStore);
207 [ + - ]: 2375 : return mapKeys.contains(address);
208 : 2375 : }
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 : 10945 : bool FillableSigningProvider::GetKey(const CKeyID &address, CKey &keyOut) const
221 : : {
222 : 10945 : LOCK(cs_KeyStore);
223 : 10945 : KeyMap::const_iterator mi = mapKeys.find(address);
224 [ + + ]: 10945 : if (mi != mapKeys.end()) {
225 [ + - ]: 10814 : keyOut = mi->second;
226 : : return true;
227 : : }
228 : : return false;
229 : 10945 : }
230 : :
231 : 116 : bool FillableSigningProvider::AddCScript(const CScript& redeemScript)
232 : : {
233 [ + + - + ]: 116 : if (redeemScript.size() > MAX_SCRIPT_ELEMENT_SIZE) {
234 : 0 : LogError("FillableSigningProvider::AddCScript(): redeemScripts > %i bytes are invalid\n", MAX_SCRIPT_ELEMENT_SIZE);
235 : 0 : return false;
236 : : }
237 : :
238 : 116 : LOCK(cs_KeyStore);
239 [ + - + - ]: 116 : mapScripts[CScriptID(redeemScript)] = redeemScript;
240 [ + - ]: 116 : return true;
241 : 116 : }
242 : :
243 : 1776 : bool FillableSigningProvider::HaveCScript(const CScriptID& hash) const
244 : : {
245 : 1776 : LOCK(cs_KeyStore);
246 [ + - ]: 1776 : return mapScripts.contains(hash);
247 : 1776 : }
248 : :
249 : 0 : std::set<CScriptID> FillableSigningProvider::GetCScripts() const
250 : : {
251 : 0 : LOCK(cs_KeyStore);
252 : 0 : std::set<CScriptID> set_script;
253 [ # # ]: 0 : for (const auto& mi : mapScripts) {
254 [ # # ]: 0 : set_script.insert(mi.first);
255 : : }
256 [ # # ]: 0 : return set_script;
257 : 0 : }
258 : :
259 : 3155 : bool FillableSigningProvider::GetCScript(const CScriptID &hash, CScript& redeemScriptOut) const
260 : : {
261 : 3155 : LOCK(cs_KeyStore);
262 : 3155 : ScriptMap::const_iterator mi = mapScripts.find(hash);
263 [ + + ]: 3155 : if (mi != mapScripts.end())
264 : : {
265 : 1545 : redeemScriptOut = (*mi).second;
266 : 1545 : return true;
267 : : }
268 : : return false;
269 : 3155 : }
270 : :
271 : 647 : CKeyID GetKeyForDestination(const SigningProvider& store, const CTxDestination& dest)
272 : : {
273 : : // Only supports destinations which map to single public keys:
274 : : // P2PKH, P2WPKH, P2SH-P2WPKH, P2TR
275 [ + + ]: 647 : if (auto id = std::get_if<PKHash>(&dest)) {
276 : 109 : return ToKeyID(*id);
277 : : }
278 [ + + ]: 538 : if (auto witness_id = std::get_if<WitnessV0KeyHash>(&dest)) {
279 : 316 : return ToKeyID(*witness_id);
280 : : }
281 [ + + ]: 222 : if (auto script_hash = std::get_if<ScriptHash>(&dest)) {
282 : 92 : CScript script;
283 [ + - ]: 92 : CScriptID script_id = ToScriptID(*script_hash);
284 : 92 : CTxDestination inner_dest;
285 [ + - + - : 92 : if (store.GetCScript(script_id, script) && ExtractDestination(script, inner_dest)) {
+ - + - ]
286 [ + + ]: 92 : if (auto inner_witness_id = std::get_if<WitnessV0KeyHash>(&inner_dest)) {
287 [ + - ]: 89 : return ToKeyID(*inner_witness_id);
288 : : }
289 : : }
290 : 92 : }
291 [ + + ]: 133 : if (auto output_key = std::get_if<WitnessV1Taproot>(&dest)) {
292 [ + - ]: 108 : TaprootSpendData spenddata;
293 [ + - ]: 108 : CPubKey pub;
294 [ + - ]: 108 : if (store.GetTaprootSpendData(*output_key, spenddata)
295 [ + - ]: 101 : && !spenddata.internal_key.IsNull()
296 [ + + ]: 101 : && spenddata.merkle_root.IsNull()
297 [ + + + - : 157 : && store.GetPubKeyByXOnly(spenddata.internal_key, pub)) {
- + ]
298 [ + - ]: 49 : return pub.GetID();
299 : : }
300 : 108 : }
301 : 84 : return CKeyID();
302 : : }
303 : :
304 : 59901 : void MultiSigningProvider::AddProvider(std::unique_ptr<SigningProvider> provider)
305 : : {
306 : 59901 : m_providers.push_back(std::move(provider));
307 : 59901 : }
308 : :
309 : 822 : bool MultiSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const
310 : : {
311 [ + + ]: 842 : for (const auto& provider: m_providers) {
312 [ + + ]: 822 : if (provider->GetCScript(scriptid, script)) return true;
313 : : }
314 : : return false;
315 : : }
316 : :
317 : 30032 : bool MultiSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const
318 : : {
319 [ + - ]: 30032 : for (const auto& provider: m_providers) {
320 [ - + ]: 30032 : if (provider->GetPubKey(keyid, pubkey)) return true;
321 : : }
322 : : return false;
323 : : }
324 : :
325 : :
326 : 79835 : bool MultiSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const
327 : : {
328 [ + + ]: 82199 : for (const auto& provider: m_providers) {
329 [ + + ]: 80931 : if (provider->GetKeyOrigin(keyid, info)) return true;
330 : : }
331 : : return false;
332 : : }
333 : :
334 : 0 : bool MultiSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const
335 : : {
336 [ # # ]: 0 : for (const auto& provider: m_providers) {
337 [ # # ]: 0 : if (provider->GetKey(keyid, key)) return true;
338 : : }
339 : : return false;
340 : : }
341 : :
342 : 1308 : bool MultiSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const
343 : : {
344 [ + + ]: 1442 : for (const auto& provider: m_providers) {
345 [ + + ]: 1372 : if (provider->GetTaprootSpendData(output_key, spenddata)) return true;
346 : : }
347 : : return false;
348 : : }
349 : :
350 : 0 : bool MultiSigningProvider::GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const
351 : : {
352 [ # # ]: 0 : for (const auto& provider: m_providers) {
353 [ # # ]: 0 : if (provider->GetTaprootBuilder(output_key, builder)) return true;
354 : : }
355 : : return false;
356 : : }
357 : :
358 : 22173 : /*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b)
359 : : {
360 : 22173 : NodeInfo ret;
361 : : /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */
362 [ + + ]: 62217 : for (auto& leaf : a.leaves) {
363 [ + - ]: 40044 : leaf.merkle_branch.push_back(b.hash);
364 [ + - ]: 40044 : ret.leaves.emplace_back(std::move(leaf));
365 : : }
366 : : /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */
367 [ + + ]: 50948 : for (auto& leaf : b.leaves) {
368 [ + - ]: 28775 : leaf.merkle_branch.push_back(a.hash);
369 [ + - ]: 28775 : ret.leaves.emplace_back(std::move(leaf));
370 : : }
371 [ + - ]: 22173 : ret.hash = ComputeTapbranchHash(a.hash, b.hash);
372 : 22173 : return ret;
373 : 0 : }
374 : :
375 : 1655 : void TaprootSpendData::Merge(TaprootSpendData other)
376 : : {
377 : : // TODO: figure out how to better deal with conflicting information
378 : : // being merged.
379 [ + + + - ]: 4183 : if (internal_key.IsNull() && !other.internal_key.IsNull()) {
380 : 873 : internal_key = other.internal_key;
381 : : }
382 [ + + + + ]: 4416 : if (merkle_root.IsNull() && !other.merkle_root.IsNull()) {
383 : 552 : merkle_root = other.merkle_root;
384 : : }
385 [ + + ]: 3303 : for (auto& [key, control_blocks] : other.scripts) {
386 : 1648 : scripts[key].merge(std::move(control_blocks));
387 : : }
388 : 1655 : }
389 : :
390 : 41000 : void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
391 : : {
392 [ - + ]: 41000 : assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
393 : : /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
394 : : * so would mean the Add() invocations do not correspond to a DFS traversal of a
395 : : * binary tree. */
396 [ - + - + ]: 41000 : if ((size_t)depth + 1 < m_branch.size()) {
397 : 0 : m_valid = false;
398 : 0 : return;
399 : : }
400 : : /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
401 : : * The 'node' variable is overwritten here with the newly combined node. */
402 [ + - - + : 63173 : while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
+ + + + ]
403 : 22173 : node = Combine(std::move(node), std::move(*m_branch[depth]));
404 : 22173 : m_branch.pop_back();
405 [ - + ]: 22173 : if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
406 : 22173 : --depth;
407 : : }
408 [ + - ]: 41000 : if (m_valid) {
409 : : /* Make sure the branch is big enough to place the new node. */
410 [ - + + + ]: 41000 : if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
411 [ - + ]: 41000 : assert(!m_branch[depth].has_value());
412 : 41000 : m_branch[depth] = std::move(node);
413 : : }
414 : : }
415 : :
416 : 2125 : /*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
417 : : {
418 : 2125 : std::vector<bool> branch;
419 [ + + ]: 3296 : for (int depth : depths) {
420 : : // This inner loop corresponds to effectively the same logic on branch
421 : : // as what Insert() performs on the m_branch variable. Instead of
422 : : // storing a NodeInfo object, just remember whether or not there is one
423 : : // at that depth.
424 [ + + ]: 1196 : if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
425 [ + + ]: 1195 : if ((size_t)depth + 1 < branch.size()) return false;
426 [ + + + + ]: 1912 : while (branch.size() > (size_t)depth && branch[depth]) {
427 [ - + ]: 741 : branch.pop_back();
428 [ + + ]: 741 : if (depth == 0) return false;
429 : 735 : --depth;
430 : : }
431 [ + + + - ]: 1171 : if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
432 [ - + ]: 1171 : assert(!branch[depth]);
433 : 1171 : branch[depth] = true;
434 : : }
435 : : // And this check corresponds to the IsComplete() check on m_branch.
436 [ + + + + : 2100 : return branch.size() == 0 || (branch.size() == 1 && branch[0]);
+ - ]
437 : 2125 : }
438 : :
439 : 40999 : TaprootBuilder& TaprootBuilder::Add(int depth, std::span<const unsigned char> script, int leaf_version, bool track)
440 : : {
441 [ - + ]: 40999 : assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
442 [ + - ]: 40999 : if (!IsValid()) return *this;
443 : : /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
444 : 40999 : NodeInfo node;
445 [ + - ]: 40999 : node.hash = ComputeTapleafHash(leaf_version, script);
446 [ + - + - : 81998 : if (track) node.leaves.emplace_back(LeafInfo{std::vector<unsigned char>(script.begin(), script.end()), leaf_version, {}});
+ - ]
447 : : /* Insert into the branch. */
448 [ + - ]: 40999 : Insert(std::move(node), depth);
449 : 40999 : return *this;
450 : 40999 : }
451 : :
452 : 1 : TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash)
453 : : {
454 [ + - ]: 1 : if (!IsValid()) return *this;
455 : : /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
456 : 1 : NodeInfo node;
457 : 1 : node.hash = hash;
458 [ + - ]: 1 : Insert(std::move(node), depth);
459 : 1 : return *this;
460 : 1 : }
461 : :
462 : 127902 : TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
463 : : {
464 : : /* Can only call this function when IsComplete() is true. */
465 [ - + ]: 127902 : assert(IsComplete());
466 : 127902 : m_internal_key = internal_key;
467 [ - + + + ]: 127902 : auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
468 [ - + ]: 127902 : assert(ret.has_value());
469 : 127902 : std::tie(m_output_key, m_parity) = *ret;
470 : 127902 : return *this;
471 : : }
472 : :
473 : 127764 : WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; }
474 : :
475 : 10306 : TaprootSpendData TaprootBuilder::GetSpendData() const
476 : : {
477 [ - + ]: 10306 : assert(IsComplete());
478 [ - + ]: 10306 : assert(m_output_key.IsFullyValid());
479 [ - + ]: 10306 : TaprootSpendData spd;
480 [ - + + + ]: 10306 : spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash;
481 : 10306 : spd.internal_key = m_internal_key;
482 [ - + + + ]: 10306 : if (m_branch.size()) {
483 : : // If any script paths exist, they have been combined into the root m_branch[0]
484 : : // by now. Compute the control block for each of its tracked leaves, and put them in
485 : : // spd.scripts.
486 [ + + ]: 17371 : for (const auto& leaf : m_branch[0]->leaves) {
487 : 10668 : std::vector<unsigned char> control_block;
488 [ - + + - ]: 10668 : control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size());
489 [ + + ]: 16344 : control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0);
490 : 10668 : std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1);
491 [ - + + + ]: 10668 : if (leaf.merkle_branch.size()) {
492 : 5514 : std::copy(leaf.merkle_branch[0].begin(),
493 : 5514 : leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(),
494 : 5514 : control_block.begin() + TAPROOT_CONTROL_BASE_SIZE);
495 : : }
496 [ + - + - : 21336 : spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
+ - ]
497 : 10668 : }
498 : : }
499 : 10306 : return spd;
500 : 0 : }
501 : :
502 : 4913 : std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
503 : : {
504 : : // Verify that the output matches the assumed Merkle root and internal key.
505 [ + + ]: 9826 : auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root);
506 [ + - - + ]: 4913 : if (!tweak || tweak->first != output) return std::nullopt;
507 : : // If the Merkle root is 0, the tree is empty, and we're done.
508 : 4913 : std::vector<std::tuple<int, std::vector<unsigned char>, int>> ret;
509 [ + + ]: 9826 : if (spenddata.merkle_root.IsNull()) return ret;
510 : :
511 : : /** Data structure to represent the nodes of the tree we're going to build. */
512 [ + + - - ]: 5742 : struct TreeNode {
513 : : /** Hash of this node, if known; 0 otherwise. */
514 : : uint256 hash;
515 : : /** The left and right subtrees (note that their order is irrelevant). */
516 : : std::unique_ptr<TreeNode> sub[2];
517 : : /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair.
518 : : * nullptr otherwise. */
519 : : const std::pair<std::vector<unsigned char>, int>* leaf = nullptr;
520 : : /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */
521 : : bool explored = false;
522 : : /** Whether or not this node is an inner node (unknown until explored = true). */
523 : : bool inner;
524 : : /** Whether or not we have produced output for this subtree. */
525 : : bool done = false;
526 : : };
527 : :
528 : : // Build tree from the provided branches.
529 : 1914 : TreeNode root;
530 : 1914 : root.hash = spenddata.merkle_root;
531 [ + + ]: 4800 : for (const auto& [key, control_blocks] : spenddata.scripts) {
532 : 2886 : const auto& [script, leaf_ver] = key;
533 [ + + ]: 6532 : for (const auto& control : control_blocks) {
534 : : // Skip script records with nonsensical leaf version.
535 [ + - - + ]: 3646 : if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue;
536 : : // Skip script records with invalid control block sizes.
537 [ - + + - : 3646 : if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE ||
+ - ]
538 [ + - ]: 3646 : ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue;
539 : : // Skip script records that don't match the control block.
540 [ - + ]: 3646 : if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue;
541 : : // Skip script records that don't match the provided Merkle root.
542 [ - + + - ]: 3646 : const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script);
543 [ - + + - ]: 3646 : const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash);
544 [ - + ]: 3646 : if (merkle_root != spenddata.merkle_root) continue;
545 : :
546 : 3646 : TreeNode* node = &root;
547 [ - + ]: 3646 : size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
548 [ + + ]: 9067 : for (size_t depth = 0; depth < levels; ++depth) {
549 : : // Can't descend into a node which we already know is a leaf.
550 [ + + - + ]: 5421 : if (node->explored && !node->inner) return std::nullopt;
551 : :
552 : : // Extract partner hash from Merkle branch in control block.
553 : 5421 : uint256 hash;
554 : 5421 : std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE,
555 : 5421 : control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE,
556 : : hash.begin());
557 : :
558 [ + + ]: 5421 : if (node->sub[0]) {
559 : : // Descend into the existing left or right branch.
560 : 4096 : bool desc = false;
561 [ + - ]: 4096 : for (int i = 0; i < 2; ++i) {
562 [ + + + + : 5436 : if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) {
+ + ]
563 : 3256 : node->sub[i]->hash = hash;
564 : 3256 : node = &*node->sub[1-i];
565 : 3256 : desc = true;
566 : 3256 : break;
567 : : }
568 : : }
569 : 3256 : if (!desc) return std::nullopt; // This probably requires a hash collision to hit.
570 : : } else {
571 : : // We're in an unexplored node. Create subtrees and descend.
572 : 2165 : node->explored = true;
573 : 2165 : node->inner = true;
574 [ + - ]: 2165 : node->sub[0] = std::make_unique<TreeNode>();
575 [ + - ]: 2165 : node->sub[1] = std::make_unique<TreeNode>();
576 : 2165 : node->sub[1]->hash = hash;
577 : 2165 : node = &*node->sub[0];
578 : : }
579 : : }
580 : : // Cannot turn a known inner node into a leaf.
581 [ - + ]: 3646 : if (node->sub[0]) return std::nullopt;
582 : 3646 : node->explored = true;
583 : 3646 : node->inner = false;
584 : 3646 : node->leaf = &key;
585 : 3646 : node->hash = leaf_hash;
586 : : }
587 : : }
588 : :
589 : : // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid
590 : : // overflowing the call stack (the tree may be 128 levels deep).
591 [ + - ]: 1914 : std::vector<TreeNode*> stack{&root};
592 : 14289 : while (!stack.empty()) {
593 : 12375 : TreeNode& node = *stack.back();
594 [ - + ]: 12375 : if (!node.explored) {
595 : : // Unexplored node, which means the tree is incomplete.
596 : 0 : return std::nullopt;
597 [ + + ]: 12375 : } else if (!node.inner) {
598 : : // Leaf node; produce output.
599 [ - + + - ]: 4395 : ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second);
600 : 4395 : node.done = true;
601 : 4395 : stack.pop_back();
602 [ + + + + : 8517 : } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() &&
+ + + - ]
603 [ + - ]: 537 : ComputeTapbranchHash(node.sub[1]->hash, node.sub[1]->hash) == node.hash) {
604 : : // Whenever there are nodes with two identical subtrees under it, we run into a problem:
605 : : // the control blocks for the leaves underneath those will be identical as well, and thus
606 : : // they will all be matched to the same path in the tree. The result is that at the location
607 : : // where the duplicate occurred, the left child will contain a normal tree that can be explored
608 : : // and processed, but the right one will remain unexplored.
609 : : //
610 : : // This situation can be detected, by encountering an inner node with unexplored right subtree
611 : : // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash.
612 : : //
613 : : // To deal with this, simply process the left tree a second time (set its done flag to false;
614 : : // noting that the done flag of its children have already been set to false after processing
615 : : // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored)
616 : : // subtree to true.
617 : 537 : node.sub[0]->done = false;
618 : 537 : node.sub[1]->done = true;
619 [ + + + + ]: 7443 : } else if (node.sub[0]->done && node.sub[1]->done) {
620 : : // An internal node which we're finished with.
621 : 2481 : node.sub[0]->done = false;
622 : 2481 : node.sub[1]->done = false;
623 : 2481 : node.done = true;
624 : 2481 : stack.pop_back();
625 [ + + ]: 4962 : } else if (!node.sub[0]->done) {
626 : : // An internal node whose left branch hasn't been processed yet. Do so first.
627 [ + - ]: 3018 : stack.push_back(&*node.sub[0]);
628 [ + - ]: 1944 : } else if (!node.sub[1]->done) {
629 : : // An internal node whose right branch hasn't been processed yet. Do so first.
630 [ + - + + ]: 16233 : stack.push_back(&*node.sub[1]);
631 : : }
632 : : }
633 : :
634 : 1914 : return ret;
635 : 6827 : }
636 : :
637 : 209 : std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> TaprootBuilder::GetTreeTuples() const
638 : : {
639 [ - + ]: 209 : assert(IsComplete());
640 : 209 : std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> tuples;
641 [ - + + - ]: 209 : if (m_branch.size()) {
642 : 209 : const auto& leaves = m_branch[0]->leaves;
643 [ + + ]: 686 : for (const auto& leaf : leaves) {
644 [ - + - + ]: 477 : assert(leaf.merkle_branch.size() <= TAPROOT_CONTROL_MAX_NODE_COUNT);
645 [ + - ]: 477 : uint8_t depth = (uint8_t)leaf.merkle_branch.size();
646 : 477 : uint8_t leaf_ver = (uint8_t)leaf.leaf_version;
647 [ + - ]: 477 : tuples.emplace_back(depth, leaf_ver, leaf.script);
648 : : }
649 : : }
650 : 209 : return tuples;
651 : 0 : }
|
