A possible cryptographic implementation of a zero-knowledge proving system is a “zk-SNARK”, and as far as I know it’s the oldest practical implementation of a zero-knowledge system.

zk-SNARK means Zero-Knowledge Succinct Non-interactive ARgument of Knowledge. 

Zero-Knowledge has the meaning explained above: nothing is revealed beyond truth of statement.

Succinct means that the proof is short (e.g. for the crypto people, let’s say that it can easily be stored in a transaction of an existing blockchain) and can be easily verified (e.g. it can be cheaply checked by a blockchain node when validating blocks).

Non-interactive means that we can write and store a proof, without the need to have question/answer cycles as in the introductory “snooker ball” example in the Home Page. So a proof can be computed and published say on a blockchain, and everyone can verify it.

ARgument of Knowledge roughly means that we can produce a cryptographic proof for the defined statement. A more precise explanation of the terms goes beyond the purpose of this text, and beyond my own knowledge of the subject, but intuitively an argument can be defined as a series of statements intended to determine the degree of truth of another statement. In our case, the argument is the proof that we can give of the defined statement. The argument needs to satisfy the property of completeness, i.e. true statements have proofs, and false statements don’t. And that’s all about the “Argument” part of the definition. With the term “knowledge” instead, we are saying that every prover producing a convincing proof of the defined statement, must “know a witness”; a witness in cryptography is a piece of information that allows to efficiently verify that the given statement is true. As an example, if the statement is y=HASH(x), where HASH() is a one-way function and y is a known value, x can be the witness: knowing that x, we can easily and quickly verify that the statement y=HASH(x) is true. So to wrap it up, “argument of knowledge” means the ability to produce a convincing proof of knowledge of a witness, x, to the defined statement, y=HASH(x).

 

In more practical terms, a zk-Snark offers a way to prove the correct execution of a defined computation, without disclosing the values used when performing that very computation. zk-Snarks are typically implemented as a sequence of 5 main steps:

  1. Representation of the computation to be proved, as a set of constraints among variables
  2. Reduction of the above set of constraints to polynomial equations
  3. Choice of a random value and one-way mapping of it and of all the equations to a “homomorphic” space, i.e a space where linear combinations (sums and multiplications to coefficients) still hold, so that the equations defined in point 2 are still true in this new space. It’s a one-way mapping, based on elliptic curve math, so it’s an “encryption” technique: it will be computationally unfeasible to calculate the original value if you only know the mapped encrypted point. The original chosen value will then be a secret, never known to anybody (“toxic waste”, “trusted set-up”, etc.)
  4. Proof creation, by mapping the equations, calculated in the chosen (secret) value, to the homomorphic space. Random values are used to further hide the equations in this phase, while preserving the equation structure.
  5. Verify the proof, by calculating that the equations stand. The verification is not performed directly in the mapped space, but values are once more mapped to a new space by a “pairing” function, that preserves and allows to check multiplication between the original variables.

 

As we can see, zk-Snarks are made of many components, and if we want to understand how they work, we need to understand each of these components, and then see how they are combined together.