[bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns]

Hello world,

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.

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.

I'll split this into two emails, this one's the handwavy overview,
the followup will go into some of the implementation complexities.



The basic idea is to think about "updating" a utxo by changing the
taproot tree.

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=P+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.

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:

 * Updating the internal public key (ie from P to P' = 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)

Once you've done those things, you can then calculate the new merkle
root by resolving the updated merkle path (eg, S' = MerkleRootFor(AB,
F, H_TapLeaf(E))), and then calculate a new scriptPubKey based on that
and the updated internal public key (Q' = P' + H(P', S')).

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.

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.



Here's two examples of how you might use this functionality.

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.

To set this up with TLUV, you construct a taproot output with COLD as
the internal public key, and a script that specifies:

 * The tx is signed via HOT
 * <D> 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

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.

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:

 * 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)

The other script is either "locked" (which is just "OP_RETURN") or
"available" which specifies:

 * The tx is signed via HOT
 * <D> 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.

H_LOCKED and H_AVAILABLE are just the TapLeaf hash corresponding to the
"locked" and "available" scripts.

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.



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:

 * 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

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.

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.

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).

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.



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)



I think there's two limitations of this method that are worth pointing out.

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

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.



(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)

Cheers,
aj

[0] https://gist.github.com/ajtowns/dc9a59cf0a200bd1f9e6fb569f76f7a0

[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.

[2] Recently in covid-adjusted terms, or on the bitcoin consensus
    change scale anyway...
    https://mobile.twitter.com/ajtowns/status/1385091604357124100 

[3] https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#Constructing_and_spending_Taproot_outputs 

[4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017231.html

[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.

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns]

On Thu, Sep 09, 2021 at 04:41:38PM +1000, Anthony Towns wrote:
> I'll split this into two emails, this one's the handwavy overview,
> the followup will go into some of the implementation complexities.

(This is informed by discussions with Greg, Matt Corallo, David Harding
and Jeremy Rubin; opinions and mistakes my own, of course)



First, let's talk quickly about IN_OUT_AMOUNT. I think the easiest way to
deal with it is just a single opcode that pushes two values to the stack;
however it could be two opcodes, or it could even accept a parameter
letting you specify which input (and hence which corresponding output)
you're talking about (-1 meaning the current input perhaps). 

Anyway, a big complication here is that amounts in satoshis require up
to 51 bits to represent them, but script only allows you to do 32 bit
maths. However introducing IN_OUT_AMOUNT already means using an OP_SUCCESS
opcode, which in turn allows us to arbitrarily redefine the behaviour
of other opcodes -- so we can use the presence of IN_OUT_AMOUNT in the
script to upgrade ADD, SUB, and the comparison operators to support 64
bit values. Enabling MUL, DIV and MOD might also be worthwhile.



Moving onto TLUV. My theory is that it pops three items off the stack. The
top of the stack is "C" the control integer; next is "H" the
additional path step; and finally "X" the tweak for the internal
pubkey. If "H" is the empty vector, no additional path step is
added; otherwise it must be 32 bytes. If "X" is the empty vector,
the internal pubkey is not tweaked; otherwise it must be a 32 byte
x-only pubkey.

The low bit of C indicates the parity of X; if it's 0, X has even y,
if it's 1, X has odd y.

The next bit of C indicates whether the current script is dropped from
the merkle path, if it's 0, the current script is kept, if it's 1 the
current script is dropped.

The remaining bits of C (ie C >> 2) are the number of steps in the merkle
path that are dropped. (If C is negative, behaviour is to be determined
-- either always fail, or always succeed and left for definition via
future soft-fork)

For example, suppose we have a taproot utxo that had 5 scripts
(A,B,C,D,E), calculated as per the example in BIP 341 as:

    AB = H_TapBranch(A, B)
    CD = H_TapBranch(C, D)
    CDE = H_TapBranch(CD, E)
    ABCDE = H_TapBranch(AB, CDE)

And we're spending using script E, in that case the control block includes
the script E, and the merkle path to it, namely (AB, CD).

So here's some examples of what you could do with TLUV to control how
the spending scripts can change, between the input sPK and the output sPK.

At it's simplest, if we used the script "0 0 0 TLUV", then that says we
keep the current script, keep all steps in the merkle path, don't add
any new ones, and don't change the internal public key -- that is that
we want to resulting sPK to be exactly the same as the one we're spending.

If we used the script "0 F 0 TLUV" (H=F, C=0) then we keep the current
script, keep all the steps in the merkle path (AB and CD), and add
a new step to the merkle path (F), giving us:

    EF = H_TapBranch(E, F)
    CDEF =H_TapBranch(CD, EF)
    ABCDEF = H_TapBranch(AB, CDEF)

If we used the script "0 F 2 TLUV" (H=F, C=2) then we drop the current
script, but keep all the other steps, and add a new step (effectively
replacing the current script with a new one):

    CDF = H_TapBranch(CD, F)
    ABCDF = H_TapBranch(AB, CDF)

If we used the script "0 F 4 TLUV" (H=F, C=4) then we keep the current
script, but drop the last step in the merkle path, and add a new step
(effectively replacing the *sibling* of the current script):

    EF = H_TapBranch(E, F)
    ABEF = H_TapBranch(AB, EF)

If we used the script "0 0 4 TLUV" (H=empty, C=4) then we keep the current
script, drop the last step in the merkle path, and don't add anything new
(effectively dropping the sibling), giving just:

    ABE = H_TapBranch(AB, E)



Implementing the release/locked/available vault construct would then
look something like this:

Locked script = "OP_RETURN"
Available script = "<HOT> CHECKSIGVERIFY IN_OUT_AMOUNT SWAP <X> SUB DUP 0 GREATERTHAN IF GREATERTHANOREQUAL VERIFY 0 <H_LOCKED> 2 TLUV ELSE 2DROP ENDIF <D> CSV"
Release script = "<HOT> CHECKSIGVERIFY IF <H_LOCKED> ELSE <H_AVAILABLE> ENDIF 0 SWAP 4 TLUV  INPUTAMOUNT OUTPUTAMOUNT LESSTHANOREQUAL"
HOT = 32B hot wallet pubkey
X = maximum amount spendable via hot wallet at any time
D = compulsory delay between releasing funds and being able to spend them
H_LOCKED = H_TapLeaf(locked script)
H_AVAILABLE= H_TapLeaf(available script)
Internal public key = 32B cold wallet pubkey



Moving on to the pooled scheme and actually updating the internal pubkey
is, unfortunately, where things start to come apart. In particular,
since taproot uses 32-byte x-only pubkeys (with implicit even-y) for the
scriptPubKey and the internal public key, we have to worry about what
happens if, eg, A,B,C and A+B+C all have even-y, but (A+B)=(A+B+C)-C does
not have even-y. In that case allowing C to remove herself from the pool,
might result in switching from the scriptPubKey Qabc to the scriptPubKey
Qab as follows:

     Qabc = (A+B+C) + H(A+B+C, (Sa, (Sb, Sc)))*G
     Qab = -(A+B) + H( -(A+B), (Sa, Sb)*G

That's fine so far, but what happens if B then removes himself from the
pool? You take the internal public key, which turns out to be -(A+B)
since (A+B) did not have even y, and then subtract B, but that gives you
-A-2B instead of just A. So B obtains his funds, but B's signature hasn't
been cancelled out from the internal public key, so is still required
in order to do key path spends, which is definitely not what we want.

If we ignore that caveat (eg, having TLUV consider it to be an error if
you end up an internal public key that has odd-y) then the scripts for
exiting the pool are straightforward (if your balance is BAL and your
key is KEY):

    <KEY> DUP "" 1 TLUV
    CHECKSIGVERIFY 
    IN_OUT_AMOUNT SUB <BAL> GREATERTHANOREQUAL

It seems like "just ignore it" might be feasible for modest sized pools --
just choose A, B, C, D.. so that every combination of them (A+B+C, A+D,
etc) sums to a point that happens to have even-y and have each participant
in the pool verify that prior to using the pool. If I got my maths right,
you'll need to do about (2**n) trials to find a set of lucky points,
but each unlucky set will tend to fail quickly, leading to amortized
constant time for each test, so something like 3*(2**n) work overall. So
as long as n is no more than 20 or 30, that should be reasonably feasible.

To deal with it properly, you need to have the utxo commit to the parity
of the internal public key and have some way to find out that value when
using TLUV. There are probably three plausible ways of doing this.

The straightforward way is just to commit to it in the scriptPubKey --
that is, rather than taproot's approach of setting Q = P + H(P, S)*G where
P is a 32 byte x-only pubkey, also commit to the parity of P in the H(P,
S) step, and reveal the parity of the internal public key as part of the
control block when spending via the script path, in addition to revealing
the parity of the scriptPubKey point as we do already. Since taproot is
already locked in for activation, it's too late to change this behaviour
for taproot addresses, but we could include this in a future soft-fork
that enabled entroot or similar, or we could make this the behaviour of
(eg) 33B segwit v1 addresses that begin with 0x00, or similar.

If we don't commit to the parity in the scriptPubKey, there are two other
ways to commit to it in the utxo: either by having script ensure it is
committed to it in the value, or by extending the data that's saved in
the utxo database.

To commit to it in the value, you might do something like:

    <P> <H> IN_OUT_AMOUNT 2 MOD SWAP 2 MOD TUCK EQUAL 2 MUL ADD TLUV

and change TLUV's control parameter to be: C&1 = add/subtract the point,
C&2 = require the result to be even/odd y (with C&4 and C>>3 controlling
whether the current script and how many merkle paths are dropped). The
idea being to require that, if the utxo's value in satoshis is 0 mod
2, you subtract the point, and if it's 1 mod 2, you add the point,
and that the *output* amount's value in satoshis is different (mod 2)
from the input amount's value (mod 2), exactly when the resulting point
ends up with odd y.  Combined with a rule to ensure the output amount
doesn't decrease by more than your balance, this would effectively mean
that if half the time when you withdraw your balance you'll have to pay
a 1 satoshi fee to the remaining pool members so the the parity of the
remaining value is correct, which is inelegant, but seems like workable.

The other approach sits somewhere between those two, and would involve
adding a flag to each entry in the utxo database to say whether the
internal public key had been inverted. This would only be set if the
utxo had been created via a spending script that invoked TLUV, and TLUV
would use the flag to determine whether to add/subtract the provided
point. That seems quite complicated to implement to me, particularly if
you want to allow the flag to be able to be set by future opcodes that
we haven't thought of yet.



All of this so far assumed that the hashes for any new merkle steps are
fixed when the contract is created. If "OP_CAT" or similar were enabled,
however, you could construct those hashes programmatically in script,
which might lead to some interesting behaviour. For example, you could
construct a script that says "allow anyone to add themselves to the
buy-a-citadel pool, as long as they're contributing at least 10 BTC",
which would then verify they have control of the pubkey they're adding,
and allow them to add a script that lets them pull their 10 BTC back
out via that pubkey, and participate in key path spends in the same
way as everyone else. Of course, that sort of feature probably also
naturally extends to many of the "covenants considered harmful" cases,
eg a dollar-auction-like-contract: "Alice can spend this utxo after 1000
confirmations" or "anyone who increases the balance by 0.1 BTC can swap
Alice's pubkey for their own in the sibling script to this".

An interesting thing to note is that constructing the script can sometimes
be more efficient than hardcoding it, eg, I think

    "TapLeaf" SHA256 DUP CAT [0xc0016a] CAT SHA256

is correct for calculating the hash for the "OP_RETURN" script, and at
~17 bytes should be cheaper than the ~33 bytes it would take to hardcode
the hash.

To construct a new script programmatically you almost certainly need to
use templates, eg

    SIZE 32 EQUALVERIFY [0xc02220] SWAP CAT [0xac] CAT
    "TapLeaf" SHA256 DUP CAT SWAP CAT SHA256

might take a public key off the stack and turn it into the hash for a
script that expects a signature from that pubkey. I believe you could
construct multiple scripts and combine them via

    CAT "TapBranch" SHA256 DUP CAT SWAP CAT SHA256

or similar as well.

There's a serious caveat with doing that in practice though: if you allow
people to add in arbitrary opcodes when constructing the new script,
they could choose to have that opcode be one of the "OP_SUCCESS" opcodes,
and, if they're a miner, use that to bypass the covenant constraints
entirely. So if you want to think about this, the template being filled
in probably has to be very strict, eg including the specific PUSH opcode
for the data being provided in the witness, and checking that the length
of the witness data exactly matches the PUSH opcode being used.

Cheers,
aj

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Matt Corallo]

Thanks for taking the time to write this up!

To wax somewhat broadly here, I’m very excited about this as a direction for bitcoin covenants. Other concrete proposals seem significantly more limited, which worries me greatly. Further, this feels very “taproot-native” in a way that encourages utilizing taproot’s features fully while building covenants, saving fees on chain and at least partially improving privacy.

I’ve been saying we need more covenants research and proposals before we move forward with one and this is a huge step in that direction, IMO. With Taproot activating soon, I’m excited for what coming forks bring.

Matt

> On Sep 8, 2021, at 23:42, Anthony Towns via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> Hello world,
> 
> 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.
> 
> 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.
> 
> I'll split this into two emails, this one's the handwavy overview,
> the followup will go into some of the implementation complexities.
> 
> 
> 
> The basic idea is to think about "updating" a utxo by changing the
> taproot tree.
> 
> 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=P+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.
> 
> 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:
> 
> * Updating the internal public key (ie from P to P' = 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)
> 
> Once you've done those things, you can then calculate the new merkle
> root by resolving the updated merkle path (eg, S' = MerkleRootFor(AB,
> F, H_TapLeaf(E))), and then calculate a new scriptPubKey based on that
> and the updated internal public key (Q' = P' + H(P', S')).
> 
> 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.
> 
> 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.
> 
> 
> 
> Here's two examples of how you might use this functionality.
> 
> 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.
> 
> To set this up with TLUV, you construct a taproot output with COLD as
> the internal public key, and a script that specifies:
> 
> * The tx is signed via HOT
> * <D> 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
> 
> 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.
> 
> 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:
> 
> * 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)
> 
> The other script is either "locked" (which is just "OP_RETURN") or
> "available" which specifies:
> 
> * The tx is signed via HOT
> * <D> 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.
> 
> H_LOCKED and H_AVAILABLE are just the TapLeaf hash corresponding to the
> "locked" and "available" scripts.
> 
> 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.
> 
> 
> 
> 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:
> 
> * 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
> 
> 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.
> 
> 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.
> 
> 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).
> 
> 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.
> 
> 
> 
> 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)
> 
> 
> 
> I think there's two limitations of this method that are worth pointing out.
> 
> 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
> 
> 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.
> 
> 
> 
> (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)
> 
> Cheers,
> aj
> 
> [0] https://gist.github.com/ajtowns/dc9a59cf0a200bd1f9e6fb569f76f7a0
> 
> [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.
> 
> [2] Recently in covid-adjusted terms, or on the bitcoin consensus
>    change scale anyway...
>    https://mobile.twitter.com/ajtowns/status/1385091604357124100 
> 
> [3] https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#Constructing_and_spending_Taproot_outputs 
> 
> [4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017231.html
> 
> [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.
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[darosior]

Hi Anthony,


This post is a follow-up to your insight on Twitter [0], sent here for better
posterity, accessibility and readability than Twitter. And also to motivate this
idea by giving another concrete [1] usecase for it.

Revault [2] is a multi-party "vault" protocol. It involves 2 sets of participants
that may or may not intersect (although i expect the second one to often be a subset
of the first one). The stakeholders, analogous to the "cold keys", receive coins on
a (large) N-of-N multisig and presign an Unvault transaction which creates an Unvault
output which pays to either the (small) K-of-M multisig of the managers after a timelock
or to the N-of-N immediately (allowing for a Cancel transaction).

This allows for partial delegation of the funds, and some automated policies (can't
broadcast the Unvault outside business hours, can't unvault more than <limit> BTC a
week, etc..) that can be enforced by watchtowers. That's nice, but it would be even
nicer if we could have policies on the Spend transaction (the one created by the
managers to spend the Unvault output) itself to further restrict how the coin can move [3].

But in order to do so, you'd need the managers to disclaim the Spend transaction they
are going to use before broadcasting the Unvault and somehow commit to it at unvaulting
time. Apart from stupid hacks [4] i could not find a reasonable covenant design as a
solution to this issue.
It think TLUV fixes this.

The idea (your idea, actually) is to receive coins not to a N-of-N anymore but to a
Taproot with a branch which contains the manager multisig + a TLUV which would replace
the current branch being executed by a CSV + CTV which input hash value will be taken
from the witness stack at Unvault broadcast. Therefore chosen by the managers at spending
time, and available for the entire duration of the timelock.

So, the scripts would be something like (assuming CAT, CTV, TLUV):
V = max acceptable fees
D = "CTV <X> CSV DROP 1"
C = "<32 bytes> D"
B = "
<pk man 1> CHECKSIG <pk man 2> CHECKSIGADD ... <pk man M> CHECKSIGADD <K> EQUALVERIFY
IN_OUT_AMOUNT SUB <V> LESSTHANOREQUAL DUP VERIFY
SIZE 32 EQUALVERIFY <0xc0 | len(D) + 32 + 1 | 0x20> SWAP CAT "Tapleaf" SHA256 DUP CAT SWAP CAT SHA256 0 SWAP 2 TLUV
"
A = "<pk stk 1> CHECKSIGVERIFY <pk stk 2> CHECKSIGVERIFY ... <pk stk N> CHECKSIG"

The deposit output ScriptPubKey would be Taproot(A, B) [5].
The unvault output ScriptPubKey would be Taproot(A, C).
This also allows for a lot more flexibility (batching at the Unvault level [7], use RBF
instead of more wasteful CPFP, etc..) and creates a number of problems [6] on which
i won't expand on. But it does the most important part: it enables it.

Looking forward to more feedback on your proposal!


Thanks,
Antoine



[0] https://twitter.com/ajtowns/status/1435884659146059776?s=20
[1] we've proposed Revault a year and a half ago, have been building it since. We
    should have a first version released soon (tm).
[2] https://github.com/revault
[3] technically we do optionally offer this at the moment, but at the expense of a
    reduction of security and a pretty ugly hack: by using "anti-replay" oracles
    (cosigning servers that are only going to sign only once for a given prevout)
[4] the last bad idea to date is "have ANYPREVOUT, presign the Unvault with
    SIGHASH_SINGLE, enforce that the Unvault output is only spent with a transaction
    spending <same txid>:1 and have managers append an output to the Unvault enforcing
    a covenant just before broadcast"
[5] as a branch because i don't know how to use the keypath spend for a multisig with
    cold keys (yet).
[6] as such you'd need a sig for canceling but not for unvaulting, so it reverses the
    security model from "can't do anything til everyone signed" to "can steal until
    everyone has signed" so you'd need a TLUV for the cancel spending path as well, but
    then how to make this covenant non-replayable, flexible enough to feebump but not
    enough be vulnerable to pining, etc..
[7] Note that this means all Cancel must be confirmed to recover the funds but a single
    one needs to in order to prevent a spending.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐

Le jeudi 9 septembre 2021 à 8:53 AM, Anthony Towns via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> a écrit :

> On Thu, Sep 09, 2021 at 04:41:38PM +1000, Anthony Towns wrote:
>
> > I'll split this into two emails, this one's the handwavy overview,
> >
> > the followup will go into some of the implementation complexities.
>
> (This is informed by discussions with Greg, Matt Corallo, David Harding
>
> and Jeremy Rubin; opinions and mistakes my own, of course)
>
> First, let's talk quickly about IN_OUT_AMOUNT. I think the easiest way to
>
> deal with it is just a single opcode that pushes two values to the stack;
>
> however it could be two opcodes, or it could even accept a parameter
>
> letting you specify which input (and hence which corresponding output)
>
> you're talking about (-1 meaning the current input perhaps).
>
> Anyway, a big complication here is that amounts in satoshis require up
>
> to 51 bits to represent them, but script only allows you to do 32 bit
>
> maths. However introducing IN_OUT_AMOUNT already means using an OP_SUCCESS
>
> opcode, which in turn allows us to arbitrarily redefine the behaviour
>
> of other opcodes -- so we can use the presence of IN_OUT_AMOUNT in the
>
> script to upgrade ADD, SUB, and the comparison operators to support 64
>
> bit values. Enabling MUL, DIV and MOD might also be worthwhile.
>
> Moving onto TLUV. My theory is that it pops three items off the stack. The
>
> top of the stack is "C" the control integer; next is "H" the
>
> additional path step; and finally "X" the tweak for the internal
>
> pubkey. If "H" is the empty vector, no additional path step is
>
> added; otherwise it must be 32 bytes. If "X" is the empty vector,
>
> the internal pubkey is not tweaked; otherwise it must be a 32 byte
>
> x-only pubkey.
>
> The low bit of C indicates the parity of X; if it's 0, X has even y,
>
> if it's 1, X has odd y.
>
> The next bit of C indicates whether the current script is dropped from
>
> the merkle path, if it's 0, the current script is kept, if it's 1 the
>
> current script is dropped.
>
> The remaining bits of C (ie C >> 2) are the number of steps in the merkle
>
> path that are dropped. (If C is negative, behaviour is to be determined
>
> -- either always fail, or always succeed and left for definition via
>
> future soft-fork)
>
> For example, suppose we have a taproot utxo that had 5 scripts
>
> (A,B,C,D,E), calculated as per the example in BIP 341 as:
>
> AB = H_TapBranch(A, B)
>
> CD = H_TapBranch(C, D)
>
> CDE = H_TapBranch(CD, E)
>
> ABCDE = H_TapBranch(AB, CDE)
>
> And we're spending using script E, in that case the control block includes
>
> the script E, and the merkle path to it, namely (AB, CD).
>
> So here's some examples of what you could do with TLUV to control how
>
> the spending scripts can change, between the input sPK and the output sPK.
>
> At it's simplest, if we used the script "0 0 0 TLUV", then that says we
>
> keep the current script, keep all steps in the merkle path, don't add
>
> any new ones, and don't change the internal public key -- that is that
>
> we want to resulting sPK to be exactly the same as the one we're spending.
>
> If we used the script "0 F 0 TLUV" (H=F, C=0) then we keep the current
>
> script, keep all the steps in the merkle path (AB and CD), and add
>
> a new step to the merkle path (F), giving us:
>
> EF = H_TapBranch(E, F)
>
> CDEF =H_TapBranch(CD, EF)
>
> ABCDEF = H_TapBranch(AB, CDEF)
>
> If we used the script "0 F 2 TLUV" (H=F, C=2) then we drop the current
>
> script, but keep all the other steps, and add a new step (effectively
>
> replacing the current script with a new one):
>
> CDF = H_TapBranch(CD, F)
>
> ABCDF = H_TapBranch(AB, CDF)
>
> If we used the script "0 F 4 TLUV" (H=F, C=4) then we keep the current
>
> script, but drop the last step in the merkle path, and add a new step
>
> (effectively replacing the sibling of the current script):
>
> EF = H_TapBranch(E, F)
>
> ABEF = H_TapBranch(AB, EF)
>
> If we used the script "0 0 4 TLUV" (H=empty, C=4) then we keep the current
>
> script, drop the last step in the merkle path, and don't add anything new
>
> (effectively dropping the sibling), giving just:
>
> ABE = H_TapBranch(AB, E)
>
> Implementing the release/locked/available vault construct would then
>
> look something like this:
>
> Locked script = "OP_RETURN"
>
> Available script = "<HOT> CHECKSIGVERIFY IN_OUT_AMOUNT SWAP <X> SUB DUP 0 GREATERTHAN IF GREATERTHANOREQUAL VERIFY 0 <H_LOCKED> 2 TLUV ELSE 2DROP ENDIF <D> CSV"
>
> Release script = "<HOT> CHECKSIGVERIFY IF <H_LOCKED> ELSE <H_AVAILABLE> ENDIF 0 SWAP 4 TLUV INPUTAMOUNT OUTPUTAMOUNT LESSTHANOREQUAL"
>
> HOT = 32B hot wallet pubkey
>
> X = maximum amount spendable via hot wallet at any time
>
> D = compulsory delay between releasing funds and being able to spend them
>
> H_LOCKED = H_TapLeaf(locked script)
>
> H_AVAILABLE= H_TapLeaf(available script)
>
> Internal public key = 32B cold wallet pubkey
>
> Moving on to the pooled scheme and actually updating the internal pubkey
>
> is, unfortunately, where things start to come apart. In particular,
>
> since taproot uses 32-byte x-only pubkeys (with implicit even-y) for the
>
> scriptPubKey and the internal public key, we have to worry about what
>
> happens if, eg, A,B,C and A+B+C all have even-y, but (A+B)=(A+B+C)-C does
>
> not have even-y. In that case allowing C to remove herself from the pool,
>
> might result in switching from the scriptPubKey Qabc to the scriptPubKey
>
> Qab as follows:
>
> Qabc = (A+B+C) + H(A+B+C, (Sa, (Sb, Sc)))*G
>
> Qab = -(A+B) + H( -(A+B), (Sa, Sb)*G
>
> That's fine so far, but what happens if B then removes himself from the
>
> pool? You take the internal public key, which turns out to be -(A+B)
>
> since (A+B) did not have even y, and then subtract B, but that gives you
>
> -A-2B instead of just A. So B obtains his funds, but B's signature hasn't
>
> been cancelled out from the internal public key, so is still required
>
> in order to do key path spends, which is definitely not what we want.
>
> If we ignore that caveat (eg, having TLUV consider it to be an error if
>
> you end up an internal public key that has odd-y) then the scripts for
>
> exiting the pool are straightforward (if your balance is BAL and your
>
> key is KEY):
>
> <KEY> DUP "" 1 TLUV
>
>     CHECKSIGVERIFY
>     IN_OUT_AMOUNT SUB <BAL> GREATERTHANOREQUAL
>
>
> It seems like "just ignore it" might be feasible for modest sized pools --
>
> just choose A, B, C, D.. so that every combination of them (A+B+C, A+D,
>
> etc) sums to a point that happens to have even-y and have each participant
>
> in the pool verify that prior to using the pool. If I got my maths right,
>
> you'll need to do about (2n) trials to find a set of lucky points,
>
> but each unlucky set will tend to fail quickly, leading to amortized
>
> constant time for each test, so something like 3*(2n) work overall. So
>
> as long as n is no more than 20 or 30, that should be reasonably feasible.
>
> To deal with it properly, you need to have the utxo commit to the parity
>
> of the internal public key and have some way to find out that value when
>
> using TLUV. There are probably three plausible ways of doing this.
>
> The straightforward way is just to commit to it in the scriptPubKey --
>
> that is, rather than taproot's approach of setting Q = P + H(P, S)*G where
>
> P is a 32 byte x-only pubkey, also commit to the parity of P in the H(P,
>
> S) step, and reveal the parity of the internal public key as part of the
>
> control block when spending via the script path, in addition to revealing
>
> the parity of the scriptPubKey point as we do already. Since taproot is
>
> already locked in for activation, it's too late to change this behaviour
>
> for taproot addresses, but we could include this in a future soft-fork
>
> that enabled entroot or similar, or we could make this the behaviour of
>
> (eg) 33B segwit v1 addresses that begin with 0x00, or similar.
>
> If we don't commit to the parity in the scriptPubKey, there are two other
>
> ways to commit to it in the utxo: either by having script ensure it is
>
> committed to it in the value, or by extending the data that's saved in
>
> the utxo database.
>
> To commit to it in the value, you might do something like:
>
> <P> <H> IN_OUT_AMOUNT 2 MOD SWAP 2 MOD TUCK EQUAL 2 MUL ADD TLUV
>
> and change TLUV's control parameter to be: C&1 = add/subtract the point,
>
> C&2 = require the result to be even/odd y (with C&4 and C>>3 controlling
>
> whether the current script and how many merkle paths are dropped). The
>
> idea being to require that, if the utxo's value in satoshis is 0 mod
>
> 2, you subtract the point, and if it's 1 mod 2, you add the point,
>
> and that the output amount's value in satoshis is different (mod 2)
>
> from the input amount's value (mod 2), exactly when the resulting point
>
> ends up with odd y. Combined with a rule to ensure the output amount
>
> doesn't decrease by more than your balance, this would effectively mean
>
> that if half the time when you withdraw your balance you'll have to pay
>
> a 1 satoshi fee to the remaining pool members so the the parity of the
>
> remaining value is correct, which is inelegant, but seems like workable.
>
> The other approach sits somewhere between those two, and would involve
>
> adding a flag to each entry in the utxo database to say whether the
>
> internal public key had been inverted. This would only be set if the
>
> utxo had been created via a spending script that invoked TLUV, and TLUV
>
> would use the flag to determine whether to add/subtract the provided
>
> point. That seems quite complicated to implement to me, particularly if
>
> you want to allow the flag to be able to be set by future opcodes that
>
> we haven't thought of yet.
>
> All of this so far assumed that the hashes for any new merkle steps are
>
> fixed when the contract is created. If "OP_CAT" or similar were enabled,
>
> however, you could construct those hashes programmatically in script,
>
> which might lead to some interesting behaviour. For example, you could
>
> construct a script that says "allow anyone to add themselves to the
>
> buy-a-citadel pool, as long as they're contributing at least 10 BTC",
>
> which would then verify they have control of the pubkey they're adding,
>
> and allow them to add a script that lets them pull their 10 BTC back
>
> out via that pubkey, and participate in key path spends in the same
>
> way as everyone else. Of course, that sort of feature probably also
>
> naturally extends to many of the "covenants considered harmful" cases,
>
> eg a dollar-auction-like-contract: "Alice can spend this utxo after 1000
>
> confirmations" or "anyone who increases the balance by 0.1 BTC can swap
>
> Alice's pubkey for their own in the sibling script to this".
>
> An interesting thing to note is that constructing the script can sometimes
>
> be more efficient than hardcoding it, eg, I think
>
> "TapLeaf" SHA256 DUP CAT [0xc0016a] CAT SHA256
>
> is correct for calculating the hash for the "OP_RETURN" script, and at
>
> ~17 bytes should be cheaper than the ~33 bytes it would take to hardcode
>
> the hash.
>
> To construct a new script programmatically you almost certainly need to
>
> use templates, eg
>
> SIZE 32 EQUALVERIFY [0xc02220] SWAP CAT [0xac] CAT
>
> "TapLeaf" SHA256 DUP CAT SWAP CAT SHA256
>
> might take a public key off the stack and turn it into the hash for a
>
> script that expects a signature from that pubkey. I believe you could
>
> construct multiple scripts and combine them via
>
> CAT "TapBranch" SHA256 DUP CAT SWAP CAT SHA256
>
> or similar as well.
>
> There's a serious caveat with doing that in practice though: if you allow
>
> people to add in arbitrary opcodes when constructing the new script,
>
> they could choose to have that opcode be one of the "OP_SUCCESS" opcodes,
>
> and, if they're a miner, use that to bypass the covenant constraints
>
> entirely. So if you want to think about this, the template being filled
>
> in probably has to be very strict, eg including the specific PUSH opcode
>
> for the data being provided in the witness, and checking that the length
>
> of the witness data exactly matches the PUSH opcode being used.
>
> Cheers,
>
> aj
>
> bitcoin-dev mailing list
>
> bitcoin-dev@lists.linuxfoundation.org
>
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 5671 bytes --]

I like this proposal, I think it has interesting use cases! I'm quick to
charitably Matt's comment, "I’ve been saying we need more covenants
research and proposals before we move forward with one", as before we move
forward with *any.* I don't think that these efforts are rival -- different
opcodes for different nodes as they say.

I've previously done some analysis comparing Coin / Payment Pools with CTV
to TapLeafUpdate which make CTV out favorably in terms of chain load and
privacy.

On the "anyone can withdraw themselves in O(1) transactions" front, is that
if you contrast a CTV-style tree, the withdraws are O(log(n)) but E[O(1)]
for all participants, e.g. summing over the entire tree as it splits to
evict a bad actor ends up being O(N) total work over N participants, so you
do have to look at the exact transactions that come out w.r.t. script size
to determine which Payment Pool has overall less chain work to trustlessly
withdraw. This is compounded by the fact that a Taproot for N participants
uses a O(log N) witness.


Let's do out that basic math. First, let's assume we have 30 participants.
The basic script for each node would be:

TLUV: Taproot(Tweaked Key, {<KEY> DUP "" 1 TLUV
    CHECKSIGVERIFY
    IN_OUT_AMOUNT SUB <BAL> GREATERTHANOREQUAL, ...})

Under this, the first withdraw for TLUV would require in witnesses stack:
Assume average amount is 0.005BTC, so we have 4.2 B users = 18.9 bits =3
bytes

1 signature (1+64 bytes) + (1 Script = (+ 1 1 32 1 1 1 1 1 1 1 3 1 1) = 46
bytes) + (1 taproot path = 2 + 33 + log2(N)*32)
= 146+log2(N)*32.

now, because we delete the key, we need to sum this from N=0 to N=30:

>>> sum([65+46+35+math.log(N,2)*32 for N in range(1, 31)])
7826.690154943152 bytes of witness data

Each transaction should have 1 input (40 bytes), 2 outputs (2* (34+8) =
84), 4 bytes locktime, 4 bytes version, 2 byte witness flag, 1 byte in
counter 1 byte out counter  = 136 bytes (we already count witnesses above)


136 * 30 + 7827 = 11907 bytes to withdraw all trustlessly

Now for CTV:
-CTV: Taproot(MuSigKey(subparties), <H splits pool with radix 4> CTV)

*sidebar: **why radix 4? A while ago, I did the math out and a radix of 4
or 5 was optimal for bare script... assuming this result holds with
taproot.*


balance holders: 0..30
you have a base set of transactions paying out: 0..4 4..8 8..12 12..16
16..20 20..24 24..27 27..30
interior nodes covering: 0..16 16..30
root node covering: 0..30

The witness for each of these looks like:

(Taproot Script = 1+1+32+1) + (Taproot Control = 33) = 68 bytes

A transaction with two outputs should have 1 input (40 bytes), 2 outputs
(2* (34+8) = 84), 4 bytes locktime, 4 bytes version, 2 byte witness flag, 1
byte in counter 1 byte out counter  = 136 bytes + 68 bytes witness = 204
A transaction with three outputs should have 1 input (40 bytes), 3 outputs
(3* (34+8) = 126), 4 bytes locktime, 4 bytes version, 2 byte witness flag,
1 byte in counter 1 byte out counter  = 178 bytes + 68 bytes witness = 246
A transaction with 4 outputs should have 1 input (40 bytes), 4 outputs (4*
(34+8) = 126), 4 bytes locktime, 4 bytes version, 2 byte witness flag, 1
byte in counter 1 byte out counter  = 220 bytes + 68 bytes witness = 288

204 + 288*6 + 246*2 = 2424 bytes

Therefore the CTV style pool is, in this example, about 5x more efficient
in block space utilization as compared to TLUV at trustlessly withdrawing
all participants. This extra space leaves lots of headroom to e.g.
including things like OP_TRUE anchor outputs (12*10) = 120 bytes total for
CPFP; an optional script path with 2 inputs for a gas-paying input (cost is
around 32 bytes for taproot?). The design also scales beyond 30
participants, where the advantage grows further (iirc, sum i = 0 to n log i
is relatively close to n log n).

In the single withdrawal case, the cost to eject a single participant with
CTV is 204+288 = 492 bytes, compared to 65+46+35+math.log(30,2)*32+136 =
439 bytes. The cost to eject a second participant in CTV is much smaller as
it amortizes -- worst case is 288, best case is 0 (already expanded),
whereas in TLUV there is limited amortization so it would be about 438
bytes.

The protocols are identical in the cooperative case.

In terms of privacy, the CTV version is a little bit worse. At every
splitting, radix of the root nodes total value gets broadcast. So to eject
a participant, you end up leaking a bit more information. However, it might
be a reasonable assumption that if one of your counterparties is
uncooperative, they might dox you anyways. CTV trees are also superior
during updates for privacy in the cooperative case. With the TLUV pool, you
must know all tapleafs and the corresponding balances. Whereas in CTV
trees, you only need to know the balances of the nodes above you. E.g., we
can update the balances

from: [[1 Alice, 2 Bob], [3 Carol, 4 Dave]]
to: [[2.5 Alice, 0.5 Bob], [3 Carol, 4 Dave]]

without informing Carol or Dave about the updates in our subtree, just that
our slice of participants signed off on it. So even in the 1 party
uncooperative case, 3/4 the pool has update privacy against them, and the
subtrees that share a branch with the uncooperative also have this privacy
recursively to an extent.

CTV's TXID stability also lets you embed payment channels a bit easier, but
perhaps TLUV would be in an ANYPREVOUT universe w.r.t. channel protocols so
that might matter less across the designs. Nevertheless, I think it's
exciting to think about these payment pools where every node is an
updatable channel.

[-- Attachment #2: Type: text/html, Size: 12827 bytes --]

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 3867 bytes --]

I'm a bit skeptical of the safety of the control byte. Have you considered
the following issues?



> The low bit of C indicates the parity of X; if it's 0, X has even y,
> if it's 1, X has odd y.
>
> The next bit of C indicates whether the current script is dropped from
> the merkle path, if it's 0, the current script is kept, if it's 1 the
> current script is dropped.
>
> The remaining bits of C (ie C >> 2) are the number of steps in the merkle
> path that are dropped. (If C is negative, behaviour is to be determined
> -- either always fail, or always succeed and left for definition via
> future soft-fork)
>
> For example, suppose we have a taproot utxo that had 5 scripts
> (A,B,C,D,E), calculated as per the example in BIP 341 as:
>
>     AB = H_TapBranch(A, B)
>     CD = H_TapBranch(C, D)
>     CDE = H_TapBranch(CD, E)
>     ABCDE = H_TapBranch(AB, CDE)
>
> And we're spending using script E, in that case the control block includes
> the script E, and the merkle path to it, namely (AB, CD).
>
> So here's some examples of what you could do with TLUV to control how
> the spending scripts can change, between the input sPK and the output sPK.
>
> At it's simplest, if we used the script "0 0 0 TLUV", then that says we
> keep the current script, keep all steps in the merkle path, don't add
> any new ones, and don't change the internal public key -- that is that
> we want to resulting sPK to be exactly the same as the one we're spending.
>
> If we used the script "0 F 0 TLUV" (H=F, C=0) then we keep the current
> script, keep all the steps in the merkle path (AB and CD), and add
> a new step to the merkle path (F), giving us:
>
>     EF = H_TapBranch(E, F)
>     CDEF =H_TapBranch(CD, EF)
>     ABCDEF = H_TapBranch(AB, CDEF)
>
> If we used the script "0 F 2 TLUV" (H=F, C=2) then we drop the current
> script, but keep all the other steps, and add a new step (effectively
> replacing the current script with a new one):
>
>     CDF = H_TapBranch(CD, F)
>     ABCDF = H_TapBranch(AB, CDF)
>

If we recursively apply this rule, would it not be possible to repeatedly
apply it and end up burning out path E beyond the 128 Taproot depth limit?

Suppose we protect against this by checking that after adding F the depth
is not more than 128 for E.

The E path that adds F could also be burned for future use once the depth
is hit, and if adding F is necessary for correctness, then we're burned
anyways.

I don't see a way to protect against this generically.

Perhaps it's OK: E can always approve burning E?




>
> If we used the script "0 F 4 TLUV" (H=F, C=4) then we keep the current
> script, but drop the last step in the merkle path, and add a new step
> (effectively replacing the *sibling* of the current script):
>
>     EF = H_TapBranch(E, F)
>     ABEF = H_TapBranch(AB, EF)


> If we used the script "0 0 4 TLUV" (H=empty, C=4) then we keep the current
> script, drop the last step in the merkle path, and don't add anything new
> (effectively dropping the sibling), giving just:
>
>     ABE = H_TapBranch(AB, E)
>
>
>
Is C = 4 stable across all state transitions? I may be missing something,
but it seems that the location of C would not be stable across transitions.


E.g., What happens when, C and E are similar scripts and C adds some
clauses F1, F2, F3, then what does this sibling replacement do? Should a
sibling not be able to specify (e.g., by leaf version?) a NOREPLACE flag
that prevents siblings from modifying it?

What happens when E adds a bunch of F's F1 F2 F3, is C still in the same
position as when E was created?

Especially since nodes are lexicographically sorted, it seems hard to
create stable path descriptors even if you index from the root downwards.

Identifying nodes by Hash is also not acceptable because of hash cycles,
unless you want to restrict the tree structure accordingly (maybe OK
tradeoff?).

[-- Attachment #2: Type: text/html, Size: 7181 bytes --]

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 30047 bytes --]

Hi AJ,

Thanks for finally putting the pieces together! [0]

We've been hacking with Gleb on a paper for the CoinPool protocol [1]
during the last weeks and it should be public soon, hopefully highlighting
what kind of scheme, TAPLEAF_UPDATE_VERIFY-style of covenant enable :)

Here few early feedbacks on this specific proposal,

> 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:
>
>  * Updating the internal public key (ie from P to P' = 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)

"Talk is cheap. Show me the code" :p

    case OP_MERKLESUB:
    {
        if (!(flags & SCRIPT_VERIFY_MERKLESUB)) {
            break;
        }

        if (stack.size() < 2) {
            return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
        }

        valtype& vchPubKey = stacktop(-1);

        if (vchPubKey.size() != 32) {
            break;
        }

        const std::vector<unsigned char>& vch = stacktop(-2);
        int nOutputPos = CScriptNum(stacktop(-2), fRequireMinimal).getint();

        if (nOutputPos < 0) {
            return set_error(serror, SCRIPT_ERR_NEGATIVE_MERKLEVOUT);
        }

        if (!checker.CheckMerkleUpdate(*execdata.m_control, nOutputPos,
vchPubKey)) {
            return set_error(serror, SCRIPT_ERR_UNSATISFIED_MERKLESUB);
        }
        break;
    }

    case OP_NOP1: case OP_NOP5:



    template <class T>
    bool GenericTransactionSignatureChecker<T>::CheckMerkleUpdate(const
std::vector<unsigned char>& control, unsigned int out_pos, const
std::vector<unsigned char>& point) const
    {
        //! The internal pubkey (x-only, so no Y coordinate parity).
        XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() +
1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))};
        //! Update the internal key by subtracting the point.
        XOnlyPubKey s{uint256(point)};
        XOnlyPubKey u;
        try {
            u = p.UpdateInternalKey(s).value();
        } catch (const std::bad_optional_access& e) {
            return false;
        }

        //! The first control node is made the new tapleaf hash.
        //! TODO: what if there is no control node ?
        uint256 updated_tapleaf_hash;
        updated_tapleaf_hash = uint256(std::vector<unsigned
char>(control.data() + TAPROOT_CONTROL_BASE_SIZE, control.data() +
TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE));

        //! The committed-to output must be in the spent transaction vout
range.
        if (out_pos >= txTo->vout.size()) return false;
        int witnessversion;
        std::vector<unsigned char> witnessprogram;
        txTo->vout[out_pos].scriptPubKey.IsWitnessProgram(witnessversion,
witnessprogram);
        //! The committed to output must be a witness v1 program at least
        if (witnessversion == 0) {
            return false;
        } else if (witnessversion == 1) {
            //! The committed-to output.
            const XOnlyPubKey q{uint256(witnessprogram)};
            //! Compute the Merkle root from the leaf and the incremented
by one path.
            const uint256 merkle_root = ComputeTaprootMerkleRoot(control,
updated_tapleaf_hash, 1);
            //! TODO modify MERKLESUB design
            bool parity_ret = q.CheckTapTweak(u, merkle_root, true);
            bool no_parity_ret = q.CheckTapTweak(u, merkle_root, false);
            if (!parity_ret && !no_parity_ret) {
                return false;
            }
        }
        return true;
    }


Here the main chunks for an "<n> <point> OP_MERKLESUB" opcode, with `n` the
output position which is checked for update and `point` the x-only pubkey
which must be subtracted from the internal key.

I think one design advantage of explicitly passing the output position as a
stack element is giving more flexibility to your contract dev. The first
output could be SIGHASH_ALL locked-down. e.g "you have to pay Alice on
output 1 while pursuing the contract semantic on output 2".

One could also imagine a list of output positions to force the taproot
update on multiple outputs ("OP_MULTIMERKLESUB"). Taking back your citadel
joint venture example, partners could decide to split the funds in 3
equivalent amounts *while* conserving the pre-negotiated script policies [2]

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 ?

We can also explore more fancy opcodes where the updated merkle branch is
pushed on the stack for deep manipulations. Or even n-dimensions
inspections if combined with your G'root [3] ?

Note, this current OP_MERKLESUB proposal doesn't deal with committing the
parity of the internal pubkey as part of the spent utxo. As you highlighted
well in your other mail, if we want to conserve the updated key-path across
a sequence of TLUV-covenanted transactions, we need either
a) to select a set of initial points, where whatever combination of
add/sub, it yields an even-y point. Or b) have the even/odd bit
re-committed at each update. Otherwise, we're not guaranteed to cancel the
point from the aggregated key.

This property is important for CoinPool. Let's say you have A+B+C+D, after
the D withdraw transaction has been confirmed on-chain, you want A+B+C to
retain the ability to use the key-path and update the off-chain state,
without forcing a script path spend to a new setup.

If we put the updated internal key parity bit in the first control byte, we
need to have a  redundant commitment somewhere else as we can't trust the
spender to not be willingly to break the key-path spend of the remaining
group of signers.

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 ?

> 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.

    if ((output_type & SIGHASH_GROUP) == SIGHASH_GROUP) {
        // Verify the output group bounds
        if (execdata.m_bundle->first == execdata.m_bundle->second ||
execdata.m_bundle->second >= tx_to.vout.size()) return false;

        // Verify the value commitment
        if (VerifyOutputsGroup(tx_to, cache.m_spent_outputs[in_pos].nValue,
execdata.m_bundle->first, execdata.m_bundle->second)) return false;



        for (unsigned int out_pos = execdata.m_bundle->first; out_pos <
execdata.m_bundle->second + 1; out_pos++) {
            bool anypubkey_flag = false;
            bool anyamount_flag = false;
            std::map<unsigned int, char>::const_iterator it;

            if ((output_type & SIGHASH_GROUP_ANYPUBKEY) ==
SIGHASH_GROUP_ANYPUBKEY) {
                it = execdata.m_anypubkeys.find(out_pos);
                if (it != execdata.m_anypubkeys.end() && it->second == 1) {
                    anypubkey_flag = true;
                }
            }

            if ((output_type & SIGHASH_GROUP_ANYAMOUNT) ==
SIGHASH_GROUP_ANYAMOUNT) {
                it = execdata.m_anyamounts.find(out_pos);
                if (it != execdata.m_anyamounts.end() && it->second == 1) {
                    anyamount_flag = true;
                }
            }

            if (!anypubkey_flag) {
                ss << tx_to.vout[out_pos].scriptPubKey;
            }
            if (!anyamount_flag) {
                ss << tx_to.vout[out_pos].nValue;
            }

        }
    }

I think it's achieving the same effect as IN_OUT_AMOUNT, at least for
CoinPool use-case. A MuSig  `contract_pubkey` can commit to the
`to_withdraw` output while allowing a wildcard for the `to_pool` output
nValue/scriptPubKey. The nValue correctness will be ensured by the
group-value-lock validation rule (`VerifyOutputsGroup`) and scriptPubkey by
OP_MERKLESUB commitment.

I think witness data size it's roughly equivalent as the annex fields must
be occupied by the output group commitment. SIGHASH_GROUP might be more
flexible than IN_OUT_AMOUNT for a range of use-cases, see my point on AMM.

> 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:
>
>  * 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

Yes the security model is roughly similar to the LN one. Instead of a
counter-signed commitment transaction which can be broadcast at any point
during channel lifetime, you have a pre-signed withdraw transaction sending
to {`to_withdraw`,`to_pool`} outputs. Former is your off-chain balance, the
latter one is the pool balance, and one grieved with the updated Taproot
output. The withdraw tapscript force the point subtraction with the
following format (`<n> <withdraw_point> <OP_MERKLESUB> <33-byte
contract_pubkey> OP_CHECKSIG)

> 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.

Yes, that kind of blockchain validation semantic extension is vaudoo-magic
if we want to enable smart corporation/scalable multi-event contracts. I
gave a presentation on advanced bitcoin contracts two years ago, mentioning
we would need covenants to solve the factorial complexity on edge-case [4]

Bitcoin ledger would fit perfectly well to host international commerce law
style of contracts, where you have a lot of usual fancy provisions (e.g
hardship, delay penalty, ...) :)

> 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

Yeah, in that kind of case, we might want to push the merkle root as a
stack element but still update the internal pubkey from the spent utxo ?
This new merkle_root would be the tree of tweaked scripts as you expect
them if you execute *this* tapscript. And you can still this new tree with
a tapbranch inherited from the taproot output.

(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)

> 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). I think it
can be simplified to just generate pairs of input btc-amount/output
usdt-amount for the whole range of strike price you want to cover.

Each transaction puzzle has 1-input/2-outputs. The first output is signed
with SIGHASH_ANYPUBKEY but committed to a USDT amount. The second output is
signed with SIGHASH_ANYAMOUNT but committed to the maker pubkey. The input
commits to the spent BTC amount but not the spent txid/scriptPubKey.
The maker generates a Taproot tree where each leaf is committing to a
different "strike price".

A taker is finalizing the puzzle by inserting its withdraw scriptPubKey for
the first output and the maker amount for the second output. The
transitivity value output group rule guarantees that a malicious taker
can't siphon the fund.

> (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)

Yeah, I think CHECKSIGFROMSTACK is a no-go if we want to emulate
TAPLEAF_UPDATE_VERIFY functionality. If you want to update the 100th
tapscript, I believe we'll have to throw on the stack the corresponding
merkle branch and it sounds inefficient in terms of witness space ? Though
ofc, in both cases we bear the tree traversal computational cost ?

Really really excited to see progress on more powerful covenants for
Bitcoin :)

Cheers,
Antoine

[0] For the ideas genealogy, I think Greg's OP_MERKLE_UPDATE has been
circulating for a while and we chatted with Jeremy last year about the
current limitation of the script interpreter w.r.t expressing the factorial
complexity of advanced off-chain systems. I also remember Matt's artistic
drawing of a TAPLEAF_UPDATE_VERIFY ancestor on a Chaincode whiteboard :)

[1]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017964.html

[2]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html

[3] A legal construction well-spread in the real-world. Known as
"indivision" in civil law".

[4] https://github.com/ariard/talk-slides/blob/master/advanced-contracts.pdf

Le jeu. 9 sept. 2021 à 02:42, Anthony Towns via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a écrit :

> Hello world,
>
> 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.
>
> 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.
>
> I'll split this into two emails, this one's the handwavy overview,
> the followup will go into some of the implementation complexities.
>
>
>
> The basic idea is to think about "updating" a utxo by changing the
> taproot tree.
>
> 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=P+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.
>
> 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:
>
>  * Updating the internal public key (ie from P to P' = 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)
>
> Once you've done those things, you can then calculate the new merkle
> root by resolving the updated merkle path (eg, S' = MerkleRootFor(AB,
> F, H_TapLeaf(E))), and then calculate a new scriptPubKey based on that
> and the updated internal public key (Q' = P' + H(P', S')).
>
> 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.
>
> 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.
>
>
>
> Here's two examples of how you might use this functionality.
>
> 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.
>
> To set this up with TLUV, you construct a taproot output with COLD as
> the internal public key, and a script that specifies:
>
>  * The tx is signed via HOT
>  * <D> 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
>
> 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.
>
> 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:
>
>  * 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)
>
> The other script is either "locked" (which is just "OP_RETURN") or
> "available" which specifies:
>
>  * The tx is signed via HOT
>  * <D> 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.
>
> H_LOCKED and H_AVAILABLE are just the TapLeaf hash corresponding to the
> "locked" and "available" scripts.
>
> 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.
>
>
>
> 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:
>
>  * 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
>
> 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.
>
> 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.
>
> 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).
>
> 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.
>
>
>
> 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)
>
>
>
> I think there's two limitations of this method that are worth pointing out.
>
> 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
>
> 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.
>
>
>
> (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)
>
> Cheers,
> aj
>
> [0] https://gist.github.com/ajtowns/dc9a59cf0a200bd1f9e6fb569f76f7a0
>
> [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.
>
> [2] Recently in covid-adjusted terms, or on the bitcoin consensus
>     change scale anyway...
>     https://mobile.twitter.com/ajtowns/status/1385091604357124100
>
> [3]
> https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#Constructing_and_spending_Taproot_outputs
>
> [4]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017231.html
>
> [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.
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 33978 bytes --]

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns]

On Thu, Sep 09, 2021 at 12:26:37PM -0700, Jeremy wrote:
> I'm a bit skeptical of the safety of the control byte. Have you considered the
> following issues?

>     If we used the script "0 F 0 TLUV" (H=F, C=0) then we keep the current
>     script, keep all the steps in the merkle path (AB and CD), and add
>     a new step to the merkle path (F), giving us:
>         EF = H_TapBranch(E, F)
>         CDEF =H_TapBranch(CD, EF)
>         ABCDEF = H_TapBranch(AB, CDEF)
> 
> If we recursively apply this rule, would it not be possible to repeatedly apply
> it and end up burning out path E beyond the 128 Taproot depth limit?

Sure. Suppose you had a script X which allows adding a new script A[0..n]
as its sibling. You'd start with X and then go to (A0, X), then (A0,
(A1, X)), then (A0, (A1, (A2, X))) and by the time you added A127 TLUV
would fail because it'd be trying to add a path longer than 128 elements.

But this would be bad anyway -- you'd already have a maximally unbalanced
tree. So the fix for both these things would be to do a key path spend
and rebalance the tree. With taproot, you always want to do key path
spends if possible.

Another approach would be to have X replace itself not with (X, A) but
with (X, (X, A)) -- that way you go from:

   /\
  A  X

to 
     /\
    A /\
     X /\
      B  X
  
to 
      /\
     /  \
    A   /\
       /  \
      /    \
     /\    /\
    C  X  B  X

and can keep the tree height at O(log(n)) of the number of members.

This means the script X would need a way to reference its own hash, but
you could do that by invoking TLUV twice, once to check that your new
sPK is adding a sibling (X', B) to the current script X, and a second
time to check that you're replacing the current script with (X', (X',
B)). Executing it twice ensures that you've verified X' = X, so you can
provide X' on the stack, rather than trying to include the script's on
hash in itself.

> Perhaps it's OK: E can always approve burning E?

As long as you've got the key path, then I think that's the thing to do.

>     If we used the script "0 F 4 TLUV" (H=F, C=4) then we keep the current
>     script, but drop the last step in the merkle path, and add a new step
>     (effectively replacing the *sibling* of the current script):
>         EF = H_TapBranch(E, F)
>         ABEF = H_TapBranch(AB, EF) 
>     If we used the script "0 0 4 TLUV" (H=empty, C=4) then we keep the current
>     script, drop the last step in the merkle path, and don't add anything new
>     (effectively dropping the sibling), giving just:
>         ABE = H_TapBranch(AB, E)
> 
> Is C = 4 stable across all state transitions? I may be missing something, but
> it seems that the location of C would not be stable across transitions.

Dropping a sibling without replacing it or dropping the current script
would mean you could re-execute the same script on the new utxo, and
repeat that enough times and the only remaining ways of spending would
be that script and the key path.

> E.g., What happens when, C and E are similar scripts and C adds some clauses
> F1, F2, F3, then what does this sibling replacement do? Should a sibling not be
> able to specify (e.g., by leaf version?) a NOREPLACE flag that prevents
> siblings from modifying it?

If you want a utxo where some script paths are constant, don't construct
the utxo with script paths that can modify them.

> What happens when E adds a bunch of F's F1 F2 F3, is C still in the same
> position as when E was created?

That depends how you define "position". If you have:

    
   /\
  R  S

and

   /\
  R /\
   S  T

then I'd say that "R" has stayed in the same position, while "S" has
been lowered to allow for a new sibling "T". But the merkle path to
R will have changed (from "H(S)" to "H(H(S),H(T))"). 

> Especially since nodes are lexicographically sorted, it seems hard to create
> stable path descriptors even if you index from the root downwards.

The merkle path will always change unless you have the exact same set
of scripts, so that doesn't seem like a very interesting way to define
"position" when you're adding/removing/replacing scripts.

The "lexical ordering" is just a modification to how the hash is
calculated that makes it commutative, so that H(A,B) = H(B,A), with
the result being that the merkle path for any script in the the R,(S,T)
tree above is the same for the corresponding script in the tree:

   /\
  /\ R
 T  S

Cheers,
aj

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns]

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

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 15408 bytes --]

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 <aj@erisian.com.au> 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
>
>

[-- Attachment #2: Type: text/html, Size: 16734 bytes --]

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns]

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

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 16027 bytes --]

> 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 <aj@erisian.com.au> 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
>
>

[-- Attachment #2: Type: text/html, Size: 18008 bytes --]

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns]

On Sat, Sep 18, 2021 at 10:11:10AM -0400, Antoine Riard wrote:
> 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.

Note that it's not "update" so much as "add to"; and I mostly think
graftroot (and friends), or just updating the utxo onchain, are a better
general purpose way of doing that. It's definitely a tradeoff though.

> 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"

Hmm, I'm reading C5 as "If an oracle says X, and Alice and Carol agree,
they can distribute all the remaining funds as they see fit".

> 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)))

Make it:

  (((AB, (A,B)), (CD, (C,D))), ACO)

AB = DROP <alice+bob> DUP 0 6 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 2BTC LESSTHAN
CD = same but for carol+dave
A = <alice> DUP <B'> 10 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 1BTC LESSTHAN
B' = <bob> DUP 0 2 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 1BTC LESSTHAN
B,C,D = same as A but for bob, etc
A',C',D' = same as B' but for alice, etc
ACO = <alice+carol> CHECKSIGVERIFY <oracle> CHECKSIG

Probably AB, CD, A..D, A'..D' all want a CLTV delay in there as well.
(Relative timelocks would probably be annoying for everyone who wasn't
the first to exit the pool)

> 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...

I think the above fixes that -- when AB is spent it deletes itself and
the (A,B) pair; when A is spent, it deletes (A, B and AB) and replaces
them with B'; when B' is spent it just deletes itself.

Cheers,
aj

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 3711 bytes --]

> Hmm, I'm reading C5 as "If an oracle says X, and Alice and Carol agree,
> they can distribute all the remaining funds as they see fit".

Should be read as an OR:

        IF 2 <oracle_sig> <alice_sig> 2 CHECKMULTISIG
        ELSE 2 <oracle_sig> <bob_sig> 2 CHECKMULTISIG
        ENDIF
        <> 2 IN_OUT_AMOUNT

The empty vector is a wildcard on the spent amount, as this tapscript may
be executed before/
after the split or any withdraw option.

> (Relative timelocks would probably be annoying for everyone who wasn't
> the first to exit the pool)

And I think unsafe, if you're wrapping a time-sensitive output in your
withdraw scriptPubkey.

> I think the above fixes that -- when AB is spent it deletes itself and
> the (A,B) pair; when A is spent, it deletes (A, B and AB) and replaces
> them with B'; when B' is spent it just deletes itself.

Right, here the subtlety in reading the scripts is about the B'
substitution tapscript in the
A one. And it sounds correct to me that AB exercise deletes the withdraw
pair (A, B).

Le lun. 20 sept. 2021 à 10:52, Anthony Towns <aj@erisian.com.au> a écrit :

> On Sat, Sep 18, 2021 at 10:11:10AM -0400, Antoine Riard wrote:
> > 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.
>
> Note that it's not "update" so much as "add to"; and I mostly think
> graftroot (and friends), or just updating the utxo onchain, are a better
> general purpose way of doing that. It's definitely a tradeoff though.
>
> > 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"
>
> Hmm, I'm reading C5 as "If an oracle says X, and Alice and Carol agree,
> they can distribute all the remaining funds as they see fit".
>
> > 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)))
>
> Make it:
>
>   (((AB, (A,B)), (CD, (C,D))), ACO)
>
> AB = DROP <alice+bob> DUP 0 6 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 2BTC
> LESSTHAN
> CD = same but for carol+dave
> A = <alice> DUP <B'> 10 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 1BTC LESSTHAN
> B' = <bob> DUP 0 2 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 1BTC LESSTHAN
> B,C,D = same as A but for bob, etc
> A',C',D' = same as B' but for alice, etc
> ACO = <alice+carol> CHECKSIGVERIFY <oracle> CHECKSIG
>
> Probably AB, CD, A..D, A'..D' all want a CLTV delay in there as well.
> (Relative timelocks would probably be annoying for everyone who wasn't
> the first to exit the pool)
>
> > 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...
>
> I think the above fixes that -- when AB is spent it deletes itself and
> the (A,B) pair; when A is spent, it deletes (A, B and AB) and replaces
> them with B'; when B' is spent it just deletes itself.
>
> Cheers,
> aj
>

[-- Attachment #2: Type: text/html, Size: 4487 bytes --]

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Olaoluwa Osuntokun]

[-- Attachment #1: Type: text/plain, Size: 5504 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 6320 bytes --]

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Billy Tetrud]

[-- Attachment #1: Type: text/plain, Size: 6908 bytes --]

I very much like this idea. It seems pretty flexible and has a lot of
interesting properties and use cases without being very complex. I'll have
to read through this more deeply later. I'm curious to understand more how
it compares to OP_CTV. It seems that implementing OP_TLUV wouldn't make
OP_CTV obsolete/uncessary, is that right?

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

This is talking about sending data to the output from an input or getting
data from a parent input, other than any added output tapscripts, right? I
think this can/should be done with a separate opcode, so I'm not sure I
would really call this a limitation here. I wrote a proposal for something
that does allow interaction like that (specifically sending data to an
output: OP_PUSHOUTPUTSTACK
<https://github.com/fresheneesz/bip-efficient-bitcoin-vaults/blob/main/bip-pushoutputstack.md>
).

On Wed, Sep 22, 2021 at 7:29 PM Olaoluwa Osuntokun via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 8249 bytes --]

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Tim Ruffing]

Hi aj,

I think there's another workaround for the x-only issue with
TAPLEAF_UPDATE_VERIFY.

So the opcode will need a function f that ensures that the new internal
key f(P'), where P' = P + X, has even y. You describe what happens for
the canonical choice of
f(P') = if has_even_y(P') then P' else -P'.

This leads to issues because negation turns around the signs of A and B
if say P' = A + B. Or more generally, negation is multiplicative
tweaking with a tweak -1, and that changes the coefficients of A und B.

But what if we use additive tweaking, which won't change the
coefficients? For example, you could try adding the generator until you
hit an even point, i.e., 
f(P') = if has_even_y(P') then P' else f(P' + G).

Then you may get a chain like
 * Pabc = A + B + C
 * Pab  = A + B      + 2G
* Pa = A + 2G + 1G = A + 3G

Pool members will simply need to track the accumulated tweak t and take
the tweak into account when signing. For example, A and B would sign
with t = 2 and A alone would sign with t = 3. 

This choice of f will succeed after 1 addition on average. (I don't
know if this can be proven but even if not, experiments show that it's
true and that's good enough.) So the actual running time is
probabilistic. I don't think that's an issue but if it is an issue,
other choices of f are possible, e.g., let the spender provide the
tweak t explicitly and set
f(P',t) = if 0 <= t < 128 and has_even_y(P'+tG) then P'+tG else fail.

This workaround is not exactly elegant either but it may be better than
the other suggestions.

Best,
Tim

On Thu, 2021-09-09 at 16:53 +1000, Anthony Towns via bitcoin-dev wrote:
> Moving on to the pooled scheme and actually updating the internal
> pubkey
> is, unfortunately, where things start to come apart. In particular,
> since taproot uses 32-byte x-only pubkeys (with implicit even-y) for
> the
> scriptPubKey and the internal public key, we have to worry about what
> happens if, eg, A,B,C and A+B+C all have even-more elegy, but
> (A+B)=(A+B+C)-C does
> not have even-y. In that case allowing C to remove herself from the
> pool,
> might result in switching from the scriptPubKey Qabc to the
> scriptPubKey
> Qab as follows:
> 
>      Qabc = (A+B+C) + H(A+B+C, (Sa, (Sb, Sc)))*G
>      Qab = -(A+B) + H( -(A+B), (Sa, Sb)*G
> 
> That's fine so far, but what happens if B then removes himself from
> the
> pool? You take the internal public key, which turns out to be -(A+B)
> since (A+B) did not have even y, and then subtract B, but that gives
> you
> -A-2B instead of just A. So B obtains his funds, but B's signature
> hasn't
> been cancelled out from the internal public key, so is still required
> in order to do key path spends, which is definitely not what we want.
>