MIME-Version: 1.0
References: <rcWu5FJZQGCdQeFZSUKV2AylHwmlTYPWAnxvN-FP8lER3qFBLIYLPVH4-r0js0k6_Xy_TwxA3jWXZC15jFbAafNb_vnr3a54ZMrgAeTz6vM=@protonmail.com>
 <CAGpPWDawAQShRU4OYcVnOE+qmHQv79ahwhMeyALF8iwjkZ_sOg@mail.gmail.com>
 <1zAD-_yaVAjRfYOQmNn_lh1cIQ9yxtR_TpLpHfl3A8TbtTpHEpduMloN72b-zI8U4HjrXRCHBBee16Ly89OAZJohfJuewWNCCHuacBN5TE8=@protonmail.com>
 <CAGpPWDYCPgLxO4rDRVhK+ye50EBinKKXdiJTG+4CoW8SDtvJAA@mail.gmail.com>
 <-3inEV9Skl4K8wQefM7I0EbYzQc-zWV4QPgJSXKNxx0X_2EbwyTRmVjwooU1a8wFRNU41Cr41hb-Ajno_nV39U9rOge1oaUg9MvKmQ7-v30=@protonmail.com>
In-Reply-To: <-3inEV9Skl4K8wQefM7I0EbYzQc-zWV4QPgJSXKNxx0X_2EbwyTRmVjwooU1a8wFRNU41Cr41hb-Ajno_nV39U9rOge1oaUg9MvKmQ7-v30=@protonmail.com>
From: Billy Tetrud <billy.tetrud@gmail.com>
Date: Mon, 7 Mar 2022 11:26:13 -0600
Message-ID: <CAGpPWDbFZWjQE5PqU85GHQa0WJwRMsgSVQdDeXiZSbxVZeV4pw@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="0000000000003ec01305d9a42ae7"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] `OP_FOLD`: A Looping Construct For Bitcoin SCRIPT
Precedence: list

--0000000000003ec01305d9a42ae7
Content-Type: text/plain; charset="UTF-8"

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 <ZmnSCPxj@protonmail.com> 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
>

--0000000000003ec01305d9a42ae7
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Let me organize my thoughts on this a little more cle=
arly. There&#39;s a couple possibilities I can think of for a jet-like syst=
em:<br></div><div><br></div><div>A. We could implement jets now without a c=
onsensus change, and without=C2=A0requiring all nodes to upgrade to new rel=
ay rules. Probably. This would give upgraded nodes improved=C2=A0validation=
 performance and many upgraded nodes relay savings (transmitting/receiving =
fewer bytes). Transactions would be weighted the same as without the use of=
 jets tho.<br>B. We could implement the above=C2=A0+ lighter weighting by u=
sing a soft fork to put the jets in a part of the blockchain hidden from un=
upgraded nodes, as you mentioned.=C2=A0</div><div>C. We could implement the=
 above=C2=A0+ the jet registration idea in a soft fork.=C2=A0</div><div><br=
></div><div>For A:</div><div><br></div><div>* Upgraded nodes query each con=
nection for support of jets in general, and which specific jets they suppor=
t.</div><div>* For a connection to another upgraded node that supports the =
jet(s) that a transaction contains, the transaction is sent verbatim=C2=A0w=
ith 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 ha=
ppens, or when a miner includes it in a block, the jet opcode call is repla=
ced with the script it represents so hashing happens in a way that is recog=
nizable to unupgraded nodes.</div><div>* For a connection to a non-upgraded=
 node that doesn&#39;t support jets, or an upgraded node that doesn&#39;t s=
upport the particular jet included in the script, the jet opcode call is re=
placed as above before sending to that node. In addition, some data is adde=
d to the transaction that unupgraded nodes propagate along but otherwise ig=
nore. Maybe this is extra witness data, maybe this is some kind of &quot;an=
nex&quot;, or something else. But that data would contain the original jet =
opcode (in this example &quot;23 OP_JET&quot;) so that when that transactio=
n data reaches an upgraded node that recognizes that jet again, it can swap=
 that back in, in place of the script fragment it represents.=C2=A0</div><d=
iv><br></div><div>I&#39;m not 100% sure the required mechanism I mentioned =
of &quot;extra ignored data&quot; exists, and if it doesn&#39;t, then all n=
odes would at least need to be upgraded to support that before this mechani=
sm could fully work. But even if such a mechanism doesn&#39;t exist, a jet =
script could still be used, but it would be clobbered by the first nonupgra=
ded node it is relayed to, and can&#39;t then be converted back (without us=
ing a potentially expensive lookup table as you mentioned).=C2=A0</div><div=
><br></div><div>&gt; If the script does not weigh less if it uses a jet, th=
en there is no incentive for end-users to use a jet<br></div><div><br></div=
><div>That&#39;s a good point. However, I&#39;d point out that nodes do lot=
s of things that there&#39;s no individual incentive for, and this might be=
 one where people either altruistically use jets to be lighter on the netwo=
rk, or use them in the hopes that the jet is accepted as a standard, reduci=
ng 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.</d=
iv><div><br></div><div>&gt;if a jet would allow SCRIPT weights to decrease,=
 upgraded nodes need to hide them from unupgraded nodes</div><div>&gt; we h=
ave to do that by telling unupgraded nodes &quot;this script will always su=
cceed and has weight 0&quot;<br></div><div><br></div><div>Right. It doesn&#=
39;t have to be weight zero, but that would work fine enough.=C2=A0</div><d=
iv><br></div><div>&gt; if everybody else has not upgraded, a user of a new =
jet has no security.</div><div><br></div><div>For case A, no security is lo=
st. For case B you&#39;re right. For case C, once nodes upgrade to the init=
ial 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 up=
grading, and nodes could be further upgraded to optimize the validation of =
various of those registered jets, but those processing savings couldn&#39;t=
 change the weighting of transactions without an additional soft fork.</div=
><div><br></div><div>&gt; Consider an attack where I feed you a SCRIPT that=
 validates trivially but is filled with almost-but-not-quite-jettable code<=
/div><div><br></div><div>I agree a pattern-matching lookup table is probabl=
y not a great design. But a lookup table like that is not needed for the je=
t registration idea. After the necessary soft fork, there would be standard=
 rules for which registered jets nodes are required to keep an index of, an=
d so the lookup table would be a straightforward jet hash lookup rather tha=
n a pattern-matching lookup, which wouldn&#39;t have the same DOS problems.=
 A node would simply find a jet opcode call like &quot;ab38cd39e OP_JET&quo=
t; and just lookup ab38cd39e in its index.=C2=A0</div><div><br></div></div>=
<br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sun=
, Mar 6, 2022 at 2:38 PM ZmnSCPxj &lt;<a href=3D"mailto:ZmnSCPxj@protonmail=
.com" target=3D"_blank">ZmnSCPxj@protonmail.com</a>&gt; wrote:<br></div><bl=
ockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-lef=
t:1px solid rgb(204,204,204);padding-left:1ex">Good morning Billy,<br>
<br>
&gt; Even changing the weight of a transaction using jets (ie making a scri=
pt weigh less if it uses a jet) could be done in a similar=C2=A0way to how =
segwit separated=C2=A0the witness out.<br>
<br>
The way we did this in SegWit was to *hide* the witness from unupgraded nod=
es, who are then unable to validate using the upgraded rules (because you a=
re hiding the data from them!), which is why I bring up:<br>
<br>
&gt; &gt; If a new jet is released but nobody else has upgraded, how bad is=
 my security if I use the new jet?<br>
&gt;<br>
&gt; Security wouldn&#39;t be directly affected, only (potentially) cost. I=
f your security depends on cost (eg if it depends on pre-signed transaction=
s and is for some reason not easily CPFPable or RBFable), then security mig=
ht be affected if the unjetted=C2=A0scripts costs substantially more to min=
e.=C2=A0<br>
<br>
So if we make a script weigh less if it uses a jet, we have to do that by t=
elling unupgraded nodes &quot;this script will always succeed and has weigh=
t 0&quot;, just like `scriptPubKey`s with `&lt;0&gt; &lt;P2WKH hash&gt;` ar=
e, to pre-SegWit nodes, spendable with an empty `scriptSig`.<br>
At least, that is how I always thought SegWit worked.<br>
<br>
Otherwise, a jet would never allow SCRIPT weights to decrease, as unupgrade=
d 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 cod=
e.<br>
And weight is a consensus parameter, blocks are restricted to 4Mweight.<br>
<br>
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.<br>
<br>
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.<br>
<br>
If the script does not weigh less if it uses a jet, then there is no incent=
ive for end-users to use a jet, as they would still pay the same price anyw=
ay.<br>
<br>
Now you might say &quot;okay even if no end-users use a jet, we could have =
fullnodes recognize jettable code and insert them automatically on transpor=
t&quot;.<br>
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.<br>
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 opc=
ode at the last byte, *and* handle jettable code of varying sizes (because =
of course some jets are going to e more compressible than others).<br>
Consider an attack where I feed you a SCRIPT that validates trivially but i=
s filled with almost-but-not-quite-jettable code (and again, note that expa=
nded forms of jets are varying sizes), your node has to look up all those j=
ets but then fails the last byte of the almost-but-not-quite-jettable code,=
 so it ends up not doing any jetting.<br>
And since the SCRIPT validated your node feels obligated to propagate it to=
o, so now you are helping my DDoS.<br>
<br>
&gt; &gt;=C2=A0 I suppose the point would be --- how often *can* we add new=
 jets?<br>
&gt;<br>
&gt; A simple jet would be something that&#39;s just added to bitcoin softw=
are 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 y=
ou want to add it to. However, the idea I proposed in my last email would a=
llow anyone to add a new jet. Then each node can have their own policy to d=
etermine which jets of the ones registered it wants to keep an index of and=
 use. On its own, it wouldn&#39;t give any processing power optimization, b=
ut it would be able to do the same kind of script compression you&#39;re ta=
lking about op_fold allowing. And a list of registered jets could inform wh=
at jets would be worth building an optimized function for.=C2=A0This would =
require a consensus change to implement this mechanism, but thereafter any =
jet could be registered in userspace.<br>
<br>
Certainly a neat idea.<br>
Again, lookup table tho.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--0000000000003ec01305d9a42ae7--