Putting Some Knowledge Behind Zero Knowledge
Zero Knowledge Proofs (ZKPs) are mathematical proofs that allow data to be verified by some party without the prover needing to reveal the contents of the data. ZKPs were first conceived in 1985 by Goldwasser, Micali, and Rackoff in “The Knowledge Complexity of Interactive Proof-Systems”. These problems were used in the early 90s to make breakthroughs in computer science complexity theory, such as proving that all problems in class NP have zero-knowledge proofs. In the 21st century, ZKPs are actively being pursued as an L2 scaling solution for blockchains like Ethereum. The following is a comprehensive overview of the mathematics and structure of ZKPs as they relate to the field of mathematics and computer science.
The Structure of a ZKP
ZKPs are like many interactive proof systems, in that they must be complete and sound to ensure security and honesty in computational systems. However, beyond these fundamental properties, they include a third component that measures the proofs scale of achieving “zero-knowledge”, or abstraction from the information being proved. We will examine and dissect the different properties that are necessary to have a ZKP. Formal ZKPs are proved using Turing-complete machines, meaning they must be capable of computing any given, infinite output, computer algorithm using a set of discrete variables that are selected from some finite alphabet. As an aside, alphabet in this context does not just include letters but rather any discrete variables.
Completeness
A ZKPs completeness is defined as the verifier's ability to be convinced of some statement by the prover. In proper terms, a proof is complete when some prover, P, with a valid statement, x, in a language, x ∈ L, can convince an honest verifier, V, that their zero-knowledge representation of the statement S is true. This must be true for all statements in a language made by the same prover and verified by the same verifier. Say we want to use a ZKP to prove multiple things in one language, for all x ∈ L, p must be able to prove to v that all x is true. This means that a proof system is only complete when p can prove all statements x to be true. Simply put, a proof system is complete if the prover can prove all statements to the verifier in the system.
We can consider a machine complete if, in the case of an adversary, say A, who wants to attack the system, our prover P holds a significant advantage over A in proving x to V. In the case of an attacker trying to disprove some given proof, they will win if they take the same arguments as P must prove, say A(x), and V outputs false, meaning the proof has failed and the attacker has won. On the flip side, a prover can win if, given the same argument, P(x) results in V outputting true or an error, meaning either the proof is true or the proof does not exist. If the probability that P wins for all statements is significantly higher than A, such that A’s probability of attacking the system successfully is negligible, the system is considered complete.
The probability of an attacker’s advantage can vary based on multiple variables in a proof system. Attackers with significantly better computing equipment, memory optimization, speed or run time, and incentives can determine how much of an advantage they hold. There can be systems in which the advantage of an attacker is statistically complete (also known as unconditionally complete) where the probability of winning is non-zero, and there is also perfect completeness where adversaries have zero advantage.
Soundness
For ZKPs to be considered sound they must be resistant to a cheating prover. This does not mean that cheating provers cannot exist in a proof system, but rather that a cheating prover must have little or no chance of convincing an honest verifier that some statement is true when it may not be or vice versa. We will use a similar example to the one discussed in the completeness portion above to illustrate how this may occur.
Consider an attacker, A, who wants to disrupt the soundness of a proof system. They will win if they take the argument of some statement y that does not exist in the language L, y ∉ L, and the verifier accepts the proof as valid. Thus, if A can convince V that some statement y, which is not an element of the trusted L, then the proof system is not sound. If the prover, P, can prove to the verifier that x is the valid proof because it is an element of L. it will render y invalid and the verifier will accept P’s proof and reject A’s proof. This will classify the proof system sound.
There is often confusion in delineating between the completeness and soundness of a proof system. It is important to note that these components are not mutually exclusive. For example, you may have a system that is complete but not sound. This means the prover is always able to prove all statements, even false ones, but because of this, determining if those statements are true is impossible. The same is true for systems that are sound but not complete. A prover could prove nothing in a system, making it sound but incomplete as the system is incapable of producing proofs for all statements.
Zero-Knowledgeability
Zero-knowledgeability is the most important component of a ZKP as it is what differentiates a ZKP from a normal proof system. It a given statement is accepted by the verifier, the proof is considered to be a ZKP as long as the verifier has learned nothing about the statement other than the fact that it is true. They cannot know the contents or details of the statement and they must be able to verify the truth of the statement given these barriers. This is possible if the verifier has some simulator that generates a proof that is adjacent to that of a proof that would occur between an honest prover and verifier. This simulated proof is not identical in material or structure to the ZKP, but it is accurately able to prove the statement of the ZKP. This is by far the most complicated and difficult part of implementing ZKPs in practice.
Applications of ZKPs in Mathematics
The most common examples of ZKPs tend to abstract away all mathematics and describe scenarios in which some prover needs to convince a verifier of an abstract concept without revealing too much information. The classic “Where’s Waldo” and “Two Balls and Color-Blind Friend” problems have made it easy to visualize and conceptualize how ZKPs work in social settings. However, the application of ZKPs to the blockchain is not as simple. They involve compressing complex metadata, cryptographic encryption, and advanced mathematic solutions to ensure efficiency. To delve into these complexities, we will analyze two commonly studied use cases of ZKPs in mathematics and their underlying logic.
Hamiltonian Cycles in Undirected Graphs
Imagine we have an undirected graph made up of n nodes and e edges, represented as G. Our prover wants to prove that there exists a Hamiltonian cycle in G. A Hamiltonian cycle is a path that traverses through a graph such that no node is visited twice and all nodes are visited at most once. Our prover, however, does not want to reveal the order in which this cycle occurs, which nodes are passed through first, or what direction the cycle is moving in between any of the edges in the graph. They can use a ZKP to achieve this goal and prove to the verifier that a Hamiltonian cycle exists in the graph without revealing any of the details they are concerned about.
The first thing our prover will do is create a new graph, H, that is isomorphic to G. This means that H has the same number of nodes and edges between them, but they are all labeled differently and placed at different areas.
Because the graphs are isomorphic, our prover will be able to identify a Hamiltonian cycle within H the same way they identified a cycle within G. Once our prover has created H, they must commit an immutable list of all the nodes in H and G, and identify which nodes have a connection in any order. This ensures that the prover cannot change H and ensures that the verifier still does not know the structure or layout of H but is aware of the number of nodes and which nodes have edges between them.
After the commitment has been made, there are two ways that the verifier can confirm the proof. The verifier can ask the prover to identify the isomorphic translation between the graphs. At this point, the prover will reveal the committed list and translate the edges on G in terms of how they are connected to H. This proves the graphs are isomorphic and proves the statement that any cycle in H will exist in G. The other thing the verifier can ask is for the prover to prove that there exists a Hamiltonian cycle in H. The prover can simply only uncover the edges that are in the Hamiltonian cycle which is enough for the verifier to confirm if a cycle exists or not. It should be noted that the verifier will only verify using one of these methods, not both. This is common with ZKPs as part of the process of proving is verification over multiple iterations with some level of obscurity on which verification method the verifier will ask the prover to provide. In each iteration the probability of a verifier asking for one method or the other is random so over a consistent number of iterations, it becomes difficult to falsify the proof.
This proof confirms that the prover was able to convince the verifier that a Hamiltonian cycle exists in graph G without revealing what G looks like, what the placement and paths of individual nodes are, and what direction the cycle is moving in. This ZKP is complete because the prover can prove for any isomorphic translation of G that there exists a Hamiltonian cycle. They can rename all of the nodes and reassign the edges and still get the same result for all combinations that exist. The proof is also sound since the prover must guess which method of verification the verifier will choose. Either they will be asked to identify the isomorphic translation or the Hamiltonian cycle. This means the odds of the prover fooling the verifier are 2-n where n is the number of rounds a verifier is verifying. Thus, it becomes extremely difficult to convince a verifier of a false proof given an increasing number of verifications of the same proof. Finally, the proof satisfies the property of zero-knowledgeability since none of the information being revealed by the prover exposes details of the original graph, G, other than the number of edges and nodes in the graph and which nodes are connected by an edge. If our prover was asked to recreate G with the information given, they would not be able to recreate the graph in an identical fashion to the information given in the proof.
Discrete Log of Integers
Consider the case in which our prover wishes to validate some information they are sending to multiple people because they wish to remain anonymous but still send information consistently (think of Satoshi Nakamoto wanting to release another whitepaper and needing to convince people that they are indeed Satoshi Nakamoto without revealing their identity). For this to occur, our prover can use a ZKP of some discrete log value to prove their identity without revealing any information about their identity.
To understand the structure of this problem, it is important to understand how discrete logs work. A logarithm is the inverse of some exponential function. Say we have the function ax=b; to convert this exponential function to a logarithm we would write loga(b)=x. Discrete in this context just means relating to numbers that are not continuous, such as 1.5 or 1.4999. It is also important to understand how modular arithmetic functions to fully digest the mechanism by which this ZKP is working. Modular arithmetic, or mods, function as a way for numbers to wrap around some discrete variable. Clocks are a common example of tools that use modular arithmetic, as time wraps around and resets every time, we reach the number 12; thus, clocks are mod12. For this problem, we will be using a combination of exponential, logarithmic, and modular arithmetic to allow our prover to prove they are a trustworthy individual without them needing to reveal any information about themselves.
Our prover wants to prove that for some generated integer, g, a large prime number, p, their identity represented by the integer, x, and some information y that is the result of the function gxmodp = y, that they know the value of x without revealing x, as it is their identity that is allowing them to create the information y.
To begin the proof, our prover will generate some random number, r, and compute a value C=grmodp. The prover will then disclose C to the verifier. At this point in the proof, the prover has access to all the variables in the proof and the verifier only knows the values of C, g, p, and y.
The verifier can now verify the ZKP by asking one of two questions:
· First, they can ask the prover to reveal r, the random number, and then calculate whether C is derived from r by calculating grmodp.
· Second, the verifier can ask the prover to compute the value of (x+r)mod(p-1) and only send the output. The verifier can then check if this outputted value is equal to C*ymodp by computing goutputmodp.
If the prover truly knows x, then C*ymodp = goutputmodp in all cases since r being truly random means there could be an infinite number of values that (x+r) could be to result in some value smaller than our (p-1) value. To simplify this, let's consider a base case of mods. Two modular equations, 1601mod4 and 1201mod4 both equal 1. In this case, our x value could be any number between 0 and 1201 or 1601 respectively as our r would be the complement of x on the lefthand side of the mod. As the values get larger, it becomes increasingly difficult to predict what sum of values is giving us the lefthand side of the mod, and even then, there is an equally distributed probability that any of our set of numbers that result in mod4 = 1 is the combination of x+r. From there it becomes difficult to guess that r is without running a new iteration of the proof and losing the initial x+r value we asked the prover for. Therefore, the verifier can only ask one question since they must first verify that the randomness from the prover is honest and then confirm that the prover truly knows x.
To solidify the ZKP, the verifier will ask one of the two questions over a number of iterations. The probability of one question being asked over the other is equally distributed and random. Thus, the verifier may ask for the prover to either confirm that they have the same random number or the same result from the equation listed in question two over a series of iterations. The odds of the prover fooling the verifier shrinks proportionally to the same rate as the Hamiltonian cycle problem since there are two potential questions that the verifier may ask and the prover cannot, with certainty, predict what the verifier may ask during each iteration. Thus, the final probability of fooling the verifier is 2-n where n is the number of iterations.
This proof satisfies all the properties of a ZKP. It is complete since the prover can prove for any value x that they know x without exposing any information about x to the verifier. The proof is sound since each iteration of confirmation between the verifier and prover results in the probability of falsifying the proof is exponentially smaller. Finally, the proof adheres to the zero-knowledgeability property since the verifier will never know what x is but will be confident that the prover knows x.
Conclusion
The application of ZKPs as a scaling solution in the blockchain is increasingly being seen as the “holy grail” of scaling solutions. Through the implementation of ZK-roll ups and other scaling solutions that leverage zero knowledge, L1 chains, like Ethereum, are aiming to optimize transaction processing and execution. Understanding the roots and applications of ZKPs is thus incredibly important as these technologies continue to scale and the opportunities to contribute to the creation of ZK-infrastructure are in high demand. By learning about the application of ZKPs in multiple mathematical contexts, we can translate theoretical mathematical principles to the blockchain, accelerating the process of scaling and improving the overall user experience for blockchains across the ecosystem.
