Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2016 The Bitcoin developers
3 : // Copyright (c) 2015-2020 The PIVX Core developers
4 : // Distributed under the MIT software license, see the accompanying
5 : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
6 :
7 : #include "merkleblock.h"
8 :
9 : #include "consensus/consensus.h"
10 : #include "hash.h"
11 : #include "primitives/block.h" // for MAX_BLOCK_SIZE
12 : #include "utilstrencodings.h"
13 :
14 :
15 169 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
16 : {
17 169 : std::vector<unsigned char> ret((bits.size() + 7) / 8);
18 77405 : for (unsigned int p = 0; p < bits.size(); p++) {
19 77236 : ret[p / 8] |= bits[p] << (p % 8);
20 : }
21 169 : return ret;
22 : }
23 :
24 168 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
25 : {
26 168 : std::vector<bool> ret(bytes.size() * 8);
27 78168 : for (unsigned int p = 0; p < ret.size(); p++) {
28 156000 : ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
29 : }
30 168 : return ret;
31 : }
32 :
33 13 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids)
34 : {
35 13 : header = block.GetBlockHeader();
36 :
37 13 : std::vector<bool> vMatch;
38 26 : std::vector<uint256> vHashes;
39 :
40 13 : vMatch.reserve(block.vtx.size());
41 13 : vHashes.reserve(block.vtx.size());
42 :
43 94 : for (unsigned int i = 0; i < block.vtx.size(); i++) {
44 81 : const uint256& hash = block.vtx[i]->GetHash();
45 97 : if (txids && txids->count(hash)) {
46 2 : vMatch.push_back(true);
47 79 : } else if (filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
48 20 : vMatch.push_back(true);
49 20 : vMatchedTxn.emplace_back(i, hash);
50 : } else {
51 59 : vMatch.push_back(false);
52 : }
53 81 : vHashes.push_back(hash);
54 : }
55 :
56 13 : txn = CPartialMerkleTree(vHashes, vMatch);
57 13 : }
58 :
59 143372 : uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256>& vTxid)
60 : {
61 143372 : if (height == 0) {
62 : // hash at height 0 is the txids themself
63 90913 : return vTxid[pos];
64 : } else {
65 : // calculate left hash
66 52459 : uint256 left = CalcHash(height - 1, pos * 2, vTxid), right;
67 : // calculate right hash if not beyond the end of the array - copy left hash otherwise1
68 52459 : if (pos * 2 + 1 < CalcTreeWidth(height - 1))
69 52227 : right = CalcHash(height - 1, pos * 2 + 1, vTxid);
70 : else
71 232 : right = left;
72 : // combine subhashes
73 52459 : return Hash(BEGIN(left), END(left), BEGIN(right), END(right));
74 : }
75 : }
76 :
77 77325 : void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256>& vTxid, const std::vector<bool>& vMatch)
78 : {
79 : // determine whether this node is the parent of at least one matched txid
80 77325 : bool fParentOfMatch = false;
81 944952 : for (unsigned int p = pos << height; p < (pos + 1) << height && p < nTransactions; p++)
82 867627 : fParentOfMatch |= vMatch[p];
83 : // store as flag bit
84 77325 : vBits.push_back(fParentOfMatch);
85 77325 : if (height == 0 || !fParentOfMatch) {
86 : // if at height 0, or nothing interesting below, store hash and stop
87 38686 : vHash.push_back(CalcHash(height, pos, vTxid));
88 : } else {
89 : // otherwise, don't store any hash, but descend into the subtrees
90 38639 : TraverseAndBuild(height - 1, pos * 2, vTxid, vMatch);
91 38639 : if (pos * 2 + 1 < CalcTreeWidth(height - 1))
92 38505 : TraverseAndBuild(height - 1, pos * 2 + 1, vTxid, vMatch);
93 : }
94 77325 : }
95 :
96 386247 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int& nBitsUsed, unsigned int& nHashUsed, std::vector<uint256>& vMatch)
97 : {
98 386247 : if (nBitsUsed >= vBits.size()) {
99 : // overflowed the bits array - failure
100 0 : fBad = true;
101 0 : return UINT256_ZERO;
102 : }
103 386247 : bool fParentOfMatch = vBits[nBitsUsed++];
104 386247 : if (height == 0 || !fParentOfMatch) {
105 : // if at height 0, or nothing interesting below, use stored hash and do not descend
106 193236 : if (nHashUsed >= vHash.size()) {
107 : // overflowed the hash array - failure
108 0 : fBad = true;
109 0 : return UINT256_ZERO;
110 : }
111 193236 : const uint256& hash = vHash[nHashUsed++];
112 193236 : if (height == 0 && fParentOfMatch) // in case of height 0, we have a matched txid
113 96788 : vMatch.push_back(hash);
114 193236 : return hash;
115 : } else {
116 : // otherwise, descend into the subtrees to extract matched txids and hashes
117 193011 : uint256 left = TraverseAndExtract(height - 1, pos * 2, nBitsUsed, nHashUsed, vMatch), right;
118 193011 : if (pos * 2 + 1 < CalcTreeWidth(height - 1))
119 192385 : right = TraverseAndExtract(height - 1, pos * 2 + 1, nBitsUsed, nHashUsed, vMatch);
120 : else
121 626 : right = left;
122 : // and combine them before returning
123 193011 : return Hash(BEGIN(left), END(left), BEGIN(right), END(right));
124 : }
125 : }
126 :
127 181 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256>& vTxid, const std::vector<bool>& vMatch) : nTransactions(vTxid.size()), fBad(false)
128 : {
129 : // reset state
130 181 : vBits.clear();
131 181 : vHash.clear();
132 :
133 : // calculate height of tree
134 181 : int nHeight = 0;
135 1323 : while (CalcTreeWidth(nHeight) > 1)
136 1142 : nHeight++;
137 :
138 : // traverse the partial tree
139 181 : TraverseAndBuild(nHeight, 0, vTxid, vMatch);
140 181 : }
141 :
142 181 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
143 :
144 851 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256>& vMatch)
145 : {
146 851 : vMatch.clear();
147 : // An empty set will not work
148 851 : if (nTransactions == 0)
149 0 : return UINT256_ZERO;
150 : // check for excessively high numbers of transactions
151 851 : if (nTransactions > MAX_BLOCK_SIZE_CURRENT / 60) // 60 is the lower bound for the size of a serialized CTransaction
152 0 : return UINT256_ZERO;
153 : // there can never be more hashes provided than one for every txid
154 851 : if (vHash.size() > nTransactions)
155 0 : return UINT256_ZERO;
156 : // there must be at least one bit per node in the partial tree, and at least one node per hash
157 851 : if (vBits.size() < vHash.size())
158 0 : return UINT256_ZERO;
159 : // calculate height of tree
160 : int nHeight = 0;
161 6411 : while (CalcTreeWidth(nHeight) > 1)
162 5560 : nHeight++;
163 : // traverse the partial tree
164 851 : unsigned int nBitsUsed = 0, nHashUsed = 0;
165 851 : uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch);
166 : // verify that no problems occurred during the tree traversal
167 851 : if (fBad)
168 0 : return UINT256_ZERO;
169 : // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
170 851 : if ((nBitsUsed + 7) / 8 != (vBits.size() + 7) / 8)
171 0 : return UINT256_ZERO;
172 : // verify that all hashes were consumed
173 851 : if (nHashUsed != vHash.size())
174 0 : return UINT256_ZERO;
175 851 : return hashMerkleRoot;
176 : }
|
