public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Tim Ruffing <crypto@timruffing.de>
To: Anthony Towns <aj@erisian.com.au>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode
Date: Fri, 08 Jul 2022 21:52:12 +0200	[thread overview]
Message-ID: <b0fa72d03b9eb9341e85b0003e807f64abe1bb95.camel@timruffing.de> (raw)
In-Reply-To: <20210909065330.GB22496@erisian.com.au>

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


  parent reply	other threads:[~2022-07-08 19:59 UTC|newest]

Thread overview: 17+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-09-09  6:41 [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode Anthony Towns
2021-09-09  6:53 ` Anthony Towns
2021-09-09 12:56   ` darosior
2021-09-09 15:54   ` Jeremy
2021-09-09 19:26   ` Jeremy
2021-09-10  7:42     ` Anthony Towns
2022-07-08 19:52   ` Tim Ruffing [this message]
2021-09-09  9:16 ` Matt Corallo
2021-09-10  4:12 ` Antoine Riard
2021-09-11  3:26   ` Anthony Towns
2021-09-12 23:37     ` Antoine Riard
2021-09-15  6:50       ` Anthony Towns
2021-09-18 14:11         ` Antoine Riard
2021-09-20 14:52           ` Anthony Towns
2021-09-22  1:40             ` Antoine Riard
2021-09-23  0:29 ` Olaoluwa Osuntokun
2021-10-29 15:47   ` Billy Tetrud

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=b0fa72d03b9eb9341e85b0003e807f64abe1bb95.camel@timruffing.de \
    --to=crypto@timruffing.de \
    --cc=aj@erisian.com.au \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox