Beldex 백서

Beldex

원문

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

culate c3 =Hn(R, m, [αG]) – Fori = 1, 2 c1 =Hn(R, m, [r3G +c3K3]) c2 =Hn(R, m, [r1G +c1K1]) – close the loop by responding with r2 =α−k2c2 mod l We can substitute α intoc3 to see where the word ring comes from: c3 =Hn(R, m, [(r2 +k2c2)G]) c3 =Hn(R, m, [r2G +c2K2]) Then verification usingR, and σ(m) = (c1,r 1,r 2,r 3): – We user1 and c1 to compute c′2 =Hn(R, m, [r1G +K1G]) – From when we made the signature, we seec′2 =c2 . With r2 andc′2 we compute c′3 =Hn(R, m, [(r2G +K2c′2]) – 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 +K3c′3]) c′1 =c1 if we substitute c3 for c′3. 10 2.2.3 Back’s Linkable Spontaneous Anonymous Group (bLSAG) In the LSAG signature scheme [LWW04], 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. Let m be the message to sign, R ={K1,K 2,...,K n} a set of distinct public keys (a group/ring), and kπ the signer‘s private key corresponding to his public key Kπ∈R existence of two hash functions, Hn andHp, mapping to integers from 1 to l, and curve points EC, respectively. • Signature 1. Compute key image ˜K =kπHp(Kπ) 2. Generate random number α∈R Zl and fake responsesri∈R Zl (i = 1, 2,...,n ) excluding i =π. 3. Calculate cπ+1 =Hn(m, [αG], [αHp(R)]) (4) 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) 5. Define the real response rπ such that α =rπ +cπkπ (mod l) The ring signature contains the signature σ(m) = (c1,r 1,r 2,...,r n), the key image ˜K and the ringR. • Verification 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) (6) 3. If c′1 =c1, then the signature is valid. Note that c′1 is the last term calculated. In this scheme we store (1 + n) integers, have one EC key image, and use n public keys. We must checkl ˜K ?= 0 because it is possible to add an EC point from the subgroup of sizeh (the cofactor) to ˜K and, if allci are multiples ofh (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. This is because an EC point multiplied by its subgroup’s order is zero. To be clear, given some point K in the subgroup of order l, some point Kh with order h, and an integer c divisible by h: c∗ (K +Kh) =cK +cKh =ck + 0 11 • 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 in R 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π). 2.2.4 Multilayer Linkable Spontaneous Anonymous Group (ML-SAG) sig- natures In order to sign transactions, one has to sign with multiple private keys. In [NMRL16], 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}fori ∈{ 1, 2,...,n }andj ∈{ 1, 2,...,m } where we know the m private keys{kπ,j} corresponding to the subset{Kπ,j} for some index i = π. 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 ) 2. Generate random number αj ∈R Zl and fake responses ri,j ∈R Zl for i ∈ {1, 2,...,n } (excluding i =π) and j ={1, 2,...,m }. 3. Calculate cπ+1 =Hn(m, [α1G], [α1Hp(Kπ,1)],..., [αmHp(Kπ,m)]) (7) 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],..., [ri,mG +ciKi,m], [ri,mHp(Ki,m) +ci ˜Km]) 5. Define the real response rπ such that rπ,j =αj−cπkπ,j (mod l) The ring signature contains the signatureσ(m) = (c1,r 1,1,...,r 1,m,...,r n,1...,r n,m), the key images ˜K1,..., ˜Km and the ringR. 12 • Verification: 1. For j∈{ 1, 2,...,m }, Check l ˜Kj ?= 0. 2. For i = 1, 2,...,n iteratively compute, replacing n + 1→ 1 c′i+1 =Hn(m, [ri,1G +ciKi,1], [ri,1Hp(Ki,1) +ci ˜K1],..., [ri,mG +ciKi,m], [ri,mHp(Ki,m) +ci ˜Km]) 3. If c′1 =c1, then the signature is valid. Note that c′1 is the last term calculated. • Why it works ? Just as with the original LSAG algorithm, we can readily observe that 1. If i̸=π, then clearly the valuesc′i+1 are calculated as described in the signature algorithm. 2. If i =π then, since rπ,j =αj−cπkπ,j closes the loop rπ,jG +cπkπ,jG = (αj−cπkπ,j)G +cπkπ,jG =αjG and rπ,jHp(Kπ,m) +cπ ˜Kj = (αj−cπkπ,j)Hp(Kπ,j) +cπ ˜Kj =αjHp(Kπ,j) In other words, it holds also that c′π+1 =cπ+1 . • Linkability: If a private keykπ,j is re-used to make any signature, the correspond- ing key image ˜Kj supplied in the signature will reveal it. This observation matches our generalized definition of linkability 2. • Space Requirements In this scheme we store (1 + m∗n) integers, have m EC key images, and use m∗n public keys. 2.3 Stealth Addresses For any crypto transaction, the receiver would have to share their address, either directly to the sender, or on a public forum, thus revealing the details of their transaction. Beldex uses a form of intermediary addresses called stealth addresses to obfuscate the identity of the receiver. Whenever a sender initiates a transaction, the receiver generates a one-time intermediary address and funds are sent to this address. Funds sent to the intermediary address always reflect on the public address. The Diffie-Hellman key exchange enables the receiver to generate a private spend key for their intermediary address. So, they can claim ownership of the funds transferred to this intermediary address [DH76]. Thus, the receivers in a Beldex transaction are protected by a one-time expendable stealth address. 2As with bLSAG, linked MLSAG signatures do not indicate which public key was used to sign it. However, if the linking key image’s sub-loops’ rings have only one key in common, the culprit is obvious. If the culprit is identified, all other signing members of both signatures are revealed since they share the culprit’s indices. 13 2.4 RingCT Protecting transactional confidentiality doesn’t stop with obfuscating the sender and receiver identity. To prevent any time-based analysis of transactions using the amount transferred, The paper [NMRL16], first proposed Ring Confidential Transactions (RingCT) as a means to obfuscate the amount in a transaction. RingCT uses range proofs which employ Pedersen commitments to ensure that the amount transferred can be verified without knowing the actual value, and this range is between 0 and 2 64. If Alice sends an amount x to Bob, she commits a value y and hashes y to the secret x such as H(x||y). Once Bob receives the amount, she can then reveal her secret and Bob can verify that Alice indeed committed the correct outcome y. Thus, with Pedersen commitments, one can ensure that only non-negative values are sent and the actual value is masked. The size of crypto transactions that use traditional range proofs are large, thus, as an alternative, bulletproofs is used to greatly reduce the size of the transaction [BBB +18]. Therefore, to improve transaction scalability, Beldex will utilise a form of bulletproofs to reduce the payload that nodes and masternodes are required to store and transmit. 2.4.1 Pedersen Commitments Generally speaking, a cryptographic commitment scheme is a way of committing to a value without revealing the value itself. For example, in a coin-flipping game Alice could privately commit to one outcome (i.e. ’call it’) before Bob flips the coin by publishing her committed value hashed with secret data. After Bob flips the coin, Alice could declare which value she committed to and prove it by publishing her secret data. Bob could then verify her claim. In other words, assume that Alice has secret string blah and the value she wants to commit to is heads. She could simply hash h =H(blah,heads ) and give h to Bob. Bob flips a coin, Alice tells Bob about blah and informs him she committed to heads, and then Bob calculates h′ =H(blah,heads ). If h′ = h, then he knows Alice called heads before the coin flip. Alice uses the so-called ’salt’ blah so that Bob can‘t just guess H(heads) andH(tails) flip, and figure out she committed to heads. A Pedersen commitment is a commitment that has the property of being additively homomorphic. If C(a) and C(b) denote the commitments for values a andb respectively, then C(a +b) = C(a) + C(b). This property is useful when committing transaction amounts, as one could prove, for instance, that inputs equal outputs, without revealing the amounts at hand. Fortunately, Pedersen commitments are easy to implement with elliptic curve cryptography, as the following holds trivially aG +bG = (a +b)G Clearly, by defining a commitment as simply C(a) = aG, we could easily create cheat tables of commitments to help us recognize common amounts a. To attain information-theoretic hiding, one needs to add a secret blinding factor and another generator H, such that it is unknown for which value of γ the following holds: H =γG. The hardness of the discrete logarithmic problem ensures calculating γ fromH is infeasible. In the case of Beldex, H =Hp(G). We can then define the commitment to an amount a asC(x,a ) =xG +aH, where x is a blinding factor that prevents observers 14 from guessing a (for example: if you just commit C(a = 1), it is trivial to guess and check). Commitment C(x,a ) is information-theoretically private because there are many possible combinations of x and a that would output the same C. If x is truly random, an attacker would have literally no way to figure out amount a. 2.4.2 Amount Commitments Owning cryptocurrency is not like a bank account, where a person‘s balance exists as a single value in a database. Rather, a person owns a bunch of transaction outputs. Each output has an ’amount’, and the sum of amounts in all unspent outputs owned is consid- ered a person’s balance. To send cryptocurrency to someone else, we create a transaction. A transaction references old outputs as inputs and addresses new outputs to recipients. Once an output has been referenced, i.e. ’spent’, it can never be referenced/spent again. Since it is rare for input amounts to equal intended output amounts, most transactions include ’change’, an output that sends excess back to the sender. In Beldex, transaction amounts are hidden using a technique called RingCT, first implemented in September, 2018. While transaction verifiers don‘t know how much Beldex is contained in each input and output, they still need to prove the sum of input amounts equals the sum of output amounts. In other words, if we had a transaction with inputs containing amounts a1,...,a m and outputs with amounts b1,...,b p, then an observer would justifiably expect that: ∑ j aj− ∑ t bt = 0 Since commitments are additive and we don’t know γ, we could easily prove our inputs equal outputs to observers by making the sum of commitments to input and output amounts equal zero ∑ j Cj,in− ∑ t bt,out = 0 To avoid sender identifiability, Shen Noether [NMRL16] proposed verifying that com- mitments sum to a certain non-zero value: ∑ j Cj,in− ∑ t bt,out =zG ∑ j (xjG +ajH)− ∑ t (ytG +btH) =zG ∑ j xj− ∑ t yt =zG The reasons why this is useful will become clear in next chapter when we discuss the structure of transactions. Note that C =zG is called a commitment to zero because we can make a signature with z, which proves that there is noH component toC (assuming γ is unknown). In other words C =zG + 0H. 15 2.4.3 Range proofs One problem with additive commitments is that, if we have commitments C(a1), C(a2), C(b1), and C(b2) and we intend to use them to prove that (a1 +a2)− (b1 +b2) = 0, then those commitments would still apply if one value in the equation were ’negative’ . For instance, we could have a1 = 6,a 2 = 5,b 1 = 21, and b2 =−10. (6 + 5)− (21 +−10) = 0 Where, 21G +−10G = 21G + (l− 10)G = (l + 11)G = 11G The solution addressing this issue in Beldex is to prove each output amount is in a certain range using the Borromean signature scheme. This method treats each bit in the binary representation of the amount as a separate amount which we can commit to zero. Given a commitment C(b) with blinding factor for amount b, use the binary repre- sentation (b0,b 1,...,b k−1) such that b =b020 +b121 +··· +bk−12k−1 Generate random numbersy0,y 1,...,y k−1∈ Zl to be used as blinding factors. Define also Pedersen commitments for eachbi,Ci =yiG+bi2iH and derive public keys{Ci,Ci−2iH} Clearly one of those public keys will equal yiG: • If bi = 0, then Ci =yiG + 0H • If bi = 1, then Ci = 2iH =yiG + 2iH− 2iH =yiG In other words, a blinding factoryi will always be the private key corresponding to one of the points{Ci,Ci− 2iH}. The point that equals yiG is a commitment to zero, because either bi2i = 0 or bi2i− 2i = 0. We can prove a transaction output’s amount b is in the range [0,..., 2− 1] by signing it using the Borromean Ring Signature scheme with the ring of public keys: { {C0,C 0− 20H},..., {Ck−1,Ck−1− 2k−1H}} Where, we know the private keys{y0,...,y k−1} corresponding to each pair. Resulting in a signature σ = (c1,r 0,1,r 0,2,...,r k1,1,rk1,2) 2.4.4 Range proofs in a blockchain In the context of Beldex we will use range proofs to prove there are valid amounts in the outputs of each transaction. Transaction verifiers will have to check that the sum of each output‘s range proof commitments Ci equals its amount commitment Cb. For this to work we need to modify our definition of the blinding factor yb: set y0,...,y k−1∈ Zl and define yb =∑k−1i=0 yi. The following equation now holds k−1∑ i=0 Cb 16 We will store only the range proof commitments/keys Ci, the output amount‘s commit- ment Cb, and the signature σ’s terms in the blockchain. The mining community can easily calculate Ci− 2iH and verify the Borromean ring signature for each output. It will not be necessary for the receiver nor any other party to know the blinding factors yi, as their sole purpose is proving a new output‘s amount is in range. Since the Borromean signature scheme requires knowledge of yi to produce a signature, any third party who verifies one can convince himself that each loop contains a commitment to zero, so total amounts must fall within range and money is not being artificially created. In this scheme we store (1 + 2 ∗k) integers, use k public keys (commitments), and verify with: DVBA Double-variable-base addition for some integersa,b , and pointB :aG+bB[2∗k]. Verifiers need to calculate Ci− 2iH and∑iCi, so verification times include: PA Point addition for some points A,B : A +B[k− 1] PS Point subtraction for some points A,B : A−B[k] KBSM Known-base scalar multiplications for some integer a :aG[k] Beldex uses a special function to compute Ci− 2iH and∑iCi that is supposed to be faster: VRSF Verify range proof special function [k] For a total verification requirement: VRSF Verify range proof special function [k] DVBA Double-variable-base addition for some integersa,b , and pointB :aG+bB[2∗k] 2.5 Beldex Transactions 2.5.1 User Keys Unlike Bitcoin, Beldex users have two sets of private/public keys, ( kv,K v) and (ks,K s) as described in public key cryptography. The address of a user is the pair of public keys (Kv,K s). Her private keys will be the corresponding pair ( kv,ks). Using two sets of keys allows function segregation. The rationale will become clear later in this chapter, but for the moment let us call private keykv is the view key , andks is the spend key . A person can use their view key to determine if an output is addressed to them, and their spend key will allow them to send that output in a transaction (and retroactively figure out it has been spent). 2.5.2 One-time addresses To verify a transfer of money, observers need to know the money starts off being owned by the spender. How do they own it in the first place? Every Beldex user has a public address which they may distribute to other users, who can then send money to that address via transaction outputs. The public address is never used directly. Instead, a Diffie-Hellman-like exchange is applied to it, creating a unique one-time address for each transaction output to be paid to the user. In this way, even external observers who know all users‘ public addresses will not be able to identify which user received any given transaction output. A recipient can spend their received outputs by signing a message with the one-time addresses, thereby 17 proving they know the private keys and must therefore own what they are spending. We will gradually flesh out this concept. Let‘s start with a very simple transaction, containing exactly one input and one output a payment from Alice to Bob. Bob has private/public keys (kvB,ksB) and (KvB,K sB) and Alice knows his public keys. A transaction could proceed as follows: 1. Alice generates a random number r∈ Zl, and calculates the one-time public key Ko =Hn(rKvB)G +KsB (8) 2. Alice sets Ko as the addressee of the payment, adds the valuerG to the transaction data, and submits it to the network. 3. Bob receives the data and sees the valuesrG andKo. He can calculatekvBrG =rKvB. He can then calculate Ks′B =Ko−H n(rkvBG)G. When he sees that Ks′B =KsB, he knows the transaction is addressed to him. The private key ksB is called the view key because anyone who has it (and Bob’s public spend key) can calculate Ks′B for every transaction output in the blockchain (record of transactions), and ’view’ which ones are addressed to Bob. 4. The one time keys for the output are: Ko =Hn(rKvB)G +KsB = (Hn(rKvB) +ksB)G ko =Hn(rKvB) +ksB While Alice can calculate the public key Ko for the one-time address, she cannot compute the corresponding private key ko, since it would require either knowing Bob‘s spend keykBs , or solving the discrete logarithm problem forKsB =ksBG, which we assume to be hard. As will become clear later in this chapter, 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. A third party with Bob‘s view key can verify an output is addressed to Bob, yet without knowledge of the spend key this third party would not be able to spend that output nor know when it has been spent. Such a third party could be a trusted custodian, an auditor, a tax authority, etc. Somebody who could be allowed read access to the user‘s transaction history, without any further rights. This third party would also be able to decrypt the output‘s amount (to be explained in Section ??). 2.5.3 Multi-output transactions Most transactions will contain more than one output. If nothing else, to transfer ’change’ back to the sender. Beldex senders generate only one random value r. The value rG is normally known as the transaction public key and is published in the blockchain. To ensure that all output addresses in a transaction with p outputs are different even in cases where the same addressee is used twice, Beldex uses an output index. Every output from a transaction has an index t ∈ {1,...,p }. By appending this value to 18 the shared secret before hashing it, one can ensure the resulting one-time addresses are unique: Kot =Hn(rKvt,t )G +Kst = (Hn(rKvt,t ) +kst )G kot =Hn(rKvt,t ) +kst 2.5.4 Sub-addresses Beldex users can generate subaddresses from each address. Funds sent to a subaddress can be viewed an
프로젝트로 돌아가기