aboutsummaryrefslogtreecommitdiff
path: root/src/consensus
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2015-11-17 17:35:44 +0100
committerPieter Wuille <pieter.wuille@gmail.com>2015-11-27 15:36:52 +0100
commiteece63fa72566068cb2a1bf85c95a72a5ba59bc9 (patch)
tree093633b56700e77f3bc4d8fda2b3032d2aa7c4dd /src/consensus
parentee60e5625bf8a11c8e5509b9cea8b6465056c448 (diff)
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.
Diffstat (limited to 'src/consensus')
-rw-r--r--src/consensus/merkle.cpp20
-rw-r--r--src/consensus/merkle.h15
2 files changed, 35 insertions, 0 deletions
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