Three ways to audit wallets in CryptoNote

This article discusses three ways to audit wallets without transferring control in cryptocurrencies of the CryptoNote family. Wallet auditing refers to the possibility 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. The article discusses various ways to provide this possibility in the CryptoNote 2.0 cryptocurrency protocol, where auditing is only partially implemented: using the 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 familiar with the topic of blockchain and “classic” cryptocurrencies, as well as with the basics of elliptic curve cryptography. What is CryptoNote? Oddly enough, most of those interested in blockchain and cryptocurrencies have not heard anything about CryptoNote, despite the fact that this technology was the basis for more than 300 forks, the most famous of which was Monero. In 2014, mentions of the project appeared in the cryptocurrency environment, which was called Bytecoin. The project was not a fork of Bitcoin or any other 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 inputs using a ring signature (it was also called at that time “a 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 crypto-currency 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, managed to attract the greatest attention to the technology both among the community and among investors. This fork was called BitMonero, but rather soon it was renamed Monero. Later on, 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 developments of the CryptoNote technology. The concept of audit and its applications Unlike the classic “pseudo-named” blockchain such as Bitcoin, in which anyone can trivially calculate the balances of any address by scanning the blockchain, 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 mentions of any addresses in the blockchain at all (this property is usually referred to as anonymity). Secondly, due to the fact that, thanks to the ring signature, the transaction input does not point to one specific output of the parent transaction, but points to many possible outputs, it is also not possible to track the movement of funds (this property is called untraceability). In the traditional sense of a private cryptocurrency, these properties are necessary, but there are special cases where a wallet owner may want to disclose their transaction history and current wallet balance to a third party, while ensuring that they cannot be spent by a third party. This may be necessary, for example, for exchanges to interact with regulators or supervisory authorities.. In addition, it may be important for various funds that would like to be able to be transparent to a certain group of people or be completely public. Formally speaking, wallet auditing means the ability for a third party (“auditor”) to see the transactions of this wallet and calculate it correct current balance without transferring the right to spend funds. In the original version of CryptoNote, auditing was only partially implemented: using the tracking key, you can recognize incoming transactions, but you need a full set of keys to recognize outgoing ones. by the same hands that the original technology code was written. The team is now considering the possibility of adding wallet auditing to the project and is conducting research on this topic in order to select the best option. The author wishes to acquaint readers with the results of some of these studies.2. Elliptic Curve Cryptography Basics The CrypoNote protocol uses the elliptic curve from the ed25519 public key digital signature scheme. Recall the main parameters of this curve and give additional definitions. A large prime number q = 2255 – 19 is fixed. All operations occur in integers in a finite field Fq of residues modulo q. Given an elliptic curve over a field Fq, denoted by E/Fq: −x2+y2= 1 +dx2 y2, where d = −121665/121666 (the ratio is calculated in Fq and is an integer). The fact of its symmetry with respect to x and y is important. An operation is geometrically defined over the set of points of the curve that gives the third one for any two points: F(A, B) = C, conditionally called “addition”, and the neutral element is given as a point lying at infinity (this is discussed in detail here). This operation does not lead outside the set, has associativity, commutativity and the presence of an inverse element, due to which all points of the curve, together with it, form an Abelian group, denoted by E(Fq). The order of this group (the number of all points): #E(Fq)=2cl, where c = 3 (cofactor) and l=2252+27742317777372353535851937790883648493. Each point of the curve is given by its own coordinates (x, y). Since the coordinates are related by a curve equation, this representation is redundant, and therefore only the y-coordinate, encoded as a 256-bit number, is used to save money when implementing cryptographic functions. x-coordinate, according to the symmetry of the curve (see. equation) can be only one of two options, the choice of which is encoded as the most significant bit of the number representing the y-coordinate. A special point of the curve G = (x, −4/5) is fixed. The point is given by the y-coordinate, of the two possible options for x, a positive one is chosen. Addition (cm. p. 3) a point G with itself n times defines the operation of multiplying by an integer, which forms a closed multiplicative group G, the order of which is less than E(Fq): #G< #E(Fq), while #G=l=2252+ 27742317777372353535851937790883648493. The public key X is an elliptic curve point that belongs to the group G: X ∈ G The secret key x, or scalar corresponding to the public key X, is an integer such that: X = x * G, x ∈ [1; l-1] Private key, same as public key (see. above) is encoded as a 256-bit number. The main hash function H is defined (referred to as cn_fast_hash in the code and other sources). It computes a 32-byte hash over an arbitrary dataset: H : {0, 1} * → [0.2256-1]. valid secret key: Hs : {0,1} * → [1; l-1] Hs can be implemented trivially via H: Hs(x)= H(x) + 1 mod l key: Hp : {0,1} * → G The implementation of this hash function presents a certain complexity for the reason that, firstly, not any set of 256 bits can be decoded into an elliptic curve point (see. p. 4), and secondly, not every point of the curve belongs to the group G (see. p. 6). One trivial way to implement Hp is to sequentially hash the data H(H(...H(x)...)) until the result can be decoded to point XG. CryptoNote uses a more complex and efficient approach, implemented in the form of the ge_fromfe_frombytes_vartime function, which is discussed in detail in this work. Let's define a function that deterministically converts arbitrary 256 bits into an element of the group G as: to_point :[0.2256-1] → G In CryptoNote, the Hp hash function is implemented as follows: Hp(x) = to_point( H(x) ) 3. Accounting for funds and calculating the balance in CryptoNote 2.0 Let's recall how funds are sent and the balance is calculated in the original version of the protocol. Alice, sending money to Bob, generates the outputs of her transaction as follows. Rice. 3.1. Alice generates transaction outputs by sending money to Bob Bob has a pair of private keys (v, s). He calculates his address as a pair of corresponding public keys (V, S) and publishes it or sends it to Alice. Alice chooses a random transaction secret key r and calculates the public key R = r * G, which she writes in a special extra field of the transaction. For each output, Alice calculates the stealth address (one-time destination key): Pi = Hs(r * V, i) * G + S, where i is the exit sequence number. Alice signs and sends the transaction. An outside observer, analyzing the Pi stealth addresses, cannot tell whether a particular output is intended for Bob, and cannot even determine whether different outputs with keys Pi and Pj are intended for the same recipient.. To accept money, Bob analyzes all transactions on the blockchain in the following way. Rice. 3.2. Bob checks the outputs of the transaction to determine the incoming transfers. Using his private key v, Bob computes for each output P'i = Hs(v * R, i) * G + S (where i is the ordinal of the output, S is the public spend key Bob). If P'i == Pi, then this means that he is the recipient of this output and can spend it by calculating the corresponding secret key. Therefore, Bob increases his wallet balance by the value of this output. To spend an output that Bob is the recipient of and send coins to Carol, he proceeds as follows. Rice. 3.3. Bob generates an input for a new transaction using his own output Bob, using his private keys (v, s), calculates the private key xi = Hs(v * R, i) + s to the stealth address Pi, i.e. Pi = xi * G. Bob calculates the key image: I = xi * Hp(Pi) and writes it, the denomination and the link to the corresponding output into the input of his transaction for Carol. It should be noted that, firstly, only the owner of the secret spend-key s can calculate the key image (the correctness of this will be verified by the ring signature), and secondly, a third party will not be able to associate key image I and the corresponding stealth address Pi. Bob reduces the balance of his wallet by the value of the output used in step 6. Bob generates outputs in the transaction for Carol in accordance with paragraph 6.. 2-3. Then he signs the transaction and sends. Assuming that Bob has lost all of his transaction history but still has his private keys (v, s), then he can recover the transaction history and calculate his current balance as follows. Rice. 3.4. Bob determines his incoming and outgoing payments and calculates the balance Bob scans the entire blockchain and analyzes all transactions for outputs addressed to him (see. p. five). When finding such an output Pi, Bob increases the balance of his wallet by the value of the face value. Then, using its secret spend key s, calculates the corresponding secret exit key xi (n. 6) and key image I (n. 7). Then it writes the key image, Pi and other payment data to the table. If, during further scanning of the blockchain, Bob finds in the input of some transaction a key image that is 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 nominal value of the entry. By acting in this way, Bob will restore the current balance of his wallet. Please note that if the third-party auditor Dan receives the secret key v from Bob, then he will be able to recognize Bob's incoming transactions in the blockchain, however, without having the secret key s, he will not be able to recognize Bob's outgoing transactions, and therefore calculate the correct balance.. As will be shown below, if Bob directly spends the output 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 the auditor Dan both of his private keys (v, s), this will be equivalent to handing over the funds themselves, since Den, having s, will be able to spend them. Therefore, a full-fledged audit of wallets within the framework of the original CryptoNote 2.0 protocol is impossible.. In the following sections, we will consider protocol modification options that have this capability.. Note that it makes sense for Alice to keep the secret key of the transaction r (which happens in some implementations of the protocol). Anyone who knows r for a certain transaction can check whether the output i of this transaction refers to a given address (V, S) by simply repeating the calculation from step 3: P'i = Hs(r * V, i) * G + S and comparing the result with Pi. Alice can use this fact, for example, to prove that she transferred the money to Bob. It is impossible to calculate the target address (V, S) from the output, even knowing r. 4. Option A: Bytecoin Auditable Coins At the time of its inception, Bytecoin was the first and only implementation of the CryptoNote protocol, so it had all the features and limitations discussed in the previous section.. On February 7, 2018, the developers released version 3.4.0 of Amethyst, containing a number of improvements and changes to CryptoNote, which we will now review. Within the scope of this article, the most interesting change was the ability for ordinary wallets to create special copies - auditable wallet (AW), which have two properties: AW cannot spend funds from the main wallet; AW balance is always the same as the main wallet balance. It is not possible to change the main wallet balance without affecting the AW balance. However, only new version wallet addresses, the so-called amethyst addresses, have this functionality.. Existing addresses and accounts are backward compatible and 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, so both transactions of the old format ? and new ones are currently circulating in the Bytecoin network. New format transactions also support two types of addresses: amethyst and legacy, so we end up with 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 schema, but with deterministic r generation. The wallet account is represented by a secret key s and a hash vs. The secret view key v is deterministically generated as a function of vs. The secret key r of the transaction is now not chosen randomly, but calculated using vs: r = Hs(ht, vs), where ht = H(tx.inputs, tx.version) This eliminates the need to store secret keys r in local storage for future needs, since for any of its transactions ever sent to the blockchain, such a key can be calculated using vs. The wallet balance is calculated similarly to the original CryptoNote (see. section 3), i.e., to account for outgoing payments, you need the secret spend-key s. If all addresses to which funds have ever been transferred are stored in the local storage of the wallet, then it is possible to calculate the correct balance without using the secret spend-key s as follows: Alice scans transactions in the blockchain and keeps a record of incoming payments using secret view-key v, as described in section 3, and increases the 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 = Hs(r * V, i) * G + S If P'i = Pi, then this the output is Alice's outgoing payment to the address (V, S) and she reduces the balance. So Alice will calculate the balance using only vs and v. Obviously, this method is unreliable and impractical, since the absence of the address to which the transfer was actually made in the specified local storage will lead to overestimation of the balance. Therefore, it is of more theoretical interest.. 4.2. tx.version >= amethyst As noted above, starting from version 3.4.0 of Amethyst, Bytecoin has changed the transaction format. If tx.version >= amethyst, then transaction outputs have a different format. Now each output, in addition to the face value of amount and the public key Pi, also contains an additional public key Qi (denoted in the code as encrypted_secret) and an additional byte containing the encrypted address type, amethyst or legacy (called encrypted_address_type in the code). These structures are schematically shown in Fig.. 4.2. Fig. 4.2. Comparison of data structure for CryptoNote and Bytecoin Amethyst transaction outputs Thus, the size of each output increased by 33 bytes. For each output i, the address type is encoded and decoded as follows: encrypted_address_type(i) = (H(oi) & 255) xor address_tag where: oi = H(ht, vs, i) (referred to in 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 the secret key s and the hash vs, from which the secret view key v is deterministically generated. Alice, sending money to Bob at his address (V, S), forms the outputs of her transaction as follows: Calculates ht = H(tx.inputs, tx.version), then for each output i: Di = Hs(ht, vs, i) * G (denoted as output_shared_secret in the code) Pi = S + Hs(Di, ht, i) * G Qi = Hs(ht, vs, i) * V (in this case, Qi = v * Di, however, the recipient's view key v unknown) Pair (Pi, Qi) — public keys of output i. To accept money, Bob analyzes all transactions in the following way. 6. For each transaction calculates ht = H(tx.inputs, tx.version), then for each output i: 7. Di = v-1 * Qi 8. S' = Pi – Hs(Di, ht, i) * G 9. If S' matches Bob's public key S, then this output is for him and he increases his wallet balance by the corresponding value. To spend an output that Bob is the recipient of and send coins to Carol, he proceeds as follows. 10. Using his secret keys v and s, calculates the secret part of Pi: Di = v-1 * Qi xi = s + Hs(Di, ht, i), while it is easy to see that Pi = xi * G (see. p. 3)

11. Bob calculates the key image: I = xi * Hp(Pi) and writes it, the denomination and a link to the corresponding output into the input of his transaction for Carol.12.Bob reduces his wallet balance by the denomination of the output used.13. Bob generates transaction outputs for Carol in accordance with p.p.. 1-5. Then he signs the transaction and sends. A feature of this scheme, unlike CryptoNote, is that anyone to whom Alice passes her secret hash vs will be able to calculate the recipient address (V, S) for any Alice transaction: 14. Di = Hs(ht, vs, i) * G 15. S = Pi – Hs(Di, ht, i) * G 16. V = Hs(ht, vs, i)-1 * Qi However, the problem in this case is the task of determining which transactions were generated and sent by Alice. Without this information in p.p.. 14-16 for arbitrary transactions, arbitrary useless data will be obtained, indistinguishable from real addresses (V, S). The encrypted_address_type encoding algorithm can provide some help in this, since for Alice's transactions this field after decoding will only have valid values {0, 1}. But, unfortunately, valid values can also turn out arbitrarily, and such a case cannot be distinguished. Since in this scheme the calculation of the key image also requires knowledge of the secret spend-key s, the problem of auditing, that is, calculating the exact balance of the wallet without transferring the rights to spend funds, remains unresolved. 4.4. tx.version >= amethyst, amethyst address Constant H This cryptographic scheme requires the introduction of a new constant – the point H, an element of the group G, and the order of the point H is unknown. In other words, this is some fixed public key, the secret part of which is guaranteed to be unknown and the probability of finding it is negligible: H = y * G, where y is an unknown number. For example, you can set H as suggested here: H = Hp(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: 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} -7453428}}}; However, the search for this numerical sequence showed that they use the same constant as in Monero for RingCT, the method of calculating which and its rationale are discussed here.. Since H belongs to the group G, we can say that H generates the group G in the same way as the base point G. This means that ∀ x ∈ [1,p – 1], x *H ∈ G ) In the original CryptoNote, each wallet (that is, a set of secret keys) is associated with one public address, which is used to transfer funds to it. The considered scheme allows generating an unlimited number of public addresses on the same set of secret keys.. In this case: addresses are generated deterministically from the initial set of secrets; these addresses cannot be linked, i.e.. an outside observer will not be able to figure out that they belong to the same account; checking incoming transactions and accounting for the balance for N multiple addresses will be computationally simpler than checking N accounts in the usual scheme. The wallet account is represented by the secret key s and the hash vs, just like in the previous diagram. However, based on the vs hash, not only the secret view key v is now deterministically generated, but also an additional secret audit key a. The process of generating the i-th address is as follows: Fig. 4.4.2. Generation of amethyst addresses for a Bytecoin account (yellow circled pre-calculated values, the disclosure of which does not threaten the disclosure of secret keys v, s and vs) Calculate δ = Hs(A + s * H, i), Δ = δ * G S = A + s * H + Δ V = v * S = v * (A + s * H + Δ) = v * (A + s * H) + δ * V pair (V, S) = (v * S, S) is i-th 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) The values s * H and v * (A + s * H) are pre-calculated when creating an account and are considered safe in the sense that knowing them, one cannot calculate s or v. The generated addresses are stored locally in a container optimized for searching by the S field. Forming outputs when sending funds Alice, sending money to Bob at his address (V, S), generates the outputs of her transaction as follows (Fig.. 4.4.3). Fig. 4.4.3. Formation of transaction outputs when sending funds to an Amethyst address Calculates ht = H(tx.inputs, tx.version), then for each output i: Pi = Hs( Hp(ht, vs, i), ht, i )-1 * S Qi = Hs( Hp(ht, vs, i), ht, i )-1 * V + Hp(ht, vs, i) The pair (Pi, Qi) are the public keys of exit i. Accounting for incoming payments To accept money, Bob analyzes all transactions as follows (Fig.. 4.4.4.). Fig. 4.4.4. Parsing transaction outputs for incoming transfers For each output i, using the secret view key v, Bob calculates: K = Hp(ht, vs, i) = Qi – v * Pi (output_shared_secret in the code) S' = Hs(K, ht, i) * Pi Then tries to find S' in the list of its addresses. If found, it means that this output 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. Generating Outgoing Payments To spend output i, of which Bob is the recipient, and send coins to Carol, he proceeds as follows. K = Hp(ht, vs, i) = Qi – v * Pi (output_shared_secret in code) xi = Hs(K, ht, i)-1 * (a + δ) Xi = xi * G + Hs(K, ht , i)-1 * s * H Calculates key image I = xi * Hp(Xi) Bob decrements the balance related to his address S = Hs(K, ht, i) * Pi by the value of the corresponding output. Bob generates transaction outputs, signs it and sends it. It can be seen that to calculate the key image, knowledge of not only the secret view key v, but also a is required. key s. Disclosing recipient addresses for audit Just like the previous one, this cryptographic scheme allows you to extract recipient addresses from transaction outputs if the secret hash of the sender is known vs. This happens as follows: Fig. 4.4.5. The auditor, having vs, recovers information about incoming / outgoing payments, balance and addresses of recipients Suppose that Alice gave vs and s * H Carol. Then Carol: Retrieve secret keys v and a, Retrieve Alice's address list. Will scan the blockchain and for each output i of each transaction will determine if it is an incoming payment, trying to find S' = Hs(Qi – v * Pi, ht, i) * Pi among Alice's addresses. If found, then Carol will increase the balance of the corresponding address and, using a and v, calculate the key image (see. above) and store it locally. If among the transaction inputs there is Alice's key image, then this will mean that this transaction is Alice's outgoing payment. Carol will restore the recipient addresses for all outputs of this transaction: S = Pi * Hs(Hp(ht, vs, i), ht, i) V = (Qi – Hp(ht, vs, i)) * Hs(Hp(ht, vs, i), ht, i) and reduce the balance of the corresponding address of Alice by the nominal value of the input. Thus, by disclosing part of the account data, it is possible to provide a third party with various 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 their addresses, without disclosing the addresses of the recipients: a v s * H To audit, i.e.. calculate the balance for their addresses, and at the same time reveal the addresses of the recipients: vs s * H 4.5. Comparison of CryptoNote and Bytecoin Amethyst transaction signatures Data structures and signature sizes As noted above, the implementation of the ability to audit wallets without revealing the 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 to identify the type of address are transmitted. Total, 33 bytes per output. In CryptoNote, a transaction is signed separately for each of its inputs.. For each public key Pi of some output to which this input refers, a pair of scalars (r,c) with a total size of 64 bytes is written into the signature. (An input can refer to multiple outputs, only one of which is real, and the rest serve to anonymize the translation.) Thus, if there are Ninputs of inputs in a transaction, each of which refers to Nmixins of outputs, then the total size of the signature in bytes can be expressed as: S = 32 * 2 * Nmixins * Ninputs 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. Comparison of the structure of the transaction signature in CryptoNote and Bytecoin For each transaction input, a dot, two scalars and another Nmixins of scalars are written to the signature. Another scalar is also added to the entire signature. In total, the total signature size in bytes can be expressed as: S = 32 * ((3 + Nmixins) * Ninputs + 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 Nmixins * Ninputs. 4.5.2). Fig. 4.5.2. Difference in Bytecoin transaction signature size compared to CryptoNote (as a percentage of CryptoNote signature size; green indicates Bytecoin signature gain) when one output is mixed (Nmixins = 2), Bytecoin signature size is larger than CryptoNote up to 150%. When two outputs are mixed (Nmixins = 3), the sizes of signatures in both schemes are practically the same. With a further increase in the number of mixed outputs, the Bytecoin signature size turns out to be smaller. It is worth noting that with the release of version 3.4.0 of Amethyst, Bytecoin developers set the minimum number of mixed outputs to 3 in order to increase anonymity.. Under such conditions, 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 signature verification for CryptoNote and Bytecoin could be easily compared in practice by simply writing a test that generates and then verifies a large number of signatures with given Nmixins and Ninputs, however, since further in the article we will consider those that have not yet been implemented in practice, but only those proposed in theory of the scheme, it would be logical to evaluate the complexity of 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 characteristic execution time of the most commonly used primitives on a modern middle-end computer with a Core i5-6500 processor is given (for comparison, the original source code compiled in Microsoft Visual Studio 2017 with all possible speed optimizations was used). Rice. 4.5.3. Characteristic time of the main cryptographic operations The results obtained from the tests in Bytecoin and CryptoNote are in good agreement with each other. It is easy to see that the operation of multiplying a scalar by a number will make the greatest contribution, and, to a lesser extent, the procedure for calculating the hash function Hp, while the operations of adding two points and calculating the hash function Hs will not significantly affect the complexity. Consider the procedure for verifying the CryptoNote ring signature (Fig.. 4.5.4, the signature generation procedure is discussed in detail in the White Paper and will not be considered here). Rice. 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 input of the transaction verifies the corresponding line (in the figure) of the signature as follows. For each pair of values rj and cj, using the key-image of the input I and the public key Pj of the next output referred to by this input, the values are calculated: Lj = rj * G + cj * Pj Rj = rj * Hp(Pj) + cj * I (the index j runs from 0 to Nmixins) The sum c of all cj is calculated. The hash c`=Hs(tx_prefix_hash, L0 .. Ln, R0.. Rn) where tx_prefix_hash is the hash of the prefix part of the transaction (without signature). Checking equality c` = c. If it is true, then the ring signature is considered valid. Let us estimate the number of operations of multiplying a scalar by a point and calculating the hash Hp. Each calculation of Lj and Rj requires two scalar multiplications. The number of pairs Lj, Rj corresponds to the number of mixed outputs Nmixins for each input. Therefore, we have: O(*) = Ninputs * 4 * Nmixins In this case, the hash function Hp is used once for each calculation of Rj, therefore: O(Hp) = Ninputs * Nmixins Now consider the ring signature verification algorithm in Bytecoin Amethyst (Fig.. 4.5.5). Fig. 4.5.5. Ring signature verification scheme in Bytecoin Amethyst The entire signature is verified, for all inputs at once. It happens like this: The prefix hash of the transaction (without a signature) is written to the hash buffer. For each input i (signature line in the figure): X is calculated. The values of the pairs (Y0, Z0) .. are sequentially calculated.. (Yn, Zn), where n = Nmixins Nabar (pp, X, Yn, Zn, P0 … Pn), where Pj are the public keys of the outputs referenced by this input, is added to the hash buffer. Hs is calculated over all hash buffer data and the result is compared with c0. The signature is considered valid if the equality is observed. Let us estimate the number of operations of multiplying a scalar by a point and calculating the hash Hp. Each calculation of Yj and Zj requires two dot multiplications, plus the calculation of X requires three dot multiplications. The number of pairs Yj, Zj corresponds to the number of mixed outputs Nmixins for each input. Therefore, we have: O(*) = Ninputs * (3 + 4 * Nmixins) In this case, the hash function Hp is used once for each calculation of Zj and once to calculate B for each of the inputs, therefore: O(Hp) = Ninputs * (Nmixins + 1) To visually compare the computational complexity of both algorithms on typical data, we introduce the following metric. Let's add the number of scalar multiplication operations and Hp calculation operations with weights proportional to the characteristic execution time of these operations: O(total) = 130 * O(*) + 15 * O(Hp) Then we compare the relative results for CryptoNote and Byteсoin in percent (Fig.. 4.5.6). Fig. 4.5.6. Computational complexity of Bytecoin Amethyst ring signature verification compared to CryptoNote (no dependency on Ninputs) As you can see, Bytecoin signature verification is a much more time-consuming operation. However, as noted above, in Bytecoin since version 3.4.0 of Amethyst, in order to increase anonymity, the minimum number of mixed outputs is set to 3, so 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 mixed outputs (with a large number it turns out to be less): S = 32 * ((3 + Nmixins) * Ninputs + 1) The computational complexity is higher than in CryptoNote and depends significantly on the number of mixed outputs: O(*) = Ninputs * (3 + 4 * Nmixins) O(Hp) = Ninputs * (Nmixins + 1) 5. Audit Research in CryptoNote by Anton Sokolov A series of essays (1, 2, 3, 4, 5, 6) was published on Medium.com in the fall of 2019 about the problem of auditing in CryptoNote and possible ways to solve it, authored by Anton Sokolov. It theoretically considers several options for modifying the original protocol in such a way as to solve the audit problem for a third party. Consider the last of them as the most optimized. We will abbreviate it as “AS”. Note: for consistency, spend-keys will continue to be denoted by the letters s and S, view-keys by the letters v and V, despite the fact that b, B and a, A are used in the original works, respectively. Formation of outputs A wallet account is represented by a set of not two, as in CryptoNote, but three secret keys {v, s, d}: view-, spend- and audit-keys, respectively. The set of three public keys {V, S, D} represents the public address of this account. Alice, sending money to Bob, acts as follows (Fig.. 5.1). Fig. 5.1. Generating Transaction Outputs in the AS Schema Bob publishes his address, so Alice knows his public keys V, S, and D. Just like in CryptoNote, Alice chooses a random secret transaction key r and computes the public key R = r * G, which writes in the special field extra of the transaction. For each exit, Alice calculates not one, but two stealth addresses P and T. The first is calculated similarly to CryptoNote: P = Hs(r * V) * G + S The second is otherwise: T = Hs(r * D) * D and in practice it will be one of the arguments of the Hs function, similar to CryptoNote (see Section 3). Alice signs and sends the transaction. An outside observer will not be able to associate P and T with Bob's address. Recognizing incoming payments and generating inputs To accept and spend money, Bob acts as follows (Fig.. 5.2). Fig. 5.2. Determining incoming transfers and generating inputs for the transaction that spends them 5. Using his secret view key v, Bob compares the stealth address P of each output with a dot: P' = Hs(v*R)*G+S (this step is similar to CryptoNote) 6. If the equality is true, this means that this output is addressed to Bob. It increases its balance by the value of the nominal value of the output. 7. If it is necessary to transfer the received funds to Carol, Bob, using his secret spend and audit keys s and d, calculates two key images: I and П. The first is similar to CryptoNote: I = x * Hp(P) and additional: t = Hs(d*R)*d Ï = t * Hp(P) Then writes them, the denomination and a link to the corresponding output into the input of his transaction for Carol . eight. Bob then generates transaction outputs for Carol, reduces his balance in proportion to the outputs spent, signs the transaction, and sends. As you can see, here, just like in CryptoNote, a third party – the Auditor – having only the secret view key v, will be able to recognize only 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: 9. For each incoming payment, the Auditor will calculate and store an additional key image Ï in local storage: t = Hs(d*R)*d Ï = t * Hp(P)10. If in the inputs of any of the blockchain transactions the additional key image П matches one of the saved ones, then this will mean that this transaction is Bob's outgoing payment. The auditor will reduce the balance by the face 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 in the blockchain and restore his correct balance. At the same time, the Auditor will not be able to spend the funds, because without the secret spend-key s, he will not be able to calculate the main key image I. Problem solved. Ring signature Using the ideas from this paper, the author managed to reduce the size of the signature compared to CryptoNote: now, for each input, only Nmixins + 1 scalar is stored in the signature (Fig. 5.3). Rice. 5.3. Comparison of the size of the ring signature in the AS scheme and CryptoNote Thus, the size of the signature is almost halved. Consider the computational complexity of its verification. The signature verification scheme is shown in fig. 5.4. Rice. 5.4. AS Ring Signature Verification Scheme This algorithm is very similar in structure to that used in CryptoNote (see fig.. 4.5.4). The verification is carried out separately for each input and consists in the sequential calculation of the values uj, Lj, Rj, cj for all outputs used for mixing in this input. As a result, the cycle from cj must close and the value cn+1 must coincide with c0, in which case the signature is considered valid. The computational complexity of the algorithm is determined by six scalar multiplication operations and one calculation of the Hp hash function per iteration, the number which is the product of Ninputs * Nmixins. Comparison with CryptoNote in terms of data and computational load Address size increases by 50%, because. the address now represents a collection of three public keys: {V, S, D}, and not two {V, S}. Кодированное представление адреса увеличится примерно на столько же: например, стандартный Zano-адрес, содержащий два открытых ключа, занимает 97 символов: ZxD5UBX5PM3RTsEtTRd9ATUFxXyocoQzDRk3baVBahuWQJRK8QHTUT9GQM7jk7GoedK5B2nP4HxSPDpuLHvizpwj2q99bmz7t Аналогичный Zano-адрес, содержащий три открытых ключа будет иметь длину порядка 141 символа: ZxD5UBX5PM3RTsEtTRd9ATUFxXyocoQzDRk3baVBahuWQJRK8QHTUT9GQM7jk7GoedK5B2nP4HxSPDpuLHvizpwjcenhnGbhpJFLk8vkhJywHCcht4d9EKA7CHHav1H6QPpB1cLsTvPfj Размер каждого выхода увеличивается на дополнительный стелс -address T – 32 bytes. The size of each entry is increased by an additional key image Ï – 32 bytes. Ring signature size is smaller than in CryptoNote: S = 32 * (Nmixins + 1) * Ninputs Computational complexity is higher than in CryptoNote: O(*) = Ninputs * 6 * NmixinsO(Hp) = Ninputs * Nmixins 6. Auditing through Constraint on Mixing Outputs Let's consider another way to implement auditing in CryptoNote. Mix_attr exit attribute In the Zano project, which is a successor of CryptoNote, the transaction exit has an additional 8-bit mix_attr attribute, and a kernel rule that restricts the use of exits in mixing, depending on its value. The output structure of CryptoNote and Bytecoin (Fig.. 4.2) we can now complete in this way (Fig. 6.1.). Rice. 6.1. Comparison of the data structure for the outputs of CryptoNote, Zano and Bytecoin Amethyst transactions The core rule that restricts mixing depending on mix_attr is: If mix_attr = 0, then no restrictions. This outlet can be used to mix with other outlets 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 only be spent by mixing others, and the total number of used outputs must not be less than the value of mix_attr. The main feature of this innovation is. 3, which makes it possible to increase untraceability (untraceability of links) by eliminating situations when the output already used in mixing is spent directly by its owner (this is discussed in detail in [19]). However, in the context of this article, we will be interested in. 2, i.e. the situation where mix_attr = 1 and an output marked in this way can only be spent directly. This limitation is illustrated in Fig.. 6.2. Fig. 6.2. Limitation illustration. Above: input #0 only refers to output #0 with mix_attr = 1 (immediate waste) – a valid situation. Bottom: input #1 refers to three outputs: output #2 with mix_attr = 1, and also 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, like output #0. This feature can be used to organize an audit. Auditing with mix_attr = 1 As noted in section 3, if, under the original CryptoNote protocol, Auditor Dan receives the secret key v from Bob, he will be able to recognize incoming transactions, but will not be able to recognize outgoing ones, so an accurate balance calculation is impossible. However, since Dan will have complete information about Bob's unspent outputs (UTXO), he will be able to track the fact that some transaction in its inputs refers to Bob's UTXO.. When using mixing other outputs, Dan will not be able to determine whether a given 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 being 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 be able to see the receipt of funds from Alice and the fact that they are spent when Bob decides to spend them. The scheme of work will look like this (Fig.. 6.3). Fig. 6.3. The auditor uses Bob's private view key v to determine incoming and outgoing transactions. Bob informs Alice of his public address (V, S) and also asks her to set the mix_attr attribute to 1 in all outputs addressed to him (we'll see how this can be done below). implement technically). Bob gives auditor Dan his secret view key v. Alice sends a transaction to Bob using the usual CryptoNote scheme. In the outputs addressed to Bob, she sets mix_attr = 1. Den scans all transactions in the blockchain and, using Bob's secret view key, checks for each output Pi == P'i = Hs(v * R, i) * G + S (where i is the exit sequence number, S is Bob's public spend key). If the equality is true, then this output is addressed to Bob. Dan makes sure mix_attr == 1, adds the given output to the list, and increments the balance by the value of the output. Den also checks all inputs of all transactions, and if one of the inputs refers to Bob's UTXO from the list, then this means that this transaction is Bob's outgoing payment. Due to the mix_attr = 1 constraint, this 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 nominal value of the input. This way Den can calculate the correct balance of Bob's wallet without having 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 the transaction. If Alice does not do this, then the funds will come to Bob, but in the future Den will not be able to unambiguously say whether Bob spent them or not, since any other user will be able to use the data output for mixing. One of the solutions is to introduce addresses of a special type 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 to set mix_attr = 1 for the corresponding outputs. Feature 2. Using addresses of a special type does not oblige Alice to set the desired attribute value for outputs. She can send the funds without doing so, however, this will be immediately revealed to both Bob and auditor Dan. Feature 3. In this scheme, the ability to audit is achieved at the cost of the ultimate reduction in untraceability (untraceability of links). This is not a particular problem if the possibility of audit is provided to an unlimited circle of persons. For example, a charitable foundation can publish a donation address along with a secret view key, so that anyone can act as an auditor and calculate the current balance of their wallet. It is important that the anonymity of incoming transfers remains standard for CryptoNote (you can use a large number of Nmixins). However, the anonymity of outgoing payments will be limited by the inability to mix in arbitrary outputs. It is worth noting that in the case where the audit opportunity is given 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 the ease of implementation and the absence of additional computational and data burden. 7. Conclusion We've looked at three options for adding auditability to the CryptoNote protocol: Bytecoin Amethyst, Anton Sokolov's theoretical AS schema, and using mix_attr (let's call it MA). The relative change in the size of the ring signature for all options except Bytecoin (BCN) does not depend on Ninputs, so consider Ninputs = 1 (minimum) and Ninputs = 3 (Fig.. 7.1). Fig. 7.1. Comparison of ring signature sizes for Ninputs = 1 and Ninputs= 3 for all considered options Note. Ninputs is the number of transaction inputs, Nmixins is the number of outputs associated with each transaction input. If Nmixins > 1, then this means that in order to increase untraceability, each input refers to more than one output of some other transaction, and it cannot be established which of them is real. The AS scheme shows the best result, giving a reduction in the size of the ring signature in a wide range of the number of mixed outputs (Nmixins). Bytecoin also performs well when Nmixins >= 3 (as already noted, Bytecoin Amethyst introduced a limit of 3 minimum Nmixins to improve untraceability). The MA scheme does not offer any improvement in terms of the size of the ring signature. Let us now compare the complexity of the ring signature verification procedure. To do this, we will use the metric mentioned above, namely, we will take the sum of the operations of the scalar product and the calculation of the hash function Hp with weights proportional to their execution time on a typical modern processor: O(total) = 130 * O(*) + 15 * O( Hp) We have the following picture (Fig.. 7.2). Fig. 7.2. Comparison of increase in computational complexity of ring signature verification (Ninputs = 1) With direct spending (Nmixins = 1), AS and Bytecoin schemes require significantly more computation to verify the signature. When mixing outputs (Nmixins > 1), the Bytecoin Amethyst scheme seems to be preferable to AS, but the last considered MA option remains unbeatable. Let's sum up the final result, taking into account such factors as an increase in the size of the address, inputs and outputs of transactions (Fig.. 7.3). Fig. 7.3. Comparison of all considered Bytecoin schemes keeps the length of the address convenient for the end user, while Anton Sokolov's scheme increases it by 50%. This does not directly affect the size of the blockchain (although the sender's address in encrypted form can be transmitted in extra transactions if the latter is desired, for example) and computational complexity, but it does not significantly affect usability.. In the MA scheme, the address size remains at 64 bytes, but a way is needed to distinguish between auditable addresses and normal addresses. Bytecoin and AS auditing implementations add one dot (32 bytes) to each transaction output, however, the input size remains the same for Bytecoin only. It is also worth noting the fact that the Bytecoin Amethyst scheme has been implemented in code for a long time and, judging by the lack of reports of problems since its implementation, has been well tested in practice. However, its public description in a strict form could not be found, therefore, there are no formal proofs of its correctness yet. The AS scheme, on the other hand, is strictly described and proposed for discussion in the crypto community. The MA scheme does not have a strictly described formal proof, however, due to its extreme simplicity, it seems redundant.