Pedersen Commitments: the Envelope of Secrets

How can verifiers in Zero-Knowledge proof systems ensure that the prover doesn't change the original statement after sending the proof?

Simple, get the prover to COMMIT to the statement!

ZK-proofs are a way for someone to prove that a statement is true without revealing anything about the statement:

“Why are you scared of commitments?”

Imagine Bob wants to take a loan from Alice. Alice is cautious with her money, and will only give him the loan if he has maintained an average balance of >$10K in the past 3 months.

Bob doesn't want to share his exact account balance with Alice, so he decides to use a ZK proof to prove that his average account balance over the past 3 months is > $10K. Alice then sends him a challenge question - for example, “What was the 3-month average account balance exactly 1 month ago?”

Bob sends the proof for the response to this challenge question, which Alice can verify for the correctness and sanction the loan.

BUT, what if, Bob is malicious? Say he used to have money but lost it all on a shitcoin and is currently broke. Now he needs the loan to pay back his debts. He could easily have scammed Alice by forging the proofs:

• In the original proof, he sends the current average balance of a friend’s account which has a >$10K balance

• And in response to the challenge message, he sends his own account balance from a month ago

Because Alice is verifying just the balance amount, she would never know that she has been scammed.

Commitment Schemes

To ensure this doesn't happen, Alice can ask Bob to 'commit' to his original statement so that he provides proofs from the same account. In cryptography, one such widely used commitment scheme is called Pedersen Commitment.

Commitment schemes have 2 basic properties:

1. Hiding- until the committed value is revealed, it cannot be discovered

2. Binding- once a commitment is made, its value cannot be changed

Let's look at a simple example:

Imagine there's an auction for a chance to go on a space trip with SpaceX. To ensure the bids stay private, Elon asks all the participants to write their bids on a piece of paper, lock the paper in a box, and give the box to him.

Once everyone has submitted their locked boxes, they can then share the keys to unlock their bids. This way the participants 'commit' to a bid:

• Hidden: The bids are inside the box, with no visibility

• Binding: Since the boxes are with Elon, the bids cannot be changed

In Pedersen Commitments, this is done using Elliptic Curve Cryptography (ECC). It is a way to encrypt data using the mathematical properties of elliptic curves:

The Magic Behind Pedersen Commitments

In ECC, different points on the elliptic curve can be added to or multiplied by each other. For example, given a starting point 'g', addition/multiplication operations can be performed to get 2g, 3g, and so on.

However, given a new point 'Ag' on the curve, it is almost impossible to find the value of 'A'. This makes ECC extremely secure:

• g is the generator

• The combined value ‘Ag’ is the public key used for encryption

• A is the private key used for decryption

If we use ECC for our auction example, the participants can use different secret values of 'A' to lock their boxes.

The problem?

Elon has some secret supercomputers that he can use to brute force the value of A & unlock the boxes without the keys.

So even though ECC *in this case* is good at 'binding' the committed value, it's not good at 'hiding' it. This is solved by Pedersen Commitments. This commitment scheme chooses a (secure), large random number, say R, in the range:

R is called the 'blinding factor'.

Then, another starting point (generator) 'h' is chosen on the graph and is encrypted in the typical ECC way to get a new value 'Rh'.

The Pedersen Commitment scheme then is simply:

c = Ag + Rh

Given the mathematical properties of ECC, it is extremely difficult to break down a Pedersen commitment even with supercomputers.

Now, this changes the entire game!

Let’s go back to our Bob-Alice loan example to see how Alice can use Pedersen Commitments to make sure Bob is not malicious.

This time, instead of just a proof of average balance, Alice asks Bob to commit to an account as well! Using the above image, now Bob will send the balance proof as:

c = Ag + Rh

where, A = avg bank balance, and R = account number

When Alice sends a challenge message this time, Bob has no option but to use the same account number (R) as last time, otherwise, his response will fail the verification.

Importance of Commitments

Pedersen Commitments are extensively used in privacy cryptocurrencies like Monero (@monero). Since the transactions are private, there's no way of knowing the exact amount of individual transactions. But the Pedersen Commitments mean that the sum of encrypted transactions can be verified such that:

Total transactions in = Total transactions out 

This helps verify that the transactions are valid and not creating currency out of thin air:

This property makes Pedersen Commitments a powerful cryptographic technique with many such potential uses, including anonymity-preserving cryptocurrency transactions, secure multi-party computations, and zero-knowledge-proof systems.