Changeset View
Changeset View
Standalone View
Standalone View
src/merkleblock.cpp
// Copyright (c) 2009-2010 Satoshi Nakamoto | // Copyright (c) 2009-2010 Satoshi Nakamoto | ||||
// Copyright (c) 2009-2016 The Bitcoin Core developers | // Copyright (c) 2009-2016 The Bitcoin Core developers | ||||
// Distributed under the MIT software license, see the accompanying | // Distributed under the MIT software license, see the accompanying | ||||
// file COPYING or http://www.opensource.org/licenses/mit-license.php. | // file COPYING or http://www.opensource.org/licenses/mit-license.php. | ||||
#include "merkleblock.h" | #include "merkleblock.h" | ||||
#include "consensus/consensus.h" | #include "consensus/consensus.h" | ||||
#include "hash.h" | #include "hash.h" | ||||
#include "utilstrencodings.h" | #include "utilstrencodings.h" | ||||
CMerkleBlock::CMerkleBlock(const CBlock &block, CBloomFilter &filter) { | CMerkleBlock::CMerkleBlock(const CBlock &block, CBloomFilter &filter) { | ||||
header = block.GetBlockHeader(); | header = block.GetBlockHeader(); | ||||
std::vector<bool> vMatch; | std::vector<bool> vTxIdMask; | ||||
std::vector<uint256> vHashes; | std::vector<uint256> vHashes; | ||||
vMatch.reserve(block.vtx.size()); | vTxIdMask.reserve(block.vtx.size()); | ||||
vHashes.reserve(block.vtx.size()); | vHashes.reserve(block.vtx.size()); | ||||
for (size_t i = 0; i < block.vtx.size(); i++) { | for (size_t i = 0; i < block.vtx.size(); i++) { | ||||
const CTransaction *tx = block.vtx[i].get(); | const CTransaction *tx = block.vtx[i].get(); | ||||
const uint256 &txid = tx->GetId(); | const uint256 &txid = tx->GetId(); | ||||
if (filter.IsRelevantAndUpdate(*tx)) { | if (filter.IsRelevantAndUpdate(*tx)) { | ||||
vMatch.push_back(true); | vTxIdMask.push_back(true); | ||||
vMatchedTxn.push_back(std::make_pair(i, txid)); | vMatchedTxn.push_back(std::make_pair(i, txid)); | ||||
} else { | } else { | ||||
vMatch.push_back(false); | vTxIdMask.push_back(false); | ||||
} | } | ||||
vHashes.push_back(txid); | vHashes.push_back(txid); | ||||
} | } | ||||
txn = CPartialMerkleTree(vHashes, vMatch); | txn = CPartialMerkleTree(vHashes, vTxIdMask); | ||||
} | } | ||||
CMerkleBlock::CMerkleBlock(const CBlock &block, const std::set<TxId> &txids) { | CMerkleBlock::CMerkleBlock(const CBlock &block, const std::set<TxId> &txids) { | ||||
header = block.GetBlockHeader(); | header = block.GetBlockHeader(); | ||||
std::vector<bool> vMatch; | std::vector<bool> vTxIdMask; | ||||
std::vector<uint256> vHashes; | std::vector<uint256> vHashes; | ||||
vMatch.reserve(block.vtx.size()); | vTxIdMask.reserve(block.vtx.size()); | ||||
vHashes.reserve(block.vtx.size()); | vHashes.reserve(block.vtx.size()); | ||||
for (const auto &tx : block.vtx) { | for (const auto &tx : block.vtx) { | ||||
const TxId &txid = tx->GetId(); | const TxId &txid = tx->GetId(); | ||||
vMatch.push_back(txids.count(txid)); | vTxIdMask.push_back(txids.count(txid)); | ||||
vHashes.push_back(txid); | vHashes.push_back(txid); | ||||
} | } | ||||
txn = CPartialMerkleTree(vHashes, vMatch); | txn = CPartialMerkleTree(vHashes, vTxIdMask); | ||||
} | } | ||||
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> &vTxid) { | ||||
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]; | ||||
} | } | ||||
Show All 9 Lines | uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, | ||||
} | } | ||||
// 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> &vTxid, | ||||
const std::vector<bool> &vMatch) { | const std::vector<bool> &vTxIdMask) { | ||||
// 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 (unsigned int p = pos << height; | ||||
p < (pos + 1) << height && p < nTransactions; p++) { | p < (pos + 1) << height && p < nTransactions; p++) { | ||||
fParentOfMatch |= vMatch[p]; | fParentOfMatch |= vTxIdMask[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, vTxIdMask); | ||||
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, vTxIdMask); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
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> &vMatchingTxHashes, | ||||
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 txid. | ||||
if (height == 0 && fParentOfMatch) { | if (height == 0 && fParentOfMatch) { | ||||
vMatch.push_back(hash); | vMatchingTxHashes.push_back(hash); | ||||
vnIndex.push_back(pos); | vnIndex.push_back(pos); | ||||
} | } | ||||
return hash; | return hash; | ||||
} | } | ||||
// Otherwise, descend into the subtrees to extract matched txids and hashes. | // Otherwise, descend into the subtrees to extract matched txids and hashes. | ||||
uint256 left = TraverseAndExtract(height - 1, pos * 2, nBitsUsed, nHashUsed, | uint256 left = TraverseAndExtract(height - 1, pos * 2, nBitsUsed, nHashUsed, | ||||
vMatch, vnIndex), | vMatchingTxHashes, 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, vMatchingTxHashes, 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> &vTxid, | ||||
const std::vector<bool> &vMatch) | const std::vector<bool> &vTxIdMask) | ||||
: nTransactions(vTxid.size()), fBad(false) { | : nTransactions(vTxid.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, vTxid, vTxIdMask); | ||||
} | } | ||||
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> &vMatchingTxHashes, | |||||
std::vector<unsigned int> &vnIndex) { | std::vector<unsigned int> &vnIndex) { | ||||
vMatch.clear(); | vMatchingTxHashes.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. | ||||
// 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. | ||||
Show All 12 Lines | CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatchingTxHashes, | ||||
// 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; | unsigned int nBitsUsed = 0, nHashUsed = 0; | ||||
uint256 hashMerkleRoot = | uint256 hashMerkleRoot = TraverseAndExtract( | ||||
TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex); | nHeight, 0, nBitsUsed, nHashUsed, vMatchingTxHashes, 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(); | ||||
} | } | ||||
// verify that all bits were consumed (except for the padding caused by | // verify that all bits were consumed (except for the padding caused by | ||||
// serializing it as a byte sequence) | // serializing it as a byte sequence) | ||||
Show All 11 Lines |