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
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
|
Return-Path: <german@diviproject.org>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 99CF7C0175
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Apr 2020 18:40:22 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by hemlock.osuosl.org (Postfix) with ESMTP id 7E47E885FB
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Apr 2020 18:40:22 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from hemlock.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id PtviSRo1Ekyi
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Apr 2020 18:40:20 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail-wm1-f49.google.com (mail-wm1-f49.google.com
[209.85.128.49])
by hemlock.osuosl.org (Postfix) with ESMTPS id 45B95885EC
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Apr 2020 18:40:20 +0000 (UTC)
Received: by mail-wm1-f49.google.com with SMTP id e26so7514469wmk.5
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Apr 2020 11:40:20 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=diviproject-org.20150623.gappssmtp.com; s=20150623;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=r+ZL1q+uOs3Hf9G5udvnT/L8R2iOjbybcIKikmAPSHU=;
b=qeqVg5j2SHQ/XWIpXVCGu7jh+SfJ7HVdG4azKPAuyzpf3CTcyDjXeZGQd9IAYkVgH6
yB30pTA1lt5TUMhIuI58Te+/5RCrfWyiiWNNNOdaeGt/ypg+DAJpabXqfUMDOC56HrX1
g85xfhaqrpramOXBQ4FfklpWSk1PWYE0eJE46lE1YIaYKUTWRgWV4K65pMdeVY0H5+I6
6NzUiPx9J8hb0fehNy6FT1EEVPXpwNlJcTkSx3dwROcR3r0WMBoRjINy+xVomFhegmBX
wYlN+15PE4IOCcQMZqMWkrAQ+5efaxMz8GVfaRbJLSndxzBQN22RkXRTcB6kUw0wz9mH
y2Yw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc;
bh=r+ZL1q+uOs3Hf9G5udvnT/L8R2iOjbybcIKikmAPSHU=;
b=EABxcXZYmL95lxh1H6sI4wrAvl6+uFWYw7hnNYUBsQZjaJuoNc6112406BEMug6CZk
hHLnHNCiarjFCEBwXdqm+gMaZ3o5r2g991SJ32Qyew2mmVGNk/bVP/KfqOUHg24l0i2b
5hXwdQ+Z3xzB05QLTufk9KWXtoceol/WF+QyykW1kfZIjgR5Nh71HBiVyJwr5Y9pIRCF
VqGKDQk/m07KoW7T4KsWSj51QSEdiyLwnRHsU8TrbtOPPMFs48qmllob39Q5daTzeb+J
KhUb2gR2ME9YaF+0H5sgS5WY7ZKEAMynG85Quf5yLHxOK3PWQith6QVSXsREB2c2fnu6
GS7w==
X-Gm-Message-State: AGi0Puahcyg3nbMjMs3oCc1l69R+9jQoIk0NXjGH4z4l/IJamVSkKVbE
gEsjMT4j8vByYXSObV/sEYhCfBGnW73AjxE2UYtyHA==
X-Google-Smtp-Source: APiQypLHWVE67FoFpw7wsvb5zx2knB6yn7xen1JFvuwLPP5OMI1P9UiVVyNV+hFDkf0WqDE+vhEqgOJ8dY0VIAmEAkk=
X-Received: by 2002:a1c:148:: with SMTP id 69mr5749063wmb.181.1587667218501;
Thu, 23 Apr 2020 11:40:18 -0700 (PDT)
MIME-Version: 1.0
References: <CALmj_sWCA6S_4bnmLetvLuzNhv=PfQvLnX3zVEZwsRtgzA=yqw@mail.gmail.com>
<CALmj_sVwLG82_pCEnc-mdT-Cf+cPitpL59AruBbvyYLjaYoZ2Q@mail.gmail.com>
<mRCFEsXTvivO-I7sBdoTbqV0RsnX9vdGGORqzJBGYWXd1Xqis-oBNtEFaCEWIt3g9ARrvNeqH3l6sWSH4uQdcj5ps5WAmaEbEUvb9Znk9Rw=@protonmail.com>
In-Reply-To: <mRCFEsXTvivO-I7sBdoTbqV0RsnX9vdGGORqzJBGYWXd1Xqis-oBNtEFaCEWIt3g9ARrvNeqH3l6sWSH4uQdcj5ps5WAmaEbEUvb9Znk9Rw=@protonmail.com>
From: German Luna <german@diviproject.org>
Date: Thu, 23 Apr 2020 12:40:06 -0600
Message-ID: <CALmj_sUuw8JkodDemnq4qkapWD28vpojKD3bmkiVYm3Cp76+NQ@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="00000000000094a5d005a3f994b5"
X-Mailman-Approved-At: Thu, 23 Apr 2020 18:52:05 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fwd: (Semi)Traceless 2-party coinjoin off-chain
protocol using schnorr signatures
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: Thu, 23 Apr 2020 18:40:22 -0000
--00000000000094a5d005a3f994b5
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Good morning ZmnSCPxj,
Thank you for your excellent feedback!
Indeed, with a little protocol-level sugar so that the coins being swapped
get paid out of different pubkeys.
I read your article. Excellent idea on the randomized locktimes! I've still
to read the details of what S6 amounts to but I'm excited to.
With regards to trying to tackle the problem of value-based correlations,
wouldn't it be possible to try to model the solution after the
equal-sum-subset problem (np complete problem)(
https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompl=
eteness.pdf
)?
That is, a pair of individuals with a set of UTXOs that both add up to
similar if not equal value perform a swap of similar-(total)value sets. In
this way the values of the UTXOs can be broken up essentially at random
(following some nominal distribution so that it doesn't stand out; e.g.
https://en.wikipedia.org/wiki/Benford%27s_law), but swapped in conjunction
and decorrelated by using different keys + randomized locktimes.
Regards,
Germ=C3=A1n
On Thu, Apr 23, 2020 at 11:56 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
> Good morning Germ=C3=A1n,
>
> It looks to me like this is CoinSwap with Schnorr Scriptless Scripts.
>
> * https://joinmarket.me/blog/blog/coinswaps/
> *
> https://joinmarket.me/blog/blog/flipping-the-scriptless-script-on-schnorr=
/
>
> I also recently put up an article on extending such a protocol across 3 o=
r
> more participants:
>
> * https://zmnscpxj.github.io/bitcoin/multiswap.html
>
> Regards,
> ZmnSCPxj
>
> > ## Objective
> > * Make atomic swaps within the same chain possible in a traceless way
> > * Achieving traceless same-chain atomic-swaps effectively turns an
> entire chain into a (P2PKH) mixer by default
> >
> > ## Proposed solution
> > Similar to the way that atomic swaps would work with schnorr signatures
> (i.e. leveraging adaptor signatures), the proposed solution is to use - i=
n
> place of the secret 't' - a suitably chosen schnorr signature. The end
> result being that when one counterparty claims their side of the funds, t=
he
> party can obtain the signature they're missing to claim the funds in the
> (schnorr) multisig that pays them.
> > On-chain, this would appear like two independent transactions, even
> though effectively the two parties have =E2=80=9Cexchanged=E2=80=9D the h=
istory attached to
> the UTXOs. Unlike a mixing service, in which all of the histories get
> merged, with this protocol histories can be pairwise swapped without
> anybody=E2=80=99s knowledge.
> >
> > ## Protocol description
> > * Alice and Bob, holding funds at UTXO1 (controlled by Alice) and UTXO2
> (controlled by Bob) wish to swap them.
> > * Alice provides Bob with a single public key P_A
> > * Bob provides Alice two pubkeys P_B1, P_B2.
> > * Bob and Alice construct the P2PKH addresses Addr1 =3D Hash(P_A+P_B1)
> [where the UTXO1 funds will be sent to eventually] and Addr2 =3D
> Hash(P_A+P_B2) [where the UTXO2 funds will be sent to eventually]
> > * Bob and Alice exchange time-locked refund transactions for the fundin=
g
> transactions sending the funds to Addr1 and Addr2.
> > * Bob and Alice submit the funding transactions (Alice pays to Addr1
> from UTXO1; Bob pays to Addr2 from UTXO2)
> > * Alice sends Bob an adaptor signature: r1 + H(r1 | m)*x_a + r2 + H( r2
> | m')*x_a
> > * Bob verifies the adaptor signature Alice sent contains a valid
> signature for spending from Addr1 AND another valid signature for spendin=
g
> from Addr2. Both signatures from Alice. Bob cannot separate out the two
> signatures and hence cannot claim any of the funds, provided H( r1 | m) !=
=3D
> H( r2 | m') in the signature commitment.
> > * Bob now sends Alice the valid signature: r2 + H( r2 | m' )*x_b2
> > * Alice can now add her signature to Bob's and get: r2 + H( r2| m'
> )*(x_b2 + x_a) which is a valid signature to spend the funding transactio=
n
> sent to Addr2.
> > * Finally, Bob sees Alice claims the fund sent to Addr2 and uses that
> signature to subtract his own: r2 + H( r2 | m' )*(x_b2 + x_a) - (r2 + H( =
r2
> | m' )*x_b2) =3D H( r2 | m ')*x_a
> > * Bob takes the original adaptor signature and subtracts the known
> quantity r2+ H( r2 | m' )*x_a, to get a valid signature: r1 + H( r1 | m
> )*x_a
> > * Bob can now add to that valid signature, his own signature and
> retrieve the funds.
> > ## Notes
> > * It is possible for the counterparty to store copies of the signatures
> as proof that such a join has taken place. But plausible deniability is
> available upon discarding signatures since the joint private keys (x_a +
> x_b*) are unavailable.
> >
> > I'm interested in hearing feedback on this idea if possible, and deemed
> interesting enough.
> >
> > Best regards,
> > --
> > Germ=C3=A1n
> > Mathematician
>
>
>
--=20
Germ=C3=A1n
Mathematician
--00000000000094a5d005a3f994b5
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Good morning=C2=A0
<span style=3D"color:rgb(34,34,34);background-color:rgb(255,255,255)">ZmnSC=
Pxj,</span><div><br></div><div>Thank you for your excellent feedback!</div>=
<div><br></div><div>Indeed, with a little protocol-level sugar so that the =
coins being swapped get paid out of different pubkeys.</div><div>I read you=
r article. Excellent idea on the randomized locktimes! I've still to re=
ad the details of what S6 amounts to but I'm excited to.</div><div><br>=
</div><div>With regards to trying to tackle the problem of value-based corr=
elations, wouldn't it be possible to try to model the solution after th=
e equal-sum-subset problem (np complete problem)(
<a href=3D"https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subse=
tSumNPCompleteness.pdf">https://www.cs.mcgill.ca/~lyepre/pdf/assignment2-so=
lutions/subsetSumNPCompleteness.pdf</a>=C2=A0 )?=C2=A0</div><div>That is, a=
pair of individuals with a set of UTXOs that both add up to similar if not=
equal value perform a swap of similar-(total)value sets. In this way the v=
alues of the UTXOs can be broken up essentially at random (following some n=
ominal distribution so that it doesn't stand out; e.g.=C2=A0<a href=3D"=
https://en.wikipedia.org/wiki/Benford%27s_law">https://en.wikipedia.org/wik=
i/Benford%27s_law</a>), but swapped=C2=A0in conjunction and decorrelated by=
using different keys=C2=A0+ randomized locktimes.</div><div><br></div><div=
><br></div><div>Regards,</div><div>Germ=C3=A1n</div></div><br><div class=3D=
"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, Apr 23, 2020 at=
11:56 AM ZmnSCPxj <<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@=
protonmail.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" st=
yle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padd=
ing-left:1ex">Good morning Germ=C3=A1n,<br>
<br>
It looks to me like this is CoinSwap with Schnorr Scriptless Scripts.<br>
<br>
* <a href=3D"https://joinmarket.me/blog/blog/coinswaps/" rel=3D"noreferrer"=
target=3D"_blank">https://joinmarket.me/blog/blog/coinswaps/</a><br>
* <a href=3D"https://joinmarket.me/blog/blog/flipping-the-scriptless-script=
-on-schnorr/" rel=3D"noreferrer" target=3D"_blank">https://joinmarket.me/bl=
og/blog/flipping-the-scriptless-script-on-schnorr/</a><br>
<br>
I also recently put up an article on extending such a protocol across 3 or =
more participants:<br>
<br>
* <a href=3D"https://zmnscpxj.github.io/bitcoin/multiswap.html" rel=3D"nore=
ferrer" target=3D"_blank">https://zmnscpxj.github.io/bitcoin/multiswap.html=
</a><br>
<br>
Regards,<br>
ZmnSCPxj<br>
<br>
> ## Objective<br>
> * Make atomic swaps within the same chain possible in a traceless way<=
br>
> * Achieving traceless same-chain atomic-swaps effectively turns an ent=
ire chain into a=C2=A0 (P2PKH) mixer by default<br>
><br>
> ## Proposed solution<br>
> Similar to the way that atomic swaps would work with schnorr signature=
s (i.e. leveraging adaptor signatures), the proposed solution is to use - i=
n place of the secret 't' - a suitably chosen schnorr signature. Th=
e end result being that when one counterparty claims their side of the fund=
s, the party can obtain the signature they're missing to claim the fund=
s in the (schnorr) multisig that pays them.<br>
> On-chain, this would appear like two independent transactions, even th=
ough effectively the two parties have =E2=80=9Cexchanged=E2=80=9D the histo=
ry attached to the UTXOs. Unlike a mixing service, in which all of the hist=
ories get merged, with this protocol histories can be pairwise swapped with=
out anybody=E2=80=99s knowledge.<br>
><br>
> ## Protocol description<br>
> * Alice and Bob, holding funds at UTXO1 (controlled by Alice) and UTXO=
2 (controlled by Bob) wish to swap them.=C2=A0<br>
> * Alice provides Bob with a single public key P_A<br>
> * Bob provides Alice two pubkeys P_B1, P_B2.<br>
> * Bob and Alice construct the P2PKH addresses Addr1 =3D Hash(P_A+P_B1)=
[where the UTXO1 funds will be sent to eventually] and Addr2=C2=A0 =3D Has=
h(P_A+P_B2) [where the UTXO2 funds will be sent to eventually]<br>
> * Bob and Alice exchange time-locked refund transactions for the fundi=
ng transactions sending the funds to Addr1 and Addr2.<br>
> * Bob and Alice submit the funding transactions (Alice pays to Addr1 f=
rom UTXO1; Bob pays to Addr2 from UTXO2)<br>
> * Alice sends Bob an adaptor signature: r1=C2=A0+ H(r1 | m)*x_a=C2=A0+=
r2=C2=A0+ H( r2 | m')*x_a<br>
> * Bob verifies the adaptor signature Alice sent contains a valid signa=
ture for spending from Addr1 AND another valid signature for spending from =
Addr2. Both signatures from Alice. Bob cannot separate out the two signatur=
es and hence cannot claim any of the funds, provided H( r1 | m) !=3D H( r2 =
| m') in the signature commitment.=C2=A0<br>
> * Bob now sends Alice the valid signature: r2=C2=A0+ H( r2 | m' )*=
x_b2<br>
> * Alice can now add her signature to Bob's and get: r2 + H( r2| m&=
#39; )*(x_b2=C2=A0+ x_a) which is a valid signature to spend the funding tr=
ansaction sent to Addr2.<br>
> * Finally, Bob sees Alice claims the fund sent to Addr2 and uses that =
signature to subtract his own: r2 + H( r2 | m' )*(x_b2=C2=A0+ x_a) - (r=
2=C2=A0+ H( r2 | m' )*x_b2) =3D H( r2 | m ')*x_a<br>
> * Bob takes the original adaptor signature and subtracts the known qua=
ntity r2+ H( r2 | m' )*x_a, to get a valid signature: r1=C2=A0+ H( r1 |=
m )*x_a<br>
> * Bob can now add to that valid signature, his own signature and retri=
eve the funds.<br>
> ## Notes<br>
> * It is possible for the counterparty to store copies of the signature=
s as proof that such a join has taken place. But plausible deniability is a=
vailable upon discarding signatures since the joint private keys (x_a=C2=A0=
+ x_b*)=C2=A0are unavailable.<br>
><br>
> I'm interested in hearing feedback on this idea if possible, and d=
eemed interesting enough.<br>
><br>
> Best regards,<br>
> --<br>
> Germ=C3=A1n<br>
> Mathematician<br>
<br>
<br>
</blockquote></div><br clear=3D"all"><div><br></div>-- <br><div dir=3D"ltr"=
class=3D"gmail_signature"><div dir=3D"ltr">Germ=C3=A1n<div>Mathematician</=
div></div></div>
--00000000000094a5d005a3f994b5--
|