Monero uses Pedersen commitments to make transaction amounts private (hidden), but what, if any, are the problems of perfectly hidden and computationally binding commitments?
Add a comment
|
2 Answers
There seems to be a fair amount of misunderstanding amongst a few people of what is meant by the phrase "perfectly hiding and computationally binding" when discussing Monero security. In Monero, we use Pedersen commitments to hide the values in transactions and to help ensure there is no hidden inflation. Without an understanding of the context of the words "perfectly" and "computationally", this can lead to unnecessary fears.
To better understand, I find it helps to first grasp the concept of input and output spaces.
In the case of the input space for a Pedersen commitment, this is the set of all integers in a 506 bit range (a tuple x,a, two 253 bit scalars), and in the case of the output space, is the set of all points on the curve (Ed25519) used, a 253 bit range. Here you can see the input space is far larger than the output space. What this means in practice is that different inputs can map to the same output, or to put it another way, it works like a many-to-one relationship. Reference the Pigeonhole principle. Therefore, being in possession of the "one" part in a many-to-one relationship, you have no way (computationally at least) to determine specifically which of the "many" is the real input. Therefore, if an input space is larger than an output space, you can achieve perfect hiding.
Now, for the computationally binding. For a Pedersen commitment C, we have C = xG + aH, where x is the binding factor and a is the amount of Monero. What's important to understand here is that the generator point H must be chosen in such a way that no one knows an h such that hG = H (and it's regarded as safe to simply hash G for H here). Importantly, there is only one h that could possibly yield H (technically there could be others, but only one is actually needed for what follows), or to put it another way, the relationship is one-to-one. The input space is practically the same size as the output space. Now, to calculate this h would require knowing the discrete log of H w.r.t. G. This is what gives us the computationally binding aspect. It requires significant computation, but in theory, it's possible with unbounded computational power, to calculate this h.
So, assuming the sky falls any time soon and we have computers which can solve for the discrete logarithm problem, and thus someone is able to compute h such that hG = H, where does that leave us? Well, apart from all of ECC being vulnerable and the consequences of that, what it means w.r.t. Monero and the Pedersen commitments is that someone can publish a commitment using some random y, e.g. C = yG. Later, when asked to verify this commitment, they can pretend to have bound it with any given x. E.g. to calculate an a which will work for a given x:
xG + aH = C
xG + ahG = yG
thus
a = h^-1(y-x)
Or conversely, to obtain a binding factor x for any chosen amount b, that verifies the published commitment C = yG:
xG + bH = C
xG + bhG = yG
thus
x = y-bh
The binding property is lost. Whilst the existing amounts on the blockchain stay perfectly hidden, we would succumb to a problem of possible hidden inflation (we could no longer trust the amounts in commitments are accurate). And recall, this is a one-to-one mapping, you only need to find h once to be able to use it again for any given x.
Some people ask why we couldn't switch to having computationally hidden and perfectly bound commitments. Of course, we could, there are other commitment schemes that offer exactly this, e.g. ElGamal commitments. The real trade-off here is that ElGamal commitments are significantly larger than Pedersen commitments and also, they suffer the reverse issue e.g. they are perfectly binding but only computationally hiding (so with just one piece of information, all amounts could theoretically be revealed). Some also ask if there are any perfectly hiding and perfectly binding schemes. Not presently is the answer here.
But I'll stress here, just because something is not perfectly binding (or hiding), doesn't present some huge weakness. Being computationally strong is what ECC (and a great deal of other cryptography) is founded on - the discrete logarithm problem. We've got some time yet before computers are powerful enough to solve for this, and when they do, we've got a lot of bigger problems to deal with if we haven't come up with something else by then!
If it's not abundantly clear from all of the above, breaking the binding property does not break the hiding property. You simply cannot brute-force, no matter how unbounded your computational power is, e.g. even in the presence of quantum computing, to unhide the amount of Monero. You could at best calculate an amount that could be valid (recall there are many amounts that could be valid, you just have absolutely no way of knowing which is the one used). And breaking the binding has far more significant ramifications than just Monero's inflation security.
Adding to jtgrassies answer:
Perfect hiding and perfect binding are impossible to get.
A perfectly binding scheme implies a one to one relationship, each input is binded to one value in the output.
A perfectly hiding scheme implies a many to one relationship, each output can be hidden amongst many input values.
A slightly different example I can think of is a public key signature scheme. One public key goes to one signature, so it is perfectly binding. By this token, it cannot be perfectly hiding.
A ring signature on the other hand in most circumstances are or should be perfectly hiding, so that each member of the ring can have plausible deniability. By this token, it should be impossible to be 100% sure which member of the ring signed it. Interestingly, there is a new linkable ring signature scheme that scales logarithmically in the size of the ring members, however it also gives any member of the ring the ability to provide proof that they did not sign the ring.
Edit:
When we speak of perfect, we are using information theoretical terms which for the most part do not give much flexibility/practicality in terms of schemes we can use(one-time pad) while computational complexity gives us this notion of infeasibility which allows us to argue that although it is possible, it is computationally infeasible.
