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