Branch data Line data Source code
1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : : // Copyright (c) 2009-present 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 : : #include <util/overflow.h>
11 : :
12 : :
13 : 1008 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
14 : : {
15 : 1008 : std::vector<unsigned char> ret(CeilDiv(bits.size(), 8u));
16 [ + + ]: 7040715 : for (unsigned int p = 0; p < bits.size(); p++) {
17 : 7039707 : ret[p / 8] |= bits[p] << (p % 8);
18 : : }
19 : 1008 : return ret;
20 : : }
21 : :
22 : 299 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
23 : : {
24 [ - + ]: 299 : std::vector<bool> ret(bytes.size() * 8);
25 [ + + ]: 7076539 : for (unsigned int p = 0; p < ret.size(); p++) {
26 : 7076240 : ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
27 : : }
28 : 299 : return ret;
29 : : }
30 : :
31 [ - + ]: 986 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<Txid>* txids)
32 : : {
33 : 986 : header = static_cast<const CBlockHeader&>(block);
34 : :
35 : 986 : std::vector<bool> vMatch;
36 : 986 : std::vector<Txid> vHashes;
37 : :
38 [ - + + - ]: 986 : vMatch.reserve(block.vtx.size());
39 [ - + + - ]: 986 : vHashes.reserve(block.vtx.size());
40 : :
41 [ - + + + ]: 578693 : for (unsigned int i = 0; i < block.vtx.size(); i++)
42 : : {
43 [ + + ]: 577707 : const Txid& hash{block.vtx[i]->GetHash()};
44 [ + + + + ]: 577707 : if (txids && txids->contains(hash)) {
45 [ + - ]: 254497 : vMatch.push_back(true);
46 [ + + + - : 323210 : } else if (filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
+ + ]
47 [ + - ]: 149709 : vMatch.push_back(true);
48 [ + - ]: 149709 : vMatchedTxn.emplace_back(i, hash);
49 : : } else {
50 [ + - ]: 173501 : vMatch.push_back(false);
51 : : }
52 [ + - ]: 577707 : vHashes.push_back(hash);
53 : : }
54 : :
55 [ + - ]: 1972 : txn = CPartialMerkleTree(vHashes, vMatch);
56 : 986 : }
57 : :
58 : : // NOLINTNEXTLINE(misc-no-recursion)
59 : 747964 : uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<Txid> &vTxid) {
60 : : //we can never have zero txs in a merkle block, we always need the coinbase tx
61 : : //if we do not have this assert, we can hit a memory access violation when indexing into vTxid
62 [ - + - + ]: 747964 : assert(vTxid.size() != 0);
63 [ + + ]: 747964 : if (height == 0) {
64 : : // hash at height 0 is the txids themselves
65 : 577707 : return vTxid[pos].ToUint256();
66 : : } else {
67 : : // calculate left hash
68 : 170257 : uint256 left = CalcHash(height-1, pos*2, vTxid), right;
69 : : // calculate right hash if not beyond the end of the array - copy left hash otherwise
70 [ + + ]: 170257 : if (pos*2+1 < CalcTreeWidth(height-1))
71 : 170110 : right = CalcHash(height-1, pos*2+1, vTxid);
72 : : else
73 : 147 : right = left;
74 : : // combine subhashes
75 : 170257 : return Hash(left, right);
76 : : }
77 : : }
78 : :
79 : : // NOLINTNEXTLINE(misc-no-recursion)
80 : 814480 : void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<Txid> &vTxid, const std::vector<bool> &vMatch) {
81 : : // determine whether this node is the parent of at least one matched txid
82 : 814480 : bool fParentOfMatch = false;
83 [ + + + + ]: 7840257 : for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
84 : 7025777 : fParentOfMatch |= vMatch[p];
85 : : // store as flag bit
86 : 814480 : vBits.push_back(fParentOfMatch);
87 [ + + ]: 814480 : if (height==0 || !fParentOfMatch) {
88 : : // if at height 0, or nothing interesting below, store hash and stop
89 : 407597 : vHash.push_back(CalcHash(height, pos, vTxid));
90 : : } else {
91 : : // otherwise, don't store any hash, but descend into the subtrees
92 : 406883 : TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
93 [ + + ]: 406883 : if (pos*2+1 < CalcTreeWidth(height-1))
94 : 406611 : TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
95 : : }
96 : 814480 : }
97 : :
98 : : // NOLINTNEXTLINE(misc-no-recursion)
99 : 303124 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<Txid> &vMatch, std::vector<unsigned int> &vnIndex) {
100 [ + + ]: 303124 : if (nBitsUsed >= vBits.size()) {
101 : : // overflowed the bits array - failure
102 : 146 : fBad = true;
103 : 146 : return uint256();
104 : : }
105 [ + + ]: 302978 : bool fParentOfMatch = vBits[nBitsUsed++];
106 : : if (height==0 || !fParentOfMatch) {
107 : : // if at height 0, or nothing interesting below, use stored hash and do not descend
108 [ - + + + ]: 151405 : if (nHashUsed >= vHash.size()) {
109 : : // overflowed the hash array - failure
110 : 5201 : fBad = true;
111 : 5201 : return uint256();
112 : : }
113 [ + + ]: 146204 : const uint256 &hash = vHash[nHashUsed++];
114 [ + + ]: 146204 : if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
115 : 141806 : vMatch.push_back(Txid::FromUint256(hash));
116 : 141806 : vnIndex.push_back(pos);
117 : : }
118 : 146204 : return hash;
119 : : } else {
120 : : // otherwise, descend into the subtrees to extract matched txids and hashes
121 : 151573 : uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
122 [ + + ]: 151573 : if (pos*2+1 < CalcTreeWidth(height-1)) {
123 : 151292 : right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
124 [ + + ]: 151292 : if (right == left) {
125 : : // The left and right branches should never be identical, as the transaction
126 : : // hashes covered by them must each be unique.
127 : 137603 : fBad = true;
128 : : }
129 : : } else {
130 : 281 : right = left;
131 : : }
132 : : // and combine them before returning
133 : 151573 : return Hash(left, right);
134 : : }
135 : : }
136 : :
137 [ - + ]: 986 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<Txid> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
138 : : // reset state
139 : 986 : vBits.clear();
140 [ - + ]: 986 : vHash.clear();
141 : :
142 : : // calculate height of tree
143 : : int nHeight = 0;
144 [ + + ]: 1968 : while (CalcTreeWidth(nHeight) > 1)
145 : 982 : nHeight++;
146 : :
147 : : // traverse the partial tree
148 [ + - ]: 986 : TraverseAndBuild(nHeight, 0, vTxid, vMatch);
149 : 986 : }
150 : :
151 : 3185 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
152 : :
153 : 497 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<Txid> &vMatch, std::vector<unsigned int> &vnIndex) {
154 [ - + ]: 497 : vMatch.clear();
155 : : // An empty set will not work
156 [ + + ]: 497 : if (nTransactions == 0)
157 : 223 : return uint256();
158 : : // check for excessively high numbers of transactions
159 [ + + ]: 274 : if (nTransactions > MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT)
160 : 8 : return uint256();
161 : : // there can never be more hashes provided than one for every txid
162 [ - + + + ]: 266 : if (vHash.size() > nTransactions)
163 : 5 : return uint256();
164 : : // there must be at least one bit per node in the partial tree, and at least one node per hash
165 [ + + ]: 261 : if (vBits.size() < vHash.size())
166 : 2 : return uint256();
167 : : // calculate height of tree
168 : : int nHeight = 0;
169 [ + + ]: 2038 : while (CalcTreeWidth(nHeight) > 1)
170 : 1779 : nHeight++;
171 : : // traverse the partial tree
172 : 259 : unsigned int nBitsUsed = 0, nHashUsed = 0;
173 : 259 : uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
174 : : // verify that no problems occurred during the tree traversal
175 [ + + ]: 259 : if (fBad)
176 : 145 : return uint256();
177 : : // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
178 [ + + ]: 114 : if (CeilDiv(nBitsUsed, 8u) != CeilDiv(vBits.size(), 8u))
179 : 11 : return uint256();
180 : : // verify that all hashes were consumed
181 [ - + + + ]: 103 : if (nHashUsed != vHash.size())
182 : 6 : return uint256();
183 : 97 : return hashMerkleRoot;
184 : : }
|
