Changeset View
Changeset View
Standalone View
Standalone View
src/merkleblock.h
// 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. | ||||
#ifndef BITCOIN_MERKLEBLOCK_H | #ifndef BITCOIN_MERKLEBLOCK_H | ||||
#define BITCOIN_MERKLEBLOCK_H | #define BITCOIN_MERKLEBLOCK_H | ||||
#include <bloom.h> | #include <bloom.h> | ||||
#include <primitives/block.h> | #include <primitives/block.h> | ||||
#include <serialize.h> | #include <serialize.h> | ||||
#include <uint256.h> | #include <uint256.h> | ||||
#include <vector> | #include <vector> | ||||
// Helper functions for serialization. | |||||
std::vector<uint8_t> BitsToBytes(const std::vector<bool> &bits); | |||||
std::vector<bool> BytesToBits(const std::vector<uint8_t> &bytes); | |||||
/** | /** | ||||
* 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 txid's 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 txid's 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, | ||||
▲ Show 20 Lines • Show All 66 Lines • ▼ Show 20 Lines | protected: | ||||
* 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, size_t pos, size_t &nBitsUsed, | uint256 TraverseAndExtract(int height, size_t pos, size_t &nBitsUsed, | ||||
size_t &nHashUsed, std::vector<uint256> &vMatch, | size_t &nHashUsed, std::vector<uint256> &vMatch, | ||||
std::vector<size_t> &vnIndex); | std::vector<size_t> &vnIndex); | ||||
public: | public: | ||||
/** serialization implementation */ | SERIALIZE_METHODS(CPartialMerkleTree, obj) { | ||||
ADD_SERIALIZE_METHODS; | READWRITE(obj.nTransactions, obj.vHash); | ||||
std::vector<uint8_t> bytes; | |||||
template <typename Stream, typename Operation> | SER_WRITE(obj, bytes = BitsToBytes(obj.vBits)); | ||||
inline void SerializationOp(Stream &s, Operation ser_action) { | READWRITE(bytes); | ||||
READWRITE(nTransactions); | SER_READ(obj, obj.vBits = BytesToBits(bytes)); | ||||
READWRITE(vHash); | SER_READ(obj, obj.fBad = false); | ||||
std::vector<uint8_t> vBytes; | |||||
if (ser_action.ForRead()) { | |||||
READWRITE(vBytes); | |||||
CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree *>(this)); | |||||
us.vBits.resize(vBytes.size() * 8); | |||||
for (size_t p = 0; p < us.vBits.size(); p++) { | |||||
us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0; | |||||
} | |||||
us.fBad = false; | |||||
} else { | |||||
vBytes.resize((vBits.size() + 7) / 8); | |||||
for (size_t p = 0; p < vBits.size(); p++) { | |||||
vBytes[p / 8] |= vBits[p] << (p % 8); | |||||
} | |||||
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); | ||||
▲ Show 20 Lines • Show All 52 Lines • ▼ Show 20 Lines | public: | ||||
/** | /** | ||||
* Create a Merkle proof for a set of transactions. | * Create a Merkle proof for a set of transactions. | ||||
*/ | */ | ||||
CMerkleBlock(const CBlock &block, const std::set<TxId> &txids) | CMerkleBlock(const CBlock &block, const std::set<TxId> &txids) | ||||
: CMerkleBlock(block, nullptr, &txids) {} | : CMerkleBlock(block, nullptr, &txids) {} | ||||
CMerkleBlock() {} | CMerkleBlock() {} | ||||
ADD_SERIALIZE_METHODS; | SERIALIZE_METHODS(CMerkleBlock, obj) { READWRITE(obj.header, obj.txn); } | ||||
template <typename Stream, typename Operation> | |||||
inline void SerializationOp(Stream &s, Operation ser_action) { | |||||
READWRITE(header); | |||||
READWRITE(txn); | |||||
} | |||||
private: | private: | ||||
/** | /** | ||||
* Combined constructor to consolidate code. At most one of filter | * Combined constructor to consolidate code. At most one of filter | ||||
* or txids may be provided. | * or txids may be provided. | ||||
*/ | */ | ||||
CMerkleBlock(const CBlock &block, CBloomFilter *filter, | CMerkleBlock(const CBlock &block, CBloomFilter *filter, | ||||
const std::set<TxId> *txids); | const std::set<TxId> *txids); | ||||
}; | }; | ||||
#endif // BITCOIN_MERKLEBLOCK_H | #endif // BITCOIN_MERKLEBLOCK_H |