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