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  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  EQUAL, let *them* 
add a NOP. Or better to avoid NOP let them use HASH160  
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   EQUAL
>
> Redeemed with the same scriptSig as the OP_EVAL proposal:
>   
>
> Old clients/miners will ignore  and just validate that the
> hash of  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 script>".
>


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

[roconnor]

Seems ... acceptable from first glance.

Though I propose an ammendent to either

(1)

make the script: OP_NOP1 HASH160  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  

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

OP_NOP1 OP_1 HASH160  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   EQUAL
>
> Redeemed with the same scriptSig as the OP_EVAL proposal:
>  
>
> Old clients/miners will ignore  and just validate that the
> hash of  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  script>".
>
>

-- 
Russell O'Connor  
``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.''

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

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   EQUAL

Redeemed with the same scriptSig as the OP_EVAL proposal:
 

Old clients/miners will ignore  and just validate that the
hash of  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 ".

-- 
--
Gavin Andresen

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

[Stefan Thomas]

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

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

> From: Joel Joonatan Kaartinen 
> Subject: Re: [Bitcoin-development] Alternative to OP_EVAL
> To: rocon...@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, rocon...@theorem.ca
> wrote:
> > On Thu, 29 Dec 2011, theymos wrote:
> > 
> > > On Thu, Dec 29, 2011, at 01:55 AM, rocon...@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
> 

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

[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, rocon...@theorem.ca wrote:
> On Thu, 29 Dec 2011, theymos wrote:
> 
> > On Thu, Dec 29, 2011, at 01:55 AM, rocon...@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

[roconnor]

On Sat, 31 Dec 2011, Chris Double wrote:


On Fri, Dec 30, 2011 at 5:42 AM,   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  
``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.''--
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

[Chris Double]

On Fri, Dec 30, 2011 at 5:42 AM,   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

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

[Alan Reiner]

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

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

> On Thu, Dec 29, 2011 at 01:55:03AM -0500, rocon...@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 < 

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, rocon...@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  OP_EQUAL

and is redeemed using

  [script input] <

Re: [Bitcoin-development] Alternative to OP_EVAL

[Stefan Thomas]

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:  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:  
scriptPuKey:
   IF  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:  

scriptPubKey:  ... standard DUP HASH160<>  EQUALVERIFY EVAL

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

  CODESEPARATOR this_or_that_code
  CODEHASH
  CODESEPARATOR
  IF  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.



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

[Pieter Wuille]

On Thu, Dec 29, 2011 at 01:55:03AM -0500, rocon...@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 < 

Re: [Bitcoin-development] Alternative to OP_EVAL

[Gavin Andresen]

RE: preventing OP_EVAL from executing the result of calculations:

> This is not adequate:  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:   
scriptPuKey:
  IF  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:   

scriptPubKey:  ... standard DUP HASH160 <> EQUALVERIFY EVAL

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

   CODESEPARATOR this_or_that_code
 CODEHASH
 CODESEPARATOR
 IF  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

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

[Luke-Jr]

On Thursday, December 29, 2011 12:01:20 PM rocon...@theorem.ca wrote:
> This is not adequate:  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.

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

[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.  CHECKSIG  becomes   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:
>OP_ADD OP_EVAL  <-- Look! Dragons!
>
> If  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:  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  
``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.''

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

[roconnor]

On Thu, 29 Dec 2011, theymos wrote:

> On Thu, Dec 29, 2011, at 01:55 AM, rocon...@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  
``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.''

--
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.  CHECKSIG  becomes   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:
OP_ADD OP_EVAL  <-- Look! Dragons!

If  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

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