Concrete-policy compiler entrypoints can abort on large n-of-n threshold lowering instead of returning a normal error

[Nuhiat-Arefin]

Summary

rust-miniscript's public concrete-policy compiler entrypoints can overflow the Rust stack and abort the process on a large all-key threshold policy, instead of returning a normal compiler error.

I verified this locally on commit:

6131095c8ee99ba9a91ee004b1d387dd8418766a

The affected public entrypoints I confirmed locally are:

• Policy::compile::<Segwitv0>()
• Policy::compile::<Tap>()
• Policy::compile_tr(...)
• Policy::compile_tr_native(...)
• Policy::compile_tr_private_experimental(...)

The reproducing policy is manually constructed with the shape:

or(99@pk(I),1@thresh(n,pk(K1),...,pk(Kn)))

with n = 999.

Importantly, the input policy is shallow:

• top-level Or
• one Key branch
• one flat Thresh(n, ...) branch

In other words, this is not a deeply nested caller-supplied policy tree. The fatal recursion depth appears to be created during compiler lowering.

Minimal repro

use std::sync::Arc;

use miniscript::bitcoin::secp256k1::{PublicKey as SecpPublicKey, Secp256k1, SecretKey};
use miniscript::bitcoin::PublicKey;
use miniscript::policy::concrete::Policy;
use miniscript::{Segwitv0, Threshold};

fn mk_key(secp: &Secp256k1<miniscript::bitcoin::secp256k1::All>, n: u32) -> PublicKey {
    let mut bytes = [0u8; 32];
    bytes[28..].copy_from_slice(&n.to_be_bytes());

    let sk = SecretKey::from_slice(&bytes).unwrap();
    let pk = SecpPublicKey::from_secret_key(secp, &sk);

    PublicKey::new(pk)
}

fn main() {
    let secp = Secp256k1::new();
    let keys: Vec<PublicKey> = (1..=1000).map(|n| mk_key(&secp, n)).collect();

    let thresh_items: Vec<Arc<Policy<PublicKey>>> = keys[1..]
        .iter()
        .cloned()
        .map(Policy::Key)
        .map(Arc::new)
        .collect();

    let policy = Policy::Or(vec![
        (99, Arc::new(Policy::Key(keys[0].clone()))),
        (
            1,
            Arc::new(Policy::Thresh(
                Threshold::new(999, thresh_items).unwrap(),
            )),
        ),
    ]);

    let _ = policy.compile::<Segwitv0>();
}

Observed behavior

Locally, at n = 999, all of the public compiler entrypoints listed above abort with:

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

This is not simply “every large threshold fails.”

I observed the following smaller cases returning normal results:

• at n = 100, compile::<Segwitv0>() returned Err(LimitsExceeded)
• at n = 100, compile::<Tap>() succeeded
• at n = 100, compile_tr_private_experimental(...) succeeded
• at n = 250, compile_tr_private_experimental(...) still succeeded

So there appears to be a concrete scaling region where normal compiler results turn into a raw process abort.

Why this seems to happen

The issue appears to be in the n-of-n threshold lowering path.

Relevant local source points:

• src/primitives/threshold.rs, around line 103: is_and() means k == inner.len()
• src/policy/compiler.rs, around line 1056: that case folds the flat threshold into a left-nested binary Concrete::And chain
• src/policy/compiler.rs, around line 841: Concrete::And compilation recurses into both children

The relevant lowering appears to be:

if thresh.is_and() {
    let mut it = thresh.iter();
    let mut policy = it.next().expect("No sub policy in thresh() ?").clone();
    policy = it.fold(policy, |acc, pol| Concrete::And(vec![acc, pol.clone()]).into());

    ret = best_compilations(policy_cache, policy.as_ref(), sat_prob, dissat_prob)?;
}

A flat 999-of-999 threshold is therefore lowered into an approximately 998-deep left-leaning binary And tree, and the compiler then recursively processes that manufactured depth.

That distinction matters: the caller supplies width, but the compiler creates the fatal depth.

arser/depth hardening work

Freshness / overlap note

I performed narrow GitHub searches for an obvious exact existing issue or PR covering this specific shallow-wide n-of-n threshold lowering case and did not find a clear duplicate.

The closest prior issue I found was rust-bitcoin/rust-miniscript#41, but that appears to concern deeply nested caller-supplied concrete-policy input. This report concerns a shallow input where the compiler transform itself creates the deep recursive structure.