💻Computation

Book an audit with Zokyo

At a high level, a zero-knowledge proof allows a prover to convince a verifier that they know a certain piece of information without revealing what that information is. To understand this in a computational sense, you need to think of a function or computation that operates on some inputs to produce an output.

The computation phase, at its core, involves defining and understanding the problem you're trying to prove in a zero-knowledge manner.

Zero-Knowledge Proofs: The Computation Phase Explained

When working with zero-knowledge proofs (ZKPs), one of the first steps is defining the computation you wish to prove knowledge of without revealing specific details. This is often referred to as the "computation phase." Let's break down the "whats" and "whys" of this phase using an example.

What is a Zero-Knowledge Proof?

In simple terms, a zero-knowledge proof is a method by which one party (the prover) can prove to another party (the verifier) that they know a specific piece of information without revealing that information

Why Do We Need the Computation Phase?

Before any proof can be generated or verified, we first need a clear definition of the computation or problem we're addressing. This is critical because:

• Both the prover and verifier need to agree on the computation being proved.

• This computation will be the foundation for subsequent phases of the ZKP process.

Example: Proving Knowledge of a Secret Number using Zero-Knowledge Proofs

Suppose you wish to demonstrate to a colleague (designated as the verifier) that you possess a secret integer $x$ in the range [1, 100], yet you aim to keep $x$ undisclosed.

Representing the Computation

Function Definition: In the initial computation phase, our primary objective is to concisely delineate the function or computation under consideration. Let's designate our function as $f$. It's described mathematically as: $f(x)=x$ Here, $x$ signifies the secret integer.

Constraints: Subsequent to defining $f$, it's imperative to specify the boundaries or constraints within which $f$ operates. These constraints can be articulated as: $1≤f(x)≤100$

Public and Private Inputs: Delving into the realm of zk-proofs, there's a distinction between public and private inputs. The former is accessible to both the prover and verifier, while the latter remains exclusive to the prover.

In our delineated scenario:

• Private Input: The concealed integer, $x$.

• Public Input: The stipulation that $x$ lies in the interval [1, 100].

Desired Outcome

Concluding our zero-knowledge demonstration, the ultimate objective is for the prover to authenticate to the verifier the knowledge of an integer $x$ within the specified range, ensuring $x$ remains undisclosed.

The computation phase is the groundwork. It's where you define the problem, represent it mathematically, and determine the inputs and constraints. The steps that follow in the zk-proof process (like representing the computation as an algebraic circuit, translating it to R1CS, etc.) are about preparing this computation in a way that a proof can be generated and verified efficiently, without revealing the private inputs.

In practical zk-proof systems, the computations might involve proving ownership of assets, verifying correct transaction execution, or validating other complex conditions without revealing sensitive details. The key is to start with a clear understanding of the computation you want to prove, as that sets the stage for all the subsequent steps.

Problem Definition

The IsZero() Function: Our Computation -> SNARK Example

Let's delve into a conceptual function named IsZero(). Here is its pseudo-code representation

template IsZero() {
   signal input in;
   signal output out;
   signal inv;

   inv = (in != 0) ? 1 / in : 0;
   out = -1 * in * inv + 1;
   constraint: in * out === 0;
}

Function Breakdown:

Input (in): The function accepts an input named in.

Inverse Calculation (inv):

• If in is NOT zero, inv is assigned the value $1/in1​$.

• If in is zero, inv is designated as zero.

Output Calculation (out): The output is computed as: $out=−1×in×inv+1$

Constraint: The product of in and out must equate to zero, represented mathematically as: $in×out=0$

Relevance in ZKP:

In ZKP terminology, the prover's goal is to affirm to the verifier that they've accurately computed the IsZero() function to derive an output out from a specific input in without exposing the actual in value.

Diving Deeper into the IsZero() Function:

Inverse (inv): The inverse segment discerns if the input in is zero. If it isn't, the inverse is computed. For a zero in, as the inverse is non-existent, it is assigned zero. This precaution is to bypass computational discrepancies with non-zero entities.

Output (out): The mechanism involves multiplying in with its inverse (if existent), multiplying the product by -1, and then appending 1. In conjugation with the constraint, this method yields an output aligning with the function's logic.

Constraint: This serves as an integral logic checkpoint, validating the computation's accuracy. The product of in and out must perpetually be zero for computational authenticity.

Computation Phase Conclusion:

We've elucidated our conundrum: "Validate knowledge of executing the IsZero() function to acquire an output out for a given input in, without unmasking the in value."

As ZKP unfolds, this computation will metamorphose into mathematical illustrations apt for proof creation and verification, but the proof's core remains anchored to this function.

Importance of Computation Phase in ZKP: This phase is elemental for any ZKP. It orchestrates the direction, delineates the guidelines, and ascertains that both the prover and verifier have a mutual understanding of the proof's essence.

Public vs. Private Inputs:

For IsZero():

Private Input (in): The in signal represents the concealed input. The prover, being aware of this value, seeks to authenticate its knowledge sans disclosing the actual in value. Essentially, the aim is to affirm the accurate computation of IsZero() for a particular in without unveiling its value.

Public Input (out): Upon function execution, out can be shared with the verifier. While the verifier remains oblivious to the original in, they discern the consequent out and the constraint $in×out=0$. Through the ZKP mechanism, the verifier gets convinced of the prover's accurate function execution for an undisclosed in.

Summary:

• Private Input: in

• Public Input: out

Note: Real-world ZKP applications might exhibit a more intricate distinction between public and private inputs, contingent upon the specific protocol. However, in this instance and concerning the IsZero() function, the inputs' division is as depicted above.