Date: Thu, 10 Mar 2022 06:43:56 +0000
To: Billy Tetrud <billy.tetrud@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <8R8D_XAaz7xYHmgWXR-pc3_GVFRzBCNdRT6s3PdKblrnnZPirB0orzLpEUvynBZHNBTiqOM_EteDdUjdqXQ5ZmrGbdlgnnfjIihgFZIXpUM=@protonmail.com>
In-Reply-To: <CAGpPWDafWGcZJOUs4wSEt0DzFP8OXB4nrbx+9sUtTe5JfdwE_w@mail.gmail.com>
References: <EIwjydT0d68Z7Jv8_JlrCbQW6NHSSnIU5sWwE8eX2rm9K3djfzU3nQqUrmt44U8-L9sObegelHCV6Sk7h2nwq_HS1d26FophzjNU7xC_6SE=@protonmail.com>
 <CAGpPWDafWGcZJOUs4wSEt0DzFP8OXB4nrbx+9sUtTe5JfdwE_w@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Jets (Was: `OP_FOLD`: A Looping Construct For
	Bitcoin SCRIPT)
Precedence: list

Good morning Billy,

> Hi=C2=A0ZmnSCPxj,
>
> >=C2=A0 Just ask a bunch of fullnodes to add this 1Mb of extra ignored da=
ta in this tiny 1-input-1-output transaction so I pay only a small fee
>
> I'm not suggesting that you wouldn't have to pay a fee for it. You'd pay =
a fee for it as normal, so there's no DOS vector. Doesn't adding extra=
=C2=A0witness data do what would be needed here? Eg simply adding extra dat=
a onto the witness script that will remain unconsumed after successful exec=
ution of the script?

I think we would want to have a cleanstack rule at some point (do not remem=
ber out-of-hand if Taproot already enforces one).

So now being nice to the network is *more* costly?
That just *dis*incentivizes jet usage.

> > how do new jets get introduced?
>
> In scenario A, new jets get introduced by being added to bitcoin software=
 as basically relay rules.=C2=A0
>
> > If a new jet requires coordinated deployment over the network, then you=
 might as well just softfork and be done with it.
>
> It would not need a coordinated deployment. However, the more nodes that =
supported that jet, the more efficient using it would be for the network.=
=C2=A0
>
> > If a new jet can just be entered into some configuration file, how do y=
ou coordinate those between multiple users so that there *is* some benefit =
for relay?
>
> When a new version of bitcoin comes out, people generally upgrade to it e=
ventually. No coordination is needed. 100% of the network need not support =
a jet. Just some critical mass to=C2=A0get some benefit.=C2=A0

How large is the critical mass needed?

If you use witness to transport jet information across non-upgraded nodes, =
then that disincentivizes use of jets and you can only incentivize jets by =
softfork, so you might as well just get a softfork.

If you have no way to transport jet information from an upgraded through a =
non-upgraded back to an upgraded node, then I think you need a fairly large=
 buy-in from users before non-upgraded nodes are rare enough that relay is =
not much affected, and if the required buy-in is large enough, you might as=
 well softfork.

> > Having a static lookup table is better since you can pattern-match on s=
trings of specific, static length
>
> Sorry, better than what exactly?=C2=A0

Than using a dynamic lookup table, which is how I understood your previous =
email about "scripts in the 1000 past blocks".

> > How does the unupgraded-to-upgraded boundary work?
> <snip>
> When the non-jet aware node sends this to a jet-aware node, that node wou=
ld see the extra items on the stack after script execution, and would inter=
pret them as an OP_JET call specifying that OP_JET should replace the witne=
ss items starting at index 0 with `1b5f03cf=C2=A0=C2=A0OP_JET`. It does thi=
s and then sends that along to the next hop.

It would have to validate as well that the SCRIPT sub-section matches the j=
et, else I could pretend to be a non-jet-aware node and give you a SCRIPT s=
ub-section that does not match the jet and would cause your validation to d=
iverge from other nodes.

Adler32 seems a bit short though, it seems to me that it may lead to two di=
fferent SCRIPT subsections hashing to the same hash.

Suppose I have two different node softwares.
One uses a particular interpretation for a particular Adler32 hash.
The other uses a different interpretation.
If we are not careful, if these two jet-aware software talk to each other, =
they will ban each other from the network and cause a chainsplit.
Since the Bitcoin software is open source, nothing prevents anyone from usi=
ng a different SCRIPT subsection for a particular Adler32 hash if they find=
 a collision and can somehow convince people to run their modified software=
.

> In order to support this without a soft fork, this extra otherwise unnece=
ssary=C2=A0data would be needed, but for jets that represent long scripts, =
the extra witness data could be well worth it (for the network).=C2=A0
>
> However, this extra data would be a disincentive to do transactions this =
way, even when its=C2=A0better for the network. So it might not be worth do=
ing it this way without a soft fork. But with a soft fork to upgrade nodes =
to support an OP_JET opcode, the extra witness data can be removed (replace=
d with out-of-band script fragment transmission for nodes that don't suppor=
t a particular jet).=C2=A0

Which is why I pointed out that each individual jet may very well require a=
 softfork, or enough buy-in that you might as well just softfork.

> One interesting additional thing that could be done with this mechanism i=
s to add higher-order function ability to jets, which could allow nodes to =
add OP_FOLD or similar functions as a jet without requiring additional soft=
 forks.=C2=A0 Hypothetically, you could imagine a jet script that uses an O=
P_LOOP jet be written as follows:
>
> 5=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0# Loop 5 times
> 1=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0# Loop the next 1 operat=
ion
> 3c1g14ad=C2=A0
> OP_JET
> OP_ADD=C2=A0 # The 1 operation to loop
>
> The above would sum up 5 numbers from the stack. And while this summation=
 jet can't be represented in bitcoin script on its own (since bitcoin scrip=
t can't manipulate opcode calls), the jet *call* can still be represented a=
s:
>
> OP_ADD=C2=A0=C2=A0
> OP_ADD=C2=A0=C2=A0
> OP_ADD=C2=A0=C2=A0
> OP_ADD=C2=A0=C2=A0
> OP_ADD=C2=A0=C2=A0
>
> which means all of the above replacement functionality would work just as=
 well.=C2=A0
>
> So my point here is that jets implemented in a way similar to this would =
give a much wider range of "code as compression" possibilities than impleme=
nting a single opcode like op_fold.=C2=A0

Yes, that is certainly the case, and nothing really prevents us bringing "p=
rogramming as compression" to its logical conclusion.

> > To make jets more useful, we should redesign the language so that `OP_P=
USH` is not in the opcode stream, but instead, we have a separate table of =
constants that is attached / concatenated to the actual SCRIPT.
>
> This can already be done, right? You just have to redesign the script to =
consume and swap/rot around the data in the right way to separate them out =
from the main script body.=C2=A0

Yes, but that implies additional operations (and execution overhead), incre=
asing the costs to use jets, which makes it even less palatable to use jets=
, *in addition to* the witness hack disincentivizing jets.

So I would suggest that, if we were to seriously pursue jets, we should rea=
lly replace most of the `OP_PUSH` opcodes with variants that look up in a s=
tatic table at the start, before the executable script body.
I.e. opcodes 0x01 to 0x4e instead mean "push contents of `c1` to `c78` from=
 the constants table", and have aliases `a` through `z` for `c1` to `c26`, =
etc.
That way, replacing the `OP_PUSH` is shorter in the actual SCRIPT (instead =
of a bunch of stack manipulations) and hopefully the overhead of the consta=
nts table can be kept low.

In particular, this helps jets compose more easily; if we want a SCRIPT tha=
t incorporates an existing jet, we do not have to manipulate the stack in a=
 way that the existing jet expects, we just load the proper data into the c=
onstants table.

Or something, anyway.
This seems a fair amount of complexity here.

Regards,
ZmnSCPxj