MIME-Version: 1.0
In-Reply-To: <20170320221101.GC10783@boulet.lan>
References: <20170320221101.GC10783@boulet.lan>
From: Bryan Bishop <kanzure@gmail.com>
Date: Mon, 20 Mar 2017 17:36:04 -0500
Message-ID: <CABaSBaw5+uVpRT=KtZwB2-pE4Wcoh3e=BqMiJzsyy+7JPJRy_w@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>,
	Bryan Bishop <kanzure@gmail.com>
Content-Type: multipart/mixed; boundary=94eb2c047922283858054b312789
Subject: [bitcoin-dev] Fwd: [Mimblewimble] Lightning in Scriptless Scripts
Precedence: list

--94eb2c047922283858054b312789
Content-Type: multipart/alternative; boundary=94eb2c047922283853054b312787

--94eb2c047922283853054b312787
Content-Type: text/plain; charset=UTF-8

---------- Forwarded message ----------
From: Andrew Poelstra <apoelstra@wpsoftware.net>
Date: Mon, Mar 20, 2017 at 5:11 PM
Subject: [Mimblewimble] Lightning in Scriptless Scripts
To: mimblewimble@lists.launchpad.net


In my last post about scriptless scripts [2] I described a way to do
deniable atomic swaps by pre-sharing a difference of signatures. This
had the limitation that it required at least one party to be shared
between the signatures, allowed only pairwise linking, and required
both signatures to cover data that is known at the time of setup.
Linking a multi-hop Lightning channel with these constraints has proved
difficult.

* * *

Recently I've found a different construction that behaves much more like
a hash preimage challenge, and this can actually be used for Lightning.
Further, it supports reblinding, so you can learn a preimage but hide
which one you're looking for. (Ethan, one might actually overlap with
TumbleBit, sorry :)).

It works like this. We'll treat x -> xG as a hash function, so x is the
preimage of xG. There are two separate but related things I can do: (a)
construct a signature which reveals the preimage; or (b) create a
"pre-signature" which can be turned into a signature with the help of
the preimage.

Here's how it works: suppose I send xG to Rusty and he wants to send
me coins conditional on my sending him x. Lets say I have key P1 and
nonce R1; he has key P2 and nonce R2. Together we're going to make a
multisignature with key P1 + P2 and Rusty is going to set things up
so that I can't complete the signature without telling him x.

Here we go.

  0. We agree somehow on R1, R2, P1, P2.

  1. We can both compute a challenge e = H(P1 + P2 || R1 + R2 || tx).

  2. I send s' = k1 - x - x1e, where R1 = k1G and P1 = x1G. Note he
     can verify I did so with the equation s'G = R1 - xG - eP1.

  3. He now sends me s2 = k2 - x2e, which is his half of the multisig.

  4. I complete the sig by adding s1 = k1 - x1e. The final sig is
     (s1 + s2, R1 + R2).

Now as soon as this signature gets out, I can compute x = s1 - s'.

* * *

Ok, pretty nifty. But now suppose Rusty wants to receive coins conditioned
on him revealing x, say, because he's a middle hop in a Lightning channel.
You might think he could act the same as I did in step (2), computing
s' = k1 - x - x1e, but actually he can't, because he doesn't know x himself!
All good. Instead he does the following.

To put names on things, let's say he's taking coins from Tadge. The
protocol is almost the same as above.

  0. They agree somehow on R1, R2, P1, P2. Tadge's key and nonce are
     R1 and P1, but there's a catch: P1 = x1G as before, but now
     R1 - xG = k1G. That is, his nonce is offset by k1G.

  1. They can both compute a challenge e = H(P1 + P2 || R1 + R2 || tx).

  2. Tadge sends the "presignature" s' = k1 - x1e. Rusty can verify this
     with the equation s'G = R1 - xG - eP1.

  3. Now whenever Rusty obtains x, he can compute s1 = s' - x, which is
     Tadge's half of the final signature.

  4. Rusty computes s2 himself and completes the signature.

* * *

Ok, even cooler. But the real Rusty complained about these stories, saying
that it's a privacy leak for him to use the same xG with me as he used with
Tadge. In a onion-routed Lightning channel, this xG-reuse would let all
any two participants in a path figure out that they were in one path, if
they were colluding, even if they weren't directly connected.

No worries, we can fix this very simply. Rusty chooses a reblinding factor
rG. I give him x, as before, but what Tadge demands from him is (x + r).
(I give xG to Rusty as a challenge; he forwards this as xG + rG to Tadge.)
Since Rusty knows r he's able to do the translation. The two challenges
appear uniformly independently random to any observers.

* * *

Let's put this together into my understanding of how Lightning is supposed
to work. Suppose Andrew is trying to send coins to Drew, through Bob and
Carol. He constructs a path

  A --> B --> C --> D

where each arrow is a Lightning channel. Only Andrew knows the complete
path, and is onion-encrypting his connections to each participant (who
know the next and previous participants, but that's it).

He obtains a challenge T = xG from D, and reblinding factors U and V
from B and C. Using the above tricks,

  1. A sends coins to B contingent on him learning the discrete logarithm
     of T + U + V.

  2. B sends coins to C contingent on him learning the discrete logarithm
     of T + V. (He knows the discrete log of U, so this is sufficient for
     him to meet Andrew's challenge.)

  3. C sends to D contingent on him learning the discrete log of T, which
     is D's original challenge. Again, because C knows the discrete log
     of V, this is sufficient for her to meet B's challenge.

The resulting path consists of transactions which are signed with single
uniformly random independent Schnorr signatures. Even though they're all
part of an atomic Lightning path.

* * *

Note that the s' values need to be re-communicated every time the
transaction
changes (as does the nonce). Because it depends on the other party's nonce,
this might require an additional round of interaction per channel update.

Note also that nothing I've said depends at all on what's being signed. This
means this works just as well for MimbleWimble as it would for
Bitcoin+Schnorr
as it would for Monero (with a multisig ring-CT construction) as it would
for Ethereum+Schnorr. Further, it can link transactions across chains.


I'm very excited about this.

Cheers
Andrew


[1] https://lists.launchpad.net/mimblewimble/msg00036.html


--
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
       --Joanna Newsom


--
Mailing list: https://launchpad.net/~mimblewimble
Post to     : mimblewimble@lists.launchpad.net
Unsubscribe : https://launchpad.net/~mimblewimble
More help   : https://help.launchpad.net/ListHelp


-- 
- Bryan
http://heybryan.org/
1 512 203 0507

--94eb2c047922283853054b312787
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><div class=3D"gmail_quote">---------- Forwarded messag=
e ----------<br>From: <span class=3D"gmail_sendername">Andrew Poelstra</spa=
n> <span dir=3D"ltr">&lt;<a href=3D"mailto:apoelstra@wpsoftware.net">apoels=
tra@wpsoftware.net</a>&gt;</span><br>Date: Mon, Mar 20, 2017 at 5:11 PM<br>=
Subject: [Mimblewimble] Lightning in Scriptless Scripts<br>To: <a href=3D"m=
ailto:mimblewimble@lists.launchpad.net">mimblewimble@lists.launchpad.net</a=
><br><br><br><br>
<br>
<br>
In my last post about scriptless scripts [2] I described a way to do<br>
deniable atomic swaps by pre-sharing a difference of signatures. This<br>
had the limitation that it required at least one party to be shared<br>
between the signatures, allowed only pairwise linking, and required<br>
both signatures to cover data that is known at the time of setup.<br>
Linking a multi-hop Lightning channel with these constraints has proved<br>
difficult.<br>
<br>
* * *<br>
<br>
Recently I&#39;ve found a different construction that behaves much more lik=
e<br>
a hash preimage challenge, and this can actually be used for Lightning.<br>
Further, it supports reblinding, so you can learn a preimage but hide<br>
which one you&#39;re looking for. (Ethan, one might actually overlap with<b=
r>
TumbleBit, sorry :)).<br>
<br>
It works like this. We&#39;ll treat x -&gt; xG as a hash function, so x is =
the<br>
preimage of xG. There are two separate but related things I can do: (a)<br>
construct a signature which reveals the preimage; or (b) create a<br>
&quot;pre-signature&quot; which can be turned into a signature with the hel=
p of<br>
the preimage.<br>
<br>
Here&#39;s how it works: suppose I send xG to Rusty and he wants to send<br=
>
me coins conditional on my sending him x. Lets say I have key P1 and<br>
nonce R1; he has key P2 and nonce R2. Together we&#39;re going to make a<br=
>
multisignature with key P1 + P2 and Rusty is going to set things up<br>
so that I can&#39;t complete the signature without telling him x.<br>
<br>
Here we go.<br>
<br>
=C2=A0 0. We agree somehow on R1, R2, P1, P2.<br>
<br>
=C2=A0 1. We can both compute a challenge e =3D H(P1 + P2 || R1 + R2 || tx)=
.<br>
<br>
=C2=A0 2. I send s&#39; =3D k1 - x - x1e, where R1 =3D k1G and P1 =3D x1G. =
Note he<br>
=C2=A0 =C2=A0 =C2=A0can verify I did so with the equation s&#39;G =3D R1 - =
xG - eP1.<br>
<br>
=C2=A0 3. He now sends me s2 =3D k2 - x2e, which is his half of the multisi=
g.<br>
<br>
=C2=A0 4. I complete the sig by adding s1 =3D k1 - x1e. The final sig is<br=
>
=C2=A0 =C2=A0 =C2=A0(s1 + s2, R1 + R2).<br>
<br>
Now as soon as this signature gets out, I can compute x =3D s1 - s&#39;.<br=
>
<br>
* * *<br>
<br>
Ok, pretty nifty. But now suppose Rusty wants to receive coins conditioned<=
br>
on him revealing x, say, because he&#39;s a middle hop in a Lightning chann=
el.<br>
You might think he could act the same as I did in step (2), computing<br>
s&#39; =3D k1 - x - x1e, but actually he can&#39;t, because he doesn&#39;t =
know x himself!<br>
All good. Instead he does the following.<br>
<br>
To put names on things, let&#39;s say he&#39;s taking coins from Tadge. The=
<br>
protocol is almost the same as above.<br>
<br>
=C2=A0 0. They agree somehow on R1, R2, P1, P2. Tadge&#39;s key and nonce a=
re<br>
=C2=A0 =C2=A0 =C2=A0R1 and P1, but there&#39;s a catch: P1 =3D x1G as befor=
e, but now<br>
=C2=A0 =C2=A0 =C2=A0R1 - xG =3D k1G. That is, his nonce is offset by k1G.<b=
r>
<br>
=C2=A0 1. They can both compute a challenge e =3D H(P1 + P2 || R1 + R2 || t=
x).<br>
<br>
=C2=A0 2. Tadge sends the &quot;presignature&quot; s&#39; =3D k1 - x1e. Rus=
ty can verify this<br>
=C2=A0 =C2=A0 =C2=A0with the equation s&#39;G =3D R1 - xG - eP1.<br>
<br>
=C2=A0 3. Now whenever Rusty obtains x, he can compute s1 =3D s&#39; - x, w=
hich is<br>
=C2=A0 =C2=A0 =C2=A0Tadge&#39;s half of the final signature.<br>
<br>
=C2=A0 4. Rusty computes s2 himself and completes the signature.<br>
<br>
* * *<br>
<br>
Ok, even cooler. But the real Rusty complained about these stories, saying<=
br>
that it&#39;s a privacy leak for him to use the same xG with me as he used =
with<br>
Tadge. In a onion-routed Lightning channel, this xG-reuse would let all<br>
any two participants in a path figure out that they were in one path, if<br=
>
they were colluding, even if they weren&#39;t directly connected.<br>
<br>
No worries, we can fix this very simply. Rusty chooses a reblinding factor<=
br>
rG. I give him x, as before, but what Tadge demands from him is (x + r).<br=
>
(I give xG to Rusty as a challenge; he forwards this as xG + rG to Tadge.)<=
br>
Since Rusty knows r he&#39;s able to do the translation. The two challenges=
<br>
appear uniformly independently random to any observers.<br>
<br>
* * *<br>
<br>
Let&#39;s put this together into my understanding of how Lightning is suppo=
sed<br>
to work. Suppose Andrew is trying to send coins to Drew, through Bob and<br=
>
Carol. He constructs a path<br>
<br>
=C2=A0 A --&gt; B --&gt; C --&gt; D<br>
<br>
where each arrow is a Lightning channel. Only Andrew knows the complete<br>
path, and is onion-encrypting his connections to each participant (who<br>
know the next and previous participants, but that&#39;s it).<br>
<br>
He obtains a challenge T =3D xG from D, and reblinding factors U and V<br>
from B and C. Using the above tricks,<br>
<br>
=C2=A0 1. A sends coins to B contingent on him learning the discrete logari=
thm<br>
=C2=A0 =C2=A0 =C2=A0of T + U + V.<br>
<br>
=C2=A0 2. B sends coins to C contingent on him learning the discrete logari=
thm<br>
=C2=A0 =C2=A0 =C2=A0of T + V. (He knows the discrete log of U, so this is s=
ufficient for<br>
=C2=A0 =C2=A0 =C2=A0him to meet Andrew&#39;s challenge.)<br>
<br>
=C2=A0 3. C sends to D contingent on him learning the discrete log of T, wh=
ich<br>
=C2=A0 =C2=A0 =C2=A0is D&#39;s original challenge. Again, because C knows t=
he discrete log<br>
=C2=A0 =C2=A0 =C2=A0of V, this is sufficient for her to meet B&#39;s challe=
nge.<br>
<br>
The resulting path consists of transactions which are signed with single<br=
>
uniformly random independent Schnorr signatures. Even though they&#39;re al=
l<br>
part of an atomic Lightning path.<br>
<br>
* * *<br>
<br>
Note that the s&#39; values need to be re-communicated every time the trans=
action<br>
changes (as does the nonce). Because it depends on the other party&#39;s no=
nce,<br>
this might require an additional round of interaction per channel update.<b=
r>
<br>
Note also that nothing I&#39;ve said depends at all on what&#39;s being sig=
ned. This<br>
means this works just as well for MimbleWimble as it would for Bitcoin+Schn=
orr<br>
as it would for Monero (with a multisig ring-CT construction) as it would<b=
r>
for Ethereum+Schnorr. Further, it can link transactions across chains.<br>
<br>
<br>
I&#39;m very excited about this.<br>
<br>
Cheers<br>
Andrew<br>
<br>
<br>
[1] <a href=3D"https://lists.launchpad.net/mimblewimble/msg00036.html" rel=
=3D"noreferrer" target=3D"_blank">https://lists.launchpad.net/<wbr>mimblewi=
mble/msg00036.html</a><br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
<br>
<br>
<br>
--<br>
Andrew Poelstra<br>
Mathematics Department, Blockstream<br>
Email: apoelstra at <a href=3D"http://wpsoftware.net" rel=3D"noreferrer" ta=
rget=3D"_blank">wpsoftware.net</a><br>
Web:=C2=A0 =C2=A0<a href=3D"https://www.wpsoftware.net/andrew" rel=3D"noref=
errer" target=3D"_blank">https://www.wpsoftware.net/<wbr>andrew</a><br>
<br>
&quot;A goose alone, I suppose, can know the loneliness of geese<br>
=C2=A0who can never find their peace,<br>
=C2=A0whether north or south or west or east&quot;<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0--Joanna Newsom<br>
<br>
</font></span><br>--<br>
Mailing list: <a href=3D"https://launchpad.net/~mimblewimble" rel=3D"norefe=
rrer" target=3D"_blank">https://launchpad.net/~<wbr>mimblewimble</a><br>
Post to=C2=A0 =C2=A0 =C2=A0: <a href=3D"mailto:mimblewimble@lists.launchpad=
.net">mimblewimble@lists.launchpad.<wbr>net</a><br>
Unsubscribe : <a href=3D"https://launchpad.net/~mimblewimble" rel=3D"norefe=
rrer" target=3D"_blank">https://launchpad.net/~<wbr>mimblewimble</a><br>
More help=C2=A0 =C2=A0: <a href=3D"https://help.launchpad.net/ListHelp" rel=
=3D"noreferrer" target=3D"_blank">https://help.launchpad.net/<wbr>ListHelp<=
/a><br>
<br></div><br><br clear=3D"all"><div><br></div>-- <br><div class=3D"gmail_s=
ignature" data-smartmail=3D"gmail_signature">- Bryan<br><a href=3D"http://h=
eybryan.org/" target=3D"_blank">http://heybryan.org/</a><br>1 512 203 0507<=
/div>
</div>

--94eb2c047922283853054b312787--
--94eb2c047922283858054b312789
Content-Type: application/pgp-signature; name="signature.asc"
Content-Disposition: attachment; filename="signature.asc"
Content-Transfer-Encoding: base64
X-Attachment-Id: e57cf51814471aed_0.0.1

LS0tLS1CRUdJTiBQR1AgU0lHTkFUVVJFLS0tLS0NCg0KaVFFY0JBRUJDQUFHQlFKWTBGTnpBQW9K
RU1XSTFqemtHNWZCbzZrSC8zZEw5M01YOWZaK0pZbEJtY1dpcTdNNg0KZFJwRnZMWXc4SFhvNnRN
UCtsTmRVMndpYW0wbkpnMVJXZ2IrUHNxbmVNNXcyM0RMbEFCcW8yYlpkQmJtcEdDag0KL1Ewdysz
VHhHTk9xU05TdkV0QS80SS9MczcxOEdmeVFmTkFIb1FuS3lXYjljc01OY3grVHZMNDJidjFndGQ1
SA0KUEtELzZqNmQwRWYwSmVFSzdyVHdZaVVzZnV1ZWhiOEN4TE9KdERJVzJQZ25LWkU5amhIRUxm
MWorOExuU1JzUQ0KWnU3VjIzQXhXaHdnd2hOc05wQWRzOWpmSTdzR1hid3VDNVd2cWljaDRNRXNE
dXIyc2VURFRYSHNBT2tNa1VUQQ0KUkJSM1RBbUFzUmFEMG5jN0tRQm0yMkNnOGlqTjFNcnVlMy8v
T0M5VENzWW8wU2ErSk1WbUYrUHhXeVZkdUhzPQ0KPWxyNXkNCi0tLS0tRU5EIFBHUCBTSUdOQVRV
UkUtLS0tLQ0K
--94eb2c047922283858054b312789--