ARN

In security, what is zk-SNARK?

An intro to the most popular zero-knowledge protocol.

Zk-SNARK, which stands for zero-knowledge succinct non-interactive argument or knowledge, is the most popular zero-knowledge protocol.

This a space of increasing importance, as zero knowledge systems are an area of active development that stand to disrupt how authentication works. While the math is intense, the overall ideas are not hard to understand. 

What is zero knowledge?

Zero knowledge is the attempt to use the smallest amount of information possible when verifying a statement. It works to devise proofs that avoid transfer of extra data.

Ground zero for this field is the paper Knowledge Complexity of Interactive Proof Systems, which appeared in a few editions during the 1980’s. As the name implies, the paper undertakes to get an understanding of how knowledge behaves in proving statements between interacting systems.

This paper is best understood as a descendant of Stephen Cook’s seminal 1971 paper The Completeness of Theorem Proving Procedures, which inspired the field of complexity theory in computer science. Cook’s paper attempted to explicitly look at and put bounds around the complexity of algorithms.

In a parallel way, the knowledge complexity paper brought knowledge into explicit focus, attempting to put upper and lower bounds around it in proofs.

Zero knowledge and authentication

By proof, we may understand authentication. When two or more software systems are in communication, and one party makes a claim, how does it prove its claim to the other parties?

Zero knowledge looks at how this is done and proposes methods alternative to naive approaches, methods that reduce the amount of knowledge-leak, thereby improving the security of the overall system.

For example, in a naive approach, a system may claim to have knowledge of a password. To prove it to another system, the password would simply be transmitted. Zero knowledge protocols work to convince with a minimum of knowledge, without sending the password itself in this example. Such proofs are based on probability. They allow for the high probability that authentication is valid.

Interactive proofs require the ongoing dialog between parties. The prover and the verifier engage in a back-and-forth, where the verifier interrogates the prover for information. Each correct answer increases the verifier's confidence (reduces the probability the prover is lying) in the prover’s claim.

The innovation contained in zk-SNARK proofs is that this process of dialog is encapsulated in a secure package that can be delivered once from prover to verifier. The verifier thereafter can interact with the proof itself. Hence, they are non-interactive proofs.

Non-interactive proofs were first demonstrated in 1988 in the paper Non-interactive Zero-Knowledge. This work set out the viability of encapsulating zero-knowledge proofs in a non-interactive format. 

This was followed in 2012 by From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again, which introduced SNARKs. Since then, the story has been one of incrementally refining and implementing the basic idea.

Implementations of zk-SNARK

If the SNARK idea is seen as a conceptual specification, then the first (nearly) practical implementation is the Pinocchio protocol, proposed in 2013.

In that paper, a scheme for public verifiable computation is described, wherein untrusted compute resources can be used to confirm execution of functions. This idea was further elaborated on and described in Succinct Non-Interactive Zero Knowledge for a Von Neumann Architecture.

The takeaway from much of the work here is that zk-SNARK seems to be an impenetrable mathematical thicket. Indeed, there are impressive mental feats that include Diffie-Hellman-like intuitive leaps, as well as an incredible amount of hard work in walking out the transformations that underpin working systems. Plenty of both inspiration and perspiration.

The complexity of zk-SNARK is compounded by its newness. The theory itself, as you’ve seen, is a recent development and still being elaborated upon.

Implementations are an especially active area, as the fundamentals become abstracted and then wrapped into libraries that are targeted at specific applications and use cases. Those use cases themselves are being discovered as the applicability of zk-SNARK is in-the-wild tested with working systems.

The use cases and the software systems that support them are of higher-order interest here, but before we turn to that, let's gain a deeper understanding of how zk-SNARK works without wading too deeply into the math.

How zk-SNARK works

ZK-SNARK fundamentally verifies that a computation has taken place. This is done by taking the original computation (i.e., a function) and expressing it in a very specific format. This is achieved through a series of mathematical transformations.

That final format is the actual zk-SNARK format that can be used to prove the computation has occurred with the given input (the input is called a witness in zk-SNARK, because it can be used to demonstrate the computation occurred with that argument).

Two comments are appropriate about that arrangement. First, for many applications, like proving possession of a password, the arrangement requires first altering the desired claim into a functional equivalent.

For example, in the case of a password, the plain-text password can be run through a hashing algorithm. The thing that will then be proved is that the hash was run against the password, which is equivalent to proving possession of the password.

The other comment is that the nature of verifiable computation opens up a new model of computing that has implications beyond simple statement authentication. That model enables outsourcing of computation to third party resources, even in a trustless environment, because the resource can demonstrate cryptographically the execution.

This has major consequences for blockchains, because instead of verifying transactions by broadcasting the actual information, blockchains can use zk-SNARKs to broadcast only the proof. The MINA protocol is an example of a blockchain working on this line of thinking.

Outsourcing computation in this way may have use cases beyond blockchain as well, in creating a kind of compute marketplace without the need for trusted third party organisations. Today, those organisations are generally cloud providers of various types.

The transformations that SNARK uses, after the statement is phrased as a function, follow this general pattern (from Vitalik Buterin’s Quadratic Arithmetic paper): the original computation -> algebraic circuit -> rank 1 constraint system (R1CS) -> quadratic arithmetic program (QAP) -> Linear PCP -> Linear interactive proof -> zkSNARK.

The referenced paper offers a good account of the first 4 transformations. For an excellent plain-English tour of the entire process, The Why and How of zk-SNARK is recommended. Another good resource for zk-SNARK and zero knowledge in general is the Zero-Knowledge blog.

The key trick zk-SNARK performs is in turning the computation into a polynomial form. In that format, the computation can be proven by testing for points on the graph of polynomials.

That is, solutions to the polynomial are used to verify the prover is actually in possession of the proof, instead of the polynomial itself. By testing a number of points, the proof increases the probable reliability.

So the first part of the transformations are responsible for turning a function into a mathematical form (algebraic circuit -> R1CS) then turning it into a polynomial (QAP) then turning it into a form that is efficiently verifiable (Linear PCP -> Linear interactive proof) and finally a transmittable form: the SNARK itself.

There may be other approaches to encapsulating zero knowledge proofs into a non-interactive form, but today, this is the main approach.

Applications for zk-SNARK

In addition to the potential for moving blockchains to verifiable computation, zk-SNARKs may support zero-knowledge style authentication, both in terms of providing credentials for login, as well as more broadly for establishing statements.

For example, asserting that the user has a bank account over a certain amount (this would require interacting with the bank as a third-party).

By using zk-SNARKs, a kind of anonymous authentication is possible. That is to say, the user can demonstrate that they are permitted to access a resource based simply on a fact in their possession, as opposed to their identity. Such a mechanism increases the safety of secure systems by limiting the amount of knowledge exchanged in performing authentication activities.

Finally, it is possible to implement fully anonymous payment systems with zk-SNARK. A transaction can proceed by verifying available funds, assuring that they are in escrow, verifying delivery of goods and completing the contract, all without ever divulging either party’s identity.