descriptors: taproot partial descriptors

Eunovo commented at 11:53 am on June 7, 2024: contributor

This PR adds support for rawnode() and rawleaf() under tr() descriptor discussed in #24114 and tr-rawnode-and-rawleaf

DrahtBot commented at 11:53 am on June 7, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/30243.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29136 (wallet: addhdkey RPC to add just keys to wallets via new void(KEY) descriptor by achow101)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

Eunovo marked this as a draft on Jun 7, 2024

Eunovo force-pushed on Jun 7, 2024

DrahtBot added the label CI failed on Jun 7, 2024

DrahtBot commented at 3:07 pm on June 7, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/25939869075

Eunovo marked this as ready for review on Jun 7, 2024

DrahtBot removed the label CI failed on Jun 7, 2024

in src/script/descriptor.cpp:1116 in 62541c8f4b outdated

1115+        assert(m_nodes.size() == scripts.size());
1116+        for (size_t pos = 0; pos < m_nodes.size(); ++pos) {
1117+            if (m_nodes[pos].type == TRNodeType::NODE_HASH) {
1118+                builder.AddOmitted(m_nodes[pos].depth, uint256(Span(scripts[pos])));
1119+            } else if (m_nodes[pos].type == TRNodeType::LEAF_SCRIPT) {
1120+                builder.Add(m_nodes[pos].depth, scripts[pos], m_nodes[pos].leaf_version.value());

ajtowns commented at 5:01 am on June 11, 2024:

Having an optional when in one branch you ignore the value and in the other you assume it always has a value doesn’t make a lot of sense to me.

Would it make sense to drop leaf_version from TRNodeInfo and store the leaf version as the first byte of the script? Alternatively, could just drop the optional and default it to 0.

Eunovo commented at 11:47 am on June 11, 2024:

Having an optional when in one branch you ignore the value and in the other you assume it always has a value doesn’t make a lot of sense to me.

Would it make sense to drop leaf_version from TRNodeInfo and store the leaf version as the first byte of the script? Alternatively, could just drop the optional and default it to 0. @ajtowns I prefer to drop the optional and default leaf_version to 0

ajtowns commented at 5:11 am on June 11, 2024: contributor

Seems okay to me. Presumably should update doc/descriptors.md though, and might also be nice to have some functional tests demonstrating it works end-to-end? (Add some examples to DESCS in wallet_miniscript.py maybe?

Eunovo commented at 11:45 am on June 11, 2024: contributor

Seems okay to me. Presumably should update doc/descriptors.md though, and might also be nice to have some functional tests demonstrating it works end-to-end? (Add some examples to DESCS in wallet_miniscript.py maybe? @ajtowns I’ll do that.

Eunovo force-pushed on Jun 11, 2024

Eunovo commented at 9:36 pm on June 11, 2024: contributor

@ajtowns Thanks for the review. I added some examples to wallet_miniscript.py and updated descriptors.md

dergoegge commented at 9:22 am on June 15, 2024: member

Found a crash in the mocked_descriptor_parse fuzz target, to reproduce:

0$ echo "dHIoJUJELHJhd2xlYWYoQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCLEE3LCUyNywlQjcsJTIzLCVCZCwlRkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQmNGKSk=" | base64 --decode > pr30243-mocked_descriptor_parse.crash
1$ FUZZ=mocked_descriptor_parse src/test/fuzz/fuzz pr30243-mocked_descriptor_parse.crash
2fuzz: script/signingprovider.cpp:368: TaprootBuilder &TaprootBuilder::Add(int, Span<const unsigned char>, int, bool): Assertion `(leaf_version & ~TAPROOT_LEAF_MASK) == 0' failed.

Eunovo commented at 9:49 am on June 15, 2024: contributor

Found a crash in the mocked_descriptor_parse fuzz target, to reproduce:

Thanks for this @dergoegge. I’ll fix it

Eunovo commented at 1:04 pm on June 18, 2024: contributor

Found a crash in the mocked_descriptor_parse fuzz target, to reproduce:

0$ echo "dHIoJUJELHJhd2xlYWYoQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCLEE3LCUyNywlQjcsJTIzLCVCZCwlRkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQmNGKSk=" | base64 --decode > pr30243-mocked_descriptor_parse.crash
1$ FUZZ=mocked_descriptor_parse src/test/fuzz/fuzz pr30243-mocked_descriptor_parse.crash
2fuzz: script/signingprovider.cpp:368: TaprootBuilder &TaprootBuilder::Add(int, Span<const unsigned char>, int, bool): Assertion `(leaf_version & ~TAPROOT_LEAF_MASK) == 0' failed.

@dergoegge Pushed https://github.com/bitcoin/bitcoin/pull/30243/commits/7efb115fd10584157d3ad752fee7e8ee4d267b02 to fix this

DrahtBot added the label CI failed on Jun 28, 2024

DrahtBot removed the label CI failed on Jul 2, 2024

in src/script/descriptor.cpp:2222 in 6908349fa5 outdated

1941+        if (leaf_version->size() > 1) {
1942+            error = "Leaf Version is too large";
1943+            return nullptr;
1944+        }
1945+        if (leaf_version->size() == 0) {
1946+            error = "Expected Leaf Version but not provided";

brunoerg commented at 1:21 pm on July 4, 2024:

In 6908349fa559c16164c76fff2f140a39f52279e2 “descriptor: Implement rawleaf(() partial descriptor”: Please correct me if I’m wrong, but is this check needed? If the expected leaf version is not provided, won’t it be verified before (in if (!Const(",", expr))?.

Eunovo commented at 8:46 pm on July 4, 2024:

Thanks for the review @brunoerg. I pushed https://github.com/bitcoin/bitcoin/pull/30243/commits/abe28609c0c7124c8ecf3f09adb537e3b642d50c which adds a test that triggers this error

brunoerg commented at 8:47 pm on July 4, 2024:

Cool

Eunovo requested review from ajtowns on Jul 8, 2024

Eunovo requested review from brunoerg on Jul 8, 2024

in src/test/descriptor_tests.cpp:646 in abe28609c0 outdated

642@@ -643,6 +643,25 @@ BOOST_AUTO_TEST_CASE(descriptor_test)
643     Check("tr(a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,{and_v(and_v(v:hash256(ae253ca2a54debcac7ecf414f6734f48c56421a08bb59182ff9f39a6fffdb588),v:pk(KykUPmR5967F4URzMUeCv9kNMU9CNRWycrPmx3ZvfkWoQLabbimL)),older(42)),multi_a(2,adf586a32ad4b0674a86022b000348b681b4c97a811f67eefe4a6e066e55080c,KztMyyi1pXUtuZfJSB7JzVdmJMAz7wfGVFoSRUR5CVZxXxULXuGR)})", "tr(a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,{and_v(and_v(v:hash256(ae253ca2a54debcac7ecf414f6734f48c56421a08bb59182ff9f39a6fffdb588),v:pk(1c9bc926084382e76da33b5a52d17b1fa153c072aae5fb5228ecc2ccf89d79d5)),older(42)),multi_a(2,adf586a32ad4b0674a86022b000348b681b4c97a811f67eefe4a6e066e55080c,14fa4ad085cdee1e2fc73d491b36a96c192382b1d9a21108eb3533f630364f9f)})", "tr(a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,{and_v(and_v(v:hash256(ae253ca2a54debcac7ecf414f6734f48c56421a08bb59182ff9f39a6fffdb588),v:pk(1c9bc926084382e76da33b5a52d17b1fa153c072aae5fb5228ecc2ccf89d79d5)),older(42)),multi_a(2,adf586a32ad4b0674a86022b000348b681b4c97a811f67eefe4a6e066e55080c,14fa4ad085cdee1e2fc73d491b36a96c192382b1d9a21108eb3533f630364f9f)})", MISSING_PRIVKEYS | XONLY_KEYS | SIGNABLE | SIGNABLE_FAILS, {{"51209a3d79db56fbe3ba4d905d827b62e1ed31cd6df1198b8c759d589c0f4efc27bd"}}, OutputType::BECH32M);
644     Check("tr(a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,{and_v(and_v(v:hash256(ae253ca2a54debcac7ecf414f6734f48c56421a08bb59182ff9f39a6fffdb588),v:pk(KykUPmR5967F4URzMUeCv9kNMU9CNRWycrPmx3ZvfkWoQLabbimL)),older(42)),multi_a(2,adf586a32ad4b0674a86022b000348b681b4c97a811f67eefe4a6e066e55080c,KztMyyi1pXUtuZfJSB7JzVdmJMAz7wfGVFoSRUR5CVZxXxULXuGR)})", "tr(a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,{and_v(and_v(v:hash256(ae253ca2a54debcac7ecf414f6734f48c56421a08bb59182ff9f39a6fffdb588),v:pk(1c9bc926084382e76da33b5a52d17b1fa153c072aae5fb5228ecc2ccf89d79d5)),older(42)),multi_a(2,adf586a32ad4b0674a86022b000348b681b4c97a811f67eefe4a6e066e55080c,14fa4ad085cdee1e2fc73d491b36a96c192382b1d9a21108eb3533f630364f9f)})", "tr(a34b99f22c790c4e36b2b3c2c35a36db06226e41c692fc82b8b56ac1c540c5bd,{and_v(and_v(v:hash256(ae253ca2a54debcac7ecf414f6734f48c56421a08bb59182ff9f39a6fffdb588),v:pk(1c9bc926084382e76da33b5a52d17b1fa153c072aae5fb5228ecc2ccf89d79d5)),older(42)),multi_a(2,adf586a32ad4b0674a86022b000348b681b4c97a811f67eefe4a6e066e55080c,14fa4ad085cdee1e2fc73d491b36a96c192382b1d9a21108eb3533f630364f9f)})", MISSING_PRIVKEYS | XONLY_KEYS | SIGNABLE, {{"51209a3d79db56fbe3ba4d905d827b62e1ed31cd6df1198b8c759d589c0f4efc27bd"}}, OutputType::BECH32M, /*op_desc_id=*/{}, {{}}, /*spender_nlocktime=*/0, /*spender_nsequence=*/42, /*preimages=*/{{ParseHex("ae253ca2a54debcac7ecf414f6734f48c56421a08bb59182ff9f39a6fffdb588"), ParseHex("000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f")}});
645 
646+    // Can have rawwnode under tr()

brunoerg commented at 9:03 pm on July 10, 2024:

0    // Can have rawnode under tr()

Eunovo requested review from brunoerg on Jul 11, 2024

brunoerg commented at 9:37 am on July 11, 2024: contributor

You can squash some commits.

Eunovo force-pushed on Jul 11, 2024

Eunovo commented at 1:20 pm on July 11, 2024: contributor

You can squash some commits.

Thanks @brunoerg. Done!

in src/script/descriptor.cpp:1905 in a945bc21d4 outdated

1899@@ -1822,6 +1900,63 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
1900         error = "Can only have raw() at top level";
1901         return nullptr;
1902     }
1903+    if (ctx == ParseScriptContext::P2TR && Func("rawnode", expr)) {
1904+        std::string str(expr.begin(), expr.end());
1905+        if (!IsHex(str)) {

brunoerg commented at 6:05 pm on July 17, 2024:

In 21b6bf4268e40020523d027e2811402b17b755eb “descriptor: Implement rawnode() partial descriptor”: Is this IsHex verification necessary? Wouldn’t it be verified in ParseHex?

Eunovo commented at 11:39 am on July 18, 2024:

In https://github.com/bitcoin/bitcoin/pull/30243/commits/0b30b690e7067240b05ece17fdc7ad44549368a3 I now use TryParseHex and just check for the presence of a response

in src/script/descriptor.cpp:1099 in ba99e596a8 outdated

1094+};
1095+
1096+/** A struct hold information on a node taproot descriptor script tree */
1097+struct TRNodeInfo {
1098+    int depth;
1099+    int leaf_version;

brunoerg commented at 6:22 pm on July 17, 2024:

In ba99e596a86531cc4ad00826ab24804bc02dc777 “descriptor: Add TRNodeInfo”: Does leaf_version need to be int? https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-7

Eunovo commented at 11:37 am on July 18, 2024:

No it doesn’t. I have changed the type to uint8_t

in doc/descriptors.md:87 in a945bc21d4 outdated

82@@ -83,6 +83,8 @@ Descriptors consist of several types of expressions. The top level expression is
83 - `addr(ADDR)` (top level only): the script which ADDR expands to.
84 - `raw(HEX)` (top level only): the script whose hex encoding is HEX.
85 - `rawtr(KEY)` (top level only): P2TR output with the specified key as output key. NOTE: while it's possible to use this to construct wallets, it has several downsides, like being unable to prove no hidden script path exists. Use at your own risk.
86+- `rawnode(HEX)` (inside `tr` only): specify tree or branch merkle root in HEX encoding. NOTE: this hides script paths which are only revealed after spending. Use at your own risk
87+- `rawleaf(HEX,[LEAF_VERSION_HEX])`(inside `tr` only): specify raw leaf script and leaf version in hex encoding. `LEAF_VERSION_HEX` defaults to `c0`

brunoerg commented at 6:37 pm on July 17, 2024:

In a945bc21d4ad4fd5da68ae783ec295d27f50227a “doc: Add reference for rawnode() and rawleaf()”: Wouldn’t it be rawleaf(HEX[,LEAF_VERSION_HEX])?

brunoerg commented at 6:38 pm on July 17, 2024:

maybe

0- `rawleaf(HEX,[LEAF_VERSION_HEX])`(inside `tr` only): specify raw leaf script and leaf version in HEX encoding. `LEAF_VERSION_HEX` defaults to `c0`

Eunovo force-pushed on Jul 18, 2024

Eunovo requested review from brunoerg on Jul 18, 2024

DrahtBot added the label Needs rebase on Aug 28, 2024

Eunovo force-pushed on Sep 2, 2024

Eunovo commented at 1:21 pm on September 2, 2024: contributor

Rebased on top of master https://github.com/bitcoin/bitcoin/commit/a865494deeff7dedcad7140299aee00ab3cdd62c
Added a test for rawnode with multipath descriptors in https://github.com/bitcoin/bitcoin/pull/30243/commits/133b30019c139a3a0e624df2015f65c64040c0c8

DrahtBot removed the label Needs rebase on Sep 2, 2024

achow101 commented at 3:37 pm on October 15, 2024: member

Needs a bip

achow101 requested review from josibake on Oct 15, 2024

DrahtBot added the label CI failed on Oct 23, 2024

DrahtBot removed the label CI failed on Oct 25, 2024

in src/script/descriptor.cpp:1167 in 475981527f outdated

1162@@ -1163,17 +1163,36 @@ class WSHDescriptor final : public DescriptorImpl
1163     }
1164 };
1165 
1166+/** Represents the type of a node in taproot descriptor script tree */
1167+enum TRNodeType {

ismaelsadeeq commented at 8:19 pm on January 22, 2025:

In “descriptor: Add TRNodeInfo” 475981527f052f7c9709d1f3a90270770f4dc160

0enum  class TaprootNodeType {

in src/script/descriptor.cpp:1173 in 475981527f outdated

1168+    LEAF_SCRIPT,
1169+    NODE_HASH
1170+};
1171+
1172+/** A struct hold information on a node taproot descriptor script tree */
1173+struct TRNodeInfo {

ismaelsadeeq commented at 9:07 pm on January 22, 2025:

In “descriptor: Add TRNodeInfo” 475981527f052f7c9709d1f3a90270770f4dc160

0struct TaprootNode {

in src/script/descriptor.cpp:2071 in 475981527f outdated

2068+                this_subs.emplace_back(std::move(subscripts[pos].at(i)));
2069+                TRNodeInfo node;
2070+                node.depth = depths[pos];
2071+                node.leaf_version = TAPROOT_LEAF_TAPSCRIPT;
2072+                node.type = TRNodeType::LEAF_SCRIPT;
2073+                this_nodes.emplace_back(node);

ismaelsadeeq commented at 9:11 pm on January 22, 2025:

In “descriptor: Add TRNodeInfo” 475981527f052f7c9709d1f3a90270770f4dc160

You should add a constructor to TRNodeInfo, this will prevent constructing the object and individually adding all elements before emplacing to the vector here and other places.

0                this_nodes.emplace_back(depths[pos], TAPROOT_LEAF_TAPSCRIPT, TRNodeType::LEAF_SCRIPT);

in src/script/descriptor.cpp:1434 in a9a9e78c3f outdated

1430+public:
1431+    RawNodeDescriptor(std::vector<unsigned char> bytes) : DescriptorImpl({}, "rawnode"), m_bytes(std::move(bytes)) {}
1432+
1433+    bool IsSolvable() const final { return false; }
1434+
1435+    bool IsSingleType() const final { return true; }

ismaelsadeeq commented at 9:23 pm on January 22, 2025:

In “descriptor: Implement rawnode() partial descriptor” a9a9e78c3f839eceebb3abd473d8658fabd92f1f This can be inlined?

in src/script/descriptor.cpp:1461 in a9a9e78c3f outdated

1454+    }
1455+    std::vector<CScript> MakeScripts(const std::vector<CPubKey>&, Span<const CScript>, FlatSigningProvider&) const override { return Vector(m_leaf_script); }
1456+public:
1457+    RawLeafDescriptor(CScript leaf_script, uint8_t leaf_version) : DescriptorImpl({}, "rawleaf"), m_leaf_script(leaf_script), m_leaf_version(leaf_version) {}
1458+
1459+    bool IsSolvable() const final { return false; }

ismaelsadeeq commented at 9:29 pm on January 22, 2025:

In “descriptor: Implement rawnode() partial descriptor” a9a9e78c3f839eceebb3abd473d8658fabd92f1f We are duplicating this code here!

I wonder if DescriptorImpl will just define this duplicate methods with the truthy or falsy values, All descriptor that require concrete implementation will just override those methods.

Eunovo commented at 12:36 pm on January 24, 2025:

I wonder if DescriptorImpl will just define this duplicate methods with the truthy or falsy values, All descriptor that require concrete implementation will just override those methods.

IIUC what you’ve described is what currently exists. IsSolvable() is already defined in DescriptorImpl and IsSingleType() is defined in Descriptor.

ismaelsadeeq commented at 9:32 pm on January 22, 2025: member

Needs a bip

There is a BIP draft opened @furszy that define these output descriptors https://github.com/bitcoin/bips/pull/1721

But the BIP and PR diverge in rawleaf output descriptor, where the bip is omitting the leaf version, I prefer the approach taken in this PR which is also in line with the initial issue discussion in the issue.

Eunovo force-pushed on Jan 24, 2025

DrahtBot added the label CI failed on Mar 23, 2025

DrahtBot commented at 11:27 am on March 23, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/36120275693

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

Eunovo force-pushed on Mar 24, 2025

descriptor: Add TaprootNode

Prepare TRDescriptor to add omitted branches and leaves with user-provided version

8320432def

descriptor: Implement rawnode() partial descriptor 35dc15dfe4

test: add e2e tests for rawnode() and rawleaf() 3f63d7be30

doc: Add reference for rawnode() and rawleaf() b118fbd67a

Eunovo force-pushed on Mar 24, 2025

Eunovo renamed this:
~~Tr partial descriptors~~
descriptors: taproot partial descriptors
on Mar 24, 2025

DrahtBot removed the label CI failed on Mar 24, 2025

DrahtBot added the label Descriptors on Mar 24, 2025

Eunovo commented at 11:37 am on March 24, 2025: contributor

Rebased on master https://github.com/bitcoin/bitcoin/commit/770d39a37652d40885533fecce37e9f71cc0d051

changed Span to std::span

descriptors: taproot partial descriptors #30243

Code Coverage & Benchmarks

Reviews

Conflicts