Privacy Protection for Blockchains with Account and Multi-Asset Model

Donghui Ding ,Kang Li,Linpeng Jia ,Zhongcheng Li ,Jun Li ,Yi Sun ,＊

1 Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China

2 State key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China

3 University of Chinese Academy of Sciences,Beijing 100049,China

4 Ant Financial Services Group,Hangzhou 310012,China

Abstract: The blockchain technology has been applied to wide areas.However,the open and transparent properties of the blockchains pose serious challenges to users' privacy.Among all the schemes for the privacy protection,the zero-knowledge proof algorithm conceals most of the private information in a transaction,while participants of the blockchain can validate this transaction without the private information.However,current schemes are only aimed at blockchains with the UTXO model,and only one type of assets circulates on these blockchains.Based on the zero-knowledge proof algorithm,this paper proposes a privacy protection scheme for blockchains that use the account and multi-asset model.We design the transaction structure,anonymous addresses and anonymous asset metadata,and also propose the methods of the asset transfer and double-spending detection.The zk-SNARKs algorithm is used to generate and to verify the zero-knowledge proof.And finally,we conduct the experiments to evaluate our scheme.

Keywords: blockchain; privacy protection;zero-knowledge proof algorithm; account and multi-asset model

I.INTRODUCTION

In 2008,Satoshi Nakamoto proposed Bitcoin,which for the first time used the blockchain technology to implement an electronic currency system without the involvement of third parities [1].Blockchains enable participants to maintain a transparent ledger,and to safely transfer the electronic assets.Nowadays,blockchains have been used in wide areas such as banks and supply chains.

However,blockchains pose challenges to users' privacy.All transactions are recorded into the blockchain,and each participant maintains a complete replica of the blockchain.The private information in a transaction is thus exposed to all participants.Current research has analyzed users' behaviour by tracking the transactions,and even mapped the addresses in transactions into real entities [2][3].

Aimed at this problem,various schemes are proposed.Among all schemes,the zero-knowledge proof algorithm conceals most private information in a transaction.Each participant can validate the transaction without such information.

ZCash [4]is the most mature blockchain that uses the zero-knowledge proof algorithm.This blockchain is built on the UTXO model,and only a single type of assets circulates on ZCash blockchain.When assets are spent on ZCash,a transaction with multiple inputs and outputs is constructed.These inputs consume assets in previous transactions' outputs,while assets in the newly-generated outputs can be used by future transactions.Such transactions can realize the conversion between transparent assets and anonymous assets at a 1:1 rate.

However,blockchains with the account and multi-asset model have appeared in recent years.The state of a blockchain with this model is organized by a series ofaccounts.Assets spent by a transaction are from the sender's account instead of other transactions'outputs.Therefore,the transaction structure of this model is different from that of the UTXO model.Since the scheme based on the zero-knowledge proof algorithm is tightly coupled with the transaction structure,the scheme of ZCash is incompatible with the account and multi-asset model.

In addition,this model contains different assets with various types.So it is necessary to ensure the conversion between the same type of anonymous and transparent assets,and the transfer of the same type of anonymous assets.

Based on the zero-knowledge proof algorithm,we design a privacy protection scheme for blockchains that use the account and multi-asset model.The sender,receiver,and amount in a transaction are concealed,and all participants can validate a transaction without such information.

II.RELATED WORK

Various privacy protection schemes for blockchains have been proposed.Dashcoin [5]cuts off the relation between the senders and receivers by the CoinJoin technology [6],but causes potential centralization problems.Monero [7]conceals senders' addresses using the ring signature technology,but the transaction amounts are still exposed to the public.Stealth Address [8]uses one-time addresses to receive assets and thus protects the receivers'privacy,but fails to conceal the transaction senders.Fabric [9]and Corda [10]limit the identities of participants that can access the transactions,but at the expense of the global consistency of the blockchain data.The homomorphic encryption [11]is also used to protect users' privacy [12],but it suffers from the low efficiency.

Recently,the zero-knowledge proof algorithm has attracted increasing attentions,by which one party can prove to the other party that a statement is correct without revealing other extra information [13].In all congeneric algorithms,the zk-SNARKs algorithm [14][15]is the most practical one because it uses a succinct character string rather than complex interactions to finish the proof procedure.This character string is defined as the “zero-knowledge proof ”.

Zerocoin [16]firstly applied the zero-knowledge proof algorithm to the blockchain.ZCash improves Zerocash,and conceals most private information in transactions including the senders,receivers and amounts.However,ZCash is only fit for the UTXO and single-asset model.

III.VERIFICATION RULES FOR SHIELDED TRANSACTIONS

A shielded transaction realizes the conversion between transparent assets and anonymous assets,or transfers anonymous assets between different accounts.Shielded transactions conceal information including the senders,receivers and amounts,and thus protect users'privacy.All blockchain nodes run the verification rules for shielded transactions,and reach consensus based on these rules.

Verification rules are required to verify the existence and ownership of the assets spent by the transaction senders.Furthermore,the rules should ensure the safe transfer of assets,and detect double-spending behaviors.Aimed at these issues,the rules that we design include the structure of the shielded transaction,the anonymous address of the account,the metadata of the anonymous asset,the transfer of anonymous assets,and the anti double-spending mechanism.

3.1 Structure of the shielded transaction

As is shown in TableI,the structure of a shielded transaction in our system contains following fields.

nonceThe number of transactions sent by the account of the sender.It is used to prevent replay attacks.

senderThe account address of the sender.When the transaction is used to transfer anonymous assets,this field is set to zero.

receiverThe account address of the receiver.When the transaction is used to transfer anonymous assets,this field is set to zero.

assetIDThe type of the assets to be transferred.

in_valueThe amount of transparent assets spent by the sender.

out_valueThe amount of transparent assets received by the receiver.

vAggreSegThe description of anAggreSeg(aggregated segment),which is the basic unit that describes how anonymous assets are generated or transferred in a shielded transaction.

nAggreSegThe number ofvAggreSegsin a shielded transaction.

aggreSegSigIn order to ensure eachvAggreSegis correlated with a single shielded transaction and can not be replayed by malicious transactions,the sender generates a key pair for each shielded transaction,and signs this transaction excepttxSig.

aggreSegPubKeyThe temporary public key used to verifyaggreSegSig.

txSigThe signature of the whole transaction.It is used to verify the account address of the sender,and is concealed when the shielded transaction is used to transfer anonymous assets.

In our system,thevAggreSegis represented by a C++ classAggreSegDesc.The structure is shown in TableII.

vpub_oldandvpub_newThe amounts oftransparent assets thisvAggreSegspends and generates.Both of these fields can be set to zero.

TableI Structure of shielded transaction.

TableII.Structure of vAggreSeg.

anchorA Merkle tree root.It is used to verify the existence of the anonymous asset spent by thisvAggreSeg.More details are discussed in the section 3.3.

assetIdThe type of the anonymous asset spent by thisvAggreSeg.

sequenceA serial number assigned to the asset to be spent.It is used to prevent double-spending behaviors.More details are discussed in the section 3.5.

commitments[2]The commitments for newly-generated anonymous assets.The design of the commitments is discussed in the section 3.3.

ephemeralKeyA temporary public key based on Curve25519,which is used to nego-tiate a symmetric key between the sender and receiver.

randomSeedA 256-bit random value,which is used to calculate the sequences of newly-generated assets.More details are discussed in the section 3.5.

zkproofThe zero-knowledge proof of thisvAggreSeg.

encCiphertexts[2]The encrypted metadata of the newly-generated assets.More details are discussed in the section 3.3 and section 3.4.

Fig.1.Proportion distribution chart for Bitcoin transactions.

Since the zk-SNARKs algorithm needs parameters with fixed sizes,it is necessary to determine the number of anonymous assets to be spent and the number of newly-generated assets in avAggreSeg.We find that the usage characteristics of anonymous assets are similar to those of UTXOs in Bitcoin.Therefore,we analyzed all 312252902 Bitcoin transactions from January 2009 to April 2018,and counted the number of inputs and outputs of each transaction.The proportion distribution chart is shown in figure 1.(a) is the chart for transaction inputs,and shows that transactions with 1 input account for the majority of all transactions.(b) is the chart for transaction outputs,and shows that after 2011 transactions with 2 outputs account for the majority of all transactions.

Based on the above analysis,eachvAggre-Segspends one anonymous asset,and generates two new anonymous assets.If the number of assets to be spent is greater than 1,multiplevAggreSegscan be contained in a shielded transaction.The spending and generation of anonymous assets are discussed in the section 3.4 and section 3.5.

3.2 Anonymous addresses of the account

An anonymous address consists of the payment private keyask,payment public keyapk,communication private keyskencand communication public keyskpub.The payment keysaskandapkare used to verify the sender's ownership of an anonymous asset,and the communication keysskencandskpubare used to encrypt the metadata of anonymous assets.

Current asymmetric cryptography is complex and unfit for the zero-knowledge proof algorithm,so Equation 1 is used to deduceapkfromask.

In Equation 1,SHA256Compress is a hash function.The inputs of this function are two 256-bit values,and the output is one 256-bit value.The payment private keyaskis a 252-bit random value selected by the user.Since SHA256Compress is used for the generation of multiple parameters such asapkandskenc,a prefix “1100” is added toaskto distinguish different usages of SHA256Compress.

The relation betweenaskandapkis encoded into the zero-knowledge proof.The blockchain nodes validate the zero-knowledge proof to judge whetherapkis deduced fromask.The ownership of an anonymous asset is thus verified.

By Curve25519 algorithm,skencandskpubare used to negotiate a symmetric key that encrypts the metadata of anonymous assets.Given Equation 1,2 and 3,apk,skencandskpubcan be deduced fromask,so the user only needs to maintainask.The details of Equation 2 and 3 are introduced in the paper [17].

3.3 Metadata of the anonymous asset

The metadata defines the structure of an anonymous asset,and contains following fields.

Payment Public Keyapk.It is used to identify the ownership of this asset.

Value.Although the number of assets that avAggreSegcan spend and generate is fixed,an arbitrary value can be assigned to an asset as long as the double-spending behaviour is not triggered.This ensures the flexibility of the transaction amounts.

Sequence Factorρ.It is used to generate a unique sequence for this asset.

Commitment Factorr.It is a random value,and adds randomness to the commitment so the security is improved.

id.It is the type of this anonymous asset.

When an anonymous asset is spent,the first problem is how to represent the asset without disclosing the private information.We use thecommitment(cm) to represent an anonymous asset.The generation ofcmis shown in Equation 4.

The sender encodes the commitment,the metadata and the relation between them (i.e.,Equation 4) into the zero-knowledge proof.A blockchain node can thus verify whether a given commitment is generated by this anonymous asset.

The second problem is how to verify the existence of an anonymous asset.Aimed at this problem,a blockchain node organizes all existing commitments into a Merkle tree.Since anonymous assets are ceaselessly generated,the Merkle tree is constantly updated.When an asset is spent,the corresponding Merkle tree rootrtis put into thevAggreSeg(i.e.,anchor).The sender encodesrt,the commitment for the asset to be spent,the Merkle branch of this commitment,and the verification rules of the Merkle tree [18]into the zero-knowledge proof.A blockchain node checks the existence ofrtand verifies the zero-knowledge proof so the existence of an anonymous asset is proved.

3.4 Asset transfer mechanism

EachvAggreSegdisables an old anonymous asset,and generates two new anonymous assets.In most cases,one of the new anonymous assets is sent to the receiver,and the other acts as the sender's change.The destruction of the old asset is used to prevent double-spending behaviors,and is discussed in the section 3.5.The commitments for the new assets are put into thevAggreSeg(i.e.,commitments[2]),by which blockchain nodes can generate the new Merkle tree.The relation between the metadata of new assets and the commitments for new assets is encoded into the zero-knowledge proof.

The sender encrypts the metadata of the new assets using the key generated by Curve25519 [17],and puts the ciphertext into thevAggreSeg(i.e.,encCiphertexts[2]).The receiver tries to decrypt the cyphertext of each shielded transaction in the network,and puts the new anonymous assets into the wallet if the corresponding cyphertext can be decrypted.

3.5 Anti double-spending mechanism

A unique sequence is assigned to each anonymous asset.The generation of the new sequence(i∈{0,1}) is shown in Equation 5,6 and 7.

snoldis the sequence of the asset spent by thisvAggreSeg,φis a random value selected by the sender,andBLAKE2b-256 is a hash function proposed in the paper [19].Sincesnoldis a unique value,sninewdeduced fromsnoldis unique.

No anonymous assets exist at the beginning.In this case,new anonymous assets are generated from transparent assets.ThevAggreSegwill spend an “initial” anonymous asset withvalue= 0.The sequence of the “initial”asset is set randomly,so the sequences of new assets are generated.

Algorithm 1 shows the anti double-spending mechanism.Each blockchain node maintains a setsnSet,which contains all existing anonymous assets' sequences.A shielded transaction contains the sequences of the assets to be spent (i.e.,sequence in thevAggreSeg).For each shielded transaction,a blockchain node verifies whether any of the sequences has been present insnSet.If so,a potential double-spending behaviour is detected so the transaction is rejected.By contrast,if the shielded transaction is valid,these sequences will be added intosnSet.

Algorithm 1.Anti Double-Spending Mechanism.1: function verifyTransaction(tx)2: for all i∈{1···tx.nAggreSeg} do 3: if tx.vAggreSeg[i].sequence∈snSet then 4: return “Double Spending”5: end if 6: end for 7: Do Other Verifications 8: updateSnSet(tx)9: return “Transaction Received”10: end function

IV.GENERATION AND VERIFICATION OF ZERO-KNOWLEDGE PROOF

We use the libsnark library [20]to generate and to verify the zero-knowledge proof.The technology behind the libsnark library is the zk-SNARKs algorithm.

4.1 Public parameter initialization

The zk-SNARKs algorithm needs two public parameters before usage: the proving key and the verifying key.The sender uses the proving key to generate the zero-knowledge proof,and the blockchain nodes use the verifying key to verify the zero-knowledge proof.The libsnark library utilizes the elliptic curve cryptography based on thealt_bn128to generate the public parameters.

4.2 Generation of zero-knowledge proof

The generation of zero-knowledge proof is shown in figure 2.The plaintext input is known by the sender and other blockchain nodes,and is represented by thevAggreSeg.The auxiliary input is only known by the sender.TableIII shows the structure of the auxiliary input.

4.3 Verification of Zero-Knowledge Proof

As is shown in figure 3,a blockchain node verifies the zero-knowledge proof using the verifying key and the plaintext input.

If the zero-knowledge proof is valid,it proves that:

- The asset to be spent exists in the blockchain system.

- The sender has the ownership of the asset to be spent.

- The sequence of the asset to be spent is valid.

-ρinewin each newly-generated assetassetinewis valid.

- The commitment for each newly-generated assetassetinewis valid.

- The type of the asset to be spent,the type of the newly-generated assets,and the assetId in thevAggreSegare the same.

- The balance of payment is ensured.In other words,Equation 8 is satisfied,whereandare the values of vpub_old and vpub_new in thevAggreSeg,valueoldis thevalueofassetold,andis thevalueof

V.IMPLEMENTATION AND EXPERIMENTS

In this section,we will first introduce our development environment,and then introduce the initialization and verification of a shielded transaction.Finally,we will describe our experiments and give the experiment results.

5.1 Environment for Implementation

Our system is developed by C++,and the environment is shown in TableIV.It is developed on Ubuntu 16.04,but can run on most Linux versions.Furthermore,it relies on rocksdb[21],an open-source Key-Value database,to store the state of the blockchain account.

5.2 Initialization and Verification of a Shielded Transaction

When a shielded transaction is initialized,a request is sent to the wallet through RPC (Remote Procedure Call),and anonymous assets are searched in the wallet.For example,Alice transfers anonymous assets to Bob and Carl,and the values to be transferred are 10 and 8.Assume an asset with value = 20 is selected,and twovAggreSegsare constructed shown in figure 4.The asset back to Alice in the firstvAggreSegis used by the secondvAggreSeg.After the anonymous assets are selected,the zero-knowledge proof is generated and packed into the shielded transaction.Finally,the shielded transaction is broadcast to the network.

Each blockchain node monitors the transactions in the network.When it receives ashielded transaction,it first detects the double-spending behaviour as is explained in the section 3.5,and then verifies the existence of the Merkle tree root contained in eachvAggreSeg.At last,the node verifies the zero-knowledge proof.If the transaction is valid,the corresponding blockchain accounts will be updated and persisted to the rocksdb.

TableIII.Structure of auxiliary input.

TableIV.System development environment.

Fig.2.Generation of zero-knowledge proof.

Fig.3.Verification of zero-knowledge proof.

Fig.4.vAggreSegs in the shielded transaction.

5.3 Experiments

We evaluated our system by experiments under the environment in TableIV.Following are the detailed steps of our experiments.

Fig.5.Initial state of 10 accounts in the blockchain.

Fig.6.State of two accounts after the experiments.

- Step1.200 accounts with anonymous addresses were generated,and then we allocated transparent assets of the type0x01and0x02to each account.The accounts were sorted based on their anonymous addresses,and the initial state of 10 accounts is shown in figure 5.

- Step2.Each of the first 100 accounts transferred anonymous assets of the type =0x01to the last 100 accounts.And then,each of the last 100 accounts transferred anonymous assets of the type =0x02to the first 100 accounts.Since no anonymous assets existed before Step2,the anonymous assets to be transferred were converted from the transparent assets.

- Step3.Each of the first 100 accounts transferred anonymous assets of the type =0x02to the last 100 accounts.And then,each of the last 100 accounts transferred anonymous assets of the type =0x01to the first 100 account.

Thevalueof each anonymous asset transferred in Step2 and Step3 was set randomly.400 shielded transactions were generated in the network after the above three steps,and each shielded transaction contained onevAggreSeg.One of the anonymous asset in avAggreSegwas transferred to another account,and the other asset was given back to the sender as the change.

The state of two accounts after the experiments is shown in figure 6.The size of the sequence set was 400,which was equal to the number of shielded transactions.Each account held 4 anonymous assets because it sent and received 4 shielded transactions.In addition,since the commitments for all anonymous assets were organized into a single Merkle tree,the Merkle tree root of each anonymous asset is the same.

In order to evaluate the influence of our scheme on the blockchain performance,we measured the time for zero-knowledge proof generation and verification.

The zero-knowledge proof generation time for all 400 shielded transactions is shown in figure 7.This time was maintained at 60 to 70 seconds.The generation procedure took a long time,because the zk-SNARKs algorithm involved hundreds of thousands of times of polynomial multiplication.The libsnark library uses the Bos-Coster algorithm [22]to reduce the computational complexity,but this complexity cannot be reduced to the constant time.

The zero-knowledge proof is generated during the construction of a new shielded transaction.This generation procedure has been completed before the transaction is broadcast into the network,so it can not influence the transaction processing efficiency of the blockchain.Nevertheless,this delay may reduce the user experience,so we will design more efficient generation algorithms in our future work.

The zero-knowledge proof verification time for all 400 shielded transactions is shown in figure 8(a).This time was maintained at about 40 to 70 milliseconds.Compared with the generation procedure,the verification procedure took a shorter time,because it only performed a small amount of computation on the elliptic curve.

We also measured the verification time for 400 transactions without the privacy protection.As is shown in figure 8(b),the verification time was maintained below 1 milliseconds for most of the transactions.Therefore,the zk-SNARKs algorithm significantly extended the verification time for a single transaction.

However,the zk-SNARKs algorithm causes relatively small influence on the overall performance of the blockchain.Given the fixed block size,the transaction processing speed of the blockchain is mainly influenced by the generation interval of each block [23].Since this interval is usually large (e.g.,15 seconds for Ethereum and 10 minutes for Bitcoin),the influence of the transaction verification time is negligible.Moreover,this influence can be minimized by the method proposed in the paper [24],in which a new block can be broadcast to other participants immediately without the transaction verification if the block header is valid.

Fig.7.Time for zero-knowledge proof generation.

Fig.8.Verification time for zero-knowledge proof & transactions without privacy protection.

VI.CONCLUSIONS

Blockchains pose serious challenges to users'privacy.Among all the schemes for the privacy protection,the zero-knowledge proof algorithm conceals most of the private information in a transaction,while each participant can validate this transaction without such information.However,current schemes based on the zero-knowledge proof algorithm are only aimed at the UTXO and single-asset model.

Based on the zero-knowledge proof algorithm,we propose a privacy protection scheme aimed at the account and multi-asset model.Our scheme conceals the sender,receiver and amount in a transaction.We design the verif ication rules for the shielded transactions,and use the zk-SNARKs algorithm to generate and to verify the zero-knowledge proof.We implemented our scheme,and evaluated the system by experiments.Our future work includes the design of more efficient algorithms for the zero-knowledge proof generation.