From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 03B04B7D for ; Mon, 20 Mar 2017 22:36:08 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ot0-f169.google.com (mail-ot0-f169.google.com [74.125.82.169]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B96D614F for ; Mon, 20 Mar 2017 22:36:06 +0000 (UTC) Received: by mail-ot0-f169.google.com with SMTP id i1so141792854ota.3 for ; Mon, 20 Mar 2017 15:36:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=k/bONHc+xGKMQLiKxdofC3wHE+Sy6CM5WWFgWk9C2nQ=; b=JDeKWvxx6eXhD3dchwovMAlEqBaLUWs3F+XNgEZcowQ/1yo/m1ZXldnPkwVj0AE+hX D+TbBaUVOMyHUOWdtY/V8CwIvYHS56lL3WeRp8PbfrYgQ9FbOiC4kgSGAcwoqgvpJFej 31RPs8cmU+Ts2pJVGCcGcUnDZc95ZY33pHptxezHnEftJudjdDODD+K7z4rCse4D+xGw UbvSnUu6BVHTHjpUAz85m/SyBBO03212QJavzU10ADhpEY+5HK7Og61o0rTsXqSx0FMf Jzc2XWaYHXSka7X0QlXft33ILoq12n4pitZrfqnAwULM8QeUcBkAstq6PU5k0x3FuD/t Bv4w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=k/bONHc+xGKMQLiKxdofC3wHE+Sy6CM5WWFgWk9C2nQ=; b=g3k8ySxtJKR3MnvbN8coHg7ErdJGwVvJ6c3hdlILq+IZ03e3I6uURR6p4QYvI4GRBb dE4cLUvpi3XyPdUoo56JdwiDHBL0GKXLRVd84/I5xmcxQ8qfRz/h3EkMKTDEarKJVs6F Ex9m/YAcIMxiBNoURiZUc6miWx3fAK27laXgrnLwhBLbc8lX2SbVuGj+tbJEqqh9S5uR m3Mq7yzywzyWVKv/B8IHKMxxb6/AcvXk+Sdz4laGNbFexAy3ZMFfobcWsr7BZjjR9rBm Zb6dzNF7o2y8L66J4z63XwYsVzSixwgKaUu+Zd3uTLLTZMajaX5i7B929gPFMbnCEP4L lSBA== X-Gm-Message-State: AFeK/H0UgdIE5HOU6hUBrtdkwDwmGo36UxCNI63ZGZdwiFa5S5aJEpU1fuXSALd4ljASSp29y6sl7MOlikw2fQ== X-Received: by 10.157.47.38 with SMTP id h35mr15057293otb.130.1490049365942; Mon, 20 Mar 2017 15:36:05 -0700 (PDT) MIME-Version: 1.0 Received: by 10.157.37.115 with HTTP; Mon, 20 Mar 2017 15:36:04 -0700 (PDT) In-Reply-To: <20170320221101.GC10783@boulet.lan> References: <20170320221101.GC10783@boulet.lan> From: Bryan Bishop Date: Mon, 20 Mar 2017 17:36:04 -0500 Message-ID: To: Bitcoin Dev , Bryan Bishop Content-Type: multipart/mixed; boundary=94eb2c047922283858054b312789 X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [bitcoin-dev] Fwd: [Mimblewimble] Lightning in Scriptless Scripts X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 20 Mar 2017 22:36:08 -0000 --94eb2c047922283858054b312789 Content-Type: multipart/alternative; boundary=94eb2c047922283853054b312787 --94eb2c047922283853054b312787 Content-Type: text/plain; charset=UTF-8 ---------- Forwarded message ---------- From: Andrew Poelstra 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

---------- Forwarded messag= e ----------
From: Andrew Poelstra <apoels= tra@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 lik= e
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 hel= p 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.

=C2=A0 0. We agree somehow on R1, R2, P1, P2.

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

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

=C2=A0 3. He now sends me s2 =3D k2 - x2e, which is his half of the multisi= g.

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

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

Ok, pretty nifty. But now suppose Rusty wants to receive coins conditioned<= br> on him revealing x, say, because he's a middle hop in a Lightning chann= el.
You might think he could act the same as I did in step (2), computing
s' =3D 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.

=C2=A0 0. They agree somehow on R1, R2, P1, P2. Tadge's key and nonce a= re
=C2=A0 =C2=A0 =C2=A0R1 and P1, but there's a catch: P1 =3D x1G as befor= e, but now
=C2=A0 =C2=A0 =C2=A0R1 - xG =3D k1G. That is, his nonce is offset by k1G.
=C2=A0 1. They can both compute a challenge e =3D H(P1 + P2 || R1 + R2 || t= x).

=C2=A0 2. Tadge sends the "presignature" s' =3D k1 - x1e. Rus= ty can verify this
=C2=A0 =C2=A0 =C2=A0with the equation s'G =3D R1 - xG - eP1.

=C2=A0 3. Now whenever Rusty obtains x, he can compute s1 =3D s' - x, w= hich is
=C2=A0 =C2=A0 =C2=A0Tadge's half of the final signature.

=C2=A0 4. Rusty computes s2 himself and completes the signature.

* * *

Ok, even cooler. But the real Rusty complained about these stories, saying<= br> 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<= br> 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.)<= br> 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 suppo= sed
to work. Suppose Andrew is trying to send coins to Drew, through Bob and Carol. He constructs a path

=C2=A0 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 =3D xG from D, and reblinding factors U and V
from B and C. Using the above tricks,

=C2=A0 1. A sends coins to B contingent on him learning the discrete logari= thm
=C2=A0 =C2=A0 =C2=A0of T + U + V.

=C2=A0 2. B sends coins to C contingent on him learning the discrete logari= thm
=C2=A0 =C2=A0 =C2=A0of T + V. (He knows the discrete log of U, so this is s= ufficient for
=C2=A0 =C2=A0 =C2=A0him to meet Andrew's challenge.)

=C2=A0 3. C sends to D contingent on him learning the discrete log of T, wh= ich
=C2=A0 =C2=A0 =C2=A0is D's original challenge. Again, because C knows t= he discrete log
=C2=A0 =C2=A0 =C2=A0of V, this is sufficient for her to meet B's challe= nge.

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

* * *

Note that the s' values need to be re-communicated every time the trans= action
changes (as does the nonce). Because it depends on the other party's no= nce,
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 sig= ned. This
means this works just as well for MimbleWimble as it would for Bitcoin+Schn= orr
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/mimblewi= mble/msg00036.html




--
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:=C2=A0 =C2=A0https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
=C2=A0who can never find their peace,
=C2=A0whether north or south or west or east"
=C2=A0 =C2=A0 =C2=A0 =C2=A0--Joanna Newsom


--
Mailing list: https://launchpad.net/~mimblewimble
Post to=C2=A0 =C2=A0 =C2=A0: mimblewimble@lists.launchpad.net
Unsubscribe : https://launchpad.net/~mimblewimble
More help=C2=A0 =C2=A0: https://help.launchpad.net/ListHelp<= /a>




--
- Bryan
http://heybryan.org/
1 512 203 0507<= /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--