# ZK Hack - Double Trouble - WriteUp
In Zk Hack 3rd puzzle solution, we will explore important parts of ZKP that will make our understanding of the overall zero-knowledge proofs systems easier and smoother. The terms used here will serve as the foundation for understanding many of my and others' articles on ZK.This write-up is the third part of my series aimed at understanding key ZK concepts through real life puzzles. These puzzles not only help in understanding the core concepts but also in assessing the security of various protocols, and where things can go sideways.

[Detailed Plan](https://x.com/0xhashiman/status/1865080568154648794)
[Puzzle link](https://github.com/kobigurk/zkhack-double-trouble)

## Introduction
To solve this ZKP puzzle as we always do, we must break down each major part into smaller sections, otherwise we risk getting lost in the process of finding the solution. However, before diving in and explaining the actual puzzle, it is essential to understand the notions and terms necessary to hack this. The first step is to carefully review the puzzle description.

pub const PUZZLE_DESCRIPTION: &str = r#"
Bob has developed a new zero-knowledge inner-product proof allows proving that
the inner product of a hidden, committed vector `a` with a public vector `b`
equals the claimed value `v` that is committed. He's released the protocol
license-free below, but still wants to profit from his invention. So, he
developed a proprietary prover that he claims is 2x faster than the standard one
described below, but without sacrificing zero-knowledge: it still hides all
information about the committed vector `a`. To back up his claim, he has
published a few proofs generated by this proprietary prover for the same `a` but
with respect to different `b` vectors, and has challenged people to recover `a`
from just these proofs.

Can you rise to the challenge and recover the vector `a`?.


The inner-product proof is obtained by applying the Fiat--Shamir transform to the following sigma protocol:

Before proof:
During proof of inner product with public vector b:
        Prover                                           Verifier
=================================================================================================
Offline phase (before `b` is available):
1. Prover computes 
    C_a := PedersenCOMM(a; α) 
         = sum_i (a_i * G_i) + α * H
    where G_i and H are random group elements, 
    and s is sampled randomly.
                            --------- C_a ---------->

Online phase for a given public vector `b` (can be repeated for different `b`s):

1. Prover samples a random vector r
    and random elements ρ, τ, υ.
2. Prover computes 
    C_r := PedersenCOMM(r; ρ)
    C_1 := PedersenCOMM(<a, b>; τ) // <x, y> denotes inner product of x and y.
    C_2 := PedersenCOMM(<r, b>; υ)
                            ---- C_r, C_1, C_2 ----->
                            <- random challenge γ ---
3. Prover computes 
    s := a + γr,
    u := α + γρ
    t := τ + γυ,
                            -------- s, u, t ------->
                                                // Check that `s` really is a + γr,
                                                Check PedersenCOMM(s; u) = C_a + γC_r
                                                // Check that the inner product is committed in C_1.
                                                Check PedersenCOMM(<s, b>; t) = C_1 + γC_2
==================================================================================================
"#;

After reading the puzzle introduction carefully, we can identify four important keywords: `Pedersen commitment`, `Sigma protocol`, `Inner-product proof`, and `Fiat–Shamir Transformation`. Understanding these keywords and how each one contributes to Bob’s system will provide a smooth learning curve to solve the puzzle. This understanding will help us comprehend what Bob built, how the system qualifies as zero-knowledge, the interactions between the prover and verifier, and the meaning behind terms like the hidden committed vector `a`, the public vector `b` and the committed value `v`.

## Commitment Schemes 101

### Definition
In this first part, we will focus mainly on commitment schemes and more precisely Pedersen commitments, since they serve as a building block and heavily used in more advanced protocols like inner-product proofs. A commitment scheme is a cryptographic scheme that allows a committer to commit to some data without revealing it. Later, the committer can "open" the commitment to prove they knew the value without revealing the entire data.
The general formula for creating a commitment to a value often involves elliptic curve points:
$$
C(a) = a \cdot G + r \cdot H
$$
where $G$ and $H$ are base points on the elliptic curve (or generators of the group), $a$ is the data being committed to, $r$ is a random number, and $C(a)$ is the commitment.

### Steps in Commitment Scheme

**Commit:**
- The prover creates a commitment $C(a)$ for the committed value $a$ by combining its value with an EC point and a **random blinding factor** $r$, also combined with EC points.

**(PS: Remember that even a public EC point will hide the scalar used in multiplication because finding the scalar is infeasible due to DLP)**

**Open:**
- The verifier will ask the prover to open the commitment and send both $r$ and $a$ used to create the commitment $C(a)$.

**Verify:**
- The verifier will then recalculate a new commitment based on the provided random value and the value $a$. It then checks if this recalculated commitment is consistent with the original commitment $C(a)$.

The two main properties of comitements schemes and the reason why we use them is because they preserve:

1. **Hiding:**
- The commitment $C(a)$ hides the value of $a$ from the verifier before it's opened. If someone only has the commitment $C(a)$, they won’t be able to learn anything about $a$ itself.

2. **Binding:**
- Once the prover generates $C(a)$, they are bound to it. They cannot later change it or provide a different value, otherwise the verification will fail.

### Pedersen Commitments
Pedersen commitments are a specific type of commitment scheme. They are a cryptographic scheme that allows committing to a value while preserving both hiding and binding properties. The commitment to a value $a$ is defined as:
$$
C(a) = aG + rH
$$

- $G$ and $H$ are public group generators
- $r$ is a random blinding factor chosen by the prover
- $a$ is the value being committed

**Key Properties:**
1. **Hiding:**
- The term $rH$ ensures that $C(a)$ reveals nothing about $a$ or $r$, as solving for $a$ is infeasible due to DLP.

2. **Binding:**
- Once $C(a)$ is created, the prover cannot change $a$ without invalidating the commitment.

## Inner-Product Proofs
Inner-product proofs use homomorphic cryptographic commitments (e.g Pedersen commitments) to create a full fledged ZK systems that preserves both zero-knowledge and soundness properties. The system is built on Sigma protocol, offering a standard framework for proving relationships between values efficiently.Specifically, inner-product proofs allow proving statements about the inner product of two vectors $\langle a, b \rangle$. These vectors can either be represented as raw vectors $\vec{a} = [a_0, a_1, \dots]$ or encoded as polynomials. In this chapter, we will focus on working with raw vectors to solve the puzzle and illustrate the main concepts. However, it is important to note that the entire system can also be represented using polynomials.

- The vector $a$ represents the prover’s private input or secret, which must be **hidden**.
- The vector $b$ is public because it typically represents verifier-generated or agreed-upon challenges.

### Sigma Protocol

Sigma protocols can be seen as a versatile blueprint for constructing zero-knowledge proof systems where a prover can convince a verifier of the truth of some statement in three interactive steps, without disclosing any more than whether the statement is true or false.

1. Commit: The prover commits to a value by sending some initial information to the verifier based on their secret and randomness.
2. Challenge: The verifier sends a random challenge typically represented as a scalar or some randomness.
3. Response: The prover generates a response using their secret the initial commitment and the verifier's challenge.

**PS: Interactive protocols can be transformed into non interactive ones using the Fiat-Shamir Transformation. This transformation will be explored in detail in the fifth article of my series, along with potential issues that may happen when implementing it.**

### Inner-Product Proofs
Inner-product proof system can be thought of as a more complex Sigma protocol tailored for proving statements about inner products, this systems allows the prover to prove that the inner product of two vectors $a$ and $b$ equals a claimed value $v$, without revealing the secret vector $a$.
The inner product of two vectors $a = [a_1, a_2, \dots, a_n]$ and $b = [b_1, b_2, \dots, b_n]$ is defined as: $$\langle a, b \rangle = \sum_{i=1}^n a_i \cdot b_i$$ The goal is to convince the verifier that$\langle a, b \rangle = v$. Where $v$ is the claimed value while keeping $a$ hidden. To handle vector $a$, Pedersen commitments are used as follows:
- The pedersen commitment $C_a$ to the vector $a$ is: ($n$ is the size of vector $a$, $\alpha$ is a random number)
$$
C_a = \sum_{i=1}^n a_i G_i + \alpha H
$$

### Prover-Verifier Interaction

This is how the inner-product proof system works for two vectors $a$ and $b$. The goal is to **prove that the inner product** $\langle a, b \rangle$ equals a committed value $v$, while keeping $a$ hidden from the verifier.

1. **Commit Phase (Prover):**
- The prover commits to the secret vector $a$ by computing:
$$
C_a = \sum_{i=1}^n a_i G_i + \alpha H
$$
where $G_i$ are public generators and $\alpha$ is a random blinding factor.
- The prover samples: A random vector $r = [r_1, r_2, \dots, r_n]$ and random scalars $\rho, \tau, \upsilon$
- The prover computes the following commitments using the public vector $b$:
$$
C_r = \sum_{i=1}^n r_i G_i + \rho H, \quad C_1 = \langle a, b \rangle G + \tau H, \quad C_2 = \langle r, b \rangle G + \upsilon H
$$
- The prover sends $C_a, C_r, C_1, C_2$ to the verifier.

2. **Challenge Phase (Verifier):**
- The verifier sends a random challenge scalar $\gamma$ to the prover.

3. **Response Phase (Prover):**
- The prover computes the following responses:
- The vector $s$:
$$
s = a + \gamma r
$$
- The scalar $u$:
$$
u = \alpha + \gamma \rho
$$
- The scalar $t$:
$$
t = \tau + \gamma \upsilon
$$
- The prover sends $s, u, t$ to the verifier.

4. **Verification Phase (Verifier):**
- The verifier checks two key relationships:
- Consistency of $s$ with $a$ and $r$:
$$
C_a + \gamma C_r = \sum_{i=1}^n s_i G_i + u H
$$
- Correctness of the inner product:
$$
C_1 + \gamma C_2 = \langle s, b \rangle G + t H
$$

### Inner-Product Proofs: Properties

The inner-product proof system satisfies the following key properties:

**Zero-Knowledge:**
The zero knowledge property ensures that the verifier learns nothing about the secret vector $a$. To achieve this, the prover uses randomness like $r, \rho, \tau$ when creating the commitments and responses. The random vector $r$ acts as a mask that hides $a$, so even when the verifier sees the response $s = a + \gamma r$, they cannot distinguish $a$ because $r$ introduces uncertainty. Similarly, the commitments $C_r, C_1,$ and $C_2$ include randomness that ensures no information about $a$ is leaked. As a result, the proof reveals nothing about $a$ while still convincing the verifier that the inner product claim is correct.

**Soundness:**
The soundness property ensures that the prover cannot cheat or provide false information. This is achieved through the random challenge $\gamma$, which the verifier generates and sends during the protocol. The challenge forces the prover to produce responses that are consistent with the original commitments. If the prover tries to use invalid commitments or incorrect responses, the verification equations:
$$
C_a + \gamma C_r = \sum_{i=1}^n s_i G_i + u H \quad \text{and} \quad C_1 + \gamma C_2 = \langle s, b \rangle G + t H
$$
will not hold, and the verifier will reject the proof. As a result, the prover can only succeed if they compute the inner product $\langle a, b \rangle$ honestly.

### Polynomials in Inner Product Proofs
Inner product proofs, or inner product arguments as they are referred to in research papers, extend far beyond vector arithmetic which is the main focus of this article. They use **polynomials** to encode vectors, a technique used in systems like Bulletproofs, which allows for more compact proofs and efficient verification.
For a vector $\vec{a} = [a_0, a_1, \dots, a_n]$, we can encode it as:
$$
f(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n
$$

The goal remains the same: to prove that the inner product of $a$ with a vector $b$ matches a committed value without revealing $a$ itself, or sometimes even both $a$ and $b$. By encoding the problem as polynomial evaluations, the prover and verifier will interact over a smaller dataset, ensuring scalability and faster interactions.

## Puzzle Walkthrough
### Puzzle Explanation
If you managed to understand all the notions explained above, you did not just make yourself ready to understand and solve the puzzle, but you learned a zk proof system called IPA (Inner Product Argument), which is also considered a foundation part of Bulletproof systems. Now we can actually move to explain the actual puzzle. Let's recall the goal of this puzzle, which is to recover the hidden committed vector $a$. But in order to actually pass the assert statement in [verify-double-trouble.rs](https://github.com/kobigurk/zkhack-double-trouble/blob/main/src/bin/verify-double-trouble.rs#L23-L30), we need both the random value used to make the commitment and the actual $a$ vector.
The function `commit_with_explicit_randomness` will then calculate a new commitment and compare it to the one from the proofs. Speaking of proofs Bob published two, let's first look at those and see what each proof contains and how we can recover $a$ and the random used $\alpha$.

Two proofs are provided $\pi_1$ and $\pi_2$:

Proof 1 -> $\pi_1(C_{r_1}, C_2, s_1, u_1, t_1)$
Proof 2 -> $\pi_2(C_{r_2}, C_1, C_2, s_2, u_2, t_2)$

The commitments $C_1$, $C_2$, and $C_{r_1}$, $C_{r_2}$ encode the inner products of the vectors we need to solve the puzzle:

For Proof 1 we have:
$$
C_1 = \langle a, b_1 \rangle G + \tau H
$$
$$
C_2 = \langle r_1, b_1 \rangle G + \upsilon H
$$
$$
C_{r_1} = r_1 G + \rho_1 H
$$

For Proof 2 we have:
$$
C_1 = \langle a, b_2 \rangle G + \tau H
$$
$$
C_2 = \langle r_2, b_2 \rangle G + \upsilon H
$$
$$
C_{r_2} = r_2 G + \rho_2 H
$$

It is impossible to recover $a$ from only the commitments of both proofs above because they are all EC points. We need to solve the DLP somehow if we want to find it, however this doesn’t seem to be the best and most efficient solution.

The responses $s$ from both proofs are also important since they are tied to the vector $a$ as well.
From Proof 1 we got $s_1$:
$$
s_1 = a + \gamma_1 r_1 \iff a = s_1 - \gamma_1 r_1
$$
From Proof 2 we got $s_2$:
$$
s_2 = a + \gamma_2 r_2 \iff a = s_2 - \gamma_2 r_2
$$
The equation we will have after we subtract $s_2$ from $s_1$ to eliminate $a$ is $\Delta$:
$$
(\Delta) \quad s_2 - s_1 = \gamma_1 r_1 - \gamma_2 r_2
$$

If we wanted to solve the puzzle using only the data we have now it is very hard and almost impossible. In other words, we must find a link that connects all of these equations in a logical way. This is where the puzzle name `Double Trouble` and the hint section help because they mention an important detail, `"Comm_r in proof 2 is double the comm_r in proof 1."`

This means: $C_{r_2} = 2 * C_{r_1}$ which is enough to recover all missing parts.

Now we have:
$$
C_{r_2} = 2 * C_{r_1} = 2 * (r_1 G + \rho_1 H) = 2 r_1 G + 2 \rho_1 H
$$

This also means:
$$
r_2 = 2r_1 \quad \text{and} \quad \rho_2 = 2 \rho_1
$$

At this stage, we can easily solve the equation $\Delta$ we got earlier by replacing $r_2$ in the equation with $2 r_1$:
$$
(\Delta) \quad s_2 - s_1 = \gamma_1 r_1 - \gamma_2 r_2
$$
$$
s_2 - s_1 = \gamma_1 r_1 - \gamma_2 * 2 r_1
$$
$$
s_2 - s_1 = r_1 (\gamma_1 - 2 \gamma_2)
$$
$$
r_1 = \frac{(s_2 - s_1)}{(\gamma_1 - 2 \gamma_2)}
$$

With what we found, we can solve:
$$
a = s_1 - \gamma_1 r_1
$$
and find the hidden vector because all variables are now known.

Now to the last part of the challenge, which is finding the random value $alpha$ used to create the commitment to the vector $a$. The only part of the proof that is linked to this random value is $u$ from both proofs:

$$
u_1 = \alpha + \gamma_1 \rho_1
$$
$$
u_2 = \alpha + \gamma_2 \rho_2
$$

Using the same logic we used to solve for $a$, let’s try and eliminate $\alpha$ by subtracting $u_2$ and $u_1$ to create the equation $\xi$:

$$
(\xi) \quad u_2 - u_1 = \gamma_2 \rho_2 - \gamma_1 \rho_1
$$

Recall from previously that $\rho_2 = 2 \rho_1$. Let’s substitute this into the equation $\xi$:
$$
(\xi) \quad u_2 - u_1 = \gamma_2(2 \rho_1) - \gamma_1 \rho_1
$$
$$
u_2 - u_1 = \rho_1(2\gamma_2 - \gamma_1)
$$
$$
\rho_1 = \frac{(u_2 - u_1)}{( 2 \gamma_2 - \gamma_1 )}
$$

Now we have an easy path to recover the random value $\alpha$. Using $u_1$, we can rearrange this equation to find $\alpha$. The equation we will have is:
$$
\alpha = u_1 - \gamma_1 \rho_1
$$
and we have all values to compute it as well.

### Puzzle Solution
You can add the code below in [verify-double-trouble.rs](https://github.com/kobigurk/zkhack-double-trouble/blob/main/src/bin/verify-double-trouble.rs) to solve the equations mentionned previously and recover $a$ , $\alpha$.

/// This function calculates the hidden random vector r₁ using the difference between vectors s₁ and s₂ along with verifier challenges
/// r₁ = (s₂ - s₁) / (γ₁ - 2γ₂)  
///  s₁: Response vector from proof 1  
///  s₂: Response vector from proof 2  
///  γ₁: Verifier challenge from proof 1  
///  γ₂: Verifier challenge from proof 2  
fn solve_eq_for_r1(s1: &[Fr], s2: &[Fr], challenge1: Fr, challenge2: Fr) -> Vec<Fr> {
    let delta_inv = (challenge1 - challenge2.double())
        .inverse()
        .expect("Challenge difference must have an inverse");

    s1.iter()
        .zip(s2.iter())
        .map(|(s1_i, s2_i)| (*s1_i - *s2_i) * delta_inv)
        .collect()
}

/// Recover hidden vector a from s₁, r₁ and γ₁ 
/// a = s₁ - γ₁ * r₁  
///  s₁: Response vector from proof 1  
///  γ₁: Verifier challenge from proof 1  
///  r₁: Recovered random vector r₁  
fn solve_eq_for_a_from_r1(s1: &[Fr], challenge1: Fr, r1: &[Fr]) -> Vec<Fr> {
    s1.iter()
        .zip(r1.iter())
        .map(|(s1_i, r1_i)| *s1_i - challenge1 * *r1_i)
        .collect()
}

/// This function solves for ρ₁ the randomness used in the commitment to r₁ using u₁, u₂ and verifier challenges
/// ρ₁ = ( u₂ - u₁ ) / ( 2γ₂ - γ₁ )  
///  u₁: Scalar from proof 1  
///  u₂: Scalar from proof 2  
///  γ₁: Verifier challenge from proof 1  
///  γ₂: Verifier challenge from proof 2  
fn solve_eq_for_rho1(u1: Fr, u2: Fr, challenge1: Fr, challenge2: Fr) -> Fr {
    let xi_inv = (challenge2.double() - challenge1)
        .inverse()
        .expect("Challenge difference must have an inverse");
    (u2 - u1) * xi_inv
}

/// This function recovers the random α used in the commitment to vector a 
/// α = u₁ - γ₁ * ρ₁  
///  u₁: Scalar from proof 1  
///  γ₁: Verifier challenge from proof 1  
///  ρ₁: Randomness recovered from ξ equation  
fn solve_eq_for_alpha_from_rho1(u1: Fr, challenge1: Fr, rho1: Fr) -> Fr {
    u1 - challenge1 * rho1
}

fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);
    let (ck, [instance_and_proof_1, instance_and_proof_2]) = puzzle_data();
    let (instance1, proof1) = instance_and_proof_1;
    let (instance2, proof2) = instance_and_proof_2;

    assert!(verify(&ck, &instance1, &proof1));
    assert!(verify(&ck, &instance2, &proof2));

    let challenge1 = challenge(&ck, &instance1, &proof1.commitment);
    let challenge2 = challenge(&ck, &instance2, &proof2.commitment);

    // STEP 1: SOLVE FOR r₁ USING s₁ AND s₂ and challenges
    let r1: Vec<Fr> = solve_eq_for_r1(
        &proof1.response.s,
        &proof2.response.s,
        challenge1,
        challenge2,
    );

    // STEP 2: SOLVE FOR a USING r₁
    let a: Vec<Fr> = solve_eq_for_a_from_r1(&proof1.response.s, challenge1, &r1);

    // STEP 3: SOLVE FOR ρ₁
    let rho1: Fr = solve_eq_for_rho1(proof1.response.u, proof2.response.u, challenge1, challenge2);

    // STEP 4: SOLVE FOR α 
    let alpha: Fr = solve_eq_for_alpha_from_rho1(proof1.response.u, challenge1, rho1);

    //Ensure the recovered vector a and randomness α match both commitments
    assert_eq!(
        ck.commit_with_explicit_randomness(&a, alpha),
        instance1.comm_a
    );
    assert_eq!(
        ck.commit_with_explicit_randomness(&a, alpha),
        instance2.comm_a
    );
}

## Key Resources
For further exploration into zero-knowledge proofs and related cryptographic concepts discussed in this article, the following resources provide detailed insights and explanations.
- [Pedersen Commitments Explained (Rareskills)](https://www.rareskills.io/post/pedersen-commitment)

- [Inner Product Algebra (Rareskills)](https://www.rareskills.io/post/inner-product-algebra)

- [Inner Product Argument (Rareskills)](https://www.rareskills.io/post/inner-product-argument)

- [Inner Product Argument Overview (Mimoo)](https://hackmd.io/@mimoo/ByuE81Q0_#Inner-product-argument)

- [Inner Product Arguments in ZKPs (Dankrad Feist)](https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html)

## Conclusion

I hope you enjoyed this article and that the core ideas behind Inner Product Arguments are now clear. In the next write-up, we will focus more on polynomials and their role in cryptography and ZKPs. Specifically, I will explain polynomial commitments and how they can be constructed using Pedersen commitments, then dive into schemes like KZG the foundation of PLONK and the main subject of the puzzle.