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