common: fix over-allocation in merkle tree creation.
What the developer wrote
Authored by Rusty Russell
common: fix over-allocation in merkle tree creation.
If we have 5 fields, ilog64(5) is 3, and (1 << 3) is 8. Adding one
made it 16.
In fact, since ilog64(4) is also 3, we should *subtract one*, but
this handles 0 more neatly (ilog64(0) is defined to return 0, as
a special case).
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
What changed, and why it matters
This commit fixes a simple math bug that caused the program to reserve up to twice as much temporary memory as needed when building a special data structure (a Merkle tree) used in BOLT 12 offers. The bug did not corrupt data or expose secrets; it only wasted memory. The patch removes an unnecessary '+1' in the allocation size calculation.
No urgent action required. Treat as a routine cleanup/optimization. If backporting, include it with other BOLT 12 fixes but do not prioritize as a security patch.
Security signals we found
Over-allocation in temporary array
No out-of-bounds access or use-after-free pattern
No attacker-controlled size leading to overflow
No secret-dependent branch or memory disclosure
Evidence from the diff
In common/bolt12_merkle.c, merkle_tlv() allocates a temporary array of struct sha256* pointers sized as a power of two based on the number of TLV fields. The old code used 1ULL << (ilog64(tal_count(fields)) + 1), which could over-allocate by up to 2x (e.g., 5 fields -> ilog64(5)=3 -> 1<<4=16 slots, when 8 would suffice). The patch changes this to 1ULL << ilog64(tal_count(fields)). The comment notes that ilog64(0) returns 0, so the simpler formula still handles the empty-fields case. This is a memory-efficiency fix, not a memory-safety or correctness fix.
Changed components
common/bolt12_merkle.cmerkle_tlv()BOLT 12 offer/invoice Merkle tree constructionInspect captured patch +1 / −1
diff --git a/common/bolt12_merkle.c b/common/bolt12_merkle.c
index dadd6dec..f4a1374b 100644
--- a/common/bolt12_merkle.c
+++ b/common/bolt12_merkle.c
@@ -171,7 +171,7 @@ void merkle_tlv(const struct tlv_field *fields, struct sha256 *merkle)
* NULL. This is less efficient than calculating the
* power-of-2 split as we recurse, but simpler. */
arr = tal_arrz(NULL, struct sha256 *,
- 1ULL << (ilog64(tal_count(fields)) + 1));
+ 1ULL << ilog64(tal_count(fields)));
n = 0;
for (size_t i = 0; i < tal_count(fields); i++) {
Why this scored 26/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.