policy: allow exact annex padding for simplicity spends by delta1 · Pull Request #1539 · ElementsProject/elements · GitHub

Implements BlockstreamResearch/simplicity#290 for Elements standardness policy.

Something concerning to be investigated is that Cost::get_padding in rust-simplicity is returning a padding 2 bytes bigger than this calculation.. presumably an error in that method?

Fix for rust-simplicity get_padding at BlockstreamResearch/rust-simplicity#356

I'll have some more comment later but first and foremost there is no need to amend the Simplicity C code.

Instead there is a minCost parameter that can needs to be passed up through CheckSimplicity. See https://github.com/roconnor-blockstream/bitcoin/pull/1/changes#diff-a0337ffd7259e8c7c9a7786d6dbd420c80abfa1afdb34ebae3261109d9ae3c19R1876-R1886 for an example of this. You will need to pass a minCost of 0 when in consensus mode rather than policy mode.

Have a careful read of the documentation for minCost in execSimplicity.

Thanks @roconnor-blockstream updated

Cost::get_padding previously always assumed only 1 byte for compactsize encoding when calculating required padding size. For larger differences in cost/budget, this incorrectly resulted in an additional 1 or 2 bytes of padding depending on the difference. I found this when calculating padding for the SimplicityHL hash loop example, where rust-simplicity was calculating a 7426 byte annex padding while libsimplicity required a 7424 byte padding, since the compactsize encoding requires an additional 2 bytes. See ElementsProject/elements#1539

Cost::get_padding previously always assumed only 1 byte for compactsize encoding when calculating required padding size. For larger differences in cost/budget, this incorrectly resulted in an additional 1 or 2 bytes of padding depending on the difference. I found this when calculating padding for the SimplicityHL hash loop example, where rust-simplicity was calculating a 7426 byte annex padding while libsimplicity required a 7424 byte padding, since the compactsize encoding requires 2 additional bytes. See ElementsProject/elements#1539

Force push to fix a null-pointer-use identified by the fuzz task

This looks approximately like what I'm expecting, but I'll need some time to go over it in more detail.

Feel free to push back on this idea, but I think it would be marginally better to move this zero-padding check into policy.cpp. That is to say that IsWitnessStandard says that an annex is standard only when it is both

all zeros and
is part of a Simplicity redemption.

The all zero check can be validated without parsing of the Simplicity program, and moving the code there removes the need for an explicit SCRIPT_ERR_SIMPLICITY_PADDING_NONZERO error. It just simply becomes non-standard to have a non-zero annex.

I'm of two minds about this, I initially did have it in IsWitnessStandard, but I mildly prefer this approach since it returns a specific error to the client instead of just "non-standard" with no additional info. I don't really mind either way, and do see your point not having to parse the Simplicity program or needing a new error variant.

Okay, let's leave it as is unless an Element's reviewer suggests otherwise.

!zero_padding.empty() can never be false here because zero_padding.size() > 0. The condition should be 1 < zero_padding.size().

Preferably we'd add a test case to catch this programming error before fixing it. It would be something like a program that needs exactly one byte of padding in order to be spendable. With the code as currently written, such program would fail to be spendable. One byte of padding would require a minimal annex with 0 zero bytes. But the serialization of the stack item 0x50 requires two bytes, one for the 0x50 and one for the prefix. Two bytes would put the program overweight with the current logic.

When I was last looking at how to construct such a specific example, I had asked @apoelstra to use his fuzzer to find one.

I will try to generate such a program, any suggestion as to how to fix that case?

In f65006a I have changed the conditional check, and only pop_back off zero_padding when its > 1. Then the minCost addition is moved out of the conditional

No no, keep the minCost addition inside the conditional.

The logic here is as as follows, and maybe we should explicitly document this in the code:

(1) If there is no annex, or we are in consensus checking mode, minCost is set to 0 which effectively disable any overweight cost checks.

(2) If there is an annex, we set minCost to be what the budget would have been if they user made their annex padding smaller. This computation proceeds in two stages:

First we set minCost to be what the stack size would have been without the annex. Because the number of stack items is at most 3, this calculation can be done by subtracting the annex stack item size from the budget.

(a) If the annex exists and is empty, then the only way the annex could be smaller is by eliminating it entirely, and thus we use the above computed value for minCost. Note: in this case the minCost is 2 WU less than the budget.

(b) If the annex exists and is non-empty, then we add to minCost the value of an annex that contains one fewer byte. Note: If the length of the padding (including the annex prefix) is exactly 253, then minCost will be 3 WU less than the budget! Similarly for padding of length 65536.

Okay thanks for the clarification. Updated and added this documentation

7871509 fix: get_padding for larger costs and padding lengths (Byron Hambly) Pull request description: `Cost::get_padding` previously always assumed only 1 byte for compactsize encoding when calculating required padding size. For larger differences in cost/budget, this incorrectly resulted in an additional 1 or 2 bytes of padding depending on the difference. I found this when calculating padding for the SimplicityHL hash loop example, where rust-simplicity was calculating a 7426 byte annex padding while libsimplicity required a 7424 byte padding, since the compactsize encoding requires 2 additional bytes. See ElementsProject/elements#1539 ACKs for top commit: ivanlele: ACK. Ran tests at 7871509 apoelstra: ACK 7871509; successfully ran local tests Tree-SHA512: 518d7ba03519c751721f79bae2517e239858c21cac38e6e2b847285653e02bf6d7557dc3e4e68c8b386477314e19c590f7ae50de606c5a8905a630002a00db2e

utACK 3d352ed

Needs rebase. Sorry for the long delay.

Thanks @apoelstra. Rebased.

Lint CI job is unrelated to this PR, and resolved by #1572

"test each commit" job is also unrelated and will eventually be fixed upstream by BlockstreamResearch/simplicity#345

utACK fb337f2

What needs to be done to land this?

@apoelstra I think it's good to go, I'll fix the lint CI job (edit: rebased on master).

"test each commit" needs a subtree update so I don't see it as a blocker for this PR.

In bfde7b7:

This looks like a double-pop. A few lines below this change there is another if-block, if (stack.size() >= 2) (which will trigger if this block triggers) that also has

const auto& control_block = SpanPopBack(stack);

Found by Qwen 3.8-Flash-Next.

The bot also gave me this unit test file

// Temporary review probe for Elements PR #1539 (NOT for commit):
// annexed Simplicity spend where the 32-byte CMR starts with 0xc0/0xc1.
// IsWitnessStandard's annex branch pops annex AND control block, then the
// generic script-path branch pops the CMR as "control block"; if cmr[0] & 0xfe
// == 0xc0 (Tapscript leaf), MAX_STANDARD_TAPSCRIPT_STACK_ITEM_SIZE (80) is
// applied to the remaining witness items. Probe compares a Simplicity annexed
// spend with a 100-byte witness across cmr[0] in {0x11, 0xc0, 0xc1, 0xbe}.
#include <test/util/setup_common.h>

#include <coins.h>
#include <policy/policy.h>
#include <primitives/transaction.h>
#include <script/script.h>
#include <arith_uint256.h>
#include <uint256.h>

#include <boost/test/unit_test.hpp>

#include <map>
#include <vector>

namespace {
class MapCoinsView : public CCoinsView
{
    std::map<COutPoint, Coin> m_coins;
public:
    void Add(const COutPoint& out, Coin coin) { m_coins[out] = std::move(coin); }
    std::optional<Coin> GetCoin(const COutPoint& outpoint) const override
    {
        auto it = m_coins.find(outpoint);
        if (it == m_coins.end()) return std::nullopt;
        return it->second;
    }
};
} // namespace

BOOST_FIXTURE_TEST_SUITE(annex_padding_probe, BasicTestingSetup)

static CTransactionRef MakeAnnexedSpend(uint8_t cmr_first, size_t witness_len)
{
    CMutableTransaction tx;
    tx.vin.resize(1);
    tx.vin[0].prevout = COutPoint(Txid::FromUint256(ArithToUint256(1)), 0);
    tx.vout.resize(1);
    tx.vout[0].nValue.SetToAmount(1000);

    CTxInWitness win;
    std::vector<uint8_t> cmr(32, 0x22);
    cmr[0] = cmr_first;
    std::vector<uint8_t> control(33, 0xcc);
    control[0] = 0xbe; // TAPROOT_LEAF_TAPSIMPLICITY, depth 0
    std::vector<uint8_t> annex(12, 0);
    annex[0] = 0x50;   // ANNEX_TAG + zero padding
    win.scriptWitness.stack = {
        std::vector<uint8_t>(witness_len, 0xaa), // "simplicity witness"
        std::vector<uint8_t>(40, 0x11),          // "simplicity program"
        cmr,                                     // script CMR (32 bytes)
        control,                                 // control block
        annex,
    };
    tx.witness.vtxinwit.push_back(win);
    return MakeTransactionRef(std::move(tx));
}

BOOST_AUTO_TEST_CASE(annex_padding_double_pop_probe)
{
    CScript taproot_spk;
    std::vector<uint8_t> prog(32, 0xab);
    taproot_spk << OP_1 << prog;

    MapCoinsView view;
    CTxOut prevout;
    prevout.nValue.SetToAmount(100000);
    prevout.scriptPubKey = taproot_spk;
    view.Add({Txid::FromUint256(ArithToUint256(1)), 0}, Coin{std::move(prevout), 1, false});
    CCoinsViewCache coins(&view);

    const bool a = IsWitnessStandard(*MakeAnnexedSpend(0x11, 100), coins);
    const bool b = IsWitnessStandard(*MakeAnnexedSpend(0xc4, 100), coins);
    const bool c = IsWitnessStandard(*MakeAnnexedSpend(0xc5, 100), coins);
    const bool d = IsWitnessStandard(*MakeAnnexedSpend(0xbe, 100), coins);
    const bool e = IsWitnessStandard(*MakeAnnexedSpend(0xc4, 80), coins); // <= limit
    BOOST_TEST_MESSAGE("100-byte witness: cmr[0]=0x11 -> " << a << "; 0xc4 -> " << b
                       << "; 0xc5 -> " << c << "; 0xbe -> " << d << "   | 80-byte witness, 0xc4 -> " << e);
    BOOST_CHECK(a);
    BOOST_CHECK(d);
    BOOST_CHECK(e);
    BOOST_CHECK_EQUAL(b, a);
    BOOST_CHECK_EQUAL(c, a);
}

BOOST_AUTO_TEST_SUITE_END()

delta1 requested review from apoelstra and roconnor-blockstream March 13, 2026 13:24

delta1 force-pushed the 2026-02-annex-policy branch 2 times, most recently from 4cdb88c to 1918260 Compare March 25, 2026 13:26

delta1 marked this pull request as ready for review March 25, 2026 13:26

delta1 mentioned this pull request Mar 30, 2026

fix: get_padding for larger costs and padding lengths BlockstreamResearch/rust-simplicity#356

Merged

delta1 force-pushed the 2026-02-annex-policy branch from 1918260 to ddf712e Compare March 30, 2026 14:04

roconnor-blockstream requested changes Mar 31, 2026

View reviewed changes

roconnor-blockstream reviewed Mar 31, 2026

View reviewed changes

Comment thread src/policy/policy.cpp Outdated

delta1 force-pushed the 2026-02-annex-policy branch from f65006a to d070b5d Compare April 7, 2026 14:02

roconnor-blockstream reviewed May 14, 2026

View reviewed changes

Comment thread src/policy/policy.cpp Outdated

delta1 force-pushed the 2026-02-annex-policy branch from 3d352ed to fb337f2 Compare July 13, 2026 07:00

apoelstra mentioned this pull request Aug 24, 2026

feat: add padding keyword to increase program size BlockstreamResearch/SimplicityHL#226

Open

simplicity: allow exact annex padding in policy

bfde7b7

test: add exact annex padding test for simplicity spends

fac8080

delta1 force-pushed the 2026-02-annex-policy branch from fb337f2 to fac8080 Compare August 25, 2026 08:43

apoelstra reviewed Sep 4, 2026

View reviewed changes

+                                  valtype zero_padding(padding.size(), 0);
+                                  zero_padding[0] = ANNEX_TAG;
+                                  if (padding != zero_padding) {
+                                      return set_error(serror, SCRIPT_ERR_SIMPLICITY_PADDING_NONZERO);

+                                  // Compute what the budget would have been without the padding.
+                                  // budget includes the padding cost, so subtracting this stack item won't underflow.
+                                  minCost = budget - ::GetSerializeSize(padding);
+                                  if (!zero_padding.empty()) {

-                              // Annexes are nonstandard as long as no semantics are defined for them.
-                              return false;
+                              SpanPopBack(stack); // drop the annex
+                              const auto& control_block = SpanPopBack(stack);

policy: allow exact annex padding for simplicity spends by delta1 · Pull Request #1539 · ElementsProject/elements · GitHub

Repository navigation

policy: allow exact annex padding for simplicity spends - #1539

policy: allow exact annex padding for simplicity spends #1539delta1 wants to merge 2 commits intoElementsProject:masterElementsProject/elements:masterfrom delta1:2026-02-annex-policydelta1/elements:2026-02-annex-policyCopy head branch name to clipboard

Conversation

delta1 commented Mar 13, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

roconnor-blockstream commented Mar 16, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

delta1 commented Mar 25, 2026

Uh oh!

delta1 commented Mar 30, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

roconnor-blockstream commented Mar 30, 2026

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

roconnor-blockstream Mar 31, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

delta1 Apr 2, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

apoelstra commented Jul 11, 2026

Uh oh!

delta1 commented Jul 13, 2026

Uh oh!

delta1 commented Jul 13, 2026

Uh oh!

apoelstra commented Jul 27, 2026

Uh oh!

apoelstra commented Aug 24, 2026

Uh oh!

delta1 commented Aug 25, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

policy: allow exact annex padding for simplicity spends #1539
delta1 wants to merge 2 commits into
ElementsProject:masterfrom
delta1:2026-02-annex-policy

delta1 commented Mar 13, 2026 •
edited
Loading

roconnor-blockstream commented Mar 16, 2026 •
edited
Loading

delta1 commented Mar 30, 2026 •
edited
Loading

roconnor-blockstream Mar 31, 2026 •
edited
Loading

delta1 Apr 2, 2026 •
edited
Loading

delta1 commented Aug 25, 2026 •
edited
Loading