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 namespace {
270 class CScriptVisitor
271 {
272 public:
273  CScript operator()(const CNoDestination& dest) const
274  {
275  return CScript();
276  }
277 
278  CScript operator()(const PKHash& keyID) const
279  {
280  return CScript() << OP_DUP << OP_HASH160 << ToByteVector(keyID) << OP_EQUALVERIFY << OP_CHECKSIG;
281  }
282 
283  CScript operator()(const ScriptHash& scriptID) const
284  {
285  return CScript() << OP_HASH160 << ToByteVector(scriptID) << OP_EQUAL;
286  }
287 
288  CScript operator()(const WitnessV0KeyHash& id) const
289  {
290  return CScript() << OP_0 << ToByteVector(id);
291  }
292 
293  CScript operator()(const WitnessV0ScriptHash& id) const
294  {
295  return CScript() << OP_0 << ToByteVector(id);
296  }
297 
298  CScript operator()(const WitnessV1Taproot& tap) const
299  {
300  return CScript() << OP_1 << ToByteVector(tap);
301  }
302 
303  CScript operator()(const WitnessUnknown& id) const
304  {
305  return CScript() << CScript::EncodeOP_N(id.version) << std::vector<unsigned char>(id.program, id.program + id.length);
306  }
307 };
308 } // namespace
309 
311 {
312  return std::visit(CScriptVisitor(), dest);
313 }
314 
316 {
317  return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG;
318 }
319 
320 CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
321 {
322  CScript script;
323 
324  script << nRequired;
325  for (const CPubKey& key : keys)
326  script << ToByteVector(key);
327  script << keys.size() << OP_CHECKMULTISIG;
328 
329  return script;
330 }
331 
333  return dest.index() != 0;
334 }
335 
337 {
338  NodeInfo ret;
339  /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */
340  for (auto& leaf : a.leaves) {
341  leaf.merkle_branch.push_back(b.hash);
342  ret.leaves.emplace_back(std::move(leaf));
343  }
344  /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */
345  for (auto& leaf : b.leaves) {
346  leaf.merkle_branch.push_back(a.hash);
347  ret.leaves.emplace_back(std::move(leaf));
348  }
349  /* Lexicographically sort a and b's hash, and compute parent hash. */
350  if (a.hash < b.hash) {
351  ret.hash = (CHashWriter(HASHER_TAPBRANCH) << a.hash << b.hash).GetSHA256();
352  } else {
353  ret.hash = (CHashWriter(HASHER_TAPBRANCH) << b.hash << a.hash).GetSHA256();
354  }
355  return ret;
356 }
357 
359 {
360  // TODO: figure out how to better deal with conflicting information
361  // being merged.
362  if (internal_key.IsNull() && !other.internal_key.IsNull()) {
363  internal_key = other.internal_key;
364  }
365  if (merkle_root.IsNull() && !other.merkle_root.IsNull()) {
366  merkle_root = other.merkle_root;
367  }
368  for (auto& [key, control_blocks] : other.scripts) {
369  // Once P0083R3 is supported by all our targeted platforms,
370  // this loop body can be replaced with:
371  // scripts[key].merge(std::move(control_blocks));
372  auto& target = scripts[key];
373  for (auto& control_block: control_blocks) {
374  target.insert(std::move(control_block));
375  }
376  }
377 }
378 
380 {
381  assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
382  /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
383  * so would mean the Add() invocations do not correspond to a DFS traversal of a
384  * binary tree. */
385  if ((size_t)depth + 1 < m_branch.size()) {
386  m_valid = false;
387  return;
388  }
389  /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
390  * The 'node' variable is overwritten here with the newly combined node. */
391  while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
392  node = Combine(std::move(node), std::move(*m_branch[depth]));
393  m_branch.pop_back();
394  if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
395  --depth;
396  }
397  if (m_valid) {
398  /* Make sure the branch is big enough to place the new node. */
399  if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
400  assert(!m_branch[depth].has_value());
401  m_branch[depth] = std::move(node);
402  }
403 }
404 
405 /*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
406 {
407  std::vector<bool> branch;
408  for (int depth : depths) {
409  // This inner loop corresponds to effectively the same logic on branch
410  // as what Insert() performs on the m_branch variable. Instead of
411  // storing a NodeInfo object, just remember whether or not there is one
412  // at that depth.
413  if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
414  if ((size_t)depth + 1 < branch.size()) return false;
415  while (branch.size() > (size_t)depth && branch[depth]) {
416  branch.pop_back();
417  if (depth == 0) return false;
418  --depth;
419  }
420  if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
421  assert(!branch[depth]);
422  branch[depth] = true;
423  }
424  // And this check corresponds to the IsComplete() check on m_branch.
425  return branch.size() == 0 || (branch.size() == 1 && branch[0]);
426 }
427 
428 TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version, bool track)
429 {
430  assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
431  if (!IsValid()) return *this;
432  /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
433  NodeInfo node;
434  node.hash = (CHashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256();
435  if (track) node.leaves.emplace_back(LeafInfo{script, leaf_version, {}});
436  /* Insert into the branch. */
437  Insert(std::move(node), depth);
438  return *this;
439 }
440 
442 {
443  if (!IsValid()) return *this;
444  /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
445  NodeInfo node;
446  node.hash = hash;
447  Insert(std::move(node), depth);
448  return *this;
449 }
450 
452 {
453  /* Can only call this function when IsComplete() is true. */
454  assert(IsComplete());
455  m_internal_key = internal_key;
456  auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
457  assert(ret.has_value());
458  std::tie(m_output_key, m_parity) = *ret;
459  return *this;
460 }
461 
463 
465 {
466  assert(IsComplete());
467  TaprootSpendData spd;
468  spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash;
470  if (m_branch.size()) {
471  // If any script paths exist, they have been combined into the root m_branch[0]
472  // by now. Compute the control block for each of its tracked leaves, and put them in
473  // spd.scripts.
474  for (const auto& leaf : m_branch[0]->leaves) {
475  std::vector<unsigned char> control_block;
476  control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size());
477  control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0);
478  std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1);
479  if (leaf.merkle_branch.size()) {
480  std::copy(leaf.merkle_branch[0].begin(),
481  leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(),
482  control_block.begin() + TAPROOT_CONTROL_BASE_SIZE);
483  }
484  spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
485  }
486  }
487  return spd;
488 }
489 
490 std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
491 {
492  // Verify that the output matches the assumed Merkle root and internal key.
493  auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root);
494  if (!tweak || tweak->first != output) return std::nullopt;
495  // If the Merkle root is 0, the tree is empty, and we're done.
496  std::vector<std::tuple<int, CScript, int>> ret;
497  if (spenddata.merkle_root.IsNull()) return ret;
498 
500  struct TreeNode {
502  uint256 hash;
504  std::unique_ptr<TreeNode> sub[2];
507  const std::pair<CScript, int>* leaf = nullptr;
509  bool explored = false;
511  bool inner;
513  bool done = false;
514  };
515 
516  // Build tree from the provided branches.
517  TreeNode root;
518  root.hash = spenddata.merkle_root;
519  for (const auto& [key, control_blocks] : spenddata.scripts) {
520  const auto& [script, leaf_ver] = key;
521  for (const auto& control : control_blocks) {
522  // Skip script records with nonsensical leaf version.
523  if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue;
524  // Skip script records with invalid control block sizes.
525  if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE ||
526  ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue;
527  // Skip script records that don't match the control block.
528  if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue;
529  // Skip script records that don't match the provided Merkle root.
530  const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script);
531  const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash);
532  if (merkle_root != spenddata.merkle_root) continue;
533 
534  TreeNode* node = &root;
535  size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
536  for (size_t depth = 0; depth < levels; ++depth) {
537  // Can't descend into a node which we already know is a leaf.
538  if (node->explored && !node->inner) return std::nullopt;
539 
540  // Extract partner hash from Merkle branch in control block.
541  uint256 hash;
542  std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE,
543  control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE,
544  hash.begin());
545 
546  if (node->sub[0]) {
547  // Descend into the existing left or right branch.
548  bool desc = false;
549  for (int i = 0; i < 2; ++i) {
550  if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) {
551  node->sub[i]->hash = hash;
552  node = &*node->sub[1-i];
553  desc = true;
554  break;
555  }
556  }
557  if (!desc) return std::nullopt; // This probably requires a hash collision to hit.
558  } else {
559  // We're in an unexplored node. Create subtrees and descend.
560  node->explored = true;
561  node->inner = true;
562  node->sub[0] = std::make_unique<TreeNode>();
563  node->sub[1] = std::make_unique<TreeNode>();
564  node->sub[1]->hash = hash;
565  node = &*node->sub[0];
566  }
567  }
568  // Cannot turn a known inner node into a leaf.
569  if (node->sub[0]) return std::nullopt;
570  node->explored = true;
571  node->inner = false;
572  node->leaf = &key;
573  node->hash = leaf_hash;
574  }
575  }
576 
577  // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid
578  // overflowing the call stack (the tree may be 128 levels deep).
579  std::vector<TreeNode*> stack{&root};
580  while (!stack.empty()) {
581  TreeNode& node = *stack.back();
582  if (!node.explored) {
583  // Unexplored node, which means the tree is incomplete.
584  return std::nullopt;
585  } else if (!node.inner) {
586  // Leaf node; produce output.
587  ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second);
588  node.done = true;
589  stack.pop_back();
590  } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() &&
591  (CHashWriter{HASHER_TAPBRANCH} << node.sub[1]->hash << node.sub[1]->hash).GetSHA256() == node.hash) {
592  // Whenever there are nodes with two identical subtrees under it, we run into a problem:
593  // the control blocks for the leaves underneath those will be identical as well, and thus
594  // they will all be matched to the same path in the tree. The result is that at the location
595  // where the duplicate occurred, the left child will contain a normal tree that can be explored
596  // and processed, but the right one will remain unexplored.
597  //
598  // This situation can be detected, by encountering an inner node with unexplored right subtree
599  // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash.
600  //
601  // To deal with this, simply process the left tree a second time (set its done flag to false;
602  // noting that the done flag of its children have already been set to false after processing
603  // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored)
604  // subtree to true.
605  node.sub[0]->done = false;
606  node.sub[1]->done = true;
607  } else if (node.sub[0]->done && node.sub[1]->done) {
608  // An internal node which we're finished with.
609  node.sub[0]->done = false;
610  node.sub[1]->done = false;
611  node.done = true;
612  stack.pop_back();
613  } else if (!node.sub[0]->done) {
614  // An internal node whose left branch hasn't been processed yet. Do so first.
615  stack.push_back(&*node.sub[0]);
616  } else if (!node.sub[1]->done) {
617  // An internal node whose right branch hasn't been processed yet. Do so first.
618  stack.push_back(&*node.sub[1]);
619  }
620  }
621 
622  return ret;
623 }
WITNESS_V0_KEYHASH_SIZE
static constexpr size_t WITNESS_V0_KEYHASH_SIZE
Definition: interpreter.h:222
WITNESS_V0_SCRIPTHASH_SIZE
static constexpr size_t WITNESS_V0_SCRIPTHASH_SIZE
Signature hash sizes.
Definition: interpreter.h:221
WitnessUnknown
CTxDestination subtype to encode any future Witness version.
Definition: standard.h:125
count
static int count
Definition: tests.c:41
assert
assert(!tx.IsCoinBase())
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:219
TAPROOT_CONTROL_BASE_SIZE
static constexpr size_t TAPROOT_CONTROL_BASE_SIZE
Definition: interpreter.h:227
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:310
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:185
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:464
CScriptNum::getint
int getint() const
Definition: script.h:326
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:379
scriptnum_error
Definition: script.h:213
TaprootBuilder::NodeInfo
Information associated with a node in the Merkle tree.
Definition: standard.h:237
interpreter.h
opcodetype
opcodetype
Script opcodes.
Definition: script.h:66
CScript::EncodeOP_N
static opcodetype EncodeOP_N(int n)
Definition: script.h:505
XOnlyPubKey
Definition: pubkey.h:220
CScript::DecodeOP_N
static int DecodeOP_N(opcodetype opcode)
Encode/decode small integers:
Definition: script.h:498
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:30
TxoutType::WITNESS_V1_TAPROOT
@ WITNESS_V1_TAPROOT
TAPROOT_CONTROL_MAX_SIZE
static constexpr size_t TAPROOT_CONTROL_MAX_SIZE
Definition: interpreter.h:230
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:70
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:219
XOnlyPubKey::begin
const unsigned char * begin() const
Definition: pubkey.h:278
CPubKey::begin
const unsigned char * begin() const
Definition: pubkey.h:113
OP_1
@ OP_1
Definition: script.h:76
prevector::end
iterator end()
Definition: prevector.h:292
strencodings.h
OP_0
@ OP_0
Definition: script.h:69
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:104
ToByteVector
std::vector< unsigned char > ToByteVector(const T &in)
Definition: script.h:60
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:462
OP_16
@ OP_16
Definition: script.h:92
IsValidDestination
bool IsValidDestination(const CTxDestination &dest)
Check whether a CTxDestination is a CNoDestination.
Definition: standard.cpp:332
GetScriptForRawPubKey
CScript GetScriptForRawPubKey(const CPubKey &pubKey)
Generate a P2PK script for the given pubkey.
Definition: standard.cpp:315
TaprootSpendData
Definition: standard.h:207
GetScriptForMultisig
CScript GetScriptForMultisig(int nRequired, const std::vector< CPubKey > &keys)
Generate a multisig script.
Definition: standard.cpp:320
OP_EQUAL
@ OP_EQUAL
Definition: script.h:139
TaprootBuilder::m_valid
bool m_valid
Whether the builder is in a valid state so far.
Definition: standard.h:246
CPubKey::end
const unsigned char * end() const
Definition: pubkey.h:114
XOnlyPubKey::end
const unsigned char * end() const
Definition: pubkey.h:279
TaprootBuilder::NodeInfo::leaves
std::vector< LeafInfo > leaves
Tracked leaves underneath this node (either from the node itself, or its children).
Definition: standard.h:243
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:225
TaprootSpendData::merkle_root
uint256 merkle_root
The Merkle root of the script tree (0 if no scripts).
Definition: standard.h:212
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:428
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:240
TaprootBuilder::m_branch
std::vector< std::optional< NodeInfo > > m_branch
The current state of the builder.
Definition: standard.h:283
CScript
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:405
TaprootBuilder::m_output_key
XOnlyPubKey m_output_key
The output key, computed when finalizing.
Definition: standard.h:286
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:405
TaprootBuilder::IsComplete
bool IsComplete() const
Return whether there were either no leaves, or the leaves form a Huffman tree.
Definition: standard.h:308
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:180
TaprootSpendData::internal_key
XOnlyPubKey internal_key
The BIP341 internal key.
Definition: standard.h:210
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:490
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:285
prevector::data
value_type * data()
Definition: prevector.h:528
TaprootBuilder::LeafInfo
Information about a tracked leaf in the Merkle tree.
Definition: standard.h:229
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:287
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:306
node
Definition: interfaces.cpp:68
OP_EQUALVERIFY
@ OP_EQUALVERIFY
Definition: script.h:140
WITNESS_V1_TAPROOT_SIZE
static constexpr size_t WITNESS_V1_TAPROOT_SIZE
Definition: interpreter.h:223
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:228
TaprootBuilder::Finalize
TaprootBuilder & Finalize(const XOnlyPubKey &internal_key)
Finalize the construction.
Definition: standard.cpp:451
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:225
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
fAcceptDatacarrier
bool fAcceptDatacarrier
A data carrying output is an unspendable output containing data.
Definition: standard.cpp:19
OP_CHECKSIG
@ OP_CHECKSIG
Definition: script.h:183
CScriptID::CScriptID
CScriptID()
Definition: standard.h:28
OP_PUSHDATA4
@ OP_PUSHDATA4
Definition: script.h:73
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:441
TaprootBuilder::Combine
static NodeInfo Combine(NodeInfo &&a, NodeInfo &&b)
Combine information about a parent Merkle tree node from its child nodes.
Definition: standard.cpp:336
ScriptHash
Definition: standard.h:89
base_blob::begin
unsigned char * begin()
Definition: uint256.h:58
OP_DUP
@ OP_DUP
Definition: script.h:118
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:358
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:235
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:487
TAPROOT_CONTROL_MAX_NODE_COUNT
static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT
Definition: interpreter.h:229
DEFAULT_ACCEPT_DATACARRIER
static const bool DEFAULT_ACCEPT_DATACARRIER
Definition: standard.h:18
WitnessV1Taproot
Definition: standard.h:118