consensus_encoding: implement batched allocation for WitnessDecoder by jrakibi · Pull Request #5298 · rust-bitcoin/rust-bitcoin

jrakibi · 2025-11-17T10:52:54Z

Currently an attacker can force a 32 MB memory allocation by only providing 10 bytes as inputs (see test case that proves that in #5239 (comment))

With the current approach we reduce this attack surface to ~17 MB.

Attack vector (test case inputs):

[0xFE, 0x00, 0x09, 0x3D, 0x00] = 4_000_000 (witness count)
[0xFE, 0x00, 0x09, 0x3D, 0x00] = 4_000_000 (1st element length)

10 bytes of input will trigger the allocation below

Old approach with resize_if_needed (32 MB allocation):

Index space = 16 MB (4_000_000 witness elements × 4 bytes)
Initial buffer = 16 MB + 128 bytes
When the 4 MB element length is decoded, resize_if_needed doubles the buffer
Because required_len = 16 MB + 128 + 4 MB = 20 MB + 128 bytes, it doubles from 16 MB to 32 MB
Total allocation = 32 MB

New approach with reserve_batch (~17 MB allocation):

Index space = 16 MB
Initial buffer = 16 MB + 128 bytes
When a 4 MB element length is decoded, reserve_batch allocates in 1 MB batches
Total allocation = 16 MB + 128 bytes + 1 MB = 17_000_128 bytes

The current approach automatically addresses the concerns raised in #5258 and #5239 (comment)

apoelstra · 2025-11-20T14:45:44Z

cc #5177

apoelstra · 2025-11-20T14:50:48Z

In ea980a5:

Should be a separate PR but at some point we should also stop 0-allocating here and use ptr::write or whatever to write into uninitialized memory. Or maybe we can use push and extend rather than copy_from_slice , which would avoid the need for unsafe code.

apoelstra

ACK ea980a5; successfully ran local tests

nyonson · 2025-11-20T23:46:27Z

primitives/src/witness.rs

+            // Allocate space for the index and buffer. For DoS prevention,
+            // we allocate index space incrementally (not all upfront).


I think I might be missin something, the docs here mention that the index space is allocated incrementally, but where does that happen?

EDIT: But I guess it doesn't matter since the cursor is initialized to the "end" of the index space.

we are actually allocating incrementally the index space too
if we claim to have 16Mb index space, we initially allocate only 1MB.
As we try to write data at the cursor position (16MB), reserve_batch() grows the buffer toward the cursor in 1MB batches

tcharding · 2025-11-21T01:56:14Z

primitives/src/witness.rs

+            let initial_elements = witness_elements.min(max_initial_elements);
+            let initial_index_space = initial_elements * 4;
+
            self.cursor = witness_index_space;


Why is the cursor, the write position, set to the witness_index_space? (Also this can be greater than content.len() which is semantically odd for a 'write position'.)

(I'm aware that its not part of this PR but it effects it because this PR uses self.cursor below.)

Can we have this please

// Initially the index space is at the front of the buffer then we rotate left in `end`. self.cursor = witness_index_space`

tcharding · 2025-11-21T01:58:11Z

primitives/src/witness.rs


-                // Store the element position in the index.
+                let encoded_size = compact_size::encoded_size(element_length);
+                let required_len = self.cursor + encoded_size;


Here self.cursor could be outside of the content buffer, again even if the math works its odd and hard to reason about.

tcharding · 2025-11-21T02:05:18Z

primitives/src/witness.rs

+                let actual_len = self.reserve_batch(required_len);
+
+                if actual_len < required_len {
+                    return Ok(true);


If this returns I believe we have read the element size but not written it into content.

I think you can ignore this ...

Oh, yes this is a real bug.

tcharding · 2025-11-21T02:06:09Z

primitives/src/witness.rs

+                    return Ok(true);
+                }
                let position_after_rotation = self.cursor - witness_index_space;
                encode_cursor(&mut self.content, 0, self.element_idx, position_after_rotation);


Either I'm blind or this encoders the element_idx at the start of context not at the start of the index section.

Oh shit, I only just worked out that we rotate left in end - face palm.

tcharding · 2025-11-21T02:29:19Z

Phew, I thought I could not read code but turns out I can.

I believe this is buggy, as this output shows. I added a bunch of println statements and commented out the [buggy] length check that was allowing the test_dos_attack test to not panic

                 // Among other things if this returns we loose the data read so far.
                // if actual_len < required_len {
                //     return Ok(true);
                // }

running 1 test
input bytes: [254, 0, 9, 61, 0, 254, 0, 9, 61, 0]
cursor: 16000000
content len: 1000128
before reserve content len: 1000128
after reserve content len: 2000128
actual len 2000128 required_len 16000005
decoded content [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
input bytes: []
cursor: 16000000
content len: 2000128

thread 'witness::test::test_dos_attack' (612268) panicked at primitives/src/witness.rs:495:29:
range start index 16000000 out of range for slice of length 2000128
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
test witness::test::test_dos_attack ... FAILED

failures:

failures:
    witness::test::test_dos_attack

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 113 filtered out; finished in 0.02s

tcharding · 2025-11-21T02:35:30Z

So I guess one of two things:

Either the code is too complex for me to reason about, in which case we can add a bunch of tests that prove its not buggy
Having the cursor write position set to be greater than the content size should not happen (either because its a bug or because it makes the code too hard to reason about)

And yes, if git blaming you'll see that I introduced this code originally into primitives. When I copied moved the original code I did not grok it I just copied it as it was - 100% my bad. In my defence the original code is only 60 lines, it has grown considerably in complexity since we added the new encoding traits. git co c1eccfde25~1

EDIT: I went away and came back fresh. Looked at the code on master then again at this PR. I believe the crux of the issue is that when reading the current code it is really hard to know how big the content buffer is at any stage in the code and where the cursor points to and what it even is if it points outside of the content buffer.

apoelstra · 2025-11-21T17:29:11Z

Can you write a unit test that triggers this?

tcharding · 2025-11-21T21:31:24Z

I knew someone was going to say that ... I'll hack it up.

jrakibi · 2025-11-22T12:35:05Z

I agree the DoS protection we added for index space allocation makes the code a bit confusing to reason about, but I don't think the code is buggy.

The confusing part is that we don’t consume/write anything until the buffer has grown to reach the cursor position.
so the check you mentioned:

if actual_len < required_len {
    return Ok(true);
}

is importatnt! it triggers the incremental allocation for index space and prevents us from writing beyond the buffer

For example in the test case:

Call 1: cursor=16MB, buffer=1MB → can't write yet → allocate
Call 2: cursor=16MB, buffer=2MB → can't write yet → allocate
...
Call 16: cursor=16MB, buffer=16MB → can write → process data

without the check, we'd try to write at position cursor (16MB), but content.len() is only 2MB (which triggers the issue you mentioned before)

jrakibi · 2025-11-22T12:38:50Z

If this is too confusing, I think we can remove the batched allocation for the index space and only keep it for the data area.
With that, we’ll always have cursor <= content.len()

An attacker can still force around 20 MB of free allocation tho, but maybe maybe that’s fine !!

apoelstra · 2025-11-22T15:59:18Z

Yeah, 20MB is a reduction from the current "attack", which is already below the threshold that I'd consider to be a security concern. We can always try again to improve it later.

nyonson · 2025-11-23T01:17:12Z

Just tossing in my 2 cents, I'd prefer the simpler approach for now cause I too got tripped on the cursor-position-index-allocation interaction.

jrakibi · 2025-11-23T19:18:25Z

Makes sense, I’ll remove the index space allocation once I’m back on my laptop ..

jrakibi · 2025-11-25T00:36:08Z

I’ll remove the index space allocation

done

nyonson

Reviewed c15d5ae

Was definitely able to wrap my head around it faster, but wonder if possible to drop a bit more code.

nyonson · 2025-11-25T23:13:27Z

primitives/src/witness.rs

                let encoded_size = compact_size::encoded_size(element_length);
                let required_len = self.cursor + encoded_size + element_length;
-                self.resize_if_needed(required_len);
+                self.reserve_batch(required_len);


I found it a little confusing how the return value is ignored here, while checked in the other branch. Makes sense that 9 bytes will always be available at this point. But wondering if reserve_batch needs to return a value if it isn't going to be consistently used cause made me feel like I was missing something.

we need the return value in the first branch because reserve_batch may allocate less than what we request.
For the second branch, it’s guaranteed we already have enough capacity for encoded_size (<= 9 bytes)

True, but I think I'd prefer reserve_batch to return nothing and for the first branch to just check content length directly. But don't feel too strongly about it.

nyonson · 2025-11-25T23:17:53Z

primitives/src/witness.rs

-                // Ensure we have enough space.
-                let required_len = self.cursor + copy_len;
-                self.resize_if_needed(required_len);
+                if can_copy == 0 {


Is this short-circuit necessary? Seems like it could be removed and just flow through. Also having a tough time thinkin up the scenario where it is triggered.

you're right fixed in b9f9098

tcharding · 2025-11-26T22:23:46Z

@jrakibi I appreciate your effort but I'm hesitant on this PR. To see if I can be convinced, can we have the description improved to justify this please. Something like "currently an attacker can cause memory to be allocated like ... with this applied the attack surface is reduced to ...".

To justify my hesitation: I already spent more time than I want to trying to understand the additional complexity. I don't like the idea of adding complexity that we have to carry for ever, along with the risk of any bugs, unless there is justification. And also I don't feel like putting in the time/effort to review deeply again without the justification. Thanks mate.

FTR my position can be veto'd by @apoelstra

jrakibi · 2025-11-26T23:42:03Z

Thanks, my fault, I should have added a detailed description to explain this better.

can we have the description improved to justify this please.

I’ve updated the description now.
tldr: we reduce the attack surface from 32 MB free allocation in the old code to ~17 MB (more details in the description).

I don't like the idea of adding complexity that we have to carry for ever

If this still introduces too much complexity, I’m happy to keep the 32 MB free allocation. I think @apoelstra is also okay with that from what I understand here: #5239 (comment) and #5298 (comment) (maybe correct me if I’m wrong)

apoelstra · 2025-11-27T21:24:15Z

I'd prefer to reduce it and I don't mind the complexity (which is not API-visible so we don't have to "carry it forever"). But this might take a while to review, and I do want two ACKs on it before merging.

tcharding · 2025-11-27T21:27:11Z

which is not API-visible so we don't have to "carry it forever"

Maybe I was being hypbolic, I meant readers of the code have to read it for ever (while it exists). But fair point about being an internal complexity only.

tcharding · 2025-11-27T21:27:57Z

But this might take a while to review, and I do want two ACKs on it before merging.

Sweet, if there is no rush I can definitely review when I have the bandwidth available.

apoelstra · 2025-11-27T21:31:59Z

Yeah, I'd say no rush. @jrakibi's summary of my view -- that the 32MB allocation is small enough that it shouldn't count as an attack that we urgently need to deal with. In the "10 bytes to get 32 MB" example the allocation is dropped because parsing fails, so it is very hard to amplify this.

apoelstra

ACK b9f9098; successfully ran local tests

tcharding · 2026-01-16T02:53:04Z

Needs rebase please

jrakibi · 2026-01-16T03:11:17Z

rebased

jrakibi · 2026-01-16T03:33:35Z

Cargo mutants check is failing, will take a look at this later today

Add batched allocation for witness decoder (data area). we allocate incrementally in ~1 MB batches The current approach automatically addresses the concerns raised in rust-bitcoin#5258 and rust-bitcoin#5239 (comment) we aslo add `reserve_batch` to Mutants exclusion list Mutation testing in WitnessDecoder::reserve_batch changes the buffer allocation logic and they cause infinite loop during decoding

jrakibi · 2026-01-17T18:08:39Z

Fixed, 9bf1522 adds reserve_batch to the mutants exclusion list. these mutations cause infinite loop during decoding

tcharding

ACK 9bf1522

apoelstra

ACK 9bf1522; successfully ran local tests

github-actions bot added the C-primitives label Nov 17, 2025

jrakibi mentioned this pull request Nov 17, 2025

consensus_encoding: implement batched allocation for vector decoders #5177

Merged

apoelstra previously approved these changes Nov 20, 2025

View reviewed changes

nyonson reviewed Nov 20, 2025

View reviewed changes

tcharding mentioned this pull request Nov 21, 2025

Release tracking PR: bitcoin 0.33.0-beta.0 #5169

Merged

tcharding reviewed Nov 21, 2025

View reviewed changes

jrakibi dismissed apoelstra’s stale review via b265867 November 24, 2025 08:55

jrakibi force-pushed the 17-11-witness-allocation branch 2 times, most recently from b265867 to c15d5ae Compare November 24, 2025 09:00

nyonson reviewed Nov 25, 2025

View reviewed changes

jrakibi force-pushed the 17-11-witness-allocation branch from c15d5ae to b9f9098 Compare November 26, 2025 09:54

jrakibi mentioned this pull request Nov 27, 2025

Add decode test for reserve capacity #5335

Merged

apoelstra previously approved these changes Nov 28, 2025

View reviewed changes

jrakibi dismissed apoelstra’s stale review via bd68f30 January 16, 2026 03:09

jrakibi force-pushed the 17-11-witness-allocation branch from b9f9098 to bd68f30 Compare January 16, 2026 03:09

jrakibi force-pushed the 17-11-witness-allocation branch from 6bd8885 to 9bf1522 Compare January 17, 2026 18:02

tcharding approved these changes Jan 18, 2026

View reviewed changes

apoelstra approved these changes Jan 24, 2026

View reviewed changes

apoelstra merged commit 02c01d3 into rust-bitcoin:master Jan 24, 2026
27 checks passed

jrakibi mentioned this pull request Jan 25, 2026

primitives: further tighten memory allocations in witness decoder #5258

Closed

		// Allocate space for the index and buffer. For DoS prevention,
		// we allocate index space incrementally (not all upfront).

Conversation

jrakibi commented Nov 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Attack vector (test case inputs):

Uh oh!

apoelstra commented Nov 20, 2025

Uh oh!

apoelstra commented Nov 20, 2025

Uh oh!

apoelstra left a comment

Choose a reason for hiding this comment

Uh oh!

nyonson Nov 20, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tcharding commented Nov 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tcharding commented Nov 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

apoelstra commented Nov 21, 2025

Uh oh!

tcharding commented Nov 21, 2025

Uh oh!

jrakibi commented Nov 22, 2025

Uh oh!

jrakibi commented Nov 22, 2025

Uh oh!

apoelstra commented Nov 22, 2025

Uh oh!

nyonson commented Nov 23, 2025

Uh oh!

jrakibi commented Nov 23, 2025

Uh oh!

jrakibi commented Nov 25, 2025

Uh oh!

nyonson left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tcharding commented Nov 26, 2025

Uh oh!

jrakibi commented Nov 26, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

apoelstra commented Nov 27, 2025

Uh oh!

tcharding commented Nov 27, 2025

Uh oh!

jrakibi commented Nov 17, 2025 •

edited

Loading

nyonson Nov 20, 2025 •

edited

Loading

tcharding commented Nov 21, 2025 •

edited

Loading

tcharding commented Nov 21, 2025 •

edited

Loading

jrakibi commented Nov 26, 2025 •

edited

Loading