Bitcoin Core 29.99.0
P2P Digital Currency
merkleblock.cpp
Go to the documentation of this file.
1// Copyright (c) 2009-2010 Satoshi Nakamoto
2// Copyright (c) 2009-2020 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#include <merkleblock.h>
7
8#include <hash.h>
10
11
12std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
13{
14 std::vector<unsigned char> ret((bits.size() + 7) / 8);
15 for (unsigned int p = 0; p < bits.size(); p++) {
16 ret[p / 8] |= bits[p] << (p % 8);
17 }
18 return ret;
19}
20
21std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
22{
23 std::vector<bool> ret(bytes.size() * 8);
24 for (unsigned int p = 0; p < ret.size(); p++) {
25 ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
26 }
27 return ret;
28}
29
30CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<Txid>* txids)
31{
32 header = block.GetBlockHeader();
33
34 std::vector<bool> vMatch;
35 std::vector<Txid> vHashes;
36
37 vMatch.reserve(block.vtx.size());
38 vHashes.reserve(block.vtx.size());
39
40 for (unsigned int i = 0; i < block.vtx.size(); i++)
41 {
42 const Txid& hash{block.vtx[i]->GetHash()};
43 if (txids && txids->count(hash)) {
44 vMatch.push_back(true);
45 } else if (filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
46 vMatch.push_back(true);
47 vMatchedTxn.emplace_back(i, hash);
48 } else {
49 vMatch.push_back(false);
50 }
51 vHashes.push_back(hash);
52 }
53
54 txn = CPartialMerkleTree(vHashes, vMatch);
55}
56
57// NOLINTNEXTLINE(misc-no-recursion)
58uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<Txid> &vTxid) {
59 //we can never have zero txs in a merkle block, we always need the coinbase tx
60 //if we do not have this assert, we can hit a memory access violation when indexing into vTxid
61 assert(vTxid.size() != 0);
62 if (height == 0) {
63 // hash at height 0 is the txids themselves
64 return vTxid[pos].ToUint256();
65 } else {
66 // calculate left hash
67 uint256 left = CalcHash(height-1, pos*2, vTxid), right;
68 // calculate right hash if not beyond the end of the array - copy left hash otherwise
69 if (pos*2+1 < CalcTreeWidth(height-1))
70 right = CalcHash(height-1, pos*2+1, vTxid);
71 else
72 right = left;
73 // combine subhashes
74 return Hash(left, right);
75 }
76}
77
78// NOLINTNEXTLINE(misc-no-recursion)
79void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<Txid> &vTxid, const std::vector<bool> &vMatch) {
80 // determine whether this node is the parent of at least one matched txid
81 bool fParentOfMatch = false;
82 for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
83 fParentOfMatch |= vMatch[p];
84 // store as flag bit
85 vBits.push_back(fParentOfMatch);
86 if (height==0 || !fParentOfMatch) {
87 // if at height 0, or nothing interesting below, store hash and stop
88 vHash.push_back(CalcHash(height, pos, vTxid));
89 } else {
90 // otherwise, don't store any hash, but descend into the subtrees
91 TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
92 if (pos*2+1 < CalcTreeWidth(height-1))
93 TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
94 }
95}
96
97// NOLINTNEXTLINE(misc-no-recursion)
98uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<Txid> &vMatch, std::vector<unsigned int> &vnIndex) {
99 if (nBitsUsed >= vBits.size()) {
100 // overflowed the bits array - failure
101 fBad = true;
102 return uint256();
103 }
104 bool fParentOfMatch = vBits[nBitsUsed++];
105 if (height==0 || !fParentOfMatch) {
106 // if at height 0, or nothing interesting below, use stored hash and do not descend
107 if (nHashUsed >= vHash.size()) {
108 // overflowed the hash array - failure
109 fBad = true;
110 return uint256();
111 }
112 const uint256 &hash = vHash[nHashUsed++];
113 if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
114 vMatch.push_back(Txid::FromUint256(hash));
115 vnIndex.push_back(pos);
116 }
117 return hash;
118 } else {
119 // otherwise, descend into the subtrees to extract matched txids and hashes
120 uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
121 if (pos*2+1 < CalcTreeWidth(height-1)) {
122 right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
123 if (right == left) {
124 // The left and right branches should never be identical, as the transaction
125 // hashes covered by them must each be unique.
126 fBad = true;
127 }
128 } else {
129 right = left;
130 }
131 // and combine them before returning
132 return Hash(left, right);
133 }
134}
135
136CPartialMerkleTree::CPartialMerkleTree(const std::vector<Txid> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
137 // reset state
138 vBits.clear();
139 vHash.clear();
140
141 // calculate height of tree
142 int nHeight = 0;
143 while (CalcTreeWidth(nHeight) > 1)
144 nHeight++;
145
146 // traverse the partial tree
147 TraverseAndBuild(nHeight, 0, vTxid, vMatch);
148}
149
150CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
151
152uint256 CPartialMerkleTree::ExtractMatches(std::vector<Txid> &vMatch, std::vector<unsigned int> &vnIndex) {
153 vMatch.clear();
154 // An empty set will not work
155 if (nTransactions == 0)
156 return uint256();
157 // check for excessively high numbers of transactions
159 return uint256();
160 // there can never be more hashes provided than one for every txid
161 if (vHash.size() > nTransactions)
162 return uint256();
163 // there must be at least one bit per node in the partial tree, and at least one node per hash
164 if (vBits.size() < vHash.size())
165 return uint256();
166 // calculate height of tree
167 int nHeight = 0;
168 while (CalcTreeWidth(nHeight) > 1)
169 nHeight++;
170 // traverse the partial tree
171 unsigned int nBitsUsed = 0, nHashUsed = 0;
172 uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
173 // verify that no problems occurred during the tree traversal
174 if (fBad)
175 return uint256();
176 // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
177 if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
178 return uint256();
179 // verify that all hashes were consumed
180 if (nHashUsed != vHash.size())
181 return uint256();
182 return hashMerkleRoot;
183}
int ret
Definition: block.h:69
std::vector< CTransactionRef > vtx
Definition: block.h:72
CBlockHeader GetBlockHeader() const
Definition: block.h:104
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:45
bool IsRelevantAndUpdate(const CTransaction &tx)
Also adds any outputs which match the filter to the filter (to match their spending txes)
Definition: bloom.cpp:94
std::vector< std::pair< unsigned int, Txid > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:139
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:130
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
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...
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
static transaction_identifier FromUint256(const uint256 &id)
256-bit opaque blob.
Definition: uint256.h:196
static const unsigned int MAX_BLOCK_WEIGHT
The maximum allowed weight for a block, see BIP 141 (network rule)
Definition: consensus.h:15
static const size_t MIN_TRANSACTION_WEIGHT
Definition: consensus.h:23
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
Definition: hash.h:75
unsigned int nHeight
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
assert(!tx.IsCoinBase())