Monero 백서

Monero

원문

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

Zero to Monero: Second Edition a technical guide to a private digital currency; for beginners, amateurs, and experts Published April 4, 2020 (v2.0.0) koe1, Kurt M. Alonso 2, Sarang Noether 3 License: Zero to Monero: Second Edition is released into the public domain. 1 ukoe@protonmail.com 2 kurt@oktav.se 3 sarang.noether@protonmail.com Abstract Cryptography. It may seem like only mathematicians and computer scientists have access to this obscure, esoteric, powerful, elegant topic. In fact, many kinds of cryptography are simple enough that anyone can learn their fundamental concepts. It is common knowledge that cryptography is used to secure communications, whether they be coded letters or private digital interactions. Another application is in so-called cryptocurrencies. These digital moneys use cryptography to assign and transfer ownership of funds. To ensure that no piece of money can be duplicated or created at will, cryptocurrencies usually rely on ‘blockchains’, which are public, distributed ledgers containing records of currency transactions that can be verified by third parties [97]. It might seem at first glance that transactions need to be sent and stored in plain text format to make them publicly verifiable. In fact, it is possible to conceal a transaction’s participants, as well as the amounts involved, using cryptographic tools that nevertheless allow transactions to be verified and agreed upon by observers [136]. This is exemplified in the cryptocurrency Monero. We endeavor here to teach anyone who knows basic algebra and simple com- puter science concepts like the ‘bit representation’ of a number not only how Monero works at a deep and comprehensive level, but also how useful and beautiful cryptography can be. For our experienced readers: Monero is a standard one-dimensional distributed acyclic graph (DAG) cryptocurrency blockchain [97] where transactions are based on elliptic curve cryptography using curve Ed25519 [38], transaction inputs are signed with Schnorr-style multilayered linkable spontaneous anonymous group signatures (MLSAG) [108], and output amounts (communicated to recipients via ECDH [52]) are concealed with Pedersen commitments [88] and proven in a legitimate range with Bulletproofs [43]. Much of the first part of this report is spent explaining these ideas. Contents 1 Introduction 1 1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Readership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Origins of the Monero cryptocurrency . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4.1 Part 1: ‘Essentials’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4.2 Part 2: ‘Extensions’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4.3 Additional content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 History of Zero to Monero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.7 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 I Essentials 7 2 Basic Concepts 8 2.1 A few words about notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 iii 2.2.1 Modular addition and multiplication . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 Modular exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.3 Modular multiplicative inverse . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.4 Modular equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Elliptic curve cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1 What are elliptic curves? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.2 Public key cryptography with elliptic curves . . . . . . . . . . . . . . . . . . 16 2.3.3 Diffie-Hellman key exchange with elliptic curves . . . . . . . . . . . . . . . . 16 2.3.4 Schnorr signatures and the Fiat-Shamir transform . . . . . . . . . . . . . . 16 2.3.5 Signing messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Curve Ed25519 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.1 Binary representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.2 Point compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.3 EdDSA signature algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5 Binary operator XOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Advanced Schnorr-like Signatures 25 3.1 Prove knowledge of a discrete logarithm across multiple bases . . . . . . . . . . . . 25 3.2 Multiple private keys in one proof . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Spontaneous Anonymous Group (SAG) signatures . . . . . . . . . . . . . . . . . . 27 3.4 Back’s Linkable Spontaneous Anonymous Group (bLSAG) signatures . . . . . . . . 29 3.5 Multilayer Linkable Spontaneous Anonymous Group (MLSAG) signatures . . . . . 32 3.6 Concise Linkable Spontaneous Anonymous Group (CLSAG) signatures . . . . . . . 34 4 Monero Addresses 36 4.1 User keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 One-time addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2.1 Multi-output transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3 Subaddresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.3.1 Sending to a subaddress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.4 Integrated addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.5 Multisignature addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 iv 5 Monero Amount Hiding 43 5.1 Commitments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Pedersen commitments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.3 Amount commitments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.4 RingCT introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.5 Range proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6 Monero Ring Confidential Transactions (RingCT) 48 6.1 Transaction types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.2 Ring Confidential Transactions of type RCTTypeBulletproof2 . . . . . . . . . . . . 49 6.2.1 Amount commitments and transaction fees . . . . . . . . . . . . . . . . . . 49 6.2.2 Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2.3 Avoiding double-spending . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2.4 Space requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.3 Concept summary: Monero transactions . . . . . . . . . . . . . . . . . . . . . . . . 53 6.3.1 Storage requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 7 The Monero Blockchain 55 7.1 Digital currency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.1.1 Distributed/shared version of events . . . . . . . . . . . . . . . . . . . . . . 56 7.1.2 Simple blockchain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.2 Difficulty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.2.1 Mining a block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.2.2 Mining speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.2.3 Consensus: largest cumulative difficulty . . . . . . . . . . . . . . . . . . . . 59 7.2.4 Mining in Monero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.3 Money supply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.3.1 Block reward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.3.2 Dynamic block weight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 v 7.3.3 Block reward penalty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.3.4 Dynamic minimum fee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 7.3.5 Emission tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.3.6 Miner transaction: RCTTypeNull . . . . . . . . . . . . . . . . . . . . . . . . 69 7.4 Blockchain structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.4.1 Transaction ID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.4.2 Merkle tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 7.4.3 Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 II Extensions 74 8 Monero Transaction-Related Knowledge Proofs 75 8.1 Transaction proofs in Monero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.1.1 Multi-base Monero transaction proofs . . . . . . . . . . . . . . . . . . . . . 76 8.1.2 Prove creation of a transaction input ( SpendProofV1) . . . . . . . . . . . . 76 8.1.3 Prove creation of a transaction output ( OutProofV2) . . . . . . . . . . . . . 78 8.1.4 Prove ownership of an output ( InProofV2) . . . . . . . . . . . . . . . . . . 79 8.1.5 Prove an owned output was not spent in a transaction (UnspentProof) . . . 81 8.1.6 Prove an address has a minimum unspent balance ( ReserveProofV2) . . . 82 8.2 Monero audit framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8.2.1 Prove an address and subaddress correspond (SubaddressProof) . . . . . . 84 8.2.2 The audit framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 9 Multisignatures in Monero 86 9.1 Communicating with co-signers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 9.2 Key aggregation for addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 9.2.1 Naive approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 9.2.2 Drawbacks to the naive approach . . . . . . . . . . . . . . . . . . . . . . . . 88 9.2.3 Robust key aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 vi 9.3 Thresholded Schnorr-like signatures . . . . . . . . . . . . . . . . . . . . . . . . . . 91 9.4 MLSTAG Ring Confidential signatures for Monero . . . . . . . . . . . . . . . . . . 93 9.4.1 RCTTypeBulletproof2 with N-of-N multisig . . . . . . . . . . . . . . . . . . 93 9.4.2 Simplified communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 9.5 Recalculating key images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 9.6 Smaller thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 9.6.1 1-of-N key aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 9.6.2 (N-1)-of-N key aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 9.6.3 M-of-N key aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 9.7 Key families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.7.1 Family trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.7.2 Nesting multisig keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 9.7.3 Implications for Monero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 10 Monero in an Escrowed Marketplace 107 10.1 Essential features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 10.1.1 Purchasing workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 10.2 Seamless Monero multisig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 10.2.1 Basics of a multisig interaction . . . . . . . . . . . . . . . . . . . . . . . . . 110 10.2.2 Escrowed user experience . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 11 Joint Monero Transactions (TxTangle) 117 11.1 Building joint transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 11.1.1 n-way communication channel . . . . . . . . . . . . . . . . . . . . . . . . . 118 11.1.2 Message rounds to construct a joint transaction . . . . . . . . . . . . . . . . 119 11.1.3 Weaknesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 11.2 Hosted TxTangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 11.2.1 Basic communication with a host over I2P, and other features . . . . . . . . 122 11.2.2 Host as a service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 11.3 Using a trusted dealer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 11.3.1 Dealer-based procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 vii Bibliography 126 Appendices 133 A RCTTypeBulletproof2 Transaction Structure 135 B Block Content 141 C Genesis Block 144 viii CHAPTER 1 Introduction In the digital realm it is often trivial to make endless copies of information, with equally endless alterations. For a currency to exist digitally and be widely adopted, its users must believe its supply is strictly limited. A money recipient must trust they are not receiving counterfeit coins, or coins that have already been sent to someone else. To accomplish that without requiring the collaboration of any third party like a central authority, its supply and complete transaction history must be publicly verifiable. We can use cryptographic tools to allow data registered in an easily accessible database - the blockchain - to be virtually immutable and unforgeable, with legitimacy that cannot be disputed by any party. Cryptocurrencies store transactions in the blockchain, which acts as a public ledger 1 of all the currency operations. Most cryptocurrencies store transactions in clear text, to facilitate verifica- tion of transactions by the community of users. Clearly, an open blockchain defies any basic understanding of privacy or fungibility 2, since it literally publicizes the complete transaction histories of its users. 1 In this context ledger just means a record of all currency creation and exchange events. Specifically, how much money was transferred in each event and to whom. 2 “F ungiblemeans capable of mutual substitution in use or satisfaction of a contract. ... Examples: ... money, etc.”[25] In an open blockchain such as Bitcoin, the coins owned by Alice can be differentiated from those owned by Bob based on the ‘transaction history’ of those coins. If Alice’s transaction history includes transactions related to supposedly nefarious actors, then her coins might be ‘tainted’ [95], and hence less valuable than Bob’s (even if they own the same amount of coins). Reputable figures claim that newly minted Bitcoins trade at a premium over used coins, since they don’t have a history [118]. 1 CHAPTER 1. INTRODUCTION 2 To address the lack of privacy, users of cryptocurrencies such as Bitcoin can obfuscate trans- actions by using temporary intermediate addresses [99]. However, with appropriate tools it is possible to analyze flows and to a large extent link true senders with receivers [125, 41, 112, 48]. In contrast, the cryptocurrency Monero (Moe-neh-row) attempts to tackle the issue of privacy by storing only single-use addresses for receipt of funds in the blockchain, and by authenticating the dispersal of funds in each transaction with ring signatures. With these methods there are no known generally effective ways to link receivers or trace the origin of funds. 3 Additionally, transaction amounts in the Monero blockchain are concealed behind cryptographic constructions, rendering currency flows opaque. The result is a cryptocurrency with a high level of privacy and fungibility. 1.1 Objectives Monero is an established cryptocurrency with over five years of development [127, 13], and main- tains a steadily increasing level of adoption [54]. 4 Unfortunately, there is little comprehensive documentation describing the mechanisms it uses. 5,6 Even worse, essential parts of its theoretical framework have been published in non-peer-reviewed papers that are incomplete or contain errors. For significant parts of the theoretical framework of Monero, only the source code is reliable as a source of information. 7 Moreover, for those without a background in mathematics, learning the basics of elliptic curve cryptography, which Monero uses extensively, can be a haphazard and frustrating endeavor. 8 We intend to palliate this situation by introducing the fundamental concepts necessary to under- stand elliptic curve cryptography, reviewing algorithms and cryptographic schemes, and collecting in-depth information about Monero’s inner workings. To provide the best experience for our readers, we have taken care to build a constructive, step- by-step description of the Monero cryptocurrency. 3 Depending on the behavior of users, there may be cases where transactions can be analyzed to some extent. For an example see this article: [61]. 4 In terms of market capitalization, Monero has been steady relative to other cryptocurrencies. It was 14 th as of June 14th, 2018, and 12 th on January 5 th, 2020; see https://coinmarketcap.com/. 5 One documentation effort, at https://monerodocs.org/, has some helpful entries, especially related to the Command Line Interface. The CLI is a Monero wallet accessible through a console/terminal. It has the most functionality out of all Monero wallets, at the expense of no user-friendly graphical interface. 6 Another, more general, documentation effort called Mastering Monero can be found here: [57]. 7 Mr. Seguias has created the excellent Monero Building Blocks series [123], which contains a thorough treatment of the cryptographic security proofs used to justify Monero’s signature schemes. As with Zero to Monero: First Edition [33], Seguias’s series is focused on v7 of the protocol. 8 A previous attempt to explain how Monero works [110] did not elucidate elliptic curve cryptography, was incomplete, and is now over five years outdated. CHAPTER 1. INTRODUCTION 3 In the second edition of this report we have centered our attention on version 12 of the Monero protocol9, corresponding to version 0.15.x.x of the Monero software suite. All transaction and blockchain-related mechanisms described here belong to those versions. 10,11 Deprecated trans- action schemes have not been explored to any extent, even if they may be partially supported for backward compatibility. Likewise with deprecated blockchain features. The first edition [33] corresponded to version 7 of the protocol, and version 0.12.x.x of the software suite. 1.2 Readership We anticipate many readers will encounter this report with little to no understanding of discrete mathematics, algebraic structures, cryptography12, and blockchains. We have tried to be thorough enough that laypeople from all perspectives may learn Monero without needing external research. We have purposefully omitted, or delegated to footnotes, some mathematical technicalities, when they would be in the way of clarity. We have also omitted concrete implementation details where we thought they were not essential. Our objective has been to present the subject half-way between mathematical cryptography and computer programming, aiming at completeness and conceptual clarity.13 1.3 Origins of the Monero cryptocurrency The cryptocurrency Monero, initially known as BitMonero, was created in April 2014 as a
프로젝트로 돌아가기