Comment on page

# ZKP(Zero-knowledge Proof)

Non-Interactive Zero-Knowledge (NIZK) algorithms transform programs into polynomials and commit to these polynomials. For instance, the classic PLONK algorithm requires commitments to each gate and the relationships between them. When committing, each gate is committed based on elliptic curve bilinear mapping, which demands extensive memory and time for the prover to generate ZKP. Additionally, TrustSetup is required, which can be challenging in scenarios where the client generates ZKP.
Conversely, IZK algorithms are interactive, eliminating the need for TrustSetup. They can directly generate Vector Oblivious Linear Evaluation (VOLE) interactively and commit to each gate. Since VOLE is linear, it allows for batch processing. The prover and verifier can also perform local calculations simultaneously, aggregating and verifying the results at the end, significantly improving computational efficiency.

### Interactive Proof System

In computational complexity theory, an interactive proof system represents computation as an exchange of messages between two parties: a prover and a verifier. These parties interact to determine whether a given string belongs to a specific language. Although the prover has unlimited computational resources, it is considered untrustworthy. In contrast, the verifier has limited computational power but is assumed to be honest. The exchange of messages continues until the verifier is satisfied with the solution and convinced of its correctness.
Essentially, an interactive proof system can be understood as follows:
1. 1.
Interactive method for Prover to prove to Verifier the knowledge of a secret
$\mathcal{S}$
.
2. 2.
Completeness:
$\mathcal{S}$
is true
$\implies$
Verifier will be convinced of this fact.
3. 3.
Soundness:
$\mathcal{S}$
is false.
$\implies$
No cheating prover can convince the verifier that
$\mathcal{S}$
is true.

### Interactive Zero-Knowledge Proof

Building on the interactive proof system, we introduce zero-knowledge properties:
1. 1.
Interactive method for Prover to prove to Verifier that a statement
$\mathcal{S}$
is true, without revealing anything other than the veracity of
$\mathcal{S}$
.
2. 2.
Completeness:
$\mathcal{S}$
is true
$\implies$
Verifier will be convinced of this fact.
3. 3.
Soundness:
$\mathcal{S}$
is false
$\implies$
No cheating prover can convince the verifier that
$\mathcal{S}$
is true.
4. 4.
Zero-Knowledge:
$\mathcal{S}$
is true
$\implies$
No cheating verifier learns anything other than this fact.
The goal of the zkPass Protocol is to maintain responsiveness (with quick client responses) even when the client has extremely limited memory and computing resources. As a result, we have significantly upgraded the ZKP algorithm.
Interactive Zero-Knowledge (IZK) proofs with optimal memory footprints have attracted considerable interest because these protocols can efficiently prove large computations with minimal memory requirements.

### The ZKP implementation in zkPass The final step of the zkPass protocol involves the client generating zero-knowledge proof, which the smart contract on the blockchain verifies. We employ a Hybrid Zero-Knowledge (ZK) approach that combines both interactive and non-interactive ZK protocols.
Interactive Zero-Knowledge (IZK):
We utilize a VOLE-based interactive Zero-Knowledge (ZK) protocol, which we refer to as VOLE-ZK 23. This protocol plays a crucial role in authentication, ensuring the data's origin from the precise data source and safeguarding it against tampering by clients. The VOLE-ZK 23 protocol can be described as a "commit and prove" framework. In this setup, both the Prover (P) and the Verifier (V) jointly generate numerous VOLE instances, each satisfying a linear formula denoted as "m = k + w * delta." P holds certain components of this formula as a commitment, with 'm' serving as the commitment, and 'w' can be converted into a witness after derandomization.
On the other hand, V holds the remaining components ('k' and 'delta'). The objective is to prove and verify the satisfaction of a boolean circuit. P establishes a commitment for every gate based on the VOLE instance. Since the correlation between VOLE instances is linear, we can batch-check the results by summing up all commitments and confirming whether the final result still adheres to the correlation. This linearity is a key reason our solution is cost-effective, setting it apart from other high-degree polynomial solutions like SNARK. Consequently, P only needs to transmit two field elements (the sum of 'm' and the sum of 'w') to the Verifier. To protect sensitive information, a random linear combination can be created. V then validates the correlation using its VOLE parameters ('k' and 'delta').
There are five main constraints at this stage:
The vector x = (Q', R', mac_key_pv, b) represents the public signal, and w = (enc_key, token, Q, R) is the witness.
Dec(enc_key, Q') = Q, and Q = Query(token)
The first two constraints are related to the HTTP requests made to the trusted data source. The first constraint ensures that the request is encrypted using the encryption key. The second constraint specifies that the request must be generated using the user's access token, typically stored in cookies in most cases. These two constraints confirm that the user is using their personal data (such as a username and password) and is following a specific API defined in the template.
Dec(enc_key, R‘) = R
R' represents the response received from the trusted data source and is encrypted using the encryption key. Therefore, this constraint implies that the user must possess the encryption key, generated during a three-party handshake, to decrypt the response. This constraint serves to ensure that the user cannot create a counterfeit encryption key.
Verify(mac_key_pv, MAC, R) = 1
R stands for the decrypted response. It's crucial for the zkPass protocol to ensure that this response (R) remains unaltered by the user. To substantiate this, the constraint is applied. The additional MAC (Message Authentication Code) data attached to the end of R is generated using the MAC key. The verification process employs HMAC with the SHA256 hash function. This verification step serves as a safeguard against any unauthorized modifications to the response data by the user.
b = Assert(R)
The final constraint signifies that the data contained within R must adhere to specific conditions outlined in the template. For instance, if R is structured as a JSON object like {user: xxx, age: 30}, it necessitates that the "age" property must have a value greater than 18. In simpler terms, this constraint ensures that the data inside R complies with predetermined criteria.