Re: [Bitcoin-development] Alternative to OP_EVAL
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.'' -- 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
+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: HASH160push-20-byte-hash EQUAL Redeemed with the same scriptSig as the OP_EVAL proposal: signatures serialized Script Old clients/miners will ignoresignatures and just validate that the hash ofserialized 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 inserialized 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
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
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.kaarti...@gmail.com wrote:
From: Joel Joonatan Kaartinen joel.kaarti...@gmail.com
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
On Fri, Dec 30, 2011 at 5:42 AM, rocon...@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 -- 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
On Sat, 31 Dec 2011, Chris Double wrote: On Fri, Dec 30, 2011 at 5:42 AM, rocon...@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.''-- 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
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 scriptHash OP_EQUAL and is redeemed using [script input] script -- 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
Re: [Bitcoin-development] Alternative to OP_EVAL
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 POSThttp://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.wui...@gmail.comwrote: 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 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
