From eece63fa72566068cb2a1bf85c95a72a5ba59bc9 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 17 Nov 2015 17:35:44 +0100
Subject: 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.
---
 src/consensus/merkle.cpp | 20 ++++++++++++++++++++
 src/consensus/merkle.h   | 15 +++++++++++++++
 2 files changed, 35 insertions(+)

(limited to 'src/consensus')

diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
index 6be9c26df2..9a8afa8a33 100644
--- a/src/consensus/merkle.cpp
+++ b/src/consensus/merkle.cpp
@@ -150,3 +150,23 @@ uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint2
     }
     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
index 7fd13d3e43..6ef59745ac 100644
--- a/src/consensus/merkle.h
+++ b/src/consensus/merkle.h
@@ -8,10 +8,25 @@
 #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
-- 
cgit v1.2.3