← Watch feed
validation: pre-reserve leaves to prevent reallocs with odd vtx count
Public commit record
93/100 · Strong
What the developer wrote
Authored by Lőrinc
validation: pre-reserve leaves to prevent reallocs with odd vtx count
`ComputeMerkleRoot` duplicates the last hash when the input size is odd. If the caller provides a `std::vector` whose capacity equals its size, that extra `push_back` forces a reallocation, doubling its capacity (allocating 3x the necessary memory).
This affects roughly half of the created blocks (those with odd transaction counts), causing unnecessary memory fragmentation during every block validation.
Fix this by pre-reserving the vector capacity to account for the odd-count duplication. The expression `(size + 1) & ~1ULL` adds 1 to the size and clears the last bit, effectively rounding up to the next even number. This syntax produces optimal assembly across x86/ARM and 32/64-bit platforms for gcc/clang, see https://godbolt.org/z/xzscoq7nv.
Also switch from `resize` to `reserve` + `push_back` to eliminate the default construction of `uint256` objects that are immediately overwritten.
> ./build/bin/bench_bitcoin -filter='MerkleRoot.*' -min-time=1000
| ns/leaf | leaf/s | err% | total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
| 43.73 | 22,867,350.51 | 0.0% | 1.10 | `MerkleRoot`
| 44.17 | 22,640,349.14 | 0.0% | 1.10 | `MerkleRootWithMutation`
Massif memory measurements after show 0.8 MB peak memory usage
KB
801.4^ #
| #
| #
| #
| #
| #
| #
| # :::::@:::::@:
| #:::@@@::@:::::::::::::::@::@:@:::@@:::::::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
| #:::@ @: @:::::::::::::::@::@:@:::@ :::: ::::@::::::@:::::@::::@:::::@:
0 +----------------------------------------------------------------------->s
0 227.5
and the stacks don't show reallocs anymore:
96.37% (790,809B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->35.10% (288,064B) 0x2234AF: allocate (new_allocator.h:151)
| ->35.10% (288,064B) 0x2234AF: allocate (allocator.h:203)
| ->35.10% (288,064B) 0x2234AF: allocate (alloc_traits.h:614)
| ->35.10% (288,064B) 0x2234AF: _M_allocate (stl_vector.h:387)
| ->35.10% (288,064B) 0x2234AF: reserve (vector.tcc:79)
| ->35.10% (288,064B) 0x2234AF: ToMerkleLeaves<std::vector<uint256>, MerkleRoot(ankerl::nanobench::Bench&)::<lambda()>::<lambda(bool, const auto:46&)> > (merkle.h:19)
| ->35.10% (288,064B) 0x2234AF: operator() (merkle_root.cpp:25)
| ->35.10% (288,064B) 0x2234AF: ankerl::nanobench::Bench& ankerl::nanobench::Bench::run<MerkleRoot(ankerl::nanobench::Bench&)::{lambda()
Co-authored-by: optout21 <13562139+optout21@users.noreply.github.com>
Co-authored-by: Hodlinator <172445034+hodlinator@users.noreply.github.com>
✓ Specific, descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context✓ Explains rationale or failure mode✓ Links an issue, advisory, or supporting reference
What changed, and why it matters
This commit is a performance and memory-efficiency improvement, not a security fix. It changes how Bitcoin Core builds the list of transaction hashes before computing a Merkle root. Previously, when a block contained an odd number of transactions, the internal duplicate-hash step could force an extra memory reallocation, wasting memory and causing fragmentation. The patch pre-allocates exactly the needed capacity and avoids default-constructing unused objects. There is no vulnerability or exploit here.
Recommended action
No security action required. Treat as a normal performance optimization during review and merge.
Security signals we found
01
No security-relevant behavior change
02
Memory allocation optimization only
03
No input validation, parsing, or cryptographic changes
04
No bug class such as overflow, use-after-free, or out-of-bounds access is introduced or fixed
Evidence from the diff
The patch modifies BlockMerkleRoot, BlockWitnessMerkleRoot, and ComputeModifiedMerkleRoot to reserve vector capacity rounded up to the next even number ((size + 1) & ~1ULL) before pushing transaction hashes. This prevents a reallocation inside ComputeMerkleRoot when it duplicates the final hash for odd-sized inputs. It also replaces resize() + indexed assignment with reserve() + push_back/emplace_back, eliminating default construction of uint256 objects that were immediately overwritten. The benchmark and Massif output in the commit message confirm reduced memory spikes and removed reallocations.
Changed components
src/consensus/merkle.cppsrc/signet.cppsrc/bench/merkle_root.cppInspect captured patch +10 / −10
diff --git a/src/bench/merkle_root.cpp b/src/bench/merkle_root.cpp
index 5be59270..0e4c779f 100644
--- a/src/bench/merkle_root.cpp
+++ b/src/bench/merkle_root.cpp
@@ -24,9 +24,9 @@ static void MerkleRoot(benchmark::Bench& bench)
for (bool mutate : {false, true}) {
bench.name(mutate ? "MerkleRootWithMutation" : "MerkleRoot").batch(hashes.size()).unit("leaf").run([&] {
std::vector<uint256> leaves;
- leaves.resize(hashes.size());
+ leaves.reserve((hashes.size() + 1) & ~1ULL); // capacity rounded up to even
for (size_t s = 0; s < hashes.size(); s++) {
- leaves[s] = hashes[s];
+ leaves.push_back(hashes[s]);
}
bool mutated{false};
diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
index 703a824e..b0819a17 100644
--- a/src/consensus/merkle.cpp
+++ b/src/consensus/merkle.cpp
@@ -66,9 +66,9 @@ uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
{
std::vector<uint256> leaves;
- leaves.resize(block.vtx.size());
+ leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
for (size_t s = 0; s < block.vtx.size(); s++) {
- leaves[s] = block.vtx[s]->GetHash().ToUint256();
+ leaves.push_back(block.vtx[s]->GetHash().ToUint256());
}
return ComputeMerkleRoot(std::move(leaves), mutated);
}
@@ -76,10 +76,10 @@ uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
uint256 BlockWitnessMerkleRoot(const CBlock& block)
{
std::vector<uint256> leaves;
- leaves.resize(block.vtx.size());
- leaves[0].SetNull(); // The witness hash of the coinbase is 0.
+ leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
+ leaves.emplace_back(); // The witness hash of the coinbase is 0.
for (size_t s = 1; s < block.vtx.size(); s++) {
- leaves[s] = block.vtx[s]->GetWitnessHash().ToUint256();
+ leaves.push_back(block.vtx[s]->GetWitnessHash().ToUint256());
}
return ComputeMerkleRoot(std::move(leaves));
}
diff --git a/src/signet.cpp b/src/signet.cpp
index 6524ebff..6c1df371 100644
--- a/src/signet.cpp
+++ b/src/signet.cpp
@@ -58,10 +58,10 @@ static bool FetchAndClearCommitmentSection(const std::span<const uint8_t> header
static uint256 ComputeModifiedMerkleRoot(const CMutableTransaction& cb, const CBlock& block)
{
std::vector<uint256> leaves;
- leaves.resize(block.vtx.size());
- leaves[0] = cb.GetHash().ToUint256();
+ leaves.reserve((block.vtx.size() + 1) & ~1ULL); // capacity rounded up to even
+ leaves.push_back(cb.GetHash().ToUint256());
for (size_t s = 1; s < block.vtx.size(); ++s) {
- leaves[s] = block.vtx[s]->GetHash().ToUint256();
+ leaves.push_back(block.vtx[s]->GetHash().ToUint256());
}
return ComputeMerkleRoot(std::move(leaves));
}
Risk score
Our methodology →Why this scored 20/100
Human-validated context
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
No validated notes yet.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.