You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

merkleblock.cpp 6.7KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
  1. // Copyright (c) 2009-2010 Satoshi Nakamoto
  2. // Copyright (c) 2009-2016 The Starwels developers
  3. // Distributed under the MIT software license, see the accompanying
  4. // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  5. #include "merkleblock.h"
  6. #include "hash.h"
  7. #include "consensus/consensus.h"
  8. #include "utilstrencodings.h"
  9. CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter& filter)
  10. {
  11. header = block.GetBlockHeader();
  12. std::vector<bool> vMatch;
  13. std::vector<uint256> vHashes;
  14. vMatch.reserve(block.vtx.size());
  15. vHashes.reserve(block.vtx.size());
  16. for (unsigned int i = 0; i < block.vtx.size(); i++)
  17. {
  18. const uint256& hash = block.vtx[i]->GetHash();
  19. if (filter.IsRelevantAndUpdate(*block.vtx[i]))
  20. {
  21. vMatch.push_back(true);
  22. vMatchedTxn.push_back(std::make_pair(i, hash));
  23. }
  24. else
  25. vMatch.push_back(false);
  26. vHashes.push_back(hash);
  27. }
  28. txn = CPartialMerkleTree(vHashes, vMatch);
  29. }
  30. CMerkleBlock::CMerkleBlock(const CBlock& block, const std::set<uint256>& txids)
  31. {
  32. header = block.GetBlockHeader();
  33. std::vector<bool> vMatch;
  34. std::vector<uint256> vHashes;
  35. vMatch.reserve(block.vtx.size());
  36. vHashes.reserve(block.vtx.size());
  37. for (unsigned int i = 0; i < block.vtx.size(); i++)
  38. {
  39. const uint256& hash = block.vtx[i]->GetHash();
  40. if (txids.count(hash))
  41. vMatch.push_back(true);
  42. else
  43. vMatch.push_back(false);
  44. vHashes.push_back(hash);
  45. }
  46. txn = CPartialMerkleTree(vHashes, vMatch);
  47. }
  48. uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid) {
  49. //we can never have zero txs in a merkle block, we always need the coinbase tx
  50. //if we do not have this assert, we can hit a memory access violation when indexing into vTxid
  51. assert(vTxid.size() != 0);
  52. if (height == 0) {
  53. // hash at height 0 is the txids themself
  54. return vTxid[pos];
  55. } else {
  56. // calculate left hash
  57. uint256 left = CalcHash(height-1, pos*2, vTxid), right;
  58. // calculate right hash if not beyond the end of the array - copy left hash otherwise
  59. if (pos*2+1 < CalcTreeWidth(height-1))
  60. right = CalcHash(height-1, pos*2+1, vTxid);
  61. else
  62. right = left;
  63. // combine subhashes
  64. return Hash(BEGIN(left), END(left), BEGIN(right), END(right));
  65. }
  66. }
  67. void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) {
  68. // determine whether this node is the parent of at least one matched txid
  69. bool fParentOfMatch = false;
  70. for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
  71. fParentOfMatch |= vMatch[p];
  72. // store as flag bit
  73. vBits.push_back(fParentOfMatch);
  74. if (height==0 || !fParentOfMatch) {
  75. // if at height 0, or nothing interesting below, store hash and stop
  76. vHash.push_back(CalcHash(height, pos, vTxid));
  77. } else {
  78. // otherwise, don't store any hash, but descend into the subtrees
  79. TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
  80. if (pos*2+1 < CalcTreeWidth(height-1))
  81. TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
  82. }
  83. }
  84. uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
  85. if (nBitsUsed >= vBits.size()) {
  86. // overflowed the bits array - failure
  87. fBad = true;
  88. return uint256();
  89. }
  90. bool fParentOfMatch = vBits[nBitsUsed++];
  91. if (height==0 || !fParentOfMatch) {
  92. // if at height 0, or nothing interesting below, use stored hash and do not descend
  93. if (nHashUsed >= vHash.size()) {
  94. // overflowed the hash array - failure
  95. fBad = true;
  96. return uint256();
  97. }
  98. const uint256 &hash = vHash[nHashUsed++];
  99. if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
  100. vMatch.push_back(hash);
  101. vnIndex.push_back(pos);
  102. }
  103. return hash;
  104. } else {
  105. // otherwise, descend into the subtrees to extract matched txids and hashes
  106. uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
  107. if (pos*2+1 < CalcTreeWidth(height-1)) {
  108. right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
  109. if (right == left) {
  110. // The left and right branches should never be identical, as the transaction
  111. // hashes covered by them must each be unique.
  112. fBad = true;
  113. }
  114. } else {
  115. right = left;
  116. }
  117. // and combine them before returning
  118. return Hash(BEGIN(left), END(left), BEGIN(right), END(right));
  119. }
  120. }
  121. CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
  122. // reset state
  123. vBits.clear();
  124. vHash.clear();
  125. // calculate height of tree
  126. int nHeight = 0;
  127. while (CalcTreeWidth(nHeight) > 1)
  128. nHeight++;
  129. // traverse the partial tree
  130. TraverseAndBuild(nHeight, 0, vTxid, vMatch);
  131. }
  132. CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
  133. uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
  134. vMatch.clear();
  135. // An empty set will not work
  136. if (nTransactions == 0)
  137. return uint256();
  138. // check for excessively high numbers of transactions
  139. if (nTransactions > MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT)
  140. return uint256();
  141. // there can never be more hashes provided than one for every txid
  142. if (vHash.size() > nTransactions)
  143. return uint256();
  144. // there must be at least one bit per node in the partial tree, and at least one node per hash
  145. if (vBits.size() < vHash.size())
  146. return uint256();
  147. // calculate height of tree
  148. int nHeight = 0;
  149. while (CalcTreeWidth(nHeight) > 1)
  150. nHeight++;
  151. // traverse the partial tree
  152. unsigned int nBitsUsed = 0, nHashUsed = 0;
  153. uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
  154. // verify that no problems occurred during the tree traversal
  155. if (fBad)
  156. return uint256();
  157. // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
  158. if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
  159. return uint256();
  160. // verify that all hashes were consumed
  161. if (nHashUsed != vHash.size())
  162. return uint256();
  163. return hashMerkleRoot;
  164. }