---
# System prepended metadata

title: ZKHack - Puzzle 3

---

# ZKHack - Puzzle 3

Michael Adjedj aka ZeroFearSyndrom

URL: https://www.zkhack.dev/puzzle3.html
GitHub Repo: https://github.com/kobigurk/zkhack-double-trouble

----------------------

## First run
Running the Rust package with
```
cargo run --release
```
gives the following messages: 
```
    ______ _   __  _   _            _
    |___  /| | / / | | | |          | |
       / / | |/ /  | |_| | __ _  ___| | __
      / /  |    \  |  _  |/ _` |/ __| |/ /
    ./ /___| |\  \ | | | | (_| | (__|   <
    \_____/\_| \_/ \_| |_/\__,_|\___|_|\_\
    

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

The goal of this new challenge is to recover the hidden, committed vector `a = a0, ..., a7` of scalars, and the binding scalar `α`.

## Code analysis

### Files and flow
Let's dive a bit into what the code does. It consists in few files:
```
├── src
│   ├── bin
│   │   └── verify-double-trouble.rs
│   ├── data.rs
│   ├── inner_product_argument
│   │   ├── data_structures.rs
│   │   └── utils.rs
│   ├── inner_product_argument.rs
│   └── lib.rs
```

The main function is the following:
```rust
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 (a, comm_a_rand): (Vec<Fr>, Fr) = {
        // Your solution here!
        todo!()
    };
    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
    );
}
```

The lines 
```rust
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; 
```
import the data contained in the following constants `COMMIT_KEY_BYTES` and `INSTANCE_AND_PROOF_BYTES` defined in the `src/data.rs` file. `COMMIT_KEY_BYTES` is the concatenation of the points `G_i` and `H`, while `INSTANCE_AND_PROOF_BYTES` contains the transcripts of two proofs, `base64` encoded.

### Extracting Data: Parsing elements from proofs and instances

To work on the challenge, I needed to extract all the data, which I will then import into another tool (PARI-GP: https://pari.math.u-bordeaux.fr/ or `apt install pari-gp`).
To do so, I just added the following lines in the main function (and sometimes had to add the default `Display` or `Debug` traits to some structures):
```rust
    println!("/* Generators */");
    print!("Gi = "); print_vector(&ck.generators);
    print!("H = {};", ck.hiding_generator);

    println!("Len of generators: {}", ck.generators.len());
    let (a1, b1) = (instance1.comm_a.clone(), instance1.b.clone());
    let (a2, b2) = (instance2.comm_a.clone(), instance2.b.clone());
    println!("instances values: ");
    print!("Instance 1: a {} / b ", a1.to_string());
    print_vector(&b1);

    print!("Instance 2: a {} / b ", a2.to_string());
    print_vector(&b2);

    let (Cr1, Cr2) = (proof1.commitment.comm_r, proof2.commitment.comm_r);
    println!("Cr values: ");
    print!("Cr1: {}", Cr1);
    print!("Cr2: {}", Cr2);

    let (C11, C12) = (proof1.commitment.comm_1, proof2.commitment.comm_1);
    println!("C1 values: ");
    println!("C11: {}", C11);
    println!("C12: {}", C12);

    let (C21, C22) = (proof1.commitment.comm_2, proof2.commitment.comm_2);
    println!("C2 values: ");
    println!("C21: {}", C21);
    println!("C22: {}", C22);

    let (s1, s2) = (proof1.response.s, proof2.response.s);
    println!("s values: ");
    print!("s1 = "); print_vector(&s1);
    print!("s2 = "); print_vector(&s2);

    let (u1, u2) = (proof1.response.u, proof2.response.u);
    println!("/* u values: */");
    println!("u1= {};", u1);
    println!("u2= {};", u2);

    let (t1, t2) = (proof1.response.t, proof2.response.t);
    println!("/* t values: */");
    println!("t1= {};", t1);
    println!("t2= {};", t2);
```

The challenge description also says that the sigma protocol described is instanciated using the Fiat-Shamir transform. The random challenge `γ` is in this case derived from the previous exchanged data.
A quick look into `src/inner_product_argument.rs:prove()` function tells me that it's computed by a call to the following function:
```rust
pub fn challenge(ck: &CommitKey, instance: &Instance, proof_comm: &ProofCommitment) -> Fr
```

Computing the random challenges from the two executions of the proving algorithm is done via:
```rust
    let (gamma1, gamma2) = (
        challenge(&ck, &instance1, &proof1.commitment),
        challenge(&ck, &instance2, &proof2.commitment)
    );
    println!("gamma values: ");
    println!("gamma1: {}", gamma1);
    println!("gamma2: {}", gamma2);
```

Everything is now extracted. Let's break it!

## Breaking the Challenge

### Getting the Curve Parameters

Getting the curve parameters was easy, since the documentation of the `Arkwork` package gives them:
```rust
//! Curve information:
//! * Base field: q = 52435875175126190479447740508185965837690552500527637822603658699938581184513
//! * Scalar field: r = 6554484396890773809930967563523245729705921265872317281365359162392183254199
//! * Valuation(q - 1, 2) = 32
//! * Valuation(r - 1, 2) = 1
//! * Curve equation: ax^2 + y^2 =1 + dx^2y^2, where
//!    * a = -1
//!    * d = -(10240/10241)
```
To use it in my favorite computer algebra system, I had to translate it into its Weierstrass form, and to be able to import points in this representation.
Luckily, I found this script: https://github.com/zhenfeizhang/bandersnatch/blob/main/bandersnatch/script/bandersnatch.sage
I extracted a simple function to convert from Twisted Edward to Weierstrass any point on the curve:
```
te_to_w(P) = {
	my([Px, Py] = P, Mx, My, Wx, Wy);
	Mx = (1+Py)/(1-Py);
	My = Mx/Px;
	Wx = Mx/MB + MA/3/MB;
	Wy = My/MB;
	return ([Wx, Wy])
}
```

### Exhbiting relations between transcripts.

I now got the following points `Gi, H, Cr1, Cr2, C11, C12, C21, C22` from the proofs, and the following instances: `Ca1, Ca2, b1, b2`.
```
Ca1 = te_to_w([0x6AE271E04FBB0AE9FB89506FF7180F5C06A8D60F802D934987965F694228BF8A, 0x2BFBFA9CCF2151F01E71A069366DAD9398960B64684888D1AABB50D4D57BDF32]);
Ca2 = te_to_w([0x6AE271E04FBB0AE9FB89506FF7180F5C06A8D60F802D934987965F694228BF8A, 0x2BFBFA9CCF2151F01E71A069366DAD9398960B64684888D1AABB50D4D57BDF32]);

b1 = [0x08180E66A534AADEBC88D09E1397DC7C33E2014115EB973B489E7D5CDBF839CD, 0x036AFB822FAC04AC9191CCEEF5BF4E27ADA6DC0440C88ECF3E06DC2FAFB162E6, 0x0DE7FE23DCF79F2A041E2C21876F9B9AEB3F2BC628E07B87F52DF460408334F2, 0x0891BBE1E3DA5717F7ED59288C9F51186E7BBAE018C9DA56F4BC8B4BBBD7457E, 0x05D81F4C416350A3D02B1685176BFE5A98FA15D51C84DBD47680326F9F005E96, 0x06D5E58667508A24F3A3FFBB244575DE29ECB3408D6EBC6D3DCDEFF02AA9453C, 0x06BC47A67C6BD353EE624051B4C4A6A28E7F8CEDB6ED65A007D897AC071CBDCB, 0x0CF6D9D35E0B6F2309568E5BB7C19448D993D2EFFEF7B3D77C137A26C524315A];
b2 = [0x08180E66A534AADEBC88D09E1397DC7C33E2014115EB973B489E7D5CDBF839CD, 0x036AFB822FAC04AC9191CCEEF5BF4E27ADA6DC0440C88ECF3E06DC2FAFB162E6, 0x0DE7FE23DCF79F2A041E2C21876F9B9AEB3F2BC628E07B87F52DF460408334F2, 0x0891BBE1E3DA5717F7ED59288C9F51186E7BBAE018C9DA56F4BC8B4BBBD7457E, 0x05D81F4C416350A3D02B1685176BFE5A98FA15D51C84DBD47680326F9F005E96, 0x06D5E58667508A24F3A3FFBB244575DE29ECB3408D6EBC6D3DCDEFF02AA9453C, 0x06BC47A67C6BD353EE624051B4C4A6A28E7F8CEDB6ED65A007D897AC071CBDCB, 0x0CF6D9D35E0B6F2309568E5BB7C19448D993D2EFFEF7B3D77C137A26C524315A];
```

A quick look tells us that they are equal. Meaning that the two proofs were using the same instances variables `ai, b, α`.

Let's see if we have trivial relations between points. Obviously, `Gi` and `H` are derived from a string and a hash function, so it's very unlikely that there exists a trivial relation between them.

Let's see if we can find a relation between `Cr1, Cr2`, `C11, C12` and `C21, C22`. It finally appear that the following relation holds `Cr2 = [2]Cr1`.
Recall that `Cr = sum_i (r_i * G_i) + ρH`. Since we can assume there is no trivial relation between `Gi` and `H`, we have:
```
                  | r2_i = 2 * r1_i (1)
Cr2 = [2]Cr1 <=>  |
                  | ρ2 = 2*ρ1`      (2)
```

### Solving it
Combining the equation `s := a + γr` with (1) we have:
```
s1 := a + γ1r1
s2 := a + γ2r2   =>  s1 - s2 = γ1r1 - γ2r2
                 =>  s1 - s2 = γ1r1 - 2*γ2*r1  // since r2 = 2 * r1
                 =>  r1 = (s1 - s2) / (γ1 - 2*γ2)
```
I got 
```
r1 = [4455526514920697353590091917468006060382082423912754007959838457062205031897, 5137463897763692896670918241275300821488771020231365993414762794848631959336, 5827436134036754496515006574145521884012453032765085533400923541721681377083, 107637658748812129461584697230022445607773907303888512155409473648490707157, 6097003273278321075526694728587224938275119471601054388709301624563062034294, 1945883547590986497495001993441568047421980313075975139274713220780333549190, 1249124886120477656867674624038930393218735409381338212733155710627503085604, 4148873330630903456478107752654028471706157241016846994349779645350740283927]
r2 = [2356568632950620897249216271412766391058243581953190734554317751732226809595, 3720443398636611983410868919027355913271620774590414705464166427305080664473, 5100387871182735183099045584767798038318984799657853785436487921051179499967, 215275317497624258923169394460044891215547814607777024310818947296981414314, 5639522149665868341122421893651204146844317677329791496053244086733940814389, 3891767095181972994990003986883136094843960626151950278549426441560667098380, 2498249772240955313735349248077860786437470818762676425466311421255006171208, 1743262264371033103025247941784811213706393216161376707334200128309297313655]
```
From now on, getting `a` is easy, using `a = s1 - γ1r1`
```
a = [2336706075964247989947433674548942226827306841875429968112509828215618329159, 3183796673245796636687562422863836804215466330278309281736435087784983849340, 5178612562806274700109127208151001095511383281260239557723446192273548168238, 2176409113060157430684277991899328451416352041675746388298954703991743482874, 5310968795039368315853267802615936582862130677392677794847104969389960514693, 5806564767929688700136171453700501428844225212575251330189050251826120035765, 1006011101679865533947259717866832372946407201677415593630279116718161273337, 1648764725587973804015859780978773015249711523441957090043447269437062523478]
```

Getting `α` is now easily achieved combining the equation `u := α + γρ` with (2):
```
u1 := α + γ1ρ1
u2 := α + γ2ρ2   =>  u1 - u2 = γ1ρ1 - γ2ρ2
                 =>  u1 - u2 = γ1ρ1 - 2*γ2*ρ2  // since ρ2 = 2 * ρ1
                 =>  ρ1 = (u1 - u2) / (γ1 - 2*γ2)
                 =>  α  = u1 - γ1ρ1
```

It finally gives the value `α = 1617264654250654530393647253572292035968664667634001469351271665735252350260`

Replacing the computed values of `a` and `α` into the main function confirmed the value were correct! 
Cheers !
