# KOE et al. - Zero to Monero (Highlights)  ## Metadata **Cover**:: https://readwise-assets.s3.amazonaws.com/media/uploaded_book_covers/profile_155788/3433eeec-e22b-4987-83a0-655a9733f7ee.png **Source**:: #from/readwise **Zettel**:: #zettel/fleeting **Status**:: #x **Authors**:: [[KOE]], [[Kurt M. Alonso]], [[Sarang Noether]] **Full Title**:: Zero to Monero **Category**:: #books #readwise/books **Category Icon**:: 📚 **Document Tags**:: #blockchain **Highlighted**:: [[2021-03-05]] **Created**:: [[2022-09-26]] ## Highlights - 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]. (Page 2) - supply and complete transaction history must be publicly verifiable. (Page 9) ### CHAPTER 1 Introduction - attempts to tackle the issue of privacy (Page 10) - a high level of privacy and fungibility. (Page 10) - For significant parts of the theoretical framework of Monero, only the source code is reliable as a source of information. (Page 10) ### Part I Essentials #### CHAPTER 2 Basic Concepts - double-and-add (Page 18) - square-and-multiply (Page 19) - Fermat’s little theorem (Page 20) - an−2 ≡ a−1 (Page 20) - Twisted (Page 21) - Edwards curves (Page 21) - If P generates a subgroup whose order is prime, then all the included points (except for (Page 22) - the point-at-infinity) generate that same subgroup. (Page 22) - Schoof ’s algorithm (Page 22) #blue - The smallest n such that nP = 0 is the order u of the subgroup. (Page 22) - only one subgroup of size l is possible. (Page 22) - there are only h points P in EC where hP will equal 0. (Page 23) - Any two points P1 and P2 with (Page 23) - order u are in the same subgroup, which is composed of multiples of (N/u)P (cid:48). (Page 23) - finding n such that P1 = nP2 is thought to be computationally hard. (Page 23) - double-and-add (Page 23) - kG = K. (Page 24) - Diffie-Hellman key exchange (Page 24) - Schnorr signatures and the Fiat-Shamir transform (Page 24) - The verifier can compute R(cid:48) = αG + c ∗ K before the prover, (Page 25) - the prover reuses α to prove his knowledge of k (Page 25) - the prover knew c from the beginning (Page 25) - The scheme is not publicly verifiable. (Page 25) - Using a hash function, instead of the verifier, to generate challenges is known as a Fiat-Shamir (Page 25) - transform (Page 25) - makes an interactive proof non-interactive and publicly verifiable [ (Page 25) - ECDSA. (Page 26) - Generate random number α (Page 27) - (m, (Page 27) #green - α = r + c ∗ kA (Page 27) #green - (c, r). (Page 27) #green - Monero uses a particular Twisted Edwards elliptic curve for cryptographic operations, Ed25519, (Page 28) - F2255−19 (Page 28) - most significant bit (Page 28) - point com (Page 28) - pression (Page 28) - two possible x values (+ or −) for each y (Page 29) - x and –x have different odd/even assignments. (Page 29) - We set the most significant bit of y to 0 if x is even, and 1 if it is odd. (Page 29) - q = 2255 − 19 ≡ 5 (mod 8), (Page 29) - instead of generating random integers every time, it uses a hash value derived (Page 30) - from the private key of the signer and the message itself. (Page 30) - α = H(hk, m) (Page 30) #green - K, (Page 30) #green - The public key K can be any EC point, but we only want to use points in the generator G’s (Page 31) - Multiplying by the cofactor 2c ensures all points are in that subgroup. (Page 31) - subgroup. (Page 31) - For XOR inputs with b bits, there are 2b − 1 other combinations of inputs that would make the (Page 31) - This means if C = XOR(A, B) and input A ∈R {0, ..., 2b−1}, an observer who (Page 31) - same output. (Page 31) - learned C would gain no information about B. (Page 31) - At the same time, anyone who knows two of the elements in {A, B, C}, where C = XOR(A, B), (Page 32) - can calculate the third element, such as A = XOR(B, C). (Page 32) - MLSAG (Page 33) - Prove knowledge of a discrete logarithm across multiple bases (Page 33) - we can prove knowledge of the discrete log k in kG, prove knowledge of k in kR, (Page 33) - all without revealing k (Page 33) - and prove that k is the same in both cases (all without revealing k). (Page 33) - {J1, ..., Jd} (Page 33) #green #### CHAPTER 3 Advanced Schnorr-like Signatures - random number (Page 34) #green - αJi (Page 34) #green - verifier knows J and K, (Page 34) #green - Multiple private keys in one proof (Page 34) - for all i ∈ (1, ..., d), (Page 35) #green - (c, r1, ..., rd). (Page 35) #green - verifier knows J and K, (Page 35) #green - Spontaneous Anonymous Group (SAG) signatures (Page 35) - anonymity (Page 35) #green - spontaneity. (Page 35) #green - linkability, (Page 35) - SAG, (Page 35) - ring (Page 36) - signature. (Page 36) - Ring signatures are composed of a ring and a signature. (Page 36) - Each ring is a set of public keys, one of (Page 36) - The signature is generated with (Page 36) - which belongs to the signer and the rest of which are unrelated. (Page 36) - that ring of keys, and anyone verifying it would not be able to tell which ring member was the (Page 36) - actual signer. (Page 36) - R = {K1, K2, ..., Kn} (Page 36) #green - m (Page 36) #green - π is a secret index (Page 36) - kπ (Page 36) - fake responses ri (Page 36) - ci (Page 36) - σ(m) = (c1, r1, ..., rn), (Page 36) #green - Back’s Linkable Spontaneous Anonymous Group (bLSAG) (Page 37) - signatures (Page 37) - Signer Ambiguity (Page 38) - Linkability (Page 38) #green - Unforgeability (Page 38) - R = {K1, K2, ..., Kn} (Page 38) #green - m (Page 38) #green - π is a secret index. (Page 38) - kπ (Page 38) - Hp (Page 38) #green - Hp, (Page 38) #green - ˜K = kπHp(Kπ) (Page 38) #green - rπ = α − cπkπ (Page 39) #green - ˜K (Page 39) #green - . Check l ˜K = 0. (Page 39) #green - if ˜K = ˜K(cid:48) then clearly both signatures come from the same private key. (Page 40) - Multilayer Linkable Spontaneous Anonymous Group (ML SAG) signatures (Page 40) #green - Multilayer Linkable Spontaneous Anonymous Group (ML (Page 40) - SAG) signatures (Page 40) - m k (Page 40) - R = {Ki,j} for i ∈ {1, 2, ..., n} and j ∈ {1, 2, ..., m} (Page 40) - we know the m private keys {kπ,j} (Page 40) - Linkability (Page 40) #green - any private key kπ,j (Page 40) - If any private key kπ,j is used in 2 different signatures, then those signatures will be (Page 40) - automatically linked. (Page 40) - key images ˜Kj = kπ,jHp(Kπ,j) (Page 40) - j ∈ {1, 2, ..., m}. 2. Generate random numbers αj ∈R Zl, and ri,j ∈R Zl for i ∈ {1, 2, ..., n} (except i = π) and (Page 40) - cπ+1 = Hn(m, [α1G], [α1Hp(Kπ,1)], ..., [αmG], [αmHp(Kπ,m)]) (Page 40) - 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], ..., [ri,mG+ciKi,m], [ri,mHp(Ki,m)+ci ˜Km]) (Page 41) - rπ,j = αj − cπkπ,j (mod l). (Page 41) - kπ,j (Page 41) - The signature will be σ(m) = (c1, r1,1, ..., r1,m, ..., rn,1, ..., rn,m), with key images ( ˜K1, ..., ˜Km). (Page 41) - Linkability (Page 41) - Concise Linkable Spontaneous Anonymous Group (CLSAG) (Page 42) - signatures (Page 42) - linkability only applies to the primary. (Page 42) - ˜Kj = kπ,jHp(Kπ,1) f (Page 42) #green #### CHAPTER 4 Monero Addresses - Monero users have two sets of private/public keys (Page 45) - public keys (Kv, Ks) (Page 45) - of a user is the pair of public keys (Kv, Ks). The address (Page 45) - kv the view key, and ks the spend key (Page 45) - One-time addresses (Page 45) #green - Diffie-Hellman-like exchange (Page 45) - Alice generates a random number r ∈R Zl, (Page 45) - Ko = Hn(rKv B)G + Ks B (Page 46) - rG (Page 46) - kv BrG = rKv B (Page 46) - B)G B = Ko − Hn(rKv K(cid:48)s (Page 46) - B = Ks K(cid:48)s B (Page 46) - is the ‘view key’ since it can be used to find outputs spendable by Bob. (Page 46) - without ko Alice can’t compute the output’s key image, so she can never know for sure if Bob spends the output she sent him. (Page 46) - rG is typically known (Page 47) - as the transaction public key (Page 47) - t , t) + ks t = (Hn(rKv t )G t = Hn(rKv Ko t = Hn(rKv ko t , t)G + Ks t , t) + ks t (Page 47) #blue - , t) (Page 47) #green - t = Hn(rKv ko t , t) + ks t (Page 47) - Kv,i = kv(ks + Hn(kv, i))G Ks,i = (ks + Hn(kv, i))G (Page 47) #blue - rKs, B (Page 48) #green #### CHAPTER 5 Monero Amount Hiding - Pedersen commitments (Page 52) #green - additively homomorphic. (Page 52) - C(a + b) = C(a) + C(b) (Page 52) - by defining a commitment as simply C(a) = aG, we could easily create cheat tables of commitments to help us recognize common values of a. (Page 52) - secret blinding factor (Page 52) - another generator H (Page 52) - H = γG (Page 52) - it is unknown for which value of γ (Page 52) - C(x, a) = xG + aH (Page 52) - C(y, b) = yG + bH (Page 53) - amount stored in the (Page 53) - transaction’s data. (Page 53) - yt = Hn(“commitment mask”, Hn(rKv B, t)) amount t = bt ⊕8 Hn(“amount”, Hn(rKv B, t)) (Page 53) - amount t (Page 53) - RingCT (Page 53) - While a transaction’s verifiers don’t know how much money is contained in each input and output, (Page 53) - they still need to be sure the sum of input amounts equals the sum of output amounts. (Page 53) - Ca j − C(cid:48)a j = (xj − x(cid:48) j)G (Page 54) - (xj − x(cid:48) j) = zj (Page 54) - Ca j = zjG + 0H j − C(cid:48)a (Page 54) - C(cid:48)a j a pseudo output commitment. Pseudo output commitments are included in trans (Page 54) - action data, and there is one for each input. (Page 54) - are random except for the mth pseudo out commitment (Page 55) - Range proofs (Page 55) - one value in the equation were ‘negative’. (Page 55) - Bulletproofs (Page 55) - n-tuple aggregate proof ΠBP = (A, S, T1, T2, τx, µ, L, R, a, b, t) (Page 55) - Monero Ring Confidential Transactions (RingCT) (Page 56) #green #### CHAPTER 6 Monero Ring Confidential Transactions (RingCT) - RCTTypeBulletproof2. (Page 57) - RCTTypeBulletproof2 (Page 57) - each input is signed separately (Page 57) - Amount commitments and transaction fees (Page 57) - one-time addresses Ko π,m π,1, ..., Ko (Page 57) - amount commitments Ca π,1, ..., Ca π,m (Page 57) - the private keys ko π,1, ..., ko π,m (Page 57) - This sender knows (Page 57) - the blinding factors xj used in commitments Ca π,j (Page 57) - Transaction fee amounts f are stored in clear text in the transaction data (Page 57) - C(cid:48)a π,m π,1, ..., C(cid:48)a (Page 58) - The sender calculates pseudo output commitments for the input amounts (Page 58) - creates commitments for intended output amounts (Page 58) - Cb 0, ..., Cb p−1 (Page 58) - C(f ) = f H (Page 58) - (cid:88) ( C(cid:48)a j − (cid:88) Cb t ) − f H = 0 j t (Page 58) - Signature (Page 58) - unrelated (Page 58) - Rj = {{Ko 1,j, (C1,j − C(cid:48)a π,j)}, ... {Ko ... {Ko π,j, (Ca π,j − C(cid:48)a π,j)}, v+1,j, (Cv+1,j − C(cid:48)a π,j)}} (Page 58) - The message m signed by each input is essentially a hash of all transaction data except for the MLSAG signatures. (Page 59) - The advantage of signing inputs individually is that the set of real inputs and commitments to zero need not be placed at the same index π (Page 59) - Extra: includes the transaction public key rG, or, if at least one output is directed to a for each subaddress’d output t and rtG for each normal address’d output subaddress, rtKs,i t t, and maybe an encoded payment ID (should be at most one per transaction)15 (Page 61) #### CHAPTER 7 The Monero Blockchain - Dynamic block weight (Page 70) #green - Bulletproof verification is linear, so artificially increasing transaction weights ‘prices in’ that extra verification time (it’s called a ‘clawback’). (Page 71) - transaction clawback = 0.8 ∗ [(23 ∗ (p + num dummy outs)/2) · 32 − (2 · (cid:100)log2(64 · p)(cid:101) + 9) · 32] (Page 71) - transaction weight = transaction size + transaction clawback (Page 71) - Long term block weight (Page 71) - longterm block weight = min{block weight, 1.4 ∗ previous effective longterm median} effective longterm median = max{300kB, median 100000blocks longterm weights} (Page 72) - Cumulative median weight (Page 72) - cumulative weights median = max{300kB, min{max{300kB, median 100blocks weights}, 50 ∗ effective longterm median}} (Page 72) - max next block weight = 2 ∗ cumulative weights median (Page 72) - While the maximum block weight can rise up to 100 times the effective median long term weight after a few hundred blocks (Page 72) - it cannot rise more than 40% beyond that over the next 50,000 blocks. Therefore long-term block weight growth is tethered by the long term weights, and in the short term weights may surge above their steady-state values. (Page 72) - 7.3.3 Block reward penalty (Page 72) - If the intended block weight is greater than the cumulative median, (Page 73) - Bactual = B − P Bactual = B ∗ (1 − ((block weight/cumulative weights median) − 1)2) (Page 73) - Dynamic minimum fee (Page 73) - from exceeding the block reward (Page 74) - marginal penalty (Page 74) #blue - cumulative median (Page 74) #blue - 2% of the penalty zone the fee gets doubled (Page 75) - f B min = B ∗ ( 1 cumulative weights median ) ∗ 0.002 (Page 75) - an attacker can use minimum fees to maintain high block weights (relative to organic transaction volume) with very low cost. (Page 75) - smallest median = max{300kB, min{median 100blocks weights, effective longterm median}} (Page 75) - f B min−actual = B ∗ ( 1 smallest median ) ∗ 0.002 (Page 76) - average total block fees will tend to be of a magnitude lower than, or at least the same as, the block reward (Page 76) - Transactions competing for block space with higher fees leads to a bigger supply of block space, and lower fees. (Page 76) - Emission tail (Page 76) - After a while its block rewards fall to zero. With no more penalty on increasing block weight, miners add any transaction with a non-zero fee to their blocks. (Page 76) - prevents this by not allowing the block reward to fall below 0.6 XMR Monero (Page 77) - not allowing the block reward to fall below 0.6 XMR (Page 77) #green ### Part II Extensions #### CHAPTER 8 Monero Transaction-Related Knowledge Proofs #### CHAPTER 9 Multisignatures in Monero #### CHAPTER 10 Monero in an Escrowed Marketplace #### CHAPTER 11 Joint Monero Transactions (TxTangle) ### Appendices - RCTTypeBulletproof2 Transaction Structure (Page 143) #### APPENDIX A RCTTypeBulletproof2 Transaction Structure - "txnFee" (Page 145) #### APPENDIX B Block Content #### APPENDIX C Genesis Block