Bitcoin Core 29.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>
12#include <serialize.h>
13#include <uint256.h>
14
15#include <set>
16#include <vector>
17
18// Helper functions for serialization.
19std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits);
20std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes);
21
57{
58protected:
60 unsigned int nTransactions;
61
63 std::vector<bool> vBits;
64
66 std::vector<uint256> vHash;
67
69 bool fBad;
70
72 unsigned int CalcTreeWidth(int height) const {
73 return (nTransactions+(1 << height)-1) >> height;
74 }
75
77 uint256 CalcHash(int height, unsigned int pos, const std::vector<Txid> &vTxid);
78
80 void TraverseAndBuild(int height, unsigned int pos, const std::vector<Txid> &vTxid, const std::vector<bool> &vMatch);
81
86 uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<Txid> &vMatch, std::vector<unsigned int> &vnIndex);
87
88public:
89
91 {
92 READWRITE(obj.nTransactions, obj.vHash);
93 std::vector<unsigned char> bytes;
94 SER_WRITE(obj, bytes = BitsToBytes(obj.vBits));
95 READWRITE(bytes);
96 SER_READ(obj, obj.vBits = BytesToBits(bytes));
97 SER_READ(obj, obj.fBad = false);
98 }
99
101 CPartialMerkleTree(const std::vector<Txid> &vTxid, const std::vector<bool> &vMatch);
102
104
110 uint256 ExtractMatches(std::vector<Txid> &vMatch, std::vector<unsigned int> &vnIndex);
111
115 unsigned int GetNumTransactions() const { return nTransactions; };
116
117};
118
119
127{
128public:
132
139 std::vector<std::pair<unsigned int, Txid> > vMatchedTxn;
140
146 CMerkleBlock(const CBlock& block, CBloomFilter& filter) : CMerkleBlock(block, &filter, nullptr) { }
147
148 // Create from a CBlock, matching the txids in the set
149 CMerkleBlock(const CBlock& block, const std::set<Txid>& txids) : CMerkleBlock{block, nullptr, &txids} {}
150
151 CMerkleBlock() = default;
152
153 SERIALIZE_METHODS(CMerkleBlock, obj) { READWRITE(obj.header, obj.txn); }
154
155private:
156 // Combined constructor to consolidate code
157 CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<Txid>* txids);
158};
159
160#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:127
std::vector< std::pair< unsigned int, Txid > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:139
SERIALIZE_METHODS(CMerkleBlock, obj)
Definition: merkleblock.h:153
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:130
CMerkleBlock(const CBlock &block, CBloomFilter &filter)
Create from a CBlock, filtering transactions according to filter Note that this will call IsRelevantA...
Definition: merkleblock.h:146
CMerkleBlock(const CBlock &block, const std::set< Txid > &txids)
Definition: merkleblock.h:149
CPartialMerkleTree txn
Definition: merkleblock.h:131
CMerkleBlock()=default
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:57
unsigned int nTransactions
the total number of transactions in the block
Definition: merkleblock.h:60
uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector< Txid > &vMatch, std::vector< unsigned int > &vnIndex)
recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBu...
Definition: merkleblock.cpp:98
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
Definition: merkleblock.h:63
bool fBad
flag set when encountering invalid data
Definition: merkleblock.h:69
unsigned int GetNumTransactions() const
Get number of transactions the merkle proof is indicating for cross-reference with local blockchain k...
Definition: merkleblock.h:115
uint256 CalcHash(int height, unsigned int pos, const std::vector< Txid > &vTxid)
calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves)
Definition: merkleblock.cpp:58
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:66
void TraverseAndBuild(int height, unsigned int pos, const std::vector< Txid > &vTxid, const std::vector< bool > &vMatch)
recursive function that traverses tree nodes, storing the data as bits and hashes
Definition: merkleblock.cpp:79
uint256 ExtractMatches(std::vector< Txid > &vMatch, std::vector< unsigned int > &vnIndex)
extract the matching txid's represented by this partial merkle tree and their respective indices with...
SERIALIZE_METHODS(CPartialMerkleTree, obj)
Definition: merkleblock.h:90
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:72
256-bit opaque blob.
Definition: uint256.h:196
std::vector< unsigned char > BitsToBytes(const std::vector< bool > &bits)
Definition: merkleblock.cpp:12
std::vector< bool > BytesToBits(const std::vector< unsigned char > &bytes)
Definition: merkleblock.cpp:21
#define SER_WRITE(obj, code)
Definition: serialize.h:147
#define SER_READ(obj, code)
Definition: serialize.h:146
#define READWRITE(...)
Definition: serialize.h:145