Bitcoin ABC  0.22.13
P2P Digital Currency
merkleblock.cpp
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 #include <merkleblock.h>
7 
8 #include <consensus/consensus.h>
9 #include <hash.h>
10 
12  const std::set<TxId> *txids) {
13  header = block.GetBlockHeader();
14 
15  std::vector<bool> vMatch;
16  std::vector<uint256> vHashes;
17 
18  vMatch.reserve(block.vtx.size());
19  vHashes.reserve(block.vtx.size());
20 
21  if (filter) {
22  for (const auto &tx : block.vtx) {
23  vMatch.push_back(filter->MatchAndInsertOutputs(*tx));
24  }
25  }
26 
27  for (size_t i = 0; i < block.vtx.size(); i++) {
28  const CTransaction *tx = block.vtx[i].get();
29  const TxId &txid = tx->GetId();
30  if (filter) {
31  if (!vMatch[i]) {
32  vMatch[i] = filter->MatchInputs(*tx);
33  }
34  if (vMatch[i]) {
35  vMatchedTxn.push_back(std::make_pair(i, txid));
36  }
37  } else {
38  vMatch.push_back(txids && txids->count(txid));
39  }
40 
41  vHashes.push_back(txid);
42  }
43 
44  txn = CPartialMerkleTree(vHashes, vMatch);
45 }
46 
47 uint256 CPartialMerkleTree::CalcHash(int height, size_t pos,
48  const std::vector<uint256> &vTxid) {
49  // we can never have zero txs in a merkle block, we always need the
50  // coinbase tx if we do not have this assert, we can hit a memory
51  // access violation when indexing into vTxid
52  assert(vTxid.size() != 0);
53  if (height == 0) {
54  // hash at height 0 is the txids themself.
55  return vTxid[pos];
56  }
57 
58  // Calculate left hash.
59  uint256 left = CalcHash(height - 1, pos * 2, vTxid), right;
60  // Calculate right hash if not beyond the end of the array - copy left hash
61  // otherwise.
62  if (pos * 2 + 1 < CalcTreeWidth(height - 1)) {
63  right = CalcHash(height - 1, pos * 2 + 1, vTxid);
64  } else {
65  right = left;
66  }
67 
68  // Combine subhashes.
69  return Hash(left.begin(), left.end(), right.begin(), right.end());
70 }
71 
72 void CPartialMerkleTree::TraverseAndBuild(int height, size_t pos,
73  const std::vector<uint256> &vTxid,
74  const std::vector<bool> &vMatch) {
75  // Determine whether this node is the parent of at least one matched txid.
76  bool fParentOfMatch = false;
77  for (size_t p = pos << height; p < (pos + 1) << height && p < nTransactions;
78  p++) {
79  fParentOfMatch |= vMatch[p];
80  }
81 
82  // Store as flag bit.
83  vBits.push_back(fParentOfMatch);
84  if (height == 0 || !fParentOfMatch) {
85  // If at height 0, or nothing interesting below, store hash and stop.
86  vHash.push_back(CalcHash(height, pos, vTxid));
87  } else {
88  // Otherwise, don't store any hash, but descend into the subtrees.
89  TraverseAndBuild(height - 1, pos * 2, vTxid, vMatch);
90  if (pos * 2 + 1 < CalcTreeWidth(height - 1)) {
91  TraverseAndBuild(height - 1, pos * 2 + 1, vTxid, vMatch);
92  }
93  }
94 }
95 
97  size_t &nBitsUsed,
98  size_t &nHashUsed,
99  std::vector<uint256> &vMatch,
100  std::vector<size_t> &vnIndex) {
101  if (nBitsUsed >= vBits.size()) {
102  // Overflowed the bits array - failure
103  fBad = true;
104  return uint256();
105  }
106 
107  bool fParentOfMatch = vBits[nBitsUsed++];
108  if (height == 0 || !fParentOfMatch) {
109  // If at height 0, or nothing interesting below, use stored hash and do
110  // not descend.
111  if (nHashUsed >= vHash.size()) {
112  // Overflowed the hash array - failure
113  fBad = true;
114  return uint256();
115  }
116  const uint256 &hash = vHash[nHashUsed++];
117  // In case of height 0, we have a matched txid.
118  if (height == 0 && fParentOfMatch) {
119  vMatch.push_back(hash);
120  vnIndex.push_back(pos);
121  }
122  return hash;
123  }
124 
125  // Otherwise, descend into the subtrees to extract matched txids and hashes.
126  uint256 left = TraverseAndExtract(height - 1, pos * 2, nBitsUsed, nHashUsed,
127  vMatch, vnIndex),
128  right;
129  if (pos * 2 + 1 < CalcTreeWidth(height - 1)) {
130  right = TraverseAndExtract(height - 1, pos * 2 + 1, nBitsUsed,
131  nHashUsed, vMatch, vnIndex);
132  if (right == left) {
133  // The left and right branches should never be identical, as the
134  // transaction hashes covered by them must each be unique.
135  fBad = true;
136  }
137  } else {
138  right = left;
139  }
140 
141  // and combine them before returning.
142  return Hash(left.begin(), left.end(), right.begin(), right.end());
143 }
144 
145 CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid,
146  const std::vector<bool> &vMatch)
147  : nTransactions(vTxid.size()), fBad(false) {
148  // reset state
149  vBits.clear();
150  vHash.clear();
151 
152  // calculate height of tree
153  int nHeight = 0;
154  while (CalcTreeWidth(nHeight) > 1) {
155  nHeight++;
156  }
157 
158  // traverse the partial tree
159  TraverseAndBuild(nHeight, 0, vTxid, vMatch);
160 }
161 
163 
164 uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch,
165  std::vector<size_t> &vnIndex) {
166  vMatch.clear();
167 
168  // An empty set will not work
169  if (nTransactions == 0) {
170  return uint256();
171  }
172 
173  // Check for excessively high numbers of transactions.
174  // FIXME: Track the maximum block size we've seen and use it here.
175 
176  // There can never be more hashes provided than one for every txid.
177  if (vHash.size() > nTransactions) {
178  return uint256();
179  }
180 
181  // There must be at least one bit per node in the partial tree, and at least
182  // one node per hash.
183  if (vBits.size() < vHash.size()) {
184  return uint256();
185  }
186 
187  // calculate height of tree.
188  int nHeight = 0;
189  while (CalcTreeWidth(nHeight) > 1) {
190  nHeight++;
191  }
192 
193  // traverse the partial tree.
194  size_t nBitsUsed = 0, nHashUsed = 0;
195  uint256 hashMerkleRoot =
196  TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
197 
198  // verify that no problems occurred during the tree traversal.
199  if (fBad) {
200  return uint256();
201  }
202 
203  // verify that all bits were consumed (except for the padding caused by
204  // serializing it as a byte sequence)
205  if ((nBitsUsed + 7) / 8 != (vBits.size() + 7) / 8) {
206  return uint256();
207  }
208 
209  // verify that all hashes were consumed.
210  if (nHashUsed != vHash.size()) {
211  return uint256();
212  }
213 
214  return hashMerkleRoot;
215 }
uint256 ExtractMatches(std::vector< uint256 > &vMatch, std::vector< size_t > &vnIndex)
Extract the matching txid&#39;s represented by this partial merkle tree and their respective indices with...
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:162
CBlockHeader GetBlockHeader() const
Definition: block.h:91
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:70
Definition: block.h:62
bool fBad
flag set when encountering invalid data
Definition: merkleblock.h:64
unsigned int nHeight
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:45
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:52
uint32_t nTransactions
the total number of transactions in the block
Definition: merkleblock.h:55
bool MatchAndInsertOutputs(const CTransaction &tx)
Scans output scripts for matches and adds those outpoints to the filter for spend detection...
Definition: bloom.cpp:110
std::vector< uint256 > vHash
txids and internal hashes
Definition: merkleblock.h:61
std::vector< std::pair< size_t, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:171
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...
Definition: merkleblock.cpp:96
uint8_t * end()
Definition: uint256.h:78
uint256 Hash(const T1 pbegin, const T1 pend)
Compute the 256-bit hash of an object.
Definition: hash.h:72
uint8_t * begin()
Definition: uint256.h:76
CPartialMerkleTree txn
Definition: merkleblock.h:163
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
Definition: merkleblock.h:58
256-bit opaque blob.
Definition: uint256.h:120
std::vector< CTransactionRef > vtx
Definition: block.h:65
A TxId is the identifier of a transaction.
Definition: txid.h:14
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:72
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&#39;s themselves) ...
Definition: merkleblock.cpp:47
The basic transaction that is broadcasted on the network and contained in blocks. ...
Definition: transaction.h:211
bool MatchInputs(const CTransaction &tx)
Scan inputs to see if the spent outpoints are a match, or the input scripts contain matching elements...
Definition: bloom.cpp:159
const TxId GetId() const
Definition: transaction.h:261