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
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
|
Return-Path: <antoine.riard@gmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 52B0EC000B
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Mar 2022 00:59:49 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp1.osuosl.org (Postfix) with ESMTP id 2DCD581357
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Mar 2022 00:59:49 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 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,
HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp1.osuosl.org (amavisd-new);
dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp1.osuosl.org ([127.0.0.1])
by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id MCwkMwDjo4jS
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Mar 2022 00:59:47 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-yw1-x1136.google.com (mail-yw1-x1136.google.com
[IPv6:2607:f8b0:4864:20::1136])
by smtp1.osuosl.org (Postfix) with ESMTPS id 45E19812E1
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 7 Mar 2022 00:59:47 +0000 (UTC)
Received: by mail-yw1-x1136.google.com with SMTP id
00721157ae682-2dbfe58670cso147094457b3.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 06 Mar 2022 16:59:47 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=UGOks/IC0I9EfxjGn9rq8TFTfzH9wD1hryHgQyLSGqc=;
b=TgAxsV4EH0d4UXeb3JU1uzv8np/yvuqUJ3lEI9iTg7Q/uhzD1+l+1QjBbWih9AkdqD
erwCoH9/82f4pQzqTA45IZSEj7e6PeIs7CTavXlVGqflS7NwSCnKimC+d1AIFE5BNRZe
21zHT0lyGQHhWdA9YM90AM9oLTfpRB0z8AAtFRohaHEqi8EIdNzoUmCb5XFpG9wqqwaV
BSOPfP6uemcaCk6A4uZLHqpSOEf3vO4Whm0m1EeS3Chg84BHbMV0eebQWHDL7wc21XlG
GcRSgMyRDmG4r6+k7tnJ0ijf25t04GoLp1q8hue0mIbwVXxyGKlhj2Z5qJba/Sjy5WET
LSng==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to;
bh=UGOks/IC0I9EfxjGn9rq8TFTfzH9wD1hryHgQyLSGqc=;
b=fhIaS4H7Ra6/DtD1vIOthTqpVZ7s4yRK7FJDV3Sjms1Adc1/88XnGAuZ8y9k6AKfHf
FbH3Pa3XUtzEVrYg2QZpGvdMhkMb66aEI4Mh+XKnq2dLM0qE0gYPQ3GcvzWaDogYY21f
jLO7o4mZdlgfN67xwhby2zd+/h79JeIGr64L3UiVprZ4buPgwxSLUejVhsA2xY9Wz2Sr
e3pHO0Yhn0+1mKNpOc4VZGR/Bn9TrzjozrGU7Np085uAQjFDMzxUjJ0TlzdfxN6wYlmk
/NFkMPDhLRIRZYEKRBhtnEWCUnveTQPZYfcgT7QIy6QzJLEkpCYDmGV9HWrZaMC0H2Pp
lj9A==
X-Gm-Message-State: AOAM5338nnYI2N5QkRxVEslMxuFXujTCdA0nldaz0QnRV0Cx3wiRycpM
vexJTRZHI9fwCvk0UlFbo/C/g5+NaRNKhfNktSA0S9p4bss=
X-Google-Smtp-Source: ABdhPJy7rzdAT/q2TNfmAJHj7oFod5Fd0T4TXW/8P7U26XRDbWH4h34wsyO+vDCt+67thcgtqYt6sZMaz/ghawue+50=
X-Received: by 2002:a0d:ea90:0:b0:2dc:2fdf:dd9a with SMTP id
t138-20020a0dea90000000b002dc2fdfdd9amr6668588ywe.321.1646614786199; Sun, 06
Mar 2022 16:59:46 -0800 (PST)
MIME-Version: 1.0
References: <CAD5xwhgXE9sB-hdzz_Bgz6iEA-M5-Yu2VOn1qRzkaq+DdVsgmw@mail.gmail.com>
In-Reply-To: <CAD5xwhgXE9sB-hdzz_Bgz6iEA-M5-Yu2VOn1qRzkaq+DdVsgmw@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Sun, 6 Mar 2022 19:59:33 -0500
Message-ID: <CALZpt+GmX18Nbz5B7JDBP8eSRovhD3y4yjURr5zBO6CpSbpLtw@mail.gmail.com>
To: Jeremy Rubin <jeremy.l.rubin@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000069d75705d9966154"
X-Mailman-Approved-At: Mon, 07 Mar 2022 17:42:31 +0000
Subject: Re: [bitcoin-dev] Annex Purpose Discussion: OP_ANNEX,
Turing Completeness, and other considerations
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 00:59:49 -0000
--00000000000069d75705d9966154
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Hi Jeremy,
> I've seen some discussion of what the Annex can be used for in Bitcoin.
For
> example, some people have discussed using the annex as a data field for
> something like CHECKSIGFROMSTACK type stuff (additional authenticated
data)
> or for something like delegation (the delegation is to the annex). I thin=
k
> before devs get too excited, we should have an open discussion about what
> this is actually for, and figure out if there are any constraints to usin=
g
> it however we may please.
I think one interesting purpose of the annex is to serve as a transaction
field extension, where we assign new consensus validity rules to the annex
payloads.
One could think about new types of locks, e.g where a transaction inclusion
is constrained before the annex payload value is superior to the chain's
`ChainWork`. This could be useful in case of contentious forks, where you
want your transaction to confirm only when enough work is accumulated, and
height isn't a reliable indicator anymore.
Or a relative-timelock where the endpoint is the presence of a state number
encumbering the spent transaction. This could be useful in the context of
payment pools, where the user withdraw transactions are all encumbered by a
bip68 relative-timelock, as you don't know which one is going to confirm
first, but where you don't care about enforcement of the timelocks once the
contestation delay has played once and no higher-state update transaction
has confirmed.
Of course, we could reuse the nSequence field for some of those new types
of locks, though we would lose the flexibility of combining multiple locks
encumbering the same input.
Another use for the annex is locating there the SIGHASH_GROUP group count
value. One advantage over placing the value as a script stack item could be
to have annex payloads interdependency validity, where other annex payloads
are reusing the group count value as part of their own semantics.
Antoine
Le ven. 4 mars 2022 =C3=A0 18:22, Jeremy Rubin via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :
> I've seen some discussion of what the Annex can be used for in Bitcoin.
> For example, some people have discussed using the annex as a data field f=
or
> something like CHECKSIGFROMSTACK type stuff (additional authenticated dat=
a)
> or for something like delegation (the delegation is to the annex). I thin=
k
> before devs get too excited, we should have an open discussion about what
> this is actually for, and figure out if there are any constraints to usin=
g
> it however we may please.
>
> The BIP is tight lipped about it's purpose, saying mostly only:
>
> *What is the purpose of the annex? The annex is a reserved space for
> future extensions, such as indicating the validation costs of
> computationally expensive new opcodes in a way that is recognizable witho=
ut
> knowing the scriptPubKey of the output being spent. Until the meaning of
> this field is defined by another softfork, users SHOULD NOT include annex
> in transactions, or it may lead to PERMANENT FUND LOSS.*
>
> *The annex (or the lack of thereof) is always covered by the signature an=
d
> contributes to transaction weight, but is otherwise ignored during taproo=
t
> validation.*
>
> *Execute the script, according to the applicable script rules[11], using
> the witness stack elements excluding the script s, the control block c, a=
nd
> the annex a if present, as initial stack.*
>
> Essentially, I read this as saying: The annex is the ability to pad a
> transaction with an additional string of 0's that contribute to the virtu=
al
> weight of a transaction, but has no validation cost itself. Therefore,
> somehow, if you needed to validate more signatures than 1 per 50 virtual
> weight units, you could add padding to buy extra gas. Or, we might someho=
w
> make the witness a small language (e.g., run length encoded zeros) such
> that we can very quickly compute an equivalent number of zeros to 'charge=
'
> without actually consuming the space but still consuming a linearizable
> resource... or something like that. We might also e.g. want to use the
> annex to reserve something else, like the amount of memory. In general, w=
e
> are using the annex to express a resource constraint efficiently. This
> might be useful for e.g. simplicity one day.
>
> Generating an Annex: One should write a tracing executor for a script, ru=
n
> it, measure the resource costs, and then generate an annex that captures
> any externalized costs.
>
> -------------------
>
> Introducing OP_ANNEX: Suppose there were some sort of annex pushing
> opcode, OP_ANNEX which puts the annex on the stack as well as a 0 or 1 (t=
o
> differentiate annex is 0 from no annex, e.g. 0 1 means annex was 0 and 0 =
0
> means no annex). This would be equivalent to something based on <annex
> flag> OP_TXHASH <has annex flag> OP_TXHASH.
>
> Now suppose that I have a computation that I am running in a script as
> follows:
>
> OP_ANNEX
> OP_IF
> `some operation that requires annex to be <1>`
> OP_ELSE
> OP_SIZE
> `some operation that requires annex to be len(annex) + 1 or does a
> checksig`
> OP_ENDIF
>
> Now every time you run this, it requires one more resource unit than the
> last time you ran it, which makes your satisfier use the annex as some so=
rt
> of "scratch space" for a looping construct, where you compute a new annex=
,
> loop with that value, and see if that annex is now accepted by the progra=
m.
>
> In short, it kinda seems like being able to read the annex off of the
> stack makes witness construction somehow turing complete, because we can
> use it as a register/tape for some sort of computational model.
>
> -------------------
>
> This seems at odds with using the annex as something that just helps you
> heuristically guess computation costs, now it's somehow something that
> acts to make script satisfiers recursive.
>
> Because the Annex is signed, and must be the same, this can also be
> inconvenient:
>
> Suppose that you have a Miniscript that is something like: and(or(PK(A),
> PK(A')), X, or(PK(B), PK(B'))).
>
> A or A' should sign with B or B'. X is some sort of fragment that might
> require a value that is unknown (and maybe recursively defined?) so
> therefore if we send the PSBT to A first, which commits to the annex, and
> then X reads the annex and say it must be something else, A must sign
> again. So you might say, run X first, and then sign with A and C or B.
> However, what if the script somehow detects the bitstring WHICH_A WHICH_B
> and has a different Annex per selection (e.g., interpret the bitstring as=
a
> int and annex must =3D=3D that int). Now, given and(or(K1, K1'),... or(Kn=
,
> Kn')) we end up with needing to pre-sign 2**n annex values somehow... thi=
s
> seems problematic theoretically.
>
> Of course this wouldn't be miniscript then. Because miniscript is just fo=
r
> the well behaved subset of script, and this seems ill behaved. So maybe
> we're OK?
>
> But I think the issue still arises where suppose I have a simple thing
> like: and(COLD_LOGIC, HOT_LOGIC) where both contains a signature, if
> COLD_LOGIC and HOT_LOGIC can both have different costs, I need to decide
> what logic each satisfier for the branch is going to use in advance, or
> sign all possible sums of both our annex costs? This could come up if
> cold/hot e.g. use different numbers of signatures / use checksigCISAadd
> which maybe requires an annex argument.
>
>
>
> ------------
>
> It seems like one good option is if we just go on and banish the OP_ANNEX=
.
> Maybe that solves some of this? I sort of think so. It definitely seems
> like we're not supposed to access it via script, given the quote from abo=
ve:
>
> *Execute the script, according to the applicable script rules[11], using
> the witness stack elements excluding the script s, the control block c, a=
nd
> the annex a if present, as initial stack.*
>
> If we were meant to have it, we would have not nixed it from the stack,
> no? Or would have made the opcode for it as a part of taproot...
>
> But recall that the annex is committed to by the signature.
>
> So it's only a matter of time till we see some sort of Cat and Schnorr
> Tricks III the Annex Edition that lets you use G cleverly to get the anne=
x
> onto the stack again, and then it's like we had OP_ANNEX all along, or
> without CAT, at least something that we can detect that the value has
> changed and cause this satisfier looping issue somehow.
>
> Not to mention if we just got OP_TXHASH
>
>
>
> -----------
>
> Is the annex bad? After writing this I sort of think so?
>
> One solution would be to... just soft-fork it out. Always must be 0. When
> we come up with a use case for something like an annex, we can find a way
> to add it back. Maybe this means somehow pushing multiple annexes and
> having an annex stack, where only sub-segments are signed for the last
> executed signature? That would solve looping... but would it break some
> aggregation thing? Maybe.
>
>
> Another solution would be to make it so the annex is never committed to
> and unobservable from the script, but that the annex is always something
> that you can run get_annex(stack) to generate the annex. Thus it is a hin=
t
> for validation rules, but not directly readable, and if it is modified yo=
u
> figure out the txn was cheaper sometime after you execute the scripts and
> can decrease the value when you relay. But this sounds like something tha=
t
> needs to be a p2p only annex, because consensus we may not care (unless
> it's something like preallocating memory for validation?).
>
> -----------------------
>
> Overall my preference is -- perhaps sadly -- looking like we should
> soft-fork it out of our current Checksig (making the policy that it must =
0
> a consensus rule) and redesign the annex technique later when we actually
> know what it is for with a new checksig or other mechanism. But It's not =
a
> hard opinion! It just seems like you can't practically use the annex for
> this worklimit type thing *and* observe it from the stack meaningfully.
>
>
>
> Thanks for coming to my ted-talk,
>
> Jeremy
>
>
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--00000000000069d75705d9966154
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hi Jeremy,<br><br>> I've seen some discussion of wh=
at the Annex can be used for in Bitcoin. For<br>> example, some people h=
ave discussed using the annex as a data field for<br>> something like CH=
ECKSIGFROMSTACK type stuff (additional authenticated data)<br>> or for s=
omething like delegation (the delegation is to the annex). I think<br>> =
before devs get too excited, we should have an open discussion about what<b=
r>> this is actually for, and figure out if there are any constraints to=
using<br>> it however we may please.<br><br>I think one interesting pur=
pose of the annex is to serve as a transaction field extension, where we as=
sign new consensus validity rules to the annex payloads.<br><br>One could t=
hink about new types of locks, e.g where a transaction inclusion is constra=
ined before the annex payload value is superior to the chain's `ChainWo=
rk`. This could be useful in case of contentious forks, where you want your=
transaction to confirm only when enough work is accumulated, and height is=
n't a reliable indicator anymore.<br><br>Or a relative-timelock where t=
he endpoint is the presence of a state number encumbering the spent transac=
tion. This could be useful in the context of payment pools, where the user =
withdraw transactions are all encumbered by a bip68 relative-timelock, as y=
ou don't know which one is going to confirm first, but where you don=
9;t care about enforcement of the timelocks once the contestation delay has=
played once=C2=A0 and no higher-state update transaction has confirmed.<br=
><br>Of course, we could reuse the nSequence field for some of those new ty=
pes of locks, though we would lose the flexibility of combining multiple lo=
cks encumbering the same input.<br><br>Another use for the annex is locatin=
g there the SIGHASH_GROUP group count value. One advantage over placing the=
value as a script stack item could be to have annex payloads interdependen=
cy validity, where other annex payloads are reusing the group count value a=
s part of their own semantics.<br><br>Antoine<br></div><br><div class=3D"gm=
ail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0ven. 4 mars 2022 =
=C3=A0=C2=A018:22, Jeremy Rubin via bitcoin-dev <<a href=3D"mailto:bitco=
in-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>=
> a =C3=A9crit=C2=A0:<br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-fami=
ly:arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)">I've se=
en some discussion of what the Annex can be used for in Bitcoin. For exampl=
e, some people have discussed using the annex as a data field for something=
like CHECKSIGFROMSTACK type stuff (additional authenticated data) or for s=
omething like delegation (the delegation is to the annex). I think before d=
evs get too excited, we should have an open discussion about what this is a=
ctually for, and figure out if there are any constraints to using it howeve=
r we may please.</div><div class=3D"gmail_default" style=3D"font-family:ari=
al,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)"><br></div><div cl=
ass=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-=
size:small;color:rgb(0,0,0)">The BIP is tight lipped about it's purpose=
, saying mostly only:</div><div class=3D"gmail_default"><br><i>What is the =
purpose of the annex? The annex is a reserved space for future extensions, =
such as indicating the validation costs of computationally expensive new op=
codes in a way that is recognizable without knowing the scriptPubKey of the=
output being spent. Until the meaning of this field is defined by another =
softfork, users SHOULD NOT include annex in transactions, or it may lead to=
PERMANENT FUND LOSS.</i></div><div class=3D"gmail_default"><i><br></i></di=
v><div class=3D"gmail_default"><i>The annex (or the lack of thereof) is alw=
ays covered by the signature and contributes to transaction weight, but is =
otherwise ignored during taproot validation.</i></div><div class=3D"gmail_d=
efault"><i><br></i></div><div class=3D"gmail_default"><i>Execute the script=
, according to the applicable script rules[11], using the witness stack ele=
ments excluding the script s, the control block c, and the annex a if prese=
nt, as initial stack.</i></div><div class=3D"gmail_default"><font face=3D"a=
rial, helvetica, sans-serif" color=3D"#000000"><br></font></div><div class=
=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" color=3D"#00=
0000">Essentially, I read this as saying: The annex is the ability to pad a=
transaction with an additional string of 0's that contribute to the vi=
rtual weight of a transaction, but has no validation cost itself. Therefore=
, somehow, if you needed to validate more signatures than 1 per 50 virtual =
weight units, you could add padding to buy extra gas. Or, we might somehow =
make the witness a small language (e.g., run length encoded zeros) such tha=
t we can very quickly compute an equivalent number of zeros to 'charge&=
#39; without actually consuming the space but still consuming a linearizabl=
e resource... or something like that. We might also e.g. want to use the an=
nex to reserve something else, like the amount of memory. In general, we ar=
e using the annex to express a resource constraint efficiently. This might =
be useful for e.g. simplicity one day.</font></div><div class=3D"gmail_defa=
ult"><font face=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></fo=
nt></div><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-=
serif" color=3D"#000000">Generating an Annex: One should write a tracing ex=
ecutor for a script, run it, measure the resource costs, and then generate =
an annex that captures any externalized costs.</font></div><div class=3D"gm=
ail_default"><font face=3D"arial, helvetica, sans-serif" color=3D"#000000">=
<br></font></div><div class=3D"gmail_default"><font face=3D"arial, helvetic=
a, sans-serif" color=3D"#000000"><span>-------------------</span></font></d=
iv><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif"=
color=3D"#000000"><span><br></span></font></div><div class=3D"gmail_defaul=
t"><font face=3D"arial, helvetica, sans-serif" color=3D"#000000">Introducin=
g OP_ANNEX: Suppose there were some sort of annex pushing opcode, OP_ANNEX =
which puts the annex on the stack as well as a 0 or 1 (to differentiate ann=
ex is 0 from no annex, e.g. 0 1 means annex was 0 and 0 0 means no annex). =
This would be equivalent to something based on <annex flag> OP_TXHASH=
<has annex flag> OP_TXHASH.</font></div><div class=3D"gmail_default"=
><font face=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font><=
/div><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-seri=
f" color=3D"#000000">Now suppose that I have a computation that I am runnin=
g in a script as follows:</font></div><div class=3D"gmail_default"><br></di=
v><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" =
color=3D"#000000">OP_ANNEX</font></div><div class=3D"gmail_default"><font f=
ace=3D"arial, helvetica, sans-serif" color=3D"#000000">OP_IF</font></div><d=
iv class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" colo=
r=3D"#000000">=C2=A0 =C2=A0 `some operation that requires annex to be <1=
>`</font></div><div class=3D"gmail_default"><font face=3D"arial, helveti=
ca, sans-serif" color=3D"#000000">OP_ELSE</font></div><div class=3D"gmail_d=
efault"><font face=3D"arial, helvetica, sans-serif" color=3D"#000000">=C2=
=A0 =C2=A0 OP_SIZE</font></div><div class=3D"gmail_default"><font face=3D"a=
rial, helvetica, sans-serif" color=3D"#000000">=C2=A0 =C2=A0 `some operatio=
n that requires annex to be len(annex)=C2=A0+ 1 or does a checksig`</font><=
/div><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-seri=
f" color=3D"#000000">OP_ENDIF</font></div><div class=3D"gmail_default"><fon=
t face=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font></div>=
<div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" co=
lor=3D"#000000">Now every time you run this, it requires one more resource =
unit than the last time you ran it, which makes your satisfier use the anne=
x as some sort of "scratch space" for a looping construct, where =
you compute a new annex, loop with that value, and see if that annex is now=
accepted by the program.</font></div><div class=3D"gmail_default"><font fa=
ce=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font></div><div=
class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" color=
=3D"#000000">In short, it kinda seems like being able to read the annex off=
of the stack makes witness construction somehow turing complete, because w=
e can use it as a register/tape for some sort of computational model.</font=
></div><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-se=
rif" color=3D"#000000"><br></font></div><div class=3D"gmail_default"><div c=
lass=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" color=3D=
"#000000">-------------------</font></div></div><div class=3D"gmail_default=
"><font face=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font>=
</div><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-ser=
if" color=3D"#000000">This seems at odds with using the annex as something =
that just helps you heuristically guess =C2=A0computation costs, now it'=
;s somehow something that acts to make script satisfiers recursive.</font><=
/div><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-seri=
f" color=3D"#000000"><br></font></div><div class=3D"gmail_default"><font fa=
ce=3D"arial, helvetica, sans-serif" color=3D"#000000">Because the Annex is =
signed, and must be the same, this can also be inconvenient:</font></div><d=
iv class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" colo=
r=3D"#000000"><br></font></div><div class=3D"gmail_default"><font face=3D"a=
rial, helvetica, sans-serif" color=3D"#000000">Suppose that you have a Mini=
script that is something like: and(or(PK(A), PK(A')), X, or(PK(B), PK(B=
'))).</font></div><div class=3D"gmail_default"><font face=3D"arial, hel=
vetica, sans-serif" color=3D"#000000"><br></font></div><div class=3D"gmail_=
default"><font face=3D"arial, helvetica, sans-serif" color=3D"#000000">A or=
A' should sign with B or B'. X is some sort of fragment that might=
require a value that is unknown (and maybe recursively defined?) so theref=
ore if we send the PSBT to A first, which commits to the annex, and then X =
reads the annex and say it must be something else, A must sign again. So yo=
u might say, run X first, and then sign with A and C or B. However, what if=
the script somehow detects the bitstring WHICH_A WHICH_B and has a differe=
nt Annex per selection (e.g., interpret the bitstring as a int and annex mu=
st =3D=3D that int). Now, given and(or(K1, K1'),... or(Kn, Kn')) we=
end up with needing to pre-sign 2**n annex values somehow... this seems pr=
oblematic theoretically.</font></div><div class=3D"gmail_default"><font fac=
e=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font></div><div =
class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" color=
=3D"#000000">Of course this wouldn't be miniscript then. Because minisc=
ript is just for the well behaved subset of script, and this seems ill beha=
ved. So maybe we're OK?</font></div><div class=3D"gmail_default"><font =
face=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font></div><d=
iv class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" colo=
r=3D"#000000">But I think the issue still arises where suppose I have a sim=
ple thing like: and(COLD_LOGIC, HOT_LOGIC) where both contains a signature,=
if COLD_LOGIC and HOT_LOGIC can both have different costs, I need to decid=
e what logic each satisfier for the branch is going to use in advance, or s=
ign all possible sums of both our annex costs? This could come up if cold/h=
ot e.g. use different numbers of signatures / use checksigCISAadd which may=
be requires an annex argument.</font></div><div class=3D"gmail_default"><fo=
nt face=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font></div=
><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" c=
olor=3D"#000000"><br></font></div><div class=3D"gmail_default"><font face=
=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font></div><div c=
lass=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" color=3D=
"#000000">------------</font></div><div class=3D"gmail_default"><font face=
=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font></div><div c=
lass=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" color=3D=
"#000000">It seems like one good option is if we just go on and banish the =
OP_ANNEX. Maybe that solves some of this? I sort of think so. It definitely=
seems like we're not supposed to access it via script, given the quote=
from above:</font></div><div class=3D"gmail_default"><font face=3D"arial, =
helvetica, sans-serif" color=3D"#000000"><br></font></div><div class=3D"gma=
il_default"><div class=3D"gmail_default"><i>Execute the script, according t=
o the applicable script rules[11], using the witness stack elements excludi=
ng the script s, the control block c, and the annex a if present, as initia=
l stack.</i></div><br></div><div class=3D"gmail_default">If we were meant t=
o have it, we would have not nixed it from the stack, no? Or would have mad=
e the opcode for it as a part of taproot...</div><div class=3D"gmail_defaul=
t"><font face=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></font=
></div><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-se=
rif" color=3D"#000000">But recall that the annex is committed=C2=A0to by=C2=
=A0the signature.</font></div><div class=3D"gmail_default"><font face=3D"ar=
ial, helvetica, sans-serif" color=3D"#000000"><br></font></div><div class=
=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" color=3D"#00=
0000">So it's only a matter of time till we see some sort of Cat and Sc=
hnorr Tricks III the Annex Edition that lets you use G cleverly to get the =
annex onto the stack again, and then it's like we had OP_ANNEX all alon=
g, or without CAT, at least something that we can detect that the value has=
changed and cause this satisfier looping issue somehow.</font></div><div c=
lass=3D"gmail_default"><font face=3D"arial, helvetica, sans-serif" color=3D=
"#000000"><br></font></div><div class=3D"gmail_default"><font face=3D"arial=
, helvetica, sans-serif" color=3D"#000000">Not to mention if we just got OP=
_TXHASH</font></div><div class=3D"gmail_default"><font face=3D"arial, helve=
tica, sans-serif" color=3D"#000000"><br></font></div><div class=3D"gmail_de=
fault"><font face=3D"arial, helvetica, sans-serif" color=3D"#000000"><br></=
font></div><div class=3D"gmail_default"><font face=3D"arial, helvetica, san=
s-serif" color=3D"#000000"><br></font></div><div class=3D"gmail_default"><f=
ont face=3D"arial, helvetica, sans-serif" color=3D"#000000">-----------</fo=
nt></div><div class=3D"gmail_default"><font face=3D"arial, helvetica, sans-=
serif" color=3D"#000000"><br></font></div><div class=3D"gmail_default"><fon=
t face=3D"arial, helvetica, sans-serif" color=3D"#000000"><span>Is the anne=
x bad? After writing this I sort of think so?</span></font></div><div class=
=3D"gmail_default"><br></div><div class=3D"gmail_default"><font face=3D"ari=
al, helvetica, sans-serif" color=3D"#000000"><span>One solution would be to=
... just soft-fork it out. Always must be 0. When we come up with a use cas=
e for something like an annex, we can find a way to add it back.=C2=A0 Mayb=
e this means somehow pushing multiple annexes and having an annex stack, wh=
ere only sub-segments are signed for the last executed signature? That woul=
d solve looping... but would it break some aggregation thing? Maybe.</span>=
</font></div><div class=3D"gmail_default"><font face=3D"arial, helvetica, s=
ans-serif" color=3D"#000000"><br></font></div><div class=3D"gmail_default">=
<br></div><div class=3D"gmail_default">Another solution would be to make it=
so the annex is never committed=C2=A0to and unobservable from the script, =
but that the annex is always something that you can run get_annex(stack) to=
generate the annex. Thus it is a hint for validation rules, but not direct=
ly readable, and if it is modified you figure out the txn was cheaper somet=
ime after you execute the scripts and can decrease the value when you relay=
. But this sounds like something that needs to be a p2p only annex, because=
consensus we may not care (unless it's something like preallocating me=
mory for validation?).</div><div class=3D"gmail_default"><br></div><div cla=
ss=3D"gmail_default">-----------------------</div><div class=3D"gmail_defau=
lt"><br></div><div class=3D"gmail_default">Overall my preference is -- perh=
aps sadly -- looking like we should soft-fork it out of our current Checksi=
g (making the policy that it must 0 a consensus rule) and redesign the anne=
x technique later when we actually know what it is for with a new checksig =
or other mechanism. But It's not a hard opinion! It just seems like you=
can't practically use the annex for this worklimit type thing *and* ob=
serve it from the stack meaningfully.</div><div class=3D"gmail_default"><br=
></div><div class=3D"gmail_default"><br></div><div class=3D"gmail_default">=
<br></div><div class=3D"gmail_default">Thanks for coming to my ted-talk,</d=
iv><div class=3D"gmail_default"><br></div><div class=3D"gmail_default">Jere=
my</div><div class=3D"gmail_default"><br></div><div class=3D"gmail_default"=
><br></div><div><div dir=3D"ltr"><div dir=3D"ltr">--<br><a href=3D"https://=
twitter.com/JeremyRubin" target=3D"_blank">@JeremyRubin</a><br></div></div>=
</div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
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>
</blockquote></div>
--00000000000069d75705d9966154--
|