Bitcoin Core  22.99.0
P2P Digital Currency
standard.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2020 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/standard.h>
7 
8 #include <crypto/sha256.h>
9 #include <hash.h>
10 #include <pubkey.h>
11 #include <script/interpreter.h>
12 #include <script/script.h>
13 #include <util/strencodings.h>
14 
15 #include <string>
16 
17 typedef std::vector<unsigned char> valtype;
18 
21 
23 CScriptID::CScriptID(const ScriptHash& in) : BaseHash(static_cast<uint160>(in)) {}
24 
26 ScriptHash::ScriptHash(const CScriptID& in) : BaseHash(static_cast<uint160>(in)) {}
27 
28 PKHash::PKHash(const CPubKey& pubkey) : BaseHash(pubkey.GetID()) {}
29 PKHash::PKHash(const CKeyID& pubkey_id) : BaseHash(pubkey_id) {}
30 
31 WitnessV0KeyHash::WitnessV0KeyHash(const CPubKey& pubkey) : BaseHash(pubkey.GetID()) {}
32 WitnessV0KeyHash::WitnessV0KeyHash(const PKHash& pubkey_hash) : BaseHash(static_cast<uint160>(pubkey_hash)) {}
33 
34 CKeyID ToKeyID(const PKHash& key_hash)
35 {
36  return CKeyID{static_cast<uint160>(key_hash)};
37 }
38 
40 {
41  return CKeyID{static_cast<uint160>(key_hash)};
42 }
43 
45 {
46  CSHA256().Write(in.data(), in.size()).Finalize(begin());
47 }
48 
50 {
51  switch (t) {
52  case TxoutType::NONSTANDARD: return "nonstandard";
53  case TxoutType::PUBKEY: return "pubkey";
54  case TxoutType::PUBKEYHASH: return "pubkeyhash";
55  case TxoutType::SCRIPTHASH: return "scripthash";
56  case TxoutType::MULTISIG: return "multisig";
57  case TxoutType::NULL_DATA: return "nulldata";
58  case TxoutType::WITNESS_V0_KEYHASH: return "witness_v0_keyhash";
59  case TxoutType::WITNESS_V0_SCRIPTHASH: return "witness_v0_scripthash";
60  case TxoutType::WITNESS_V1_TAPROOT: return "witness_v1_taproot";
61  case TxoutType::WITNESS_UNKNOWN: return "witness_unknown";
62  } // no default case, so the compiler can warn about missing cases
63  assert(false);
64 }
65 
66 static bool MatchPayToPubkey(const CScript& script, valtype& pubkey)
67 {
68  if (script.size() == CPubKey::SIZE + 2 && script[0] == CPubKey::SIZE && script.back() == OP_CHECKSIG) {
69  pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::SIZE + 1);
70  return CPubKey::ValidSize(pubkey);
71  }
72  if (script.size() == CPubKey::COMPRESSED_SIZE + 2 && script[0] == CPubKey::COMPRESSED_SIZE && script.back() == OP_CHECKSIG) {
73  pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_SIZE + 1);
74  return CPubKey::ValidSize(pubkey);
75  }
76  return false;
77 }
78 
79 static bool MatchPayToPubkeyHash(const CScript& script, valtype& pubkeyhash)
80 {
81  if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160 && script[2] == 20 && script[23] == OP_EQUALVERIFY && script[24] == OP_CHECKSIG) {
82  pubkeyhash = valtype(script.begin () + 3, script.begin() + 23);
83  return true;
84  }
85  return false;
86 }
87 
89 static constexpr bool IsSmallInteger(opcodetype opcode)
90 {
91  return opcode >= OP_1 && opcode <= OP_16;
92 }
93 
94 static constexpr bool IsPushdataOp(opcodetype opcode)
95 {
96  return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
97 }
98 
99 static constexpr bool IsValidMultisigKeyCount(int n_keys)
100 {
101  return n_keys > 0 && n_keys <= MAX_PUBKEYS_PER_MULTISIG;
102 }
103 
104 static bool GetMultisigKeyCount(opcodetype opcode, valtype data, int& count)
105 {
106  if (IsSmallInteger(opcode)) {
107  count = CScript::DecodeOP_N(opcode);
109  }
110 
111  if (IsPushdataOp(opcode)) {
112  if (!CheckMinimalPush(data, opcode)) return false;
113  try {
114  count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
116  } catch (const scriptnum_error&) {
117  return false;
118  }
119  }
120 
121  return false;
122 }
123 
124 static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys)
125 {
126  opcodetype opcode;
127  valtype data;
128  int num_keys;
129 
130  CScript::const_iterator it = script.begin();
131  if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
132 
133  if (!script.GetOp(it, opcode, data) || !GetMultisigKeyCount(opcode, data, required_sigs)) return false;
134  while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
135  pubkeys.emplace_back(std::move(data));
136  }
137  if (!GetMultisigKeyCount(opcode, data, num_keys)) return false;
138 
139  if (pubkeys.size() != static_cast<unsigned long>(num_keys) || num_keys < required_sigs) return false;
140 
141  return (it + 1 == script.end());
142 }
143 
144 TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet)
145 {
146  vSolutionsRet.clear();
147 
148  // Shortcut for pay-to-script-hash, which are more constrained than the other types:
149  // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL
150  if (scriptPubKey.IsPayToScriptHash())
151  {
152  std::vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
153  vSolutionsRet.push_back(hashBytes);
154  return TxoutType::SCRIPTHASH;
155  }
156 
157  int witnessversion;
158  std::vector<unsigned char> witnessprogram;
159  if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
160  if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) {
161  vSolutionsRet.push_back(std::move(witnessprogram));
163  }
164  if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
165  vSolutionsRet.push_back(std::move(witnessprogram));
167  }
168  if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
169  vSolutionsRet.push_back(std::move(witnessprogram));
171  }
172  if (witnessversion != 0) {
173  vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion});
174  vSolutionsRet.push_back(std::move(witnessprogram));
176  }
177  return TxoutType::NONSTANDARD;
178  }
179 
180  // Provably prunable, data-carrying output
181  //
182  // So long as script passes the IsUnspendable() test and all but the first
183  // byte passes the IsPushOnly() test we don't care what exactly is in the
184  // script.
185  if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
186  return TxoutType::NULL_DATA;
187  }
188 
189  std::vector<unsigned char> data;
190  if (MatchPayToPubkey(scriptPubKey, data)) {
191  vSolutionsRet.push_back(std::move(data));
192  return TxoutType::PUBKEY;
193  }
194 
195  if (MatchPayToPubkeyHash(scriptPubKey, data)) {
196  vSolutionsRet.push_back(std::move(data));
197  return TxoutType::PUBKEYHASH;
198  }
199 
200  int required;
201  std::vector<std::vector<unsigned char>> keys;
202  if (MatchMultisig(scriptPubKey, required, keys)) {
203  vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20
204  vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
205  vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..20
206  return TxoutType::MULTISIG;
207  }
208 
209  vSolutionsRet.clear();
210  return TxoutType::NONSTANDARD;
211 }
212 
213 bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
214 {
215  std::vector<valtype> vSolutions;
216  TxoutType whichType = Solver(scriptPubKey, vSolutions);
217 
218  switch (whichType) {
219  case TxoutType::PUBKEY: {
220  CPubKey pubKey(vSolutions[0]);
221  if (!pubKey.IsValid())
222  return false;
223 
224  addressRet = PKHash(pubKey);
225  return true;
226  }
227  case TxoutType::PUBKEYHASH: {
228  addressRet = PKHash(uint160(vSolutions[0]));
229  return true;
230  }
231  case TxoutType::SCRIPTHASH: {
232  addressRet = ScriptHash(uint160(vSolutions[0]));
233  return true;
234  }
236  WitnessV0KeyHash hash;
237  std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
238  addressRet = hash;
239  return true;
240  }
242  WitnessV0ScriptHash hash;
243  std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
244  addressRet = hash;
245  return true;
246  }
248  WitnessV1Taproot tap;
249  std::copy(vSolutions[0].begin(), vSolutions[0].end(), tap.begin());
250  addressRet = tap;
251  return true;
252  }
254  WitnessUnknown unk;
255  unk.version = vSolutions[0][0];
256  std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.program);
257  unk.length = vSolutions[1].size();
258  addressRet = unk;
259  return true;
260  }
261  case TxoutType::MULTISIG:
264  return false;
265  } // no default case, so the compiler can warn about missing cases
266  assert(false);
267 }
268 
269 // TODO: from v23 ("addresses" and "reqSigs" deprecated) "ExtractDestinations" should be removed
270 bool ExtractDestinations(const CScript& scriptPubKey, TxoutType& typeRet, std::vector<CTxDestination>& addressRet, int& nRequiredRet)
271 {
272  addressRet.clear();
273  std::vector<valtype> vSolutions;
274  typeRet = Solver(scriptPubKey, vSolutions);
275  if (typeRet == TxoutType::NONSTANDARD) {
276  return false;
277  } else if (typeRet == TxoutType::NULL_DATA) {
278  // This is data, not addresses
279  return false;
280  }
281 
282  if (typeRet == TxoutType::MULTISIG)
283  {
284  nRequiredRet = vSolutions.front()[0];
285  for (unsigned int i = 1; i < vSolutions.size()-1; i++)
286  {
287  CPubKey pubKey(vSolutions[i]);
288  if (!pubKey.IsValid())
289  continue;
290 
291  CTxDestination address = PKHash(pubKey);
292  addressRet.push_back(address);
293  }
294 
295  if (addressRet.empty())
296  return false;
297  }
298  else
299  {
300  nRequiredRet = 1;
301  CTxDestination address;
302  if (!ExtractDestination(scriptPubKey, address))
303  return false;
304  addressRet.push_back(address);
305  }
306 
307  return true;
308 }
309 
310 namespace {
311 class CScriptVisitor
312 {
313 public:
314  CScript operator()(const CNoDestination& dest) const
315  {
316  return CScript();
317  }
318 
319  CScript operator()(const PKHash& keyID) const
320  {
321  return CScript() << OP_DUP << OP_HASH160 << ToByteVector(keyID) << OP_EQUALVERIFY << OP_CHECKSIG;
322  }
323 
324  CScript operator()(const ScriptHash& scriptID) const
325  {
326  return CScript() << OP_HASH160 << ToByteVector(scriptID) << OP_EQUAL;
327  }
328 
329  CScript operator()(const WitnessV0KeyHash& id) const
330  {
331  return CScript() << OP_0 << ToByteVector(id);
332  }
333 
334  CScript operator()(const WitnessV0ScriptHash& id) const
335  {
336  return CScript() << OP_0 << ToByteVector(id);
337  }
338 
339  CScript operator()(const WitnessV1Taproot& tap) const
340  {
341  return CScript() << OP_1 << ToByteVector(tap);
342  }
343 
344  CScript operator()(const WitnessUnknown& id) const
345  {
346  return CScript() << CScript::EncodeOP_N(id.version) << std::vector<unsigned char>(id.program, id.program + id.length);
347  }
348 };
349 } // namespace
350 
352 {
353  return std::visit(CScriptVisitor(), dest);
354 }
355 
357 {
358  return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG;
359 }
360 
361 CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
362 {
363  CScript script;
364 
365  script << nRequired;
366  for (const CPubKey& key : keys)
367  script << ToByteVector(key);
368  script << keys.size() << OP_CHECKMULTISIG;
369 
370  return script;
371 }
372 
374  return dest.index() != 0;
375 }
376 
378 {
379  NodeInfo ret;
380  /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */
381  for (auto& leaf : a.leaves) {
382  leaf.merkle_branch.push_back(b.hash);
383  ret.leaves.emplace_back(std::move(leaf));
384  }
385  /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */
386  for (auto& leaf : b.leaves) {
387  leaf.merkle_branch.push_back(a.hash);
388  ret.leaves.emplace_back(std::move(leaf));
389  }
390  /* Lexicographically sort a and b's hash, and compute parent hash. */
391  if (a.hash < b.hash) {
392  ret.hash = (CHashWriter(HASHER_TAPBRANCH) << a.hash << b.hash).GetSHA256();
393  } else {
394  ret.hash = (CHashWriter(HASHER_TAPBRANCH) << b.hash << a.hash).GetSHA256();
395  }
396  return ret;
397 }
398 
400 {
401  // TODO: figure out how to better deal with conflicting information
402  // being merged.
403  if (internal_key.IsNull() && !other.internal_key.IsNull()) {
404  internal_key = other.internal_key;
405  }
406  if (merkle_root.IsNull() && !other.merkle_root.IsNull()) {
407  merkle_root = other.merkle_root;
408  }
409  for (auto& [key, control_blocks] : other.scripts) {
410  // Once P0083R3 is supported by all our targeted platforms,
411  // this loop body can be replaced with:
412  // scripts[key].merge(std::move(control_blocks));
413  auto& target = scripts[key];
414  for (auto& control_block: control_blocks) {
415  target.insert(std::move(control_block));
416  }
417  }
418 }
419 
421 {
422  assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
423  /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
424  * so would mean the Add() invocations do not correspond to a DFS traversal of a
425  * binary tree. */
426  if ((size_t)depth + 1 < m_branch.size()) {
427  m_valid = false;
428  return;
429  }
430  /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
431  * The 'node' variable is overwritten here with the newly combined node. */
432  while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
433  node = Combine(std::move(node), std::move(*m_branch[depth]));
434  m_branch.pop_back();
435  if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
436  --depth;
437  }
438  if (m_valid) {
439  /* Make sure the branch is big enough to place the new node. */
440  if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
441  assert(!m_branch[depth].has_value());
442  m_branch[depth] = std::move(node);
443  }
444 }
445 
446 /*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
447 {
448  std::vector<bool> branch;
449  for (int depth : depths) {
450  // This inner loop corresponds to effectively the same logic on branch
451  // as what Insert() performs on the m_branch variable. Instead of
452  // storing a NodeInfo object, just remember whether or not there is one
453  // at that depth.
454  if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
455  if ((size_t)depth + 1 < branch.size()) return false;
456  while (branch.size() > (size_t)depth && branch[depth]) {
457  branch.pop_back();
458  if (depth == 0) return false;
459  --depth;
460  }
461  if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
462  assert(!branch[depth]);
463  branch[depth] = true;
464  }
465  // And this check corresponds to the IsComplete() check on m_branch.
466  return branch.size() == 0 || (branch.size() == 1 && branch[0]);
467 }
468 
469 TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version, bool track)
470 {
471  assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
472  if (!IsValid()) return *this;
473  /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
474  NodeInfo node;
475  node.hash = (CHashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256();
476  if (track) node.leaves.emplace_back(LeafInfo{script, leaf_version, {}});
477  /* Insert into the branch. */
478  Insert(std::move(node), depth);
479  return *this;
480 }
481 
483 {
484  if (!IsValid()) return *this;
485  /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
486  NodeInfo node;
487  node.hash = hash;
488  Insert(std::move(node), depth);
489  return *this;
490 }
491 
493 {
494  /* Can only call this function when IsComplete() is true. */
495  assert(IsComplete());
496  m_internal_key = internal_key;
497  auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
498  assert(ret.has_value());
499  std::tie(m_output_key, m_parity) = *ret;
500  return *this;
501 }
502 
504 
506 {
507  TaprootSpendData spd;
508  spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash;
510  if (m_branch.size()) {
511  // If any script paths exist, they have been combined into the root m_branch[0]
512  // by now. Compute the control block for each of its tracked leaves, and put them in
513  // spd.scripts.
514  for (const auto& leaf : m_branch[0]->leaves) {
515  std::vector<unsigned char> control_block;
516  control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size());
517  control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0);
518  std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1);
519  if (leaf.merkle_branch.size()) {
520  std::copy(leaf.merkle_branch[0].begin(),
521  leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(),
522  control_block.begin() + TAPROOT_CONTROL_BASE_SIZE);
523  }
524  spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
525  }
526  }
527  return spd;
528 }
529 
530 std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
531 {
532  // Verify that the output matches the assumed Merkle root and internal key.
533  auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root);
534  if (!tweak || tweak->first != output) return std::nullopt;
535  // If the Merkle root is 0, the tree is empty, and we're done.
536  std::vector<std::tuple<int, CScript, int>> ret;
537  if (spenddata.merkle_root.IsNull()) return ret;
538 
540  struct TreeNode {
542  uint256 hash;
544  std::unique_ptr<TreeNode> sub[2];
547  const std::pair<CScript, int>* leaf = nullptr;
549  bool explored = false;
551  bool inner;
553  bool done = false;
554  };
555 
556  // Build tree from the provided branches.
557  TreeNode root;
558  root.hash = spenddata.merkle_root;
559  for (const auto& [key, control_blocks] : spenddata.scripts) {
560  const auto& [script, leaf_ver] = key;
561  for (const auto& control : control_blocks) {
562  // Skip script records with nonsensical leaf version.
563  if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue;
564  // Skip script records with invalid control block sizes.
565  if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE ||
566  ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue;
567  // Skip script records that don't match the control block.
568  if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue;
569  // Skip script records that don't match the provided Merkle root.
570  const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script);
571  const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash);
572  if (merkle_root != spenddata.merkle_root) continue;
573 
574  TreeNode* node = &root;
575  size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
576  for (size_t depth = 0; depth < levels; ++depth) {
577  // Can't descend into a node which we already know is a leaf.
578  if (node->explored && !node->inner) return std::nullopt;
579 
580  // Extract partner hash from Merkle branch in control block.
581  uint256 hash;
582  std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE,
583  control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE,
584  hash.begin());
585 
586  if (node->sub[0]) {
587  // Descend into the existing left or right branch.
588  bool desc = false;
589  for (int i = 0; i < 2; ++i) {
590  if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) {
591  node->sub[i]->hash = hash;
592  node = &*node->sub[1-i];
593  desc = true;
594  break;
595  }
596  }
597  if (!desc) return std::nullopt; // This probably requires a hash collision to hit.
598  } else {
599  // We're in an unexplored node. Create subtrees and descend.
600  node->explored = true;
601  node->inner = true;
602  node->sub[0] = std::make_unique<TreeNode>();
603  node->sub[1] = std::make_unique<TreeNode>();
604  node->sub[1]->hash = hash;
605  node = &*node->sub[0];
606  }
607  }
608  // Cannot turn a known inner node into a leaf.
609  if (node->sub[0]) return std::nullopt;
610  node->explored = true;
611  node->inner = false;
612  node->leaf = &key;
613  node->hash = leaf_hash;
614  }
615  }
616 
617  // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid
618  // overflowing the call stack (the tree may be 128 levels deep).
619  std::vector<TreeNode*> stack{&root};
620  while (!stack.empty()) {
621  TreeNode& node = *stack.back();
622  if (!node.explored) {
623  // Unexplored node, which means the tree is incomplete.
624  return std::nullopt;
625  } else if (!node.inner) {
626  // Leaf node; produce output.
627  ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second);
628  node.done = true;
629  stack.pop_back();
630  } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() &&
631  (CHashWriter{HASHER_TAPBRANCH} << node.sub[1]->hash << node.sub[1]->hash).GetSHA256() == node.hash) {
632  // Whenever there are nodes with two identical subtrees under it, we run into a problem:
633  // the control blocks for the leaves underneath those will be identical as well, and thus
634  // they will all be matched to the same path in the tree. The result is that at the location
635  // where the duplicate occurred, the left child will contain a normal tree that can be explored
636  // and processed, but the right one will remain unexplored.
637  //
638  // This situation can be detected, by encountering an inner node with unexplored right subtree
639  // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash.
640  //
641  // To deal with this, simply process the left tree a second time (set its done flag to false;
642  // noting that the done flag of its children have already been set to false after processing
643  // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored)
644  // subtree to true.
645  node.sub[0]->done = false;
646  node.sub[1]->done = true;
647  } else if (node.sub[0]->done && node.sub[1]->done) {
648  // An internal node which we're finished with.
649  node.sub[0]->done = false;
650  node.sub[1]->done = false;
651  node.done = true;
652  stack.pop_back();
653  } else if (!node.sub[0]->done) {
654  // An internal node whose left branch hasn't been processed yet. Do so first.
655  stack.push_back(&*node.sub[0]);
656  } else if (!node.sub[1]->done) {
657  // An internal node whose right branch hasn't been processed yet. Do so first.
658  stack.push_back(&*node.sub[1]);
659  }
660  }
661 
662  return ret;
663 }
WITNESS_V0_KEYHASH_SIZE
static constexpr size_t WITNESS_V0_KEYHASH_SIZE
Definition: interpreter.h:215
WITNESS_V0_SCRIPTHASH_SIZE
static constexpr size_t WITNESS_V0_SCRIPTHASH_SIZE
Signature hash sizes.
Definition: interpreter.h:214
WitnessUnknown
CTxDestination subtype to encode any future Witness version.
Definition: standard.h:125
count
static int count
Definition: tests.c:41
HASHER_TAPBRANCH
const CHashWriter HASHER_TAPBRANCH
Hasher with tag "TapBranch" pre-fed to it.
Definition: interpreter.cpp:1488
CSHA256::Write
CSHA256 & Write(const unsigned char *data, size_t len)
Definition: sha256.cpp:637
MatchMultisig
static bool MatchMultisig(const CScript &script, int &required_sigs, std::vector< valtype > &pubkeys)
Definition: standard.cpp:124
Solver
TxoutType Solver(const CScript &scriptPubKey, std::vector< std::vector< unsigned char >> &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
Definition: standard.cpp:144
ScriptHash::ScriptHash
ScriptHash()
Definition: standard.h:91
prevector::const_iterator
Definition: prevector.h:98
TaprootSpendData::scripts
std::map< std::pair< CScript, int >, std::set< std::vector< unsigned char >, ShortestVectorFirstComparator > > scripts
Map from (script, leaf_version) to (sets of) control blocks.
Definition: standard.h:232
TAPROOT_CONTROL_BASE_SIZE
static constexpr size_t TAPROOT_CONTROL_BASE_SIZE
Definition: interpreter.h:220
TxoutType
TxoutType
Definition: standard.h:59
TxoutType::NONSTANDARD
@ NONSTANDARD
TxoutType::WITNESS_UNKNOWN
@ WITNESS_UNKNOWN
Only for Witness versions not already defined above.
GetScriptForDestination
CScript GetScriptForDestination(const CTxDestination &dest)
Generate a Bitcoin scriptPubKey for the given CTxDestination.
Definition: standard.cpp:351
WitnessUnknown::version
unsigned int version
Definition: standard.h:127
CPubKey::SIZE
static constexpr unsigned int SIZE
secp256k1:
Definition: pubkey.h:38
OP_CHECKMULTISIG
@ OP_CHECKMULTISIG
Definition: script.h:184
CScript::IsWitnessProgram
bool IsWitnessProgram(int &version, std::vector< unsigned char > &program) const
Definition: script.cpp:220
TaprootBuilder::GetSpendData
TaprootSpendData GetSpendData() const
Compute spending data (after Finalize()).
Definition: standard.cpp:505
CScriptNum::getint
int getint() const
Definition: script.h:325
BaseHash< uint256 >::begin
unsigned char * begin()
Definition: hash_type.h:18
WitnessUnknown::length
unsigned int length
Definition: standard.h:128
TaprootBuilder::Insert
void Insert(NodeInfo &&node, int depth)
Insert information about a node at a certain depth, and propagate information up.
Definition: standard.cpp:420
scriptnum_error
Definition: script.h:212
TaprootBuilder::NodeInfo
Information associated with a node in the Merkle tree.
Definition: standard.h:250
interpreter.h
opcodetype
opcodetype
Script opcodes.
Definition: script.h:65
CScript::EncodeOP_N
static opcodetype EncodeOP_N(int n)
Definition: script.h:504
XOnlyPubKey
Definition: pubkey.h:220
CScript::DecodeOP_N
static int DecodeOP_N(opcodetype opcode)
Encode/decode small integers:
Definition: script.h:497
CKeyID
A reference to a CKey: the Hash160 of its serialized public key.
Definition: pubkey.h:22
CScript::IsPayToScriptHash
bool IsPayToScriptHash() const
Definition: script.cpp:201
pubkey.h
BaseHash
Definition: hash_type.h:9
CPubKey::ValidSize
static bool ValidSize(const std::vector< unsigned char > &vch)
Definition: pubkey.h:76
MAX_PUBKEYS_PER_MULTISIG
static const int MAX_PUBKEYS_PER_MULTISIG
Definition: script.h:29
TxoutType::WITNESS_V1_TAPROOT
@ WITNESS_V1_TAPROOT
TAPROOT_CONTROL_MAX_SIZE
static constexpr size_t TAPROOT_CONTROL_MAX_SIZE
Definition: interpreter.h:223
MatchPayToPubkey
static bool MatchPayToPubkey(const CScript &script, valtype &pubkey)
Definition: standard.cpp:66
WitnessV0KeyHash
Definition: standard.h:109
OP_FALSE
@ OP_FALSE
Definition: script.h:69
CheckMinimalPush
bool CheckMinimalPush(const valtype &data, opcodetype opcode)
Definition: interpreter.cpp:228
CScript::IsPushOnly
bool IsPushOnly(const_iterator pc) const
Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical).
Definition: script.cpp:236
CScriptNum
Definition: script.h:218
XOnlyPubKey::begin
const unsigned char * begin() const
Definition: pubkey.h:273
CPubKey::begin
const unsigned char * begin() const
Definition: pubkey.h:113
OP_1
@ OP_1
Definition: script.h:75
prevector::end
iterator end()
Definition: prevector.h:292
strencodings.h
OP_0
@ OP_0
Definition: script.h:68
TxoutType::WITNESS_V0_SCRIPTHASH
@ WITNESS_V0_SCRIPTHASH
ComputeTaprootMerkleRoot
uint256 ComputeTaprootMerkleRoot(Span< const unsigned char > control, const uint256 &tapleaf_hash)
Compute the BIP341 taproot script tree Merkle root from control block and leaf hash.
Definition: interpreter.cpp:1855
OP_RETURN
@ OP_RETURN
Definition: script.h:103
ToByteVector
std::vector< unsigned char > ToByteVector(const T &in)
Definition: script.h:59
TxoutType::PUBKEY
@ PUBKEY
CTxDestination
std::variant< CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessV1Taproot, WitnessUnknown > CTxDestination
A txout script template with a specific destination.
Definition: standard.h:157
GetMultisigKeyCount
static bool GetMultisigKeyCount(opcodetype opcode, valtype data, int &count)
Definition: standard.cpp:104
TaprootBuilder::GetOutput
WitnessV1Taproot GetOutput()
Compute scriptPubKey (after Finalize()).
Definition: standard.cpp:503
OP_16
@ OP_16
Definition: script.h:91
IsValidDestination
bool IsValidDestination(const CTxDestination &dest)
Check whether a CTxDestination is a CNoDestination.
Definition: standard.cpp:373
GetScriptForRawPubKey
CScript GetScriptForRawPubKey(const CPubKey &pubKey)
Generate a P2PK script for the given pubkey.
Definition: standard.cpp:356
TaprootSpendData
Definition: standard.h:223
GetScriptForMultisig
CScript GetScriptForMultisig(int nRequired, const std::vector< CPubKey > &keys)
Generate a multisig script.
Definition: standard.cpp:361
OP_EQUAL
@ OP_EQUAL
Definition: script.h:138
TaprootBuilder::m_valid
bool m_valid
Whether the builder is in a valid state so far.
Definition: standard.h:259
CPubKey::end
const unsigned char * end() const
Definition: pubkey.h:114
XOnlyPubKey::end
const unsigned char * end() const
Definition: pubkey.h:274
TaprootBuilder::NodeInfo::leaves
std::vector< LeafInfo > leaves
Tracked leaves underneath this node (either from the node itself, or its children).
Definition: standard.h:256
IsSmallInteger
static constexpr bool IsSmallInteger(opcodetype opcode)
Test for "small positive integer" script opcodes - OP_1 through OP_16.
Definition: standard.cpp:89
prevector::back
T & back()
Definition: prevector.h:453
IsValidMultisigKeyCount
static constexpr bool IsValidMultisigKeyCount(int n_keys)
Definition: standard.cpp:99
TAPROOT_LEAF_MASK
static constexpr uint8_t TAPROOT_LEAF_MASK
Definition: interpreter.h:218
TaprootSpendData::merkle_root
uint256 merkle_root
The Merkle root of the script tree (0 if no scripts).
Definition: standard.h:228
TaprootBuilder::Add
TaprootBuilder & Add(int depth, const CScript &script, int leaf_version, bool track=true)
Add a new script at a certain depth in the tree.
Definition: standard.cpp:469
standard.h
IsPushdataOp
static constexpr bool IsPushdataOp(opcodetype opcode)
Definition: standard.cpp:94
TxoutType::SCRIPTHASH
@ SCRIPTHASH
CPubKey::COMPRESSED_SIZE
static constexpr unsigned int COMPRESSED_SIZE
Definition: pubkey.h:39
uint256
256-bit opaque blob.
Definition: uint256.h:124
nMaxDatacarrierBytes
unsigned nMaxDatacarrierBytes
Maximum size of TxoutType::NULL_DATA scripts that this node considers standard.
Definition: standard.cpp:20
XOnlyPubKey::IsNull
bool IsNull() const
Test whether this is the 0 key (the result of default construction).
Definition: pubkey.h:239
CSHA256::Finalize
void Finalize(unsigned char hash[OUTPUT_SIZE])
Definition: sha256.cpp:663
TaprootBuilder::NodeInfo::hash
uint256 hash
Merkle hash of this node.
Definition: standard.h:253
TaprootBuilder::m_branch
std::vector< std::optional< NodeInfo > > m_branch
The current state of the builder.
Definition: standard.h:296
CScript
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:404
TaprootBuilder::m_output_key
XOnlyPubKey m_output_key
The output key, computed when finalizing.
Definition: standard.h:299
TaprootBuilder::ValidDepths
static bool ValidDepths(const std::vector< int > &depths)
Check if a list of depths is legal (will lead to IsComplete()).
Definition: standard.cpp:446
TaprootBuilder::IsComplete
bool IsComplete() const
Return whether there were either no leaves, or the leaves form a Huffman tree.
Definition: standard.h:321
script.h
ExtractDestination
bool ExtractDestination(const CScript &scriptPubKey, CTxDestination &addressRet)
Parse a standard scriptPubKey for the destination address.
Definition: standard.cpp:213
CNoDestination
Definition: standard.h:73
OP_HASH160
@ OP_HASH160
Definition: script.h:179
TaprootSpendData::internal_key
XOnlyPubKey internal_key
The BIP341 internal key.
Definition: standard.h:226
TxoutType::NULL_DATA
@ NULL_DATA
unspendable OP_RETURN script that carries data
sha256.h
TxoutType::PUBKEYHASH
@ PUBKEYHASH
PKHash
Definition: standard.h:79
ToKeyID
CKeyID ToKeyID(const PKHash &key_hash)
Definition: standard.cpp:34
GetTxnOutputType
std::string GetTxnOutputType(TxoutType t)
Get the name of a TxoutType as a string.
Definition: standard.cpp:49
uint160
160-bit opaque blob.
Definition: uint256.h:113
CPubKey
An encapsulated public key.
Definition: pubkey.h:32
MAX_OP_RETURN_RELAY
static const unsigned int MAX_OP_RETURN_RELAY
Default setting for nMaxDatacarrierBytes.
Definition: standard.h:38
base_blob::IsNull
bool IsNull() const
Definition: uint256.h:31
HASHER_TAPLEAF
const CHashWriter HASHER_TAPLEAF
Hasher with tag "TapLeaf" pre-fed to it.
Definition: interpreter.cpp:1487
InferTaprootTree
std::optional< std::vector< std::tuple< int, CScript, int > > > InferTaprootTree(const TaprootSpendData &spenddata, const XOnlyPubKey &output)
Given a TaprootSpendData and the output key, reconstruct its script tree.
Definition: standard.cpp:530
Hash160
uint160 Hash160(const T1 &in1)
Compute the 160-bit hash an object.
Definition: hash.h:92
PKHash::PKHash
PKHash()
Definition: standard.h:81
TaprootBuilder::m_internal_key
XOnlyPubKey m_internal_key
The internal key, set when finalizing.
Definition: standard.h:298
prevector::data
value_type * data()
Definition: prevector.h:528
TaprootBuilder::LeafInfo
Information about a tracked leaf in the Merkle tree.
Definition: standard.h:242
CHashWriter
A writer stream (for serialization) that computes a 256-bit hash.
Definition: hash.h:100
prevector::size
size_type size() const
Definition: prevector.h:282
prevector::begin
iterator begin()
Definition: prevector.h:290
TxoutType::MULTISIG
@ MULTISIG
TaprootBuilder::m_parity
bool m_parity
The tweak parity, computed when finalizing.
Definition: standard.h:300
CSHA256
A hasher class for SHA-256.
Definition: sha256.h:13
TaprootBuilder::IsValid
bool IsValid() const
Return true if so far all input was valid.
Definition: standard.h:319
node
Definition: interfaces.cpp:68
OP_EQUALVERIFY
@ OP_EQUALVERIFY
Definition: script.h:139
assert
assert(s1.IsAddrV1Compatible())
WITNESS_V1_TAPROOT_SIZE
static constexpr size_t WITNESS_V1_TAPROOT_SIZE
Definition: interpreter.h:216
valtype
std::vector< unsigned char > valtype
Definition: interpreter.cpp:15
MatchPayToPubkeyHash
static bool MatchPayToPubkeyHash(const CScript &script, valtype &pubkeyhash)
Definition: standard.cpp:79
TAPROOT_CONTROL_NODE_SIZE
static constexpr size_t TAPROOT_CONTROL_NODE_SIZE
Definition: interpreter.h:221
TaprootBuilder::Finalize
TaprootBuilder & Finalize(const XOnlyPubKey &internal_key)
Finalize the construction.
Definition: standard.cpp:492
CPubKey::IsValid
bool IsValid() const
Definition: pubkey.h:185
TaprootBuilder
Utility class to construct Taproot outputs from internal key and script tree.
Definition: standard.h:238
TxoutType::WITNESS_V0_KEYHASH
@ WITNESS_V0_KEYHASH
WitnessV0ScriptHash
Definition: standard.h:102
ComputeTapleafHash
uint256 ComputeTapleafHash(uint8_t leaf_version, const CScript &script)
Compute the BIP341 tapleaf hash from leaf version & script.
Definition: interpreter.cpp:1850
CScriptID
A reference to a CScript: the Hash160 of its serialization (see script.h)
Definition: standard.h:25
WitnessV0KeyHash::WitnessV0KeyHash
WitnessV0KeyHash()
Definition: standard.h:111
ExtractDestinations
bool ExtractDestinations(const CScript &scriptPubKey, TxoutType &typeRet, std::vector< CTxDestination > &addressRet, int &nRequiredRet)
Parse a standard scriptPubKey with one or more destination addresses.
Definition: standard.cpp:270
fAcceptDatacarrier
bool fAcceptDatacarrier
A data carrying output is an unspendable output containing data.
Definition: standard.cpp:19
OP_CHECKSIG
@ OP_CHECKSIG
Definition: script.h:182
CScriptID::CScriptID
CScriptID()
Definition: standard.h:28
OP_PUSHDATA4
@ OP_PUSHDATA4
Definition: script.h:72
WitnessV0ScriptHash::WitnessV0ScriptHash
WitnessV0ScriptHash()
Definition: standard.h:104
TaprootBuilder::AddOmitted
TaprootBuilder & AddOmitted(int depth, const uint256 &hash)
Like Add(), but for a Merkle node with a given hash to the tree.
Definition: standard.cpp:482
TaprootBuilder::Combine
static NodeInfo Combine(NodeInfo &&a, NodeInfo &&b)
Combine information about a parent Merkle tree node from its child nodes.
Definition: standard.cpp:377
ScriptHash
Definition: standard.h:89
base_blob::begin
unsigned char * begin()
Definition: uint256.h:58
OP_DUP
@ OP_DUP
Definition: script.h:117
valtype
std::vector< unsigned char > valtype
Definition: standard.cpp:17
TaprootSpendData::Merge
void Merge(TaprootSpendData other)
Merge other TaprootSpendData (for the same scriptPubKey) into this.
Definition: standard.cpp:399
XOnlyPubKey::CreateTapTweak
std::optional< std::pair< XOnlyPubKey, bool > > CreateTapTweak(const uint256 *merkle_root) const
Construct a Taproot tweaked output point with this point as internal key.
Definition: pubkey.cpp:218
WitnessUnknown::program
unsigned char program[40]
Definition: standard.h:129
CScript::GetOp
bool GetOp(const_iterator &pc, opcodetype &opcodeRet, std::vector< unsigned char > &vchRet) const
Definition: script.h:486
TAPROOT_CONTROL_MAX_NODE_COUNT
static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT
Definition: interpreter.h:222
DEFAULT_ACCEPT_DATACARRIER
static const bool DEFAULT_ACCEPT_DATACARRIER
Definition: standard.h:18
WitnessV1Taproot
Definition: standard.h:118