Date: Thu, 09 Sep 2021 12:56:10 +0000
To: Anthony Towns <aj@erisian.com.au>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: darosior <darosior@protonmail.com>
Reply-To: darosior <darosior@protonmail.com>
Message-ID: <Er7M8L4KS9ZxYK6pIPy6dCtTbjb2edbIzAjhU4CCQi3n1klj6x7C0gTw0MrL4w91wZ_aRVEFuzcFOc8U8wz_KfKchlLi3Hp2Okhu7D-CTRo=@protonmail.com>
In-Reply-To: <20210909065330.GB22496@erisian.com.au>
References: <20210909064138.GA22496@erisian.com.au>
 <20210909065330.GB22496@erisian.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode
Precedence: list

Hi Anthony,


This post is a follow-up to your insight on Twitter [0], sent here for bett=
er
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 partic=
ipants
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 aft=
er 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 policie=
s (can't
broadcast the Unvault outside business hours, can't unvault more than <limi=
t> 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 b=
y the
managers to spend the Unvault output) itself to further restrict how the co=
in can move [3].

But in order to do so, you'd need the managers to disclaim the Spend transa=
ction they
are going to use before broadcasting the Unvault and somehow commit to it a=
t unvaulting
time. Apart from stupid hacks [4] i could not find a reasonable covenant de=
sign 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 wo=
uld replace
the current branch being executed by a CSV + CTV which input hash value wil=
l be taken
from the witness stack at Unvault broadcast. Therefore chosen by the manage=
rs at spending
time, and available for the entire duration of the timelock.

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

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=3D20
[1] we've proposed Revault a year and a half ago, have been building it sin=
ce. 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 expen=
se of a
    reduction of security and a pretty ugly hack: by using "anti-replay" or=
acles
    (cosigning servers that are only going to sign only once for a given pr=
evout)
[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 tr=
ansaction
    spending <same txid>:1 and have managers append an output to the Unvaul=
t enforcing
    a covenant just before broadcast"
[5] as a branch because i don't know how to use the keypath spend for a mul=
tisig with
    cold keys (yet).
[6] as such you'd need a sig for canceling but not for unvaulting, so it re=
verses the
    security model from "can't do anything til everyone signed" to "can ste=
al 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 feebu=
mp 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.

=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 Original Me=
ssage =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90

Le jeudi 9 septembre 2021 =C3=A0 8:53 AM, Anthony Towns via bitcoin-dev <bi=
tcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :

> 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_SUCCES=
S
>
> 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. Th=
e
>
> 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 =3D H_TapBranch(A, B)
>
> CD =3D H_TapBranch(C, D)
>
> CDE =3D H_TapBranch(CD, E)
>
> ABCDE =3D H_TapBranch(AB, CDE)
>
> And we're spending using script E, in that case the control block include=
s
>
> 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=3DF, C=3D0) then we keep the curren=
t
>
> 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 =3D H_TapBranch(E, F)
>
> CDEF =3DH_TapBranch(CD, EF)
>
> ABCDEF =3D H_TapBranch(AB, CDEF)
>
> If we used the script "0 F 2 TLUV" (H=3DF, C=3D2) then we drop the curren=
t
>
> script, but keep all the other steps, and add a new step (effectively
>
> replacing the current script with a new one):
>
> CDF =3D H_TapBranch(CD, F)
>
> ABCDF =3D H_TapBranch(AB, CDF)
>
> If we used the script "0 F 4 TLUV" (H=3DF, C=3D4) then we keep the curren=
t
>
> script, but drop the last step in the merkle path, and add a new step
>
> (effectively replacing the sibling of the current script):
>
> EF =3D H_TapBranch(E, F)
>
> ABEF =3D H_TapBranch(AB, EF)
>
> If we used the script "0 0 4 TLUV" (H=3Dempty, C=3D4) then we keep the cu=
rrent
>
> script, drop the last step in the merkle path, and don't add anything new
>
> (effectively dropping the sibling), giving just:
>
> ABE =3D H_TapBranch(AB, E)
>
> Implementing the release/locked/available vault construct would then
>
> look something like this:
>
> Locked script =3D "OP_RETURN"
>
> Available script =3D "<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 =3D "<HOT> CHECKSIGVERIFY IF <H_LOCKED> ELSE <H_AVAILABLE>=
 ENDIF 0 SWAP 4 TLUV INPUTAMOUNT OUTPUTAMOUNT LESSTHANOREQUAL"
>
> HOT =3D 32B hot wallet pubkey
>
> X =3D maximum amount spendable via hot wallet at any time
>
> D =3D compulsory delay between releasing funds and being able to spend th=
em
>
> H_LOCKED =3D H_TapLeaf(locked script)
>
> H_AVAILABLE=3D H_TapLeaf(available script)
>
> Internal public key =3D 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)=3D(A+B+C)-C do=
es
>
> 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 =3D (A+B+C) + H(A+B+C, (Sa, (Sb, Sc)))*G
>
> Qab =3D -(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 participan=
t
>
> 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 =3D P + H(P, S)*G wh=
ere
>
> 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 =3D add/subtract the point=
,
>
> C&2 =3D require the result to be even/odd y (with C&4 and C>>3 controllin=
g
>
> 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 sometime=
s
>
> 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