Bitcoin ABC  0.24.7
P2P Digital Currency
merkleblock.h
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2016 The Bitcoin Core developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 
6 #ifndef BITCOIN_MERKLEBLOCK_H
7 #define BITCOIN_MERKLEBLOCK_H
8 
9 #include <bloom.h>
10 #include <primitives/block.h>
11 #include <serialize.h>
12 #include <uint256.h>
13 
14 #include <vector>
15 
16 // Helper functions for serialization.
17 std::vector<uint8_t> BitsToBytes(const std::vector<bool> &bits);
18 std::vector<bool> BytesToBits(const std::vector<uint8_t> &bytes);
19 
57 protected:
59  uint32_t nTransactions;
60 
62  std::vector<bool> vBits;
63 
65  std::vector<uint256> vHash;
66 
68  bool fBad;
69 
74  size_t CalcTreeWidth(int height) const {
75  return (nTransactions + (1 << height) - 1) >> height;
76  }
77 
82  uint256 CalcHash(int height, size_t pos, const std::vector<uint256> &vTxid);
83 
88  void TraverseAndBuild(int height, size_t pos,
89  const std::vector<uint256> &vTxid,
90  const std::vector<bool> &vMatch);
91 
97  uint256 TraverseAndExtract(int height, size_t pos, size_t &nBitsUsed,
98  size_t &nHashUsed, std::vector<uint256> &vMatch,
99  std::vector<size_t> &vnIndex);
100 
101 public:
103  READWRITE(obj.nTransactions, obj.vHash);
104  std::vector<uint8_t> bytes;
105  SER_WRITE(obj, bytes = BitsToBytes(obj.vBits));
106  READWRITE(bytes);
107  SER_READ(obj, obj.vBits = BytesToBits(bytes));
108  SER_READ(obj, obj.fBad = false);
109  }
110 
115  CPartialMerkleTree(const std::vector<uint256> &vTxid,
116  const std::vector<bool> &vMatch);
117 
119 
125  uint256 ExtractMatches(std::vector<uint256> &vMatch,
126  std::vector<size_t> &vnIndex);
127 
132  uint32_t GetNumTransactions() const { return nTransactions; };
133 };
134 
148 public:
152 
159  std::vector<std::pair<size_t, uint256>> vMatchedTxn;
160 
166  CMerkleBlock(const CBlock &block, CBloomFilter &filter)
167  : CMerkleBlock(block, &filter, nullptr) {}
168 
172  CMerkleBlock(const CBlock &block, const std::set<TxId> &txids)
173  : CMerkleBlock(block, nullptr, &txids) {}
174 
176 
177  SERIALIZE_METHODS(CMerkleBlock, obj) { READWRITE(obj.header, obj.txn); }
178 
179 private:
184  CMerkleBlock(const CBlock &block, CBloomFilter *filter,
185  const std::set<TxId> *txids);
186 };
187 
188 #endif // BITCOIN_MERKLEBLOCK_H
block.h
CPartialMerkleTree::SERIALIZE_METHODS
SERIALIZE_METHODS(CPartialMerkleTree, obj)
Definition: merkleblock.h:102
CPartialMerkleTree::TraverseAndExtract
uint256 TraverseAndExtract(int height, size_t pos, size_t &nBitsUsed, size_t &nHashUsed, std::vector< uint256 > &vMatch, std::vector< size_t > &vnIndex)
Recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBu...
Definition: merkleblock.cpp:112
CPartialMerkleTree::vBits
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
Definition: merkleblock.h:62
CPartialMerkleTree
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:56
CBlockHeader
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:22
CBloomFilter
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:45
CMerkleBlock::CMerkleBlock
CMerkleBlock(const CBlock &block, const std::set< TxId > &txids)
Create a Merkle proof for a set of transactions.
Definition: merkleblock.h:172
CMerkleBlock
Used to create a Merkle proof (usually from a subset of transactions), which consists of a block head...
Definition: merkleblock.h:147
uint256.h
CMerkleBlock::header
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:150
CPartialMerkleTree::TraverseAndBuild
void TraverseAndBuild(int height, size_t pos, const std::vector< uint256 > &vTxid, const std::vector< bool > &vMatch)
Recursive function that traverses tree nodes, storing the data as bits and hashes.
Definition: merkleblock.cpp:88
CPartialMerkleTree::CalcHash
uint256 CalcHash(int height, size_t pos, const std::vector< uint256 > &vTxid)
Calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves)
Definition: merkleblock.cpp:63
bloom.h
BitsToBytes
std::vector< uint8_t > BitsToBytes(const std::vector< bool > &bits)
Definition: merkleblock.cpp:11
CPartialMerkleTree::ExtractMatches
uint256 ExtractMatches(std::vector< uint256 > &vMatch, std::vector< size_t > &vnIndex)
Extract the matching txid's represented by this partial merkle tree and their respective indices with...
Definition: merkleblock.cpp:180
uint256
256-bit opaque blob.
Definition: uint256.h:127
READWRITE
#define READWRITE(...)
Definition: serialize.h:179
CPartialMerkleTree::fBad
bool fBad
flag set when encountering invalid data
Definition: merkleblock.h:68
CMerkleBlock::SERIALIZE_METHODS
SERIALIZE_METHODS(CMerkleBlock, obj)
Definition: merkleblock.h:177
CPartialMerkleTree::CalcTreeWidth
size_t CalcTreeWidth(int height) const
Helper function to efficiently calculate the number of nodes at given height in the merkle tree.
Definition: merkleblock.h:74
CBlock
Definition: block.h:55
CMerkleBlock::txn
CPartialMerkleTree txn
Definition: merkleblock.h:151
BytesToBits
std::vector< bool > BytesToBits(const std::vector< uint8_t > &bytes)
Definition: merkleblock.cpp:19
serialize.h
CPartialMerkleTree::nTransactions
uint32_t nTransactions
the total number of transactions in the block
Definition: merkleblock.h:59
CMerkleBlock::CMerkleBlock
CMerkleBlock(const CBlock &block, CBloomFilter &filter)
Create a Merkle proof according to a bloom filter.
Definition: merkleblock.h:166
SER_WRITE
#define SER_WRITE(obj, code)
Definition: serialize.h:186
SER_READ
#define SER_READ(obj, code)
Definition: serialize.h:182
CMerkleBlock::vMatchedTxn
std::vector< std::pair< size_t, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:159
CPartialMerkleTree::vHash
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:65
CPartialMerkleTree::CPartialMerkleTree
CPartialMerkleTree()
Definition: merkleblock.cpp:178
CMerkleBlock::CMerkleBlock
CMerkleBlock()
Definition: merkleblock.h:175
CPartialMerkleTree::GetNumTransactions
uint32_t GetNumTransactions() const
Get number of transactions the merkle proof is indicating for cross-reference with local blockchain k...
Definition: merkleblock.h:132