diff options
author | Pieter Wuille <pieter.wuille@gmail.com> | 2015-11-17 17:35:44 +0100 |
---|---|---|
committer | Pieter Wuille <pieter.wuille@gmail.com> | 2015-11-27 15:36:52 +0100 |
commit | eece63fa72566068cb2a1bf85c95a72a5ba59bc9 (patch) | |
tree | 093633b56700e77f3bc4d8fda2b3032d2aa7c4dd /src/consensus/merkle.cpp | |
parent | ee60e5625bf8a11c8e5509b9cea8b6465056c448 (diff) | |
download | bitcoin-eece63fa72566068cb2a1bf85c95a72a5ba59bc9.tar.xz |
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/merkle.cpp')
-rw-r--r-- | src/consensus/merkle.cpp | 20 |
1 files changed, 20 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); +} |