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.

Fig. 1 - I went to market...

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 choose 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.

Fig. 2 - Closing the ring

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.


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.

\begin{equation} \begin{aligned} &k_t^O = x = \mathcal{H_s}(k_t^vR,t) + k_t^s = \mathcal{H_s}(rK_t^v,t) + k_t^s \qquad &&\text{---> secret key} \\ &K_t^O = P = xG = k_t^O G = \mathcal{H_s}(rK_t^v,t)G + K_t^s \qquad &&\text{---> public key (outputs)} \\ &KI = I = x\mathcal{H_p}(P) \qquad &&\text{---> key image} \end{aligned} \end{equation}

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
Fig. 3 - Choosing ring members.

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:

Ring member: 

Ring member: 

Ring member: 

Ring member: 

Ring member: 

Ring member: 


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')

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

            # 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: ')
            Ri[ii] = qs * tmp1 
            print('Ri: ')


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

            # 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: ')

            tmp2 = hash_to_point(str(pubs[ii]))
            print('Result of hash_to_point: ')
            # 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: ')

            # 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: ')

    c = hash_to_scalar(buf.decode())
    print('The hash of the message is: ')
    # 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('The signature r: ')
    return image, sigc, sigr

If we take as input the following arguments:

        prefix = b"8ae47e12cca160c1a52e5517f6f1822d2bb6f1a24e8094b78891458f2b3e4d5d"
        image = "f1206393161213a5e4093f9c65e6ef92ca7f21b3513c90e50422e1280ca8165b" 
        pubs_array = [Point('649f27680aa9cbfb1166d5ad0dd80d20508646442e3e850c0a772a13a4c6b14a')]
        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
Result of hash_to_point: 
Random number qi generated for index 1
Random number qi generated for index 1
Result of hash_to_point: 
Random number qi generated for index 2
Random number qi generated for index 2
Result of hash_to_point: 
The message c is: 
The hash of the message is: 
The signature c: 
[ee85ba7ce135ad94ec874f1ceb73fddb980e8eaf9b41a02df8716197695c6c02, 26bfcd7c0111f0eff2747d04e2c0c7ae0d2378489e0b6f389c891a24bc63a60d, 7d83f8a40ff191ef168248efa77e6eb13448cda71447bf858667fc00674bff0c]
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\ \overset ? = \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))
        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))
        summ = sc_add(summ, sigc[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: ')

    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
Li calculated for index = 2
Ri calculated for index = 2
Li calculated for index = 3
Ri calculated for index = 3
Li calculated for index = 4
Ri calculated for index = 4
Li calculated for index = 5
Ri calculated for index = 5

Which proves that the signature is valid.

Why it works? (Generation)

For n = 3, consider the set of public keys in the blockchain $P_1,P_2,P_3$ where we control $P_3$ (we know its private key) and we can generate the corresponding key image.

  1. Consider W and Q the sets of random scalars: $Q = \{q_0,..,q_n\} $ and $W = \{ w_i \; | \; i = 0,..,n \; | \; i \neq s \}$.
  2. Calculate $R_i$ and $L_i$: \begin{equation} \begin{aligned} L_1 &= q_1G + w_1P_1 \quad &&L_2 = q_2G + w_2P_2 \quad &&L_3 = q_3G \\ R_1 &= q_1\mathcal{H_p}(P_1) + w_1I \qquad &&R_2 = q_2\mathcal{H_p}(P_2) + w_2I \quad &&R_3 = q_3\mathcal{H_p}(P_3) \\ \end{aligned} \end{equation}
  3. Calculate challenge: \[ c = \mathcal{H}(m+L_1+L_2+L_3+R_1+R_2+R_3) \] \begin{equation} \begin{aligned} c = \mathcal{H}(m+q_1G + w_1P_1+q_2G + w_2P_2 + q_3G + q_1\mathcal{H_p}(P_1) + w_1I + q_2\mathcal{H_p}(P_2) + w_2I + q_3\mathcal{H_p}(P_3)) \end{aligned} \end{equation}
  4. Define $c_i$ and $r_i$: \begin{equation} \begin{aligned} &c_1 = w_1 \quad &&c_2 = w_2 \quad &&c_3 = c - w_1 - w_2 \\ &r_1 = q_1 \quad &&r_2 = q_2 \quad &&r_3 = q_3 - c_3 x \\ \end{aligned} \end{equation}
  5. Publish signature: \[ \sigma = (c_1,c_2,c_3,r_1,r_2,r_3) \]

Why it works? (Verification)

  1. Consider signature $\sigma = (c_1,c_2,c_3,r_1,r_2,r_3)$ and key image $I$.
  2. Calculate $L_i`$ and $R_i`$. \begin{equation} \begin{aligned} L_1^` &= r_1G + c_1P_1 \quad &&L_2^` = r_2G + c_2P_2 \quad &&L_3^` = r_3G + c_3P_3 \\ R_1^` &= r_1\mathcal{H_p}(P_1) + c_1I \qquad &&R_2^` = r_2\mathcal{H_p}(P_2) + c_2I \quad &&R_3^` = r_3\mathcal{H_p}(P_3) + c_3I \\ \end{aligned} \end{equation}
  3. Check if signature is valid: \[ \displaystyle\sum_{i=0}^{n} c_i\ = c \overset ? = \mathcal{H}(m + L_1^`+L_2^`+L_3^` + R_1^`+R_2^`+R_3^`) \quad mod\ l\ \] \begin{equation} \begin{aligned} \mathcal{H}(m+&r_1G + c_1P_1+r_2G + c_2P_2+ \textcolor{red}{r_3G} + \textcolor{blue}{c_3P_3} + \\ &r_1\mathcal{H_p}(P_1) + c_1I + r_2\mathcal{H_p}(P_2) + c_2I + \textcolor{orange}{r_3\mathcal{H_p}(P_3)} + \textcolor{green}{c_3I}) = \\ \mathcal{H}(m+&q_1G + w_1P_1+q_2G + w_2P_2+ \textcolor{red}{(q_3-(c-w_1-w_2)x)G} + \textcolor{blue}{(c-w_1-w_2)P_3}+ \\ &q_1\mathcal{H_p}(P_1) + w_1I + q_2\mathcal{H_p}(P_2) + w_2I + \textcolor{orange}{(q_3-(c-w_1-w_2)x)\mathcal{H_p}(P_3)} + \textcolor{green}{(c-w_1-w_2)I}) = \\ \mathcal{H}(m+&q_1G + w_1P_1+q_2G + w_2P_2 + \textcolor{red}{q_3G - cxG + w_1xG + w_2xG} + \textcolor{blue}{cP_3 - w_1P_3 - w_2P_3} + \\ &q_1\mathcal{H_p}(P_1) + w_1I + q_2\mathcal{H_p}(P_2) + w_2I + \textcolor{orange}{q_3\mathcal{H_p}(P_3) - cx\mathcal{H_p}(P_3) + w_1x\mathcal{H_p}(P_3) + w_2x\mathcal{H_p}(P_3)} + \textcolor{green}{cI - w_1I - w_2I}) = \\ \mathcal{H}(m+&q_1G + w_1P_1+q_2G + w_2P_2 + \textcolor{red}{q_3G - \cancelto{cP_3}{cxG} + \cancelto{w_1P_3}{w_1xG} + \cancelto{w_2P_3}{w_2xG}} + \textcolor{blue}{\cancel{cP_3} - \cancel{w_1P_3} - \cancel{w_2P_3}} + \\ &q_1\mathcal{H_p}(P_1) + w_1I + q_2\mathcal{H_p}(P_2) + w_2I + \textcolor{orange}{q_3\mathcal{H_p}(P_3) - \cancelto{cI}{cx\mathcal{H_p}(P_3)} + \cancelto{w_1I}{w_1x\mathcal{H_p}(P_3)} + \cancelto{w_2I}{w_2x\mathcal{H_p}(P_3)}} + \textcolor{green}{\cancel{cI} - \cancel{w_1I} - \cancel{w_2I}}) = \\ \mathcal{H}(m+&q_1G + w_1P_1+q_2G + w_2P_2 + \textcolor{red}{q_3G} + \\ &q_1\mathcal{H_p}(P_1) + w_1I + q_2\mathcal{H_p}(P_2) + w_2I + \textcolor{orange}{q_3\mathcal{H_p}(P_3)}) \end{aligned} \end{equation}

The signature will only be valid if the terms cancel out as illustrated above and they will only cancel out if: