summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAntoine Riard <antoine.riard@gmail.com>2022-03-06 19:59:33 -0500
committerbitcoindev <bitcoindev@gnusha.org>2022-03-07 00:59:49 +0000
commitacc2f47b0758e41511604579684eb830a60372da (patch)
tree272a20dacba000b3a50e0ddb713e4bf90314d395
parent8a7007db1a051660d3b80c9b74132f022cea7916 (diff)
downloadpi-bitcoindev-acc2f47b0758e41511604579684eb830a60372da.tar.gz
pi-bitcoindev-acc2f47b0758e41511604579684eb830a60372da.zip
Re: [bitcoin-dev] Annex Purpose Discussion: OP_ANNEX, Turing Completeness, and other considerations
-rw-r--r--8d/8ad258d3e637bf32cfa645539f1672621a6b6c598
1 files changed, 598 insertions, 0 deletions
diff --git a/8d/8ad258d3e637bf32cfa645539f1672621a6b6c b/8d/8ad258d3e637bf32cfa645539f1672621a6b6c
new file mode 100644
index 000000000..f1c205c30
--- /dev/null
+++ b/8d/8ad258d3e637bf32cfa645539f1672621a6b6c
@@ -0,0 +1,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>&gt; I&#39;ve seen some discussion of wh=
+at the Annex can be used for in Bitcoin. For<br>&gt; example, some people h=
+ave discussed using the annex as a data field for<br>&gt; something like CH=
+ECKSIGFROMSTACK type stuff (additional authenticated data)<br>&gt; or for s=
+omething like delegation (the delegation is to the annex). I think<br>&gt; =
+before devs get too excited, we should have an open discussion about what<b=
+r>&gt; this is actually for, and figure out if there are any constraints to=
+ using<br>&gt; 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&#39;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&#39;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&#39;t know which one is going to confirm first, but where you don&#3=
+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 &lt;<a href=3D"mailto:bitco=
+in-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>=
+&gt; 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&#39;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&#39;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&#39;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 &#39;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 &lt;annex flag&gt; OP_TXHASH=
+ &lt;has annex flag&gt; 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 &lt;1=
+&gt;`</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 &quot;scratch space&quot; 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&#39=
+;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&#39;)), X, or(PK(B), PK(B=
+&#39;))).</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&#39; should sign with B or B&#39;. 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&#39;),... or(Kn, Kn&#39;)) 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&#39;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&#39;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&#39;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&#39;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&#39;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&#39;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&#39;s not a hard opinion! It just seems like you=
+ can&#39;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--
+