[Lightning-dev] Better privacy with SNARKs

[Anthony Towns]

On Fri, Nov 20, 2015 at 05:44:15PM +1000, Anthony Towns wrote:
> > 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!

And wow, it looks like you can do it without adding opcodes to bitcoin.

Two approaches to forcing someone to reveal the private key corresponding
to secp256k1 public key P. Number one, which Greg Maxwell came up with:

  OP_SIZE 57 OP_LESSTHANOREQUAL OP_VERIFY <P> OP_CHECKSIGVERIFY

To satisfy this script, you have to generate a signature with P, that
produces <r> and <s> parameters for the signature that have a combined
total of 15 leading zero bytes (or more). There is a known <r> value with
11 leading zero bytes though: g^(1/2), so you need to brute force about
2**32=4B <s> parameters to get a valid signature, and that's just modifing
the transaction, hashing it, and doing modular arithmetic ops.  It might
mean paying for a few seconds use of dedicated mining hardware though.

Using that <r> value reveals the secret key p: p = (2s - h)/r (mod O(g)).

If you want to cheat, you can brute force a secret key N with
corresponding public key r with as many leading zero bytes as possible.
Greg Maxwell thinks grinding r values at a rate 0.08 microseconds per
try is practical, so that's ~10e6/second. Doing that on 2000 8-core
machines for abut a week gets you an r-value with 7 leading 0-bytes.
Getting 8 leading 0-bytes might take 20k machines and four months.

With 7 leading zeroes in r, you still need 8 leading zeroes in s, which
would require about 213,000 GH/s worth of mining hardware running for 24
hours to achieve. With 8 leading zeroes in r, you'd only need 7 leading
zeroes in s, which you could get in 1 hour with 20GH/s of mining hardware.



The alternative approach, which andytoshi and I came up with
independently is a lot more complicated:

  revealP( Q, R, sigA, sigB, sigC ) {
    check_multisig_verify(2, P, R, 2, sigA, sigB); code_separtor();
    check_multisig_verify(2, Q, R, 2, sigA, sigC); code_separtor();
    check_multisig_verify(2, P, Q, 2, sigC, sigB);
  }

If sigA, sigB and sigC all share the same r and SIGHASH settings, coming
up with secret keys Q' and R' is straightforward (Q'=P'-(h2-h1)/r,
R'=P'-(h2-h3)/r, where h1, h2 and h3 are the transaction hashes for
the various steps), and you have two valid sigs by key P with the same
r value, letting you calculate P'. If you don't use the same r value,
or use different sighash types between the signatures, coming up with
valid keys and sigs seems to require doing discrete logs on the elliptic
curve, so should be intractable. (In particular, I don't think throwing
lots of hashpower at the problem helps at all)

But if you have to drop the transaction to the blockchain, it's six
sigops, which combined with the two other signatures an HTLC needs to
be usable (one for A on timeout, one for B on success), means a total
of 8 sigops per output, which is about equivalent to 400B per output
given the relationship between the bytes-per-block and sigops-per-block
limits. Yikes. Translating from pseudocode into script is a little
hard too.


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

Greg Maxwell also pointed out you can also do this faster while still
being secure; assuming Q was the public key from the incoming HTLC, and P
is the public key you'll use for the outgoing HTLC, and r is your secret:

 p = q + r
 P = (q+r)*G = q*G + r*G = Q + r*G

Given Q is already known, calculating P just requires multiplying the
base point and an addition, which is quicker than multiplying an arbitrary
point. And once you find out p, calculating q=p-r is obviously easy.

Cheers,
aj