Skip to content

Commit dbb0ce9

Browse files
sipasipa
committed
Add TaprootSpendData data structure, equivalent to script map for P2[W]SH
This data structures stores all information necessary for spending a taproot output (the internal key, the Merkle root, and the control blocks for every script leaf). It is added to signing providers, and populated by the tr() descriptor.
1 parent b0e5fbf commit dbb0ce9

File tree

6 files changed

+109
-7
lines changed

6 files changed

+109
-7
lines changed

‎src/pubkey.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -234,6 +234,10 @@ class XOnlyPubKey
234234
* fail. */
235235
bool IsFullyValid() const;
236236

237+
/** Test whether this is the 0 key (the result of default construction). This implies
238+
* !IsFullyValid(). */
239+
bool IsNull() const { return m_keydata.IsNull(); }
240+
237241
/** Construct an x-only pubkey from exactly 32 bytes. */
238242
explicit XOnlyPubKey(Span<const unsigned char> bytes);
239243

‎src/script/descriptor.cpp‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -843,7 +843,9 @@ class TRDescriptor final : public DescriptorImpl
843843
XOnlyPubKey xpk(keys[0]);
844844
if (!xpk.IsFullyValid()) return {};
845845
builder.Finalize(xpk);
846-
return Vector(GetScriptForDestination(builder.GetOutput()));
846+
WitnessV1Taproot output = builder.GetOutput();
847+
out.tr_spenddata[output].Merge(builder.GetSpendData());
848+
return Vector(GetScriptForDestination(output));
847849
}
848850
bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, bool priv, bool normalized) const override
849851
{

‎src/script/signingprovider.cpp‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,11 @@ bool HidingSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& inf
4444
return m_provider->GetKeyOrigin(keyid, info);
4545
}
4646

47+
bool HidingSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const
48+
{
49+
return m_provider->GetTaprootSpendData(output_key, spenddata);
50+
}
51+
4752
bool FlatSigningProvider::GetCScript(const CScriptID& scriptid, CScript& script) const { return LookupHelper(scripts, scriptid, script); }
4853
bool FlatSigningProvider::GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const { return LookupHelper(pubkeys, keyid, pubkey); }
4954
bool FlatSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const
@@ -54,6 +59,10 @@ bool FlatSigningProvider::GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info)
5459
return ret;
5560
}
5661
bool FlatSigningProvider::GetKey(const CKeyID& keyid, CKey& key) const { return LookupHelper(keys, keyid, key); }
62+
bool FlatSigningProvider::GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const
63+
{
64+
return LookupHelper(tr_spenddata, output_key, spenddata);
65+
}
5766

5867
FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvider& b)
5968
{
@@ -66,6 +75,10 @@ FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvide
6675
ret.keys.insert(b.keys.begin(), b.keys.end());
6776
ret.origins = a.origins;
6877
ret.origins.insert(b.origins.begin(), b.origins.end());
78+
ret.tr_spenddata = a.tr_spenddata;
79+
for (const auto& [output_key, spenddata] : b.tr_spenddata) {
80+
ret.tr_spenddata[output_key].Merge(spenddata);
81+
}
6982
return ret;
7083
}
7184

‎src/script/signingprovider.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ class SigningProvider
2525
virtual bool GetKey(const CKeyID &address, CKey& key) const { return false; }
2626
virtual bool HaveKey(const CKeyID &address) const { return false; }
2727
virtual bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const { return false; }
28+
virtual bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const { return false; }
2829
};
2930

3031
extern const SigningProvider& DUMMY_SIGNING_PROVIDER;
@@ -42,6 +43,7 @@ class HidingSigningProvider : public SigningProvider
4243
bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override;
4344
bool GetKey(const CKeyID& keyid, CKey& key) const override;
4445
bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override;
46+
bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override;
4547
};
4648

4749
struct FlatSigningProvider final : public SigningProvider
@@ -50,11 +52,13 @@ struct FlatSigningProvider final : public SigningProvider
5052
std::map<CKeyID, CPubKey> pubkeys;
5153
std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> origins;
5254
std::map<CKeyID, CKey> keys;
55+
std::map<XOnlyPubKey, TaprootSpendData> tr_spenddata; /** Map from output key to spend data. */
5356

5457
bool GetCScript(const CScriptID& scriptid, CScript& script) const override;
5558
bool GetPubKey(const CKeyID& keyid, CPubKey& pubkey) const override;
5659
bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const override;
5760
bool GetKey(const CKeyID& keyid, CKey& key) const override;
61+
bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const override;
5862
};
5963

6064
FlatSigningProvider Merge(const FlatSigningProvider& a, const FlatSigningProvider& b);

‎src/script/standard.cpp‎

Lines changed: 54 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -377,6 +377,16 @@ bool IsValidDestination(const CTxDestination& dest) {
377377
/*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b)
378378
{
379379
NodeInfo ret;
380+
/* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */
381+
for (auto& leaf : a.leaves) {
382+
leaf.merkle_branch.push_back(b.hash);
383+
ret.leaves.emplace_back(std::move(leaf));
384+
}
385+
/* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */
386+
for (auto& leaf : b.leaves) {
387+
leaf.merkle_branch.push_back(a.hash);
388+
ret.leaves.emplace_back(std::move(leaf));
389+
}
380390
/* Lexicographically sort a and b's hash, and compute parent hash. */
381391
if (a.hash < b.hash) {
382392
ret.hash = (CHashWriter(HASHER_TAPBRANCH) << a.hash << b.hash).GetSHA256();
@@ -386,6 +396,21 @@ bool IsValidDestination(const CTxDestination& dest) {
386396
return ret;
387397
}
388398

399+
void TaprootSpendData::Merge(TaprootSpendData other)
400+
{
401+
// TODO: figure out how to better deal with conflicting information
402+
// being merged.
403+
if (internal_key.IsNull() && !other.internal_key.IsNull()) {
404+
internal_key = other.internal_key;
405+
}
406+
if (merkle_root.IsNull() && !other.merkle_root.IsNull()) {
407+
merkle_root = other.merkle_root;
408+
}
409+
for (auto& [key, control_blocks] : other.scripts) {
410+
scripts[key].merge(std::move(control_blocks));
411+
}
412+
}
413+
389414
void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
390415
{
391416
assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
@@ -435,13 +460,14 @@ void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
435460
return branch.size() == 0 || (branch.size() == 1 && branch[0]);
436461
}
437462

438-
TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version)
463+
TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version, bool track)
439464
{
440465
assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
441466
if (!IsValid()) return *this;
442-
/* Construct NodeInfo object with leaf hash. */
467+
/* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
443468
NodeInfo node;
444469
node.hash = (CHashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256();
470+
if (track) node.leaves.emplace_back(LeafInfo{script, leaf_version, {}});
445471
/* Insert into the branch. */
446472
Insert(std::move(node), depth);
447473
return *this;
@@ -464,8 +490,33 @@ TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
464490
m_internal_key = internal_key;
465491
auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
466492
assert(ret.has_value());
467-
std::tie(m_output_key, std::ignore) = *ret;
493+
std::tie(m_output_key, m_parity) = *ret;
468494
return *this;
469495
}
470496

471497
WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; }
498+
499+
TaprootSpendData TaprootBuilder::GetSpendData() const
500+
{
501+
TaprootSpendData spd;
502+
spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash;
503+
spd.internal_key = m_internal_key;
504+
if (m_branch.size()) {
505+
// If any script paths exist, they have been combined into the root m_branch[0]
506+
// by now. Compute the control block for each of its tracked leaves, and put them in
507+
// spd.scripts.
508+
for (const auto& leaf : m_branch[0]->leaves) {
509+
std::vector<unsigned char> control_block;
510+
control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size());
511+
control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0);
512+
std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1);
513+
if (leaf.merkle_branch.size()) {
514+
std::copy(leaf.merkle_branch[0].begin(),
515+
leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(),
516+
control_block.begin() + TAPROOT_CONTROL_BASE_SIZE);
517+
}
518+
spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
519+
}
520+
}
521+
return spd;
522+
}

‎src/script/standard.h‎

Lines changed: 31 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@
1111
#include <uint256.h>
1212
#include <util/hash_type.h>
1313

14+
#include <map>
1415
#include <string>
1516
#include <variant>
1617

@@ -209,15 +210,38 @@ CScript GetScriptForRawPubKey(const CPubKey& pubkey);
209210
/** Generate a multisig script. */
210211
CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys);
211212

213+
struct TaprootSpendData
214+
{
215+
/** The BIP341 internal key. */
216+
XOnlyPubKey internal_key;
217+
/** The Merkle root of the script tree (0 if no scripts). */
218+
uint256 merkle_root;
219+
/** Map from (script, leaf_version) to (sets of) control blocks. */
220+
std::map<std::pair<CScript, int>, std::set<std::vector<unsigned char>>> scripts;
221+
/** Merge other TaprootSpendData (for the same scriptPubKey) into this. */
222+
void Merge(TaprootSpendData other);
223+
};
224+
212225
/** Utility class to construct Taproot outputs from internal key and script tree. */
213226
class TaprootBuilder
214227
{
215228
private:
229+
/** Information about a tracked leaf in the Merkle tree. */
230+
struct LeafInfo
231+
{
232+
CScript script; //!< The script.
233+
int leaf_version; //!< The leaf version for that script.
234+
std::vector<uint256> merkle_branch; //!< The hashing partners above this leaf.
235+
};
236+
216237
/** Information associated with a node in the Merkle tree. */
217238
struct NodeInfo
218239
{
219240
/** Merkle hash of this node. */
220241
uint256 hash;
242+
/** Tracked leaves underneath this node (either from the node itself, or its children).
243+
* The merkle_branch field for each is the partners to get to *this* node. */
244+
std::vector<LeafInfo> leaves;
221245
};
222246
/** Whether the builder is in a valid state so far. */
223247
bool m_valid = true;
@@ -260,7 +284,8 @@ class TaprootBuilder
260284
std::vector<std::optional<NodeInfo>> m_branch;
261285

262286
XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing.
263-
XOnlyPubKey m_output_key; //!< The output key, computed when finalizing. */
287+
XOnlyPubKey m_output_key; //!< The output key, computed when finalizing.
288+
bool m_parity; //!< The tweak parity, computed when finalizing.
264289

265290
/** Combine information about a parent Merkle tree node from its child nodes. */
266291
static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b);
@@ -269,8 +294,9 @@ class TaprootBuilder
269294

270295
public:
271296
/** Add a new script at a certain depth in the tree. Add() operations must be called
272-
* in depth-first traversal order of binary tree. */
273-
TaprootBuilder& Add(int depth, const CScript& script, int leaf_version);
297+
* in depth-first traversal order of binary tree. If track is true, it will be included in
298+
* the GetSpendData() output. */
299+
TaprootBuilder& Add(int depth, const CScript& script, int leaf_version, bool track = true);
274300
/** Like Add(), but for a Merkle node with a given hash to the tree. */
275301
TaprootBuilder& AddOmitted(int depth, const uint256& hash);
276302
/** Finalize the construction. Can only be called when IsComplete() is true.
@@ -285,6 +311,8 @@ class TaprootBuilder
285311
WitnessV1Taproot GetOutput();
286312
/** Check if a list of depths is legal (will lead to IsComplete()). */
287313
static bool ValidDepths(const std::vector<int>& depths);
314+
/** Compute spending data (after Finalize()). */
315+
TaprootSpendData GetSpendData() const;
288316
};
289317

290318
#endif // BITCOIN_SCRIPT_STANDARD_H

0 commit comments

Comments
 (0)