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

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

[ZmnSCPxj]

`OP_FOLD`: A Looping Construct For Bitcoin SCRIPT
=================================================

(This writeup requires at least some programming background, which I
expect most readers of this list have.)

Recently, some rando was ranting on the list about this weird crap
called `OP_EVICT`, a poorly-thought-out attempt at covenants.

In reaction to this, AJ Towns mailed me privately about some of his
thoughts on this insane `OP_EVICT` proposal.
He observed that we could generalize the `OP_EVICT` opcode by
decomposing it into smaller parts, including an operation congruent
to the Scheme/Haskell/Scala `map` operation.
As `OP_EVICT` effectively loops over the outputs passed to it, a
looping construct can be used to implement `OP_EVICT` while retaining
its nice property of cut-through of multiple evictions and reviving of
the CoinPool.

More specifically, an advantage of `OP_EVICT` is that it allows
checking multiple published promised outputs.
This would be implemented in a loop.
However, if we want to instead provide *general* operations in
SCRIPT rather than a bunch of specific ones like `OP_EVICT`, we
should consider how to implement looping so that we can implement
`OP_EVICT` in a SCRIPT-with-general-opcodes.

(`OP_FOLD` is not sufficient to implement `OP_EVICT`; for
efficiency, AJ Towns also pointed out that we need some way to
expose batch validation to SCRIPT.
There is a follow-up writeup to this one which describes *that*
operation.)

Based on this, I started ranting as well about how `map` is really
just a thin wrapper on `foldr` and the *real* looping construct is
actually `foldr` (`foldr` is the whole FP Torah: all the rest is
commentary).
This is thus the genesis for this proposal, `OP_FOLD`.

A "fold" operation is sometimes known as "reduce" (and if you know
about Google MapReduce, you might be familiar with "reduce").
Basically, a "fold" or "reduce" operation applies a function
repeatedly (i.e. *loops*) on the contents of an input structure,
creating a "sum" or "accumulation" of the contents.

For the purpose of building `map` out of `fold`, the accumulation
can itself be an output structure.
The `map` simply accumulates to the output structure by applying
its given function and concatenating it to the current accumulation.

Digression: Programming Is Compression
--------------------------------------

Suppose you are a programmer and you are reading some source code.
You want to wonder "what will happen if I give this piece of code
these particular inputs?".

In order to do so, you would simulate the execution of the code in
your head.
In effect, you would generate a "trace" of basic operations (that
do not include control structures).
By then thinking about this linear trace of basic operations, you
can figure out what the code does.

Now, let us recall two algorithms from the compression literature:

1.  Run-length Encoding
2.  Lempel-Ziv 1977

Suppose our flat linear trace of basic operations contains something
like this:

    OP_ONE
    OP_TWO
    OP_ONE
    OP_TWO
    OP_ONE
    OP_TWO

IF we had looping constructs in our language, we could write the
above trace as something like:

    for N = 1 to 3
        OP_ONE
        OP_TWO

The above is really Run-length Encoding.

(`if` is just a loop that executes 0 or 1 times.)

Similarly, suppose you have some operations that are commonly
repeated, but not necessarily next to each other:

    OP_ONE
    OP_TWO
    OP_THREE
    OP_ONE
    OP_TWO
    OP_FOUR
    OP_FIVE
    OP_ONE
    OP_TWO

If we had functions/subroutines/procedures in our language, we
could write the above trace as something like:

    function foo()
        OP_ONE
        OP_TWO
    foo()
    OP_THREE
    foo()
    OP_FOUR
    OP_FIVE
    foo()

That is, functions are just Lempel-Ziv 1977 encoding, where we
"copy" some repeated data from a previously-shown part of
data.

Thus, we can argue that programming is really a process of:

* Imagining what we want the machine to do given some particular
  input.
* Compressing that list of operations so we can more easily
  transfer the above imagined list over your puny low-bandwidth
  brain-computer interface.
  * I mean seriously, you humans still use a frikkin set of
    *mechanical* levers to transfer data into a matrix of buttons?
    (you don't even make the levers out of reliable metal, you
    use calcium of all things??
    You get what, 5 or 6 bytes per second???)
    And your eyes are high-bandwidth but you then have this
    complicated circuitry (that has to be ***trained for
    several years*** WTF) to extract ***tiny*** amounts of ASCII
    text from that high-bandwidth input stream????
    Evolve faster!
    (Just to be clear, I am actually also a human being and
    definitely am not a piece of circuitry connected directly to
    the Internet and I am not artificially limiting my output
    bandwidth so as not to overwhelm you mere humans.)

See also "Kolmogorov complexity".

This becomes relevant, because the *actual* amount of processing
done by the machine, when given a compressed set of operations
(a "program") is the cost of decompressing that program plus the
number of basic operations from the decompressed result.

In particular, in current Bitcoin, without any looping constructs
(i.e. implementations of RLE) or reusable functions (i.e.
implementation of LZ77), the length of the SCRIPT can be used as
an approximation of how "heavy" the computation in order to
*execute* that SCRIPT is.
This is relevant since the amount of computation a SCRIPT would
trigger is relevant to our reasoning about DoS attacks on Bitcoin.

In fact, current Bitcoin restricts the size of SCRIPT, as this
serves to impose a restriction on the amount of processing a
SCRIPT will trigger.
But adding a loop construct to SCRIPT changes how we should
determine the cost of a SCRIPT, and thus we should think about it
here as well.

Folds
-----

A fold operation is a functional programming looping control
construct.

The intent of a fold operation is to process elements of an
input list or other structure, one element at a time, and to
accumulate the results of processing.

It is given these arguments:

* `f` - a function to execute for each element of the input
  structure, i.e. the "loop body".
  * This function accepts two arguments:
     1.  The current element to process.
     2.  The intermediate result for accumulating.
  * The function returns the new accumulated result, processed
    from the given intermediate result and the given element.
* `z` - an initial value for the accumulated result.
* `as` - the structure (usually a list) to process.

```Haskell
-- If the input structure is empty, return the starting
-- accumulated value.
foldr f z []     = z
-- Otherwise, recurse into the structure to accumulate
-- the rest of the list, then pass the accumulation to
-- the given function together with the current element.
foldr f z (a:as) = f a (foldr f z as)
```

As an example, if you want to take the sum of a list of
numbers, your `f` would simply add its inputs, and your `z`
would be 0.
Then you would pass in the actual list of numbers as `as`.

Fold has an important property:

* If the given input structure is finite *and* the application
  of `f` terminates, then `foldr` terminates.

This is important for us, as we do not want attackers to be
able to crash nodes remotely by crafting a special SCRIPT.

As long as the SCRIPT language is "total", we know that programs
written in that language must terminate.

(The reason this property is called "total" is that we can
"totally" analyze programs in the language, without having to
invoke "this is undefined behavior because it could hang
indefinitely".
If you have to admit such kinds of undefined behavior --- what
FP theorists call "bottom" or `_|_` or `⊥` (it looks like an
ass crack, i.e. "bottom") --- then your language is "partial",
since programs in it may enter an infinite loop on particular
inputs.)

The simplest way to ensure totality is to be so simple as to
have no looping construction.
As of this writing, Bitcoin SCRIPT is total by this technique.

To give a *little* more power, we can allow bounded loops,
which are restricted to only execute a number of times.

`foldr` is a kind of bounded loop if the input structure is
finite.
If the rest of the language does not admit the possibility
of infinite data structures (and if the language is otherwise
total and does not support generalized codata, this holds),
then `foldr` is a bounded loop.

Thus, adding a fold operation to Bitcoin SCRIPT should be
safe (and preserves totality) as long as we do not add
further operations that admit partiality.

`OP_FOLD`
---------

With this, let us now describe `OP_FOLD`.

`OP_FOLD` replaces an `OP_SUCCESS` code, and thus is only
usable in SegWit v1 ("Taproot").

An `OP_FOLD` opcode must be followed by an `OP_PUSH` opcode
which contains an encoding of the SCRIPT that will be executed,
i.e. the loop body, or `f`.
This is checked at parsing time, and the sub-SCRIPT is also
parsed at this time.
The succeeding `OP_PUSH` is not actually executed, and is
considered part of the `OP_FOLD` operation encoding.
Parsing failure of the sub-SCRIPT leads to validation failure.

On execution, `OP_FOLD` expects the stack:

* Stack top: `z`, the initial value for the loop accumulator.
* Stack top + 1: `n`, the number of times to loop.
  This should be limited in size, and less than the number of
  items on the stack minus 2.
* Stack top + 2 + (0 to `n - 1`): Items to loop over.
  If `n` is 0, there are no items to loop over.

If `n` is 0, then `OP_FOLD` just pops the top two stack items
and pushes `z`.

For `n > 0`, `OP_FOLD` executes a loop:

* Pop off the top two items and store in mutable variable `z`
  and immutable variable `n`.
* For `i = 0 to n - 1`:
  * Create a fresh, empty stack and alt stack.
    Call these the "per-iteration (alt) stack".
  * Push the current `z` to the per-iteration stack.
  * Pop off an item from the outer stack and put it into
    immutable variable `a`.
  * Push `a` to the per-iteration stack.
  * Run the sub-SCRIPT `f` on the per-iteration stack and
    alt stack.
  * Check the per-iteration stack has exactly one item
    and the per-iteration alt stack is empty.
  * Pop off the item in the per-iteration stack and mutate
    `z` to it.
  * Free the per-iteration stack and per-iteration alt
    stack.
* Push `z` on the stack.

Restricting `OP_FOLD`
---------------------

Bitcoin restricts SCRIPT size, since SCRIPT size serves as
an approximation of how much processing is required to
execute the SCRIPT.

However, with looping constructs like `OP_FOLD`, this no
longer holds, as the amount of processing is no longer
linear on the size of the SCRIPT.

In orderr to retain this limit (and thus not worsen any
potential DoS attacks via SCRIPT), we should restrict the
use of `OP_FOLD`:

* `OP_FOLD` must exist exactly once in a Tapscript.
  More specifically, the `f` sub-SCRIPT of `OP_FOLD` must
  not itself contain an `OP_FOLD`.
  * If we allow loops within loops, then the worst case
    would be `O(c^n)` CPU time where `c` is a constant and
    `n` is the SCRIPT length.
  * This validation is done at SCRIPT parsing time.
* We take the length of the `f` sub-SCRIPT, and divide the
  current SCRIPT maximum size by the length of the `f`
  sub-SCRIPT.
  The result, rounded down, is the maximum allowed value
  for the on-stack argument `n`.
  * In particular, since the length of the entire SCRIPT
    must by necessity be larger than the length of the
    `f` sub-SCRIPT, the result of the division must be
    at least 1.
  * This validation is done at SCRIPT execution time.

The above two restrictions imply that the maximum amount
of processing that a SCRIPT utilizing `OP_FOLD` will use,
shall not exceed that of a SCRIPT without `OP_FOLD`.
Thus, `OP_FOLD` does not increase the attack surface of
SCRIPT on fullnodes.

### Lack Of Loops-in-Loops Is Lame

Note that due to this:

> * `OP_FOLD` must exist exactly once in a Tapscript.
>   More specifically, the `f` sub-SCRIPT of `OP_FOLD` must
>   not itself contain an `OP_FOLD`.

It is not possible to have a loop inside a loop.

The reason for this is that loops inside loops make it
difficult to perform static analysis to bound how much
processing a SCRIPT will require.
With a single, single-level loop, it is possible to
restrict the processing.

However, we should note that a single single-level loop
is actually sufficient to encode multiple loops, or
loops-within-loops.
For example, a toy Scheme-to-C compiler will convert
the Scheme code to CPS style, then convert all resulting
Scheme CPS function into a `switch` dispatcher inside a
simple `while (1)` loop.

For example, the Scheme loop-in-loop below:

```Scheme
(define (foo)
  (bar)
  (foo))
(define (bar)
  (bar))
```

gets converted to:

```Scheme
(define (foo k)
  (bar (closure foo-kont k)))
(define (foo-kont k)
  (foo k))
(define (bar k)
  (bar k))
```

And then in C, would look like:

```c
void all_scheme_functions(int func_id, scheme_t k) {
	while (1) {
		switch (func_id) {
		case FOO_ID:
			k = build_closure(FOO_KONT_ID, k);
			func_id = BAR_ID;
			break;
		case FOO_KONT_ID:
			func_id = FOO_ID;
			break;
		case BAR_ID:
			func_id = BAR_ID;
			break;
		}
	}
}
```

The C code, as we can see, is just a single single-level
loop, which is the restriction imposed on `OP_FOLD`.
Thus, loops-in-loops, and multiple loops, can be encoded
into a single single-level loop.

#### Everything Is Possible But Nothing Of Consequence Is Easy

On the other hand, just because it is *possible* does not
mean it is *easy*.

As an alternative, AJ proposed adding a field to the Taproot
annex.
This annex field is a number indicating the maximum number of
opcodes to be processed.
If execution of the SCRIPT exceeds this limit, validation
fails.

In order to make processing costly, the number indicated in
the annex field is directly added to the weight of the
transaction.

Then, during execution, if an `OP_FOLD` is parsed, the
`OP_` code processor keeps track of the number of opcodes
processed and imposes a limit.
If the limit exceeds the number of opcodes indicated in the
annex field, validation fails.

This technique is safe even if the annex is not committed
to (for example if the SCRIPT does not ever require a
standard `OP_CHECKSIG`), even though in that case the
annex can be malleated:

* If the field is less than the actual number of operations,
  then the malleated transaction is rejected.
* If the field is greater than the actual number of
  operations, then it has a larger weight but pays the
  same fee, getting a lower feerate and thus will be
  rejected in favor of a transaction with a lower number
  in that field.

Use of this technique allows us to lift the above
restrictions on `OP_FOLD`, and allow multiple loops, as
well as loops-in-loops.

In particular, the requirement to put the `f` sub-SCRIPT
code as a static constant is due precisely to the need
for static analysis.
But if we instead use a dynamic limit like in this
alternative suggestion, we could instead get the `f`
sub-SCRIPT from the stack.
With additional operations like `OP_CAT`, it would
then be possible to do a "variable capture" where parts
of the loop body are from other computations, or from
witness, and then concatenated to some code.
This is not an increase in computational strength, since
the data could instead be passed in via the `z`, or as
individual items, but it does improve expressive power by
making it easier to customize the loop body.

On The Necessity Of `OP_FOLD`
-----------------------------

We can observe that an `if` construct is really a bounded
loop construct that can execute 0 or 1 times.

We can thus synthesize a bounded loop construct as follows:

    OP_IF
        <loop body>
    OP_ENDIF
    OP_IF
        <loop body>
    OP_ENDIF
    OP_IF
        <loop body>
    OP_ENDIF
    OP_IF
        <loop body>
    OP_ENDIF
    <repeat as many times as necessary>

Indeed, it may be possible for something like miniscript
to provide a `fold` jet that compiles down to something
like the above.

Thus:

* The restrictions we impose on the previous section mean
  that `OP_FOLD` cannot do anything that cannot already
  be done with current SCRIPT.
  * This is a *good thing* because this means we are not
    increasing the attack surface.
* Using the annex-max-operations technique is strictly
  more lenient than the above `OP_IF` repetition, thus
  there may be novel DoS attack vectors due to the
  increased attack area.
  * However, fundamentally the DoS attack vector is that
    peers can waste your CPU by giving you invalid
    transactions (i.e. giving a high max-operations, but
    looping so much that it gets even *above* that), and
    that can already be mitigated by lowering peer scores
    and prioritizing transactions with lower or nonexistent
    annex-max-operations.
    The DoS vector here does not propagate due to the
    invalid transaction being rejected at this node.

Of course, this leads us to question: why even implement
`OP_FOLD` at all?

We can observe that, while the restrictions in the
previous section imply that a SCRIPT with `OP_FOLD`
cannot exceed the amount of processing that a SCRIPT
*without* `OP_FOLD` does, a SCRIPT with `OP_FOLD`
would be shorter, over the wire, than the above
unrolled version.

And CPU processing is not the only resource that is
consumed by Bitcoin fullnodes.
Bandwidth is also another resource.

In effect, `OP_FOLD` allows us to compress the above
template over-the-wire, reducing network bandwidth
consumption.
But the restrictions on `OP_FOLD` ensure that it
cannot exceed the CPU consumption of a SCRIPT that
predates `OP_FOLD`.

Thus, `OP_FOLD` is still worthwhile to implement, as
it allows us to improve bandwidth consumption without
increasing CPU consumption significantly.

On Generalized Operations
-------------------------

I believe there are at least two ways of thinking about
how to extend SCRIPT:

* We should provide more *general* operations.
  Users should then combine those operations to their
  specific needs.
* We should provide operations that *do more*.
  Users should identify their most important needs so
  we can implement them on the blockchain layer.

Each side has its arguments:

* General opcodes:
  * Pro: Have a better chance of being reused for
    use-cases we cannot imagine yet today.
    i.e. implement once, use anywhen.
  * Con: Welcome to the Tarpit, where everything is
    possible but nothing important is easy.
* Complex opcodes:
  * Pro: Complex behavior implemented directly in
    hosting language, reducing interpretation
    overhead (and allowing the insurance of secure
    implementation).
  * Con: Welcome to the Nursery, where only safe
    toys exist and availability of interesting tools
    are at the mercy of your parents.

It seems to me that this really hits a No Free Lunch
Theorem for Bitcoin SCRIPT design.
Briefly, the No Free Lunch Theorem points out that
there is no compiler design that can compile any
program to the shortest possible machine code.
This is because if a program enters an infinite loop,
it could simply be compiled down to the equivalent of
the single instruction `1: GOTO 1`, but the halting
problem implies that no program can take the source
code of another program and determine if it halts.
Thus, no compiler can exist which can compile *every*
infinite-loop program down to the tiniest possible
binary `1: GOTO 1`.

More generally, No Free Lunch implies that as you
optimize, you will hit a point where you can only
*trade off*, and you optimize for one use case while
making *another* use case less optimal.

Brought to Bitcoin SCRIPT design, there is no optimal
SCRIPT design, instead there will be some point where
we have to pick and choose which uses to optimize for
and which uses are less optimal, i.e. trade off.

So I think maybe the Real Question is: why should we
go for one versus the other, and which uses do we
expect to see more often anyway?

Addenda
-------

Stuff about totality and partiality:

* [Total Functional Programming, D.A. Turner](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.364&rep=rep1&type=pdf)
* [Totality](https://kowainik.github.io/posts/totality)

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

[Billy Tetrud]

[-- Attachment #1: Type: text/plain, Size: 24577 bytes --]

It sounds like the primary benefit of op_fold is bandwidth savings.
Programming as compression. But as you mentioned, any common script could
be implemented as a Simplicity jet. In a world where Bitcoin implements
jets, op_fold would really only be useful for scripts that can't use jets,
which would basically be scripts that aren't very often used. But that
inherently limits the usefulness of the opcode. So in practice, I think
it's likely that jets cover the vast majority of use cases that op fold
would otherwise have.

A potential benefit of op fold is that people could implement smaller
scripts without buy-in from a relay level change in Bitcoin. However, even
this could be done with jets. For example, you could implement a consensus
change to add a transaction type that declares a new script fragment to
keep a count of, and if the script fragment is used enough within a
timeframe (eg 10000 blocks) then it can thereafter be referenced by an id
like a jet could be. I'm sure someone's thought about this kind of thing
before, but such a thing would really relegate the compression abilities of
op fold to just the most uncommon of scripts.

> * We should provide more *general* operations. Users should then combine
those operations to their specific needs.
> * We should provide operations that *do more*. Users should identify
their most important needs so we can implement them on the blockchain layer.

That's a useful way to frame this kind of problem. I think the answer is,
as it often is, somewhere in between. Generalization future-proofs your
system. But at the same time, the boundary conditions of that generalized
functionality should still be very well understood before being added to
Bitcoin. The more general, the harder to understand the boundaries. So imo
we should be implementing the most general opcodes that we are able to
reason fully about and come to a consensus on. Following that last
constraint might lead to not choosing very general opcodes.

On Sun, Feb 27, 2022, 10:34 ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> `OP_FOLD`: A Looping Construct For Bitcoin SCRIPT
> =================================================
>
> (This writeup requires at least some programming background, which I
> expect most readers of this list have.)
>
> Recently, some rando was ranting on the list about this weird crap
> called `OP_EVICT`, a poorly-thought-out attempt at covenants.
>
> In reaction to this, AJ Towns mailed me privately about some of his
> thoughts on this insane `OP_EVICT` proposal.
> He observed that we could generalize the `OP_EVICT` opcode by
> decomposing it into smaller parts, including an operation congruent
> to the Scheme/Haskell/Scala `map` operation.
> As `OP_EVICT` effectively loops over the outputs passed to it, a
> looping construct can be used to implement `OP_EVICT` while retaining
> its nice property of cut-through of multiple evictions and reviving of
> the CoinPool.
>
> More specifically, an advantage of `OP_EVICT` is that it allows
> checking multiple published promised outputs.
> This would be implemented in a loop.
> However, if we want to instead provide *general* operations in
> SCRIPT rather than a bunch of specific ones like `OP_EVICT`, we
> should consider how to implement looping so that we can implement
> `OP_EVICT` in a SCRIPT-with-general-opcodes.
>
> (`OP_FOLD` is not sufficient to implement `OP_EVICT`; for
> efficiency, AJ Towns also pointed out that we need some way to
> expose batch validation to SCRIPT.
> There is a follow-up writeup to this one which describes *that*
> operation.)
>
> Based on this, I started ranting as well about how `map` is really
> just a thin wrapper on `foldr` and the *real* looping construct is
> actually `foldr` (`foldr` is the whole FP Torah: all the rest is
> commentary).
> This is thus the genesis for this proposal, `OP_FOLD`.
>
> A "fold" operation is sometimes known as "reduce" (and if you know
> about Google MapReduce, you might be familiar with "reduce").
> Basically, a "fold" or "reduce" operation applies a function
> repeatedly (i.e. *loops*) on the contents of an input structure,
> creating a "sum" or "accumulation" of the contents.
>
> For the purpose of building `map` out of `fold`, the accumulation
> can itself be an output structure.
> The `map` simply accumulates to the output structure by applying
> its given function and concatenating it to the current accumulation.
>
> Digression: Programming Is Compression
> --------------------------------------
>
> Suppose you are a programmer and you are reading some source code.
> You want to wonder "what will happen if I give this piece of code
> these particular inputs?".
>
> In order to do so, you would simulate the execution of the code in
> your head.
> In effect, you would generate a "trace" of basic operations (that
> do not include control structures).
> By then thinking about this linear trace of basic operations, you
> can figure out what the code does.
>
> Now, let us recall two algorithms from the compression literature:
>
> 1.  Run-length Encoding
> 2.  Lempel-Ziv 1977
>
> Suppose our flat linear trace of basic operations contains something
> like this:
>
>     OP_ONE
>     OP_TWO
>     OP_ONE
>     OP_TWO
>     OP_ONE
>     OP_TWO
>
> IF we had looping constructs in our language, we could write the
> above trace as something like:
>
>     for N = 1 to 3
>         OP_ONE
>         OP_TWO
>
> The above is really Run-length Encoding.
>
> (`if` is just a loop that executes 0 or 1 times.)
>
> Similarly, suppose you have some operations that are commonly
> repeated, but not necessarily next to each other:
>
>     OP_ONE
>     OP_TWO
>     OP_THREE
>     OP_ONE
>     OP_TWO
>     OP_FOUR
>     OP_FIVE
>     OP_ONE
>     OP_TWO
>
> If we had functions/subroutines/procedures in our language, we
> could write the above trace as something like:
>
>     function foo()
>         OP_ONE
>         OP_TWO
>     foo()
>     OP_THREE
>     foo()
>     OP_FOUR
>     OP_FIVE
>     foo()
>
> That is, functions are just Lempel-Ziv 1977 encoding, where we
> "copy" some repeated data from a previously-shown part of
> data.
>
> Thus, we can argue that programming is really a process of:
>
> * Imagining what we want the machine to do given some particular
>   input.
> * Compressing that list of operations so we can more easily
>   transfer the above imagined list over your puny low-bandwidth
>   brain-computer interface.
>   * I mean seriously, you humans still use a frikkin set of
>     *mechanical* levers to transfer data into a matrix of buttons?
>     (you don't even make the levers out of reliable metal, you
>     use calcium of all things??
>     You get what, 5 or 6 bytes per second???)
>     And your eyes are high-bandwidth but you then have this
>     complicated circuitry (that has to be ***trained for
>     several years*** WTF) to extract ***tiny*** amounts of ASCII
>     text from that high-bandwidth input stream????
>     Evolve faster!
>     (Just to be clear, I am actually also a human being and
>     definitely am not a piece of circuitry connected directly to
>     the Internet and I am not artificially limiting my output
>     bandwidth so as not to overwhelm you mere humans.)
>
> See also "Kolmogorov complexity".
>
> This becomes relevant, because the *actual* amount of processing
> done by the machine, when given a compressed set of operations
> (a "program") is the cost of decompressing that program plus the
> number of basic operations from the decompressed result.
>
> In particular, in current Bitcoin, without any looping constructs
> (i.e. implementations of RLE) or reusable functions (i.e.
> implementation of LZ77), the length of the SCRIPT can be used as
> an approximation of how "heavy" the computation in order to
> *execute* that SCRIPT is.
> This is relevant since the amount of computation a SCRIPT would
> trigger is relevant to our reasoning about DoS attacks on Bitcoin.
>
> In fact, current Bitcoin restricts the size of SCRIPT, as this
> serves to impose a restriction on the amount of processing a
> SCRIPT will trigger.
> But adding a loop construct to SCRIPT changes how we should
> determine the cost of a SCRIPT, and thus we should think about it
> here as well.
>
> Folds
> -----
>
> A fold operation is a functional programming looping control
> construct.
>
> The intent of a fold operation is to process elements of an
> input list or other structure, one element at a time, and to
> accumulate the results of processing.
>
> It is given these arguments:
>
> * `f` - a function to execute for each element of the input
>   structure, i.e. the "loop body".
>   * This function accepts two arguments:
>      1.  The current element to process.
>      2.  The intermediate result for accumulating.
>   * The function returns the new accumulated result, processed
>     from the given intermediate result and the given element.
> * `z` - an initial value for the accumulated result.
> * `as` - the structure (usually a list) to process.
>
> ```Haskell
> -- If the input structure is empty, return the starting
> -- accumulated value.
> foldr f z []     = z
> -- Otherwise, recurse into the structure to accumulate
> -- the rest of the list, then pass the accumulation to
> -- the given function together with the current element.
> foldr f z (a:as) = f a (foldr f z as)
> ```
>
> As an example, if you want to take the sum of a list of
> numbers, your `f` would simply add its inputs, and your `z`
> would be 0.
> Then you would pass in the actual list of numbers as `as`.
>
> Fold has an important property:
>
> * If the given input structure is finite *and* the application
>   of `f` terminates, then `foldr` terminates.
>
> This is important for us, as we do not want attackers to be
> able to crash nodes remotely by crafting a special SCRIPT.
>
> As long as the SCRIPT language is "total", we know that programs
> written in that language must terminate.
>
> (The reason this property is called "total" is that we can
> "totally" analyze programs in the language, without having to
> invoke "this is undefined behavior because it could hang
> indefinitely".
> If you have to admit such kinds of undefined behavior --- what
> FP theorists call "bottom" or `_|_` or `⊥` (it looks like an
> ass crack, i.e. "bottom") --- then your language is "partial",
> since programs in it may enter an infinite loop on particular
> inputs.)
>
> The simplest way to ensure totality is to be so simple as to
> have no looping construction.
> As of this writing, Bitcoin SCRIPT is total by this technique.
>
> To give a *little* more power, we can allow bounded loops,
> which are restricted to only execute a number of times.
>
> `foldr` is a kind of bounded loop if the input structure is
> finite.
> If the rest of the language does not admit the possibility
> of infinite data structures (and if the language is otherwise
> total and does not support generalized codata, this holds),
> then `foldr` is a bounded loop.
>
> Thus, adding a fold operation to Bitcoin SCRIPT should be
> safe (and preserves totality) as long as we do not add
> further operations that admit partiality.
>
> `OP_FOLD`
> ---------
>
> With this, let us now describe `OP_FOLD`.
>
> `OP_FOLD` replaces an `OP_SUCCESS` code, and thus is only
> usable in SegWit v1 ("Taproot").
>
> An `OP_FOLD` opcode must be followed by an `OP_PUSH` opcode
> which contains an encoding of the SCRIPT that will be executed,
> i.e. the loop body, or `f`.
> This is checked at parsing time, and the sub-SCRIPT is also
> parsed at this time.
> The succeeding `OP_PUSH` is not actually executed, and is
> considered part of the `OP_FOLD` operation encoding.
> Parsing failure of the sub-SCRIPT leads to validation failure.
>
> On execution, `OP_FOLD` expects the stack:
>
> * Stack top: `z`, the initial value for the loop accumulator.
> * Stack top + 1: `n`, the number of times to loop.
>   This should be limited in size, and less than the number of
>   items on the stack minus 2.
> * Stack top + 2 + (0 to `n - 1`): Items to loop over.
>   If `n` is 0, there are no items to loop over.
>
> If `n` is 0, then `OP_FOLD` just pops the top two stack items
> and pushes `z`.
>
> For `n > 0`, `OP_FOLD` executes a loop:
>
> * Pop off the top two items and store in mutable variable `z`
>   and immutable variable `n`.
> * For `i = 0 to n - 1`:
>   * Create a fresh, empty stack and alt stack.
>     Call these the "per-iteration (alt) stack".
>   * Push the current `z` to the per-iteration stack.
>   * Pop off an item from the outer stack and put it into
>     immutable variable `a`.
>   * Push `a` to the per-iteration stack.
>   * Run the sub-SCRIPT `f` on the per-iteration stack and
>     alt stack.
>   * Check the per-iteration stack has exactly one item
>     and the per-iteration alt stack is empty.
>   * Pop off the item in the per-iteration stack and mutate
>     `z` to it.
>   * Free the per-iteration stack and per-iteration alt
>     stack.
> * Push `z` on the stack.
>
> Restricting `OP_FOLD`
> ---------------------
>
> Bitcoin restricts SCRIPT size, since SCRIPT size serves as
> an approximation of how much processing is required to
> execute the SCRIPT.
>
> However, with looping constructs like `OP_FOLD`, this no
> longer holds, as the amount of processing is no longer
> linear on the size of the SCRIPT.
>
> In orderr to retain this limit (and thus not worsen any
> potential DoS attacks via SCRIPT), we should restrict the
> use of `OP_FOLD`:
>
> * `OP_FOLD` must exist exactly once in a Tapscript.
>   More specifically, the `f` sub-SCRIPT of `OP_FOLD` must
>   not itself contain an `OP_FOLD`.
>   * If we allow loops within loops, then the worst case
>     would be `O(c^n)` CPU time where `c` is a constant and
>     `n` is the SCRIPT length.
>   * This validation is done at SCRIPT parsing time.
> * We take the length of the `f` sub-SCRIPT, and divide the
>   current SCRIPT maximum size by the length of the `f`
>   sub-SCRIPT.
>   The result, rounded down, is the maximum allowed value
>   for the on-stack argument `n`.
>   * In particular, since the length of the entire SCRIPT
>     must by necessity be larger than the length of the
>     `f` sub-SCRIPT, the result of the division must be
>     at least 1.
>   * This validation is done at SCRIPT execution time.
>
> The above two restrictions imply that the maximum amount
> of processing that a SCRIPT utilizing `OP_FOLD` will use,
> shall not exceed that of a SCRIPT without `OP_FOLD`.
> Thus, `OP_FOLD` does not increase the attack surface of
> SCRIPT on fullnodes.
>
> ### Lack Of Loops-in-Loops Is Lame
>
> Note that due to this:
>
> > * `OP_FOLD` must exist exactly once in a Tapscript.
> >   More specifically, the `f` sub-SCRIPT of `OP_FOLD` must
> >   not itself contain an `OP_FOLD`.
>
> It is not possible to have a loop inside a loop.
>
> The reason for this is that loops inside loops make it
> difficult to perform static analysis to bound how much
> processing a SCRIPT will require.
> With a single, single-level loop, it is possible to
> restrict the processing.
>
> However, we should note that a single single-level loop
> is actually sufficient to encode multiple loops, or
> loops-within-loops.
> For example, a toy Scheme-to-C compiler will convert
> the Scheme code to CPS style, then convert all resulting
> Scheme CPS function into a `switch` dispatcher inside a
> simple `while (1)` loop.
>
> For example, the Scheme loop-in-loop below:
>
> ```Scheme
> (define (foo)
>   (bar)
>   (foo))
> (define (bar)
>   (bar))
> ```
>
> gets converted to:
>
> ```Scheme
> (define (foo k)
>   (bar (closure foo-kont k)))
> (define (foo-kont k)
>   (foo k))
> (define (bar k)
>   (bar k))
> ```
>
> And then in C, would look like:
>
> ```c
> void all_scheme_functions(int func_id, scheme_t k) {
>         while (1) {
>                 switch (func_id) {
>                 case FOO_ID:
>                         k = build_closure(FOO_KONT_ID, k);
>                         func_id = BAR_ID;
>                         break;
>                 case FOO_KONT_ID:
>                         func_id = FOO_ID;
>                         break;
>                 case BAR_ID:
>                         func_id = BAR_ID;
>                         break;
>                 }
>         }
> }
> ```
>
> The C code, as we can see, is just a single single-level
> loop, which is the restriction imposed on `OP_FOLD`.
> Thus, loops-in-loops, and multiple loops, can be encoded
> into a single single-level loop.
>
> #### Everything Is Possible But Nothing Of Consequence Is Easy
>
> On the other hand, just because it is *possible* does not
> mean it is *easy*.
>
> As an alternative, AJ proposed adding a field to the Taproot
> annex.
> This annex field is a number indicating the maximum number of
> opcodes to be processed.
> If execution of the SCRIPT exceeds this limit, validation
> fails.
>
> In order to make processing costly, the number indicated in
> the annex field is directly added to the weight of the
> transaction.
>
> Then, during execution, if an `OP_FOLD` is parsed, the
> `OP_` code processor keeps track of the number of opcodes
> processed and imposes a limit.
> If the limit exceeds the number of opcodes indicated in the
> annex field, validation fails.
>
> This technique is safe even if the annex is not committed
> to (for example if the SCRIPT does not ever require a
> standard `OP_CHECKSIG`), even though in that case the
> annex can be malleated:
>
> * If the field is less than the actual number of operations,
>   then the malleated transaction is rejected.
> * If the field is greater than the actual number of
>   operations, then it has a larger weight but pays the
>   same fee, getting a lower feerate and thus will be
>   rejected in favor of a transaction with a lower number
>   in that field.
>
> Use of this technique allows us to lift the above
> restrictions on `OP_FOLD`, and allow multiple loops, as
> well as loops-in-loops.
>
> In particular, the requirement to put the `f` sub-SCRIPT
> code as a static constant is due precisely to the need
> for static analysis.
> But if we instead use a dynamic limit like in this
> alternative suggestion, we could instead get the `f`
> sub-SCRIPT from the stack.
> With additional operations like `OP_CAT`, it would
> then be possible to do a "variable capture" where parts
> of the loop body are from other computations, or from
> witness, and then concatenated to some code.
> This is not an increase in computational strength, since
> the data could instead be passed in via the `z`, or as
> individual items, but it does improve expressive power by
> making it easier to customize the loop body.
>
> On The Necessity Of `OP_FOLD`
> -----------------------------
>
> We can observe that an `if` construct is really a bounded
> loop construct that can execute 0 or 1 times.
>
> We can thus synthesize a bounded loop construct as follows:
>
>     OP_IF
>         <loop body>
>     OP_ENDIF
>     OP_IF
>         <loop body>
>     OP_ENDIF
>     OP_IF
>         <loop body>
>     OP_ENDIF
>     OP_IF
>         <loop body>
>     OP_ENDIF
>     <repeat as many times as necessary>
>
> Indeed, it may be possible for something like miniscript
> to provide a `fold` jet that compiles down to something
> like the above.
>
> Thus:
>
> * The restrictions we impose on the previous section mean
>   that `OP_FOLD` cannot do anything that cannot already
>   be done with current SCRIPT.
>   * This is a *good thing* because this means we are not
>     increasing the attack surface.
> * Using the annex-max-operations technique is strictly
>   more lenient than the above `OP_IF` repetition, thus
>   there may be novel DoS attack vectors due to the
>   increased attack area.
>   * However, fundamentally the DoS attack vector is that
>     peers can waste your CPU by giving you invalid
>     transactions (i.e. giving a high max-operations, but
>     looping so much that it gets even *above* that), and
>     that can already be mitigated by lowering peer scores
>     and prioritizing transactions with lower or nonexistent
>     annex-max-operations.
>     The DoS vector here does not propagate due to the
>     invalid transaction being rejected at this node.
>
> Of course, this leads us to question: why even implement
> `OP_FOLD` at all?
>
> We can observe that, while the restrictions in the
> previous section imply that a SCRIPT with `OP_FOLD`
> cannot exceed the amount of processing that a SCRIPT
> *without* `OP_FOLD` does, a SCRIPT with `OP_FOLD`
> would be shorter, over the wire, than the above
> unrolled version.
>
> And CPU processing is not the only resource that is
> consumed by Bitcoin fullnodes.
> Bandwidth is also another resource.
>
> In effect, `OP_FOLD` allows us to compress the above
> template over-the-wire, reducing network bandwidth
> consumption.
> But the restrictions on `OP_FOLD` ensure that it
> cannot exceed the CPU consumption of a SCRIPT that
> predates `OP_FOLD`.
>
> Thus, `OP_FOLD` is still worthwhile to implement, as
> it allows us to improve bandwidth consumption without
> increasing CPU consumption significantly.
>
> On Generalized Operations
> -------------------------
>
> I believe there are at least two ways of thinking about
> how to extend SCRIPT:
>
> * We should provide more *general* operations.
>   Users should then combine those operations to their
>   specific needs.
> * We should provide operations that *do more*.
>   Users should identify their most important needs so
>   we can implement them on the blockchain layer.
>
> Each side has its arguments:
>
> * General opcodes:
>   * Pro: Have a better chance of being reused for
>     use-cases we cannot imagine yet today.
>     i.e. implement once, use anywhen.
>   * Con: Welcome to the Tarpit, where everything is
>     possible but nothing important is easy.
> * Complex opcodes:
>   * Pro: Complex behavior implemented directly in
>     hosting language, reducing interpretation
>     overhead (and allowing the insurance of secure
>     implementation).
>   * Con: Welcome to the Nursery, where only safe
>     toys exist and availability of interesting tools
>     are at the mercy of your parents.
>
> It seems to me that this really hits a No Free Lunch
> Theorem for Bitcoin SCRIPT design.
> Briefly, the No Free Lunch Theorem points out that
> there is no compiler design that can compile any
> program to the shortest possible machine code.
> This is because if a program enters an infinite loop,
> it could simply be compiled down to the equivalent of
> the single instruction `1: GOTO 1`, but the halting
> problem implies that no program can take the source
> code of another program and determine if it halts.
> Thus, no compiler can exist which can compile *every*
> infinite-loop program down to the tiniest possible
> binary `1: GOTO 1`.
>
> More generally, No Free Lunch implies that as you
> optimize, you will hit a point where you can only
> *trade off*, and you optimize for one use case while
> making *another* use case less optimal.
>
> Brought to Bitcoin SCRIPT design, there is no optimal
> SCRIPT design, instead there will be some point where
> we have to pick and choose which uses to optimize for
> and which uses are less optimal, i.e. trade off.
>
> So I think maybe the Real Question is: why should we
> go for one versus the other, and which uses do we
> expect to see more often anyway?
>
> Addenda
> -------
>
> Stuff about totality and partiality:
>
> * [Total Functional Programming, D.A. Turner](
> https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.364&rep=rep1&type=pdf
> )
> * [Totality](https://kowainik.github.io/posts/totality)
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 27839 bytes --]

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

[ZmnSCPxj]

Good morning Billy,

> It sounds like the primary benefit of op_fold is bandwidth savings. Programming as compression. But as you mentioned, any common script could be implemented as a Simplicity jet. In a world where Bitcoin implements jets, op_fold would really only be useful for scripts that can't use jets, which would basically be scripts that aren't very often used. But that inherently limits the usefulness of the opcode. So in practice, I think it's likely that jets cover the vast majority of use cases that op fold would otherwise have.

I suppose the point would be --- how often *can* we add new jets?
Are new jets consensus critical?
If a new jet is released but nobody else has upgraded, how bad is my security if I use the new jet?
Do I need to debate `LOT` *again* if I want to propose a new jet?

> A potential benefit of op fold is that people could implement smaller scripts without buy-in from a relay level change in Bitcoin. However, even this could be done with jets. For example, you could implement a consensus change to add a transaction type that declares a new script fragment to keep a count of, and if the script fragment is used enough within a timeframe (eg 10000 blocks) then it can thereafter be referenced by an id like a jet could be. I'm sure someone's thought about this kind of thing before, but such a thing would really relegate the compression abilities of op fold to just the most uncommon of scripts. 
>
> > * We should provide more *general* operations. Users should then combine those operations to their specific needs.
> > * We should provide operations that *do more*. Users should identify their most important needs so we can implement them on the blockchain layer.
>
> That's a useful way to frame this kind of problem. I think the answer is, as it often is, somewhere in between. Generalization future-proofs your system. But at the same time, the boundary conditions of that generalized functionality should still be very well understood before being added to Bitcoin. The more general, the harder to understand the boundaries. So imo we should be implementing the most general opcodes that we are able to reason fully about and come to a consensus on. Following that last constraint might lead to not choosing very general opcodes.

Yes, that latter part is what I am trying to target with `OP_FOLD`.
As I point out, given the restrictions I am proposing, `OP_FOLD` (and any bounded loop construct with similar restrictions) is implementable in current Bitcoin SCRIPT, so it is not an increase in attack surface.

Regards,
ZmnSCPxj

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

[Billy Tetrud]

[-- Attachment #1: Type: text/plain, Size: 5041 bytes --]

> Are new jets consensus critical?
> Do I need to debate `LOT` *again* if I want to propose a new jet?

New jets should never need a consensus change. A jet is just an
optimization - a way to both save bytes in transmission as well as save
processing power. Anything that a jet can do can be done with a normal
script. Because of this, a script using a particular jet could be sent to a
node that doesn't support that jet by simply expanding the jet into the
script fragment it represents. The next node that recognizes the jet can
remove the extraneous bytes so extra transmission and processing-time would
only be needed for nodes that don't support that jet. (Note that this
interpretation of a 'jet' is probably slightly different than as described
for simplicity, but the idea is basically the same). 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.

> 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.

>  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.

On Sat, Mar 5, 2022 at 5:02 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Billy,
>
> > It sounds like the primary benefit of op_fold is bandwidth savings.
> Programming as compression. But as you mentioned, any common script could
> be implemented as a Simplicity jet. In a world where Bitcoin implements
> jets, op_fold would really only be useful for scripts that can't use jets,
> which would basically be scripts that aren't very often used. But that
> inherently limits the usefulness of the opcode. So in practice, I think
> it's likely that jets cover the vast majority of use cases that op fold
> would otherwise have.
>
> I suppose the point would be --- how often *can* we add new jets?
> Are new jets consensus critical?
> If a new jet is released but nobody else has upgraded, how bad is my
> security if I use the new jet?
> Do I need to debate `LOT` *again* if I want to propose a new jet?
>
> > A potential benefit of op fold is that people could implement smaller
> scripts without buy-in from a relay level change in Bitcoin. However, even
> this could be done with jets. For example, you could implement a consensus
> change to add a transaction type that declares a new script fragment to
> keep a count of, and if the script fragment is used enough within a
> timeframe (eg 10000 blocks) then it can thereafter be referenced by an id
> like a jet could be. I'm sure someone's thought about this kind of thing
> before, but such a thing would really relegate the compression abilities of
> op fold to just the most uncommon of scripts.
> >
> > > * We should provide more *general* operations. Users should then
> combine those operations to their specific needs.
> > > * We should provide operations that *do more*. Users should identify
> their most important needs so we can implement them on the blockchain layer.
> >
> > That's a useful way to frame this kind of problem. I think the answer
> is, as it often is, somewhere in between. Generalization future-proofs your
> system. But at the same time, the boundary conditions of that generalized
> functionality should still be very well understood before being added to
> Bitcoin. The more general, the harder to understand the boundaries. So imo
> we should be implementing the most general opcodes that we are able to
> reason fully about and come to a consensus on. Following that last
> constraint might lead to not choosing very general opcodes.
>
> Yes, that latter part is what I am trying to target with `OP_FOLD`.
> As I point out, given the restrictions I am proposing, `OP_FOLD` (and any
> bounded loop construct with similar restrictions) is implementable in
> current Bitcoin SCRIPT, so it is not an increase in attack surface.
>
> Regards,
> ZmnSCPxj
>

[-- Attachment #2: Type: text/html, Size: 5599 bytes --]

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

[ZmnSCPxj]

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

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

[Billy Tetrud]

[-- Attachment #1: Type: text/plain, Size: 8934 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 9850 bytes --]