Comprehensive analysis of zero-knowledge proof: resolve the expansion problem and redefine "privacy security"
Author: Packy McCormick, Jill Carlson
Original Compilation: Jessie, Siqi
This article is from Overseas Unicorn.
As the smallest unit of the Internet world, in order to obtain the convenience brought by the Internet, people have to sell their private data in the process of participating in online life, work, and transactions:You must enter your credit card number on the website, you must provide your bank credit history to the housing agent, and you must provide your ID card information to the bank. In addition to individuals, companies and institutions have always had to disclose sensitive information to each other in order to conduct business. Sharing information and accepting its insecurities seems to be accepted as a necessary sacrifice in the functioning of society.
Zero-knowledge proof (zero-knowledge proof, which we refer to as ZKP in this article) is proposed to solve this dilemma. ZKP essentially allows people to authenticate their identity and rights without revealing any private information.
The current best practice of ZKP is in the blockchain field. The scalability issue has been one of the biggest dilemmas facing Ethereum,ZKP-based zk Rollup technology is unanimously optimistic about the expansion route of encryption leaders including Vitalik, zk Rollup has created a layer 2 network (Layer 2) with higher throughput and lower cost based on the premise of inheriting the security of Ethereum. Therefore, ZKP has attracted much attention.
Although ZKP is more associated with the blockchain at this stage, its application scenarios are more than that. With its unique privacy, accuracy and verifiability, ZKP will also bring applications and innovations in cloud computing, finance, online voting, machine learning and other fields.
We believe that ZKP is a technical theory that is very important for future business. Like every revolutionary technology that brings about changes in the technological field, these emerging technologies always experience hype and bubble bursts in their early stages before bringing about disruptive changes. We must have a prudent and optimistic attitude towards it, and by grasping its principles, we can better deal with the evolution of the cycle.
Zero-knowledge proof is a complex cryptographic concept. We hope to popularize industry science in an easy-to-understand way, so that more people can understand zero-knowledge proofs. This is also one of the efforts of "overseas unicorns" to promote "cognitive equality".
The following is the table of contents of this article, and it is recommended to read it in combination with the main points.
01. What is a zero-knowledge proof?
02. The History of Zero Knowledge
03. The trade-off of privacy
04. Classification of zero-knowledge proofs
05. Risks of zero-knowledge proofs
first level title
01.
What is a zero-knowledge proof?
Data is everywhere. Names, dates of birth, email addresses, credit card numbers, addresses where we have lived for the past five years...these are just a few of the vast amount of information about us that is sent to different businesses, social media sites every day , account managers, sometimes our data will be stolen by criminals.
The risks of this state of affairs are self-evident: identity theft, email breaches, data breaches, and other forms of fraud cost individuals and businesses tens of billions of dollars each year, several dollars more than spending on defense and prevention. Magnitude. Not to mention the hassle of dealing with the fallout.
As a participant in the modern connected world, the proliferation of data and its vulnerability has become a recognized cost of engaging in business activities:We have to trust each other, we have to put credit card numbers on websites, we have to send credit history to landlords, we have to give social security numbers to banks. Not just individuals, companies and institutions have to disclose sensitive information to each other all the time in order to conduct business. Sharing information and accepting its insecurities is a necessary sacrifice for society to function.
But what if there was a way to interact and transact with the same level of trust and certainty without sharing this data?working principle
working principle
This technique allows someone to prove that he has the information without revealing any specific details. Here's a simple way to explain how it works:
A colorblind friend and I are facing a table of balls, one red and one green, that look identical except for their color. He wasn't sure he believed me when I told him they were two different colors. Eventually we decided to play a game to make sure that the two balls were indeed different colors:
He first hid two balls behind his back;
Then he showed me a ball;
Then he put the ball back behind him, showed me another ball, and asked, "Did I switch?"
If we repeat this game enough times and I get it right every time, I can prove to him that the balls are two different colors. More importantly, in the process, I did not disclose any other information other than answering "changed" or "not changed", especially did not argue about the color of the ball itself.
secondary title
three attributes
A zero-knowledge proof must have three different properties at the same time:
Completeness:If the claim is true and the user correctly complies withIf the rules are followed, then the verifier will be persuaded without any human help.
Soundness:This proof technology can ensure the authenticity and validity of the information. If the prover's claims are false, the verifier will not be convinced under any circumstances.
Zero-knowledge:first level title
02.
The History of Zero Knowledge
"Zero-knowledge proof" is not a new concept that just appeared recently. It was designed and proposed by MIT researchers Shafi Goldwasser, Silvio Micali, and Charles Rackoff in the 1980s.
At the time, the research focus of Shafi Goldwasser, Silvio Micali, and Charles Rackoff was related to interactive proof systems. There are two roles involved in the interactive proof system:
informationalprover
informationalverifier
Usually it is assumed that the prover (prover) is untrustworthy and the verifier (verifier) is trusted. The goals of designing the system in this way are:
A verifier can be persuaded by an untrustworthy prover to believe a true statement
It is impossible for the prover to convince the verifier that the statement is not true
One can imagine a scenario:There is a long queue at the entrance of the bar. If these queuers want to enter the bar, they must prove to the bouncer that they are of age. Then the queuing person is the prover (prover) of his own age, and the bodyguard is the verifier (verifier), but the bodyguard does not know whether he can trust the queuing person.
The application of the interactive proof system in this scenario is that the bodyguard needs to know whether the age of the queue is over 18 years old, and the queue also needs to prove this to the bodyguard, then with the support of the ID card information, the bodyguard can verify the age of the queue Judge and finally decide whether the other party can enter the bar.
Goldwasser, Micali, and Rackoff raised a question on this basis: If the bodyguards not only do not trust the people in line, but also the people in the line do not trust the bodyguards, because personal ID information is very sensitive, they do not want to give this information directly to How to deal with a bodyguard who has never met before?The solution of the three of them to this problem is actually "zero-knowledge proof", that is, people in line can still convince the other party that they are of age and enter the bar without telling the bodyguard their actual date of birth.
During the 1980s and 1990s, zero-knowledge proofs were further studied in academia, but with little practical application. It wasn't until the 21st century that researchers and entrepreneurs began to put the theory into practice.
One of the earliest applications of zero-knowledge proofs was network password security around the mid-2000s.When a user uses a password to log in to a website, the actual process behind it is that the user needs to enter their own password when logging in to the website, and these passwords are sent to the server of the website, and the server compresses the password into a string of gobbledygook strings, and the system compares the characters Whether the string matches the gobbledygook (an encrypted gibberish) string previously stored in the system. If the two values are the same, the user is successfully logged in.
The use of gobbledygook is to protect the user's original password: once a hacker obtains the gobbledygook string in the system, the real password cannot be deduced from this string of characters, that is, the user password is not stored in plain text. However, there is still a problem here: that is, there is still a risk of password leakage in the links where users log in to the website, enter plaintext passwords, and send these passwords to the server before they are converted into strings.
In the 2000s, a protocol using zero-knowledge proofs to solve this vulnerability was proposed, and the first cases of applying ZKP to the real world appeared, especially concentratedExploration in the direction of identity verification. But the real inflection point for zero knowledge occurred a few years later.
In 2013-2014, zero-knowledge proofs found commercial application in another system: cryptocurrencies.People usually think that cryptocurrencies are completely anonymous and have strong privacy, so many illegal transactions are carried out through cryptocurrencies. But in fact, this anonymity is relative. Absolutely,The core feature of Bitcoin and most other cryptocurrencies is that the movement of these encrypted assets is recorded on the blockchain and made public, which is very easy to be censored by the police.
Note:
Note:
On May 7, 2021, Colonial Pipeline, the largest fuel oil pipeline in the United States, was attacked by ransomware. The attackers stole 100 GB of data from Colonial Pipeline, causing the company to suspend all pipeline operations and shut down a major pipeline at night. Fuel transfer pipes. Colonial Pipeline was able to restart operations after paying a ransom of 75 bitcoins ($4.4 million) in cryptocurrency, as demanded by hackers. Subsequently, the FBI obtained evidence of the extortion transaction based on the asset transfer records recorded on the chain, locked the identity of the attacker, and sanctioned him.
Based on the improvement of the transparency of Bitcoin, a "anonymous currency" with strong privacy has emerged.
Zcash is the earliest "privacy coin". In 2013, Matthew Green, Ian Miers, and Christina Garman of Johns Hopkins University proposed Zerocoin (a privacy cryptocurrency) created using a zero-knowledge system. Building on this foundation, the team recruited seven founding scientists to further refine the protocol, creating Zcash. Zero-knowledge proof enables a network of computers running the Zcash protocol to verify that each transaction is valid (that is, I do own the 10 Zcash I sent you), introducing more Close to the privacy protection of physical cash, it can be said that it is almost completely untraceable.
Zcash and other privacy-oriented cryptocurrencies have attracted a lot of attention and money. In the bull market in 2021, Zcash's highest market value was once close to $4 billion. The high attention of the market and the influx of a large amount of funds have promoted the rapid progress of zero knowledge in practical application, and a series of breakthroughs have been made.
Note:
Note:
FATF, Financial Action Task Force, Anti-Money Laundering Financial Action Task Force, was established in France in July 1989 and is one of the most important international organizations in the world to combat money laundering.
But the demand for private transactions is real, especially with the explosion of DeFi applications, this demand has become stronger.
How to protect one's trading strategy from others in chain transactions is one of the most concerned issues for traders, because once their trading strategy is followed or imitated by others, it will directly affect whether they can obtain alpha from the market income. If you trade on a centralized exchange, there is a risk of being manipulated by the centralized exchange, but traditional decentralized exchanges are completely transparent, and their trading strategies can be queried and tracked by anyone.
The decentralized exchange supported by zero-knowledge proof satisfies their needs well, taking into account the demands of decentralization and privacy. There is no control by a centralized organization, and there is no need to expose your own transaction records and trading strategies. The more famous case is DeversiFi, which uses the StarkEx service of the zero-knowledge technology provider StarkWare to build a highly private decentralized exchange. .
Therefore, judging from the recent privacy projects that have received the most attention in the industry, compared with privacy cryptocurrencies, the inclusion of privacy protection functions on mainstream blockchains will become a longer-term trend.first level title
03.
Trade-offs for privacy
There are two types of attitudes towards personal privacy:
Giving up privacy and assuming all their data is available to whoever really wants it
extremely concerned about their privacy
Most of us fall into the first camp. Although no one will admit that they are willing to expose private information to hackers, for example, people maintain the habit of regularly updating passwords, but when everyone has a lot of information stored online, the workload of maintaining privacy is not just updating passwords So simple, sometimes the cost of maintaining personal information is much higher than people can afford.
In other words, most people would be willing toPrivacy is sacrificed for convenience.
Zero-knowledge proofs have the potential to eliminate this unnecessary transfer of rights and trade-offs, and change people's thinking about privacy.When faced with a situation involving their own privacy, people will ask:"Who, under which circumstances, needs how much information?" is no longer a black-and-white decision.
With the help of ZKP, the verifier (verifier) only needs to know what he wants to know about the prover (prover), without knowing all the information of the other party, and without storing all the data on the server to complete the verification work .
ZKPs are not the only potential solution to provide more privacy with less friction. There are also other startups trying to come up with solutions to protect more privacy without requiring much change in consumer behavior and experience.
Companies such as Stytch and Magic smuggle passwordless authentication into their products by providing toolkits for developers to easily authenticate users in a more secure way, eliminating the need for users to enter passwords to log in in the past, such as email authentication. , Google Authenticator, WhatsApp links, and more without worrying about your password being stolen.
Evervault builds encryption infrastructure for developers to ensure that any data entered by users is automatically encrypted on the spot and never exists in unencrypted form in the company's database. Evervault perfectly represents the spirit of this new generation of privacy technology:
Privacy is a basic expectation and human right, but in no way should it cause any friction or slow down the rate of technological progress.
In other words, people don't have to make trade-offs about privacy as they used to.
first level title
04.
Classification of zero-knowledge proofs
According to the interaction mode and form between the prover (Prover) and the verifier (Verifier),Zero-knowledge proofs can be divided into interactive zero-knowledge proofs and non-interactive zero-knowledge proofs.
Interactive zero-knowledge proofs:The prover and verifier need to interact multiple times, the verifier will continue to ask questions to challenge the prover, and the prover will continue to respond to these challenges until the verifier is convinced.
But interactive zero-knowledge proofs have two obvious problems:
Portability is limited:Interactive proofs are only valid for the original verifier, and no other verifiers can trust this proof. Therefore, once the verifier changes, even if it is the same proof, the certifier still needs to repeat the entire previous process;
Not scalable:Interactive ZKP requires the prover and verifier to be online at the same time, which makes the whole process unscalable.
This is why interactive zero-knowledge proof blockchains work better with a small number of participants rather than large groups. In order to solve the problems faced by interactive zero-knowledge proofs, non-interactive zero-knowledge proofs came into being.
Non-interactive zero-kowledge proofs:The prover only needs to send a proof to the verifier for the first time, and the verifier can verify the proof information at any time, and only needs to verify once to decide whether to trust the prover. This type of proof requires more computing power to complete than interactive proofs.
In an interactive proof system, the "prover" and "verifier" must be online at the same time to successfully perform an operation, which makes the whole process unscalable. In 1986, Fiat and Shamir invented the Fiat-Shamir heuristic, which changed interactive zero-knowledge proofs to non-interactive zero-knowledge proofs. Here, the verifier is replaced by a hash function. Due to the randomness of the sequence generated by the hash function, the prover cannot predict it in advance. As long as the hash value provided by the prover is correct, the proof is passed.
The main advantages of non-interactive proofs are:
Scalable: it does not require provers or verifiers to be online all the time
Portable: Once the prover gives the proof, it can be made public, and there is no need to repeat the proof for different verifiers
If interactive zero-knowledge proofs are like making a phone call and must communicate synchronously, non-interactive zero-knowledge proofs are similar to a special message system that can communicate asynchronously and prove their correctness.Arguably, non-interactive zero-knowledge proofs are the best way to prove your claims to many people without adding resources and costs.
first level title
05.
The Risks of Zero-Knowledge Proofs
Although zero-knowledge proof is powerful and iterative, it also has the following shortcomings:
Not 100% guaranteed that the information is true:Even if the prover has a very low probability of passing the proof when lying, ZKP cannot guarantee that the statement is 100% valid. The probability that a validator is lying decreases with each iteration, but it can never reach zero. Therefore, zero-knowledge proof is not a proof in the mathematical sense that strictly follows mathematical logic. It is probabilistic rather than deterministic.
Calculation intensity:first level title
06.
Application of zero-knowledge system
secondary title
A Simple Example: Renting an Apartment
A couple wanted to rent an apartment, and the real estate agent was required to conduct a credit check on the tenant, requiring the tenant to provide information such as bank statements, proof of income, and social security number.
But because the tenant has just met the real estate agent, he does not think that the other party will properly protect his privacy. Naturally, you don’t want the real estate agent and its team to see your detailed financial situation, especially the tenants can’t be sure whether the real estate agent’s information system is secure enough to ensure that hackers will not get the data.
At this time, the idea of zero knowledge can be introduced to solve the above problems.
Assuming that the monthly rent of the apartment is $1,000, according to the requirements of the intermediary, the tenant needs to prove that his income is at least 40 times the monthly rent to be eligible to rent the apartment. Here's how tenants are tested:
The intermediary set up 10 mailboxes marked with 10 integers ranging from $10,000 to $100,000, and each mailbox has a key and a slot. While putting the 10 mailboxes into the room, the broker destroyed the keys to nine of them and took only the key to the $40,000 mailbox.
After the intermediary left the room, the tenant walked into the room with 10 pieces of paper, and marked "+" or "-" on the paper according to whether the number of each mailbox was more or less than his actual assets, and put The slips are placed in the corresponding mailboxes. Let's say the tenant's annual income is $75,000, so they put "+" slips in the first 7 messages and "-" in the last three mailboxes throughout the process.
secondary title
more complex example
blockchain privacy
In the world of cryptocurrencies, the above-mentioned interaction has become possible. There are several projects today working on using ZKPs to prove a trader's credit score. There are also projects building new, general-purpose platforms for ZKP-oriented assets and transactions. Still others are still focused on bringing ZKP-based privacy to Ethereum. Ethereum founder Vitalik believes: "Zero-knowledge proof is the most powerful privacy solution. Although the technology is the most difficult to implement, it has the best effect in protecting the privacy and security of the Ethereum network."
The transparency of public blockchains like Bitcoin and Ethereum enables transactions to be publicly verifiable. However, it also means little to no privacy. Zero-knowledge proofs can bring more privacy to public blockchains, for example, the cryptocurrency Zcash is the first project implementation of zk-SNARKs, a form of non-interactive zero-knowledge proofs that can provide the strongest privacy.
These innovations promise to open up cryptocurrencies and their applications to users who have traditionally been outside the crypto world.Businesses don’t use stablecoins today to run international payrolls, even though they are more efficient than wire transfers; nor do many financial institutions seek alpha gains in the lucrative and high-yielding market for decentralized finance protocols.A key reason for this is that companies like this can't spread their financial information and transaction history around on the Internet, and they have to worry about data privacy.
So why aren't these businesses using something like Zcash? Or a privacy-oriented stablecoin? because,In addition to worrying about data security, these enterprises also worry about compliance.They can't use something that's always been in the privacy sphere because they don't have audit reports to prove they're making payments to known counterparties and not sanctioned actors or terrorist groups.
The coolest thing about ZKPs that are being developed today is that,Not only do they have privacy features, but they also support selective disclosure of information.So, you can now imagine a stablecoin product that meets both the data and compliance needs of companies: the issuer can have a full audit trail and be able to verify the compliance It appears that they transfer funds between anonymous accounts in complete privacy.
Blockchain expansion
In addition to applications to privacy and selective disclosure concerns, zero-knowledge proof systems have also been used for blockchain scaling.
A major problem with blockchain scaling is that, over time, the amount of data stored on the blockchain becomes enormous. A blockchain is a publicly verifiable ledger that records everything that happens to a cryptocurrency. So if you want to validate the ledger, you have to sync your computer to the whole ledger, all the way back to the first transaction. For many average users, the memory and bandwidth requirements to actually do this are prohibitively high.
Blockchain utilizes ZKP to solve this problem. The entire transaction history can be compressed into a single proof, and only the proof needs to be verified, not the entire ledger. The proof is no larger than a few tweets in size and can be done with anyone's hardware.
ZKP is also an important tool for scaling Ethereum.
Eli Ben Sasson, the co-founder of the blockchain expansion technology provider StarkWare team, was a senior professor at the Israel Institute of Technology and a founding scientist of Zcash. He invented the zkRollup technology based on zk STARK (a non-interactive proof) to solve the expansion problem of Ethereum, improve the throughput of Ethereum and reduce transaction fees. zkRollups relieve the burden of content that must exist directly on the blockchain ledger, replacing all data that previously needed to be on-chain with cheaper, lighter proofs of data.
While much of the innovation around ZKPs was pioneered in the cryptocurrency space, and where most of the funding for this innovation comes from, its impact and applications are much broader.
Non-Blockchain Applications
cloud computing:finance:
finance:In 2017, ING Bank (International Nederlanden Group, also known as ING), which has customers in more than 40 countries, uses the ZKP method to allow customers to prove that one of their indicators meets the requirements. For example, a mortgage applicant can demonstrate that their income falls within the required range without disclosing their exact salary. A year later, ING has taken the privacy solution a step further by verifying not only numbers but other types of information, for example, a bank can verify whether a new customer lives in an EU country without the customer needing to reveal which country they live in .
Vote online:Online voting must meet a number of requirements to achieve the same or higher level of security as traditional paper voting. These requirements mainly come from four aspects: (by voters) authentication, honesty, privacy and verifiability. ZKPs allow voters to vote anonymously, in such a way that they can attest to the correctness of the process, verify that their votes were included in the final count, and ensure that no manipulation of votes occurred during the counting process.
machine learning:In the process of training a machine learning model, in addition to providing a large amount of data, it is also necessary to answer the question "Is the output of my model credible?" The easiest way is to record the entire calculation process and carry out reverse verification of "backward deduction". Although it is theoretically feasible, in practice, this kind of verification process not only has a huge workload, but also weakens the transferability of the model in use, because once new data input is involved, this process must be performed once, which is not conducive to the machine. The large-scale popularization and application of learning, and there is also the risk of data leakage and algorithm model leakage. Dr. Zhang Yupeng of Texas State University pointed out in a paper last year that zero-knowledge proofs can also be introduced into the training process of machine learning models, which can verify a certain output more quickly on the basis of protecting database data and algorithm models. Whether the results are accurate and credible.
Nuclear disarmament:The first experimental demonstration of a zero-knowledge proof of physics, which allows verifiers to confirm whether an object is a nuclear weapon without recording, sharing or disclosing it, was conducted at the U.S. Department of Energy's (DOE) Princeton Plasma Physics Laboratory (PPPL) in 2016 Internal confidential work.
......
These are just a few examples of the countless possibilities.The prospect of zero-knowledge proof is promising, but sometimes the reality may be far less than expected in the short term. After all, there are severe technical, economic and social challenges to be solved, and there is a long way to go.
