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 410 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
13 : {
14 410 : std::vector<unsigned char> ret((bits.size() + 7) / 8);
15 77797 : for (unsigned int p = 0; p < bits.size(); p++) {
16 77387 : ret[p / 8] |= bits[p] << (p % 8);
17 77387 : }
18 410 : return ret;
19 410 : }
20 :
21 290 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
22 : {
23 290 : std::vector<bool> ret(bytes.size() * 8);
24 78658 : for (unsigned int p = 0; p < ret.size(); p++) {
25 78368 : ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
26 78368 : }
27 290 : return ret;
28 290 : }
29 :
30 102 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids)
31 51 : {
32 51 : header = block.GetBlockHeader();
33 :
34 51 : std::vector<bool> vMatch;
35 51 : std::vector<uint256> vHashes;
36 :
37 51 : vMatch.reserve(block.vtx.size());
38 51 : vHashes.reserve(block.vtx.size());
39 :
40 51 : 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 218 : for (unsigned int i = 0; i < block.vtx.size(); i++)
52 : {
53 167 : const auto& tx = *block.vtx[i];
54 167 : const uint256& hash = tx.GetHash();
55 167 : bool isAllowedType = !tx.IsSpecialTxVersion() || allowedTxTypes.count(tx.nType) != 0;
56 :
57 167 : if (txids && txids->count(hash)) {
58 42 : vMatch.push_back(true);
59 167 : } else if (isAllowedType && filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
60 24 : vMatch.push_back(true);
61 24 : vMatchedTxn.emplace_back(i, hash);
62 24 : } else {
63 101 : vMatch.push_back(false);
64 : }
65 167 : vHashes.push_back(hash);
66 167 : }
67 :
68 51 : txn = CPartialMerkleTree(vHashes, vMatch);
69 102 : }
70 :
71 144068 : 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 144068 : assert(vTxid.size() != 0);
75 144068 : if (height == 0) {
76 : // hash at height 0 is the txids themselves
77 91317 : return vTxid[pos];
78 : } else {
79 : // calculate left hash
80 52751 : 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 52751 : if (pos*2+1 < CalcTreeWidth(height-1))
83 52476 : right = CalcHash(height-1, pos*2+1, vTxid);
84 : else
85 275 : right = left;
86 : // combine subhashes
87 52751 : return Hash(left, right);
88 : }
89 144068 : }
90 :
91 77486 : 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 77486 : bool fParentOfMatch = false;
94 942013 : for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
95 864527 : fParentOfMatch |= vMatch[p];
96 : // store as flag bit
97 77486 : vBits.push_back(fParentOfMatch);
98 77486 : if (height==0 || !fParentOfMatch) {
99 : // if at height 0, or nothing interesting below, store hash and stop
100 38841 : vHash.push_back(CalcHash(height, pos, vTxid));
101 38841 : } else {
102 : // otherwise, don't store any hash, but descend into the subtrees
103 38645 : TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
104 38645 : if (pos*2+1 < CalcTreeWidth(height-1))
105 38487 : TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
106 : }
107 77486 : }
108 :
109 384589 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
110 384589 : if (nBitsUsed >= vBits.size()) {
111 : // overflowed the bits array - failure
112 0 : fBad = true;
113 0 : return uint256();
114 : }
115 384589 : bool fParentOfMatch = vBits[nBitsUsed++];
116 384589 : if (height==0 || !fParentOfMatch) {
117 : // if at height 0, or nothing interesting below, use stored hash and do not descend
118 192425 : if (nHashUsed >= vHash.size()) {
119 : // overflowed the hash array - failure
120 0 : fBad = true;
121 0 : return uint256();
122 : }
123 192425 : const uint256 &hash = vHash[nHashUsed++];
124 192425 : if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
125 96873 : vMatch.push_back(hash);
126 96873 : vnIndex.push_back(pos);
127 96873 : }
128 192425 : return hash;
129 : } else {
130 : // otherwise, descend into the subtrees to extract matched txids and hashes
131 192164 : uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
132 192164 : if (pos*2+1 < CalcTreeWidth(height-1)) {
133 191474 : right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
134 191474 : 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 191474 : } else {
140 690 : right = left;
141 : }
142 : // and combine them before returning
143 192164 : return Hash(left, right);
144 : }
145 384589 : }
146 :
147 708 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
148 : // reset state
149 354 : vBits.clear();
150 354 : vHash.clear();
151 :
152 : // calculate height of tree
153 354 : int nHeight = 0;
154 1686 : while (CalcTreeWidth(nHeight) > 1)
155 1332 : nHeight++;
156 :
157 : // traverse the partial tree
158 354 : TraverseAndBuild(nHeight, 0, vTxid, vMatch);
159 708 : }
160 :
161 1436 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
162 :
163 951 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
164 951 : vMatch.clear();
165 : // An empty set will not work
166 951 : if (nTransactions == 0)
167 0 : return uint256();
168 : // check for excessively high numbers of transactions
169 951 : 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 951 : 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 951 : if (vBits.size() < vHash.size())
176 0 : return uint256();
177 : // calculate height of tree
178 951 : int nHeight = 0;
179 6624 : while (CalcTreeWidth(nHeight) > 1)
180 5673 : nHeight++;
181 : // traverse the partial tree
182 951 : unsigned int nBitsUsed = 0, nHashUsed = 0;
183 951 : uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
184 : // verify that no problems occurred during the tree traversal
185 951 : 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 950 : if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
189 0 : return uint256();
190 : // verify that all hashes were consumed
191 950 : if (nHashUsed != vHash.size())
192 0 : return uint256();
193 950 : return hashMerkleRoot;
194 951 : }
|
