The technical challenge of applying zero knowledge proof to blockchain

Li Kang 1,2, Sun Yi 1,2, Zhang Jun 3, Li Jun 4, Zhou Jihua 5, Li Zhongcheng 1

  1. Institute of computing technology, Chinese Academy of Sciences , Beijing 100190

  2. University of Chinese Academy of Sciences , Beijing 100049

  3. Inner Mongolia University , Inner Mongolia Autonomous Region Hohhot, 010021

  4. Bobby ( Beijing ) Network Technology Co., Ltd , Beijing 100190

  5. Chongqing Jinmei Communication Co., Ltd , Chongqing 400030

Abstract : Blockchain is a point-to-point distributed ledger technology based on cryptography algorithm , However , Open and transparent blockchain account books supplemented by sociological mining 、 Data mining and other statistical methods , Make the privacy of users face a major threat , Therefore, privacy protection has become a hot topic in the research of blockchain technology . The existing privacy protection schemes are summarized , Focus on zero knowledge proof technology , This paper expounds and analyzes the technical challenges of applying zero knowledge proof to blockchain privacy protection scheme , And give a guiding solution .

key word : Blockchain ; Privacy protection ; Proof of zero knowledge


Citation format of the paper : Li Kang , Sun Yi , Zhang Jun , etc. . The technical challenge of applying zero knowledge proof to blockchain [J]. big data , 2018, 4(1): 57-65.

LI K, SUN Y, ZHANG J, et al. Technical challenges in applying zero-knowledge proof to blockchain[J]. Big Data Research, 2018, 4(1): 57-65.

1 introduction

It is the first time to solve the problem of trust centralization based on blockchain , It's based on the value of cryptography , Based on hash chain and time stamp mechanism, the traceability of data is guaranteed 、 Tamper proof features , Consensus based algorithm ensures the consistency of block data among nodes . Blockchain technology system is profoundly changing the production mode of all walks of life , It will become the cornerstone of value Internet in the future digital economy era .

since 2008 Since the advent of bitcoin in , Blockchain technology has been developed and applied rapidly , Blockchain platforms with various functions emerge as the times require , Such as Ethereum, a smart contract platform 、 Go to the central storage platform Filecoin And financial business solutions Corda etc. . Industry applications based on blockchain are becoming more and more abundant , for example , The London Stock Exchange 、 The London Clearing House 、 Societe Generale 、 The blockchain group, jointly established by UBS and Euroclear, applies blockchain technology to the securities field , It aims to change the clearing and settlement methods of securities transactions through blockchain technology ; The United States Factom The company applies blockchain technology to the field of digital certificate keeping , Try to innovate the data management and data recording methods of the commercial society and government departments through blockchain technology ; The United States Chronicled The company applies blockchain technology to the field of supply chain traceability , Guarantee the authenticity of the goods , protect consumers ' right .

However , The openness and transparency of blockchain also brings great challenges to the privacy protection of users . Blockchain participants maintain a common ledger , You can view and verify the transaction data of other participants , This opens the door to the disclosure of the privacy of the participants , Pictured 1 Shown [1]. therefore , Privacy protection has become one of the bottlenecks restricting the development of blockchain applications .

 The technical challenge of applying zero knowledge proof to blockchain

chart 1 2013 Bitcoin trading map in

So , How to make everyone verifiable without sacrificing blockchain 、 On the premise of openness and transparency , Protect the privacy data of participants , It has become the main scientific problem in the field of blockchain research .

In view of the above situation , This paper will summarize the existing privacy protection schemes in the field of blockchain , Focus on zero knowledge proof technology , This paper describes how to apply it to the blockchain to achieve transaction privacy protection , It also introduces several technical challenges that need to be solved in the combination of zero knowledge proof and blockchain .

2 Research status of blockchain privacy protection scheme

The most important component of blockchain is transaction , Transaction is the information carrier that drives the operation of blockchain system , By trade , Blockchain nodes can transfer funds between users , And a series of more complex operations , For example, executing related smart contracts . The basic elements involved in a transaction are the sender 、 The receiving party 、 amount of money , Although the sender and receiver are generally represented as public key addresses in blockchain systems , But supplemented by sociological mining methods , You can associate real-world identities with public key addresses , And blockchain as a public trading book , Anyone can find out what other users have done in the system , Such as the process of capital flow 、 Contract execution process, etc , Thus, the privacy of users is revealed . therefore , How to ensure that users' operation behavior in the blockchain system is not obtained by others is the main content of blockchain privacy protection , The solution to this goal is to protect the key information of the transaction from being leaked .

Since bitcoin, blockchain platforms have begun to pay attention to the privacy protection of transactions , And support the privacy protection of transactions from the protocol level , And there's no need to lose the publicly verifiable nature of blockchain , This has laid a foundation for the further application and development of blockchain .

Dascoin is the first platform to realize transaction privacy protection in blockchain and get large-scale application . It uses a method called “ Mixed currency ” Technology , Anonymous sending is realized (darksend) The function of . Anonymous sending is an implementation of mixed currency technology , The basic idea is to use the main node in the network to mix the transactions from multiple users to form a single transaction . Zhongda coin is sent anonymously , Each user needs to send the transaction to the master node , The master node needs at least 3 A deal to mix , And then form multiple outputs in a single transaction , And make sure the output is out of order . In order to improve the privacy of the system as a whole , Fixed denominations are required 0.1、1、10、100 The transaction amount of , In each round of mixing , All users should submit inputs and outputs of the same denomination , In addition to using the same denomination , The transaction fee will be removed from the transaction , And in independence 、 Payment in unlinkable transactions . In anonymous sending , The primary node is responsible for privacy protection , Being is *** The possibility of . By introducing Chain mixing (chaining) technology , Users will randomly select multiple master nodes , These master nodes form a chain , Finally, output the mixed transaction ; By introducing the blind technology based on relay system (blinding), Users may not submit transactions directly to the transaction pool , On the contrary, select the master node randomly in the whole network , Then the master node is required to submit the transaction to the target master node , In this way, it is difficult for the target master node to obtain the user's real identity . But the limitation of dascoin is , Nodes always need to trust the primary node selected by the network and the users participating in the mixed currency service , Once the master node is controlled , Or the users involved in the currency mixing are malicious , Will lead to the disclosure of user privacy to a certain extent .

In order to avoid the trust risk of master node in dascoin , Monroe coin adopts a hybrid encryption scheme independent of the master node , There are two key technical points involved : One is secret address technology , The other is ring signature technology . The basic principle of secret address is , When the sender sends a sum of money , First, through the recipient's address , One time public key generation based on elliptic curve , The sender then broadcasts the transaction along with the additional information to the blockchain network , The receiver always uses his private key to monitor the transactions in the blockchain , If the transaction can be resolved successfully , Prove that the sender has sent the relevant transaction ; When the receiver wants to spend the transaction , Use the private key with additional information to calculate the signature private key , Signing a transaction costs , It ensures that the input and output addresses are not associated . The basic idea of ring signature and user private key signature is to use their own public key , When verifying a signature , Then use the other person's public key and the parameters contained in the signature , So as to achieve the purpose of hiding the sender's information . But the limitation of Monroe is that , When users use ring signature technology , Need to rely on other users' public keys , If other users are malicious , It will lead to the disclosure of user privacy to a certain extent .

2016 year 11 month , International famous bank blockchain Alliance R3 The organization has opened up its commercial solutions for financial institutions ——Corda platform . In the business environment of financial institutions , Privacy protection is essential ,Corda A lot of work has been done in this respect . First , In the traditional blockchain , All nodes maintain a common ledger , The possibility of privacy leakage will be greatly increased , therefore ,Corda The act of broadcasting without trading , Only in the dissemination and witness of transactions between related parties . secondly , Take sensitive information extraction (tear-off) technology , Hashing sensitive information , And it's made up of layers Merkle Trees , So that non sensitive information can still pass through Merkle Tree for branch validation , And in the event of a legal dispute , You can apply for disclosure of sensitive information , To verify . Last , Compound signature technology is adopted , By assigning negotiated weight to each signature subject , With signature threshold setting , You can set up a flexible signature scheme , To protect the signer's information .

2016 year 11 month , Zero coin with privacy as its main function (Zcash)[2] Blockchain system is open source , Committed to creating a perfect privacy protection platform . Zero coin uses the most famous of zero knowledge proofs zkSNARKs[3-10] technology , The technology is non interactive 、 Conciseness 、 Public verifiability, etc . There are transparent address and anonymous address in zero coin system , Using anonymous address can achieve the purpose of transaction privacy protection , Transactions that contain anonymous addresses are called covert transactions , Secret transactions will be sent by 、 The receiving party 、 The transfer amount is all hidden in the generated zero knowledge evidence , The blockchain node verifies the key according to the zero knowledge evidence generated in advance , Can verify the authenticity of secret transactions , Guarantee that only the real sender can complete an effective secret transaction with real assets . Since the secret transaction does not include the sender 、 The receiving party 、 Transfer amount and other key information , bring *** No more information can be obtained from transaction traceability , So as to effectively protect the user's privacy .

In addition to the above technologies that have been applied to the blockchain platform for privacy protection , Blockchain researchers also list homomorphic encryption technology as a key cryptography technology for privacy protection . The characteristic of homomorphic encryption makes the transaction related parties witness plaintext , The parties not involved in the transaction can witness the ciphertext , To verify the validity of the transaction . But due to the low efficiency of homomorphic encryption technology , The combination with blockchain is still in a relatively primary stage . If homomorphic encryption technology makes a major breakthrough in the future , It will greatly promote the application of homomorphic encryption technology in blockchain system .

3 The technology of zero knowledge proof applied to blockchain war

Zero knowledge proof refers to one party ( Certifier ) To the other side ( Verifier ) To prove that a statement is correct , Without disclosing any information other than that the statement is correct , Apply to solve any NP problem . The blockchain can be abstracted into multiple parties to verify whether the transaction is effective (NP problem ) The platform of , therefore , The two are naturally compatible . The technical challenges that need to be considered when applying zero knowledge proof to blockchain can be divided into two categories : One is the design scheme of blockchain architecture for privacy protection , Including the proof of the existence of secret assets 、 The problem of anonymous asset double spending 、 Anonymous asset spending and transfer 、 Technical challenges such as indistinguishable secret transactions ; The other is the challenge of zero knowledge proof technology itself , Including parameter initialization phase 、 Algorithm performance and security issues and other technical challenges .

3.1 Proof of the existence of secret exchange assets

In blockchain systems that don't use zero knowledge proof , There are two models to prove the existence of exchange assets : Transaction output not spent (unspent transaction outputs,UTXO) Model and account model . stay UTXO In the model , The input of each transaction refers to the output from the previous transaction , The blockchain node will be based on the saved UTXO Collection to verify the existence of a transaction cost asset ; In the account model , Each transaction will specify the sender , The blockchain node will verify whether a transaction cost asset exists and is sufficient according to the saved account information . If zero knowledge proof is used in the blockchain to ensure the privacy of transactions , The first solution is how to prove the existence of secret assets on the blockchain . Because the secret transaction hides the sender's address information , Therefore, the secret exchange assets cannot come from the transparent assets that already exist in the blockchain , This means that the previous transaction output or account cannot be explicitly referenced . therefore , The assets spent on covert transactions should be anonymous , This requires designing a mechanism to issue anonymous assets , And identify anonymous assets . There are two anonymous asset issuing mechanisms in zero coin system : One is the cost “ dig ” The reward , Turning rewards into anonymous assets , The goal is to have enough anonymous assets in the system , Prevent anonymous assets from being tracked ; The second is to convert transparent assets into anonymous assets through normal transactions . that , When secret transactions cost anonymous assets , How to make the blockchain node believe the existence of the anonymous asset ? The zero coin system marks every anonymous asset with a digital commitment , And organize these digital commitments into a tree Merkle Trees , It is used to identify all anonymous assets that have appeared in the system ( Including spent and not spent ). Covert trading involves the location of anonymous assets Merkle The root hash value of the tree and the proof that the anonymous asset does exist in Merkle Zero knowledge evidence in the tree , Through the public verification key, the blockchain node can verify that the assets spent by the secret transaction have indeed appeared in the blockchain system , But I don't know which anonymous asset , Nor can it prove whether the anonymous asset has been spent , So there will be a double flower problem , Next, we will explore how to solve the problem of anonymous assets double flower . in summary , The privacy protection scheme of blockchain transaction needs to design a set of anonymous asset issuance mechanism and existence proof mechanism (Merkle Trees ), Make sure it exposes verifiable features .

3.2 The problem of anonymous asset double spending

One of the core problems to be solved by blockchain is the double spending of funds , stay UTXO In the blockchain of the model , All blockchain nodes need to be maintained UTXO aggregate , When verifying a transaction , Export the transaction reference from UTXO Remove... From collection , So when verifying another transaction that costs the same output , Because it's in UTXO The output cannot be found in the collection and becomes invalid . In the account model , All blockchain nodes maintain account status , This includes , When verifying a transaction , First, we will judge whether the account balance is enough , Therefore, it can also effectively prevent Shuanghua . In order to protect the privacy of blockchain transactions , You need to use anonymous assets , However, there will be a double flower problem , Therefore, we need to further strengthen the attribute of anonymous assets in the blockchain . The zero coin system gives each anonymous asset a unique serial number , Blockchain nodes save all the serial numbers that have appeared , When launching a secret deal , The serial number needs to be disclosed , The node checks whether the serial number has appeared , This can effectively prevent the double flower problem of anonymous assets . Be careful , Appropriate hash function and random number should be selected , Code anonymous asset number commitment and serial number , Make sure they're connected , And one to one .

3.3 Anonymous asset spending and transfer

In blockchain systems that don't use zero knowledge proof , Asset spending is done through a pair of public and private keys , Asset transfer is done by specifying the address of the receiver in the transaction . For privacy protection , Secret transactions need to hide the sender as well as the receiver , So how does the blockchain node verify that the anonymous asset is spent by the owner , And transferred to the right recipient ? Secret trading costs anonymous assets , Anonymous assets should include at least the amount 、 Public key address, etc , therefore , When generating anonymous assets , You need to put the amount 、 The public key address is encoded into the digital commitment . When spending an anonymous asset , Put the private key 、 The generating relationship between public key and digital commitment is encoded into zero knowledge evidence , Combined with the proof of the existence of anonymous assets , The blockchain node can use the public verification key of zero knowledge proof to verify the existence of digital commitment , And through the corresponding public key address 、 Amount generation , And the person sending the transaction has the private key corresponding to the public key address , Make sure that only those who own anonymous assets have the right to spend .

How does the transfer of ownership of anonymous assets occur ? Since there is no receiver in the secret transaction , And every anonymous asset is associated with its owner's public key , So we use the destruction of old anonymous assets 、 The strategy of generating new anonymous assets ensures the transfer of anonymous assets . The generation of digital commitment of anonymous asset needs its public key address 、 Amount, etc , And the original information is also sent to the receiver , So the receiver needs to provide two public keys , One is the payment public key , One is encrypted public key . Pay public key for sender to generate digital commitment , The encrypted public key is used by the sender to encrypt the information used in the process of generating digital commitment . Of course , The payment public key and the encryption public key can be the same , But for the sake of safety , It is recommended to use a different public key . The receiver needs to monitor the transactions on the blockchain , Try to decrypt the encrypted information contained in the secret transaction with your private key , If the decryption is successful , It means that the receiver of the secret transaction is himself , Put the anonymous asset under your own payment key pair account , Easy to spend later .

In addition to anonymous asset costs and transfers , The relationship between the total assets spent and the total assets generated by the transfer should also be coded into zero knowledge evidence , That is, the total amount of assets spent should be greater than or equal to the total amount of assets generated by the transfer , To ensure the effectiveness of covert trading .

in summary , The application of zero knowledge proof in blockchain needs to design a set of reasonable anonymous asset ownership verification rules and transfer rules , These rules are encoded into zero knowledge evidence using zero knowledge proof technology , So as to achieve the publicly verifiable characteristics of blockchain .

3.4 The indistinguishable nature of covert trading

In order to achieve the purpose of transaction privacy protection , Secret transactions in the blockchain should be indistinguishable , It can't be compared 、 Analyze secret transactions and cluster them . in addition , Because zero knowledge proof requires circuits ( Validation rules are transformed from ) Is constant , therefore , In a blockchain that uses zero knowledge proof , Secret trading should have a fixed number of inputs and outputs , When the input and output quantity cannot meet the specified quantity , Random redundant inputs and outputs should be built , And the generated zero knowledge evidence should contain the conditions to determine whether the input and output are redundant or true , When a blockchain node receives a secret transaction , It will decide whether to process the corresponding anonymous assets according to the authenticity of the input and output , The indistinguishability of secret transaction further strengthens the protection of transaction privacy .

3.5 Zero knowledge proof initialization phase

Zero knowledge proof can be divided into interactive and non interactive , And in the blockchain system , Interactivity is not appropriate , Because every node in the blockchain has to verify the validity of the transaction , In order to achieve the purpose of privacy protection, the sender needs to exchange information with the whole network verification node of the blockchain system , Therefore, non interactive zero knowledge proof should be adopted in the blockchain system . In non interactive zero knowledge proof , zkSNARKs The most mature .zkSNARKs The algorithm needs a centralized initialization phase , It is used to create a proof key for generating zero knowledge evidence and a verification key for verifying zero knowledge evidence . The blockchain itself is a decentralized system , that zkSNARKs The initialization phase of the algorithm undoubtedly brings trust risk to the blockchain , So how to ensure zkSNARKs It is a key technical challenge for blockchain to construct the initialization phase reliably . In the zero coin system, an initialization phase of multi-party security formula is designed [11], That is to say, each party cooperatively calculates the proof key and the verification key without disclosing its own information , But the proof key and the verification key only need to be generated once , It can be used repeatedly in the future . But the multi-party security computing used by zero coin system is limited to a few people , There's no way to get more people involved , Therefore, we need to further improve the performance of multi-party secure computing , send zkSNARKs The construction scheme of algorithm initialization is more decentralized .

3.6 zkSNARKs Algorithm performance

zkSNARKs The current performance of the algorithm is poor , The computational complexity mainly comes from the elliptic curve pairing operation , At present, the zero system uses BN254 Elliptic curve [12], Generating zero knowledge evidence for a secret transaction requires 40 s about , And occupy about 4 GB Memory , This makes it impossible to use on existing mobile devices zkSNARKs Algorithm , also 40 s In the high concurrency scenario, it also appears to be very slow . Therefore, it is necessary to carefully design elliptic curves that are friendly to pairing operation , At present, there have been relevant research progress , For example, the zero coin system developers have designed BLS12-381[13] Elliptic curve , Preliminary test , The time of generating zero knowledge evidence can be reduced to 7 s, Memory footprint reduced to 40 MB about , Greatly improved zkSNARKs The availability of algorithms .

zkSNARKs The security of the algorithm depends on the elliptic curve selected at the bottom ,BN254 The security of elliptic curve implementation is about 128 bit, There have been studies recently [14] indicate ,BN The security of elliptic curve is actually 110 bit about . So when you design an elliptic curve , The safety of the curve should be considered .

in summary , When zero knowledge proof algorithm is applied to blockchain privacy protection , It needs to meet the core functional characteristics of blockchain , That is to say, to confirm the right of assets, to transfer and to prevent double spending . This paper is based on zero knowledge proof algorithm , This paper presents a set of anonymous asset issuance 、 Transfer mechanism , While protecting the privacy of users, it effectively realizes the function of asset confirmation and transfer, as well as preventing double flowers . In the combination of zero knowledge proof and blockchain practice , It is recommended to use mature 、 Efficient 、 Safe zkSNARKs Algorithm , And gives zkSNARKs The direction of further optimization of the algorithm .

4 Conclusion

In the context of digital economic globalization , The emergence of blockchain technology makes it possible to transfer value through the Internet , However, the openness and transparency of blockchain also brings great challenges to people's privacy protection , Therefore, how to achieve privacy protection has become a problem hindering the further development of blockchain .

This article explains in detail the methods adopted by the current blockchain platform to achieve privacy protection , Focus on zero knowledge proof technology , This paper expounds several common problems that need to be considered in the combination of zero knowledge proof and blockchain , And the technical challenges of zero knowledge proof in blockchain are explained . In the future, the privacy protection of blockchain still has a long way to go , How to achieve fast and efficient 、 Trusted zero knowledge proof algorithm and how to implement zero knowledge proof algorithm that can resist quantum computing , They are all problems that need to be solved further .