Back Solution

by grjte

In order to be irreplaceable one must always be different.

Introduction

This puzzle marks the halfway point of the incredibly fun learning experience that is ZK Hack. 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/or cryptography. Speaking as someone who had never explored either one prior to ZK Hack, the background resources, events, and puzzle challenges provide a fantastic bootcamp.
Onwards to the puzzle!
The background materials for this puzzle are linked below.

See puzzle details on Github

The Puzzle Setup

The puzzle describes the setup for a new "zero-knowledge inner-product proof" and challenges us to recover the prover's secret $$\overrightarrow{a}$$. The proof description outlines an interactive proof between a prover and a verifier. However, we're told that the inner-product proof we will be working with will be obtained by "applying the Fiat-Shamir transform".

What this means in practice 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. In fact, reviewing the code shows that there's an available function we can use to compute this. So that means we don't need to worry about this part too much (although it's worth learning), and we can focus on the provided description of the sigma protocol.

Terminology note: In general, I'm sticking to the terminology used in the written proof from the problem description. 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_r$$, $$C_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.

According to the puzzle description, our mission is to recover the prover's secret $$\overrightarrow{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:\overrightarrow{a}$$ and $$\alpha$$ (comm_a_rand). T hen we'll use those to recreate the commitment and compare it to the commitment used in each proof. Although we'll eventually need to find $$\alpha$$, let's focus on $$\overrightarrow{a}$$ first.

What Do We Know About $$\overrightarrow{a}$$?

Let's start by talking about what the proof tells us with respect to the secret $$\overrightarrow{a}$$ that we want to recover. There are three public elements which use $$\overrightarrow{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 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 calculate 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. 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 the proof of knowledge soundness 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 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 what we were looking for so we can 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 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 (this was supposed to be a secret nonce!)
// 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:

$$ρ = (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!