12 std::vector<unsigned char>
BitsToBytes(
const std::vector<bool>& bits)
14 std::vector<unsigned char> ret((bits.size() + 7) / 8);
15 for (
unsigned int p = 0; p < bits.size(); p++) {
16 ret[p / 8] |= bits[p] << (p % 8);
21 std::vector<bool>
BytesToBits(
const std::vector<unsigned char>& bytes)
23 std::vector<bool> ret(bytes.size() * 8);
24 for (
unsigned int p = 0; p < ret.size(); p++) {
25 ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
34 std::vector<bool> vMatch;
35 std::vector<uint256> vHashes;
37 vMatch.reserve(block.
vtx.size());
38 vHashes.reserve(block.
vtx.size());
40 for (
unsigned int i = 0; i < block.
vtx.size(); i++)
43 if (txids && txids->count(hash)) {
44 vMatch.push_back(
true);
46 vMatch.push_back(
true);
49 vMatch.push_back(
false);
51 vHashes.push_back(hash);
66 uint256 left = CalcHash(height-1, pos*2, vTxid), right;
68 if (pos*2+1 < CalcTreeWidth(height-1))
69 right = CalcHash(height-1, pos*2+1, vTxid);
73 return Hash(left, right);
79 bool fParentOfMatch =
false;
80 for (
unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
81 fParentOfMatch |= vMatch[p];
83 vBits.push_back(fParentOfMatch);
84 if (height==0 || !fParentOfMatch) {
86 vHash.push_back(CalcHash(height, pos, vTxid));
89 TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
90 if (pos*2+1 < CalcTreeWidth(height-1))
91 TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
96 if (nBitsUsed >= vBits.size()) {
101 bool fParentOfMatch = vBits[nBitsUsed++];
102 if (height==0 || !fParentOfMatch) {
104 if (nHashUsed >= vHash.size()) {
109 const uint256 &hash = vHash[nHashUsed++];
110 if (height==0 && fParentOfMatch) {
111 vMatch.push_back(hash);
112 vnIndex.push_back(pos);
117 uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
118 if (pos*2+1 < CalcTreeWidth(height-1)) {
119 right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
129 return Hash(left, right);
168 unsigned int nBitsUsed = 0, nHashUsed = 0;
174 if ((nBitsUsed+7)/8 != (
vBits.size()+7)/8)
177 if (nHashUsed !=
vHash.size())
179 return hashMerkleRoot;
CBlockHeader header
Public only for unit testing.
uint256 ExtractMatches(std::vector< uint256 > &vMatch, std::vector< unsigned int > &vnIndex)
extract the matching txid's represented by this partial merkle tree and their respective indices with...
void TraverseAndBuild(int height, unsigned int pos, const std::vector< uint256 > &vTxid, const std::vector< bool > &vMatch)
recursive function that traverses tree nodes, storing the data as bits and hashes ...
CBlockHeader GetBlockHeader() const
unsigned int nTransactions
the total number of transactions in the block
bool fBad
flag set when encountering invalid data
bool IsRelevantAndUpdate(const CTransaction &tx)
Also adds any outputs which match the filter to the filter (to match their spending txes) ...
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
unsigned int CalcTreeWidth(int height) const
helper function to efficiently calculate the number of nodes at given height in the merkle tree ...
Data structure that represents a partial merkle tree.
std::vector< unsigned char > BitsToBytes(const std::vector< bool > &bits)
static const unsigned int MAX_BLOCK_WEIGHT
The maximum allowed weight for a block, see BIP 141 (network rule)
std::vector< uint256 > vHash
txids and internal hashes
std::vector< bool > BytesToBits(const std::vector< unsigned char > &bytes)
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
std::vector< CTransactionRef > vtx
uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector< uint256 > &vMatch, std::vector< unsigned int > &vnIndex)
recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBu...
std::vector< std::pair< unsigned int, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
static const size_t MIN_TRANSACTION_WEIGHT
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
uint256 CalcHash(int height, unsigned int pos, const std::vector< uint256 > &vTxid)
calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves) ...