← Back to team overview

mimblewimble team mailing list archive

Re: Hashed switch commitments


Just put a PR up for discussion that uses this new proposed variant of hashed switch commitments.

BLAKE2(bJ, r)

Where the following apply -
* digest is now 32 bytes
* r is 32 bytes
* r is derived from the extended key in the wallet (different seed key and chaincode from the secret key itself, so b and r and unrelated other than the derivation number and the wallet seed itself)

— Antioch

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

-------- Original Message --------
On December 14, 2017 12:29 PM, Tim Ruffing <crypto@xxxxxxxxxxxxx> wrote:

> Hm, if I understand this correctly, then I think this throws together
> two unrelated concepts. With this proposal, users are forced to open
> their commitments (and give up some privacy) just to realize some
> unrelated functionality, i.e., timelocks.
> If we want to store that in the same hash to save space, which is
> probably a good idea, then I think the way to go is something like
> hash(data||hash(bJ||r))
> where data can be anything, e.g., lock_height.
> Then, if you show bJ, you are forced to show data as well but this is
> fine:
> If you show bJ, then you want to spend, and then you need to show the
> lock_height anyway.
> Regarding identifying outputs:
> r can be derived from the wallet key as well, so that's not an issue, I
> think.
> Best.
> Tim
> On Wed, 2017-12-13 at 15:01 -0500, Antioch wrote:
>> 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/439dca94ec3970b7821b9fa78487521
>> db1e922f1/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 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-com
>>> mitments.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