Bryan Bishop via bitcoin-dev

2017-03-20 22:36:04 UTC

Permalink

---------- Forwarded message ----------Raw Message

From: Andrew Poelstra <***@wpsoftware.net>

Date: Mon, Mar 20, 2017 at 5:11 PM

Subject: [Mimblewimble] Lightning in Scriptless Scripts

To: ***@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 : ***@lists.launchpad.net

Unsubscribe : https://launchpad.net/~mimblewimble

More help : https://help.launchpad.net/ListHelp

--

- Bryan

http://heybryan.org/

1 512 203 0507

- Bryan

http://heybryan.org/

1 512 203 0507