Confidential transactions in Monero, or how to translate it is unknown what is unknown where

We continue our cycle on the Monero blockbuster, and today's article will be devoted to the RingCT (Ring Confidential Transactions) protocol, which presents confidential transactions and new ring signatures. Unfortunately, there is little information on the Internet about how it works, and we tried to fill this gap.
 
 
Confidential transactions in Monero, or how to translate it is unknown what is unknown where
 
 
We'll talk about how the network hides the transfer amounts using this protocol, why they abandoned the classic ringtones for cryptonote and how this technology will evolve further.
 
 
Since this protocol is one of the most complex technologies in Monero, the reader will need basic knowledge about the device of this block and surface knowledge in cryptography on elliptical curves (in order to refresh this knowledge, you can read the first chapters of our previous article about .multipods ).
 
 

Protocol RingCT


 
One of the possible attacks on cryptonote-currencies is blocking analysis, based on knowing the amount and time of the transaction sent. This allows article Confidential Transactions . The current implementation of RingCT is its modification with the possibility of using ring signatures (much without them), and it got its name - Ring Confidential Transactions.
 
 
Among other things, the protocol helps to get rid of problems with mixing of dust exits - outputs for a small amount (usually obtained as a change from transactions), which created problems more than they themselves cost.
 
 
In January 2017 the Monero network was hosted, which allows the optional use of confidential transactions. And already in September of the same year with the version 6 hardfork, such transactions became the only ones allowed on the network.
 
 
RingCT uses several mechanisms at once: multilayered spontaneous anonymous group signatures (Multilayered Linkable Spontaneous Anonymous Group Signature, hereinafter referred to as MLSAG), a scheme of obligations (Pedersen Commitments) and range proofs (there is no established translation into Russian).
 
 
The RingCT protocol introduces two types of anonymous transactions: simple and full. The first purse generates when the transaction uses more than one input, the second - in the reverse situation. They differ in the validation of transaction amounts and MLSAG-signed data (more on this later). Moreover, transactions of type full can be generated with any number of inputs, there is no fundamental difference. In the book «Zero to Monero» on this occasion it is said that the decision to limit the full transaction to one entrance was taken in a hurry and in the future may change.
 
 

MLSAG signature


 
Let's remember what the signed transaction inputs are. Each transaction spends some money and generates. Generation of funds occurs by creating transaction outputs (direct analogy - bills), and the output that the transaction spends (because in real life we ​​spend money bills), it becomes the entrance (carefully, it's very easy to get confused here).
 
 
The input refers to several outputs, but spends only one, thus creating a "smokescreen" to make it difficult to analyze the history of translations. If a transaction has more than one input, then such a structure can be represented as a matrix, where the rows are inputs, and the columns are the outputs to be mixed. To prove the network that the transaction spends its outputs (knows their secret keys), the inputs are signed with a ring signature. Such a signature gives a guarantee that the signer knew the secret keys from all the elements of any of the columns.
 
 
Confidential transactions no longer use the classic for cryptonote ring signatures, they were replaced by MLSAG - a version of similar single-layered ring signatures adapted for several inputs, LSAG .
 
 
They are called multi-layered because they sign several inputs at once, each of which is involved with several others, that is, a matrix is ​​subscribed, and not one row. As we shall see later, this helps to save on the size of the signature.
 
 
Let's look at how a ring signature is formed, using the example of a transaction that spends 2 real outputs and uses m-1 random from blocking to mix. Denote the public keys of the outputs, which we spend as
 
, and key images for them, respectively:
Thus, we obtain a matrix of size 2 x m . First, we need to calculate the so-called challenges for each pair of outputs:
 

 
Calculations begin with the outputs that we spend using their public keys:
and the random numbers
As a result, we get the values:
 
, which we use to calculate challenge
 
the next pair of outputs (to make it easier to understand what to substitute, we have selected these values ​​in different colors). All the following values ​​are computed in a circle according to the formulas given in the first illustration. The last calculates the challenge with a pair of real outputs.
 
 
As you can see, in all columns, except for containing real outputs, randomly generated numbers are used. . For π th column, they are also required. We transform in s:

 
The signature itself is a tuple of all these values:
 
 

 
 
These data are then written to the transaction.
 
 
As we can see, MLSAG contains only one challenge c 0 , which saves on the size of the signature (which already requires a lot of space). Next, any verifier using the data. , restores the values ​​c 1 , , c m and verifies that . Thus, our ring was closed and the signature was tested.
 
 
For RingCT transactions of type full, one more line to the matrix with the associated outputs is added, but we will discuss this later.
 
 

Pedersen Commitments


 
Schemes of obligations (more often use the English term obligations) are used so that one side can prove that it knows a certain secret (number) without actually revealing it. For example, you throw a number on the bones, consider commitment and pass it to the checking party. Thus, at the time of disclosing a secret number, the examiner independently considers the commitment, thereby making sure that you have not deceived him.
 
 
In the Monero commitments are used to conceal the amounts of transfers and apply the most common option - the Pedersen commitments. By the way, a curious fact is that first the developers suggested to hide the amounts by usual mixing, that is, to add exits to arbitrary amounts to introduce uncertainty, but then switched to commitments (not the fact that they saved on the transaction size, as we will see below).
 
In general, the commitment is as follows:
 
Where C - the meaning of the commitment itself, a - The amount to be hidden, H - fixed point on the elliptic curve (additional generator), and x - some kind of arbitrary mask, hiding factor, generated randomly. A mask is needed here so that a third party can not simply pick out the meaning of commitment.
 
 
When generating a new output, the wallet calculates commitment for it, and, when used, takes either the value calculated at the generation or recounts it again - depending on the type of transaction.
 
 

RingCT simple


 
In the case of simple RingCT transactions, in order to ensure that the transaction created outputs equal to the sum of the inputs (did not generate money from the air), the sum of obligations of the first and second ones must be the same, that is:
 

 
Commitment of the commission is considered a little different - without a mask:
 
, where a - The amount of the commission, it is publicly available.
 
 
This approach allows us to prove to the auditor that we use the same amount without disclosing them.
 
 
To make things clear, let's look at an example. Suppose a transaction spends two outputs (that is, they become inputs) on 10 and 5 XMR and generates three outputs for the sum of 12 XMR: ? 4 and 5 XMR. At the same time, he pays a commission of 3 XMR. Thus, the amount of money spent plus the amount of generated and commission is 15 XMR. Let's try to calculate obligations and look at the difference of their sums (we'll recall the mathematics):
 
 

 
Here we see that the equation converges - we need the sums of the masks of the inputs and outputs to be the same. To do this, the wallet generates randomly x 1 , y 1 , y 2 and y 3 , and the remaining x 2 counts like this:
 

 
Using these masks, we can prove to any inspector that we do not generate funds more than we spend without revealing the amount. It's original, is not it?
 
 

RingCT full


 
In full RingCT transactions, checking the amounts of transfers is somewhat more intricate. In these transactions, the wallet does not recalculate commitments for inputs, but uses the ones calculated when generating them. In this case, we must assume that we do not get the difference of sums equal to zero, but instead:
 

 
Here z - difference of masks of inputs and outputs. If we consider zG as a public key (the de facto it is), then z Is a private key. Thus, we know the public and relevant private keys. With this data, we can use them in the MLSAG ring sign along with the public keys of the outputs to be mixed:
 

 
Thus, a valid ring signature will ensure that we know all the private keys of one of the columns, and we can only know the private key in the last line if the transaction does not generate more funds than it spends. By the way, here is the answer to the question "why here the difference of the amounts of commitments does not lead to zero" - if zG = 0 , then we will open a column with real outputs.
 
 
And how does the recipient of the funds find out how much money was sent to him? Here everything is simple - the sender of the transaction and the recipient exchange the keys using the Diffie-Hellman protocol, using the transaction key and the view-key of the recipient and compute the shared secret. The sender writes data into the special transaction fields about the sum of the outputs encrypted with this shared key.
 
 

Range proofs


 
And what will happen if, as a sum in commitments, use a negative number? This can lead to the generation of additional coins! Such an outcome is unacceptable, therefore, a guarantee is needed that the amounts we use are not negative (without disclosing these amounts, of course, otherwise so much labor and all in vain). In other words, we must prove that the sum is in the interval [0, 2n — 1] .
 
 
For this, the sum of each output is divided into binary digits and the commitment for each discharge is considered separately. How this happens, it is better to consider the example.
 
 
Suppose that the sums are small and placed in 4 bits (in practice this is 64 bits), and we create an output of 5 XMR. We consider obligations for each category and a total commitment for the whole amount:

 
Further, each commitment is mixed with the surrogate (C
? i
? -2
? i
? H)
and is signed in pairs by the Borromeo ring sign (another ring signature), proposed by Greg Maxwell in 2015 (more details about it can be read here ):
 
Collectively, this is called a range proof and allows you to ensure that commitments use sums in the range [0, 2n — 1] .
 
 

What's next?


 
In the current implementation, range proofs take up a lot of space - ?176 bytes per output. This leads to large transactions and, accordingly, higher commissions. To reduce the size of the Monero transaction, developers introduce instead of Borromeo signatures bulletproofs - a mechanism of range proof without bit commitments. According to some estimates , they are able to reduce the size of the range proof up to 94%. By the way, in the middle of July the technology passed audit from the company Kudelski Security, which did not reveal significant shortcomings in the technology itself, and in its implementation. The technology is already used in the test network, and with the new hardware, it can probably move to the main network.
 
 
Ask your questions, suggest topics for new articles about technologies in the field of crypto-currency, and also subscribe to our group in Facebook to keep abreast of our events and publications.
+ 0 -

Add comment