Monero 백서

Monero

원문

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

called cache timing attacks [39]. We provide here an outline of the steps performed by the algorithm. A complete description and sample implementation in the Python language can be found in [75]. Signature 1. Let hk be a hashH(k) of the signer’s private key k. Compute α as a hash α =H(hk, m) of the hashed private key and message. Depending on implementation, m could be the actual message or its hash [75]. 2. Calculate αG and the challenge ch =H([αG],K, m). 3. Calculate the response r =α +ch·k. 4. The signature is the pair ( αG,r ). Verification Verification is performed as follows 1. Compute ch′ =H([αG],K, m). 2. If the equality 2 crG ?= 2cαG + 2cch′∗K holds then the signature is valid. The 2c term comes from Bernstein et al.’s general form of the EdDSA algorithm [39]. According to that paper, though it isn’t required for adequate verification, removing 2 c provides stronger equations. 29 See src/crypto/ crypto ops builder/ ref10Comm- entedComb- ined/ [40] for efficient group operations in Twisted Edwards EC (i.e. point addition, doubling, mixed addition, etc). See [36] for efficient modular arithmetic. CHAPTER 2. BASIC CONCEPTS 23 The public key K can be any EC point, but we only want to use points in the generator G’s subgroup. Multiplying by the cofactor 2 c ensures all points are in that subgroup. Alternatively, verifiers could check lK ?= 0, which only works if K is in the subgroup. We do not know of any weaknesses caught by these precautions, though as we will see the latter method is important in Monero (Section 3.4). In this signature scheme we store one EC point and one scalar, and have one public EC key. Why it works 2crG = 2c(α +H([αG],K, m)·k)·G = 2cαG + 2cH([αG],K, m)·K Binary representation By default, an EdDSA signature would need 64 + 32 bytes for the EC point αG and scalar r. However, RFC8032 assumes point αG is compressed, which reduces space requirements to only 32 + 32 bytes. We include the public key K, which implies 32 + 32 + 32 total bytes. 2.5 Binary operator XOR The binary operator XOR is a useful tool that will appear in Sections 4.4 and 5.3. It takes two arguments and returns true if one, but not both, of them is true [22]. Here is its truth table: A B A XOR B T T F T F T F T T F F F In the context of computer science, XOR is equivalent to bit addition modulo 2. For example, the XOR of two bit pairs: XOR({1, 1},{1, 0}) ={1 + 1, 1 + 0} (mod 2) ={0, 1} Each of these also produce{0, 1}: XOR({1, 0},{1, 1}), XOR({0, 0},{0, 1}), and XOR({0, 1},{0, 0}). For XOR inputs with b bits, there are 2 b− 1 other combinations of inputs that would make the same output. This means if C = XOR(A,B ) and input A∈R {0,..., 2b−1}, an observer who learned C would gain no information about B. CHAPTER 2. BASIC CONCEPTS 24 At the same time, anyone who knows two of the elements in {A,B,C}, where C = XOR(A,B ), can calculate the third element, such as A = XOR(B,C ). XOR indicates if two elements are different or the same, so knowing C and B is enough to expose A. A careful examination of the truth table reveals this vital feature. 30 30 One interesting application of XOR (unrelated to Monero) is swapping two bit registers without a third register. We use the symbol⊕ to indicate an XOR operation. A⊕A = 0, so after three XOR operations between the registers: {A,B}→{ [A⊕B],B}→{ [A⊕B],B⊕ [A⊕B]} ={[A⊕B],A⊕ 0} ={[A⊕B],A}→{ [A⊕B]⊕A,A} ={B,A}. CHAPTER 3 Advanced Schnorr-like Signatures A basic Schnorr signature has one signing key. As it happens, we can apply its core concepts to create a variety of progressively more complex signature schemes. One of those schemes, MLSAG, will be of central importance in Monero’s transaction protocol. 3.1 Prove knowledge of a discrete logarithm across multiple bases It is often useful to prove the same private key was used to construct public keys on different ‘base’ keys. For example, we could have a normal public key kG, and a Diffie-Hellman shared secret kR with some other person’s public key (recall Section 2.3.3), where the base keys are G and R. As we will soon see, we can prove knowledge of the discrete log k inkG, prove knowledge of k inkR, and prove that k is the same in both cases (all without revealing k). Non-interactive proof Suppose we have a private key k, and d base keys J ={J1,...,J d}. The corresponding public keys areK ={K1,...,K d}. We make a Schnorr-like proof (recall Section 2.3.4) across all bases. 1 Assume the existence of a hash function Hn mapping to integers from 0 to l− 1.2 1 While we say ‘proof’, it can be trivially made a signature by including a message m in the challenge hash. The terminology is loosely interchangeable in this context. 2 In Monero, the hash function Hn(x) = sc reduce32(Keccak(x)) where Keccak is the basis of SHA3 and sc reduce32() puts the 256 bit result in the range 0 to l− 1 (although it should really be 1 to l− 1). 25 CHAPTER 3. ADVANCED SCHNORR-LIKE SIGNATURES 26 1. Generate random number α∈R Zl, and compute, for all i∈ (1,...,d ), αJi. 2. Calculate the challenge, c =Hn(J,K, [αJ1], [αJ2],..., [αJd]) 3. Define the response r =α−c∗k. 4. Publish the signature ( c,r ). Verification Assuming the verifier knowsJ andK, he does the following. 1. Calculate the challenge: c′ =H(J,K, [rJ1 +c∗K1], [rJ2 +c∗K2],..., [rJd +c∗Kd]) 2. If c =c′ then the signer must know the discrete logarithm across all bases, and it’s the same discrete logarithm in each case (as always, except with negligible probability). Why it works If instead of d base keys there was just one, this proof would clearly be the same as our original Schnorr proof (Section 2.3.4). We can imagine each base key in isolation to see that the multi-base proof is just a bunch of Schnorr proofs connected together. Moreover, by using only one challenge and response for all of those proofs, they must have the same discrete logarithm k. To get a single response that works for multiple keys the challenge would need to be known before defining an α for each key, but c is a function of α! 3.2 Multiple private keys in one proof Much like a multi-base proof, we can combine many Schnorr proofs that use different private keys. Doing so proves we know all the private keys for a set of public keys, and reduces storage requirements by making just one challenge for all proofs. Non-interactive proof Suppose we have d private keys k1,...,k d, and base keys J ={J1,...,J d}.3 The corresponding public keys areK ={K1,...,K d}. We make a Schnorr-like proof for all keys simultaneously. 3 There is no reason J can’t contain duplicate base keys here, or for all base keys to be the same (e.g. G). Duplicates would be redundant for multi-base proofs, but now we are dealing with different private keys. CHAPTER 3. ADVANCED SCHNORR-LIKE SIGNATURES 27 1. Generate random numbers αi∈R Zl for all i∈ (1,...,d ), and compute all αiJi. 2. Calculate the challenge, c =Hn(J,K, [α1J1], [α2J2],..., [αdJd]) 3. Define each response ri =αi−c∗ki. 4. Publish the signature ( c,r 1,...,r d). Verification Assuming the verifier knowsJ andK, he does the following. 1. Calculate the challenge: c′ =H(J,K, [r1J1 +c∗K1], [r2J2 +c∗K2],..., [rdJd +c∗Kd]) 2. If c = c′ then the signer must know the private keys for all public keys in K (except with negligible probability). 3.3 Spontaneous Anonymous Group (SAG) signatures Group signatures are a way of proving a signer belongs to a group, without necessarily identifying him. Originally (Chaum in [49]), group signature schemes required the system be set up, and in some cases managed, by a trusted person in order to prevent illegitimate signatures, and, in a few schemes, adjudicate disputes. These relied on a group secret which is not desirable since it creates a disclosure risk that could undermine anonymity. Moreover, requiring coordination between group members (i.e. for setup and management) is not scalable beyond small groups or inside companies. Liu et al. presented a more interesting scheme in [85] building on the work of Rivest et al. in [119]. The authors detailed a group signature algorithm called LSAG characterized by three properties: anonymity, linkability, and spontaneity. Here we discuss SAG, the non-linkable version of LSAG, for conceptual clarity. We reserve the idea of linkability for later sections. Schemes with anonymity and spontaneity are typically referred to as ‘ring signatures’. In the context of Monero they will ultimately allow for unforgeable, signer-ambiguous transactions that leave currency flows largely untraceable. CHAPTER 3. ADVANCED SCHNORR-LIKE SIGNATURES 28 Signature Ring signatures are composed of a ring and a signature. Each ring is a set of public keys, one of which belongs to the signer and the rest of which are unrelated. The signature is generated with that ring of keys, and anyone verifying it would not be able to tell which ring member was the actual signer. Our Schnorr-like signature scheme in Section 2.3.5 can be considered a one-key ring signature. We get to two keys by, instead of defining r right away, generating a decoy r′ and creating a new challenge to define r with. Let m be the message to sign, R ={K1,K 2,...,K n} a set of distinct public keys (a group/ring), andkπ the signer’s private key corresponding to his public key Kπ∈R , where π is a secret index. 1. Generate random number α∈R Zl and fake responses ri ∈R Zl for i∈ {1, 2,...,n} but excluding i =π. 2. Calculate cπ+1 =Hn(R, m, [αG]) 3. For i =π + 1,π + 2,...,n, 1, 2,...,π − 1 calculate, replacing n + 1→ 1, ci+1 =Hn(R, m, [riG +ciKi]) 4. Define the real response rπ such that α =rπ +cπkπ (mod l). The ring signature contains the signature σ(m) = (c1,r 1,...,r n), and the ring R. Verification Verification means proving σ(m) is a valid signature created by a private key corresponding to a public key inR (without necessarily knowing which one), and is done in the following manner: 1. For i = 1, 2,...,n iteratively compute, replacing n + 1→ 1, c′i+1 =Hn(R, m, [riG +ciKi]) 2. If c1 =c′1 then the signature is valid. Note that c′1 is the last term calculated. In this scheme we store (1+n) integers and use n public keys. CHAPTER 3. ADVANCED SCHNORR-LIKE SIGNATURES 29 Why it works We can informally convince ourselves the algorithm works by going through an example. Consider ring R ={K1,K 2,K 3} with kπ =k2. First the signature: 1. Generate random numbers: α, r1, r3 2. Seed the signature loop: c3 =Hn(R, m, [αG]) 3. Iterate: c1 =Hn(R, m, [r3G +c3K3]) c2 =Hn(R, m, [r1G +c1K1]) 4. Close the loop by responding: r2 =α−c2k2 (mod l) We can substitute α intoc3 to see where the word ‘ring’ comes from: c3 =Hn(R, m, [(r2 +c2k2)G]) c3 =Hn(R, m, [r2G +c2K2 ]) Then verification usingR, and σ(m) = (c1,r 1,r 2,r 3): 1. We use r1 and c1 to compute c′2 =Hn(R, m, [r1G +c1K1]) 2. From when we made the signature, we see c′2 =c2. With r2 and c′2 we compute c′3 =Hn(R, m, [r2G +c′2K2]) 3. We can easily see that c′3 =c3 by substituting c2 for c′2. Using r3 and c′3 we get c′1 =Hn(R, m, [r3G +c′3K3]) No surprises here: c′1 =c1 if we substitute c3 for c′3. 3.4 Back’s Linkable Spontaneous Anonymous Group (bLSAG) signatures The ring signature schemes discussed here on out display several properties that will be useful for producing confidential transactions. 4 Note that both ‘signer ambiguity’ and ‘unforgeability’ also apply to SAG signatures. 4 Keep in mind that all robust signature schemes have security models which contain various properties. The properties mentioned here are perhaps most relevant to understanding the purpose of Monero’s ring signatures, but are not a comprehensive overview of linkable ring signature properties. CHAPTER 3. ADVANCED SCHNORR-LIKE SIGNATURES 30 Signer Ambiguity An observer should be able to determine the signer must be a member of the ring (except with negligible probability), but not which member. 5 Monero uses this to obfuscate the origin of funds in each transaction. Linkability If a private key is used to sign two different messages then the messages will become linked.6 As we will show, this property is used to prevent double-spending attacks in Monero (except with negligible probability). Unforgeability No attacker can forge a signature except with negligible probability. 7 This is used to prevent theft of Monero funds by those not in possession of the appropriate private keys. In the LSAG signature scheme [85], the owner of a private key could produce one anonymous unlinked signature per ring.8 In this section we present an enhanced version of the LSAG algorithm where linkability is independent of the ring’s decoy members. 9 The modification was unraveled in [108] based on a publication by Adam Back [35] regarding the CryptoNote [136] ring signature algorithm (previously used in Monero, and now deprecated; see Section 8.1.2), which was in turn inspired by Fujisaki and Suzuki’s work in [65]. Signature As with SAG, let m be the message to sign, R ={K1,K 2,...,K n} a set of distinct public keys, andkπ the signer’s private key corresponding to his public key Kπ∈R , where π is a secret index. Assume the existence of a hash function Hp, which maps to curve points in EC. 10,11 1. Calculate key image ˜K =kπHp(Kπ).12 5 Anonymity for an action is usually in terms of an ‘anonymity set’, which is ‘all the people who could have possibly taken that action’. The largest anonymity set is ‘humanity’, and for Monero it is the ring size, or e.g. the so-called ‘mixin level’ v plus the real signer. Mixin refers to how many fake members each ring signature has. If the mixin is v = 4 then there are 5 possible signers. Expanding anonymity sets makes it progressively harder to track down real actors. 6 The linkability property does not apply to non-signing public keys. That is, a ring member whose public key has been used in different ring signatures will not cause linkage. 7 Certain ring signature schemes, including the one in Monero, are strong against adaptive chosen-message and adaptive chosen-public-key attacks. An attacker who can obtain legitimate signatures for chosen messages and corresponding to specific public keys in rings of his choice cannot discover how to forge the signature of even one message. This is called existential unforgeability; see [108] and [85]. 8 In the LSAG scheme linkability only applies to signatures using rings with the same members and in the same order, the ‘exact same ring.’ It is really “one anonymous signature per ring member per ring.” Signatures can be linked even if made for different messages. 9 LSAG was discussed in the first edition of this report. [33] 10 It doesn’t matter if points from Hp are compressed or not. They can always be decompressed. 11 Monero uses a hash function src/ringct/ rctOps.cpp hash to p3() that returns curve points directly, rather than computing some integer that is then multiplied by G. Hp would be broken if someone discovered a way to find nx such that nxG =Hp(x). See a description of the algorithm in [107]. According to the CryptoNote whitepaper [136] its origin was this paper: [133]. 12 In Monero it’s important to use the hash to point function for key images instead of another base point so linearity doesn’t lead to linking signatures created by the same address (even if for different one-time addresses). See [136] page 18. CHAPTER 3. ADVANCED SCHNORR-LIKE SIGNATURES 31 2. Generate random number α∈R Zl and random numbers ri∈R Zl for i∈{ 1, 2,...,n} but excluding i =π. 3. Compute cπ+1 =Hn(m, [αG], [αHp(Kπ)]) 4. For i =π + 1,π + 2,...,n, 1, 2,...,π − 1 calculate, replacing n + 1→ 1, ci+1 =Hn(m, [riG +ciKi], [riHp(Ki) +ci ˜K]) 5. Define rπ =α−cπkπ (mod l). The signature will be σ(m) = (c1,r 1,...,r n), with key image ˜K and ringR. Verification Verification means proving σ(m) is a valid signature created by a private key corresponding to a public key inR, and is done in the following manner: 1. Check l ˜K ?= 0. 2. For i = 1, 2,...,n iteratively compute, replacing n + 1→ 1, c′i+1 =Hn(m, [riG +ciKi], [riHp(Ki) +ci ˜K]) 3. If c1 =c′1 then the signature is valid. In this scheme we store (1+n) integers, have one EC key image, and use n public keys. We src/crypto- note core/ cryptonote core.cpp check tx inputs key- images do- main() must checkl ˜K ?= 0 because it is possible to add an EC point from the subgroup of size h (the cofactor) to ˜K and, if all ci are multiples of h (which we could achieve with automated trial and error using different α and ri values), make h unlinked valid signatures using the same ring and signing key.13 This is because an EC point multiplied by its subgroup’s order is zero. 14 To be clear, given some point K in the subgroup of order l, some point Kh with order h, and an integerc divisible by h: c∗ (K +Kh) =cK +cKh =cK + 0 We can demonstrate correctness (i.e. ‘how it works’) in a similar way to the more simple SAG signature scheme. Our description attempts to be faithful to the original explanation of bLSAG, which does not includeR in the hash that calculates ci. Including keys in the hash is known as ‘key prefixing’. Recent research [77] suggests it may not be necessary, although adding the prefix is standard practice for similar signature schemes (LSAG uses key prefixing). 13 We are not concerned with points from other subgroups because the output of Hn is confined to Zl. For EC order N =hl, all divisors of N (and hence, possible subgroups) are either multiples of l (a prime) or divisors of h. 14 In Monero’s early history this was not checked for. Fortunately, it was not exploited before a fix was implemented in April 2017 (v5 of the protocol) [63]. CHAPTER 3. ADVANCED SCHNORR-LIKE SIGNATURES 32 Linkability Given two valid signatures that are different in some way (e.g. different fake responses, different messages, different overall ring members), σ(m) = (c1,r 1,...,r n) with ˜K, and σ′(m′) = (c′1,r′1,...,r′n′) with ˜K′, if ˜K = ˜K′ then clearly both signatures come from the same private key. While an observer could link σ andσ′, he wouldn’t necessarily know which Ki inR orR′ was the culprit unless there was only one common key between them. If there was more than one common ring member, his only recourse would be solving the DLP or auditing the rings in some way (such as learning all ki with i⁄=π, or learning kπ).15 3.5 Multilayer Linkable Spontaneous Anonymous Group (ML- SAG) signatures In order to sign transactions, one has to sign with multiple private keys. In [108], Shen Noether et al. describe a multi-layered generalization of the bLSAG signature scheme applicable when we have a set of n·m keys; that is, the set R ={Ki,j} for i∈{ 1, 2,...,n} and j∈{ 1, 2,...,m} where we know them private keys{kπ,j} corresponding to the subset{Kπ,j} for some indexi =π. Such an algorithm would address our needs if we generalize the notion of linkability. Linkability If any private key kπ,j is used in 2 different signatures, then those signatures will be automatically linked. Signature 1. Calculate key images ˜Kj =kπ,jHp(Kπ,j) for all j∈{ 1, 2,...,m}. 2. Generate random numbers αj∈R Zl, and ri,j∈R Zl for i∈{ 1, 2,...,n} (except i = π) and j∈{ 1, 2,...,m}. 3. Compute 16 cπ+1 =Hn(m, [α1G], [α1Hp(Kπ,1)],..., [αmG], [αmHp(Kπ,m)]) 15 LSAG, which is quite similar to bLSAG, is unforgeable, meaning no attacker could make a valid ring signature without knowing a private key. If he invents a fake ˜K and seeds his signature computation with cπ+1, then, not knowingkπ, he can’t calculate a number rπ =α−cπkπ that would produce [rπG +cπKπ] =αG. A verifier would reject his signature. Liu et al. prove forgeries that manage to pass verification are extremely improbable [85]. 16 Monero src/ringct/ rctSigs.cpp MLSAG Gen() MLSAG uses key prefixing. Each challenge contains explicit public keys like this (adding the K terms absent from bLSAG; key images are included in the message signed): cπ+1 =Hn(m,Kπ,1, [α1G], [α1Hp(Kπ,1)],...,K π,m, [αmG], [αmHp(Kπ,m)]) CHAPTER 3. ADVANCED SCHNORR-LIKE SIGNATURES 33 4. For i =π + 1,π + 2,...,n, 1, 2,...,π − 1 calculate, replacing n + 1→ 1, ci+1 =Hn(m, [ri,1G+ciKi,1], [ri,1Hp(Ki,1)+ci ˜K1]
프로젝트로 돌아가기