From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id DB0E3C000D for ; Thu, 9 Sep 2021 09:16:20 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id BDFC1401E4 for ; Thu, 9 Sep 2021 09:16:20 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -4.402 X-Spam-Level: X-Spam-Status: No, score=-4.402 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, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp4.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=mattcorallo.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 d1RMZ9v00LG7 for ; Thu, 9 Sep 2021 09:16:19 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 Received: from mail.as397444.net (mail.as397444.net [69.59.18.99]) by smtp4.osuosl.org (Postfix) with ESMTPS id DF380401E1 for ; Thu, 9 Sep 2021 09:16:18 +0000 (UTC) Received: by mail.as397444.net (Postfix) with ESMTPSA id 4H4tfR6ZMfz11x1H; Thu, 9 Sep 2021 09:16:15 +0000 (UTC) X-DKIM-Note: Keys used to sign are likely public at https://as397444.net/dkim/ DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mattcorallo.com; s=1631176864; t=1631178976; bh=VsQkMSWyKBWSfMuoYsN1gzj6kE6lXvlZjPCez7xL4oQ=; h=From:Subject:References:In-Reply-To:To:From; b=catdOXNi57dz5+0Xfh7c4lB0bxhSNmZi8oKMd2997hZ5RLsLyf4Ptu6OTAKtxleD4 CT74qDKVZOChQfL/E4vlfSUyyAGY826OUnMaw+FYcjpYvQGALdCw3SjfKVvSMJkyoi dbg3EBfP0YZEd8IYiwrXdvqYCqMLOHB0rwJ/ZvBGOfR4fLs6RkHqekw1LKNAHQmke2 HvsWZBWCPEwSM7SdZTjc1Qv/6Z6qaCfqEJBKUekv9m2xGnFE3vyLBPURnqXWZyV9QQ ZSv8vzO0htR2d4HYASprnhu0EKzOZwJEqPspxxlUWo+JOjZye5jWOIMQRWAOQcm7cP U6iWkzOGdDYFQ== Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Matt Corallo Mime-Version: 1.0 (1.0) Date: Thu, 9 Sep 2021 02:16:12 -0700 Message-Id: <2AED377C-17D3-45A0-B934-9EA5242B9487@mattcorallo.com> References: <20210909064138.GA22496@erisian.com.au> In-Reply-To: <20210909064138.GA22496@erisian.com.au> To: Anthony Towns , Bitcoin Protocol Discussion 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, 09 Sep 2021 09:16:21 -0000 Thanks for taking the time to write this up! To wax somewhat broadly here, I=E2=80=99m very excited about this as a direc= tion for bitcoin covenants. Other concrete proposals seem significantly more= limited, which worries me greatly. Further, this feels very =E2=80=9Ctaproo= t-native=E2=80=9D in a way that encourages utilizing taproot=E2=80=99s featu= res fully while building covenants, saving fees on chain and at least partia= lly improving privacy. I=E2=80=99ve been saying we need more covenants research and proposals befor= e we move forward with one and this is a huge step in that direction, IMO. W= ith Taproot activating soon, I=E2=80=99m excited for what coming forks bring= . Matt > On Sep 8, 2021, at 23:42, Anthony Towns via bitcoin-dev wrote: >=20 > =EF=BB=BFHello world, >=20 > A couple of years ago I had a flight of fancy [0] imagining how it > might be possible for everyone on the planet to use bitcoin in a > mostly decentralised/untrusted way, without requiring a block size > increase. It was a bit ridiculous and probably doesn't quite hold up, > and beyond needing all the existing proposals to be implemented (taproot, > ANYPREVOUT, CTV, eltoo, channel factories), it also needed a covenant > opcode [1]. I came up with something that I thought fit well with taproot,= > but couldn't quite figure out how to use it for anything other than my > ridiculous scheme, so left it at that. >=20 > But recently [2] Greg Maxwell emailed me about his own cool idea for a > covenant opcode, which turned out to basically be a reinvention of the > same idea but with more functionality, a better name and a less fanciful > use case; and with that inspiration, I think I've also now figured out > how to use it for a basic vault, so it seems worth making the idea a > bit more public. >=20 > I'll split this into two emails, this one's the handwavy overview, > the followup will go into some of the implementation complexities. >=20 >=20 >=20 > The basic idea is to think about "updating" a utxo by changing the > taproot tree. >=20 > As you might recall, a taproot address is made up from an internal public > key (P) and a merkle tree of scripts (S) combined via the formula Q=3DP+H(= P, > S)*G to calculate the scriptPubKey (Q). When spending using a script, > you provide the path to the merkle leaf that has the script you want > to use in the control block. The BIP has an example [3] with 5 scripts > arranged as ((A,B), ((C,D), E)), so if you were spending with E, you'd > reveal a path of two hashes, one for (AB), then one for (CD), then you'd > reveal your script E and satisfy it. >=20 > So that makes it relatively easy to imagine creating a new taproot address= > based on the input you're spending by doing some or all of the following: >=20 > * Updating the internal public key (ie from P to P' =3D P + X) > * Trimming the merkle path (eg, removing CD) > * Removing the script you're currently executing (ie E) > * Adding a new step to the end of the merkle path (eg F) >=20 > Once you've done those things, you can then calculate the new merkle > root by resolving the updated merkle path (eg, S' =3D MerkleRootFor(AB, > F, H_TapLeaf(E))), and then calculate a new scriptPubKey based on that > and the updated internal public key (Q' =3D P' + H(P', S')). >=20 > 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. The opcode then calculates the > scriptPubKey that matches that, and verifies that the output corresponding= > to the current input spends to that scriptPubKey. >=20 > That's useless without some way of verifying that the new utxo retains > the bitcoin that was in the old utxo, so also include a new opcode > IN_OUT_AMOUNT that pushes two items onto the stack: the amount from this > input's utxo, and the amount in the corresponding output, and then expect > anyone using TLUV to use maths operators to verify that funds are being > appropriately retained in the updated scriptPubKey. >=20 >=20 >=20 > Here's two examples of how you might use this functionality. >=20 > First, a basic vault. The idea is that funds are ultimately protected > by a cold wallet key (COLD) that's inconvenient to access but is as > safe from theft as possible. In order to make day to day transactions > more convenient, a hot wallet key (HOT) is also available, which is > more vulnerable to theft. The vault design thus limits the hot wallet > to withdrawing at most L satoshis every D blocks, so that if funds are > stolen, you lose at most L, and have D blocks to use your cold wallet > key to re-secure the funds and prevent further losses. >=20 > To set this up with TLUV, you construct a taproot output with COLD as > the internal public key, and a script that specifies: >=20 > * The tx is signed via HOT > * CSV -- there's a relative time lock since the last spend > * If the input amount is less than L + dust threshold, fine, all done, > the vault can be emptied. > * Otherwise, the output amount must be at least (the input amount - > L), and do a TLUV check that the resulting sPK is unchanged >=20 > So you can spend up to "L" satoshis via the hot wallet as long as you > wait D blocks since the last spend, and can do whatever you want via a > key path spend with the cold wallet. >=20 > You could extend this to have a two phase protocol for spending, where > first you use the hot wallet to say "in D blocks, allow spending up to > L satoshis", and only after that can you use the hot wallet to actually > spend funds. In that case supply a taproot sPK with COLD as the internal > public key and two scripts, the "release" script, which specifies: >=20 > * The tx is signed via HOT > * Output amount is greater or equal to the input amount. > * Use TLUV to check: > + the output sPK has the same internal public key (ie COLD) > + the merkle path has one element trimmed > + the current script is included > + a new step is added that matches either H_LOCKED or H_AVAILABLE as > described below (depending on whether 0 or 1 was provided as > witness info) >=20 > The other script is either "locked" (which is just "OP_RETURN") or > "available" which specifies: >=20 > * The tx is signed via HOT > * CSV -- there's a relative time lock since the last spend (ie, > when the "release" script above was used) > * If the input amount is less than L, fine, all done, the vault can > be emptied > * Otherwise, the output amount must be at least (the input amount minus > L), and via TLUV, check the resulting sPK keeps the internal pubkey > unchanged, keeps the merkle path, drops the current script, and adds > H_LOCKED as the new step. >=20 > H_LOCKED and H_AVAILABLE are just the TapLeaf hash corresponding to the > "locked" and "available" scripts. >=20 > I believe this latter setup matches the design Bryan Bishop talked about > a couple of years ago [4], with the benefit that it's fully recursive, > allows withdrawals to vary rather than be the fixed amount L (due to not > relying on pre-signed transactions), and generally seems a bit simpler > to work with. >=20 >=20 >=20 > The second scheme is allowing for a utxo to represent a group's pooled > funds. The idea being that as long as everyone's around you can use > the taproot key path to efficiently move money around within the pool, > or use a single transaction and signature for many people in the pool > to make payments. But key path spends only work if everyone's available > to sign -- what happens if someone disappears, or loses access to their > keys, or similar? For that, we want to have script paths to allow other > people to reclaim their funds even if everyone else disappears. So we > setup scripts for each participant, eg for Alice: >=20 > * The tx is signed by Alice > * The output value must be at least the input value minus Alice's balance > * Must pass TLUV such that: > + the internal public key is the old internal pubkey minus Alice's key > + the currently executing script is dropped from the merkle path > + no steps are otherwise removed or added >=20 > The neat part here is that if you have many participants in the pool, > the pool continues to operate normally even if someone makes use of the > escape hatch -- the remaining participants can still use the key path to > spend efficiently, and they can each unilaterally withdraw their balance > via their own script path. If everyone decides to exit, whoever is last > can spend the remaining balance directly via the key path. >=20 > Compared to having on-chain transactions using non-pooled funds, this > is more efficient and private: a single one-in, one-out transaction > suffices for any number of transfers within the pool, and there's no > on-chain information about who was sending/receiving the transfers, or > how large the transfers were; and for transfers out of the pool, there's > no on-chain indication which member of the pool is sending the funds, > and multiple members of the pool can send funds to multiple destinations > with only a single signature. The major constraint is that you need > everyone in the pool to be online in order to sign via the key path, > which provides a practical limit to how many people can reasonably be > included in a pool before there's a breakdown. >=20 > Compared to lightning (eg eltoo channel factories with multiple > participants), the drawback is that no transfer is final without an > updated state being committed on chain, however there are also benefits > including that if one member of the pool unilaterally exits, that > doesn't reveal the state of anyone remaining in the pool (eg an eltoo > factory would likely reveal the balances of everyone else's channels at > that point). >=20 > A simpler case for something like this might be for funding a joint > venture -- suppose you're joining with some other early bitcoiners to > buy land to build a citadel, so you each put 20 BTC into a pooled utxo, > ready to finalise the land purchase in a few months, but you also want > to make sure you can reclaim the funds if the deal falls through. So > you might include scripts like the above that allow you to reclaim your > balance, but add a CLTV condition preventing anyone from doing that until > the deal's deadline has passed. If the deal goes ahead, you all transfer > the funds to the vendor via the keypath; if it doesn't work out, you > hopefully return your funds via the keypath, but if things turn really > sour, you can still just directly reclaim your 20 BTC yourself via the > script path. >=20 >=20 >=20 > I think a nice thing about this particular approach to recursive covenants= > at a conceptual level is that it automatically leaves the key path as an > escape mechanism -- rather than having to build a base case manually, > and have the risk that it might not work because of some bug, locking > your funds into the covenant permanently; the escape path is free, easy, > and also the optimal way of spending things when everything is working > right. (Of course, you could set the internal public key to a NUMS point > and shoot yourself in the foot that way anyway) >=20 >=20 >=20 > I think there's two limitations of this method that are worth pointing out= . >=20 > First it can't tweak scripts in areas of the merkle tree that it can't > see -- I don't see a way of doing that particularly efficiently, so maybe > it's best just to leave that as something for the people responsible for > the funds to negotiate via the keypath, in which case it's automatically > both private and efficient since all the details stay off-chain, anyway >=20 > And second, it doesn't provide a way for utxos to "interact", which is > something that is interesting for automated market makers [5], but perhaps= > only interesting for chains aiming to support multiple asset types, > and not bitcoin directly. On the other hand, perhaps combining it with > CTV might be enough to solve that, particularly if the hash passed to > CTV is constructed via script/CAT/etc. >=20 >=20 >=20 > (I think everything described here could be simulated with CAT and > CHECKSIGFROMSTACK (and 64bit maths operators and some way to access > the internal public key), the point of introducing dedicated opcodes > for this functionality rather than (just) having more generic opcodes > would be to make the feature easy to use correctly, and, presuming it > actually has a wide set of use cases, to make it cheap and efficient > both to use in wallets, and for nodes to validate) >=20 > Cheers, > aj >=20 > [0] https://gist.github.com/ajtowns/dc9a59cf0a200bd1f9e6fb569f76f7a0 >=20 > [1] Roughly, the idea was that if you have ~9 billion people using > bitcoin, but can only have ~1000 transactions per block, then you > need have each utxo represent a significant number of people. That > means that you need a way of allowing the utxo's to be efficiently > spent, but need to introduce some level of trust since expecting > many people to constantly be online seems unreliable, but to remain > mostly decentralised/untrusted, you want to have some way of limiting > how much trust you're introducing, and that's where covenants come in. >=20 > [2] Recently in covid-adjusted terms, or on the bitcoin consensus > change scale anyway... > https://mobile.twitter.com/ajtowns/status/1385091604357124100=20 >=20 > [3] https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#Constru= cting_and_spending_Taproot_outputs=20 >=20 > [4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/01= 7231.html >=20 > [5] The idea behind an automated market maker being that you setup a > script that says "you can withdraw x BTC if you deposit f(x) units of > USDT, or you can withdraw g(x) units of USDT if you deposit x units > of BTC", with f(x)/x giving the buy price, and f(x)>g(x) meaning > you make a profit. Being able to specify a covenant that links the > change in value to the BTC utxo (+/-x) and the change in value to > the USDT utxo (+f(x) or -g(x)) is what you'd need to support this > sort of use case, but TLUV doesn't provide a way to do that linkage. >=20 > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev