mimblewimble team mailing list archive

mimblewimble team

Mailing list archive

Message #00374
Re: Hashed switch commitments
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#L545L546
> 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.
>  Optout money, optin privacy: If your privacy is more important
> than your money, then you can decide not to reveal the preimage of
> the hash. Then you cannot spend the money but you retain privacy
> even against postquantum 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.unisaarland.de/~truffing/papers/switchcommitments.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^641] 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^((16064)) = 2^(96). This probability is small enough
> even if we aim for a 128bit 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, 20170908 at 13:43 +0200, Tim Ruffing wrote:
>
>> On Thu, 20170907 at 18:12 +0000, Andrew Poelstra wrote:
>>
>>> It's true that people can put nonrandom things here which would be
>>> really
>>> bad for privacy. I don't think there's any efficientlyverifiable
>>> way
>>> to
>>> prevent that. Maybe requiring the data be a hash and requiring the
>>> preimage
>>> be exposed during spending, even in the preswitch 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
Follow ups
References