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> vMatch; | ||||
std::vector<uint256> vHashes; | std::vector<TxId> vTxids; | ||||
vMatch.reserve(block.vtx.size()); | vMatch.reserve(block.vtx.size()); | ||||
vHashes.reserve(block.vtx.size()); | vTxids.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 TxId &txid = tx->GetId(); | ||||
if (filter.IsRelevantAndUpdate(*tx)) { | if (filter.IsRelevantAndUpdate(*tx)) { | ||||
vMatch.push_back(true); | vMatch.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); | vMatch.push_back(false); | ||||
} | } | ||||
vHashes.push_back(txid); | vTxids.push_back(txid); | ||||
} | } | ||||
txn = CPartialMerkleTree(vHashes, vMatch); | txn = CPartialMerkleTree(vTxids, vMatch); | ||||
} | } | ||||
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> vMatch; | ||||
std::vector<uint256> vHashes; | std::vector<TxId> vTxids; | ||||
vMatch.reserve(block.vtx.size()); | vMatch.reserve(block.vtx.size()); | ||||
vHashes.reserve(block.vtx.size()); | vTxids.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)); | vMatch.push_back(txids.count(txid)); | ||||
vHashes.push_back(txid); | vTxids.push_back(txid); | ||||
} | } | ||||
txn = CPartialMerkleTree(vHashes, vMatch); | txn = CPartialMerkleTree(vTxids, 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<TxId> &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]; | ||||
} | } | ||||
// 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 | ||||
// otherwise1. | // 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, 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, unsigned int pos, | ||||
const std::vector<uint256> &vTxid, | const std::vector<TxId> &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 (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, 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, 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<TxId> &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 txid. | ||||
if (height == 0 && fParentOfMatch) { | if (height == 0 && fParentOfMatch) { | ||||
vMatch.push_back(hash); | vMatch.push_back(TxId(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), | vMatch, vnIndex), | ||||
Show All 9 Lines | uint256 CPartialMerkleTree::TraverseAndExtract( | ||||
} 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<TxId> &vTxid, | ||||
const std::vector<bool> &vMatch) | const std::vector<bool> &vMatch) | ||||
: 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, 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<TxId> &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) { | if (nTransactions == 0) { | ||||
return uint256(); | return uint256(); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 43 Lines • Show Last 20 Lines |