> For the complete documentation index, see [llms.txt](https://zokyo-auditing-tutorials.gitbook.io/zokyo-tutorials/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zokyo-auditing-tutorials.gitbook.io/zokyo-tutorials/tutorial-16-zero-knowledge-zk/theory/computation.md). # Computation {% hint style="info" %} [**Book an audit with Zokyo**](https://www.zokyo.io/) {% endhint %} {% hint style="info" %} 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. {% endhint %} > 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.