primitives: add minimum allocation size
What the developer wrote
Authored by Andrew Poelstra
primitives: add minimum allocation size
It's possible to construct witnesses that force our current logic to repeatedly
allocate a single byte, many thousands of times. This is inefficient, and on
some targets (notably: x86 with fuzzer instrumentation) it is slow to the point
of being a DoS vector.
I was not able to construct a unit test which meaningfully demonstrates this
behavior (or even runs slowly enough to notice), but with this patch, a fuzzer
input which previously took several seconds now takes only milliseconds.
What changed, and why it matters
This commit fixes a performance problem in how the library reads Bitcoin transaction witness data. Before the fix, specially crafted witness data could force the code to allocate memory one byte at a time, thousands of times in a row. That slowness could be abused to cause denial of service, especially when the code is run under fuzz testing or other instrumentation. The fix ensures the code always allocates at least 1,000 bytes at once, removing the repeated tiny allocations.
Apply the patch. It is a low-risk performance hardening change. Consider adding a regression test or benchmark that exercises large witness deserialization to prevent reintroduction of the pathological allocation pattern.
Security signals we found
DoS vector explicitly mentioned in commit message
Pathological allocation pattern in deserialization
Fuzzer instrumentation target noted as affected
No bounds or correctness change; only allocation batching
Evidence from the diff
In primitives/src/witness.rs, the WitnessDecoder previously called reserve_exact with a batch_size of bytes_needed.min(MAX_VECTOR_ALLOCATE). When bytes_needed was 1, this reserved exactly one byte per iteration, causing O(n) allocations for n bytes of witness content. The patch introduces MIN_VECTOR_ALLOCATE = 1,000 and uses clamp(MIN_VECTOR_ALLOCATE, MAX_VECTOR_ALLOCATE) so every growth step reserves at least 1,000 bytes. This amortizes allocation and eliminates the pathological single-byte allocation loop.
Changed components
primitives/src/witness.rsWitnessDecoderWitness deserialization (alloc feature)Inspect captured patch +5 / −1
diff --git a/primitives/src/witness.rs b/primitives/src/witness.rs
index 9c0c23bd..ba1ece52 100644
--- a/primitives/src/witness.rs
+++ b/primitives/src/witness.rs
@@ -33,6 +33,10 @@ use self::error::WitnessDecoderErrorInner;
#[cfg(feature = "alloc")]
const MAX_VECTOR_ALLOCATE: usize = 1_000_000;
+/// Minimum amount of memory (in bytes) to allocate at once when deserializing vectors.
+#[cfg(feature = "alloc")]
+const MIN_VECTOR_ALLOCATE: usize = 1_000;
+
/// Maximum number of items in a witness stack.
///
/// This is an anti-DoS limit based on Bitcoin's 4MB block weight limit.
@@ -350,7 +354,7 @@ impl WitnessDecoder {
let available_capacity = self.content.capacity() - self.content.len();
if available_capacity == 0 {
- let batch_size = bytes_needed.min(MAX_VECTOR_ALLOCATE);
+ let batch_size = bytes_needed.clamp(MIN_VECTOR_ALLOCATE, MAX_VECTOR_ALLOCATE);
self.content.reserve_exact(batch_size);
}
Why this scored 57/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.