Switch blocks to a constant-space Merkle root/branch algorithm.

This switches the Merkle tree logic for blocks to one that runs in constant (small) space.
The old code is moved to tests, and a new test is added that for various combinations of
block sizes, transaction positions to compute a branch for, and mutations:
 * Verifies that the old code and new code agree for the Merkle root.
 * Verifies that the old code and new code agree for the Merkle branch.
 * Verifies that the computed Merkle branch is valid.
 * Verifies that mutations don't change the Merkle root.
 * Verifies that mutations are correctly detected.

1 files changed, 2 insertions, 1 deletions

diff --git a/src/main.cpp b/src/main.cpp
index ceb5cb66f3..191b2b3c12 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);