Message-ID: <b0fa72d03b9eb9341e85b0003e807f64abe1bb95.camel@timruffing.de>
From: Tim Ruffing <crypto@timruffing.de>
To: Anthony Towns <aj@erisian.com.au>, Bitcoin Protocol Discussion
 <bitcoin-dev@lists.linuxfoundation.org>
Date: Fri, 08 Jul 2022 21:52:12 +0200
In-Reply-To: <20210909065330.GB22496@erisian.com.au>
References: <20210909064138.GA22496@erisian.com.au>
 <20210909065330.GB22496@erisian.com.au>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode
Precedence: list

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' =3D P + X, has even y. You describe what happens for
the canonical choice of
f(P') =3D 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' =3D 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.,=20
f(P') =3D if has_even_y(P') then P' else f(P' + G).

Then you may get a chain like
 * Pabc =3D A + B + C
 * Pab =C2=A0=3D A + B =C2=A0 =C2=A0 =C2=A0+ 2G
* Pa =3D A + 2G + 1G =3D 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 =3D 2 and A alone would sign with t =3D 3.=20

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) =3D if 0 <=3D 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)=3D(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:
>=20
> =C2=A0=C2=A0=C2=A0=C2=A0 Qabc =3D (A+B+C) + H(A+B+C, (Sa, (Sb, Sc)))*G
> =C2=A0=C2=A0=C2=A0=C2=A0 Qab =3D -(A+B) + H( -(A+B), (Sa, Sb)*G
>=20
> 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.
>=20