Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.215.47 as permitted sender)
	client-ip=209.85.215.47; envelope-from=joel.kaartinen@gmail.com;
	helo=mail-lpp01m010-f47.google.com; 
From: Joel Joonatan Kaartinen <joel.kaartinen@gmail.com>
To: roconnor@theorem.ca
In-Reply-To: <alpine.LRH.2.00.1112291135040.22327@theorem.ca>
References: <alpine.LRH.2.00.1112290111310.22327@theorem.ca>
	<1325148259.14431.140661016987461@webmail.messagingengine.com>
	<alpine.LRH.2.00.1112291135040.22327@theorem.ca>
Content-Type: text/plain; charset="UTF-8"
Date: Sat, 31 Dec 2011 11:54:13 +0200
Message-ID: <1325325253.2800.3.camel@mei>
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Alternative to OP_EVAL
Precedence: list

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