Linkable ring signatures and key images (2004)

A ring signature is too anonymous for money: a spender could sign twice with the same coin and nobody could tell. Liu, Wei and Wong added a key image \(I = H_p(P)^x\), fixed by the signer’s key pair but revealing nothing about which key it is. Every signature by the key carries the same image, and the same response proves both

\[L_i = g^{r_i} P_i^{c_i}, \qquad R_i = H_p(P_i)^{r_i} I^{c_i},\]

so the image cannot be faked. A ledger stores the images of spent coins and rejects a repeat. CryptoNote, and Monero after it, hash the public key rather than the ring into \(H_p\), so the images link across rings.

import matplotlib.pyplot as plt

import blockchainkit as bk

G = bk.crypto.TEACHING_GROUP

A ledger of spent key images

secrets = list(range(1_001, 1_011))
outputs = [G.public(x) for x in secrets]
spent: set[int] = set()


def accept(message, ring, signature):
    if not bk.privacy.lsag_verify(message, ring, signature):
        return "invalid"
    if signature.key_image in spent:
        return "double spend"
    spent.add(signature.key_image)
    return "accepted"


first_ring = [outputs[i] for i in (0, 3, 4, 7)]
second_ring = [outputs[i] for i in (2, 4, 8, 9)]
pay_bob = bk.privacy.lsag_sign(b"pay bob", first_ring, 2, secrets[4], seed=1)
pay_eve = bk.privacy.lsag_sign(b"pay eve", second_ring, 1, secrets[4], seed=2)
pay_cat = bk.privacy.lsag_sign(b"pay cat", second_ring, 3, secrets[9], seed=3)
results = [accept(b"pay bob", first_ring, pay_bob), accept(b"pay eve", second_ring, pay_eve)]
results.append(accept(b"pay cat", second_ring, pay_cat))
print(results)
assert results == ["accepted", "double spend", "accepted"]
assert bk.privacy.linked(pay_bob, pay_eve) and not bk.privacy.linked(pay_eve, pay_cat)

['accepted', 'double spend', 'accepted']

The image reveals nothing of the key

images = [bk.privacy.key_image(x) for x in secrets]
fig, ax = plt.subplots(figsize=(6, 4))
ax.scatter([p / G.p for p in outputs], [i / G.p for i in images], color="#2563eb")
ax.set(xlabel="public key / p", ylabel="key image / p", xlim=(0, 1), ylim=(0, 1))
ax.set_title("Key images are unrelated to their public keys")
fig.tight_layout()

plt.show()

Exercise

Why must the key image use \(H_p(P)\) rather than \(g\), that is, why would \(I = g^x\) be a disaster? A worked solution is in Exercises: privacy.