Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 58B56C000D for ; Thu, 23 Sep 2021 00:29:32 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 414EE415ED for ; Thu, 23 Sep 2021 00:29:32 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: 0.852 X-Spam-Level: X-Spam-Status: No, score=0.852 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, 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: smtp4.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 1o9pJLrF_Bkf for ; Thu, 23 Sep 2021 00:29:31 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-qk1-x72a.google.com (mail-qk1-x72a.google.com [IPv6:2607:f8b0:4864:20::72a]) by smtp4.osuosl.org (Postfix) with ESMTPS id D1C81415E4 for ; Thu, 23 Sep 2021 00:29:30 +0000 (UTC) Received: by mail-qk1-x72a.google.com with SMTP id c7so16399518qka.2 for ; Wed, 22 Sep 2021 17:29:30 -0700 (PDT) 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=TSNJ2McJNkJv2L6GaObEjFE8/yNfNy8IsqBN0KA2fY0=; b=AMATYdgRHXR9V8qqvoZqQCHIsKcJiKpJpvbE9vl0BWzfRkcsWiXyANHEe+suiQonFJ PJ75dSqyk4AKDuBW+uEKB088U6k0OKVHKwJVOeAGIe75cVDM4q/L2HdoyNcG3LoIIomN 50WXPdU+bLzFW97v/S7kL0RzLvquhP3tVrtzo6dt6k8BfOK1Jf+mejY/YWq+kqTOVdtT 5Kug3rFAOb2Ywyi8ix+NqDSk2cP3fXUbgMOXmpUzZR22sEmQ97Tl4PuUggHJsJ6SpF8n FTwm7iH066+1q0wcfnzXM2U2YST/WwFajmwujXOp55Gt+LEIbZji3dMzh7HQtwjU5ZNE F2uw== 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=TSNJ2McJNkJv2L6GaObEjFE8/yNfNy8IsqBN0KA2fY0=; b=X7ymNem16J7vTskpyQtATmF+igneNp7XLVy904bBrbfL4TsESvTkMl8rJ+aJ400Vt6 RCAjXQihWXIpjEdNZ2UgCpTP1+zFhbeV6s5o/alrkrJcP7WYOErVTCDKJK9e/98VMz0T NRUlVyb29wMKDZC7k1nCWM07rYbpX3cWl5C5qGmzMMwF1yKqLBdEESOmcUrb0NKMNJMk Bugh0DYp6zrThQozXidUC+0ANQEQuUm/qV4g6+7/YdjoqqkCqINZdWToqXDcn+MBmwDi N+DueEotMs3iKotO/LfAsvDSCJe21tY86TvGF5IijM9gvKXPeuLHD+6SAo6CHuZ1gT8x 0v4g== X-Gm-Message-State: AOAM532y8aAVtTyXiry7VyfyXfSMs7Sa4xdskwgxT/XB0lZ53xmn5HCb EVyW/YhPwoq7bdYYDRttrkAP4CB/Bz3TsKIlgApbNKCjXH4= X-Google-Smtp-Source: ABdhPJz3K+gMObC2XJg5shPqOFGS3r5Nl/vlnLPbaB+enFiqFbLoFY4uLIwaNUjbc7zvsse91cmWW+w/tUZFcRj5t8Y= X-Received: by 2002:a25:1b05:: with SMTP id b5mr2310231ybb.343.1632356969411; Wed, 22 Sep 2021 17:29:29 -0700 (PDT) MIME-Version: 1.0 References: <20210909064138.GA22496@erisian.com.au> In-Reply-To: <20210909064138.GA22496@erisian.com.au> From: Olaoluwa Osuntokun Date: Wed, 22 Sep 2021 17:29:18 -0700 Message-ID: To: Anthony Towns , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="0000000000004ef88105cc9eb936" Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 23 Sep 2021 00:29:32 -0000 --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
Hi AJ,

Happy to see that this proposal has finally= seen the light of day! I've been
hearing about it in hinted backgro= und 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 t= hree inputs: one that specifies how to update the
> internal public k= ey (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 sc= ript 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 t= hreshold of parties that control the output, or them
all (mu sig, etc, e= tc). This serves to create a generic "upgrade" mechanism
for a= ny tapscript output (covenant or not). Functionally, this is similar to
= the existence of "admin keys" or voted DAO upgrades that exists i= n 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 b= ehavior (leaf in
tree that accepts script updates), and also allows cont= ract developers to
progressively upgrade or fix issues in prior versions= of their deployed
contracts.

This little trick is secure since u= nlike the witness itself, the annex is
actually _signed_ within the sigh= ash like everything else. Incorporating
this proposal would require the = addition of an OP_PUSH_ANNEX op code, which
by itself seems expertly use= ful. If one views the annex as a sort of
authenticated associated data t= hat can be passed into the script execution
context, then this actually = serves to absorb _some_ uses cases of a
hypothetical OP_CHECKSIG_FROM_ST= ACK opcode. A push annex op code also makes
doing things like output del= egation to a given key passed into the witness
secure since the prior &q= uot;owner" of the output commits to the key within the
sighash.
=
Even assuming a more powerful type of covenant that allows partial
a= pplication of binding logic, something like this is still super useful
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
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 bei= ng unrolled (just a toy
example).

It would also allow an individu= al 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 scrip= t that tracks the next free leaf slot(s). With this model
an "opera= tor" is able to include a single transaction in the chain that
stam= ps a batch of updates in the payment tree.=C2=A0 Users then get a
contes= tation period where they can refute a modification to the tree in
order = to withdraw their funds.

> And second, it doesn't provide a w= ay for utxos to "interact",

This is due to the fact that t= he op code doesn't allow any sort of late
binding or pattern matchin= g 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 sys= tem 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<= br>contract in a single block w/o a coordination layer to synchronize theaccess.

One solution to this concurrency issue, that I believe is = already employed
by Chia is to allow "contracts" to be identif= ied 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 the= n specify their contract and "regular"
inputs, with the requir= ement that every transaction spends at least a single
regular input.
The trade-off here is that nodes need to maintain this extra index int= o the
UTXO set. However, this can be alleviated by applying a utreexo li= ke
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 covenan= t space has been processing over the
past few years. IMO its the single = most important (along with the utreexo
type stateless stuff mentioned ab= ove) 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/accou= nts-strict-access-lists-and-utxos/37
[4]: https://www.learnplasma.org/en/learn/cash.= html
[5]: https://epri= nt.iacr.org/2018/642
--0000000000004ef88105cc9eb936--