Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

From: Antoine Riard <[email-masked]>
Date: Sun, 12 Sep 2021 19:37:56 -0400

Sorry for the lack of clarity, sometimes it sounds easier to explain ideas
with code.

While MERKLESUB is still WIP, here the semantic. If the input spent is a
SegWit v1 Taproot output, and the script path spending is used, the top
stack item is interpreted as an output position of the spending
transaction. The second top stack item is interpreted as a 32-byte x-only
pubkey to be negated and added to the spent internal pubkey.

The spent tapscript is removed from the merkle tree of tapscripts and a new
merkle root is recomputed with the first node element of the spending
control block as the tapleaf hash. From then, this new merkle root is added
as the taproot tweak to the updated internal pubkey, while correcting for
parity. This new tweaked pubkey is interpreted as a v1 witness program and
must match the scriptPubKey of the spending transaction output as the
passed position. Otherwise, MERKLESUB returns a failure.

I believe this is matching your description and the main difference
compared to your TLUV proposal is the lack of merkle tree extension, where
a new merkle path is added in place of the removed tapscript. Motivation is
saving up the one byte of the new merkle path step, which is not necessary
for our CoinPool use-case.

> That would mean anyone who could do a valid spend of the tx could
> violate the covenant by spending to an unencumbered witness v2 output
> and (by collaborating with a miner) steal the funds. I don't think
> there's a reasonable way to have existing covenants be forward
> compatible with future destination addresses (beyond something like CTV
> that strictly hardcodes them).

That's a good catch, thanks for raising it :)

Depends how you define reasonable, but I think one straightforward fix is
to extend the signature digest algorithm to encompass the segwit version
(and maybe program-size ?) of the spending transaction outputs.

Then you add a "contract" aggregated-key in every tapscript where a
TLUV/MERKLESUB covenant is present. The off-chain contract participant can
exchange signatures at initial setup committing to the segwit version. I
think this addresses the sent-to-unknown-witness-output point ?

When future destination addresses are deployed, assuming a new round of
interactivity, the participants can send the fund to a v1+ by exchanging
signatures with SIGHASH_ALL, that way authorizing the bypass of
TLUV/MERKLESUB.

Of course, in case of v1+ deployment, the key path could be used. Though
this path could have been "burnt" by picking up an internal point with an
unknown scalar following the off-chain contract/use-case semantic ?

> Having the output position parameter might be an interesting way to
> merge/split a vault/pool, but it's not clear to me how much sense it
> makes sense to optimise for that, rather than just doing that via the key
> path. For pools, you want the key path to be common anyway (for privacy
> and efficiency), so it shouldn't be a problem; but even for vaults,
> you want the cold wallet accessible enough to be useful for the case
> where theft is attempted, and maybe that's also accessible enough for
> the ocassional merge/split to keep your utxo count/sizes reasonable.

I think you can come up with interesting contract policies. Let's say you
want to authorize the emergency path of your pool/vault balances if X
happens (e.g a massive drop in USDT price signed by DLC oracles). You have
(A+B+C+D) forking into (A+B) and (C+D) pooled funds. To conserve the
contracts pre-negotiated economic equilibrium, all the participants would
like the emergency path to be inherited on both forks. Without relying on
the key path interactivity, which is ultimately a trust on the post-fork
cooperation of your counterparty ?

> Saving a byte of witness data at the cost of specifying additional
> opcodes seems like optimising the wrong thing to me.

I think we should keep in mind that any overhead cost in the usage of a
script primitive is echoed to the user of off-chain contract/payment
channels. If the tapscripts are bigger, your average on-chain spends in
case of non-cooperative scenarios are increased in consequence, and as such
your fee-bumping reserve. Thus making those systems less economically
accessible.

If we really envision having billions of Bitcoin users owning a utxo or
shards of them, we should also think that those users might have limited
means to pay on-chain fees. Where should be the line between resource
optimizations and protocol/implementation complexity ? Hard to tell.

> I don't think that works, because different scripts in the same merkle
> tree can have different script versions, which would here indicate
> different parities for the same internal pub key.

Let me make it clearer. We introduce a new tapscript version 0x20, forcing
a new bit in the first byte of the control block to be interpreted as the
parity bit of the spent internal pubkey. To ensure this parity bit is
faithful and won't break the updated key path, it's committed in the spent
taptweak. A malicious counterparty while having malleability on the control
block, by setting the parity bit to the wrong value will break the taptweak
and fail the taproot commitment verification ?

I think the correct commitment of different script versions in the merkle
tree can be verified by tree participants at setup ?

> The IN_OUT_AMOUNT opcode lets you do maths on the values, so you can
> specify "hot wallets can withdraw up to X" rather than "hot wallets
> must withdraw exactly X". I don't think there's a way of doing that with
> SIGHASH_GROUP, even with a modifier like ANYPUBKEY?

You can exchange signatures for withdraw outputs with multiples `nValue`
covering the authorized range, assuming the ANYAMOUNT modifier ? One
advantage of leveraging sighash is the ability to update a withdraw policy
in real-time. Vaults participants might be willing to bump the withdraw
policy beyond X, assuming you have N-of-M consents.

> If you want to tweak all the scripts, I think you should be using the
> key path.
>
> One way you could do somthing like that without changing the scripts
> though, is have the timelock on most of the scripts be something like
> "[3 months] CSV", and have a "delay" script that doesn't require a CSV,
> does require a signature from someone able to authorise the delay,
> and requires the output to have the same scriptPubKey and amount. Then
> you can use that path to delay resolution by 3 months however often,
> even if you can't coordinate a key path spend

I think I would like to express the following contract policy. Let's say
you have 1) a one-time conditional script path to withdraw fund ("a put on
strike price X"), 2) a conditional script path to tweak by 3 months all the
usual withdraw path and 3) those remaining withdraw paths. Once played out,
you would like the one-time path to be removed from your merkle tree. And
this removal to be inherited on the tweaked tree if 2) plays out.

I agree that's advanced Bitcoin contracting and we might not require from
one script primitive to cover the whole expressivity we're aiming to.

> that's a constant product market maker without a profit margin. There's
> lots of research in the ethereum world about doing these things, and
> bitmatrix is trying to do it on liquid. It's not clear to me if there's
> anywhere in bitcoin per se that it would make sense.

Good with the more detailed explanation. Yeah I know it's widely deployed
on the ethereum-side, still late on catching up with literature/resources
on that. Assuming we have a widely-deployed token protocol on the
bitcoin-side, you could couple it with a DLC-style of security model and
that might be enough to bootstrap a fruitful token trading ecosystem ?
Though I agree, expressing an AMM in bitcoin primitives is an interesting
design challenge!

> So maybe it would make more sense to introduce an opcode
> that builds a merkle root from tagged hashes directly, rather than one
> that lets you compare to 32B strings so that you can do the TapBranch
> logic manually.

IIUC, you would like an opcode to edit the spent merkle root or build a new
one from stack elements ? E.g adding new withdraw tapleaf if the input
amount is over X. I think that the design description gives more
flexibility but I'm worried you will need more than one opcode. Like
OP_TWEAKADD, to add the tweak on the updated internal key and
OP_SCRIPTPUBKEY_VERIFY (or at least OP_CSFS though more expensive) ?

Le ven. 10 sept. 2021 à 23:26, Anthony Towns <[email-masked]> a écrit :

> On Fri, Sep 10, 2021 at 12:12:24AM -0400, Antoine Riard wrote:
> > "Talk is cheap. Show me the code" :p
> >     case OP_MERKLESUB:
>
> I'm not entirely clear on what your opcode there is trying to do. I
> think it's taking
>
>    <N> <P> MERKLESUB
>
> and checking that output N has the same scripts as the current input
> except with the current script removed, and with its internal pubkey as
> the current input's internal pubkey plus P.
>
> >         txTo->vout[out_pos].scriptPubKey.IsWitnessProgram(witnessversion,
> > witnessprogram);
> >         //! The committed to output must be a witness v1 program at least
>
> That would mean anyone who could do a valid spend of the tx could
> violate the covenant by spending to an unencumbered witness v2 output
> and (by collaborating with a miner) steal the funds. I don't think
> there's a reasonable way to have existing covenants be forward
> compatible with future destination addresses (beyond something like CTV
> that strictly hardcodes them).
>
> > One could also imagine a list of output positions to force the taproot
> update
> > on multiple outputs ("OP_MULTIMERKLESUB").
>
> Having the output position parameter might be an interesting way to
> merge/split a vault/pool, but it's not clear to me how much sense it
> makes sense to optimise for that, rather than just doing that via the key
> path. For pools, you want the key path to be common anyway (for privacy
> and efficiency), so it shouldn't be a problem; but even for vaults,
> you want the cold wallet accessible enough to be useful for the case
> where theft is attempted, and maybe that's also accessible enough for
> the ocassional merge/split to keep your utxo count/sizes reasonable.
>
> > For the merkle branches extension, I was thinking of introducing a
> separate
> > OP_MERKLEADD, maybe to *add* a point to the internal pubkey group
> signer. If
> > you're only interested in leaf pruning, using OP_MERKLESUB only should
> save you
> > one byte of empty vector ?
>
> Saving a byte of witness data at the cost of specifying additional
> opcodes seems like optimising the wrong thing to me.
>
> > One solution I was thinking about was introducing a new tapscript version
> > (`TAPROOT_INTERNAL_TAPSCRIPT`) signaling that VerifyTaprootCommitment
> must
> > compute the TapTweak with a new TapTweak=(internal_pubkey || merkle_root
> ||
> > parity_bit). A malicious participant wouldn't be able to interfere with
> the
> > updated internal key as it would break its own spending taproot
> commitment
> > verification ?
>
> I don't think that works, because different scripts in the same merkle
> tree can have different script versions, which would here indicate
> different parities for the same internal pub key.
>
> > > 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.
> > Credit to you for the SIGHASH_GROUP design, here the code, with
> > SIGHASH_ANYPUBKEY/ANYAMOUNT extensions.
> >
> > I think it's achieving the same effect as IN_OUT_AMOUNT, at least for
> CoinPool
> > use-case.
>
> The IN_OUT_AMOUNT opcode lets you do maths on the values, so you can
> specify "hot wallets can withdraw up to X" rather than "hot wallets
> must withdraw exactly X". I don't think there's a way of doing that with
> SIGHASH_GROUP, even with a modifier like ANYPUBKEY?
>
> > (I think I could come with some use-case from lex mercatoria where if
> you play
> > out a hardship provision you want to tweak all the other provisions by a
> CSV
> > delay while conserving the rest of their policy)
>
> If you want to tweak all the scripts, I think you should be using the
> key path.
>
> One way you could do somthing like that without changing the scripts
> though, is have the timelock on most of the scripts be something like
> "[3 months] CSV", and have a "delay" script that doesn't require a CSV,
> does require a signature from someone able to authorise the delay,
> and requires the output to have the same scriptPubKey and amount. Then
> you can use that path to delay resolution by 3 months however often,
> even if you can't coordinate a key path spend.
>
> > > 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.
> > That's where SIGHASH_GROUP might be more interesting as you could
> generate
> > transaction "puzzles".
> > IIUC, the problem is how to have a set of ratios between x/f(x).
>
> Normal way to do it is specify a formula, eg
>
>    outBTC * outUSDT >= inBTC * inUSDT
>
> that's a constant product market maker without a profit margin. There's
> lots of research in the ethereum world about doing these things, and
> bitmatrix is trying to do it on liquid. It's not clear to me if there's
> anywhere in bitcoin per se that it would make sense.
>
> Then your relative balances of each token imply a price, and traders will
> rebalance anytime that price is out of whack with the rest of the market.
>
> You can tweak the formula so that you make a profit, which also ends up
> meaning the fund pool becomes more liquid overtime. But that means that
> you want to cope with 100 BTC and 5M USDT at $50k, but also 200 BTC and
> 10M USDT at $50k, and many values in between. So I don't think:
>
> > The maker generates a Taproot tree where each leaf is committing to a
> different
> > "strike price".
>
> really works that well.
>
> One irritating thing I realised while reading Jeremy's mail is that
>
>   CAT "TapBranch" SHA256 DUP CAT SWAP CAT SHA256
>
> doesn't actually work -- the first CAT needs to sort the two branches
> first, and "LESSTHAN" etc want to compare values numerically rather
> than lexically. So maybe it would make more sense to introduce an opcode
> that builds a merkle root from tagged hashes directly, rather than one
> that lets you compare to 32B strings so that you can do the TapBranch
> logic manually.
>
> Cheers,
> aj
>
>