Background

Assumed knowledge

  • Polynomials, Basic linear algebra

  • Homomorphisms

  • ECC, Bilinear Mappings

In this background section, we will offer the user a relatable high-level overview of the process, before diving into the technicalities, section by section.

Example

Let‘s consider a simple scenario where we are trying to create and verify ZK proofs to assess if a user knows how to compute a particular equation for some arbitrary inputs.

f(x) = (x1 * x2) / (x3 - x4)

The user picks arbitrary values for x1 through x4, including the expected output, f(x). The user’s claim is that his provided values of x and f(x), honour the equation above.

Meaning to say, if he had provided values like so:

# User inputs
x1, x2, x4 = 2
x3 = 4
out = 7

f(x) = (x1 * x2) / (x3 - x4)
     = (2) / (2)
     = 1

# but out != f(x) -> 7 != 1

His claim of knowing values of x and f(x) would be incorrect, and this reflects that he does not have knowledge of the actual computation being executed.

Alternatively, if he had provided values such that the calculated f(x) matches his claimed value of out - we have proof that he does indeed have knowledge of the computation.

Another way we can present this to be more digestible is as a program. This program calculates f(x) to verify if the user’s claim is correct. The claim the user makes is that he knows how to execute the computation correctly.

def someProblem(x1, x2, x3, x4, out):
		res = (x1 * x2) / (x3 - x4)
		assert res == out, "invalid calculation"

Here, out represents the final value as calculated by the user. This is required to verify his claim of accurate computation.

We can go on to transform this program into a series simple arithmetic operations, to create a system of constraints:

(1) v1  <== x1 * x2
(2) v2  <== x3 - x4
(3) out <== v1 / v2

These constraints serve to map out the final output from the provided inputs/claim of knowledge sequentially. One can also think of them as assert statements, stepping through the program’s execution.

From the user’s provided values of x1, x2, x3, x4, the intermediate values v1 and v2 are calculated. Then v1 and v2 are divided and checked against the out value provided by the user.

In the event, incorrect values were provided, out would not equal to v1/v2, and the last step would fail.

This is simple illustration of ZK circuit generation from a computational problem. For now, the only thing the reader has to take away from this is that circuits are based on such a system of constraints.

Wherefore art thou prover-verifier?

Let’s have a bird’s eye view for a moment to understand how the different components come together.

We have two key components, the prover and the verifier. The prover exists to generate ZK proofs, which serves as a “signature” for some specific set of values provided by the user - that is assumed to be fulfilling the constraints of the defined problem - in this case our equation f(x).

The verifier will verify if the provided signature is valid, and therefore ascertaining by proxy if the user provided values are correct, without knowing what those values are to begin with.

Proof generation is computationally intensive and is done off-chain, typically client-side via some WASM module that runs in the browser.

Here, the user provides to the prover what he thinks the correct inputs are [x1, x2, x3, x4, out]; the prover then creates a cryptographic signature which obfuscates the original values but preserves certain structures of computation such that the verifier will be able to ascertain that the computational steps are honoured. (Think homomorphic hashes)

This proof will be passed to the verifier which checks if the proof is valid.

Witness: SNARK Prover input parameters

  • inputs to the equation [x1, x2, x3]

  • intermediate values [v1,v2]

  • final output value [out]

The witness is all of these prerequisite values: [x1, x2 ,x3, x4, v1, v2, out]. Therefore, it can be said that the witness consists of all the input values to the witness.

Common literature explains the witness as the piece of information required to prove a claim/statement is true.

  • Prover: The party trying to prove the statement is true, without revealing the witness.

  • Verifier: The party verifying the statement’s truth without learning the witness.

In common literature it may appear that all of these inputs are user provided, however from an implementation standpoint most libraries allow for automatic calculation of intermediate values. Thus the user will typically only have to provide the primary inputs: [x1, x2, x3]

In the next sections we will explain the various steps involved in proof generation and verification. Now for the deep dive.

Next1. Arithmetization

Last updated

Was this helpful?