summaryrefslogtreecommitdiff
path: root/93/e73016313ce81eaae7384cc07cad796095bf48
blob: fddf614fd70ce20040eed9a06d9f75a0309526fb (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
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 90B8AC000B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  7 Mar 2022 23:35:15 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 6D8D7415B7
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  7 Mar 2022 23:35:15 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.599
X-Spam-Level: 
X-Spam-Status: No, score=-1.599 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, RCVD_IN_MSPIKE_H5=0.001,
 RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Authentication-Results: smtp4.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=protonmail.com
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id yUi-PyXXihtx
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  7 Mar 2022 23:35:14 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from mail-4319.protonmail.ch (mail-4319.protonmail.ch [185.70.43.19])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 298514159F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon,  7 Mar 2022 23:35:14 +0000 (UTC)
Date: Mon, 07 Mar 2022 23:35:04 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
 s=protonmail3; t=1646696110;
 bh=uIn9iL9PM5afJrPIXK6odtZ5nMPGLtQgiBq/UQpMuas=;
 h=Date:To:From:Cc:Reply-To:Subject:Message-ID:From:To:Cc:Date:
 Subject:Reply-To:Feedback-ID:Message-ID;
 b=A1/lXqAJ28hSUUGp88gLABBQ7kuCr2AhcjowVUd3fXdhXVZ/D0ObdhaFrtfrU+Wto
 tme+K193RhHKKD5rfTdjAHmYx6IjcGLPcGDDcPnA+MJFxM2r6EXnBCNmR4Tpkshepe
 FtHrF0/1JggrkVDLTv506ra+XoKJtqsmV9UL5vUC8Q+sERsmhTC5ONatKaIMmquddy
 NUWrsBd7MmH6WMLr6ElmXOPm9YsUnQND9kyZhz+8KAl9DZHfVDEhFgRTcD05pUG7vj
 /d/EhE29zWUNwnDkpE+3HA4hMXIt9ptRmBj4E2XglL/f+SC7gd605gSlmL7ePvaBie
 YLcl86FqTClEQ==
To: Billy Tetrud <billy.tetrud@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <EIwjydT0d68Z7Jv8_JlrCbQW6NHSSnIU5sWwE8eX2rm9K3djfzU3nQqUrmt44U8-L9sObegelHCV6Sk7h2nwq_HS1d26FophzjNU7xC_6SE=@protonmail.com>
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: [bitcoin-dev] Jets (Was: `OP_FOLD`: A Looping Construct For Bitcoin
	SCRIPT)
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: Mon, 07 Mar 2022 23:35:15 -0000

Good morning Billy,

Changed subject since this is only tangentially related to `OP_FOLD`.

> Let me organize my thoughts on this a little more clearly. There's a coup=
le possibilities I can think of for a jet-like system:
>
> A. We could implement jets now without a consensus change, and without=
=C2=A0requiring all nodes to upgrade to new relay rules. Probably. This wou=
ld give upgraded nodes improved=C2=A0validation performance and many upgrad=
ed nodes relay savings (transmitting/receiving fewer bytes). Transactions w=
ould be weighted the same as without the use of jets tho.
> B. We could implement the above=C2=A0+ lighter weighting by using a soft =
fork to put the jets in a part of the blockchain hidden from unupgraded nod=
es, as you mentioned.=C2=A0
> C. We could implement the above=C2=A0+ the jet registration idea in a sof=
t fork.=C2=A0
>
> For A:
>
> * Upgraded nodes query each connection for support of jets in general, an=
d which specific jets they support.
> * For a connection to another upgraded node that supports the jet(s) that=
 a transaction contains, the transaction is sent verbatim=C2=A0with the jet=
 included in the script (eg as some fake opcode line like 23 OP_JET, indica=
ting to insert standard jet 23 in its place). When validation happens, or w=
hen a miner includes it in a block, the jet opcode call is replaced with th=
e script it represents so hashing happens in a way that is recognizable to =
unupgraded nodes.
> * For a connection to a non-upgraded node that doesn't support jets, or a=
n upgraded node that doesn't support the particular jet included in the scr=
ipt, the jet opcode call is replaced as above before sending to that node. =
In addition, some data is added to the transaction that unupgraded nodes pr=
opagate along but otherwise ignore. Maybe this is extra witness data, maybe=
 this is some kind of "annex", or something else. But that data would conta=
in the original jet opcode (in this example "23 OP_JET") so that when that =
transaction data reaches an upgraded node that recognizes that jet again, i=
t can swap that back in, in place of the script fragment it represents.=
=C2=A0
>
> I'm not 100% sure the required mechanism I mentioned of "extra ignored da=
ta" exists, and if it doesn't, then all nodes would at least need to be upg=
raded to support that before this mechanism could fully work.

I am not sure that can even be *made* to exist.
It seems to me a trivial way to launch a DDoS: Just ask a bunch of fullnode=
s to add this 1Mb of extra ignored data in this tiny 1-input-1-output trans=
action so I pay only a small fee if it confirms but the bandwidth of all fu=
llnodes is wasted transmitting and then ignoring this block of data.

> But even if such a mechanism doesn't exist, a jet script could still be u=
sed, but it would be clobbered by the first nonupgraded node it is relayed =
to, and can't then be converted back (without using a potentially expensive=
 lookup table as you mentioned).=C2=A0

Yes, and people still run Bitcoin Core 0.8.x.....

> > If the script does not weigh less if it uses a jet, then there is no in=
centive for end-users to use a jet
>
> That's a good point. However, I'd point out that nodes do lots of things =
that there's no individual incentive for, and this might be one where peopl=
e either altruistically use jets to be lighter on the network, or use them =
in the hopes that the jet is accepted as a standard, reducing the cost of t=
heir scripts. But certainly a direct incentive to use them is better. Hones=
t nodes can favor connecting to those that support jets.

Since you do not want a dynamic lookup table (because of the cost of lookup=
), how do new jets get introduced?
If a new jet requires coordinated deployment over the network, then you mig=
ht as well just softfork and be done with it.
If a new jet can just be entered into some configuration file, how do you c=
oordinate those between multiple users so that there *is* some benefit for =
relay?

> >if a jet would allow SCRIPT weights to decrease, upgraded nodes need to =
hide them from unupgraded nodes
> > we have to do that by telling unupgraded nodes "this script will always=
 succeed and has weight 0"
>
> Right. It doesn't have to be weight zero, but that would work fine enough=
.=C2=A0
>
> > if everybody else has not upgraded, a user of a new jet has no security=
.
>
> For case A, no security is lost. For case B you're right. For case C, onc=
e nodes upgrade to the initial soft fork, new registered jets can take adva=
ntage of relay-cost weight savings (defined by the soft fork) without requi=
ring any nodes to do any upgrading, and nodes could be further upgraded to =
optimize the validation of various of those registered jets, but those proc=
essing savings couldn't change the weighting of transactions without an add=
itional soft fork.
>
> > Consider an attack where I feed you a SCRIPT that validates trivially b=
ut is filled with almost-but-not-quite-jettable code
>
> I agree a pattern-matching lookup table is probably not a great design. B=
ut a lookup table like that is not needed for the jet registration idea. Af=
ter the necessary soft fork, there would be standard rules for which regist=
ered jets nodes are required to keep an index of, and so the lookup table w=
ould be a straightforward jet hash lookup rather than a pattern-matching lo=
okup, which wouldn't have the same DOS problems. A node would simply find a=
 jet opcode call like "ab38cd39e OP_JET" and just lookup ab38cd39e in its i=
ndex.=C2=A0

How does the unupgraded-to-upgraded boundary work?
Having a static lookup table is better since you can pattern-match on strin=
gs of specific, static length, and we can take a page from `rsync` and use =
its "rolling checksum" idea which works with identifying strings of a certa=
in specific length at arbitrary offsets.

Say you have jetted sequences where the original code is 42 bytes, and anot=
her jetted sequence where the original code is 54 bytes, you would keep a 4=
2-byte rolling checksum and a separate 54-byte rolling checksum, and then w=
hen it matches, you check if the last 42 or 54 bytes matched the jetted seq=
uences.

It does imply having a bunch of rolling checksums around, though.
Sigh.

---

To make jets more useful, we should redesign the language so that `OP_PUSH`=
 is not in the opcode stream, but instead, we have a separate table of cons=
tants that is attached / concatenated to the actual SCRIPT.

So for example instead of an HTLC having embedded `OP_PUSH`es like this:

   OP_IF
       OP_HASH160 <hash> OP_EQUALVERIFY OP_DUP OP_HASH160 <acceptor pkh>
   OP_ELSE
       <timeout> OP_CHECKLOCKTIMEVERIFY OP_DROP OP_DUP OP_HASH160 <offerrer=
 pkh>
   OP_ENDIF
   OP_EQUALVERIFY
   OP_CHECKSIG

We would have:

   constants:
       h =3D <hash>
       a =3D <acceptor pkh>
       t =3D <timeout>
       o =3D <offerer pkh>
   script:
       OP_IF
           OP_HASH160 h OP_EQUALVERIFY OP_DUP OP_HASH160 a
       OP_ELSE
           t OP_CHECKLOCKTIMEVERIFY OP_DROP OP_DUP OP_HASH160 o
       OP_ENDIF
       OP_EQUALVERIFY
       OP_CHECKSIG

The above allows for more compressibility, as the entire `script` portion c=
an be recognized as a jet outright.
Move the incompressible hashes out of the main SCRIPT body.

We should note as well that this makes it *easier* to create recursive cove=
nants (for good or ill) out of `OP_CAT` and whatever opcode you want that a=
llows recursive covenants in combination with `OP_CAT`.
Generally, recursive covenants are *much* more interesting if they can chan=
ge some variables at each iteration, and having a separate table-of-constan=
ts greatly facilitates that.

Indeed, the exercise of `OP_TLUV` in [drivechains-over-recursive-convenants=
][] puts the loop variables into the front of the SCRIPT to make it easier =
to work with the SCRIPT manipulation.

[drivechains-over-recursive-covenants]: https://lists.linuxfoundation.org/p=
ipermail/bitcoin-dev/2022-February/019976.html

---

Perhaps we can consider the general vs specific tension in information-theo=
retic terms.

A language which supports more computational power --- i.e. more general --=
- must, by necessity, have longer symbols, as a basic law of information th=
eory.
After all, a general language can express more things.

However, we do recognize that certain sequences of things-to-say are much m=
ore likely than others.
That is, we expect that certain sequences "make sense" to do.
That is why "jets" are even proposed, they are shortcuts towards those.

Assuming a general language is already deployed for Bitcoin, then a new opc=
ode is a jet as it simply makes the SCRIPT shorter.

Instead of starting with a verbose (by necessity) general language, we coul=
d instead start with a terse but restricted language, and slowly loosen up =
its restrictions by adding new capabilities in softforks.

Regards,
ZmnSCPxj