# Is it easily provable by a third party that the key image used in a transaction is associated with the spent output without revealing the (P,I) pair?

What I'm getting at is I'd like to know how the Monero network can know that a key image used in a transaction is not either forged (probably an easy answer) or created from a different output owned by the same wallet (perhaps a more technical, but hopefully straightforward, answer).

The transaction private key, `x`, probably signs the ring and the key image, right? My hunch is that the distinctive ring signature provides a way to check the math that `P` (the output public key) being spent is a ring member, and is also associated with `I`, the key image that's attached to the ring signature.

How does it work? I don't understand how the verification works without revealing the actual tx pub key being spent.

I've been reading other SE questions and answers here, here, and here. I haven't found an answer expressed in the way I'd like to understand it.

The signature verification algorithm will only return a "correct signature" result if `P` is equal to `x·G` (i.e. the real spent output's public key is derived from the output's secret spend key `x`) and if `I` is equal to `x·Hp(P)` (i.e. the key image I is derived from the output's secret spend key `x`).

If you can understand the algorithms on page 6 of MRL-0003, you will see that the `Li` elements check the public key and the `Ri` elements check the key image.

```Signature algorithm:
--------------------
i ← 0
while i < numkeys do
if i = s then
k ← random Fq element
Li ← k·G
Ri ← k·Hp(Pi)
else
k1 ← random Fq element
k2 ← random Fq element
Li ← k1·Pi + k2·G
Ri ← k1·I + k2·Hp(Pi)
ci ← k1
ri ← k2
end if
i ← i + 1
end while
h ← Hs(prefix + {Li} + {Ri})
cs ← h − ∑ci   (with i ≠ s)
rs ← k − x·cs
return (I, {ci}, {ri})

Verification algorithm:
-----------------------
i ← 0
while i < numkeys do
L′i ← ci·Pi + ri·G
R′i ← ri·Hp(Pi) + ci·I
i ← i + 1
end while
h ← Hs(prefix + {L′i} + {R′i})
h ← h − ∑ci
return (h = 0 (mod q))
```

The verification algorithm will give a "correct signature" result when `∑ci` is equal to `Hs(prefix + {L′i} + {R′i})`. For this to be true, `{L'i}` must be equal to `{Li}` and `{R'i}` must be equal to `{Ri}`.

For the decoy keys (i.e. `i ≠ s`) it is obvious that `L'i = Li` and `R'i = Ri` as they are generated with identical formulas.

For the real key (i.e. `i = s`):

```    L's = Ls
<=> cs·Ps + rs·G = k·G
<=> cs·Ps + (k - cs·x)·G = k·G
<=> cs·Ps + k·G - cs·x·G = k·G
<=> cs·Ps = cs·x·G

R's = Rs
<=> rs·Hp(Ps) + cs·I = k·Hp(Ps)
<=> (k - cs·x)·Hp(Ps) + cs·I = k·Hp(Ps)
<=> k·Hp(Ps) - cs·x·Hp(Ps) + cs·I = k·Hp(Ps)
<=> cs·I = cs·x·Hp(Ps)
```

So for the signature to be valid, the signer has to know the secret key `x` so that `x·G = Ps` and `x·Hp(Ps) = I`.