Merge bitcoin/bitcoin#22051: Basic Taproot derivation support for descriptors

2667366aaa69447a9de4d819669d254a5ebd4d4b tests: check derivation of P2TR (Pieter Wuille)
7cedafc5412857404e9a6c3450b100cb8ee4081a Add tr() descriptor (derivation only, no signing) (Pieter Wuille)
90fcac365e1616779b40a69736428435df75fdf2 Add TaprootBuilder class (Pieter Wuille)
5f6cc8daa83700d1c949d968a5cf0d935be337b7 Add XOnlyPubKey::CreateTapTweak (Pieter Wuille)
2fbfb1becb3c0c109cd7c30b245b51da22039932 Make consensus checking of tweaks in pubkey.* Taproot-specific (Pieter Wuille)
a4bf84039c00b196b87f969acf6369d72c56ab46 Separate WitnessV1Taproot variant in CTxDestination (Pieter Wuille)
41839bdb89b3777ece2318877b9c7921ecca2472 Avoid dependence on CTxDestination index order (Pieter Wuille)
31df02a07091dbd5e0b315c8e5695e808f3a5505 Change Solver() output for WITNESS_V1_TAPROOT (Pieter Wuille)
4b1cc08f9f94a1e6e1ecba6b97f99b73fb513872 Make XOnlyPubKey act like byte container (Pieter Wuille)

Pull request description:

  This is a subset of #21365, to aide review.

  This adds support `tr(KEY)` or `tr(KEY,SCRIPT)` or `tr(KEY,{{S1,{{S2,S3},...}},...})` descriptors, describing Taproot outputs with specified internal key, and optionally any number of scripts, in nested groups of 2 inside `{`/`}` if there are more than one. While it permits importing `tr(KEY)`, anything beyond that is just laying foundations for more features later.

  Missing:
  * Signing support (see #21365)
  * Support for more interesting scripts inside the tree (only `pk(KEY)` is supported for now). In particular, a multisig policy based on the new `OP_CHECKSIGADD` opcode would be very useful.
  * Inferring `tr()` descriptors from outputs (given sufficient information).
  * `getaddressinfo` support.
  * MuSig support. Standardizing that is still an ongoing effort, and is generally kind of useless without corresponding PSBT support.
  * Convenient ways of constructing descriptors without spendable internal key (especially ones that arent't trivially recognizable as such).

ACKs for top commit:
  Sjors:
    utACK 2667366 (based on https://github.com/bitcoin/bitcoin/pull/21365#issuecomment-846945215 review, plus the new functional test)
  achow101:
    Code Review ACK 2667366aaa69447a9de4d819669d254a5ebd4d4b
  lsilva01:
    Tested ACK https://github.com/bitcoin/bitcoin/pull/22051/commits/2667366aaa69447a9de4d819669d254a5ebd4d4b
  meshcollider:
    utACK 2667366aaa69447a9de4d819669d254a5ebd4d4b

Tree-SHA512: 61046fef22c561228338cb178422f0b782ef6587ec8208d3ce2bd07afcff29a664b54b35c6b01226eb70b6540b43f6dd245043d09aa6cb6db1381b6042667e75

1 files changed, 70 insertions, 3 deletions

diff --git a/src/test/script_standard_tests.cpp b/src/test/script_standard_tests.cpp
index 44fbfa5970..a01d3fa03a 100644
--- a/src/test/script_standard_tests.cpp
+++ b/src/test/script_standard_tests.cpp
@@ -3,10 +3,12 @@
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <key.h>
+#include <key_io.h>
 #include <script/script.h>
 #include <script/signingprovider.h>
 #include <script/standard.h>
 #include <test/util/setup_common.h>
+#include <util/strencodings.h>
 
 #include <boost/test/unit_test.hpp>
 
@@ -111,9 +113,8 @@ BOOST_AUTO_TEST_CASE(script_standard_Solver_success)
     s.clear();
     s << OP_1 << ToByteVector(uint256::ZERO);
     BOOST_CHECK_EQUAL(Solver(s, solutions), TxoutType::WITNESS_V1_TAPROOT);
-    BOOST_CHECK_EQUAL(solutions.size(), 2U);
-    BOOST_CHECK(solutions[0] == std::vector<unsigned char>{1});
-    BOOST_CHECK(solutions[1] == ToByteVector(uint256::ZERO));
+    BOOST_CHECK_EQUAL(solutions.size(), 1U);
+    BOOST_CHECK(solutions[0] == ToByteVector(uint256::ZERO));
 
     // TxoutType::WITNESS_UNKNOWN
     s.clear();
@@ -379,4 +380,70 @@ BOOST_AUTO_TEST_CASE(script_standard_GetScriptFor_)
     BOOST_CHECK(result == expected);
 }
 
+BOOST_AUTO_TEST_CASE(script_standard_taproot_builder)
+{
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,1}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,0,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,0,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,0,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,1,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,1,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,1,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,2,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,2,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,2,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,0,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,0,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,0,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,1,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,1,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,1,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,2,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,2,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,2,2}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,0,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,0,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,0,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,1,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,1,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,1,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2,1}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2,2,3,4,5,6,7,8,9,10,11,12,14,14,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,31,31,31,31,31,31,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,128}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({128,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114,113,112,111,110,109,108,107,106,105,104,103,102,101,100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({129,129,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114,113,112,111,110,109,108,107,106,105,104,103,102,101,100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}), false);
+
+    XOnlyPubKey key_inner{ParseHex("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798")};
+    XOnlyPubKey key_1{ParseHex("c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5")};
+    XOnlyPubKey key_2{ParseHex("f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9")};
+    CScript script_1 = CScript() << ToByteVector(key_1) << OP_CHECKSIG;
+    CScript script_2 = CScript() << ToByteVector(key_2) << OP_CHECKSIG;
+    uint256 hash_3 = uint256S("31fe7061656bea2a36aa60a2f7ef940578049273746935d296426dc0afd86b68");
+
+    TaprootBuilder builder;
+    BOOST_CHECK(builder.IsValid() && builder.IsComplete());
+    builder.Add(2, script_2, 0xc0);
+    BOOST_CHECK(builder.IsValid() && !builder.IsComplete());
+    builder.AddOmitted(2, hash_3);
+    BOOST_CHECK(builder.IsValid() && !builder.IsComplete());
+    builder.Add(1, script_1, 0xc0);
+    BOOST_CHECK(builder.IsValid() && builder.IsComplete());
+    builder.Finalize(key_inner);
+    BOOST_CHECK(builder.IsValid() && builder.IsComplete());
+    BOOST_CHECK_EQUAL(EncodeDestination(builder.GetOutput()), "bc1pj6gaw944fy0xpmzzu45ugqde4rz7mqj5kj0tg8kmr5f0pjq8vnaqgynnge");
+}
+
 BOOST_AUTO_TEST_SUITE_END()