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 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 ) </span></div>
<div class="" id="magicdomid13"><br>
</div>
<div class="" id="magicdomid14"><span
class="author-g-ijgixz122zfb16tkorac">hashes to </span></div>
<div class="" id="magicdomid15"><br>
</div>
<div class="" id="magicdomid16"><span
class="author-g-ijgixz122zfb16tkorac">AE4C10400B7DF3A56FE2B32B9906BCF1B1AFE975 </span></div>
<div class="" id="magicdomid17"><br>
</div>
<div class="" id="magicdomid18"><span
class="author-g-ijgixz122zfb16tkorac">which OP_EVAL interprets
as </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,
<a class="moz-txt-link-rfc2396E" href="mailto:roconnor@theorem.ca"><roconnor@theorem.ca></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. 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--
|