## Understanding Ring Signatures

This page is divided into two sections. The first one is meant to explain what ring signatures are for someone that has no background in mathematics and computer science. The second for those who wants to see how deep the rabbit hole goes.

#### Ring Signatures in Layman's terms

Imagine that we are playing a bit different version of the game 'I went to market and I bought...'. Instead of the next person repeating all the previous fruits before mentioned, he has only to say the last one and provide a new one.

Our goal is to prove that we have control over one person and insider information about the ring formation. Let's imagine that we are playing this game with 6 people and instead of fruits we are playing with secret keys, which are just huge numbers. The scenario can be the following: The first person ($P_1$) will repeat the previous fruit (a huge number) that was told to her and choose a new fruit (56b...a60). As $P_1$ is starting, he can make up a fruit as if someone told him (46c...118). Person number two ($P_2$) will pick $P_1$ fruit (56b...a60) and create another one (d1b...130). The game continues until person $P_6$. At this point all the fruits have changed. If we have privileged information (we know which random fruit $P_1$ chose to start) and we control $P_6$, then we can close the ring by forcing $P_6$ to chose the random fruit that $P_1$ chose to start. Next, we turn the ring so an outside observer can't tell where it has started.

For an outside observer, he can't tell who has the insider information and who is the person constructing the ring and signing the message. That is the idea of the ring, hide the sender among other possible candidates in the blockchain.

Note 1: Any person can create a ring with the members he wants, the v1 allows members that have the same amount of XMR being spent and does not provide a minimum or maximum quantity of ring members.

#### Ring Signatures in practice

The best resources available are: the whitepaper of cryptonote and the book Zero To Monero. This work has the intention of providing more practical examples and tools to understand and verify the components, like ring signatures, to prove the non-occurrence of inflation.

Before we talk about how to verify the ring signatures, it makes sense to understand how they are created. Let's take a look on the generate_ring_signature function.

The generate_ring_signature function has the following inputs: prefix, image, pubs, pubs_count, sec, sec_index and the following outputs: signatures, it can be found in the monero source code here.

All the parameters will be explained with the minimum theory necessary to understand it and examples will be given to clarify what is happening. Let's move forward sequentially.

###### Prefix

There are two variables that need to be understood here. The prefix and the prefix_hash. As the name suggests, the prefix is the transaction information encoded in hexadecimal without the signatures. The prefix_hash is the hash, using the hash function Keccak256, of the prefix. An example is illustrated below.

If we enter the following commmand in monerod (the monero daemon) to print the first transaction in the blockchain print_tx beb76a82ea17400cd6d7f595f70e1667d2018ed8f5a78d1ce07484222618c3cd +hex +json, we will get the following results:

Found in blockchain at height 110

{ "version": 1, "unlock_time": 0, "vin": [ { "key": { "amount": 7000000000000, "key_offsets": [ 1, 4, 1, 17, 7, 1 ], "k_image": "f254220bb50d901a5523eaed438af5d43f8c6d0e54ba0632eb539884f6b7c020" } } ], "vout": [ { "amount": 9000000, "target": { "key": "f9c7cf807ae74e56f4ec84db2bd93cfb02c2249b38e306f5b54b6e05d00d543b" } }, { "amount": 90000000, "target": { "key": "b6abb84e00f47f0a72e37b6b29392d906a38468404c57db3dbc5e8dd306a27a8" } }, { "amount": 900000000, "target": { "key": "cfc40a86723e7d459e90e45d47818dc0e81a1f451ace5137a4af8110a89a35ea" } }, { "amount": 9000000000, "target": { "key": "6b19c796338607d5a2c1ba240a167134142d72d1640ef07902da64fed0b10cfc" } }, { "amount": 90000000000, "target": { "key": "1f6f655254fee84161118b32e7b6f8c31de5eb88aa00c29a8f57c0d1f95a24dd" } }, { "amount": 900000000000, "target": { "key": "3321af593163cea2ae37168ab926efd87f195756e3b723e886bdb7e618f751c4" } }, { "amount": 1000000000000, "target": { "key": "95ed2b08d1cf44482ae0060a5dcc4b7d810a85dea8c62e274f73862f3d59f8ed" } }, { "amount": 5000000000000, "target": { "key": "dc50f2f28d7ceecd9a1147f7106c8d5b4e08b2ec77150f52dd7130ee4f5f50d4" } } ], "extra": [ 1, 211, 79, 144, 172, 134, 29, 14, 233, 254, 56, 145, 101, 106, 35, 78, 168, 106, 138, 147, 191, 81, 162, 55, 219, 101, 186, 160, 13, 63, 74, 161, 150 ], "signatures": [ "a9e1d89bc06b40e94ea9a26059efc7ba5b2de7ef7c139831ca62f3fe0bb252008f8c7ee810d3e1e06313edf2db362fc39431755779466b635f12f9f32e44470a3e85e08a28fcd90633efc94aa4ae39153dfaf661089d045521343a3d63e8da08d7916753c66aaebd4eefcfe8e58e5b3d266b752c9ca110749fa33fce7c44270386fcf2bed4f03dd5dadb2dc1fd4c505419f8217b9eaec07521f0d8963e104603c926745039cf38d31de6ed95ace8e8a451f5a36f818c151f517546d55ac0f500e54d07b30ea7452f2e93fa4f60bdb30d71a0a97f97eb121e662006780fbf69002228224a96bff37893d47ec3707b17383906c0cd7d9e7412b3e6c8ccf1419b093c06c26f96e3453b424713cdc5c9575f81cda4e157052df11f4c40809edf420f88a3dd1f7909bbf77c8b184a933389094a88e480e900bcdbf6d1824742ee520fc0032e7d892a2b099b8c6edfd1123ce58a34458ee20cad676a7f7cfd80a28f0cb0888af88838310db372986bdcf9bfcae2324480ca7360d22bff21fb569a530e"] }

As we can see, the prefix without the signatures ("a9e1...530e") is the hexadecimal value:

When we make the hash using the 'cn_fast_hash' function used in Monero, we get the value:

Tx prefix_hash: ccabefb57635c09cfe66af861f11e1a379cd0de0e030409ab3c26418cf302166

This value can also be obtained using this online tool with the hash function Keccak-256.

###### Key image

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 $KI$ 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

###### Public keys

First, let's consider a set of 'public keys', which are just the stealth addresses of outputs of other transactions. In order to create the 'ring', we will pick $n-1$ random public keys previously available in the blockchain plus the one that we control (which means that we know the secret key for it). Figure 1 shows how the ring members are chosen. Let's say that we know the secret key (or private key) of the member $P_2$, and we create a ring with the following order: $P_2$, $P_1$, $P_3$. Then, the secret index would be 0 (as we know the private key of the first element of the ring). Therefore, our ring is defined as $P_2$, $P_1$, $P_3$, the 'pubs_count' (the quantity of public keys or members in the ring) is 3 and the secret index (the index where our public key with the funds that we want to spend from) is 0.

Now that we have defined all the components of the function generate_ring_signature, let's dive into the math and idea behind it with some equations and examples.

Considering again the first transaction at block 110, we have the 'key offsets' field in 'vin'.

These offsets represent the index at which they are stored in the blockchain according to their amount. It is not trivial to calculate the value of the index as they are stored according to their appearence in the blockchain. They can easily be queried from the blockchain though, by simply using the command 'get_outs' using the RPC calls of the daemon. The first offset value corresponds to the first absolute appearence in the blockchain and the other values are added to this absolute value. For example, we have for the first transaction (block 110), the value: "key_offsets": [ 1, 4, 1, 17, 7, 1]. They correspond to the following ring members:


Offset:
1
Ring member:

Offset:
5
Ring member:

Offset:
6
Ring member:
1e4f2708aa04f52d4607d98ba18bf0f87b5045ff74df71f45649975093d19a12

Offset:
23
Ring member:
d1468a64e2703489fcd7d759bb0ca2a93d4acbdda3aaa77c103f5eb4424ed6b9

Offset:
30
Ring member:
feca0b1c0266f02eed4fb19f97bc077171de836d5dcca99280367f9c94ed05e8

Offset:
31
Ring member:
3c65dd846c83fb48036cd978d4d40c35065de407d20df34234332e5db49c6fde



###### Generate ring signatures

The idea behind ring signatures is 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.

Now that we have an idea how the ring signatures work, let's see the math and code behind it.

First, consider a set of n members (where n is the size of participants in the ring) and their values are big random numbers with the size of the secret key (64 hexadecimal characters = 256 bits). Let's call this set $Q = \{q_0,..,q_n\}$. Let's also consider another set of random numbers $W = \{ w_i \; | \; i = 0,..,n \; | \; i \neq s \}$.

Now, let's apply the following algorithm as specified in the cryptonote paper.

$L_i = \begin{cases} q_iG & if \quad (i = s) \\ q_iG + w_iP_i & if \quad (i \neq s) \end{cases}$ $R_i = \begin{cases} q_i\mathcal{H_p}(P_i) & if \quad (i = s) \\ q_i\mathcal{H_p}(P_i) + w_iI & if \quad (i \neq s) \end{cases}$

Here we define $L_i$ and $R_i$ for each ring member. Notice that we only need to know the set of public keys participating in the ring, the key image that we control the funds and the sets of random numbers that we created.

The next step is to calculate the hash of the message (the prefix) and bind it together with the random generated numbers. So let's define the result of this operation $c$. Where $c = \mathcal{H}(m,L_1,...,L_n,R_1,...,R_n)$

Now, we have to calculate the signature. It will linearly scale with the number of members in the ring and it is composed by two parts, the $c$ and $r$ components, defined as below.

$c_i = \begin{cases} c - \displaystyle\sum_{W} c_i\ mod\ l\ & if \quad (i = s) \\ w_i & if \quad (i \neq s) \end{cases}$ $r_i = \begin{cases} q_s - c_s x\ mod\ l\ & if \quad (i = s) \\ q_i & if \quad (i \neq s) \end{cases}$

Finally, we need to publish the signature so it can be later validated. It has the following shape $\sigma = (c_1,r_1,...,c_n,r_n)$

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.

Let's consider the following snippet in Python to generate a ring signature.

def generate_ring_signature(prefix, image, pubs, pubs_count, sec, sec_index):

summ = Scalar(0)
Li = [Scalar(0) for xx in range(pubs_count)]
Ri = [Scalar(0) for xx in range(pubs_count)]

sigc = [Scalar(0) for xx in range(pubs_count)] #these are the c[i]'s from the whitepaper
sigr =[Scalar(0) for xx in range(pubs_count)] #these are the r[i]'s from the whitepaper

for ii in range(0, pubs_count):
if (ii == sec_index):

# Let's generate the random qi
qs = dumb25519.random_scalar()
print('Random number qi generated for index '+str(ii)+' corresponding to the secret index')
print(qs)

# Get Li for i=s
Li[ii] = scalarmultBase(qs) #L[i] for i = s
print('Li: ')
print(Li[ii])

# Makes the hash of the public key and maps it to a point in the elliptic curve
tmp1 = hash_to_point(str(pubs[ii]))
print('Result of hash_to_point: ')
print(tmp1)
Ri[ii] = qs * tmp1
print('Ri: ')
print(Ri[ii])

else:

# Let's generate the random qi and wi for i!=s
qi = dumb25519.random_scalar()
print('Random number qi generated for index '+str(ii))
print(qi)
wi = dumb25519.random_scalar()
print('Random number qi generated for index '+str(ii))
print(qi)

# Get Li for i!=s
Li[ii] = ge_double_scalarmult_base_vartime(qi, pubs[ii], wi) #this is L[i] for i != s
print('Li: ')
print(Li[ii])

tmp2 = hash_to_point(str(pubs[ii]))
print('Result of hash_to_point: ')
print(tmp2)
# Makes the hash of the public key, maps it to a point in the elliptic curve and sums this point with wi*I
Ri[ii] = ge_double_scalarmult_vartime(wi, tmp2, qi, Point(image)) #R[i] for i != s
print('Ri: ')
print(Ri[ii])

# Create the signature for i!=s
sigc[ii] = qi  #the random c[i] for i != s
sigr[ii] = wi  #the random r[i] for i != s

# Create the variable summ as the summ of the signatures except for i=s
summ = sc_add(summ, sigc[ii]) #summing the c[i] to get the c[s] via page 9 whitepaper

# Construct the hash of the message (which contains the values and other information)
buf = struct.pack('64s', prefix)
for ii in range(0, pubs_count):
buf += struct.pack('64s', str(Li[ii]).encode())
buf += struct.pack('64s', str(Ri[ii]).encode())

print('The message c is: ')
print(buf)

c = hash_to_scalar(buf.decode())
print('The hash of the message is: ')
print(c)

# The signature at the secret index
sigc[sec_index] = sc_sub(c, summ) # c[s] = hash - sum c[i] mod l
sigr[sec_index] = sc_mulsub(sigc[sec_index], sec, qs) # r[s] = q[s] - sec * c[index]

print('The signature c: ')
print(sigc)

print('The signature r: ')
print(sigr)
return image, sigc, sigr



If we take as input the following arguments:

        prefix = b"8ae47e12cca160c1a52e5517f6f1822d2bb6f1a24e8094b78891458f2b3e4d5d"
image = "f1206393161213a5e4093f9c65e6ef92ca7f21b3513c90e50422e1280ca8165b"
pubs = PointVector(pubs_array)
pubs_count = 1
sec = Scalar("568325b113beabab5b8a1643b065f4bae5181c7b2026ea8dfefeff118ba6de0d")
sec_index = 0

ima, sic, sir = generate_ring_signature(prefix, image, pubs, pubs_count, sec, sec_index)



Then the generated results and signature will be the following:

Random number qi generated for index 0 corresponding to the secret index
Li:
Result of hash_to_point:
2b444877eac6f5e10376e338107ce5a8d07ddb35272cb78f1db4436ff6db355b
Ri:
Random number qi generated for index 1
26bfcd7c0111f0eff2747d04e2c0c7ae0d2378489e0b6f389c891a24bc63a60d
Random number qi generated for index 1
26bfcd7c0111f0eff2747d04e2c0c7ae0d2378489e0b6f389c891a24bc63a60d
Li:
66bbdb9067a7c2293dafba516651819dc8e35127f0f9a066e06f556b932cd4a9
Result of hash_to_point:
Ri:
Random number qi generated for index 2
7d83f8a40ff191ef168248efa77e6eb13448cda71447bf858667fc00674bff0c
Random number qi generated for index 2
7d83f8a40ff191ef168248efa77e6eb13448cda71447bf858667fc00674bff0c
Li:
c541b04e3e8f4fbe04590959f1014f245a0de3cfc82db4b23426df0d384da2c6
Result of hash_to_point:
beee3d78d738ed8b1e75fd00de9e5e959e2bbcdf13eeb2b90ef768fe00b43ca5
Ri:
4ab91b7593f9a72a7633f9a5d1d3c06be815532e00b2a5653364c2d93943391b
The message c is:
The hash of the message is:
a4f48a41d8d41c1c20e21d6d96b95427db79d39f4e94ceeb1a6378bc8c0b120d
The signature c:
The signature r:
[271ccbf212b1bc3c3c8a2fb6b08df96a967e4426f5ed6eed96e61696d7e8bb0e, 65dbaa31298ffd36686d02fb6e279a9066935bab9782dfa07f1f03819a425509, b427b6dc41f5eb7658b251edffd7b44956a59367f3efda5c1b73b943ddd90e0c]


###### Check ring signatures

To check if the signature is valid or not, we have to do the inverse process. The arguments for the check_ring_signature function are: (prefix, key_image, pubs, pubs_count, sigr, sigc). The verifier should first proceed calculating the $L_i^$ and $R_i^$.

$L_i^ = r_iG + c_iP_i \\$ $R_i^ = r_i\mathcal{H_p}(P_i) + c_iI \\$

Next, we need to calculate the sum of $c_i$, which will lead to $c$ as described in the generate_ring_signature, and compare it with the hash of the message and the calculated $L_i^$ and $R_i^$. Which means, verifying if the following is true. $\displaystyle\sum_{i=0}^{n} c_i\ = \mathcal{H}(m,L_1^,...,L_n^,R_1^,...,R_n^) \quad mod\ l\$

The following Python snippet shows how to verify the signature according to the equations above:

def check_ring_signature(prefix, key_image, pubs, pubs_count, sigr, sigc):
Li = [Scalar(0) for xx in range(pubs_count)]
Ri = [Scalar(0) for xx in range(pubs_count)]

summ = Scalar(0)
for ii in range(0, pubs_count):
Li[ii] = ge_double_scalarmult_base_vartime(sigc[ii], pubs[ii], sigr[ii])
print('Li calculated for index = ' + str(ii))
print(Li[ii])
tmp1 = hash_to_point(str(pubs[ii]))
Ri[ii] = ge_double_scalarmult_vartime(sigr[ii], tmp1, sigc[ii], Point(key_image))
print('Ri calculated for index = ' + str(ii))
print(Ri[ii])

buf = struct.pack('64s', prefix)
for ii in range(0, pubs_count):
buf += struct.pack('64s', str(Li[ii]).encode())
buf += struct.pack('64s', str(Ri[ii]).encode())

h = hash_to_scalar(buf.decode())
res = sc_sub(h, summ)
print('Result: ')
print(res)

return sc_isnonzero(hh) == 0


If we verify the first transaction, which happened on block 110, we will have the following results executing this code:

Li calculated for index = 0
Ri calculated for index = 0
Li calculated for index = 1
Ri calculated for index = 1
a0f52f4204c69946160047a10da9ab6482f2c26e991546cf2fb77f5b233faf36
Li calculated for index = 2
ca0e182dbe2996c96e2c6d7454af149f71021a474537b46bf9aa7fe6fb564c38
Ri calculated for index = 2
Li calculated for index = 3
dbd8a6d292e8982e34ae8bb0ba1f51a3eca4715f4729fe8b0d5d453c4c1a1c71
Ri calculated for index = 3
1af4c614dd93f5b968daa2b4fdf95dfda0cc9f103bb72aecc3c261e2329e3b7b
Li calculated for index = 4
6910523101bdc8c687bba320337904b39c9fb18698738bd7e8051905f8354f47
Ri calculated for index = 4
e3cd00b1c6785d4e422a8efb22606bcdbd36497df79af0492a46704399898501
Li calculated for index = 5