3
$\begingroup$

I have read that perdersen commitment can be used to hide the messages such as transactions by participants. The verifier will just have to make sure that the difference of the commitments is zero. But I don’t quite understand how is this verification valid.

For eg, for the input messages, 10, 5, 2, Alice could choose and apply a blinding factor, (7, 3, 8) to each of them: $$ input_c = g^{10} \cdot h^7 + g^5 \cdot h^3 + g^2 \cdot h^8 $$

Then, for the output messages, 8, 9, Bob could do the same thing with blinding factors (11, 21): $$ output_c = g^8 \cdot h^{11} + g^9 \cdot h^{21} $$

All the actual message values and blinding factors are only known to the Alice and Bob themselves. They only commit the $input_c$ and $output_c$ values. So, the verifier would take their differences to check for zero: $$ output_c - input_c \stackrel{?}{=} 0 $$

However, since both Alice and Bob are picking their blinding factors randomly and they don’t know each other’s blinding factors, how can the differences ever be $0$?

On the other hand, couldn’t Bob cheats by just committing his commitment exactly the same as the $input_c$ since he gets to see it before committing? Instead of computing $output_c$, he just takes $input_c$ as his fake commitment: $$ fakeOutput_c = input_c $$

Now when the verifier takes the difference, it’s always zero! What am I missing here?

$\endgroup$

2 Answers 2

4
$\begingroup$

I think you are applying the concept to the wrong scenario (I mean stop thinking input/output messages). I propose you to take the stuff this way:

Pedersen commitments, as other flavours, have two main properties: hiding and binding (be careful, non bLinding!! ;) ):

  • hiding means they hide the original message
  • binding means that once a PC is bound to a message, it's not possible to provide another message different from the original one and resulting in the same commitment value (in that sense commitments equality is a proof of equal messages)

Given different commitment kinds, these two properties can be honoured by various degrees: for PC, binding is a computational, essentially meaning that if PC wasn't binding, the discrete logarithm problem would be broken: but DLP is assumed hard, so PC is assumed binding :) A quick proof of that (just let me use additive notation and let's assume the message is just a number):

$C = mG +bH$

where $C$ is the commitment, $m$ the original message, $b$ the bLinding factor (this time the L is ok ;) ), random and known only to the party producing the commitment, $G$ and $H$ are generators, but be careful: even if they belong to the same EC group, so there exist $j$ so that:

$H = jG$

that $j$ is unknown to everyone (it's reasonably possible to come up to this scenario, the heuristics about it are usually called NUMS). Now the juicy part of the proof:

if the original author of the commitment pretend a second message $m_2$ has the same commitment $C$, it means he has found a second blinding factor $b_2$ so that:

$mG + bH = m_2G + b_2H$

but in that case a few of algebra lead us to:

$H = \frac{m_2 -m}{b-b_2} G$

So:

$\frac{m_2 -m}{b-b_2} = j$

But $j$ was unknown to everybody, so we have just found a non-hard way to break DLP :-)

You can find a lot more about all of this in the first 6 pages of https://github.com/AdamISZ/from0k2bp/blob/master/from0k2bp.pdf

This was to answer about Pedersen commitments, but one last thing: the fact that you are speaking about transaction, inputs, outputs.. well that makes me think the use case you have in mind is the value balance in privacy coins TXs: if so, that's a bigger topic than just commitments, even if commitments have an important role: if you want to take a glance, e.g. Monero currently handles that issue in this way: https://www.bybaro.it/tss/RctCheatsheet20210604.pdf (disclaimer 1: it's not easy, and needs a previous knowledge of other topics in https://www.bybaro.it/tss - disclaimer 2: I'm the author of those infographics)


FOLLOW UP TO TRY TO EXPLAIN PROOF LOGIC TO OP

It seems my proof about computational binding of PC has confused the OP about the validity of DLP hardness assumption. My educated guess that's because of lack of habit with proving techniques, so I try to make more explicit previous "reductio ad absurdum". We have seen that (brush up above if needed):

$C(m)=C(m_2) \Rightarrow j = \frac{m_2 -m}{b-b_2} \Rightarrow$ DLP is broken

but DLP hardness is ASSUMED to hold (it's a matter of faith based on years of clever guys attempts), so how to reconcile the fact DLP isn't broken with the above chain of implications which is so simple that cannot hide any subtle error? We check where those implications lead to when the chain conclusion is false:

  • if $j \neq \frac{m_2 -m}{b-b_2} \Leftarrow$ DLP is NOT broken

(meaning that if DLP is NOT broken, $j$ cannot be calculated by means of that simple fraction) because of the truth table of a true implication. And the same with the first implication:

  • $C(m) \neq C(m_2) \Leftarrow j \neq \frac{m_2 -m}{b-b_2}$

Putting all together we get:

$C(m) \neq C(m_2) \Leftarrow j \neq \frac{m_2 -m}{b-b_2} \Leftarrow$ DLP is NOT broken

(NOTE that I reversed the arrow hoping it can help the understanding, usually the hypothesis and the thesis are the inverted ones, keeping the implication arrow pointing right-wise).

So we have proved that, holding the hardness of DLP (which -I stress again- is ASSUMED to hold), $m$ and $m_2$ cannot have the same commitment value: that's why binding property of PC is said to be computational: it's safe until the computational capabilities of the adversaries will not exceed the common ones (which, btw, do not permit to break DLP either)

$\endgroup$
6
  • $\begingroup$ Follow-up #1: Ohh... I've always thought $H$ is simply any generator point on the curve known to everyone and decided by the implementer? Will there always be a $j$ for any point on the curve $H$ such that $H=jG$? What if there isn't such a $j$ for a particular chosen point $H$ on the curve? $\endgroup$
    – xenon
    Nov 5, 2022 at 10:13
  • $\begingroup$ Follow-up #2: When the original author fakes a different message $m_2$ for commitment $C$ and $m_2 \neq m$ with $b_2$, assuming there can only be one value for $j$ such that $H=jG$ (meaning no other value for $j$ to satisfy the equation), will this will cause $\frac{m_2 -m}{b-b_2} = j_2$ such that $j_2 \neq j$? Meaning $j_2$ is different from the original intended value of $j$ for $H=jG$? Since $m_2 \neq m$ and $b_2 \neq b$, the newly derived $j_2$ must be different from $j$ to keep $H$ the same original point so that $H=j_{2}G$, wouldn’t it? Since $j \neq j_2$, isn't the DLP not broken? $\endgroup$
    – xenon
    Nov 5, 2022 at 10:14
  • $\begingroup$ Follow-up #3: If $j$ can indeed be solved from $\frac{m_2 -m}{b-b_2} = j$, doesn’t this mean the pederson commitment can’t exactly bind to the original value because it seems like the original author could find a different $m_2$ and $b_2$ to match the commintment $C$? I think I’m missing something here.😬 $\endgroup$
    – xenon
    Nov 5, 2022 at 10:15
  • $\begingroup$ #1 as far as G and H are on the same EC group there's just one j (mod the group order), if G and H are about different curves or groups I don't know if you can prove computational binding property at all; #2 just one j (mod...) as said before: if j_2 is calculated it's = j; #3 you're right, in fact the proof proves it will not be your case (j is calculated => DLP is broken, so take the contrapositive - justified by DLP hardness assumption) $\endgroup$
    – baro77
    Nov 5, 2022 at 11:34
  • $\begingroup$ I've been thinking about it but I'm still not very sure. Sorry if I'm gonna sound dumb. I'm very new to these stuff. If it's as you said that the DLP can be broken this way, how is Pedersen commitment still used in so many places? It must have been secure to be used, isn't it? $\endgroup$
    – xenon
    Nov 7, 2022 at 15:05
2
$\begingroup$

Alice sends an amount $a$ to Bob, but does not declare the amount $a$ transparently on the blockchain.

Instead, she declares the Pedersen commitment $A=aG+a'H$ as part of the transaction that appears on the blockchain. $a'$ is a uniformly random blinding factor, and $G$ and $H$ are well-known generator points chosen such that the EC discrete log $G/H$ is unknown. Alice additionally encrypts $a'$ as part of the transaction such that only Bob can decrypt it with his private key.

Now, Bob wants to spend $a$, splitting it up so that the amount $b$ goes to Carol, and the amount $c$ is returned to him as change.

Bob declares the Pedersen commitments $B=bG+b'H$ and $C=cG+c'H$, and includes them in the transaction.

Now, Bob has to prove that he has not created any currency out of thin air. He needs to prove that the three commitments $A, B, C$ commit to amounts $a,b,c$ such that $a=b+c$.

He does his by providing a signature on the value $C-A-B$ on the generator point $H$. He can do this since he was sent the blinding factor $a'$ by Alice, and he knows the blinding factors $b'$ and $c'$ because he has just chosen them.

A signature for $C-A-B$ on the generator point $H$ proves that the value $x$ is known such that $xH=C-A-B$.

Bob knows $x$, since $x = c'-a'-b'$.

The signature on the generator point $H$ is only possible if all the $G$ values cancel each other out. For example. If $C-A-B=3G+xH$, then $x=c'-a'-b'+3(G/H)$. But, since the discrete log $G/H$ is unknown, Bob cannot know $x$ when the commitment amounts do not cancel out the $G$ component.

Therefore, the signature is evidence that no amount was created out of thin air. The amount spent must perfectly match the sum of the amounts received.

Note that due to the cyclical nature of group elements (generator points), Bob could spend the amount $a=3$ such that $b=\ell-1000$ and c=$1003$, where $\ell$ is the size of the group. This would mean that $a-b-c \operatorname{mod} \ell = 0$, and Bob has created the amount 1000 out of thin air. This is why you additionally need to provide a range proof for each Pedersen commitment declared in a transaction, demonstrating that amounts must be in a small range such that they can never sum to an amount that equals or exceeds $\ell$.

$\endgroup$
4
  • $\begingroup$ Follow-up #1: Thank you! Can I clarify what does it mean by “providing a signature on the value $C-A-B$ on generator point H”? I’m thinking, $C-A-B = (c-a-b)G + (c’-a’-b’)H$. Does it mean Bob provides a signature only on the evaluated value for the part $(c’-a’-b’)H$ without the $(c-a-b)G$ part? $\endgroup$
    – xenon
    Nov 5, 2022 at 10:15
  • $\begingroup$ Follow-up #2: So it seems like one could easily come up with a $b’$ and $c’$ for a fake $b$ and $c$ values to force the difference between $C-A-B$ to be zero and hence trick the verifier? Does it mean that due to the cyclical nature of the generator points, Pedersen commitments cannot be verified safely without a range proof? $\endgroup$
    – xenon
    Nov 5, 2022 at 10:15
  • $\begingroup$ @xenon Normally, you have a private key $x$ and a public key $X=xG$. You are providing a signature for $X$ on the generator point $G$, proving knowledge of $x$. What I'm talking about is exactly the same thing, except you have to tweak the signature library which normally uses $G$ to let you use $H$ as the base point instead. When it comes to using the signature library, you just tell it about $x$ and $H$ when signing. When verifying, the point you verify against would simply be point calculated as $C-A-B$, where those points will have been publicly declared. $\endgroup$
    – knaccc
    Nov 5, 2022 at 11:04
  • $\begingroup$ @xenon Re: your second msg: it's the $G$ values that have to cancel out, which means you have to make sure $c=a+b$. You can't trick anyone through strategic choice of $a'$, $b'$, or $c'$ values, because those only affect the $H$ component of the commitment. You only need range proofs if you want to ensure people can't declare commitments to huge numbers. If it's just two Pedersen commitments you're testing for equality, you don't need a range proof. Check out Zero to Monero section 5.2, which explains how this stuff works getmonero.org/library/Zero-to-Monero-2-0-0.pdf $\endgroup$
    – knaccc
    Nov 5, 2022 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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