1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2015 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.
6 #include "merkleblock.h"
9 #include "consensus/consensus.h"
10 #include "utilstrencodings.h"
14 CMerkleBlock::CMerkleBlock(const CBlock
& block
, CBloomFilter
& filter
)
16 header
= block
.GetBlockHeader();
19 vector
<uint256
> vHashes
;
21 vMatch
.reserve(block
.vtx
.size());
22 vHashes
.reserve(block
.vtx
.size());
24 for (unsigned int i
= 0; i
< block
.vtx
.size(); i
++)
26 const uint256
& hash
= block
.vtx
[i
].GetHash();
27 if (filter
.IsRelevantAndUpdate(block
.vtx
[i
]))
29 vMatch
.push_back(true);
30 vMatchedTxn
.push_back(make_pair(i
, hash
));
33 vMatch
.push_back(false);
34 vHashes
.push_back(hash
);
37 txn
= CPartialMerkleTree(vHashes
, vMatch
);
40 CMerkleBlock::CMerkleBlock(const CBlock
& block
, const std::set
<uint256
>& txids
)
42 header
= block
.GetBlockHeader();
45 vector
<uint256
> vHashes
;
47 vMatch
.reserve(block
.vtx
.size());
48 vHashes
.reserve(block
.vtx
.size());
50 for (unsigned int i
= 0; i
< block
.vtx
.size(); i
++)
52 const uint256
& hash
= block
.vtx
[i
].GetHash();
53 if (txids
.count(hash
))
54 vMatch
.push_back(true);
56 vMatch
.push_back(false);
57 vHashes
.push_back(hash
);
60 txn
= CPartialMerkleTree(vHashes
, vMatch
);
63 uint256
CPartialMerkleTree::CalcHash(int height
, unsigned int pos
, const std::vector
<uint256
> &vTxid
) {
65 // hash at height 0 is the txids themself
68 // calculate left hash
69 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 if (pos
*2+1 < CalcTreeWidth(height
-1))
72 right
= CalcHash(height
-1, pos
*2+1, vTxid
);
76 return Hash(BEGIN(left
), END(left
), BEGIN(right
), END(right
));
80 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 bool fParentOfMatch
= false;
83 for (unsigned int p
= pos
<< height
; p
< (pos
+1) << height
&& p
< nTransactions
; p
++)
84 fParentOfMatch
|= vMatch
[p
];
86 vBits
.push_back(fParentOfMatch
);
87 if (height
==0 || !fParentOfMatch
) {
88 // if at height 0, or nothing interesting below, store hash and stop
89 vHash
.push_back(CalcHash(height
, pos
, vTxid
));
91 // otherwise, don't store any hash, but descend into the subtrees
92 TraverseAndBuild(height
-1, pos
*2, vTxid
, vMatch
);
93 if (pos
*2+1 < CalcTreeWidth(height
-1))
94 TraverseAndBuild(height
-1, pos
*2+1, vTxid
, vMatch
);
98 uint256
CPartialMerkleTree::TraverseAndExtract(int height
, unsigned int pos
, unsigned int &nBitsUsed
, unsigned int &nHashUsed
, std::vector
<uint256
> &vMatch
, std::vector
<unsigned int> &vnIndex
) {
99 if (nBitsUsed
>= vBits
.size()) {
100 // overflowed the bits array - failure
104 bool fParentOfMatch
= vBits
[nBitsUsed
++];
105 if (height
==0 || !fParentOfMatch
) {
106 // if at height 0, or nothing interesting below, use stored hash and do not descend
107 if (nHashUsed
>= vHash
.size()) {
108 // overflowed the hash array - failure
112 const uint256
&hash
= vHash
[nHashUsed
++];
113 if (height
==0 && fParentOfMatch
) { // in case of height 0, we have a matched txid
114 vMatch
.push_back(hash
);
115 vnIndex
.push_back(pos
);
119 // otherwise, descend into the subtrees to extract matched txids and hashes
120 uint256 left
= TraverseAndExtract(height
-1, pos
*2, nBitsUsed
, nHashUsed
, vMatch
, vnIndex
), right
;
121 if (pos
*2+1 < CalcTreeWidth(height
-1)) {
122 right
= TraverseAndExtract(height
-1, pos
*2+1, nBitsUsed
, nHashUsed
, vMatch
, vnIndex
);
124 // The left and right branches should never be identical, as the transaction
125 // hashes covered by them must each be unique.
131 // and combine them before returning
132 return Hash(BEGIN(left
), END(left
), BEGIN(right
), END(right
));
136 CPartialMerkleTree::CPartialMerkleTree(const std::vector
<uint256
> &vTxid
, const std::vector
<bool> &vMatch
) : nTransactions(vTxid
.size()), fBad(false) {
141 // calculate height of tree
143 while (CalcTreeWidth(nHeight
) > 1)
146 // traverse the partial tree
147 TraverseAndBuild(nHeight
, 0, vTxid
, vMatch
);
150 CPartialMerkleTree::CPartialMerkleTree() : nTransactions(0), fBad(true) {}
152 uint256
CPartialMerkleTree::ExtractMatches(std::vector
<uint256
> &vMatch
, std::vector
<unsigned int> &vnIndex
) {
154 // An empty set will not work
155 if (nTransactions
== 0)
157 // check for excessively high numbers of transactions
158 if (nTransactions
> MAX_BLOCK_SIZE
/ 60) // 60 is the lower bound for the size of a serialized CTransaction
160 // there can never be more hashes provided than one for every txid
161 if (vHash
.size() > nTransactions
)
163 // there must be at least one bit per node in the partial tree, and at least one node per hash
164 if (vBits
.size() < vHash
.size())
166 // calculate height of tree
168 while (CalcTreeWidth(nHeight
) > 1)
170 // traverse the partial tree
171 unsigned int nBitsUsed
= 0, nHashUsed
= 0;
172 uint256 hashMerkleRoot
= TraverseAndExtract(nHeight
, 0, nBitsUsed
, nHashUsed
, vMatch
, vnIndex
);
173 // verify that no problems occurred during the tree traversal
176 // verify that all bits were consumed (except for the padding caused by serializing it as a byte sequence)
177 if ((nBitsUsed
+7)/8 != (vBits
.size()+7)/8)
179 // verify that all hashes were consumed
180 if (nHashUsed
!= vHash
.size())
182 return hashMerkleRoot
;