# How do key images really work?

I have the following questions regarding the equation `I=xHp(P)`:

1. What is the hash function `Hp`?
2. How can we know that `Hp(P)` is a point on the `Ed25519` curve? Or is it not?
3. Is the value `I` published with the transaction?
4. How can an external person verify that the key image has been produced by the owner of one of the transactions, without revealing the identity but at the same time providing double spending resistance (even when the signer chooses two different rings)?

I've found very fragmented information at different places but none of them has an in-depth explanation of how double spends are avoided in monero while preserving privacy.

1. What is the hash function Hp?

The `Hp` is the hash-to-point function. Result of that would be some random point on the Ed25519 curve. In the CN whitepaper it's defined as:

H_p: a deterministic hash function E(F_q) -> E(F_q)

If I understand well, it takes any point on the curve, and yields a random point on the same curve. The implementation is in the `hash_to_ec` function. It's not entirely clear to me, but I've written what I could understand as an answer to this question.

Anyways, the definition is clear: a function to take a point and return a random point, so implementation is expected do the same. Anything multiplied with the basepoint will yield a point, and we must multiply it by 8 to get a point on the primary group. There's some info about that here.

2. How can we know that Hp(P) is a point on the Ed25519 curve? Or is it not?

It is, and that's not the only requirement - it must also be a point on the primary sub-group of the base-point `G`. You can check by multiplying with `l`. If you get the identity element, it's in the `G` sub-group.

3. Is the value I published with the transaction?

Yes, the value of `I` is published with each transaction. You can look up any TX on a block explorer and see that.

4. How can an external person verify that the key image has been produced by the owner of one of the transactions, without revealing the identity but at the same time providing double spending resistance (even when the signer chooses two different rings)?

I was asking myself the same thing. Looking at the CN whitepaper again, we see that the ring signature is composed of the public keys + the key image.

Similarly, the signature checking alghoritm involves key image as part of it.

If the signature is ok, the verifier checks whether it had already been used, effectively preventing double-spends.

Finally, there are some general notes about the whole mechanism.

And that answers the question - the coefficients `(r_i, c_i)` are used by the signer to prove that he knows such `x` that at least one `H_p(P_i) = I * x^-1`, effectively proving that it's one from the ring.