From aj at erisian.com.au  Fri Nov 27 04:42:19 2015
From: aj at erisian.com.au (Anthony Towns)
Date: Fri, 27 Nov 2015 14:42:19 +1000
Subject: [Lightning-dev] Better privacy with SNARKs
In-Reply-To: <87610ort9e.fsf@rustcorp.com.au>
References: <877fldmozx.fsf@rustcorp.com.au>
	<CAE8CtV=1uL-pcyhznYZMp4wyV1b6JcoeCJec9PBB9_Ow1VBjjQ@mail.gmail.com>
	<20151120074415.GA24674@navy>
	<20151126111516.GA21851@sapphire.erisian.com.au>
	<87610ort9e.fsf@rustcorp.com.au>
Message-ID: <20151127044219.GA4443@sapphire.erisian.com.au>

On Fri, Nov 27, 2015 at 02:25:09PM +1030, Rusty Russell wrote:
> Anthony Towns <aj at erisian.com.au> writes:
> > 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.  

The scriptPubkey has the pubkey P, and a whole mess of stack operations
to implement the function above; the scriptSig just has Q, R and the
three signatures.

> We can't
> have them provide it in the scriptSig, since theres no "do these have
> the same r value" operator in script.

There's six sig ops, but only three different signatures. Getting the
various combinations to have the same signature forces the same r value
between each of the signatures, without needing a separate op to check
it explicitly.

It's mathematically possible to come up with Q, R, sigA, sigB, sigC where
sigA.r, sigB.r and sigC.r are all different; but it requires being able
to come up with a transaction with a particular hash, or calculating the
discrete log of a weird value to do so, so should be safely intractable.

Cheers,
aj