We continue our series about the Monero blockchain, and today's article will be devoted to the RingCT (Ring Confidential Transactions) protocol, which introduces 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.
We will talk about how the network hides the amount of transfers using this protocol, why they abandoned the classic ring signatures for cryptonote and how this technology will develop further.
Since this protocol is one of the most complex technologies in Monero, the reader will need a basic knowledge of the structure of this blockchain and a smattering of knowledge in elliptic curve cryptography (to refresh this knowledge, you can read the first chapters of our previous article on ).
RingCT Protocol
One of the possible attacks on cryptonote currencies is blockchain analysis based on knowing the amount and time of the sent transaction. This allows significantly narrow the scope of the search for exits of interest to the attacker. To protect against such analysis, Monero implemented an anonymous transaction protocol that completely hides the amount of transfers on the network.
It is worth noting that the idea of ββhiding amounts is not new. One of the first to describe it was Bitcoin Core developer Greg Maxwell in his . The current implementation of RingCT acts as its modification with the possibility of using ring signatures (where without them), and this is how it got its name - Ring Confidential Transactions.
Among other things, the protocol helps to get rid of problems with mixing dusty outputs - outputs for a small amount (usually obtained in the form of change from transactions) that created more problems than they were worth.
In January 2017, the Monero network was hard forked, allowing optional use of confidential transactions. And already in September of the same year, from the version 6 hard fork, such transactions became the only ones allowed on the network.
RingCT uses several mechanisms at once: multilayered linked spontaneous anonymous group signatures (Multilayered Linkable Spontaneous Anonymous Group Signature, hereinafter referred to as MLSAG), commitment scheme (Pedersen Commitments) and range proofs (this term does not have an established translation into Russian).
The RingCT protocol introduces two types of anonymous transactions: simple and full. The first wallet generates when a transaction uses more than one input, the second - in the opposite situation. They differ in the validation of transaction amounts and the data signed by the MLSAG signature (more on this below). Moreover, transactions of the full type can be generated with any number of inputs, there is no fundamental difference. In the book on this occasion, it is said that the decision to limit full transactions to one entry was made in haste and may change in the future.
MLSAG signature
Recall what the signed transaction inputs are. Each transaction spends some money and generates. Funds are generated by creating transaction outputs (a direct analogy is banknotes), and the output that the transaction spends (because in real life we ββspend exactly banknotes) becomes the input (carefully, it is very easy to get confused here).
An input refers to multiple outputs but spends only one, thus creating a "smoke screen" to make it difficult to analyze the history of transfers. If a transaction has more than one input, then such a structure can be represented as a matrix, where rows are inputs and columns are kneaded outputs. To prove to the network that the transaction spends exactly its outputs (knows their secret keys), the inputs are signed with a ring signature. Such a signature guarantees that the signer knew the secret keys for all elements of any of the columns.
Confidential transactions no longer use classic ring signatures, they were replaced by MLSAG - a version adapted for several inputs of similar single-layer ring signatures, .
They are called multilayer because they sign several inputs at once, each of which is mixed with several others, that is, a matrix is ββsigned, and not one row. As we will see later, this helps save on signature size.
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 ones from the blockchain to mix. Denote the public keys of the outputs that we spend as
, and key images for them, respectively: Thus, we get a matrix of size 2 x m. First we need to calculate the so-called challenges for each pair of outputs:
We start the calculations with the outputs that we spend using their public keys:and random numbersAs a result, we get the values:
, which we use to calculate challenge
the next pair of outputs (to make it easier to understand what we substitute where, we highlighted these values ββin different colors). All the following values ββare calculated in a circle according to the formulas shown in the first illustration. Challenge c is computed last for a pair of real outputs.
As we can see, in all columns, except for the one containing real outputs, randomly generated numbers are used.. For Οth column, we also need them. Let's transformin s:
The signature itself is a tuple of all these values:
Further, this data is written into the transaction.
As we can see, MLSAG contains only one challenge c0, which allows you to save on the size of the signature (which already require a lot of space). Further, any verifier, using the data, restores the values ββc1,β¦, cm and checks that. Thus, our ring is closed and the signature has been verified.
For RingCT transactions of the full type, one more row is added to the matrix with mixed outputs, but we will talk about this below.
Pedersen Commitments
(more often they use the English term - commitments) are used so that one side can prove that they know a certain secret (number), without actually revealing it. For example, you roll a certain number on the dice, count the commitment and pass it to the verifying party. Thus, at the moment of revealing the secret number, the verifier independently calculates the commitment, thereby making sure that you did not deceive him.
Monero commitments are used to hide the amount of transfers and use the most common option - Pedersen commitments. By the way, an interesting fact - at first, the developers suggested hiding the amounts with the usual mixing, that is, adding outputs for arbitrary amounts in order to introduce uncertainty, but then they switched to commitments (it is not a fact that they saved on the size of the transaction, as we will see below).
In general, a commitment looks like this:
Where C - the meaning of the commitment itself, a - hidden amount H is a fixed point on an elliptic curve (additional generator), and x - some arbitrary mask that hides a randomly generated factor. The mask is needed here so that the third party cannot pick up the commitment value by simple enumeration.
When generating a new output, the wallet calculates a commitment for it, and when spending it, it takes either the value calculated during generation or recalculates 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 inputs (not made money out of thin air), it is necessary that the sum of commitments of the first and second be the same, that is:
Commitment commissions consider a little differently - without a mask:
Where a - the amount of the commission, it is publicly available.
This approach allows us to prove to the relying party that we use the same amounts without disclosing them.
To make things clearer, let's look at an example. Let's say a transaction spends two outputs (that is, they become inputs) for 10 and 5 XMR and generates three outputs worth 12 XMR: 3, 4, and 5 XMR. At the same time, it pays a commission of 3 XMR. Thus, the amount of money spent plus the amount generated and the commission is equal to 15 XMR. Let's try to calculate the commitments and look at the difference between their sums (remember the math):
Here we see that the equation converges - we need the sums of the masks of inputs and outputs to be the same. To do this, the wallet generates randomly x1, y1, y2 and y3, and the remaining x2 calculates like this:
Using these masks, we can prove to any reviewer that we are not generating more funds than we spend without disclosing the amount. Original, right?
RingCT full
In full RingCT transactions, the verification of transfer amounts is somewhat more intricate. In these transactions, the wallet does not recalculate commitments for inputs, but uses those calculated when generating them. In this case, we must assume that we will no longer get the difference of the sums equal to zero, but instead:
Here z is the difference between input and output masks. If we consider zG as a public key (which it de facto is), then z is the private key. Thus, we know the public and the corresponding private keys. With this data, we can use it in the MLSAG ring signature along with the public keys of the kneaded outputs:
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 row 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 in the amounts of commitments does not lead to zeroβ - if zG = 0, then we expand the column with real outputs.
But how does the recipient of the funds find out how much money was sent to him? Everything is simple here - the sender of the transaction and the recipient exchange keys using the Diffie-Hellman protocol, using the transaction key and the recipient's view-key and calculate the shared secret. The sender writes in the special fields of the transaction data on the amounts of outputs encrypted with this shared key.
Range proofs
But what happens if you use a negative number as the amount in commitments? This may lead to the generation of additional coins! Such an outcome is unacceptable, so we need a guarantee that the amounts we use are not negative (without disclosing these amounts, of course, otherwise so much work and all in vain). In other words, we must prove that the sum is in the interval [0, 2n - 1].
To do this, the sum of each output is divided into binary digits and the commitment for each digit is considered separately. How this happens is best seen with an example.
Let's assume that our sums are small and fit in 4 bits (in practice it is 64 bits), and we create an output in the amount of 5 XMR. We consider commitments for each category and the total commitment for the entire amount:
Further, each commitment is mixed with a surrogate (Ci-2iH) and signed in pairs with the Borromean ring signature (another ring signature) proposed by Greg Maxwell in 2015 (you can read more about it ):
Collectively, this is called range proof and ensures that commitments use amounts in the range [0, 2n - 1].
What's next?
In the current implementation, range proofs take up a lot of space - 6176 bytes per output. This leads to large transactions and, accordingly, higher commissions. To reduce the size of a Monero transaction, developers introduce bulletproofs instead of Borromeo signatures - a range proof mechanism without bitwise commitments. , they are able to reduce range proof by up to 94%. By the way, in mid-July, the technology passed from Kudelski Security, which did not reveal significant shortcomings both in the technology itself and in its implementation. The technology is already being deployed on the testnet, and with the new hard fork, it is likely to move to the mainnet as well.
Ask your questions, suggest topics for new articles about technologies in the field of cryptocurrencies, and also subscribe to our group in to keep up to date with our events and publications.
Source: habr.com