3

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.

3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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