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++)
42 const Txid& hash{block.
vtx[i]->GetHash()};
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);
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) {
96 if (nBitsUsed >=
vBits.size()) {
101 bool fParentOfMatch =
vBits[nBitsUsed++];
102 if (height==0 || !fParentOfMatch) {
104 if (nHashUsed >=
vHash.size()) {
110 if (height==0 && fParentOfMatch) {
111 vMatch.push_back(hash);
112 vnIndex.push_back(pos);
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;
std::vector< CTransactionRef > vtx
CBlockHeader GetBlockHeader() const
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
bool IsRelevantAndUpdate(const CTransaction &tx)
Also adds any outputs which match the filter to the filter (to match their spending txes)
CBlockHeader header
Public only for unit testing.
std::vector< std::pair< unsigned int, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Data structure that represents a partial merkle tree.
unsigned int nTransactions
the total number of transactions in the block
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
bool fBad
flag set when encountering invalid data
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
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)
std::vector< uint256 > vHash
txids and internal hashes
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...
unsigned int CalcTreeWidth(int height) const
helper function to efficiently calculate the number of nodes at given height in the merkle tree
static const unsigned int MAX_BLOCK_WEIGHT
The maximum allowed weight for a block, see BIP 141 (network rule)
static const size_t MIN_TRANSACTION_WEIGHT
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
std::vector< bool > BytesToBits(const std::vector< unsigned char > &bytes)
std::vector< unsigned char > BitsToBytes(const std::vector< bool > &bits)