From matsjj at gmail.com  Thu Nov 19 13:16:57 2015
From: matsjj at gmail.com (Mats Jerratsch)
Date: Thu, 19 Nov 2015 13:16:57 +0000
Subject: [Lightning-dev] Better privacy with SNARKs
In-Reply-To: <20151117211436.GA17583@debian>
References: <20151117211436.GA17583@debian>
Message-ID: <CAE8CtV=1uL-pcyhznYZMp4wyV1b6JcoeCJec9PBB9_Ow1VBjjQ@mail.gmail.com>

Interesting, thanks for the write-up Anthony!

Indeed, if we can somehow prove that R1 = R2 XOR X without revealing
R1 or R2, we can switch R in between the routing an arbitrary amount
of time. This would solve the last obvious privacy attack vector that
we have currently.

I feel like the way ZKPs are constructed, one has to be absolutely
certain everything is perfectly implemented to actually work out the
way we want it.

> A drawback is that you'd either (a) have to do all this on the merchant's
> side (not just sending SHA(R) to whoever wants to pay you, but sending
> SHA(R1), SHA(R2), SHA(R3), SHA(R4), X12, X23, X34, and three proofs,
> which would be pretty painful; or (b) you'd have to generate all the
> R secrets as a consumer, and you wouldn't get to use the fact that you
> know R as evidence that you paid the merchant.

I don't think (a) would be too much of a problem. I am playing around
with the idea of having a messaging system over the same route as the
actual payment. The data that needs to be communicated over regular
channels (QR, ...) would be limited to a rendezvous node and the
encrypted route from that node to the receiver. The sender can contact
the receiver over that route and include the encrypted route back for
further communications.

I also think that - given how young SNARKs still are - efficiency will
further be improved. Especially generation and verification of the
proof, such that it is no longer a major cost factor.

---------------

After a night of sleep and some reassurance with sipa, I thought about
something similar but with EC keys, that will allow us to do the same,
but without SNARKS.

If we would switch from preimage-hash verification to
privatekey-publickey, we can use the arithmetic operations inherited
from the elliptic curve field.

Assume two keypairs, K1(Q, q) and K2(R, r). Further we have a scalar
p, such that

r = p * q

and

R = r * G = ( p * q ) * G = p * ( q * G ) = p * Q.

You can therefore give someone Q, R and p and he is able to verify
that above conditions indeed holds true. For a sufficiently large p it
is not possible to derive that relationship within reasonable time
without p. If he ever gets to know q, he is able to directly compute r
as well.

So instead of making a payment towards a hash, we make a payment
towards a public key. If we ever get to know the private key, the
payment is deemed settled.

This will allow for following construction:

(1) Bob calculates a key pair he wants to receive a payment on
(2) Bob will give the public key Q to Alice
(3) Alice calculates a route, consisting of 10 hops
(4) Alice chooses x random large numbers N_x and calculates x public
keys, such that

Q_y = Q * N_x * N_x-1 * ... * N_y.

(5) Alice constructs an onion object and includes Q_y together with N_y

Each hop is able to translate the public key towards the corresponding
key for the next relay node, only Alice, with the knowledge of the set
N is able to relate the payment though.

There is one caveat. We are currently unable to enforce a payment with
a priv/pub key pair. We would need a new operator
OP_CHECKPRIVPUBKEYPAIR or similar that pops two items from the stack

<Private Key> <Public Key>

and replaces them with true/false. It could also be constructed in a
softfork-manner, where the stack is not touched and it only fails in
case the key pair is not correct.

Revealing the private key has the same effect as revealing a preimage.

Cheers
Mats