Merge bitcoin/bitcoin#30955: Mining interface: getCoinbaseMerklePath() and submitSolution()

525e9dcba0b8c6744bcd3725864f39786afc8ed5 Add submitSolution to BlockTemplate interface (Sjors Provoost)
47b4875ef050c4a41bd04398021af8d605415cab Add getCoinbaseMerklePath() to Mining interface (Sjors Provoost)
63d6ad7c89cd682f6e779968c4861ea085058356 Move BlockMerkleBranch back to merkle.{h,cpp} (Sjors Provoost)

Pull request description:

  The new `BlockTemplate` interface introduced in #30440 allows for a more efficient way for a miner to submit the block solution. Instead of having the send the full block, it only needs to provide the nonce, timestamp, version fields and coinbase transaction.

  This PR introduces `submitSolution()` for that. It's currently unused.

  #29432 and https://github.com/Sjors/bitcoin/pull/48 use it to process the Stratum v2 message [SubmitSolution](https://github.com/stratum-mining/sv2-spec/blob/main/07-Template-Distribution-Protocol.md#77-submitsolution-client---server). The method should be sufficiently generic to work with alternative mining protocols (none exist that I'm aware off).

  This PR also introduces `getCoinbaseMerklePath()`, which is needed in Stratum v2 to construct the `merkle_path` field of the `NewTemplate` message (see [spec](https://github.com/stratum-mining/sv2-spec/blob/main/07-Template-Distribution-Protocol.md#72-newtemplate-server---client)). The coinbase merkle path is also used in Stratum "v1", see e.g. https://bitcoin.stackexchange.com/questions/109820/questions-on-merkle-root-hashing-for-stratum-pools

  This last function uses `BlockMerkleBranch` which was moved to the test code in #13191. The reason back then for moving it was that it was no longer used. This PR moves it back.

  This PR does not change behaviour since both methods are unused.

ACKs for top commit:
  achow101:
    ACK 525e9dcba0b8c6744bcd3725864f39786afc8ed5
  itornaza:
    Code review ACK 525e9dcba0b8c6744bcd3725864f39786afc8ed5
  tdb3:
    Code review and light test ACK 525e9dcba0b8c6744bcd3725864f39786afc8ed5
  ryanofsky:
    Code review ACK 525e9dcba0b8c6744bcd3725864f39786afc8ed5. Left minor suggestions but none are important, and looks like this could be merged as-is

Tree-SHA512: 2a6a8f5d409ff4926643193cb67702240c7c687615414371e53383d2c13c485807f65e21e8ed98515b5456eca3d9fca13cec04675814a4081467d88b849c5653

6 files changed, 162 insertions, 106 deletions

diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
index af01902c92..dc32f0ab80 100644
--- a/src/consensus/merkle.cpp
+++ b/src/consensus/merkle.cpp
@@ -83,3 +83,106 @@ uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
     return ComputeMerkleRoot(std::move(leaves), mutated);
 }
 
+/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
+static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
+    if (pbranch) pbranch->clear();
+    if (leaves.size() == 0) {
+        if (pmutated) *pmutated = false;
+        if (proot) *proot = uint256();
+        return;
+    }
+    bool mutated = false;
+    // count is the number of leaves processed so far.
+    uint32_t count = 0;
+    // inner is an array of eagerly computed subtree hashes, indexed by tree
+    // level (0 being the leaves).
+    // For example, when count is 25 (11001 in binary), inner[4] is the hash of
+    // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
+    // the last leaf. The other inner entries are undefined.
+    uint256 inner[32];
+    // Which position in inner is a hash that depends on the matching leaf.
+    int matchlevel = -1;
+    // First process all leaves into 'inner' values.
+    while (count < leaves.size()) {
+        uint256 h = leaves[count];
+        bool matchh = count == branchpos;
+        count++;
+        int level;
+        // For each of the lower bits in count that are 0, do 1 step. Each
+        // corresponds to an inner value that existed before processing the
+        // current leaf, and each needs a hash to combine it.
+        for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
+            if (pbranch) {
+                if (matchh) {
+                    pbranch->push_back(inner[level]);
+                } else if (matchlevel == level) {
+                    pbranch->push_back(h);
+                    matchh = true;
+                }
+            }
+            mutated |= (inner[level] == h);
+            h = Hash(inner[level], h);
+        }
+        // Store the resulting hash at inner position level.
+        inner[level] = h;
+        if (matchh) {
+            matchlevel = level;
+        }
+    }
+    // Do a final 'sweep' over the rightmost branch of the tree to process
+    // odd levels, and reduce everything to a single top value.
+    // Level is the level (counted from the bottom) up to which we've sweeped.
+    int level = 0;
+    // As long as bit number level in count is zero, skip it. It means there
+    // is nothing left at this level.
+    while (!(count & ((uint32_t{1}) << level))) {
+        level++;
+    }
+    uint256 h = inner[level];
+    bool matchh = matchlevel == level;
+    while (count != ((uint32_t{1}) << level)) {
+        // If we reach this point, h is an inner value that is not the top.
+        // We combine it with itself (Bitcoin's special rule for odd levels in
+        // the tree) to produce a higher level one.
+        if (pbranch && matchh) {
+            pbranch->push_back(h);
+        }
+        h = Hash(h, h);
+        // Increment count to the value it would have if two entries at this
+        // level had existed.
+        count += ((uint32_t{1}) << level);
+        level++;
+        // And propagate the result upwards accordingly.
+        while (!(count & ((uint32_t{1}) << level))) {
+            if (pbranch) {
+                if (matchh) {
+                    pbranch->push_back(inner[level]);
+                } else if (matchlevel == level) {
+                    pbranch->push_back(h);
+                    matchh = true;
+                }
+            }
+            h = Hash(inner[level], h);
+            level++;
+        }
+    }
+    // Return result.
+    if (pmutated) *pmutated = mutated;
+    if (proot) *proot = h;
+}
+
+static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
+    std::vector<uint256> ret;
+    MerkleComputation(leaves, nullptr, nullptr, position, &ret);
+    return ret;
+}
+
+std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position)
+{
+    std::vector<uint256> leaves;
+    leaves.resize(block.vtx.size());
+    for (size_t s = 0; s < block.vtx.size(); s++) {
+        leaves[s] = block.vtx[s]->GetHash();
+    }
+    return ComputeMerkleBranch(leaves, position);
+}
diff --git a/src/consensus/merkle.h b/src/consensus/merkle.h
index 4ae5a5b897..363f68039c 100644
--- a/src/consensus/merkle.h
+++ b/src/consensus/merkle.h
@@ -24,4 +24,14 @@ uint256 BlockMerkleRoot(const CBlock& block, bool* mutated = nullptr);
  */
 uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated = nullptr);
 
+/**
+ * Compute merkle path to the specified transaction
+ *
+ * @param[in] block the block
+ * @param[in] position transaction for which to calculate the merkle path, defaults to coinbase
+ *
+ * @return merkle path ordered from the deepest
+ */
+std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position = 0);
+
 #endif // BITCOIN_CONSENSUS_MERKLE_H
diff --git a/src/interfaces/mining.h b/src/interfaces/mining.h
index f71f7d7251..c77f3c30a2 100644
--- a/src/interfaces/mining.h
+++ b/src/interfaces/mining.h
@@ -42,6 +42,20 @@ public:
     virtual CTransactionRef getCoinbaseTx() = 0;
     virtual std::vector<unsigned char> getCoinbaseCommitment() = 0;
     virtual int getWitnessCommitmentIndex() = 0;
+
+    /**
+     * Compute merkle path to the coinbase transaction
+     *
+     * @return merkle path ordered from the deepest
+     */
+    virtual std::vector<uint256> getCoinbaseMerklePath() = 0;
+
+    /**
+     * Construct and broadcast the block.
+     *
+     * @returns if the block was processed, independent of block validity
+     */
+    virtual bool submitSolution(uint32_t version, uint32_t timestamp, uint32_t nonce, CMutableTransaction coinbase) = 0;
 };
 
 //! Interface giving clients (RPC, Stratum v2 Template Provider in the future)
diff --git a/src/ipc/capnp/mining.capnp b/src/ipc/capnp/mining.capnp
index 4ea69d16c9..5e0216acea 100644
--- a/src/ipc/capnp/mining.capnp
+++ b/src/ipc/capnp/mining.capnp
@@ -31,6 +31,8 @@ interface BlockTemplate $Proxy.wrap("interfaces::BlockTemplate") {
     getCoinbaseTx @4 (context: Proxy.Context) -> (result: Data);
     getCoinbaseCommitment @5 (context: Proxy.Context) -> (result: Data);
     getWitnessCommitmentIndex @6 (context: Proxy.Context) -> (result: Int32);
+    getCoinbaseMerklePath @7 (context: Proxy.Context) -> (result: List(Data));
+    submitSolution@8 (context: Proxy.Context, version: UInt32, timestamp: UInt32, nonce: UInt32, coinbase :Data) -> (result: Bool);
 }
 
 struct BlockCreateOptions $Proxy.wrap("node::BlockCreateOptions") {
diff --git a/src/node/interfaces.cpp b/src/node/interfaces.cpp
index ec4777ba7f..60dbd03488 100644
--- a/src/node/interfaces.cpp
+++ b/src/node/interfaces.cpp
@@ -8,6 +8,7 @@
 #include <chain.h>
 #include <chainparams.h>
 #include <common/args.h>
+#include <consensus/merkle.h>
 #include <consensus/validation.h>
 #include <deploymentstatus.h>
 #include <external_signer.h>
@@ -872,7 +873,7 @@ public:
 class BlockTemplateImpl : public BlockTemplate
 {
 public:
-    explicit BlockTemplateImpl(std::unique_ptr<CBlockTemplate> block_template) : m_block_template(std::move(block_template))
+    explicit BlockTemplateImpl(std::unique_ptr<CBlockTemplate> block_template, NodeContext& node) : m_block_template(std::move(block_template)), m_node(node)
     {
         assert(m_block_template);
     }
@@ -912,7 +913,37 @@ public:
         return GetWitnessCommitmentIndex(m_block_template->block);
     }
 
+    std::vector<uint256> getCoinbaseMerklePath() override
+    {
+        return BlockMerkleBranch(m_block_template->block);
+    }
+
+    bool submitSolution(uint32_t version, uint32_t timestamp, uint32_t nonce, CMutableTransaction coinbase) override
+    {
+        CBlock block{m_block_template->block};
+
+        auto cb = MakeTransactionRef(std::move(coinbase));
+
+        if (block.vtx.size() == 0) {
+            block.vtx.push_back(cb);
+        } else {
+            block.vtx[0] = cb;
+        }
+
+        block.nVersion = version;
+        block.nTime = timestamp;
+        block.nNonce = nonce;
+
+        block.hashMerkleRoot = BlockMerkleRoot(block);
+
+        auto block_ptr = std::make_shared<const CBlock>(block);
+        return chainman().ProcessNewBlock(block_ptr, /*force_processing=*/true, /*min_pow_checked=*/true, /*new_block=*/nullptr);
+    }
+
     const std::unique_ptr<CBlockTemplate> m_block_template;
+
+    ChainstateManager& chainman() { return *Assert(m_node.chainman); }
+    NodeContext& m_node;
 };
 
 class MinerImpl : public Mining
@@ -979,7 +1010,7 @@ public:
     {
         BlockAssembler::Options assemble_options{options};
         ApplyArgsManOptions(*Assert(m_node.args), assemble_options);
-        return std::make_unique<BlockTemplateImpl>(BlockAssembler{chainman().ActiveChainstate(), context()->mempool.get(), assemble_options}.CreateNewBlock(script_pub_key));
+        return std::make_unique<BlockTemplateImpl>(BlockAssembler{chainman().ActiveChainstate(), context()->mempool.get(), assemble_options}.CreateNewBlock(script_pub_key), m_node);
     }
 
     NodeContext* context() override { return &m_node; }
diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp
index 70308cb29a..2b1cf8595d 100644
--- a/src/test/merkle_tests.cpp
+++ b/src/test/merkle_tests.cpp
@@ -23,110 +23,6 @@ static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vecto
     return hash;
 }
 
-/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
-static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
-    if (pbranch) pbranch->clear();
-    if (leaves.size() == 0) {
-        if (pmutated) *pmutated = false;
-        if (proot) *proot = uint256();
-        return;
-    }
-    bool mutated = false;
-    // count is the number of leaves processed so far.
-    uint32_t count = 0;
-    // inner is an array of eagerly computed subtree hashes, indexed by tree
-    // level (0 being the leaves).
-    // For example, when count is 25 (11001 in binary), inner[4] is the hash of
-    // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
-    // the last leaf. The other inner entries are undefined.
-    uint256 inner[32];
-    // Which position in inner is a hash that depends on the matching leaf.
-    int matchlevel = -1;
-    // First process all leaves into 'inner' values.
-    while (count < leaves.size()) {
-        uint256 h = leaves[count];
-        bool matchh = count == branchpos;
-        count++;
-        int level;
-        // For each of the lower bits in count that are 0, do 1 step. Each
-        // corresponds to an inner value that existed before processing the
-        // current leaf, and each needs a hash to combine it.
-        for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
-            if (pbranch) {
-                if (matchh) {
-                    pbranch->push_back(inner[level]);
-                } else if (matchlevel == level) {
-                    pbranch->push_back(h);
-                    matchh = true;
-                }
-            }
-            mutated |= (inner[level] == h);
-            h = Hash(inner[level], h);
-        }
-        // Store the resulting hash at inner position level.
-        inner[level] = h;
-        if (matchh) {
-            matchlevel = level;
-        }
-    }
-    // Do a final 'sweep' over the rightmost branch of the tree to process
-    // odd levels, and reduce everything to a single top value.
-    // Level is the level (counted from the bottom) up to which we've sweeped.
-    int level = 0;
-    // As long as bit number level in count is zero, skip it. It means there
-    // is nothing left at this level.
-    while (!(count & ((uint32_t{1}) << level))) {
-        level++;
-    }
-    uint256 h = inner[level];
-    bool matchh = matchlevel == level;
-    while (count != ((uint32_t{1}) << level)) {
-        // If we reach this point, h is an inner value that is not the top.
-        // We combine it with itself (Bitcoin's special rule for odd levels in
-        // the tree) to produce a higher level one.
-        if (pbranch && matchh) {
-            pbranch->push_back(h);
-        }
-        h = Hash(h, h);
-        // Increment count to the value it would have if two entries at this
-        // level had existed.
-        count += ((uint32_t{1}) << level);
-        level++;
-        // And propagate the result upwards accordingly.
-        while (!(count & ((uint32_t{1}) << level))) {
-            if (pbranch) {
-                if (matchh) {
-                    pbranch->push_back(inner[level]);
-                } else if (matchlevel == level) {
-                    pbranch->push_back(h);
-                    matchh = true;
-                }
-            }
-            h = Hash(inner[level], h);
-            level++;
-        }
-    }
-    // Return result.
-    if (pmutated) *pmutated = mutated;
-    if (proot) *proot = h;
-}
-
-static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
-    std::vector<uint256> ret;
-    MerkleComputation(leaves, nullptr, nullptr, position, &ret);
-    return ret;
-}
-
-static std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position)
-{
-    std::vector<uint256> leaves;
-    leaves.resize(block.vtx.size());
-    for (size_t s = 0; s < block.vtx.size(); s++) {
-        leaves[s] = block.vtx[s]->GetHash();
-    }
-    return ComputeMerkleBranch(leaves, position);
-}
-
 // Older version of the merkle root computation code, for comparison.
 static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
 {