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