Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto 2 : // Copyright (c) 2009-2016 The Bitcoin developers 3 : // Copyright (c) 2017-2020 The PIVX Core developers 4 : // Distributed under the MIT software license, see the accompanying 5 : // file COPYING or http://www.opensource.org/licenses/mit-license.php. 6 : 7 : #ifndef PIVX_MERKLEBLOCK_H 8 : #define PIVX_MERKLEBLOCK_H 9 : 10 : #include "bloom.h" 11 : #include "primitives/block.h" 12 : #include "serialize.h" 13 : #include "uint256.h" 14 : 15 : #include <vector> 16 : 17 : // Helper functions for serialization. 18 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits); 19 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes); 20 : 21 : /** Data structure that represents a partial merkle tree. 22 : * 23 : * It represents a subset of the txid's of a known block, in a way that 24 : * allows recovery of the list of txid's and the merkle root, in an 25 : * authenticated way. 26 : * 27 : * The encoding works as follows: we traverse the tree in depth-first order, 28 : * storing a bit for each traversed node, signifying whether the node is the 29 : * parent of at least one matched leaf txid (or a matched txid itself). In 30 : * case we are at the leaf level, or this bit is 0, its merkle node hash is 31 : * stored, and its children are not explorer further. Otherwise, no hash is 32 : * stored, but we recurse into both (or the only) child branch. During 33 : * decoding, the same depth-first traversal is performed, consuming bits and 34 : * hashes as they written during encoding. 35 : * 36 : * The serialization is fixed and provides a hard guarantee about the 37 : * encoded size: 38 : * 39 : * SIZE <= 10 + ceil(32.25*N) 40 : * 41 : * Where N represents the number of leaf nodes of the partial tree. N itself 42 : * is bounded by: 43 : * 44 : * N <= total_transactions 45 : * N <= 1 + matched_transactions*tree_height 46 : * 47 : * The serialization format: 48 : * - uint32 total_transactions (4 bytes) 49 : * - varint number of hashes (1-3 bytes) 50 : * - uint256[] hashes in depth-first order (<= 32*N bytes) 51 : * - varint number of bytes of flag bits (1-3 bytes) 52 : * - byte[] flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits) 53 : * The size constraints follow from this. 54 : */ 55 : class CPartialMerkleTree 56 : { 57 : protected: 58 : /** the total number of transactions in the block */ 59 : unsigned int nTransactions; 60 : 61 : /** node-is-parent-of-matched-txid bits */ 62 : std::vector<bool> vBits; 63 : 64 : /** txids and internal hashes */ 65 : std::vector<uint256> vHash; 66 : 67 : /** flag set when encountering invalid data */ 68 : bool fBad; 69 : 70 : /** helper function to efficiently calculate the number of nodes at given height in the merkle tree */ 71 291843 : unsigned int CalcTreeWidth(int height) 72 : { 73 291843 : return (nTransactions + (1 << height) - 1) >> height; 74 : } 75 : 76 : /** calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves) */ 77 : uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256>& vTxid); 78 : 79 : /** recursive function that traverses tree nodes, storing the data as bits and hashes */ 80 : void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256>& vTxid, const std::vector<bool>& vMatch); 81 : 82 : /** 83 : * recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild. 84 : * it returns the hash of the respective node. 85 : */ 86 : uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int& nBitsUsed, unsigned int& nHashUsed, std::vector<uint256>& vMatch); 87 : 88 : public: 89 : 90 673 : SERIALIZE_METHODS(CPartialMerkleTree, obj) 91 : { 92 337 : READWRITE(obj.nTransactions, obj.vHash); 93 674 : std::vector<unsigned char> bytes; 94 675 : SER_WRITE(obj, bytes = BitsToBytes(obj.vBits)); 95 337 : READWRITE(bytes); 96 673 : SER_READ(obj, obj.vBits = BytesToBits(bytes)); 97 337 : SER_READ(obj, obj.fBad = false); 98 337 : } 99 : 100 : /** Construct a partial merkle tree from a list of transaction id's, and a mask that selects a subset of them */ 101 : CPartialMerkleTree(const std::vector<uint256>& vTxid, const std::vector<bool>& vMatch); 102 : 103 : CPartialMerkleTree(); 104 : 105 : /** 106 : * extract the matching txid's represented by this partial merkle tree. 107 : * returns the merkle root, or 0 in case of failure 108 : */ 109 : uint256 ExtractMatches(std::vector<uint256>& vMatch); 110 : }; 111 : 112 : 113 : /** 114 : * Used to relay blocks as header + vector<merkle branch> 115 : * to filtered nodes. 116 : */ 117 : class CMerkleBlock 118 : { 119 : public: 120 : /** Public only for unit testing */ 121 : CBlockHeader header; 122 : CPartialMerkleTree txn; 123 : 124 : /** 125 : * Public only for unit testing and relay testing (not relayed). 126 : * 127 : * Used only when a bloom filter is specified to allow 128 : * testing the transactions which matched the bloom filter. 129 : */ 130 : std::vector<std::pair<unsigned int, uint256> > vMatchedTxn; 131 : 132 : /** 133 : * Create from a CBlock, filtering transactions according to filter 134 : * Note that this will call IsRelevantAndUpdate on the filter for each transaction, 135 : * thus the filter will likely be modified. 136 : */ 137 11 : CMerkleBlock(const CBlock& block, CBloomFilter& filter) : CMerkleBlock(block, &filter, nullptr) { } 138 : 139 : // Create from a CBlock, matching the txids in the set 140 2 : CMerkleBlock(const CBlock& block, const std::set<uint256>& txids) : CMerkleBlock(block, nullptr, &txids) { } 141 : 142 0 : CMerkleBlock() {} 143 : 144 1 : SERIALIZE_METHODS(CMerkleBlock, obj) { READWRITE(obj.header, obj.txn); } 145 : 146 : private: 147 : // Combined constructor to consolidate code 148 : CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids); 149 : 150 : }; 151 : 152 : #endif // PIVX_MERKLEBLOCK_H