Exponential time type checking on nested thresh inputs(algorithmic complexity DoS)

[Nuhiat-Arefin]

Summary

Type checking a Miniscript expression that nests thresh(...) appears to run in exponential time with respect to nesting depth.

The issue is that thresh visits each of its children twice during type checking, and the AST visitor does not memoize results. As a result, every enclosing thresh checks the entire inner subtree again.

A small valid input of about 6 KB at depth 24 takes about 5 seconds to type check, and each added layer roughly doubles the runtime. Parsing succeeds quickly; the cost is entirely in the correctness and type check pass.

Status

Confirmed by measurement: approximately 2× runtime per added layer.

Severity

A small valid input can cause unbounded CPU usage during type checking.

Reproduction

K1 = "032fa2104d6b38d11b0230010559879124e42ab8dfeff5ff29dc9cdadd4ecacc3f"
K2 = "024ce119c96e2fa357200b559b2f7dd5a5f02d5290aff74b03f3e471b273211c97"
K3 = "03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556"

def build(n):
    e = f"thresh(2,nd:and_v(v:older(1),v:after(1)),sc:pk_k({K3}))"

    for _ in range(n):
        e = (
            f"thresh(2,"
            f"or_i(c:and_v(vjc:pk_k({K1}),pk_h({K2})),{e}),"
            f"sc:pk_k({K3}))"
        )

    return e

# Parse and type check build(n) for n = 20, 22, 24

Measured results:

Layers	Input bytes	Type check time
20	5137	0.32 s
22	5639	1.44 s
24	6141	5.37 s

The runtime roughly doubles per added layer.

Projected from this growth:

Layers	Approximate impact
30	minutes
34	over an hour

For comparison on the same depth 24 input:

Implementation	Result
rust miniscript	0.01 s, rejects early on its resource or opcode bound
NBitcoin	0.35 s
tinyminiscript	5.37 s

Root cause

The AST visitor dispatches without caching. visit_ast_by_index computes the node on every call, and results are never memoized:

src/context.rs:21

In thresh type checking, each child is visited twice:

1. The type validation loop calls visit_ast_by_index(ctx, *x) for every child.
2. The property aggregation loop again calls visit_ast_by_index(ctx, *x) for every child.

Relevant locations:

src/type_checker.rs:627
src/type_checker.rs:674

Because there is no caching, each nested thresh(...) causes the entire inner subtree to be checked multiple times.

In effect:

thresh(...)
  checks child subtree twice

thresh(thresh(...))
  checks inner subtree four times

thresh(thresh(thresh(...)))
  checks inner subtree eight times

This produces exponential behavior, approximately O(2^depth).