← Back to team overview

mimblewimble team mailing list archive

Re: To Schnorr or not to Schnorr

 

Caught Andrew on #mimblewimble: bottom line is the libsecp256k1-zkp Schnorr implementation doesn't commit to the pubkey (so not a proof-of-knowledge) and its use is discouraged. But a better impl is expected in not too long in libsecp.

So I'm leaning toward sticking with ECDSA for now, and switch when Schnorr is ready. We can just build with that in mind. For John Tromp's double-handshake transaction scheme we could introduce a trait with the Schnorr operations we need exposed and just have a mocked implementation, so we're not fully blocked on that front.

- Igno

-------- Original Message --------
Subject: Re: [Mimblewimble] To Schnorr or not to Schnorr
Local Time: March 27, 2017 11:11 AM
UTC Time: March 27, 2017 6:11 PM
From: igno.peverell@xxxxxxxxxxxxxx
To: Andrew Poelstra <apoelstra@xxxxxxxxxxxxxx>
mimblewimble@xxxxxxxxxxxxxxxxxxx <mimblewimble@xxxxxxxxxxxxxxxxxxx>

And what about starting with the zkp Schnorr impl instead of ECDSA? :) Again, assuming a dev/test setting.

- Igno

-------- Original Message --------
Subject: Re: [Mimblewimble] To Schnorr or not to Schnorr
Local Time: March 27, 2017 6:40 AM
UTC Time: March 27, 2017 1:40 PM
From: apoelstra@xxxxxxxxxxxxxx
To: Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>
mimblewimble@xxxxxxxxxxxxxxxxxxx <mimblewimble@xxxxxxxxxxxxxxxxxxx>

My feeling is that we should start with unconditionally sound commitments
rather than trying to switch later, though the idea is clever. When Tim
wrote that paper we (meaning myself and the other secp devs, maybe Tim
knew more) didn't know how efficient it would be to create perfectly
sound rangeproofs (we suspected it would double the size).

My reasoning is that it's hard to say exactly when "we get there" regarding
needing to protect against quantum inflators.

In fact, there is an optimization of CT in my Confidential Assets paper[1]
which gives a 25% or so space reduction ... adding unconditional soundness
to that exactly erases the improvement, so the result is a wash :).

Without the optimization, you can still get soundness with a 20% space hit,
still not bad, and this requires very few/simple code changes to CT (so I
can do it myself for grin even if we haven't gotten around to it upstream
by the time we want it).

[1] http://fc17.ifca.ai/bitcoin/schedule.html

On Sun, Mar 26, 2017 at 06:26:06PM -0400, Ignotus Peverell wrote:
> Thanks for elaborating!
>
> So in a dev/testnet context, you still think we should go for ECDSA first instead of using the secp-zkp Schnorr implementation? The latter would allow us to experiment earlier with multlsig, lightning, etc.
>
> Speaking of resistance to a broken discrete log, have you looked at Switch commitments [1]? May be a good way to protect older UTXOs when/if we get there.
>
> - Igno
>
> [1] https://people.mmci.uni-saarland.de/~truffing/papers/switch-commitments.pdf
>
> -------- Original Message --------
> Subject: Re: [Mimblewimble] To Schnorr or not to Schnorr
> Local Time: March 26, 2017 11:20 AM
> UTC Time: March 26, 2017 6:20 PM
> From: apoelstra@xxxxxxxxxxxxxx
> To: Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>
> mimblewimble@xxxxxxxxxxxxxxxxxxx <mimblewimble@xxxxxxxxxxxxxxxxxxx>
>
> Ok, as long as it's only dev/testnet I'm happy. We have to be sure that
> our ECDSA signatures sign the kernel itself, which will make it a "good
> enough" proof of knowledge ... in the same sense that ECDSA is a "good
> enough" signature despite having no formal proof of security.
>
> The reason being good enough for Bitcoin might not be good enough for us
> is that Bitcoin uses signatures as signatures, whereas we actually need
> them to be a proof of knowledge discrete logarithm. In particular we
> need to be protected from related-key attacks which aren't covered by
> the ordinary notion of signature security.
>
> More generally, in Bitcoin the signature covers transaction data. Simple.
> In MW the transaction data is sorta coded into the public key and the
> signature does double-duty as a proof-of-knowledge declaring that the
> holders of the public key consent to having this key be constructed
> and as a proof-of-zero-value declaring that the transaction has no net
> inflation.
>
> This is pretty far aware from the security definition of a signature.
>
> I may be being a bit paranoid; Bitcoin + BIP32 also needs protection from
> related-key attacks, and it gets this sorta-by-accident by virtue of its
> signatures signing input txids which then commit to the signing keys. As
> far as I'm aware nobody has exploited the algebraic structure of ECDSA
> to get around this, and I've spent a long time trying to.
>
> As a side note, I would like eventually to replace our rangeproofs and
> signatures with proofs of equality of discrete log. It will increase
> the size of each kernel by one curvepoint and the size of each rangeproof
> by $n_digits curvepoints. In exchange we get provable non-inflation
> _even in the case that discrete log is broken_.
>
> There's a fairly trivial modification to Schnorr that will get us this,
> the signature and PoK security are unchanged but the zero-knowledgeness
> is weakened from perfect to computational (i.e. a quantum computer will
> be able to deanonymize amounts). I highly doubt this is possible for ECDSA.
>
> Cheers
>
> Andrew
>
> On Sat, Mar 25, 2017 at 05:51:43PM -0400, Ignotus Peverell wrote:
> > Thanks a lot for the reply and details. I'd like to explore this a little more, to avoid stupid mistakes (most likely caused by me).
> >
> > Regarding ECDSA, if the implementation is good enough for bitcoin, it seems it'd be good enough for us. Or I'm missing something? Also what are the implications of ECDSA not being a PoK? I didn't realize we needed a full PoK protocol for kernels (as opposed to just any sig).
> >
> > Regarding Schnorr, as long as it's only for dev/testnet the current implementation is functional, we can just fix multisig. And even if a new libsecp makes incompatible signatures, we can just wipe whatever testnet we're on (assuming we're that far). So why wouldn't that be a better placeholder? We can still consider upstream libsecp Schnorr a blocker.
> >
> > Thanks!
> > - Igno
> >
>
> --
> Andrew Poelstra
> Mathematics Department, Blockstream
> Email: apoelstra at wpsoftware.net
> Web: https://www.wpsoftware.net/andrew
>
> "A goose alone, I suppose, can know the loneliness of geese
> who can never find their peace,
> whether north or south or west or east"
> --Joanna Newsom

> --
> Mailing list: https://launchpad.net/~mimblewimble
> Post to : mimblewimble@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~mimblewimble
> More help : https://help.launchpad.net/ListHelp

--
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
who can never find their peace,
whether north or south or west or east"
--Joanna Newsom

References