I generated a Pedersen commitment for a given account balance (say, 10) and stored it in the ledger. Now, when I debit 15 tokens from the same account, I first retrieve the Pedersen commitment of 10 from the ledger and subtract it from the Pedersen commitment of 15, and then I want to check whether the resultant Pedersen commitment is negative or not. Is it possible at all? The primary concern here is, without knowing the original value of Pedersen commitment, is it possible to determine if it is a negative or positive number if I only have Pedersen commitment (and corresponding blinding factor, generator)?
4
-
$\begingroup$ I assume you mean that the blinding factor generator is known, but not the blinding factor. If the blinding factor is known for a commitment, then it is easily possible to brute-force the commitment to discover the amount committed to (if the the amounts committed to are small numbers like 5 or 10) $\endgroup$– knacccCommented Nov 11, 2023 at 5:17
-
$\begingroup$ @knaccc: actually, if you know the blinding factor, you can use a $\sqrt{n}$ attack to find the committed value. With that, you can search through 60 bit commit values on a laptop... $\endgroup$– ponchoCommented Nov 11, 2023 at 8:22
-
$\begingroup$ @poncho oh cool - do you have a link to a description of that attack please? Does it apply to EC commitments? $\endgroup$– knacccCommented Nov 11, 2023 at 9:15
-
1$\begingroup$ @knaccc: Baby Step Giant Step (en.wikipedia.org/wiki/Baby-step_giant-step) works (and it does apply to EC) $\endgroup$– ponchoCommented Nov 13, 2023 at 13:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
A Pedersen commitment is an element of a cyclic group, and all group elements are generators of the group.
This means that strictly speaking, there is no such thing as a negative Pedersen commitment.
If the size of the group is $\ell$, then a commitment to $-5$ is identical to a commitment to $\ell-5$.
When cryptocurrencies use Pedersen commitments to represent amounts, they restrict the maximum value of a commitment, typically to $2^{64}$. A "range proof" is then declared with a transaction, which proves that the commitment is to an amount between $0$ and $2^{64}$.
This means that they can't cheat and declare a negative value as part of a transaction, because $\ell$ will typically be around $2^{252}$ or $2^{256}$. Therefore, "negative" amounts are actually positive amounts so big that they will not be able to create a range proof demonstrating that the amount is less than $2^{64}$.
The creator of the transaction is responsible for providing this range proof, so that others can know the commitment is not negative. This requires the creator of the transaction to know the amount of the Pedersen commitment that they are creating. They cannot create a range proof if the amount is unknown to them.
-
$\begingroup$ In my use case, when I debit an account, I retrieve the encrypted sender's remaining balance after subtracting commitments of balance from the transacted amount. I want to verify if the encrypted sender balance is negative or not. Based on your response, I believe it is impossible to determine if Pedersen's commitment is negative or positive without knowing the original value. $\endgroup$ Commented Nov 11, 2023 at 20:38
-
$\begingroup$ @PradyTej I'm not sure I fully understand. When you refer to an "encrypted" balance, do you mean a Pedersen commitment to the balance, or do you mean the balance encrypted through other means such that it can be decrypted? $\endgroup$– knacccCommented Nov 12, 2023 at 7:15
-
$\begingroup$ In this case, "encrypted" refers to Pedersen's commitment to the remaining balance. I saved the balance as a Pedersen commitment in the ledger, and then when debiting, I removed the transactedAmount Pedersen commitment from the balance Pedersen commitment. I want to see if the Pedersen commitment of the remaining balance is negative (I don't know the original value of the remaining balance, only the Pedersen commitment). $\endgroup$ Commented Nov 12, 2023 at 18:04
-
$\begingroup$ I'm curious how crypto transactions accomplish this because this is a common issue $\endgroup$ Commented Nov 12, 2023 at 18:04
-
$\begingroup$ @PradyTej In cryptonote transactions, the amount is encrypted such that the recipient of the transaction can decrypt the transaction amount and decrypt the blinding factor. In addition, a Pedersen commitment is declared along with range proofs, so that the public can verify that no negative amounts have been added to the blockchain. Full information here $\endgroup$– knacccCommented Nov 12, 2023 at 21:02
$\begingroup$
$\endgroup$
3
Is it possible at all? The primary concern here is, without knowing the original value of Pedersen commitment, is it possible to determine if it is a negative or positive number if I only have Pedersen commitment (and corresponding blinding factor, generator)?
No, it is not (independent of what "negative" means in this case), assuming you cannot ask the committer for help.
For any commitment $C$ and any committed value $m$, there is a blinding factor $s$ with $C = g^m h^s$. That is, if you have a commitment and nothing else, you get no information about the committed value, and this is true even if you have computationally unbounded resources.
If the committer is allowed to be involved, this doesn't apply (because he can know what $s$ is); he can generate a range proof that can give the answer.
-
$\begingroup$ We need to know the original value to build the range proof because range proofs are created using the original value, but in my case, I don't know the original value. Simply put, I know the transactedAmount, and after deducting the commitment of the transactedAmount from the balance, I only know the encrypted sender's remaining balance((C(10, r1) - C(15,r2). Is it possible to determine whether the encrypted sender's reamingnbalance is negative or not? I'm curious how crypto transactions accomplish this because this is a common issue. $\endgroup$ Commented Nov 11, 2023 at 20:45
-
$\begingroup$ I'm curious how crypto transactions accomplish this because this is a common issue. $\endgroup$ Commented Nov 11, 2023 at 20:52
-
$\begingroup$ Here, I refer to the "encrypted" remaining balance as Pedersen's commitment to the remaining balance. $\endgroup$ Commented Nov 12, 2023 at 18:32