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
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id EC780C002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 7 May 2022 14:08:41 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id DAB7D60E1E
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 7 May 2022 14:08:41 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.601
X-Spam-Level:
X-Spam-Status: No, score=-1.601 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
FROM_LOCAL_NOVOWEL=0.5, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Authentication-Results: smtp3.osuosl.org (amavisd-new);
dkim=pass (2048-bit key) header.d=protonmail.com
Received: from smtp3.osuosl.org ([127.0.0.1])
by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id ORC2VglBvBpH
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 7 May 2022 14:08:41 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from mail-40130.protonmail.ch (mail-40130.protonmail.ch
[185.70.40.130])
by smtp3.osuosl.org (Postfix) with ESMTPS id 0422460E1B
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 7 May 2022 14:08:40 +0000 (UTC)
Date: Sat, 07 May 2022 14:08:27 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=protonmail2; t=1651932517;
bh=yl8bLcOBZWbcrwgP7W/xN7JKA+FZlZbpyv7iXnPJlCY=;
h=Date:To:From:Cc:Reply-To:Subject:Message-ID:In-Reply-To:
References:Feedback-ID:From:To:Cc:Date:Subject:Reply-To:
Feedback-ID:Message-ID;
b=KW6PHrBF70dXRnl5h14JnXVQ9V3XHoWqtd1IHUCQXoHYgm2BRutMd18MKTA8VfwC8
Bvf+zqdInscYW0P48xsL9zHptSBV02HJ9AlaBmXeefJ2ngO8le9EUy7+60YnJt2b2m
CVPFHOjnnwW4BWqc+STRR8GtGv8+d9qgAHCSnYGO95hAmogMIzIpf8C0QjfVI/kEYS
uU+7zS2pKZ8/P/cpjapt7Py/ef1rRX+Ga8FOgkgSrjaRI53QdmLyZ5kTFje7pnQWLC
MiPe6vzz1knUvU3prLWtH3wKDLT0qmLTrB6A0f3PR4KY1xNnm2qfZcmRQGjask7Kwx
9lWWOsM/3TQVg==
To: =?utf-8?Q?Jorge_Tim=C3=B3n?= <jtimon@jtimon.cc>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <CiNPwh37hW6iDk3mMg6G2QWMPS5ADUvSdySnNp6esOaloiVyoPwHGxOMLyG6mMGQnyf4iGcch12XfmOB2WnFcETwFwvRTSNSeBu27G9Cju8=@protonmail.com>
In-Reply-To: <CABm2gDrdwMjLu=i0p2m4SZ_91xpr-RvwSSWOnS9jhaQ3uaCxPA@mail.gmail.com>
References: <CABm2gDoivzQKFr6KqeqW6+Lx7xFVprRCUAn1k3X6P29NPzw+yQ@mail.gmail.com>
<1JO1xrnJ9GwGM4TgLH_rL_LpnZgSb1SyeEOJ9Gzc1VMbKUrmxSh-zUXKwFNvp_5wyiDtRviOf-gRJbrfbhOJl-qym1eEHXpoDAgjE9juucw=@protonmail.com>
<CABm2gDrdwMjLu=i0p2m4SZ_91xpr-RvwSSWOnS9jhaQ3uaCxPA@mail.gmail.com>
Feedback-ID: 2872618:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2)
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: Sat, 07 May 2022 14:08:42 -0000
Good morning Jorge,
> Thanks a lot for the many clarifications.
> Yeah, I forgot it wasn't OP_CAT alone, but in combination with other thin=
gs.
> I guess this wouldn't be a covenants proposal then.
> But simplicity would enable covenants too indeed, no?
> Or did I get that wrong too?
Yes, it would enable covenants.
However, it could also enable *recursive* covenants, depending on what intr=
ospection operations are actually implemented (though maybe not? Russell O'=
Connor should be the one that answers this).
It is helpful to delineate between non-recursive covenants from recursive c=
ovenants.
* Even ***with*** `OP_CAT`, the following will enable non-recursive covenan=
ts without enabling recursive covenants:
* `OP_CTV`
* `SIGHASH_ANYPREVOUT`
* With `OP_CAT`, the following would enable recursive covenants:
* `OP_EVAL`
* `OP_CHECKSIGFROMSTACK`
* `OP_TX`/`OP_TXHASH`
* ...possibly more.
* It is actually *easier* to *design* an opcode which inadvertently sup=
ports recursive covenants than to design one which avoids recursive covenan=
ts.
Recursive covenants are very near to true Turing-completeness.
We want to avoid Turing-completeness due to the halting problem being unsol=
vable for Turing-complete languages.
That is, given just a program, we cannot determine for sure if for all poss=
ible inputs, it will terminate.
It is important in our context (Bitcoin) that any SCRIPT programs we write =
*must* terminate, or else we run the risk of a DoS on the network.
A fair amount of this is theoretical crap, but if you want to split hairs, =
recursive covenants are *not* Turing-complete, but are instead total functi=
onal programming with codata.
As a very rough bastardization, a program written in a total functional pro=
gramming language with codata will always assuredly terminate.
However, the return value of a total functional programming language with c=
odata can be another program.
An external program (written in a Turing-complete language) could then just=
keep invoking the interpreter of the total functional programming language=
with codata (taking the output program and running it, taking *its* output=
program and running it, ad infinitum, thus effectively able to loop indefi=
nitely.
Translated to Bitcoin transactions, a recursive covenant system can force a=
n output to be spent only if the output is spent on a transaction where one=
of the outputs is the same covenant (possibly with tweaks).
Then an external program can keep passing the output program to the Bitcoin=
SCRIPT interpreter --- by building transactions that spend the previous ou=
tput.
This behavior is still of concern.
It may be possible to attack the network by eroding its supply, by such a r=
ecursive covenant.
--
Common reactions:
* We can just limit the number of opcodes we can process and then fail it i=
f it takes too many operations!
That way we can avoid DoS!
* Yes, this indeed drops it from Turing-complete to total, possibly total=
functional programming **without** codata.
But if it is possible to treat data as code, it may drop it "total but =
with codata" instead (i.e. recursive covenants).
But if you want to avoid recursive covenants while allowing recursive o=
nes (i.e. equivalent to total without codata), may I suggest you instead lo=
ok at `OP_CTV` and `SIGHASH_ANYPREVOUT`?
* What is so wrong with total-with-codata anyway??
So what if the recursive covenant could potentially consume all Bitcoins,=
nobody will pay to it except as a novelty!!
If you want to burn your funds, 1BitcoinEater willingly accepts it!
* The burden of proof-of-safety is on the proposer, so if you have some p=
roof that total-with-codata is safe, by construction, then sure, we can add=
opcodes that may enable recursive covenants, and add `OP_CAT` back in too.
Regards,
ZmnSCPxj
|