Bitcoin Core  0.20.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 
16 // Helper functions for serialization.
17 std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits);
18 std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes);
19 
55 {
56 protected:
58  unsigned int nTransactions;
59 
61  std::vector<bool> vBits;
62 
64  std::vector<uint256> vHash;
65 
67  bool fBad;
68 
70  unsigned int CalcTreeWidth(int height) const {
71  return (nTransactions+(1 << height)-1) >> height;
72  }
73 
75  uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid);
76 
78  void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
79 
84  uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
85 
86 public:
87 
89  {
90  READWRITE(obj.nTransactions, obj.vHash);
91  std::vector<unsigned char> bytes;
92  SER_WRITE(obj, bytes = BitsToBytes(obj.vBits));
93  READWRITE(bytes);
94  SER_READ(obj, obj.vBits = BytesToBits(bytes));
95  SER_READ(obj, obj.fBad = false);
96  }
97 
99  CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
100 
102 
108  uint256 ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
109 
113  unsigned int GetNumTransactions() const { return nTransactions; };
114 
115 };
116 
117 
125 {
126 public:
130 
137  std::vector<std::pair<unsigned int, uint256> > vMatchedTxn;
138 
144  CMerkleBlock(const CBlock& block, CBloomFilter& filter) : CMerkleBlock(block, &filter, nullptr) { }
145 
146  // Create from a CBlock, matching the txids in the set
147  CMerkleBlock(const CBlock& block, const std::set<uint256>& txids) : CMerkleBlock(block, nullptr, &txids) { }
148 
150 
151  SERIALIZE_METHODS(CMerkleBlock, obj) { READWRITE(obj.header, obj.txn); }
152 
153 private:
154  // Combined constructor to consolidate code
155  CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids);
156 };
157 
158 #endif // BITCOIN_MERKLEBLOCK_H
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:128
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:77
unsigned int nTransactions
the total number of transactions in the block
Definition: merkleblock.h:58
Definition: block.h:62
bool fBad
flag set when encountering invalid data
Definition: merkleblock.h:67
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:70
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:54
std::vector< unsigned char > BitsToBytes(const std::vector< bool > &bits)
Definition: merkleblock.cpp:12
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:64
Used to relay blocks as header + vector<merkle branch> to filtered nodes.
Definition: merkleblock.h:124
unsigned int GetNumTransactions() const
Get number of transactions the merkle proof is indicating for cross-reference with local blockchain k...
Definition: merkleblock.h:113
CPartialMerkleTree txn
Definition: merkleblock.h:129
SERIALIZE_METHODS(CPartialMerkleTree, obj)
Definition: merkleblock.h:88
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
Definition: merkleblock.h:61
256-bit opaque blob.
Definition: uint256.h:123
CMerkleBlock(const CBlock &block, const std::set< uint256 > &txids)
Definition: merkleblock.h:147
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:95
std::vector< std::pair< unsigned int, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:137
CMerkleBlock(const CBlock &block, CBloomFilter &filter)
Create from a CBlock, filtering transactions according to filter Note that this will call IsRelevantA...
Definition: merkleblock.h:144
#define SER_READ(obj, code)
Definition: serialize.h:173
SERIALIZE_METHODS(CMerkleBlock, obj)
Definition: merkleblock.h:151
#define SER_WRITE(obj, code)
Definition: serialize.h:174
std::vector< bool > BytesToBits(const std::vector< unsigned char > &bytes)
Definition: merkleblock.cpp:21
#define READWRITE(...)
Definition: serialize.h:171
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:57