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 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.
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
0100010280e08d84ddcb0106010401110701f254220bb50d901a5523eaed438af5d43f8c6d0e54ba0632eb539884f6b7c02008c0a8a50402f9c7cf807ae74e56f4ec84db2bd93cfb02c2249b38e306f5b54b6e05d00d543b8095f52a02b6abb84e00f47f0a72e37b6b29392d906a38468404c57db3dbc5e8dd306a27a880d293ad0302cfc40a86723e7d459e90e45d47818dc0e81a1f451ace5137a4af8110a89a35ea80b4c4c321026b19c796338607d5a2c1ba240a167134142d72d1640ef07902da64fed0b10cfc8088aca3cf02021f6f655254fee84161118b32e7b6f8c31de5eb88aa00c29a8f57c0d1f95a24dd80d0b8e1981a023321af593163cea2ae37168ab926efd87f195756e3b723e886bdb7e618f751c480a094a58d1d0295ed2b08d1cf44482ae0060a5dcc4b7d810a85dea8c62e274f73862f3d59f8ed80a0e5b9c2910102dc50f2f28d7ceecd9a1147f7106c8d5b4e08b2ec77150f52dd7130ee4f5f50d42101d34f90ac861d0ee9fe3891656a234ea86a8a93bf51a237db65baa00d3f4aa196a9e1d89bc06b40e94ea9a26059efc7ba5b2de7ef7c139831ca62f3fe0bb252008f8c7ee810d3e1e06313edf2db362fc39431755779466b635f12f9f32e44470a3e85e08a28fcd90633efc94aa4ae39153dfaf661089d045521343a3d63e8da08d7916753c66aaebd4eefcfe8e58e5b3d266b752c9ca110749fa33fce7c44270386fcf2bed4f03dd5dadb2dc1fd4c505419f8217b9eaec07521f0d8963e104603c926745039cf38d31de6ed95ace8e8a451f5a36f818c151f517546d55ac0f500e54d07b30ea7452f2e93fa4f60bdb30d71a0a97f97eb121e662006780fbf69002228224a96bff37893d47ec3707b17383906c0cd7d9e7412b3e6c8ccf1419b093c06c26f96e3453b424713cdc5c9575f81cda4e157052df11f4c40809edf420f88a3dd1f7909bbf77c8b184a933389094a88e480e900bcdbf6d1824742ee520fc0032e7d892a2b099b8c6edfd1123ce58a34458ee20cad676a7f7cfd80a28f0cb0888af88838310db372986bdcf9bfcae2324480ca7360d22bff21fb569a530e
{ "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:
0100010280e08d84ddcb0106010401110701f254220bb50d901a5523eaed438af5d43f8c6d0e54ba0632eb539884f6b7c02008c0a8a50402f9c7cf807ae74e56f4ec84db2bd93cfb02c2249b38e306f5b54b6e05d00d543b8095f52a02b6abb84e00f47f0a72e37b6b29392d906a38468404c57db3dbc5e8dd306a27a880d293ad0302cfc40a86723e7d459e90e45d47818dc0e81a1f451ace5137a4af8110a89a35ea80b4c4c321026b19c796338607d5a2c1ba240a167134142d72d1640ef07902da64fed0b10cfc8088aca3cf02021f6f655254fee84161118b32e7b6f8c31de5eb88aa00c29a8f57c0d1f95a24dd80d0b8e1981a023321af593163cea2ae37168ab926efd87f195756e3b723e886bdb7e618f751c480a094a58d1d0295ed2b08d1cf44482ae0060a5dcc4b7d810a85dea8c62e274f73862f3d59f8ed80a0e5b9c2910102dc50f2f28d7ceecd9a1147f7106c8d5b4e08b2ec77150f52dd7130ee4f5f50d42101d34f90ac861d0ee9fe3891656a234ea86a8a93bf51a237db65baa00d3f4aa196
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
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:
de00acad5a0df1c52ef51637cb89ae1c991c877acf6152252529009d6e51adbc
Offset:
5
Ring member:
1b6367f72a1cdbc7a21aa37e0ab2155529e404c2efaadd72ca7702e42bc96640
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_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 eab873e2d6a1f8fe1fa0f11deb7fee6e9129e16d887fa9adbc9717738a3a4700 Li: 21c7f1d9d02bae22eead5204c90483496fa4106d7e33455b61a5f10d1d5aab8d Result of hash_to_point: 2b444877eac6f5e10376e338107ce5a8d07ddb35272cb78f1db4436ff6db355b Ri: c4bba60e6989bfd03b088ea95f58e4203986e0b70a0e8ad639df67e3e7773dd2 Random number qi generated for index 1 26bfcd7c0111f0eff2747d04e2c0c7ae0d2378489e0b6f389c891a24bc63a60d Random number qi generated for index 1 26bfcd7c0111f0eff2747d04e2c0c7ae0d2378489e0b6f389c891a24bc63a60d Li: 66bbdb9067a7c2293dafba516651819dc8e35127f0f9a066e06f556b932cd4a9 Result of hash_to_point: a8bed181ff67f32a81e06043fa2efb782c93936d93716ad0914f2f3c82266ee4 Ri: 21a24451723c80e9f15e27f1ea86c2ec3f432cdc380cad260998bd37e74861fb 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: b'7f658119722803b0fdab41843d4c3c2510e1cbbe64746255dfbd93b48a38085621c7f1d9d02bae22eead5204c90483496fa4106d7e33455b61a5f10d1d5aab8dc4bba60e6989bfd03b088ea95f58e4203986e0b70a0e8ad639df67e3e7773dd266bbdb9067a7c2293dafba516651819dc8e35127f0f9a066e06f556b932cd4a921a24451723c80e9f15e27f1ea86c2ec3f432cdc380cad260998bd37e74861fbc541b04e3e8f4fbe04590959f1014f245a0de3cfc82db4b23426df0d384da2c64ab91b7593f9a72a7633f9a5d1d3c06be815532e00b2a5653364c2d93943391b' The hash of the message is: a4f48a41d8d41c1c20e21d6d96b95427db79d39f4e94ceeb1a6378bc8c0b120d 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))
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])
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: ')
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 afe1c73a9462c5d0262ab4a93753626faa8d0887dd22b5f14ac19a3e6dbad45a Ri calculated for index = 0 f492d6b5822fb20a507f64ea536ddadf70b39ea4d38a502cb728a6c5fc2833b9 Li calculated for index = 1 210bada8afd13055efa2f0bcc2f3e37945a121b27a2e787c85b2ed5b9287bfeb Ri calculated for index = 1 a0f52f4204c69946160047a10da9ab6482f2c26e991546cf2fb77f5b233faf36 Li calculated for index = 2 ca0e182dbe2996c96e2c6d7454af149f71021a474537b46bf9aa7fe6fb564c38 Ri calculated for index = 2 b16f4fa53891774bd9c1eb4420bdea8f81cef07520c1c9fa2fc7ade428d53b7c 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 750400c6ce7096e001adac2f8007666ea76489c5e2f588fa7939d34749edc3c0 Ri calculated for index = 5 1141a762e14c80c9c40583f42100653cd8180440b6a894931857a8f3904ac365 Result: 0000000000000000000000000000000000000000000000000000000000000000
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.
- Consider W and Q the sets of random scalars: $Q = \{q_0,..,q_n\} $ and $W = \{ w_i \; | \; i = 0,..,n \; | \; i \neq s \}$.
- 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}
- 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}
- 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}
- Publish signature: \[ \sigma = (c_1,c_2,c_3,r_1,r_2,r_3) \]
Why it works? (Verification)
- Consider signature $\sigma = (c_1,c_2,c_3,r_1,r_2,r_3)$ and key image $I$.
- 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}
- 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:
- $xG = P_3$
- $x\mathcal{H_p}(P_3) = I$
