From aj at erisian.com.au Thu Nov 26 11:15:16 2015 From: aj at erisian.com.au (Anthony Towns) Date: Thu, 26 Nov 2015 21:15:16 +1000 Subject: [Lightning-dev] Better privacy with SNARKs In-Reply-To: <20151120074415.GA24674@navy> References: <877fldmozx.fsf@rustcorp.com.au> <20151120074415.GA24674@navy> Message-ID: <20151126111516.GA21851@sapphire.erisian.com.au> 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

OP_CHECKSIGVERIFY To satisfy this script, you have to generate a signature with P, that produces and parameters for the signature that have a combined total of 15 leading zero bytes (or more). There is a known value with 11 leading zero bytes though: g^(1/2), so you need to brute force about 2**32=4B 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 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