A few descriptor improvements to prepare for Taproot support #21238

sipa commented at 7:41 PM on February 19, 2021: member

These are a few refactors and non-invasive improvements to the descriptors code to prepare for adding Taproot descriptors.

None of the commits change behavior in any way, except the last one which improves error reporting a bit.

RiccardoMasutti approved

RiccardoMasutti commented at 8:12 PM on February 19, 2021: contributor

ACK, seems good to me. Waiting for squash and will review again.

sipa commented at 8:12 PM on February 19, 2021: member

I don't intend to squash. They're all independent improvements.

DrahtBot added the label Tests on Feb 19, 2021

DrahtBot commented at 5:05 AM on February 20, 2021: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#21329 (descriptor wallet: Cache last hardened xpub and use in normalized descriptors by achow101)
#16116 (Avoid unnecessary signing provider copies on descriptor expansion by Empact)

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.

in src/script/descriptor.cpp:594 in 5a044ac64f outdated

 594 | -            out = Merge(out, subprovider);
 595 | +        FlatSigningProvider subprovider;
 596 | +        for (const auto& subarg : m_subdescriptor_args) {
 597 | +            std::vector<CScript> outscripts;
 598 | +            if (!subarg->ExpandHelper(pos, arg, read_cache, outscripts, subprovider, write_cache)) return false;
 599 | +            if (outscripts.size() != 1 && m_subdescriptor_args.size() != 1) return false;

Sjors commented at 1:15 PM on March 11, 2021:

5a044ac64f3f51dc89a772f512d403c7baa12ae2: I'm a bit confused what this new check is doing

sipa commented at 3:22 AM on March 12, 2021:

Gone.

in src/script/descriptor.cpp:605 in 5a044ac64f outdated

 606 |          for (auto& entry : entries) {
 607 |              pubkeys.push_back(entry.first);
 608 |              out.origins.emplace(entry.first.GetID(), std::make_pair<CPubKey, KeyOriginInfo>(CPubKey(entry.first), std::move(entry.second)));
 609 |          }
 610 | -        if (m_subdescriptor_arg) {
 611 | +        if (m_subdescriptor_args.size() == 1) {

Sjors commented at 1:19 PM on March 11, 2021:

5a044ac64f3f51dc89a772f512d403c7baa12ae2: why is m_subdescriptor_args length 1 a special case?

sipa commented at 3:22 AM on March 12, 2021:

Gone.

Sjors commented at 1:38 PM on March 11, 2021: member

Code review 45bc0c04e0f2ea6dcce734652f45cabc6d10d7d5 looks good, but I got confused in one place...

achow101 commented at 1:19 AM on March 12, 2021: member

Partial ACK. Same questions as Sjors.

sipa force-pushed on Mar 12, 2021

sipa commented at 3:22 AM on March 12, 2021: member

@achow101 @Sjors Good that you raise that point.

The original reason why this behavior of MakeScripts-is-invoked-once-per-evaluation existed was to support things like combo(), where a single evaluation at a single index results in multiple scriptPubKeys. This was particularly complicated to combine with descriptors that support multiple subdescriptors (like tr()) - there isn't really a straightforward way of doing that (cartesian product? requiring the same number of evaluations from each and combining pairwise? ...?). I didn't want to deal with that, so I added the restriction that this once-per-evaluation only existed for descriptors with 1 subdescriptor.

This is all silly, because we don't ever need it. combo() is the only descriptor that produces multiple output scripts, and it is only permitted at the top level - so it's not even possible to have it as a subdescriptor. I've just removed support for multiple-outputscripts-from-subscriptor entirely in a separate commit now. Bye.

DrahtBot added the label Needs rebase on Mar 12, 2021

Sjors commented at 8:28 AM on March 12, 2021: member

Thanks, I'll review again after rebase.

sipa force-pushed on Mar 12, 2021

sipa commented at 8:40 AM on March 12, 2021: member

Rebased.

DrahtBot removed the label Needs rebase on Mar 12, 2021

Sjors commented at 2:02 PM on March 12, 2021: member

ACK 05c633e

Conceptually I find it marginally simpler if you reverse the first and second commit, so the first step is to remove the unused loop:

        if (m_subdescriptor_arg) {
            const auto& subscript = subscripts[0];
            out.scripts.emplace(CScriptID(subscript), subscript);
            output_scripts = MakeScripts(pubkeys, &subscript, out);
        } else {
            output_scripts = MakeScripts(pubkeys, nullptr, out);
        }

And then the second commit drops out.scripts.emplace and moves that into MakeScripts (which is also where combo does this).

To sanity check my understanding: key_exp_index is currently used for multisig descriptors to create a seperate cache for each participating key. With taproot, you might have a root key (key_exp_index == 0), one branch with a key key_exp_index == 2, and another branch with a 3 key multisig (key_exp_index 3,4,5). Is that how it works?

achow101 commented at 6:00 PM on March 12, 2021: member

ACK 05c633e0efaf300aa3353303f77c0a622647a588

sipa force-pushed on Mar 12, 2021

sipa commented at 6:58 PM on March 12, 2021: member

@Sjors

Conceptually I find it marginally simpler if you reverse the first and second commit

Ok, done.

With taproot, you might have a root key (key_exp_index == 0), one branch with a key key_exp_index == 2, and another branch with a 3 key multisig (key_exp_index 3,4,5). Is that how it works?

I think you skipped the 1, but otherwise: exactly.

achow101 commented at 7:41 PM on March 15, 2021: member

re-ACK 35cbef1c483ac9905331f8035d32600e105baab4

Only change was commit reordering.

in src/script/descriptor.cpp:508 in 35cbef1c48 outdated

 511 |  
 512 |  public:
 513 | -    DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::unique_ptr<DescriptorImpl> script, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_arg(std::move(script)) {}
 514 | +    DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args() {}
 515 | +    DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::unique_ptr<DescriptorImpl> script, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args(Vector(std::move(script))) {}
 516 | +    DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::vector<std::unique_ptr<DescriptorImpl>> scripts, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args(std::move(scripts)) {}

Sjors commented at 10:04 AM on March 16, 2021:

warning: unused member function 'DescriptorImpl'

sipa commented at 1:18 AM on March 30, 2021:

Fixed.

Sjors commented at 10:06 AM on March 16, 2021: member

re-ACK 35cbef1c483ac9905331f8035d32600e105baab4 modulo unused constructor

DrahtBot added the label Needs rebase on Mar 17, 2021

sipa force-pushed on Mar 18, 2021

DrahtBot removed the label Needs rebase on Mar 18, 2021

in src/script/descriptor.cpp:603 in 6c114a1010 outdated

 596 | +            std::vector<CScript> outscripts;
 597 | +            if (!subarg->ExpandHelper(pos, arg, read_cache, outscripts, subprovider, write_cache)) return false;
 598 | +            assert(outscripts.size() == 1);
 599 | +            subscripts.emplace_back(std::move(outscripts[0]));
 600 |          }
 601 | +        out = Merge(std::move(out), std::move(subprovider));

S3RK commented at 8:29 AM on March 24, 2021:

Q: why do we need to move the first argument?

sipa commented at 7:39 AM on March 25, 2021:

It doesn't matter now apparently, as Merge takes const lvalue references only. But a more efficient variant could be added that takes advantage of inputs that aren't needed anymore.

in src/script/descriptor.cpp:626 in 6c114a1010 outdated

 621 | @@ -621,9 +622,9 @@ class DescriptorImpl : public Descriptor
 622 |              if (!p->GetPrivKey(pos, provider, key)) continue;
 623 |              out.keys.emplace(key.GetPubKey().GetID(), key);
 624 |          }
 625 | -        if (m_subdescriptor_arg) {
 626 | +        for (const auto& arg : m_subdescriptor_args) {
 627 |              FlatSigningProvider subprovider;

S3RK commented at 8:31 AM on March 24, 2021:

nit: I think one instance of FlatSigningProvider is enough, same as you do in ExpandHelper

sipa commented at 1:17 AM on March 30, 2021:

Done. In fact, I don't need any at all.

in src/script/descriptor.cpp:557 in c612a1d3fc outdated

 558 | -            if (pos++) ret += ",";
 559 | -            std::string tmp;
 560 | -            if (!scriptarg->ToStringHelper(arg, tmp, priv, normalized)) return false;
 561 | -            ret += std::move(tmp);
 562 | -        }
 563 | +        if (!ToStringSubScriptHelper(arg, ret, priv, normalized, pos)) return false;

S3RK commented at 8:55 AM on March 24, 2021:

nit: I find it clearer If we keep placing of the first comma inside ToStringHelper and do not pass pos into ToStringSubScriptHelper. Something like:

std::string subscript;
if (!ToStringSubScriptHelper(arg, subscript, priv, normalized)) return false;
if (pos && subscript.size()) ret += ",";
out = std::move(ret) + std::move(subscript) + ")";

sipa commented at 1:17 AM on March 30, 2021:

Done.

S3RK commented at 7:33 AM on March 25, 2021: member

Code Review ACK 394e387. Nice and clear improvements!

Remove support for subdescriptors expanding to multiple scripts 84f3939ece

refactor: move population of out.scripts from ExpandHelper to MakeScripts

There are currently two DescriptorImpl subclasses that rely on the functionality
that ExpandHelper automatically adds subscripts to the output SigningProvider.

Taproot descriptors will have subscripts, but we don't want them in the
SigningProvider's bare script field. To avoid them ending up there, move this
functionality into the specific classes' MakeScripts implementation.

a917478db0

Make DescriptorImpl support multiple subscripts

So far, no descriptor exists that supports more than one sub-script
descriptor. This will change with taproot, so prepare for this by
changing the m_subdescriptor_arg from a unique_ptr to a vector of
unique_ptr's.

4441c6f3c0

Account for key cache indices in subexpressions

This has no effect for now, as the only fragments with sub-script
expressions (sh, wsh) only allow one, and don't have key expressions
in them.

A future Taproot descriptor will however violate both, and we want
the keys in different sub-scripts to be assigned non-overlapping
cache indices.

6ba5dda0c9

refactor: split off subscript logic from ToStringHelper

This will allow subclasses to overwrite the serialization of subscript
arguments without needing to reimplement all the rest of the ToString
logic.

17e006ff8d

refactor: move uncompressed-permitted logic into ParsePubkey*

This is a preparation for parsing xonly pubkeys, which will complicate
this logic. It's cleaner to put the decision logic close to the public
key parsing itself.

33275a9649

Clean up context dependent checks in descriptor parsing

This changes all context dependent checks in the parser to be
disjunctions of equality checks, rather than also including inequalities.
This makes sure that adding a new context enum in the future won't change
semantics for existing checks.

The error messages are also made a bit more consistent.

0b188b751f

sipa force-pushed on Mar 30, 2021

sipa commented at 1:19 AM on March 30, 2021: member

Rebased, and addressed all comments I think.

S3RK commented at 7:06 AM on March 30, 2021: member

reACK 0b188b7 The only changes are addressing review comments above. 1) removing unused constructor 2) removing redundant signing provided instance creation 3) simplifying ToStringSubScriptHelper signature

Sjors commented at 11:57 AM on April 1, 2021: member

re-ACK 0b188b7

MarcoFalke removed the label Tests on Apr 1, 2021

DrahtBot added the label Tests on Apr 1, 2021

MarcoFalke removed the label Tests on Apr 1, 2021

MarcoFalke added the label Descriptors on Apr 1, 2021

achow101 commented at 7:46 PM on April 9, 2021: member

re-ACK 0b188b751f970027c52729e0c223cc9257669322

Sjors commented at 8:50 AM on April 16, 2021: member

@instagibbs what do you think?

instagibbs commented at 12:32 AM on April 18, 2021: member

Seems like 3 ACKs is enough? not familiar enough with this code anymore to give a proper ACK

in src/script/descriptor.cpp:1070 in 0b188b751f

1065 | @@ -1045,6 +1066,9 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t key_exp_index, Span<const c
1066 |          }
1067 |          auto bytes = ParseHex(str);
1068 |          return std::make_unique<RawDescriptor>(CScript(bytes.begin(), bytes.end()));
1069 | +    } else if (Func("raw", expr)) {
1070 | +        error = "Can only have raw() at top level";

ysangkok commented at 12:40 AM on April 20, 2021:

why is there no new test for this and for addr()?

laanwj merged this on Apr 20, 2021

laanwj closed this on Apr 20, 2021

laanwj referenced this in commit 1483f156f5 on Apr 20, 2021

laanwj referenced this in commit e5faec65bd on Apr 20, 2021

MarcoFalke referenced this in commit 572b36d4ff on Apr 20, 2021

sidhujag referenced this in commit bcf00cdb00 on Apr 20, 2021

sidhujag referenced this in commit 96fceb1a1c on Apr 20, 2021

windsok referenced this in commit 1bae370e98 on Apr 23, 2021

DrahtBot locked this on Aug 16, 2022