Monero 백서

Monero

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 19쪽 중 2쪽

deriva- tive of the proof-of-concept currency CryptoNote [127]. Monero means ‘money’ in the language Esperanto, and its plural form is Moneroj (Moe-neh-rowje, similar to Moneros but using the -ge from orange). CryptoNote is a cryptocurrency devised by various individuals. A landmark whitepaper describing it was published under the pseudonym of Nicolas van Saberhagen in October 2013 [136]. It offered receiver anonymity through the use of one-time addresses, and sender ambiguity by means of ring signatures. 9 The ‘protocol’ is the set of rules that each new block is tested against before it can be added to the blockchain. This set of rules includes the ‘transaction protocol’ (currently version 2, RingCT), which are general rules pertaining to how a transaction is constructed. Specific transaction rules can, and do, change, without the transaction protocol’s version changing. Only large-scale changes to the transaction structure warrant moving its version number. 10 The Monero codebase’s integrity and reliability is predicated on assuming enough people have reviewed it to catch most or all significant errors. We hope that readers will not take our explanations for granted, and verify for themselves the code does what it’s supposed to. If it doesn’t, we hope you will make a responsible disclosure ( https://hackerone.com/monero) for major problems, or Github pull request ( https://github.com/ monero-project/monero) for minor issues. 11 Several protocols worth considering for the next generation of Monero transactions are undergoing research and investigation, including Triptych [106], RingCT3.0 [143], Omniring [84], and Lelantus [71]. 12 An extensive textbook on applied cryptography can be found here: [42]. 13 Some footnotes, especially in chapters related to the protocol, spoil future chapters or sections. These are intended to make more sense on a second read-through, since they usually involve specific implementation details that are only useful to those who have a grasp of how Monero works. CHAPTER 1. INTRODUCTION 4 Since its inception, Monero has further strengthened its privacy aspects by implementing amount hiding, as described by Greg Maxwell (among others) in [89] and integrated into ring signatures based on Shen Noether’s recommendations in [108], then made more efficient with Bulletproofs [43]. 1.4 Outline As mentioned, our aim is to deliver a self-contained and step-by-step description of the Monero cryptocurrency. Zero to Monero has been structured to fulfill this objective, leading the reader through all parts of the currency’s inner workings. 1.4.1 Part 1: ‘Essentials’ In our quest for comprehensiveness, we have chosen to present all the basic elements of cryptog- raphy needed to understand the complexities of Monero, and their mathematical antecedents. In Chapter 2 we develop essential aspects of elliptic curve cryptography. Chapter 3 expands on the Schnorr signature scheme from the prior chapter, and outlines the ring signature algorithms that will be applied to achieve confidential transactions. Chapter 4 explores how Monero uses addresses to control ownership of funds, and the different kinds of addresses. In Chapter 5 we introduce the cryptographic mechanisms used to conceal amounts. With all the components in place, we explain the transaction scheme used in Monero in Chapter 6. The Monero blockchain is unfolded in Chapter 7. 1.4.2 Part 2: ‘Extensions’ A cryptocurrency is more than just its protocol, and in ‘Extensions’ we talk about a number of different ideas, many of which have not been implemented. 14 Various information about a transaction can be proven to observers, and those methods are the content of Chapter 8. While not essential to the operation of Monero, there is a lot of utility in multisignatures that allow multiple people to send and receive money collaboratively. Chapter 9 describes Monero’s current multisignature approach and outlines possible future developments in that area. 14 Please note that future protocol versions of Monero, especially those implementing new transaction protocols, may make any or all of these ideas impossible or impractical. CHAPTER 1. INTRODUCTION 5 Of extreme importance is applying multisig to the interactions of vendors and shoppers in online marketplaces. Chapter 10 constitutes our original design of an escrowed marketplace using Monero multisig. First presented here, TxTangle, outlined in Chapter 11, is a decentralized protocol for joining the transactions of multiple individuals into one. 1.4.3 Additional content Appendix A explains the structure of a sample transaction from the blockchain. Appendix B explains the structure of blocks (including block headers and miner transactions) in Monero’s blockchain. Finally, Appendix C brings our report to a close by explaining the structure of Monero’s genesis block. These provide a connection between the theoretical elements described in earlier sections with their real-life implementation. We Isn’t this useful? use margin notes to indicate where Monero implementation details can be found in the source code.15 There is usually a file path, such as src/ringct/rctOps.cpp, and a function, such as ecdhEncode(). Note: ‘-’ indicates split text, such as crypto- note → cryptonote, and we ne- glect namespace qualifiers (e.g. Blockchain::) in most cases. 1.5 Disclaimer All signature schemes, applications of elliptic curves, and Monero implementation details should be considered descriptive only. Readers considering serious practical applications (as opposed to a hobbyist’s explorations) should consult primary sources and technical specifications (which we have cited where possible). Signature schemes need well-vetted security proofs, and Monero imple- mentation details can be found in Monero’s source code. In particular, as a common saying goes, ‘don’t roll your own crypto’. Code implementing cryptographic primitives should be well-reviewed by experts and have a long history of dependable performance. Moreover, original contributions in this document may not be well-reviewed and are likely untested, so readers should exercise their judgement when reading them. 1.6 History of Zero to Monero Zero to Monero is an expansion of Kurt Alonso’s master’s thesis, ‘Monero - Privacy in the Blockchain’ [32], published in May 2018. The first edition was published in June 2018 [33]. For the second edition we have improved how ring signatures are introduced (Chapter 3), reor- ganized how transactions are explained (added Chapter 4 on Monero Addresses), modernized the 15 Our margin notes are accurate for version 0.15.x.x of the Monero software suite, but may gradually become inaccurate as the codebase is constantly changing. However, the code is stored in a git repository ( https://github. com/monero-project/monero), so a complete history of changes is available. CHAPTER 1. INTRODUCTION 6 method used to communicate output amounts (Section 5.3), replaced Borromean ring signatures with Bulletproofs (Section 5.5), deprecated RCTTypeFull (Chapter 6), updated and elaborated Monero’s dynamic block weight and fee system (Chapter 7), investigated transaction-related proofs (Chapter 8), described Monero multisignatures (Chapter 9), designed solutions for escrowed mar- ketplaces (Chapter 10), proposed a new decentralized joint transaction protocol named TxTangle (Chapter 11), updated or added various minor details to align with the most current protocol (v12) and Monero software suite (v0.15.x.x), and scoured the document for quality-of-reading edits. 16 1.7 Acknowledgements Written by author ‘koe’. This report would not exist without Kurt’s original master’s thesis [32], so to him I owe a great debt of gratitude. Monero Research Lab (MRL) researchers Brandon “Surae Noether” Goodell and pseudonymous ‘Sarang Noether’ (who collaborated with me on Section 5.5 and Chapter 8) have been a reliable and knowledgeable resource throughout both editions of Zero to Monero’s development. Pseudonymous ‘moneromooo’, the Monero Project’s most prolific core developer, has probably the most extensive understanding of the codebase on this planet, and has pointed me in the right direction numerous times. And of course, many other wonderful Monero contributors have spent time answering my endless questions. Finally, to the various individuals who contacted us with proofreading feedback, and encouraging comments, thank you! 16 The LATEX source code for both editions of Zero to Monero can be found here (the first edition is in branch ‘ztm1’): https://github.com/UkoeHB/Monero-RCT-report. Part I Essentials 7 CHAPTER 2 Basic Concepts 2.1 A few words about notation A focal objective of this report was to collect, review, correct, and homogenize all existing informa- tion concerning the inner workings of the Monero cryptocurrency. And, at the same time supply all the necessary details to present the material in a constructive and single-threaded manner. An important instrument to achieve this was to settle for a number of notational conventions. Among others, we have used: • lower case letters to denote simple values, integers, strings, bit representations, etc. • upper case letters to denote curve points and complicated constructs For items with a special meaning, we have tried to use as much as possible the same symbols throughout the document. For instance, a curve generator is always denoted by G, its order is l, private/public keys are denoted whenever possible by k/K respectively, etc. Beyond that, we have aimed at being conceptual in our presentation of algorithms and schemes. A reader with a computer science background may feel we have neglected questions like the bit representation of items, or, in some cases, how to carry out concrete operations. Moreover, students of mathematics may find we disregarded explanations of abstract algebra. 8 CHAPTER 2. BASIC CONCEPTS 9 However, we don’t see this as a loss. A simple object such as an integer or a string can always be represented by a bit string. So-called ‘endianness’ is rarely relevant, and is mostly a matter of convention for our algorithms. 1 Elliptic curve points are normally denoted by pairs ( x,y ), and can therefore be represented with two integers. However, in the world of cryptography it is common to apply point compression techniques, which allow representing a point using only the space of one coordinate. For our con- ceptual approach it is often accessory whether point compression is used or not, but most of the time it is implicitly assumed. We src/crypto/ keccak.c have also used cryptographic hash functions freely without specifying any concrete algorithms. In the case of Monero it will typically be a Keccak2 variant, but if not explicitly mentioned then it is not important to the theory. A cryptographic hash function (henceforth simply ‘hash function’, or ‘hash’) takes in some message m of arbitrary length and returns a hash h (or ‘message digest’) of fixed length, with each possible output equiprobable for a given input. Cryptographic hash functions are difficult to reverse, have an interesting feature known as the large avalanche effect which can cause very similar messages to produce very dissimilar hashes, and it is hard to find two messages with the same message digest. Hash functions will be applied to integers, strings, curve points, or combinations of these objects. These occurrences should be interpreted as hashes of bit representations, or the concatenation of such representations. Depending on context, the result of a hash will be numeric, a bit string, or even a curve point. Further details in this respect will be given as needed. 2.2 Modular arithmetic Most modern cryptography begins with modular arithmetic, which in turn begins with the modulus operation (denoted ‘mod’). We only care about the positive modulus, which always returns a positive integer. The positive modulus is similar to the ‘remainder’ after dividing two numbers, e.g. c the ‘remain- der’ ofa/b. Let’s imagine a number line. To calculate c =a (mod b) we stand at pointa then walk toward zero with each step = b until we reach an integer ≥ 0 and <b . That is c. For example, 4 (modulo 3) = 1,−5 (mod 4) = 3, and so on. 1 In computer memory, each byte is stored in its own address (an address is akin to a numbered slot, which a byte can be stored in). A given ‘word’ or variable is referenced by the lowest address of its bytes. If variable x has 4 bytes, stored in addresses 10-13, address 10 is used to find x. The way bytes of x are organized in its set of addresses depends on endianness, although each individual byte is always and everywhere stored the same way within its address. Basically, which end of x is stored in the reference address? It could be the big end or little end. Given x = 0x12345678 (hexadecimal, 2 hexadecimal digits occupy 1 byte e.g. 8 binary digits a.k.a. bits), and an array of addresses{10, 11, 12, 13}, the big endian encoding of x is{12, 34, 56, 78} and the little endian encoding is{78, 56, 34, 12}. [78] 2 The Keccak hashing algorithm forms the basis for the NIST standard SHA-3 [27]. CHAPTER 2. BASIC CONCEPTS 10 Formally, the positive modulus is here defined for c =a (mod b) as a =bx +c, where 0≤c < b and x is a signed integer which gets discarded ( b is a positive non-zero integer). Note that, if a≤n,−a (mod n) is the same as n−a. 2.2.1 Modular addition and multiplication In computer science it is important to avoid large numbers when doing modular arithmetic. For example, if we have 29 + 87 (mod 99) and we aren’t allowed variables with three or more digits (such as 116 = 29 + 87), then we can’t compute 116 (mod 99) = 17 directly. To perform c =a +b (mod n), where a and b are each less than the modulus n, we can do this: • Compute x =n−a. If x>b then c =a +b, otherwise c =b−x. We can use modular addition to achieve modular multiplication ( a∗b (mod n) = c) with an algorithm called ‘double-and-add’. Let us demonstrate by example. Say we want to do 7 ∗ 8 (mod 9) = 2. It is the same as 7∗ 8 = 8 + 8 + 8 + 8 + 8 + 8 + 8 (mod 9) Now break this into groups of two. (8 + 8) + (8 + 8) + (8 + 8) + 8 And again, by groups of two. [(8 + 8) + (8 + 8)] + (8 + 8) + 8 The total number of + point operations falls from 6 to 4 because we only need to find (8+8) once.3 Double-and-add is implemented by converting the first number (the ‘multiplicand’ a) to binary (in our example, 7 → [0111]), then going through the binary array and doubling and adding. Let’s make an array A = [0111] and index it 3,2,1,0. 4 A[0] = 1 is the first element of A and is the least significant bit. We set a result variable to be initially r = 0, and set a sum variable to be initially s = 8 (more generally, we start with s =b). We follow this algorithm: 1. Iterate through: i = (0,...,A size− 1) (a) If A[i] == 1, then r =r +s (mod n). (b) Compute s =s +s (mod n). 2. Use the final r: c =r. 3 The effect of double-and-add becomes apparent with large numbers. For example, with 2 15∗ 230 straight addition would require about 2 15 + operations, while double-and-add only requires 15! 4 This is known as ‘LSB 0’ numbering, since the least significant bit has index 0. We will use ‘LSB 0’ for the rest of this chapter. The point here is clarity, not accurate conventions. CHAPTER 2. BASIC CONCEPTS 11 In our example 7∗ 8 (mod 9), this sequence appears: 1. i = 0 (a) A[0] = 1, so r = 0 + 8 (mod 9) = 8 (b) s = 8 + 8 (mod 9) = 7 2. i = 1 (a) A[1] = 1, so r = 8 + 7 (mod 9) = 6 (b) s = 7 + 7 (mod 9) = 5 3. i = 2 (a) A[2] = 1, so r = 6 + 5 (mod 9) = 2 (b) s = 5 + 5 (mod 9) = 1 4. i = 3 (a) A[3] = 0, so r stays the same (b) s = 1 + 1 (mod 9) = 2 5. r = 2 is the result 2.2.2 Modular exponentiation Clearly 8 7 (mod 9) = 8 ∗ 8∗ 8∗ 8∗ 8∗ 8∗ 8 (mod 9). Just like double-and-add, we can do square-and-multiply. Forae (mod n): 1. Define escalar→ebinary; A = [ebinary]; r = 1; m =a 2. Iterate through: i = (0,...,A size− 1) (a) If A[i] == 1, then r =r∗m (mod n). (b) Compute m =m∗m (mod n). 3. Use the final r as result. 2.2.3 Modular multiplicative inverse Sometimes we need 1/a (mod n), or in other words a−1 (mod n). The inverse of something times itself is by definition one (identity). Imagine 0 .25 = 1/4, and then 0.25∗ 4 = 1. CHAPTER 2. BASIC CONCEPTS 12 In modular arithmetic, for c = a−1 (mod n), ac≡ 1 (mod n) for 0 ≤ c < nand for a and n relatively prime.5 Relatively prime means they don’t share any divisors except 1 (the fraction a/n can’t be reduced/simplified). We can use square-and-multiply to compute the modular multiplicative inverse when n is a prime number because of Fermat’s little theorem:6 an−1≡ 1 (mod n) a∗an−2≡ 1 (mod n) c≡an−2≡a−1 (mod n) More generally (and more rapidly), the so-called ‘extended Euclidean algorithm’ [7] can also find modular inverses. 2.2.4 Modular equations Suppose we have an equation c = 3∗ 4∗ 5 (mod 9). Computing this is straightforward. Given some operation◦ (for example,◦ =∗) between two expressions A and B: (A◦B) (mod n) = [A (mod n)]◦ [B (mod n)] (mod n) In our example, we set A = 3∗ 4, B = 5, and n = 9: (3∗ 4∗ 5) (mod 9) = [3 ∗ 4 (mod 9)] ∗ [5 (mod 9)] (mod 9) = [3]∗ [5] (mod 9) c = 6 Now we have a way to do modular subtraction. A−B (mod n)→A + (−B) (mod n) → [A (mod n)] + [−B (mod n)] (mod n) The same principle would apply to something like x = (a−b∗c∗d)−1(e∗f +gh) (mod n).7 5 In the equation a≡b (mod n), a is congruent to b (mod n), which just means a (mod n) =b (mod n). 6 The modular multiplicative inverse has a rule stating: If ac ≡ b (mod n) with a and n relatively prime, the solution to this linear congruence is given by c = a−1b (mod n).[10] It means we can do c =a−1b (mod n)→ca≡b (mod n)→a≡c−1b (mod n). 7 The modulus of large numbers can exploit modular equations. It turns out 254 (mod 13)≡ 2∗10∗10+5∗10+4≡ (((2)∗ 10 + 5)∗ 10 + 4) (mod 13). An algorithm for a (mod n) when a>n is: 1. Define A→ [adecimal]; r = 0 2. For i =Asize− 1,..., 0 (a) r = (r∗ 10 +A[i]) (mod n) 3. Use the final r as result. CHAPTER 2. BASIC CONCEPTS 13 2.3 Elliptic curve cryptography 2.3.1 What are elliptic curves? A fe: field element finite field Fq, where q is a prime number greater than 3, is the field formed by the set {0, 1, 2,...,q − 1}. Addition and multiplication (+,·) and negation (−) are calculated (mod q). “Calculated (mod q)” means (mod q) is performed on any instance of an arithmetic operation between two field elements, or negation of a single field element. For example, given a prime field Fp with p = 29, 17 + 20 = 8 because 37 (mod 29) = 8. Also, −13 =−13 (mod 29) = 16. Typically, an elliptic curve with a given (a,b ) pair is defined as the set of all points with coordinates (x,y ) satisfying a Weierstraß equation [69]:8 y2 =x3 +ax +b where a,b,x,y ∈ Fq The cryptocurrency Monero uses a special curve belonging to the category of so-called Twisted Edwards curves [38], which are commonly expressed as (for a given ( a,d ) pair): ax2 +y2 = 1 +dx2y2 where a,d,x,y ∈ Fq In what follows we will prefer this second form. The advantage it offers over the previously men- tioned Weierstraß form is that basic cryptographic primitives require fewer arithmetic operations, resulting in faster cryptographic algorithms (see Bernstein et al. in [40] for details). Let P1 = (x1,y 1) and P2 = (x2,y 2) be two points belonging to a Twisted Edwards elliptic curve (henceforth known simply as an EC). We define addition on points by definingP1 +P2 = (x1,y 1)+ (x2,y 2) as the point P3 = (x3,y 3) where9 x3 = x1y2 +y1x21 +dx1x2y1y2 (mod q) y3 = y1y2−ax1x21−dx1x2y1y2 (mod q) These formulas for addition also apply for point doubling; that is, when P1 =P2. To subtract a point, invert its coordinates over the y-axis, ( x,y )→ (−x,y ) [38], and use point addition. Recall that ‘negative’ elements−x of Fq are really−x (mod q). Whenever two curve points are added together P3 is a point on the ‘original’ elliptic curve, or in other words all x3,y 3∈ Fq and satisfy the EC equation. Each point P in EC can generate a subgroup of order (size) u out
프로젝트로 돌아가기