mimblewimble team mailing list archive

[Antioch <apeverell@xxxxxxxxxxxxxx>]

Just to add a couple of bits of info to this discussion -

We were actually experimenting with including a secret key as part of the blake2 hashing - using the lock_height of coinbase outputs in the switch commit hash here (not merged, still under discussion, parked due to testnet1) -
https://github.com/mimblewimble/grin/pull/215

Specifically -
https://github.com/antiochp/grin/blob/439dca94ec3970b7821b9fa78487521db1e922f1/core/src/core/transaction.rs#L545-L546

> proposed switch commit hash: blake2(h, rJ) where h the lock_height is used as the secret key to the hash function.

This was an attempt at ensuring the associated lock_height could not be altered once the coinbase output was on the block chain.

Also - I believe we are currently using the switch commit hash as a convenient way of identifying "our" outputs in the UTXO set for wallet recovery.
This is trivial currently as we know rJ from our wallet private keys and we can quickly check if the switch commit hash was generated by us.

None of this is to say I disagree - just wanted to make sure these were both visible as well.

— Antioch

Sent with [ProtonMail](https://protonmail.com) Secure Email.

> -------- Original Message --------
> Subject: Re: [Mimblewimble] Hashed switch commitments
> Local Time: December 13, 2017 11:18 AM
> UTC Time: December 13, 2017 4:18 PM
> From: crypto@xxxxxxxxxxxxx
> To: mimblewimble@xxxxxxxxxxxxxxxxxxx
>
> 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:
>
> - 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).
> - Privacy for "old" outputs, which have been spent long ago, is
> retained even against quantum computers.
> - 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
>
> Mailing list: https://launchpad.net/~mimblewimble
> Post to : mimblewimble@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~mimblewimble
> More help : https://help.launchpad.net/ListHelp