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
|
Return-Path: <jgarzik@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id BE136E92
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 10 Dec 2015 04:03:31 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ig0-f175.google.com (mail-ig0-f175.google.com
[209.85.213.175])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 003CE151
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 10 Dec 2015 04:03:30 +0000 (UTC)
Received: by mail-ig0-f175.google.com with SMTP id ph11so5063870igc.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 09 Dec 2015 20:03:30 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc:content-type;
bh=ORF4aXCxlyq6cCrsinDR7otBKLRePnxgjhyk6ZHldK8=;
b=oAK6av4eu4Omg2jy6MZ1vpbsxGUcuBdoJ4KFptGEQh9Q1mkblb3z4yDZhb+F0+oqlN
qg9C9go37Bn6JxxzT6xCZgvcDpm9U9M7lAGJWx2ZCglZuLd7AKXYT63cgum9I785e2cU
QGVb1QF1h5oJNj5bzp7FRHmjNNVFI4HCDZ+g88c7LB+9R/jXkDn0s8XQjkAYR8tzccau
Ldd7kf+10M9Bt3QGR0TRAtNvP5J3G2oRSmNwbnCRYe5Vq55zOWdBRiJARRPmt1QJw60B
uK/cqk6lI90zHpVk6KfvE3r+2n1t7i3lOTaq6Z4pfPX5SRWdeVxINZIQYLIdf7zz4hpx
9RFw==
MIME-Version: 1.0
X-Received: by 10.50.160.2 with SMTP id xg2mr34722923igb.54.1449720210432;
Wed, 09 Dec 2015 20:03:30 -0800 (PST)
Received: by 10.79.8.198 with HTTP; Wed, 9 Dec 2015 20:03:30 -0800 (PST)
In-Reply-To: <CAEj3M+wYicoACcpG5YUU6vF8vg98XCcJWmgBiyrJj-xHHxrhig@mail.gmail.com>
References: <CAEj3M+wYicoACcpG5YUU6vF8vg98XCcJWmgBiyrJj-xHHxrhig@mail.gmail.com>
Date: Thu, 10 Dec 2015 12:03:30 +0800
Message-ID: <CADm_WcZdC-iNF=tMmYYafsaLaHUcck03zw8cdsSCCPvXdTNyrw@mail.gmail.com>
From: Jeff Garzik <jgarzik@gmail.com>
To: Luke Durback <luke.durback@gmail.com>
Content-Type: multipart/alternative; boundary=001a11343db82aa9190526834a94
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin development mailing list <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Standard BIP Draft: Turing Pseudo-Completeness
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Thu, 10 Dec 2015 04:03:31 -0000
--001a11343db82aa9190526834a94
Content-Type: text/plain; charset=UTF-8
There is no need for a BIP draft. "Turing complete" is just a fancy,
executive-impressing term for "it can run any computer program", or put
even more simply, "it can loop"
Furthermore, the specification of such a language is trivial. It is the
economics of validation that is the complex piece. Proving whether or not
a program will halt as expected - The Halting Problem - is near impossible
for most complex programs. As a result, your proof is... running the
program. That produces enormous validation consequences and costs for
generic-execution scripts when applied to a decentralized network of
validation P2P nodes.
If you need that capability, it is just as easy to use a normal C/C++/etc.
computer language, with your preferred algorithm libraries and development
tools.
See https://github.com/jgarzik/moxiebox for a working example of provable
execution.
On Thu, Dec 10, 2015 at 9:35 AM, Luke Durback via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Hello Bitcoin-Dev,
>
> I hope this isn't out of line, but I joined the mailing list to try to
> start a discussion on adding opcodes to make Script Turing Pseudo-Complete
> as Wright suggested is possible.
>
> ---
>
> In line with Wright's suggestion, I propose adding a return stack
> alongside the, already existing, control stack.
>
> The principle opcodes (excluding conditional versions of call and
> return_from) needed are
>
> OP_DEFINITION_START FunctionName: The code that follows is the definition
> of a new function to be named TransactionSenderAddress.FunctionName. If
> this function name is already taken, the transaction is marked invalid.
> Within the transaction, the function can be called simply as FunctionName.
>
> OP_DEFINITION_END: This ends a function definition
>
> OP_FUNCTION_NAME FunctionName: Gives the current transaction the name
> FunctionName (this is necessary to build recursive functions)
>
> ---
>
> OP_CALL Namespace.FunctionName Value TransactionFee: This marks the
> transaction as valid. It also pushes the current execution location onto
> the return stack, debits the calling transaction by the TransactionFee and
> Value, and creates a new transaction specified by Namespace.FunctionName
> with both stacks continued from before (this may be dangerous, but I see no
> way around it) with the specified value.
>
> OP_RETURN_FROM_CALL_AND_CONTINUE: This pops the top value off the return
> stack and continues from the specified location with both stacks in tact.
>
> ---
>
> It would also be useful if a transaction can create another transaction
> arbitrarily, so to prepare for that, I additionally propose
>
> OP_NAMESPACE: Pushes the current namespace onto the control stack
>
> This, combined with the ability to make new transactions arbitrarily would
> allow a function to pay its creator.
>
>
>
> I understand that this isn't all that is needed, but I think it's a
> start. I hope this proposal has met you all well,
>
> Luke Durback
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
--001a11343db82aa9190526834a94
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">There is no need for a BIP draft. =C2=A0"Turing compl=
ete" is just a fancy, executive-impressing term for "it can run a=
ny computer program", or put even more simply, "it can loop"=
<div><br></div><div>Furthermore, the specification of such a language is tr=
ivial.=C2=A0 It is the economics of validation that is the complex piece.=
=C2=A0 Proving whether or not a program will halt as expected - The Halting=
Problem - is near impossible for most complex programs.=C2=A0 As a result,=
your proof is... running the program.=C2=A0 That produces enormous validat=
ion consequences and costs for generic-execution scripts when applied to a =
decentralized network of validation P2P nodes.</div><div><br></div><div>If =
you need that capability, it is just as easy to use a normal C/C++/etc. com=
puter language, with your preferred algorithm libraries and development too=
ls.</div><div><br></div><div>See=C2=A0<a href=3D"https://github.com/jgarzik=
/moxiebox">https://github.com/jgarzik/moxiebox</a> for a working example of=
provable execution.</div><div><br></div><div><br></div></div><div class=3D=
"gmail_extra"><br><div class=3D"gmail_quote">On Thu, Dec 10, 2015 at 9:35 A=
M, Luke Durback via bitcoin-dev <span dir=3D"ltr"><<a href=3D"mailto:bit=
coin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.lin=
uxfoundation.org</a>></span> wrote:<br><blockquote class=3D"gmail_quote"=
style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><d=
iv dir=3D"ltr"><div>Hello Bitcoin-Dev,<br></div><div><br></div><div>I hope =
this isn't out of line, but I joined the mailing list to try to start a=
discussion on adding opcodes to make Script Turing Pseudo-Complete as Wrig=
ht suggested is possible.</div><div><br></div><div>---</div><div><br></div>=
<div>In line with Wright's suggestion, I propose adding a return stack =
alongside the, already existing, control stack.</div><div><br></div><div>Th=
e principle opcodes (excluding conditional versions of call and return_from=
) needed are</div><div><br></div><div>OP_DEFINITION_START FunctionName: =C2=
=A0The code that follows is the definition of a new function to be named Tr=
ansactionSenderAddress.FunctionName.=C2=A0 If this function name is already=
taken, the transaction is marked invalid.=C2=A0 Within the transaction, th=
e function can be called simply as FunctionName.</div><div><br></div><div>O=
P_DEFINITION_END: =C2=A0This ends a function definition</div><div><div><br>=
</div><div>OP_FUNCTION_NAME FunctionName: =C2=A0Gives the current transacti=
on the name FunctionName (this is necessary to build recursive functions)</=
div></div><div><br></div><div>---</div><div><br></div><div>OP_CALL Namespac=
e.FunctionName Value TransactionFee: =C2=A0This marks the transaction as va=
lid.=C2=A0 It also pushes the current execution location onto the return st=
ack, debits the calling transaction by the TransactionFee and Value, and cr=
eates a new transaction specified by Namespace.FunctionName with both stack=
s continued from before (this may be dangerous, but I see no way around it)=
with the specified value.</div><div><br></div><div>OP_RETURN_FROM_CALL_AND=
_CONTINUE: =C2=A0This pops the top value off the return stack and continues=
from the specified location with both stacks in tact.</div><div><br></div>=
<div>---<br></div><div><br></div><div>It would also be useful if a transact=
ion can create another transaction arbitrarily, so to prepare for that, I a=
dditionally propose</div><div><br></div><div>OP_NAMESPACE: =C2=A0Pushes the=
current namespace onto the control stack<br><br>This, combined with the ab=
ility to make new transactions arbitrarily would allow a function to pay it=
s creator.</div><div><br></div><div><br></div><div><br></div><div>I underst=
and that this isn't all that is needed, but I think it's a start.=
=C2=A0 I hope this proposal has met you all well,</div><div><br></div><div>=
Luke Durback</div></div>
<br>_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
<br></blockquote></div><br></div>
--001a11343db82aa9190526834a94--
|
