Changeset View
Changeset View
Standalone View
Standalone View
src/merkleblock.cpp
Show First 20 Lines • Show All 46 Lines • ▼ Show 20 Lines | for (const auto &tx : block.vtx) { | ||||
const TxId &txid = tx->GetId(); | const TxId &txid = tx->GetId(); | ||||
vMatch.push_back(txids.count(txid)); | vMatch.push_back(txids.count(txid)); | ||||
vHashes.push_back(txid); | vHashes.push_back(txid); | ||||
} | } | ||||
txn = CPartialMerkleTree(vHashes, vMatch); | txn = CPartialMerkleTree(vHashes, vMatch); | ||||
} | } | ||||
uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, | uint256 CPartialMerkleTree::CalcHash(int height, size_t pos, | ||||
const std::vector<uint256> &vTxid) { | const std::vector<uint256> &vTxid) { | ||||
// we can never have zero txs in a merkle block, we always need the | // we can never have zero txs in a merkle block, we always need the | ||||
// coinbase tx if we do not have this assert, we can hit a memory | // coinbase tx if we do not have this assert, we can hit a memory | ||||
// access violation when indexing into vTxid | // access violation when indexing into vTxid | ||||
assert(vTxid.size() != 0); | assert(vTxid.size() != 0); | ||||
if (height == 0) { | if (height == 0) { | ||||
// hash at height 0 is the txids themself. | // hash at height 0 is the txids themself. | ||||
return vTxid[pos]; | return vTxid[pos]; | ||||
} | } | ||||
// Calculate left hash. | // Calculate left hash. | ||||
uint256 left = CalcHash(height - 1, pos * 2, vTxid), right; | uint256 left = CalcHash(height - 1, pos * 2, vTxid), right; | ||||
// Calculate right hash if not beyond the end of the array - copy left hash | // Calculate right hash if not beyond the end of the array - copy left hash | ||||
// otherwise. | // otherwise. | ||||
if (pos * 2 + 1 < CalcTreeWidth(height - 1)) { | if (pos * 2 + 1 < CalcTreeWidth(height - 1)) { | ||||
right = CalcHash(height - 1, pos * 2 + 1, vTxid); | right = CalcHash(height - 1, pos * 2 + 1, vTxid); | ||||
} else { | } else { | ||||
right = left; | right = left; | ||||
} | } | ||||
// Combine subhashes. | // Combine subhashes. | ||||
return Hash(BEGIN(left), END(left), BEGIN(right), END(right)); | return Hash(BEGIN(left), END(left), BEGIN(right), END(right)); | ||||
} | } | ||||
void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, | void CPartialMerkleTree::TraverseAndBuild(int height, size_t pos, | ||||
const std::vector<uint256> &vTxid, | const std::vector<uint256> &vTxid, | ||||
const std::vector<bool> &vMatch) { | const std::vector<bool> &vMatch) { | ||||
// Determine whether this node is the parent of at least one matched txid. | // Determine whether this node is the parent of at least one matched txid. | ||||
bool fParentOfMatch = false; | bool fParentOfMatch = false; | ||||
for (unsigned int p = pos << height; | for (size_t p = pos << height; p < (pos + 1) << height && p < nTransactions; | ||||
p < (pos + 1) << height && p < nTransactions; p++) { | p++) { | ||||
fParentOfMatch |= vMatch[p]; | fParentOfMatch |= vMatch[p]; | ||||
} | } | ||||
// Store as flag bit. | // Store as flag bit. | ||||
vBits.push_back(fParentOfMatch); | vBits.push_back(fParentOfMatch); | ||||
if (height == 0 || !fParentOfMatch) { | if (height == 0 || !fParentOfMatch) { | ||||
// If at height 0, or nothing interesting below, store hash and stop. | // If at height 0, or nothing interesting below, store hash and stop. | ||||
vHash.push_back(CalcHash(height, pos, vTxid)); | vHash.push_back(CalcHash(height, pos, vTxid)); | ||||
} else { | } else { | ||||
// Otherwise, don't store any hash, but descend into the subtrees. | // Otherwise, don't store any hash, but descend into the subtrees. | ||||
TraverseAndBuild(height - 1, pos * 2, vTxid, vMatch); | TraverseAndBuild(height - 1, pos * 2, vTxid, vMatch); | ||||
if (pos * 2 + 1 < CalcTreeWidth(height - 1)) { | if (pos * 2 + 1 < CalcTreeWidth(height - 1)) { | ||||
TraverseAndBuild(height - 1, pos * 2 + 1, vTxid, vMatch); | TraverseAndBuild(height - 1, pos * 2 + 1, vTxid, vMatch); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
uint256 CPartialMerkleTree::TraverseAndExtract( | uint256 CPartialMerkleTree::TraverseAndExtract(int height, size_t pos, | ||||
int height, unsigned int pos, unsigned int &nBitsUsed, | size_t &nBitsUsed, | ||||
unsigned int &nHashUsed, std::vector<uint256> &vMatch, | size_t &nHashUsed, | ||||
std::vector<unsigned int> &vnIndex) { | std::vector<uint256> &vMatch, | ||||
std::vector<size_t> &vnIndex) { | |||||
if (nBitsUsed >= vBits.size()) { | if (nBitsUsed >= vBits.size()) { | ||||
// Overflowed the bits array - failure | // Overflowed the bits array - failure | ||||
fBad = true; | fBad = true; | ||||
return uint256(); | return uint256(); | ||||
} | } | ||||
bool fParentOfMatch = vBits[nBitsUsed++]; | bool fParentOfMatch = vBits[nBitsUsed++]; | ||||
if (height == 0 || !fParentOfMatch) { | if (height == 0 || !fParentOfMatch) { | ||||
▲ Show 20 Lines • Show All 48 Lines • ▼ Show 20 Lines | CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, | ||||
// traverse the partial tree | // traverse the partial tree | ||||
TraverseAndBuild(nHeight, 0, vTxid, vMatch); | TraverseAndBuild(nHeight, 0, vTxid, vMatch); | ||||
} | } | ||||
CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {} | CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {} | ||||
uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, | uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, | ||||
std::vector<unsigned int> &vnIndex) { | std::vector<size_t> &vnIndex) { | ||||
vMatch.clear(); | vMatch.clear(); | ||||
// An empty set will not work | // An empty set will not work | ||||
if (nTransactions == 0) { | if (nTransactions == 0) { | ||||
return uint256(); | return uint256(); | ||||
} | } | ||||
// Check for excessively high numbers of transactions. | // Check for excessively high numbers of transactions. | ||||
Show All 12 Lines | uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, | ||||
// calculate height of tree. | // calculate height of tree. | ||||
int nHeight = 0; | int nHeight = 0; | ||||
while (CalcTreeWidth(nHeight) > 1) { | while (CalcTreeWidth(nHeight) > 1) { | ||||
nHeight++; | nHeight++; | ||||
} | } | ||||
// traverse the partial tree. | // traverse the partial tree. | ||||
unsigned int nBitsUsed = 0, nHashUsed = 0; | size_t nBitsUsed = 0, nHashUsed = 0; | ||||
uint256 hashMerkleRoot = | uint256 hashMerkleRoot = | ||||
TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex); | TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex); | ||||
// verify that no problems occurred during the tree traversal. | // verify that no problems occurred during the tree traversal. | ||||
if (fBad) { | if (fBad) { | ||||
return uint256(); | return uint256(); | ||||
} | } | ||||
Show All 13 Lines |