ComputeMerkleRoot already received a list of values, usually sized to fit their current size exactly (i.e. capacity() == size()). We can of course increase the capacity inside - it’s what:
0if (hashes.size() & 1) {
1 hashes.push_back(hashes.back());
2}
does already, but if we want to avoid reallocations, we have to predict the size of the vector before we start populating it.
We could add some kind of lambda as a parameter and an expected size maybe, something like:
0template <typename Gen>
1uint256 GenerateMerkleRoot(std::size_t count, Gen&& gen, bool* mutated = nullptr)
2{
3 std::vector<uint256> leaves;
4 leaves.reserve(RoundUpToEven(count));
5 for (std::size_t i{0}; i < count; ++i) {
6 leaves.push_back(gen(i));
7 }
8 return ComputeMerkleRoot(std::move(leaves), mutated);
9}
and the production code callers would look like:
0static uint256 ComputeModifiedMerkleRoot(const CMutableTransaction& cb, const CBlock& block)
1{
2 return GenerateMerkleRoot(block.vtx.size(), [&](auto i) { return i == 0 ? cb.GetHash() : block.vtx[i]->GetHash(); });
3}
4
5uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
6{
7 return GenerateMerkleRoot(block.vtx.size(), [&](auto i) { return block.vtx[i]->GetHash(); }, mutated);
8}
9uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
10{
11 return GenerateMerkleRoot(block.vtx.size(), [&](auto i) { return i == 0 ? uint256{} : uint256(block.vtx[i]->GetWitnessHash()); }, mutated);
12}
Would that be simpler in your opinion?
0diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
1index 8c56d979a5..a0e358b005 100644
2--- a/src/consensus/merkle.cpp
3+++ b/src/consensus/merkle.cpp
4@@ -5,7 +5,6 @@
5 #include <consensus/merkle.h>
6 #include <hash.h>
7 #include <util/check.h>
8-#include <util/ints.h>
9
10 /* WARNING! If you're reading this because you're learning about crypto
11 and/or designing a new system that will use merkle trees, keep in mind
12@@ -63,26 +62,14 @@ uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
13 return hashes[0];
14 }
15
16-
17 uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
18 {
19- std::vector<uint256> leaves;
20- leaves.reserve(RoundUpToEven(block.vtx.size()));
21- for (size_t s = 0; s < block.vtx.size(); s++) {
22- leaves.push_back(block.vtx[s]->GetHash());
23- }
24- return ComputeMerkleRoot(std::move(leaves), mutated);
25+ return GenerateMerkleRoot(block.vtx.size(), [&](auto i) { return block.vtx[i]->GetHash(); }, mutated);
26 }
27
28 uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
29 {
30- std::vector<uint256> leaves;
31- leaves.reserve(RoundUpToEven(block.vtx.size()));
32- leaves.emplace_back(); // The witness hash of the coinbase is 0.
33- for (size_t s = 1; s < block.vtx.size(); s++) {
34- leaves.push_back(block.vtx[s]->GetWitnessHash());
35- }
36- return ComputeMerkleRoot(std::move(leaves), mutated);
37+ return GenerateMerkleRoot(block.vtx.size(), [&](auto i) { return i == 0 ? uint256{} : uint256(block.vtx[i]->GetWitnessHash()); }, mutated);
38 }
39
40 /* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
41diff --git a/src/consensus/merkle.h b/src/consensus/merkle.h
42index c722cbe446..8b5c14157a 100644
43--- a/src/consensus/merkle.h
44+++ b/src/consensus/merkle.h
45@@ -9,9 +9,21 @@
46
47 #include <primitives/block.h>
48 #include <uint256.h>
49+#include <util/ints.h>
50
51 uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated = nullptr);
52
53+template <typename Gen>
54+uint256 GenerateMerkleRoot(std::size_t count, Gen&& gen, bool* mutated = nullptr)
55+{
56+ std::vector<uint256> leaves;
57+ leaves.reserve(RoundUpToEven(count));
58+ for (std::size_t i{0}; i < count; ++i) {
59+ leaves.push_back(gen(i));
60+ }
61+ return ComputeMerkleRoot(std::move(leaves), mutated);
62+}
63+
64 /*
65 * Compute the Merkle root of the transactions in a block.
66 * *mutated is set to true if a duplicated subtree was found.
67diff --git a/src/signet.cpp b/src/signet.cpp
68index 3104b7f2d7..5aea084f15 100644
69--- a/src/signet.cpp
70+++ b/src/signet.cpp
71@@ -58,13 +58,8 @@ static bool FetchAndClearCommitmentSection(const std::span<const uint8_t> header
72
73 static uint256 ComputeModifiedMerkleRoot(const CMutableTransaction& cb, const CBlock& block)
74 {
75- std::vector<uint256> leaves;
76- leaves.reserve(RoundUpToEven(block.vtx.size()));
77- leaves.push_back(cb.GetHash());
78- for (size_t s = 1; s < block.vtx.size(); ++s) {
79- leaves.push_back(block.vtx[s]->GetHash());
80- }
81- return ComputeMerkleRoot(std::move(leaves));
82+ return GenerateMerkleRoot(block.vtx.size(),
83+ [&](auto i) { return i ? block.vtx[i]->GetHash() : cb.GetHash(); });
84 }
85
86 std::optional<SignetTxs> SignetTxs::Create(const CBlock& block, const CScript& challenge)
