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