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