资源描述：
Con dential AssetsAndrew Poelstra, Adam Back, Mark Friedenbach, Gregory Maxwell, andPieter WuilleBlockstreamfapoelstra, adam, mark, gmaxwell, Abstract. Bitcoin is an online distributed ledger in which coins aredistributed according to the unspent transaction output UTXO set, andtransactions describe changes to this set. Every UTXO has associated toit an amount and signature veri cation key, representing the quantitythat can be spent and the entity authorized to do so, respectively.Because the ledger is distributed and publicly veri able, every UTXOand the history of all changes is publicly available and may be used foranalysis of all users’ payment history. Although this history is not directlylinked to users in any way, it exposes enough structure that even smallamounts of personally identi able ination may completely breakusers’ privacy. Further, the ability to trace coin history creates a marketfor \clean coins, harming the fungibility of the underlying asset.In this paper we describe a scheme, con dential transactions, whichblinds the amounts of all UTXOs, while preserving public veri abilitythat no transaction creates or destroys coins. This removes a signi cantamount of ination from the transaction graph, improving privacyand fungibility without a trusted setup or exotic cryptographic assump-tions.We further extend this to con dential assets, a scheme in which a singleblockchain-based ledger may track multiple asset types. We extend con-dential transactions to blind not only output amounts, but also theirasset type, improving the privacy and fungibility of all assets.1 IntroductionDeployed in 2009, Bitcoin [16] is an online currency with no trusted issuer ortransaction processor, which works by means of a publicly veri able distributedledger called a blockchain. The blockchain contains every transaction since itsinception, resulting in a nal state, the unspent transaction output set UTXOset, which describes the amounts and owners of all coins.Each UTXO contains an amount and a veri cation key; transactions destroyUTXOs and create new ones of equal or lesser total amount, and must be signedwith the keys associated to each destroyed UTXO. This model allows all usersto verify transaction correctness without trusting any payment processor to behonest or reliable. However, this model has a serious cost to user privacy, sinceevery transaction is preserved forever, exposing signi cant amounts of ina-tion directly and indirectly [10].2One suggestion to obscure transaction structure is CoinJoin [13], which allowsusers to interactively combine transactions, obscuring which s map to whichoutputs. However, because transaction amounts are exposed, it is di cult to useCoinJoin in such a way that these mappings cannot be recovered, at least in astatistical sense [20]. In particular, unless all output amounts are the same, theyare distinguishable and may be grouped.We propose a partial solution to the exposure of transaction data, whichblinds the amounts of all outputs, while preserving public veri ability of the factthat the total output amount is equal to the total amount. This solution,termed con dential transactions, has been described inally by Maxwell [14]and deployed on the Elements Alpha sidechain [2] for over a year. In brief,each explicit UTXO amount is replaced by a homomorphic commitment to theamount. Since these amounts are homomorphic over a nite ring rather than theset of integers, we also attach a rangeproof to each output to prevent attacksrelated to over ow.First, we alize and improve con dential transactions, describing a spaceoptimization of the underlying ring signature used in Elements Alpha. Thenwe extend con dential transactions to a new scheme, con dential assets, whichfurther supports multiple asset types within single transactions. We retain publicveri ability that no assets are created or destroyed, while hiding both the outputamounts and the output asset types.Related Work. Multi-asset blockchains were described in 2013 in Friedenbachand Tim on’s Freimarkets [8], though the supported assets were not con dential;that is, the amounts and asset tags of all s and outputs of transactions arepublicly visible.Support for asset issuance on top of Bitcoin has been proposed by means ofcolored coins [12], a scheme in which individual coins are marked in such a waythat they are identi able as representing distinct asset types. In e ect, it worksby exploiting Bitcoin’s imperfect fungibility.Ethereum [22] directly supports asset issuance using its smart contractinglanguage, and has a standard means to do so which ensures interoperabilitywith supporting software [18]. Like the above schemes, no attempt is made toobfuscating either the asset types or their amounts.ZCash [21] is a recently announced cryptocurrency project which supportsblinding of amounts, as well as any other identifying ination about trans-action s and outputs. It does not support multiple assets, though its useof zk-SNARKs [3], which are general-purpose zero-knowledge arguments, meanthat asset support would not be a di cult extension.However, ZCash’s privacy comes at a signi cant cost the underlying SNARKsuse a trusted setup, meaning it is initialized by multiple parties who are ableto collude to silently in ate the currency; it relies on novel cryptographic as-sumptions; its zero-knowledge proofs are very slow to compute. To contrast, thescheme described in this paper relies only on elliptic curve discrete logarithmECDL being hard and the random oracle model, and all computations involvefew and standard elliptic curve operations e.g. no pairings.3Acknowledgements. We thank Ben Gorlick for his on the practical re-quirements of a con dential assets-based system, and his technical review, andfeedback on the systems design.2 PreliminariesDe nition 1. We de ne a Bitcoin transaction as the following data{ A list of outputs, containing a veri cation key and an amount.{ A list of s, which are unambiguous references to the outputs of othertransactions. These also have signatures using the veri cation keys of theirrespective outputs.{ A fee, which is computed as the total amount minus the total outputamount, and is captured by the network.To bootstrap the system, we also need coinbase transactions, which have out-puts but no s; for the purpose of this paper they can be considered astransactions with negative fee.In Bitcoin, all amounts are explicit, and for a non-coinbase transactionto be valid, it must have a non-negative fee as well as valid signatures of thetransaction with all s’ veri cation keys.We will replace these explicit amounts with homomorphic commitments, forwhich we need the following de nitions.De nition 2. Given a message space M Zq, commitment space C’M andpublic parameters space PP, we de ne a homomorphic commitment scheme asa triple of algorithms{ Setup PP{ Commit PP M MC,{ Open PP M M Cftrue;falsegsatisfying, for pp Setup,{ for all m;r2M M, Openpp;m;r;Commitpp;m;r accepts; and{ ipp;m1;r1;C1 and Openpp;m2;r2;C2both accept, thenOpenpp;m1 m2;r1 r2;C1 C2also accepts.We will often leave pp implicit and not mention it as an to Commitor Open. Unless otherwise speci ed, all theorems are understood to hold for allpp2PP.4We further require our commitments be binding and hiding, by which we meanthe following.De nition 3. A commitment is perfectly binding if for all m6 m02M, allr;r02M, Openm;r;Commitm0;r0 rejects.It is computationally binding if for all p.p.t. adversariesA, the probability ofA producing m0;r0 with m06 m such that Openm;r;Commitm0;r0 acceptsis negligible.De nition 4. A commitment scheme is perfectly, statistically, computation-ally hiding if given pp and m16 m2, the distributionsU1 fC C Commitpp;m1;r;r MgU2 fC C Commitpp;m2;r;r Mgare equal, statistically indistinguishable, computationally indistinguishable.For the purposes of this paper, we will use Pedersen commitments, whichare computationally binding, perfectly hiding homomorphic commitments [17].They are de ned as follows.De nition 5. The Pedersen commitment scheme is the following triple of algo-rithms. We takeM Zq andC to be an isomorphic elliptic curve group; furtherH is a point-valued hash function modeled as a random oracle.{ Setup takes a cyclic group with distinguished generator G, G as well asauxiliary . It computes H H and outputs pp fG;G;Hg.{ Commitm;r outputs mH rG.{ Openm;r;C accepts i C mH rG.The original Pedersen scheme uses unily random generators G, H, ratherthan taking H as the output of a hash function. In the random oracle model,these are equivalent.In order to commit to transaction amounts, which are integers, we will needto represent them as elements of M Zq, which will complicate matters sinceevery multiple of q will be indistinguishable from zero. To avoid problems, wewill need one more primitive.De nition 6. Given a homomorphic commitment scheme as above, and 0 A B q, we de ne a rangeproof of the range [A;B] as a pair of randomizedalgorithms{ Prove[A;B]PP MC M S takes a value and generates a commitmentto that value with opening ination and an associated rangeproof.{ Verify[A;B] PP C Sftrue;falseg takes a commitment and rangeproofand either accepts or rejects it.5where S represents the space of possible rangeproofs. We require that for allv2[A;B], C;r; Prove[A;B]v that bothVerify[A;B]C; and Openv;r;Caccept.We require the following security properties of rangeproofsDe nition 7. Proving. Let 0 A B q. Then a rangeproof scheme isproving an amount in the range [A;B] if for any p.p.t. algorithm A that outputsC; 2C S such that VerifyC; accepts, a simulator B exists which givenoracle access to A can produce v;r such that v 2 [A;B] and Openv;r;Caccepts.We observe that since the commitment scheme is binding, an opening to anamount in [A;B] precludes an opening to any amount outside of [A;B].In light of De nition 7, given a commitmentC with valid rangeproof , we cantalk about \the opening ination v;r of C unambiguously in simulation-based proofs, even without knowledge of it since this knowledge can in principlebe obtained by the simulator. In particular, any security proof which requiresan adversary to produce opening ination of commitments will continue tohold if the opening ination is replaced by rangeproofs.De nition 8. Statistical zero-knowledge. Given pp 2 PP and two valuesv1;v22[A;B], the following distributions are identicalfC; C; ; Prove pp;v1gfC; C; ; Prove pp;v2g3 Con dential transactions3.1 RangeproofsWe begin by describing an e cient rangeproof for Pedersen commitments overthe interval [0;mn 1], which has total size proportional to 1 nm, using avariant of a folklore bit-decomposition based rangeproof, in which numbers areexpressed in base m and each digit is proven to lie in [0;m 1] using a ringsignature.We use a variant of Borromean Ring Signatures [15], which itself is a variantof the Abe-Ohkubo-Suzuki ring signature [1], tweaked to exploit the fact thatmany small rings of related keys are used.Unlike some other rangeproofs in the literature [6], ours does not require atrusted setup 1. In fact, the only cryptographic assumption it relies on is the1 While our rangeproof does require setup, the only generated parameters are uni-ly random curvepoints, which can be generated with no possibility of trapdoorination, e.g. by the algorithm by Fouque and Tibouchi [7]6hardness of discrete logarithm in the random oracle model. Nor is it interactive,as is the scheme described in [5]. Despite these improvements, our scheme stillproduces smaller proofs than these papers for the ranges 30-80 bits that weare interested in.Schoenmakers [19] described a simple rangeproof of base-b digits using theconjuction of zero-knowledge OR proofs of each digit. Our work is based on thisrangeproof with the following changes our OR proofs are based on BorromeanRing Signatures, which allow sharing a random challenge across every digit’sproof, and we remove one scalar from each proof by a novel trick in which wemay change the commitment to each digit without changing the digit itselfwhile we produce the proof.De nition 9. Back-Maxwell Rangeproof Consider a Pedersen commitmentscheme with generators G, H, and let HCM be a random oracle hash.{ Verify C; e0; C0;s01;s02;;s0m 1 ; Cn 1;sn 11 ;sn 12 ;;sn 1m 1 works as follows1. For each i2f0;;n 1g,a De ne ei0 e0 for consistency of the following equations.b For each j2f1;;m 1g, computeeij H sijG eij 1 Ci jmiH 1c Compute Ri eim 1Ci.2. Compute e0 HR0k kRn 1.3. Accept i e0 e0; andC PiCi.{ Provev;r Proving works as follows.1. Write v in base m as v0v1m vn 1mn 1. Note that superscriptson m are exponents while superscripts on v are just superscripts.2. For each i2f0;;n 1g,a If vi 0, choose ki0 Zq and set Ri ki0G.b Otherwise,i. Choose ri unily randomly and compute Ci Commitmivi;ri.ii. Choose ki Zq and compute eivi HkiG.iii. For each j2fvi1;;m 1g, choose sij Zq, and compute eijdirectly from equation 1. If vi m 1, this step is a no-op.iv. Compute Ri eim 1Ci.3. Set e0 HR0k kRn 1.4. For each i2f0;;n 1g,a If vi 0,i. For each j2f1;;m 1g, choosekij Zqeij Hkij eij 1mijHtaking ei0 e0.7ii. Set Ci Rieim 1 ki0eim 1G.iii. For each j2f1;;m 1g, set sij kij ki0eij 1eim 1 .b Otherwise,i. For each j 2f1;;vi 1g, choose sij Zq, and compute eijdirectly from equation 1, taking ei0 e0. If vi 1 this is ano-op.ii. Set sivi ki eivi 1ri.5. Set C Pn 1i0 Ci. Output e0; C0;s01;s02;;s0m 1 ; Cn 1;sn 11 ;sn 12 ;;sn 1m 1 We observe that this is nearly the same construction as Borromean Ring Signa-tures except for the following two di erences{ There are no si0 values, which were used in the calculation of e0 in theBorromean Ring Signature construction, saving i scalars in the total proof.{ The commitments Ci are no longer included in any hashes which is neces-sary when computing sub-commitments to the digit m 1, as seen in step4aii of the Prove algorithm.Unfortunately, the resulting construction is no longer a secure ring signaturein general; the proof of security depends on all keys being binding commit-ments rather than arbitrary public keys.It is immediate that the above construction is a correct rangeproof. We arguesecurity in the next two theorems.Theorem 1. If the underlying commitment scheme is binding in the sense ofDe nition 3, then the above construction is a proving rangeproof in the sense ofDe nition 7.Proof. Let C; be generated by some p.p.t. algorithmA, such that VerifyC; accepts. Write e0; C0;s01;s02;;s0m 1 ; Cn 1;sn 11 ;sn 12 ;;sn 1m 1 By Theorem 8 in Appe
展开阅读全文