[Lightning-dev] Better privacy with SNARKs

Anthony Towns aj at erisian.com.au
Fri Nov 20 07:44:15 UTC 2015


On Thu, Nov 19, 2015 at 01:16:57PM +0000, Mats Jerratsch wrote:
> Interesting, thanks for the write-up Anthony!

Glad I went ahead and implemented it as a snark before posting the idea
or you would have spoiled all the fun I had playing with snarkfront!

> 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.

Yeah. I think you could have a "stop-loss" condition, where any node that
gets cheated (ie, they have a proof that R2 gives them and R1 for H1,H2,X;
but they have an R2 that doesn't give them R1) can just publish all that
evidence, and everyone can immediately stop trusting snarks and so only
a small amount of money can actually be stolen from the system. But, yeah.

> ---------------
> 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.

So this is genius! And I swear I would have thought of it myself if
I could just get past my mental block on adding opcodes to bitcoin.
Honest, guv!

> 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.

Even better, given K1(Q,q) (q the public key provided by the merchant,
Q the merchant's secret, used to claim the payment and serving as a
receipt), you (as the consumer) can construct r2, .., rN by generating
random bits, and then generate

  q1 = q
  q2 = r2*q1
  q3 = r3*q2
  ...
  qN = rN*q[N-1]

and route your HTLC payable to qN at the first hop, q[N-1] at the second
all the way to q1 when it gets to the merchant. The merchant reveals
Q=Q1, and nodes calculate:

  Q2 = r2*Q1
  Q3 = r3*Q2
  ...
  QN = rN*Q[N-1]

to collect their payments. So the extra burden for keeping the payment
private falls entirely on the consumer, rather than the merchant. (Okay,
you had this point in your mail already essentially)

Hmm, I'm not sure if you can divide QN by (r2*..*rN) to get back to Q1,
but I think you can (the lowercase q's are the points on the elliptic
curve where division is hard, but the capital Q's are just numbers
in Z_n where n is the order of G on the curve, I think?). If you can,
you even get the original receipt/proof of payment!

Oh, _and_ you don't even having to reveal q1/Q to any intermediate hops
-- you could just pay to q[N-1] on the final hop and provide rN in the
onion message on the final hop. If you do that, nobody but the merchant
and the end consumer can calculate the proof of payment.

_And_ I think you could just use SHA(ECDH_SEC || 3) as the r values at
each stage rather than needing any additional entropy, or having to add
any significant data to the onion packets.

> 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.

There are a few "generic" crypto ops that might be useful to have; two
that come to mind are:

  <point> <multiplicand> <resultpoint> OP_CHECK_SECP256K1_MUL_VERIFY
    (enough for this, maybe lets you do ECDH on the blockchain,
     and allows you to commit to revealing a key on the blockchain)

  <signature> <pubkey> <message> OP_CHECK_INLINE_SIGNATURE_VERIFY
    (this would let you do atomic cross-chain swaps without knowing in
     advance who you're swapping with)

Maybe it'd make sense to combine them into a soft-forkable OP_CRYPTO_OP
that pulls the crypto operation id from the stack, then if the operation
is known, pulls the operands, and fails the script if the operands
don't add up. If the operation is unknown, mark it as non-standard but
acceptable for future soft-forkability...

On Fri, Nov 20, 2015 at 12:05:46PM +1030, Rusty Russell wrote:
> With the segregated witness proposal, introducing new opcodes is easy,
> so maybe someone would find a reason to prefer open-coding it like this?

I don't follow how segregated witness makes new opcodes any easier?

Cheers,
aj



More information about the Lightning-dev mailing list