Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Tim Ruffing via bitcoin-dev]

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

[Billy Tetrud via bitcoin-dev]

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

).

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 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Olaoluwa Osuntokun via bitcoin-dev]

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 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Antoine Riard via bitcoin-dev]

> 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   2 CHECKMULTISIG
ELSE 2   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  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  DUP 0 6 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 2BTC
> LESSTHAN
> CD = same but for carol+dave
> A =  DUP  10 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 1BTC LESSTHAN
> B' =  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 =  CHECKSIGVERIFY  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
>
___
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

[Anthony Towns via bitcoin-dev]

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  DUP 0 6 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 2BTC 
LESSTHAN
CD = same but for carol+dave
A =  DUP  10 TLUV CHECKSIGVERIFY IN_OUT_AMOUNT SUB 1BTC LESSTHAN
B' =  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 =  CHECKSIGVERIFY  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
___
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

[Antoine Riard via bitcoin-dev]

> I think "  MERKLESUB" is the same as " OP_0 2 TLUV", provided
>  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   2 CHECKMULTISIG  CHECKSIG"
B=" DUP 0 2 TLUV CHECKSIG"
C=" DUP 0 2 TLUV CHECKSIG"
D=" 0 6 TLUV 1   2 CHECKMULTISIG"
E=" DUP 0 2 TLUV CHECKSIG"
F=" DUP 0 2 TLUV CHECKSIG"
G=" 0 6 TLUV 1   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 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns via bitcoin-dev]

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 "  MERKLESUB" is the same as " OP_0 2 TLUV", provided
 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 -- 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Antoine Riard via bitcoin-dev]

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 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns via bitcoin-dev]

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

 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 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Antoine Riard via bitcoin-dev]

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& 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 
bool GenericTransactionSignatureChecker::CheckMerkleUpdate(const
std::vector& control, unsigned int out_pos, const
std::vector& point) const
{
//! The internal pubkey (x-only, so no Y coordinate parity).
XOnlyPubKey p{uint256(std::vector(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(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 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 "  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 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns via bitcoin-dev]

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

___
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 via bitcoin-dev]

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?).
___
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 via bitcoin-dev]

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, { DUP "" 1 TLUV
CHECKSIGVERIFY
IN_OUT_AMOUNT SUB  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),  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 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[darosior via bitcoin-dev]

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  
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  CSV DROP 1"
C = "<32 bytes> D"
B = "
 CHECKSIG  CHECKSIGADD ...  CHECKSIGADD  
EQUALVERIFY
IN_OUT_AMOUNT SUB  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 = " CHECKSIGVERIFY  CHECKSIGVERIFY ...  
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 :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 
 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 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Matt Corallo via bitcoin-dev]

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 
>  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
> *  CSV -- there's a relative time lock since the last spend
> * If the input 

Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns via bitcoin-dev]

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 = " CHECKSIGVERIFY IN_OUT_AMOUNT SWAP  SUB DUP 0 
GREATERTHAN IF GREATERTHANOREQUAL VERIFY 0  2 TLUV ELSE 2DROP ENDIF 
 CSV"
Release script = " CHECKSIGVERIFY IF  ELSE  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