Branch data Line data Source code
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>
9 : : #include <consensus/consensus.h>
10 : :
11 : :
12 : 1306 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
13 : : {
14 [ + - ]: 1306 : std::vector<unsigned char> ret((bits.size() + 7) / 8);
15 [ + + ]: 7895204 : for (unsigned int p = 0; p < bits.size(); p++) {
16 [ + - ]: 7893898 : ret[p / 8] |= bits[p] << (p % 8);
17 : 7893898 : }
18 : 1306 : return ret;
19 [ + - ]: 1306 : }
20 : :
21 : 5489 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
22 : : {
23 [ + - ]: 5489 : std::vector<bool> ret(bytes.size() * 8);
24 [ + + ]: 24471953 : for (unsigned int p = 0; p < ret.size(); p++) {
25 [ + - ]: 24466464 : ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
26 : 24466464 : }
27 : 5489 : return ret;
28 [ + - ]: 5489 : }
29 : :
30 : 1227 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<Txid>* txids)
31 : : {
32 [ + - ]: 1227 : header = block.GetBlockHeader();
33 : :
34 : 1227 : std::vector<bool> vMatch;
35 : 1227 : std::vector<uint256> vHashes;
36 : :
37 [ + - ]: 1227 : vMatch.reserve(block.vtx.size());
38 [ + - ]: 1227 : vHashes.reserve(block.vtx.size());
39 : :
40 [ + + ]: 469548 : for (unsigned int i = 0; i < block.vtx.size(); i++)
41 : : {
42 [ + - ]: 468321 : const Txid& hash{block.vtx[i]->GetHash()};
43 [ + + + - : 468321 : if (txids && txids->count(hash)) {
+ + ]
44 [ + - ]: 171076 : vMatch.push_back(true);
45 [ + + + - : 468321 : } else if (filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
+ + ]
46 [ + - ]: 114183 : vMatch.push_back(true);
47 [ + - ]: 114183 : vMatchedTxn.emplace_back(i, hash);
48 : 114183 : } else {
49 [ + - ]: 183062 : vMatch.push_back(false);
50 : : }
51 [ + - + - ]: 468321 : vHashes.push_back(hash);
52 : 468321 : }
53 : :
54 [ + - ]: 1227 : txn = CPartialMerkleTree(vHashes, vMatch);
55 : 1227 : }
56 : :
57 : : // NOLINTNEXTLINE(misc-no-recursion)
58 : 648057 : uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &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 [ + - ]: 648057 : assert(vTxid.size() != 0);
62 [ + + ]: 648057 : if (height == 0) {
63 : : // hash at height 0 is the txids themselves
64 : 468321 : return vTxid[pos];
65 : : } else {
66 : : // calculate left hash
67 : 179736 : 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 [ + + ]: 179736 : if (pos*2+1 < CalcTreeWidth(height-1))
70 : 179621 : right = CalcHash(height-1, pos*2+1, vTxid);
71 : : else
72 : 115 : right = left;
73 : : // combine subhashes
74 : 179736 : return Hash(left, right);
75 : 179736 : }
76 : 648057 : }
77 : :
78 : : // NOLINTNEXTLINE(misc-no-recursion)
79 : 576416 : void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) {
80 : : // determine whether this node is the parent of at least one matched txid
81 : 576416 : bool fParentOfMatch = false;
82 [ + + + + ]: 5544150 : for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
83 : 4967734 : fParentOfMatch |= vMatch[p];
84 : : // store as flag bit
85 : 576416 : vBits.push_back(fParentOfMatch);
86 [ + + + + ]: 576416 : if (height==0 || !fParentOfMatch) {
87 : : // if at height 0, or nothing interesting below, store hash and stop
88 : 288700 : vHash.push_back(CalcHash(height, pos, vTxid));
89 : 288700 : } else {
90 : : // otherwise, don't store any hash, but descend into the subtrees
91 : 287716 : TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
92 [ + + ]: 287716 : if (pos*2+1 < CalcTreeWidth(height-1))
93 : 287473 : TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
94 : : }
95 : 576416 : }
96 : :
97 : : // NOLINTNEXTLINE(misc-no-recursion)
98 : 267991 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
99 [ + + ]: 267991 : if (nBitsUsed >= vBits.size()) {
100 : : // overflowed the bits array - failure
101 : 135 : fBad = true;
102 : 135 : return uint256();
103 : : }
104 : 267856 : bool fParentOfMatch = vBits[nBitsUsed++];
105 [ + + + + ]: 267856 : if (height==0 || !fParentOfMatch) {
106 : : // if at height 0, or nothing interesting below, use stored hash and do not descend
107 [ + + ]: 133832 : if (nHashUsed >= vHash.size()) {
108 : : // overflowed the hash array - failure
109 : 3899 : fBad = true;
110 : 3899 : return uint256();
111 : : }
112 : 129933 : const uint256 &hash = vHash[nHashUsed++];
113 [ + + + + ]: 129933 : if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
114 : 124744 : vMatch.push_back(hash);
115 : 124744 : vnIndex.push_back(pos);
116 : 124744 : }
117 : 129933 : return hash;
118 : 129933 : } else {
119 : : // otherwise, descend into the subtrees to extract matched txids and hashes
120 : 134024 : uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
121 [ + + ]: 134024 : if (pos*2+1 < CalcTreeWidth(height-1)) {
122 : 133715 : right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
123 [ + + ]: 133715 : 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 : 121499 : fBad = true;
127 : 121499 : }
128 : 133715 : } else {
129 : 309 : right = left;
130 : : }
131 : : // and combine them before returning
132 : 134024 : return Hash(left, right);
133 : 134024 : }
134 : 267991 : }
135 : :
136 : 1227 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
137 : : // reset state
138 : 1227 : vBits.clear();
139 : 1227 : vHash.clear();
140 : :
141 : : // calculate height of tree
142 : 1227 : int nHeight = 0;
143 [ + - + + ]: 2155 : while (CalcTreeWidth(nHeight) > 1)
144 : 928 : nHeight++;
145 : :
146 : : // traverse the partial tree
147 [ + - ]: 1227 : TraverseAndBuild(nHeight, 0, vTxid, vMatch);
148 : 1227 : }
149 : :
150 : 3719 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
151 : :
152 : 527 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
153 : 527 : vMatch.clear();
154 : : // An empty set will not work
155 [ + + ]: 527 : if (nTransactions == 0)
156 : 251 : return uint256();
157 : : // check for excessively high numbers of transactions
158 [ + + ]: 276 : if (nTransactions > MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT)
159 : 18 : return uint256();
160 : : // there can never be more hashes provided than one for every txid
161 [ + + ]: 258 : if (vHash.size() > nTransactions)
162 : 3 : return uint256();
163 : : // there must be at least one bit per node in the partial tree, and at least one node per hash
164 [ + + ]: 255 : if (vBits.size() < vHash.size())
165 : 3 : return uint256();
166 : : // calculate height of tree
167 : 252 : int nHeight = 0;
168 [ + + ]: 2151 : while (CalcTreeWidth(nHeight) > 1)
169 : 1899 : nHeight++;
170 : : // traverse the partial tree
171 : 252 : unsigned int nBitsUsed = 0, nHashUsed = 0;
172 : 252 : uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
173 : : // verify that no problems occurred during the tree traversal
174 [ + + ]: 252 : if (fBad)
175 : 146 : return uint256();
176 : : // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
177 [ + + ]: 106 : if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
178 : 12 : return uint256();
179 : : // verify that all hashes were consumed
180 [ + + ]: 94 : if (nHashUsed != vHash.size())
181 : 5 : return uint256();
182 : 89 : return hashMerkleRoot;
183 : 527 : }
|
