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