💻Computation
Last updated
Last updated
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.
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 in the range [1, 100], yet you aim to keep 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 . It's described mathematically as: Here, signifies the secret integer.
Constraints: Subsequent to defining , it's imperative to specify the boundaries or constraints within which operates. These constraints can be articulated as:
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:
Desired Outcome
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.
The IsZero() Function: Our Computation -> SNARK Example
Let's delve into a conceptual function named IsZero()
. Here is its pseudo-code representation
Function Breakdown:
Input (in
): The function accepts an input named in
.
Inverse Calculation (inv
):
If in
is zero, inv
is designated as zero.
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.
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.
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.
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.
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.
Private Input: The concealed integer, .
Public Input: The stipulation that lies in the interval [1, 100].
Concluding our zero-knowledge demonstration, the ultimate objective is for the prover to authenticate to the verifier the knowledge of an integer within the specified range, ensuring remains undisclosed.
If in
is NOT zero, inv
is assigned the value .
Output Calculation (out
):
The output is computed as:
Constraint:
The product of in
and out
must equate to zero, represented mathematically as:
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 . Through the ZKP mechanism, the verifier gets convinced of the prover's accurate function execution for an undisclosed in
.