Changeset View
Changeset View
Standalone View
Standalone View
src/merkleblock.h
Show First 20 Lines • Show All 46 Lines • ▼ Show 20 Lines | |||||
* - varint number of bytes of flag bits (1-3 bytes) | * - varint number of bytes of flag bits (1-3 bytes) | ||||
* - byte[] flag bits, packed per 8 in a byte, least significant bit first | * - byte[] flag bits, packed per 8 in a byte, least significant bit first | ||||
* (<= 2*N-1 bits) | * (<= 2*N-1 bits) | ||||
* The size constraints follow from this. | * The size constraints follow from this. | ||||
*/ | */ | ||||
class CPartialMerkleTree { | class CPartialMerkleTree { | ||||
protected: | protected: | ||||
/** the total number of transactions in the block */ | /** the total number of transactions in the block */ | ||||
unsigned int nTransactions; | uint32_t nTransactions; | ||||
/** node-is-parent-of-matched-txid bits */ | /** node-is-parent-of-matched-txid bits */ | ||||
std::vector<bool> vBits; | std::vector<bool> vBits; | ||||
/** txids and internal hashes */ | /** txids and internal hashes */ | ||||
std::vector<uint256> vHash; | std::vector<uint256> vHash; | ||||
/** flag set when encountering invalid data */ | /** flag set when encountering invalid data */ | ||||
bool fBad; | bool fBad; | ||||
/** | /** | ||||
* Helper function to efficiently calculate the number of nodes at given | * Helper function to efficiently calculate the number of nodes at given | ||||
* height in the merkle tree. | * height in the merkle tree. | ||||
*/ | */ | ||||
unsigned int CalcTreeWidth(int height) const { | size_t CalcTreeWidth(int height) const { | ||||
return (nTransactions + (1 << height) - 1) >> height; | return (nTransactions + (1 << height) - 1) >> height; | ||||
} | } | ||||
/** | /** | ||||
* Calculate the hash of a node in the merkle tree (at leaf level: the | * Calculate the hash of a node in the merkle tree (at leaf level: the | ||||
* txid's themselves) | * txid's themselves) | ||||
*/ | */ | ||||
uint256 CalcHash(int height, unsigned int pos, | uint256 CalcHash(int height, size_t pos, const std::vector<uint256> &vTxid); | ||||
const std::vector<uint256> &vTxid); | |||||
/** | /** | ||||
* Recursive function that traverses tree nodes, storing the data as bits | * Recursive function that traverses tree nodes, storing the data as bits | ||||
* and hashes. | * and hashes. | ||||
*/ | */ | ||||
void TraverseAndBuild(int height, unsigned int pos, | void TraverseAndBuild(int height, size_t pos, | ||||
const std::vector<uint256> &vTxid, | const std::vector<uint256> &vTxid, | ||||
const std::vector<bool> &vMatch); | const std::vector<bool> &vMatch); | ||||
/** | /** | ||||
* Recursive function that traverses tree nodes, consuming the bits and | * Recursive function that traverses tree nodes, consuming the bits and | ||||
* hashes produced by TraverseAndBuild. It returns the hash of the | * hashes produced by TraverseAndBuild. It returns the hash of the | ||||
* respective node and its respective index. | * respective node and its respective index. | ||||
*/ | */ | ||||
uint256 TraverseAndExtract(int height, unsigned int pos, | uint256 TraverseAndExtract(int height, size_t pos, size_t &nBitsUsed, | ||||
unsigned int &nBitsUsed, unsigned int &nHashUsed, | size_t &nHashUsed, std::vector<uint256> &vMatch, | ||||
std::vector<uint256> &vMatch, | std::vector<size_t> &vnIndex); | ||||
std::vector<unsigned int> &vnIndex); | |||||
public: | public: | ||||
/** serialization implementation */ | /** serialization implementation */ | ||||
ADD_SERIALIZE_METHODS; | ADD_SERIALIZE_METHODS; | ||||
template <typename Stream, typename Operation> | template <typename Stream, typename Operation> | ||||
inline void SerializationOp(Stream &s, Operation ser_action) { | inline void SerializationOp(Stream &s, Operation ser_action) { | ||||
READWRITE(nTransactions); | READWRITE(nTransactions); | ||||
READWRITE(vHash); | READWRITE(vHash); | ||||
std::vector<uint8_t> vBytes; | std::vector<uint8_t> vBytes; | ||||
if (ser_action.ForRead()) { | if (ser_action.ForRead()) { | ||||
READWRITE(vBytes); | READWRITE(vBytes); | ||||
CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree *>(this)); | CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree *>(this)); | ||||
us.vBits.resize(vBytes.size() * 8); | us.vBits.resize(vBytes.size() * 8); | ||||
for (unsigned int p = 0; p < us.vBits.size(); p++) { | for (size_t p = 0; p < us.vBits.size(); p++) { | ||||
us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0; | us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0; | ||||
} | } | ||||
us.fBad = false; | us.fBad = false; | ||||
} else { | } else { | ||||
vBytes.resize((vBits.size() + 7) / 8); | vBytes.resize((vBits.size() + 7) / 8); | ||||
for (unsigned int p = 0; p < vBits.size(); p++) { | for (size_t p = 0; p < vBits.size(); p++) { | ||||
vBytes[p / 8] |= vBits[p] << (p % 8); | vBytes[p / 8] |= vBits[p] << (p % 8); | ||||
} | } | ||||
READWRITE(vBytes); | READWRITE(vBytes); | ||||
} | } | ||||
} | } | ||||
/** | /** | ||||
* Construct a partial merkle tree from a list of transaction ids, and a | * Construct a partial merkle tree from a list of transaction ids, and a | ||||
* mask that selects a subset of them. | * mask that selects a subset of them. | ||||
*/ | */ | ||||
CPartialMerkleTree(const std::vector<uint256> &vTxid, | CPartialMerkleTree(const std::vector<uint256> &vTxid, | ||||
const std::vector<bool> &vMatch); | const std::vector<bool> &vMatch); | ||||
CPartialMerkleTree(); | CPartialMerkleTree(); | ||||
/** | /** | ||||
* Extract the matching txid's represented by this partial merkle tree and | * Extract the matching txid's represented by this partial merkle tree and | ||||
* their respective indices within the partial tree. Returns the merkle | * their respective indices within the partial tree. Returns the merkle | ||||
* root, or 0 in case of failure. | * root, or 0 in case of failure. | ||||
*/ | */ | ||||
uint256 ExtractMatches(std::vector<uint256> &vMatch, | uint256 ExtractMatches(std::vector<uint256> &vMatch, | ||||
std::vector<unsigned int> &vnIndex); | std::vector<size_t> &vnIndex); | ||||
}; | }; | ||||
/** | /** | ||||
* Used to create a Merkle proof (usually from a subset of transactions), | * Used to create a Merkle proof (usually from a subset of transactions), | ||||
* which consists of a block header and partial Merkle Tree. | * which consists of a block header and partial Merkle Tree. | ||||
* SPV clients typically use this Merkle proof to limit bandwidth and | * SPV clients typically use this Merkle proof to limit bandwidth and | ||||
* computation requirements to process incoming transactions. | * computation requirements to process incoming transactions. | ||||
* From the peer-node's perspective, the SPV client is a "filtered node". | * From the peer-node's perspective, the SPV client is a "filtered node". | ||||
* See BIP37 for details: | * See BIP37 for details: | ||||
* https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki | * https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki | ||||
* | * | ||||
* NOTE: The class assumes that the given CBlock has *at least* 1 transaction. | * NOTE: The class assumes that the given CBlock has *at least* 1 transaction. | ||||
* If the CBlock has 0 txs, it will hit an assertion. | * If the CBlock has 0 txs, it will hit an assertion. | ||||
*/ | */ | ||||
class CMerkleBlock { | class CMerkleBlock { | ||||
public: | public: | ||||
/** Public only for unit testing */ | /** Public only for unit testing */ | ||||
CBlockHeader header; | CBlockHeader header; | ||||
CPartialMerkleTree txn; | CPartialMerkleTree txn; | ||||
/** Public only for unit testing and relay testing (not relayed) */ | /** Public only for unit testing and relay testing (not relayed) */ | ||||
std::vector<std::pair<unsigned int, uint256>> vMatchedTxn; | std::vector<std::pair<size_t, uint256>> vMatchedTxn; | ||||
/** | /** | ||||
* Create a Merkle proof according to a bloom filter. Note | * Create a Merkle proof according to a bloom filter. Note | ||||
* that this will call IsRelevantAndUpdate on the filter for each | * that this will call IsRelevantAndUpdate on the filter for each | ||||
* transaction, thus the filter will likely be modified. | * transaction, thus the filter will likely be modified. | ||||
*/ | */ | ||||
CMerkleBlock(const CBlock &block, CBloomFilter &filter); | CMerkleBlock(const CBlock &block, CBloomFilter &filter); | ||||
Show All 17 Lines |