An audit of a cryptocurrency wallet is an opportunity for a third party (the “auditor”) to see the transactions of this wallet and calculate its correct current balance without the right to spend money.

The article discusses various ways of providing such an opportunity in the cryptocurrency protocol CryptoNote 2.0 [ 1 ], where the audit is only partially implemented: using a tracking key, you can recognize incoming transactions, but to recognize outgoing transactions you need a full set of keys.

The material is intended for readers who are familiar with the topic of blockchain and “classic” cryptocurrencies, as well as with the basics of cryptography on elliptic curves.

Content

1.
2.
3. CryptoNote
4. 1/3. Bytecoin Auditable Coins
4.1. tx.version < amethyst, legacy address
4.2. tx.version ≥ amethyst
4.3. tx.version ≥ amethyst, legacy address
4.4. tx.version ≥ amethyst, amethyst address
4.5. CryptoNote Bytecoin Amethyst
5. 2/3. CryptoNote Anton Sokolov
6. 3/3.
7.

1.

CryptoNote?

Oddly enough, most of those interested in blockchain technology have not heard anything about CryptoNote, and this despite the fact that this technology has become the basis for more than 300 forks, the most famous of which is Monero.

In 2014, mentions appeared in the cryptocurrency environment [ 2] about a project called Bytecoin. The project was not a fork of Bitcoin or another open source project and had a completely new code base, which was extremely unusual for that time. Its main concept was to implement a privacy technology called CryptoNote. Privacy was provided by two mechanisms: stealth addresses and mixing of inputs using a ring signature (it was also called at that time “mixer on the blockchain”). Since at that time Zcash existed only in theory, the technology turned out to be very competitive and caused a great resonance in the cryptocurrency community.

Soon, a group of enthusiasts who showed interest in one of the first forks of this technology, and then seized the initiative in this fork, with their energetic actions managed to attract the greatest attention to technology both among the community and among investors. This fork was called BitMonero [ 3 , 4 ], but pretty soon it was renamed Monero.

In the future, both projects - Bytecoin and Monero - developed in technologically different ways: if Bytecoin remained a closed anonymous project, then Monero turned into a large community-driven project with a very large number of participants and developers. However, they are both a development of CryptoNote technology.

The concept of audit and its application

Unlike the classic “pseudonymous” blockchain such as Bitcoin, in which anyone, by scanning the blockchain, can trivially calculate the balances of any address, in a private blockchain, in particular in CryptoNote, this task is hardly feasible without additional knowledge. Firstly, thanks to the technology of stealth addresses, there are no references to any addresses in the blockchain (this property is usually referred to as anonymity ). Secondly, due to the fact that due to the ring signature, the transaction input does not indicate one specific output of the parent transaction, but rather, in general, indicates many possible outputs, it is also not possible to track the movement of funds (this property is called untraceability ).

In the traditional understanding of private cryptocurrency, these properties are necessary, but there are special cases where the wallet owner may want to disclose the history of his transactions and the current wallet balance to a third party, while guaranteeing that it is impossible for a third party to spend money. This may be necessary, for example, to exchanges, for interaction with regulators or checking authorities. In addition, this may be important for various funds that would like to be able to be transparent to a specific group of individuals or to be fully public.

Speaking formally, an audit of wallets means an opportunity for a third party (“auditor”) to see the transactions of this wallet and calculate its correct current balance without transferring the right to spend funds. In the original version of CryptoNote, audit was only partially implemented: using a tracking key, you can recognize incoming transactions, but to recognize outgoing transactions, you need a full set of keys.

About the author and purpose of publication

The author of this material is one of the main developers of the Zano project - a project based on CryptoNote, which has been developing for several years with the same hands that wrote the original technology code.

Our team is now considering adding a wallet audit to the project and conducting research on this topic in order to choose the best option. The author wants to introduce the results of some of these studies to readers in this article.

2. Basic information about cryptography on elliptic curves

The CryptoNote protocol uses an elliptic curve from the ed25519 public key digital signature scheme [ 5 ].

Recall the main parameters of this curve and give additional definitions.

Fixed a large prime $q = 2^{255}-19$ .
$F_q$ $q$ .
$F_q$ , $E/F_q$ :
$−x^2+y^2= 1 +dx^2y^2$
$d = −121665/121666$ ( $F_q$ ).
$x$ $y$ .
, : $F(A, B) = C$ , «», , , ( [6]). , , , , $E(F_q)$ .
( ): $\# E(F_q)=2^cl$ , $= 3$ () $l=2^{252}+27742317777372353535851937790883648493$ .
$(x, y)$ . , , $y$ , 256- .
$x$ -, (. ), , , $y$ -.
$G = (x, −4/5)$ . $y$ -, x .
(. . 3) $G$ $n$ ( $*$ , ) , $\mathbf{G}$ , , $E(F_q)$ :
$\#\mathbf{G} < \#E(F_q)$ ,

$\#\mathbf{G}=l=2^{252}+27742317777372353535851937790883648493$ .
$X$ — , $\mathbf{G}$ :
$X \in \mathbf{G}$
$x$ , , $X$ — , :
$X = x*G, x \in [1; l-1]$
, (. ), 256- .
- $H$ ( cn_fast_hash). 32- : $H:\{0, 1\}^* \to [0,2^{256}-1]$
- $H_s$ ( $s$ scalar) , , .. :
$H_s:\{0,1\}^* \to [1; l-1]$
$H_s$ $H$ :
$H_s(x)= H(x) \mod (l-1) + 1$
- $H_p$ ( $p$ point — ) $\mathbf{G}$ , , :
$H_p:\{0,1\}^* \to \mathbf{G}$
- , -, 256 (. . 4), -, $\mathbf{G}$ (. . 6).
$H_p$ $H(H(...H(x)...))$ , $X \in \mathbf{G}$ .
CryptoNote , ge_fromfe_frombytes_vartime, [7].
, 256 $\mathbf{G}$ :
$to\_point : [0,2^{256}-1] \to \mathbf{G}$
CryptoNote - $H_p$ implemented like this:
$H_p(x) = to\_point( H(x) )$

3. Accounting and balance calculation in CryptoNote

Recall how the funds are sent and the balance is calculated in the original version of the protocol.

Alice, sending money to Bob, forms the outputs of her transaction as follows (Fig. 3.1).

_{Fig. 3.1. Alice generates transaction exits by sending money to Bob}

Bob has a pair of private keys $(v, s)$ . It calculates its address as a pair of matching public keys $(V, S)$ and publishes it or sends it to Alice.
Alice picks a random secret transaction key $r$ and calculates the public key $R = r G$ which writes to the special field extra transactions.
For each output, Alice calculates the stealth address (one-time destination key):
$P_i = H_s(rV, i)G + S$ where $i$ - serial number of the output.
Alice signs and sends the transaction.

Third-party observer analyzing stealth addresses

$P_i$ , cannot say whether a particular output is intended for Bob, and cannot even determine whether different outputs with keys are intended

$P_i$ and

$P_j$ to one recipient.

To accept the money, Bob analyzes all transactions on the blockchain as follows (Fig. 3.2).

_{Fig. 3.2. Bob checks transaction outputs to determine incoming transfers}

5. Using your private key

$v$ Bob computes for each output

$P’_i = H_s(vR, i)G + S$ (Where

$i$ - serial number of the output,

$S$ - Bob's public spend-key).
If

$P’_i = P_i$ , then this means that he is the recipient of this output and can spend it by calculating the corresponding secret key. Therefore, Bob increases the balance of his wallet by the value of this output.

To spend the output Bob is the recipient of and send Carol coins, he acts as follows.

_{Fig. 3.3. Bob forms an entry for a new transaction using his own exit}

6. Bob using his secret keys

$(v, s)$ calculates the private key

$x_i = H_s(vR, i) + s$ to stealth address

$P_i$ , i.e., such that

$P_i = x_i G$ .

7. Bob calculates the key image:

$I = x_i H_p(P_i)$ and writes it, the face value and a link to the corresponding output in the input of his transaction for Carol.
It should be noted that, firstly, only the owner of the secret spend-key can calculate key image

$s$ (the correctness of this will be certified by a ring signature), and secondly, a third party will not be able to bind key image

$I$ and corresponding stealth address

$P_i$ .

8. Bob reduces the balance of his wallet by the nominal value of the output used in paragraph 6.

9. Bob forms the outputs in the transaction for Carol in accordance with paragraphs. 2-3. Then signs the transaction and sends.

Assuming Bob has lost the entire history of his operations, but still owns his secret keys

$(v, s)$ , then he will be able to restore the transaction history and calculate his current balance as follows (Fig. 3.4).

_{Fig. 3.4. Bob determines his incoming and outgoing payments and calculates the balance}

10. Bob scans the entire blockchain and analyzes all transactions for the presence of outputs addressed to him (see paragraph 5).

11. When finding such an exit

$P_i$ , Bob increases the balance of his wallet by the value of the face value.
Then using your secret spend key

$s$ computes the corresponding secret exit key

$x_i$ (p. 6) and key image

$I$ (paragraph 7). Then writes key image,

$P_i$ and other payment data in a table.

12. If during further scanning of the blockchain, Bob finds in the input of some transaction the key image in the table, this will mean that this transaction was once formed by Bob. Therefore, he will reduce the balance of his wallet by the value of the entry value.

By doing so, Bob will restore the current balance of his wallet.

Please note that if third-party auditor Dan receives a secret key from Bob

$v$ , then he will be able to recognize Bob's incoming transactions on the blockchain, however, without a secret key

$s$ , he will not be able to recognize Bob's outgoing transactions, which means that he will also calculate the correct balance. As will be shown later, in the case of direct spending of the exit by Bob without mixing, Den will be able to identify such a transaction as Bob's outgoing transfer, but in the general case this cannot be done.

Thus, to calculate the balance of Bob’s wallet, you need to know both secret keys $(v, s)$ .

If Bob gives both of his private keys to auditor Dan

$(v, s)$ , this will be tantamount to transferring the funds themselves, since Den, possessing

$s$ will be able to spend them. Therefore, a full audit of wallets under the original CryptoNote protocol is not possible.

In the following sections, we will consider options for modifying the protocol that have this capability.

Note that the secret key of the transaction

$r$ It makes sense to save Alice (which is what happens in some implementations of the protocol). Anyone who knows

$r$ for some transaction, can check if the output is relevant

$i$ this transaction to the given address

$(V, S)$ simply repeating the calculations from clause 3:

$P’_i = H_s(rV, i)G + S$

and comparing the result with

$P_i$ .

Alice can, for example, use this fact to prove that she transferred the money to Bob.

Calculate Destination Address

$(V, S)$ on exit, even knowing

$r$ , you can’t.

4. Option 1/3. Bytecoin auditable coins

At the time of its appearance, Bytecoin was the first and only implementation of the CryptoNote protocol, so it was characterized by all the features and limitations discussed in the previous section.

On February 7, 2019, developers released ([ 20 ]) version 3.4.0 of Amethyst, which contains a number of improvements and changes to CryptoNote, which we will now consider. Most of the information in this section was obtained by analyzing the source code of Bytecoin, since no official documentation was provided.

Within the scope of this article, the most interesting change was the ability for ordinary wallets to create special copies - auditable wallet (AW), with two properties:

AW cannot spend funds from the main wallet;
AW balance always coincides with the balance of the main wallet. It is not possible to change the balance of the main wallet so that it does not affect the balance of AW.

However, only the wallet addresses of new versions, the so-called amethyst addresses, have such functionality. Backward compatibility is provided with existing addresses and accounts; they are now called legacy addresses. The implementation of the new functionality became possible only in transactions of the new version, since the developers changed the format of the outputs, therefore, bytecoin networks currently circulate both old-format transactions and new ones. Transactions of the new format also support two types of addresses: amethyst and legacy, so in the end we have three options for cryptographic schemes:

tx.version <amethyst, legacy address;
tx.version ≥ amethyst, legacy address;
tx.version ≥ amethyst, amethyst address.

Let's consider them in more detail.

4.1. tx.version <amethyst, legacy address

This is the original CryptoNote scheme, but with deterministic generation.

$r$ .

Wallet account represented by secret key.

$s$ and hash

$v_s$ . Secret view key

$v$ deterministically generated as a function of

$v_s$ .

The secret key

$r$ transactions are now selected not by chance, but calculated using

$v_s$ :

$r = H_s(h_t, v_s)$ where

$h_t = H(tx.inputs, tx.version)$

This eliminates the need for private keys.

$r$ in local storage for future needs, since for any transaction ever sent to the blockchain, such a key can be calculated using

$v_s$ .

The wallet balance is calculated similarly to the original CryptoNote (see section 3), that is, a secret spend-key is required to account for outgoing payments

$s$ .

If all addresses that have ever been transferred to the wallet are stored in the local wallet , then it is possible to calculate the correct balance without involving a secret spend-key

$s$ in the following way:

Alice scans transactions on the blockchain and keeps track of incoming payments using a secret view key $v$ , as described in section 3, and increases balance.
Also, for each output of each transaction, Alice goes through all the addresses $(V, S)$ to which transfers have ever been made and calculates:
$P’_i = H_s(rV, i)G + S$
If $P’_i = P_i$ , then this output is Alice's outgoing payment to the address $(V, S)$ and it reduces balance.

So Alice will calculate the balance using only

$v_s$ and

$v$ .

Obviously, this method is unreliable and impractical, since the absence in the indicated local storage of the address to which the transfer was actually carried out will lead to an overestimation of the balance. Therefore, it is, rather, of theoretical interest.

4.2. tx.version ≥ amethyst

As noted above, since version 3.4.0 of Amethyst, Bytecoin has changed the format of transactions. If tx.version ≥ amethyst, then the transaction outputs have a different format.

Now, each output, in addition to the amount and the public key P _i , also contains an additional public key Q _i (indicated in the code as encrypted_secret) and an additional byte containing the encrypted address type, amethyst or legacy (referred to in the code encrypted_address_type). These structures are shown schematically in Fig. 4.2.

_{Fig. 4.2. Comparing the data structure for CryptoNote and Bytecoin Amethyst transaction exits}

Thus, the size of each output increased by 33 bytes.

For each output i, the address type is encoded and decoded as follows: where:

encrypted_address_type(i) = (H(o_i) & 255) xor address_tag

$o_i = H(h_t, v_s, i)$ (indicated in the code as output_seed),

address_tag is 0 for legacy addresses and 1 for ametyst addresses.

4.3. tx.version ≥ amethyst, legacy address

The wallet account is also represented by a secret key.

$s$ and hash

$v_s$ on the basis of which a secret view key is generated deterministically

$v$ .

Alice sending money to Bob at his address

$(V, S)$ forms the outputs of its transaction as follows:

1. Calculates

$h_t = H(tx.inputs, tx.version)$ , then for each exit

$i$ :
2.

$D_i = H_s(h_t, v_s, i)G$ (indicated in the code as output_shared_secret)
3.

$P_i = S + H_s(D_i, h_t, i)G$
4.

$Q_i = H_s(h_t, v_s, i)V$ (wherein

$Q_i = v D_i$ however view key

$v$ recipient unknown)
5. Pair

$(P_i, Q_i)$ - public exit keys

$i$ .

To accept the money, Bob analyzes all transactions as follows.

6. For each transaction, calculates

$h_t = H(tx.inputs, tx.version)$ , then for each exit

$i$ :
7.

$D_i = v^{-1} Q_i$
8.

$S’ = P_i — H_s(D_i, h_t, i) G$
9. If

$S’$ matches the public key

$S$ Bob, then this exit is intended for him and he increases the balance of his wallet by the corresponding face value.

To spend the output Bob is the recipient of and send Carol coins, he acts as follows.

10. Using your secret keys

$v$ and

$s$ calculates the secret part

$P_i$ :

$D_i = v^{-1} Q_i$

$x_i = s + H_s(D_i, h_t, i)$ , it is easy to see that

$P_i = x_i G$ (see paragraph 3).
11. Bob calculates the key image:

$I = x_i H_p(P_i)$ and writes it, the face value and a link to the corresponding output in the input of his transaction for Carol.
12. Bob reduces the balance of his wallet by the value of the output used.
13. Bob forms the outputs in the transaction for Carol in accordance with 1-5. Then signs the transaction and sends.

A feature of this scheme, unlike CryptoNote, is that anyone to whom Alice will transfer her secret hash

$v_s$ , will be able to calculate the recipient address

$(V, S)$ for any Alice transaction:

14.

$D_i = H_s(h_t, v_s, i) G$
fifteen.

$S = P_i — H_s(D_i, h_t, i) G$
sixteen.

$V = H_s(h_t, v_s, i)^{-1} Q_i$

However, the problem in this case is the task of determining which transactions Alice generated and sent. Without this information in p.p. 14-16 for arbitrary transactions will be obtained arbitrary useless data indistinguishable from real addresses

$(V, S)$ . The coding algorithm may provide some help in this encrypted_address_type, since for Alice’s transactions this field after decoding will have only valid values

$\{0, 1\}$ . But, unfortunately, acceptable values can also be obtained arbitrarily, and such a case cannot be distinguished.

Since in this scheme the calculation of key image also requires knowledge of the secret spend-key

$s$ , then the audit problem, that is, calculating the exact balance of the wallet without transferring the rights to spend money, remains unresolved.

4.4. tx.version ≥ amethyst, amethyst address

Constant h

The operation of this cryptographic scheme requires the introduction of a new constant - the point

$H$ group element

$\mathbf{G}$ , and the order of the point

$H$ unknown. In other words, this is some fixed public key, the secret part of which is guaranteed unknown and the probability of its finding is negligible:

$H = yG$ where

$y$ Is an unknown number.

For example, you can set

$H$ as proposed in [ 8 ]:

$H = H_p(G) = to\_point( cn\_fast\_hash(G) )$

Bytecoin developers do not calculate the constant, but set it numerically, without any indication of the nature of its origin:

bytecoin / src / crypto / crypto_helpers.hpp, line 67

constexpr P3 H{ge_p3{{7329926, -15101362, 31411471, 7614783, 27996851, -3197071, -11157635, -6878293, 466949, -7986503},    {5858699, 5096796, 21321203, -7536921, -5553480, -11439507, -5627669, 15045946, 19977121, 5275251},    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},    {23443568, -5110398, -8776029, -4345135, 6889568, -14710814, 7474843, 3279062, 14550766, -7453428}}};

However, a search for this numerical sequence showed ([ 9 ]) that they use the same constant as in Monero for RingCT, the calculation method of which and its justification were considered in [ 8 ].

Because the

$H$ belongs to the group

$\mathbf{G}$ , then we can say that

$H$ also spawns a group

$\mathbf{G}$ as the base point

$G$ .

It means that

$\forall x \in [1,p-1], xH \in \mathbf{G}$

Multiple unlinkable addresses

In the original CryptoNote, each wallet (that is, a set of secret keys) was associated with one public address, which was used to transfer funds to it.

The considered scheme allows generating an unlimited number of public addresses on the same set of secret keys. Wherein:

addresses are generated deterministically from the initial set of secrets;
these addresses cannot be interconnected, i.e. an outside observer will not be able to calculate that they belong to the same account;
verification of incoming transactions and accounting for $N$ multiple addresses will be computationally easier than checking $N$ accounts in the usual scheme.

Wallet account represented by secret key.

$s$ and hash

$v_s$ , as well as in the previous scheme. However, based on the hash

$v_s$ now not only a secret view key is generated deterministically

$v$ , but also an additional secret audit key

$a$ .

The process of generating the i-th address is as follows (Fig. 4.4.2).

_{Fig. 4.4.2. Generation of amethyst addresses for the Bytecoin account (the calculated values are highlighted in yellow, the disclosure of which does not threaten the disclosure of secret keys $v$ , $s$ and $v_s$ )}

1. Calculated

$\delta = H_s(A + sH, i)$ and

$\Delta = \delta G$
2.

$S = A + sH + Δ$
3.

$V = vS = v(A + sH + Δ) = v(A + sH) + δV$
4. pair

$(V, S) = (v S, S)$ is an

$i$ The public address of this account.

Note that for the calculation it is enough to know the following values:
•

$A$
•

$V$
•

$s H$
•

$v (A + s H)$

Quantities

$s H$ and

$v (A + s H)$ are calculated when creating an account and are considered safe in the sense that knowing them, you cannot calculate

$s$ or

$v$ .

Generated addresses are stored locally in a container optimized for field search.

$S$ .

Formation of exits when sending funds

Alice sending money to Bob at his address

$(V, S)$ forms the outputs of its transaction as follows (Fig. 4.4.3).

_{Fig. 4.4.3. Formation of transaction outputs when sending funds to an Amethyst address}

1. Calculates

$h_t = H(tx.inputs, tx.version)$ , then for each exit

$i$ :
2.

$P_i = H_s( H_p(h_t, v_s, i), h_t, i )^{-1} S$
3.

$Q_i = H_s( H_p(h_t, v_s, i), h_t, i )^{-1} V + H_p(h_t, v_s, i)$
4. Couple

$(P_i, Q_i)$ - public exit keys

$i$ .

Accounting for Incoming Payments

To accept the money, Bob analyzes all transactions as follows (Fig. 4.4.4.).

_{Fig. 4.4.4. Analysis of transaction outputs for incoming transfers}

For each exit $i$ using a secret view key $v$ Bob computes: $K = H_p(h_t, v_s, i) = Q_i — v P_i$ ( output_shared_secretin code)
$S’ = H_s(K, h_t, i) P_i$
After which he tries to find $S’$ in your address list. If it finds, it means that this exit transfers money to Bob. It increases the balance for the corresponding address.

This means that in order to correctly take into account incoming payments, in this scheme, in addition to the list of addresses or keys for generating them, you need to know the secret view key

$v$ .

Formation of outgoing payments

To spend a way out

$i$ which Bob is the recipient, and send the coins to Carol, he acts as follows.

$K = H_p(h_t, v_s, i) = Q_i — v P_i$ ( output_shared_secretin code)
$x_i = H_s(K, h_t, i)^{-1} (a + \delta)$
$X_i = x_i G + H_s(K, h_t, i)^{-1} s H$
Calculates key image $I = x_i * H_p(X_i)$
Bob reduces the balance related to his address $S = H_s(K, h_t, i) P_i$ by the nominal value of the corresponding output.
Bob generates transaction outputs, signs it, and sends it.

It is seen that to calculate the key image requires knowledge of not only the secret view key

$v$ , but also

$a$ .

An important feature of this scheme is the ability to calculate a key image (and, therefore, take into account its outgoing payments, therefore, balance calculation) without using a secret spend-key $s$ .

Audit Recipient Address Disclosure

As well as the previous one, this cryptographic scheme allows you to extract recipient addresses from transaction outputs if the sender’s secret hash is known

$v_s$ .

This happens as follows (Fig. 4.4.5).

_{Fig. 4.4.5. Auditor possessing $v_s$ , restores information on incoming / outgoing payments, balance and addresses of recipients}

Suppose Alice passed

$v_s$ and

$s H$ Carol. Then Carol:

Recover secret keys $v$ and $a$ , will restore Alice's address list.
Will scan the blockchain for each output. $i$ each transaction will determine if it is an incoming payment, trying to find
$S’ = H_s(Q_i — v P_i, h_t, i) P_i$
among the addresses of Alice.
If it finds, then Carol will increase the balance of the corresponding address and, with $a$ and $v$ , will compute key image (see above) and save it locally.
If Alice's key image is found among transaction inputs, then this will mean that this transaction is Alice's outgoing payment. Carol will recover recipient addresses for all outputs of this transaction:
$S = P_i H_s(H_p(h_t, v_s, i), h_t, i)$
$V = (Q_i — H_p(h_t, v_s, i)) H_s(H_p(h_t, v_s, i), h_t, i)$
and reduce the balance of the corresponding Alice address by the value of the input value.

Thus, revealing part of the account data, you can provide third parties with different levels of access to information.

To generate a list of your addresses:
•

$A$
•

$V$
•

$s H$
•

$v (A + s H)$

To recognize only incoming payments:
•

$A$
•

$v$
•

$s H$

To audit, i.e. calculate the balance at your addresses, without disclosing the addresses of the recipients:
•

$a$
•

$v$
•

$s H$

To audit, i.e. calculate the balance at your addresses, and disclose the addresses of the recipients:
•

$v_s$
•

$s H$

4.5. Comparing CryptoNote and Bytecoin Amethyst Transaction Signatures

Data Structures and Signature Sizes

As noted above, the implementation of the ability to audit wallets without revealing a secret spend key required Bytecoin Amethyst developers to increase the size of the data transmitted in each transaction output: compared to the original protocol, one public key and 1 byte are transferred to identify the type of address. Total 33 bytes per output.

In CryptoNote, each transaction is signed separately for a transaction. For each public key

$P_i$ of some output to which this input refers, a pair of scalars is written in the signature

$(r,c)$ total size of 64 bytes. (An entry can refer to several exits, only one of which is real, and the rest serve to anonymize the transfer.)

Thus, if the transaction

$N_{inputs}$ inputs, each of which refers to

$N_{mixins}$ outputs, the total size of the signature in bytes can be expressed as:

$S = 32 * 2 * N_{mixins} * N_{inputs}$

The minimum signature size for a transaction is 64 bytes (one input that spends one output directly).

In Bytecoin Amethyst, the entire transaction is signed, and the corresponding data structure is complicated (Fig. 4.5.1).

_{Fig. 4.5.1. Comparing Transaction Signature Structure in CryptoNote and Bytecoin}

For each transaction input, a period, two scalars and another

$N_{mixins}$ scalars. Another signature is also added to the entire signature. Total, the total size of the signature in bytes can be expressed as:

$S = 32 * ((3 + N_{mixins}) * N_{inputs} + 1)$

The minimum signature size for a transaction is 160 bytes (one input that spends one output directly).

It can be seen that both functions grow in proportion to the product

$N_{mixins} * N_{inputs}$

To compare the difference in transaction signature sizes more clearly, we calculate them for the most characteristic values

$N_{mixins}$ and

$N_{inputs}$ and make a table (Fig. 4.5.2).

_{Fig. 4.5.2. The difference in the size of the Bytecoin transaction signature compared to CryptoNote (as a percentage of the size of the CryptoNote signature; the green is the gain in the size of the Bytecoin signature)}

As you can easily see, in a situation where there is no mixing of outputs and there is a direct waste of funds (

$N_{mixins} = 1$ ), or when one output is mixed (

$N_{mixins} = 2$ ), Bytecoin's signature size is larger than CryptoNote up to 150%.

When mixing two outputs (

$N_{mixins} = 3$ ) the sizes of signatures in one and the other scheme practically coincide.

With a further increase in the number of mixed outputs, the size of the Bytecoin signature is smaller.

It is worth noting that Bytecoin developers with the release of version 3.4.0 Amethyst in order to increase anonymity set the minimum number of mixed outputs to 3 [ 10 ]. In such circumstances, the Bytecoin signature will have a smaller size.

The complexity of signature verification

In addition to the size of the ring signature, which directly affects the size of the blockchain, another important characteristic is the computational complexity of its verification. It determines such important parameters of the cryptocurrency system as, for example, the speed of synchronization with the network of new nodes and the computational load on the network with a large flow of transactions.

The complexity of signing verification for CryptoNote and Bytecoin could be easily compared practically by simply writing a test that generates and then verifies a large number of signatures with given

$N_{mixins}$ and

$N_{inputs}$ , however, since later in the article we will consider the schemes that have not yet been implemented in practice, but only proposed in theory, it will be logical to laborious and evaluate these schemes empirically, according to the number of cryptographic operations used.

CryptoNote and Bytecoin use several basic primitives (see section 2). In the table in fig. 4.5.3. the typical runtime of the most commonly used primitives is given on a modern middle-end computer with a Core i5-6500 processor (for comparison, the original source code compiled in Microsoft Visual Studio 2017 with all possible speed optimizations was used).

_{Fig. 4.5.3. The characteristic time of the main cryptographic operations}

The results obtained from tests in Bytecoin and CryptoNote are in good agreement. It is easy to see that the largest contribution will be made by the operation of multiplying the scalar by a point, and, to a lesser extent, the procedure for computing the hash function

$H_p$ , while the operations of adding two points and computing a hash function

$H_s$ will not significantly affect complexity.

Consider the CryptoNote ring signature verification procedure (Fig. 4.5.4, the signature generation procedure was discussed in detail in [ 1 ] and will not be considered here).

_{Fig. 4.5.4. CryptoNote Ring Signature Verification Scheme}

As already noted, in CryptoNote, each transaction input is signed separately, respectively, and each input is also checked separately. Therefore, the verifier for each transaction input verifies the corresponding line (in the figure) of the signature as follows.

For each pair of values $r_j$ and $c_j$ using key-image input $I$ and public key $P_j$ of the next output to which this input refers, the values are calculated: $L_j = r_j G + c_j P_j$
$R_j = r_j H_p(P_j) + c_j I$
(in this case, index j runs from 0 to $N_{mixins}$ )
The amount is calculated $c$ of all $c_j$ .
The hash is calculated $c`=H_s(tx\_prefix\_hash, L_0 ... L_n, R_0 ... R_n$ )
where tx_prefix_hashis the hash of the prefix part of the transaction (without a signature).
Equality checked $c` = c$ . If it is, then the ring signature is considered valid.

Let us estimate the number of scalar multiplication operations by a point and hash calculations

$H_p$ .

Every calculation

$L_j$ and

$R_j$ requires two scalar multiplications. Number of pairs

$L_j, R_j$ corresponds to the number of outputs to be mixed

$N_{mixins}$ for each entry. Therefore, we have:

$O(*) = N_{inputs} * 4 * N_{mixins}$

In this case, the hash function

$H_p$ used once per calculation

$R_j$ , hence:

$O(H_p) = N_{inputs} * N_{mixins}$

Now, consider the ring signature verification algorithm in Bytecoin Amethyst (Fig. 4.5.5).

_{Fig. 4.5.5. Bytecoin Amethyst ring signature verification scheme}

The entire signature is checked entirely, for all inputs at once. It happens like this:

The prefix hash of the transaction is written to the hash buffer (without signature).
For each entry $i$ (signature line in the figure):
Calculated $H_s$ according to all data of the hash buffer and the result is compared with the value $c_0$ . A signature is considered valid if equality is respected.

Let us estimate the number of scalar multiplication operations by a point and hash calculations

$H_p$ .

Every calculation

$Y_j$ and

$Z_j$ requires two scalar multiplications, plus calculation

$X$ requires three scalar multiplications. Number of pairs

$Y_j, Z_j$ corresponds to the number of outputs to be mixed

$N_{mixins}$ for each entry. Therefore, we have:

$O(*) = N_{inputs} * (3 + 4 * N_{mixins})$

In this case, the hash function

$H_p$ used once per calculation

$Z_j$ and once for calculating

$B$ for each of the inputs, therefore:

$O(H_p) = N_{inputs} * (N_{mixins} + 1)$

To visually compare the computational complexity of both algorithms on standard data, we introduce the following metric. Add the number of scalar multiplication operations and calculation operations

$H_p$ with weights proportional to the characteristic time taken to complete these operations:

$O(total) = 130 * O(*) + 15 * O(H_p)$

Then compare the relative results for CryptoNote and Bytecoin in percent (Fig. 4.5.6).

_{Fig. 4.5.6. Computational complexity of Bytecoin Amethyst ring signature verification compared to CryptoNote (dependency on $N_{inputs}$ missing)}

As you can see, Bytecoin signature verification is a much more time-consuming operation.

However, as noted above, in Bytecoin from version 3.4.0 Amethyst, in order to increase anonymity, the minimum number of mixed outputs is set to 3 [ 10 ], therefore, the worst practical value will not exceed 25% (in theory).

To summarize:

The size of each output is increased by the public key $Q$ - 32 bytes.
The size of the ring signature varies in comparison with the size of the CryptoNote signature depending on the number of outputs mixed (with a large number it turns out to be less):
$S = 32 * ((3 + N_{mixins}) * N_{inputs} + 1)$
Computational complexity is higher than in CryptoNote and significantly depends on the number of outputs to be mixed:
$O(*) = N_{inputs} * (3 + 4 * N_{mixins})$
$O(H_p) = N_{inputs} * (N_{mixins} + 1)$

5. Option 2/3. Audit Studies at CryptoNote by Anton Sokolov

In the fall of 2019, a series of essays [ 11 , 12 , 13 , 14 , 15 , 18 ] about the audit problem in CryptoNote and possible ways to solve it authored by Anton Sokolov was published on Medium.com . It theoretically considers several options for modifying the original protocol in such a way as to solve the audit task for a third party.

We consider the last of them [ 15 ] as the most optimized. We will abbreviate it as "AS".

Note: for consistency, spend keys will continue to be denoted by letters

$s$ and

$S$ , view keys in letters

$v$ and

$V$ , despite the fact that in the original works are used

$b$ ,

$B$ and

$a$ ,

$A$ respectively.

Output Formation

The wallet account is represented by a set of three secret keys, not two, as in CryptoNote

$\{v, s, d\}$ : view-, spend- and audit-keys, respectively.

A collection of three public keys

$\{V, S, D\}$ represents the public address of this account.

Alice, sending money to the bean, acts as follows (Fig. 5.1).

_{Fig. 5.1. Formation of transaction outputs in the AS scheme}

Bob publishes his address, so Alice knows his public keys $V$ , $S$ and $D$ .
Like CryptoNote, Alice picks a random secret transaction key $r$ and calculates the public key $R = r G$ which writes to the special field extra transactions.
For each output, Alice calculates not one, but two stealth addresses $P$ and $T$ . The first is calculated similarly to CryptoNote:
$P = H_s(r V) G + S$
The second is different:
$T = H_s(r D) D$
The serial number of the output is not used in the original work, however, it is reasonable to assume that this is done for simplification and in practice it will be one of the function arguments $H_s$ similar to CryptoNote (see section 3).
Alice signs and sends the transaction.

An outside observer will not be able to bind

$P$ and

$T$ with Bob's address.

Recognition of incoming payments and formation of inputs

To accept and spend money, Bob acts as follows (Fig. 5.2).

_{Fig. 5.2. Definition of incoming transfers and formation of inputs for the transaction that spends them}

Using your private view key $v$ Bob stealth address $P$ compares each output with a point:
$P’ = H_s(vR)G+S$
(this step is similar to CryptoNote)
In case equality is fulfilled, this means that this output is addressed to Bob. He increases his balance by the value of the nominal output.
If necessary, transfer the funds received Carol, Bob, using their secret spend- and audit-keys $s$ and $d$ computes two key image: $I$ and $\ddot I$ . The first is similar to CryptoNote:
$I = x * H_p(P)$
and optional:
$t = H_s(dR)d$
$\ddot I = t H_p(P)$
Then he writes them, the face value and a link to the corresponding output into the input of his transaction for Carol.
Then Bob forms the transaction outputs for Carol, reduces his balance in proportion to the spent outputs, signs the transaction and sends.

As you can see, here, as in CryptoNote, the third party - the Auditor - possessing only a secret view key

$v$ , can only recognize incoming transfers.

Audit

If the Auditor also has a secret audit key

$d$ , then he will be able to recognize Bob's outgoing payments and calculate his balance as follows:

For each incoming payment, the Auditor will calculate and remember an additional key image $\ddot I$ in local storage:
$t = H_s(d R) d$
$\ddot I = t H_p(P)$
If in the inputs of any of the blockchain transactions an additional key image $Ï$ If it coincides with one of the saved ones, this will mean that this transaction is Bob's outgoing payment. The auditor will reduce the balance by the nominal value of the corresponding input.

Thus, the Auditor, having a set of keys

$\{v, S, d\}$ will be able to recognize Bob's incoming and outgoing transfers on the blockchain and restore his correct balance. At the same time, the Auditor will not be able to spend money, because without secret spend key

$s$ he will not be able to calculate the main key image

$I$ .

The problem is solved.

Ring signature

Applying the ideas from [ 16 ], the author managed to reduce the size of the signature compared to CryptoNote: now, for each input, only the signature is stored

$N_{mixins} + 1$ scalar (Fig. 5.3).

_{Fig. 5.3. Comparing Ring Signature Sizes in AS and CryptoNote}

Thus, the signature size is almost halved.

Consider the computational complexity of its verification. The signature verification scheme is shown in Fig. 5.4.

_{Fig. 5.4. Ring signature verification scheme in AS}

This algorithm is very similar in structure to that used in CryptoNote (see Fig. 4.5.4). The check is carried out separately for each input and consists in sequentially calculating the values

$u_j$ ,

$L_j$ ,

$R_j$ ,

$c_j$ for all outputs used for mixing in this input. As a result, the cycle of

$c_j$ should close and the value

$c_{n+1}$ must match

$c_0$ , in this case, the signature is considered valid.

The computational complexity of the algorithm is determined by six scalar multiplication operations and one calculation of the hash function

$H_p$ to iteration, the number which is the product

$N_{inputs} * N_{mixins}$ .

Comparison with CryptoNote by data and computational load

The size of the address increases by 50%, because the address now represents a collection of three public keys:{V,S,D}not two {V,S}.
The encoded representation of the address will increase by about the same: for example, a standard Zano address containing two public keys takes 97 characters:
```
ZxD5UBX5PM3RTsEtTRd9ATUFxXyocoQzDRk3baVBahuWQJRK8QHTUT9GQM7jk7GoedK5B2nP4HxSPDpuLHvizpwj2q99bmz7t
```
A similar Zano address containing three public keys will have a length of about 141 characters:
```
ZxD5UBX5PM3RTsEtTRd9ATUFxXyocoQzDRk3baVBahuWQJRK8QHTUT9GQM7jk7GoedK5B2nP4HxSPDpuLHvizpwjcenhnGbhpJFLk8vkhJywHCcht4d9EKA7CHHav1H6QPpB1cLsTvPfj
```
The size of each output is increased by an additional stealth address $T$ - 32 bytes.
The size of each input is increased by an additional key image $\ddot I$ - 32 bytes.
The size of the ring signature is smaller than in CryptoNote:
$S = 32 * (N_{mixins} + 1) N_{inputs}$
Computational complexity is higher than in CryptoNote:
$O(*) = N_{inputs} * 6 * N_{mixins}$
$O(H_p) = N_{inputs} * N_{mixins}$

6. Option 3/3. Audit through output mixing limit

Consider another way to implement auditing in CryptoNote.

Mix_attr output attribute

In the Zano project, which is the successor to CryptoNote, the transaction output has an additional 8-bit mix_attr attribute, and a kernel rule restricting the use of outputs in mixing, depending on its value.

The structure of the outputs of CryptoNote and Bytecoin (Fig. 4.2) we can now supplement in this way (Fig. 6.1.).

_{Fig. 6.1. Comparing the data structure for CryptoNote, Zano, and Bytecoin Amethyst transaction outputs}

The kernel rule restricting mixing according to mix_attr is this:

If mix_attr = 0, then there are no restrictions. This output can be used to mix with other outputs in any combination. This is the default value.
If mix_attr = 1, then this output can only be spent directly, without mixing, and cannot be used to mix with other outputs.
If mix_attr ≥ 2, then this output can be spent only when mixing others, while the total number of outputs used should not be less than the value of mix_attr.

The main feature of this innovation is paragraph 3, which allows one to increase untraceability (untraceability of bonds) by eliminating situations where the output already used in mixing is spent by its owner directly (this was described in detail in [ 19 ]).

However, in the context of this article, we will be interested in item 2, that is, the situation where mix_attr = 1 and the output marked in this way can only be spent directly. This limitation is illustrated in fig. 6.2.

_{Fig. 6.2. Limit illustration. Above : input # 0 refers only to output # 0 with mix_attr = 1 (direct waste) - a valid situation. Bottom : input # 1 refers to three outputs: output # 2 with mix_attr = 1 and also to output # 1 and output # 3 - an invalid situation}

Since output # 2 has mix_attr = 1, it cannot be mixed with other outputs, regardless of their mix_attr attribute values. It can only be spent directly, as output # 0.

This feature can be used to organize an audit.

Audit with mix_attr = 1

As noted in Section 3, if, under the original CryptoNote protocol, Auditor Dan receives a secret key from Bob

$v$ , he will be able to recognize incoming transactions, but he will not be able to recognize outgoing transactions, so accurate calculation of the balance is impossible.

Nevertheless, since Den will have complete information about Bob's unspent (UTXO) exits, he will be able to track the fact that some transaction in his inputs refers to Bob's UTXO. When using the mixing of other outputs, Den will not be able to determine whether this transaction is spending Bob's output, which is achieved through the use of a ring signature. However, if there is no mixing and Bob’s UTXO is spent directly, then Auditor Dan can be sure that this transaction is Bob’s outgoing payment. This is the idea of this scheme.

Suppose Alice sends a transaction to Bob, and Bob wants Auditor Dan to see the fact that Alice received the money and that they spent when Bob decided to spend it.

The scheme of work will look as follows (Fig. 6.3).

_{Fig. 6.3. Auditor using a secret view key $v$ Bob defines inbound and outbound transactions}

Bob tells Alice his public address $(V, S)$ , and also asks her to set the mix_attr attribute to 1 in all the outputs addressed to him (below we will consider how this can be technically implemented).
Bob gives auditor Dan his secret view key $v$ .
Alice sends Bob a transaction using the usual CryptoNote scheme. In the outputs addressed to Bob, she sets mix_attr = 1.
Dan scans all transactions on the blockchain and, using Bob's secret view key, checks for each exit $P_i \stackrel{?}{=} P’_i = H_s(v R, i) G + S$ (Where $i$ - serial number of the output, $S$ - Bob's public spend-key). If equality holds, then this output is addressed to Bob.
Den makes sure that mix_attr == 1, adds this output to the list and increases the balance by the value of the output.
Dan also checks all the inputs of all transactions, and if one of the inputs refers to Bob's UTXO from the list, this means that this transaction is Bob's outgoing payment. Due to the restriction mix_attr = 1, the input cannot mix other outputs, which means it spends Bob's output directly, and Den can be sure that this is Bob's outgoing payment. Den reduces the balance by the value of the input.

Thus, Den will be able to calculate the correct balance of Bob’s wallet without gaining access to his secret spend-key

$s$ .

Circuit features

Feature 1. It is important that the sending party (Alice) set mix_attr to 1 when sending a transaction. If Alice does not do this, then the funds will come to Bob, but in the future, Den will not be able to clearly say whether Bob spent them or not, since any other user will be able to use this output to mix.

One solution is introducing a special type of address containing the same two public keys

$(V, S)$ but packaged in a different way from the standard. Alice, sending funds to an address of this type, will know about the need to set mix_attr = 1 for the corresponding outputs.

Feature 2. The use of addresses of a special type does not oblige Alice to set the desired attribute value for the outputs. She can send funds without doing this, however, it will be immediately revealed by both Bob and the auditor Dan.

Feature 3. In this scheme, audit capability is achieved at the price of the utmost reduction in untraceability. This does not present a particular problem if the audit opportunity is provided to an unlimited circle of people. For example, a charity fund can publish a donation address along with a secret view key, so anyone can act as an auditor and calculate the current balance of his wallet. It is important that in this case the anonymity of incoming transfers remains standard for CryptoNote (a large number of

$N_{mixins}$ ) However, the anonymity of outgoing payments will be limited by the inability to mix arbitrary outputs.

It is worth noting that in the case when the audit opportunity is provided to a narrow circle of people, in contrast to the example above, a decrease in untraceability may be an undesirable effect.

The big advantages of this option are ease of implementation and the absence of additional load on calculations and data.

7. Conclusion

We examined three options for adding the possibility of conducting an audit to the CryptoNote protocol: Bytecoin Amethyst, the theoretical AS scheme by Anton Sokolov, and the use of mix_attr (denoted by MA).

The relative change in ring signature size for all options except Bytecoin (BCN) is independent of

$N_{inputs}$ therefore consider

$N_{inputs} = 1$ (minimum) and

$N_{inputs} = 3$ (Fig. 7.1).

_{Fig. 7.1. Comparison of the sizes of the ring signature when $N_{inputs} = 1$ and $N_{inputs} = 3$ for all options considered}

Note. $N_{inputs}$ - the number of entries in the transaction, $N_{mixins}$ - the number of outputs associated with each transaction input. If $N_{mixins} > 1$ this means that to increase untraceability, each input refers to more than one output of some other transaction, and it is impossible to establish which one is real.

The best result is shown by the AS circuit, giving a reduction in the size of the ring signature in a wide range of the number of outputs to be mixed (

$N_{mixins}$ ) Bytecoin also gives good results when

$N_{mixins} \ge 3$ (as already noted, a minimum number limit was introduced in Bytecoin Amethyst to increase untraceability

$N_{mixins}$ equal to 3).

The MA scheme does not offer any improvements in the size of the ring signature.

Let us now compare the laboriousness of the ring signature verification procedure. To do this, we will use the metric mentioned above, namely, we take the sum of the operations of the scalar product and the calculation of the hash function

$H_p$ with weights proportional to their runtime on a typical modern processor:

$O(total) = 130 * O(*) + 15 * O(H_p)$

We have the following picture (Fig. 7.2).

_{Fig. 7.2. Comparison of the increase in computational complexity of ring signature verification ( $N_{inputs} = 1$ )}

With direct spending of funds (

$N_{mixins} = 1$ ) AS and Bytecoin schemes require significantly more computation to verify the signature.

When mixing outputs (

$N_{mixins} > 1$ ) Bytecoin Amethyst scheme looks preferable to AS, however, the last considered MA option remains unsurpassed.

Let us summarize the final result, taking into account factors such as an increase in the size of the address, inputs and outputs of transactions (Fig. 7.3).

_{Fig. 7.3. Comparison of all considered schemes}

Bytecoin maintains the length of the address convenient for the end user, while the Anton Sokolov scheme increases it by 50%. This does not directly affect the blockchain size (although the sender address in encrypted form can be transmitted in extra transactions if the latter wishes, for example) and computational complexity, however, it does not significantly affect usability. In the MA scheme, the address size remains equal to 64 bytes; however, a way is required to distinguish audit addresses from normal ones.

Audit options for Bytecoin and AS include adding one point (32 bytes) to each transaction output, however, the input size remains unchanged only for Bytecoin.

It is also worth noting that the Bytecoin Amethyst scheme has been implemented in the code for a long time and, judging by the lack of messages about problems that have passed since its implementation, it is well tested in practice. However, it was not possible to find its public description in a strict form, therefore, there are no formal proofs of its correctness.

The AS scheme, on the contrary, is strictly described and proposed for discussion in the crypto community [ 17 ].

The MA scheme does not have a strictly described formal proof; however, due to its extreme simplicity, it seems unnecessary.

Audit Wallets in CryptoNote

Content

1.

CryptoNote?

The concept of audit and its application

About the author and purpose of publication

2. Basic information about cryptography on elliptic curves

3. Accounting and balance calculation in CryptoNote

4. Option 1/3. Bytecoin auditable coins

4.1. tx.version <amethyst, legacy address

4.2. tx.version ≥ amethyst

4.3. tx.version ≥ amethyst, legacy address

4.4. tx.version ≥ amethyst, amethyst address

Constant h

Multiple unlinkable addresses

Formation of exits when sending funds

Accounting for Incoming Payments

Formation of outgoing payments

Audit Recipient Address Disclosure

4.5. Comparing CryptoNote and Bytecoin Amethyst Transaction Signatures

Data Structures and Signature Sizes

The complexity of signature verification

5. Option 2/3. Audit Studies at CryptoNote by Anton Sokolov

Output Formation

Recognition of incoming payments and formation of inputs

Audit

Ring signature

Comparison with CryptoNote by data and computational load

6. Option 3/3. Audit through output mixing limit

Mix_attr output attribute

Audit with mix_attr = 1

Circuit features

7. Conclusion

Literature

More articles: