## Ring Signatures in the CLSAG era

Let's understand what are CLSAG (Concise Spontaneous Anonymous Group) signatures, how it differs from MLSAG and why the Monero developers implemented it on 17 October 2020. A simple description in layman's terms and a comprehensive explanation of the verification code is provided here.

#### CLSAG in Layman's terms

The purpose of implementing CLSAG was to reduce the operational cost (storage and computation) by removing the decoys in the commitment rings, so they won't be stored in the blockchain anymore and therefore a lot of space will spared. This also promotes the linkability between the commitment and the public key ring. CLSAGs are half way between bLSAGs and MLSAGs. Instead of having only one dimension like bLSAG (only for the public key members) or two dimensions like MLSAG (one for the public key and another for the commitment members), CLSAG will only store the signatures for the public key members and only the commitment that unlocks the real output (which nobody can tell which one is the real one by just looking at the commitment or signatures).

#### CLSAG Signatures in practice

Before understanding the generation and verification function of a CLSAG signature (generate_CLSAG(msg,p,P,z,C_offset,C,C_nonzero) and check_CLSAG(msg, s, c1, D, P, C_nonzero, C_offset)), we need to understand its inputs arguments and to what they relate to.

##### Message (m)

The message represents all the information of a transaction (version, unlock time, inputs, outputs, extra, rct_signatures and rct_prunable) except the ring signatures (CLSAGs). It can only be signed by the person owning the private key corresponding to the published public key.

In the CLSAG era, the message is divided into three parts:

• P1 = version + unlock_time + vin + vout + extra
• P2 = rct_signatures (Tx type, fees, amounts, outPk)
• P3 = rct_prunable or rangeproof coefficients (A,S,T1,T2,taux,mu,L,R,a,b,t)

The final message $m$ is the hash of the sum of the hashes of each part, i.e. $m =\mathcal{H} (\mathcal{H}(P1) + \mathcal{H}(P2) +\mathcal{H}(P3))$

Let's get the transaction c39652b79beb888464525fee06c3d078463af5b76d493785f8903cae93405603 as example.

Here we have:

P1 = 02000102000be9aac314d8e710844d8d258133d9f701b0649e568b0cb50b1dea8103138a37c5543f3c632ef80331940cabeba29b758045db328d8d8a99de380200025155f659da61b507b0b8591cbef0ba1534b9db29a69be4a933f7897e58870b250002002de4643160fb8351a841f8079aa5af2ac62c9631bb2d5a48fcdb564cb699d12c01eaaa5acba0bc44657da783903d3de7febf7124ae03cf578938244068b475d906020901da0190b93466979e

hash(P1) = ffc97c3febc55e14f0c2ee78092e023935121e7d750cbeb65511e4368242fe22

hash(P2) = 5778b38f679c0bfca78e8ab9a1ba35f029e0e1b33a3be91849cbf30c18c7a6f1

hash(P3) = 93525ff81e8f015f06bf9668c8ef67844de4deac85de2edea4aa0e7298d1da2b

Let's build our Public Key vectors, which means, let's get the participants (members) of our ring as represented in figure 1.

The members of the ring can be retrieved by looking at the field ['vin']['key_offsets'] stored in a transaction. The members are previous transactions outputs (stealth addresses and commitments) that contains funds to be spent from.

It is important to notice that every output (stealth address and commitment) is stored by its index number (which is the index position where that output can be found in the pile of its respective amount). This index number is what the key_offset represents. Alongside with that, we can also retrieve the block_height and tx_id.

In the case of a RCTTypeCLSAG transaction, we also have one pseudo output for each input (or key_image). Which can be retrieved from a transaction at the 'pseudoOuts' field.

Finally, from the key_offsets, let's retrieve what we need to build our Public Key vector which has the dimensions $n$, where $n$ is the number of participants in one ring which is the length of the key_offsets vector. In order to do so, we need to extract the 'key' which represents the stealth address of a previous transaction.

We also have to extract the 'mask' which represents the commitment to a value of a previous transaction.

Therefore, our algorithm to build the Public Key vector, with $n$ being the length of the key_offsets, looks like:

RCTTypeCLSAG(Type 5)

For $i = 0 .. n$:

$pubs[i] = \text{get_outs(key_offsets[}i\text{])["key"]}$

$masks[i] = \text{get_outs(key_offsets[}i\text{])["mask"]}$

Notice that we are only verifying one input or key_image at a time. We need to repeat this procedure for as many inputs that a transaction has.

See an example below.

Let's get the transaction c39652b79beb888464525fee06c3d078463af5b76d493785f8903cae93405603 as example.

It is a RCTTypeCLSAG and we have one input only.

Stealth addresses ring members:
pubs = [09a9cd2976908e172096b41bd6e701baf89a54580ddaf7338e837f944cacdf4e, d899b26b27778a5bb4c05c537a721f7822442ee4c6d9feebac62a15d76e23efe, a65d0610b529f918d486abe7bdcc5a4aaea3e40ae1791cda91399113d9727136, 08f4824943cc66da49aa4f2d4e7b6370026d1bc3d3e542c796a750f0d9a53864, 3f6e0c940ee6d00f23c3bfffd7a49cd771da7b3814f8023c87e070d5a94b312f, 5e0709be62408e42d4f0448ce928514cc2f2e2fa7be8ef1d71fca8493d9392cb, 5073c115a4b9b726c5131c83a84c239cb38a408e404f8669ceb68b9aefc4ade9, 8ca62cc1330761cdb7f7f0d7d6028e3ffd94c94a55f703adc62a024f650f88c7, c81f7662f255c82d563db4635f8ecf50e7b3378c739d684a0d43b808f9cca905, f3d71b7bdb06602fbeafec7bc99b87e846eff10faf8c4119a8f2e39ac8754a9f, 41bd8dab5bdc5af694dde135a7278e8e0aab0cb863483e037a73fd17a6a8a36a]

PseudoOuts:
C_offset = c4cf22334e32fd33193fbfa1c4cb9e3182fb2357cf7a800f552b87579cc41d99



##### Key Image (KI)

The key image is just the secret key times the hash of the public key. It can be defined by the equation: $KI = x\mathcal{H_p}(P)$. Where $I$ is the key image, $x$ is the secret key and $\mathcal{H_p}(P)$ is the hash mapped to a point of the public key generated by $x$.

Notice that this 'secret key' in the context of Monero is actually the secret key to unlock an output (stealth address) and it is a function that depends on the transaction public key, the secret view key, the secret spend key and the output index. Therefore, one person can create multiple key_images with the same secret view and spend keys, if this person have multiple outputs addressed to him/her, of course. The equation below shows what this secret key represents but please check how 'One-time addresses' are created, if you want to further investigate it. You will find a good resource here.

$k_t^O = \mathcal{H_s}(rK_t^v,t) + k_t^s \qquad \text{---> secret key} \\$ $K_t^O = k_t^O G \qquad \text{---> public key}\\$

Let's suppose that we have the following private (secret) key: x = 09321db315661e54fe0d606faffc2437506d6594db804cddd5b5ce27970f2e09

From it, we can derive the public key by the definition of a point in an elliptic curve.

The public key (P) is defined by: P = xG

Using the Monero elliptic curve definitions (Edwards25519), we have P = cd48cd05ee40c3d42dfd9d39e812cbe7021141d1357eb4316f25ced372a9d695

In order to make it possible to perform another point multiplication, we need to treat P as a hash and map it to a point in the elliptic curve. The $\mathcal{H_p}$ is responsible for that. In our case, $\mathcal{H_p}(P)$ is the Point $\mathcal{H_p}(P)$ = c530057dc18b4a216cc15ab76e53720865058b76791ff8c9cef3303d73ae5628

Finally, we need to perform another point multiplication, which is $KI = x\mathcal{H_p}(P)$. The key image in our case is $KI$ = d9a248bf031a2157a5a63991c00848a5879e42b7388458b4716c836bb96d96c0

In the context of CLSAG, let's get the key_image of the following transaction: c39652b79beb888464525fee06c3d078463af5b76d493785f8903cae93405603

Key Image: ea8103138a37c5543f3c632ef80331940cabeba29b758045db328d8d8a99de38

##### Generating a CLSAG signature

The idea behind the CLSAG signatures is also simple. We want to obfuscate the sender by proving that someone in the ring set signed the message and transferred the funds without being able to specify exactly who.

In order to generate a CLSAG signature, let's see what we need generate_CLSAG(msg,p,P,z,C_offset,C,C_nonzero) to pass as parameters:

• $msg$ is the message discussed before.
• $p$ is the private key corresponding to one of the ring members.
• $P$ is the set of public keys (stealth_addresses) of the ring.
• $z$ is the private key of the new commitment involved in the transaction.
• $C_{offset}$ is the pseudoOut, which is the new commitment of the input.
• $C$ is the set of commitments of the ring.
• $C_{nonzero}$ is equal to $C[i] - C_{offset}$ for all i.

Before we talk about the CLSAG scheme, we need to define some variables. Let's get started.

If $l$ is the secret index of the ring member signing the transaction, then we have: $P[l]=pG$ , $C[l]=zG$ and for all i, we have $C_{nonzero}[i]=C[i]+C_{offset}$ (for hashing purposes).

Let's start by defining some domain names which will be hashed with some values later:

• str_agg0 = "CLSAG_agg_0"
• str_agg1 = "CLSAG_agg_1"
• str_round = "CLSAG_round"

Now let's define some other variables that will be needed later:

• I: The key image can be simply obtained by $I = p\mathcal{H_p}(P[l])$
• D: The auxiliary key image D is defined as $D = (1/8) z\mathcal{H_p}(P[l])$
• strP: The concatenation of all public keys in the ring
• strC: The concatenation of all commitment keys in the ring
• strC_nonzero: The concatenation of all C_nonzero[i]

Finally, let's get the variables $mu_P$ and $mu_C$ which are separated by the domain name:

• $mu_P = \mathcal{H_s}\text{(str_agg0+strP+strC_nonzero+I+D+C_offset)}$
• $mu_C = \mathcal{H_s}\text{(str_agg1+strP+strC_nonzero+I+D+C_offset)}$

Now we are ready to see how the ring signature generation scheme works in CLSAG.

Considering $\alpha$ a random scalar, let's start defining the following points:

• $aG = \alpha G$
• $aH = \alpha \mathcal{H_p}(P[l])$

Now define $c$ as:

$c =\mathcal{H_s}\text{(str_round+strP+strC_nonzero+C_offset+msg+aG+aH)}$

We want $c1$ (a new variable) to be equal to $c$ when the index i=(l+1)%n is equal to zero. Therefore, if $i == 0$ then $c1 = c$.

Now let's start our loop at i and do it n times, where is the number of ring members, i,e: for i = l+1,l+2,..,n-1,0,1,..,l-1,l.

$s[i] = \text{random_scalar()} \\$ $cp = c \, mu_P \\$ $cc = c \, mu_C \\$ $L = s[i]G + cpP[i]+ ccC[i] \\$ $R = s[i]\mathcal{H_p}(P[i]) + cpI + 8ccD \\$ $\text{str_hash = str_round+strP+strC_nonzero+str(C_offset)+str(msg)} \\$ $\text{str_hash += str(L) + str(R)} \\$ $c = \mathcal{H_s}\text{(str_hash)} \\$

We increase the counter and check if it is equal to zero:

$i = (i+1) \% n \\$ $\text{ if i == 0 : { c1 = c }} \\$

Finally, we need to modify the signature s at the index l.

$s[l] = alpha - c(p \, mu_P+ z \, mu_C)$

As you noticed, the signature is basically composed by the random numbers that we generated except at the index where we control the funds of one of the members. But of course, for an external reader, he cannot tell where the secret index is.

The final signature will be s,c1 and D

$\sigma = \{ s, c1, D \}$

Let's suppose that we have the following parameters as inputs:

msg = str('612ebe1b1bfdd4f49732afedc43f4c815f899e190f316eda75fad5423e53b8e6')
p = Scalar('073d1d6d6d3ec1b47b03b40d4fd9fec97fca4b61ed49a66bb32e818b5d9c710f')
z = Scalar('64aca5a5c70ff73ef3a192f8286efb1353eb8c642ef96d8c263d8b4ea2259b0c')
C_offset = Point('feae5544786270b394a8f34f753d550be92a318c291926b7d9bfa7fb4cde3745')
l = 1



Let's also suppose that we execute the following code to produce the signatures $s$ and $c1$ and $D$:

def generate_CLSAG(msg,p,P,z,C_offset,C,C_nonzero,Seed=None):
inv8 = Scalar(8).invert()
n = len(P) # ring size

# Recover the private key index
l = None
for i in range(n):
if P[i] == dumber25519.G*p and C[i] == dumber25519.G*z:
l = i
break
if l is None:
raise IndexError('Private keys must correspond to public keys!')

# Construct key images
I = hash_to_point(str(P[l]))*p
D = hash_to_point(str(P[l]))*z*inv8

domain0 = 'CLSAG_agg_0'
domain1 = 'CLSAG_agg_1'
domain_round = 'CLSAG_round'

str0 = str(Scalar(0))
str_agg0_aux = domain0.encode("utf-8").hex()
str_aux = str0[len(str_agg0_aux):]
str_agg0 = str_agg0_aux + str_aux

str_agg1_aux = domain1.encode("utf-8").hex()
str_aux = str0[len(str_agg1_aux):]
str_agg1 = str_agg1_aux + str_aux

str_round_aux = domain_round.encode("utf-8").hex()
str_aux = str0[len(str_round_aux):]
str_round = str_round_aux + str_aux

strP = ''
for i in range(len(P)):
strP += str(P[i])

strC = ''
for i in range(len(C)):
strC += str(C[i])

strC_nonzero = ''
for i in range(len(C_nonzero)):
strC_nonzero += str(C_nonzero[i])

# Now generate the signature
mu_P = hash_to_scalar(str_agg0+strP+strC_nonzero+str(I)+str(D)+str(C_offset))
mu_C = hash_to_scalar(str_agg1+strP+strC_nonzero+str(I)+str(D)+str(C_offset))
s = [None]*n

alpha = random_scalar()

# Private index
aG = dumber25519.G*alpha
aH = hash_to_point(str(P[l]))*alpha
c = hash_to_scalar(str_round+strP+strC_nonzero+str(C_offset)+str(msg)+str(aG)+str(aH))

i = (l+1) % n
if (i==0):
c1 = copy.copy(c)

while (i!=l):
s[i] = random_scalar()
cp = c*mu_P
cc = c*mu_C

L = s[i]*dumber25519.G + cp*P[i]+ cc*C[i]

R = s[i]*hash_to_point(str(P[i])) + cp*I + cc*D*Scalar(8)

str_hash = str_round+strP+strC_nonzero+str(C_offset)+str(msg)
str_hash += str(L) + str(R)

c = hash_to_scalar(str_hash)

i = (i+1) % n
if i==0:
c1 = copy.copy(c)

s[l] = alpha - c*(p*mu_P+mu_C*z)

return s,c1,D



In the end, a valid signature would look like:

s:

c1:
437a25418bd78a4712740c36c84f7b24a983d91e064456a3502bc3da4531ec0f

D:
c73294efab521c03b43a97ddd9313decb40aed61fa12395772a18751d319cc3e


##### Checking a CLSAG signature

To check if the signature is valid let's first understand the math behind it. The verification function looks like check_CLSAG(msg, s, c1, D, P, C_nonzero, C_offset), where:

• $msg$ is the message being signed.
• $s$ is the signature component 's' of the CLSAGs.
• $c1$ is the signature component 'c1' of the CLSAGs.
• $D$ is the signature component 'D' of the CLSAGs.
• $I$ is the key_image of the ring.
• $P$ are the ring members (stealth addresses).
• $C_nonzero$ are the commitments for every ring member. They represent the OutPk of a previous transaction.
• $C_{offset}$ is the pseudoOuts or pseudo output commitment.

In the same way we did to generate a CLSAG ring signature, let's start by defining some domain names which will be hashed with some values later:

• str_agg0 = "CLSAG_agg_0"
• str_agg1 = "CLSAG_agg_1"
• str_round = "CLSAG_round"

Now let's define some other variables that will be needed later:

• strP: The concatenation of all public keys in the ring
• strC_nonzero: The concatenation of all commitment keys in the ring. They are the same as the strC_nonzero in the generation function.

Finally, let's get the variables $mu_P$ and $mu_C$ which are separated by the domain name:

• $mu_P = \mathcal{H_s}\text{(str_agg0+strP+strC_nonzero+I+D+C_offset)}$
• $mu_C = \mathcal{H_s}\text{(str_agg1+strP+strC_nonzero+I+D+C_offset)}$

Now we are ready to see how we can check the ring signature scheme in CLSAG.

Let's copy c1 to c and execute the following steps for i = 0 .. n-1:

$cp = c \, mu_P$ $cc = c \, mu_C$ $L = s[i]G + cpP[i]+ cc\text{(C_nonzero[i] - C_offset)}$ $R = s[i]\mathcal{H_p}(P[i]) + cpI + 8ccD$ $\text{str_hash = str_round+strP+strC_nonzero+str(C_offset)+msg}$ $\text{str_hash += str(L) + str(R)}$ $c = \mathcal{H_s}\text{(str_hash)}$

Lastly, if $c$ equals $c1$, then the signature is valid.

Let's check the signature from the examples above: c39652b79beb888464525fee06c3d078463af5b76d493785f8903cae93405603.

We have as inputs:

message:

pubs:

C_offset:
c4cf22334e32fd33193fbfa1c4cb9e3182fb2357cf7a800f552b87579cc41d99

I:
ea8103138a37c5543f3c632ef80331940cabeba29b758045db328d8d8a99de38

s:

c1:
400328b595456b6451dc07eac7c8f6849dc065bb7f5ac49cff1530658bcc4d09

D:
d03e2f9611a5561dc3a90b3b2f3d933dc110db73904aeee5abcd2362a0e1b045



If we execute the following code, we will see that the signatures match.

def check_CLSAG(msg, s, c1, D_aux,I, P, C_nonzero, C_offset):

domain0 = 'CLSAG_agg_0'
domain1 = 'CLSAG_agg_1'
domain_round = 'CLSAG_round'

str0 = str(Scalar(0))
str_agg0_aux = domain0.encode("utf-8").hex()
str_aux = str0[len(str_agg0_aux):]
str_agg0 = str_agg0_aux + str_aux

str_agg1_aux = domain1.encode("utf-8").hex()
str_aux = str0[len(str_agg1_aux):]
str_agg1 = str_agg1_aux + str_aux

str_round_aux = domain_round.encode("utf-8").hex()
str_aux = str0[len(str_round_aux):]
str_round = str_round_aux + str_aux

D = copy.copy(D_aux)

strP = ''
for i in range(len(P)):
strP += str(P[i])

strC_nonzero = ''
for i in range(len(C_nonzero)):
strC_nonzero+= str(C_nonzero[i])

mu_P = hash_to_scalar(str_agg0+strP+strC_nonzero+str(I)+str(D)+str(C_offset))
mu_C = hash_to_scalar(str_agg1+strP+strC_nonzero+str(I)+str(D)+str(C_offset))

c = copy.copy(c1)

print('c: ')
print(c)

i = 0
n = len(P)

while (i < n):
cp = c*mu_P
cc = c*mu_C

L = s[i]*dumber25519.G + cp*P[i]+ cc*(C_nonzero[i] - C_offset )
R = s[i]*hash_to_point(str(P[i])) + cp*I + cc*D*Scalar(8)

str_hash = str_round+strP+strC_nonzero+str(C_offset)+msg
str_hash += str(L) + str(R)

c = hash_to_scalar(str_hash)
i = i+1

print('c: ')
print(c)

c_final = c - c1

import ipdb;ipdb.set_trace()

return c_final