Back

### Introduction

## See puzzle details on Github

Puzzle link
### The Puzzle Setup

### What Do We Know About \(\overrightarrow{a}\)?

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

### Finding \(\vec{r}\)

### The Breakthrough: \(2 * C_{r1} = C_{r2}\)

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

## Step 1: solve for \(\vec{r}\)

## Step 2: solve for \(\vec{a}\)

## Step 3: solve for \(\rho\)

## Step 4: solve for \(\alpha\)

### Putting it all together

Solution

by grjte

In order to be irreplaceable one must always be different.

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

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.

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?

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.

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 := α + γρ\).

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 }

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 }

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 }

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 }

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!