CHIP 2024-12 OP_EVAL: Function Evaluation

[emergent_reasons]

Can just paste the whole html. We are living in the future

Ok back to OP_EVAL.

[Jonas]

I’ve been thinking about this for a while and I certainly don’t think stack protection should be implemented for OP_EVAL.
Messing with the stack is a feature that could open the door for many compile time optimizations.
A contrived example could be a reusable bytecode to clean up the stack:

<push bytecode to pop everything recursively from the stack>
<some more pushes>
[...]
OP_DEPTH
OP_IF
  // Do some stuff, leave "true" on stack to exit
  OP_IF
    <index to stack clean bytecode> OP_PICK OP_EVAL
  OP_ENDIF
OP_ENDIF
OP_DEPTH
OP_IF
  // Do some more stuff, leave "true" on stack to exit
  OP_IF
    <index to stack clean bytecode> OP_PICK OP_EVAL
  OP_ENDIF
OP_ENDIF
[...]

[Jonas]

Another example:

Given some arbitrary data blob you want to push all bytes directly after 0x00 as a new item on the stack, i.e. 0x0001000204560078 → 0x01, 0x02, 0x78.
It’s possible to do a recursive bytesequence to do those pushes and execute with OP_EVAL.

For OP_EXEC you’d have to first do OP_EXEC on one bytecode that does the counting and returns that as a push so you know how many items the real function will produce that you could give as an argument to another bytecode.

[tom]

@bitcoincashautist

If you wrote a function in CashScript that takes in 2 args and returns 1 then the compiler would create a well-behaved Script bytecode for that function - which doesn’t even try to break out by consuming more than 2 stack items, so why would we need low-level guarantees when we’re already controlling the bytecode to be eval’d and can ourselves guarantee that it adheres to calling convention or have the compiler produce compliant bytecode?

Great question!

Look at Jonas’s post to get the answer. Because people will try to work around it.

And more to the point, because safety of your money should not be optional.

The important part here is that this stack protection which Jason is focusing on fighting is actually practically free.
So the question really that should be asked is why there is pushback at all. Why are some people very actively advocating against a free stack protection.

[Jonas]

@tom

Look at Jonas’s post to get the answer. Because people will try to work around it.

What? I wrote examples in low level Script, not CashScript.

@tom

And more to the point, because safety of your money should not be optional.

Safety from what? A misbehaving compiler (like, for instance cashc)?

@tom

The important part here is that this stack protection which Jason is focusing on fighting is actually practically free.

I literally gave from-the-top-of-my-head examples of things that would be more convoluted (i.e. not free) with stack protection.
In the first example each IF-block would need to end with an explicit number of OP_DROPs.
In the second example there would be two different OP_EXECs, one for counting the number of pushes the second one would produce and pushing that number as an input to the second OP_EXEC. Since the second example is recursive a counter for the OP_EXEC parameter count would also need to be tracked thru the callstack.
Adding stack protection and pushing a number for specifying the number of parameters adds no value. Just because the bytecode can’t do unspecified things with the stack doesn’t make it “secure”.

That being said, I still think OP_EVAL (and friends) is a can of worms. I am not (yet) in favor of adding it.

[bitjson]

Very glad to see others experimenting with OP_EVAL and reviewing OP_EXEC/stack isolation, thanks @bitcoincashautist and @Jonas!

@bitcoincashautist

but if you have {some trusted code} <untrusted_code> OP_EVAL {some trusted code} then the untrusted_code could’ve changed the result of the preceding block, and the succeeding block would have to treat the stack state as untrusted data - just as if it’s being executed after input’s data pushes - the spender could’ve provided anything to be run as untrusted_code .

Ignoring the missing context for a moment: this just describes a poorly-factored program. Concatenative languages are underappreciated:

• With OP_EXEC: trusted_code_a <untrusted_code> <0> <0> OP_EXEC trusted_code_bc
• Saving 2+ bytes with OP_EVAL: trusted_code_ab <untrusted_code> OP_EVAL trusted_code_c

But again – everything that matters is being hidden behind undefined untrusted_code and trusted_code identifiers. It’s not possible to properly review any code snippet without context.

In this case, you’ve restated (omitting context) a less-efficient formulation of my attempted steelman of OP_EXEC (“User-provided pure functions”). The same questions apply:

1. Why untrusted_code rather than untrusted_result? I.e. what specific feature of this scenario makes it impossible or less efficient to provide code rather than a precomputed result?
2. Which party first created this contract? Why were they unable to “compile in” the untrusted_code?
   1. If not the originator, whose wallet provided the untrusted_code?
   2. How did that user/wallet audit the resulting contract behavior (including the “untrusted” code)?
   3. If applicable, how did the covenant or other contract parties review the untrusted_code before somehow internalizing it or signing on to the new contract? Given a malicious input at this stage, can the covenant be permanently frozen? (I.e. is there already a critical vulnerability in the evaluation prior to the evaluation in which OP_EXEC is assumed to add some sort of security?)
3. Can this scenario be made more efficient by removing the OP_EVAL/OP_EXEC and using a pre-commitment structure (“covenants-as-standards”), where the untrusted_code gets “compiled” into resulting child covenants?
   1. If so, does that need to happen on-chain, or are we wasting on-chain bytes to pretend that end-user wallets don’t need to audit the full child covenant’s behavior (including the “untrusted” code).
4. Specifically, what “untrusted” code can make the contract misbehave?
   1. Who stands to lose money if it misbehaves? (If it’s just the current spender – again, we’re dealing with a wallet bug.)
   2. If a third party or the covenant are at risk: is there an equivalent exploit path that does not rely on stack item counts? I.e. if the “untrusted” code is a market making algorithm, can it be rewritten to offer the exploiter more control over the “price” such that stealing funds does not require any sort of stack manipulation, only an unexpected mathematical result which otherwise obeys the “function signature”?

Again:

@bitjson

“Stack isolation” is a reasoning trap. If you think it might add security value, your mental model is omitting critical context.
[…]
OP_EXEC is like requiring motorcycle helmets in a swimming pool.

[tom]

@bitjson

whose wallet provided the untrusted_code ?

In Bitcoin Cash we have today efforts underway that try to define a system of “templates”, whic are close to libbitauth templates.

The core features aimed at is that normal users can use this library of pre-defined ASM to build their transactions on top of.

Adding any sort of eval/exec to this mix allows those templates to reference library code. Which I’m sure will happen, as NPM shows, people are doing that kind of optimizations because we are mostly lazy beings. Nothing wrong with that.

The “untrusted” concept is thus absolutly relevant in the wider scope of things.

Using either proposal you can get that code from another output using introspection. But that code may not be vetted as well as it should have been. Which makes it untrusted.

The basic concept of either op-eval/op-exec both allow the unlocking script to have a push with that code, absolutely qualifies as untrusted if you don’t go through the extra steps of validating it.

So, in short, the idea that we need not add (free!!!) protection rules because there is no way to mistakingly end up running “bad” code in your transaction is naive. Nobody downloads plain executables from the Internet either, right? In reality they do, virus’ protection companies exist. That’s the reality we need to operate in.

@bitjson

Specifically, what “untrusted” code can make the contract misbehave?

1. Who stands to lose money if it misbehaves? (If it’s just the current spender – again, we’re dealing with a wallet bug.)

Wallet bugs are certainly possible. Please don’t dismiss that as a problem that doesn’t exist or can be ignored.

[bitcoincashautist]

@tom

Using either proposal you can get that code from another output using introspection. But that code may not be vetted as well as it should have been. Which makes it untrusted.

So what? You can replace a .dll on your system with a hacker’s. Why would you do it, though? Just verify the hash so you know what you’re loading.

@tom

The basic concept of either op-eval/op-exec both allow the unlocking script to have a push with that code, absolutely qualifies as untrusted if you don’t go through the extra steps of validating it.

It’s agnostic of the source. You can just have all the pushes of eval scripts you need be part of the locking bytecode which makes them trusted and you can just call them with <N> OP_PICK OP_EVAL whenever you need them.

As the contract author - choice is yours. You want trusted? Either provide it as part of main script’s pushes (part of locking bytecode), or hash-verify if you load externally (either by unlocking data push or introspection). You want untrusted? Then refactor your contract so those come after the last VERIFY of the main’s logic you want to protect.

Script is low-level, we don’t need it to hold people’s hands.

[bitjson]

@bitcoincashautist

A function written in CashScript can’t surprise the compiler because compiler is the one creating the bytecode - compiler decides what’s the max. number of stack items it will pop during execution.

I’ll add that OP_EVAL is a contract implementation detail, it’s purpose is compression. We can already do MAST-like constructions, we can already run “functions” (words) multiple times by duplicating the code, VM limits are already solved with or without OP_EVAL, etc.

OP_EVAL just allows contracts to be expressed in fewer bytes (often added by a compiler stage rather than by deliberate design of the contract author).

@bitcoincashautist

[…] which is why Jason makes a good argument that OP_EXEC doesn’t really add security, it only adds some flexibility for one class of use-cases that would be akin to 3rd party plugins, but we don’t see much use for those.

Thanks for all the great comments @bitcoincashautist – just want to note (because I ed the post) that the analogy still isn’t accurate: I see a great variety of uses for “3rd party plugins” across multiple interpretations of that phrase.

Instead, I’m saying that OP_EXEC does not add any “flexibility” or “security” in any possible case.

Stack “isolation” fundamentally misunderstands contract development. It’s an “obvious” solution at the top of a Dunning–Kruger peak.

---

I really want to encourage people to get past reasoning by analogy about OP_EVAL and/or OP_EXEC:

• There’s no security-for-efficiency “tradeoff”
• Bytecode isn’t “untrusted” or “trusted”
• This is not a question of “architecture” or “philosophy”
• There is no “caller” nor “callee”
• It’s not a “RISC vs. CISC” thing
• “higher-level” and “lower-level” are nonsensical in this context
• OP_EXEC is not “isolation” nor a “sandbox”
• OP_EXEC doesn’t add “flexibility”, etc.

If you care to understand the topic, drop these mental crutches. Otherwise, here’s a correct analogy:

@bitjson

OP_EXEC is like requiring motorcycle helmets in a swimming pool.

[bitjson]

@Jonas

That being said, I still think OP_EVAL (and friends) is a can of worms. I am not (yet) in favor of adding it.

When you get a chance, could you try to describe these concerns? I’d love to address them in the CHIP’s rationale.

[tom]

@bitjson

Stack “isolation” fundamentally misunderstands contract development.

The claim here is interesting in that what we are doing on bitcoincashresearch is designing a plaform for random people we have never met to start and do “contract development”.
That is to say, it makes zero sense to claim some future people will or will not do something. If given the chance, people will do something. I have the entire history of (computer) security to back that up.

Jason then goes and writes:

• Bytecode isn’t “untrusted” or “trusted”

which doesn’t even attempt to disprove or otherwise debate the actual specific technical detailed post I wrote here. It just states the opposite like it is true.

I do agree with various other points he makes there, though.

• There is no “caller” nor “callee”
• It’s not a “RISC vs. CISC” thing
• “higher-level” and “lower-level” are nonsensical in this context

It’s just interesting how Jason is pushing for an idea that has been rejected by the bitcoin community a decade ago. Not even touching the ideas that could fix it, because that would mean debating those ideas. Instead we see him undercutting that possible debate by repeatedly making elusive statements about how basic security would not be needed in bitcoin cash because… something fuzzy.

Anyway, this debate seems not to go anywhere where it may improve the proposal.

[bitcoincashautist]

@tom

Instead we see him undercutting that possible debate by repeatedly making elusive statements about how basic security would not be needed in bitcoin cash because… something fuzzy.

What are you even trying to debate that he’s supposedly “undercutting”? Some alternative you randomly came up with that solves non-existent problems?

You’ve been doing the “undercutting” by writing word salads and trying to make parallels that don’t make sense in this context and then whining and making ad-hominems at Jason who’s been very patient here and tolerant of your passive aggression.

We all learned the pattern from previous CHIP cyles: you being wrong and everyone having to spend insane amount of energy and time showing exactly how you’re wrong, all the while tolerating your annoying condescenting tone coming from the peak of Dunning-Kruger hill. I don’t blame Jason for trying to avoid such timesink here.

I don’t know if you’re malicious or incompetent, I’m leaning towards incompetence, but outcome is the same: it’s a drag.

Your posts here show how clueless you are about how smart contract stuff works and yet you posture as some authority because of some “history” and expect people to give you the attention and authority you think you deserve. Ironic above you tried to call out people’s egos all the while your own ego desperately trying to be relevant.

[Jonas]

@bitjson

When you get a chance, could you try to describe these concerns? I’d love to address them in the CHIP’s rationale.

Sure, need to contemplate it some more since it’s an unknown unknowns kind of thing. OP_EVAL is really powerful, especially with recursion, and I start to wonder if the loops CHIP is needed or that would be syntactical sugar.

[bitjson]

Makes sense, please let me know if you come across items we need to address in the CHIP

@Jonas

OP_EVAL is really powerful, especially with recursion, and I start to wonder if the loops CHIP is needed or that would be syntactical sugar.

You can technically achieve some compression of iteration logic with OP_EVAL, but loops are generally much more efficient, e.g. merkle tree validation or aggregations like “sum all input values”.

For a good direct comparison, see the VMB tests for each CHIP (loops, eval).

OP_BEGIN/OP_UNTIL: Fibonacci to 13

• Unlock: <6>
• Lock (16 bytes): <0> <1> OP_ROT OP_BEGIN OP_1SUB OP_TOALTSTACK OP_SWAP OP_OVER OP_ADD OP_FROMALTSTACK OP_IFDUP OP_NOT OP_UNTIL OP_NIP <13> OP_EQUAL

OP_EVAL: Fibonacci to 13

• Unlock: <6>
• Lock (21 bytes): <0> <1> OP_ROT <OP_1SUB OP_TOALTSTACK OP_SWAP OP_OVER OP_ADD OP_FROMALTSTACK OP_IFDUP OP_IF OP_ACTIVEBYTECODE OP_ELSE <0> OP_ENDIF OP_EVAL> OP_EVAL OP_NIP <13> OP_EQUAL

And here’s link to open these scripts in Bitauth IDE →

Comparison between OP_EVAL and Loops

You can see that OP_ACTIVEBYTECODE + internal conditionals allow us to emulate loops with recursive OP_EVAL, but it requires some overhead (larger transaction sizes), is often harder to review, and cannot iterate beyond 100 without some sort of “trampoline pattern” to limit control stack depth. (So OP_EVAL is even worse for >100 iterations, e.g. summing all inputs in large transactions.) Depending on the length of the iterated code, the overall cost of pushing evaluated code can also accumulate very quickly and make otherwise-reasonable things impractical (esp. aggregations from all inputs/outputs).

On the other hand, only OP_EVAL can most efficiently “compress” any shape of contract, esp. common functions called in disparate locations. While you can technically wrap your whole contract in a giant loop + (ab)use conditional logic to activate and deactivate various code snippets at the right moment(s), that setup is going to produce quite a bit more overhead than simply calling functions in the right locations.

Summary

OP_EVAL and loops each have their strengths, and they’re often better together.

Loops are ideal for iteration, and OP_EVAL is ideal for compression of all other code sequences longer than 3 bytes.

---

I’ll also add that logistically, it’s quite a bit easier to implement both Loops and OP_EVAL at the same time: each requires modification to the control stack + carefully testing and benchmarking the VM’s control flow behavior(s) for performance regressions. (Though thanks to the VM Limits upgrade, we already have a very strong benchmarking suite for this purpose.)

[MathieuG]

Caught up to all the great discussion here and in the ‘brainstorming EVAL’ thread.

Categories of Potential Use-cases

I appreciate the overview of categories for potential use-cases for OP_EVAL @bitjson!

• Contract compression via reusable functions ( common case)
• MAST-like constructions
• Post-funding assigned instructions ( security theater/use-case covered by CashTokens )
• User-provided pure functions ( contrived example )

From the CHIP it’s clear that OP_EVAL is proposed mainly for the ‘reusable functions’ use-case, but it’s great to now have an analysis the other potential uses for the opcode also. Especially because MAST-like constructions was amongst the rationale in historic OP_EVAL discussions.

Comparison of OP_EVAL and OP_EXEC

The 'long evaluation comparing OP_EVAL to optimized OP_EXEC’ makes it clear that the cases OP_EXEC claims to optimize for are niche use-cases, and when we investigate closely, the ‘stack isolation feature’ doesn’t bring any real benefits to the smart contract designs.

I fully agree with Jason’s arguments and his conclusions written down in this thread:

@bitjson

I’ve tried my best to steelman OP_EXEC, but as of now, my analysis is:

• OP_EXEC misunderstands contract security and usage. It only seems to make sense if you haven’t tried to use it.
• OP_EXEC has zero advantages and significant disadvantages vs. OP_EVAL.

Other Evaluated Alternatives

I’m glad to see there also comparison/evaluation of the old proposals further in the thread!

@bitjson

There are many decades of prior art here – if anything, this CHIP is taken more from Chuck Moore than Gavin or any of the other 2012 proposals. OP_EVAL gets BCH VM bytecode to a “fully capable” Forth dialect.

On the other hand, the various 2012 proposals did nonsensical things like clearing stacks and preventing “nesting” – i.e. functions calling functions – and generally misunderstood the control stack and/or how non-trivial Forth programs are factored. (Understandable for the time: VM limits were a huge, untenable problem that overshadowed clear thinking about a lot of topics, and most “smart contract” ideas were very hypothetical. We’re spoiled now to have more certainty on both.)

One alternative I haven’t seen mentioned in this thread is that we can emulate OP_EVAL, as I know @bitcoincashautist described in his article. It would be good to explicit mention the benefits of ‘native eval’ vs ‘emulated eval’ somewhere also.

UTXO Transaction context

@MathieuG

i know eval in javascript is a big security concern, I wonder how this relates to the blockchain context.

Great to have this answered head-on:

@bitjson

The reasoning trap

WARNING: experienced programmers will almost certainly be misled about OP_EVAL and OP_EXEC by their intuitions from other languages/environments.

This is downstream of 1) our unusual environment – the whole transaction is the potentially-abusive input, not just the hypothetical “code” being consumed by OP_EVAL/OP_EXEC (and in another sense, the VM is itself a “sandbox”: malicious code can’t consume excessive resources or take control of the node), and 2) the concatenative programming paradigm. (It’s a deep rabbit hole, see Thinking Forth and maybe 1% the code .)

[bitcoincashautist]

@MathieuG

It would be good to explicit mention the benefits of ‘native eval’ vs ‘emulated eval’ somewhere also.

Emulated eval allows mast-like constructions but DOESN’T allow compression, because each “call” needs its own input to replicate & execute the code + the overhead of introspection opcodes gluing everything together.

[MathieuG]

CashScript user-defined functions

For CashScript we created an issue for reusable functions in Jul, 2023. The issue we were thinking about at the time was to create easy emulation for muldiv which wouldn’t overflow in the intermediate result.

Our toy-example (which doesn’t contain the real logic) was to allow a .cash library file like the following:

library Math {
  function muldiv(int x, int y, int z) returns (int) {
    return x * y / z;
  }
}

which users could then use in their contract like

import { muldiv } from "Math.cash";

contract Example() {
    function test(int x, int y, int z) {
        int result = muldiv(x, y, z);
        ...
    }
}

CashScript, a modular programming language

Having callable functions with return types adds a lot of extra scope to CashScript. We’d now need to figure out import functionality/syntax, function dependency graphs, possibly also dependency versioning etc.

With this functionality CashScript would become a ‘modular programming language’, which is in line with industry standard but definitely an important expansion from the single-file contracts we have today.

It’s definitely be a challenge but it would make a ‘proper’ fully featured programming language from CashScript

User-defined functions

To have complex zero-knowledge programs, we need user-defined functions. OP_EVAL can be a compiler detail to some extent that it is optimizing the resulting code, but for developer experience it is essential users can define reusable function APIs.

As Jason wrote in the ‘brainstorming eval’ thread, we’d expect developers to reuse functions in their code, which uses other functions in their code which uses other functions. The smart contract code to implement zero-knowledge proof verification should be readable as if it was written in JS. This logic is not blockchain specific, it is just math/cryptography.

What happens with the result of this function, how it affects the desired transaction shape, would of course be using BCH-specific logic using transaction introspection.

@bitjson

IMO, the most important use case of OP_EVAL is as a function-calling pattern. I expect nearly every sufficiently complex contract to use OP_EVAL at least once (to minimize transaction sizes), and covenants with non-trivial math (esp. crypto) are going to be calling OP_EVAL tens, hundreds, or thousands of times (though never deeper than the 100 depth limit)

Function APIs

Jason described the problems with OP_EXEC lambda/function evaluation behavior:

@bitjson

1. The resulting transactions require more bytes than OP_EVAL.
2. Defining a per-contract, bytecode-based “OP_EXEC API” is complex, error prone, and incompatible with existing contract systems. E.g. for an existing multisig wallet, each multisig signer has to be taught to understand and sign for the new OP_EXEC-based input type rather than simply signing their known input type in new transactions.
3. Stack isolation adds no security value. When you compare an end-to-end example OP_EXEC-based delegation scheme vs. constructions that we already have today (sibling inputs, introspection, CashTokens, etc.), OP_EXEC systems have more potential security pitfalls with no bandwidth savings.

I definitely agree with point 1 and 3, but I’m not sure I understand/agree with 2

let’s discuss how I envision CashScript would use ‘function APIs’
instead of:

code param1…paramN N_Params M_Returns OP_EXEC => ret1…retN

we would use the model

param1…paramN code OP_EVAL => ret1…retN

Instead of modifying the existing deep stack items, which might be at variable depths each time the reusable function is called, we just stack juggle the params to the top before executing the function and then leave the function results at the top of the stack. We wouldn’t modify deep stack elements.

This is the coding paradigm that CashScript reusable functions would have, similar to functional programming, functions have inputs and outputs and don’t have any side-effects of mutating/consuming the existing stack besides the function parameters.

If we would not provide the params up front, the alternative is to try to stack juggle them inside the ‘eval’ reusable function logic, where there is no guarantee where in the stack things are. functions would not really be re-usable at all.

Stack protection doesn’t add any security, but I also don’t see CashScript usage modifying the original stack from inside a function, just consuming params on top of the stack & adding back results to the stack

Counting arguments and clean_stack rule

In CashScript we also don’t have to check for the number of unlocking arguments provided by a spender, the ‘clean stack’ rule makes sure that the program would not work if there is more or less arguments provided than what is expected by the program. In the same way we don’t have to count the number of unlocking arguments we also don’t have to count the number of (user) arguments provided to a reusable function.

I do believe that without any clean_stack rule, these considerations would be different.

[Jonas]

@MathieuG

we would use the model

param1…paramN code OP_EVAL => ret1…retN

Instead of modifying the existing deep stack items, which might be at variable depths each time the reusable function is called, we just stack juggle the params to the top before executing the function and then leave the function results at the top of the stack. We wouldn’t modify deep stack elements.

This is the coding paradigm that CashScript reusable functions would have, similar to functional programming, functions have inputs and outputs and don’t have any side-effects of mutating/consuming the existing stack besides the function parameters.

If we would not provide the params up front, the alternative is to try to stack juggle them inside the ‘eval’ reusable function logic, where there is no guarantee where in the stack things are. functions would not really be re-usable at all.

Stack protection doesn’t add any security, but I also don’t see CashScript usage modifying the original stack from inside a function, just consuming params on top of the stack & adding back results to the stack

That makes sense in the generic case. Compiling code to use OP_EVAL with deep stack elements would be an optimization. Consider the following code where foo(int) is only called in these two places.

int a = 10;
[...]
if(x == 1) {
  foo(a);
  [...]
} else if (x == 2) {
  foo(a);
  [...]
} else {
  [...]
}

Since the stack element a would be in the same location for both invocations of foo() the bytecode executed by OP_EVAL could very well be compiled to pick it from deep in the stack.

[Jonas]

One thing I can’t put my finger on is the OP_ACTIVEBYTECODE behavior inside code executed within OP_EVAL. The old specification of it is:

Push the full bytecode currently being evaluated to the stack. For Pay-to-Script-Hash (P2SH) evaluations, this is the redeem bytecode of the Unspent Transaction Output (UTXO) being spent; for all other evaluations, this is the locking bytecode of the UTXO being spent.

What is the reason for changing this? If we kept that behavior and wanted a recursive OP_EVAL the bytecode to be evaluated could be OP_DUP´d at the top of the stack before calling OP_EVAL.

It just feels like an asymmetry that the full stack is available but not the full active bytecode (unless it is pushed to the stack before evaluation).

[bitjson]

Thanks for weighing in @MathieuG!

Purpose of OP_EVAL and loops: compression

@MathieuG

It would be good to explicit mention the benefits of ‘native eval’ vs ‘emulated eval’ somewhere also.

I’ll add to the CHIP, thanks!

@bitcoincashautist

Emulated eval allows mast-like constructions but DOESN’T allow compression, because each “call” needs its own input to replicate & execute the code + the overhead of introspection opcodes gluing everything together.

Exactly.

All of the value in both loops and OP_EVAL can be summarized as “compression”. Our VM can technically compute anything already, but saving KBs or MBs from transaction sizes makes many more use cases practical.

Clarifying review of OP_EXEC

@MathieuG

Jason described the problems with OP_EXEC lambda/function evaluation behavior:

@bitjson

1. The resulting transactions require more bytes than OP_EVAL.

2. Defining a per-contract, bytecode-based “OP_EXEC API” is complex, error prone, and incompatible with existing contract systems. E.g. for an existing multisig wallet, each multisig signer has to be taught to understand and sign for the new OP_EXEC-based input type rather than simply signing their known input type in new transactions.

3. Stack isolation adds no security value. When you compare an end-to-end example OP_EXEC-based delegation scheme vs. constructions that we already have today (sibling inputs, introspection, CashTokens, etc.), OP_EXEC systems have more potential security pitfalls with no bandwidth savings.

I definitely agree with point 1 and 3, but I’m not sure I understand/agree with 2

let’s discuss how I envision CashScript would use ‘function APIs’ […]

All good, #2 isn’t talking about internal “function APIs” but rather a hypothetical kind of secondary, external contract API. (A fuzzy idea that people are reasoning-by-analogy from OP_EXEC, not realizing that CashTokens are an already superior alternative available today.)

Deep stack juggling (usually) considered harmful

@MathieuG

Instead of modifying the existing deep stack items, which might be at variable depths each time the reusable function is called, we just stack juggle the params to the top before executing the function and then leave the function results at the top of the stack. We wouldn’t modify deep stack elements.

Perfect, this is an optimal compilation result for Forth-like syntaxes.

The stack is for piping arguments through multiple words/functions without the overhead of naming and plumbing all outputs to the next inputs. (And this is the reason stack-based languages are better suited for interactive development than static text.)

If your compiled programs do much deep-stack juggling, they’re probably not optimally factored.

It’s long been frowned upon to dig deeply in the stack from a word/function definition, for many reasons. From Thinking Forth (1984):

Some folks like the words PICK and ROLL. They use these words to access elements from any level on the stack. We don’t recommend them. For one thing, PICK and ROLL encourage the programmer to think of the stack as an array, which it is not. If you have so many elements on the stack that you need PICK and ROLL, those elements should be in an array instead.

Second, they encourage the programmer to refer to arguments that have been left on the stack by higher-level, calling definitions without being explicitly passed as arguments. This makes the definition dependent on other definitions. That’s unstructured—and dangerous.

Finally, the position of an element on the stack depends on what’s above it, and the number of things above it can change constantly. For instance, if you have an address at the fourth stack position down, you can write 4 PICK @ to fetch its contents. But you must write ( n) 5 PICK ! because with “n” on the stack, the address is now in the fifth position. Code like this is hard to read and harder to modify.

Of course, the aim of this text is different from BCH VM design: this author is thinking in Forth for application design, while the BCH VM simply uses Forth-like syntax to simplify VM implementation and minimize the byte length of contracts.

Our PICK and ROLL are more useful because we don’t have arrays or other data structures (and even if we had them, optimally-compiled bytecode would still use PICK, ROLL, and/or use the alt stack instead).

Regardless, CashScript users can simply think in CashScript, so all else being equal, consensus upgrades should focus on enabling smaller compiled results to be produced by CashScript, Libauth’s compiler (for Libauth’s CashAssembly), etc.

CashScript doesn’t necessarily need syntax for OP_EVAL

@MathieuG

Stack protection doesn’t add any security, but I also don’t see CashScript usage modifying the original stack from inside a function, just consuming params on top of the stack & adding back results to the stack

Yes, as @Jonas noted, some optimizations enabled by OP_EVAL require visibility over the entire contract code.

I’ll go a step further: all optimizations enabled by OP_EVAL are best applied near the end of the compilation pipeline, i.e. CashScript’s function behavior doesn’t need to be tied to OP_EVAL’s semantics at all.

In fact, if CashScript were to attempt to produce “code with OP_EVAL” as a result of function compilations in early compiler stages, the final compiled bytecode will be stuck at a local maximum in optimizing contract byte length.

The ideal behavior is for CashScript to ignore that OP_EVAL exists in early compiler stages, producing a much longer raw bytecode with many repeated sequences of bytes, then feed that long sequence into a deterministic “OP_EVAL optimization” function – i.e. optimize(rawBytecode) -> optimizedBytecode (Libauth’s compiler will have one or more of these, so CashScript should be able to simply choose and import one).

Note that unlike earlier CashScript stages, this final stage is capable of taking advantage of the VM’s concatenative semantics: there may be sections of 4+ byte repeats in many contracts which the contract author and earlier compiler stages did not anticipate, and this final compiler stage is in the best place to identify and factor those out, arrange them optimally to minimize stack manipulation, then OVER/DUP/CAT/PICK/ROLL/EVAL to minimize total bytecode length.

As with other compiled languages, contract authors are likely to try to “work with the optimizer” to produce better and better outputs, but it’s useful to note that the language itself doesn’t necessarily need any syntax for this, and it’s probably better to wait a while for the ecosystem to experiment before trying to add any sort of syntax for “optimization hinting”.

So my recommendation: don’t try to make functions compile into OP_EVAL. Just make functions work like macros and leave OP_EVAL to later compilation stages. You’ll end up with better-optimized bytecode.

@Jonas

Since the stack element a would be in the same location for both invocations of foo() the bytecode executed by OP_EVAL could very well be compiled to pick it from deep in the stack.

Yes, and in this case you don’t want the function to be compiled in at all! If you call it in two places with the same input, the compiler should just move it up and encode the call once, without the OP_EVAL if more efficient (and if possible, precompute, e.g. with CashAssembly’s $() internal evaluation syntax).

What about OP_EVALed OP_ACTIVEBYTECODE?

@Jonas

One thing I can’t put my finger on is the OP_ACTIVEBYTECODE behavior inside code executed within OP_EVAL . The old specification of it is:

Push the full bytecode currently being evaluated to the stack. For Pay-to-Script-Hash (P2SH) evaluations, this is the redeem bytecode of the Unspent Transaction Output (UTXO) being spent; for all other evaluations, this is the locking bytecode of the UTXO being spent.

What is the reason for changing this? If we kept that behavior and wanted a recursive OP_EVAL the bytecode to be evaluated could be OP_DUP ´d at the top of the stack before calling OP_EVAL .

It just feels like an asymmetry that the full stack is available but not the full active bytecode (unless it is pushed to the stack before evaluation).

Thanks for the question!

First I want to note that it’s not a change from the current behavior.

Right now, OP_ACTIVEBYTECODE returns the “active bytecode” truncated at the last executed code separator. In P2S, this is the locking bytecode, but in P2SH it’s the redeem bytecode – without the “parent” locking bytecode. Currently the CHIP matches this behavior exactly: within an OP_EVAL, the “active bytecode” is the eval-ed bytecode without any “parent” bytecode (again, truncated at the last executed code separator).

For more background on why OP_ACTIVEBYTECODE behaves as it does, see:

• Differences Between OP_ACTIVEBYTECODE and OP_INPUTINDEX OP_UTXOBYTECODE and

• OP_ACTIVEBYTECODE Support for OP_CODESEPARATOR.

Should OP_ACTIVEBYTECODE encode the whole “call stack”?

On the other hand, ignoring OP_ACTIVEBYTECODE's P2SH behavior, it’s easy to assume that OP_ACTIVEBYTECODE should behave differently inside OP_EVAL, e.g. by stepping through the control stack to concatenate the encoding of every “parent” active bytecode (presumably separated by OP_CODESEPARATOR) before finally appending the currently-active bytecode.

In this case, OP_ACTIVEBYTECODE would cover the whole “call stack” rather than just the currently-active bytecode.

To compare this alternative against the CHIP’s specified behavior, we need to review both items impacted by “active bytecode” (A.K.A. coveredBytecode or scriptCode): 1) OP_ACTIVEBYTECODE, and 2) transaction signature checking (OP_CHECKSIG[VERIFY] and OP_CHECKMULTISIG[VERIFY], but not OP_CHECKDATASIG[VERIFY]).

Also note the Ongoing Value of OP_CODESEPARATOR Operation is to save bytes in specific constructions (allowing one public key to sign for different code paths in a single contract without risking a counterparty maleateing the transaction to follow an unintended code path).

Results:

OP_EVALed OP_ACTIVEBYTECODE covering full "call stack"

• Greater consensus implementation complexity: this requires a new consensus-critical encoding for the “call stack”, more code to specify the full encoding behavior, and creates more surface area for performance regressions in specific VM implementations (if call stack encoding is unusually slow in a particular implementation, it could be a denial-of-service concern).

• OP_ACTIVEBYTECODE is less useful: it carries baggage from all “parent” function calls, likely separated with OP_CODESEPARATOR. Contracts must almost certainly seek-through and OP_SPLIT the encoded output to get to anything within it. In practice, this will never be more efficient than simply OP_PICKing whatever parent/active bytecode you’re after.

• Transaction signature checking: reduced flexibility, increased complexity and contract lengths:

• No added security, reduced flexibility: A single public key can sign for multiple code paths regardless of whether or not the whole “call stack” is encoded. In both cases, signatures using different code paths must execute a differing OP_CODESEPARATOR to prevent the signature from being misused in an unexpected code path. At best, the call stack behavior has saved a byte by serving as an “implicitly-called” OP_CODESEPARATOR. On the other hand, it’s also not possible for contracts to avoid this behavior, so in some cases workarounds could waste many more bytes creating a solution that idempotently accepts the same signature in multiple places (perfectly efficient with the current OP_EVAL CHIP).

• Increased complexity of signing implementations: encoding the call stack has no impact on the “single key, multiple paths” use case for OP_CODESEPARATOR, but it has a huge impact on the practicality of signing implementations. Now, instead of being able to sign the more predictable, static bytecode which contains the intended signature checking operation, signing implementations are forced to understand or be hinted with the expected shape of the call stack at each signature checking location. In practice, I expect many contracts would instead chose to prefix all signature checking evaluations with an OP_CODESEPARATOR, wasting a byte to skip dealing with this call stack nonsense.

OP_EVALed OP_ACTIVEBYTECODE covering only the active bytecode

• Simple consensus implementation: matching the current behavior for P2SH.

• OP_ACTIVEBYTECODE is useful: since OP_ACTIVEBYTECODE is always available, compilers can simplify code both before and within the OP_EVAL call, occasionally saving a few bytes vs. OP_DUP some_stack_juggling OP_EVAL + additional stack juggling within the OP_EVAL.

• Simplified signing implementations, shorter contracts: signers don’t need to encode the expected call stack, and can typically encode some statically-analyzable bytecode. making signing implementations much simpler, especially for offline and/or hardware wallets. Signature checks are idempotent: if they pass in one place, they can be made to pass it in multiple places at zero cost (by wrapping them in a “function” and calling that function in each location). Signatures from the same public key can also be easily made to not pass when checked in multiple locations, also at zero cost (because every function evaluation instantiates its own “active bytecode”, many contracts won’t even have to add the extra 1-byte OP_CODESEPARATOR to get the “single key, multiple paths” behavior).

Summary: OP_EVALed OP_ACTIVEBYTECODE

The OP_EVAL CHIP’s handling of active bytecode matches the existing P2SH behavior and simplifies consensus implementations, simplifies signing implementations (esp. offline and/or hardware wallets), and reduces contract sizes.