Yet another padding option: Tapleaves

General
1

Currently, you cannot submit a program that has a budget above the transaction’s weight. There are a few solutions to this, but the main one we are waiting for is the PR in elements that adds a standardness rule to allow annex padding.

Instead of waiting for that, you can also try some other options. One is to use the padding::<x>() built in, in the SimpicityHL PR. This pads the actual simplicity program, changing the CMR.

Another option is to pad the witness yourself with empty values, as done in deadcat

let budget_pad_a: u256 = witness::BUDGET_PAD_A;
    let budget_pad_b: u256 = witness::BUDGET_PAD_B;
    assert!(jet::eq_256(budget_pad_a, budget_pad_b));
    let budget_pad_c: u256 = witness::BUDGET_PAD_C;
    let budget_pad_d: u256 = witness::BUDGET_PAD_D;
    assert!(jet::eq_256(budget_pad_c, budget_pad_d));

One more option exists, which I’m proposing today: Padding the control block with empty leaves. Basically, in this pattern, instead of putting the simplicity program in a single leaf in the Taproot tree, you make a very large tree, which is deep enough to include enough Taproot nodes in the control block to pay for the program.

This would need to be done by the wallet, so you could add some auto generation in txmanifest, for example.

The upside of doing this means you would not need to wait for the annex pr to land. Some downsides though:

  1. The address changes, so the padding needs to be known ahead of time.
  2. The upper limit of this method is around 4000 weight units, so the infamous hashloop example could not be done using this method.
  3. State parameters are either hard to do or impossible.
  4. Covenant checking scripts couldn’t really implement this.

The downsides probably disqualify this method for most use cases, but nevertheless, the method is presented for anyone who is interested.

Padding problem: execution cost exceeded budget limit
2

I think this limit is too severe for the idea to be worth the implementation complexity.

3

That was my feeling as well, but I thought I would add it here for documentation purposes.

1 Like
4

To further document padding workarounds: the method you mentioned used by deadcat above doesn’t scale very well if you need a lot of witness padding. Basically the additional code to consume the witness itself adds to the amount of padding that you need, and it gets less and less efficient as you add more padding (seemingly with a crossover point that’s a maximum amount of witness padding that can be successfully added by this method!).

Claude discovered a different method to make witness padding scale more efficiently using array_fold:

fn combine_pad(elem: u256, acc: bool) -> bool {
    and(acc, jet::eq_256(elem, elem))
}

let pad: [u256; 1500] = witness::BUDGET_PAD;
let pad_ok: bool = array_fold::<combine_pad, 1500>(pad, true);
assert!(pad_ok);

I have a long explanation from Claude about why it thinks this works better, but I don’t want to paste it without understanding or verifying the justification myself.

Overall, I think this is a workaround for a workaround and not some kind of awesome best practice or anything. I look forward to the availability of the official annex padding method!

1 Like
5

I have another padding method which is kinda interesting: adding auxiliary witnesses. For example, the fe_square_root jet costs 10275 milliweight units but the fe_square jet costs only 556. If you need 32 padding bytes for other reasons, you can provide the square root as a witness, square it and assert equality, and then you’ve saved almost 10wu.

The same thing can be applied to the decompress jet for curvepoints, where you take the y coordinate as witness, check its sign matches the parity bit and check ge_is_on_curve jet, and you also avoid a squareroot and ~10wu. (If you are decompressing CT points, you will need to “do both”, i.e. you need to take the square root of your y coordinate and square this to get a y coordinate that is a quadratic residue, which you conditionally negate.)

This idea came indirectly from ChatGPT 6 while discussing Elements: parity bit of confidential asset/amount points uses Elements' square-y encoding, but decompress treats it as odd-y · Issue #349 · BlockstreamResearch/simplicity · GitHub