Three ways to audit wallets in CryptoNote

Auditing wallets
refers to the ability for a third party (“auditor”) to see
transactions of that wallet and calculate its correct actual balance without

The article discusses
different ways to make this possible in the cryptocurrency protocol
CryptoNote 2.0, where auditing
is only partially implemented: with a tracking key you can recognize
incoming transactions can be recognized, but a full set of keys is needed to recognize outgoing transactions.

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

What is CryptoNote?

In a strange way, it is.
most people interested in blockchain and cryptocurrencies have not heard anything about
CryptoNote, despite the fact that the technology has been the basis for over
more than 300 forks, the most famous of which was Monero.

In 2014, the cryptocurrency environment
cryptocurrency environment there were mentions of a project called Bytecoin. The project was not a fork of Bitcoin or
It was not a fork of Bitcoin or any other open source project, and it had a completely new code base, which was extremely unusual at the time
unusual for the time. Its basic concept was to implement
of privacy technology, which was called CryptoNote. Privacy was ensured by
Privacy was ensured by two mechanisms: stealth addresses and swapping inputs using
The ring signature (also referred to at the time as the “blockchain mixer”). Since
Zcash existed only in theory at the time, the technology proved to be very
competitive and resonated strongly in the cryptocurrency
The cryptocurrency community.

It wasn’t long before a group of
of enthusiasts who took an interest in one of the first forks of the technology and then
then took the lead in that fork, and through their energetic actions
was able to attract the most attention to the technology among both the community and
among investors. This fork was called BitMonero, but pretty soon it was renamed to Monero.

The two projects subsequently
– Bytecoin and Monero – went technologically different ways: if Bytecoin
remained a closed, anonymous project, but Monero became a large
community-driven project with very many participants and developers.
Nevertheless, they are both an evolution of CryptoNote technology.

The concept of audit and its
applications

In contrast to the
classic “pseudonymous” blockchain like Bitcoin, in which anyone
scanning the blockchain can trivially calculate the balances of any address, in
private blockchain, in particular CryptoNote, this task is hardly feasible
without additional knowledge. First, thanks to stealth-address technology, the
The blockchain does not mention any addresses at all (this property is usually
anonymity). Second, due to the fact that due to the
ring signature, the input of a transaction does not point to one particular output
of the parent transaction, but points to many possible outputs, it is not possible to trace
The transaction input does not point to a single specific output of the parent transaction, but instead points to a multitude of plausible outputs (this property is called untraceability).
private cryptocurrency, these properties are necessary, but there are
special cases where the wallet owner may want to disclose to a third party
their transaction history and current wallet balance, while ensuring for themselves
that it is impossible for a third party to spend the money. This may be necessary,
For example, for exchanges to interact with regulators or inspectors
authorities. It may also be important for various foundations that
would like to be able to be transparent to a certain group of individuals or
be fully public.

Speaking formally, by
wallet auditing refers to the ability for a third party
(“auditor”) to see that wallet’s transactions and calculate its
the correct actual balance without delegating the right to spend the funds. В
The original version of CryptoNote only partially implemented auditing: with the
The original version of CryptoNote auditing was only partially implemented: a tracking key can recognize incoming transactions, but a full set of keys is needed to recognize outgoing transactions.

About the author and purpose
About the author

The author of this article is one of the main developers of the Zano project, based on
based on CryptoNote, which has evolved over several years by the same people who wrote the original code for it.
original technology code was written.

The team is now
The team is considering adding wallet auditing to the project and is
researching this topic in order to choose the best option. With the results
of some of these studies the author wants to introduce to readers.

2. Basic information about elliptic curve cryptography

The CrypoNote protocol
uses the elliptic curve from the public-key digital signature scheme
ed25519.

Let’s recall the basic parameters of this curve and give additional definitions.

The large prime number q = 2255 – 19 is fixed.

1. All operations occur in integers in the finite field Fq of deductions modulo
   q.
2. An elliptic curve over the 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
   number).
   The fact of its symmetry with respect to x and y is important.<br

3. An operation is geometrically defined over the set of points of a curve
   is geometrically defined an operation which for any two points gives a third one: F(A, B) = C,
   conventionally called “addition”, and a neutral element is given as a point,
   lying in infinity (this is discussed in detail here). This operation does not lead beyond the
   It is associative, commutative, and has an
   Inverse element, so that 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
   (кофактор) и l=2252+27742317777372353535851937790883648493.
4. Each point of the curve is given by its coordinates
   (x, y). Since the coordinates are connected by a curve equation, this representation
   is redundant, and therefore in the implementation of cryptographic functions to save
   only the y-coordinate, encoded as a 256-bit number, is used.
   The x-coordinate, in accordance with the symmetry of the curve (cf.. equation),
   can be only one of two options, the choice of which is coded as
   the highest bit of the number representing the y-coordinate.
5. The special point of the curve G = (x,
   -4/5). The point is given by the y-coordinate, from two possible variants x
   is chosen the positive one.
6. Addition (see. п. 3) points G with itself n times
   defines an operation of multiplication by an integer which forms a closed
   multiplicative group G whose order is less than E(Fq):

   #G< #E(Fq), with #G=l=2252+2774242317777372353535851937790883648493.

7. Open key X is a point of an elliptic curve,
   belonging to group G: X ∈ G
8. The secret key x, or the scalar corresponding
   public key X is such an integer that:

   X = x * G, x ∈ [1; l-1]

   .
   A secret key, just as a public key (cf.. above), is encoded as a 256-bit
   number.

9. The basic hash function H is defined (in the code and other sources
   Other sources refer to it as cn_fast_hash). It calculates a 32-byte hash on an arbitrary
   dataset:

   H : {0, 1} * → [0,2256-1]

10. The hash function Hs (s stands for scalar) on arbitrary data
    produces a number which is a scalar, i.e.. with a valid secret key:

    Hs : {0,1} * → [1; l-1]

    Hs can be implemented
    trivially through H:

    Hs(x)= H(x) + 1 mod l

11. The hash function Hp (p stands for point of curve) on
    arbitrary data produces an element of group G, i.e., a valid public
    key:

    Hp : {0,1} * → G

    The implementation of this hash function is somewhat complicated because
    First, not every set of 256 bits can be decoded into a point
    of an elliptic curve (cf.. п. 4), and secondly, not every point of the curve
    belongs to group G (cf.. п. 6).
    One trivial way to implement Hp is to sequentially hash
    H(H(…H(x)…)) data) until the result can be
    decode to an XG point.
    CryptoNote uses a more complex and efficient approach,
    implemented in the form of the function ge_fromfe_frombytes_vartime, which is discussed in detail in this paper.
    We define a function that deterministically converts arbitrary 256 bits into
    element of group G as:

    to_point :[0,2256-1] → G

    .
    In CryptoNote, the hash function Hp is implemented like this

    Hp(x) = to_point( H(x) )

3. Funds accounting and balance calculation in CryptoNote 2.0

We’ll look back at how
Sending funds and calculating balance in the original version of the protocol.

Alice sends money to
Bob, generates the outputs of his transaction as follows.

1. Bob has a pair of private keys (v, s). It
   calculates his address as a pair of corresponding public keys (V, S) and
   publishes it or sends it to Alice.
2. Alice chooses a random secret key
   transaction r and computes the public key R = r * G, which she writes in
   a special field of the extra transaction.
3. For each exit, Alice computes the stealth address
   (one-time destination key):

   Pi = Hs(r * V, i) * G + S, where i is
   is the sequence number of the output.

4. Alice signs and sends the transaction.

Secondary Observer,
analyzing the stealth Pi addresses, cannot tell whether a particular output is intended
particular output to Bob, and can’t even tell if the different outputs are intended
outputs with keys Pi and Pj to the same recipient.

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

.

5. Using his secret key v, Bob calculates for each output P’i = Hs(v * R, i) * G + S
   (where i is the sequence number of the output, S is Bob’s public spend-key).

If P’i == Pi, it 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 nominal value of this output.

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

6. Bob, using his secret keys (v, s), computes the private key xi = Hs(v * R, i) + s to stealth address
   Pi, that is, Pi = xi * G.

8. Bob calculates the key image: I = xi * Hp(Pi) and writes it, the nominal and the reference to
   the corresponding output to the input of his transaction for Carol.
   It should be noted that, first, only the owner of the secret spend-key can calculate the key image.
   the owner of the secret spend-key s (the correctness of this will be certified
   ring signature), and secondly a third party will not be able to bind the key image I
   and the corresponding Pi stealth address.<br

10. Bob reduces his wallet balance by the denomination of the output used in clause.
    6.

12. Bob generates outputs in the transaction for Carol according to clause. 2-3.
    Then it signs the transaction and sends it.

If we assume that
Bob has lost all of his transaction history, but still owns his
secret keys (v, s), then he can retrieve his transaction history and
calculate his current balance as follows.

10. Bob scans the entire blockchain and analyzes all transactions for
    for outputs addressed to him (cf.. п. 5).
    

12. When such a Pi exit is found, Bob increases his wallet balance
    by the value of the face value.
    Then, using his secret spend-key s, he calculates the corresponding
    secret output key xi (n. 6) и key image I (п. 7). After that
    writes the key image, Pi and other payment data to the table.<br

13. If on further scanning of the blockchain Bob discovers in the input of some
    transaction has a key image in its input, it means that the transaction
    transaction was once generated by Bob.. Therefore, he will reduce the balance of his
    his wallet by the amount of his entry value.

Doing so,
Bob will restore his current wallet balance.

Please note that
If third-party auditor Dan gets the secret key v from Bob, he will be able to
recognize Bob’s incoming transactions on the blockchain, but without having the secret
s secret key, he will not be able to recognize Bob’s outgoing transactions, and hence
calculate the correct balance. As will be shown below, in the case of a direct
Bob’s spending of the output without the swaps, Dan will be able to identify such a transaction as
Bob’s outgoing transfer, but in the general case this cannot be done.

So, in order to
Bob’s wallet balance calculation requires knowing both secret keys (v, s).

If Bob were to give
Auditor to Dan both of his secret keys (v, s), this would be tantamount to handing over
the funds themselves, since Dan, possessing the s, would be able to spend them. Therefore, a full-fledged
audit of wallets within the original CryptoNote 2.0 protocol is not possible.

In the following sections, we will
we’ll look at modifications to the protocol that have this capability.

We should note that it makes sense to keep the secret
It makes sense to keep the transaction key r Alice (which some protocol implementations do).
protocol implementations). Anyone who knows r for some transaction can
check whether output i of that transaction belongs to the given address (V, S),
simply by repeating the calculations in step 3:

P’i = Hs(r * V, i) * G + S

and comparing the result with
Pi.

This fact Alice can,
For example, she can use it to prove that it was Bob who transferred the money.

This is a fact Alice can use to prove she transferred the money to Bob.

Calculate the target address
(V, S) from the output, even if you know r, you can’t.

4. Option A: Bytecoin Auditable Coins

Bytecoin was the first and only implementation of the CryptoNote protocol
Bytecoin was the first and only implementation of CryptoNote,
Therefore, it had all of the features and limitations discussed in the
previous section.

February 7, 2018
developers released version 3.4.0 of Amethyst, which contains a number of improvements and
CryptoNote changes, which we will now take a look at.

In the context of the topic of this
the most interesting change in this article is the ability for regular wallets
The most interesting change within the scope of this article has been the creation of the auditable wallet (AW), which has two
features:

.
1. AW can’t spend money from the primary
2. The AW cannot spend funds from the primary wallet

.

3. The balance of the AW is always the same as the primary wallet
   wallet. It is impossible to change the balance of the main wallet without
   the balance of the AW.

However, this functionality
only newer versions of wallet addresses have this functionality, so
so-called amethyst addresses. Existing addresses and accounts
backward compatibility is ensured, they are now called legacy addresses.
The implementation of the new functionality became possible only in transactions of the new
version, because the developers have changed the format of the outputs, so in the Bytecoin network
at the moment there are circulating both transactions of old format, and new. The new format transactions
also support two types of addresses: amethyst and legacy, so we end up with
we end up with three options for cryptographic schemes:

1. tx.version.
   < amethyst, legacy address;
2. tx.version
   >= amethyst, legacy address;
3. tx.version
   >= amethyst, amethyst address;

.
Let’s take a closer look at them.

4.1. tx.version <
amethyst, legacy address

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

The wallet account
is represented by the secret key s and the hash vs. The secret view-key v is deterministically
is generated as a function of vs.

The secret key r
of a transaction is no longer chosen at random, but is computed using vs:

r = Hs(ht, vs), where ht = H(tx.inputs, tx.version)

This obviates the need to
The need to keep r’s secret keys in local storage for future use,
because for any of its transactions ever sent to the blockchain, such
key can be computed using vs.

Wallet balance
is calculated in the same way as the original CryptoNote (see. section 3), which means that in order to
the accounting of outgoing payments requires a secret spend-key s.

In the event that all of the addresses in
Wallet’s local storage will store all of the addresses that
ever made a transfer, it is possible to calculate the
the correct balance without using the secret spend key as follows:

.
1. Alice scans transactions in the blockchain and keeps
   accounting for incoming payments using the secret view key v, as described in
   described in section 3 and increments the balance.

2. Also for each exit 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

.

3. If P’i = Pi, then this output is an outgoing payment
   Alice to (V, S) and it reduces the balance.

That’s how Alice calculates
balance using only vs and v.

Obviously, this method

It’s obvious that this method is unreliable and impractical, because if the specified local
address that the transfer was actually made to, will cause the balance to
An inflated balance. Therefore, it is of more theoretical interest.

4.2. tx.version >=
amethyst

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

Now every output,
has an additional public key, Pi, in addition to the amount and the public key
key Qi (referred to in the code as encrypted_secret) and an extra byte that contains the encrypted address type, amethyst or
legacy (referred to in the code as encrypted_address_type). These structures are shown schematically in Fig.. 4.2.

.

This increases the size of each output by 33 bytes.

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

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

where:

oi = H(ht, vs, i) (denoted in
code as output_seed),

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

4.3. tx.version >=
amethyst, legacy address

The wallet account is also
is represented by the secret key s and the hash vs, which deterministically
the secret view-key v is generated.

Alice, by sending money to
Bob to his address (V, S) forms the outputs of his transaction as follows:

1. Calculates ht = H(tx.inputs, tx.version), then for each
   output i:
2. Di = Hs(ht, vs, i) * G (referred to in the code as output_shared_secret)
3. Pi = S + Hs(Di, ht, i) * G
4. Qi = Hs(ht, vs, i) * V (with Qi = v * Di, but the view-key v of the recipient
   is unknown)
5. Pair (Pi, Qi) – open keys of output i.

To accept money,
Bob analyzes all transactions as follows.

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 that output is for him
and he increases his wallet balance by the corresponding denomination.

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

10. Using its secret keys v and s, calculates the secret part of Pi:
Di = v-1 * Qi
xi = s + Hs(Di, ht, i), and it is easy to see that Pi = xi * G (cf.. п. 3)

11. Bob calculates the key image: I = xi * Hp(Pi) and writes it, the denomination, and the reference to
the corresponding output to the input of his transaction for Carol.

12.Bob reduces his wallet balance by the denomination of the output used.

13. Bob generates outputs in the transaction for Carol according to p.p.. 1-5.
Then signs the transaction and sends.

The feature of the scheme, as opposed to CryptoNote, is that anyone who
of this scheme, as opposed to CryptoNote, is that anyone who gets their
its secret hash vs, will be able to calculate the recipient’s address (V, S) for any
Alice’s transaction:

14. Di = Hs(ht, vs, i) * G

15. S = Pi – Hs(Di, ht, i) * G

16. V = Hs(ht, vs, i)-1 * Qi

The problem in
here is the problem of determining which transactions Alice has generated and
sent by Alice. Without this information in the paragraph. 14-16 for arbitrary transactions
will produce arbitrary useless data, indistinguishable from the real
addresses (V, S). The encrypted_address_type encoding algorithm may be of some help here.
encrypted_address_type, because for Alice transactions this field after
decoding will have only valid values {0, 1}. But, unfortunately,
the permissible values can also turn out arbitrarily, and such a case cannot be
will not be distinguishable.

Since, in this scheme, the
the calculation of the key image also requires knowledge of the secret spend-key s, the problem of
of auditing, that is, figuring out the exact balance of a wallet without delegating the rights to spend

The problem of auditing, that is, figuring out the exact balance of a wallet without delegating spending, remains unsolved.

4.4. tx.version >= amethyst, amethyst address

constant H

This
cryptographic scheme requires a new constant, the H point, an element
of group G, and the order of point H is unknown. In other words, it is
Some fixed public key, the secret part of which is guaranteed to be
is unknown and the probability of finding it is negligible:

H = y * G, where y
unknown number.

For example, you could set H
as suggested here:

H = Hp(G) = to_point(
cn_fast_hash(G) )

The Bytecoin developers don’t
calculate the constant, but rather 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},

{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},

{23443568, -5110398, -8776029,
-4345135, 6889568, -14710814, 7474843, 3279062, 14550766, -7453428}}};

However, a search of this
of this numeric sequence revealed,
that they use the same constant as in Monero for RingCT, the method
of which and its rationale are discussed here.

Since H belongs to the group
of group G, we can say that H also gives rise to group G, just as
and the base point of G.

This means that ∀ x ∈ [1,p – 1], x *H ∈ G 

Multiple
unlinkable addresses

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

The scheme in question
allows an unlimited number of public addresses to be generated on the same set of secret keys.
Public Addresses. That said:

.
1. addresses are generated deterministically from
   initial set of secrets;

.

2. these addresses cannot be linked,
   i.e.. an outside observer will not be able to deduce that they belong to the same

.

3. checking incoming transactions and balance accounting for N
   multiple addresses will be computationally easier 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 scheme. However,
based on the hash vs is now deterministically generated not only by the secret view-key v, but also by
an additional secret audit key a.

The process for generating the i-th

The process for generating the i-th address is as follows

.
1. Calculates δ = Hs(A + s * H, i), Δ = δ * G
2. S = A + s * H + Δ
3. V = v *
   S = v * (A + s * H + Δ) = v * (A + s * H) + δ * V
4. the pair (V, S) = (v * S, S) is the i-th public
   address of the given account.

Note that in order to calculate
it is sufficient to know the following values:

• A
• V
• s * H
• v * (A + s * H)

.

The values of s * H and v * (A
+ s * H) are precalculated when you create the account and are considered
safe in the sense that you can’t calculate s or v if you know them.

The generated addresses
are stored locally in a container optimized for searching by S.

The generated addresses are stored locally.

Generating outputs
When sending funds

Alice, when sending money to
Bob to his address (V, S) forms the outputs of his transaction as follows
(Fig.. 4.4.3).

Calculates ht = H(tx.inputs, tx.version), then for each
output i:

1. Pi = Hs( Hp(ht, vs, i), ht, i )-1 * S
2. Qi = Hs( Hp(ht, vs, i), ht, i )-1 * V + Hp(ht, vs, i)
3. Pair (Pi, Qi) is the open keys of output i.

Accounting for incoming payments

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

.

1. For each output i, using the secret
   view-key v, Bob calculates:

   K = Hp(ht, vs, i) = Qi – v * Pi (output_shared_secret in code)

2. S’ = Hs(K, ht, i) * Pi
3. Then tries to find S’ in the list of its
   addresses in its list. If it does, it means that the output in question is transferring money
   Bob. It increases the balance for the corresponding address.

This means that in order to
In order to correctly account for incoming payments in this scheme, in addition to a list of
addresses or keys to generate them, you need to know the secret view-key v.

Generating outgoing payments

To spend the output i,
of which Bob is the recipient, and send the coins to Carol, he proceeds as follows
as follows.

1. K = Hp(ht, vs, i) = Qi – v * Pi (output_shared_secret in code)
2. xi = Hs(K, ht, i)-1 * (a + δ)
3. Xi = xi * G + Hs(K, ht, i)-1 * s * H
4. Calculates the key
   image I = xi * Hp(Xi)

.

5. Bob reduces the balance related to its address S
   = Hs(K, ht, i) * Pi by the value of the nominal
   of the corresponding output.
6. Bob generates transaction outputs, signs it and
   sends.

We can see that in order to
to compute the key image not only requires knowledge of the secret view-key v, but also
a.

The important feature of
of this scheme is the ability to calculate the key image (and hence the ability to
the key image (and therefore the accounting of their outgoing payments, therefore the balance calculation) without using the secret spend key s

Disclosing the recipients’ addresses
recipients for auditing

In the same way as the previous one,
This cryptographic scheme makes it possible to retrieve recipient addresses from transaction outputs

This works in the following way

Suppose that Alice
passed vs and s * H to Carol. Then Carole:

.
1. Restore the secret keys v and a, restore
   Alice’s list of addresses.
2. It 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.

3. If found, Carol will increase the balance
   of the corresponding address and, using a and v, compute the key image (see

4. Carol.. above)
   and save it locally.

5. If among the transaction inputs there is a key image
   Alice, it will mean that this transaction is an outgoing payment
   Alice’s. 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 Alice address by the value of the nominal
   of the input.

This way, disclosing
part of the account information, you can give the third party different levels of
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 perform an audit,
i.e.. calculate the balance for their addresses, without disclosing the recipients’ addresses:

• a
• v
• s * H

.

To perform an audit,
i.e.. calculate the balance of their addresses, and in doing so reveal the addresses of
recipients:

• vs
• s * H

.

4.5. Signature Comparison
of CryptoNote and Bytecoin Amethyst transactions

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 address type is transmitted. That’s a total of 33
bytes per output.

In CryptoNote
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 to the signature
a pair of scalars (r,c) with a total size of 64 bytes. (An input can refer to more than one
outputs, only one of which is real, and the others serve to anonymize
translation.)

So if there are
transaction Ninputs inputs, each referring to Nmixins outputs, then the total
signature size in bytes can be expressed as:

S = 32 * 2 * Nmixins * Ninputs

The minimum size
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 associated data structure
is more complex (Fig.. 4.5.1).

.

For each input
transaction is signed with a point, two scalars and Nmixins of scalars. To the entire
signature is also added another scalar. The total size of the signature in bytes
can be expressed as:

S = 32 * ((3 + Nmixins) * Ninputs + 1)

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

You can see that both functions
grow in proportion to the product of Nmixins * Ninputs

In order to compare the difference in
of the transaction signature sizes more clearly, let’s calculate them for the most
Nmixins and Ninputs and compile a table (fig.. 4.5.2).

.

As you can easily see,
when there is no output swapping and there is a direct waste of
funds (Nmixins = 1), or when one output is swapped (Nmixins = 2), the signature size
Bytecoin is larger than CryptoNote up to 150%.

When mixing two
outputs (Nmixins = 3), the sizes of signatures in both schemes are almost the same.

In further
the size of the signature of Bytecoin appears to be smaller as the number of outputs increases.
smaller.

It is worth noting that
Bytecoin developers with the release of version 3.4.0 Amethyst in order to increase
anonymity, they set the minimum number of outputs to be switched as 3. Under such conditions, the Bytecoin signature will
have a smaller size.

The laboriousness of verifying
signature

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

The laboriousness of signature verification
of signature verification for CryptoNote and Bytecoin could easily be compared practically,
by simply writing a test that generates and then verifies a large number of signatures with
Nmixins and Ninputs given, however, since the following article will discuss those not yet implemented
in practice, but only schemes proposed in theory, it will be logical to estimate the labor-intensiveness of
of these schemes should be estimated empirically, by the number of cryptographic

.

The CryptoNote and Bytecoin
uses several basic primitives (cf.. section 2). The table in Fig.
4.5.3. The typical execution time of the most frequently used
primitives on a modern middle-end computer with a Core i5-6500 processor (for comparison, the original source code compiled by Microsoft
for comparison, we used the original source code compiled in Microsoft
Visual Studio 2017 with all possible speed optimizations).

The results obtained
from Bytecoin and CryptoNote tests agree well with each other. It is easy to see,
that the greatest contribution will come from the operation of multiplying a scalar by a number, and, to a lesser extent
to a lesser extent, the procedure of computing the hash function Hp, while the operations of
of adding two points and calculating the hash function Hs will not significantly
do not significantly affect the complexity.

See the CryptoNote
The CryptoNote ring signature verification procedure (fig.. 4.5.4, the signature generation procedure
is covered in detail in the White Paper and will not be reviewed here
The procedure for generating a signature is covered in detail in the White Book.

As mentioned above, in
CryptoNote signs each input of a transaction separately, respectively, and
Each input is also checked separately. Therefore, the checker for each input
transaction checks the corresponding line (in the figure) of the signature as follows
as follows.

1. For each pair of values rj and cj, using key-image input I and
   the public key Pj
   of the next output to which this input refers, the values are computed:

   Lj = rj * G + cj * Pj
   Rj = rj * Hp(Pj) + cj * I

   (with index j running a value from 0 to Nmixins)

2. Calculates the sum c of all cj.
3. Calculates 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 the signature).
4. The equality of c` = c. If it
   is fulfilled, the ring signature is considered valid.

We 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 meshed outputs
Nmixins for each input. Therefore we have:

O(*) = Ninputs * 4 * Nmixins

The hash function Hp is used once
for each calculation of Rj, hence:

O(Hp) = Ninputs * Nmixins

Now let’s take a look at
The Bytecoin Amethyst ring signature verification algorithm (Fig.. 4.5.5).

.

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

1. The prefix hash is written to the hash buffer
   of the transaction (without the signature).
2. For each input i (signature string in the figure):
.
1. Calculates X.
2. The values of pairs (Y0, Z0) are sequentially calculated .. (Yn, Zn), where n = Nmixins
3. The set (pp, X, Yn, Zn, P0 .. Pn), where Pj is the public keys of the outputs referenced by this input, is added to the
   hash buffer.

.

.

3. Calculates Hs on all hash buffer data and compares the result with the value of c0.
   .
   The signature is considered valid if the equality is met.

We 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
scalar multiplications, plus calculating X requires three scalar multiplications. The number of
Yj, Zj pairs corresponds to the number of Nmixins outputs for each input.
Therefore we have:

O(*) = Ninputs * (3 + 4 * Nmixins)

The hash function Hp is used once
for each computation of Zj and once to compute B for each
of the inputs, hence:

O(Hp) = Ninputs * (Nmixins + 1)

In order to clearly compare
the computational complexity of both algorithms on standard data, we introduce the following
metric. Let us add the number of scalar multiplication operations and Hp calculation operations with weights
proportional to the characteristic time of these operations:

O(total) = 130 * O(*) + 15 * O(Hp)

Then let’s compare
the relative results for CryptoNote and Vutecoin as a percentage (Fig.. 4.5.6).

.

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

However, as already
noted above, Bytecoin since version 3.4.0 of Amethyst has set the minimum number of
anonymity is set to have a minimum number of swiped outputs of 3, so the worst practical value will not
will not exceed 25% (in theory).

Summarize:

.
1. The size of each output is increased by the public
   Q – 32 bytes.
2. The size of the ring signature varies vs.
   size of the CryptoNote signature depending on the number of meshed outputs
   (A larger number is smaller):

   S = 32 * ((3 + Nmixins) * Ninputs + 1)

3. Computational complexity is higher than in CryptoNote and
   depends a lot on the number of outputs that can be substituted:

   O(*) = Ninputs * (3 + 4 * Nmixins)
   O(Hp) = Ninputs * (Nmixins + 1)

5. Audit research in CryptoNote by Anton Sokolov

In the fall of 2019, Medium.com published a series of essays (1,
2, 3, 4, 5, 6) on the problem of auditing in CryptoNote and possible ways to
of its solution by Anton Sokolov. From a theoretical point of view
Several options for modifying the original protocol in such a way
from a theoretical perspective to solve the problem of auditing for a third party.

See the last of these as the most optimized one.
We’ll refer to it briefly as “AS”.

Note: For the sake of consistency
For the sake of consistency, spend-keys will continue to be referred to by the letters s and S,
view-keys will be denoted by the letters v and V, even though the original works
are b, B and a, A, respectively.

Shaping outputs

The wallet account
is represented by a set of three secret keys {v, s,
d}: view-, spend- and audit-keys, respectively.

The aggregate of the three
{V, S, D} public keys represent the public address of this account.

Alice, when she sends money
to the bean, does the following (fig.. 5.1).

.

1. Bob publishes his address, so Alice
   knows his public keys V, S and D.

2. In the same way as in CryptoNote, Alice chooses
   random transaction secret key r and calculates the public key R = r * G,
   which she writes in the special field of the extra transaction.

3. 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 one is calculated differently:

   T = Hs(r * D) * D

   The serial number of the output in the original paper is not used here,
   but it is reasonable to suppose that this is done for simplification, and in practice
   it will be one of the arguments of the function Hs by analogy with CryptoNote (see Section 3).
   (see Section 3).

4. Alice signs and sends the transaction.

The other observer will not
be able to associate P and T with Bob’s address.
Recognizing incoming payments and generating inputs

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

5.
Using his secret view-key v, Bob stealth address P of each output
compares it to a point:
P’ = Hs(v*R)*G+S
(this step is similar to CryptoNote)

6.
If the equality is met, it means that this output
is addressed to Bob. It increases its balance by the value of the output rating.

7.
When it is necessary to transfer the funds received 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 the reference to the corresponding output to the input of its
transaction for Carol.

8.
Bob then generates transaction outputs for Carol, reduces his balance
proportional to the spent outputs, signs the transaction, and sends it off.

As you can see, it’s the same here,
as in CryptoNote, the third party, the Auditor, with only the secret
view key v, will only be able to recognize incoming translations.

Audit

If the Auditor
also has the secret audit key d, he will be able to recognize Bob’s outgoing
Bob’s payments and calculate his balance as follows:

9.
For each incoming payment, the Auditor will calculate and store
additional key image Ï in the local storage:
t = Hs(d*R)*d
Ï = t * Hp(P)

10.
If in the inputs of any of the blockchain transactions an additional key image
Ï coincides with one of the stored ones, it will mean that this transaction
is an outgoing payment of Bob’s. The auditor will reduce the balance by the nominal
of the corresponding input.

In this way, the Auditor,
with the key set {v, S, d} will be able to recognize Bob’s incoming and
Bob’s outgoing transfers 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, it will not
will not be able to calculate the main key image I.

The problem is solved.

Ring Signature

In applying the ideas in this work, the author has managed to reduce the size of the
of the signature compared to CryptoNote: now, for every input the signature stores
only Nmixins + 1 scalar (fig.. 5.3).

.

This way, the size of the

So the size of the signature is almost halved.

See
The computational complexity of its verification. The scheme of signature verification is shown in
Figure 5.4.

.

.

This algorithm is very
similar in structure to the one used in CryptoNote (see Fig. 4.5.4). Checking
is performed separately for each input, and consists in the sequential
calculation of values uj, Lj, Rj, cj for all outputs used for substitution in this input. В
As a result, the loop of cj must close and the value of cn+1 must coincide with c0, in which case the signature
is considered valid.

The computational complexity of the
of the algorithm is determined by six scalar multiplication operations and one
calculation of the hash function Hp per iteration, which number is the product of Ninputs * Nmixins.

Comparison with CryptoNote
In terms of data and computational load

.
1. The size of the address increases by 50%, because. address
   now represents the set of three public keys: {V, S, D} instead of
   two {V, S}.
   The coded representation of the address will increase by about the same amount:
   For example, a standard Zano address containing two public keys takes
   97 characters:
   ZxD5UBX5PM3RRTsEtTRd9ATUFxXyocoQzDRk3baVBahuWQJRK8QHTUT9GQM7jk7GoedK5B2
   nP4HxSPDpuLvizpwj2q99bmz7t
   A similar Zano-address containing three public keys would have a length of
   on the order of 141 characters:
   ZxD5UBX5PM3RTsEtTRd9ATUFxXyocoQzDRk3baVBahuWQJRK8QHTUT9GQM7jk7GoedK5B2
   nP4HxSPDpuLvizpwjcenhnGbhpJk8vkhJyHCt4d9EKA7CHHav1H6QpB1cLsTvPfj
2. The size of each output is increased by
   additional stealth address T – 32 bytes.
3. The size of each input is incremented by an additional
   key image Ï – 32 bytes.
4. The size of the ring signature is smaller than in
   CryptoNote:

   S = 32 * (Nmixins + 1) * Ninputs

5. The computational complexity is higher than in CryptoNote:

   O(*) = Ninputs * 6 * Nmixins

   O(Hp) = Ninputs * Nmixins

6. Auditing through restriction on swept outputs

Let’s take a look at another
another way to implement auditing in CryptoNote.

Mix_attr output attribute

In the Zano,
the CryptoNote successor project, the transaction output now has an additional
mix_attr attribute of size 8 bits, and a kernel rule that limits the use of
outputs in the mixattr, depending on its value.

The structure of the outputs
CryptoNote and Bytecoin (fig.. 4.2) we can now complete it this way (Fig.
6.1.).

.

The kernel rule,
restricting mixing depending on mix_attr is as follows:

.
1. If mix_attr = 0, then no restriction. This
   This output can be used to mix with other outputs in any combination of
   combinations. This is the default value.

.

2. If mix_attr = 1, then this output can be
   directly, without mixing, and cannot be used to mix other outputs.
   used to mix with other outputs.
3. If mix_attr = 1, then this output can only be spent directly without mixing.
4. If mix_attr ≥ 2, then this output can be
   only when mixing other outputs, and the total number of
   outputs used must not be less than the value of mix_attr.

The main feature
of this innovation is the n. 3, which allows increasing untraceability
(untraceability of connections) by eliminating situations where an output already used
in the substitution is spent directly by its owner (this is discussed in detail in [19]).
discussed in detail in [19]).

But in the context of
of this article, we will be interested in the n. 2, i.e. the situation when mix_attr =
1 and the output marked in this way can only be spent
directly. This limitation is illustrated in Fig.. 6.2.

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

This feature can be

This feature can be used to set up an audit.

Auditing with
mix_attr = 1

As noted in
Section 3, if, as part of the original CryptoNote protocol, Auditor Dan receives
the secret key v from Bob, he would be able to recognize incoming transactions, but not
be able to recognize outgoing ones, so an accurate balance calculation is not possible.

However, since
Dan will have complete information about Bob’s unspent outputs (UTXOs), then
he will be able to track the fact that some transaction in its inputs refers to
to Bob’s UTXO.. If you use a swap of other outputs, Dan will not be able to
determine if it is Bob’s output that the transaction is spending, which is
is achieved through the use of a circular signature. However, if
there is no underwriting and Bob’s UTXO is spent directly, then Auditor Dan can
be confident that the transaction in question is Bob’s outgoing payment. And that’s
is the idea behind this scheme.

Let’s say that Alice
sends Bob a transaction, and Bob wants Dan, the auditor, to be able to see the fact that
of money coming in from Alice and the fact that he’s spending it when Bob decides to spend it.

The workflow would
as follows (Fig.. 6.3).

.

1. Bob tells Alice his public address (V, S), and
   also asks her in all outputs addressed to him to put the attribute
   mix_attr to 1 (see below how this can be implemented
   technically).
2. Bob gives auditor Dan his secret
   view key v.
3. Alice sends Bob the transaction in the usual way
   CryptoNote. In the outputs addressed to Bob she puts mix_attr = 1.
4. Den scans all the transactions in the blockchain and with
   Using Bob’s secret view key, she checks for each output Pi == P’i = Hs(v * R, i) * G + S (where i
   – is the sequence number of the output, S is Bob’s open spend-key). If the equality
   is met, then this output is addressed to Bob.
   Dan makes sure that mix_attr == 1, adds this output to the list and
   adds this output to the list, and increases the balance by the value of the output rating.
5. Den also checks all inputs of all transactions, and
   If one of the inputs refers to Bob’s UTXO from the list, it means that
   This transaction is Bob’s outgoing payment. Thanks to the mix_attr
   = 1, this input cannot mix other outputs, which means it spends the output
   Bob directly, and Dan can be sure that it is an outgoing payment
   Bob’s.
   Dan reduces the balance by the value of the input.

.

This way, Dan
will be able to calculate Bob’s correct wallet balance without gaining access to his
secret spend-key s.

This way, Dan can calculate Bob’s correct wallet balance without gaining access to his secret spend-key.

Scheme Features

Particularity 1. Important,
that the sending side (Alice) set mix_attr to 1 when sending
transaction. If Alice does not do this, the funds will go to Bob, but at a later date, Dan will not be able to tell whether Bob spent them or not.
Later, Dan won’t be able to tell for sure if Bob spent it, because
Any other user will be able to use the output to tamper with it.

One possible solution
One solution is to create a special type of address with the same two public keys
(V, S), but packaged in a different way than the standard one. Alice, when sending
funds to an address of this type will know to set mix_attr
= 1 for the corresponding outputs.

Particularity 2.
Using special type addresses does not force Alice to set the attribute
attribute value for outputs. She can send funds without doing so,
However, this will be immediately revealed by both Bob and Auditor Dan.

Specialty 3.. In this
auditability is achieved at the cost of a marginal reduction in
untraceability (untraceability of connections). This is not a particular problem
if the possibility of an audit is made available to an unlimited number of people.
For example, a charitable foundation might publish a donation address
along with a secret view-key so that anyone can act as an auditor
as an auditor and calculate the current balance of their wallet. What is important is that at the same time
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 tamper with arbitrary outputs.

It’s worth noting that in
Where the ability to audit is given to a narrow range of individuals, unlike in the
The example above, a reduction in untraceability could be an undesirable effect.

It’s worth noting that when audits are given to a narrow circle of people, unlike the example above.

The big advantages
With this option, it’s easy to implement and there’s no extra
data and computational burden.

7. Conclusion

We’ve looked at three
options for adding auditing capabilities to the CryptoNote protocol:
Bytecoin Amethyst, Anton Sokolov’s theoretical AS scheme, and the use of
mix_attr (let’s refer to it as MA).

The relative change in
ring signature size for all variants except Bytecoin (BCN) is independent of
of Ninputs, so consider Ninputs = 1 (minimum) and Ninputs = 3 (Fig.. 7.1).

.

Note. Ninputs – the number of inputs in
transaction, Nmixins – number of outputs associated with each transaction input. If Nmixins > 1 it means,
that to increase untraceability each input refers to more than
one output of some other transaction and there’s no way to tell which one is the real one.
is real.

The best result
is shown by the AS scheme, giving a reduction in the size of the ring signature over a wide
range of the number of meshed outputs (Nmixins). Bytecoin also gives good results
with Nmixins >=3 (as already noted, the Bytecoin Amethyst introduced a limit of at least 3 Nmixins to improve
untraceability was introduced a restriction on the minimum number of Nmixins equal to 3).

The MA scheme has no
The MA scheme offers no improvement in terms of the size of the ring signature.

Let us now compare
The laboriousness of the ring signature verification procedure. To do this we will use
metric mentioned above, namely, take the sum of scalar
product and computation of the hash function Hp with weights proportional to their execution times
on a typical modern CPU:

O(total) = 130 * O(*) + 15 * O(Hp)

We have the following picture (Fig.. 7.2).

.

Directly spending money
(Nmixins = 1) AS and Bytecoin schemes require significantly more computation
for signature verification.

When mashing the outputs.
(Nmixins > 1) the Bytecoin Amethyst scheme looks preferable to AS, however
the last considered MA variant remains unbeatable.

To summarize.
summarize by taking into account such factors as the increase in address size, inputs, and
transactional outputs (Fig.. 7.3).

.

Bytecoin maintains
end-user-friendly address length, while Anton
Sokolov’s scheme increases it by 50%. This does not directly affect the size of the
of the blockchain (although the sender’s encrypted address can be transmitted in the
extra transaction if the latter wishes, for example) and computational complexity,
but it does have a slight effect on usability. In the MA scheme, the address size
remains 64 bytes, but it does require a way to distinguish addresses
addresses that are intended for auditing and those that are not.

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

.

It is also worth noting the fact
The Bytecoin Amethyst scheme has been implemented in code for quite a long time and, judging by
judging by the lack of reports about problems since the moment of its implementation
well tested in practice. However, its public description in a rigorous form
It has not been possible to find, so there is no formal evidence of its correctness yet.

.

The AS scheme, on the other hand,
is strictly described and offered for discussion in the cryptocommunity.

Scheme MA does not have a strictly described formal proof, but because of its extreme simplicity, it seems unnecessary.