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

From: Antoine Riard <[email-masked]>
Date: Sat, 18 Sep 2021 10:11:10 -0400

> I think "<I> <P> MERKLESUB" is the same as "<P> OP_0 2 TLUV", provided
> <I> happens to be the same index as the current input. So it misses the
> ability to add branches (replacing OP_0 with a hash), the ability to
> preserve the current script (replacing 2 with 0), and the ability to
> remove some of the parent paths (replacing 2 with 4*n); but gains the
> ability to refer to non-corresponding outputs.

Yes, I agree.

> That... doesn't sound very straightforward to me; it's basically
> introducing a new covenant approach, that's getting fixed into a
> signature, rather than being a separate opcode.

I think one design advantage of combining scope-minimal opcodes like
MERKLESUB with sighash malleability is the ability to update a subset of
the off-chain contract transactions fields after the funding phase. With a
lower level of cooperation than required by the key path. I think not an
ability offered by templated covenants.

> I'm not really sure what you're saying there; is that any different to a
> pool of (A and B) where A suddenly wants to withdraw funds ASAP and can't
> wait for a key path signature? In that case A authorises the withdrawal
> and does whatever she wants with the funds (including form a new pool),
> and B remains in the pool.

Yes this is a different contract policy that I would like to set up.

Let's say you would like to express the following set of capabilities.

C0="Split the 4 BTC funds between Alice/Bob and Caroll/Dave"
C1="Alice can withdraw 1 BTC after 2 weeks"
C2="Bob can withdraw 1 BTC after 2 weeks"
C3="Caroll can withdraw 1 BTC after 2 weeks"
C4="Dave can withdraw 1 BTC after 2 weeks"
C5="If USDT price=X, Alice can withdraw 2 BTC or Caroll can withdraw 2 BTC"

If C4 is exercised, to avoid trust in the remaining counterparty, both
Alice or Caroll should be able to conserve the C5 option, without relying
on the updated key path.

As you're saying, as we know the group in advance, one way to setup the tree
could be:

       (A, (((((B, C), BC), D), BCD), ((((E, F), EF), G), EFG)))

where:
A="1 <alice> <caroll> 2 CHECKMULTISIG <usdt_oracle> CHECKSIG"
B="<alice> DUP 0 2 TLUV CHECKSIG"
C="<bob> DUP 0 2 TLUV CHECKSIG"
D="<alice+bob> 0 6 TLUV 1 <caroll> <dave> 2 CHECKMULTISIG"
E="<caroll> DUP 0 2 TLUV CHECKSIG"
F="<dave> DUP 0 2 TLUV CHECKSIG"
G="<caroll+dave> 0 6 TLUV 1 <alice> <bob> 2 CHECKMULTISIG"

E.g, if D is exercised, B+C+D are removed from the tree and A, E, F, G are
conserved in the Caroll/Dave fork. Then Caroll can exercise the USDT option
without trusting Dave.

Note, this solution isn't really satisfying as the G path isn't neutralized
on the Caroll/Dave fork and could be replayed by Alice or Bob... One
improvement could be to have the "withdraw" script path (C,D,F,G) expressed
redundantly. That way when a "split" script path is exercised the uncle
split path and all the siblings "withdraw" paths can be removed.

Echoing your point about the difficulty of reliably composing arbitrary
subsets of the pool, I lean to agree that merkle trees aren't the most
straightforward way to encode that kind of contract policy.

> If you're worried about the cost of a single byte of witness data you
> probably can't afford to do script path spends at all -- certainly
> having to do 64 bytes of witness data to add a signature that commits
> to an amount and the like will be infeasible in that case.

Yes, I agree fully templated covenants are more efficient to save witness
data.

I still like the idea of inserting a key as you might have an interesting
ability.
Like a N-of-M, a subset of the vault/pool able to update the withdraw
pubkey.

> That doesn't work. Suppose you start off with an even internal pubkey,
> with three scripts, (A, (B,C)). All of those scripts have tapscript
> version 0xc0 because the internal pubkey is even. You spend using A and
> calculate the new internal pubkey which turns out to be odd. You then
> need to change B and C's script version from 0xc0 to 0x20, but you can't
> do that (at least, you can't do it without revealing every script).

I'm not sure we're aligned on the mechanism.

We introduce a new tapscript version 0x20.

At spent taproot commitment verification, if the tapscript version=0x20,
the second-lowest bit of the first byte of the control block is interpreted
as the parity bit of the spent internal pubkey (i.e control[0] & 0x2).

This parity bit is used to compute a new format of TapTweakV2=H(p || m ||
bit) and commitment verification keep proceeding unmodified.

As the leaf version is committed as part of every TapLeaf, I think any
usage of MERKLESUB would require to use tapscript version 0x20 for the
whole set of leaves.

If you build a tree blurring 0xc0 leaves and TapTweakV2, I think those
leaves will be unspendable as they will always fail the commitment
verification.

> Changing the TapTweak calculation is a hard fork; existing software
> already verifies the calculation even if the script version is unknown.

Thinking more, you're right...

In case of TapTweakV2, non-upgraded nodes won't be able to pass the
validation of unknown script version (0x20), and the failure will provoke a
fork.

Could we commit the spent internal pubkey parity bit as a one-more-tweak
transparent to non-upgrades nodes ?

For upgraded, P = R + (t2 * G) and Q = P + (t1 * G)
For non-upgraded, Q = P + (t1 * G).

Could we add a new validation rule (e.g VerifyInternalPubkeyCommitment)
conditional on a newer tapscript version just before
VerifyTaprootCommitment ?

> That is, the strategy isn't "tweak the scripts by delaying them 3 months"
> it's "tweak the merkle tree, to replace the scripts that would be delayed
> with a new script that has a delay and then allows itself to be replaced
> by the original scripts that we now want back".

Yes, that's a good strategy to have logically equivalent subtree embedded
in the modifying tapscript.

If you have multiple modifying scripts and you can't predict the order, I
think the tree complexity will be quickly too high and grafroot-like
approaches are likely better

Le mer. 15 sept. 2021 à 02:51, Anthony Towns <[email-masked]> a écrit :

> On Sun, Sep 12, 2021 at 07:37:56PM -0400, Antoine Riard via bitcoin-dev
> wrote:
> > While MERKLESUB is still WIP, here the semantic. [...]
> > 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.
>
> I think "<I> <P> MERKLESUB" is the same as "<P> OP_0 2 TLUV", provided
> <I> happens to be the same index as the current input. So it misses the
> ability to add branches (replacing OP_0 with a hash), the ability to
> preserve the current script (replacing 2 with 0), and the ability to
> remove some of the parent paths (replacing 2 with 4*n); but gains the
> ability to refer to non-corresponding outputs.
>
> > > 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.
>
> That... doesn't sound very straightforward to me; it's basically
> introducing a new covenant approach, that's getting fixed into a
> signature, rather than being a separate opcode.
>
> I think a better approach for that would be to introduce the opcode (eg,
> PUSH_OUTPUT_SCRIPTPUBKEY, and SUBSTR to be able to analyse the segwit
> version), and make use of graftroot to allow a signature to declare that
> it's conditional on some extra script code. But it feels like it's going
> a bit off topic.
>
> > > 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 ?
>
> I'm not really sure what you're saying there; is that any different to a
> pool of (A and B) where A suddenly wants to withdraw funds ASAP and can't
> wait for a key path signature? In that case A authorises the withdrawal
> and does whatever she wants with the funds (including form a new pool),
> and B remains in the pool.
>
> I don't think you can reliably have some arbitrary subset of the pool
> able to withdraw atomically without using the key path -- if A,B,C,D have
> individual scripts allowing withdrawal, then there's no way of setting
> the tree up so that every pair of members can have their scripts cut
> off without also cutting off one or both of the other members withdrawal
> scripts.
>
> If you know in advance which groups want to stick together, you could
> set things up as:
>
>   (((A, B), AB), C)
>
> where:
>
>   A =   "A DUP H(B') 10 TLUV CHECKSIG"  -> (B', C)
>   B =   "B DUP H(A') 10 TLUV CHECKSIG"  -> (A', C)
>   A' =  "A DUP 0 2 TLUV CHECKSIG"   -> (C)
>   B' =  "B DUP 0 2 TLUV CHECKSIG"   -> (C)
>   AB =  "(A+B) DUP 6 TLUV CHECKSIG  -> (C)
>   C  =  "C DUP 0 2 TLUV CHECKSIG"   -> ((A,B), AB)
>
> (10 = 2+4*2 = drop my script, my sibling and my uncle; 6 = 2+4*1 =
> drop my script and my sibling; 2 = drop my script only)
>
> Which would let A and B exit together in a single tx rather than needing
> two
> transactions to exit separately.
>
> > > 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 you're worried about the cost of a single byte of witness data you
> probably can't afford to do script path spends at all -- certainly
> having to do 64 bytes of witness data to add a signature that commits
> to an amount and the like will be infeasible in that case.
>
> > > 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.
>
> That doesn't work. Suppose you start off with an even internal pubkey,
> with three scripts, (A, (B,C)). All of those scripts have tapscript
> version 0xc0 because the internal pubkey is even. You spend using A and
> calculate the new internal pubkey which turns out to be odd. You then
> need to change B and C's script version from 0xc0 to 0x20, but you can't
> do that (at least, you can't do it without revealing every script).
>
> > To ensure this parity bit is faithful and
> > won't break the updated key path, it's committed in the spent taptweak.
>
> Changing the TapTweak calculation is a hard fork; existing software
> already verifies the calculation even if the script version is unknown.
>
> > > 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 ?
>
> If you want your hotwallet to be able to withdraw up to $2000, that's
> around 4,000,000 sats, so you'd be doing up to 4M signatures there if you
> wanted to get the exact value you're trying to send, without having to
> either overpay, or first pay yourself then have another tx that splits
> your withdrawal into what you're spending and change that's no longer
> in your vault.
>
> > 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.
>
> I mean, maybe? It seems like a very heavy weight construct where a more
> general approach would probably be better (eg, graftroot to attach a
> script to a signature; or checkdatasig or whatever so you push a value
> to the stack then check it's signature, then reuse the authenticated
> data against other checks) so that you only have to supply a signature
> when you want to be able to approve things after the fact.
>
> > 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.
>
> Okay, so I think that means we've got the unconditional withdraw path
> "U" (your 1), the delay path "D" (your 2) and some normal path(s) "N"
> (your 3). I think you can get that behaviour with:
>
>    S1 = Merkle( U, (D, N) )
>    S2 = Merkle( U, W )
>    S3 = Merkle( N )
>
> that is, you start off with the funds in scriptPubKey S1, then spend
> using D to get to S2, then spend using W to get to S3, then presumably
> spend using N at some point.
>
> The script for W is just:
>
>    "IN_OUT_AMOUNT EQUALVERIFY 0 <N> 6 TLUV <3 months> CSV"
>        (drop the script, drop its sibling, add N, wait 3 months)
>
> The script for D is:
>
>    "IN_OUT_AMOUNT EQUALVERIFY 0 <W> 6 TLUV <sigcheck...>"
>        (drop the script, drop its sibling, add W, extra conditions
>         to avoid anyone being able to delay things)
>
> That is, the strategy isn't "tweak the scripts by delaying them 3 months"
> it's "tweak the merkle tree, to replace the scripts that would be delayed
> with a new script that has a delay and then allows itself to be replaced
> by the original scripts that we now want back".
>
> Cheers,
> aj
>
>