descriptors: Multipath/PR 22838 follow-ups

hodlinator commented at 8:10 am on March 25, 2025: contributor

Follows up on unresolved suggestions from #22838. In order of priority:

Fixes a couple of typos ¹² and indentation to conform to Markdown.
Solves for-loop nit ³ and also limits variable scope.
Clarifies data relationships ⁴⁵ by introducing struct rather than comments.

DrahtBot commented at 8:10 am on March 25, 2025: 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/32134.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Stale ACK	l0rinc, rkrux, Prabhat1308

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

DrahtBot added the label Descriptors on Mar 25, 2025

hodlinator commented at 8:18 am on March 25, 2025: contributor

CC @glozow & @jonatack since these follow-ups are mostly based on your comments in the original PR (see references in PR description).

I ran into the broken formatting and 2/3 typo while looking at another PR and traced them back to 22838. Don’t feel strongly about the two refactoring commits. Fine with dropping either/both to not hold the doc-commit hostage.

in doc/descriptors.md:295 in 360f06ea19 outdated

294-   multi(2,xpub.../0/0/*,xpub.../2/*)
295-   multi(2,xpub.../1/0/*,xpub.../3/*)
296-   multi(2,xpub.../2/0/*,xpub.../4*)
297+    multi(2,xpub.../0/0/*,xpub.../2/*)
298+    multi(2,xpub.../1/0/*,xpub.../3/*)
299+    multi(2,xpub.../2/0/*,xpub.../4*)

l0rinc commented at 9:54 am on March 25, 2025:

shouldn’t the wildcard have its own position in the hierarchy?

0    multi(2,xpub.../2/0/*,xpub.../4/*)

rkrux commented at 11:34 am on March 25, 2025:

Yes, I believe it should.

hodlinator commented at 8:29 pm on March 25, 2025:

Thread https://github.com/bitcoin/bitcoin/pull/32134/files#r2011731171:

Good catch! (Edit: Just found a local branch from February where I had actually fixed that too. :sweat_smile:)

in src/script/descriptor.cpp:1496 in a29e7bf0bd outdated

1495+    if (!multipath) {
1496         out.emplace_back(std::move(path));
1497     } else {
1498         // Replace the multipath placeholder with each value while generating paths
1499-        for (auto value : multipath_values) {
1500+        for (auto value : multipath->values) {

l0rinc commented at 9:57 am on March 25, 2025:

nit: I had to check the type of value to make sure this isn’t needlessly copied - to make it slightly simpler to review, consider:

0        for (const auto& value : multipath->values) {

hodlinator commented at 8:28 pm on March 25, 2025:

Thread https://github.com/bitcoin/bitcoin/pull/32134/files#r2011736752:

Going with this for now:

0        for (uint32_t value : multipath->values) {

in src/script/descriptor.cpp:1470 in a29e7bf0bd outdated

1466@@ -1464,6 +1467,7 @@ std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostr
1467                 return false;
1468             }
1469 
1470+            multipath.emplace();

l0rinc commented at 10:11 am on March 25, 2025:

I don’t like this third commit (nor the original implementation), we’re looping over the splits, assigning a multipath if found, checking if it was already found during previous iterations, setting errors to output parameters and returning early, if we didn’t return we assume it was correct, etc - it’s too stateful, we’re mixing not-strictly-related operations in a single loop, i.e. validation with usage, we should be able to separate the two concerns (it’s a tiny loop).

rkrux commented at 12:36 pm on March 25, 2025:

I like the suggested change, it’s cleaner and easier to follow. There’s a bit of validation in the second loop as well but I guess there is no way to completely separate the validation from parsing. The alternative would be to parse the multipath nums in the first loop as well but I would prefer this implementation over that.

rkrux commented at 12:39 pm on March 25, 2025:

A comment before the first loop would be nice stating Validate multipath key path specifiers

hodlinator commented at 8:27 pm on March 25, 2025:

Thread https://github.com/bitcoin/bitcoin/pull/32134/files#r2011759617:

Splitting validation from usage sounds good, but l0rincs version introduces more state and as rkrux mentioned still validates the parsing of the numbers in the “non-validating” loop. It’s a bit more drastic than I was aiming for and still feels incomplete.

That version also undoes the move to keep the multipath data together towards the end, see list item 3 in the PR description. In the beginning it also uses std::pair with unnamed components instead of a struct with explanatory fields.

rkrux commented at 12:40 pm on March 27, 2025:

It’s a bit more drastic than I was aiming for and still feels incomplete.

Even though I like the suggested change because of its intent, there are trade-offs, and as mentioned it’s more than what the author originally intended to do in this pull. So, I will leave its fate to the author.

in src/script/descriptor.cpp:1484 in a29e7bf0bd outdated

1481+                multipath->values.emplace_back(*op_num);
1482             }
1483 
1484             path.emplace_back(); // Placeholder for multipath segment
1485-            multipath_segment_index = path.size()-1;
1486+            multipath->segment_index = path.size()-1;

l0rinc commented at 11:03 am on March 25, 2025:

nit: since we’re already touching this line we might as well format it

l0rinc changes_requested

l0rinc commented at 11:06 am on March 25, 2025: contributor

Could we separate the concerns of ParseKeyPath (validation from parsing)? And I think there may be a typo in the doc.

  0diff --git a/doc/descriptors.md b/doc/descriptors.md
  1index d5e845273a..60d3e0159f 100644
  2--- a/doc/descriptors.md
  3+++ b/doc/descriptors.md
  4@@ -288,11 +288,11 @@ For example, a descriptor of the form:
  5 
  6     multi(2,xpub.../<0;1;2>/0/*,xpub.../<2;3;4>/*)
  7 
  8-will expand to the 3 descriptors
  9+will expand to the following descriptors:
 10 
 11     multi(2,xpub.../0/0/*,xpub.../2/*)
 12     multi(2,xpub.../1/0/*,xpub.../3/*)
 13-    multi(2,xpub.../2/0/*,xpub.../4*)
 14+    multi(2,xpub.../2/0/*,xpub.../4/*)
 15 
 16 When this tuple contains only two elements, wallet implementations can use the
 17 first descriptor for receiving addresses and the second descriptor for change addresses.
 18diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
 19index d2224263d0..7a594f6e75 100644
 20--- a/src/script/descriptor.cpp
 21+++ b/src/script/descriptor.cpp
 22@@ -1439,37 +1439,35 @@ std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostr
 23  **/
 24 [[nodiscard]] bool ParseKeyPath(const std::vector<std::span<const char>>& split, std::vector<KeyPath>& out, bool& apostrophe, std::string& error, bool allow_multipath)
 25 {
 26-    KeyPath path;
 27-    struct Multipath {
 28-        size_t segment_index;
 29-        std::vector<uint32_t> values;
 30-    };
 31-    std::optional<Multipath> multipath;
 32-
 33-    for (size_t i = 1; i < split.size(); ++i) {
 34-        const std::span<const char>& elem = split[i];
 35-
 36+    std::optional<std::pair<size_t, std::vector<std::span<const char>>>> multipath_data;
 37+    for (size_t i{1}; i < split.size(); ++i) {
 38         // Check if element contains multipath specifier
 39-        if (!elem.empty() && elem.front() == '<' && elem.back() == '>') {
 40+        if (const auto& elem{split[i]}; elem.size() >= 2 && elem.front() == '<' && elem.back() == '>') {
 41             if (!allow_multipath) {
 42                 error = strprintf("Key path value '%s' specifies multipath in a section where multipath is not allowed", std::string(elem.begin(), elem.end()));
 43                 return false;
 44-            }
 45-            if (multipath) {
 46+            } else if (multipath_data) {
 47                 error = "Multiple multipath key path specifiers found";
 48                 return false;
 49             }
 50-
 51-            // Parse each possible value
 52-            std::vector<std::span<const char>> nums = Split(std::span(elem.begin()+1, elem.end()-1), ";");
 53-            if (nums.size() < 2) {
 54+            auto spans{Split(std::span(elem.begin() + 1, elem.end() - 1), ";")};
 55+            if (spans.size() < 2) {
 56                 error = "Multipath key path specifiers must have at least two items";
 57                 return false;
 58             }
 59 
 60-            multipath.emplace();
 61+            multipath_data = {i, spans};
 62+        }
 63+    }
 64+
 65+    KeyPath path;
 66+    std::optional<size_t> multipath_segment_index;
 67+    std::vector<uint32_t> multipath_values;
 68+
 69+    for (size_t i{1}; i < split.size(); ++i) {
 70+        if (multipath_data && i == multipath_data->first) {
 71             std::unordered_set<uint32_t> seen_multipath;
 72-            for (const auto& num : nums) {
 73+            for (const auto& num : multipath_data->second) {
 74                 const auto& op_num = ParseKeyPathNum(num, apostrophe, error);
 75                 if (!op_num) return false;
 76                 auto [_, inserted] = seen_multipath.insert(*op_num);
 77@@ -1477,25 +1475,25 @@ std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostr
 78                     error = strprintf("Duplicated key path value %u in multipath specifier", *op_num);
 79                     return false;
 80                 }
 81-                multipath->values.emplace_back(*op_num);
 82+                multipath_values.emplace_back(*op_num);
 83             }
 84 
 85             path.emplace_back(); // Placeholder for multipath segment
 86-            multipath->segment_index = path.size()-1;
 87+            multipath_segment_index = path.size() - 1;
 88         } else {
 89-            const auto& op_num = ParseKeyPathNum(elem, apostrophe, error);
 90+            const auto& op_num = ParseKeyPathNum(split[i], apostrophe, error);
 91             if (!op_num) return false;
 92             path.emplace_back(*op_num);
 93         }
 94     }
 95 
 96-    if (!multipath) {
 97+    if (!multipath_segment_index) {
 98         out.emplace_back(std::move(path));
 99     } else {
100         // Replace the multipath placeholder with each value while generating paths
101-        for (auto value : multipath->values) {
102+        for (const auto& value : multipath_values) {
103             KeyPath branch_path = path;
104-            branch_path[multipath->segment_index] = value;
105+            branch_path[*multipath_segment_index] = value;
106             out.emplace_back(std::move(branch_path));
107         }
108     }

rkrux commented at 12:42 pm on March 25, 2025: contributor

Re: #32134#pullrequestreview-2713105661

In the docs file, I would keep the 3 though. Explicitly stating the count of descriptors it will expand to is helpful.

descriptors doc: Correct Markdown format + wording 99a92efdd9

hodlinator force-pushed on Mar 25, 2025

hodlinator commented at 8:38 pm on March 25, 2025: contributor

Thanks for reviewing! Pushed improvements based on feedback.

l0rinc commented at 8:44 pm on March 25, 2025: contributor

ACK bd34c6008aa455d5b294db8977be471d1bc837df - not yet sure about the last commit, let’s see what others think

in src/script/descriptor.cpp:1467 in bd34c6008a outdated

1463@@ -1465,6 +1464,7 @@ std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostr
1464                 return false;
1465             }
1466 
1467+            std::unordered_set<uint32_t> seen_multipath;

rkrux commented at 11:53 am on March 27, 2025:

Good catch here, makes sense to reduce the life of this variable here. This set is not cleared anywhere in the function that led me to consider whether the older implementation was buggy but it was not because the multipath key specifier can only appear once in the descriptor as per the check on line 1456/1455.

The naming of this variable (not a new change) feels incomplete though. It’s a set of derivation indexes/values but this term is not mentioned anywhere in the function. So, something like seen_multipath_nums (to keep it consistent with the existing terminology here) would be ok instead of what it is now.

hodlinator commented at 3:49 pm on March 27, 2025:

Thanks for pointing this out. Context implies “multipath” now that the lifetime has been narrowed, making the naming poorer.

“nums” feels quite general though. Renamed to seen_substitutes in latest push. Made me modify an additional line but I think it might be worth it.

in src/script/descriptor.cpp:1445 in 1e1f11e894 outdated

1439@@ -1440,8 +1440,11 @@ std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostr
1440 [[nodiscard]] bool ParseKeyPath(const std::vector<std::span<const char>>& split, std::vector<KeyPath>& out, bool& apostrophe, std::string& error, bool allow_multipath)
1441 {
1442     KeyPath path;
1443-    std::optional<size_t> multipath_segment_index;
1444-    std::vector<uint32_t> multipath_values;
1445+    struct Multipath {
1446+        size_t segment_index;
1447+        std::vector<uint32_t> values;

rkrux commented at 12:34 pm on March 27, 2025:

Again these are derivation indexes/values, so derivation_values can be an option instead of just values, which feels bland.

hodlinator commented at 3:45 pm on March 27, 2025:

I would conceptually call them derivation path components… :) But like shorter names, changed to substitutes. How about that?

Also changed segment_index to placeholder_index, inspired by the code comment

// Replace the multipath placeholder with each value while generating paths

in src/script/descriptor.cpp:1443 in 1e1f11e894 outdated

1439@@ -1440,8 +1440,11 @@ std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostr
1440 [[nodiscard]] bool ParseKeyPath(const std::vector<std::span<const char>>& split, std::vector<KeyPath>& out, bool& apostrophe, std::string& error, bool allow_multipath)
1441 {
1442     KeyPath path;
1443-    std::optional<size_t> multipath_segment_index;
1444-    std::vector<uint32_t> multipath_values;
1445+    struct Multipath {

rkrux commented at 12:42 pm on March 27, 2025:

Using struct here seems reasonable to me in order to tie these two related variables together.

rkrux approved

rkrux commented at 12:43 pm on March 27, 2025: contributor

crACK 1e1f11e8946126180f4a93d6d99d5981ecfc7cd3

I shared couple naming suggestions though non-blocking.

DrahtBot requested review from l0rinc on Mar 27, 2025

descriptors refactor: Use range-for and limit scope of seen_multipath

* Range-for avoids ++i/i++ debate and decreases linecount.
* seen_multipath is only used if multipath_segment_index hasn't already been set. Rename it to seen_substitutes to better describe what it does, now that the context implies its involved in multipath.

32c3126d71

hodlinator force-pushed on Mar 27, 2025

hodlinator commented at 3:50 pm on March 27, 2025: contributor

Attempted to improve naming in latest push in response to #32134#pullrequestreview-2721049447.

in src/script/descriptor.cpp:1445 in 78327f9a8d outdated

1439@@ -1440,20 +1440,22 @@ std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostr
1440 [[nodiscard]] bool ParseKeyPath(const std::vector<std::span<const char>>& split, std::vector<KeyPath>& out, bool& apostrophe, std::string& error, bool allow_multipath)
1441 {
1442     KeyPath path;
1443-    std::optional<size_t> multipath_segment_index;
1444-    std::vector<uint32_t> multipath_values;
1445-    std::unordered_set<uint32_t> seen_multipath;
1446+    struct Multipath {
1447+        size_t placeholder_index;
1448+        std::vector<uint32_t> substitutes;

Prabhat1308 commented at 4:28 am on March 28, 2025:

I don’t like the name substitutes. It implies that it is an alternative to a one major path which I don’t think is the case ?

hodlinator commented at 10:45 am on March 28, 2025:

Pushed new version that hopefully clarifies things: https://github.com/bitcoin/bitcoin/blob/7aa397a7d45ce0ae1b83cc6f3a65db0e41b21ee8/src/script/descriptor.cpp#L1442-L1447

Prabhat1308 commented at 4:29 am on March 28, 2025: none

crACK 78327f9

DrahtBot requested review from rkrux on Mar 28, 2025

descriptors refactor: Clarify multipath data relationships through local struct 7aa397a7d4

hodlinator force-pushed on Mar 28, 2025

descriptors: Multipath/PR 22838 follow-ups #32134

Code Coverage & Benchmarks

Reviews