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 238 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
13 : {
14 238 : std::vector<unsigned char> ret((bits.size() + 7) / 8);
15 77075 : for (unsigned int p = 0; p < bits.size(); p++) {
16 76837 : ret[p / 8] |= bits[p] << (p % 8);
17 76837 : }
18 238 : return ret;
19 238 : }
20 :
21 191 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
22 : {
23 191 : std::vector<bool> ret(bytes.size() * 8);
24 77767 : for (unsigned int p = 0; p < ret.size(); p++) {
25 77576 : ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
26 77576 : }
27 191 : return ret;
28 191 : }
29 :
30 26 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids)
31 13 : {
32 13 : header = block.GetBlockHeader();
33 :
34 13 : std::vector<bool> vMatch;
35 13 : std::vector<uint256> vHashes;
36 :
37 13 : vMatch.reserve(block.vtx.size());
38 13 : vHashes.reserve(block.vtx.size());
39 :
40 13 : const static std::set<int> allowedTxTypes = {
41 : TRANSACTION_NORMAL,
42 : TRANSACTION_PROVIDER_REGISTER,
43 : TRANSACTION_PROVIDER_UPDATE_SERVICE,
44 : TRANSACTION_PROVIDER_UPDATE_REGISTRAR,
45 : TRANSACTION_PROVIDER_UPDATE_REVOKE,
46 : TRANSACTION_COINBASE,
47 : TRANSACTION_ASSET_LOCK,
48 : TRANSACTION_ASSET_UNLOCK,
49 : };
50 :
51 94 : for (unsigned int i = 0; i < block.vtx.size(); i++)
52 : {
53 81 : const auto& tx = *block.vtx[i];
54 81 : const uint256& hash = tx.GetHash();
55 81 : bool isAllowedType = !tx.IsSpecialTxVersion() || allowedTxTypes.count(tx.nType) != 0;
56 :
57 81 : if (txids && txids->count(hash)) {
58 2 : vMatch.push_back(true);
59 81 : } else if (isAllowedType && filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
60 20 : vMatch.push_back(true);
61 20 : vMatchedTxn.emplace_back(i, hash);
62 20 : } else {
63 59 : vMatch.push_back(false);
64 : }
65 81 : vHashes.push_back(hash);
66 81 : }
67 :
68 13 : txn = CPartialMerkleTree(vHashes, vMatch);
69 26 : }
70 :
71 143586 : uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid) {
72 : //we can never have zero txs in a merkle block, we always need the coinbase tx
73 : //if we do not have this assert, we can hit a memory access violation when indexing into vTxid
74 143586 : assert(vTxid.size() != 0);
75 143586 : if (height == 0) {
76 : // hash at height 0 is the txids themselves
77 90925 : return vTxid[pos];
78 : } else {
79 : // calculate left hash
80 52661 : uint256 left = CalcHash(height-1, pos*2, vTxid), right;
81 : // calculate right hash if not beyond the end of the array - copy left hash otherwise
82 52661 : if (pos*2+1 < CalcTreeWidth(height-1))
83 52438 : right = CalcHash(height-1, pos*2+1, vTxid);
84 : else
85 223 : right = left;
86 : // combine subhashes
87 52661 : return Hash(left, right);
88 : }
89 143586 : }
90 :
91 76936 : void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) {
92 : // determine whether this node is the parent of at least one matched txid
93 76936 : bool fParentOfMatch = false;
94 940537 : for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
95 863601 : fParentOfMatch |= vMatch[p];
96 : // store as flag bit
97 76936 : vBits.push_back(fParentOfMatch);
98 76936 : if (height==0 || !fParentOfMatch) {
99 : // if at height 0, or nothing interesting below, store hash and stop
100 38487 : vHash.push_back(CalcHash(height, pos, vTxid));
101 38487 : } else {
102 : // otherwise, don't store any hash, but descend into the subtrees
103 38449 : TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
104 38449 : if (pos*2+1 < CalcTreeWidth(height-1))
105 38305 : TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
106 : }
107 76936 : }
108 :
109 384262 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
110 384262 : if (nBitsUsed >= vBits.size()) {
111 : // overflowed the bits array - failure
112 0 : fBad = true;
113 0 : return uint256();
114 : }
115 384262 : bool fParentOfMatch = vBits[nBitsUsed++];
116 384262 : if (height==0 || !fParentOfMatch) {
117 : // if at height 0, or nothing interesting below, use stored hash and do not descend
118 192221 : if (nHashUsed >= vHash.size()) {
119 : // overflowed the hash array - failure
120 0 : fBad = true;
121 0 : return uint256();
122 : }
123 192221 : const uint256 &hash = vHash[nHashUsed++];
124 192221 : if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
125 96760 : vMatch.push_back(hash);
126 96760 : vnIndex.push_back(pos);
127 96760 : }
128 192221 : return hash;
129 : } else {
130 : // otherwise, descend into the subtrees to extract matched txids and hashes
131 192041 : uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
132 192041 : if (pos*2+1 < CalcTreeWidth(height-1)) {
133 191369 : right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
134 191369 : if (right == left) {
135 : // The left and right branches should never be identical, as the transaction
136 : // hashes covered by them must each be unique.
137 1 : fBad = true;
138 1 : }
139 191369 : } else {
140 672 : right = left;
141 : }
142 : // and combine them before returning
143 192041 : return Hash(left, right);
144 : }
145 384262 : }
146 :
147 364 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
148 : // reset state
149 182 : vBits.clear();
150 182 : vHash.clear();
151 :
152 : // calculate height of tree
153 182 : int nHeight = 0;
154 1328 : while (CalcTreeWidth(nHeight) > 1)
155 1146 : nHeight++;
156 :
157 : // traverse the partial tree
158 182 : TraverseAndBuild(nHeight, 0, vTxid, vMatch);
159 364 : }
160 :
161 298 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
162 :
163 852 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
164 852 : vMatch.clear();
165 : // An empty set will not work
166 852 : if (nTransactions == 0)
167 0 : return uint256();
168 : // check for excessively high numbers of transactions
169 852 : if (nTransactions > MaxBlockSize() / 60) // 60 is the lower bound for the size of a serialized CTransaction
170 0 : return uint256();
171 : // there can never be more hashes provided than one for every txid
172 852 : if (vHash.size() > nTransactions)
173 0 : return uint256();
174 : // there must be at least one bit per node in the partial tree, and at least one node per hash
175 852 : if (vBits.size() < vHash.size())
176 0 : return uint256();
177 : // calculate height of tree
178 852 : int nHeight = 0;
179 6416 : while (CalcTreeWidth(nHeight) > 1)
180 5564 : nHeight++;
181 : // traverse the partial tree
182 852 : unsigned int nBitsUsed = 0, nHashUsed = 0;
183 852 : uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
184 : // verify that no problems occurred during the tree traversal
185 852 : if (fBad)
186 1 : return uint256();
187 : // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
188 851 : if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
189 0 : return uint256();
190 : // verify that all hashes were consumed
191 851 : if (nHashUsed != vHash.size())
192 0 : return uint256();
193 851 : return hashMerkleRoot;
194 852 : }
|
