8 #include <boost/test/unit_test.hpp>
14 for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
16 hash =
Hash(*it, hash);
18 hash =
Hash(hash, *it);
26 static void MerkleComputation(
const std::vector<uint256>& leaves,
uint256* proot,
bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
27 if (pbranch) pbranch->clear();
28 if (leaves.size() == 0) {
29 if (pmutated) *pmutated =
false;
45 while (
count < leaves.size()) {
47 bool matchh =
count == branchpos;
53 for (level = 0; !(
count & ((uint32_t{1}) << level)); level++) {
56 pbranch->push_back(inner[level]);
57 }
else if (matchlevel == level) {
58 pbranch->push_back(h);
77 while (!(
count & ((uint32_t{1}) << level))) {
81 bool matchh = matchlevel == level;
82 while (
count != ((uint32_t{1}) << level)) {
86 if (pbranch && matchh) {
87 pbranch->push_back(h);
92 count += ((uint32_t{1}) << level);
95 while (!(
count & ((uint32_t{1}) << level))) {
98 pbranch->push_back(inner[level]);
99 }
else if (matchlevel == level) {
100 pbranch->push_back(h);
109 if (pmutated) *pmutated =
mutated;
110 if (proot) *proot = h;
114 std::vector<uint256>
ret;
121 std::vector<uint256> leaves;
122 leaves.resize(block.
vtx.size());
123 for (
size_t s = 0; s < block.
vtx.size(); s++) {
124 leaves[s] = block.
vtx[s]->GetHash();
133 vMerkleTree.reserve(block.
vtx.size() * 2 + 16);
134 for (std::vector<CTransactionRef>::const_iterator it(block.
vtx.begin()); it != block.
vtx.end(); ++it)
135 vMerkleTree.push_back((*it)->GetHash());
138 for (
int nSize = block.
vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
140 for (
int i = 0; i < nSize; i += 2)
142 int i2 = std::min(i+1, nSize-1);
143 if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
147 vMerkleTree.push_back(
Hash(vMerkleTree[j+i], vMerkleTree[j+i2]));
154 return (vMerkleTree.empty() ?
uint256() : vMerkleTree.back());
160 std::vector<uint256> vMerkleBranch;
162 for (
int nSize = block.
vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
164 int i = std::min(nIndex^1, nSize-1);
165 vMerkleBranch.push_back(vMerkleTree[j+i]);
169 return vMerkleBranch;
172 static inline int ctz(uint32_t i) {
173 if (i == 0)
return 0;
184 for (
int i = 0; i < 32; i++) {
188 for (
int mutate = 0; mutate <= 3; mutate++) {
189 int duplicate1 = mutate >= 1 ? 1 <<
ctz(ntx) : 0;
190 if (duplicate1 >= ntx)
break;
191 int ntx1 = ntx + duplicate1;
192 int duplicate2 = mutate >= 2 ? 1 <<
ctz(ntx1) : 0;
193 if (duplicate2 >= ntx1)
break;
194 int ntx2 = ntx1 + duplicate2;
195 int duplicate3 = mutate >= 3 ? 1 <<
ctz(ntx2) : 0;
196 if (duplicate3 >= ntx2)
break;
197 int ntx3 = ntx2 + duplicate3;
200 block.
vtx.resize(ntx);
201 for (
int j = 0; j < ntx; j++) {
207 bool unmutatedMutated =
false;
211 block.
vtx.resize(ntx3);
212 for (
int j = 0; j < duplicate1; j++) {
213 block.
vtx[ntx + j] = block.
vtx[ntx + j - duplicate1];
215 for (
int j = 0; j < duplicate2; j++) {
216 block.
vtx[ntx1 + j] = block.
vtx[ntx1 + j - duplicate2];
218 for (
int j = 0; j < duplicate3; j++) {
219 block.
vtx[ntx2 + j] = block.
vtx[ntx2 + j - duplicate3];
222 bool oldMutated =
false;
223 std::vector<uint256> merkleTree;
226 bool newMutated =
false;
235 for (
int loop = 0; loop < std::min(ntx, 16); loop++) {
279 CBlock block, blockWithRepeatedLastTx;
283 for (std::size_t pos = 0; pos < block.
vtx.size(); pos++) {
289 blockWithRepeatedLastTx = block;
290 blockWithRepeatedLastTx.
vtx.push_back(blockWithRepeatedLastTx.
vtx.back());
302 CBlock block, leftSubtreeBlock, rightSubtreeBlock;
306 for (pos = 0; pos < block.
vtx.size(); pos++) {
312 for (pos = 0; pos < block.
vtx.size() / 2; pos++)
313 leftSubtreeBlock.
vtx.push_back(block.
vtx[pos]);
315 for (pos = block.
vtx.size() / 2; pos < block.
vtx.size(); pos++)
316 rightSubtreeBlock.
vtx.push_back(block.
vtx[pos]);
321 std::vector<uint256> leftRight;
322 leftRight.push_back(rootOfLeftSubtree);
323 leftRight.push_back(rootOfRightSubtree);
334 for (std::size_t pos = 0; pos < block.
vtx.size(); pos++) {
342 std::vector<uint256> hashes;
343 hashes.resize(block.
vtx.size());
345 hashes[1] = block.
vtx[1]->GetHash();
std::vector< CTransactionRef > vtx
A hasher class for Bitcoin's 256-bit hash (double SHA-256).
CHash256 & Write(Span< const unsigned char > input)
void Finalize(Span< unsigned char > output)
BOOST_AUTO_TEST_SUITE_END()
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
uint256 ComputeMerkleRoot(std::vector< uint256 > hashes, bool *mutated)
uint256 BlockMerkleRoot(const CBlock &block, bool *mutated)
uint256 BlockWitnessMerkleRoot(const CBlock &block, bool *mutated)
static uint256 BlockBuildMerkleTree(const CBlock &block, bool *fMutated, std::vector< uint256 > &vMerkleTree)
static std::vector< uint256 > BlockMerkleBranch(const CBlock &block, uint32_t position)
static int ctz(uint32_t i)
static void MerkleComputation(const std::vector< uint256 > &leaves, uint256 *proot, bool *pmutated, uint32_t branchpos, std::vector< uint256 > *pbranch)
static uint256 ComputeMerkleRootFromBranch(const uint256 &leaf, const std::vector< uint256 > &vMerkleBranch, uint32_t nIndex)
static std::vector< uint256 > BlockGetMerkleBranch(const CBlock &block, const std::vector< uint256 > &vMerkleTree, int nIndex)
BOOST_AUTO_TEST_CASE(merkle_test)
static std::vector< uint256 > ComputeMerkleBranch(const std::vector< uint256 > &leaves, uint32_t position)
#define BOOST_CHECK_EQUAL(v1, v2)
#define BOOST_CHECK(expr)
static CTransactionRef MakeTransactionRef(Tx &&txIn)
static uint64_t InsecureRandRange(uint64_t range)
A mutable version of CTransaction.
Testing setup that configures a complete environment.