I’m taking a break from my series on celestial navigation. The previous posts give the basics, but I haven’t thought of a way to go further that I’m satisfied with. So now for something completely different: Pedersen commitments.

Pedersen commitments are a building block of zero knowledge proofs (ZKP), and they give an opportunity to look at a couple other other interesting topics: nothing-up-my-sleeve constructions and homomorphic encryption.

A Pedersen commitment to a value v takes a random number x and two generators of an elliptic curve, G and H, and returns

C = vG + xH.

The significance of C is that it appears to be a random number to the recipient, but the sender who calculated it can later show that it was computed from c and x. C is called a commitment to the value v because the sender cannot later say that C was computed from a different v and a different x.

Mathematical details

The addition in

C = vG + xH

is carried out on on an elliptic curve, such as Ed25519 in the case of Monero. Multiplication is defined by repeated addition, though it’s not computed that way [1]. G and H are not just points on the elliptic curve but points in a large, prime-order subgroup of the elliptic curve.

Because the value x is random, the possible values of C are uniformly distributed on the curve, and so someone observing C learns nothing about v. For that reason x is called a blinding factor.

The difficulty of the discrete logarithm problem insures that it is impractical come up with different values v‘ and x‘ such that

v G + x H = v‘ G + x‘ H.

This depends on two assumptions.

The first assumption is that the discrete logarithm problem is hard to solve given current algorithms and hardware. The prevailing opinion is that it is unlikely anyone will come up with an efficient algorithm for solving the discrete logarithm problem on current hardware. However, Shor’s algorithm could solve the discrete logarithm problem efficiently if and when a practical, large-scale quantum computer is created.

The second assumption is that the generator H was chosen at random and not calculated to be a backdoor.

How to make and use a backdoor

Because G and H are members of the same prime-order (i.e. cyclic) group, there exists some integer h such

H = hG

If the generator H was randomly selected, nobody knows h and nobody can calculate it. But if H was calculated by first selecting h and multiplying hG then there is a backdoor.

Now

C = vG + xH = vG + x(hG) = (v + xh)G.

If you know h, you can pick a new v‘ and solve for x‘ such that

v + xh = v‘ + x‘ h.

That would mean that in the context of a cryptocurrency that uses Pedersen commitments, such as Monero or the Liquid Network on top of Bitcoin, you could initially commit to spending v and later claimed that you committed to spending v‘.

Note that solving for x‘ requires modular arithmetic, not solving the discrete logarithm problem.

How to prove no backdoor

The way to prove that the generator H was chosen in good faith is to be transparent about how it was created. In practice this means using some sort of cryptographic hash function. For example, Bulletproofs hashed “bulletproof_g” and “bulletproof_h” to create it’s values of G and H. Bulletproofs require multiple values of G and H and so consecutive integers were concatenated to the strings before hashing.

Reversing a cryptographic hash like SHA256 is impractical, even assuming you have a quantum computer, and so it is extremely unlikely that there is a backdoor when the generators were created by hashing a natural string.

It’s said that Pedersen commitments do not require a trusted setup. That’s true in spirit, but more precisely they require a transparent setup that is easy to trust.

Homomorphic encryption

The function

C: (v, x) ↦ vG + xH

is a group homomorphism from pairs of integers to the subgroup generated by G and H. This means that

C(v, x) + C(v‘, x‘) = C(v + v‘, x + x‘)

or in other words, you can combine multiple commitments into a single commitment. The sum of a commitment to (v, x) and a commitment to (v‘, x‘) is a commitment to (v + v‘, x + x‘).

Related posts

• How and why Bitcoin uses Merkle trees
• Monero stealth addresses
• Zero knowledge proof of compositeness

[1] In practice the number x is enormous, say on the order of the number of points on the elliptic curve, and so software does not add H to itself x times. Instead it uses a process analogous to fast exponentiation. In fact, if you write the group operation multiplicatively rather than addititively, it is exactly fast exponentiation.