Ring signatures

How to prove "I own one of these keys" without saying which

First — a plain Schnorr signature

To understand rings, first see how to prove knowledge of one key x for P = x·G:

1. The signer picks a random α and computes α·G.
2. Computes the challenge c = Hs(message ‖ α·G).
3. Computes the response s = α − c·x. The signature is (c, s).
4. The verifier reconstructs s·G + c·P = (α − cx)·G + c·x·G = α·G and checks that Hs(message ‖ α·G) = c.

Without knowing x you can't find an s for a given c: c depends on α·G, which must be fixed before you learn c.

The ring idea: close the chain of challenges

Now we have n public keys P₀ … Pₙ₋₁ and know the key to just one, say Pπ. The trick: each challenge is computed from the previous link, and the chain closes into a ring.

1. At the real key's position π, take a random α and compute the next challenge: c_{π+1} = Hs(m ‖ α·G).
2. For each following (foreign) key pick a random sᵢ and compute c_{i+1} = Hs(m ‖ sᵢ·G + cᵢ·Pᵢ). Go around the ring.
3. Return to π, now knowing c_π. For the ring to close we need s_π·G + c_π·P_π = α·G, i.e. s_π = α − c_π·x. This can be computed only by knowing x.
4. Signature: (c₀, s₀, s₁, …, sₙ₋₁).

The verifier starts from c₀, walks every link with the same formula and checks it came back to the same c₀. All links look alike — you can't tell from the signature where the "closing" happened.

Linkability: LSAG

A plain ring signature doesn't stop the same output being spent twice in different rings. So Monero uses a linkable signature: the signer publishes a key image I = x·Hp(P_π) and in every link additionally proves that the same x connects I and Hp(Pᵢ):

Two uses of the same key give the same I — and the network rejects the second spend.

MLSAG → CLSAG

In RingCT you must prove not one but two statements per ring member: knowledge of the output key, and that the difference of commitments commits to zero (see RingCT). At first (2017) this was done with MLSAG — essentially two rings glued together: two s values per ring member.

In October 2020 (hard fork v13) it was replaced by CLSAG (Concise LSAG): the two keys at a position are folded into one via a random linear combination with hash coefficients. One s per ring member. The signature got about 25% smaller and faster to verify.

History of ring size

Why fixed? If everyone chose their own, a non-standard ring size would fingerprint the wallet.

Why not 1000?

CLSAG size and verification time grow linearly with ring size. A 1000-member ring means ~32 KB per input and dozens of times slower node sync. Schemes with logarithmic size (Triptych, Arcturus, Seraphis) were researched, but in the end Monero chose the radical option — FCMP++, where the "ring" is the whole blockchain.