From 31df02a07091dbd5e0b315c8e5695e808f3a5505 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 23 May 2021 18:00:18 -0700
Subject: Change Solver() output for WITNESS_V1_TAPROOT

This is just a small simplification to prepare for the follow-up instruction
of a CTxDestination variant for taproot outputs.

In the old code, WITNESS_V1_TAPROOT and WITNESS_UNKNOWN both produced
{version, program} as Solver() output. Change this so that WITNESS_V1_TAPROOT
produces just {program}, like WITNESS_V0_* do.
---
 src/script/standard.cpp | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

(limited to 'src/script/standard.cpp')

diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 364fac3c84..540aa0f2d9 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -155,15 +155,14 @@ TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned c
     std::vector<unsigned char> witnessprogram;
     if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
         if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) {
-            vSolutionsRet.push_back(witnessprogram);
+            vSolutionsRet.push_back(std::move(witnessprogram));
             return TxoutType::WITNESS_V0_KEYHASH;
         }
         if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
-            vSolutionsRet.push_back(witnessprogram);
+            vSolutionsRet.push_back(std::move(witnessprogram));
             return TxoutType::WITNESS_V0_SCRIPTHASH;
         }
         if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
-            vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion});
             vSolutionsRet.push_back(std::move(witnessprogram));
             return TxoutType::WITNESS_V1_TAPROOT;
         }
@@ -242,8 +241,17 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
         addressRet = hash;
         return true;
     }
-    case TxoutType::WITNESS_UNKNOWN:
     case TxoutType::WITNESS_V1_TAPROOT: {
+        /* For now, no WitnessV1Taproot variant in CTxDestination exists, so map
+         * this to WitnessUnknown. */
+        WitnessUnknown unk;
+        unk.version = 1;
+        std::copy(vSolutions[0].begin(), vSolutions[0].end(), unk.program);
+        unk.length = vSolutions[0].size();
+        addressRet = unk;
+        return true;
+    }
+    case TxoutType::WITNESS_UNKNOWN: {
         WitnessUnknown unk;
         unk.version = vSolutions[0][0];
         std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.program);
-- 
cgit v1.2.3


From a4bf84039c00b196b87f969acf6369d72c56ab46 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 23 May 2021 17:38:40 -0700
Subject: Separate WitnessV1Taproot variant in CTxDestination

---
 src/script/standard.cpp | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

(limited to 'src/script/standard.cpp')

diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 540aa0f2d9..0a233b550a 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -242,13 +242,9 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
         return true;
     }
     case TxoutType::WITNESS_V1_TAPROOT: {
-        /* For now, no WitnessV1Taproot variant in CTxDestination exists, so map
-         * this to WitnessUnknown. */
-        WitnessUnknown unk;
-        unk.version = 1;
-        std::copy(vSolutions[0].begin(), vSolutions[0].end(), unk.program);
-        unk.length = vSolutions[0].size();
-        addressRet = unk;
+        WitnessV1Taproot tap;
+        std::copy(vSolutions[0].begin(), vSolutions[0].end(), tap.begin());
+        addressRet = tap;
         return true;
     }
     case TxoutType::WITNESS_UNKNOWN: {
@@ -337,6 +333,11 @@ public:
         return CScript() << OP_0 << ToByteVector(id);
     }
 
+    CScript operator()(const WitnessV1Taproot& tap) const
+    {
+        return CScript() << OP_1 << ToByteVector(tap);
+    }
+
     CScript operator()(const WitnessUnknown& id) const
     {
         return CScript() << CScript::EncodeOP_N(id.version) << std::vector<unsigned char>(id.program, id.program + id.length);
-- 
cgit v1.2.3


From 90fcac365e1616779b40a69736428435df75fdf2 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Mon, 1 Feb 2021 18:53:24 -0800
Subject: Add TaprootBuilder class

This class functions as a utility for building taproot outputs, from
internal key and script leaves.
---
 src/script/standard.cpp | 99 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 99 insertions(+)

(limited to 'src/script/standard.cpp')

diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 0a233b550a..a4b11cc0a9 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -6,8 +6,11 @@
 #include <script/standard.h>
 
 #include <crypto/sha256.h>
+#include <hash.h>
 #include <pubkey.h>
+#include <script/interpreter.h>
 #include <script/script.h>
+#include <util/strencodings.h>
 
 #include <string>
 
@@ -370,3 +373,99 @@ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
 bool IsValidDestination(const CTxDestination& dest) {
     return dest.index() != 0;
 }
+
+/*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b)
+{
+    NodeInfo ret;
+    /* Lexicographically sort a and b's hash, and compute parent hash. */
+    if (a.hash < b.hash) {
+        ret.hash = (CHashWriter(HASHER_TAPBRANCH) << a.hash << b.hash).GetSHA256();
+    } else {
+        ret.hash = (CHashWriter(HASHER_TAPBRANCH) << b.hash << a.hash).GetSHA256();
+    }
+    return ret;
+}
+
+void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
+{
+    assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
+    /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
+     * so would mean the Add() invocations do not correspond to a DFS traversal of a
+     * binary tree. */
+    if ((size_t)depth + 1 < m_branch.size()) {
+        m_valid = false;
+        return;
+    }
+    /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
+     * The 'node' variable is overwritten here with the newly combined node. */
+    while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
+        node = Combine(std::move(node), std::move(*m_branch[depth]));
+        m_branch.pop_back();
+        if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
+        --depth;
+    }
+    if (m_valid) {
+        /* Make sure the branch is big enough to place the new node. */
+        if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
+        assert(!m_branch[depth].has_value());
+        m_branch[depth] = std::move(node);
+    }
+}
+
+/*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
+{
+    std::vector<bool> branch;
+    for (int depth : depths) {
+        // This inner loop corresponds to effectively the same logic on branch
+        // as what Insert() performs on the m_branch variable. Instead of
+        // storing a NodeInfo object, just remember whether or not there is one
+        // at that depth.
+        if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
+        if ((size_t)depth + 1 < branch.size()) return false;
+        while (branch.size() > (size_t)depth && branch[depth]) {
+            branch.pop_back();
+            if (depth == 0) return false;
+            --depth;
+        }
+        if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
+        assert(!branch[depth]);
+        branch[depth] = true;
+    }
+    // And this check corresponds to the IsComplete() check on m_branch.
+    return branch.size() == 0 || (branch.size() == 1 && branch[0]);
+}
+
+TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version)
+{
+    assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
+    if (!IsValid()) return *this;
+    /* Construct NodeInfo object with leaf hash. */
+    NodeInfo node;
+    node.hash = (CHashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256();
+    /* Insert into the branch. */
+    Insert(std::move(node), depth);
+    return *this;
+}
+
+TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash)
+{
+    if (!IsValid()) return *this;
+    /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
+    NodeInfo node;
+    node.hash = hash;
+    Insert(std::move(node), depth);
+    return *this;
+}
+
+TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
+{
+    /* Can only call this function when IsComplete() is true. */
+    assert(IsComplete());
+    m_internal_key = internal_key;
+    auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
+    assert(ret.has_value());
+    std::tie(m_output_key, std::ignore) = *ret;
+    return *this;
+}
+
+WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; }
-- 
cgit v1.2.3