Builds on top of #22051, adding signing support after derivation support.
Nothing is changed in descriptor features. Signing works for key path and script path spending, through the normal sending functions, and PSBT-based RPCs. However, PSBT usability is rather low as no extensions have been defined to convey Taproot-specific information, so all script information must be known to the signing wallet.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--174a7506f384e20aa4161008e828411d-->
Reviewers, this pull request conflicts with the following ones:
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.
Concept ACK 🎉
TBH, I find your "must be specified in depth-first search order" somewhat confusing. As an alternative syntax I suggest simply using some notation for a binary or. For example.
tr(KEY): only taproot output key known (or is it an internal pubkey with common NUMS tweak??)tr(KEY,A): internal pubkey with a single script A at level 0.tr(KEY,[A|B]): internal pubkey with a two scripts, A and B at level 1.tr(KEY.[[A|B]|C]): internal pubkey with a two scripts, A and B at level 2, and a third script at level 1.tr(KEY.[A|[B|C]]): same as above except for A is at level 1 and C is at level 2 instead.tr(KEY.[[B|C]|A]): equal to the above descriptor.tr(KEY.[[A|B]|[C|D]]): internal pubkey with a four scripts, all at level 2.tr(KEY.[[A|C]|[B|D]]): same four scripts as above, again all at level 2 but now associated differently which makes for a different tweak.tr(KEY.[A|[[B|C]|D]]): same four scripts as above, but no longer all at the same level.My claimed advantages are the implicitness of the depth, and clearer notation indicating how the scripts are associated amongst each other.
The notation above is just an example and don't care too much about the specific syntax.
Other things to include in the list of features to be added later, a MerkleRoot descriptor for fixed but unknown branches.
@roconnor-blockstream Yeah, I considered something like that, and am open to it. Both notations are equivalent in that you can fairly easily convert in both directions between them (counting bracing level in yours corresponds to the depth specified explicitly in mine, with leaves ultimately listed in the same order). The advantage I see to the current one is that I think it's a bit more readable, avoiding the need to go count braces to see relative depth of leaves. Yours is perhaps a bit easier to write (but maybe that's not something we really expect humans to do much for nontrivial cases).
There are many more variations possible. One extreme would be permitting arbitrary weights for every node, and have the descriptor expansion convert it to a Huffman tree. I'd prefer not to do this because it's adding information that can't be inferred back from the script tree it is converted to.
Right. My concern with explicit levels is that it is so easy to violate the invariant that the sum of the weights has to add up to 1, and you cannot really splice together subexpressions to compose a descriptor from fragments without going through and globally adjusting all the levels to be sane.
Additionally I understand that it is the case that checking that the weights add up to 1 is not a sufficient condition to check that a string is a well-formed descriptor as it doesn't imply that the arrangement is in some DFS order. Thus I argue that my proposed scheme is better because the well-formedness of the descriptor format is a relatively simple syntactic check (that would pass LANGSEC scrutiny).
+1 @roconnor-blockstream a bracketed version seems superior to me.
Some BIP-level (assuming this would eventually become a BIP) thoughts on things that might be useful in a descriptor:
[a-zA-Z0-9_]*( or something similar as a subtree modifier. E.g., [A,B] -> huffman[A@p,B@q].The advantage of having this baked in is great for readability -- often times you might want to express a tree as:
[Thing that should happen most likely, in the unlikely event that doesn't happen, Other thing that could happen, other thing we might want to do in unlikely event]
which would -- if depth order is required -- look like:
[Thing that should happen most likely, Other thing that could happen, in the unlikely event that doesn't happen, other thing we might want to do in unlikely event]
Which reminds me of exception throwing where the error handling source code can be very far away from the source of the error (bad).
(something like huffman does require that we also use a sorted Tree to select clauses lexicographically after probability).
3. An annotation/tag interface that would allow you to do something like [A#{escrow, alice, bob}, B#{alice, bob}] which when 'blind_for("escrow")' is called creates the [A, N2KB] descriptor.
4. Maybe a more general way of inserting extended structured metadata that Core will store/pass along but might not understand for supporting things like 3...
5. a opaque[] annotation, which compiles a subtree opaquely to any parent modifiers. This would be useful in contexts where a subtree might be known entirely already by another party and we want to preserve that structure
@JeremyRubin I agree that there is a potential use for omitted subtrees, but I don't think there is much of a difference between the two approaches there? In the current approach you'd just specify the Merkle root of the omitted subtree as a "leaf" at the depth that root exists at.
All the other things you mention seem to be things for a policy language that get compiled to descriptors rather than descriptors themselves. Descriptors are for encoding information potentially needed by signers; I can't imagine a need for information of that kind that applies a specific subtree (rather than applying to individual leaves, or to the entire tree).
That said, it's not hard to implement a nested-bracket approach; I'll try to implement that too so people can experiment with both.
My main reason for having a slight preference for the explicit depth style is that I think tr(KEY,[A|[[B|C]|D]]) is much harder to interpret by a human than tr(KEY,1:A,3:B,3:C,2:D). In the latter it's immediately clear that B and C are the least likely paths, and A is the most likely one, for example. I agree with the argument that it's harder to write, but I'm not sure that's a big problem; for nontrivial things I suspect they'll either be written once as a template, or generated from a higher-level specification.
I think it just depends on what descriptors are for v.s. what people end up using them for. Of that I am unsure, but it's worthwhile to note that this is a human readable format so presumably at some point a human may look at it or want to edit it.
w.r.t. annotations for "descriptor blinding", I actually think this is somewhat relevant. One could imagine a scenario where a branch is used both as a pre-image for a has revelation and as a script. In that case, you might not want to reveal the entire tree to someone as it might give them the ability to spend from that branch as well.
w.r.t. brackets or list, it might be interesting to make the descriptors a NEWICK format subset, which seems to be the most commonly used tree format (and is a bracket based format). Then you could dump descriptors into standard tree viewing software easily. I couldn't find a good reference for tree file formats using a list/depth approach.
edit: w.r.t omitted subtrees, as noted, this was just some BIP-level feedback as we look to expanding what can go into a tr descriptor, less so comments on implementation.
@JeremyRubin @roconnor-blockstream Added a commit to switch to "tr(KEY,{S,{{S,S},S}})" notation. I prefer {} over [] because the latter is already in use for key origin information.
Thanks!
Is there any reason not to use parens ()? NEWICK compatibility would be fun.
33 | @@ -34,11 +34,11 @@ Span<const char> Expr(Span<const char>& sp) 34 | int level = 0; 35 | auto it = sp.begin(); 36 | while (it != sp.end()) { 37 | - if (*it == '(') { 38 | + if (*it == '(' || *it == '{') {
don't we need to trace what type we are in if it is a paren or a {?
E.g., (} would pass here no?
That doesn't matter. This function is just for finding the end of the current expression. If that expression is unbalanced, the actual parsing code will fail.
I see.
bikeshed: I think something like this could be a little clearer:
// This function finds the end of the current expression and returns pair(expr_span, rest_span)
// trailing comma is included in the expr_span, e.g.
// `<expr A>,<expr B>` would return `<expr A>,` `<expr B>`
std::pair<Span<const char>, Span<const char>> Expr(const Span<const char>& sp)
{
size_t left = 0;
size_t right = 0;
auto it = sp.begin();
while (it != sp.end()) {
switch (*it) {
case '(':
case '{':
++left;
break;
case '}':
case ')':
++right;
break;
}
bool balanced = right == left;
// completed a Expr by matching nonzero left/right
if (balanced && right > 0) break;
// we have a balanced term as a comma separated entity
if (balanced && *it == ',') break;
++it;
}
return std::make_pair(sp.first(it-sp.begin), sp.subspan(it-sp.begin()));
}
That said it seem peculiar to me that , is left on the string -- maybe preferable to trim it here?
That's how the current span-based parsing works. I think discussions about improvements to that are interesting but out of scope for this PR.
1172 | + return nullptr; 1173 | + } 1174 | + continue; 1175 | + } 1176 | + auto sarg = Expr(expr); 1177 | + auto subdesc = ParseScript(key_exp_index, sarg, ParseScriptContext::P2TR, out, error);
you could directly emplace_back the subdesc and then nullcheck/return nullptr, rather than needing to std::move it.
Done.
1183 | + error = strprintf("tr(): expected '}' after script expression"); 1184 | + return nullptr; 1185 | + } 1186 | + counts.pop_back(); 1187 | + } 1188 | + if (counts.size()) {
Behavior Note:
I believe this would be more robust to go before the while loop -- it shouldn't come up, because we're in a binary tree maybe -- but it would be better to explicitly check:
if (counts.size() && counts.back() == false)
or something like
if (counts.size() && counts.back() <= 2)
if we want to limit how many terms in a nest are allowed.
right now this invariant is implicitly checked by the order of the code and it is non-obvious to me.
I've restructured things a bit, and added a bunch of comments. Does this look better?
847 | + std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts, FlatSigningProvider& out) const override 848 | + { 849 | + TaprootBuilder builder; 850 | + assert(m_depths.size() == scripts.size()); 851 | + for (size_t pos = 0; pos < m_depths.size(); ++pos) { 852 | + builder.Add(m_depths[pos], scripts[pos], TAPROOT_LEAF_TAPSCRIPT);
given that this is just iterating in order, it seems like we should be able to directly feed the TaprootBuilder from the tr parsing code and do away with the intermediate vectors?
No, unfortunately this happens at a different layers. TaprootBuilder can only be invoked with concrete keys; those don't exist yet at parsing time.
I see :(
I guess I'll mark it as a personal todo (no need to upset a working internal representation) to brainstorm if there's a more obvious way to represent the tree than the ordered depth annotations (even though it's equivalent and unambiguous, I still find it unintuitive)
I like linear data structures that don't need recursion to process, when unnecessary.
Yeah, I agree with that 100%. What I was thinking was a vec<uint128> where each bit represents a left/right on the tree. That way you can do a de-duplicate check to make sure each node is only occupied once. Then the order of the vec itself is no longer significant; it should not need to be preserved because you can sort them by value (if I'm not wrong) to get the insertion order. Depth could be computed by looking at your nearest neighbor and computing the "divergence" (or by encoding an extra byte to make it explicit -- unclear what is best here).
With a sorted vec, this also enables some nicesties such as using std:: binary searches for O(log(n)) lookup by tree position.
@roconnor-blockstream may also like that this format should be:
Why do the properties of this internal, temporary, data structure that purely used during the construction of a scriptPubKey matter? It does what it is supposed to do. If we ever need other operations on it, something else can be considered.
I find the code really hard to understand. Conceivably if we want people to review/audit it, a conceptually simpler representation & set of algorithms should be easier to understand? The above suggestion may or may not be it, but I haven't been able to fully work out how the algorithms this PR is currently using work even after staring at them for a bit.
the properties matter less.
I'll try to add more comments.
Added a big comment explaining the data structure in script/standard.h. WDYT?
Marking this as resolved. Feel free to comment if the result still isn't clear.
935 | @@ -886,6 +936,13 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S 936 | error = "Uncompressed keys are not allowed"; 937 | return nullptr; 938 | } 939 | + } else if (data.size() == 32 && ctx == ParseScriptContext::P2TR) { 940 | + unsigned char fullkey[33] = {0x02}; 941 | + std::copy(data.begin(), data.end(), fullkey + 1); 942 | + pubkey.Set(std::begin(fullkey), std::end(fullkey)); 943 | + if (pubkey.IsFullyValid()) { 944 | + return MakeUnique<ConstPubkeyProvider>(key_exp_index, pubkey);
nit: in d5a0dce8fe40153b07ec6e882e8b1568b05e3905: we can use std::make_unique in new code.
Done.
Switched to the tr(KEY,{{S1,S2},{{...) style descriptors.
Switched to the
tr(KEY,{{S1,S2},{{...)style descriptors.
Can you clarify this, maybe with a simple example, in the PR description or in descriptors.md?
90 | - Optionally followed by a single `/*` or `/*'` final step to denote all (direct) unhardened or hardened children. 91 | - The usage of hardened derivation steps requires providing the private key. 92 | 93 | +`TREE` expressions: 94 | +- any `SCRIPT` expression 95 | +- An open brace `{`, a `TREE` expression, a comma `,`, a `TREE` expression, and a closing brace `}`
So this means you can do, tr(KEY,{A}), tr(KEY,{A,B}), tr(KEY,{A,{B,C}}), etc? So a TREE must have two elements, unless it's at the top?
Maybe also point out that some taproot features have yet to be implemented, so the only script you can put in a TREE element is pk(KEY).
No, {A} is not a valid TREE. A is.
So you'd use tr(KEY,A) but tr(KEY,{A,B}). There is nothing special about the top level.
850 | + { 851 | + for (size_t pos = 0; pos < m_depths.size(); ++pos) { 852 | + ret += strprintf(",%i:", m_depths[pos]); 853 | + std::string tmp; 854 | + if (!m_subdescriptor_args[pos]->ToStringHelper(arg, tmp, priv, normalized)) return false; 855 | + ret += std::move(tmp);
In commit 8aaa61bfb7590e95eb7ca5106dfe3561f1c7a7c8 "Add tr() descriptor (derivation only, no signing)"
This looks like the original syntax and not the syntax with the braces.
Since this function is used as part of writing the descriptor to the wallet, any wallet containing a descriptor with scripts will currently have an invalid descriptor and cannot be loaded again.
Nice catch. Fixed, and added tests for roundtrippability of the descriptors.
709 | + return Vector(GetScriptForRawPubKey(keys[0])); 710 | + } 711 | + } 712 | public: 713 | - PKDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pk") {} 714 | + PKDescriptor(std::unique_ptr<PubkeyProvider> prov, bool xonly) : DescriptorImpl(Vector(std::move(prov)), "pk"), m_xonly(xonly) {}
In commit 8aaa61bfb7590e95eb7ca5106dfe3561f1c7a7c8 "Add tr() descriptor (derivation only, no signing)"
I think it would be better to default xonly = false so that existing callers don't need to change, and this is kind of what is expected for this descriptor. Then nested taproot things can set xonly as they need.
Done.
250 | - COutPoint prevout = tx.vin[index].prevout; 251 | - if (prevout.n >= input.non_witness_utxo->vout.size()) { 252 | - return false; 253 | + bool have_all_spent_outputs = true; 254 | + std::vector<CTxOut> utxos(tx.vin.size()); 255 | + for (size_t idx = 0; idx < tx.vin.size(); ++idx) {
In 1d3cc29fb86b614b76b4d97a5adab7f903fc3020 "Construct and use PrecomputedTransactionData in PSBT signing"
We should avoid iterating all of the PSBT inputs again when we are signing each input. Instead we should compute the PrecomputedTransactionData in the caller and pass that into SignPSBTInput.
This can be done in CWallet::FillPSBT where we are iterating the inputs anyways to get their previous txs from the wallet. We could be constructing the PrecomputedTransactionData at that time and then passing it into FIllPSBT which then passes it to SignPSBTInput.
Done.
Rebased.
I created a descriptor like so, to test scriptpath spending: tr(tpub1/0/*,pk(tprv2/0/*)). This way the wallet won't have private keys for the keypath spend (tpub1), so it has to use the script pk(tprv2/0*).
This seems to work on Signet, but the transaction does not enter the mempool. testmempoolaccept complains min relay fee not met, so perhaps there's a fee calculation bug? Once I bump the fee it goes through.
I used the GUI to create (and bump) the transactions. With a regular tr(tpriv1/0/*) descriptor wallet I don't see this problem.
Here's the original raw transaction:
0200000000010114a5df5cf5084ea003c2f021c4e22846238a61c89894fa786e556395048ed40c0000000000fdffffff0292a0070000000000225120a287e30feacc24a25a9a3e689ad0107223cb247fb9a14880cddf3e62f1453a6420a1070000000000160014bf15b210d9f53e5c7b002fe904af042098706c3a03406c11b79f9a417f9702a6117e3bb170956ece09af6b584b2d92e1e0e5cfcad725250c91e29db77751af36970c0e5676622cfcf6fb1c81a316dfcd349b1ea59d412220d0586a7eba2e92a38f31ba8a7d82c05b9bb101bf3a649f205bd8e1df7c428b6eac21c07a35becbfeccf3ed5367ff117681497d040e6996eeae3dd21acb123e8525729d227b0000
@Sjors That's expected, and I don't really know how to deal with this. The problem is that we determine the fee for spending an output by using the dummy signer, but the dummy signer can't know which private keys will and won't be available. Since tr spending cost differs based on what is available, this will give an inaccurate result (it'll always just use the key path).
A possibility is extending descriptors with markers to indicate that certain keys won't ever be available. It's good to point this out, but I think the scope will take us a bit too far for this PR.
This is definitely a new can of worms that will need some thought, but I agree it can wait (if documented).
The main point of having leaves is to be able to spend when the main keypath key material isn't available. But we currently have no way of indicating that.
I don't think descriptors are the right place for this. Let's say I have 3 hardware wallets. The keypath is a 3-of-3 musig, and the script(s) are 2-of-3. Normally I would sign with all 3 in order to save fees and preserve privacy. But after a minor boating accident I only have two. I wouldn't necessarily want to create a new wallet, so nothing about the descriptors changes.
The natural place to indicate which leaf to use is probably the send command (especially fun for the GUI...). From there on it should be straight forward to use the right dummies.
Concept ACK 🚀
51 | @@ -50,11 +52,13 @@ struct FlatSigningProvider final : public SigningProvider 52 | std::map<CKeyID, CPubKey> pubkeys; 53 | std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> origins; 54 | std::map<CKeyID, CKey> keys; 55 | + std::map<XOnlyPubKey, TaprootSpendData> tr_spenddata;
IIUC the key in the map is output key, but it's not immediately obvious. Maybe add a comment here and for GetTaprootSpendData?
Done (here using a comment, and in function calls by changing the parameter name to output_key).
All prerequisites have been merged! Needs rebase.
846 | @@ -847,7 +847,9 @@ class TRDescriptor final : public DescriptorImpl 847 | XOnlyPubKey xpk(keys[0]); 848 | if (!xpk.IsFullyValid()) return {}; 849 | builder.Finalize(xpk); 850 | - return Vector(GetScriptForDestination(builder.GetOutput())); 851 | + WitnessV1Taproot output = builder.GetOutput(); 852 | + out.tr_spenddata[output].Merge(builder.GetSpendData());
Is this just an assignment? We don't need to merge here, do we?
Well, not right now.
But like several things in this PR it's sort of written to accomodate future PSBT extensions that expose some of the TaprootSpendData. And one of the possbilities is only including information about a subset of leaves. In that case, you do want a merge operation when combining.
846 | @@ -847,7 +847,9 @@ class TRDescriptor final : public DescriptorImpl
847 | XOnlyPubKey xpk(keys[0]);
848 | if (!xpk.IsFullyValid()) return {};
What about the case with unspendable internal key?
There is no real difference. An unspendable internal pubkey is just a pubkey with no known private key. You still need to actually select one.
239 | @@ -234,7 +240,14 @@ class XOnlyPubKey 240 | 241 | const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); } 242 | const unsigned char* data() const { return m_keydata.begin(); } 243 | - size_t size() const { return m_keydata.size(); } 244 | + static constexpr size_t size() { return uint256::size(); }
in commit b6f6c58ef7e64f699102beef063b3b9f91c71ecd:
Could use decltype(m_keydata)::size() for self-documenting code?
Done.
73 | - `combo(KEY)` (top level only): an alias for the collection of `pk(KEY)` and `pkh(KEY)`. If the key is compressed, it also includes `wpkh(KEY)` and `sh(wpkh(KEY))`. 74 | -- `multi(k,KEY_1,KEY_2,...,KEY_n)` (anywhere): k-of-n multisig script. 75 | -- `sortedmulti(k,KEY_1,KEY_2,...,KEY_n)` (anywhere): k-of-n multisig script with keys sorted lexicographically in the resulting script. 76 | +- `multi(k,KEY_1,KEY_2,...,KEY_n)` (not inside `tr`): k-of-n multisig script. 77 | +- `sortedmulti(k,KEY_1,KEY_2,...,KEY_n)` (not inside `tr`): k-of-n multisig script with keys sorted lexicographically in the resulting script. 78 | +- `tr(XKEY)` or `tr(KEY,TREE)` (top level only): P2TR output with the specified key as internal key, and optionally a tree of script paths.
in 3f6aad2d687b5435e93bf6c99cbe1cabc9c1ff16:
Probably should be tr(KEY) instead of tr(XKEY).
Fixed.
1430 | @@ -1431,8 +1431,8 @@ void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent 1431 | } 1432 | 1433 | // Determine which precomputation-impacting features this transaction uses. 1434 | - bool uses_bip143_segwit = false; 1435 | - bool uses_bip341_taproot = false; 1436 | + bool uses_bip143_segwit = force; 1437 | + bool uses_bip341_taproot = force; 1438 | for (size_t inpos = 0; inpos < txTo.vin.size(); ++inpos) {
in 474536660d:
May as well skip this for loop altogether if force is true, if I see that correctly.
Done.
Rebased, and addressed comments.
node0 stderr bitcoin-node: script/interpreter.cpp:1714: virtual bool GenericTransactionSignatureChecker<CMutableTransaction>::CheckSchnorrSignature(Span<const unsigned char>, Span<const unsigned char>, SigVersion, const ScriptExecutionData &, ScriptError *) const [T = CMutableTransaction]: Assertion `this->txdata' failed.
74 | @@ -75,7 +75,7 @@ class base_blob 75 | return &m_data[WIDTH]; 76 | } 77 | 78 | - unsigned int size() const 79 | + static constexpr unsigned int size()
a2edabe43261ef2859742015a53c34ee8a5d1ee3 This along with the corresponding changes in pubkey.h might be worth a separate commit.
Done, added commit "Make XOnlyPubKey act like byte container".
154 | + * * WitnessV1Taproot: TxoutType::WITNESS_V1_TAPROOT destination (P2TR) 155 | + * * WitnessUnknown: TxoutType::WITNESS_UNKNOWN destination (P2W???) 156 | * A CTxDestination is the internal data type encoded in a bitcoin address 157 | */ 158 | -using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessUnknown>; 159 | +using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessUnknown, WitnessV1Taproot>;
a2edabe43261ef2859742015a53c34ee8a5d1ee3 shouldn't we keep WitnessUnknown at the end? That would also keep it consistent with the ordering in e.g. descriptor.cpp.
I didn't do that because the descriptor code's GetOutputType depended on the exact order of elements in this variant. I've addressed that in a new commit "Avoid dependence on CTxDestination index order", and then implemented your suggestion of placing WitnessUnknown last.
241 | @@ -242,8 +242,13 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet) 242 | addressRet = hash; 243 | return true; 244 | } 245 | - case TxoutType::WITNESS_UNKNOWN: 246 | case TxoutType::WITNESS_V1_TAPROOT: { 247 | + WitnessV1Taproot tap; 248 | + std::copy(vSolutions[1].begin(), vSolutions[1].end(), tap.begin());
This raises the question: why are we putting the witness version in vSolutions? That seems to have been copied from WITNESS_UNKNOWN handling, whereas we don't do it for SegWit v0.
I don't see an explanation in e9a021d7e6a454d610a45cb9b3995f0d96a5fbb6 (I might have missed it in #19953's wall of text).
The explanation is just that this was easier, because while TxoutType did have a separation between unknown and taproot, CTxDestination did not. Making them both produce {version, program} as vSolutions was easier because it allowed handling them identically in ExtractDestination.
I've addressed this by first changing the Solver output for taproot outputs to be just {program}, like P2WPKH/P2WSH, in a new commit "c1445ee0d56e56d824bc79a0c9f1db26105ade1f", and then used that in the later commits.
442 | + BOOST_CHECK(builder.IsValid() && !builder.IsComplete()); 443 | + builder.Add(1, script_1, 0xc0); 444 | + BOOST_CHECK(builder.IsValid() && builder.IsComplete()); 445 | + builder.Finalize(key_inner); 446 | + BOOST_CHECK(builder.IsValid() && builder.IsComplete()); 447 | + BOOST_CHECK_EQUAL(EncodeDestination(builder.GetOutput()), "bc1pj6gaw944fy0xpmzzu45ugqde4rz7mqj5kj0tg8kmr5f0pjq8vnaqgynnge");
f86a68c0b1a6ed9e0c7e6f0ee81989a6129abe30: as an additional sanity check, you could generate the same same address in feature_taproot.py
wallet_taproot.py already tests address derivation against the python implementation (which is also used by feature_taproot.py, so I think that's unnecessary.
282 | + /** Return whether there were either no leaves, or the leaves form a Huffman tree. */ 283 | + bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); } 284 | + /** Compute scriptPubKey (after Finalize()). */ 285 | + WitnessV1Taproot GetOutput(); 286 | + /** Check if a list of depths is legal (will lead to IsComplete()). */ 287 | + static bool ValidDepths(const std::vector<int>& depths);
f86a68c0b1a6ed9e0c7e6f0ee81989a6129abe30: note to other reviewers: this is used in d9d928198be28923d37434a924788b284a4e3760 to sanity check the descriptor parser (and made more sense to me after reviewing the {{A,B},C} parsing code).
438 | + 439 | +TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version) 440 | +{ 441 | + assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0); 442 | + if (!IsValid()) return *this; 443 | + /* Construct NodeInfo object with leaf hash and - if desired - leaf information. */
f86a68c0b1a6ed9e0c7e6f0ee81989a6129abe30: what do you mean by "if desired - leaf information"?
That comment didn't make sense in the commit where it was in. I've moved it, and made it a bit clearer.
Reviewed down to f86a68c, will continue later...
The refactoring of consensus code in 5ecaca05a299d3da9cdfdf8e9c6860500a73587d (CheckTapTweak) deserves its own commit (which also makes the diff slightly easier to read).
Fixed the bug referred to here by @MarcoFalke, and addressed most of @Sjors's comments.
Note: if this is too much, it'd be totally reasonable to split this PR in two, splitting after "Add tr() descriptor (derivation only, no signing)". Everything up to there is preparation & descriptor derivation. Everything after is signing logic.
Being able to make watch-only taproot wallet seems like a nice natural point to split this PR.
tACK up to c08bb8badb8ab030590fe1bea160078785ecdafe
In order to test descriptors with script paths, without having signing code, it would be useful to expand getaddressinfo and have it show the TREE of scripts.
395 | @@ -386,6 +396,17 @@ bool IsValidDestination(const CTxDestination& dest) { 396 | return ret; 397 | } 398 | 399 | +void TaprootSpendData::Merge(TaprootSpendData other) 400 | +{ 401 | + if (internal_key.IsNull() && !other.internal_key.IsNull()) {
In e4c8ae471d38e878a69fa8099d75d447319f4037 "Add TaprootSpendData data structure, equivalent to script map for P2[W]SH"
Since we are expecting that the TaprootSpendData being merged is for the same scriptPubKey, I think this should assert that the internal_key and merkle_root match if both have them.
Asserting sounds dangerous, as I'd expect TaprootSpendData to at some point be untrusted data (e.g. gathered from PSBT). I agree it's a bit ugly to just prefer one over the other in case of a contradiction, and I also don't have a better solution. Would you be ok with just a TODO here?
395 | @@ -386,6 +396,17 @@ bool IsValidDestination(const CTxDestination& dest) { 396 | return ret; 397 | } 398 | 399 | +void TaprootSpendData::Merge(TaprootSpendData other) 400 | +{ 401 | + if (internal_key.IsNull() && !other.internal_key.IsNull()) { 402 | + internal_key = other.internal_key; 403 | + merkle_root = other.merkle_root;
In e4c8ae471d38e878a69fa8099d75d447319f4037 "Add TaprootSpendData data structure, equivalent to script map for P2[W]SH"
Should this merkle_root be guarded with its own if instead being combined with the internal_key? It looks like in the current usage it doesn't matter, but perhaps in the future it might?
Done.
283 | @@ -261,6 +284,7 @@ class TaprootBuilder 284 | 285 | XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing. 286 | XOnlyPubKey m_output_key; //!< The output key, computed when finalizing. */ 287 | + bool m_parity; //!< The tweak parity, computed when finalizing. */
In e4c8ae471d38e878a69fa8099d75d447319f4037 "Add TaprootSpendData data structure, equivalent to script map for P2[W]SH"
nit:, extra */
bool m_parity; //!< The tweak parity, computed when finalizing. */
bool m_parity; //!< The tweak parity, computed when finalizing.
Done. Also realigned.
321 | + unsigned char sig64[64]; 322 | + 323 | + // Run the untweaked test vectors above, comparing with exact expected signature. 324 | + CKey key; 325 | + key.Set(sec.begin(), sec.end(), true); 326 | + XOnlyPubKey pubkey(key.GetPubKey());
In ebf44e081ba0ef7b8810497dee47717bb661cbdb "Add CKey::SignSchnorr function for BIP 340/341 signing"
Why not compare the pubkey against the pubkeys specified in the BIP 340 test vectors?
Done.
248 | + } 249 | + } 250 | + if (!input.witness_utxo.IsNull()) { 251 | + utxos[idx] = input.witness_utxo; 252 | + continue; 253 | + }
In 8d073d0afe285bd04542907428298d377f49c8f9 "Construct and use PrecomputedTransactionData in PSBT signing"
GetInputUTXO does all of this already, so I think you can just use that instead of reimplementing the utxo fetching. If you need to do the hash checking, it would probably be worthwhile to implement that in GetInputUTXO too.
Changed to use GetInputUTXO. I've added a commit to add the prevout hash check to GetInputUTXO itself.
232 | +{ 233 | + const CMutableTransaction& tx = *psbt.tx; 234 | + bool have_all_spent_outputs = true; 235 | + std::vector<CTxOut> utxos(tx.vin.size()); 236 | + for (size_t idx = 0; idx < tx.vin.size(); ++idx) { 237 | + if (psbt.inputs.size() <= idx) {
In 8d073d0afe285bd04542907428298d377f49c8f9 "Construct and use PrecomputedTransactionData in PSBT signing"
This case shouldn't happen because every input in the tx must have a corresponding PSBTInput, even if it is empty. So I think this should be an assert as it would be a bug.
Gone by rewriting.
156 | +{ 157 | + auto lookup_key = std::make_pair(pubkey, leaf_hash); 158 | + auto it = sigdata.taproot_script_sigs.find(lookup_key); 159 | + if (it != sigdata.taproot_script_sigs.end()) { 160 | + sig_out = it->second; 161 | + }
In ea07a01b0cf7256304b17508debf74d94cccdac7 "Basic Taproot signing logic in script/sign.cpp"
Can you explain what this is doing and why?
It's the equivalent of SignatureData::signatures, but for Taproot/Schnorr signatures. They're not indexed by CKeyId, but by full (untweaked) pubkey and leaf they occur in.
This is redundant for now, as there is no multiparty signing whatsoever, and no way of communicating partial signatures (needs PSBT extension), but this is pretty much what it would look like. I could drop it for this PR.
Since #22166 uses "Add TaprootSpendData data structure, equivalent to script map for P2[W]SH" from here but with scripts as a multimap, in the interest of reducing future merge conflicts, I think this PR should use the same commit and use the multimap too. I expect that the change to using a multimap might cause some problems with the later commits in this PR.
Addressed most of your comments, and also updated the TaprootSpendData commit to use multiset semantics. Instead of using multiset<key, control_block>, I've changed it to map<key, set<control_block>>, which also has multiset semantics that should be compatible with #22166's inference code, but also with the signing logic in this PR (which should prefer the smallest control block for a given script if multiple are available).
ACK 4ad2a1d4adfcff715fed3ec37433ffd507c98b84
I have a few simple questions, please help me understand.
134 | + * aux. 135 | + * 136 | + * When merkle_root is not nullptr, this results in a signature with a modified key as 137 | + * specified in BIP341: 138 | + * - If merkle_root->IsNull(): key + H_TapTweak(pubkey)*G 139 | + * - Otherwise: key + H_TapTweak(pubkey || *merkle_root)
* - Otherwise: key + H_TapTweak(pubkey || *merkle_root)*G
It's referring to the operation applied to the private key, not the public one.
re-ACK c69ad7e8097fb6a6cfdd28f135e666ba40405b61
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.
This provides a means to pass in a PrecomputedTransactionData object to
the MutableTransactionSignatureCreator, allowing the prevout data to be
passed into the signature hashers. It is also more efficient.
At verification time, the to be precomputed data can be inferred from
the transaction itself. For signing, the necessary witnesses don't
exist yet, so just permit precomputing everything in that case.
For non-Taproot signatures, this is interpreted as SIGHASH_ALL.
Rebased.
re-ACK 458a345b0590fd2fa04c7d8d70beb8d57e34bbc8
I'll try to review this today. Having this feature in the signet / testnet wallet makes it easier for people to test taproot before it activates, and potentially find problems (bugs, many eyes, shallow, etc). So it seems worth merging even slightly after the feature freeze.
Concept ACK, Approach ACK. Updated syntax choice makes sense to me under the readability assumption that use cases that need more than say 2 levels will be rarer. Ignoring readability, the updated syntax choice seems superior due to arguments given.
Agree with @Sjors on importance of getting this in for 22.0. Two weeks for any bug fixes from today should be ok and protections in place (e.g. #22156) regardless to prevent users from spending mainnet Taproot outputs pre-activation (November).
202 | + if (sigdata.taproot_key_path_sig.size() == 0) { 203 | + if (creator.CreateSchnorrSig(provider, sig, spenddata.internal_key, nullptr, &spenddata.merkle_root, SigVersion::TAPROOT)) { 204 | + sigdata.taproot_key_path_sig = sig; 205 | + } 206 | + } 207 | + if (sigdata.taproot_key_path_sig.size()) {
nit: this could go before the block with sigdata.taproot_key_path_sig.size() == 0 to return early and then that other block would not need that other if statement
I tried this for a bit, but I don't find the result cleaner.
51 | @@ -50,11 +52,13 @@ struct FlatSigningProvider final : public SigningProvider 52 | std::map<CKeyID, CPubKey> pubkeys; 53 | std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> origins; 54 | std::map<CKeyID, CKey> keys; 55 | + std::map<XOnlyPubKey, TaprootSpendData> tr_spenddata; /** Map from output key to spend data. */
nit: m_tr_spenddata?
It's a struct, not a class, so the developer notes don't require that (it's inconsistently applied through the codebase, in some cases using m_ prefixes for struct members too, but I don't think that's enough reason to do so here).
238 | struct NodeInfo
239 | {
240 | /** Merkle hash of this node. */
241 | 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. */
nit: reads a bit strange but maybe I am not reading it right. I would write it as "The merkle_branch field of each are the partners to get to this node."
39 | @@ -40,9 +40,11 @@ class MutableTransactionSignatureCreator : public BaseSignatureCreator { 40 | int nHashType; 41 | CAmount amount; 42 | const MutableTransactionSignatureChecker checker; 43 | + const PrecomputedTransactionData* m_txdata; 44 | 45 | public: 46 | MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, int nHashTypeIn = SIGHASH_ALL); 47 | + MutableTransactionSignatureCreator(const CMutableTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData* txdata, int nHashTypeIn = SIGHASH_ALL);
Why isn't SIGHASH_DEFAULT the default here now as well?
649 | + } 650 | + if (have_all_spent_outputs) { 651 | + txdata.Init(txConst, std::move(spent_outputs), true); 652 | + } else { 653 | + txdata.Init(txConst, {}, true); 654 | + }
nit: I think this loop could be simplified a little
for (CTxIn& txin : mtx.vin) {
auto coin = coins.find(txin.prevout);
if (coin == coins.end() || coin->second.IsSpent()) {
txdata.Init(txConst, {}, true);
break;
}
spent_outputs.emplace_back(CTxOut(coin->second.out.nValue, coin->second.out.scriptPubKey));
}
if (mtx.vin.size() == spent_outputs.size()) {
txdata.Init(txConst, std::move(spent_outputs), true);
}
55 | +{ 56 | + assert(sigversion == SigVersion::TAPROOT || sigversion == SigVersion::TAPSCRIPT); 57 | + 58 | + CKey key; 59 | + { 60 | + // For now, use the old full pubkey-based key derivation logic. As it indexed by
As it is indexed by
Code review ACK 458a345b0590fd2fa04c7d8d70beb8d57e34bbc8
I don't consider any of my comments blocking. Will test over the next days.
1430 | @@ -1431,9 +1431,9 @@ void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent 1431 | } 1432 | 1433 | // Determine which precomputation-impacting features this transaction uses. 1434 | - bool uses_bip143_segwit = false; 1435 | - bool uses_bip341_taproot = false; 1436 | - for (size_t inpos = 0; inpos < txTo.vin.size(); ++inpos) { 1437 | + bool uses_bip143_segwit = force; 1438 | + bool uses_bip341_taproot = force; 1439 | + for (size_t inpos = 0; inpos < txTo.vin.size() && !(uses_bip143_segwit && uses_bip341_taproot); ++inpos) {
ce9353164bdb6215a62b2b6dcb2121d331796f60: suggest moving if (uses_bip341_taproot && uses_bip143_segwit) break; // No need to scan further if we already need all. up to the start of the loop instead.
In the commit message maybe replace "just permit precomputing" with "just precompute".
Too late.
1477 | @@ -1478,8 +1478,8 @@ PrecomputedTransactionData::PrecomputedTransactionData(const T& txTo) 1478 | } 1479 | 1480 | // explicit instantiation 1481 | -template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut>&& spent_outputs); 1482 | -template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut>&& spent_outputs); 1483 | +template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut>&& spent_outputs, bool force);
Suggested comment:
// * [@param](/bitcoin-bitcoin/contributor/param/)[in] force Precompute data for both bip341 taproot and bip143 segwit signatures regardless of the actual inputs.
ACK 458a345b0590fd2fa04c7d8d70beb8d57e34bbc8
127 | @@ -128,6 +128,18 @@ class CKey 128 | */ 129 | bool SignCompact(const uint256& hash, std::vector<unsigned char>& vchSig) const; 130 | 131 | + /** 132 | + * Create a BIP-340 Schnorr signature, for the xonly-pubkey corresponding to *this, 133 | + * optionally tweaked by *merkle_root. Additional nonce entropy can be provided through 134 | + * aux. 135 | + * 136 | + * When merkle_root is not nullptr, this results in a signature with a modified key as
What's the use case for non-tweaked signatures?
nit: The difference between merkle_root == nullptr and merkel_root->IsNull() is subtle enough that
one might be mistaken, especially when passing the aux parameter and not reading the comments closely. Could this be a potential problem in the future?
Signatures with OP_CHECKSIG and friends aren't tweaked; only key-path signatures are.
So we do need both a way to ask for untweaked, and for tweaked with nothing. I agree it's confusing, though we need a way to ask for both. Getting it wrong is exceedingly likely to cause validation failures, though.
Yikes, I missed that subtlety too. In #22275 you could expand the comment bit, e.g.:
* When merkle_root is nullptr, as distinct from merkle_root->IsNull(), the signature is not tweaked.
* This is the case for e.g. OP_CHECKSIG in a tapscript.
* For key-path signatures on the other hand the signature is always tweaked (merkle_root is not nullptr) as follows:
two comments
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));
On macOS Mojave 10.14.6 (18G9216) system clang fails to compile this line due to the lack of std::set::merge support.
$ clang --version
Apple LLVM version 10.0.1 (clang-1001.0.46.4)
Target: x86_64-apple-darwin18.7.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin
See: https://stackoverflow.com/questions/50444908/clang-6-not-supporting-unordered-mapmerge
Reported by @S3RK.
I presume this would also make it harder to compile on https://packages.debian.org/stretch/gcc
In theory there is https://packages.debian.org/stretch/clang-7, but I don't think anyone was able to compile master with system packages on stretch recently.
Confirmed (for fun) that the issue exists with libc++7.
# make V=1
Making all in src
make[1]: Entering directory '/bitcoin/src'
make[2]: Entering directory '/bitcoin/src'
make[3]: Entering directory '/bitcoin'
make[3]: Leaving directory '/bitcoin'
/usr/bin/ccache clang++-7 -stdlib=libc++ -std=c++17 -DHAVE_CONFIG_H -I. -I../src/config -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=2 -I. -I./secp256k1/include -DBOOST_SP_USE_STD_ATOMIC -DBOOST_AC_USE_STD_ATOMIC -I/usr/include -I./leveldb/include -I./leveldb/helpers/memenv -I./univalue/include -DHAVE_BUILD_INFO -D__STDC_FORMAT_MACROS -DPROVIDE_FUZZ_MAIN_FUNCTION -fdebug-prefix-map=/bitcoin/src=. -Wstack-protector -fstack-protector-all -Wall -Wextra -Wgnu -Wformat -Wformat-security -Wvla -Wshadow-field -Wswitch -Wthread-safety -Wrange-loop-analysis -Wredundant-decls -Wunused-variable -Wunused-member-function -Wdate-time -Wconditional-uninitialized -Wsign-compare -Woverloaded-virtual -Wunreachable-code-loop-increment -Wno-unused-parameter -Wno-self-assign -Wno-unused-local-typedef -Wno-implicit-fallthrough -fPIE -g -O2 -MT script/libbitcoin_common_a-standard.o -MD -MP -MF script/.deps/libbitcoin_common_a-standard.Tpo -c -o script/libbitcoin_common_a-standard.o `test -f 'script/standard.cpp' || echo './'`script/standard.cpp
script/standard.cpp:410:22: error: no member named 'merge' in 'std::__1::set<std::__1::vector<unsigned char, std::__1::allocator<unsigned char> >, ShortestVectorFirstComparator, std::__1::allocator<std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > > >'
scripts[key].merge(std::move(control_blocks));
~~~~~~~~~~~~ ^
1 error generated.
Makefile:7756: recipe for target 'script/libbitcoin_common_a-standard.o' failed
make[2]: *** [script/libbitcoin_common_a-standard.o] Error 1
make[2]: Leaving directory '/bitcoin/src'
Makefile:15489: recipe for target 'all-recursive' failed
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory '/bitcoin/src'
Makefile:820: recipe for target 'all-recursive' failed
make: *** [all-recursive] Error 1
<!-- export DEBIAN_FRONTEND=noninteractive && apt update && apt install curl wget htop git vim ccache -y && git clone https://github.com/bitcoin/bitcoin.git && cd bitcoin && git checkout master && apt install build-essential libtool autotools-dev automake pkg-config bsdmainutils python3-zmq libevent-dev libboost-system-dev libboost-filesystem-dev libboost-test-dev libboost-thread-dev libsqlite3-dev libdb++-dev -y && ./autogen.sh && apt install libqt5gui5 libqt5core5a libqt5dbus5 qttools5-dev qttools5-dev-tools -y && apt install clang-7 llvm-7 libc++abi-7-dev libc++-7-dev -y && ./configure CC=clang-7 CXX="clang++-7 -stdlib=libc++" --with-incompatible-bdb && make -j $(nproc) src/bitcoind
Milestone
22.0