Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2019 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 186 : std::vector<unsigned char> BitsToBytes(const std::vector<bool>& bits)
13 : {
14 186 : std::vector<unsigned char> ret((bits.size() + 7) / 8);
15 76673 : for (unsigned int p = 0; p < bits.size(); p++) {
16 76487 : ret[p / 8] |= bits[p] << (p % 8);
17 : }
18 : return ret;
19 186 : }
20 :
21 184 : std::vector<bool> BytesToBits(const std::vector<unsigned char>& bytes)
22 : {
23 184 : std::vector<bool> ret(bytes.size() * 8);
24 77504 : for (unsigned int p = 0; p < ret.size(); p++) {
25 77320 : ret[p] = (bytes[p / 8] & (1 << (p % 8))) != 0;
26 : }
27 : return ret;
28 184 : }
29 :
30 60 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter* filter, const std::set<uint256>* txids)
31 30 : {
32 30 : header = block.GetBlockHeader();
33 :
34 30 : std::vector<bool> vMatch;
35 30 : std::vector<uint256> vHashes;
36 :
37 30 : vMatch.reserve(block.vtx.size());
38 30 : vHashes.reserve(block.vtx.size());
39 :
40 150 : for (unsigned int i = 0; i < block.vtx.size(); i++)
41 : {
42 120 : const uint256& hash = block.vtx[i]->GetHash();
43 120 : if (txids && txids->count(hash)) {
44 19 : vMatch.push_back(true);
45 120 : } else if (filter && filter->IsRelevantAndUpdate(*block.vtx[i])) {
46 23 : vMatch.push_back(true);
47 23 : vMatchedTxn.emplace_back(i, hash);
48 : } else {
49 78 : vMatch.push_back(false);
50 : }
51 120 : vHashes.push_back(hash);
52 : }
53 :
54 30 : txn = CPartialMerkleTree(vHashes, vMatch);
55 60 : }
56 :
57 143848 : uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid) {
58 : //we can never have zero txs in a merkle block, we always need the coinbase tx
59 : //if we do not have this assert, we can hit a memory access violation when indexing into vTxid
60 143848 : assert(vTxid.size() != 0);
61 143848 : if (height == 0) {
62 : // hash at height 0 is the txids themself
63 90964 : return vTxid[pos];
64 : } else {
65 : // calculate left hash
66 52884 : uint256 left = CalcHash(height-1, pos*2, vTxid), right;
67 : // calculate right hash if not beyond the end of the array - copy left hash otherwise
68 52884 : if (pos*2+1 < CalcTreeWidth(height-1))
69 52635 : right = CalcHash(height-1, pos*2+1, vTxid);
70 : else
71 249 : right = left;
72 : // combine subhashes
73 52884 : return Hash(left, right);
74 52884 : }
75 143848 : }
76 :
77 76586 : void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) {
78 : // determine whether this node is the parent of at least one matched txid
79 76586 : bool fParentOfMatch = false;
80 939092 : for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
81 862506 : fParentOfMatch |= vMatch[p];
82 : // store as flag bit
83 76586 : vBits.push_back(fParentOfMatch);
84 76586 : if (height==0 || !fParentOfMatch) {
85 : // if at height 0, or nothing interesting below, store hash and stop
86 38329 : vHash.push_back(CalcHash(height, pos, vTxid));
87 38329 : } else {
88 : // otherwise, don't store any hash, but descend into the subtrees
89 38257 : TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
90 38257 : if (pos*2+1 < CalcTreeWidth(height-1))
91 38130 : TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
92 : }
93 76586 : }
94 :
95 382263 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
96 382263 : if (nBitsUsed >= vBits.size()) {
97 : // overflowed the bits array - failure
98 0 : fBad = true;
99 0 : return uint256();
100 : }
101 382263 : bool fParentOfMatch = vBits[nBitsUsed++];
102 382263 : if (height==0 || !fParentOfMatch) {
103 : // if at height 0, or nothing interesting below, use stored hash and do not descend
104 191285 : if (nHashUsed >= vHash.size()) {
105 : // overflowed the hash array - failure
106 0 : fBad = true;
107 0 : return uint256();
108 : }
109 191285 : const uint256 &hash = vHash[nHashUsed++];
110 191285 : if (height==0 && fParentOfMatch) { // in case of height 0, we have a matched txid
111 95598 : vMatch.push_back(hash);
112 95598 : vnIndex.push_back(pos);
113 95598 : }
114 191285 : return hash;
115 : } else {
116 : // otherwise, descend into the subtrees to extract matched txids and hashes
117 190978 : uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch, vnIndex), right;
118 190978 : if (pos*2+1 < CalcTreeWidth(height-1)) {
119 190417 : right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch, vnIndex);
120 190417 : if (right == left) {
121 : // The left and right branches should never be identical, as the transaction
122 : // hashes covered by them must each be unique.
123 1 : fBad = true;
124 1 : }
125 : } else {
126 561 : right = left;
127 : }
128 : // and combine them before returning
129 190978 : return Hash(left, right);
130 190978 : }
131 382263 : }
132 :
133 398 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
134 : // reset state
135 199 : vBits.clear();
136 199 : vHash.clear();
137 :
138 : // calculate height of tree
139 : int nHeight = 0;
140 1367 : while (CalcTreeWidth(nHeight) > 1)
141 1168 : nHeight++;
142 :
143 : // traverse the partial tree
144 199 : TraverseAndBuild(nHeight, 0, vTxid, vMatch);
145 398 : }
146 :
147 274 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
148 :
149 868 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch, std::vector<unsigned int> &vnIndex) {
150 868 : vMatch.clear();
151 : // An empty set will not work
152 868 : if (nTransactions == 0)
153 0 : return uint256();
154 : // check for excessively high numbers of transactions
155 868 : if (nTransactions > MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT)
156 0 : return uint256();
157 : // there can never be more hashes provided than one for every txid
158 868 : if (vHash.size() > nTransactions)
159 0 : return uint256();
160 : // there must be at least one bit per node in the partial tree, and at least one node per hash
161 868 : if (vBits.size() < vHash.size())
162 0 : return uint256();
163 : // calculate height of tree
164 : int nHeight = 0;
165 6457 : while (CalcTreeWidth(nHeight) > 1)
166 5589 : nHeight++;
167 : // traverse the partial tree
168 868 : unsigned int nBitsUsed = 0, nHashUsed = 0;
169 868 : uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch, vnIndex);
170 : // verify that no problems occurred during the tree traversal
171 868 : if (fBad)
172 1 : return uint256();
173 : // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
174 867 : if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
175 0 : return uint256();
176 : // verify that all hashes were consumed
177 867 : if (nHashUsed != vHash.size())
178 0 : return uint256();
179 867 : return hashMerkleRoot;
180 868 : }
|
