If H was badly chosen for the Pederson Commitment, such that the attacker knew a k where H = kG (1)

What damage could be done to the system?

We know that C = aH + bG

If I commit a = 10 and b = 2

We have C = 10H + 2G

Substituting k:

C = 10kG + 2G

C = (10k + 2)G

How does this help the attacker create the same C value with different a and b values? As I see it, the discrete log problem has not been broken, just a bad H value was chosen.

My guess is that:

Any commitment can now be broken down into C = akG + bG. From this, we can take a value c and d.

where C2 = cH + dG

C2 = ckG + dG

We can then choose different values e and f, in order to make e and f map to the same commitment C2. We do:

x = e - ck

y = f - d

We can then form C2 with e and f by doing:

C2 = eG + xG + fG + yG

C2 = eG + (eG - ckG) + fG + (fG - dG)

C2 = 2eG - cH + 2fG - dG

C2 = -cH + (2e+2f-d)G

up vote 2 down vote accepted

The point of a commitment is that it prevents you from later claiming that you'd committed to a different value.

To use the usual algebraic letters, a commitment is C = xG + aH where the value a is being committed to and the value x is the mask (a.k.a. blinding factor).

Revealing x and a after you've created the commitment C will prove that you had committed to that particular value of a afterwards, if h is unknowable.

If the discrete logarithm of H w.r.t. G was known, we'll call it h, then C = xG + ahG == (x+ah)G.

This means you could later on decide to pretend you'd committed to a different value a' of your choice, and calculate the alternative mask you'd need to claim as x' = x + h(a-a').

Therefore knowledge of h means that commitments can't be trusted. It also means you know the private key of the commitment as c = (x+ah). This breaks a useful property of a Pedersen Commitment used in RingCT, which is that only commitments to zero have knowable private keys. This means that if h is unknowable, providing a valid signature for the public key C will prove the amount you'd committed to was zero.

H is chosen arbitrarily, which prevents anyone from being able to figure out h. If you could figure it out, you'd have broken the elliptic curve discrete logarithm problem.

To answer the question as to how knowledge of h could be exploited specifically in Monero:

When you receive an output in a transaction, the transaction publicly declares a commitment to the value of that output. When you create new outputs in a transaction that spends the aforementioned output, you also declare commitments to the values of the outputs you're creating.

A verifier will check that the sum of input commitments - output commitments - fee commitment is a commitment to zero, because you will provide a RingCT signature using the private key of that commitment to zero (which is simply the mask of that commitment to zero). Verifiers will be satisfied that the signature is only possible if that private key is known, and that private key is only knowable for commitments to zero ordinarily. Since you know h though, you will be able to sign commitments to non-zero values, and so can produce a RingCT signature even when the outputs you're creating in the transaction are greater in value than the outputs you're spending. Therefore you could create XMR out of thin air, and no one would know.

  • I believe I was a tad bit unclear in my explanation. Thanks for weeding out what I was really asking, and relating it directly to a Monero example – WeCanBeFriends Oct 17 at 22:29
  • 1
    @WeCanBeFriends Just in case it's not clear, H is not chosen on a per-transaction basis. It's a global constant, and the developers of Monero chose H arbitrarily such that no one (including them) could possibly ever know a value h such that H = hG. – knaccc Oct 17 at 22:33
  • Perhaps useful to note is that it's impossible to know whether or not they truly chose H arbitrarily just because they came out and said "Yeah, H is random and I promise I don't know h". The developers proved H is random by using H = hash(G). – Nicholas Pipitone 2 days ago

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.