Bitcoin Core  0.19.99
P2P Digital Currency
merkleblock.h
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2018 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 <serialize.h>
10 #include <uint256.h>
11 #include <primitives/block.h>
12 #include <bloom.h>
13 
14 #include <vector>
15 
51 {
52 protected:
54  unsigned int nTransactions;
55 
57  std::vector<bool> vBits;
58 
60  std::vector<uint256> vHash;
61 
63  bool fBad;
64 
66  unsigned int CalcTreeWidth(int height) const {
67  return (nTransactions+(1 << height)-1) >> height;
68  }
69 
71  uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid);
72 
74  void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
75 
80  uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
81 
82 public:
83 
86 
87  template <typename Stream, typename Operation>
88  inline void SerializationOp(Stream& s, Operation ser_action) {
89  READWRITE(nTransactions);
90  READWRITE(vHash);
91  std::vector<unsigned char> vBytes;
92  if (ser_action.ForRead()) {
93  READWRITE(vBytes);
94  CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree*>(this));
95  us.vBits.resize(vBytes.size() * 8);
96  for (unsigned int p = 0; p < us.vBits.size(); p++)
97  us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0;
98  us.fBad = false;
99  } else {
100  vBytes.resize((vBits.size()+7)/8);
101  for (unsigned int p = 0; p < vBits.size(); p++)
102  vBytes[p / 8] |= vBits[p] << (p % 8);
103  READWRITE(vBytes);
104  }
105  }
106 
108  CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
109 
111 
117  uint256 ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
118 
122  unsigned int GetNumTransactions() const { return nTransactions; };
123 
124 };
125 
126 
134 {
135 public:
139 
146  std::vector<std::pair<unsigned int, uint256> > vMatchedTxn;
147 
153  CMerkleBlock(const CBlock& block, CBloomFilter& filter) : CMerkleBlock(block, &filter, nullptr) { }
154 
155  // Create from a CBlock, matching the txids in the set
156  CMerkleBlock(const CBlock& block, const std::set<uint256>& txids) : CMerkleBlock(block, nullptr, &txids) { }
157 
159 
161 
162  template <typename Stream, typename Operation>
163  inline void SerializationOp(Stream& s, Operation ser_action) {
164  READWRITE(header);
165  READWRITE(txn);
166  }
167 
168 private:
169  // Combined constructor to consolidate code
170  CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids);
171 };
172 
173 #endif // BITCOIN_MERKLEBLOCK_H
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:137
uint256 ExtractMatches(std::vector< uint256 > &vMatch, std::vector< unsigned int > &vnIndex)
extract the matching txid&#39;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 ...
Definition: merkleblock.cpp:59
void SerializationOp(Stream &s, Operation ser_action)
Definition: merkleblock.h:163
unsigned int nTransactions
the total number of transactions in the block
Definition: merkleblock.h:54
Definition: block.h:72
bool fBad
flag set when encountering invalid data
Definition: merkleblock.h:63
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:44
unsigned int CalcTreeWidth(int height) const
helper function to efficiently calculate the number of nodes at given height in the merkle tree ...
Definition: merkleblock.h:66
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:50
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:60
Used to relay blocks as header + vector<merkle branch> to filtered nodes.
Definition: merkleblock.h:133
unsigned int GetNumTransactions() const
Get number of transactions the merkle proof is indicating for cross-reference with local blockchain k...
Definition: merkleblock.h:122
CPartialMerkleTree txn
Definition: merkleblock.h:138
ADD_SERIALIZE_METHODS
serialization implementation
Definition: merkleblock.h:85
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
Definition: merkleblock.h:57
256-bit opaque blob.
Definition: uint256.h:120
CMerkleBlock(const CBlock &block, const std::set< uint256 > &txids)
Definition: merkleblock.h:156
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...
Definition: merkleblock.cpp:77
std::vector< std::pair< unsigned int, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:146
CMerkleBlock(const CBlock &block, CBloomFilter &filter)
Create from a CBlock, filtering transactions according to filter Note that this will call IsRelevantA...
Definition: merkleblock.h:153
void SerializationOp(Stream &s, Operation ser_action)
Definition: merkleblock.h:88
#define READWRITE(...)
Definition: serialize.h:186
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:20
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&#39;s themselves) ...
Definition: merkleblock.cpp:39