Changeset View
Changeset View
Standalone View
Standalone View
src/merkleblock.h
Show All 10 Lines | |||||
#include "serialize.h" | #include "serialize.h" | ||||
#include "uint256.h" | #include "uint256.h" | ||||
#include <vector> | #include <vector> | ||||
/** | /** | ||||
* Data structure that represents a partial merkle tree. | * Data structure that represents a partial merkle tree. | ||||
* | * | ||||
* It represents a subset of the txid's of a known block, in a way that | * It represents a subset of the txhashes of a known block, in a way that | ||||
* allows recovery of the list of txid's and the merkle root, in an | * allows recovery of the list of txhashes and the merkle root, in an | ||||
* authenticated way. | * authenticated way. | ||||
* | * | ||||
* The encoding works as follows: we traverse the tree in depth-first order, | * The encoding works as follows: we traverse the tree in depth-first order, | ||||
* storing a bit for each traversed node, signifying whether the node is the | * storing a bit for each traversed node, signifying whether the node is the | ||||
* parent of at least one matched leaf txid (or a matched txid itself). In | * parent of at least one matched leaf txhash (or a matched txhash itself). In | ||||
* case we are at the leaf level, or this bit is 0, its merkle node hash is | * case we are at the leaf level, or this bit is 0, its merkle node hash is | ||||
* stored, and its children are not explorer further. Otherwise, no hash is | * stored, and its children are not explorer further. Otherwise, no hash is | ||||
* stored, but we recurse into both (or the only) child branch. During | * stored, but we recurse into both (or the only) child branch. During | ||||
* decoding, the same depth-first traversal is performed, consuming bits and | * decoding, the same depth-first traversal is performed, consuming bits and | ||||
* hashes as they written during encoding. | * hashes as they written during encoding. | ||||
* | * | ||||
* The serialization is fixed and provides a hard guarantee about the | * The serialization is fixed and provides a hard guarantee about the | ||||
* encoded size: | * encoded size: | ||||
Show All 15 Lines | |||||
* (<= 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; | unsigned int nTransactions; | ||||
/** node-is-parent-of-matched-txid bits */ | /** node-is-parent-of-matched-txhash bits */ | ||||
std::vector<bool> vBits; | std::vector<bool> vBits; | ||||
/** txids and internal hashes */ | /** txhashes 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) { | unsigned int CalcTreeWidth(int height) { | ||||
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) */ | * txhashes themselves) */ | ||||
uint256 CalcHash(int height, unsigned int pos, | uint256 CalcHash(int height, unsigned int pos, | ||||
const std::vector<uint256> &vTxid); | const std::vector<uint256> &vTxhash); | ||||
/** 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, unsigned int pos, | ||||
const std::vector<uint256> &vTxid, | const std::vector<uint256> &vTxhash, | ||||
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, unsigned int pos, | ||||
Show All 22 Lines | inline void SerializationOp(Stream &s, Operation ser_action) { | ||||
for (unsigned int p = 0; p < vBits.size(); p++) | for (unsigned int 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> &vTxhash, | ||||
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 txhashes 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<unsigned int> &vnIndex); | ||||
}; | }; | ||||
/** | /** | ||||
Show All 12 Lines | public: | ||||
/** | /** | ||||
* Create from a CBlock, filtering transactions according to filter. Note | * Create from a CBlock, filtering transactions according to 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); | ||||
// Create from a CBlock, matching the txids in the set. | // Create from a CBlock, matching the txhashes in the set. | ||||
CMerkleBlock(const CBlock &block, const std::set<uint256> &txids); | CMerkleBlock(const CBlock &block, const std::set<txhash_t> &txhashes); | ||||
CMerkleBlock() {} | CMerkleBlock() {} | ||||
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(header); | READWRITE(header); | ||||
READWRITE(txn); | READWRITE(txn); | ||||
} | } | ||||
}; | }; | ||||
#endif // BITCOIN_MERKLEBLOCK_H | #endif // BITCOIN_MERKLEBLOCK_H |