Changeset View
Changeset View
Standalone View
Standalone View
src/merkleblock.cpp
Show All 13 Lines | CMerkleBlock::CMerkleBlock(const CBlock &block, CBloomFilter &filter) { | ||||
std::vector<bool> vMatch; | std::vector<bool> vMatch; | ||||
std::vector<uint256> vHashes; | std::vector<uint256> vHashes; | ||||
vMatch.reserve(block.vtx.size()); | vMatch.reserve(block.vtx.size()); | ||||
vHashes.reserve(block.vtx.size()); | vHashes.reserve(block.vtx.size()); | ||||
for (unsigned int i = 0; i < block.vtx.size(); i++) { | for (unsigned int i = 0; i < block.vtx.size(); i++) { | ||||
const uint256 &txid = block.vtx[i]->GetId(); | const uint256 &txhash = block.vtx[i]->GetHash(); | ||||
if (filter.IsRelevantAndUpdate(*block.vtx[i])) { | if (filter.IsRelevantAndUpdate(*block.vtx[i])) { | ||||
vMatch.push_back(true); | vMatch.push_back(true); | ||||
vMatchedTxn.push_back(std::make_pair(i, txid)); | vMatchedTxn.push_back(std::make_pair(i, txhash)); | ||||
} else | } else | ||||
vMatch.push_back(false); | vMatch.push_back(false); | ||||
vHashes.push_back(txid); | vHashes.push_back(txhash); | ||||
} | } | ||||
txn = CPartialMerkleTree(vHashes, vMatch); | txn = CPartialMerkleTree(vHashes, vMatch); | ||||
} | } | ||||
CMerkleBlock::CMerkleBlock(const CBlock &block, | CMerkleBlock::CMerkleBlock(const CBlock &block, | ||||
const std::set<uint256> &txids) { | const std::set<txhash_t> &txhashes) { | ||||
header = block.GetBlockHeader(); | header = block.GetBlockHeader(); | ||||
std::vector<bool> vMatch; | std::vector<bool> vMatch; | ||||
std::vector<uint256> vHashes; | std::vector<uint256> vHashes; | ||||
vMatch.reserve(block.vtx.size()); | vMatch.reserve(block.vtx.size()); | ||||
vHashes.reserve(block.vtx.size()); | vHashes.reserve(block.vtx.size()); | ||||
for (unsigned int i = 0; i < block.vtx.size(); i++) { | for (unsigned int i = 0; i < block.vtx.size(); i++) { | ||||
const uint256 &txid = block.vtx[i]->GetId(); | const txhash_t &txhash = block.vtx[i]->GetHash(); | ||||
if (txids.count(txid)) | if (txhashes.count(txhash)) | ||||
vMatch.push_back(true); | vMatch.push_back(true); | ||||
else | else | ||||
vMatch.push_back(false); | vMatch.push_back(false); | ||||
vHashes.push_back(txid); | vHashes.push_back(txhash); | ||||
} | } | ||||
txn = CPartialMerkleTree(vHashes, vMatch); | txn = CPartialMerkleTree(vHashes, vMatch); | ||||
} | } | ||||
uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, | uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, | ||||
const std::vector<uint256> &vTxid) { | const std::vector<uint256> &vTxhash) { | ||||
if (height == 0) { | if (height == 0) { | ||||
// hash at height 0 is the txids themself. | // hash at height 0 is the txhashes themself. | ||||
return vTxid[pos]; | return vTxhash[pos]; | ||||
} else { | } else { | ||||
// Calculate left hash. | // Calculate left hash. | ||||
uint256 left = CalcHash(height - 1, pos * 2, vTxid), right; | uint256 left = CalcHash(height - 1, pos * 2, vTxhash), right; | ||||
// Calculate right hash if not beyond the end of the array - copy left | // Calculate right hash if not beyond the end of the array - copy left | ||||
// hash otherwise1. | // hash otherwise1. | ||||
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, vTxhash); | ||||
} 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, unsigned int pos, | ||||
const std::vector<uint256> &vTxid, | const std::vector<uint256> &vTxhash, | ||||
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 txhash. | ||||
bool fParentOfMatch = false; | bool fParentOfMatch = false; | ||||
for (unsigned int p = pos << height; | for (unsigned int p = pos << height; | ||||
p < (pos + 1) << height && p < nTransactions; p++) | p < (pos + 1) << height && p < nTransactions; 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, vTxhash)); | ||||
} 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, vTxhash, 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, vTxhash, vMatch); | ||||
} | } | ||||
} | } | ||||
uint256 CPartialMerkleTree::TraverseAndExtract( | uint256 CPartialMerkleTree::TraverseAndExtract( | ||||
int height, unsigned int pos, unsigned int &nBitsUsed, | int height, unsigned int pos, unsigned int &nBitsUsed, | ||||
unsigned int &nHashUsed, std::vector<uint256> &vMatch, | unsigned int &nHashUsed, std::vector<uint256> &vMatch, | ||||
std::vector<unsigned int> &vnIndex) { | std::vector<unsigned int> &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) { | ||||
// If at height 0, or nothing interesting below, use stored hash and do | // If at height 0, or nothing interesting below, use stored hash and do | ||||
// not descend. | // not descend. | ||||
if (nHashUsed >= vHash.size()) { | if (nHashUsed >= vHash.size()) { | ||||
// Overflowed the hash array - failure | // Overflowed the hash array - failure | ||||
fBad = true; | fBad = true; | ||||
return uint256(); | return uint256(); | ||||
} | } | ||||
const uint256 &hash = vHash[nHashUsed++]; | const uint256 &hash = vHash[nHashUsed++]; | ||||
// In case of height 0, we have a matched txid. | // In case of height 0, we have a matched txhash. | ||||
if (height == 0 && fParentOfMatch) { | if (height == 0 && fParentOfMatch) { | ||||
vMatch.push_back(hash); | vMatch.push_back(hash); | ||||
vnIndex.push_back(pos); | vnIndex.push_back(pos); | ||||
} | } | ||||
return hash; | return hash; | ||||
} else { | } else { | ||||
// Otherwise, descend into the subtrees to extract matched txids and | // Otherwise, descend into the subtrees to extract matched txhashes and | ||||
// hashes. | // hashes. | ||||
uint256 left = TraverseAndExtract(height - 1, pos * 2, nBitsUsed, | uint256 left = TraverseAndExtract(height - 1, pos * 2, nBitsUsed, | ||||
nHashUsed, vMatch, vnIndex), | nHashUsed, vMatch, vnIndex), | ||||
right; | right; | ||||
if (pos * 2 + 1 < CalcTreeWidth(height - 1)) { | if (pos * 2 + 1 < CalcTreeWidth(height - 1)) { | ||||
right = TraverseAndExtract(height - 1, pos * 2 + 1, nBitsUsed, | right = TraverseAndExtract(height - 1, pos * 2 + 1, nBitsUsed, | ||||
nHashUsed, vMatch, vnIndex); | nHashUsed, vMatch, vnIndex); | ||||
if (right == left) { | if (right == left) { | ||||
// The left and right branches should never be identical, as the | // The left and right branches should never be identical, as the | ||||
// transaction hashes covered by them must each be unique. | // transaction hashes covered by them must each be unique. | ||||
fBad = true; | fBad = true; | ||||
} | } | ||||
} else { | } else { | ||||
right = left; | right = left; | ||||
} | } | ||||
// and combine them before returning. | // and combine them before returning. | ||||
return Hash(BEGIN(left), END(left), BEGIN(right), END(right)); | return Hash(BEGIN(left), END(left), BEGIN(right), END(right)); | ||||
} | } | ||||
} | } | ||||
CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, | CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxhashes, | ||||
const std::vector<bool> &vMatch) | const std::vector<bool> &vMatch) | ||||
: nTransactions(vTxid.size()), fBad(false) { | : nTransactions(vTxhashes.size()), fBad(false) { | ||||
// reset state | // reset state | ||||
vBits.clear(); | vBits.clear(); | ||||
vHash.clear(); | vHash.clear(); | ||||
// 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 | ||||
TraverseAndBuild(nHeight, 0, vTxid, vMatch); | TraverseAndBuild(nHeight, 0, vTxhashes, 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<unsigned int> &vnIndex) { | ||||
vMatch.clear(); | vMatch.clear(); | ||||
// An empty set will not work | // An empty set will not work | ||||
if (nTransactions == 0) return uint256(); | if (nTransactions == 0) return uint256(); | ||||
// Check for excessively high numbers of transactions. | // Check for excessively high numbers of transactions. | ||||
// FIXME: Track the maximum block size we've seen and use it here. | // FIXME: Track the maximum block size we've seen and use it here. | ||||
// There can never be more hashes provided than one for every txid. | // There can never be more hashes provided than one for every txhash. | ||||
if (vHash.size() > nTransactions) return uint256(); | if (vHash.size() > nTransactions) return uint256(); | ||||
// There must be at least one bit per node in the partial tree, and at least | // There must be at least one bit per node in the partial tree, and at least | ||||
// one node per hash. | // one node per hash. | ||||
if (vBits.size() < vHash.size()) return uint256(); | if (vBits.size() < vHash.size()) return uint256(); | ||||
// calculate height of tree. | // calculate height of tree. | ||||
int nHeight = 0; | int nHeight = 0; | ||||
while (CalcTreeWidth(nHeight) > 1) | while (CalcTreeWidth(nHeight) > 1) | ||||
nHeight++; | nHeight++; | ||||
Show All 13 Lines |