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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
Delivery-date: Wed, 08 May 2024 17:37:23 -0700
Received: from mail-ua1-f61.google.com ([209.85.222.61])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDSJ7DXSQ4PRBO5V6CYQMGQET56ND6I@googlegroups.com>)
id 1s4rmk-0001cx-NP
for bitcoindev@gnusha.org; Wed, 08 May 2024 17:37:23 -0700
Received: by mail-ua1-f61.google.com with SMTP id a1e0cc1a2514c-7f46ba3d89bsf204691241.3
for <bitcoindev@gnusha.org>; Wed, 08 May 2024 17:37:22 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1715215036; cv=pass;
d=google.com; s=arc-20160816;
b=POYVdvkWsoCJoM9V6gvqADQFqwyAgEKLvmCgLmfi5VUjRavmxXOIAC/8pU8mnu9Sch
evLUuBBL3IMVvlnLwVHoGFdKCSWJ/JPkDBkdC2A47AGtJHlcPE2zUbthDwlm4+j0FJXd
4gKfF5Xlli3OHN44+1DHG5GVjNvJs8XV7OeYXHeKV4vg0U9FrCzVW4WCXR6jrSUptr07
mciRH/hQOHI32zviF1ceaXrGjOLyRE0HgjhfJ7M7TfiMuOBXjZQcki1XA/GyzNkksUjF
ouiUwjmbAuhzggPWwKjQJedaASxrycBM2XdkEcKnbHRAxXuMzDR1FMyEWwGwJSZvH8TJ
tD1Q==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:cc:to:subject:message-id:date:from
:in-reply-to:references:mime-version:sender:dkim-signature
:dkim-signature;
bh=8tZLcAX++VnLdj1PzWxIZj7Lq+XkP3XBu1EjMZq+vzc=;
fh=EgZ8u2KYp0oFOY6DH5L8H/orUDgVtWqV70hJtZZQgPc=;
b=Usp/QX11gNyM6KT3WAxyS7d0eeLlfnEnC/E2vfpasluszbEUOJMwjYx7RM/A0KgzuS
07pty0xDbeYyJFh4QGr/BAvuAzI8+nsLk+oOANC2py7LvL6k4GnBrlke+LkbzdAbWKeW
ZqLBXSAUWjDLcil/UhgEEusD8lbD7II3hTiX1p/tq5/GK8IojUMiY92lrMQempg3VeVw
n6j1oKJk+tjPR9JU0gvwbO9Dr8j5Ek4rd9+8MbzMLgtfNCTfsYmuRQiKBJD4S4d6CRgP
+wQuXoHW1V8uz7IQUYKw8tiToMb/0AKn6iZA7fIZqBhekC4NBbSGnnLQt247GTYIjdWg
ozkw==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=RTfajXGZ;
spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1715215036; x=1715819836; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:cc:to:subject:message-id:date:from:in-reply-to
:references:mime-version:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=8tZLcAX++VnLdj1PzWxIZj7Lq+XkP3XBu1EjMZq+vzc=;
b=pBSrldS1xgmJaDBo0T/pY1/nGR3eWKMiNTxOcqva4WxveJky9Aj8p+OGwT9Mk1VZFJ
hidi6t4OEnWuiSljfYbCBDYjRx1tv9xpf2jauLPsAT0u+TrlpKiMMP0P5wmR2/ntYxe0
jHaIUNQh+T6wer22UI8fh5rYnv/w5sTI9efspSMMsWgeMHHFHI2+n4f5haEYjC3fUSlY
qCEViuVcQ3bJfsOkiWYKPFz7fBRm+4h2v1Din5alPgVTwnBL8wmdvOnQP2XWWJwqC2uF
rnbrXfl6Z+NoYUuEVGXGJQQeCyQJGiX+WODJBWWmut01BmUEDjStTcjj3xkLxuTLy9NP
iBSg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1715215036; x=1715819836; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:cc:to:subject:message-id:date:from:in-reply-to
:references:mime-version:from:to:cc:subject:date:message-id:reply-to;
bh=8tZLcAX++VnLdj1PzWxIZj7Lq+XkP3XBu1EjMZq+vzc=;
b=GaAGW0xeJAtG8udYhXglWm3CLGjRR44eWFvPjGweDNZF7AjKHCV+7wgWzPyhmyA6vL
wNRvtdk6iHHjvUCQTucmGPyV1wtT3gp7ZapZVp29Ox+HmXelWrOoRypL7fcY3LPvytJV
PEvPdLL3rtE7R5nyvMlyiwa1k9FCPtJ+Ddk5OSS2STWnBiXhnsoO6mTO/UnTaJNWst5i
z1wRunGH8QS0cakCv1yi1tQg2ymxh5l1M99U1ypCld9MMhiYGzmTVCO2uXgTEJfcpQgN
d8zJnlEdvpyLGoyGK3orq0LhVY7ZMIxh4hJX+EqN5De/du8aQW1o89C1Irc14fBeRPD2
gLPA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1715215036; x=1715819836;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:cc:to:subject:message-id:date:from:in-reply-to
:references:mime-version:x-beenthere:x-gm-message-state:sender:from
:to:cc:subject:date:message-id:reply-to;
bh=8tZLcAX++VnLdj1PzWxIZj7Lq+XkP3XBu1EjMZq+vzc=;
b=M04MdaovTCjDElkHOxc0uFppbX9DFyeSq0chdSwL/WQhTK5RCdCSoB1/+bJHixdzx+
wMPrv5WXky38PTV2ZDFjwDT9eWPwP8q+c4I7AAAlpEUh4SGx9sNeEAKg5kb5s7EgLwsf
i+YKvBZoUZZ5bHgABJGa/WgxoxdBYl6u8+SB8lF7J1mF24Hvyaf9TknVYebqG5PwzvYN
3QOQhImRPNOwIGynbwdpSAt1pmALvKQkmd2cl4pfkzujBLu3anVzTe78gHXi2PhO1vNu
WP0ec63xGQDgbsEuTvEq5PfFkt+7n6RFRFq/FrpxhTAiS4DkgUENJcjnFvpKzP/ogbAg
dqUw==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCWW+wbe4zq2DGlm5tDvM5jtsD8Ias6H4jJkku6i3CVzKwmImVZ7OPL4X7vG7xuX/Vnmb9RbGOtygPqG9ttwH9Jv8Yge+vM=
X-Gm-Message-State: AOJu0YwU1jm3Ilw+Hf061LkPSTaA3ybrHWO5DS0eAPPBX2MLheaknE7n
G2D286p7n87P1NLt4YST29n1TyQYmdC001wjw63smQRVg88pRbF0
X-Google-Smtp-Source: AGHT+IE4W7gJbnlqITuR9PplJ1q6bULGfscFDFaa/PlRjD9c2PJTnuCtQE7rze7JKUgRTdQC0IR+JA==
X-Received: by 2002:a67:e8c7:0:b0:47e:bd11:7e5e with SMTP id ada2fe7eead31-47f3c29eb5bmr4148203137.7.1715215036122;
Wed, 08 May 2024 17:37:16 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6214:234e:b0:6a0:a8e7:f46a with SMTP id
6a1803df08f44-6a15d44a36als4180286d6.1.-pod-prod-03-us; Wed, 08 May 2024
17:37:14 -0700 (PDT)
X-Received: by 2002:a05:6214:20ea:b0:6a0:c6bc:196e with SMTP id 6a1803df08f44-6a1514c006amr1107826d6.2.1715215034745;
Wed, 08 May 2024 17:37:14 -0700 (PDT)
Received: by 2002:a05:620a:4101:b0:790:efaf:f1f8 with SMTP id af79cd13be357-792a74187c3ms85a;
Tue, 7 May 2024 09:06:32 -0700 (PDT)
X-Received: by 2002:a05:6512:482:b0:51c:eeee:8679 with SMTP id v2-20020a056512048200b0051ceeee8679mr10991072lfq.56.1715097990231;
Tue, 07 May 2024 09:06:30 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1715097990; cv=none;
d=google.com; s=arc-20160816;
b=JxqGJuKLC1aGClT2AKYcs1kbqkCkYLusuZYJRQ/MAw9/7GsAQvdKQniJKL/JF/Wb8g
XYTAlVoX4GrrrLZHnIr2cwv06n60XPMsgMtocZGdzsM6xNUJVGdxuKqOu9ExV41nFq1F
DnNwFgSjPrfpdqNFHeS7pjqXVURVQhTlaZ4ltyp6dmCvCJ5ATbleYjm7rZ6BQ3SB7pGv
SkkPGri+nbBdEsbhW7NpXc7i2kChNpNwzQEKIlk6rdWTj5bVP8BodwpLNHXdcR4GQMfm
KFu4os3ewodLVlDJ5IhtM7CT7WON3P8dGGMjz99Sqrzd+AWaLiz1l/VoLoZK6OdjhwHe
jN6Q==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
h=cc:to:subject:message-id:date:from:in-reply-to:references
:mime-version:dkim-signature;
bh=oLZCulNtOczeH8X2DshDcC2HJTjBXRd/SGumL8r4ODY=;
fh=sapDHqhE46zLmMBeB1lkoe0zq8J9+V3Afx71/j8kvug=;
b=PmX3dzorS+BfSs8OsKQVK4sPT9BR3fOHhVEVlfKA6I7q76VSJtZb1UXAt16rVmAmw8
3iJAGZegwP8ng7tjjvVl8vQMBF7pP+SdeTMBu9AD955C0RCCe+Ho0TEGVBYj5JaUhRbw
NyT6RlJwVuMoxUJwgDXm0D9sw6gYgimDVOSfnR5HUZROzO5t5vIlrJW3PrR/h+oAEP7X
DbKPFD0j42WutZ8e9aDZOLO+sPl3lP2WuzUbSiC9mGvvJAg+/EfglrOdoWV4FAxC9LAk
bEeJczr5S0OVWXIQI1yXHgFDgpuU+bQ3oAh2bSzrviKHDI2BRPq4RJ7JoLEIpZ4lTtD9
nHGA==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=RTfajXGZ;
spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com
Received: from mail-lf1-x12d.google.com (mail-lf1-x12d.google.com. [2a00:1450:4864:20::12d])
by gmr-mx.google.com with ESMTPS id h14-20020a0565123c8e00b0051d2708dd8bsi362802lfv.9.2024.05.07.09.06.30
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Tue, 07 May 2024 09:06:30 -0700 (PDT)
Received-SPF: pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as permitted sender) client-ip=2a00:1450:4864:20::12d;
Received: by mail-lf1-x12d.google.com with SMTP id 2adb3069b0e04-51fea3031c3so4261346e87.0
for <bitcoindev@googlegroups.com>; Tue, 07 May 2024 09:06:30 -0700 (PDT)
X-Received: by 2002:a05:6512:4dd:b0:520:36ea:9375 with SMTP id
w29-20020a05651204dd00b0052036ea9375mr6211797lfq.43.1715097989462; Tue, 07
May 2024 09:06:29 -0700 (PDT)
MIME-Version: 1.0
References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
<CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
<ZjD-dMMGxoGNgzIg@camus> <47711dc4ffe9d661e8321b05b6adab4e@dtrt.org>
<ZjkJ0fPyzuAPTLWS@camus> <a5a86fcd50e2cdbdf40a12ac9463a828@dtrt.org>
<ZjkqIzPSFLc0GJJ1@camus> <bd37a9f1-7fb9-4111-a069-31c3665073d2n@googlegroups.com>
In-Reply-To: <bd37a9f1-7fb9-4111-a069-31c3665073d2n@googlegroups.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Tue, 7 May 2024 12:05:52 -0400
Message-ID: <CAEM=y+X-bhUuDxyYQ-MJGA49BgvnHW9-7L3zvBLPyJux=kqYbA@mail.gmail.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
Signatures (no changes needed)
To: Antoine Riard <antoine.riard@gmail.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"
X-Original-Sender: eth3rs@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@gmail.com header.s=20230601 header.b=RTfajXGZ; spf=pass
(google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as
permitted sender) smtp.mailfrom=eth3rs@gmail.com; dmarc=pass (p=NONE
sp=QUARANTINE dis=NONE) header.from=gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)
Hi Antoine,
Responding in line:
> - Alice can:
> - a) wait for the 70% honest network to mine her transaction
> - b) increase her feerate to bump incentives to mine transaction X
> - If Alice picks up option b)
> - Alice Lamport-emulated signs and broadcast her transaction X by using ACP flag / CPFP
> - This assumes the consumption of a "fresh" fee-bumping UTXO
> - This fee-bumping UTXO can be locked under a Lamport emulated-pubkey
>
> I think this scheme with a one-time usage property is more exposed to denial-of-service
> attacks (or wallet UTXO deanonymization) than ECDSA / Schnorr scheme.
It sounded like originally you were saying she can't bump her fee
without double signing, but as you point out ANYONECANPAY or CPFP
let's you do fee bumping without double signing. This doesn't seem
different from say a pre-signed bitcoin transaction that you can't
change transaction hash of.
> I think the ECDSA signature verification algorithm forbids the usage
> of the point at infinity for the curve point resulting from the modular
> arithmetic on your r-value and s-value, not k=0 where k is the nonce.
>
> I don't know if you could play with the transaction hash to produce
> a curve point which is equals to the point at infinity, especially in
> context where the transaction hash is including inputs from multiple
> non-trusted counterparties (e.g if you're using SIGHASH flags).
I don't see the attack. If the point at infinity is forbidden, how is
this exploited? Wouldn't the attacker's signature just be rejected by
the network?
> Well, we're not comparing "apple-to-apple" here as on one side you have
> modular arithmetic operations, on the other side bitwise rotations. I'm
> thinking you might have an advantage in your ecdsa queries as a finite field
> is, as the name say so, "finite" so you could theoretically pre-compute all
> entries in your storage. On the other hand, with block mining (even assuming
> a functional implementation of Grover's algorithm) you have lookup and
> propagation latency under 10 min in average. Sounds you can parellize both
> problems resolution (re-use hash round states or point addition), so it might
> be just a classicla time-space trade-off here.
If someone discovers a smaller r than used in the signatures, they
would break the existing signatures I agree. Grover's might break P2SH
in general so Bitcoin might be in real trouble at that point.
> Correcting myself on my initial email, the design bottleneck here is obviously
> that spent outpoints are committed in a child signature digest in a no-APO world.
> This is still an interesting question if you can remove spent outpoints commitment
> by leveraging OP_SIZE or fixing other ECDSA signature components.
No APO?
Thanks,
Ethan
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BX-bhUuDxyYQ-MJGA49BgvnHW9-7L3zvBLPyJux%3DkqYbA%40mail.gmail.com.
|
