Merge pull request #6508

eece63f Switch blocks to a constant-space Merkle root/branch algorithm. (Pieter Wuille)
ee60e56 Add merkle.{h,cpp}, generic merkle root/branch algorithm (Pieter Wuille)

13 files changed, 353 insertions, 75 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index f1e98dabde..40f2e19af0 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -100,6 +100,7 @@ BITCOIN_CORE_H = \
   compat/sanity.h \
   compressor.h \
   consensus/consensus.h \
+  consensus/merkle.h \
   consensus/params.h \
   consensus/validation.h \
   core_io.h \
@@ -268,6 +269,7 @@ libbitcoin_common_a_SOURCES = \
   chainparams.cpp \
   coins.cpp \
   compressor.cpp \
+  consensus/merkle.cpp \
   core_read.cpp \
   core_write.cpp \
   hash.cpp \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index fafc1a2944..c377183ad5 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -57,6 +57,7 @@ BITCOIN_TESTS =\
   test/dbwrapper_tests.cpp \
   test/main_tests.cpp \
   test/mempool_tests.cpp \
+  test/merkle_tests.cpp \
   test/miner_tests.cpp \
   test/mruset_tests.cpp \
   test/multisig_tests.cpp \
diff --git a/src/chainparams.cpp b/src/chainparams.cpp
index 5d6d1ef9d8..a46866a2be 100644
--- a/src/chainparams.cpp
+++ b/src/chainparams.cpp
@@ -4,6 +4,7 @@
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include "chainparams.h"
+#include "consensus/merkle.h"
 
 #include "tinyformat.h"
 #include "util.h"
@@ -32,7 +33,7 @@ static CBlock CreateGenesisBlock(const char* pszTimestamp, const CScript& genesi
     genesis.nVersion = nVersion;
     genesis.vtx.push_back(txNew);
     genesis.hashPrevBlock.SetNull();
-    genesis.hashMerkleRoot = genesis.ComputeMerkleRoot();
+    genesis.hashMerkleRoot = BlockMerkleRoot(genesis);
     return genesis;
 }
 
diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
new file mode 100644
index 0000000000..9a8afa8a33
--- /dev/null
+++ b/src/consensus/merkle.cpp
@@ -0,0 +1,172 @@
+#include "merkle.h"
+#include "hash.h"
+#include "utilstrencodings.h"
+
+/*     WARNING! If you're reading this because you're learning about crypto
+       and/or designing a new system that will use merkle trees, keep in mind
+       that the following merkle tree algorithm has a serious flaw related to
+       duplicate txids, resulting in a vulnerability (CVE-2012-2459).
+
+       The reason is that if the number of hashes in the list at a given time
+       is odd, the last one is duplicated before computing the next level (which
+       is unusual in Merkle trees). This results in certain sequences of
+       transactions leading to the same merkle root. For example, these two
+       trees:
+
+                    A               A
+                  /  \            /   \
+                B     C         B       C
+               / \    |        / \     / \
+              D   E   F       D   E   F   F
+             / \ / \ / \     / \ / \ / \ / \
+             1 2 3 4 5 6     1 2 3 4 5 6 5 6
+
+       for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
+       6 are repeated) result in the same root hash A (because the hash of both
+       of (F) and (F,F) is C).
+
+       The vulnerability results from being able to send a block with such a
+       transaction list, with the same merkle root, and the same block hash as
+       the original without duplication, resulting in failed validation. If the
+       receiving node proceeds to mark that block as permanently invalid
+       however, it will fail to accept further unmodified (and thus potentially
+       valid) versions of the same block. We defend against this by detecting
+       the case where we would hash two identical hashes at the end of the list
+       together, and treating that identically to the block having an invalid
+       merkle root. Assuming no double-SHA256 collisions, this will detect all
+       known ways of changing the transactions without affecting the merkle
+       root.
+*/
+
+/* 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);
+            CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
+        }
+        // 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);
+        }
+        CHash256().Write(h.begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
+        // 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;
+                }
+            }
+            CHash256().Write(inner[level].begin(), 32).Write(h.begin(), 32).Finalize(h.begin());
+            level++;
+        }
+    }
+    // Return result.
+    if (pmutated) *pmutated = mutated;
+    if (proot) *proot = h;
+}
+
+uint256 ComputeMerkleRoot(const std::vector<uint256>& leaves, bool* mutated) {
+    uint256 hash;
+    MerkleComputation(leaves, &hash, mutated, -1, NULL);
+    return hash;
+}
+
+std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
+    std::vector<uint256> ret;
+    MerkleComputation(leaves, NULL, NULL, position, &ret);
+    return ret;
+}
+
+uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
+    uint256 hash = leaf;
+    for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
+        if (nIndex & 1) {
+            hash = Hash(BEGIN(*it), END(*it), BEGIN(hash), END(hash));
+        } else {
+            hash = Hash(BEGIN(hash), END(hash), BEGIN(*it), END(*it));
+        }
+        nIndex >>= 1;
+    }
+    return hash;
+}
+
+uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
+{
+    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 ComputeMerkleRoot(leaves, mutated);
+}
+
+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
new file mode 100644
index 0000000000..6ef59745ac
--- /dev/null
+++ b/src/consensus/merkle.h
@@ -0,0 +1,32 @@
+// Copyright (c) 2015 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_MERKLE
+#define BITCOIN_MERKLE
+
+#include <stdint.h>
+#include <vector>
+
+#include "primitives/transaction.h"
+#include "primitives/block.h"
+#include "uint256.h"
+
+uint256 ComputeMerkleRoot(const std::vector<uint256>& leaves, bool* mutated = NULL);
+std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position);
+uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& branch, uint32_t position);
+
+/*
+ * Compute the Merkle root of the transactions in a block.
+ * *mutated is set to true if a duplicated subtree was found.
+ */
+uint256 BlockMerkleRoot(const CBlock& block, bool* mutated = NULL);
+
+/*
+ * Compute the Merkle branch for the tree of transactions in a block, for a
+ * given position.
+ * This can be verified using ComputeMerkleRootFromBranch.
+ */
+std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position);
+
+#endif
diff --git a/src/main.cpp b/src/main.cpp
index 6b6840ce8c..1003dd8c36 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -12,6 +12,7 @@
 #include "checkpoints.h"
 #include "checkqueue.h"
 #include "consensus/consensus.h"
+#include "consensus/merkle.h"
 #include "consensus/validation.h"
 #include "hash.h"
 #include "init.h"
@@ -2876,7 +2877,7 @@ bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bo
     // Check the merkle root.
     if (fCheckMerkleRoot) {
         bool mutated;
-        uint256 hashMerkleRoot2 = block.ComputeMerkleRoot(&mutated);
+        uint256 hashMerkleRoot2 = BlockMerkleRoot(block, &mutated);
         if (block.hashMerkleRoot != hashMerkleRoot2)
             return state.DoS(100, error("CheckBlock(): hashMerkleRoot mismatch"),
                              REJECT_INVALID, "bad-txnmrklroot", true);
diff --git a/src/miner.cpp b/src/miner.cpp
index 5b711210db..27a1fbcf80 100644
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -10,6 +10,7 @@
 #include "chainparams.h"
 #include "coins.h"
 #include "consensus/consensus.h"
+#include "consensus/merkle.h"
 #include "consensus/validation.h"
 #include "hash.h"
 #include "main.h"
@@ -373,7 +374,7 @@ void IncrementExtraNonce(CBlock* pblock, const CBlockIndex* pindexPrev, unsigned
     assert(txCoinbase.vin[0].scriptSig.size() <= 100);
 
     pblock->vtx[0] = txCoinbase;
-    pblock->hashMerkleRoot = pblock->ComputeMerkleRoot();
+    pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
 }
 
 //////////////////////////////////////////////////////////////////////////////
diff --git a/src/primitives/block.cpp b/src/primitives/block.cpp
index 7a58074d24..7280c18f77 100644
--- a/src/primitives/block.cpp
+++ b/src/primitives/block.cpp
@@ -15,69 +15,6 @@ uint256 CBlockHeader::GetHash() const
     return SerializeHash(*this);
 }
 
-uint256 CBlock::ComputeMerkleRoot(bool* fMutated) const
-{
-    /* WARNING! If you're reading this because you're learning about crypto
-       and/or designing a new system that will use merkle trees, keep in mind
-       that the following merkle tree algorithm has a serious flaw related to
-       duplicate txids, resulting in a vulnerability (CVE-2012-2459).
-
-       The reason is that if the number of hashes in the list at a given time
-       is odd, the last one is duplicated before computing the next level (which
-       is unusual in Merkle trees). This results in certain sequences of
-       transactions leading to the same merkle root. For example, these two
-       trees:
-
-                    A               A
-                  /  \            /   \
-                B     C         B       C
-               / \    |        / \     / \
-              D   E   F       D   E   F   F
-             / \ / \ / \     / \ / \ / \ / \
-             1 2 3 4 5 6     1 2 3 4 5 6 5 6
-
-       for transaction lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] (where 5 and
-       6 are repeated) result in the same root hash A (because the hash of both
-       of (F) and (F,F) is C).
-
-       The vulnerability results from being able to send a block with such a
-       transaction list, with the same merkle root, and the same block hash as
-       the original without duplication, resulting in failed validation. If the
-       receiving node proceeds to mark that block as permanently invalid
-       however, it will fail to accept further unmodified (and thus potentially
-       valid) versions of the same block. We defend against this by detecting
-       the case where we would hash two identical hashes at the end of the list
-       together, and treating that identically to the block having an invalid
-       merkle root. Assuming no double-SHA256 collisions, this will detect all
-       known ways of changing the transactions without affecting the merkle
-       root.
-    */
-    std::vector<uint256> vMerkleTree;
-    vMerkleTree.reserve(vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
-    for (std::vector<CTransaction>::const_iterator it(vtx.begin()); it != vtx.end(); ++it)
-        vMerkleTree.push_back(it->GetHash());
-    int j = 0;
-    bool mutated = false;
-    for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
-    {
-        for (int i = 0; i < nSize; i += 2)
-        {
-            int i2 = std::min(i+1, nSize-1);
-            if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
-                // Two identical hashes at the end of the list at a particular level.
-                mutated = true;
-            }
-            vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]),  END(vMerkleTree[j+i]),
-                                       BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
-        }
-        j += nSize;
-    }
-    if (fMutated) {
-        *fMutated = mutated;
-    }
-    return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
-}
-
 std::string CBlock::ToString() const
 {
     std::stringstream s;
diff --git a/src/primitives/block.h b/src/primitives/block.h
index 54731ff557..5c017d436f 100644
--- a/src/primitives/block.h
+++ b/src/primitives/block.h
@@ -118,12 +118,6 @@ public:
         return block;
     }
 
-    // Build the merkle tree for this block and return the merkle root.
-    // If non-NULL, *mutated is set to whether mutation was detected in the merkle
-    // tree (a duplication of transactions in the block leading to an identical
-    // merkle root).
-    uint256 ComputeMerkleRoot(bool* mutated = NULL) const;
-
     std::string ToString() const;
 };
 
diff --git a/src/test/main_tests.cpp b/src/test/main_tests.cpp
index 21ae46d6e9..2b92d239e9 100644
--- a/src/test/main_tests.cpp
+++ b/src/test/main_tests.cpp
@@ -72,5 +72,4 @@ BOOST_AUTO_TEST_CASE(test_combiner_all)
     Test.disconnect(&ReturnTrue);
     BOOST_CHECK(Test());
 }
-
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp
new file mode 100644
index 0000000000..1e31f2e679
--- /dev/null
+++ b/src/test/merkle_tests.cpp
@@ -0,0 +1,136 @@
+// Copyright (c) 2015 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "consensus/merkle.h"
+#include "test/test_bitcoin.h"
+#include "random.h"
+
+#include <boost/test/unit_test.hpp>
+
+BOOST_FIXTURE_TEST_SUITE(merkle_tests, TestingSetup)
+
+// Older version of the merkle root computation code, for comparison.
+static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
+{
+    vMerkleTree.clear();
+    vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
+    for (std::vector<CTransaction>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
+        vMerkleTree.push_back(it->GetHash());
+    int j = 0;
+    bool mutated = false;
+    for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
+    {
+        for (int i = 0; i < nSize; i += 2)
+        {
+            int i2 = std::min(i+1, nSize-1);
+            if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
+                // Two identical hashes at the end of the list at a particular level.
+                mutated = true;
+            }
+            vMerkleTree.push_back(Hash(vMerkleTree[j+i].begin(), vMerkleTree[j+i].end(),
+                                       vMerkleTree[j+i2].begin(), vMerkleTree[j+i2].end()));
+        }
+        j += nSize;
+    }
+    if (fMutated) {
+        *fMutated = mutated;
+    }
+    return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
+}
+
+// Older version of the merkle branch computation code, for comparison.
+static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
+{
+    std::vector<uint256> vMerkleBranch;
+    int j = 0;
+    for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
+    {
+        int i = std::min(nIndex^1, nSize-1);
+        vMerkleBranch.push_back(vMerkleTree[j+i]);
+        nIndex >>= 1;
+        j += nSize;
+    }
+    return vMerkleBranch;
+}
+
+static inline int ctz(uint32_t i) {
+    if (i == 0) return 0;
+    int j = 0;
+    while (!(i & 1)) {
+        j++;
+        i >>= 1;
+    }
+    return j;
+}
+
+BOOST_AUTO_TEST_CASE(merkle_test)
+{
+    for (int i = 0; i < 32; i++) {
+        // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
+        int ntx = (i <= 16) ? i : 17 + (insecure_rand() % 4000);
+        // Try up to 3 mutations.
+        for (int mutate = 0; mutate <= 3; mutate++) {
+            int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
+            if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
+            int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
+            int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
+            if (duplicate2 >= ntx1) break;
+            int ntx2 = ntx1 + duplicate2;
+            int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the the third mutation.
+            if (duplicate3 >= ntx2) break;
+            int ntx3 = ntx2 + duplicate3;
+            // Build a block with ntx different transactions.
+            CBlock block;
+            block.vtx.resize(ntx);
+            for (int j = 0; j < ntx; j++) {
+                CMutableTransaction mtx;
+                mtx.nLockTime = j;
+                block.vtx[j] = mtx;
+            }
+            // Compute the root of the block before mutating it.
+            bool unmutatedMutated = false;
+            uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
+            BOOST_CHECK(unmutatedMutated == false);
+            // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
+            block.vtx.resize(ntx3);
+            for (int j = 0; j < duplicate1; j++) {
+                block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
+            }
+            for (int j = 0; j < duplicate2; j++) {
+                block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
+            }
+            for (int j = 0; j < duplicate3; j++) {
+                block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
+            }
+            // Compute the merkle root and merkle tree using the old mechanism.
+            bool oldMutated = false;
+            std::vector<uint256> merkleTree;
+            uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
+            // Compute the merkle root using the new mechanism.
+            bool newMutated = false;
+            uint256 newRoot = BlockMerkleRoot(block, &newMutated);
+            BOOST_CHECK(oldRoot == newRoot);
+            BOOST_CHECK(newRoot == unmutatedRoot);
+            BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
+            BOOST_CHECK(oldMutated == newMutated);
+            BOOST_CHECK(newMutated == !!mutate);
+            // If no mutation was done (once for every ntx value), try up to 16 branches.
+            if (mutate == 0) {
+                for (int loop = 0; loop < std::min(ntx, 16); loop++) {
+                    // If ntx <= 16, try all branches. Otherise, try 16 random ones.
+                    int mtx = loop;
+                    if (ntx > 16) {
+                        mtx = insecure_rand() % ntx;
+                    }
+                    std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx);
+                    std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
+                    BOOST_CHECK(oldBranch == newBranch);
+                    BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx].GetHash(), newBranch, mtx) == oldRoot);
+                }
+            }
+        }
+    }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp
index dc20e34634..1d7c9f65c0 100644
--- a/src/test/miner_tests.cpp
+++ b/src/test/miner_tests.cpp
@@ -5,6 +5,7 @@
 #include "chainparams.h"
 #include "coins.h"
 #include "consensus/consensus.h"
+#include "consensus/merkle.h"
 #include "consensus/validation.h"
 #include "main.h"
 #include "miner.h"
@@ -93,7 +94,7 @@ BOOST_AUTO_TEST_CASE(CreateNewBlock_validity)
         pblock->vtx[0] = CTransaction(txCoinbase);
         if (txFirst.size() < 2)
             txFirst.push_back(new CTransaction(pblock->vtx[0]));
-        pblock->hashMerkleRoot = pblock->ComputeMerkleRoot();
+        pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);
         pblock->nNonce = blockinfo[i].nonce;
         CValidationState state;
         BOOST_CHECK(ProcessNewBlock(state, chainparams, NULL, pblock, true, NULL));
diff --git a/src/test/pmt_tests.cpp b/src/test/pmt_tests.cpp
index d9f3c3e467..0d7fb2bc35 100644
--- a/src/test/pmt_tests.cpp
+++ b/src/test/pmt_tests.cpp
@@ -2,6 +2,7 @@
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
+#include "consensus/merkle.h"
 #include "merkleblock.h"
 #include "serialize.h"
 #include "streams.h"
@@ -48,7 +49,7 @@ BOOST_AUTO_TEST_CASE(pmt_test1)
         }
 
         // calculate actual merkle root and height
-        uint256 merkleRoot1 = block.ComputeMerkleRoot();
+        uint256 merkleRoot1 = BlockMerkleRoot(block);
         std::vector<uint256> vTxid(nTx, uint256());
         for (unsigned int j=0; j<nTx; j++)
             vTxid[j] = block.vtx[j].GetHash();