diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/psbt.cpp | 1 | ||||
| -rw-r--r-- | src/script/descriptor.cpp | 1 | ||||
| -rw-r--r-- | src/script/sign.h | 1 | ||||
| -rw-r--r-- | src/script/signingprovider.cpp | 295 | ||||
| -rw-r--r-- | src/script/signingprovider.h | 132 | ||||
| -rw-r--r-- | src/script/standard.cpp | 295 | ||||
| -rw-r--r-- | src/script/standard.h | 132 | ||||
| -rw-r--r-- | src/wallet/test/ismine_tests.cpp | 1 |
8 files changed, 431 insertions, 427 deletions
diff --git a/src/psbt.cpp b/src/psbt.cpp index 009ed966ed..7ec9b9c136 100644 --- a/src/psbt.cpp +++ b/src/psbt.cpp @@ -5,6 +5,7 @@ #include <psbt.h> #include <policy/policy.h> +#include <script/signingprovider.h> #include <util/check.h> #include <util/strencodings.h> diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp index 09ded5fc61..3d8497ef19 100644 --- a/src/script/descriptor.cpp +++ b/src/script/descriptor.cpp @@ -9,6 +9,7 @@ #include <pubkey.h> #include <script/miniscript.h> #include <script/script.h> +#include <script/signingprovider.h> #include <script/standard.h> #include <uint256.h> diff --git a/src/script/sign.h b/src/script/sign.h index f46bc55992..b8806876a2 100644 --- a/src/script/sign.h +++ b/src/script/sign.h @@ -13,6 +13,7 @@ #include <script/interpreter.h> #include <script/keyorigin.h> #include <script/standard.h> +#include <script/signingprovider.h> #include <uint256.h> class CKey; diff --git a/src/script/signingprovider.cpp b/src/script/signingprovider.cpp index fb5ae79c19..248305c82e 100644 --- a/src/script/signingprovider.cpp +++ b/src/script/signingprovider.cpp @@ -4,6 +4,7 @@ // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include <script/keyorigin.h> +#include <script/interpreter.h> #include <script/signingprovider.h> #include <script/standard.h> @@ -225,3 +226,297 @@ CKeyID GetKeyForDestination(const SigningProvider& store, const CTxDestination& } return CKeyID(); } +/*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b) +{ + NodeInfo ret; + /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */ + for (auto& leaf : a.leaves) { + leaf.merkle_branch.push_back(b.hash); + ret.leaves.emplace_back(std::move(leaf)); + } + /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */ + for (auto& leaf : b.leaves) { + leaf.merkle_branch.push_back(a.hash); + ret.leaves.emplace_back(std::move(leaf)); + } + ret.hash = ComputeTapbranchHash(a.hash, b.hash); + return ret; +} + +void TaprootSpendData::Merge(TaprootSpendData other) +{ + // TODO: figure out how to better deal with conflicting information + // being merged. + if (internal_key.IsNull() && !other.internal_key.IsNull()) { + internal_key = other.internal_key; + } + if (merkle_root.IsNull() && !other.merkle_root.IsNull()) { + merkle_root = other.merkle_root; + } + for (auto& [key, control_blocks] : other.scripts) { + scripts[key].merge(std::move(control_blocks)); + } +} + +void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth) +{ + assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT); + /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing + * so would mean the Add() invocations do not correspond to a DFS traversal of a + * binary tree. */ + if ((size_t)depth + 1 < m_branch.size()) { + m_valid = false; + return; + } + /* As long as an entry in the branch exists at the specified depth, combine it and propagate up. + * The 'node' variable is overwritten here with the newly combined node. */ + while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) { + node = Combine(std::move(node), std::move(*m_branch[depth])); + m_branch.pop_back(); + if (depth == 0) m_valid = false; /* Can't propagate further up than the root */ + --depth; + } + if (m_valid) { + /* Make sure the branch is big enough to place the new node. */ + if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1); + assert(!m_branch[depth].has_value()); + m_branch[depth] = std::move(node); + } +} + +/*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths) +{ + std::vector<bool> branch; + for (int depth : depths) { + // This inner loop corresponds to effectively the same logic on branch + // as what Insert() performs on the m_branch variable. Instead of + // storing a NodeInfo object, just remember whether or not there is one + // at that depth. + if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false; + if ((size_t)depth + 1 < branch.size()) return false; + while (branch.size() > (size_t)depth && branch[depth]) { + branch.pop_back(); + if (depth == 0) return false; + --depth; + } + if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1); + assert(!branch[depth]); + branch[depth] = true; + } + // And this check corresponds to the IsComplete() check on m_branch. + return branch.size() == 0 || (branch.size() == 1 && branch[0]); +} + +TaprootBuilder& TaprootBuilder::Add(int depth, Span<const unsigned char> script, int leaf_version, bool track) +{ + assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0); + if (!IsValid()) return *this; + /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */ + NodeInfo node; + node.hash = ComputeTapleafHash(leaf_version, script); + if (track) node.leaves.emplace_back(LeafInfo{std::vector<unsigned char>(script.begin(), script.end()), leaf_version, {}}); + /* Insert into the branch. */ + Insert(std::move(node), depth); + return *this; +} + +TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash) +{ + if (!IsValid()) return *this; + /* Construct NodeInfo object with the hash directly, and insert it into the branch. */ + NodeInfo node; + node.hash = hash; + Insert(std::move(node), depth); + return *this; +} + +TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key) +{ + /* Can only call this function when IsComplete() is true. */ + assert(IsComplete()); + m_internal_key = internal_key; + auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash); + assert(ret.has_value()); + std::tie(m_output_key, m_parity) = *ret; + return *this; +} + +WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; } + +TaprootSpendData TaprootBuilder::GetSpendData() const +{ + assert(IsComplete()); + assert(m_output_key.IsFullyValid()); + TaprootSpendData spd; + spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash; + spd.internal_key = m_internal_key; + if (m_branch.size()) { + // If any script paths exist, they have been combined into the root m_branch[0] + // by now. Compute the control block for each of its tracked leaves, and put them in + // spd.scripts. + for (const auto& leaf : m_branch[0]->leaves) { + std::vector<unsigned char> control_block; + control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size()); + control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0); + std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1); + if (leaf.merkle_branch.size()) { + std::copy(leaf.merkle_branch[0].begin(), + leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(), + control_block.begin() + TAPROOT_CONTROL_BASE_SIZE); + } + spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block)); + } + } + return spd; +} + +std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output) +{ + // Verify that the output matches the assumed Merkle root and internal key. + auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root); + if (!tweak || tweak->first != output) return std::nullopt; + // If the Merkle root is 0, the tree is empty, and we're done. + std::vector<std::tuple<int, std::vector<unsigned char>, int>> ret; + if (spenddata.merkle_root.IsNull()) return ret; + + /** Data structure to represent the nodes of the tree we're going to build. */ + struct TreeNode { + /** Hash of this node, if known; 0 otherwise. */ + uint256 hash; + /** The left and right subtrees (note that their order is irrelevant). */ + std::unique_ptr<TreeNode> sub[2]; + /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair. + * nullptr otherwise. */ + const std::pair<std::vector<unsigned char>, int>* leaf = nullptr; + /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */ + bool explored = false; + /** Whether or not this node is an inner node (unknown until explored = true). */ + bool inner; + /** Whether or not we have produced output for this subtree. */ + bool done = false; + }; + + // Build tree from the provided branches. + TreeNode root; + root.hash = spenddata.merkle_root; + for (const auto& [key, control_blocks] : spenddata.scripts) { + const auto& [script, leaf_ver] = key; + for (const auto& control : control_blocks) { + // Skip script records with nonsensical leaf version. + if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue; + // Skip script records with invalid control block sizes. + if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || + ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue; + // Skip script records that don't match the control block. + if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue; + // Skip script records that don't match the provided Merkle root. + const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script); + const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash); + if (merkle_root != spenddata.merkle_root) continue; + + TreeNode* node = &root; + size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE; + for (size_t depth = 0; depth < levels; ++depth) { + // Can't descend into a node which we already know is a leaf. + if (node->explored && !node->inner) return std::nullopt; + + // Extract partner hash from Merkle branch in control block. + uint256 hash; + std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE, + control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE, + hash.begin()); + + if (node->sub[0]) { + // Descend into the existing left or right branch. + bool desc = false; + for (int i = 0; i < 2; ++i) { + if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) { + node->sub[i]->hash = hash; + node = &*node->sub[1-i]; + desc = true; + break; + } + } + if (!desc) return std::nullopt; // This probably requires a hash collision to hit. + } else { + // We're in an unexplored node. Create subtrees and descend. + node->explored = true; + node->inner = true; + node->sub[0] = std::make_unique<TreeNode>(); + node->sub[1] = std::make_unique<TreeNode>(); + node->sub[1]->hash = hash; + node = &*node->sub[0]; + } + } + // Cannot turn a known inner node into a leaf. + if (node->sub[0]) return std::nullopt; + node->explored = true; + node->inner = false; + node->leaf = &key; + node->hash = leaf_hash; + } + } + + // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid + // overflowing the call stack (the tree may be 128 levels deep). + std::vector<TreeNode*> stack{&root}; + while (!stack.empty()) { + TreeNode& node = *stack.back(); + if (!node.explored) { + // Unexplored node, which means the tree is incomplete. + return std::nullopt; + } else if (!node.inner) { + // Leaf node; produce output. + ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second); + node.done = true; + stack.pop_back(); + } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() && + ComputeTapbranchHash(node.sub[1]->hash, node.sub[1]->hash) == node.hash) { + // Whenever there are nodes with two identical subtrees under it, we run into a problem: + // the control blocks for the leaves underneath those will be identical as well, and thus + // they will all be matched to the same path in the tree. The result is that at the location + // where the duplicate occurred, the left child will contain a normal tree that can be explored + // and processed, but the right one will remain unexplored. + // + // This situation can be detected, by encountering an inner node with unexplored right subtree + // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash. + // + // To deal with this, simply process the left tree a second time (set its done flag to false; + // noting that the done flag of its children have already been set to false after processing + // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored) + // subtree to true. + node.sub[0]->done = false; + node.sub[1]->done = true; + } else if (node.sub[0]->done && node.sub[1]->done) { + // An internal node which we're finished with. + node.sub[0]->done = false; + node.sub[1]->done = false; + node.done = true; + stack.pop_back(); + } else if (!node.sub[0]->done) { + // An internal node whose left branch hasn't been processed yet. Do so first. + stack.push_back(&*node.sub[0]); + } else if (!node.sub[1]->done) { + // An internal node whose right branch hasn't been processed yet. Do so first. + stack.push_back(&*node.sub[1]); + } + } + + return ret; +} + +std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> TaprootBuilder::GetTreeTuples() const +{ + assert(IsComplete()); + std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> tuples; + if (m_branch.size()) { + const auto& leaves = m_branch[0]->leaves; + for (const auto& leaf : leaves) { + assert(leaf.merkle_branch.size() <= TAPROOT_CONTROL_MAX_NODE_COUNT); + uint8_t depth = (uint8_t)leaf.merkle_branch.size(); + uint8_t leaf_ver = (uint8_t)leaf.leaf_version; + tuples.push_back(std::make_tuple(depth, leaf_ver, leaf.script)); + } + } + return tuples; +} diff --git a/src/script/signingprovider.h b/src/script/signingprovider.h index a5bbcff6a0..26886e0d57 100644 --- a/src/script/signingprovider.h +++ b/src/script/signingprovider.h @@ -14,6 +14,138 @@ #include <script/standard.h> #include <sync.h> +struct ShortestVectorFirstComparator +{ + bool operator()(const std::vector<unsigned char>& a, const std::vector<unsigned char>& b) const + { + if (a.size() < b.size()) return true; + if (a.size() > b.size()) return false; + return a < b; + } +}; + +struct TaprootSpendData +{ + /** The BIP341 internal key. */ + XOnlyPubKey internal_key; + /** The Merkle root of the script tree (0 if no scripts). */ + uint256 merkle_root; + /** Map from (script, leaf_version) to (sets of) control blocks. + * More than one control block for a given script is only possible if it + * appears in multiple branches of the tree. We keep them all so that + * inference can reconstruct the full tree. Within each set, the control + * blocks are sorted by size, so that the signing logic can easily + * prefer the cheapest one. */ + std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts; + /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */ + void Merge(TaprootSpendData other); +}; + +/** Utility class to construct Taproot outputs from internal key and script tree. */ +class TaprootBuilder +{ +private: + /** Information about a tracked leaf in the Merkle tree. */ + struct LeafInfo + { + std::vector<unsigned char> script; //!< The script. + int leaf_version; //!< The leaf version for that script. + std::vector<uint256> merkle_branch; //!< The hashing partners above this leaf. + }; + + /** Information associated with a node in the Merkle tree. */ + struct NodeInfo + { + /** Merkle hash of this node. */ + uint256 hash; + /** Tracked leaves underneath this node (either from the node itself, or its children). + * The merkle_branch field of each is the partners to get to *this* node. */ + std::vector<LeafInfo> leaves; + }; + /** Whether the builder is in a valid state so far. */ + bool m_valid = true; + + /** The current state of the builder. + * + * For each level in the tree, one NodeInfo object may be present. m_branch[0] + * is information about the root; further values are for deeper subtrees being + * explored. + * + * For every right branch taken to reach the position we're currently + * working in, there will be a (non-nullopt) entry in m_branch corresponding + * to the left branch at that level. + * + * For example, imagine this tree: - N0 - + * / \ + * N1 N2 + * / \ / \ + * A B C N3 + * / \ + * D E + * + * Initially, m_branch is empty. After processing leaf A, it would become + * {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already + * exists, and it would thus be combined with it to produce a level 1 one, + * resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C} + * and {nullopt, N1, C, D} respectively. When E is processed, it is combined + * with D, and then C, and then N1, to produce the root, resulting in {N0}. + * + * This structure allows processing with just O(log n) overhead if the leaves + * are computed on the fly. + * + * As an invariant, there can never be nullopt entries at the end. There can + * also not be more than 128 entries (as that would mean more than 128 levels + * in the tree). The depth of newly added entries will always be at least + * equal to the current size of m_branch (otherwise it does not correspond + * to a depth-first traversal of a tree). m_branch is only empty if no entries + * have ever be processed. m_branch having length 1 corresponds to being done. + */ + std::vector<std::optional<NodeInfo>> m_branch; + + XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing. + XOnlyPubKey m_output_key; //!< The output key, computed when finalizing. + bool m_parity; //!< The tweak parity, computed when finalizing. + + /** Combine information about a parent Merkle tree node from its child nodes. */ + static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b); + /** Insert information about a node at a certain depth, and propagate information up. */ + void Insert(NodeInfo&& node, int depth); + +public: + /** Add a new script at a certain depth in the tree. Add() operations must be called + * in depth-first traversal order of binary tree. If track is true, it will be included in + * the GetSpendData() output. */ + TaprootBuilder& Add(int depth, Span<const unsigned char> script, int leaf_version, bool track = true); + /** Like Add(), but for a Merkle node with a given hash to the tree. */ + TaprootBuilder& AddOmitted(int depth, const uint256& hash); + /** Finalize the construction. Can only be called when IsComplete() is true. + internal_key.IsFullyValid() must be true. */ + TaprootBuilder& Finalize(const XOnlyPubKey& internal_key); + + /** Return true if so far all input was valid. */ + bool IsValid() const { return m_valid; } + /** Return whether there were either no leaves, or the leaves form a Huffman tree. */ + bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); } + /** Compute scriptPubKey (after Finalize()). */ + WitnessV1Taproot GetOutput(); + /** Check if a list of depths is legal (will lead to IsComplete()). */ + static bool ValidDepths(const std::vector<int>& depths); + /** Compute spending data (after Finalize()). */ + TaprootSpendData GetSpendData() const; + /** Returns a vector of tuples representing the depth, leaf version, and script */ + std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> GetTreeTuples() const; + /** Returns true if there are any tapscripts */ + bool HasScripts() const { return !m_branch.empty(); } +}; + +/** Given a TaprootSpendData and the output key, reconstruct its script tree. + * + * If the output doesn't match the spenddata, or if the data in spenddata is incomplete, + * std::nullopt is returned. Otherwise, a vector of (depth, script, leaf_ver) tuples is + * returned, corresponding to a depth-first traversal of the script tree. + */ +std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output); + /** An interface to be implemented by keystores that support signing. */ class SigningProvider { diff --git a/src/script/standard.cpp b/src/script/standard.cpp index 6f5145a74b..01b074e27c 100644 --- a/src/script/standard.cpp +++ b/src/script/standard.cpp @@ -358,298 +358,3 @@ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys) bool IsValidDestination(const CTxDestination& dest) { return dest.index() != 0; } - -/*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b) -{ - NodeInfo ret; - /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */ - for (auto& leaf : a.leaves) { - leaf.merkle_branch.push_back(b.hash); - ret.leaves.emplace_back(std::move(leaf)); - } - /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */ - for (auto& leaf : b.leaves) { - leaf.merkle_branch.push_back(a.hash); - ret.leaves.emplace_back(std::move(leaf)); - } - ret.hash = ComputeTapbranchHash(a.hash, b.hash); - return ret; -} - -void TaprootSpendData::Merge(TaprootSpendData other) -{ - // TODO: figure out how to better deal with conflicting information - // being merged. - if (internal_key.IsNull() && !other.internal_key.IsNull()) { - internal_key = other.internal_key; - } - if (merkle_root.IsNull() && !other.merkle_root.IsNull()) { - merkle_root = other.merkle_root; - } - for (auto& [key, control_blocks] : other.scripts) { - scripts[key].merge(std::move(control_blocks)); - } -} - -void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth) -{ - assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT); - /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing - * so would mean the Add() invocations do not correspond to a DFS traversal of a - * binary tree. */ - if ((size_t)depth + 1 < m_branch.size()) { - m_valid = false; - return; - } - /* As long as an entry in the branch exists at the specified depth, combine it and propagate up. - * The 'node' variable is overwritten here with the newly combined node. */ - while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) { - node = Combine(std::move(node), std::move(*m_branch[depth])); - m_branch.pop_back(); - if (depth == 0) m_valid = false; /* Can't propagate further up than the root */ - --depth; - } - if (m_valid) { - /* Make sure the branch is big enough to place the new node. */ - if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1); - assert(!m_branch[depth].has_value()); - m_branch[depth] = std::move(node); - } -} - -/*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths) -{ - std::vector<bool> branch; - for (int depth : depths) { - // This inner loop corresponds to effectively the same logic on branch - // as what Insert() performs on the m_branch variable. Instead of - // storing a NodeInfo object, just remember whether or not there is one - // at that depth. - if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false; - if ((size_t)depth + 1 < branch.size()) return false; - while (branch.size() > (size_t)depth && branch[depth]) { - branch.pop_back(); - if (depth == 0) return false; - --depth; - } - if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1); - assert(!branch[depth]); - branch[depth] = true; - } - // And this check corresponds to the IsComplete() check on m_branch. - return branch.size() == 0 || (branch.size() == 1 && branch[0]); -} - -TaprootBuilder& TaprootBuilder::Add(int depth, Span<const unsigned char> script, int leaf_version, bool track) -{ - assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0); - if (!IsValid()) return *this; - /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */ - NodeInfo node; - node.hash = ComputeTapleafHash(leaf_version, script); - if (track) node.leaves.emplace_back(LeafInfo{std::vector<unsigned char>(script.begin(), script.end()), leaf_version, {}}); - /* Insert into the branch. */ - Insert(std::move(node), depth); - return *this; -} - -TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash) -{ - if (!IsValid()) return *this; - /* Construct NodeInfo object with the hash directly, and insert it into the branch. */ - NodeInfo node; - node.hash = hash; - Insert(std::move(node), depth); - return *this; -} - -TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key) -{ - /* Can only call this function when IsComplete() is true. */ - assert(IsComplete()); - m_internal_key = internal_key; - auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash); - assert(ret.has_value()); - std::tie(m_output_key, m_parity) = *ret; - return *this; -} - -WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; } - -TaprootSpendData TaprootBuilder::GetSpendData() const -{ - assert(IsComplete()); - assert(m_output_key.IsFullyValid()); - TaprootSpendData spd; - spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash; - spd.internal_key = m_internal_key; - if (m_branch.size()) { - // If any script paths exist, they have been combined into the root m_branch[0] - // by now. Compute the control block for each of its tracked leaves, and put them in - // spd.scripts. - for (const auto& leaf : m_branch[0]->leaves) { - std::vector<unsigned char> control_block; - control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size()); - control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0); - std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1); - if (leaf.merkle_branch.size()) { - std::copy(leaf.merkle_branch[0].begin(), - leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(), - control_block.begin() + TAPROOT_CONTROL_BASE_SIZE); - } - spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block)); - } - } - return spd; -} - -std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output) -{ - // Verify that the output matches the assumed Merkle root and internal key. - auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root); - if (!tweak || tweak->first != output) return std::nullopt; - // If the Merkle root is 0, the tree is empty, and we're done. - std::vector<std::tuple<int, std::vector<unsigned char>, int>> ret; - if (spenddata.merkle_root.IsNull()) return ret; - - /** Data structure to represent the nodes of the tree we're going to build. */ - struct TreeNode { - /** Hash of this node, if known; 0 otherwise. */ - uint256 hash; - /** The left and right subtrees (note that their order is irrelevant). */ - std::unique_ptr<TreeNode> sub[2]; - /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair. - * nullptr otherwise. */ - const std::pair<std::vector<unsigned char>, int>* leaf = nullptr; - /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */ - bool explored = false; - /** Whether or not this node is an inner node (unknown until explored = true). */ - bool inner; - /** Whether or not we have produced output for this subtree. */ - bool done = false; - }; - - // Build tree from the provided branches. - TreeNode root; - root.hash = spenddata.merkle_root; - for (const auto& [key, control_blocks] : spenddata.scripts) { - const auto& [script, leaf_ver] = key; - for (const auto& control : control_blocks) { - // Skip script records with nonsensical leaf version. - if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue; - // Skip script records with invalid control block sizes. - if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || - ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue; - // Skip script records that don't match the control block. - if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue; - // Skip script records that don't match the provided Merkle root. - const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script); - const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash); - if (merkle_root != spenddata.merkle_root) continue; - - TreeNode* node = &root; - size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE; - for (size_t depth = 0; depth < levels; ++depth) { - // Can't descend into a node which we already know is a leaf. - if (node->explored && !node->inner) return std::nullopt; - - // Extract partner hash from Merkle branch in control block. - uint256 hash; - std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE, - control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE, - hash.begin()); - - if (node->sub[0]) { - // Descend into the existing left or right branch. - bool desc = false; - for (int i = 0; i < 2; ++i) { - if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) { - node->sub[i]->hash = hash; - node = &*node->sub[1-i]; - desc = true; - break; - } - } - if (!desc) return std::nullopt; // This probably requires a hash collision to hit. - } else { - // We're in an unexplored node. Create subtrees and descend. - node->explored = true; - node->inner = true; - node->sub[0] = std::make_unique<TreeNode>(); - node->sub[1] = std::make_unique<TreeNode>(); - node->sub[1]->hash = hash; - node = &*node->sub[0]; - } - } - // Cannot turn a known inner node into a leaf. - if (node->sub[0]) return std::nullopt; - node->explored = true; - node->inner = false; - node->leaf = &key; - node->hash = leaf_hash; - } - } - - // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid - // overflowing the call stack (the tree may be 128 levels deep). - std::vector<TreeNode*> stack{&root}; - while (!stack.empty()) { - TreeNode& node = *stack.back(); - if (!node.explored) { - // Unexplored node, which means the tree is incomplete. - return std::nullopt; - } else if (!node.inner) { - // Leaf node; produce output. - ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second); - node.done = true; - stack.pop_back(); - } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() && - ComputeTapbranchHash(node.sub[1]->hash, node.sub[1]->hash) == node.hash) { - // Whenever there are nodes with two identical subtrees under it, we run into a problem: - // the control blocks for the leaves underneath those will be identical as well, and thus - // they will all be matched to the same path in the tree. The result is that at the location - // where the duplicate occurred, the left child will contain a normal tree that can be explored - // and processed, but the right one will remain unexplored. - // - // This situation can be detected, by encountering an inner node with unexplored right subtree - // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash. - // - // To deal with this, simply process the left tree a second time (set its done flag to false; - // noting that the done flag of its children have already been set to false after processing - // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored) - // subtree to true. - node.sub[0]->done = false; - node.sub[1]->done = true; - } else if (node.sub[0]->done && node.sub[1]->done) { - // An internal node which we're finished with. - node.sub[0]->done = false; - node.sub[1]->done = false; - node.done = true; - stack.pop_back(); - } else if (!node.sub[0]->done) { - // An internal node whose left branch hasn't been processed yet. Do so first. - stack.push_back(&*node.sub[0]); - } else if (!node.sub[1]->done) { - // An internal node whose right branch hasn't been processed yet. Do so first. - stack.push_back(&*node.sub[1]); - } - } - - return ret; -} - -std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> TaprootBuilder::GetTreeTuples() const -{ - assert(IsComplete()); - std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> tuples; - if (m_branch.size()) { - const auto& leaves = m_branch[0]->leaves; - for (const auto& leaf : leaves) { - assert(leaf.merkle_branch.size() <= TAPROOT_CONTROL_MAX_NODE_COUNT); - uint8_t depth = (uint8_t)leaf.merkle_branch.size(); - uint8_t leaf_ver = (uint8_t)leaf.leaf_version; - tuples.push_back(std::make_tuple(depth, leaf_ver, leaf.script)); - } - } - return tuples; -} diff --git a/src/script/standard.h b/src/script/standard.h index 8a76606082..9555cc2b61 100644 --- a/src/script/standard.h +++ b/src/script/standard.h @@ -175,136 +175,4 @@ std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMulti /** Generate a multisig script. */ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys); -struct ShortestVectorFirstComparator -{ - bool operator()(const std::vector<unsigned char>& a, const std::vector<unsigned char>& b) const - { - if (a.size() < b.size()) return true; - if (a.size() > b.size()) return false; - return a < b; - } -}; - -struct TaprootSpendData -{ - /** The BIP341 internal key. */ - XOnlyPubKey internal_key; - /** The Merkle root of the script tree (0 if no scripts). */ - uint256 merkle_root; - /** Map from (script, leaf_version) to (sets of) control blocks. - * More than one control block for a given script is only possible if it - * appears in multiple branches of the tree. We keep them all so that - * inference can reconstruct the full tree. Within each set, the control - * blocks are sorted by size, so that the signing logic can easily - * prefer the cheapest one. */ - std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts; - /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */ - void Merge(TaprootSpendData other); -}; - -/** Utility class to construct Taproot outputs from internal key and script tree. */ -class TaprootBuilder -{ -private: - /** Information about a tracked leaf in the Merkle tree. */ - struct LeafInfo - { - std::vector<unsigned char> script; //!< The script. - int leaf_version; //!< The leaf version for that script. - std::vector<uint256> merkle_branch; //!< The hashing partners above this leaf. - }; - - /** Information associated with a node in the Merkle tree. */ - struct NodeInfo - { - /** Merkle hash of this node. */ - uint256 hash; - /** Tracked leaves underneath this node (either from the node itself, or its children). - * The merkle_branch field of each is the partners to get to *this* node. */ - std::vector<LeafInfo> leaves; - }; - /** Whether the builder is in a valid state so far. */ - bool m_valid = true; - - /** The current state of the builder. - * - * For each level in the tree, one NodeInfo object may be present. m_branch[0] - * is information about the root; further values are for deeper subtrees being - * explored. - * - * For every right branch taken to reach the position we're currently - * working in, there will be a (non-nullopt) entry in m_branch corresponding - * to the left branch at that level. - * - * For example, imagine this tree: - N0 - - * / \ - * N1 N2 - * / \ / \ - * A B C N3 - * / \ - * D E - * - * Initially, m_branch is empty. After processing leaf A, it would become - * {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already - * exists, and it would thus be combined with it to produce a level 1 one, - * resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C} - * and {nullopt, N1, C, D} respectively. When E is processed, it is combined - * with D, and then C, and then N1, to produce the root, resulting in {N0}. - * - * This structure allows processing with just O(log n) overhead if the leaves - * are computed on the fly. - * - * As an invariant, there can never be nullopt entries at the end. There can - * also not be more than 128 entries (as that would mean more than 128 levels - * in the tree). The depth of newly added entries will always be at least - * equal to the current size of m_branch (otherwise it does not correspond - * to a depth-first traversal of a tree). m_branch is only empty if no entries - * have ever be processed. m_branch having length 1 corresponds to being done. - */ - std::vector<std::optional<NodeInfo>> m_branch; - - XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing. - XOnlyPubKey m_output_key; //!< The output key, computed when finalizing. - bool m_parity; //!< The tweak parity, computed when finalizing. - - /** Combine information about a parent Merkle tree node from its child nodes. */ - static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b); - /** Insert information about a node at a certain depth, and propagate information up. */ - void Insert(NodeInfo&& node, int depth); - -public: - /** Add a new script at a certain depth in the tree. Add() operations must be called - * in depth-first traversal order of binary tree. If track is true, it will be included in - * the GetSpendData() output. */ - TaprootBuilder& Add(int depth, Span<const unsigned char> script, int leaf_version, bool track = true); - /** Like Add(), but for a Merkle node with a given hash to the tree. */ - TaprootBuilder& AddOmitted(int depth, const uint256& hash); - /** Finalize the construction. Can only be called when IsComplete() is true. - internal_key.IsFullyValid() must be true. */ - TaprootBuilder& Finalize(const XOnlyPubKey& internal_key); - - /** Return true if so far all input was valid. */ - bool IsValid() const { return m_valid; } - /** Return whether there were either no leaves, or the leaves form a Huffman tree. */ - bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); } - /** Compute scriptPubKey (after Finalize()). */ - WitnessV1Taproot GetOutput(); - /** Check if a list of depths is legal (will lead to IsComplete()). */ - static bool ValidDepths(const std::vector<int>& depths); - /** Compute spending data (after Finalize()). */ - TaprootSpendData GetSpendData() const; - /** Returns a vector of tuples representing the depth, leaf version, and script */ - std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> GetTreeTuples() const; - /** Returns true if there are any tapscripts */ - bool HasScripts() const { return !m_branch.empty(); } -}; - -/** Given a TaprootSpendData and the output key, reconstruct its script tree. - * - * If the output doesn't match the spenddata, or if the data in spenddata is incomplete, - * std::nullopt is returned. Otherwise, a vector of (depth, script, leaf_ver) tuples is - * returned, corresponding to a depth-first traversal of the script tree. - */ -std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output); - #endif // BITCOIN_SCRIPT_STANDARD_H diff --git a/src/wallet/test/ismine_tests.cpp b/src/wallet/test/ismine_tests.cpp index fd0718fbb9..8fdfaf946e 100644 --- a/src/wallet/test/ismine_tests.cpp +++ b/src/wallet/test/ismine_tests.cpp @@ -6,6 +6,7 @@ #include <key_io.h> #include <node/context.h> #include <script/script.h> +#include <script/signingprovider.h> #include <script/standard.h> #include <test/util/setup_common.h> #include <wallet/types.h> |