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