Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.212.175 as permitted sender)
	client-ip=209.85.212.175; envelope-from=etotheipi@gmail.com;
	helo=mail-wi0-f175.google.com; 
MIME-Version: 1.0
In-Reply-To: <20111229190838.GA29609@ulyssis.org>
References: <alpine.LRH.2.00.1112290111310.22327@theorem.ca>
	<20111229190838.GA29609@ulyssis.org>
Date: Thu, 29 Dec 2011 16:31:11 -0500
Message-ID: <CALf2ePzoC85=16h63ngn-KaEHDSYFqAOkW7UWqB_Jgd2F_pkTQ@mail.gmail.com>
From: Alan Reiner <etotheipi@gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>
Content-Type: multipart/alternative; boundary=0016e6d59d69d54dbe04b541d5c8
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Alternative to OP_EVAL
Precedence: list

--0016e6d59d69d54dbe04b541d5c8
Content-Type: text/plain; charset=ISO-8859-1

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
>

--0016e6d59d69d54dbe04b541d5c8
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div>I haven&#39;t been much a part of these brainstorming discussions, and=
 so I&#39;m really looking at this from a bird&#39;s eye view, without any =
bias towards any particular idea.=A0</div><div><br></div><meta http-equiv=
=3D"content-type" content=3D"text/html; charset=3Dutf-8"><div>
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. =
=A0I cannot tell from my position if there is/has been consistent concern f=
or OP_EVAL proposal, or if it&#39;s mostly a transient response to hearing =
about recursion in the scripting engine, etc (like myself, originally). =A0=
I haven&#39;t debated this topic much, so I&#39;m not in a position to pers=
onally comment on any proposals. =A0(Though, this all feels very similar to=
 the problem of=A0<a href=3D"http://www.securityweek.com/hash-table-collisi=
on-attacks-could-trigger-ddos-massive-scale">hash-table collisions in HTTP =
POST</a>).=A0</div>
<meta http-equiv=3D"content-type" content=3D"text/html; charset=3Dutf-8"><d=
iv><br></div><div>However, I would like to remind everyone that we/you are =
messing with a $20+ million dollar <i>thing</i>. =A0There&#39;s more than j=
ust a piece of software at stake -- whatever goes in needs to be as hard as=
 diamond. =A0If 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. =A0Roconner is persuasive enough to make <b>me</b> think that =
not all corners of this functional space has been explored properly. =A0And=
 while my opinion doesn&#39;t matter, I&#39;m concerned that others may fee=
l too invested in the current design path to want to &quot;go backwards.&qu=
ot; =A0Again, I don&#39;t know one way or another, I just want to warn agai=
nst pride getting priority over security. =A0=A0</div>
<div><br></div><div>At the very least, you should consider consequences and=
 recovery path of such unanticipated problems. =A0If the things that could =
go wrong are devastating, let&#39;s lean towards a more conservative soluti=
on (like sandboxing the sub-scripting engine).=A0=A0=A0Remember, the networ=
k is working just fine <b>without </b>OP_EVAL, and while OP_EVAL provides s=
ome really nice benefits, I don&#39;t think the benefits over regular multi=
-sig are worth the consequences of making a mistake in this multi-million d=
ollar beast.</div>
<div><br></div><div>Okay, back to your regularly-scheduled debating...</div=
>
-Alan<br><br><div class=3D"gmail_quote">On Thu, Dec 29, 2011 at 2:08 PM, Pi=
eter Wuille <span dir=3D"ltr">&lt;<a href=3D"mailto:pieter.wuille@gmail.com=
" target=3D"_blank">pieter.wuille@gmail.com</a>&gt;</span> wrote:<br><block=
quote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc=
 solid;padding-left:1ex">

<div>On Thu, Dec 29, 2011 at 01:55:03AM -0500, <a href=3D"mailto:roconnor@t=
heorem.ca" target=3D"_blank">roconnor@theorem.ca</a> wrote:<br>
&gt; Gavin asked me to come up with an alternative to OP_EVAL, so here is m=
y<br>
&gt; proposal.<br>
&gt;<br>
&gt; OP_CODEHASH Initial Proposal<br>
<br>
</div>If we&#39;re again brainstorming about alternatives for OP_EVAL, I&#3=
9;ll do my own.<br>
<br>
It is called OP_CHECKEDEVAL, and is specified as follows:<br>
* It looks at the two elements most recently (in code position) pushed by a=
 literal,<br>
 =A0and not yet consumed by another OP_CHECKEDEVAL. These are S (the serial=
ized script),<br>
 =A0and H (its hash). This implies it defines its own literal-only stack, w=
here all<br>
 =A0literals push to, and only OP_CHECKEDEVAL pops from. This special stack=
 has the<br>
 =A0advantage of allowing static analysis - one does not need to execute an=
y operations<br>
 =A0to find out which data will end up on it. Note that &quot;skipped&quot;=
 code (inside the<br>
 =A0ignored part of an IF-THEN-ELSE) can still push to the literal stack.<b=
r>
* For the &quot;outer script&quot;, it does not have any effect at all, exc=
ept for:<br>
 =A0* 2 elements popped from the literal-only stack<br>
 =A0* potentially causing failure<br>
 =A0It does not touch the main stack, alt stack or any other part of the ex=
ecution state<br>
 =A0not listed above.<br>
* Failure is caused when either of these conditions hold:<br>
 =A0* No two elements remain on the literal-only stack<br>
 =A0* The Hash(S) !=3D H<br>
 =A0* The inner script execution caused failure<br>
* For the execution of the inner script:<br>
 =A0* It is executed in a completely new and independent execution environn=
ement<br>
 =A0* It executes the deserialized S<br>
 =A0* It inherits the main stack and alt stack (without the serialized scri=
pt and the hash<br>
 =A0 =A0themselves) from the outer execution.<br>
<br>
This requires OP_CHECKEDEVAL to immediately follow the push of script and h=
ash,<br>
so the code in the pair &lt; &lt;script&gt; OP_CHECKEDEVAL &gt; can be pars=
ed and interpreted as code,<br>
allowing static analysis.<br>
<br>
As OP_CHECKEDEVAL has absolutely no effects except for potentially causing =
failure, it<br>
is very similar to the OP_NOPx it would replace, and guarantees that interp=
reting<br>
OP_CHECKEDEVAL as OP_NOPx can never cause the script to become invalid if i=
t wasn&#39;t<br>
already.<br>
<br>
A basic pay-to-script-hash scriptPubKey is very short:<br>
<br>
 =A0&lt;scriptHash&gt; OP_CHECKEDEVAL<br>
<br>
And it is redeemed using:<br>
<br>
 =A0&lt;script inputs&gt; &lt;script&gt;<br>
<br>
Furthermore, the implementation is very similar to what was already done fo=
r<br>
OP_EVAL. Modifications:<br>
* EvalScriptInner needs less by-ref arguments, as it cannot modify the pare=
nt&#39;s state.<br>
* A literal-only stack needs to be maintained.<br>
<br>
<br>
I believe this combines all advantages:<br>
* Easy spend-to-script-hash (shorter than OP_EVAL)<br>
* Backward compatible (guaranteed by construction, instead of separately en=
forced like with OP_EVAL)<br>
* Statically analyzable (though it requires deserializing the script data).=
<br>
* Possibility to introduce a new language inside (not done in this proposal=
)<br>
<br>
Only disadvantages:<br>
* Slightly less flexible than OP_EVAL, as it disallows dynamic interation w=
ith serialized scripts.<br>
* Static code analyzers need to deserialize script data.<br>
<br>
Credits: gmaxwell for the idea of a literal-only stack<br>
<span><font color=3D"#888888"><br>
--<br>
Pieter<br>
</font></span><div><div><br>
---------------------------------------------------------------------------=
---<br>
Ridiculously easy VDI. With Citrix VDI-in-a-Box, you don&#39;t need a compl=
ex<br>
infrastructure or vast IT resources to deliver seamless, secure access to<b=
r>
virtual desktops. With this all-in-one solution, easily deploy virtual<br>
desktops for less than the cost of PCs and save 60% on VDI infrastructure<b=
r>
costs. Try it free! <a href=3D"http://p.sf.net/sfu/Citrix-VDIinabox" target=
=3D"_blank">http://p.sf.net/sfu/Citrix-VDIinabox</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net" target=3D"_bla=
nk">Bitcoin-development@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</div></div></blockquote></div><br>

--0016e6d59d69d54dbe04b541d5c8--