Subject: Re: [bitcoin-dev] `OP_FOLD`: A Looping Construct For Bitcoin SCRIPT

From: Billy Tetrud <[email-masked]>
Date: Mon, 7 Mar 2022 11:26:13 -0600

Let me organize my thoughts on this a little more clearly. There's a couple
possibilities I can think of for a jet-like system:

A. We could implement jets now without a consensus change, and
without requiring all nodes to upgrade to new relay rules. Probably. This
would give upgraded nodes improved validation performance and many upgraded
nodes relay savings (transmitting/receiving fewer bytes). Transactions
would be weighted the same as without the use of jets tho.
B. We could implement the above + lighter weighting by using a soft fork to
put the jets in a part of the blockchain hidden from unupgraded nodes, as
you mentioned.
C. We could implement the above + the jet registration idea in a soft fork.

For A:

* Upgraded nodes query each connection for support of jets in general, and
which specific jets they support.
* For a connection to another upgraded node that supports the jet(s) that a
transaction contains, the transaction is sent verbatim with the jet
included in the script (eg as some fake opcode line like 23 OP_JET,
indicating to insert standard jet 23 in its place). When validation
happens, or when a miner includes it in a block, the jet opcode call is
replaced with the script it represents so hashing happens in a way that is
recognizable to unupgraded nodes.
* For a connection to a non-upgraded node that doesn't support jets, or an
upgraded node that doesn't support the particular jet included in the
script, the jet opcode call is replaced as above before sending to that
node. In addition, some data is added to the transaction that unupgraded
nodes propagate along but otherwise ignore. Maybe this is extra witness
data, maybe this is some kind of "annex", or something else. But that data
would contain the original jet opcode (in this example "23 OP_JET") so that
when that transaction data reaches an upgraded node that recognizes that
jet again, it can swap that back in, in place of the script fragment it
represents.

I'm not 100% sure the required mechanism I mentioned of "extra ignored
data" exists, and if it doesn't, then all nodes would at least need to be
upgraded to support that before this mechanism could fully work. But even
if such a mechanism doesn't exist, a jet script could still be used, but it
would be clobbered by the first nonupgraded node it is relayed to, and
can't then be converted back (without using a potentially expensive lookup
table as you mentioned).

> If the script does not weigh less if it uses a jet, then there is no
incentive for end-users to use a jet

That's a good point. However, I'd point out that nodes do lots of things
that there's no individual incentive for, and this might be one where
people either altruistically use jets to be lighter on the network, or use
them in the hopes that the jet is accepted as a standard, reducing the cost
of their scripts. But certainly a direct incentive to use them is better.
Honest nodes can favor connecting to those that support jets.

>if a jet would allow SCRIPT weights to decrease, upgraded nodes need to
hide them from unupgraded nodes
> we have to do that by telling unupgraded nodes "this script will always
succeed and has weight 0"

Right. It doesn't have to be weight zero, but that would work fine enough.

> if everybody else has not upgraded, a user of a new jet has no security.

For case A, no security is lost. For case B you're right. For case C, once
nodes upgrade to the initial soft fork, new registered jets can take
advantage of relay-cost weight savings (defined by the soft fork) without
requiring any nodes to do any upgrading, and nodes could be further
upgraded to optimize the validation of various of those registered jets,
but those processing savings couldn't change the weighting of transactions
without an additional soft fork.

> Consider an attack where I feed you a SCRIPT that validates trivially but
is filled with almost-but-not-quite-jettable code

I agree a pattern-matching lookup table is probably not a great design. But
a lookup table like that is not needed for the jet registration idea. After
the necessary soft fork, there would be standard rules for which registered
jets nodes are required to keep an index of, and so the lookup table would
be a straightforward jet hash lookup rather than a pattern-matching lookup,
which wouldn't have the same DOS problems. A node would simply find a jet
opcode call like "ab38cd39e OP_JET" and just lookup ab38cd39e in its index.

On Sun, Mar 6, 2022 at 2:38 PM ZmnSCPxj <[email-masked]> wrote:

> Good morning Billy,
>
> > Even changing the weight of a transaction using jets (ie making a script
> weigh less if it uses a jet) could be done in a similar way to how segwit
> separated the witness out.
>
> The way we did this in SegWit was to *hide* the witness from unupgraded
> nodes, who are then unable to validate using the upgraded rules (because
> you are hiding the data from them!), which is why I bring up:
>
> > > If a new jet is released but nobody else has upgraded, how bad is my
> security if I use the new jet?
> >
> > Security wouldn't be directly affected, only (potentially) cost. If your
> security depends on cost (eg if it depends on pre-signed transactions and
> is for some reason not easily CPFPable or RBFable), then security might be
> affected if the unjetted scripts costs substantially more to mine.
>
> So if we make a script weigh less if it uses a jet, we have to do that by
> telling unupgraded nodes "this script will always succeed and has weight
> 0", just like `scriptPubKey`s with `<0> <P2WKH hash>` are, to pre-SegWit
> nodes, spendable with an empty `scriptSig`.
> At least, that is how I always thought SegWit worked.
>
> Otherwise, a jet would never allow SCRIPT weights to decrease, as
> unupgraded nodes who do not recognize the jet will have to be fed the
> entire code of the jet and would consider the weight to be the expanded,
> uncompressed code.
> And weight is a consensus parameter, blocks are restricted to 4Mweight.
>
> So if a jet would allow SCRIPT weights to decrease, upgraded nodes need to
> hide them from unupgraded nodes (else the weight calculations of unupgraded
> nodes will hit consensus checks), then if everybody else has not upgraded,
> a user of a new jet has no security.
>
> Not even the `softfork` form of chialisp that AJ is proposing in the other
> thread would help --- unupgraded nodes will simply skip over validation of
> the `softfork` form.
>
> If the script does not weigh less if it uses a jet, then there is no
> incentive for end-users to use a jet, as they would still pay the same
> price anyway.
>
> Now you might say "okay even if no end-users use a jet, we could have
> fullnodes recognize jettable code and insert them automatically on
> transport".
> But the lookup table for that could potentially be large once we have a
> few hundred jets (and I think Simplicity already *has* a few hundred jets,
> so additional common jets would just add to that?), jettable code could
> start at arbitrary offsets of the original SCRIPT, and jettable code would
> likely have varying size, that makes for a difficult lookup table.
> In particular that lookup table has to be robust against me feeding it
> some section of code that is *almost* jettable but suddenly has a different
> opcode at the last byte, *and* handle jettable code of varying sizes
> (because of course some jets are going to e more compressible than others).
> Consider an attack where I feed you a SCRIPT that validates trivially but
> is filled with almost-but-not-quite-jettable code (and again, note that
> expanded forms of jets are varying sizes), your node has to look up all
> those jets but then fails the last byte of the
> almost-but-not-quite-jettable code, so it ends up not doing any jetting.
> And since the SCRIPT validated your node feels obligated to propagate it
> too, so now you are helping my DDoS.
>
> > >  I suppose the point would be --- how often *can* we add new jets?
> >
> > A simple jet would be something that's just added to bitcoin software
> and used by nodes that recognize it. This would of course require some
> debate and review to add it to bitcoin core or whichever bitcoin software
> you want to add it to. However, the idea I proposed in my last email would
> allow anyone to add a new jet. Then each node can have their own policy to
> determine which jets of the ones registered it wants to keep an index of
> and use. On its own, it wouldn't give any processing power optimization,
> but it would be able to do the same kind of script compression you're
> talking about op_fold allowing. And a list of registered jets could inform
> what jets would be worth building an optimized function for. This would
> require a consensus change to implement this mechanism, but thereafter any
> jet could be registered in userspace.
>
> Certainly a neat idea.
> Again, lookup table tho.
>
> Regards,
> ZmnSCPxj
>