1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
Return-Path: <crypto@timruffing.de>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 32C04C002D
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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: <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
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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
|
