9 #include <boost/test/unit_test.hpp>
15 for (std::vector<uint256>::const_iterator it = vMerkleBranch.begin(); it != vMerkleBranch.end(); ++it) {
17 hash =
Hash(*it, hash);
19 hash =
Hash(hash, *it);
27 static void MerkleComputation(
const std::vector<uint256>& leaves,
uint256* proot,
bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) {
28 if (pbranch) pbranch->clear();
29 if (leaves.size() == 0) {
30 if (pmutated) *pmutated =
false;
46 while (
count < leaves.size()) {
48 bool matchh =
count == branchpos;
54 for (level = 0; !(
count & ((uint32_t{1}) << level)); level++) {
57 pbranch->push_back(inner[level]);
58 }
else if (matchlevel == level) {
59 pbranch->push_back(h);
63 mutated |= (inner[level] == h);
64 h =
Hash(inner[level], h);
78 while (!(
count & ((uint32_t{1}) << level))) {
82 bool matchh = matchlevel == level;
83 while (
count != ((uint32_t{1}) << level)) {
87 if (pbranch && matchh) {
88 pbranch->push_back(h);
93 count += ((uint32_t{1}) << level);
96 while (!(
count & ((uint32_t{1}) << level))) {
99 pbranch->push_back(inner[level]);
100 }
else if (matchlevel == level) {
101 pbranch->push_back(h);
105 h =
Hash(inner[level], h);
110 if (pmutated) *pmutated = mutated;
111 if (proot) *proot = h;
115 std::vector<uint256>
ret;
122 std::vector<uint256> leaves;
123 leaves.resize(block.
vtx.size());
124 for (
size_t s = 0; s < block.
vtx.size(); s++) {
125 leaves[s] = block.
vtx[s]->GetHash();
134 vMerkleTree.reserve(block.
vtx.size() * 2 + 16);
135 for (std::vector<CTransactionRef>::const_iterator it(block.
vtx.begin()); it != block.
vtx.end(); ++it)
136 vMerkleTree.push_back((*it)->GetHash());
138 bool mutated =
false;
139 for (
int nSize = block.
vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
141 for (
int i = 0; i < nSize; i += 2)
143 int i2 = std::min(i+1, nSize-1);
144 if (i2 == i + 1 && i2 + 1 == nSize && vMerkleTree[j+i] == vMerkleTree[j+i2]) {
148 vMerkleTree.push_back(
Hash(vMerkleTree[j+i], vMerkleTree[j+i2]));
155 return (vMerkleTree.empty() ?
uint256() : vMerkleTree.back());
161 std::vector<uint256> vMerkleBranch;
163 for (
int nSize = block.
vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
165 int i = std::min(nIndex^1, nSize-1);
166 vMerkleBranch.push_back(vMerkleTree[j+i]);
170 return vMerkleBranch;
173 static inline int ctz(uint32_t i) {
174 if (i == 0)
return 0;
185 for (
int i = 0; i < 32; i++) {
189 for (
int mutate = 0; mutate <= 3; mutate++) {
190 int duplicate1 = mutate >= 1 ? 1 <<
ctz(ntx) : 0;
191 if (duplicate1 >= ntx)
break;
192 int ntx1 = ntx + duplicate1;
193 int duplicate2 = mutate >= 2 ? 1 <<
ctz(ntx1) : 0;
194 if (duplicate2 >= ntx1)
break;
195 int ntx2 = ntx1 + duplicate2;
196 int duplicate3 = mutate >= 3 ? 1 <<
ctz(ntx2) : 0;
197 if (duplicate3 >= ntx2)
break;
198 int ntx3 = ntx2 + duplicate3;
201 block.
vtx.resize(ntx);
202 for (
int j = 0; j < ntx; j++) {
208 bool unmutatedMutated =
false;
212 block.
vtx.resize(ntx3);
213 for (
int j = 0; j < duplicate1; j++) {
214 block.
vtx[ntx + j] = block.
vtx[ntx + j - duplicate1];
216 for (
int j = 0; j < duplicate2; j++) {
217 block.
vtx[ntx1 + j] = block.
vtx[ntx1 + j - duplicate2];
219 for (
int j = 0; j < duplicate3; j++) {
220 block.
vtx[ntx2 + j] = block.
vtx[ntx2 + j - duplicate3];
223 bool oldMutated =
false;
224 std::vector<uint256> merkleTree;
227 bool newMutated =
false;
236 for (
int loop = 0; loop < std::min(ntx, 16); loop++) {
255 bool mutated =
false;
265 bool mutated =
false;
280 CBlock block, blockWithRepeatedLastTx;
284 for (std::size_t pos = 0; pos < block.
vtx.size(); pos++) {
290 blockWithRepeatedLastTx = block;
291 blockWithRepeatedLastTx.
vtx.push_back(blockWithRepeatedLastTx.
vtx.back());
303 CBlock block, leftSubtreeBlock, rightSubtreeBlock;
307 for (pos = 0; pos < block.
vtx.size(); pos++) {
313 for (pos = 0; pos < block.
vtx.size() / 2; pos++)
314 leftSubtreeBlock.
vtx.push_back(block.
vtx[pos]);
316 for (pos = block.
vtx.size() / 2; pos < block.
vtx.size(); pos++)
317 rightSubtreeBlock.
vtx.push_back(block.
vtx[pos]);
322 std::vector<uint256> leftRight;
323 leftRight.push_back(rootOfLeftSubtree);
324 leftRight.push_back(rootOfRightSubtree);
335 for (std::size_t pos = 0; pos < block.
vtx.size(); pos++) {
343 std::vector<uint256> hashes;
344 hashes.resize(block.
vtx.size());
346 hashes[1] = block.
vtx[1]->GetHash();
std::vector< CTransactionRef > vtx
constexpr bool IsNull() const
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)
A mutable version of CTransaction.
Testing setup that configures a complete environment.
static uint64_t InsecureRandRange(uint64_t range)