descriptor_string: crash due to resource limits

[brunoerg]

Descriptor: "wsh(thresh(1,pk(xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U/840/94709400'),slnnnnnnnnnnnnnntvtvtvtvtvtvtvtvnn:0))".

Bitcoin Core successfully parses it but rust-miniscript returns the following error: "at least one spend path exceeds the resource limits". I noticed that rust-miniscript is throwing an "impossible satisfaction" error from:

fn check_local_consensus_validity<Pk: MiniscriptKey>(
    ms: &Miniscript<Pk, Self>,
) -> Result<(), ScriptContextError> {
    match ms.ext.ops.op_count() {
        None => Err(ScriptContextError::ImpossibleSatisfaction),
        Some(op_count) if op_count > MAX_OPS_PER_SCRIPT => {
            Err(ScriptContextError::MaxOpCountExceeded {
                actual: op_count,
                limit: MAX_OPS_PER_SCRIPT,
            })
        }
        _ => Ok(()),
    }
}

In the case of Bitcoin Core, CheckOpsLimit does not return false when it cannot get the maximum number of ops needed to satisfy the script because non-malleable satisfactions are guaranteed to be valid if ValidSatisfactions() (this function checks whether the node is valid at all, then check ops limit and stack size):

//! Check the ops limit of this script against the consensus limit.
bool CheckOpsLimit() const {
    if (IsTapscript(m_script_ctx)) return true;
    if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
    return true;
}

[apoelstra]

Innteresting. I'd be ok to just copy Core's behavior here. I'm not sure how to think about this in general. It seems to me that we should be able to compute op_count here.

[apoelstra]

cc @sanket1729 if you wanna try to think through this.

[sanket1729]

Hmm, I cannot reproduce this on my end. I tested this with latest master (13.0.0) and 12.2.0 (the version used in bitcoinfuzz)

    #[test]
    fn test_btc_fuzz_issue_73() {
        let secp = secp256k1::Secp256k1::new();
        let desc = Descriptor::parse_descriptor(&secp, "wsh(thresh(1,pk(xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U/840/94709400'),slnnnnnnnnnnnnnntvtvtvtvtvtvtvtvnn:0))").unwrap();
        dbg!(&desc);
        match &desc.0 {
            Descriptor::Bare(bare) => todo!(),
            Descriptor::Pkh(pkh) => todo!(),
            Descriptor::Wpkh(wpkh) => todo!(),
            Descriptor::Sh(sh) => todo!(),
            Descriptor::Wsh(wsh) => {
                match wsh.as_inner() {
                    WshInner::SortedMulti(sorted_multi_vec) => todo!(),
                    WshInner::Ms(miniscript) => {
                        dbg!(&miniscript.ext);
                    },
                }
            },
            Descriptor::Tr(tr) => todo!(),
        }
    }

The descriptor successfully parses and computes the OpCounts correctly.

[src/descriptor/mod.rs:2071:25] &miniscript.ext = ExtData {
    pk_cost: 76,
    has_free_verify: true,
    ops: OpLimits {
        count: 31,
        sat: None,
        nsat: Some(
            0,
        ),
    },
    stack_elem_count_sat: None,
    stack_elem_count_dissat: Some(
        2,
    ),
    max_sat_size: None,
    max_dissat_size: Some(
        (
            3,
            2,
        ),
    ),
    timelock_info: TimelockInfo {
        csv_with_height: false,
        csv_with_time: false,
        cltv_with_height: false,
        cltv_with_time: false,
        contains_combination: false,
    },
    exec_stack_elem_count_sat: None,
    exec_stack_elem_count_dissat: Some(
        1,
    ),
    tree_height: 35,
}

[brunoerg]

@sanket1729 I think you need to call sanity_check after parsing the descriptor.

[sanket1729]

Ah, nice. I can reproduce it. Looking into it

[sanket1729]

@apoelstra, rust-miniscript differs from Bitcoin Core by analyzing if script elements are satisfiable. In this case 0 (OP_FALSE) in second thresh branch is not sensible as it's inherently unsatisfiable, so our implementation fails these cases for sanity checks.

But I think this uncovered another issue in rust-miniscript. Descriptor::from_str and Descriptor::parse_descriptor don't do these sanity_checks on the top levels. But Miniscript::from_str does

    #[test]
    fn test_2() {
        let desc = Descriptor::<String>::from_str("wsh(thresh(1,pk(A),s:pk(B)))").unwrap();
        let desc = Descriptor::<String>::from_str("wsh(thresh(1,pk(A),s:pk(A)))").unwrap(); // This should also ERR
        
        // But miniscript APIs are fine.
        let ms = Miniscript::<String, Segwitv0>::from_str("thresh(1,pk(A),s:pk(B))").unwrap();
        let ms = Miniscript::<String, Segwitv0>::from_str("thresh(1,pk(A),s:pk(A))").expect_err("This is not a valid miniscript");
    }

[brunoerg]

@apoelstra, rust-miniscript differs from Bitcoin Core by analyzing if script elements are satisfiable. In this case 0 (OP_FALSE) in second thresh branch is not sensible as it's inherently unsatisfiable, so our implementation fails these cases for sanity checks.

I do not see why Bitcoin Core does not fail for this case. Maybe CheckOpsLimit should return false when it cannot get the maximum number of ops needed to satisfy this script? cc: @darosior

diff --git a/src/script/miniscript.h b/src/script/miniscript.h
index 75f978457c..0ec60e286e 100644
--- a/src/script/miniscript.h
+++ b/src/script/miniscript.h
@@ -1492,7 +1492,7 @@ public:
     bool CheckOpsLimit() const {
         if (IsTapscript(m_script_ctx)) return true;
         if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
-        return true;
+        return false;
     }

[apoelstra]

Oh, yeah, this script is actually unspendable isn't it? I missed that on first reading.

But thresh requires you either satisfy or dissatisfy every child, and the nnn...nnn:0 thing cannot be satisfied (since it's 0) or dissatisfied (due to resource limits).

I guess what's happening is: in Core it interprets "cannot be satisfied" as "within resource limits", and its separate satisfiability check is broken?

[sanket1729]

I guess what's happening is: in Core it interprets "cannot be satisfied" as "within resource limits", and its separate satisfiability check is broken?

I don't think core has a notion of 'cannot be satisfied.' The branch is within resource limits, the total opcodes are 31 (< 200), but it cannot be satisfied. Our error reporting conflates the 'unsatisfied sub-child in thresh' with resource limit checks. This is because of how opcode counting is implemented using the Option, where we store 0 as None and propagate it upwards the tree.

        match ms.ext.ops.op_count() {
            None => Err(ScriptContextError::MaxOpCountExceeded), // Change this different here that shows branch is not satisfiable.
            Some(op_count) if op_count > MAX_OPS_PER_SCRIPT => {
                Err(ScriptContextError::MaxOpCountExceeded)
            }
            _ => Ok(()),
        }

But thresh requires you either satisfy or dissatisfy every child

In rust-miniscript, sanity checks we require both. Maybe this is the bug!

[darosior]

Oh, yeah, this script is actually unspendable isn't it? I missed that on first reading.

It is spendable, by providing a signature for the public key and a 1 to get the l: to just push 0.

Maybe CheckOpsLimit should return false when it cannot get the maximum number of ops needed to satisfy this script? cc: @darosior

No, i don't think an unsatisfiable fragment should be considered as bumping against the ops limit.

[brunoerg]

No, i don't think an unsatisfiable fragment should be considered as bumping against the ops limit.

Make sense.

[apoelstra]

Honestly I can't figure out what is going on in our op-counting function for thresh. I think it may be incorrectly saying there is no satisfaction cost for this. But this is such a maze of Option maps and tuples, which has changed significantly over the years, that I can't see what's wrong with it.

[sanket1729]

@apoelstra, the core issue is that rust-miniscript won't allow thresh(1,pk(A),s:0), but bitcoin core will allow this. We expect all thresh sub children to be satisfiable in sanity_checks, but core does not.

The Opcounts for satisfaction returns None resulting in this error. This should have been some other error message.