Data structure that represents a partial merkle tree. * * It represents a subset of the txid's of a known block, in a way that * allows recovery of the list of txid's and the merkle root, in an * authenticated way. * * The encoding works as follows: we traverse the tree in depth-first order, * storing a bit for each traversed node, signifying whether the node is the * parent of at least on
| 52 | * The size constraints follow from this. |
| 53 | */ |
| 54 | class CPartialMerkleTree |
| 55 | { |
| 56 | protected: |
| 57 | /** the total number of transactions in the block */ |
| 58 | unsigned int nTransactions; |
| 59 | |
| 60 | /** node-is-parent-of-matched-txid bits */ |
| 61 | std::vector<bool> vBits; |
| 62 | |
| 63 | /** txids and internal hashes */ |
| 64 | std::vector<uint256> vHash; |
| 65 | |
| 66 | /** flag set when encountering invalid data */ |
| 67 | bool fBad; |
| 68 | |
| 69 | /** helper function to efficiently calculate the number of nodes at given height in the merkle tree */ |
| 70 | unsigned int CalcTreeWidth(int height) const { |
| 71 | return (nTransactions+(1 << height)-1) >> height; |
| 72 | } |
| 73 | |
| 74 | /** calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves) */ |
| 75 | uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid); |
| 76 | |
| 77 | /** recursive function that traverses tree nodes, storing the data as bits and hashes */ |
| 78 | void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch); |
| 79 | |
| 80 | /** |
| 81 | * recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild. |
| 82 | * it returns the hash of the respective node and its respective index. |
| 83 | */ |
| 84 | uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex); |
| 85 | |
| 86 | public: |
| 87 | |
| 88 | SERIALIZE_METHODS(CPartialMerkleTree, obj) |
| 89 | { |
| 90 | READWRITE(obj.nTransactions, obj.vHash); |
| 91 | std::vector<unsigned char> bytes; |
| 92 | SER_WRITE(obj, bytes = BitsToBytes(obj.vBits)); |
| 93 | READWRITE(bytes); |
| 94 | SER_READ(obj, obj.vBits = BytesToBits(bytes)); |
| 95 | SER_READ(obj, obj.fBad = false); |
| 96 | } |
| 97 | |
| 98 | /** Construct a partial merkle tree from a list of transaction ids, and a mask that selects a subset of them */ |
| 99 | CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch); |
| 100 | |
| 101 | CPartialMerkleTree(); |
| 102 | |
| 103 | /** |
| 104 | * extract the matching txid's represented by this partial merkle tree |
| 105 | * and their respective indices within the partial tree. |
| 106 | * returns the merkle root, or 0 in case of failure |
| 107 | */ |
| 108 | uint256 ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex); |
| 109 | |
| 110 | /** Get number of transactions the merkle proof is indicating for cross-reference with |
| 111 | * local blockchain knowledge. |