Rusty Russell [ARCHIVE] on Nostr: 📅 Original date posted:2015-11-27 📝 Original message: Anthony Towns <aj at ...

📅 Original date posted:2015-11-27
📝 Original message:
Anthony Towns <aj at erisian.com.au> writes:
> 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.

Yes, this is very clever. But since it's slow, insecure or both, I
don't think we should go for it.

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

I don't think this works? We can't provide the signatures in the
scriptPubkey, since that requires them signing themselves. We can't
have them provide it in the scriptSig, since theres no "do these have
the same r value" operator in script. All those ops got disabled :(

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

Yes, this is a nice optimization.

Cheers,
Rusty.