From: Billy Tetrud <billy.tetrud@gmail•com>
To: ZmnSCPxj <ZmnSCPxj@protonmail•com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Jets (Was: `OP_FOLD`: A Looping Construct For Bitcoin SCRIPT)
Date: Fri, 11 Mar 2022 08:11:33 -0600 [thread overview]
Message-ID: <CAGpPWDZwYE__YifZ0h7Bkftas6zN6Q7yOhB4rUAAwT0dcgYk7w@mail.gmail.com> (raw)
In-Reply-To: <8R8D_XAaz7xYHmgWXR-pc3_GVFRzBCNdRT6s3PdKblrnnZPirB0orzLpEUvynBZHNBTiqOM_EteDdUjdqXQ5ZmrGbdlgnnfjIihgFZIXpUM=@protonmail.com>
[-- Attachment #1: Type: text/plain, Size: 12596 bytes --]
> I think we would want to have a cleanstack rule at some point
Ah is this a rule where a script shouldn't validate if more than just a
true is left on the stack? I can see how that would prevent the
non-soft-fork version of what I'm proposing.
> How large is the critical mass needed?
Well it seems we've agreed that were we going to do this, we would want to
at least do a soft-fork to make known jet scripts lighter weight (and
unknown jet scripts not-heavier) than their non-jet counterparts. So given
a situation where this soft fork happens, and someone wants to implement a
new jet, how much critical mass would be needed for the network to get some
benefit from the jet? Well, the absolute minimum for some benefit to happen
is that two nodes that support that jet are connected. In such a case, one
node can send that jet scripted transaction along without sending the data
of what the jet stands for. The jet itself is pretty small, like 2 or so
bytes. So that does impose a small additional cost on nodes that don't
support a jet. For 100,000 nodes, that means 200,000 bytes of transmission
would need to be saved for a jet to break even. So if the jet stands for a
22 byte script, it would break even when 10% of the network supported it.
If the jet stood for a 102 byte script, it would break even when 2% of the
network supported it. So how much critical mass is necessary for it to be
worth it depends on what the script is.
> Than using a dynamic lookup table, which is how I understood your
previous email about "scripts in the 1000 past blocks".
Ah, I didn't mean using a dynamic lookup. This was about the idea of jet
registration, where registered jets would be kept a count of for some
number of blocks (eg 1000) and dropped if they don't reach a threshold rate
of usage. A static lookup table would work for this, I agree.
> It would have to validate as well that the SCRIPT sub-section matches the
jet
Seems like a good idea.
> Adler32 seems a bit short though
You might be right. Certainly some more care would need to be taken in an
actual implementation than I've taken writing my back of the napkin idea
out ; )
> nothing prevents anyone from using a different SCRIPT subsection for a
particular Adler32 hash if they find a collision and can somehow convince
people to run their modified software.
Someone that can convince people to run their modified software can
*always* cause those people to chainsplit from the main chain, so I don't
think the above ideas are special in this regard.
>> it might not be worth doing it this way without a soft fork
> 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.
I'm saying something rather different actually. I don't think each
individual jet requires a softfork to be quite useful. What I meant by "it
might not be worth doing it this way without a soft fork" is that we
probably want to implement a soft fork to allow all jet scripts to have
reduced blockweight. However, once most nodes support that soft fork, new
individual jets do not need a softfork for the network to take advantage of
them. As I mused about above, even 10% of the network supporting a jet
standin for a medium length script could result in significant network
bandwidth savings. Different sections of the network could decide
individually what jets they want to support without needing the usual chaos
of a soft fork for each one, but of course the more the better for a
popular jet. There would be benefits for eventually soft forking such jets
in (to make them weigh even less based on implementation of optimized
validation functions), and real life usage of those jets could inform the
decisions around them. They could already be well tested in the wild before
being upgraded in a softfork.
> Yes, but that implies additional operations (and execution overhead),
increasing the costs to use jets, which makes it even less palatable to use
jets, *in addition to* the witness hack disincentivizing jets.
For the use of a single jet, this can be completely solved by that jet. All
the additional operations you're talking about only need to happen in a
general bitcoin script evaluator. But a jet evaluator can be hand optimized
for that jet, which could operate in exactly the the function-like way you
suggested, because it would actually be a function, under the hood.
> this helps jets compose more easily; if we want a SCRIPT that
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
constants table.
I think I see what you're saying about multiple jets composing together
easily. I think your idea about loading constants from their initial
positions has merit - basically function arguments that you can reference
by position rather than needing to arrange them in the right order on the
stack. Such is the existence of a stack-based language. I like the idea of
eg `c1` to `c26` paralleling the pushdata opcodes. The question I have is:
where would the constants table come from? Would it reference the original
positions of items on the witness stack?
On Thu, Mar 10, 2022 at 12:44 AM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
> Good morning Billy,
>
> > Hi ZmnSCPxj,
> >
> > > Just ask a bunch of fullnodes to add this 1Mb of extra ignored data
> 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 witness data do what would be needed here? Eg simply adding extra
> data onto the witness script that will remain unconsumed after successful
> execution of the script?
>
> I think we would want to have a cleanstack rule at some point (do not
> remember 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.
> >
> > > 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.
> >
> > > If a new jet can just be entered into some configuration file, how do
> you 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
> eventually. No coordination is needed. 100% of the network need not support
> a jet. Just some critical mass to get some benefit.
>
> 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
> strings of specific, static length
> >
> > Sorry, better than what exactly?
>
> 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
> would see the extra items on the stack after script execution, and would
> interpret them as an OP_JET call specifying that OP_JET should replace the
> witness items starting at index 0 with `1b5f03cf OP_JET`. It does this and
> then sends that along to the next hop.
>
> It would have to validate as well that the SCRIPT sub-section matches the
> jet, else I could pretend to be a non-jet-aware node and give you a SCRIPT
> sub-section that does not match the jet and would cause your validation to
> diverge from other nodes.
>
> Adler32 seems a bit short though, it seems to me that it may lead to two
> different 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
> using 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
> unnecessary data would be needed, but for jets that represent long scripts,
> the extra witness data could be well worth it (for the network).
> >
> > However, this extra data would be a disincentive to do transactions this
> way, even when its better for the network. So it might not be worth doing
> 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 (replaced
> with out-of-band script fragment transmission for nodes that don't support
> a particular jet).
>
> 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
> is 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. Hypothetically, you could imagine a jet script that uses an OP_LOOP
> jet be written as follows:
> >
> > 5 # Loop 5 times
> > 1 # Loop the next 1 operation
> > 3c1g14ad
> > OP_JET
> > OP_ADD # 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 script can't manipulate opcode calls), the jet *call* can still be
> represented as:
> >
> > OP_ADD
> > OP_ADD
> > OP_ADD
> > OP_ADD
> > OP_ADD
> >
> > which means all of the above replacement functionality would work just
> as well.
> >
> > 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
> implementing a single opcode like op_fold.
>
> Yes, that is certainly the case, and nothing really prevents us bringing
> "programming as compression" to its logical conclusion.
>
> > > To make jets more useful, we should redesign the language so that
> `OP_PUSH` 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.
>
> Yes, but that implies additional operations (and execution overhead),
> increasing 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
> really replace most of the `OP_PUSH` opcodes with variants that look up in
> a static 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
> constants table can be kept low.
>
> In particular, this helps jets compose more easily; if we want a SCRIPT
> that 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 constants table.
>
> Or something, anyway.
> This seems a fair amount of complexity here.
>
> Regards,
> ZmnSCPxj
>
[-- Attachment #2: Type: text/html, Size: 14081 bytes --]
next prev parent reply other threads:[~2022-03-11 14:11 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-03-07 23:35 ZmnSCPxj
2022-03-10 5:05 ` Billy Tetrud
2022-03-10 6:43 ` ZmnSCPxj
2022-03-11 14:11 ` Billy Tetrud [this message]
2022-03-16 15:38 ` ZmnSCPxj
2022-03-16 15:59 ` Billy Tetrud
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAGpPWDZwYE__YifZ0h7Bkftas6zN6Q7yOhB4rUAAwT0dcgYk7w@mail.gmail.com \
--to=billy.tetrud@gmail$(echo .)com \
--cc=ZmnSCPxj@protonmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox