What will happen if somebody found that magic "h": h*G = H

Development and Technical Discussion
1

Firstly, don’t worry about it, I believe nobody know this magic “h”, for now and perhaps for a long time.

But perhaps not very long! read how close are we really to building a quantum computer and timeline of quantum computing.

And even before a powerful quantum computer to break ECDLP, perhaps one day one lucky people just find a random “h” which happens to make h*G=H, who knows? a probability close to zero doesn’t means impossible.

So, for now, we MUST know what will happen in Mimblewimble if this magic “h” is known by somebody.

What will happen if I know the magic “h” which makes h*G = H ?

Let’s take a look for the Pedersen Commitment form: r*G + v*H. The simple arithmetic equation a + b = c can be expressed as commitment form:

(x*G + a*H) + (y*G + b*H) = (z*G + c*H) , with x + y = z

This is the most important pillar of MimbleWimble.

Now if I know the magic “h” which makes h*G = H, then I can change the output value freely:

     z*G + c*H = (z’ *G + c’ *H)
=> (z’-z)*G = (c-c’)*h*G
=> z’ = z + (c-c’)*h

This means I can create money out of thin air in the transaction, without breaking the balance of the commitments which sum to zero. The pillar of MimbleWimble is gone and the whole house falls.

And even worse, when this happen, there’s no one else know it’s happening! thanks to the excellent privacy of Mimblewimble protocol.

A Proposal by Tim Ruffing to Secure this Pillar

Thanks to Tim Ruffing and Giulio Malavolta 's research on Switch Commitment [1] and Tim Ruffing 's good proposal to Mimblewimble [2], we can modify the blinding factor as the following form:

r’ = r + Hash(rG+vH || rJ)
and the base point J is chosen to be orthogonal to G.

so the Pedersen Commitment r*G + v*H becomes:

     r’ *G + v*H
= (r + Hash(rG+vH || rJ))*G + v*H
= (r*G+v*H) + Hash(rG+vH || rJ)*G

And we need add an additional rule to spend an UTXO, revealing the rG+vH and rJ to spend output r’*G+v*H.

Why this enhanced design can avoid me creating money out of thin air in the transaction? even I know the magic “h” .

Let me try it.

We already know that I can change the Pedersen Commitment components freely, with the known magic “h” :

     *z*G + c*H = (z’ *G + c’ H)
=> z’ = z + (c-c’)*h

With the new form of Pedersen Commitment:

     r’ *G + v*H = (r*G+v*H) + Hash(rG+vH || rJ)*G

Now let me freely change the value from v to v" :

r*G + v*H = r" *G + v"*H
and r" = r + (v-v")*h

Then,

     r’ *G + v*H
 = (r*G+v*H) + Hash(rG+vH || rJ)*G
!= (r" *G + v"*H) + Hash(r"G+v"H || r"J)*G

So, the result is I can’t change this commitment and I fail to create money out of thin air! even I know the magic “h” .

This is mainly because of r*J != r"*J. The r*J works like a locker to forbid the change of r, and we can’t change the value v without changing r, to keep the balance of r*G + v*H = r" *G + v"*H.

The Related Status in Grin

Thanks to @jaspervdm, we have an opening PR for this enhancement solution: [DNM] Switch commitments by jaspervdm · Pull Request #2007 · mimblewimble/grin · GitHub, and 2 related PRs in secp library: Add blinding factor for switch commitment by jaspervdm · Pull Request #34 · mimblewimble/secp256k1-zkp · GitHub and Add blinding factor for switch commitment by jaspervdm · Pull Request #38 · mimblewimble/rust-secp256k1-zkp · GitHub.

And please note that we still need further research about how to gracefully integrate that additional rule:

To spend an UTXO r’*G+v*H, require to reveal the rG+vH and rJ .

But IMO, complete PR #2007 and switch the Pedersen Commitment to this enhanced design should be a MUST for Grin mainnet, and now we don’t have much time left before 15th Jan. 2019.

Any comments/feedback welcome.

[1] https://eprint.iacr.org/2017/237.pdf
[2] switch commitments (again) : Mailing list archive : mimblewimble team in Launchpad
[3] switch commitment discussion · Issue #998 · mimblewimble/grin · GitHub

2 Likes
2

Thanks for the nice writeup! Regarding the additional rule, I think we should not activate it until we think there is a real possibility that someone knows h. At that point we can require all spends to reveal the full ElGamal commitment (rG+vH, rJ) and have an accompanying range proof. We should not require this before the switch since these rangeproofs are less efficient than Bulletproofs.

3

@jaspervdm

I think we should not activate it until we think there is a real possibility that someone knows h . At that point…

I’m afraid there is NO such kind of point, because:

And even worse, when this happen, there’s no one else know it’s happening! thanks to the excellent privacy of Mimblewimble protocol.

I agree that we can postpone the additional rule after Grin mainnet, and only switch to the enhanced Pedersen Commitment for mainnet. But perhaps can’t postpone the rule too long.

Regarding to the accompanying range proof, I don’t understand why we need it, could you explain more?

4

Without a range proof, how does one verify that the revealed commitment actually is an ElGamal commitment?
For example, what is stopping them from using (rG+vH, P) where P is some random curve point? A public verifier doesn’t know r, so they can’t verify P=rJ.

5

@jaspervdm I don’t think an additional range proof is needed here.

C = r’ *G + v*H = (rG+vH) + Hash(rG+vH || rJ)*G

And this output accompany a range proof for C and v.

When someone spend this output, besides a signature to show he/she knows the blinding factor r’ , he/she also need reveal C’ = r*G + v*H and r*J. And we verify:

C = C’ + Hash(C’ || rJ)*G

Here Hash(C’ || rJ) works like another blinding factor, how he/she can use a random point P instead of rJ to make this?

C = C’ + Hash(C’ || P)*G

Please remind me if anything in paper I have missed :blush: correct me if something wrong here.

6

Ok let me try to explain. Suppose I create an output
C = rG + vH + hash(rG+vH || P)G
where P is some random point.
Now suppose I solved the log between H and G, which allows me to find new values for r and v (thereby creating money):
C = r'G + v'H + hash(r'G+v'H || P)G
(where rG + vH = r'G + v'H)
You can see that the full commitment is still the same. The whole construction only works if we require P=rJ. Because then the new commitment would be different, namely it would have a P'=r'J, which means you can’t reveal the commitment with a different amount than you originally committed to.
But that means we need to have a method to verify that P==rJ, without revealing r. I think this is accomplished by a rangeproof.

7

Yes, you’re right :+1: and sorry for my careless missing, indeed it’s also mandatory here to verify P == r*J.

8

And J could be chosen equal to G or H as well?

9

Here P works only as a locker to forbid any change of r or v, so perhaps you can use r*G or r*H instead of r*J. But what’s the benefit? we still need the way to verify P == r*X, here X = J or G or H.