summaryrefslogtreecommitdiff
path: root/8d/e39edc8cfa00da2fc4319c9dbc0bedff46c390
blob: 3ff29069f8aae951276b7f3504db7fbd3e59b8cb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
	helo=mx.sourceforge.net)
	by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <moon@justmoon.de>) id 1Rhjb7-0001b9-Cq
	for bitcoin-development@lists.sourceforge.net;
	Mon, 02 Jan 2012 15:14:49 +0000
X-ACL-Warn: 
Received: from sulfur.webpack.hosteurope.de ([217.115.142.104])
	by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
	id 1Rhjb5-0001jV-46 for bitcoin-development@lists.sourceforge.net;
	Mon, 02 Jan 2012 15:14:49 +0000
Received: from 84-72-69-153.dclient.hispeed.ch ([84.72.69.153]
	helo=[192.168.0.21]); authenticated
	by sulfur.webpack.hosteurope.de running ExIM with esmtpsa
	(TLSv1:AES256-SHA:256)
	id 1Rhjay-0001uP-RN; Mon, 02 Jan 2012 16:14:40 +0100
Message-ID: <4F01C9D8.10107@justmoon.de>
Date: Mon, 02 Jan 2012 16:14:32 +0100
From: Stefan Thomas <moon@justmoon.de>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64;
	rv:8.0) Gecko/20111105 Thunderbird/8.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <alpine.LRH.2.00.1112290111310.22327@theorem.ca>
	<1325148259.14431.140661016987461@webmail.messagingengine.com>
	<alpine.LRH.2.00.1112291135040.22327@theorem.ca>
	<CALn1vHHjY6Qq0zEUcWaNzm_eP_JekjrK26zMXfcrfPSydwSKig@mail.gmail.com>
	<alpine.LRH.2.00.1112301214380.9419@theorem.ca>
In-Reply-To: <alpine.LRH.2.00.1112301214380.9419@theorem.ca>
Content-Type: multipart/alternative;
	boundary="------------070008060708020207040002"
X-bounce-key: webpack.hosteurope.de;moon@justmoon.de;1325517287;36bd9b03;
X-Spam-Score: 2.1 (++)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
	See http://spamassassin.org/tag/ for more details.
	1.1 TRACKER_ID             BODY: Incorporates a tracking ID number
	1.0 HTML_MESSAGE           BODY: HTML included in message
X-Headers-End: 1Rhjb5-0001jV-46
Subject: Re: [Bitcoin-development] Alternative to OP_EVAL
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Mon, 02 Jan 2012 15:14:49 -0000

This is a multi-part message in MIME format.
--------------070008060708020207040002
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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


--------------070008060708020207040002
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

<html>
  <head>
    <meta content="text/html; charset=ISO-8859-1"
      http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <div class="" id="magicdomid2"><span
        class="author-g-ijgixz122zfb16tkorac">The OP_EVAL discussion
        went into some private discussion for a bit, so here is a
        summary of what we talked about.</span></div>
    <div class="" id="magicdomid3"><br>
    </div>
    <div class="" id="magicdomid4"><span
        class="author-g-ijgixz122zfb16tkorac">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:</span></div>
    <div class="" id="magicdomid5"><br>
    </div>
    <div class="ace-line" id="magicdomid2548"><span
        class="author-g-ijgixz122zfb16tkorac">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. </span><span
        class="author-g-awz122znrs6wexay424a">The script that is
        executed by OP_EVAL can be changed (polymorphic code). </span><span
        class="author-g-ijgixz122zfb16tkorac">Gavin's patch deals with
        this, by counting the sigops at runtime and aborting only after
        the limit has been reached.</span></div>
    <div class="" id="magicdomid7"><br>
    </div>
    <div class="" id="magicdomid8"><span
        class="author-g-ijgixz122zfb16tkorac">Here is an example for a
        script that based on naive counting contains no sigops, but in
        fact contains 20:</span></div>
    <div class="" id="magicdomid9"><br>
    </div>
    <div class="" id="magicdomid10"><span
        class="author-g-ijgixz122zfb16tkorac">[20 signatures] 20
        [pubkey] OP_DUP OP_DUP OP_2DUP OP_3DUP OP_3DUP&nbsp;&nbsp;&nbsp;&nbsp; OP_3DUP
        OP_3DUP OP_3DUP 20 "58959998C76C231F" OP_RIPEMD160 OP_EVAL</span></div>
    <div class="" id="magicdomid11"><br>
    </div>
    <div class="" id="magicdomid12"><span
        class="author-g-ijgixz122zfb16tkorac">RIPEMD160( 58 95 99 98 C7
        6C 23 1F )&nbsp;</span></div>
    <div class="" id="magicdomid13"><br>
    </div>
    <div class="" id="magicdomid14"><span
        class="author-g-ijgixz122zfb16tkorac">hashes to&nbsp;</span></div>
    <div class="" id="magicdomid15"><br>
    </div>
    <div class="" id="magicdomid16"><span
        class="author-g-ijgixz122zfb16tkorac">AE4C10400B7DF3A56FE2B32B9906BCF1B1AFE975&nbsp;</span></div>
    <div class="" id="magicdomid17"><br>
    </div>
    <div class="" id="magicdomid18"><span
        class="author-g-ijgixz122zfb16tkorac">which OP_EVAL interprets
        as&nbsp;</span></div>
    <div class="" id="magicdomid19"><br>
    </div>
    <div class="" id="magicdomid20"><span
        class="author-g-ijgixz122zfb16tkorac">OP_CHECKMULTISIG
        "400B7DF3A56FE2B32B9906BCF1B1AFE9" OP_DROP</span></div>
    <div class="" id="magicdomid21"><br>
    </div>
    <div class="" id="magicdomid22"><span
        class="author-g-ijgixz122zfb16tkorac">The nonce 58959998C76C231F
        was generated using this code: </span><span
        class="author-g-ijgixz122zfb16tkorac url"><a
          href="https://gist.github.com/1546061">https://gist.github.com/1546061</a></span></div>
    <div class="" id="magicdomid23"><br>
    </div>
    <div class="ace-line" id="magicdomid1985"><span
        class="author-g-ijgixz122zfb16tkorac">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 </span><span
        class="author-g-z122zttkgdbz122zi55udkp3">in the presence </span><span
        class="author-g-ijgixz122zfb16tkorac">of an OP_CHECKSIG a dry
        runner cannot predict the outcome </span><span
        class="author-g-z122zttkgdbz122zi55udkp3">of conditional
        branches, </span><span class="author-g-ijgixz122zfb16tkorac">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:</span></div>
    <div class="" id="magicdomid25"><br>
    </div>
    <div class="" id="magicdomid26"><span
        class="author-g-ijgixz122zfb16tkorac">[sig] [pubkey]</span></div>
    <div class="" id="magicdomid27"><span
        class="author-g-ijgixz122zfb16tkorac">[some data]</span></div>
    <div class="" id="magicdomid28"><span
        class="author-g-ijgixz122zfb16tkorac">[sig] [pubkey] OP_CHECKSIG
        OP_IF OP_HASH160 OP_ELSE OP_HASH256 OP_ENDIF</span></div>
    <div class="" id="magicdomid29"><span
        class="author-g-ijgixz122zfb16tkorac">(previous line repeated 33
        times with different sigs/pubkeys)</span></div>
    <div class="" id="magicdomid30"><span
        class="author-g-ijgixz122zfb16tkorac">OP_EVAL</span></div>
    <div class="" id="magicdomid31"><br>
    </div>
    <div class="ace-line" id="magicdomid2368"><span
        class="author-g-ijgixz122zfb16tkorac">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.</span></div>
    <div class="" id="magicdomid33"><br>
    </div>
    <div class="ace-line" id="magicdomid2370"><span
        class="author-g-ijgixz122zfb16tkorac">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.</span></div>
    <div class="ace-line" id="magicdomid55"><br>
    </div>
    <div class="ace-line" id="magicdomid652"><span
        class="author-g-ijgixz122zfb16tkorac">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:</span></div>
    <div class="ace-line" id="magicdomid350"><br>
    </div>
    <div class="ace-line" id="magicdomid539"><span
        class="author-g-ijgixz122zfb16tkorac">* Tell if a script
        contains a specific opcode or not</span></div>
    <div class="ace-line" id="magicdomid514"><span
        class="author-g-ijgixz122zfb16tkorac">* Count how many times a
        script will execute an operation at most</span></div>
    <div class="ace-line" id="magicdomid2371"><span
        class="author-g-ijgixz122zfb16tkorac">* Count how many total
        operations a script will execute at most</span></div>
    <div class="ace-line" id="magicdomid2427"><span
        class="author-g-ijgixz122zfb16tkorac">* Count how many
        signatures a script will execute at most</span></div>
    <div class="ace-line" id="magicdomid973"><span
        class="author-g-xpgmmks0434kl4ob">* Find the maximum length of a
        datum pushed onto the stack</span></div>
    <div class="ace-line" id="magicdomid1035"><span
        class="author-g-ijgixz122zfb16tkorac">* Find the maximum number
        of items that can be pushed onto the stack</span></div>
    <div class="ace-line" id="magicdomid2428"><span
        class="author-g-ijgixz122zfb16tkorac">* Find the maximum size
        (in bytes) of the stack</span></div>
    <div class="ace-line" id="magicdomid2470"><span
        class="author-g-ijgixz122zfb16tkorac">* Calculate how long a
        script will run at most</span></div>
    <div class="ace-line" id="magicdomid566"><br>
    </div>
    <div class="ace-line" id="magicdomid2471"><span
        class="author-g-ijgixz122zfb16tkorac">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.</span></div>
    <div class="ace-line" id="magicdomid768"><br>
    </div>
    <div class="ace-line" id="magicdomid2354"><span
        class="author-g-ijgixz122zfb16tkorac">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.</span></div>
    <div class="ace-line" id="magicdomid839"><br>
    </div>
    <div class="ace-line" id="magicdomid838"><span
        class="author-g-ijgixz122zfb16tkorac">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.</span></div>
    <div class="ace-line" id="magicdomid1250"><br>
    </div>
    <div class="ace-line" id="magicdomid1857"><span
        class="author-g-ijgixz122zfb16tkorac">There are several
        proposals for OP_EVAL that allow static analysis:</span></div>
    <div class="ace-line" id="magicdomid1312"><br>
    </div>
    <div class="ace-line" id="magicdomid1358"><span
        class="author-g-ijgixz122zfb16tkorac">* Using a fixed position
        reference prefix (sipa)</span></div>
    <div class="ace-line" id="magicdomid1428"><span
        class="author-g-ijgixz122zfb16tkorac">* Using an execute bit on
        data set by an opcode (justmoon)</span></div>
    <div class="ace-line" id="magicdomid1462"><span
        class="author-g-ijgixz122zfb16tkorac">* Using OP_CODEHASH
        (roconnor)</span></div>
    <div class="ace-line" id="magicdomid2549"><span
        class="author-g-ijgixz122zfb16tkorac">* Using OP_CHECKEDEVAL
        (sipa)</span></div>
    <div class="ace-line" id="magicdomid2641"><span
        class="author-g-ijgixz122zfb16tkorac">* Using OP_HASH160
        OP_EQUALVERIFY as a special sigPubKey (gavinandresen)</span></div>
    <div class="ace-line" id="magicdomid1494"><br>
    </div>
    <div class="ace-line" id="magicdomid1859"><span
        class="author-g-ijgixz122zfb16tkorac">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.</span></div>
    <div class="ace-line" id="magicdomid2642"><br>
    </div>
    <div class="ace-line" id="magicdomid2725"><span
        class="author-g-ijgixz122zfb16tkorac">(Update: Gavin's latest
        proposal looks *very* good, so that may settle the debate
        quickly.)</span></div>
    <div class="ace-line" id="magicdomid1815"><br>
    </div>
    <br>
    <br>
    <br>
    On 12/30/2011 6:19 PM, <a class="moz-txt-link-abbreviated" href="mailto:roconnor@theorem.ca">roconnor@theorem.ca</a> wrote:
    <blockquote cite="mid:alpine.LRH.2.00.1112301214380.9419@theorem.ca"
      type="cite">On Sat, 31 Dec 2011, Chris Double wrote:
      <br>
      <br>
      <blockquote type="cite">On Fri, Dec 30, 2011 at 5:42 AM,&nbsp;
        <a class="moz-txt-link-rfc2396E" href="mailto:roconnor@theorem.ca">&lt;roconnor@theorem.ca&gt;</a> wrote:
        <br>
        <blockquote type="cite">Basically OP_DUP lets you duplicate the
          code on the stack and that is the
          <br>
          key to looping. &nbsp;I'm pretty sure from here we get get Turing
          completeness.
          <br>
          Using the stack operations I expect you can implement the
          SK-calculus
          <br>
          given an OP_EVAL that allows arbitrary depth.
          <br>
          <br>
          OP_EVAL adds dangerously expressive power to the scripting
          language.
          <br>
        </blockquote>
        <br>
        If you look at the archives of the concatenative programming
        mailing
        <br>
        list [1] you'll see lots of examples of people creating stack
        <br>
        languages with minimal operations that exploit similar
        functionality
        <br>
        to reduce the required built in operations. The discussion on
        the list
        <br>
        is mostly about stack based languages where programs can be
        pushed on
        <br>
        the stack and executed (eg. Joy [2]/Factor/Some Forths).
        <br>
        <br>
        I don't think the scripting engine in bitcoin has the ability to
        <br>
        concatenate, append or otherwise manipulate scripts on the stack
        to be
        <br>
        eval'd though does it?
        <br>
      </blockquote>
      <br>
      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.
      <br>
      <br>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">------------------------------------------------------------------------------
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! <a class="moz-txt-link-freetext" href="http://p.sf.net/sfu/Citrix-VDIinabox">http://p.sf.net/sfu/Citrix-VDIinabox</a></pre>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">_______________________________________________
Bitcoin-development mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-development@lists.sourceforge.net</a>
<a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/bitcoin-development">https://lists.sourceforge.net/lists/listinfo/bitcoin-development</a>
</pre>
    </blockquote>
    <br>
  </body>
</html>

--------------070008060708020207040002--