# Write Up of ZK Hack Puzzle 3: Double Trouble
###### tags: `ZK Hack` `Cryptography`
by [grjte](https://gist.github.com/grjte)

This puzzle, built by [Aleo](https://www.aleo.org/), marks the halfway point of the incredibly fun learning experience that is [ZK Hack](https://www.zkhack.dev/puzzle3.html). If you haven't had a chance to participate yet, I highly recommend jumping in, even if you are completely new to zero knowledge and cryptography. Speaking as someone who hadn't explored either one prior to ZK Hack, the background resources, events, and puzzle challenges provide a fantastic bootcamp.

Onwards to the puzzle!

## The Setup

You can get access the puzzle repo [here](https://github.com/kobigurk/zkhack-double-trouble). The puzzle description describes the setup for a new "zero-knowledge inner-product proof" and challenges us to recover the prover's secret $\vec{a}$.

Here it is for reference:

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 possibly 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
==================================================================================================

### Note about Fiat-Shamir
This proof description outlines an interactive proof between a prover and a verifier. However, we're told that the inner-product proof we'll be working with will be obtained by "applying the [Fiat-Shamir](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) transform", which will yield a non-interactive proof.

What this means in practice for us is that the "random challenge $\gamma$" sent by the verifier will instead be computed as a hash of the public parameters of the proof that have been shared prior to that point in the protocol (the $G_i, H, C_a, \vec{b}, C_r, C_1, C_2$).

In fact, reviewing the code shows that there's an available function called *challenge* that we can use to compute this. That means we don't need to worry about this and we can focus on the provided sigma protocol.

### Note about Terminology
In general, I've tried to stick to the terminology used in the written proof. When mapping the proof terminology to the variables in the code, note the following:

- $C_{x}$ becomes comm_x in all cases (e.g. $C_a$ becomes comm_a)
- the variables representing the elements used for randomness are renamed with respect to the vector for which they're providing randomness. ($\alpha$ becomes comm_a_rand, $\rho$ becomes comm_r_rand, etc)

## The challenge

According to the puzzle description, our mission is to recover the prover's secret $\vec{a}$.

However, looking at the code shows us the following assert statements:

assert_eq!(
        ck.commit_with_explicit_randomness(&a, comm_a_rand),
        instance1.comm_a
);
assert_eq!(
        ck.commit_with_explicit_randomness(&a, comm_a_rand),
        instance2.comm_a
);

So it looks like we'll need to recover both of the secret values used to create the Pedersen Commitment $C_a$: $\vec{a}$ and $\alpha$ (comm_a_rand). We'll use those to recreate the commitment and compare it to the commitment shared in each proof.

Although we'll eventually need to find $\alpha$, let's focus on $\vec{a}$ first.

## What do we know about $\vec{a}$?

Let's start by talking about what the proof tells us with respect to the secret $\vec{a}$ that we want to recover.

There are three public elements which use $\vec{a}$ in their computation. Let's look at each one.

1. $C_a = PedersenComm(\vec{a}; \alpha) = \sum_i (a_i * G_i) + α * H$

2. $C_1 = PedersenCOMM(<\vec{a}, \vec{b}>; τ) = \sum_i (a_i * b_i * G_i) + τ * H$

3. $\vec{s} = \vec{a} + γ\vec{r}$

Looking at these options, our most useful relation is going to be (3), since it's the only one which doesn't require us to solve the [discrete logarithm problem](https://en.wikipedia.org/wiki/Elliptic-curve_cryptography) in order to recover information. That problem is assumed to be hard (making it a key cryptographic assumption!), so let's ignore (1) and (2) to focus on (3) and think about what we need in order to make use of this equation.

### $\vec{a} = \vec{s} - \gamma * \vec{r}$

In the interactive version of the inner-product proof from the puzzle description, the verifier knows both $\gamma$ (their random challenge value from step 2) and $\vec{s}$ (provided by the prover in step 3). After Fiat-Shamir is used to transform the proof to a non-interactive one, $\gamma$ will be a hash of the proof's public data, so we'll be able to compute this.

That means the only thing missing before we can compute $\vec{a}$ is $\vec{r}$, the random vector used as the proof's [nonce](https://en.wikipedia.org/wiki/Cryptographic_nonce). How can we go about finding that?

## Finding $\vec{r}$

In the case of the puzzle, we actually have quite a bit to work with, because we have seen 2 proof instances, both of which were created using the same secret $\vec{a}$.

That means we now have 2 equations for a:

1. $\vec{a} = \vec{s_1} - γ_1 * \vec{r_1}$ ← this is what we know from proof1
2. $\vec{a} = \vec{s_2} - γ_2 * \vec{r_2}$ ← this is what we know from proof2

Subtracting the second from the first and moving things around a bit gives us:

$\vec{s_1}-\vec{s_2} = \gamma_1 * \vec{r_1} - \gamma_2 * \vec{r_2}$

Now if we can just find some kind of relation between $\vec{r_1}$ and $\vec{r_2}$ then we'll be able to solve for one of them and then plug it back into one of our equations to solve for $\vec{a}$.

(In fact, the end of Kobi Gurkan's [proof of knowledge soundness](https://gist.github.com/kobigurk/0e9904f5a2602c628f0d3b95bcf01ffb), which was shared as a hint, shows the extractor taking advantage of this exact thing, in the case where $\vec{r_1}$ and $\vec{r_2}$ are equal)

The best place to look for a relationship between $\vec{r_1}$ and $\vec{r_2}$ will be the public $C_r$ commitments.

## The Breakthrough: $2 * C_{r1} = C_{r2}$

It turns out that there is a relationship between the $C_r$ commitments of $\vec{r}$ in proof 1 and proof 2!

$C_r$ in proof 2 is double the value of $C_r$ in proof 1, as hinted at by the puzzle's name "Double Trouble".

This turns out to be enough to recover both the secret vector $\vec{a}$ *and* the randomness $\alpha$ that's used to create the Pedersen Commitment $C_a$!

Here's how we do it:

First, recall from the proof description that $C_r = \sum_i{r_i * G_i} + ρ * H$

This gives us the following relation:

$C_{r2} = 2 * C_{r1} = 2 * \sum_i{r_i * G_i} + 2 * ρ * H$

$G$ and $H$ are public group elements which are the same in both proof instances, so it looks like the $\vec{r}$ and $\rho$ in proof 2 were *both* double the $\vec{r}$ and $\rho$ in proof 1 respectively.

That gives us the relationship we were looking for to recover $\vec{r}$ as discussed above.

In fact, it's better than we were hoping for, because it also gives us enough to easily recover the randomness $\alpha$ used for $C_a$. To do that, we'll exploit the same idea we discussed with respect to $\vec{r}$, but using the equation for the public value $u := α + γρ$.

## Step By Step: from $\vec{r}$ to $\vec{a}$ and $\rho$ to $\alpha$

### Step 1: solve for $\vec{r}$

Recall the equation we found earlier: $\vec{s_1}-\vec{s_2} = \gamma_1 * \vec{r_1} - \gamma_2 * \vec{r_2}$

Let's plug in $2 * \vec{r_1}$ for $r_2$ and then solve for $\vec{r_1}$

$\vec{r_1} = (\vec{s_1} - \vec{s_2}) / (\gamma_1 - 2 * \gamma_2)$

And now in Rust:

We can get s directly from the response data structure in each of the provided proofs:

proof1.response.s
proof2.response.s

The puzzle code has a challenge function which we can use to compute our $\gamma$'s:

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

To finish solving, take advantage of the Arkworks library's *inverse()* and *double()* functions.

// Use the publicly known s vectors and the computed verifier challenges from proofs 1 and 2 to
// solve for the random vector r used in proof1
// Because comm_r1 * 2 = comm_r2, we know that r = (proof1.response.s - proof2.response.s) / (challenge1 - 2*challenge2)
fn solve_for_r(s1: Vec<Fr>, s2: Vec<Fr>, challenge1: Fr, challenge2: Fr) -> Vec<Fr> {
    // challenge1 - 2 * challenge2
    let challenge_diff = challenge1 - challenge2.double();
    let challenge_diff_inv = challenge_diff.inverse().unwrap();

    let mut r = Vec::with_capacity(s1.capacity());
    for (s1_num, s2_num) in s1.iter().zip(s2.iter()) {
        let s_diff_i = *s1_num - *s2_num;
        let r_i = s_diff_i * challenge_diff_inv;
        r.push(r_i);
    }

    // return r
    r
}

### Step 2: solve for $\vec{a}$

Now that we have $\vec{r}$, we can plug it back into our equation for $\vec{a}$

$\vec{a} = \vec{s} - \gamma * \vec{r}$

// Use the public s vector and the computed challenge from proof 1 along with our recovered r vector to
// solve for the secret vector a. We could also have done this using known values from proof 2 with double our recovered r
// a = proof1.response.s - challenge1 * r (or a = proof2.response.s - challenge2 * 2 * r)
fn solve_for_a(s1: Vec<Fr>, challenge1: Fr, r: Vec<Fr>) -> Vec<Fr> {
    let mut a = Vec::with_capacity(s1.capacity());

    for (s1_num, r_num) in s1.iter().zip(r.iter()) {
        let a_i = *s1_num - challenge1 * *r_num;
        a.push(a_i);
    }

    // return a
    a
}

### Step 3: solve for $\rho$

This will be just like solving for $\vec{r}$ except that this time we'll use the u values from each proof, along with both verifier challenge values ($\gamma$).

From the proof description we have $u := α + γρ$, so using the u values from each proof and our relationship $\rho_2 = 2 * \rho_1$ we can get:

$ρ_1 = (u_1 - u_2) / (\gamma_1 - 2 * \gamma_2)$

// Use the public elements u (computed & shared by prover in each proof) and the computed verifier challenges from proofs 1 and 2 to
// solve for ρ (the randomness used for comm_r in proof 1)
//  ρ = (proof1.response.u - proof2.response.u) / (challenge1 - 2 * challenge2)
fn solve_for_rho(u1: Fr, u2: Fr, challenge1: Fr, challenge2: Fr) -> Fr {
    let challenge_diff_inv = (challenge1 - challenge2.double()).inverse().unwrap();
    // return rho
    (u1 - u2) * challenge_diff_inv
}

### Step 4: solve for $\alpha$

Now get $\alpha$ by plugging our recovered $\rho$ back into the equation we used above, along with the challenge we've computed, and the public value of u.

$\alpha = u - \gamma\rho$

// Use the public scalar u and the computed verifier challenge along with our recovered rho value (comm_r_rand) from the first proof to
// solve for alpha, the randomness used in the commitment of our secret vector a
// alpha = proof1.response.u - challenge1 * rho1 (or alpha = u2 - challenge2 * rho2)
fn solve_for_alpha(u1: Fr, challenge1: Fr, rho1: Fr) -> Fr {
    // return alpha
    u1 - challenge1 * rho1
}

## Putting it all together

We can now put it all together to recover $\vec{a}$ and $\alpha$ and pass them into those assert functions we spotted in the beginning.

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

// STEP 1: USE s1, s2, challenge1, challenge2, TO SOLVE FOR r1
let r1: Vec<Fr> = solve_for_r(
    proof1.response.s.clone(),
    proof2.response.s.clone(),
    challenge1,
    challenge2,
);

// STEP 2: USE s1, challenge1, r1 TO SOLVE FOR a
let a: Vec<Fr> = solve_for_a(proof1.response.s.clone(), challenge1, r1);

// STEP 3: USE u1, u2, challenge1, challenge2 TO SOLVE FOR ρ1 (comm_r_rand)
let comm_r_rand: Fr =
    solve_for_rho(proof1.response.u, proof2.response.u, challenge1, challenge2);

// STEP 4: USE u, challenge1, comm_r_rand TO SOLVE FOR alpha
let comm_a_rand: Fr = solve_for_alpha(proof1.response.u, challenge1, comm_r_rand);

assert_eq!(
    ck.commit_with_explicit_randomness(&a, comm_a_rand),
    instance1.comm_a
);
assert_eq!(
    ck.commit_with_explicit_randomness(&a, comm_a_rand),
    instance2.comm_a
);

🎉 We've done it!