[Bitcoin-development] Alternative to OP_EVAL

[Bitcoin-development] Alternative to OP_EVAL

[roconnor]

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.

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''

Re: [Bitcoin-development] Alternative to OP_EVAL

[theymos]

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

Re: [Bitcoin-development] Alternative to OP_EVAL

[roconnor]

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.

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''

Re: [Bitcoin-development] Alternative to OP_EVAL

[Chris Double]

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.
-- 
http://www.bluishcoder.co.nz

Re: [Bitcoin-development] Alternative to OP_EVAL

[roconnor]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1533 bytes --]

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.

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''

Re: [Bitcoin-development] Alternative to OP_EVAL

[Stefan Thomas]

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

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


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

Re: [Bitcoin-development] Alternative to OP_EVAL

[Gavin Andresen]

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

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Alternative to OP_EVAL

[roconnor]

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

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''

Re: [Bitcoin-development] Alternative to OP_EVAL

[Stefan Thomas]

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

Re: [Bitcoin-development] Alternative to OP_EVAL

[Joel Joonatan Kaartinen]

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

Re: [Bitcoin-development] Alternative to OP_EVAL

[Zell Faze]

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
>

Re: [Bitcoin-development] Alternative to OP_EVAL

[Gavin Andresen]

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.

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Alternative to OP_EVAL

[roconnor]

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.

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''

Re: [Bitcoin-development] Alternative to OP_EVAL

[Luke-Jr]

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: [Bitcoin-development] Alternative to OP_EVAL

[Gavin Andresen]

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.

-- 
--
Gavin Andresen

Re: [Bitcoin-development] Alternative to OP_EVAL

[Stefan Thomas]

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

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


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

Re: [Bitcoin-development] Alternative to OP_EVAL

[Pieter Wuille]

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

Re: [Bitcoin-development] Alternative to OP_EVAL

[Pieter Wuille]

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

-- 
Pieter  

Re: [Bitcoin-development] Alternative to OP_EVAL

[Alan Reiner]

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

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
>

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