A paper on the history of cryptography, working principle, zero-knowledge proof and potential impact

This article describes the history of cryptography, how it works, proof of zero knowledge, and its potential future impact. Readers who have the basic knowledge of blockchain will be relatively easy to read. However, this article is still trying to make the readers feel interesting and relevant to themselves.

Let's warm up first. Agatha Christie's famous series of detective novels, such a description of the old woman in the hometown to detect various crimes, Miss Marple…

… The unmarried old man sits quietly and quietly, and you will think that her brain has a kind of hole to wear the magic of others' subconsciousness. It is only a matter of time to solve any problem. It is even more admirable to think that she has lived in the small village of St. Mary's in England for the rest of her life. She only knows the world through the prism of the village and the daily life there, but because of her nuanced observation of the whole village, the whole world seems to escape her eye.

Russian writer Lev Tolstoy wrote:

Know the village and know the world.

• Market Analysis: The volume exceeds the shock range, and ETH has to take over the bull market baton?
• For the "half of the market" power, bitcoin computing power, difficulty and other network indicators hit a record high
• Suspected of forging documents, tens of billions of dollars into a mystery, CSW was questioned in court

The above two authors refer to the ability to derive the deepest truth and knowledge from a simple perspective and a small space. This ability is a great encouragement to those souls who are confused, overwhelmed and bored in earthly life, and at the same time, for those souls who are prepared to venture and explore and feel burdened in understanding the world. Ability is also a complete relief.

Both states are actually a kind of surrender. The former means that everything is understood, and it is boring. The latter means that nothing can be clarified, that is, unattainable. The rapid development of innovation and change often allows us to slip from one extreme to the other.

But there is another option: the pursuit of understanding. A pursuit means the starting point of a plan. If you want to, for example, "pursue to be a doctor," you can't wake up in the morning and decide that you can have an operation today. You must study a course, apply for a medical school or attend other medical training. Think about it, we will ask the child: "What do you grow up with?" But the question for adults is "What are you studying?" or "What are you learning?" We have clearly different expectations for the answer – – What you want to be is one thing, and what you are pursuing is completely different.

If we really want to understand something, we have to start from our starting point and need to understand the tiny details and how they relate to our world.

The following is a journey of understanding cryptography and its applications. I started to explore some of the latest applications and popular vocabulary of cryptography just because cryptography is related to the blockchain. In the end, I found that cryptography is actually the starting point of the story.

The main purpose of this paper is to let non-professional readers without a background in mathematics, computer science, or cryptography understand cryptography, its past and current history, and its future applications and potential.

Detective novelist Ai Lunpo’s short story "Golden Beetle" has inspired American contemporary economist Milton Friedman, so when it comes to cryptography, who knows that a good article might What kind of head is attracted to this field…

origin

On the whole, cryptography aims to enable the world to communicate securely through encryption protocols, or to securely share information between two or more parties, and to prevent malicious third parties from reading or intercepting private information. Cryptography covers many encryption modes, and protecting stored data in different ways is not exposed by third-party "stealing".

history

The history of cryptography can be divided into two time periods: classic and modern .

In the world of classical cryptography, information is encrypted by key combination or a set of letters or numbers and then decrypted by the same set of keys. A simple example is the "Caesar Password", where letters are simply shifted in alphabetical order and can be encrypted or decrypted. It is worth noting that once the private key is clarified, all previous encrypted information is unlocked. Overall, during the Second World War, although the encryption technology continued to improve, but the encryption method has not been surpassed, nothing more than a series of letter shifts and configuration, and ultimately were manually or by computer to crack.

Claude Elwood Shannon, an American mathematician who worked on cryptography at Bell Labs, founded information theory in 1948. He argued in information theory that the best encryption method should not display anything about the encrypted plaintext. information. It is important to know that information theory is to quantify information so that it can be shared.

Information is now defined as "entropy" or a measure of the uncertainty involved in a variable. For example, imagine that you are recording the result of a coin flip. The coin avatar may be 50% up, recorded as the number 1, and the coin avatar may be 50% down, which is recorded as the number 0. You record a series of 1 and 0 results, this sequence can not be compressed into a shorter string – because 1 and 0 occur equally, how can we shorten this string? Can't do it. But imagine that if the probability of avatar facing up is 80% and the probability of facing down is 20%, the number of 1 you get will be much more than 0, so we can compress the string to represent a real A larger number of 1s and 0s. This expression of a certain possibility is "information" and the principle of how compression works.

Shannon knows that to hide information, a good encryption method should create randomness so that the original information cannot be traced. For example, we encrypt the two English words COLOR and COLOUR, and we know that the two words are very similar. However, if we encrypt with an encryption mechanism, the result is completely different, it is perfect encryption.

This means that even if there is only a small change in the original message to be encrypted, it should be translated into a very different encrypted message, which is not exactly the same as the encrypted message of the original message. Interestingly, there is currently no encryption technology that can make a small change that affects all of the encrypted information. Cryptography is still pursuing perfect confidentiality.

Then, with the birth of the computer, modern cryptography was ushered in the 1970s, that is, the use of complexity theory to develop encryption methods, users can easily encrypt, decrypt or verify messages, without knowing the secret key, "violence The computational power required to break this method has proven to be quite high, making it difficult to achieve quantum computing.

Therefore, unlike the condition that encryption methods in classical cryptography must be kept secret, modern cryptography methods and algorithms can be shared. Even if you know the theory and algorithm in advance, you will hardly give you any advantage in "cracking them."

The following two milestone breakthroughs have brought the world into the era of modern cryptography:

• Digital Encryption Standard (DES)
• Public key cryptography (such as: RSA algorithm and Diffie-Helman algorithm)

DES (Data Encryption Standard) regulates the encryption of electronic data, which promotes a broader study of cryptography. (Off-topic, the US government's intervention in the development of DES has fueled people's distrust of the government's intervention in the backdoor encryption technology, etc. The debate about the advantages and disadvantages of enabling backdoor technology has continued to this day. ) Closer to home, DES has been in 2002. Superseded by the Advanced Encryption Standard (AES).

As for public key cryptography, it works as follows:

1. User A generates a (1) private key (private key) and a (2) public key (public key) .

What is the definition of a "key"? A key is a piece of information that determines the output of an algorithm. As a very simplified example, suppose User A has an algorithm F(x,k) in which she wants to "mask" a number x with the key k and then send it to another user B. The formula is as follows:

F(x, k) = x * k * 7

The value of x varies depending on the data or number that User A wants to share. User A then multiplies x by the key k to "hide" it.

Suppose User A's key is 10 and she wants to send the number 3 to User B. She will "encrypt" the number 3 with 3 * 10 * 7 = 210. User A will send 210 to User B. If User B knows the key k and the algorithm F, he only needs to divide 210 by 10 and 7 to "decrypt" the secret number, and the result is 3. However, in this example, the encryption key and the decryption key are the same, or symmetric encryption, that is, the same key 3 used for encryption and decryption.

In asymmetric encryption, the public key "encryption" and the private key "decryption" are two different numbers, and the algorithm is much more complicated than the one mentioned above.

In general, the public key is derived from the private key; however, to find the private key from the public key is "not computationally feasible." In regular terminology, this is called a trapdoor function —it is easy to handle in one direction, but it is very challenging to execute in the opposite direction.

Therefore, generating a public key from a private key is easy, but calculating a private key from a public key can be challenging. The greater the difference, the safer this approach is. Fundamentally, it relies on a fact in computing: multiplication is very fast, and division is much slower.

carry on……

2. User A sends her public key to User B.

3. User B encrypts a message to be sent to A with User A's public key.

4. User B sends an encrypted message to User A.

5. User A decrypts this message with her private key and then reads the message that User B sent to her.

In the RSA algorithm, in simple terms, a private key and a public key are generated based on a half prime number formed by multiplying two large prime numbers. As mentioned earlier, factorization (division) is computationally much more difficult than multiplication. However, RSA as a method of cryptographic integrity is declining.

The Global Security Index is a standard for quantifying the security of an encryption system. It translates the computing power required to break an encryption system into the energy required to "boil water." Based on this index, the 288-bit RSA encryption can be cracked by the power used to boil less than one teaspoon of water. Currently, most RSA cryptography uses a 2048-bit key.

We can compare a new type of private/public key cryptography, Elliptic Curve Cryptography (ECC) . Cracking a 288-bit ECC system requires the energy to boil all the water on Earth. Therefore, the latter is rapidly replacing RSA, which is the basis of the cryptography system used in blockchain and zero-knowledge proof. This is a fairly comprehensive summary of the comparison between ECC and RSA.

Before moving on, I want to remind you how important the use of cryptography is in history.

From Caesar to the present, the value of a country or a nation that can communicate safely is incalculable in terms of human life and economic value. As early as the Babylonian occupation of the Jeremiah in the Babylonian period, when the Babylonians were taken to Babylon by the Israelites, Babylon was called the "Shushak" who represented the secret code translation ( Jeremiah 25:26) ) may mean protecting the prophet from impunity. Even Thomas Jefferson was involved in cryptography. He made the Jefferson disc used by the US military. This invention was extended to the 20th century. Later, British scientist Alan Turing cracked the work of German Enigma cryptography and was thought to have shortened the time of World War II. There is no doubt that cryptography has changed history.

Why do you need zero knowledge?

In the private/public key example demonstrated above, note that User A should never expose her private key because any malicious party that obtains her private key can decrypt each encrypted message it gets.

Let's consider another situation: regular passwords are stored as hashes in most databases, not plain text. A hash is a function that converts an input into another unique string of data to mask or hide the original data.

In a hash function, it is actually "impossible" to unroll the original data from the unique data string created by the hash function. For example, the system can use the keccak256 hash algorithm to hash the password "3nY82$pwt4" to 0xc24ea779490258728751c1789aa30fa007261f5c052e22914599b46 ae13ccc5a. Looking at this combination of letters and numbers, even if you know the hash algorithm and use powerful computing power, you can't roll out the original password 3nY82$pwt4. Importantly, the hash function is decisive in definition, which means that the same input will always get the same output. Therefore, if a website stores your password as 0xc24ea779490258728751c1789aa30fa007261f5052e22914599b46 ae13ccc5a, then when you enter "3nY82$pwt4", the website can check if you are hashing it and comparing it with the hash stored in the database. The correct password was entered.

In the above example, please note that although the website does not store your plaintext password, you still need to share the password with the website through a secure channel to prove that you know your correct password.

Wouldn't it be nice if you could prove to the website that you know the correct password without sharing or revealing it to them? Or do it better, prove that you are the one you said now?

In general, this approach is the way most industries today validate information—providing information to validate it and recalculating it to verify that it is executed correctly and correctly. For example, if the bank wants to approve a wire transfer from your account to another account, the bank must check your account before transferring to confirm that there is enough money in your account to prove that you are not spending the money you actually do not own. Money. Similarly, if you want to prove your identity, you must provide your social security number or other government-issued identification.

In other cases, you don't need to know the details of the knowledge to check the results. For example, is Supplier A's bid higher than Supplier B? Supplier B should not see Supplier A's bid, and it is likely that neither party would want to disclose their bid to a third party other than the customer. However, a zero-knowledge proof can prove to a regulatory or auditing agency that supplier A’s bid is lower than supplier B’s.

This is what zero-knowledge proof provides: one party (certifier) can prove to the other party (verifier) that they have a particular piece of information without revealing what the information is.

Zero Knowledge Proof system

The Zero Knowledge Proof System was first proposed in 1989 by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in the paper The Knowledge Complex of Interactive Proof Systems . (It is worth noting that this paper was rejected for about three or four years before it was finally published. )

These initial zero-knowledge proof systems are interactive, meaning that the completion of a mathematical proof requires the interaction of the verifier and the prover to complete. This means that the verifier cannot operate independently and the prover must be present or can play to complete the proof. Now, we have developed a non-interactive evidence system in which a certifier can issue an evidence and leave it to the verifier for inspection.

The verification method of zero-knowledge proof emphasizes reliability and completeness. The principle of reliability means that the prover cannot persuade the verifier to accept a wrong statement. In fact, this is based on the possibility that the prover's possibility of producing a false evidence is very, very, very low, which is no different from the current encryption mechanism we have been trusting for decades. The principle of completeness means that a prover can persuade the verifier to accept a correct statement.

Obviously, one of the main features of zero-knowledge proof is that they can prove that information is known while ensuring privacy, but what is more interesting about zero-knowledge proof system systems is that they are more and more concise, which is often overlooked. A zero-knowledge proof system can prove information more succinctly than other methods. When verifying the time of an evidence, the time required to perform a calculation to verify its correctness is much shorter exponentially, and the latter is the most commonly used method for calculations in various current variations.

Replay calculations are costly and require time and resources. (Note that this is not the correctness of the verification algorithm or program – verifying the integrity of the calculation is completely another category. )

More importantly, this means that the computationally inefficient blockchain should be used to verify the evidence of the calculation, not the general calculation itself.

Fast forward to today's big environment, we have several practical examples of zero-knowledge proof systems:

Here we will briefly discuss:

• ZK-SNARKs
• ZK-STARKs
• Bullet proof

ZK-SNARKs

ZK-SNARKs is an abbreviation for " zero knowledge succinct non-interactive arguments of knowledge" . Zcash adopted this method. Zcash is now called Electric Coin Company, which uses this method to encrypt cryptocurrency. Payment anonymization. (Note: The Zcash blockchain is actually a fork of the Bitcoin blockchain. )

In the Zcash blockchain, miners do not need to know:

1. Who is sending Zcash (so there is no need to know how many Zcash they have) .

2. Who is charging Zcash.

3. The number of Zcash being passed.

However, the miners are still able to confirm the deal.

With ZK-SNARKs, miners have confirmed that no sender sends or creates more Zcash than the Zcash they currently own, and the receiver only receives the amount the sender is trying to send. In this way, Zcash becomes a true anonymous system. In Bitcoin and most public blockchains, including Ethereum, all transaction information is public, and the sending address, receiving address, and amount are known. In addition, the currency held in each individual account is known.

(It should be reminded that Zcash actually has two different address formats. The T addresses are public, and the information sent and received from these addresses can be considered a bitcoin blockchain. The Z address is private if a Z The address will send Zcash to another Z address, then the information will remain completely private. However, if a Z address sends Zcash to a T address, the information will become public. It is estimated that there is only 1% on the Zcash blockchain. The transaction uses a completely private transaction. Prior to the Sapling upgrade at the end of 2018, private transactions on the Zcash blockchain could only be performed on laptops due to size and memory requirements. Now, private transactions only take 2 – 3 seconds, in theory It's pretty amazing to be able to complete a transaction from a mobile device. Think about it, less than two years ago at the 2017 Scarbrough Thanksgiving Day, I had a privacy debate with my brother who was engaged in cybersecurity, we never thought of it. Zero knowledge trading can develop to such a fast trading speed in such a short time. I lost the debate, but said fairly The number of support each other just to get more than I do.)

How does ZK-SNARKs work?

The mathematical theory behind ZK-SNARKs is fine and dense, but can be concentrated (slightly) with the correct principles and theorems. The following is a compressed version of Christian Reitweissner's "SNARKs in a Nutshell" paper.

First, the problem is encoded and compressed into a set of polynomial equations as a quadratic operation.

t(x)h(x) = w(x)v(x)

Using these equations, the prover's goal is to convince the verifier that the equation holds.

These polynomials can be several items, and if you perform an equality check on a large number of points, the efficiency will be quite low. In order to introduce simplicity, ZK-SNARKs relies on the Schwartz-Zippel auxiliary theorem, that is, different polynomials are evaluated differently at most points, so as long as a small number of points are examined, it is possible to verify whether the polynomial used by the prover is correct. Thus, evaluation only requires a subset of points to prove the equation, and these evaluation points are random and secret. Randomness and secret points are often referred to as toxic wastes set by ZK-SNARKs. The setup phase generates a common reference string (CRS) that generates a random point s from which the polynomial is evaluated and a secret number α is generated to "shift" the value of the polynomial to maintain confidentiality. Sex. s and α are destroyed immediately after the setup phase, so malicious actors do not get them, and can only construct false evidence on their own.

The verifier can now check that the following polynomials remain equal at a random point s:

t(s)h(s) = w(s)v(s)

Next, it is to mask the randomness, secret evaluation points, and allow the verifier to use the evidence of the homomorphic encryption form to form a complete puzzle. In homomorphic encryption, values ​​are encrypted in such a way that they can be mathematically manipulated and then decrypted to display a value as if the original number were used in the evaluation. In other words, it allows you to hide numbers, perform an evaluation, and unhide, just as you do with the original, unhidden numbers (in this case not all mathematical operations, but some) .

The prover only knows E(s), but can calculate E(t(s)), E(h(s)), E(w(s)) and E(v(s)).

By multiplying the other secret value k to confuse the homomorphic encryption value, the prover can also hide its original information.

In essence, the verifier is checking the equation of the form below, t(s)h(s)k = w(s)v(s)k

How to set ZK-SNARKs?

Some people expressed doubts about how to generate "polynomial equations" and random settings mentioned above.

Regarding the questioning of the polynomial equation, the shortest version I can give is, is the equation to be proved initially (such as A > B? or A + B = C?) compressed into a loop, ie the constraint is Used to create these polynomials.

Also, how do you choose a random number?

In the first version of Zcash, the original founding members used a well-designed method to create this randomly generated toxic waste through what they called “ceremonies.” For a complete story, see this link https://www .wnycstudios.org/story/ceremony .

The "ritual" is ultimately a multi-party calculation (MPC) that produces random results. In other words, each member of the ritual (a total of six parties) produces their own unique random keys that are combined into a single random key. Recently, in the latest version of Zcash, Sapling, they implemented a new methodology for MPC – more than 80 participants generated a random private key for ZK-SNARKs. In this new approach, only one party needs to remain loyal, and the private key will not be copied. In other words, it means that all participants in the ritual must be apostasy in order to subvert the system.

ZK-STARKs

In contrast, STARKs (succinct transparent arguments of knowledge) are praised for their transparency and concise cryptography. Unlike ZK-SNARKs, STARKs do not require a trusted setup and therefore do not require the toxic wastes that appear in ZK-SNARKs – so they are transparent. STARKs are able to eliminate the need for trusted settings by using the Arthur-Merlin protocol. In the agreement, the verifier Arthur generates randomness for each problem, and the prover Merlin provides evidence by solving the problem.

STARKs also make their cryptography more concise by using a minimum of password assumptions and a balance between safe and anti-collision hash functions. This leaves a potential security risk in the post-quantum era. The minimum password assumption applies to interactive STARKs, while the non-interactive STARKs require Fiat-Shamir heuristics.

Starkware (https://starkware.co/) is working with 0x on a great project to use ZK-STARKs in decentralized and centralized clearing exchanges, and their articles on this topic are quite clear, Interested readers can find out.

STARK's certification and verification are faster than SNARKs and bulletproof proofs, except that the first STARK project and development tools in this area have just emerged.

Bulletproof proof

Bulletproof is another form of zero-knowledge system that does not require trusted settings, but it does require longer proof times than SNARKs and STARKs. These methods of proof have now been implemented in Monroe – the speed of implementation is staggering, and the publication of academic papers began in about six months.

Bulletproof is based on the existing range proof method, which combines multiple range proofs and has smaller data than previous methods.

Interestingly, bulletproof allows evidence to be aggregated, which means that you can collect and validate multiple pieces of evidence from different parties at the same time through multi-party calculations. In a recently published article, Zether bulletproof is deployed in smart contract privacy, and recently, JPMorgan Chase added these features to its proprietary, licensed blockchain Quorum .

 

Zero Knowledge Proof System Challenges

Zero-knowledge proofs are widely adopted and face some of the following major challenges:

Evidence setting time (developer tools / labor preparation)

For each calculation or scenario, a set of mathematical proofs must be generated to implement the encoding. So far, several development tools have appeared on the market; however, this still requires a challenging professional skill. The skill gap in the zero-knowledge domain (and, to a large extent, cryptography) is similar to the quantum computing field, because more developers must be trained to understand how to combine an application before it is widely adopted.

Evidence generation and verification time/scale requirements

Zero knowledge requires the prover to generate an evidence for verification by the verifier. Both of these activities take time, and the time required for this has been greatly reduced in recent years ( actually in recent months) , but this is still a problem to be considered for large-scale adoption.

Standardization of evidence

This article has explained the different methodologies for generating evidence, but each method has a similar starting point. Standardization is necessary to enable zero-knowledge proofs from the temporary processing of specific problems to the processing of a wider range of related problems and scenarios. The ZK standards organization is working to resolve related issues.

ZK-SNARK trusted setup requirements

Another factor to consider for ZK-SNARKs is that there is a need to establish a trusted setting in the world of encryption, or "toxic waste."

As mentioned above, in the trusted setting, a randomly generated "private key" is generated, which is used as a protected secret, so that the system generates a zero-knowledge proof as needed, which is the basis for the establishment of trusted settings. However, if the private key/toxic waste is compromised, anyone with a private key can provide false evidence—meaning they can provide evidence that they know a piece of information, but they don’t actually know it. It is where the vulnerability lies.

Remember, we said that ZK-STARKs and bulletproof proofs don't require trusted settings, but this year's Sonic is a new methodology that provides a generic, updatable reference character for ZK-SNARKs' trusted settings. String, which is a solution to simplify trusted settings for a larger evidence system.

a little touch

In the private sector, we have hardly begun to assess and understand where zero-knowledge proof systems are best suited for use, and which type of evidence is best suited for use under what circumstances. Be aware that much of the industry's energy is still researching where cybersecurity begins, not to mention how to incorporate zero knowledge into this strategy.

In the public domain, the rapid development of zero-knowledge proof in terms of speed and scale will undoubtedly impress the audience in related fields, but in the field of cryptocurrency, a wider audience has not had such a privacy solution so far. Resource input can be demonstrated by the low participation of blockchains that protect privacy.

Of course, it is fair to say that the smart contract's privacy solution is still at a very early stage (simple transactions are better) , and it is expected that this will accelerate the adoption of privacy protection methods in the public blockchain.

in conclusion

The zero-knowledge proof system detailed above is only part of the story that is happening in the field of cryptography. There are other forms of zero-knowledge proofs such as ZK-SHARKs and Mimblewimble. There are also some interesting developments in other areas of cryptography, such as fully homomorphic encryption and quantum cryptography.

The privacy and confidentiality provided by zero-knowledge proof and cryptography is superimposed to some extent, and its role in society depends on how you measure it.

For individuals who want to protect personal data or companies that protect trade secrets, it is a right to be an obligation to institutions that don't want to hurt it, just as those who enjoy freedom of speech are begged not to use it to harm others.

For the government (ideally) , it is a responsibility because it involves the rights of most citizens, and citizens want and believe that the government will allow us to protect our privacy and protect us from malice in a way that protects us. The actor abuses privacy violations; however, in reality, we know that this situation is impossible today.

Nonetheless, the goal of cryptography exists in both areas, so that a society can truly realize freedom: freely protect the privacy of information without fear of abuse of privacy. Given the history of cryptography over the past few centuries, one day in the future, along with the appropriate mathematical and scientific advances to be understood, cryptography may help the world achieve such goals, and this expectation does not seem crazy.

Chain Wen obtained the author's authorized translation and published the Chinese version of the article.

Author: Karen Scarbrough

Compile: Perry Wang

Source: Chain smell

We will continue to update Blocking; if you have any questions or suggestions, please contact us!