← Back to team overview

mimblewimble team mailing list archive

Re: [POLL] Perfectly hiding vs perfectly binding


On Wed, May 03, 2017 at 08:14:27PM -0400, Ignotus Peverell wrote:
> Hi all,
> I thought running a little poll could be fun and it's on a topic that may be more emotional than technical: in the advent of Quantum Computers, or even computers of infinite power, do we prefer transactions that are perfectly hiding (one will never be able to discover their value) or perfectly binding (one will never be able to steal or create money). It's really inconvenient, but it's been proven we can't have both.
> To vote, just reply with one of these 2 lines:
> [X] Perfectly hiding, privacy guarantees should remain true forever
> [X] Perfectly binding, one should never be able to break transaction integrity
> Because some arguments may be non-obvious, I'll flesh out a few.
> Why we'd really want perfectly binding transactions is straightforward: being able to create money out of thin air or stealing sounds pretty bad for any cryptocurrency. Note that most existing cryptocurrencies are sensitive to this right now: with a working and powerful Quantum Computer, you'd likely be able to steal a fair amount of bitcoins or even zcash. So there's a definite advantage in offering such strong integrity guarantees.
> On the other hand, QCs aren't going to happen overnight. We will likely have years (many experts say decades) to prepare. Also if it was to happen right now, we'd likely have very tangible issues in other places we're not anticipating. But *when* it happens, a chain that's not perfectly hiding will become fully clear. So all the transaction history up to the point where we have fully quantum safe algorithms will be analyzed. And while we can adjust algos, data stays forever.
> Cast your votes!
> - Igno
> P.S. I can't promise we'll do what the majority says (on the crypto side we have perfectly hiding, but not perfectly binding yet), but it'll influence the direction!

While chatting about Mimblewimble over Elements with instagibbs and gmaxwell
and real-or-random[0], we found a scheme that should satisfy everybody, except
for those who believe there are already quantum computers among us. (But
they should not be using MW because they should expect their coins to be
immediately stolen.)

Basically our outputs should consist of the pair

   vH + rG, sha256(rJ)

where J is a new NUMS generator, G the standard generator, and H is our asset
ID as always. We set this up so that we can softfork a rule that only allows
outputs to be spent by revealing rJ and an unconditional rangeproof, but prior
to the softfork we only require ordinary rangeproofs.

This is just switch commitments[1] with the important distinction that rJ is
hidden behind a hash. This means that users who use the scheme correctly still
have statistical soundness (practically speaking this is just as good as
unconditional soundness unless sha256 is destroyed, and in fact this is the
only form of soundness we have in the existing Elements rangeproofs because
we generate all of our secret values from a CSPRNG).

Then we get the usual benefits of switch commitments

  - If quantum computers seem imminent we can require users reveal rJ, do the
    unconditional rangeproof, and convert to some quantum-hard Pedersen commitment
    analogue. Hopefully one exists, I think [2] is what we want but maybe I've
    misunderstood it.

  - Users who want permanent privacy and are willing to sacrifice their coins in
    case the above requirement is softforked in, can use whatever gibberish they
    want in place of the hash, and they will retain their privacy even against
    quantum computers. They will have plenty of warning before any such fork, so
    they can either move their coins away or move them to upgradable outputs,
    taking the privacy hit voluntarily and knowingly and only for their most recent

  - Regardless of the above, users who generate their hashes deterministically,
    e.g. from BIP32 paths, can easily scan for and recognize their outputs when
    scanning the blockchain. This is currently quite difficult to do in MW.

  - We reduce the amount of design and code that we have to write immediately,
    letting us postpone it until we have a better idea of how people use use the
    system and what real users want as far as privacy/security.


[0] Greg Sanders, Greg Maxwell, Tim Ruffing
[1] https://eprint.iacr.org/2017/237.pdf
[2] http://eprint.iacr.org/2015/628

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

Attachment: signature.asc
Description: PGP signature

Follow ups