Moderate 50 Bitcoin Committed Mar 5, 2026 · 20:09 UTC

tx: pre-allocate the full number of witnesses when deserializing

455ec5b0 View source ↗

Public commit record

What the developer wrote

Authored by Jon Griffiths

73/100 · Adequate

tx: pre-allocate the full number of witnesses when deserializing

Prevents quadratic resizing for deserializing non-standard txs with
many witnesses. Note in the transaction.c case, analyze_tx has already
run and validated that the number of witnesses is sane.

✓ Specific, descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context

The short version

What changed, and why it matters

This change fixes a performance problem when reading Bitcoin-style transactions that contain an unusually large number of 'witness' data pieces. Previously the code started with a small buffer and repeatedly grew it, which made processing time balloon (a 'quadratic' slowdown). The patch pre-allocates the exact needed size during deserialization, so large-but-valid transactions no longer cause severe delays. It is a denial-of-service/performance fix rather than a memory-corruption bug.

Recommended action

Treat as a worthwhile hardening/DoS-fix patch. Review whether callers that accept untrusted serialized transactions enforce the same witness-count limits as analyze_tx, since the public API still caps allocation at 100 items while internal deserialization paths now trust the parsed count. Consider adding tests with large witness counts to confirm linear deserialization time.

Security signals we found

quadratic complexity / algorithmic denial-of-service mitigation

pre-allocation of deserialization buffers to avoid repeated reallocations

defense against non-standard transactions with many witness items

no memory safety bug evident in diff; performance/DoS class fix

Technical analysis

Evidence from the diff

The commit introduces an internal helper tx_witness_stack_init_alloc(allocation_len, max_allocation_len, output) and keeps the public wally_tx_witness_stack_init_alloc capped at MAX_WITNESS_ITEMS_ALLOC (100). During deserialization paths (pull_witness, witness_stack_from_bytes, tx_from_bytes) the code now calls the internal helper with max_allocation_len == num_witnesses, allowing full pre-allocation of the witness stack. This avoids repeated reallocations and the associated O(n²) cost for non-standard transactions with many witnesses. The commit message states that analyze_tx has already validated the witness count as sane in the transaction.c path.

Changed components

src/transaction.csrc/pullpush.csrc/internal.hwally_tx_witness_stack_init_alloc public APItransaction deserialization (tx_from_bytes, witness_stack_from_bytes, pull_witness)

Inspect captured patch +28 / −9

diff --git a/src/internal.h b/src/internal.h
index bc07f51..70a93d0 100644
--- a/src/internal.h
+++ b/src/internal.h
@@ -132,6 +132,12 @@ const struct wally_map_item *map_find_equal_integer(const struct wally_map *lhs,
 /* Clamp initial witness stack allocation sizing */
 #define MAX_WITNESS_ITEMS_ALLOC 100u /* Non-Taproot standardness limit */
 
+/* Allows allocating a larger witness for e.g deserializing */
+struct wally_tx_witness_stack;
+int tx_witness_stack_init_alloc(size_t allocation_len,
+                                size_t max_allocation_len,
+                                struct wally_tx_witness_stack **output);
+
 /* Absolute maximum number of inputs and outputs for BTC.
  * Liquid numbers are smaller; we use the upper limit */
 #define TX_MAX_INPUTS (TX_MAX_INPUTS_ALLOC * 10)
diff --git a/src/pullpush.c b/src/pullpush.c
index 0244373..d21c475 100644
--- a/src/pullpush.c
+++ b/src/pullpush.c
@@ -260,7 +260,8 @@ int pull_witness(const unsigned char **cursor, size_t *max,
         /* Not enough bytes remaining for num_witnesses empty witnesses */
         return WALLY_EINVAL;
     }
-    ret = wally_tx_witness_stack_init_alloc(num_witnesses, witness_out);
+    ret = tx_witness_stack_init_alloc(num_witnesses, num_witnesses,
+                                      witness_out);
 
     for (i = 0; ret == WALLY_OK && i < num_witnesses; ++i) {
         const unsigned char *wit;
diff --git a/src/transaction.c b/src/transaction.c
index 0c37021..ad3c422 100644
--- a/src/transaction.c
+++ b/src/transaction.c
@@ -138,7 +138,8 @@ int wally_tx_witness_stack_clone_alloc(const struct wally_tx_witness_stack *stac
     if (!stack)
         return WALLY_EINVAL;
 
-    ret = wally_tx_witness_stack_init_alloc(stack->items_allocation_len, output);
+    ret = tx_witness_stack_init_alloc(stack->items_allocation_len,
+                                      stack->items_allocation_len, output);
     for (i = 0; ret == WALLY_OK && i < stack->num_items; ++i) {
         ret = wally_tx_witness_stack_set(*output, i,
                                          stack->items[i].witness,
@@ -151,15 +152,16 @@ int wally_tx_witness_stack_clone_alloc(const struct wally_tx_witness_stack *stac
     return ret;
 }
 
-int wally_tx_witness_stack_init_alloc(size_t allocation_len,
-                                      struct wally_tx_witness_stack **output)
+int tx_witness_stack_init_alloc(size_t allocation_len,
+                                size_t max_allocation_len,
+                                struct wally_tx_witness_stack **output)
 {
     OUTPUT_CHECK;
     OUTPUT_ALLOC(struct wally_tx_witness_stack);
 
     if (allocation_len) {
-        if (allocation_len > MAX_WITNESS_ITEMS_ALLOC)
-            allocation_len = MAX_WITNESS_ITEMS_ALLOC;
+        if (allocation_len > max_allocation_len)
+            allocation_len = max_allocation_len;
         (*output)->items = wally_calloc(allocation_len * sizeof(struct wally_tx_witness_item));
         if (!(*output)->items) {
             wally_free(*output);
@@ -172,6 +174,16 @@ int wally_tx_witness_stack_init_alloc(size_t allocation_len,
     return WALLY_OK;
 }
 
+int wally_tx_witness_stack_init_alloc(size_t allocation_len,
+                                      struct wally_tx_witness_stack **output)
+{
+    /* The public interface is limited to pre-allocating enough
+     * witness items for a standard tx, and will be slow if adding more
+     */
+    return tx_witness_stack_init_alloc(allocation_len,
+                                       MAX_WITNESS_ITEMS_ALLOC, output);
+}
+
 static int tx_witness_stack_free(struct wally_tx_witness_stack *stack,
                                  bool free_parent)
 {
@@ -2371,7 +2383,7 @@ static int witness_stack_from_bytes(const unsigned char *bytes, struct wally_tx_
     const unsigned char *p = bytes;
     p += varint_from_bytes(p, &num_witnesses);
     if (num_witnesses) {
-        ret = wally_tx_witness_stack_init_alloc(num_witnesses, witness);
+        ret = tx_witness_stack_init_alloc(num_witnesses, num_witnesses, witness);
         if (ret != WALLY_OK)
             goto cleanup;
 
@@ -2485,8 +2497,8 @@ static int tx_from_bytes(const unsigned char *bytes, size_t bytes_len,
             p += varint_from_bytes(p, &num_witnesses);
             if (!num_witnesses)
                 continue;
-            ret = wally_tx_witness_stack_init_alloc(num_witnesses,
-                                                    &(*output)->inputs[i].witness);
+            ret = tx_witness_stack_init_alloc(num_witnesses, num_witnesses,
+                                              &(*output)->inputs[i].witness);
             if (ret != WALLY_OK)
                 goto fail;

Risk score

Why this scored 50/100

Our methodology →

Potential impact 12/30

Exploitability 8/25

Stealth signal 10/15

Affected reach 10/15

Confidence 7/10

Evidence quality 3/5

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.

What the developer wrote

What changed, and why it matters

Security signals we found

Evidence from the diff

Changed components

Why this scored 50/100

Community notes

Related watches

crypto: add ec_public_key_compress to produce a compressed pubkey

tests: add tests for parsing invalid der sigs

sign: disallow overlong der encodings and zero r or s values