Bitcoin Core  0.20.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 std::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 
21 std::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 
30 CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids)
31 {
32  header = block.GetBlockHeader();
33 
34  std::vector<bool> vMatch;
35  std::vector<uint256> 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 uint256& 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 uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid) {
58  //we can never have zero txs in a merkle block, we always need the coinbase tx
59  //if we do not have this assert, we can hit a memory access violation when indexing into vTxid
60  assert(vTxid.size() != 0);
61  if (height == 0) {
62  // hash at height 0 is the txids themself
63  return vTxid[pos];
64  } else {
65  // calculate left hash
66  uint256 left = CalcHash(height-1, pos*2, vTxid), right;
67  // calculate right hash if not beyond the end of the array - copy left hash otherwise
68  if (pos*2+1 < CalcTreeWidth(height-1))
69  right = CalcHash(height-1, pos*2+1, vTxid);
70  else
71  right = left;
72  // combine subhashes
73  return Hash(left.begin(), left.end(), right.begin(), right.end());
74  }
75 }
76 
77 void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) {
78  // determine whether this node is the parent of at least one matched txid
79  bool fParentOfMatch = false;
80  for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
81  fParentOfMatch |= vMatch[p];
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 uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
96  if (nBitsUsed >= vBits.size()) {
97  // overflowed the bits array - failure
98  fBad = true;
99  return uint256();
100  }
101  bool fParentOfMatch = vBits[nBitsUsed++];
102  if (height==0 || !fParentOfMatch) {
103  // if at height 0, or nothing interesting below, use stored hash and do not descend
104  if (nHashUsed >= vHash.size()) {
105  // overflowed the hash array - failure
106  fBad = true;
107  return uint256();
108  }
109  const uint256 &hash = vHash[nHashUsed++];
110  if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
111  vMatch.push_back(hash);
112  vnIndex.push_back(pos);
113  }
114  return hash;
115  } else {
116  // otherwise, descend into the subtrees to extract matched txids and hashes
117  uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
118  if (pos*2+1 < CalcTreeWidth(height-1)) {
119  right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
120  if (right == left) {
121  // The left and right branches should never be identical, as the transaction
122  // hashes covered by them must each be unique.
123  fBad = true;
124  }
125  } else {
126  right = left;
127  }
128  // and combine them before returning
129  return Hash(left.begin(), left.end(), right.begin(), right.end());
130  }
131 }
132 
133 CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
134  // reset state
135  vBits.clear();
136  vHash.clear();
137 
138  // calculate height of tree
139  int nHeight = 0;
140  while (CalcTreeWidth(nHeight) > 1)
141  nHeight++;
142 
143  // traverse the partial tree
144  TraverseAndBuild(nHeight, 0, vTxid, vMatch);
145 }
146 
148 
149 uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
150  vMatch.clear();
151  // An empty set will not work
152  if (nTransactions == 0)
153  return uint256();
154  // check for excessively high numbers of transactions
156  return uint256();
157  // there can never be more hashes provided than one for every txid
158  if (vHash.size() > nTransactions)
159  return uint256();
160  // there must be at least one bit per node in the partial tree, and at least one node per hash
161  if (vBits.size() < vHash.size())
162  return uint256();
163  // calculate height of tree
164  int nHeight = 0;
165  while (CalcTreeWidth(nHeight) > 1)
166  nHeight++;
167  // traverse the partial tree
168  unsigned int nBitsUsed = 0, nHashUsed = 0;
169  uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
170  // verify that no problems occurred during the tree traversal
171  if (fBad)
172  return uint256();
173  // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
174  if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
175  return uint256();
176  // verify that all hashes were consumed
177  if (nHashUsed != vHash.size())
178  return uint256();
179  return hashMerkleRoot;
180 }
CBlockHeader header
Public only for unit testing.
Definition: merkleblock.h:128
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:77
CBlockHeader GetBlockHeader() const
Definition: block.h:95
unsigned int nTransactions
the total number of transactions in the block
Definition: merkleblock.h:58
Definition: block.h:62
bool fBad
flag set when encountering invalid data
Definition: merkleblock.h:67
bool IsRelevantAndUpdate(const CTransaction &tx)
Also adds any outputs which match the filter to the filter (to match their spending txes) ...
Definition: bloom.cpp:105
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:70
Data structure that represents a partial merkle tree.
Definition: merkleblock.h:54
std::vector< unsigned char > BitsToBytes(const std::vector< bool > &bits)
Definition: merkleblock.cpp:12
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:64
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:129
std::vector< bool > BytesToBits(const std::vector< unsigned char > &bytes)
Definition: merkleblock.cpp:21
std::vector< bool > vBits
node-is-parent-of-matched-txid bits
Definition: merkleblock.h:61
256-bit opaque blob.
Definition: uint256.h:120
std::vector< CTransactionRef > vtx
Definition: block.h:66
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:95
std::vector< std::pair< unsigned int, uint256 > > vMatchedTxn
Public only for unit testing and relay testing (not relayed).
Definition: merkleblock.h:137
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:57