#002 Stack Element Size Limit

Problem: SHRINCS has signatures of up to 5,777 bytes, while the current Tapscript stack-element size limit is only 520 bytes per element.

Currently, we have two main options:

  • Chunk signatures into multiple elements of at most 520 bytes.
  • Increase the stack-element size limit to 6,000 bytes.

Let's see the pros and cons of each option.

I — Chunking Idea

We could include the number of signature chunks in the witness, provided by the spender.

For example:

scriptPubKey:

OP_1 <Q>

Tapscript:

<SHRINCS_pubkey> OP_CHECKSIG

Witness:

<chunk12> <chunk11> ... <chunk1> <12> <tapscript> <control_block>

Under this hypothetical design, OP_CHECKSIG would pop the count, then pop that number of chunks, concatenate them, and verify the reconstructed signature.

Problems

1. Static Script Analysis

With a dynamic signature-chunk count, we wouldn't know exactly how many elements OP_CHECKSIG would consume by looking only at the Tapscript. This makes certain kinds of static Script analysis harder to reason about.

One idea to fix this is to always use a fixed count of 12 chunks. For smaller signatures, we could fill the remaining positions with empty chunks.

2. Extra Witness Overhead

We need to account for the extra witness overhead required to represent the length of each signature chunk.

  • For a stateless signature of 5,777 bytes: We need 12 chunks (11 chunks of 520 bytes and a final chunk of 57 bytes).

The first 11 chunks need 3 bytes each for their CompactSize length prefixes, while the last chunk needs 1 byte.

Total prefix overhead = 3 × 11 + 1 = 34 bytes.

But a single signature element already needs a 3-byte CompactSize length prefix.

So the additional overhead is 34 − 3 = 31 bytes.

If we also include a separate chunk-count element, that's another 2 bytes.

  • For stateful signatures: …

3. Off-chain Verification

Wallets, PSBT finalizers, Lightning implementations, and other software handling these signatures would need to account for the new chunking rules when constructing or interpreting the witness.

4. Complex Edge Cases

Someone might split a signature into chunks smaller than 520 bytes.

We need to decide how to handle different chunk representations of the same signature, as well as malformed counts and empty signatures.

5. Consensus Entanglement

Bitcoin Script should treat signatures as black boxes. It shouldn't need to understand their internal structure.

Suppose we introduce a new signature scheme. The interpreter might then need additional algorithm-specific logic to determine how many chunks to consume.

6. Untrusted Data

The spender might specify an incorrect chunk count, causing the interpreter to consume stack elements that weren't intended to be part of the signature.

However, this isn't entirely new to Bitcoin. We already let the spender provide witness data.

The fixed-12-chunk approach would avoid this particular problem, since we wouldn't let the spender specify the count.

II — Relaxing the 520-Byte Limit

Increasing the stack-element size limit to 6,000 bytes also introduces some tradeoffs.

1. Memory DoS

An attacker could supply a 6,000-byte witness element and repeatedly execute:

OP_DUP
OP_DUP
OP_DUP
OP_DUP
...

With the 1,000-element combined stack limit, this could consume approximately 6 MB of raw element data if every duplicate allocates a separate copy.

So the attacker only provides the 6,000-byte element once, but causes nodes to allocate many copies of it.

This creates an imbalance: cheap for the attacker to construct, but relatively expensive for nodes to execute.

Note: PR #36721 tries to solve this using shared references. It prevents duplication from copying the underlying bytes, but doesn't eliminate the memory cost of distinct large elements.

The difference is that, in the latter case, the attacker must pay for supplying those distinct bytes, subject to the transaction and block weight limits.

2. CPU DoS

Even after fixing the memory problem, an attacker could still force nodes to perform expensive hash operations.

For example, starting with a 6,000-byte stack element:

OP_DUP
OP_RIPEMD160
OP_DROP

OP_DUP
OP_RIPEMD160
OP_DROP

OP_DUP
OP_RIPEMD160
OP_DROP

... repeat many times

The attacker supplies one 6,000-byte element and repeatedly forces nodes to hash it.

RIPEMD-160 processes input in 64-byte blocks.

For a 6,000-byte input, it requires 94 compression operations.

If repeated 1,000 times:

1,000 × 94 = 94,000 compression operations

A follow-up to PR #36721 is being developed to address this using a hash cache.

3. Hybrid Attack

Combining both memory and CPU DoS attacks.

III — Other Solutions Proposed

1. Restrict DUP and Hash Opcodes

We could restrict duplication and hashing opcodes from operating on elements larger than 520 bytes.

However, we don't know whether certain legitimate applications need these operations on larger signatures.

2. Hash Cache

We could cache hash results instead of recomputing them, but this introduces two possible design choices:

  • Fixed-size cache: Evict older entries, but an attacker could cycle through enough elements to force repeated hash calculations.
  • Cache without eviction: Avoids eviction, but requires more memory to retain cached results and their associated elements.
← All learning logs