| 130 | CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {} |
| 131 | |
| 132 | uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) { |
| 133 | vMatch.clear(); |
| 134 | // An empty set will not work |
| 135 | if (nTransactions == 0) |
| 136 | return uint256(); |
| 137 | // check for excessively high numbers of transactions |
| 138 | if (nTransactions > MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT) |
| 139 | return uint256(); |
| 140 | // there can never be more hashes provided than one for every txid |
| 141 | if (vHash.size() > nTransactions) |
| 142 | return uint256(); |
| 143 | // there must be at least one bit per node in the partial tree, and at least one node per hash |
| 144 | if (vBits.size() < vHash.size()) |
| 145 | return uint256(); |
| 146 | // calculate height of tree |
| 147 | int nHeight = 0; |
| 148 | while (CalcTreeWidth(nHeight) > 1) |
| 149 | nHeight++; |
| 150 | // traverse the partial tree |
| 151 | unsigned int nBitsUsed = 0, nHashUsed = 0; |
| 152 | uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex); |
| 153 | // verify that no problems occurred during the tree traversal |
| 154 | if (fBad) |
| 155 | return uint256(); |
| 156 | // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence) |
| 157 | if ((nBitsUsed+7)/8 != (vBits.size()+7)/8) |
| 158 | return uint256(); |
| 159 | // verify that all hashes were consumed |
| 160 | if (nHashUsed != vHash.size()) |
| 161 | return uint256(); |
| 162 | return hashMerkleRoot; |
| 163 | } |