mimblewimble team mailing list archive

[Oleg Andreev <oleganza@xxxxxxxxx>]

Andy, you mention a "20% space hit" for sound commitments. Do you mean the double space required by digit commitments (2 points vs 1)? If that's so, I'm investigating a pretty neat trick to save even that space, so the total overhead is probably just one point (compared to pedersen commitments w/o your 24% optimization).

The idea is this: all digits must share the same blinding factor and a commitment to a pure blinding factor is shared among all of them. To prevent bruteforce discovery of the digits by cancelling the blinding part via subtraction of digits, each digit would use a different generator point (precomputed).

So instead of these digit commitments (consisting of 2 points each):

(d_i*H + f_i*G, f_i*J)

you'd have these:

(d_i*H + f*G_i, f*J)

where f*J is the same point shared by all digits. G_i can be precomputed. For 64-bit numbers and base-4 you need at most 32 such generators.

The draft of this proposal is in our git repo, we are still working on review and a proof of correctness and security:

1. Pre-computed generators: https://github.com/chain/chain/blob/confidential-spec/docs/protocol/specifications/ca.md#generators (we only generated 31 of them, 32nd is the ed25519 base point).
2. Verifying range proofs using these generators: https://github.com/chain/chain/blob/confidential-spec/docs/protocol/specifications/ca.md#validate-value-range-proof

Would love to hear your thoughts on that!
Oleg.

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