Bitcoin ABC  0.22.12
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 
53 protected:
55  uint32_t nTransactions;
56 
58  std::vector<bool> vBits;
59 
61  std::vector<uint256> vHash;
62 
64  bool fBad;
65 
70  size_t CalcTreeWidth(int height) const {
71  return (nTransactions + (1 << height) - 1) >> height;
72  }
73 
78  uint256 CalcHash(int height, size_t pos, const std::vector<uint256> &vTxid);
79 
84  void TraverseAndBuild(int height, size_t pos,
85  const std::vector<uint256> &vTxid,
86  const std::vector<bool> &vMatch);
87 
93  uint256 TraverseAndExtract(int height, size_t pos, size_t &nBitsUsed,
94  size_t &nHashUsed, std::vector<uint256> &vMatch,
95  std::vector<size_t> &vnIndex);
96 
97 public:
100 
101  template <typename Stream, typename Operation>
102  inline void SerializationOp(Stream &s, Operation ser_action) {
103  READWRITE(nTransactions);
104  READWRITE(vHash);
105  std::vector<uint8_t> vBytes;
106  if (ser_action.ForRead()) {
107  READWRITE(vBytes);
108  CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree *>(this));
109  us.vBits.resize(vBytes.size() * 8);
110  for (size_t p = 0; p < us.vBits.size(); p++) {
111  us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0;
112  }
113  us.fBad = false;
114  } else {
115  vBytes.resize((vBits.size() + 7) / 8);
116  for (size_t p = 0; p < vBits.size(); p++) {
117  vBytes[p / 8] |= vBits[p] << (p % 8);
118  }
119  READWRITE(vBytes);
120  }
121  }
122 
127  CPartialMerkleTree(const std::vector<uint256> &vTxid,
128  const std::vector<bool> &vMatch);
129 
131 
137  uint256 ExtractMatches(std::vector<uint256> &vMatch,
138  std::vector<size_t> &vnIndex);
139 
144  uint32_t GetNumTransactions() const { return nTransactions; };
145 };
146 
160 public:
164 
171  std::vector<std::pair<size_t, uint256>> vMatchedTxn;
172 
178  CMerkleBlock(const CBlock &block, CBloomFilter &filter)
179  : CMerkleBlock(block, &filter, nullptr) {}
180 
184  CMerkleBlock(const CBlock &block, const std::set<TxId> &txids)
185  : CMerkleBlock(block, nullptr, &txids) {}
186 
188 
190 
191  template <typename Stream, typename Operation>
192  inline void SerializationOp(Stream &s, Operation ser_action) {
193  READWRITE(header);
194  READWRITE(txn);
195  }
196 
197 private:
202  CMerkleBlock(const CBlock &block, CBloomFilter *filter,
203  const std::set<TxId> *txids);
204 };
205 
206 #endif // BITCOIN_MERKLEBLOCK_H
uint256 ExtractMatches(std::vector< uint256 > &vMatch, std::vector< size_t > &vnIndex)
Extract the matching txid&#39;s represented by this partial merkle tree and their respective indices with...
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:162
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:70
void SerializationOp(Stream &s, Operation ser_action)
Definition: merkleblock.h:192
Definition: block.h:62
bool fBad
flag set when encountering invalid data
Definition: merkleblock.h:64
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:45
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:52
uint32_t nTransactions
the total number of transactions in the block
Definition: merkleblock.h:55
uint32_t GetNumTransactions() const
Get number of transactions the merkle proof is indicating for cross-reference with local blockchain k...
Definition: merkleblock.h:144
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:61
Used to create a Merkle proof (usually from a subset of transactions), which consists of a block head...
Definition: merkleblock.h:159
std::vector< std::pair< size_t, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:171
CMerkleBlock(const CBlock &block, const std::set< TxId > &txids)
Create a Merkle proof for a set of transactions.
Definition: merkleblock.h:184
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:96
CPartialMerkleTree txn
Definition: merkleblock.h:163
ADD_SERIALIZE_METHODS
serialization implementation
Definition: merkleblock.h:99
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
Definition: merkleblock.h:58
256-bit opaque blob.
Definition: uint256.h:120
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:72
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&#39;s themselves) ...
Definition: merkleblock.cpp:47
CMerkleBlock(const CBlock &block, CBloomFilter &filter)
Create a Merkle proof according to a bloom filter.
Definition: merkleblock.h:178
void SerializationOp(Stream &s, Operation ser_action)
Definition: merkleblock.h:102
#define READWRITE(...)
Definition: serialize.h:191
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:22