Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 32C04C002D for ; Fri, 8 Jul 2022 19:59:11 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id F3F2461453 for ; Fri, 8 Jul 2022 19:59:10 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org F3F2461453 Authentication-Results: smtp3.osuosl.org; dkim=pass (2048-bit key) header.d=timruffing.de header.i=@timruffing.de header.a=rsa-sha256 header.s=MBO0001 header.b=yP+/B6Rg X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -0.901 X-Spam-Level: X-Spam-Status: No, score=-0.901 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Wp_sTHz6fNrj for ; Fri, 8 Jul 2022 19:59:10 +0000 (UTC) X-Greylist: delayed 00:06:50 by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 6F41D613D6 Received: from mout-p-202.mailbox.org (mout-p-202.mailbox.org [80.241.56.172]) by smtp3.osuosl.org (Postfix) with ESMTPS id 6F41D613D6 for ; Fri, 8 Jul 2022 19:59:09 +0000 (UTC) Received: from smtp202.mailbox.org (smtp202.mailbox.org [10.196.197.202]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-p-202.mailbox.org (Postfix) with ESMTPS id 4LfkSv48lRz9sSP; Fri, 8 Jul 2022 21:52:15 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=timruffing.de; s=MBO0001; t=1657309935; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=ZJioDGMeSGaQC5MmutiSnm4sOTlof3cvGD6kkAYxbEI=; b=yP+/B6RghOYZNbNcHg4ls6q1z6zQw3rD7Rmyd0qS0rqVGwF+QeT4VM1IxELzhS/Vg0KQho kHzcxS4m9B84ddg19k8nvZEIk9wJLuZ4O7zNs4GYi9ysdHoc4fTKM6ygmM04iVncT/+Qy+ M9EjIXqpy3yAeGBNY34ZFcj4AF+kD9KyT8Nu0gDNk2b3MFgjN5rARa6V58EpO+lLLu+rz0 j8i15tLpOOKUaUuxfpg6d0bylDdk6yavMmYB/tszI/UGhNz4LdUxq5K5GljdrL0bXgmTGu 8EXGDBv3dJv/2ZJYIClmXz7EOxtfQb9reXMqBlV/S7iIy3mNX2GdzTBjE7cn5A== Message-ID: From: Tim Ruffing To: Anthony Towns , Bitcoin Protocol Discussion 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 X-Mailman-Approved-At: Fri, 08 Jul 2022 22:39:15 +0000 Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 08 Jul 2022 19:59:11 -0000 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