Bitcoin Core  26.99.0
P2P Digital Currency
merkleblock.h
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2021 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 <common/bloom.h>
10 #include <primitives/block.h>
11 #include <serialize.h>
12 #include <uint256.h>
13 
14 #include <set>
15 #include <vector>
16 
17 // Helper functions for serialization.
18 std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits);
19 std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes);
20 
56 {
57 protected:
59  unsigned int nTransactions;
60 
62  std::vector<bool> vBits;
63 
65  std::vector<uint256> vHash;
66 
68  bool fBad;
69 
71  unsigned int CalcTreeWidth(int height) const {
72  return (nTransactions+(1 << height)-1) >> height;
73  }
74 
76  uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid);
77 
79  void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
80 
85  uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
86 
87 public:
88 
90  {
91  READWRITE(obj.nTransactions, obj.vHash);
92  std::vector<unsigned char> bytes;
93  SER_WRITE(obj, bytes = BitsToBytes(obj.vBits));
94  READWRITE(bytes);
95  SER_READ(obj, obj.vBits = BytesToBits(bytes));
96  SER_READ(obj, obj.fBad = false);
97  }
98 
100  CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
101 
103 
109  uint256 ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex);
110 
114  unsigned int GetNumTransactions() const { return nTransactions; };
115 
116 };
117 
118 
126 {
127 public:
131 
138  std::vector<std::pair<unsigned int, uint256> > vMatchedTxn;
139 
145  CMerkleBlock(const CBlock& block, CBloomFilter& filter) : CMerkleBlock(block, &filter, nullptr) { }
146 
147  // Create from a CBlock, matching the txids in the set
148  CMerkleBlock(const CBlock& block, const std::set<Txid>& txids) : CMerkleBlock{block, nullptr, &txids} {}
149 
151 
152  SERIALIZE_METHODS(CMerkleBlock, obj) { READWRITE(obj.header, obj.txn); }
153 
154 private:
155  // Combined constructor to consolidate code
156  CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<Txid>* txids);
157 };
158 
159 #endif // BITCOIN_MERKLEBLOCK_H
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:22
Definition: block.h:69
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:45
Used to relay blocks as header + vector<merkle branch> to filtered nodes.
Definition: merkleblock.h:126
SERIALIZE_METHODS(CMerkleBlock, obj)
Definition: merkleblock.h:152
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:129
CMerkleBlock(const CBlock &block, CBloomFilter &filter)
Create from a CBlock, filtering transactions according to filter Note that this will call IsRelevantA...
Definition: merkleblock.h:145
std::vector< std::pair< unsigned int, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:138
CMerkleBlock(const CBlock &block, const std::set< Txid > &txids)
Definition: merkleblock.h:148
CPartialMerkleTree txn
Definition: merkleblock.h:130
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:56
unsigned int nTransactions
the total number of transactions in the block
Definition: merkleblock.h:59
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
Definition: merkleblock.h:62
bool fBad
flag set when encountering invalid data
Definition: merkleblock.h:68
uint256 ExtractMatches(std::vector< uint256 > &vMatch, std::vector< unsigned int > &vnIndex)
extract the matching txid's represented by this partial merkle tree and their respective indices with...
unsigned int GetNumTransactions() const
Get number of transactions the merkle proof is indicating for cross-reference with local blockchain k...
Definition: merkleblock.h:114
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
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's themselves)
Definition: merkleblock.cpp:57
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:65
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
SERIALIZE_METHODS(CPartialMerkleTree, obj)
Definition: merkleblock.h:89
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:71
256-bit opaque blob.
Definition: uint256.h:106
std::vector< bool > BytesToBits(const std::vector< unsigned char > &bytes)
Definition: merkleblock.cpp:21
std::vector< unsigned char > BitsToBytes(const std::vector< bool > &bits)
Definition: merkleblock.cpp:12
#define SER_WRITE(obj, code)
Definition: serialize.h:161
#define SER_READ(obj, code)
Definition: serialize.h:160
#define READWRITE(...)
Definition: serialize.h:159