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