Bitcoin ABC  0.26.3
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
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:55
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:45
Used to create a Merkle proof (usually from a subset of transactions), which consists of a block head...
Definition: merkleblock.h:147
SERIALIZE_METHODS(CMerkleBlock, obj)
Definition: merkleblock.h:177
CMerkleBlock(const CBlock &block, const std::set< TxId > &txids)
Create a Merkle proof for a set of transactions.
Definition: merkleblock.h:172
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:150
CMerkleBlock(const CBlock &block, CBloomFilter &filter)
Create a Merkle proof according to a bloom filter.
Definition: merkleblock.h:166
std::vector< std::pair< size_t, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:159
CPartialMerkleTree txn
Definition: merkleblock.h:151
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:56
uint32_t nTransactions
the total number of transactions in the block
Definition: merkleblock.h:59
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...
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
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
uint32_t GetNumTransactions() const
Get number of transactions the merkle proof is indicating for cross-reference with local blockchain k...
Definition: merkleblock.h:132
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...
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:65
SERIALIZE_METHODS(CPartialMerkleTree, obj)
Definition: merkleblock.h:102
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
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
256-bit opaque blob.
Definition: uint256.h:127
std::vector< uint8_t > BitsToBytes(const std::vector< bool > &bits)
Definition: merkleblock.cpp:11
std::vector< bool > BytesToBits(const std::vector< uint8_t > &bytes)
Definition: merkleblock.cpp:19
#define SER_WRITE(obj, code)
Definition: serialize.h:187
#define SER_READ(obj, code)
Definition: serialize.h:183
#define READWRITE(...)
Definition: serialize.h:180