Alternative to OP_EVAL

Gavin asked me to come up with an alternative to OP_EVAL, so here is my proposal.

OP_CODEHASH Initial Proposal

The idea is to add third "codehash" stack to the scripting engine (or alternatively a codehash state variable) and have OP_CODESEPARATOR in addition to its current behaviour push the hash of the remaining code in the script onto the codehash stack (or alternatively set the codehash state variable).

Then we add a new OP_CODEHASH operator that pops the codehash stack and pushes it onto the main stack (or alternatively push the value of the codehash state variable onto the mainstack which is initialized using the hash of the sigScript).

The new send-to-script transaction would be:

OP_CODEHASH OP_HASH160 {20-byte-hash-value} OP_EQUAL

Which can be redeemed by

{20-byte-code-hash} signatures OP_CODESEPARATOR code

When run the code will consume all the signatures leaving the 20-byte-code-hash on the stack. When OP_CODEHASH is interpreted as a NOP it is skipped, then the hash is hashed and compared to the 20-byte-hash-value and a match is required to succeed.

When OP_CODEHASH is interpreted by a new client it pops the codehash stack and pushes the value onto the main stack, which in this standard transaction pushes a value identical to the existing {20-byte-code-hash} on the stack. Then again this hash is hashed and compared to to {20-byte-code-hash}.

This proposal covers all the desired behaviour from OP_EVAL proposal but
with a less radical change:
   (1) you get send-to-script addresses
   (2) you cannot redeem with the old client without knowing the hash of the script

OP_CODEHASH has no dynamically generated code that is executed. The language remains a weak stack based language which is clearly terminating. The number of operations executed is still bounded by the number of operations occurring in the script. With the OP_EVAL proposal the script language becomes essentially Turing complete, with only an artificial limit on recursion depth preventing arbitrary computation and there is no way to know what code will run without executing it. With the OP_EVAL proposal there is no way to statically analyze the script (say to count the number of uses of OP_CHECKSIG or OP_MULTICHECKSIG or other analysis) without actually executing the script.

This is just an initial proposal there are clearly some variations that could be done that would work just as well.

Thanks goes to luke-jr and others for their thoughts on this proposal.

Good night everyone.

On Thu, Dec 29, 2011, at 01:55 AM, roconnor@theorem•ca wrote:

> The number of operations executed is still bounded by the number of
> operations occurring in the script.  With the OP_EVAL proposal the
> script language becomes essentially Turing complete, with only an
> artificial limit on recursion depth preventing arbitrary computation
> and there is no way to know what code will run without executing it.

Even if OP_EVAL allowed infinite depth, you'd still need to explicitly specify all operations performed, since there is no way of looping.

I think that something like OP_EVAL will eventually be used to improve Script in a backward-compatible way (enable the disabled math ops, fix bugs, etc.), so the mechanism might as well be used now. The only advantage I see with OP_CODEHASH is that script ops won't need to be in Script "strings".

First, thanks very much to Russell for looking more closely at both BIP 12 and the patch than anybody else-- he's found two bugs and two things the BIP isn't clear enough on (so far).

And I've got to say, I'm very sympathetic to the "OP_EVAL starts down the code-as-data path, and There Be Dragons" argument.

But:

I don't think the proposed alternative would be, in practice, any better. I see two main disadvantages over OP_EVAL:

  about 20-bytes larger

  it means going back to where we were two months ago, writing more
code, reviewing it, finding bugs in it, backporting it so miners
running old software can support it, etc.

... and some other minor disadvantages:

  'standard' scripts will need to be slightly different in the
scriptSig and the scriptPubKey
   (e.g. <signature> CHECKSIG  becomes  <signature> CHECKSIGVERIFY
with OP_CODEHASH)

  OP_EVALs are not executed, and so the code associated with them does
not have to be part of the transaction, if they are in the
non-executed branch of an OP_IF. That could be good for privacy, and
could be good for reducing block-chain size.

----------------------

In discussions in IRC yesterday, we talked a little about possible
changes to the OP_EVAL BIP to make it less subject to abuse. In
particular, the big can of worms is allowing arithmetic or bit
operations on the serialized script that will be EVAL'ed:
  <serialized script> <other_data> OP_ADD OP_EVAL  <-- Look! Dragons!

If <serialized script> is more than 4 bytes, that is actually illegal right now (all of the arithmetic operations are limited to operating on numbers that are 4 bytes of less, and I believe we could prove that no series of operations will ever produce a value more than 5 bytes big given the current limitations).

Which leads me to suggest that BIP 12 be amended to state that:
  OP_EVAL shall cause script validation to fail if the top item on the
stack is less than 8 bytes long.

I'm tempted to propose a rule:
  OP_EVAL shall fail if the top item on the stack is the result of any
calculation

... but I don't think the extra code it would take to implement that (keep track of which items on the stack were the results of OP_ADD/etc) is worth it.

On the "you can't tell how many CHECKSIG operations will be performed before executing the script" issue:

That is already true, because the parameters to CHECKMULTISIG that determine how many signatures it checks might be computed.

Finally, I would echo theymos' observation that I think we'll eventually do something very much like OP_EVAL in the future-- maybe to support (in a backwards-compatible way) a quantum-computing-resistant signature algorithm or SHA3. When that is done, I think it might make sense to do a bottom-up redesign of Script based on what we've learned.

On Thu, 29 Dec 2011, theymos wrote:

> On Thu, Dec 29, 2011, at 01:55 AM, roconnor@theorem•ca wrote:
>> The number of operations executed is still bounded by the number of
>> operations occurring in the script.  With the OP_EVAL proposal the
>> script language becomes essentially Turing complete, with only an
>> artificial limit on recursion depth preventing arbitrary computation
>> and there is no way to know what code will run without executing it.
>
> Even if OP_EVAL allowed infinite depth, you'd still need to explicitly
> specify all operations performed, since there is no way of looping.

That's not true. Gavin himself showed how to use OP_EVAL to loop: OP_PUSHDATA {OP_DUP OP_EVAL} OP_DUP OP_EVAL.

Basically OP_DUP lets you duplicate the code on the stack and that is the key to looping. I'm pretty sure from here we get get Turing completeness. Using the stack operations I expect you can implement the SK-calculus given an OP_EVAL that allows arbitrary depth.

OP_EVAL adds dangerously expressive power to the scripting language.

Good morning everyone.

On Thu, 29 Dec 2011, Gavin Andresen wrote:

> First, thanks very much to Russell for looking more closely at both
> BIP 12 and the patch than anybody else-- he's found two bugs and two
> things the BIP isn't clear enough on (so far).
>
> And I've got to say, I'm very sympathetic to the "OP_EVAL starts down
> the code-as-data path, and There Be Dragons" argument.
>
> But:
>
> I don't think the proposed alternative would be, in practice, any
> better.  I see two main disadvantages over OP_EVAL:
>
>  about 20-bytes larger
>
>  it means going back to where we were two months ago, writing more
> code, reviewing it, finding bugs in it, backporting it so miners
> running old software can support it, etc.

Well, given the state that the OP_EVAL proposal was in when I looked at it this week, all your code reviews you have done so far are not adequate anyways.

Gavin, push the OP_EVAL date back 2 months. OP_EVAL just is not ready yet.

> ... and some other minor disadvantages:
>
>  'standard' scripts will need to be slightly different in the
> scriptSig and the scriptPubKey
>   (e.g. <signature> CHECKSIG  becomes  <signature> CHECKSIGVERIFY
> with OP_CODEHASH)
>
>  OP_EVALs are not executed, and so the code associated with them does
> not have to be part of the transaction, if they are in the
> non-executed branch of an OP_IF. That could be good for privacy, and
> could be good for reducing block-chain size.

I don't understand the above paragraph.

> ----------------------
>
> In discussions in IRC yesterday, we talked a little about possible
> changes to the OP_EVAL BIP to make it less subject to abuse. In
> particular, the big can of worms is allowing arithmetic or bit
> operations on the serialized script that will be EVAL'ed:
>  <serialized script> <other_data> OP_ADD OP_EVAL  <-- Look! Dragons!
>
> If <serialized script> is more than 4 bytes, that is actually illegal
> right now (all of the arithmetic operations are limited to operating
> on numbers that are 4 bytes of less, and I believe we could prove that
> no series of operations will ever produce a value more than 5 bytes
> big given the current limitations).

This is not adequate: <data> OP_SHA256 OP_EVAL runs random code that is more than 5 bytes.

> Which leads me to suggest that BIP 12 be amended to state that:
>  OP_EVAL shall cause script validation to fail if the top item on the
> stack is less than 8 bytes long.
>
> I'm tempted to propose a rule:
>  OP_EVAL shall fail if the top item on the stack is the result of any
> calculation
>
> ... but I don't think the extra code it would take to implement that
> (keep track of which items on the stack were the results of
> OP_ADD/etc) is worth it.
>
> On the "you can't tell how many CHECKSIG operations will be performed
> before executing the script" issue:
>
> That is already true, because the parameters to CHECKMULTISIG that
> determine how many signatures it checks might be computed.

Yes, but maybe there is other static analysis miners may want to do. I can't imagine every scenario.

> Finally, I would echo theymos' observation that I think we'll
> eventually do something very much like OP_EVAL in the future-- maybe
> to support (in a backwards-compatible way) a
> quantum-computing-resistant signature algorithm or SHA3. When that is
> done, I think it might make sense to do a bottom-up redesign of Script
> based on what we've learned.

IMHO I think the above observation is not very relevant to the merits of the existing OP_EVAL proposal on the table.

On Thursday, December 29, 2011 12:01:20 PM roconnor@theorem•ca wrote:

> This is not adequate: <data> OP_SHA256 OP_EVAL runs random code that is
> more than 5 bytes.

So what? Why shouldn't I be able to run random code? I could always put that random code in the script verbatim, after all.

RE: preventing OP_EVAL from executing the result of calculations:

> This is not adequate: <data> OP_SHA256 OP_EVAL runs random code that is more> than 5 bytes.

Good point, the rule should be "OP_EVAL shall fail if asked to execute 8 or fewer bytes."

RE: this minor disadvantage:

>>  OP_EVALs are not executed, and so the code associated with them does
>> not have to be part of the transaction, if they are in the
>> non-executed branch of an OP_IF. That could be good for privacy, and
>> could be good for reducing block-chain size.

> I don't understand the above paragraph.

It is the "Either This or That can redeem" case that motivated me to allow 2-deep EVAL recursion.

Start with the most straightforward code for doing "this or that" (in pseudocode):

scriptSig:  <sigs> <either the code for This or the code for That>
scriptPuKey:
  IF <hash of code> EQUALS hash of This or hash of That:
    EVAL
  ELSE
    fail validation
  ENDIF

That can be done with CODESEPARATOR/CODEHASH.

But if you want to then bundle that up so the scriptPubKey is a standard 'pay to script', you get:

scriptSig: <sigs> <either the code for This or the code for That> <serialized IF... code from above> scriptPubKey: ... standard DUP HASH160 <> EQUALVERIFY EVAL

To be backwards compatible with old clients the scriptSig would have to be:

<hash1> <hash2> <sigs> CODESEPARATOR this_or_that_code
 CODEHASH
 CODESEPARATOR
 IF <hash of code> does not equal hash2:
   fail verification
 ENDIF

That could only be done if the definition of CODEHASH was modified to hash only the stuff between CODESEPARATORS instead of hashing from CODESEPARATOR to the end of the scriptSig.

RE: static analysis:

> Yes, but maybe there is other static analysis miners may want to do.  I
> can't imagine every scenario.

The vast majority of miners are "discouraging" (not relaying or putting into blocks) anything besides 'standard' transaction types.

Until somebody smarter than me (like Russell) has done a deep analysis of Script and all of its opcodes, I don't think that should change. The standard transaction types are easy to reason about, and the standard types extended with OP_EVAL are also easy to reason about-- you can template-match them to find out how many ECDSA operations a CHECKMULTISIG will do, etc.

Again, in practice, I don't think EVAL as proposed is a danger.

RE: delaying EVAL rollout: I could live with rolling out just BIP 11 (up-to-3-signature-CHECKMULTISIG as 'standard' transactions) and delaying EVAL rollout on the main network, but I worry that will just encourage people to delay thoroughly reviewing/testing for a couple of months, and we'll be right back here at the beginning of March.

On Thu, Dec 29, 2011 at 01:55:03AM -0500, roconnor@theorem•ca wrote:

> Gavin asked me to come up with an alternative to OP_EVAL, so here is my
> proposal.
>
> OP_CODEHASH Initial Proposal

If we're again brainstorming about alternatives for OP_EVAL, I'll do my own.

It is called OP_CHECKEDEVAL, and is specified as follows:
* It looks at the two elements most recently (in code position) pushed by a literal,
  and not yet consumed by another OP_CHECKEDEVAL. These are S (the serialized script),
  and H (its hash). This implies it defines its own literal-only stack, where all
  literals push to, and only OP_CHECKEDEVAL pops from. This special stack has the
  advantage of allowing static analysis - one does not need to execute any operations
  to find out which data will end up on it. Note that "skipped" code (inside the
  ignored part of an IF-THEN-ELSE) can still push to the literal stack.
* For the "outer script", it does not have any effect at all, except for:
  * 2 elements popped from the literal-only stack
  * potentially causing failure
  It does not touch the main stack, alt stack or any other part of the execution state
  not listed above.
* Failure is caused when either of these conditions hold:
  * No two elements remain on the literal-only stack
  * The Hash(S) != H
  * The inner script execution caused failure
* For the execution of the inner script:
  * It is executed in a completely new and independent execution environnement
  * It executes the deserialized S
  * It inherits the main stack and alt stack (without the serialized script and the hash
    themselves) from the outer execution.

This requires OP_CHECKEDEVAL to immediately follow the push of script and hash, so the code in the pair < <script> OP_CHECKEDEVAL > can be parsed and interpreted as code, allowing static analysis.

As OP_CHECKEDEVAL has absolutely no effects except for potentially causing failure, it is very similar to the OP_NOPx it would replace, and guarantees that interpreting OP_CHECKEDEVAL as OP_NOPx can never cause the script to become invalid if it wasn't already.

A basic pay-to-script-hash scriptPubKey is very short:

  <scriptHash> OP_CHECKEDEVAL

And it is redeemed using:

  <script inputs> <script>

Furthermore, the implementation is very similar to what was already done for OP_EVAL. Modifications: * EvalScriptInner needs less by-ref arguments, as it cannot modify the parent's state. * A literal-only stack needs to be maintained.

I believe this combines all advantages: * Easy spend-to-script-hash (shorter than OP_EVAL) * Backward compatible (guaranteed by construction, instead of separately enforced like with OP_EVAL) * Statically analyzable (though it requires deserializing the script data). * Possibility to introduce a new language inside (not done in this proposal)

Only disadvantages: * Slightly less flexible than OP_EVAL, as it disallows dynamic interation with serialized scripts. * Static code analyzers need to deserialize script data.

Credits: gmaxwell for the idea of a literal-only stack

> RE: delaying EVAL rollout:  I could live with rolling out just BIP 11
> (up-to-3-signature-CHECKMULTISIG as 'standard' transactions) and
> delaying EVAL rollout on the main network, but I worry that will just
> encourage people to delay thoroughly reviewing/testing for a couple of
> months, and we'll be right back here at the beginning of March.

How about releasing it on testnet first? If you want "less smart" people such as myself to help test, well I don't think I would get anywhere if I tried to abstractly reason about every possibility. Low-level testing is certainly important, but for me "thorough testing" requires an actual network of nodes (running different clients) and applications capable of creating and verifying real OP_EVAL transactions.

My suggestion would be: Deploy OP_EVAL on testnet quickly, let's build some real-life applications and if it works well, /then /let's pull the trigger for mainnet. If some issues or improvements arise, we'll have a chance to adjust it and try again.

I don't think this is too conservative or paranoid. I think this is a textbook use case for testnet.

On 12/29/2011 7:00 PM, Gavin Andresen wrote:

> RE: preventing OP_EVAL from executing the result of calculations:
>
>> This is not adequate:<data>  OP_SHA256 OP_EVAL runs random code that is more>  than 5 bytes.
> Good point, the rule should be "OP_EVAL shall fail if asked to execute
> 8 or fewer bytes."
>
> RE: this minor disadvantage:
>
>>>   OP_EVALs are not executed, and so the code associated with them does
>>> not have to be part of the transaction, if they are in the
>>> non-executed branch of an OP_IF. That could be good for privacy, and
>>> could be good for reducing block-chain size.
>> I don't understand the above paragraph.
> It is the "Either This or That can redeem" case that motivated me to
> allow 2-deep EVAL recursion.
>
> Start with the most straightforward code for doing "this or that" (in
> pseudocode):
>
> scriptSig:<sigs>  <either the code for This or the code for That>
> scriptPuKey:
>    IF<hash of code>  EQUALS hash of This or hash of That:
>      EVAL
>    ELSE
>      fail validation
>    ENDIF
>
> That can be done with CODESEPARATOR/CODEHASH.
>
> But if you want to then bundle that up so the scriptPubKey is a
> standard 'pay to script', you get:
>
> scriptSig:<sigs>  <either the code for This or the code for That>
> <serialized IF... code from above>
> scriptPubKey:  ... standard DUP HASH160<>  EQUALVERIFY EVAL
>
> To be backwards compatible with old clients the scriptSig would have to be:
>
> <hash1>  <hash2>  <sigs>  CODESEPARATOR this_or_that_code
>   CODEHASH
>   CODESEPARATOR
>   IF<hash of code>  does not equal hash2:
>     fail verification
>   ENDIF
>
> That could only be done if the definition of CODEHASH was modified to
> hash only the stuff between CODESEPARATORS instead of hashing from
> CODESEPARATOR to the end of the scriptSig.
>
> RE: static analysis:
>
>> Yes, but maybe there is other static analysis miners may want to do.  I
>> can't imagine every scenario.
> The vast majority of miners are "discouraging" (not relaying or
> putting into blocks) anything besides 'standard' transaction types.
>
> Until somebody smarter than me (like Russell) has done a deep analysis
> of Script and all of its opcodes, I don't think that should change.
> The standard transaction types are easy to reason about, and the
> standard types extended with OP_EVAL are also easy to reason about--
> you can template-match them to find out how many ECDSA operations a
> CHECKMULTISIG will do, etc.
>
> Again, in practice, I don't think EVAL as proposed is a danger.
>
> RE: delaying EVAL rollout:  I could live with rolling out just BIP 11
> (up-to-3-signature-CHECKMULTISIG as 'standard' transactions) and
> delaying EVAL rollout on the main network, but I worry that will just
> encourage people to delay thoroughly reviewing/testing for a couple of
> months, and we'll be right back here at the beginning of March.
>

On Thu, Dec 29, 2011 at 08:08:38PM +0100, Pieter Wuille wrote:

> On Thu, Dec 29, 2011 at 01:55:03AM -0500, roconnor@theorem•ca wrote:
> > Gavin asked me to come up with an alternative to OP_EVAL, so here is my
> > proposal.
> >
> > OP_CODEHASH Initial Proposal
>
> If we're again brainstorming about alternatives for OP_EVAL, I'll do my own.
>
> It is called OP_CHECKEDEVAL, and is specified as follows:

I realized this may have been needlessly complicated. All is required to achieve the
same properties (plus win half-verification by old clients) is a somewhat more
restricted OP_EVAL which:
* Does not touch the stack or altstack - it looks at the last (code-position wise)
  literal pushed (and not yet consumed by another OP_EVAL) on the stack and uses
  that as script to be executed.
* Executes its subscript in an independent environment, which inherits only the
  main stack (this allows the outer script to hide information from the
  inner script by moving it temporarily to the alt stack).
* OP_EVAL is an effective no-op for the execution state of the outer script,
  except for:
  * potentially causing failure (if the subscript doesn't parse or doesn't
    terminate succesfully)
  * popping an element from the literal-only stack

A pay-to-script-hash becomes:

  OP_EVAL OP_HASH160 <scriptHash> OP_EQUAL

and is redeemed using

  [script input] <<script>>

I haven't been much a part of these brainstorming discussions, and so I'm really looking at this from a bird's eye view, without any bias towards any particular idea.

I do see what appears to be relevant concerns, brought up just before new, powerful functionality is injected into 50%+ of the nodes on the network. I cannot tell from my position if there is/has been consistent concern for OP_EVAL proposal, or if it's mostly a transient response to hearing about recursion in the scripting engine, etc (like myself, originally). I haven't debated this topic much, so I'm not in a position to personally comment on any proposals. (Though, this all feels very similar to the problem of hash-table collisions in HTTP POST<http://www.securityweek.com/hash-table-collision-attacks-could-trigger-ddos-massive-scale> ).

However, I would like to remind everyone that we/you are messing with a $20+ million dollar *thing*. There's more than just a piece of software at stake -- whatever goes in needs to be as hard as diamond. If we open up a hole that allows someone to satisfy arbitrary scripts, or create one-packet DoS/crash attacks, that could be devastating for Bitcoin. Roconner is persuasive enough to make *me* think that not all corners of this functional space has been explored properly. And while my opinion doesn't matter, I'm concerned that others may feel too invested in the current design path to want to "go backwards." Again, I don't know one way or another, I just want to warn against pride getting priority over security.

At the very least, you should consider consequences and recovery path of such unanticipated problems. If the things that could go wrong are devastating, let's lean towards a more conservative solution (like sandboxing the sub-scripting engine). Remember, the network is working just fine *without *OP_EVAL, and while OP_EVAL provides some really nice benefits, I don't think the benefits over regular multi-sig are worth the consequences of making a mistake in this multi-million dollar beast.

Okay, back to your regularly-scheduled debating... -Alan

On Thu, Dec 29, 2011 at 2:08 PM, Pieter Wuille <pieter.wuille@gmail•com>wrote:

> On Thu, Dec 29, 2011 at 01:55:03AM -0500, roconnor@theorem•ca wrote:
> > Gavin asked me to come up with an alternative to OP_EVAL, so here is my
> > proposal.
> >
> > OP_CODEHASH Initial Proposal
>
> If we're again brainstorming about alternatives for OP_EVAL, I'll do my
> own.
>
> It is called OP_CHECKEDEVAL, and is specified as follows:
> * It looks at the two elements most recently (in code position) pushed by
> a literal,
>  and not yet consumed by another OP_CHECKEDEVAL. These are S (the
> serialized script),
>  and H (its hash). This implies it defines its own literal-only stack,
> where all
>  literals push to, and only OP_CHECKEDEVAL pops from. This special stack
> has the
>  advantage of allowing static analysis - one does not need to execute any
> operations
>  to find out which data will end up on it. Note that "skipped" code
> (inside the
>  ignored part of an IF-THEN-ELSE) can still push to the literal stack.
> * For the "outer script", it does not have any effect at all, except for:
>  * 2 elements popped from the literal-only stack
>  * potentially causing failure
>  It does not touch the main stack, alt stack or any other part of the
> execution state
>  not listed above.
> * Failure is caused when either of these conditions hold:
>  * No two elements remain on the literal-only stack
>  * The Hash(S) != H
>  * The inner script execution caused failure
> * For the execution of the inner script:
>  * It is executed in a completely new and independent execution
> environnement
>  * It executes the deserialized S
>  * It inherits the main stack and alt stack (without the serialized script
> and the hash
>    themselves) from the outer execution.
>
> This requires OP_CHECKEDEVAL to immediately follow the push of script and
> hash,
> so the code in the pair < <script> OP_CHECKEDEVAL > can be parsed and
> interpreted as code,
> allowing static analysis.
>
> As OP_CHECKEDEVAL has absolutely no effects except for potentially causing
> failure, it
> is very similar to the OP_NOPx it would replace, and guarantees that
> interpreting
> OP_CHECKEDEVAL as OP_NOPx can never cause the script to become invalid if
> it wasn't
> already.
>
> A basic pay-to-script-hash scriptPubKey is very short:
>
>  <scriptHash> OP_CHECKEDEVAL
>
> And it is redeemed using:
>
>  <script inputs> <script>
>
> Furthermore, the implementation is very similar to what was already done
> for
> OP_EVAL. Modifications:
> * EvalScriptInner needs less by-ref arguments, as it cannot modify the
> parent's state.
> * A literal-only stack needs to be maintained.
>
>
> I believe this combines all advantages:
> * Easy spend-to-script-hash (shorter than OP_EVAL)
> * Backward compatible (guaranteed by construction, instead of separately
> enforced like with OP_EVAL)
> * Statically analyzable (though it requires deserializing the script data).
> * Possibility to introduce a new language inside (not done in this
> proposal)
>
> Only disadvantages:
> * Slightly less flexible than OP_EVAL, as it disallows dynamic interation
> with serialized scripts.
> * Static code analyzers need to deserialize script data.
>
> Credits: gmaxwell for the idea of a literal-only stack
>
> --
> Pieter
>
>
> ------------------------------------------------------------------------------
> Ridiculously easy VDI. With Citrix VDI-in-a-Box, you don't need a complex
> infrastructure or vast IT resources to deliver seamless, secure access to
> virtual desktops. With this all-in-one solution, easily deploy virtual
> desktops for less than the cost of PCs and save 60% on VDI infrastructure
> costs. Try it free! http://p.sf.net/sfu/Citrix-VDIinabox
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

On Fri, Dec 30, 2011 at 5:42 AM, <roconnor@theorem•ca> wrote:

> Basically OP_DUP lets you duplicate the code on the stack and that is the
> key to looping.  I'm pretty sure from here we get get Turing completeness.
> Using the stack operations I expect you can implement the SK-calculus
> given an OP_EVAL that allows arbitrary depth.
>
> OP_EVAL adds dangerously expressive power to the scripting language.

If you look at the archives of the concatenative programming mailing list [1] you'll see lots of examples of people creating stack languages with minimal operations that exploit similar functionality to reduce the required built in operations. The discussion on the list is mostly about stack based languages where programs can be pushed on the stack and executed (eg. Joy [2]/Factor/Some Forths).

I don't think the scripting engine in bitcoin has the ability to concatenate, append or otherwise manipulate scripts on the stack to be eval'd though does it?

[1] http://tech.groups.yahoo.com/group/concatenative
[2] http://tunes.org/~iepos/joy.html

Chris.

On Sat, 31 Dec 2011, Chris Double wrote:

> On Fri, Dec 30, 2011 at 5:42 AM,  <roconnor@theorem•ca> wrote:
>> Basically OP_DUP lets you duplicate the code on the stack and that is the
>> key to looping.  I'm pretty sure from here we get get Turing completeness.
>> Using the stack operations I expect you can implement the SK-calculus
>> given an OP_EVAL that allows arbitrary depth.
>>
>> OP_EVAL adds dangerously expressive power to the scripting language.
>
> If you look at the archives of the concatenative programming mailing
> list [1] you'll see lots of examples of people creating stack
> languages with minimal operations that exploit similar functionality
> to reduce the required built in operations. The discussion on the list
> is mostly about stack based languages where programs can be pushed on
> the stack and executed (eg. Joy [2]/Factor/Some Forths).
>
> I don't think the scripting engine in bitcoin has the ability to
> concatenate, append or otherwise manipulate scripts on the stack to be
> eval'd though does it?

It will limited ability manipulate scripts on the stack through the use of arithmetic and hashing operations, and if OP_CAT, OP_SUBSTR and friends are ever restored, it will have even more abilities.

Wouldn't it work to restrict the number of executions of OP_EVAL allowed per transaction? That way it wouldn't allow for unlimited looping. If there's too many OP_EVAL executions during the transaction evaluation, just consider the transaction illegal. 3 would be enough for the purposes people have been planning for here I think.

- Joel

On Thu, 2011-12-29 at 11:42 -0500, roconnor@theorem•ca wrote:

> On Thu, 29 Dec 2011, theymos wrote:
>
> > On Thu, Dec 29, 2011, at 01:55 AM, roconnor@theorem•ca wrote:
> >> The number of operations executed is still bounded by the number of
> >> operations occurring in the script.  With the OP_EVAL proposal the
> >> script language becomes essentially Turing complete, with only an
> >> artificial limit on recursion depth preventing arbitrary computation
> >> and there is no way to know what code will run without executing it.
> >
> > Even if OP_EVAL allowed infinite depth, you'd still need to explicitly
> > specify all operations performed, since there is no way of looping.
>
> That's not true.  Gavin himself showed how to use OP_EVAL to loop:
> OP_PUSHDATA {OP_DUP OP_EVAL} OP_DUP OP_EVAL.
>
> Basically OP_DUP lets you duplicate the code on the stack and that is the
> key to looping.  I'm pretty sure from here we get get Turing completeness.
> Using the stack operations I expect you can implement the SK-calculus
> given an OP_EVAL that allows arbitrary depth.
>
> OP_EVAL adds dangerously expressive power to the scripting language.
>

I agree with Joel. I think someone brought this up earlier as well. Most OP_EVAL transactions won't be complex enough to require more than a few loops.

--Zell

------------------------ "It stopped being just a website a long time ago. For many of us, most of us, Wikipedia has become an indispensable part of our daily lives." — Jimmy Wales, Founder of Wikipedia Help protect it now. Please make a donation today: http://www.wikimediafoundation.org/wiki/Donate

--- On Sat, 12/31/11, Joel Joonatan Kaartinen <joel.kaartinen@gmail•com> wrote:

> From: Joel Joonatan Kaartinen <joel.kaartinen@gmail•com>
> Subject: Re: [Bitcoin-development] Alternative to OP_EVAL
> To: roconnor@theorem•ca
> Cc: bitcoin-development@lists•sourceforge•net
> Date: Saturday, December 31, 2011, 4:54 AM
> Wouldn't it work to restrict the
> number of executions of OP_EVAL allowed
> per transaction? That way it wouldn't allow for unlimited
> looping. If
> there's too many OP_EVAL executions during the transaction
> evaluation,
> just consider the transaction illegal. 3 would be enough
> for the
> purposes people have been planning for here I think.
>
> - Joel
>
> On Thu, 2011-12-29 at 11:42 -0500, roconnor@theorem•ca
> wrote:
> > On Thu, 29 Dec 2011, theymos wrote:
> >
> > > On Thu, Dec 29, 2011, at 01:55 AM, roconnor@theorem•ca
> wrote:
> > >> The number of operations executed is still
> bounded by the number of
> > >> operations occurring in the script.
> With the OP_EVAL proposal the
> > >> script language becomes essentially Turing
> complete, with only an
> > >> artificial limit on recursion depth
> preventing arbitrary computation
> > >> and there is no way to know what code will
> run without executing it.
> > >
> > > Even if OP_EVAL allowed infinite depth, you'd
> still need to explicitly
> > > specify all operations performed, since there is
> no way of looping.
> >
> > That's not true.  Gavin himself showed how to use
> OP_EVAL to loop:
> > OP_PUSHDATA {OP_DUP OP_EVAL} OP_DUP OP_EVAL.
> >
> > Basically OP_DUP lets you duplicate the code on the
> stack and that is the
> > key to looping.  I'm pretty sure from here we get
> get Turing completeness.
> > Using the stack operations I expect you can implement
> the SK-calculus
> > given an OP_EVAL that allows arbitrary depth.
> >
> > OP_EVAL adds dangerously expressive power to the
> scripting language.
> >
>
>
>
> ------------------------------------------------------------------------------
> Ridiculously easy VDI. With Citrix VDI-in-a-Box, you don't
> need a complex
> infrastructure or vast IT resources to deliver seamless,
> secure access to
> virtual desktops. With this all-in-one solution, easily
> deploy virtual
> desktops for less than the cost of PCs and save 60% on VDI
> infrastructure
> costs. Try it free! http://p.sf.net/sfu/Citrix-VDIinabox
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

The OP_EVAL discussion went into some private discussion for a bit, so here is a summary of what we talked about.

Roconnor pointed out that the currently proposed OP_EVAL removes the ability to statically reason about scripts. Justmoon pointed out that this is evidenced by the changes to GetSigOpCount:

Currently, the client first counts the number of sigops and if it is over a certain limit, it doesn't execute the script at all. This is no longer possible with OP_EVAL, since OP_EVAL can stand for any number of other operations, which might be part of some piece of data. The script that is executed by OP_EVAL can be changed (polymorphic code). Gavin's patch deals with this, by counting the sigops at runtime and aborting only after the limit has been reached.

Here is an example for a script that based on naive counting contains no sigops, but in fact contains 20:

[20 signatures] 20 [pubkey] OP_DUP OP_DUP OP_2DUP OP_3DUP OP_3DUP OP_3DUP OP_3DUP OP_3DUP 20 "58959998C76C231F" OP_RIPEMD160 OP_EVAL

RIPEMD160( 58 95 99 98 C7 6C 23 1F )

hashes to

AE4C10400B7DF3A56FE2B32B9906BCF1B1AFE975

which OP_EVAL interprets as

OP_CHECKMULTISIG "400B7DF3A56FE2B32B9906BCF1B1AFE9" OP_DROP

The nonce 58959998C76C231F was generated using this code: https://gist.github.com/1546061

Gavin and Amir argued that it is possible to "dry run" the script, avoiding the expensive OP_CHECKSIG operation and running only the other very cheap operations. However, sipa pointed out that in the presence of an OP_CHECKSIG a dry runner cannot predict the outcome of conditional branches, so it has to either do the OP_CHECKSIG (and become just a regular execution) or it has to follow both branches. Roconnor and justmoon suggested the following script to illustrate this point:

[sig] [pubkey] [some data] [sig] [pubkey] OP_CHECKSIG OP_IF OP_HASH160 OP_ELSE OP_HASH256 OP_ENDIF (previous line repeated 33 times with different sigs/pubkeys) OP_EVAL

This script is valid assuming that the resulting hash from the branch that is chosen based on what signatures are valid contains an OP_CHECKSIG. (And the initial [sig] and [pubkey] are valid.) But a dry runner trying to count how many OP_CHECKSIGs this script contains would run into the first OP_CHECKSIG OP_IF and have to run both branches. In both branches it would again encounter a OP_CHECKSIG OP_IF and run all four branches, etc. In total it has to run (2^33 - 2) * 1.5 SHA256 operations (8 GHash) and 2^32 - 1 RIPEMD160 operations. Therefore we now believe a dry runner is not possible or at least too complicated to be involved in protocol rules such as the sigops limit.

As a result people are now on a spectrum from those who feel strongly that static analysis is an important property and not something to give up easily all the way to those who think it's superfluous and the other side is just unnecessarily delaying OP_EVAL deployment.

One thing I want to note is that static analysis is a property for which there is a better argument than for other, weaker properties, such as limited recursion depth. Bitcoin currently allows you to:

* Tell if a script contains a specific opcode or not
* Count how many times a script will execute an operation at most
* Count how many total operations a script will execute at most
* Count how many signatures a script will execute at most
* Find the maximum length of a datum pushed onto the stack
* Find the maximum number of items that can be pushed onto the stack
* Find the maximum size (in bytes) of the stack
* Calculate how long a script will run at most

OP_EVAL as proposed makes these upper bounds almost meaningless as it can contain, indirectly, up to 32 instances of any other opcode. (About 3-6 instances are currently practical.) The only way to answer these questions would then be to fully execute the script.

Suppose we want to one day allow arbitrary scripts as IsStandard, but put constraints on them, such as enforcing a subset of allowed opcodes. (See list above for other possible restrictions.) If we want to include OP_EVAL in the set of allowed opcodes, it's important that OP_EVAL is implemented in a way that allows static analysis, because we can then allow it while still maintaining other restrictions.

If proponents of the current implementation want to argue that we don't need static analysis now, the burden is on them to show how we could retrofit it when/if we get to this point or why they think we will never want to allow some freedom in IsStandard that includes OP_EVAL.

There are several proposals for OP_EVAL that allow static analysis:

* Using a fixed position reference prefix (sipa)
* Using an execute bit on data set by an opcode (justmoon)
* Using OP_CODEHASH (roconnor)
* Using OP_CHECKEDEVAL (sipa)
* Using OP_HASH160 OP_EQUALVERIFY as a special sigPubKey (gavinandresen)

Let's fully develop these proposals and see how much of a hassle it would actually be to get a statically verifiable OP_EVAL. I think that's a prerequisite for having the argument on whether it is *worth* the hassle.

(Update: Gavin's latest proposal looks *very* good, so that may settle the debate quickly.)

On 12/30/2011 6:19 PM, roconnor@theorem•ca wrote:

> On Sat, 31 Dec 2011, Chris Double wrote:
>
>> On Fri, Dec 30, 2011 at 5:42 AM, <roconnor@theorem•ca> wrote:
>>> Basically OP_DUP lets you duplicate the code on the stack and that
>>> is the
>>> key to looping.  I'm pretty sure from here we get get Turing
>>> completeness.
>>> Using the stack operations I expect you can implement the SK-calculus
>>> given an OP_EVAL that allows arbitrary depth.
>>>
>>> OP_EVAL adds dangerously expressive power to the scripting language.
>>
>> If you look at the archives of the concatenative programming mailing
>> list [1] you'll see lots of examples of people creating stack
>> languages with minimal operations that exploit similar functionality
>> to reduce the required built in operations. The discussion on the list
>> is mostly about stack based languages where programs can be pushed on
>> the stack and executed (eg. Joy [2]/Factor/Some Forths).
>>
>> I don't think the scripting engine in bitcoin has the ability to
>> concatenate, append or otherwise manipulate scripts on the stack to be
>> eval'd though does it?
>
> It will limited ability manipulate scripts on the stack through the
> use of arithmetic and hashing operations, and if OP_CAT, OP_SUBSTR and
> friends are ever restored, it will have even more abilities.
>
>
>
> ------------------------------------------------------------------------------
> Ridiculously easy VDI. With Citrix VDI-in-a-Box, you don't need a complex
> infrastructure or vast IT resources to deliver seamless, secure access to
> virtual desktops. With this all-in-one solution, easily deploy virtual
> desktops for less than the cost of PCs and save 60% on VDI infrastructure
> costs. Try it free! http://p.sf.net/sfu/Citrix-VDIinabox
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Here are my latest thoughts on a safer OP_EVAL alternative, inspired by all the ideas and agitated IRC and email discussions of the last week or so:

Goal: Let users publish a short "funding address" that is the hash of an arbitrary redemption Script revealed when they spend the funds, implemented in a backwards-compatible-in-the-blockchain way.

Proposal:

A new 'standard' transaction type, "pay to Script hash":

scriptPubKey: HASH160 <push-20-byte-hash> EQUAL

Redeemed with the same scriptSig as the OP_EVAL proposal: <signatures> <serialized Script>

Old clients/miners will ignore <signatures> and just validate that the hash of <serialized Script> matches.

New clients/miners will recognize the new type of transaction and will do the following additional validation:

1. Fail validation if there were any operations other than "push data" in the original scriptSig. 2. Deserialize the top (last) item on the scriptSig stack (fail validation if it fails to deserialize properly). 3. Run an additional validation on the deserialized script, using the remaining items on the scriptSig stack and the deserialized script as the scriptPubKey.

---------------

As Amir said in IRC chat today, "the idea is a hack.... but I like it."

I like it, too-- it is cleaner than OP_EVAL, more straightforward to implement, and pretty much exactly matches the feature I care about (moving code from the scriptPubKey to the scriptSig). There are no special cases like "CODESEPARATORS not allowed in <serialized script>".

Seems ... acceptable from first glance.

Though I propose an ammendent to either

(1)

make the script: OP_NOP1 HASH160 <push-20-byte-hash> EQUAL to make it extremely easy to see from the first byte that this is verly likely to be a special transaction (or more accurately if the first byte isn't OP_NOP1 then you immediately know it isn't a special script and can even disregard the token).

or

(2)

If you are feel like spending another byte make the script: OP_NOP1 <push-special-script-version-number> <special-script>

and assign 1 to this special script, making this case:

OP_NOP1 OP_1 HASH160 <push-20-byte-hash> EQUAL

On Mon, 2 Jan 2012, Gavin Andresen wrote:

> Here are my latest thoughts on a safer OP_EVAL alternative, inspired
> by all the ideas and agitated IRC and email
> discussions of the last week or so:
>
> Goal:  Let users publish a short "funding address" that is the hash of
> an arbitrary redemption Script revealed when they spend the funds,
> implemented in a backwards-compatible-in-the-blockchain way.
>
> Proposal:
>
> A new 'standard' transaction type, "pay to Script hash":
>
> scriptPubKey:  HASH160 <push-20-byte-hash>  EQUAL
>
> Redeemed with the same scriptSig as the OP_EVAL proposal:
> <signatures> <serialized Script>
>
> Old clients/miners will ignore <signatures> and just validate that the
> hash of <serialized Script> matches.
>
> New clients/miners will recognize the new type of transaction and will
> do the following additional validation:
>
> 1. Fail validation if there were any operations other than "push data"
> in the original scriptSig.
> 2. Deserialize the top (last) item on the scriptSig stack (fail
> validation if it fails to deserialize properly).
> 3. Run an additional validation on the deserialized script, using the
> remaining items on the scriptSig stack and the deserialized script as
> the scriptPubKey.
>
>
> ---------------
>
> As Amir said in IRC chat today, "the idea is a hack.... but I like it."
>
> I like it, too-- it is cleaner than OP_EVAL, more straightforward to
> implement, and pretty much exactly matches the feature I care about
> (moving code from the scriptPubKey to the scriptSig). There are no
> special cases like "CODESEPARATORS not allowed in <serialized
> script>".
>
>

+1. I love this proposal.

It's two less bytes than OP_EVAL even. It allows static analysis. It doesn't require any change to the script interpreter. (You can do a static replacement step between parsing and execution.) It allows all urgent use cases. It doesn't consume a NOP. If we ever want recursion or something else, we can still add OP_EVAL,... then.

@roconnor:

> 1. make the script: OP_NOP1 HASH160 <push-20-byte-hash> EQUAL to make
> it extremely easy to see from the first byte that this is verly likely
> to be a special transaction (or more accurately if the first byte
> isn't OP_NOP1 then you immediately know it isn't a special script and
> can even disregard the token).

I disagree. If people actually do mean HASH160 <hash> EQUAL, let *them* add a NOP. Or better to avoid NOP let them use HASH160 <hash> EQUALVERIFY 1. Point is, if you don't want code replacement you can easily break the pattern. But code replacement will be overwhelmingly more common, so it should be as small as possible. Every byte matters.

On 1/2/2012 4:59 PM, Gavin Andresen wrote:

> Here are my latest thoughts on a safer OP_EVAL alternative, inspired
> by all the ideas and agitated IRC and email
> discussions of the last week or so:
>
> Goal:  Let users publish a short "funding address" that is the hash of
> an arbitrary redemption Script revealed when they spend the funds,
> implemented in a backwards-compatible-in-the-blockchain way.
>
> Proposal:
>
> A new 'standard' transaction type, "pay to Script hash":
>
> scriptPubKey:  HASH160<push-20-byte-hash>   EQUAL
>
> Redeemed with the same scriptSig as the OP_EVAL proposal:
> <signatures>  <serialized Script>
>
> Old clients/miners will ignore<signatures>  and just validate that the
> hash of<serialized Script>  matches.
>
> New clients/miners will recognize the new type of transaction and will
> do the following additional validation:
>
> 1. Fail validation if there were any operations other than "push data"
> in the original scriptSig.
> 2. Deserialize the top (last) item on the scriptSig stack (fail
> validation if it fails to deserialize properly).
> 3. Run an additional validation on the deserialized script, using the
> remaining items on the scriptSig stack and the deserialized script as
> the scriptPubKey.
>
>
> ---------------
>
> As Amir said in IRC chat today, "the idea is a hack.... but I like it."
>
> I like it, too-- it is cleaner than OP_EVAL, more straightforward to
> implement, and pretty much exactly matches the feature I care about
> (moving code from the scriptPubKey to the scriptSig). There are no
> special cases like "CODESEPARATORS not allowed in<serialized
> script>".
>