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.h 5.7KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159
  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. #ifndef STARWELS_MERKLEBLOCK_H
  6. #define STARWELS_MERKLEBLOCK_H
  7. #include "serialize.h"
  8. #include "uint256.h"
  9. #include "primitives/block.h"
  10. #include "bloom.h"
  11. #include <vector>
  12. /** Data structure that represents a partial merkle tree.
  13. *
  14. * It represents a subset of the txid's of a known block, in a way that
  15. * allows recovery of the list of txid's and the merkle root, in an
  16. * authenticated way.
  17. *
  18. * The encoding works as follows: we traverse the tree in depth-first order,
  19. * storing a bit for each traversed node, signifying whether the node is the
  20. * parent of at least one matched leaf txid (or a matched txid itself). In
  21. * case we are at the leaf level, or this bit is 0, its merkle node hash is
  22. * stored, and its children are not explored further. Otherwise, no hash is
  23. * stored, but we recurse into both (or the only) child branch. During
  24. * decoding, the same depth-first traversal is performed, consuming bits and
  25. * hashes as they written during encoding.
  26. *
  27. * The serialization is fixed and provides a hard guarantee about the
  28. * encoded size:
  29. *
  30. * SIZE <= 10 + ceil(32.25*N)
  31. *
  32. * Where N represents the number of leaf nodes of the partial tree. N itself
  33. * is bounded by:
  34. *
  35. * N <= total_transactions
  36. * N <= 1 + matched_transactions*tree_height
  37. *
  38. * The serialization format:
  39. * - uint32 total_transactions (4 bytes)
  40. * - varint number of hashes (1-3 bytes)
  41. * - uint256[] hashes in depth-first order (<= 32*N bytes)
  42. * - varint number of bytes of flag bits (1-3 bytes)
  43. * - byte[] flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits)
  44. * The size constraints follow from this.
  45. */
  46. class CPartialMerkleTree
  47. {
  48. protected:
  49. /** the total number of transactions in the block */
  50. unsigned int nTransactions;
  51. /** node-is-parent-of-matched-txid bits */
  52. std::vector<bool> vBits;
  53. /** txids and internal hashes */
  54. std::vector<uint256> vHash;
  55. /** flag set when encountering invalid data */
  56. bool fBad;
  57. /** helper function to efficiently calculate the number of nodes at given height in the merkle tree */
  58. unsigned int CalcTreeWidth(int height) {
  59. return (nTransactions+(1 << height)-1) >> height;
  60. }
  61. /** calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves) */
  62. uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid);
  63. /** recursive function that traverses tree nodes, storing the data as bits and hashes */
  64. void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
  65. /**
  66. * recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild.
  67. * it returns the hash of the respective node and its respective index.
  68. */
  69. uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
  70. public:
  71. /** serialization implementation */
  72. ADD_SERIALIZE_METHODS;
  73. template <typename Stream, typename Operation>
  74. inline void SerializationOp(Stream& s, Operation ser_action) {
  75. READWRITE(nTransactions);
  76. READWRITE(vHash);
  77. std::vector<unsigned char> vBytes;
  78. if (ser_action.ForRead()) {
  79. READWRITE(vBytes);
  80. CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree*>(this));
  81. us.vBits.resize(vBytes.size() * 8);
  82. for (unsigned int p = 0; p < us.vBits.size(); p++)
  83. us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0;
  84. us.fBad = false;
  85. } else {
  86. vBytes.resize((vBits.size()+7)/8);
  87. for (unsigned int p = 0; p < vBits.size(); p++)
  88. vBytes[p / 8] |= vBits[p] << (p % 8);
  89. READWRITE(vBytes);
  90. }
  91. }
  92. /** Construct a partial merkle tree from a list of transaction ids, and a mask that selects a subset of them */
  93. CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
  94. CPartialMerkleTree();
  95. /**
  96. * extract the matching txid's represented by this partial merkle tree
  97. * and their respective indices within the partial tree.
  98. * returns the merkle root, or 0 in case of failure
  99. */
  100. uint256 ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
  101. };
  102. /**
  103. * Used to relay blocks as header + vector<merkle branch>
  104. * to filtered nodes.
  105. *
  106. * NOTE: The class assumes that the given CBlock has *at least* 1 transaction. If the CBlock has 0 txs, it will hit an assertion.
  107. */
  108. class CMerkleBlock
  109. {
  110. public:
  111. /** Public only for unit testing */
  112. CBlockHeader header;
  113. CPartialMerkleTree txn;
  114. public:
  115. /** Public only for unit testing and relay testing (not relayed) */
  116. std::vector<std::pair<unsigned int, uint256> > vMatchedTxn;
  117. /**
  118. * Create from a CBlock, filtering transactions according to filter
  119. * Note that this will call IsRelevantAndUpdate on the filter for each transaction,
  120. * thus the filter will likely be modified.
  121. */
  122. CMerkleBlock(const CBlock& block, CBloomFilter& filter);
  123. // Create from a CBlock, matching the txids in the set
  124. CMerkleBlock(const CBlock& block, const std::set<uint256>& txids);
  125. CMerkleBlock() {}
  126. ADD_SERIALIZE_METHODS;
  127. template <typename Stream, typename Operation>
  128. inline void SerializationOp(Stream& s, Operation ser_action) {
  129. READWRITE(header);
  130. READWRITE(txn);
  131. }
  132. };
  133. #endif // STARWELS_MERKLEBLOCK_H