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