Monero is Not That Mysterious

Monero is Not That Mysterious

Free Download // Login or Register
Monero is Not That Mysterious
Monero Research Lab Papers

Recently, there have been some vague fears about the CryptoNote source code and protocol floating around the internet based on the fact that it is a more complicated protocol than, for instance, Bitcoin. The purpose of this note is to try and clear up some misconceptions, and hopefully remove some of the mystery surrounding Monero Ring Signatures. I will start by comparing the mathematics involved in CryptoNote ring signatures (as described in [CN]) to the mathematics in [FS], on which CryptoNote is based. After this, I will compare the mathematics of the ring signature to what is actually in the CryptoNote codebase.

CryptoNote Origins
As noted in ([CN], 4.1) by Saberhagen, group ring signatures have a history starting as early as 1991 [CH], and various ring signature schemes have been studied by a number of researchers throughout the past two decades. As claimed in ([CN] 4.1), the main ring signature used in CryptoNote is based on [FS], with some changes to accommodate blockchain technology.

Traceable Ring Signatures
In [FS], Fujisaki and Suzuki introduce a scheme for a ring signature designed to “leak secrets anonymously, without the risk of identity escrow.” This lack of a need for identity escrow allows users of the ring signature to hide themselves in a group with an inherently higher level of distrust compared to schemes relying on a group manager.

In ring-signature schemes relying on a group manager, such as the original ring signatures described in [CH], a designated trusted person guards the secrets of the group participants. While anonymous, such schemes rely, of course, on the manager not being compromised. The result of having a group-manager, in terms of currencies, is essentially the same as having a trusted organization or node to mix your coins.

In contrast, the traceable ring signature scheme given in [FS] has no group manager.

According to [FS], there are four formal security requirements to their traceable ring signature scheme:
  • Public Traceability - Anyone who creates two signatures for different messages with respect to the same tag can be traced. (In CryptoNote, if the user opts not to use a one-time key for each transaction, then they will be traceable, however if they desire anonymity, then they will use the one-time key. Thus as stated on page 5 of [CN], the traceability property is weakened in CryptoNote.)
  • Tag-Linkability - Every two signatures generated by the same signer with respect to the same tag are linked. (This aspect in CryptoNote refers to each transaction having a key image which prevents double spending.)
  • Anonymity - As long as a signer does not sign on two different messages with respect to the same tag, the identity of the signer is indistinguishable from any of the possible ring members. In addition, any two signatures generated with respect to two distinct tags are always unlinkable. (In terms of CryptoNote, if the signer attempts to use the same key-image more than once, then they can be identified out of the group. The unlinkability aspect is retained and is a key part of CryptoNote.)
  • Exculpability - An honest ring member cannot be accused of signing twice with respect to the same tag. In other words, it should be infeasible to counterfeit a tag corresponding to another person’s secret key. (In terms of CryptoNote, this says that key images cannot be faked.)
In addition, [FS] provide a ring signature protocol on page 10 of their paper, which is equivalent to the CryptoNote ring signature algorithm, as described on page 9-10 of [CN]. It is worthwhile to note that [FS] is a publicly peer-reviewed publication appearing in Lecture Notes in Computer Science, as opposed to typical cryptocurrency protocol descriptions, where it is unclear whether or not they have been reviewed or not.

Traceability vs CryptoNote
In the original traceable ring signature algorithm described in [FS], it is possible to use the tag corresponding to a signature multiple times. However, multiple uses of the tag allow the user to be traced; in other words, the signer’s index can be determined out of the group of users signing. It is worthwhile to note that, due to the exculpability feature of the protocol ([FS] 5.6, [CN], A2), keys cannot be stolen this way, unless an attacker is able to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) upon which a large portion of modern cryptography is based ([Si] XI.4).

The process to trace a tag used more than once is described on ([FS], page 10). In the CryptoNote protocol, however, key images (tags) used more than once are rejected by the blockchain as double-spends, and hence traceability is not an aspect of CryptoNote.

Tag-Linkability vs CryptoNote
In essence, the tag-linkability aspect of the traceable ring signature protocol is what prevents CryptoNote transactions from being double-spends. The relevant protocols are referred to as “Trace” in ([FS], 5) and “LNK” in the CryptoNote paper. Essentially all that is required is to be able to keep track of the key images which have been used before, and to verify that a key image is not used again.

If one key-image is detected on the blockchain before another key-image, then the second key image is detected as a double-spend transaction. As key-images cannot be forged, being exculpable, the double-spender must in fact be the same person, and not another person trying to steal a wallet.

One-Time Ring Signatures (Mathematics)
The security of the ring signature scheme as described in ([FS] 10, [CN] 10) and implemented in the CryptoNote source relies on the known security properties of Curve25519. Note that this is the same curve used in OpenSSH 6.5, Tor, Apple iOS, and many other[1] security systems.

One-Time Ring Signatures (Application)
To understand how CryptoNote is implementing the One-Time Ring signatures, I built a model in Python of Crypto-ops.cpp and Crypto.cpp from the Monero source code using naive Twisted Edwards Curve operations (taken from code by Bernstein), rather than the apparently reasonably optimized operations existing in the CryptoNote code. Functions are explained in the code comments below. Using the model will produce a working ring signature that differs slightly from the Monero ring signatures only because of hashing and packing differences between the used libraries.

Despite the ring signature functions in the original CryptoNote source being poorly commented, the code can be traced back to established and used sources, and is relatively straightforward. The Python implementation provided with this review gives further indication of the code’s correctness. Furthermore, the elliptic curve mathematics underlying the ring signature scheme has been extremely well-studied; the concept of ring signatures is not novel, even if their application to cryptocurrencies is.
  • Like
Reactions: PrivacyCoinGuy