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.

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