Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2014 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 : #include "utilstrencodings.h"
11 :
12 : using namespace std;
13 :
14 22 : CMerkleBlock::CMerkleBlock(const CBlock& block, CBloomFilter& filter)
15 : {
16 11 : header = block.GetBlockHeader();
17 :
18 : vector<bool> vMatch;
19 : vector<uint256> vHashes;
20 :
21 22 : vMatch.reserve(block.vtx.size());
22 22 : vHashes.reserve(block.vtx.size());
23 :
24 137 : for (unsigned int i = 0; i < block.vtx.size(); i++)
25 : {
26 189 : const uint256& hash = block.vtx[i].GetHash();
27 63 : if (filter.IsRelevantAndUpdate(block.vtx[i]))
28 : {
29 20 : vMatch.push_back(true);
30 20 : vMatchedTxn.push_back(make_pair(i, hash));
31 : }
32 : else
33 43 : vMatch.push_back(false);
34 63 : vHashes.push_back(hash);
35 : }
36 :
37 11 : txn = CPartialMerkleTree(vHashes, vMatch);
38 11 : }
39 :
40 14 : CMerkleBlock::CMerkleBlock(const CBlock& block, const std::set<uint256>& txids)
41 : {
42 7 : header = block.GetBlockHeader();
43 :
44 : vector<bool> vMatch;
45 : vector<uint256> vHashes;
46 :
47 14 : vMatch.reserve(block.vtx.size());
48 14 : vHashes.reserve(block.vtx.size());
49 :
50 49 : for (unsigned int i = 0; i < block.vtx.size(); i++)
51 : {
52 63 : const uint256& hash = block.vtx[i].GetHash();
53 21 : if (txids.count(hash))
54 10 : vMatch.push_back(true);
55 : else
56 11 : vMatch.push_back(false);
57 21 : vHashes.push_back(hash);
58 : }
59 :
60 7 : txn = CPartialMerkleTree(vHashes, vMatch);
61 7 : }
62 :
63 143476 : uint256 CPartialMerkleTree::CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid) {
64 143476 : if (height == 0) {
65 : // hash at height 0 is the txids themself
66 181856 : return vTxid[pos];
67 : } else {
68 : // calculate left hash
69 52548 : uint256 left = CalcHash(height-1, pos*2, vTxid), right;
70 : // calculate right hash if not beyond the end of the array - copy left hash otherwise1
71 105096 : if (pos*2+1 < CalcTreeWidth(height-1))
72 52304 : right = CalcHash(height-1, pos*2+1, vTxid);
73 : else
74 244 : right = left;
75 : // combine subhashes
76 52548 : return Hash(BEGIN(left), END(left), BEGIN(right), END(right));
77 : }
78 : }
79 :
80 77185 : void CPartialMerkleTree::TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) {
81 : // determine whether this node is the parent of at least one matched txid
82 77185 : bool fParentOfMatch = false;
83 947172 : for (unsigned int p = pos << height; p < (pos+1) << height && p < nTransactions; p++)
84 1739974 : fParentOfMatch |= vMatch[p];
85 : // store as flag bit
86 77185 : vBits.push_back(fParentOfMatch);
87 77185 : if (height==0 || !fParentOfMatch) {
88 : // if at height 0, or nothing interesting below, store hash and stop
89 38624 : vHash.push_back(CalcHash(height, pos, vTxid));
90 : } else {
91 : // otherwise, don't store any hash, but descend into the subtrees
92 38561 : TraverseAndBuild(height-1, pos*2, vTxid, vMatch);
93 77122 : if (pos*2+1 < CalcTreeWidth(height-1))
94 38437 : TraverseAndBuild(height-1, pos*2+1, vTxid, vMatch);
95 : }
96 77185 : }
97 :
98 385419 : uint256 CPartialMerkleTree::TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch) {
99 770838 : if (nBitsUsed >= vBits.size()) {
100 : // overflowed the bits array - failure
101 0 : fBad = true;
102 : return uint256();
103 : }
104 1156257 : bool fParentOfMatch = vBits[nBitsUsed++];
105 385419 : if (height==0 || !fParentOfMatch) {
106 : // if at height 0, or nothing interesting below, use stored hash and do not descend
107 385716 : if (nHashUsed >= vHash.size()) {
108 : // overflowed the hash array - failure
109 0 : fBad = true;
110 : return uint256();
111 : }
112 385716 : const uint256 &hash = vHash[nHashUsed++];
113 192858 : if (height==0 && fParentOfMatch) // in case of height 0, we have a matched txid
114 97113 : vMatch.push_back(hash);
115 192858 : return hash;
116 : } else {
117 : // otherwise, descend into the subtrees to extract matched txids and hashes
118 192561 : uint256 left = TraverseAndExtract(height-1, pos*2, nBitsUsed, nHashUsed, vMatch), right;
119 385122 : if (pos*2+1 < CalcTreeWidth(height-1)) {
120 192001 : right = TraverseAndExtract(height-1, pos*2+1, nBitsUsed, nHashUsed, vMatch);
121 192001 : if (right == left) {
122 : // The left and right branches should never be identical, as the transaction
123 : // hashes covered by them must each be unique.
124 1 : fBad = true;
125 : }
126 : } else {
127 560 : right = left;
128 : }
129 : // and combine them before returning
130 192561 : return Hash(BEGIN(left), END(left), BEGIN(right), END(right));
131 : }
132 : }
133 :
134 748 : CPartialMerkleTree::CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch) : nTransactions(vTxid.size()), fBad(false) {
135 : // reset state
136 187 : vBits.clear();
137 187 : vHash.clear();
138 :
139 : // calculate height of tree
140 187 : int nHeight = 0;
141 2865 : while (CalcTreeWidth(nHeight) > 1)
142 1152 : nHeight++;
143 :
144 : // traverse the partial tree
145 187 : TraverseAndBuild(nHeight, 0, vTxid, vMatch);
146 187 : }
147 :
148 579 : CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
149 :
150 857 : uint256 CPartialMerkleTree::ExtractMatches(std::vector<uint256> &vMatch) {
151 : vMatch.clear();
152 : // An empty set will not work
153 857 : if (nTransactions == 0)
154 : return uint256();
155 : // check for excessively high numbers of transactions
156 857 : if (nTransactions > MAX_BLOCK_SIZE / 60) // 60 is the lower bound for the size of a serialized CTransaction
157 : return uint256();
158 : // there can never be more hashes provided than one for every txid
159 1714 : if (vHash.size() > nTransactions)
160 : return uint256();
161 : // there must be at least one bit per node in the partial tree, and at least one node per hash
162 1714 : if (vBits.size() < vHash.size())
163 : return uint256();
164 : // calculate height of tree
165 : int nHeight = 0;
166 12854 : while (CalcTreeWidth(nHeight) > 1)
167 5570 : nHeight++;
168 : // traverse the partial tree
169 857 : unsigned int nBitsUsed = 0, nHashUsed = 0;
170 857 : uint256 hashMerkleRoot = TraverseAndExtract(nHeight, 0, nBitsUsed, nHashUsed, vMatch);
171 : // verify that no problems occurred during the tree traversal
172 857 : if (fBad)
173 : return uint256();
174 : // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
175 1712 : if ((nBitsUsed+7)/8 != (vBits.size()+7)/8)
176 : return uint256();
177 : // verify that all hashes were consumed
178 1712 : if (nHashUsed != vHash.size())
179 : return uint256();
180 856 : return hashMerkleRoot;
181 : }
|
