Blogs & Articles: Additively Homomorphic Cryptographic Commitments 🔗 4 years ago

I have a pen.

I have an apple.

I have a box.

I have a lock.

I have a key.

And I choose either the apple, or the pen and I put it in the box and seal it with a lock. However I don’t tell you which one I chose. Finally I give you the box and the result is:

Umm, Cryptographic Commitment.

You have one guess. If you figure out if I put an apple or a pen in the box then I give you 10_000 bitcoins. Did you make your guess? Good. Notice that I cannot change my mind based on what you guessed for in order to avoid paying you out. So now I have to give you the key to open the box and reveal to you the answer for the million dollar question: What did I commit to? Did I commit to an apple or to a pen?

Umm, apple pen!

note to self: improve my microsoft paint skills

Sorry to disappoint you, but I’m a trickster and I put both my apple and my pen into the box, so I don’t have to pay you anything. We will fix this later.

Cryptographic Commitments

By breaking my metaphor for the sake of entertainment I failed to make you understand cryptographic commitments, but fear no more, because in this section I am fully committed to explain them to you. Pun intended.

An analogous cryptographic commitment for the above example can be a sha256 hash function. Such hash looks like this:

ea94deb8cbee4af1c991d17ae027cd54b78d02abe45eba22b408b41313d64d25

This is a hash for Luke Dashjr’s Bitcoin Knots software. He publishes this mess on his website in order for you to be able to compare this hash with the binary that you have just downloaded:

This way you can make sure that the binary hasn’t been replaced by a man in the middle after you downloaded it. For example I just verified it locally and indeed the binary has the same hash that Luke published to his website so I was not hacked:

Notice that for the same input you get the same output and you could use this to your advantage. For example you could cheat the game we just played by shaking the box. Then take another box, put an apple in it and shake it. If they shake the same way, then you figured out that it’s an apple! This is a desired feature for Luke, but for our example this enables you to cheat. So let’s fix this:

I can use some packing materials such as bubble wrap, packing peanuts, or crumpled paper to fill the empty space in the box, so both the pen and the apple box will give the same sound when shaking it. This is called the hiding property. A cryptographic equivalent of such hiding commitment would concatenate the data we are committing to with some randomness:

SHA256(apple + bubble wrap)

Here I’d like to note that there’re two kinds of hidings here: unconditional and computational, but I just can’t fit it to the applepen metaphor I’m working with, so I will omit talking about it. Same applies for the other important binding property.

Moving forward, wouldn’t it be cool if we could prove things about these commitments? Remember I tricked you before and I put both an apple and a pen in my box? What if I’d have 3 boxes, 2 apples and 2 pens and I’d create an applebox, a penbox and an applepenbox and I could prove to you that one of the boxes contains an apple, another one contains a pen and if I add them up then I get a box that both has an apple and a pen in it:

box((apple OR pen) + bubble wrap) + box((apple OR pen) + bubble wrap) = box(apple + pen + bubble wrap)

Turns out I can! Meet additively homomorphic cryptographic commitments: ElGamal and Pedersen. ElGamal commitments are computationally hiding, Pedersen commitments are perfectly hiding. So let’s talk about the latter:

Where g and h are magical public group elements in a finite cyclic group where the discrete logarithm problem (DLP) is hard, but we don’t care about any of these.

I don’t tell you which one is an apple and which one is a pen, but I can prove to you that their sum is an applepen.

But notice I can still trick you, I could do the following and the equation would still hold:

In order to prove to you that I’m not cheating I would have to prove something about individual commitments themselves. I could prove the number of items I placed in each and every box. I can prove the range, which would be in our case between 1 and 1. Such proofs are called range proofs, for example Bulletproofs, however I won’t go into their explanations as that’s out of the scope of this article and I’ve already achieved my goal of writing the most user friendly introduction to additively homomorphic cryptographic commitments that’s out there. Rather I’d point to an article of mine which shows why this construct is important in the context of Bitcoin and Confidential Transactions:

Confidential Transactions/Bulletproofs

Finally it’s only fair if I say goodbye with the real Pedersen Commitment formula: