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
|
Return-Path: <roconnor@blockstream.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 08978C000E
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 7 Jul 2021 14:24:31 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id DE591401BB
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 7 Jul 2021 14:24:30 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new);
dkim=pass (2048-bit key)
header.d=blockstream-com.20150623.gappssmtp.com
Received: from smtp2.osuosl.org ([127.0.0.1])
by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id HcGuR-ydIjfj
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 7 Jul 2021 14:24:30 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-qv1-xf36.google.com (mail-qv1-xf36.google.com
[IPv6:2607:f8b0:4864:20::f36])
by smtp2.osuosl.org (Postfix) with ESMTPS id D38F34002B
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 7 Jul 2021 14:24:29 +0000 (UTC)
Received: by mail-qv1-xf36.google.com with SMTP id i4so617159qvq.10
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 07 Jul 2021 07:24:29 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=blockstream-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=+n3iC7VxtH5jgiLfGJkxnWdOutXUrBsKi+HiuXcXwh0=;
b=O4lL9zvyuHNvobqVCjxvOrVgGVV0sKSxesu70dZO391oanNDj21QwLo6SBtkoVMoaV
duBO5qoEvL1XxCVO3KVcP2CQ57EOGQwbVQFbafEuMRC5M9iqqj5Y8DW0aMcJpzuJDRLi
dT9q+9SAzpeUZnk+QT8wjdBENnUn+DUTmJhGGaYVlfMLxHSZUgOddTrr+1ZZgNPofKVT
zbdxKV0wFYa3i2n+WclnWpd8kVrb1wH2PemqFD5oNVQHXii0fgciH/RVeqJ8//rJP7OW
13LceUvot2pnhsWO6/VeAa9EgS3NH7+h9rw6MkpUSEf5zpfk1JLQ6GpadgJ1Y12PAurq
PrKQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc;
bh=+n3iC7VxtH5jgiLfGJkxnWdOutXUrBsKi+HiuXcXwh0=;
b=gR7ZoqSClaly3nWYMblYGGSai1fl9BsnOYy2nqV5R3gH5ZL1n7YIheAdNVkL4JG2dv
Z6dkwNWMc5OhvY28IKd7uABJc8qK89/1yLs0aWarQ4Ijq09KbijqK5J0sheRo/+Y3P+Q
sNr6WTRKMSIZeHxeZcSrwW4lb+qY7NgXcnyq6GT8L9kTFmx/AE5yrz/PcfDgIqtwh4YR
P5BZhsmSEdrKfaYOphaLVQy5jpahhQeq9B37PghLhQ3c/5+diucI7fK0QKc1am0MbwvP
abezYYbm2Isr/6xpo2K9rYMdp693Nykd9rgZj8L8PTv1x0uIfnsTMX4rHwvJmaWPv4RH
yXKw==
X-Gm-Message-State: AOAM531JsPPBwxTcGZtFCjZictt+I+ItXDvzlZSHq8jMZTvud5RXDDQk
aAaYkuG6FwYB2L1u0b3N+MzvLBvH9K+4xZCA21u9fA==
X-Google-Smtp-Source: ABdhPJyE8YpoUzkuib33IlMuIO3dtRPZT24HwKNzpQ/P2d9DnmDpk1zwu+Vrinjqx4Cv+4AuHPjp5Yfc6FXCIkETbfw=
X-Received: by 2002:a0c:eb51:: with SMTP id c17mr17804182qvq.13.1625667868605;
Wed, 07 Jul 2021 07:24:28 -0700 (PDT)
MIME-Version: 1.0
References: <CAD5xwhjmu-Eee47Ho5eA6E6+aAdnchLU0OVZo=RTHaXnN17x8A@mail.gmail.com>
<20210704011341.ddbiruuomqovrjn6@ganymede>
<CAD5xwhimPBEV_tLpSPxs9B+XGUhvPx_dnhok=8=hyksyi4=B6g@mail.gmail.com>
<20210704203230.37hlpdyzr4aijiet@ganymede>
<5keA_aPvmCO5yBh_mBQ6Z5SwnnvEW0T-3vahesaDh57f-qv4FbG1SFAzDvT3rFhre6kFl282VsxV_pynwn_CdvF7fzH2q9NW1ZQHPH1pmdo=@protonmail.com>
<CAMZUoKnuRXNG1pyupHrL+Wo80TXTbADVrexoB=+BKC633v-qMw@mail.gmail.com>
<u2ETzW2-k7sjRKEz48C2n2QJvmWPVdhZIqtva_KvDNvxNDTVnR2zzYCL2Q8RUVkLm93OMJ2S2GOfUOxmdvNTaCIK1liebb4yvCCBBFB75f0=@protonmail.com>
<CAMZUoK=rRDV4F7j64gTUqEB9EiBpwhZW6LP-FMR0FxR2Bc4iBw@mail.gmail.com>
In-Reply-To: <CAMZUoK=rRDV4F7j64gTUqEB9EiBpwhZW6LP-FMR0FxR2Bc4iBw@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Wed, 7 Jul 2021 10:24:17 -0400
Message-ID: <CAMZUoK=yeb2Tc0GSfPs6ezS09gpXf=xgzkuiPrj905dfT5n6LA@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000d4cfa205c6894bae"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Unlimited covenants,
was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol 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: Wed, 07 Jul 2021 14:24:31 -0000
--000000000000d4cfa205c6894bae
Content-Type: text/plain; charset="UTF-8"
On Wed, Jul 7, 2021 at 9:12 AM Russell O'Connor <roconnor@blockstream.com>
wrote:
>
> On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
>> Good morning Russell,
>>
>> > Hi ZmnSCPxj,
>> >
>> > I don't believe we need to ban Turing completeness for the sake of
>> banning Turing completeness.
>>
>> Well I believe we should ban partial Turing-completeness, but allow total
>> Turing-completeness.
>>
>
> Unfortunately, when it comes to cross-transaction computations, it is
> infeasible to ban non-terminating computation.
>
> The nature of recursive covenants is that the program "writes" the *source
> code* next step of the computation to the scriptPubKey to one of the
> outputs of its transaction. Technically speaking it verifies that the
> scriptPubKey is a commitment to the source code of the next step of the
> program, but morally that is the same as writing the source code. Then the
> next step of the computation is invoked by someone "evaluating* that next
> step's source code by creating a valid transaction that spends the
> generated output.
>
> The point is this ability to create new source code and then evaluate it
> leads to the ability to write universal (i.e non-terminating)
> computations. The only way to prevent it is to ban source code
> manipulation, but since Bitcoin Script source code is just a string of
> bytes, it would mean banning the manipulation of strings of bytes. But the
> entire Bitcoin Script language works by manipulating strings of bytes
> within a stack machine. Indeed the most trivial of non-terminating
> programs can be implemented by extracting the current input's scriptPubKey
> from the sighash and "writing" the identical scriptPubKey to one of its
> outputs. That example hardly takes any manipulation at all to implement.
>
A follow up: Because recursive covenants need to be sent to a new
transaction in order to recurse, you might choose to view this stepping
mechanism as productive by modeling each transaction step as the continue
constructor in your RecResult codata type. Indeed after (drinking coffee
and) rereading your mailing list item, it seems that this is the point you
were making.
So sorry for my hasty response. I believe we are largely in agreement here.
--000000000000d4cfa205c6894bae
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail=
_attr">On Wed, Jul 7, 2021 at 9:12 AM Russell O'Connor <<a href=3D"m=
ailto:roconnor@blockstream.com">roconnor@blockstream.com</a>> wrote:<br>=
</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b=
order-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><d=
iv dir=3D"ltr"><br></div><div class=3D"gmail_quote"><div dir=3D"ltr" class=
=3D"gmail_attr">On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj <<a href=3D"mai=
lto:ZmnSCPxj@protonmail.com" target=3D"_blank">ZmnSCPxj@protonmail.com</a>&=
gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0=
px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Good =
morning Russell,<br>
<br>
> Hi ZmnSCPxj,<br>
><br>
> I don't believe we need to ban Turing completeness for the sake of=
banning Turing completeness.<br>
<br>
Well I believe we should ban partial Turing-completeness, but allow total T=
uring-completeness.<br></blockquote><div><br></div><div>Unfortunately, when=
it comes to cross-transaction computations, it is infeasible to ban non-te=
rminating computation.</div><div><br></div><div>The nature of recursive cov=
enants is that the program "writes" the *source code* next step o=
f the computation to the scriptPubKey to one of the outputs of its transact=
ion. Technically speaking it verifies that the scriptPubKey is a commitment=
to the source code of the next step of the program, but morally that is th=
e same as writing the source code.=C2=A0 Then the next step of the computat=
ion is invoked by someone "evaluating* that next step's source cod=
e by creating a valid transaction that spends the generated output.<br></di=
v><div><br></div><div>The point is this ability to create new source code a=
nd then evaluate it leads to the ability to write universal (i.e non-termin=
ating) computations.=C2=A0 The only way to prevent it is to ban source code=
manipulation, but since Bitcoin Script source code is just a string of byt=
es, it would mean banning the manipulation of strings of bytes.=C2=A0 But t=
he entire Bitcoin Script language works by manipulating strings of bytes wi=
thin a stack machine.=C2=A0 Indeed the most trivial of non-terminating prog=
rams can be implemented by extracting the current input's scriptPubKey =
from the sighash and "writing" the identical scriptPubKey to one =
of its outputs.=C2=A0 That example hardly takes any manipulation at all to =
implement.<br></div></div></div></blockquote><div><br></div><div>A follow u=
p:=C2=A0 Because recursive covenants need to be sent to a new transaction i=
n order to recurse, you might choose to view this stepping mechanism as pro=
ductive by modeling each transaction step as the continue constructor in yo=
ur RecResult codata type.=C2=A0 Indeed after (drinking coffee and) rereadin=
g your mailing list item, it seems that this is the point you were making.<=
/div><div><br></div><div>So sorry for my hasty response.=C2=A0 I believe we=
are largely in agreement here.<br></div></div></div>
--000000000000d4cfa205c6894bae--
|
