17 typedef std::vector<unsigned char>
valtype;
108 if (count < min || count > max)
return {};
120 if (!script.
GetOp(it, opcode, data))
return false;
122 if (!req_sigs)
return false;
123 required_sigs = *req_sigs;
125 pubkeys.emplace_back(std::move(data));
128 if (!num_keys)
return false;
129 if (pubkeys.size() !=
static_cast<unsigned long>(*num_keys))
return false;
131 return (it + 1 == script.
end());
134 std::optional<std::pair<int, std::vector<Span<const unsigned char>>>>
MatchMultiA(
const CScript& script)
136 std::vector<Span<const unsigned char>> keyspans;
142 auto it = script.
begin();
143 while (script.
end() - it >= 34) {
144 if (*it != 32)
return {};
146 keyspans.emplace_back(&*it, 32);
155 std::vector<unsigned char> data;
156 if (!script.
GetOp(it, opcode, data))
return {};
157 if (it == script.
end())
return {};
160 if (it != script.
end())
return {};
161 auto threshold =
GetScriptNumber(opcode, data, 1, (
int)keyspans.size());
162 if (!threshold)
return {};
165 return std::pair{*threshold, std::move(keyspans)};
170 vSolutionsRet.clear();
176 std::vector<unsigned char> hashBytes(scriptPubKey.
begin()+2, scriptPubKey.
begin()+22);
177 vSolutionsRet.push_back(hashBytes);
182 std::vector<unsigned char> witnessprogram;
185 vSolutionsRet.push_back(std::move(witnessprogram));
189 vSolutionsRet.push_back(std::move(witnessprogram));
193 vSolutionsRet.push_back(std::move(witnessprogram));
196 if (witnessversion != 0) {
197 vSolutionsRet.push_back(std::vector<unsigned char>{(
unsigned char)witnessversion});
198 vSolutionsRet.push_back(std::move(witnessprogram));
213 std::vector<unsigned char> data;
215 vSolutionsRet.push_back(std::move(data));
220 vSolutionsRet.push_back(std::move(data));
225 std::vector<std::vector<unsigned char>> keys;
227 vSolutionsRet.push_back({
static_cast<unsigned char>(required)});
228 vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
229 vSolutionsRet.push_back({
static_cast<unsigned char>(keys.size())});
233 vSolutionsRet.clear();
239 std::vector<valtype> vSolutions;
248 addressRet =
PKHash(pubKey);
261 std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.
begin());
267 std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.
begin());
273 std::copy(vSolutions[0].begin(), vSolutions[0].end(), tap.
begin());
279 unk.
version = vSolutions[0][0];
280 std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.
program);
281 unk.
length = vSolutions[1].size();
336 return std::visit(CScriptVisitor(), dest);
349 for (
const CPubKey& key : keys)
357 return dest.index() != 0;
364 for (
auto& leaf : a.leaves) {
365 leaf.merkle_branch.push_back(b.hash);
366 ret.leaves.emplace_back(std::move(leaf));
369 for (
auto& leaf : b.leaves) {
370 leaf.merkle_branch.push_back(a.hash);
371 ret.leaves.emplace_back(std::move(leaf));
387 for (
auto& [key, control_blocks] : other.
scripts) {
388 scripts[key].merge(std::move(control_blocks));
398 if ((
size_t)depth + 1 <
m_branch.size()) {
407 if (depth == 0)
m_valid =
false;
420 std::vector<bool> branch;
421 for (
int depth : depths) {
427 if ((
size_t)depth + 1 < branch.size())
return false;
428 while (branch.size() > (
size_t)depth && branch[depth]) {
430 if (depth == 0)
return false;
433 if (branch.size() <= (
size_t)depth) branch.resize((
size_t)depth + 1);
435 branch[depth] =
true;
438 return branch.size() == 0 || (branch.size() == 1 && branch[0]);
448 if (track)
node.leaves.emplace_back(
LeafInfo{std::vector<unsigned char>(script.
begin(), script.
end()), leaf_version, {}});
488 for (
const auto& leaf :
m_branch[0]->leaves) {
489 std::vector<unsigned char> control_block;
491 control_block[0] = leaf.leaf_version | (
m_parity ? 1 : 0);
493 if (leaf.merkle_branch.size()) {
494 std::copy(leaf.merkle_branch[0].begin(),
498 spd.
scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
508 if (!tweak || tweak->first != output)
return std::nullopt;
510 std::vector<std::tuple<int, std::vector<unsigned char>,
int>>
ret;
518 std::unique_ptr<TreeNode> sub[2];
521 const std::pair<std::vector<unsigned char>,
int>* leaf =
nullptr;
523 bool explored =
false;
533 for (
const auto& [key, control_blocks] : spenddata.
scripts) {
534 const auto& [script, leaf_ver] = key;
535 for (
const auto& control : control_blocks) {
537 if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1)
continue;
546 if (merkle_root != spenddata.
merkle_root)
continue;
548 TreeNode*
node = &root;
550 for (
size_t depth = 0; depth < levels; ++depth) {
552 if (
node->explored && !
node->inner)
return std::nullopt;
563 for (
int i = 0; i < 2; ++i) {
564 if (
node->sub[i]->hash == hash || (
node->sub[i]->hash.IsNull() &&
node->sub[1-i]->hash != hash)) {
565 node->sub[i]->hash = hash;
571 if (!desc)
return std::nullopt;
574 node->explored =
true;
576 node->sub[0] = std::make_unique<TreeNode>();
577 node->sub[1] = std::make_unique<TreeNode>();
578 node->sub[1]->hash = hash;
583 if (
node->sub[0])
return std::nullopt;
584 node->explored =
true;
587 node->hash = leaf_hash;
593 std::vector<TreeNode*> stack{&root};
594 while (!stack.empty()) {
595 TreeNode&
node = *stack.back();
596 if (!
node.explored) {
599 }
else if (!
node.inner) {
601 ret.emplace_back(stack.size() - 1,
node.leaf->first,
node.leaf->second);
604 }
else if (
node.sub[0]->done && !
node.sub[1]->done && !
node.sub[1]->explored && !
node.sub[1]->hash.IsNull() &&
619 node.sub[0]->done =
false;
620 node.sub[1]->done =
true;
621 }
else if (
node.sub[0]->done &&
node.sub[1]->done) {
623 node.sub[0]->done =
false;
624 node.sub[1]->done =
false;
627 }
else if (!
node.sub[0]->done) {
629 stack.push_back(&*
node.sub[0]);
630 }
else if (!
node.sub[1]->done) {
632 stack.push_back(&*
node.sub[1]);
642 std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> tuples;
644 const auto& leaves =
m_branch[0]->leaves;
645 for (
const auto& leaf : leaves) {
647 uint8_t depth = (uint8_t)leaf.merkle_branch.size();
648 uint8_t leaf_ver = (uint8_t)leaf.leaf_version;
649 tuples.push_back(std::make_tuple(depth, leaf_ver, leaf.script));
A reference to a CKey: the Hash160 of its serialized public key.
An encapsulated public key.
const unsigned char * end() const
static constexpr unsigned int COMPRESSED_SIZE
static constexpr unsigned int SIZE
secp256k1:
static bool ValidSize(const std::vector< unsigned char > &vch)
const unsigned char * begin() const
A hasher class for SHA-256.
void Finalize(unsigned char hash[OUTPUT_SIZE])
CSHA256 & Write(const unsigned char *data, size_t len)
Serialized script, used inside transaction inputs and outputs.
bool IsPushOnly(const_iterator pc) const
Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical).
bool IsPayToScriptHash() const
static int DecodeOP_N(opcodetype opcode)
Encode/decode small integers:
bool GetOp(const_iterator &pc, opcodetype &opcodeRet, std::vector< unsigned char > &vchRet) const
bool IsWitnessProgram(int &version, std::vector< unsigned char > &program) const
static opcodetype EncodeOP_N(int n)
A reference to a CScript: the Hash160 of its serialization (see script.h)
constexpr C * end() const noexcept
constexpr C * begin() const noexcept
Utility class to construct Taproot outputs from internal key and script tree.
WitnessV1Taproot GetOutput()
Compute scriptPubKey (after Finalize()).
static NodeInfo Combine(NodeInfo &&a, NodeInfo &&b)
Combine information about a parent Merkle tree node from its child nodes.
TaprootSpendData GetSpendData() const
Compute spending data (after Finalize()).
bool IsComplete() const
Return whether there were either no leaves, or the leaves form a Huffman tree.
static bool ValidDepths(const std::vector< int > &depths)
Check if a list of depths is legal (will lead to IsComplete()).
void Insert(NodeInfo &&node, int depth)
Insert information about a node at a certain depth, and propagate information up.
XOnlyPubKey m_internal_key
The internal key, set when finalizing.
XOnlyPubKey m_output_key
The output key, computed when finalizing.
bool IsValid() const
Return true if so far all input was valid.
TaprootBuilder & Add(int depth, Span< const unsigned char > script, int leaf_version, bool track=true)
Add a new script at a certain depth in the tree.
std::vector< std::optional< NodeInfo > > m_branch
The current state of the builder.
TaprootBuilder & AddOmitted(int depth, const uint256 &hash)
Like Add(), but for a Merkle node with a given hash to the tree.
TaprootBuilder & Finalize(const XOnlyPubKey &internal_key)
Finalize the construction.
bool m_parity
The tweak parity, computed when finalizing.
std::vector< std::tuple< uint8_t, uint8_t, std::vector< unsigned char > > > GetTreeTuples() const
Returns a vector of tuples representing the depth, leaf version, and script.
bool m_valid
Whether the builder is in a valid state so far.
bool IsNull() const
Test whether this is the 0 key (the result of default construction).
std::optional< std::pair< XOnlyPubKey, bool > > CreateTapTweak(const uint256 *merkle_root) const
Construct a Taproot tweaked output point with this point as internal key.
const unsigned char * begin() const
bool IsFullyValid() const
Determine if this pubkey is fully valid.
const unsigned char * end() const
constexpr bool IsNull() const
constexpr unsigned char * begin()
uint160 Hash160(const T1 &in1)
Compute the 160-bit hash an object.
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
uint256 ComputeTapleafHash(uint8_t leaf_version, Span< const unsigned char > script)
Compute the BIP341 tapleaf hash from leaf version & script.
uint256 ComputeTapbranchHash(Span< const unsigned char > a, Span< const unsigned char > b)
Compute the BIP341 tapbranch hash from two branches.
static constexpr size_t WITNESS_V0_KEYHASH_SIZE
static constexpr uint8_t TAPROOT_LEAF_MASK
static constexpr size_t WITNESS_V0_SCRIPTHASH_SIZE
Signature hash sizes.
static constexpr size_t TAPROOT_CONTROL_NODE_SIZE
static constexpr size_t WITNESS_V1_TAPROOT_SIZE
static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT
static constexpr size_t TAPROOT_CONTROL_MAX_SIZE
static constexpr size_t TAPROOT_CONTROL_BASE_SIZE
bool CheckMinimalPush(const std::vector< unsigned char > &data, opcodetype opcode)
std::vector< unsigned char > ToByteVector(const T &in)
opcodetype
Script opcodes.
static constexpr unsigned int MAX_PUBKEYS_PER_MULTI_A
The limit of keys in OP_CHECKSIGADD-based scripts.
static const int MAX_PUBKEYS_PER_MULTISIG
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,...
TxoutType Solver(const CScript &scriptPubKey, std::vector< std::vector< unsigned char >> &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
std::optional< std::pair< int, std::vector< Span< const unsigned char > > > > MatchMultiA(const CScript &script)
static bool MatchPayToPubkeyHash(const CScript &script, valtype &pubkeyhash)
static constexpr bool IsSmallInteger(opcodetype opcode)
Test for "small positive integer" script opcodes - OP_1 through OP_16.
CScript GetScriptForMultisig(int nRequired, const std::vector< CPubKey > &keys)
Generate a multisig script.
std::vector< unsigned char > valtype
bool ExtractDestination(const CScript &scriptPubKey, CTxDestination &addressRet)
Parse a standard scriptPubKey for the destination address.
std::string GetTxnOutputType(TxoutType t)
Get the name of a TxoutType as a string.
CScript GetScriptForRawPubKey(const CPubKey &pubKey)
Generate a P2PK script for the given pubkey.
std::optional< std::vector< std::tuple< int, std::vector< unsigned char >, int > > > InferTaprootTree(const TaprootSpendData &spenddata, const XOnlyPubKey &output)
Given a TaprootSpendData and the output key, reconstruct its script tree.
static bool MatchMultisig(const CScript &script, int &required_sigs, std::vector< valtype > &pubkeys)
static bool MatchPayToPubkey(const CScript &script, valtype &pubkey)
bool IsValidDestination(const CTxDestination &dest)
Check whether a CTxDestination is a CNoDestination.
CScript GetScriptForDestination(const CTxDestination &dest)
Generate a Bitcoin scriptPubKey for the given CTxDestination.
CKeyID ToKeyID(const PKHash &key_hash)
constexpr bool IsPushdataOp(opcodetype opcode)
@ WITNESS_UNKNOWN
Only for Witness versions not already defined above.
@ NULL_DATA
unspendable OP_RETURN script that carries data
std::variant< CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessV1Taproot, WitnessUnknown > CTxDestination
A txout script template with a specific destination.
Information about a tracked leaf in the Merkle tree.
Information associated with a node in the Merkle tree.
uint256 merkle_root
The Merkle root of the script tree (0 if no scripts).
std::map< std::pair< std::vector< unsigned char >, int >, std::set< std::vector< unsigned char >, ShortestVectorFirstComparator > > scripts
Map from (script, leaf_version) to (sets of) control blocks.
void Merge(TaprootSpendData other)
Merge other TaprootSpendData (for the same scriptPubKey) into this.
XOnlyPubKey internal_key
The BIP341 internal key.
CTxDestination subtype to encode any future Witness version.
unsigned char program[40]