pc Monero Research LabRESEARCH BULLETIN MRL-0003Monero is Not That Mysterious25 September 2014Shen Noether* and Sarang Noether*Correspondence labmonero.ccMonero Research Lab1 IntroductionRecently, there have been some vague fears about the CryptoNote source code andprotocol floating around the internet based on the fact that it is a more complicatedprotocol than, for instance, Bitcoin. The purpose of this note is to try and clearup some misconceptions, and hopefully remove some of the mystery surroundingMonero Ring Signatures. I will start by comparing the mathematics involved inCryptoNote ring signatures as described in [CN] to the mathematics in [FS], onwhich CryptoNote is based. After this, I will compare the mathematics of the ringsignature to what is actually in the CryptoNote codebase.2 CryptoNote OriginsAs noted in [CN], 4.1 by Saberhagen, group ring signatures have a history startingas early as 1991 [CH], and various ring signature schemes have been studied by anumber 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 toaccomodate blockchain technology.2.1 Traceable Ring SignaturesIn [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 needfor identity escrow allows users of the ring signature to hide themselves in a groupwith an inherently higher level of distrust compared to schemes relying on a groupmanager.In ring-signature schemes relying on a group manager, such as the original ringsignatures described in [CH], a designated trusted person guards the secrets ofthe group participants. While anonymous, such schemes rely, of course, on themanager not being compromised. The result of having a group-manager, in termsof currencies, is essentially the same as having a trusted organization or node tomix your coins.In contrast, the traceable ring signature scheme given in [FS] has no group man-ager.According to [FS], there are four al security requirements to their traceablering signature schemec Monero Research Lab Page 2 of 10Public Traceability - Anyone who creates two signatures for different mes-sages with respect to the same tag can be traced. In CryptoNote, if theuser opts not to use a one-time key for each transaction, then they will betraceable, however if they desire anonymity, then they will use the one-timekey. Thus as stated on page 5 of [CN], the traceability property is weakenedin CryptoNote.Tag-Linkability - Every two signatures generated by the same signer withrespect to the same tag are linked. This aspect in CryptoNote refers to eachtransaction having a key image which prevents double spending.Anonymity - As long as a signer does not sign on two different messageswith respect to the same tag, the identity of the signer is indistinguishablefrom any of the possible ring members. In addition, any two signatures gen-erated with respect to two distinct tags are always unlinkable. In terms ofCryptoNote, if the signer attempts to use the same key-image more thanonce, then they can be identified out of the group. The unlinkability aspectis retained and is a key part of CryptoNote.Exculpability - An honest ring member cannot be accused of signing twicewith respect to the same tag. In other words, it should be infeasible tocounterfeit a tag corresponding to another person’s secret key. In termsof CryptoNote, this says that key images cannot be faked.In addition, [FS] provide a ring signature protocol on page 10 of their paper, whichis equivalent to the CryptoNote ring signature algorithm, as described on page 9-10of [CN]. It is worthwhile to note that [FS] is a publicly peer-reviewed publicationappearing in Lecture Notes in Computer Science, as opposed to typical crypto-currency protocol descriptions, where it is unclear whether or not they have beenreviewed or not.2.2 Traceability vs CryptoNoteIn the original traceable ring signature algorithm described in [FS], it is possibleto use the tag corresponding to a signature multiple times. However, multiple usesof the tag allow the user to be traced; in other words, the signer’s index can bedetermined out of the group of users signing. It is worthwhile to note that, due tothe exculpability feature of the protocol [FS] 5.6, [CN], A2, keys cannot be stolenthis way, unless an attacker is able to solve the Elliptic Curve Discrete LogarithmProblem 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 arerejected by the blockchain as double-spends, and hence traceability is not an aspectof CryptoNote.2.3 Tag-Linkability vs CryptoNoteIn essence, the tag-linkability aspect of the traceable ring signature protocol iswhat prevents CryptoNote transactions from being double-spends. The relevantprotocols are referred to as “Trace” in [FS], 5 and “LNK” in the CryptoNotepaper. Essentially all that is required is to be able to keep track of the key imageswhich have been used before, and to verify that a key image is not used again.c Monero Research Lab Page 3 of 10If one key-image is detected on the blockchain before another key-image, then thesecond key image is detected as a double-spend transaction. As key-images cannotbe forged, being exculpable, the double-spender must in fact be the same person,and not another person trying to steal a wallet.3 One-Time Ring Signatures mathematicsThe security of the ring signature scheme as described in [FS] 10, [CN] 10 andimplemented in the CryptoNote source relies on the known security properties ofCurve25519. Note that this is the same curve used in OpenSSH 6.5, Tor, Apple iOS,and many other[1] security systems.3.1 Twisted Edwards CurvesThe basic security in the CryptoNote Ring Signature algorithm is guaranteed by theECDLP [Si], XI.4 on the Twisted Edwards curve ed25519. The security propertiesof curve ed25519 are described in [Bern], by noted cryptographer Daniel Bernstein,andin[BCPM]byateamfromMicrosoftResearch.Bernsteinnotesabouted25519the “every known attack is more expensive than pering a brute-force search ona typical 128-bit secret-key cipher.”The curve ed25519 is a singular curve of genus 1 with a group law, and describedby x2 y2 1 121665121666 x2y2. This curve is considered over the finite field Fq,q 2255 19. For those readers unfamiliar with algebraic geometry, an algebraiccurve is considered as a one dimensional sort of space, consisting of all points x;ysatisfying the above equation. All points are also considered modulo q. By virtue ofits genus, ed25519 has a “group structure” which, for the purpose of this discussion,means if P x1;y1 is a point on the curve, and Q x2;y2 is another pointon the curve, then these points can be added or subtracted and the sum ordifference, P Q or P Q will also be on the curve. The addition is not thenaive adding of x1 x2 and y1 y2, but instead points are added using the ruleP Q x1y2 y1x21 dx1x2y1y2;y1y2 x1x21 dx1x2y1y2where d nbsp;121665121666 [BBJLP] 6, [BCPM]. The mathematics of curves of genusone are explained in great detail in [Si] for the interested reader.Based on the above, we can computePP for any such point. In order to shortennotation, we rely on our algebraic intuition and denote 2P P P. If n2Z, thennP denotes the repeated sumP P nbsp;P| {z }n timesusing the above nonlinear addition law. As an example of how this differs fromordinary addition, consider the following system of equationsaP bQ XaP0bQ0 Y[1]http// Monero Research Lab Page 4 of 10where a;b;c;d are integers and P;Q;X are points. If this were a standard systemof linear equations then one could use linear algebraic techniques to easily solvefor a and b, assuming that P;Q;X;Y;P0, and Q0 are known. However, even if a;bare very small the above system is extremely difficult to solve using the ed25519addition law. For example, if a 1 and b 1, we havexPyQ yPxQ1 dxPxQyPyQ;yPyQ xPxQ1 dxPxQyPyQ xX;yXxP0yQ0 yP0 xQ01 dxP0 xQ0yP0yQ0 ;yP0yQ0 xP0 xQ01 dxP0 xQ0yP0yQ0 xY;yY So in reality, this is a system of 4 nonlinear equations. To convince yourself thatit is in fact difficult to figure out a and b, try writing the above systems assuminga 2, b 1. It should become clear that the problem is extremely difficult whena;b are chosen to be very large. As of yet, there are no known s available toefficiently solve this system for large values of a and b.Consider the following problem. Suppose your friend has a random integer q,and computes qP using the above of addition. Your friend then tells you thex and y coordinates qP x;y, but not what q itself is. Without asking, howdo you find out what q is A naive approach might be to start with P and keepadding P P P until you reach qP which you will know because you will endup at x;y. But if q is very large then this naive approach might take billionsof years using modern supercomputers. Based on what mathematicians currentlyknow about the problem and the number of possibleq, none of the currently knownattacking techniques can, as a general rule, do better in any practical sense thanbrute force.In CryptoNote, your secret key is essentially just a very, very large number xfor other considerations, see section 4.3.3, we choose x to be a multiple of 8.There is a special point G on the curve ed25519 called “the base point” of the curvewhich is used as the starting point to get xG. Your public key is just xG, andyou are protected by the above problem from someone using known ination todetermine the private key.3.2 Relation to Diffie HelmanIncluded in a ring signature are the following equations involving your secret key xP xGI xHp Prs qs csxHeresis a number giving the index in the group signature to your public key, andHp P is a hash function which deterministically takes the pointP to another pointP0 x0G, where x0 is another very large unily chosen number. The value qs ischosen unily at random, and cs is computed using another equation involvingrandom values. The particular hash function used in CryptoNote is Keccak1600,c Monero Research Lab Page 5 of 10used in other applications such as SHA-3; it is currently considered to be secure[FIPS]. The CryptoNote use of a single hash function is consistent with the stan-dard procedure of consolidating distinct random oracles in proofs of security in[FS], for example into a single strong hash function.The above equations can be written as followsP xGP0 xx0G0rs qs csxSolving the top two equations is equivalent to the ECDH as outlined in a previ-ous note [SN] and is the same practical difficulty as the ECDLP. Although theequations appear linear, they are in fact highly non-linear, as they use the additiondescribed in 3.1 and above. The third equation with unknowns qs and x, has thedifficulty of finding a random number either qs or x in Fq, a very large finite field;this is not feasible. Note that as the third equation has two unknowns, combiningit with the previous two equations does not help; an attacker needs to determine atleast one of the random numbers qs or x.3.3 Time Cost to Guess q or xSince q and x are assumed to be random very large numbers in Fq , with q 2255 19 generated as 32-byte integers, this is equivalent to a 128-bit securitylevel [BCPM], which is known to take billions of years to compute with currentsupercomputers.3.4 Review of Proofs in AppendixIn the CryptoNote appendix, there are four proofs of the four basic propertiesrequired for security of the one-time ring-signature schemeLinkability protection against double-spendingExculpability protection of your secret keyUnforgeability protection against forged ring signaturesAnonymity ability to hide a transaction within other transactionsThese theorems are essentially identical to those in [FS] and show that the ringsignature protocol satisfies the above traits. The first theorem shows that only thesecret keys corresponding to the public keys included in a group can produce asignature for that group. This relies on the ECDLP for the solution of two simulta-neous non-linear elliptic curve equations, which, as explained in 3.2, is practicallyunsolvable. The second theorem uses the same reasoning, but shows that in order tocreate a fake signature that passes verification, one would need to be able to solvethe ECDLP. The third and fourth theorems are taken directly from [FS].4 One-Time Ring Signatures ApplicationTo 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 Monerosource code using naive Twisted Edwards Curve operations taken from code byc Monero Research Lab Page 6 of 10Bernstein, rather than the apparently reasonably optimized operations existing inthe CryptoNote code. Functions are explained in the code comments below. UsingthemodelwillproduceaworkingringsignaturethatdiffersslightlyfromtheMoneroring signatures only because of hashing and packing differences between the usedlibraries. The full code is hosted at the following addresshttps// that most of the important helper functions in crypto-ops.cpp in theCryptoNote source are pulled from the reference implementation of Curve25519.This reference implentation was coded by Matthew Dempsky Mochi Media, nowGoogle[2].In addition, after comparing the python code to the paper, and in turn comparingthe python code to the actual Monero source, it is fairly easy to see that functionslike generate_ring_sig are all doing what they are supposed to based on the pro-tocol described in the whitepaper. For example, here is the ring signature generationalgorithm used in the CryptoNote sourceAlgorithm 1 Ring Signaturesi 0while i numkeys doif i s thenk random Fq elementLi k GRi k HpPielsek1 random Fq elementk2 random Fq elementLi k1Pi k2GRi k1I k2HpPici k1ri k2end ifi i 1end whileh Hsprefix L0is R0iscs h Pi6s cirs k xcsreturn I;fcig;frigComparing this with [CN] shows that it agrees with the whitepaper. Similarly,here is the algorithm used in the CryptoNote source to verify ring signaturesAlgorithm 2 VERi 0while i numkeys doL0i ciPi riGR0i riHpPi ciIi i 1end whileh Hsprefix L0is R0ish h Pi6s cireturn h 0mod q 04.1 Important Crypto-ops FunctionsDescriptions of important functions in Crypto-ops.cpp. Even more references andination is given in the comments in the MiniNero.py code linked above.[2]http//nacl.cr.yp.to/c Monero Research Lab Page 7 of 104.1.1 ge_frombytes_vartimeTakes as some data and converts to a point on ed25519. For a reference ofthe equation used, uv3/p