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.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
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.
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.
+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.
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?
I see.
bikeshed: I think something like this could be a little clearer:
0// This function finds the end of the current expression and returns pair(expr_span, rest_span)
1// trailing comma is included in the expr_span, e.g.
2// `<expr A>,<expr B>` would return `<expr A>,` `<expr B>`
3std::pair<Span<const char>, Span<const char>> Expr(const Span<const char>& sp)
4{
5 size_t left = 0;
6 size_t right = 0;
7 auto it = sp.begin();
8 while (it != sp.end()) {
9 switch (*it) {
10 case '(':
11 case '{':
12 ++left;
13 break;
14 case '}':
15 case ')':
16 ++right;
17 break;
18 }
19 bool balanced = right == left;
20 // completed a Expr by matching nonzero left/right
21 if (balanced && right > 0) break;
22 // we have a balanced term as a comma separated entity
23 if (balanced && *it == ',') break;
24 ++it;
25 }
26 return std::make_pair(sp.first(it-sp.begin), sp.subspan(it-sp.begin()));
27}
That said it seem peculiar to me that , is left on the string – maybe preferable to trim it here?
1172+ return nullptr;
1173+ }
1174+ continue;
1175+ }
1176+ auto sarg = Expr(expr);
1177+ auto subdesc = ParseScript(key_exp_index, sarg, ParseScriptContext::P2TR, out, error);
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:
0if (counts.size() && counts.back() == false)
or something like
0if (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.
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);
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)
Yeah, I agree with that 100%. What I was thinking was a vec 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:
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.
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);
std::make_unique in new code.
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.
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.
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.
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:
00200000000010114a5df5cf5084ea003c2f021c4e22846238a61c89894fa786e556395048ed40c0000000000fdffffff0292a0070000000000225120a287e30feacc24a25a9a3e689ad0107223cb247fb9a14880cddf3e62f1453a6420a1070000000000160014bf15b210d9f53e5c7b002fe904af042098706c3a03406c11b79f9a417f9702a6117e3bb170956ece09af6b584b2d92e1e0e5cfcad725250c91e29db77751af36970c0e5676622cfcf6fb1c81a316dfcd349b1ea59d412220d0586a7eba2e92a38f31ba8a7d82c05b9bb101bf3a649f205bd8e1df7c428b6eac21c07a35becbfeccf3ed5367ff117681497d040e6996eeae3dd21acb123e8525729d227b0000
@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.
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;
GetTaprootSpendData?
output_key).
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());
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 {};
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?
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).
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.
0 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()
pubkey.h might be worth a separate commit.
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>;
WitnessUnknown at the end? That would also keep it consistent with the ordering in e.g. descriptor.cpp.
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");
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);
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. */
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.
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?
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 */
0 bool m_parity; //!< The tweak parity, computed when finalizing. */
1 bool m_parity; //!< The tweak parity, computed when finalizing.
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?
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.
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.
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.
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).
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)
0 * - Otherwise: key + H_TapTweak(pubkey || *merkle_root)*G
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.
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()) {
sigdata.taproot_key_path_sig.size() == 0 to return early and then that other block would not need that other if statement
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. */
m_tr_spenddata?
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. */
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);
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
0 for (CTxIn& txin : mtx.vin) {
1 auto coin = coins.find(txin.prevout);
2 if (coin == coins.end() || coin->second.IsSpent()) {
3 txdata.Init(txConst, {}, true);
4 break;
5 }
6 spent_outputs.emplace_back(CTxOut(coin->second.out.nValue, coin->second.out.scriptPubKey));
7 }
8 if (mtx.vin.size() == spent_outputs.size()) {
9 txdata.Init(txConst, std::move(spent_outputs), true);
10 }
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
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”.
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:
0// * [@param](/bitcoin-bitcoin/contributor/param/)[in] force Precompute data for both bip341 taproot and bip143 segwit signatures regardless of the actual inputs.
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.:
0* When merkle_root is nullptr, as distinct from merkle_root->IsNull(), the signature is not tweaked.
1* This is the case for e.g. OP_CHECKSIG in a tapscript.
2* For key-path signatures on the other hand the signature is always tweaked (merkle_root is not nullptr) as follows:
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.
0$ clang --version
1Apple LLVM version 10.0.1 (clang-1001.0.46.4)
2Target: x86_64-apple-darwin18.7.0
3Thread model: posix
4InstalledDir: /Library/Developer/CommandLineTools/usr/bin
See: https://stackoverflow.com/questions/50444908/clang-6-not-supporting-unordered-mapmerge
Reported by @S3RK.
Confirmed (for fun) that the issue exists with libc++7.
0# make V=1
1Making all in src
2make[1]: Entering directory '/bitcoin/src'
3make[2]: Entering directory '/bitcoin/src'
4make[3]: Entering directory '/bitcoin'
5make[3]: Leaving directory '/bitcoin'
6/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
7script/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> > > >'
8 scripts[key].merge(std::move(control_blocks));
9 ~~~~~~~~~~~~ ^
101 error generated.
11Makefile:7756: recipe for target 'script/libbitcoin_common_a-standard.o' failed
12make[2]: *** [script/libbitcoin_common_a-standard.o] Error 1
13make[2]: Leaving directory '/bitcoin/src'
14Makefile:15489: recipe for target 'all-recursive' failed
15make[1]: *** [all-recursive] Error 1
16make[1]: Leaving directory '/bitcoin/src'
17Makefile:820: recipe for target 'all-recursive' failed
18make: *** [all-recursive] Error 1
Labels
Wallet
RPC/REST/ZMQ
Descriptors
Milestone
22.0