| 151 | CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {} |
| 152 | |
| 153 | uint256 CPartialMerkleTree::ExtractMatches(std::vector<Txid> &vMatch, std::vector<unsigned int> &vnIndex) { |
| 154 | vMatch.clear(); |
| 155 | // An empty set will not work |
| 156 | if (nTransactions == 0) |
| 157 | return uint256(); |
| 158 | // check for excessively high numbers of transactions |
| 159 | if (nTransactions > MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT) |
| 160 | return uint256(); |
| 161 | // there can never be more hashes provided than one for every txid |
| 162 | if (vHash.size() > nTransactions) |
| 163 | return uint256(); |
| 164 | // there must be at least one bit per node in the partial tree, and at least one node per hash |
| 165 | if (vBits.size() < vHash.size()) |
| 166 | return uint256(); |
| 167 | // calculate height of tree |
| 168 | int nHeight = 0; |
| 169 | while (CalcTreeWidth(nHeight) > 1) |
| 170 | nHeight++; |
| 171 | // traverse the partial tree |
| 172 | unsigned int nBitsUsed = 0, nHashUsed = 0; |
| 173 | uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex); |
| 174 | // verify that no problems occurred during the tree traversal |
| 175 | if (fBad) |
| 176 | return uint256(); |
| 177 | // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence) |
| 178 | if (CeilDiv(nBitsUsed, 8u) != CeilDiv(vBits.size(), 8u)) |
| 179 | return uint256(); |
| 180 | // verify that all hashes were consumed |
| 181 | if (nHashUsed != vHash.size()) |
| 182 | return uint256(); |
| 183 | return hashMerkleRoot; |
| 184 | } |