Bitcoin Core  22.99.0 P2P Digital Currency
merkle_tests.cpp
Go to the documentation of this file.
1 // Copyright (c) 2015-2020 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
4
5 #include <consensus/merkle.h>
7
8 #include <boost/test/unit_test.hpp>
9
11
12 static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vector<uint256>& vMerkleBranch, uint32_t nIndex) {
13  uint256 hash = leaf;
14  for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
15  if (nIndex & 1) {
16  hash = Hash(*it, hash);
17  } else {
18  hash = Hash(hash, *it);
19  }
20  nIndex >>= 1;
21  }
22  return hash;
23 }
24
25 /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
26 static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
27  if (pbranch) pbranch->clear();
28  if (leaves.size() == 0) {
29  if (pmutated) *pmutated = false;
30  if (proot) *proot = uint256();
31  return;
32  }
33  bool mutated = false;
34  // count is the number of leaves processed so far.
35  uint32_t count = 0;
36  // inner is an array of eagerly computed subtree hashes, indexed by tree
37  // level (0 being the leaves).
38  // For example, when count is 25 (11001 in binary), inner[4] is the hash of
39  // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to
40  // the last leaf. The other inner entries are undefined.
41  uint256 inner[32];
42  // Which position in inner is a hash that depends on the matching leaf.
43  int matchlevel = -1;
44  // First process all leaves into 'inner' values.
45  while (count < leaves.size()) {
46  uint256 h = leaves[count];
47  bool matchh = count == branchpos;
48  count++;
49  int level;
50  // For each of the lower bits in count that are 0, do 1 step. Each
51  // corresponds to an inner value that existed before processing the
52  // current leaf, and each needs a hash to combine it.
53  for (level = 0; !(count & (((uint32_t)1) << level)); level++) {
54  if (pbranch) {
55  if (matchh) {
56  pbranch->push_back(inner[level]);
57  } else if (matchlevel == level) {
58  pbranch->push_back(h);
59  matchh = true;
60  }
61  }
62  mutated |= (inner[level] == h);
63  CHash256().Write(inner[level]).Write(h).Finalize(h);
64  }
65  // Store the resulting hash at inner position level.
66  inner[level] = h;
67  if (matchh) {
68  matchlevel = level;
69  }
70  }
71  // Do a final 'sweep' over the rightmost branch of the tree to process
72  // odd levels, and reduce everything to a single top value.
73  // Level is the level (counted from the bottom) up to which we've sweeped.
74  int level = 0;
75  // As long as bit number level in count is zero, skip it. It means there
76  // is nothing left at this level.
77  while (!(count & (((uint32_t)1) << level))) {
78  level++;
79  }
80  uint256 h = inner[level];
81  bool matchh = matchlevel == level;
82  while (count != (((uint32_t)1) << level)) {
83  // If we reach this point, h is an inner value that is not the top.
84  // We combine it with itself (Bitcoin's special rule for odd levels in
85  // the tree) to produce a higher level one.
86  if (pbranch && matchh) {
87  pbranch->push_back(h);
88  }
89  CHash256().Write(h).Write(h).Finalize(h);
90  // Increment count to the value it would have if two entries at this
91  // level had existed.
92  count += (((uint32_t)1) << level);
93  level++;
94  // And propagate the result upwards accordingly.
95  while (!(count & (((uint32_t)1) << level))) {
96  if (pbranch) {
97  if (matchh) {
98  pbranch->push_back(inner[level]);
99  } else if (matchlevel == level) {
100  pbranch->push_back(h);
101  matchh = true;
102  }
103  }
104  CHash256().Write(inner[level]).Write(h).Finalize(h);
105  level++;
106  }
107  }
108  // Return result.
109  if (pmutated) *pmutated = mutated;
110  if (proot) *proot = h;
111 }
112
113 static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) {
114  std::vector<uint256> ret;
115  MerkleComputation(leaves, nullptr, nullptr, position, &ret);
116  return ret;
117 }
118
119 static std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position)
120 {
121  std::vector<uint256> leaves;
122  leaves.resize(block.vtx.size());
123  for (size_t s = 0; s < block.vtx.size(); s++) {
124  leaves[s] = block.vtx[s]->GetHash();
125  }
126  return ComputeMerkleBranch(leaves, position);
127 }
128
129 // Older version of the merkle root computation code, for comparison.
130 static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree)
131 {
132  vMerkleTree.clear();
133  vMerkleTree.reserve(block.vtx.size() * 2 + 16); // Safe upper bound for the number of total nodes.
134  for (std::vector<CTransactionRef>::const_iterator it(block.vtx.begin()); it != block.vtx.end(); ++it)
135  vMerkleTree.push_back((*it)->GetHash());
136  int j = 0;
137  bool mutated = false;
138  for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
139  {
140  for (int i = 0; i < nSize; i += 2)
141  {
142  int i2 = std::min(i+1, nSize-1);
143  if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
144  // Two identical hashes at the end of the list at a particular level.
145  mutated = true;
146  }
147  vMerkleTree.push_back(Hash(vMerkleTree[j+i], vMerkleTree[j+i2]));
148  }
149  j += nSize;
150  }
151  if (fMutated) {
152  *fMutated = mutated;
153  }
154  return (vMerkleTree.empty() ? uint256() : vMerkleTree.back());
155 }
156
157 // Older version of the merkle branch computation code, for comparison.
158 static std::vector<uint256> BlockGetMerkleBranch(const CBlock& block, const std::vector<uint256>& vMerkleTree, int nIndex)
159 {
160  std::vector<uint256> vMerkleBranch;
161  int j = 0;
162  for (int nSize = block.vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
163  {
164  int i = std::min(nIndex^1, nSize-1);
165  vMerkleBranch.push_back(vMerkleTree[j+i]);
166  nIndex >>= 1;
167  j += nSize;
168  }
169  return vMerkleBranch;
170 }
171
172 static inline int ctz(uint32_t i) {
173  if (i == 0) return 0;
174  int j = 0;
175  while (!(i & 1)) {
176  j++;
177  i >>= 1;
178  }
179  return j;
180 }
181
183 {
184  for (int i = 0; i < 32; i++) {
185  // Try 32 block sizes: all sizes from 0 to 16 inclusive, and then 15 random sizes.
186  int ntx = (i <= 16) ? i : 17 + (InsecureRandRange(4000));
187  // Try up to 3 mutations.
188  for (int mutate = 0; mutate <= 3; mutate++) {
189  int duplicate1 = mutate >= 1 ? 1 << ctz(ntx) : 0; // The last how many transactions to duplicate first.
190  if (duplicate1 >= ntx) break; // Duplication of the entire tree results in a different root (it adds a level).
191  int ntx1 = ntx + duplicate1; // The resulting number of transactions after the first duplication.
192  int duplicate2 = mutate >= 2 ? 1 << ctz(ntx1) : 0; // Likewise for the second mutation.
193  if (duplicate2 >= ntx1) break;
194  int ntx2 = ntx1 + duplicate2;
195  int duplicate3 = mutate >= 3 ? 1 << ctz(ntx2) : 0; // And for the third mutation.
196  if (duplicate3 >= ntx2) break;
197  int ntx3 = ntx2 + duplicate3;
198  // Build a block with ntx different transactions.
199  CBlock block;
200  block.vtx.resize(ntx);
201  for (int j = 0; j < ntx; j++) {
203  mtx.nLockTime = j;
204  block.vtx[j] = MakeTransactionRef(std::move(mtx));
205  }
206  // Compute the root of the block before mutating it.
207  bool unmutatedMutated = false;
208  uint256 unmutatedRoot = BlockMerkleRoot(block, &unmutatedMutated);
209  BOOST_CHECK(unmutatedMutated == false);
210  // Optionally mutate by duplicating the last transactions, resulting in the same merkle root.
211  block.vtx.resize(ntx3);
212  for (int j = 0; j < duplicate1; j++) {
213  block.vtx[ntx + j] = block.vtx[ntx + j - duplicate1];
214  }
215  for (int j = 0; j < duplicate2; j++) {
216  block.vtx[ntx1 + j] = block.vtx[ntx1 + j - duplicate2];
217  }
218  for (int j = 0; j < duplicate3; j++) {
219  block.vtx[ntx2 + j] = block.vtx[ntx2 + j - duplicate3];
220  }
221  // Compute the merkle root and merkle tree using the old mechanism.
222  bool oldMutated = false;
223  std::vector<uint256> merkleTree;
224  uint256 oldRoot = BlockBuildMerkleTree(block, &oldMutated, merkleTree);
225  // Compute the merkle root using the new mechanism.
226  bool newMutated = false;
227  uint256 newRoot = BlockMerkleRoot(block, &newMutated);
228  BOOST_CHECK(oldRoot == newRoot);
229  BOOST_CHECK(newRoot == unmutatedRoot);
230  BOOST_CHECK((newRoot == uint256()) == (ntx == 0));
231  BOOST_CHECK(oldMutated == newMutated);
232  BOOST_CHECK(newMutated == !!mutate);
233  // If no mutation was done (once for every ntx value), try up to 16 branches.
234  if (mutate == 0) {
235  for (int loop = 0; loop < std::min(ntx, 16); loop++) {
236  // If ntx <= 16, try all branches. Otherwise, try 16 random ones.
237  int mtx = loop;
238  if (ntx > 16) {
239  mtx = InsecureRandRange(ntx);
240  }
241  std::vector<uint256> newBranch = BlockMerkleBranch(block, mtx);
242  std::vector<uint256> oldBranch = BlockGetMerkleBranch(block, merkleTree, mtx);
243  BOOST_CHECK(oldBranch == newBranch);
244  BOOST_CHECK(ComputeMerkleRootFromBranch(block.vtx[mtx]->GetHash(), newBranch, mtx) == oldRoot);
245  }
246  }
247  }
248  }
249 }
250
251
252 BOOST_AUTO_TEST_CASE(merkle_test_empty_block)
253 {
254  bool mutated = false;
255  CBlock block;
256  uint256 root = BlockMerkleRoot(block, &mutated);
257
258  BOOST_CHECK_EQUAL(root.IsNull(), true);
259  BOOST_CHECK_EQUAL(mutated, false);
260 }
261
262 BOOST_AUTO_TEST_CASE(merkle_test_oneTx_block)
263 {
264  bool mutated = false;
265  CBlock block;
266
267  block.vtx.resize(1);
269  mtx.nLockTime = 0;
270  block.vtx[0] = MakeTransactionRef(std::move(mtx));
271  uint256 root = BlockMerkleRoot(block, &mutated);
272  BOOST_CHECK_EQUAL(root, block.vtx[0]->GetHash());
273  BOOST_CHECK_EQUAL(mutated, false);
274 }
275
276 BOOST_AUTO_TEST_CASE(merkle_test_OddTxWithRepeatedLastTx_block)
277 {
278  bool mutated;
279  CBlock block, blockWithRepeatedLastTx;
280
281  block.vtx.resize(3);
282
283  for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
285  mtx.nLockTime = pos;
286  block.vtx[pos] = MakeTransactionRef(std::move(mtx));
287  }
288
289  blockWithRepeatedLastTx = block;
290  blockWithRepeatedLastTx.vtx.push_back(blockWithRepeatedLastTx.vtx.back());
291
292  uint256 rootofBlock = BlockMerkleRoot(block, &mutated);
293  BOOST_CHECK_EQUAL(mutated, false);
294
295  uint256 rootofBlockWithRepeatedLastTx = BlockMerkleRoot(blockWithRepeatedLastTx, &mutated);
296  BOOST_CHECK_EQUAL(rootofBlock, rootofBlockWithRepeatedLastTx);
297  BOOST_CHECK_EQUAL(mutated, true);
298 }
299
300 BOOST_AUTO_TEST_CASE(merkle_test_LeftSubtreeRightSubtree)
301 {
302  CBlock block, leftSubtreeBlock, rightSubtreeBlock;
303
304  block.vtx.resize(4);
305  std::size_t pos;
306  for (pos = 0; pos < block.vtx.size(); pos++) {
308  mtx.nLockTime = pos;
309  block.vtx[pos] = MakeTransactionRef(std::move(mtx));
310  }
311
312  for (pos = 0; pos < block.vtx.size() / 2; pos++)
313  leftSubtreeBlock.vtx.push_back(block.vtx[pos]);
314
315  for (pos = block.vtx.size() / 2; pos < block.vtx.size(); pos++)
316  rightSubtreeBlock.vtx.push_back(block.vtx[pos]);
317
318  uint256 root = BlockMerkleRoot(block);
319  uint256 rootOfLeftSubtree = BlockMerkleRoot(leftSubtreeBlock);
320  uint256 rootOfRightSubtree = BlockMerkleRoot(rightSubtreeBlock);
321  std::vector<uint256> leftRight;
322  leftRight.push_back(rootOfLeftSubtree);
323  leftRight.push_back(rootOfRightSubtree);
324  uint256 rootOfLR = ComputeMerkleRoot(leftRight);
325
326  BOOST_CHECK_EQUAL(root, rootOfLR);
327 }
328
329 BOOST_AUTO_TEST_CASE(merkle_test_BlockWitness)
330 {
331  CBlock block;
332
333  block.vtx.resize(2);
334  for (std::size_t pos = 0; pos < block.vtx.size(); pos++) {
336  mtx.nLockTime = pos;
337  block.vtx[pos] = MakeTransactionRef(std::move(mtx));
338  }
339
340  uint256 blockWitness = BlockWitnessMerkleRoot(block);
341
342  std::vector<uint256> hashes;
343  hashes.resize(block.vtx.size());
344  hashes[0].SetNull();
345  hashes[1] = block.vtx[1]->GetHash();
346
347  uint256 merkleRootofHashes = ComputeMerkleRoot(hashes);
348
349  BOOST_CHECK_EQUAL(merkleRootofHashes, blockWitness);
350 }
count
static int count
Definition: tests.c:31
ComputeMerkleRoot
uint256 ComputeMerkleRoot(std::vector< uint256 > hashes, bool *mutated)
Definition: merkle.cpp:45
CHash256::Write
CHash256 & Write(Span< const unsigned char > input)
Definition: hash.h:37
setup_common.h
InsecureRandRange
static uint64_t InsecureRandRange(uint64_t range)
Definition: setup_common.h:75
MakeTransactionRef
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:387
ctz
static int ctz(uint32_t i)
Definition: merkle_tests.cpp:172
BlockGetMerkleBranch
static std::vector< uint256 > BlockGetMerkleBranch(const CBlock &block, const std::vector< uint256 > &vMerkleTree, int nIndex)
Definition: merkle_tests.cpp:158
BOOST_FIXTURE_TEST_SUITE
#define BOOST_FIXTURE_TEST_SUITE(a, b)
Definition: object.cpp:14
BOOST_AUTO_TEST_SUITE_END
BOOST_AUTO_TEST_SUITE_END()
mutated
bool mutated
Definition: deserialize.cpp:199
BOOST_AUTO_TEST_CASE
BOOST_AUTO_TEST_CASE(merkle_test)
Definition: merkle_tests.cpp:182
Hash
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
Definition: hash.h:75
CMutableTransaction::nLockTime
uint32_t nLockTime
Definition: transaction.h:349
ComputeMerkleRootFromBranch
static uint256 ComputeMerkleRootFromBranch(const uint256 &leaf, const std::vector< uint256 > &vMerkleBranch, uint32_t nIndex)
Definition: merkle_tests.cpp:12
BlockBuildMerkleTree
static uint256 BlockBuildMerkleTree(const CBlock &block, bool *fMutated, std::vector< uint256 > &vMerkleTree)
Definition: merkle_tests.cpp:130
ComputeMerkleBranch
static std::vector< uint256 > ComputeMerkleBranch(const std::vector< uint256 > &leaves, uint32_t position)
Definition: merkle_tests.cpp:113
CHash256::Finalize
void Finalize(Span< unsigned char > output)
Definition: hash.h:30
uint256
256-bit opaque blob.
Definition: uint256.h:124
merkle.h
BlockWitnessMerkleRoot
uint256 BlockWitnessMerkleRoot(const CBlock &block, bool *mutated)
Definition: merkle.cpp:75
CBlock
Definition: block.h:62
base_blob::IsNull
bool IsNull() const
Definition: uint256.h:31
CBlock::vtx
std::vector< CTransactionRef > vtx
Definition: block.h:66
std
Definition: setup_common.h:33
TestingSetup
Testing setup that configures a complete environment.
Definition: setup_common.h:107
CHash256
A hasher class for Bitcoin's 256-bit hash (double SHA-256).
Definition: hash.h:24
CMutableTransaction
A mutable version of CTransaction.
Definition: transaction.h:344
BlockMerkleBranch
static std::vector< uint256 > BlockMerkleBranch(const CBlock &block, uint32_t position)
Definition: merkle_tests.cpp:119
MerkleComputation
static void MerkleComputation(const std::vector< uint256 > &leaves, uint256 *proot, bool *pmutated, uint32_t branchpos, std::vector< uint256 > *pbranch)
Definition: merkle_tests.cpp:26
BOOST_CHECK
#define BOOST_CHECK(expr)
Definition: object.cpp:17
BOOST_CHECK_EQUAL
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:18
BlockMerkleRoot
uint256 BlockMerkleRoot(const CBlock &block, bool *mutated)
Definition: merkle.cpp:65