MIME-Version: 1.0
References: <20210909064138.GA22496@erisian.com.au>
In-Reply-To: <20210909064138.GA22496@erisian.com.au>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Wed, 22 Sep 2021 17:29:18 -0700
Message-ID: <CAO3Pvs-OviFkDJOsOWOt3Ea9t0g6xXb79hYdEe_L1=nB5ZjSQw@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000004ef88105cc9eb936"
Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode
Precedence: list

--0000000000004ef88105cc9eb936
Content-Type: text/plain; charset="UTF-8"

Hi AJ,

Happy to see that this proposal has finally seen the light of day! I've been
hearing about it in hinted background convos over the past few months, so
happy I can finally dig into the specifics of its operation.

> So the idea is to do just that via a new opcode "TAPLEAF_UPDATE_VERIFY"
> (TLUV) that takes three inputs: one that specifies how to update the
> internal public key (X), one that specifies a new step for the merkle path
> (F), and one that specifies whether to remove the current script and/or
> how many merkle path steps to remove

What if instead, it obtained the script from the _annex_? I think this small
modification would make the op code even _more_ powerful. Consider that this
allows a new script to be passed _dynamically_ after the output has been
created, possibly by a threshold of parties that control the output, or them
all (mu sig, etc, etc). This serves to create a generic "upgrade" mechanism
for any tapscript output (covenant or not). Functionally, this is similar to
the existence of "admin keys" or voted DAO upgrades that exists in chains
that utilize an account based systems. This is really useful as it allows a
script any given output to optional add in graftroot like behavior (leaf in
tree that accepts script updates), and also allows contract developers to
progressively upgrade or fix issues in prior versions of their deployed
contracts.

This little trick is secure since unlike the witness itself, the annex is
actually _signed_ within the sighash like everything else. Incorporating
this proposal would require the addition of an OP_PUSH_ANNEX op code, which
by itself seems expertly useful. If one views the annex as a sort of
authenticated associated data that can be passed into the script execution
context, then this actually serves to absorb _some_ uses cases of a
hypothetical OP_CHECKSIG_FROM_STACK opcode. A push annex op code also makes
doing things like output delegation to a given key passed into the witness
secure since the prior "owner" of the output commits to the key within the
sighash.

Even assuming a more powerful type of covenant that allows partial
application of binding logic, something like this is still super useful
since the action of re-creating a new tapscript tree based in dynamic input
data would generate a rather large witness if only something like OP_CAT was
available. The unique "update" nature of this appears to augment any other
type of covenant, which is pretty cool. Consider that it would allow you
(with the annex addition above), take something like a CTV congestion tree,
and add in _new_ users at the tree is already being unrolled (just a toy
example).

It would also allow an individual to _join_ the payment pool construct
described earlier which makes it 1000x more useful (vs just supporting
unrolling). I haven't written it all down yet, but I think this along with
something like CTV or CSFS makes it possible to implement a Plasma Cash [4]
like Commit Chain [5], which is super exciting (assume a counter is embedded
in the main script that tracks the next free leaf slot(s). With this model
an "operator" is able to include a single transaction in the chain that
stamps a batch of updates in the payment tree.  Users then get a
contestation period where they can refute a modification to the tree in
order to withdraw their funds.

> And second, it doesn't provide a way for utxos to "interact",

This is due to the fact that the op code doesn't allow any sort of late
binding or pattern matching then constraining _where_ (or whence?) the coins
can Be sent to. There's a group of developers that are attempting to make an
AMM-like system on Liquid [1] using more generic stack based covenants [2]
(see the `OP_INSPECTINPUT` op code, which seems very much inspired by
jl2012's old proposal). However one challenge that still need to be tackled
in the UTXO model is allowing multiple participants to easily interact w/
the
contract in a single block w/o a coordination layer to synchronize the
access.

One solution to this concurrency issue, that I believe is already employed
by Chia is to allow "contracts" to be identified via a fixed ID (as long as
their active in the chain) [3]. This lets transactions spend/interact with a
contract, without always needing to know the set of active UTXOs where that
contract lives. Transactions then specify their contract and "regular"
inputs, with the requirement that every transaction spends at least a single
regular input.

The trade-off here is that nodes need to maintain this extra index into the
UTXO set. However, this can be alleviated by applying a utreexo like
solution: nodes maintain some merklized data structure over the index and
require that spending transactions provide an _inclusion_ proof of the
active contract. Nodes then only need to maintain root hashes of the UTXO
and contract set.

I'm super happy w.r.t how the covenant space has been processing over the
past few years. IMO its the single most important (along with the utreexo
type stateless stuff mentioned above) missing component to allow the
creation of more decentralized self-custodial applications built on top of
Bitcoin.

-- Laolu

[1]: https://medium.com/bit-matrix
[2]:
https://github.com/sanket1729/elements/blob/84339ba5e5dc65328d98afe2b1b33dcb69ba4311/doc/tapscript_opcodes.md
[3]: https://forum.celestia.org/t/accounts-strict-access-lists-and-utxos/37
[4]: https://www.learnplasma.org/en/learn/cash.html
[5]: https://eprint.iacr.org/2018/642

--0000000000004ef88105cc9eb936
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi AJ, <br><br>Happy to see that this proposal has finally=
 seen the light of day! I&#39;ve been<br>hearing about it in hinted backgro=
und convos over the past few months, so<br>happy I can finally dig into the=
 specifics of its operation.<br><br>&gt; So the idea is to do just that via=
 a new opcode &quot;TAPLEAF_UPDATE_VERIFY&quot;<br>&gt; (TLUV) that takes t=
hree inputs: one that specifies how to update the<br>&gt; internal public k=
ey (X), one that specifies a new step for the merkle path<br>&gt; (F), and =
one that specifies whether to remove the current script and/or<br>&gt; how =
many merkle path steps to remove<br><br>What if instead, it obtained the sc=
ript from the _annex_? I think this small<br>modification would make the op=
 code even _more_ powerful. Consider that this<br>allows a new script to be=
 passed _dynamically_ after the output has been<br>created, possibly by a t=
hreshold of parties that control the output, or them<br>all (mu sig, etc, e=
tc). This serves to create a generic &quot;upgrade&quot; mechanism<br>for a=
ny tapscript output (covenant or not). Functionally, this is similar to<br>=
the existence of &quot;admin keys&quot; or voted DAO upgrades that exists i=
n chains<br>that utilize an account based systems. This is really useful as=
 it allows a<br>script any given output to optional add in graftroot like b=
ehavior (leaf in<br>tree that accepts script updates), and also allows cont=
ract developers to<br>progressively upgrade or fix issues in prior versions=
 of their deployed<br>contracts.<br><br>This little trick is secure since u=
nlike the witness itself, the annex is<br>actually _signed_ within the sigh=
ash like everything else. Incorporating<br>this proposal would require the =
addition of an OP_PUSH_ANNEX op code, which<br>by itself seems expertly use=
ful. If one views the annex as a sort of<br>authenticated associated data t=
hat can be passed into the script execution<br>context, then this actually =
serves to absorb _some_ uses cases of a<br>hypothetical OP_CHECKSIG_FROM_ST=
ACK opcode. A push annex op code also makes<br>doing things like output del=
egation to a given key passed into the witness<br>secure since the prior &q=
uot;owner&quot; of the output commits to the key within the<br>sighash.<br>=
<br>Even assuming a more powerful type of covenant that allows partial<br>a=
pplication of binding logic, something like this is still super useful<br>s=
ince the action of re-creating a new tapscript tree based in dynamic input<=
br>data would generate a rather large witness if only something like OP_CAT=
 was<br>available. The unique &quot;update&quot; nature of this appears to =
augment any other<br>type of covenant, which is pretty cool. Consider that =
it would allow you<br>(with the annex addition above), take something like =
a CTV congestion tree,<br>and add in _new_ users at the tree is already bei=
ng unrolled (just a toy<br>example).<br><br>It would also allow an individu=
al to _join_ the payment pool construct<br>described earlier which makes it=
 1000x more useful (vs just supporting<br>unrolling). I haven&#39;t written=
 it all down yet, but I think this along with<br>something like CTV or CSFS=
 makes it possible to implement a Plasma Cash [4]<br>like Commit Chain [5],=
 which is super exciting (assume a counter is embedded<br>in the main scrip=
t that tracks the next free leaf slot(s). With this model<br>an &quot;opera=
tor&quot; is able to include a single transaction in the chain that<br>stam=
ps a batch of updates in the payment tree.=C2=A0 Users then get a<br>contes=
tation period where they can refute a modification to the tree in<br>order =
to withdraw their funds.<br><br>&gt; And second, it doesn&#39;t provide a w=
ay for utxos to &quot;interact&quot;,<br><br>This is due to the fact that t=
he op code doesn&#39;t allow any sort of late<br>binding or pattern matchin=
g then constraining _where_ (or whence?) the coins<br>can Be sent to. There=
&#39;s a group of developers that are attempting to make an<br>AMM-like sys=
tem on Liquid [1] using more generic stack based covenants [2]<br>(see the =
`OP_INSPECTINPUT` op code, which seems very much inspired by<br>jl2012&#39;=
s old proposal). However one challenge that still need to be tackled<br>in =
the UTXO model is allowing multiple participants to easily interact w/ the<=
br>contract in a single block w/o a coordination layer to synchronize the<b=
r>access.<br><br>One solution to this concurrency issue, that I believe is =
already employed<br>by Chia is to allow &quot;contracts&quot; to be identif=
ied via a fixed ID (as long as<br>their active in the chain) [3]. This lets=
 transactions spend/interact with a<br>contract, without always needing to =
know the set of active UTXOs where that<br>contract lives. Transactions the=
n specify their contract and &quot;regular&quot;<br>inputs, with the requir=
ement that every transaction spends at least a single<br>regular input. <br=
><br>The trade-off here is that nodes need to maintain this extra index int=
o the<br>UTXO set. However, this can be alleviated by applying a utreexo li=
ke<br>solution: nodes maintain some merklized data structure over the index=
 and<br>require that spending transactions provide an _inclusion_ proof of =
the<br>active contract. Nodes then only need to maintain root hashes of the=
 UTXO<br>and contract set.<br><br>I&#39;m super happy w.r.t how the covenan=
t space has been processing over the<br>past few years. IMO its the single =
most important (along with the utreexo<br>type stateless stuff mentioned ab=
ove) missing component to allow the<br>creation of more decentralized self-=
custodial applications built on top of<br>Bitcoin.<br><br>-- Laolu<br><br>[=
1]: <a href=3D"https://medium.com/bit-matrix">https://medium.com/bit-matrix=
</a> <br>[2]: <a href=3D"https://github.com/sanket1729/elements/blob/84339b=
a5e5dc65328d98afe2b1b33dcb69ba4311/doc/tapscript_opcodes.md">https://github=
.com/sanket1729/elements/blob/84339ba5e5dc65328d98afe2b1b33dcb69ba4311/doc/=
tapscript_opcodes.md</a><br>[3]: <a href=3D"https://forum.celestia.org/t/ac=
counts-strict-access-lists-and-utxos/37">https://forum.celestia.org/t/accou=
nts-strict-access-lists-and-utxos/37</a><br>[4]: <a href=3D"https://www.lea=
rnplasma.org/en/learn/cash.html">https://www.learnplasma.org/en/learn/cash.=
html</a> <br>[5]: <a href=3D"https://eprint.iacr.org/2018/642">https://epri=
nt.iacr.org/2018/642</a><br></div>

--0000000000004ef88105cc9eb936--