Underpruning can produce anti-DOS error from elementsd

[schoen]

Project version

0.7.1

Project

compiler

What happened?

Some SimplicityHL programs, when redeeming, can produce this error from elementsd:

    Error: Broadcast failed with HTTP 400 for http://127.0.0.1:42415/tx: sendrawtransaction RPC error -26: non-mandatory-script-verify-flag (Anti-DOS check failed)

This "anti-DOS check" is a rule inside elementsd about whether a submitted Simplicity program was sufficiently pruned. The error asserts that a submitted program was not sufficiently pruned.

I worked on this error a lot with an AI, and it has a whole theory about why the pruning may be inadequate in some cases, but I didn't fully understand the theory as it relates a lot to SimplicityHL internals that I wasn't familiar with, and I don't really know for sure that it's correct.

However, the main concrete findings from the AI were

(1) confirming that some specific programs have non-idempotent pruning (if you prune twice, you get a smaller output than if you only prune once). However, it is not 100% clear that pruning is meant to be idempotent in all cases, as there is a comment discouraging people from attempting to re-prune a pruned program. Therefore, this phenomenon can be a symptom of the problem but not necessarily conclusive proof of a bug in its own right.

(2) lots of reproduction cases, including proof via a patch to Simplex that lets you request to prune a program twice. For the reproduction cases, the transaction with the normal singly-pruned program would fail with the anti-DOS error, while the double-pruned program would succeed. The AI managed to shrink the reproduction case a ton, with a lot of prodding, so that we finally have a concise reproduction (below).

The change to Simplex to make it allow you to double-prune programs during redemption is like this:

diff --git a/crates/sdk/src/program/core.rs b/crates/sdk/src/program/core.rs
index d683f35..1cad6c4 100644
--- a/crates/sdk/src/program/core.rs
+++ b/crates/sdk/src/program/core.rs
@@ -162,7 +162,23 @@ impl ProgramTrait for Program {
 
         let env = self.get_env(pst, input_index, network)?;
 
-        let pruned = satisfied.redeem().prune_with_tracker(&env, &mut tracker)?;
+        let mut pruned = satisfied.redeem().prune_with_tracker(&env, &mut tracker)?;
+
+        // EXPERIMENTAL: opt-in re-pruning to test whether a single `prune()`
+        // call is leaving the submitted bytecode incompletely pruned (see
+        // the chess.simf Anti-DOS investigation). `prune()`'s own doc
+        // comment warns that pruning an already-pruned program "is not
+        // sound" in general, so this is gated behind an env var rather than
+        // being unconditional -- it's here to let us test the real effect
+        // against a real node, not as a blessed fix.
+        if std::env::var("SMPLX_DOUBLE_PRUNE").is_ok() {
+            // Self-verifying: prints unconditionally when this branch fires,
+            // so it's visible whether the env var actually reached this
+            // process at all -- see SETUP_v10.md's propagation-chain caveat.
+            // No need to trust that it did; this line settles it.
+            eprintln!("[SMPLX_DOUBLE_PRUNE active] re-pruning before serialization");
+            pruned = pruned.prune(&env)?;
+        }
 
         if GlobalConfig::is_max_verbose() {
             ProgramLogger::buffer_cost_log(&pruned);

... just for convenience on reproduction here.

The Simplex test to reproduce the error:

//! Run once WITHOUT `SMPLX_DOUBLE_PRUNE` set: expect this to fail with
//! "Anti-DOS check failed".
//! Run again WITH `SMPLX_DOUBLE_PRUNE=1`: expect it to pass.

use simplex::simplicityhl::elements::Script;
use simplex::simplicityhl::{Arguments, WitnessValues};
use simplex::program::{ArgumentsTrait, Program, WitnessTrait};
use simplex::transaction::{FinalTransaction, PartialInput, ProgramInput, RequiredSignature};

/// A witness with no declared values at all -- for `minimal_repro_anti_dos_synthetic`
/// below.
#[derive(Clone)]
struct NoWitness;

impl WitnessTrait for NoWitness {
    fn build_witness(&self) -> WitnessValues {
        WitnessValues::default()
    }
}

#[derive(Clone)]
struct NoArguments;

impl ArgumentsTrait for NoArguments {
    fn build_arguments(&self) -> Arguments {
        Arguments::default()
    }
}

/// Even smaller than the prior repro: built directly from the four
/// necessary ingredients isolated by bisection (a 2-level nested match,
/// the *same* function called twice, output-feeds-input chaining,
/// the threaded value `Option`-wrapped for early exit).
const SYNTHETIC_SOURCE: &str = r#"
fn nested(a: bool, b: bool) -> bool {
    match a {
        false => match b {
            false => false,
            true => true,
        },
        true => false,
    }
}

fn step(cur: Option<bool>) -> (bool, Option<bool>) {
    match cur {
        None => (false, None),
        Some(x: bool) => match nested(x, true) {
            false => (false, Some(true)),
            true => (true, None),
        },
    }
}

fn main() {
    let (f0, n0): (bool, Option<bool>) = step(Some(false));
    let (f1, _n1): (bool, Option<bool>) = step(n0);
    let hit: bool = match f0 {
        true => f0,
        false => f1,
    };
    assert!(hit);
}
"#;

fn get_synthetic_program(context: &simplex::TestContext) -> (Program, Script) {
    let signer = context.get_default_signer();
    let program =
        Program::new(SYNTHETIC_SOURCE, Box::new(NoArguments)).with_taproot_pubkey(signer.get_schnorr_public_key());
    let script = program.get_script_pubkey(context.get_network());
    (program, script)
}

#[simplex::test]
fn most_minimal_repro_anti_dos(context: simplex::TestContext) -> anyhow::Result<()> {
    let signer = context.get_default_signer();
    let provider = context.get_default_provider();

    let (program, script) = get_synthetic_program(&context);

    let tx_receipt = signer.send(script.clone(), 50_000)?;
    tx_receipt.wait()?;

    let utxos = provider.fetch_scripthash_utxos(&script)?;

    let mut ft = FinalTransaction::new();
    ft.add_program_input(
        PartialInput::new(utxos[0].clone()),
        ProgramInput::new(Box::new(program.clone()), Box::new(NoWitness)),
        RequiredSignature::None,
    );

    signer.broadcast(&ft)?;
    Ok(())
}

Indeed, when I run this with SMPLX_DOUBLE_PRUNE=1 (building Simplex with the patch to add that feature), the test passes; without this (with a normal Simplex environment), the test fails with

    Error: Broadcast failed with HTTP 400 for http://127.0.0.1:35821/tx: sendrawtransaction RPC error -26: non-mandatory-script-verify-flag (Anti-DOS check failed)

As a further note, I tried compiling this same program via simc and submitted transactions with hal-simplicity; that redeem process completed successfully, which suggests to me that the pruning is more ambitious and/or more-correct in that workflow. I haven't tried comparing the actual pruned programs, but, for whatever it's worth, the final two steps in that workflow were

hal-simplicity simplicity pset finalize cHNldP8BAgQCAAAAAQMEAAAAAAEEAQEBBQECAfsEAgAAAAABAU4BSZqBhUX2uuOfwDtjfypOHmTlkMrBvDpvbXGqRENlTBQBAAAAAAABhqAAIlEg8KGnifeumSOzMHWfmyqg74XdebWoyhvFqMSHzNAgDhIBBwABCAEAAQ4gI011BwkrXcsQqhBPwNht4noDJwnEh/rMfoGj8loM4P8BDwQAAAAAARAE/////yIVv1CSm3TBoElUt4tLYDXpel4HiloPKOyW1Ue/7prOgDrAIQZD4MqcrvHpKNNbN1G/gD45Rx5lC+WtAhsNYIwKr5hIvgEXIFCSm3TBoElUt4tLYDXpel4HiloPKOyW1Ue/7prOgDrAARggrXQ7b4tvx7nlj0+MPVS77uNziA9nrxXbCZnk+hz/e6wAAQMIPIYBAAAAAAAH/ARwc2V0AiBJmoGFRfa645/AO2N/Kk4eZOWQysG8Om9tcapEQ2VMFAEEFgAUtYwiFR9LoVniJVdnRyrIkTfoGDAAAQMIZAAAAAAAAAAH/ARwc2V0AiBJmoGFRfa645/AO2N/Kk4eZOWQysG8Om9tcapEQ2VMFAEEAAA= 0 5FJgEFIEJAyJBQgxMggWA2SBQfScgUJA4OCbAwDEkDhgaBtA4CQKEgcRgnCChUTEWANA0g8RgcUAcVkCg/FpgGSBQbis5AoNxecfEMAxCZm42wCEig/BgQDQBwMDhIA= 

and

hal-simplicity simplicity pset extract cHNldP8BAgQCAAAAAQMEAAAAAAEEAQEBBQECAfsEAgAAAAABAU4BSZqBhUX2uuOfwDtjfypOHmTlkMrBvDpvbXGqRENlTBQBAAAAAAABhqAAIlEg8KGnifeumSOzMHWfmyqg74XdebWoyhvFqMSHzNAgDhIBBwABCPkEALPkKmAQUgQkDIkFCDEyCBYDZIFB9JyBQ0CnBmRweHJnZED/FIx6Cvuk9cvO3jZW4pMymPvZEzteJA2BoGILEGsDeQKGh82Ju1WF5pKKFsbVvpWmbtB7oRTukWZO/ncfvCl6pohIHBiQUBxAzB4eBxIBxOQKD8UmAZIFBuJzkChgCsDKQa2pxNOkeR5bPhYs3CU3SNxwt90CaQFJYqFdM6PgGAYBMjcY4BCRQfgoIBoA4EBwgCAGQ+DKnK7x6SjTWzdRv4A+OUceZQvlrQIbDWCMCq+YSCG/UJKbdMGgSVS3i0tgNel6XgeKWg8o7JbVR7/ums6AOsABDiAjTXUHCStdyxCqEE/A2G3iegMnCcSH+sx+gaPyWgzg/wEPBAAAAAABEAT/////IhW/UJKbdMGgSVS3i0tgNel6XgeKWg8o7JbVR7/ums6AOsAhBkPgypyu8eko01s3Ub+APjlHHmUL5a0CGw1gjAqvmEi+ARcgUJKbdMGgSVS3i0tgNel6XgeKWg8o7JbVR7/ums6AOsABGCCtdDtvi2/HueWPT4w9VLvu43OID2evFdsJmeT6HP97rAABAwg8hgEAAAAAAAf8BHBzZXQCIEmagYVF9rrjn8A7Y38qTh5k5ZDKwbw6b21xqkRDZUwUAQQWABS1jCIVH0uhWeIlV2dHKsiRN+gYMAABAwhkAAAAAAAAAAf8BHBzZXQCIEmagYVF9rrjn8A7Y38qTh5k5ZDKwbw6b21xqkRDZUwUAQQAAA==

and again the real Liquid testnet accepted the resulting transaction.

Minimal reproduction steps

Reproduction steps are given above in detail.

[schoen]

The AI also figured out why hal-simplicity's transaction was accepted while Simplex's was rejected: hal-simplicity is doing a decode of an already-serialized program, while Simplex is not. This different flow causes the representation of the program to be built differently and at a different stage in the process.

It seems like Simplex could work around this by deliberately serializing the program early and then decoding it again, but it might be more correct to figure out why the pruning logic is underpruning when given the in-memory representation, since I think it's still technically a bug in prune() (maybe in rust-simplicity rather than SimplicityHL though).

Sorry for the uncertainty about which project this bug should actually be filed against! Right now I think rust-simplicity may be more plausible than SimplicityHL... but I'm not positive.

Anyway, the AI has lots of theorizing about why the serialize and decode roundtrip ends up with pruning that makes elementsd happier, while pruning the in-memory program without prior serialization and decoding makes it unhappy, but I again don't know whether that speculation is correct or worth sharing. It notably didn't produce a proposed patch proving that its theory could fix the problem, or even a specific concrete proposed fix.

[stringhandler]

As far as I remember, the elements implementation marks every node in the program when running, and afterwards if there are any unmarked nodes, then it throws the unpruned error.

I think this is the correct repo for this issue. We should add more pruning commands to the CLI interface to help debug these. I think pruning only happens when you call satisfy_with_env, which is perhaps not being called.

[apoelstra]

As far as I remember, the elements implementation marks every node in the program when running, and afterwards if there are any unmarked nodes, then it throws the unpruned error.

rust-simplicity also prunes in this way.

I'm not sure how SimplicityHL/simc could do pruning. It doesn't have access to a transaction context and cannot run the programs that it produces. (Maybe it should, but that's a separate issue.)

So I think this belongs in smplx which actually calls the pruning methods.

[apoelstra]

Also, FYI, hal-simplicity simplicity pset finalize does pruning. This is because you typically can't prune a Simplicity program until the time of finalization, because before finalization you don't have a transaction environment.

[schoen]

Simplex does appear not to call satisfy_with_env at all, but it presumably could do so because it is actually building a full transaction.

The hal-simplicity version is apparently like

	// 3. Prune program.
	let redeem_node = program.redeem_node().ok_or(PsetFinalizeError::NoRedeemNode)?;
	let pruned = redeem_node.prune(&tx_env).map_err(PsetFinalizeError::ProgramPrune)?;

The Simplex version is apparently like

        let mut tracker = ProgramLogger::make_tracker(satisfied.debug_symbols(), GlobalConfig::get_log_level());
        let env = self.get_env(pst, input_index, network)?;
        let pruned = satisfied.redeem().prune_with_tracker(&env, &mut tracker)?;

Is this reflecting some kind of misconception about the correct use of these APIs?

[apoelstra]

No, if the tracker is working properly then prune_with_tracker should output the same program as prune.

satisfy_with_env is a SimplicityHL function that wraps prune and lets you call it without unwrapping the Simplicity program from the HL program.

[stringhandler]

Possible fix provided here BlockstreamResearch/rust-simplicity#379