Con dential AssetsAndrew Poelstra, Adam Back, Mark Friedenbach, Gregory Maxwell, andPieter WuilleBlockstreamfapoelstra, adam, mark, gmaxwell,

[email protected] 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 UTXO(and 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 information 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 information 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 informa-tion directly and indirectly [10].2One suggestion to obscure transaction structure is CoinJoin [13], which allowsusers to interactively combine transactions, obscuring which inputs 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 input amount. This solution,termed con dential transactions, has been described informally 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 formalize 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 outputamount(s) and the output asset type(s).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 inputs 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 information about trans-action inputs 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 logarithm(ECDL) 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 input 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 inputs, 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 input 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 inputs; 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 inputs’ 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 M!C,{ Open: PP M M C!ftrue;falsegsatisfying, for pp Setup,{ for all (m;r)2M M, Open(pp;m;r;Commit(pp;m;r)) accepts; and{ ifOpen(pp;m1;r1;C1) and Open(pp;m2;r2;C2)both accept, thenOpen(pp;m1 +m2;r1 +r2;C1 +C2)also accepts.We will often leave pp implicit and not mention it as an input 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, Open(m;r;Commit(m0;r0)) rejects.It is computationally binding if for all p.p.t. adversariesA, the probability ofA producing (m0;r0) with m06= m such that Open(m;r;Commit(m0;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 Commit(pp;m1;r);r $ MgU2 =fC : C Commit(pp;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 input . It computes H =H( ) and outputs pp =fG;G;Hg.{ Commit(m;r) outputs mH +rG.{ Open(m;r;C) accepts i C = mH +rG.(The original Pedersen scheme uses uniformly 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 M!C M S takes a value and generates a commitmentto that value with opening information and an associated rangeproof.{ Verify[A;B]: PP C S!ftrue;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 Open(v;r;C)accept.We require the following security properties of rangeproofs:De 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 outputs(C; )2C S such that Verify(C; ) accepts, a simulator B exists which givenoracle access to A can produce (v;r) such that v 2 [A;B] and Open(v;r;C)accepts.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 information (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 information of commitments will continue tohold if the opening information is replaced by rangeproofs.De nition 8. (Statistical zero-knowledge.) Given pp 2 PP and two valuesv1;v22[A;B], the following distributions are identical:f(C; ) : (C; ; ) Prove (pp;v1)gf(C; ) : (C; ; ) Prove (pp;v2)g3 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-formly random curvepoints, which can be generated with no possibility of trapdoorinformation, 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 itself)while we produce the proof.De nition 9. (Back-Maxwell Rangeproof) Consider a Pedersen commitmentscheme with generators G, H, and let H:C!M be a random oracle hash.{ Verify C; = e0; C0;s01;s02;:::;s0m 1 ;::: Cn 1;sn 11 ;sn 12 ;:::;sn 1m 1 works as follows:1. 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 (1)(c) Compute Ri eim 1Ci.2. Compute ^e0 H(R0k kRn 1).3. Accept i :^e0 = e0; andC = PiCi.{ Prove(v;r): Proving works as follows.1. Write v in base m as v0+v1m+ +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 uniformly randomly and compute Ci Commit(mivi;ri).ii. Choose ki $ Zq and compute eivi H(kiG).iii. For each j2fvi+1;:::;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 H(R0k kRn 1).4. For each i2f0;:::;n 1g,(a) If vi = 0,i. For each j2f1;:::;m 1g, choosekij $ Zqeij H(kij +eij 1mijH)taking ei0 = e0.7ii. Set Ci Ri=eim 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 1i=0 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 step4(a)ii 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 Verify(C; )accepts. Write= e0; C0;s01;s02;:::;s0m 1 ;::: Cn 1;sn 11 ;sn 12 ;:::;sn 1m 1 :By Theorem 8 in Appe