mimblewimble team mailing list archive

[Tim Ruffing <crypto@xxxxxxxxxxxxx>]

I need to resurrect this thread.

What's currently implemented in Grin [1] is 
  (vG + bH), BLAKE2(bJ), 
where the hash is truncated to 160 bits.

Hashed switch commitments are supposed to give you two main properties:
   1. Switch binding: even if you have unlimited computation power from
      tomorrow on, commitments created today are still binding if fully
      verified. This is the original property from the switch commitments
      paper [2] and it means that you can still spend your money after the
      switch to full verification (but you may lose privacy).
   2. Privacy for "old" outputs, which have been spent long ago, is
      retained even against quantum computers.
   3. Opt-out money, opt-in privacy: If your privacy is more important
      than your money, then you can decide not to reveal the pre-image of
      the hash. Then you cannot spend the money but you retain privacy
      even against post-quantum attackers.                  (This was my
      understanding, let's call it "3a". Andrew and maybe the others
      involved in the conversation had a different variant "3b" in mind:
      If you prefer privacy, then you commit to ((vG + bH), r) in the
      first place, where r is just random. This requires users to decide
      upfront if they want money or privacy but "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 history."

It turns out that the implemented variant just fulfills 1 and 3b [3].
Property 2 is trivially broken and it kind of scares me that I had
overlooked this:
Given the commitment ((vG + bH), BLAKE2(bJ)), guess v, compute b (by
solving dlog), and check if the second element is indeed BLAKE2(bJ)).

If we want all properties to hold, then the following construction
works:
  (vG + bH), BLAKE2(bJ, r),
where r is 256 bits and the hash is 256 bits as well.

Then 1 holds only computationally against quantum computers [4]. Even
in a quantum world, you need 2^128 operations to find a second preimage
in the hash. (Note that you have a quantum computer only after the
switch, you so cannot find a collision upfront.)

2 and 3a hold for the same reason: If you don't reveal r, then even a
quantum computer needs about 2^128 operations to compute it, and
without r you learn nothing about x [5].

So I propose that we switch to this new variant, pun intended.

Best,
Tim


[1] https://github.com/mimblewimble/grin/issues/177
https://github.com/Mimblewimble/grin/pull/179

[2] https://people.mmci.uni-saarland.de/~truffing/papers/switch-commitments.pdf

[3] 3b holds, because you just show a perfectly hiding Pedersen
commitment.
1 holds surprisingly, even though the hash is only 160 bits long: Given
a quantum computer, you may be able to find a second preimages of the
form b'J with BLAKE2(bJ)=BLAKE2(b'J) but the probability that there
exists at least one b' preimage that opens the commitment to a value in
range [0, 2^64-1] is small enough: with a fixed vG+bH, there are only ~
2^64 values of b' that possibly open the commitment to a value in
range, and the  probability that we have BLAKE2(b'J) for one of those
is at most 2^(-(160-64)) = 2^(-96). This probability is small enough
even if we aim for a 128-bit security level in general, because the
probability cannot be amplified afterwards: If there is no preimage,
you can compute as much as you want...

[4] This is probably fine, because we decided to use Pedersen
commitments and computationally sound rangeproofs before the switch as
well.

[5] If we want to make this formal, then this statement is dangerous in
a quantum world, where attackers can query hash functions and random
oracles in superposition. But even there, this argument be made formal.
If you're really interested, look at Lemma 4.1 in 
https://eprint.iacr.org/2017/604 or Lemma 1 in https://eprint.iacr.org/
2013/606.pdf.



On Fri, 2017-09-08 at 13:43 +0200, Tim Ruffing wrote:
> On Thu, 2017-09-07 at 18:12 +0000, Andrew Poelstra wrote:
> > It's true that people can put non-random things here which would be
> > really
> > bad for privacy. I don't think there's any efficiently-verifiable
> > way
> > to
> > prevent that. Maybe requiring the data be a hash and requiring the
> > preimage
> > be exposed during spending, even in the pre-switch era?
> > 
> 
> That is worse for privacy then. As soon as someone gets a QC, he can
> break the privacy of already spent outputs then.
> 
> In general, I think being able to recognize outputs is a very
> convincing argument for the hash.
> 
> Also, as I argued in the other thread, the hash gives users a lot of
> flexibility, because they can decide later if they would like to
> reveal
> the preimage or not. Letting users decide on an individual basis
> avoids
>  almost the entire discussion of hiding vs binding.
> 
> Tim
>