mimblewimble team mailing list archive

[Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>]

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